c语言数据结构,静态链表,结构体数组

众所周知,我的博客是写给自己看的。

 

在敲"严版"数据结构的静态数组时遇到的一些问题,并给予了改进,在此记录一下

 

前言:

没有实现教材上那个(A-B)v(B-A)的例子,实现了增加、删除等。总体上把握了静态数组的基本思想后实现这些例子都是很简单的。作了一点小改进

 

正文:

     改进:

c语言数据结构,静态链表,结构体数组

把一个静态数组分为两条形式上的链表,一条是已分配空间,一条是未分配的空间。从尾部开始,链表的头标记为arr[10].cur遍历可获得A-B-C-D,arr[10].data为已分配结点的数量;arr[0].cur是未分配空间的头标记,arr[0].data为未分配结点的数量;插入一个结点就把可用空间的结点通过改变cur来实现连接,删除也是同样的思想。

 

静态数组,其实就是顺序表。依靠结构体成员,像链表一样把不同的空间连起来,只不过把指针类型的成员变量用int类型代替。

下面是结构体:

1 int LISTSIZE = 100;
2 typedef int ElemType;
3 typedef struct SLinkList {
4   ElemType data;
5   int cur;
6 } SLinkList;

// 不建议
1 int LISTSIZE = 100; 2 typedef int ElemType; 3 typedef struct SLinkList { 4 ElemType data; 5 int cur; 6 } SLinkList[LISTSIZE];

1)、设置一个全局变量LISTSIZE代替书上的宏变量,方便在数组空间不够用的情况下新增空间

2)、typedef这个结构体变量名为SLlinkList。如果你typedef这个结构体变量为SLinkList[LISTSIZE]要注意了,这样做有许多的缺点,会让你走许多的弯路。

  1.减少了灵活性,声明这个变量SLinkList L;这样就固定了100个空间的大小,你想申请200是不可能的;而typedef为SLinkList,声明这个变量时SLinkList L[345];这样是很灵活的。

  2.把访问结构体成员弄得很复杂,熟悉c就会知道指针需要用"->"访问、变量需要用"."访问,通过形参传地址修改必须要用*p。而c基础不过关的(比如说我)就会犯错误如结构体声明为typedef SLinkList[100]; SLinkList L; L[i]->data;这样访问,这是错误的访问方法,除了静态数组第一个也就是L[0]可以修改外,其他元素修改不了。正确的访问方式是先*L访问首地址,然后(*L+i)加上偏移量找到指定空间,这是一个指针,然后(*L+i)->data这才是正确的访问方式。

 

分配地址空间:malloc分配或者变量自动分配

1 SLinkList *L = (SLinkList *)malloc(sizeof(SLinkList) * LISTSIZE);
2 或者
3 SLinkList L[LISTSIZE];

