众所周知，我的博客是写给自己看的。
在敲"严版"数据结构的静态数组时遇到的一些问题，并给予了改进，在此记录一下
前言：
没有实现教材上那个(A-B)v(B-A)的例子，实现了增加、删除等。总体上把握了静态数组的基本思想后实现这些例子都是很简单的。作了一点小改进
正文：
改进：
把一个静态数组分为两条形式上的链表，一条是已分配空间，一条是未分配的空间。从尾部开始，链表的头标记为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 }
总结：
其它的就难得写了，静态数组思想大概就是这样。"严版"数据结构书上这一节写得云里雾里的，不仔细看和操练不容易搞出来。
注意声明结构体数组不同，引用结构体成员的方式也不同；
在懂得算法思想的基础上改进、创新代码。