线性表的链式存储——链表（带源码）

一、为什么要采用链式存储（链表）存在的意义 为什么要采用链式存储：
与数组相比，链式存储（即链表）有如下两个优点：
1、数据元素的个数不确定，随时可能增减。采用固定大小的数组浪费空间。
2、方便排序，对于数组来说，每次插入一个元素都可能导致大量数据的移动。
有缺点吗：
与素族相比，链式存储有一个很大的缺点——读取数据！
对于读取其中指定第N个数据，链表必须从头结点用p = p->next（头结点不存储数据）;一直遍历N次或N-1次（头结点存储数据）。所以在需要频繁索取某些指定数据的情况下，牺牲空间为代价换取更优的性能就需要采取数组这种数据结构了。

二、链表的定义和操作
链表的基础——结构体和指针：
懂得结构体，懂得指针，那么学习链表就很简单了。

C代码

1. /*  
2.  * 头结点存储数据，即不带头结点的链表  
3.  */  
4. #include <stdio.h>   
5. #include <stdlib.h>   
6.   
7. #define OverFlow -1  //定义OverFlow表示内存溢出   
8. #define OK        0  //定义OK表示成功   
9. #define Error    -2  //定义操作失败的返回值   
10. #define OverFlow -1; //定义OverFlow表示内存溢出   
11. #define OK        0; //定义OK表示成功   
12. #define Error    -2; //定义操作失败的返回值   
13. /*   
14.  * 首先定义一个数据类型int的别名ElemType，  
15.  * 增强程序的可移植性，注意typedef和define的区别  
16.  */  
17. typedef int ElemType;   
18. /*  
19.  * 紧接着定义链表的节点，其实就是>=1个包含数据  
20.  * 的元素（类型任意）和一个本结构体类型的Next指  
21.  * 针（其值指向链表的下一个节点的地址）  
22.  */  
23. typedef struct node   
24. {   
25.     ElemType data;   
26.     struct node *next;   
27. } Node, *LinkList;   

/* * 头结点存储数据，即不带头结点的链表 */#include <stdio.h>#include <stdlib.h>#define OverFlow -1  //定义OverFlow表示内存溢出#define OK        0  //定义OK表示成功#define Error    -2  //定义操作失败的返回值#define OverFlow -1; //定义OverFlow表示内存溢出#define OK        0; //定义OK表示成功#define Error    -2; //定义操作失败的返回值/*  * 首先定义一个数据类型int的别名ElemType， * 增强程序的可移植性，注意typedef和define的区别 */typedef int ElemType;/* * 紧接着定义链表的节点，其实就是>=1个包含数据 * 的元素（类型任意）和一个本结构体类型的Next指 * 针（其值指向链表的下一个节点的地址） */typedef struct node{ElemType data;struct node *next;} Node, *LinkList; 

定义了节点的结构体，我们来进行链表操作的函数编写：
首先来看头结点不存储数据的情况：
我们需要：
1.构造一个空表
    构造空表分两种情况，构造头结点不存储数据的空表和头结点存储数据的空表。

C代码

1. /*  
2.  * 1.构建头结点不存储数据的空表（相对简单）  
3.  * 注意函数参数传递的原理  
4.  */  
5. void Init_LinkList(LinkList *Head_pointer)    
6. {   
7.     *Head_pointer = NULL;   
8. }  

/* * 1.构建头结点不存储数据的空表（相对简单） * 注意函数参数传递的原理 */void Init_LinkList(LinkList *Head_pointer) {*Head_pointer = NULL;}

2.插入一个元素（头插）
插入一个元素分三步：第一步，定义节点p并初始化，包括分配空间和赋值；第二步，找准插入位置，一般找到插入点的前一个元素；第三步，p->next赋值（这一定首先进行，进行此步骤不影响链表中任何信息)等一系列链表操作，这是核心部分。

C代码

1. /*  
2.  * 2.插入一个元素（头插）  
3.  * 这时候不需要传入位置的数据，只需要传入头指针和数据  
4.  */  
5. int Insert_First(LinkList *Head_pointer, ElemType x)   
6. {   
7.     Node *p; //这里考虑为什么不用LinkList   
8.     p = (Node *) malloc(sizeof Node);   
9.     if (p == NULL)   
10.         return OverFlow;   
11.     p->data = x;   
12.        
13.     p->next = *Head_pointer;   
14.     *Head_pointer = p;   
15.        
16.     return OK;   
17. }  

