静态链表的概念:
由于一些语言, 如Basic, Fortran等早期的编程高级语言没有指针, 像链式存储结构快速的删除,插入操作而无法完成.
所以就有人想出了数组代替指针.
首先让数组的元素都是由两个数据域组成, data与cur. 也就是说, 数组的每个下标都对应一个data和一个cur. 数据域data,用来储存数据元素, 而游标的cur相当于单链表的next指针, 存放该元素的后继在数组中的下标.
许多书有关静态链表的描述和代码发现都没有判断是否还有剩余空间,于是自己写了一个.
Malloc_SL()函数里添加了是否还有剩余空间的判断.
输出结果:
即:
静态链表有效空间为 MAXSIZE-2 (除去 第一个位置(L[0].cur指向空余空间]) 和 最后一个位置(L[MAXSIZE-1].cur指向第一个结点))
1 #include <stdio.h> //Anjaxs
2 #include <stdbool.h>
3 #define MAXSIZE 7
4 typedef int ElemType;
5
6 typedef struct{
7 ElemType data;
8 int cur;
9 }StaticList;
10
11 int Malloc_SL(StaticList * space);
12 void Free_SL(StaticList * space, int k);
13 void InitList(StaticList * space);
14 bool ListInsert(StaticList * L, int i, ElemType e);
15 bool ListDelete(StaticList * L, int i);
16 int ListLength(StaticList * L);
17 void show(StaticList * L);
18
19
20 int main()
21 {
22 int i;
23 int choice;
24 StaticList L[MAXSIZE];
25 InitList(L);
26 printf("1:插入 2:删除 3:输出 0:退出\n");
27 while (scanf("%d",&choice) && choice!=0)
28 {
29 int x;
30 int pos;
31 switch (choice)
32 {
33 case 1:
34 printf("输入要插入的数字和位置\n");
35 scanf("%d %d", &x, &pos);
36 ListInsert(L, pos, x);
37 break;
38 case 2:
39 printf("输入要删除的位置\n");
40 scanf("%d",&pos);
41 ListDelete(L, pos);
42 break;
43 case 3:
44 show(L);
45 break;
46 default:
47 printf("请输入1-3.\n");
48 break;
49 }
50 printf("1:插入 2:删除 3:输出 0:退出\n");
51 }
52
53 return 0;
54 }
55
56
57 void InitList(StaticList *space)
58 {
59 int i;
60 //space[0].cur为指向第一个空闲位置的指针
61 //space[MAXSIZE-1].cur为头指针
62 for (i = 0; i < MAXSIZE-1; ++i){
63 space[i].data = 0;
64 space[i].cur = i+1;
65 }
66 //目前静态链表为空，最后一个元素的cur为0
67 space[MAXSIZE-1].cur = 0;
68 space[MAXSIZE-1].data = 0;
69 }
70
71 bool ListInsert(StaticList *L, int i, ElemType e)
72 {
73 int j, k, l;
74 k = MAXSIZE-1;
75 if (i < 1 || i > ListLength(L)+1){
76 printf("请输入合法的位置。\n");
77 return false;
78 }
79
80 j = Malloc_SL(L);
81 if (j){
82 L[j].data = e;
83 for (l = 1; l <= i-1; ++l)
84 k = L[k].cur;
85 L[j].cur = L[k].cur;
86 L[k].cur = j;
87 return true;
88 }else{
89 //返回0则代表没有剩余空间
90 printf("没有空闲空间了。\n");
91 return false;
92 }
93 }
94
95 bool ListDelete(StaticList * L, int i)
96 {
97 int j, k;
98 if (i < 1 || i > ListLength(L)){
99 printf("请输入合法的位置。\n");
100 return false;
101 }
102 k = MAXSIZE-1;
103 for (j = 1; j <= i-1; ++j)
104 k = L[k].cur;
105 j = L[k].cur;
106 L[k].cur = L[j].cur;
107 Free_SL(L,j);
108 return true;
109 }
110
111 int ListLength(StaticList * L)
112 {
113 int j = 0;
114 int i = L[MAXSIZE-1].cur;
115 while (i)
116 {
117 i = L[i].cur;
118 j++;
119 }
120
121 return j;
122 }
123
124 int Malloc_SL(StaticList * space)
125 {
126 //返回第一个备用空闲的下标
127 int i = space[0].cur;
128
129 if (space[0].cur != MAXSIZE-1){
130 space[0].cur = space[i].cur;
131 return i;
132 }
133 else{
134 /*当(指向空余空间的指针) 指向 (指向头结点的指针) 时代表静态链表已满*/
135 return 0;
136 }
137 }
138
139 void Free_SL(StaticList * space, int k)
140 {
141 space[k].cur = space[0].cur;
142 space[0].cur = k;
143 }
144
145 void show(StaticList * L)
146 {
147 int i;
148