17、静态链表

  1 /*大话数据结构----3.12线性表的静态存储结构*/
  2 
  3 #include<stdio.h>
  4 #include<stdlib.h>
  5 #include<string.h>
  6 
  7 #define MAXSIZE 1000   //假设链表的最大长度是1000
  8 #define OK 1
  9 #define ERROR 0
 10 #define TRUE 1
 11 #define FALSE 0
 12 typedef int ElemType;//根据实际情况而定，这里假设为int
 13 typedef int Status;//函数类型，其值是函数结果代码，如OK等
 14 
 15 
 16 //定义结构体
 17 typedef struct {
 18     ElemType data;
 19     int cur;//游标（Cursor），为0时无指向
 20 }Component,StaticLinkList[MAXSIZE];
 21 
 22 /*
 23 初始化，将一维数组space中各分量链成一备用链表
 24 space[0].cur为头指针，"0"表示空指针
 25 */
 26 Status InitList(StaticLinkList space) {
 27     int i;
 28     for (i = 0; i < MAXSIZE; i++) {
 29         space[i].cur = i + 1;
 30     }
 31     space[MAXSIZE - 1].cur = 0;//目前静态链表为空，最后一个元素的cur为0
 32     return OK;
 33 }
 34 //数组长度
 35 int ListLength(StaticLinkList L) {
 36     int j = 0;
 37     int i = L[MAXSIZE - 1].cur;
 38     while (i) {
 39         i = L[i].cur;
 40         j++;
 41     }
 42     return j;
 43 }
 44 /*静态链表的插入
 45 静态链表中操作的是数组，需要自己实现申请和释放两个函数，才能做插入和删除操作
 46 将所有未被使用过的及已被删除的分量用游标链成一个备用的链表，每当进行插入时，
 47 便可以从备用链表上取得第一个结点作为待插入的新结点
 48 */
 49 
 50 //若备用链表非空，则返回分配的结点下标，否则返回0
 51 int Malloc_SLL(StaticLinkList space) {
 52     int i = space[0].cur;//当前数组第一个元素的cur存下的值
 53     //就是要返回的第一个备用空闲的下标
 54     if (space[0].cur) {
 55         space[0].cur = space[i].cur;//
 56         //由于要拿出一个分量来使用了，所以我们就得把它的下一个分量拿来备用
 57     }
 58     return i;
 59 }
 60 //插入函数：在L中的第i个元素之前插入新的数据元素e
 61 Status Insert_StaticLinkList(StaticLinkList L, int i, ElemType e) {
 62     int j, k, l;
 63     k = MAXSIZE - 1;//注意k首先是最后一个元素的下标
 64     if (i<1 || i>ListLength(L) + 1) {
 65         return ERROR;
 66     }
 67     j = Malloc_SLL(L);//获得空闲分量的下标
 68     if (j) {
 69         L[j].data = e;//将数据赋值给此分量的data
 70         for (l = 1; l <= i - 1; l++) {//找到第i个元素的位置
 71             k = L[k].cur;
 72         }
 73         L[j].cur = L[k].cur;//把第i 个元素之前的cur赋值给新元素的cur
 74         L[k].cur = j;//把新元素的下标赋值给第i个元素之前元素的cur
 75         return OK;
 76     }
 77     return ERROR;
 78 }
 79 //删除操作：free
 80 //将下标为k的空闲结点回收到备用链表
 81 void Free_SLL(StaticLinkList space, int k) {
 82     space[k].cur = space[0].cur;//把第一个元素cur值给要删除的分量cur
 83     space[0].cur = k;//把要删除的分量下标赋值给第一个元素的cur
 84 }
 85 //删除在L中的第i个元素e
 86 Status Delete_StaticLinkList(StaticLinkList L, int i) {
 87     int j, k;
 88     if (i<1 || i>ListLength(L)) {
 89         return ERROR;
 90     }
 91     k = MAXSIZE - 1;
 92     for (j = 1; j <= i - 1; j++) {
 93         k = L[k].cur;
 94     }
 95     j = L[k].cur;
 96     L[k].cur = L[j].cur;
 97     Free_SLL(L, j);
 98     return OK;
 99 }
100 
101 //获得元素操作：用e返回L中第i个元素的值
102 Status GetElem(StaticLinkList L, int i, ElemType *e) {
103     if (ListLength(L) == 0 || i<1 || i>ListLength(L)) {
104         return ERROR;
105     }
106     *e = L[i].data;
107     return OK;
108 }
109 //打印
110 void Print_StaticLinkList(StaticLinkList L) {
111 
112     int i, j;
113     j = L[MAXSIZE-1].cur;
114     for (i=0; i < ListLength(L); i++) {
115         printf("%d ", L[j].data);
116         j = L[j].cur;
117     }
118     printf("
");
119 }
120 
121 
122 int main()
123 {
124     StaticLinkList M;
125     int n[] = { 12,34,45,56,23,56,78,98 };
126     //初始化
127     InitList(M);
128 
129     //插入数据
130     for (int i = 0; i < 8;i++)
131     Insert_StaticLinkList(M, 1, n[i]);
132 
133     //打印
134     printf("链表长度：%d 
", ListLength(M));
135     Print_StaticLinkList(M);
136 
137     //删除
138     Delete_StaticLinkList(M, 3);
139 
140     //打印
141     printf("删除后链表长度：%d 
", ListLength(M));
142     Print_StaticLinkList(M);
143 
144     printf("
");
145     system("pause");
146     return 0;
147 }
运行结果：