/* * 2.插入一个元素（头插） * 这时候不需要传入位置的数据，只需要传入头指针和数据 */int Insert_First(LinkList *Head_pointer, ElemType x){Node *p; //这里考虑为什么不用LinkListp = (Node *) malloc(sizeof Node);if (p == NULL)return OverFlow;p->data = x;p->next = *Head_pointer;*Head_pointer = p;return OK;}

3.查找指定的元素（与数组查找元素效率差不多）

C代码

1. /*   
2.  * 3.查找指定元素，注意这里用到了LinkList定义数据  
3.  * 因为不是要定义一个节点，只是定义一个指针  
4.  */  
5. LinkList Location_LinkList(LinkList Head, ElemType x)   
6. {   
7.     LinkList p;   
8.     p = Head;   
9.     while(p != NULL)   
10.     {   
11.         if (p->data == x)   
12.             break;   
13.         p = p->next;   
14.     }   
15.     return p;   
16. }  

/*  * 3.查找指定元素，注意这里用到了LinkList定义数据 * 因为不是要定义一个节点，只是定义一个指针 */LinkList Location_LinkList(LinkList Head, ElemType x){LinkList p;p = Head;while(p != NULL){if (p->data == x)break;p = p->next;}return p;}

4.删除指定的元素
    这里要注意头结点就是要删除的元素时，操作代码不一样。建立链表时头结点不存入数据的原因就在这里。

C代码

1. /*  
2.  * 4.删除指定的元素  
3.  * 有可能改变头结点的值，所以要传入指针  
4.  * 对头结点就是要删除的元素进行单独处理  
5.  */  
6. int Delete_LinkList(LinkList *Head_pointer, ElemType x)   
7. {   
8.     Node *p, *q;   
9.     p = *Head_pointer;   
10.     if (p->data == x)//考虑头结点就是要删除的元素   
11.     {   
12.         *Head_pointer = (*Head_pointer)->next;   
13.         free(p);   
14.         return OK;   
15.     }   
16.     else  
17.     {   
18.         q = p; p = p->next; //q指向前一个节点，p指向下一个节点   
19.         while(p != NULL)   
20.         {   
21.             if (p->data == x)   
22.             {   
23.                 q->next = p->next;   
24.                 free(p);   
25.                 return OK;   
26.             }   
27.             q = p; p = p->next;   
28.         }   
29.     }   
30.     return Error;   
31. }  

/* * 4.删除指定的元素 * 有可能改变头结点的值，所以要传入指针 * 对头结点就是要删除的元素进行单独处理 */int Delete_LinkList(LinkList *Head_pointer, ElemType x){Node *p, *q;p = *Head_pointer;if (p->data == x)//考虑头结点就是要删除的元素{*Head_pointer = (*Head_pointer)->next;free(p);return OK;}else{q = p; p = p->next; //q指向前一个节点，p指向下一个节点while(p != NULL){if (p->data == x){q->next = p->next;free(p);return OK;}q = p; p = p->next;}}return Error;}

5.遍历链表
    其实就是逐个操作链表，操作可以包括打印每个元素，更改每个元素。
    注意如果在linux下面打印中文出现乱码的情况，请更改编码方式。可参考我在163博客中的一篇文章：http://canlynet.blog.163.com/blog/static/25501365200911300521926/

C代码

1. /*  
2.  * 5.遍历线性表，打印每个数据  
3.  * 只需要传入Head的值即可  
4.  * 头结点为空需要打印空表，在linux的超级终端下注意中文编码问题  
5.  */  
6. void Show_LinkList(LinkList Head)   
7. {   
8.     LinkList p = Head;   
9.     int i = 0;   
10.     printf("----链表打印----\n");   
11.     if (p == NULL) //处理头结点为空的情况   
12.         printf("空表\n");   
13.     while (p != NULL)   
14.     {   
15.         printf("[%d]:%d\t", i++, p->data);   
16.         p = p->next;   
17.     }   
18. }  

/* * 5.遍历线性表，打印每个数据 * 只需要传入Head的值即可 * 头结点为空需要打印空表，在linux的超级终端下注意中文编码问题 */void Show_LinkList(LinkList Head){LinkList p = Head;int i = 0;printf("----链表打印----\n");if (p == NULL) //处理头结点为空的情况printf("空表\n");while (p != NULL){printf("[%d]:%d\t", i++, p->data);p = p->next;}}

6.清空链表
    清空链表需要传入头结点指针。

C代码

1. /*  
2.  * 6.清空链表  
3.  * 清除到头结点为空的状态，也就是一个空表的状态  
4.  */  
5. void SetNull_LinkList(LinkList *Head_pointer)   
6. {   
7.     LinkList p, q;   
8.     p = *Head_pointer;   
9.     while (p != NULL)   
10.     {   
11.         q = p;   
12.         p = p->next;   
13.         free(q);   
14.     }   
15. }  

/* * 6.清空链表 * 清除到头结点为空的状态，也就是一个空表的状态 */void SetNull_LinkList(LinkList *Head_pointer){LinkList p, q;p = *Head_pointer;while (p != NULL){q = p;p = p->next;free(q);}}

7.计算链表的长度
    注意算法：从Head计算，指针不为空的总数
/*
* 7.计算链表的长度
* 计算方法：从Head开始，计算指针不为空的个数
*/
int Length_LinkList(LinkList Head)
{
LinkList p = Head;
int sum = 0;
while(p != NULL)
{
sum++;
p = p->next;
}
return sum;
}

8.调用单链表操作的主函数
    看了下面这个主函数，我们基本上能够感受到c语言编写软件的一种方式。

C代码

1. /*  
2.  *8.调用单链表操作的主函数  
3.  */  
4. int main(void)   
5. {   
6.     LinkList Head;   
7.     int i;   
8.     Node *loca;   
9.     ElemType x;   
10.        
11.     Init_LinkList(&Head);   
12.     do  
13.     {   
14.         printf("\n");   
15.         printf("1---插入一个元素（Insert）\n");   
16.         printf("2---查询一个元素（Locate）\n");   
17.         printf("3---删除一个元素（Delete）\n");   
18.         printf("4---显示所有元素（Show）\n");   
19.         printf("5---计算表的长度（Length）\n");   
20.         printf("6---退出\n");   
21.         scanf("%d", &i);   
22.         switch (i)   
23.         {   
24.             case 1: printf("请输入要插入的分数：\n");   
25.                     scanf("%d", &x);   
26.                     if (Insert_First(&Head, x) != OK)   
27.                         printf("插入失败\n");   
28.                     break;   
29.                        
30.             case 2: printf("请输入要查询的分数\n");   
31.                     loca = Location_LinkList(Head, x);   
32.                     if (loca != NULL)   
33.                         printf("查询成功\n");   
34.                     else  
35.                         printf("查询失败\n");   
36.                     break;   
37.                        
38.             case 3: printf("请输入要删除的分数\n");   
39.                     scanf("%d", &x);   
40.                     if (Delete_LinkList(&Head, x) != OK)   
41.                         printf("删除失败\n");   
42.                     else  
43.                         printf("删除成功\n");   
44.                     break;   
45.                        
46.             case 4: Show_LinkList(Head);   
47.                     break;   
48.                        
49.             case 5: printf("表的长度是：%d", Length_LinkList(Head));   
50.                     break;   
51.                        
52.             case 6: break;   
53.                
54.             default:    printf("错误选择！请重选");   
55.                         break;   
56.         }   
57.     } while (i != 6);   
58.        
59.     SetNull_LinkList(&Head);   
60.     printf("链表已清空，程序退出...\n");   
61.        
62.     return 0;   
63. }  

/* *8.调用单链表操作的主函数 */int main(void){LinkList Head;int i;Node *loca;ElemType x;Init_LinkList(&Head);do{printf("\n");printf("1---插入一个元素（Insert）\n");printf("2---查询一个元素（Locate）\n");printf("3---删除一个元素（Delete）\n");printf("4---显示所有元素（Show）\n");printf("5---计算表的长度（Length）\n");printf("6---退出\n");scanf("%d", &i);switch (i){case 1:printf("请输入要插入的分数：\n");scanf("%d", &x);if (Insert_First(&Head, x) != OK)printf("插入失败\n");break;case 2:printf("请输入要查询的分数\n");loca = Location_LinkList(Head, x);if (loca != NULL)printf("查询成功\n");elseprintf("查询失败\n");break;case 3:printf("请输入要删除的分数\n");scanf("%d", &x);if (Delete_LinkList(&Head, x) != OK)printf("删除失败\n");elseprintf("删除成功\n");break;case 4:Show_LinkList(Head);break;case 5:printf("表的长度是：%d", Length_LinkList(Head));break;case 6:break;default:printf("错误选择！请重选");break;}} while (i != 6);SetNull_LinkList(&Head);printf("链表已清空，程序退出...\n");return 0;}

附件包括了头结点存储数据（即不带头结点的单向链表的操作源码）和头结点不存储数据（即带头结点的单向循环链表）的链表操作的源码。