代码:

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4 #include "..\custom.h"
  5 #include "..\test.c"
  6 
  7 /**
  8  * 静态链表,使用index的相对位置作为指针,方便在不设指针类型的程序中使用链表结构
  9  * 预先需要分配较大的数组空间
 10  * 说白了就是链表,只不过是片连续的地址空间
 11  */
 12 int LISTSIZE = 100;
 13 typedef int ElemType;
 14 typedef struct SLinkList {
 15   ElemType data;
 16   int cur;
 17 } SLinkList;
 18 
 19 /**
 20  * 初始化
 21  */
 22 void initSLinkList(SLinkList *L) {
 23   // L[0]->data保存未分配数组的长度,不包括第一个和最后一个
 24   for (int i = 0; i < LISTSIZE - 1; i++) {
 25     L[i].cur = i + 1;
 26   }
 27   L[0].data = LISTSIZE - 2;
 28   // L[LISTSIZE].cur分配了的结点的首地址,L[LISTSIZE].data保存分配了的长度
 29   L[LISTSIZE - 1].cur = 0;
 30   L[LISTSIZE - 1].data = 0;
 31 }
 32 
 33 /**
 34  * 遍历L
 35  */
 36 void traverseSLinkList(SLinkList *L) {
 37   if (L[LISTSIZE - 1].data == 0) return;
 38   int i = L[LISTSIZE - 1].cur;
 39   while (i != 0) {
 40     printf("%d\t", L[i].data);
 41     i = L[i].cur;  // 类似于p=p->next
 42   }
 43   printf("\n");
 44 }
 45 
 46 /**
 47  * 在第i个位置插入e
 48  */
 49 int listInsert(SLinkList *L, int i, ElemType e) {
 50   if (L[0].data == 0) {
 51     // L[0].data==0表明未分配的空间已经用完,重新分配一个空间
 52     printf("空间不足");
 53     return 0;
 54   }
 55   if (i > L[LISTSIZE - 1].data + 1) {
 56     printf("位置i不合法");
 57     return 0;
 58   }
 59   // 在未分配空间的L拿出一个空间来, 就拿第一个
 60   int index = L[0].cur;
 61   L[0].cur = L[index].cur;
 62 
 63   L[index].data = e;  // 为这个空间赋值
 64 
 65   // 找已分配链表的第i个位置
 66   int k = LISTSIZE - 1;
 67   for (int j = 0; j < i; j++) {
 68     k = L[k].cur;
 69   }
 70   L[index].cur = L[k].cur;  // 连接
 71   L[k].cur = index;
 72 
 73   L[0].data--;             // 用掉一个结点
 74   L[LISTSIZE - 1].data++;  // 增加一个分配了的结点
 75   return 1;
 76 }
 77 
 78 /**
 79  * 删除一个元素
 80  */
 81 int listDelete(SLinkList *L, int i, ElemType *e) {
 82   if (L[LISTSIZE - 1].data == 0) return 0;
 83   // 找到第i个位置
 84   int k = LISTSIZE - 1;
 85   for (int j = 0; j < i; j++) {
 86     k = L[k].cur;
 87   }
 88   int index = L[k].cur;
 89   L[k].cur = L[index].cur;
 90 
 91   *e = L[index].data;  // 赋值
 92 
 93   // 加入空闲的链表
 94   L[index].cur = L[0].cur;
 95   L[0].cur = index;
 96 
 97   L[0].data++;             // 增加一个未分配结点
 98   L[LISTSIZE - 1].data--;  // 减少一个分配了的结点
 99   return 1;
100 }
101 
102 /**
103  * 测试
104  */
105 void createList(SLinkList *L) {
106   initSLinkList(L);
107   for (int i = 0; i < 10; i++) {
108     listInsert(L, i, i * 111);
109   }
110 }
111 int main() {
112   SLinkList *L = (SLinkList *)malloc(sizeof(SLinkList) * LISTSIZE);
113   createList(L);
114   traverseSLinkList(L);
115   printf("空间总长度%d\n", LISTSIZE);
116   printf("已用空间长度%d\n", L[LISTSIZE - 1].data);
117   printf("未用空间长度%d\n", L[0].data);
118   ElemType e;
119   listDelete(L, 2, &e);
120   printf("e:%d\n", e);
121   listInsert(L, 1, 5);
122   traverseSLinkList(L);
123   printf("空间总长度%d\n", LISTSIZE);
124   printf("已用空间长度%d\n", L[LISTSIZE - 1].data);
125   printf("未用空间长度%d\n", L[0].data);
126   return 0;
127 }

 

总结:

其它的就难得写了,静态数组思想大概就是这样。"严版"数据结构书上这一节写得云里雾里的,不仔细看和操练不容易搞出来。

注意声明结构体数组不同,引用结构体成员的方式也不同;

在懂得算法思想的基础上改进、创新代码。

上一篇:【Redis语法】01 Redis基本命令


下一篇:从零开始学VUE之VueX(抽取方法为常量形式)