线性表的链式存储结构（C语言实现）

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 #define OK 1
  5 #define ERR 2
  6 #define TRUE 1
  7 #define FALSE 0
  8 
  9 typedef int status; //定义函数返回的状态，OK & ERR
 10 typedef char datatype; //定义线性表中每个结点的数据类型，这里暂定为字符型
 11 
 12 typedef struct LinkList_anon{
 13     datatype data; //数据区
 14     struct LinkList_anon * next; //指针区
 15 } LinkList;
 16 
 17 /* 函数原型，线性表的基本操作 */
 18 LinkList *createLinkList(datatype first_node_value);
 19 status isEmpty(LinkList *L);
 20 void clear(LinkList **L);
 21 int getLength(LinkList *L);
 22 int locateNode(LinkList *L,datatype node_to_locate);
 23 datatype getNode(LinkList *L, int index);
 24 status insert(LinkList **L, int index, datatype node_to_insert);
 25 status delete(LinkList **L, int index);
 26 void showList(LinkList *L);
 27 
 28 int main(){
 29     /* 测试 */
 30     LinkList *root; //指向线性表
 31     root=createLinkList(‘A‘); //创建一个线性表
 32     printf("Length = %d\n",getLength(root)); //打印线性表的当前长度
 33     printf("isEmpty = %d\n",isEmpty(root)); //打印线性表是否为空
 34     insert(&root,0,‘B‘); //头插法插入2个结点
 35     insert(&root,0,‘C‘);
 36     printf("Length = %d\n",getLength(root));
 37     printf("isEmpty = %d\n",isEmpty(root));
 38     showList(root);
 39     putchar(‘\n‘);
 40     insert(&root,getLength(root),‘D‘); //尾插法插入2个结点
 41     insert(&root,getLength(root),‘E‘); //尾插法插入2个结点
 42     printf("Length = %d\n",getLength(root));
 43     printf("isEmpty = %d\n",isEmpty(root));
 44     showList(root);
 45     putchar(‘\n‘);
 46     insert(&root,1,‘F‘); //在index=1（第2个结点）插入新结点
 47     insert(&root,2,‘G‘); //在index=2（第3个结点）插入新节点
 48     insert(&root,2,‘H‘); //在index=2（第3个结点）插入新节点
 49     printf("Length = %d\n",getLength(root));
 50     printf("isEmpty = %d\n",isEmpty(root));
 51     showList(root); //打印线性表
 52     putchar(‘\n‘);
 53     delete(&root,0); //删除头结点
 54     showList(root);
 55     putchar(‘\n‘);
 56     delete(&root,getLength(root)-1); //删除尾结点
 57     showList(root);
 58     putchar(‘\n‘);
 59     delete(&root,3); //删除index=3（第4个）结点
 60     showList(root);
 61     putchar(‘\n‘);
 62     printf("Locate = %d\n",locateNode(root,‘A‘)); //打印查找到的结点的位置
 63     printf("getNode = %c\n",getNode(root,1)); //打印下标是1的结点的值
 64     clear(&root); //清空线性表
 65     printf("isEmpty = %d",isEmpty(root));
 66 
 67     return 0;
 68 }
 69 
 70 LinkList *createLinkList(datatype first_node_value){
 71     LinkList *tmp;
 72     tmp=malloc(sizeof(LinkList));//void*类型指针能自动转为其他类型的指针
 73     tmp->data=first_node_value; //初始化头指针的数据区
 74     tmp->next=NULL; //初始化头结点的指针区
 75     return tmp;
 76 }
 77 status isEmpty(LinkList *L){
 78     if (L==NULL)
 79         return TRUE; //链表为空返回TRUE
 80     else
 81         return FALSE; //链表不为空返回FALSE
 82 }
 83 void clear(LinkList **L){
 84     if (isEmpty(*L)==FALSE){
 85         //不为空时才执行删除
 86         LinkList * p,* q; //p始终指向当前要被删除的结点，而q始终指向要被删除的结点的下一个
 87         p=*L; //将p指向线性表的头结点
 88         while (p!=NULL){
 89             //p不是NULL就继续循环
 90             q=p->next; //q始终指向下一个结点
 91             free(p); //释放p所指的结点
 92             p=q; //交换
 93         }
 94         (*L)->next=NULL; //将头结点的指针区置空
 95         *L=NULL; //将指向线性表的指针设为NULL
 96     }
 97 }
 98 int getLength(LinkList *L){
 99     int i=0;
100     LinkList * p=L;
101     if (isEmpty(L)==TRUE) return 0;
102     while (p){
103         i++;
104         p=p->next;
105     }
106     return i;
107 }
108 int locateNode(LinkList *L, datatype node_to_locate){
109     //返回找到的结点的index
110     //node_to_locate应当是能唯一标识一个结点的数据，否则只返回匹配的第一个结点
111     int i;
112     int total=getLength(L);
113     LinkList * p=L;
114     for (i=0; i<total; i++){
115         if (p->data==node_to_locate)
116             return i;
117         else
118             p=p->next;
119     }
120     return -1; //未找到任何匹配
121 }
122 datatype getNode(LinkList *L, int index){
123     //index表示线性表中第N个结点，头结点的index是0
124     int i=0; //计数器
125     LinkList * p=L; //临时结点，用于遍历
126     if (isEmpty(L)==TRUE) return (datatype)ERR; //线性表为空
127     while (p!=NULL && i<index){
128         //p不是NULL且j还没等于i时，循环继续
129         p=p->next;
130         i++;
131     }
132     return p->data;
133 }
134 status insert(LinkList **L, int index, datatype node_to_insert){
135     //node_to_insert表示想要插入的结点
136     //当列表为空时，只有index=0才能插入
137     //当index=0时，即头插，会修改传入的指针，将其指向新的头结点
138     //当index=getLength(root)时，即尾插
139     int k;
140     LinkList * p;
141     LinkList * tmp=malloc(sizeof(LinkList));
142     if (index<0) return ERR; //index不在有效范围
143     if (index==0){
144         //头插
145         tmp->next=*L; //将新结点的指针区指向链表的头结点，随之，新节点变成链表的头结点
146         tmp->data=node_to_insert; //数据区
147         *L=tmp; //将原来指向头结点的指针修改为现在的新头结点
148         return OK;
149     }
150     if (index>getLength(*L)-1){
151         //尾插
152         tmp->next=NULL; //因为是尾插，此结点是链表的最后一个结点，所以指针区为NULL
153         tmp->data=node_to_insert; //数据区
154         p=*L; //变量p用于遍历
155         while (p){
156             //寻找当前线性表的最后一个结点，用于将新结点附在它的后面
157             if (p->next==NULL)
158                 //找到了当前链表的最后一个
159                 break;
160             p=p->next; //继续下一个结点
161         }
162         p->next=tmp; //将原来线性表的最后一个结点指向新的尾结点
163         return OK;
164     }
165     //不是头插也不是尾插
166     k=0;
167     p=*L;
168     for (k=0; k<index-1; k++){
169         //遍历到第index个结点的前一个结点，头结点的index等于0
170         //利用index的前一个结点的next就可以知道第index个结点
171         p=p->next;
172     }
173     tmp->next=p->next; //把tmp接到index前面
174     p->next=tmp; //再把tmp接到index前一个结点的后面
175     tmp->data=node_to_insert; //数据区
176     return OK;
177 }
178 status delete(LinkList **L, int index){
179     //当index=0时，即头删
180     //当index=getLength(root)-1时，即尾删
181     int k;
182     LinkList * p,* q;
183     if (index<0) return ERR; //index不在有效范围
184     if (index==0){
185         //头删
186         p=(*L)->next; //先将原来的头结点的下一个结点的指针保存起来
187         free(*L); //释放原来的头结点
188         *L=p; //将原来指向头结点的指针修改为现在的新头结点
189         return OK;
190     }
191     if (index>getLength(*L)-2){
192         //尾删
193         p=*L; //变量p用于遍历
194         while (p){
195             //寻找当前线性表的最后一个结点的前一个结点，将这个结点的后一个结点（即最后一个结点）删除
196             if (p->next->next==NULL)
197                 //找到
198                 break;
199             p=p->next; //继续下一个结点
200         }
201         free(p->next); //将原来线性表的最后一个结点删除
202         p->next=NULL; //将原来的倒数第二个结点变成尾结点
203         return OK;
204     }
205     //不是头插也不是尾插
206     p=*L;
207     for (k=0; k<index-1; k++){
208                 //printf("**********%d\n",index);
209         //遍历到第index个结点的前一个结点，头结点的index等于0
210         //利用index的前一个结点的next就可以知道第index个结点
211         p=p->next;
212     }
213     q=p->next;
214     p->next=p->next->next; //将index前一个结点和后一个结点相连
215     free(q); //删除index的结点
216     return OK;
217 
218 }
219 void showList(LinkList *L){
220     int i;
221     int total=getLength(L);
222     LinkList * p=L;
223     for (i=0; i<total; i++){
224         printf("%c\t",p->data); p=p->next;
225     }
226 }
227 
228 /*
229     链式存储结构的线性表的优缺点：（注意，上述实现的链式线性表叫做单链表）
230     优点：
231         1.插入和删除的时间复杂度是0(1)
232         2.存储空间不受预设限制
233     缺点：
234         1.寻找某个结点需要进行遍历操作
235     另外，
236         把单链表的尾结点的指针区指向头结点，便成为循环链表；
237         把单链表的每个结点再增加一个指针区，新加的指针区指向前一个结点，便成为双向链表
238 */
239 /* 环境: Code::Blocks with GCC 5.1 */