单链表的操作

       学习数据结构,进行单链表操作是很基础的内容;只要掌握单链表,那么循环链表、栈和队列的操作将是水到渠成的事情。单链表的难点在于结构体和指针的配合使用,这点掌握熟练,那么单链表也不在话下。这篇文章的示例程序是在Ubuntu16.04操作系统环境中进行的。

       我们学习链表的目的是什么?也就是说我们学习链表是要解决什么样的问题呢?大家都知道,针对数组,一组数据的数据类型少,产生了结构体,而结构体和数组都有一个共同的特点,在定义的时候就要规定明确的数据个数。所以对于有限个数据的处理,我们使用结构体或数组就够用了,但是,很多实际问题,我们无法在定义的时候能够明确具体的数据个数,很多时候会有未知个数的数据需要处理,这时我们就需要使用链表来进行操作了。

       下面我们便以代码为例,简单说明一下单链表的操作。

       首先编写头文件,头文件的名称为:linklist.h。声明结构体,声明各个操作函数。一般的单链表操作,是不会在节点中加入编号的,而我个人认为,加入编号方便后续的编程实现,也不容易产生混乱,可以进一步验证正确与否,尽管这样做,对于代码编写难度略有提高。

 1 /*
 2 *    文件名为:linklist.h
 3 *    文件作用:声明结构体,声明各个操作函数,便于主函数的调用
 4 *    文件用途:用于单链表的操作使用
 5 */
 6 typedef int datatype;        /*自定义变量datatype 便于阅读。*/
 7 /*    定义结构体部分*/
 8 typedef struct node{
 9     datatype data;
10     int no;
11     struct node * next;
12 }listnode,*linklist;
13 
14 /*    声明各个操作函数*/
15 /*    声明创建空表函数,返回值为空表指针*/
16 linklist list_create(void);
17 /*    声明头结点插入节点函数,返回值为操作是否成功,成功:0失败:-1*/
18 int list_head_insert(linklist H,datatype x);
19 /*    声明按节点编号插入节点函数,返回值为操作是否成功,成功:0失败:-1*/
20 int list_pos_insert(linklist H,datatype x,int pos);
21 /*    声明按数值查找函数,返回值为节点编号,失败:-1*/
22 int list_number_search(linklist H,datatype x);
23 /*    声明按节点序号查找函数,返回值为该节点编号下的数值,失败:-1*/
24 int list_pos_search(linklist H,int pos);
25 /*    声明删除指定节点编号的节点函数,返回值为操作是否成功,成功:0失败:-1*/
26 int list_delete(linklist H,int pos);
27 /*    声明将链表数据全部倒置,返回值为操作是否成功,成功:0失败:-1*/
28 int list_invode(linklist H);
29 /*    声明链表输出显示各个节点数据的函数,返回值为操作是否成功,成功:0失败:-1*/
30 int list_show(linklist H);

       以上便是头文件的编写,下面创建linklist.c文件,用于各个函数功能的实现。由于文件中代码行数较多,不方便讲述,所以下面的讲述,不是将代码整段贴在下面,而是以函数为单位进行了分割,组合起来和源文件也是一模一样的。

       第一个函数功能是创建空表,函数没有参数,但是返回值是指向创建空表的指针。首先要创建动态内存,赋值给空表指针,判断指针是否为空来确定动态内存是否分配成功,若成功,则继续给空表内的各个数值及指针赋值。最后返回指针,完成空表的创建。

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include "linklist.h"
 4 linklist list_create(void)
 5 {
 6     linklist H = NULL;
 7 /*    申请动态内存,赋值给指针*/
 8     H = (linklist)malloc(sizeof(listnode));
 9 /*    判断动态内存是否申请成功*/
10     if(H == NULL)
11     {
12         printf("no memory\n");
13         return NULL;
14     }else
15     {
16 /*    给空表中结构体中的各个成员赋值*/
17         H -> data = 0;
18         H -> no = -1;
19         H -> next = NULL;
20 /*    返回空表指针*/
21         return H;
22     }
23 }

       第二个函数功能是,在头结点之后插入结点元素。函数有两个参数,第一个参数是:所要插入节点的链表指针,第二个参数是:插入节点中结构体成员中数据的数值。返回值为操作是否成功,若成功则返回0,若失败则返回-1。

       首先要判断传参传入的链表指针是否为空,若为空说明是一个失败的链表,不能继续执行插入操作,因此返回-1,就此程序结束;若不为空则继续执行插入操作。在执行插入之前先要创建一个节点,节点的创建也需要申请动态内存管理空间,将动态内存申请的节点指针,赋予头结点的节点指针,头结点的节点指针赋予动态内存申请的指针,将参数传入的数据赋值给新创建的节点结构体中的成员,成员编号赋予0,表示头结点的下一个编号。由于每次调用这个函数,我们不能确定是第几次给头结点插入节点,因此节点的编号必然需要刷新,这样构建循环,在循环中让插入的节点的下一个节点依次自增1,使编号不会混乱。最后返回0值表明程序顺利执行。

 1 int list_head_insert(linklist H,datatype x)
 2 {
 3     linklist P = NULL;
 4 /*    判断传入的链表是否为空*/
 5     if(H == NULL)
 6     {
 7         printf("linklist H is NULL\n");
 8         return -1;
 9     }else
10     {
11 /*    创建节点,动态内存*/
12         P = (linklist)malloc(sizeof(listnode));
13         if(P == NULL)
14         {
15             printf("no memory\n");
16             return -1;
17         }else
18         {
19 /*    插入节点操作,直接赋值*/
20             P -> next = H -> next;
21             H -> next = P;
22             P -> data = x;
23             P -> no = H -> no + 1;
24 /*    刷新各个节点的编号*/
25             while(P -> next != NULL)
26             {
27                 P -> next -> no ++;
28                 P = P -> next;
29             }
30             return 0;
31         }
32     }
33 }

       第三个函数的功能是,依据节点编号插入节点。函数有三个参数,第一个参数是:所要插入节点的链表指针;第二个参数是:所要插入节点的数据值;第三个参数是:所要插入节点在链表中的节点序号。返回值为操作是否成功,若成功则返回0,若失败则返回-1。

       程序的开始依旧是判断传参传入的链表指针是否为空,若不为空,则继续执行,申请动态内存创建节点,首先要循环找到指定编号的指针的前一个指针(因为是单链表,所以没有反向的连接以进行灵活的赋值),然后新创建的节点指针赋予指定编号的前一个节点指针,指定编号的前一个节点指针赋予新创建的指针,之后便是成员赋值和刷新编号。

 1 int list_pos_insert(linklist H,datatype x,int pos)
 2 {
 3     linklist P = NULL;
 4     linklist Q = NULL;
 5 /*    判断传入的链表指针是否为空*/
 6     if(H == NULL)
 7     {
 8         printf("linklist H is NULL\n");
 9         return -1;
10     }else
11     {
12 /*  创建新节点*/
13         P = (linklist)malloc(sizeof(listnode));
14         if(P == NULL)
15         {
16             printf("no memory\n");
17             return -1;
18         }else
19         {
20 /*    找到指定编号的前一个节点*/
21             Q = H;
22             while(Q -> next -> no != pos)
23             {
24                 Q = Q -> next;
25             }
26 /*    插入操作*/
27             P -> next = Q -> next;
28             Q -> next = P;
29 /*    成员赋值*/
30             P -> data = x;
31 /*    刷新节点编号*/
32             P -> no = pos;
33             while(P -> next != NULL)
34             {
35                 P -> next -> no ++;
36                 P = P -> next;
37             }
38             Q = NULL;
39             P = NULL;
40             return 0;
41         }
42     }
43 }

       第四个和第五个函数功能分别是按值查找和按位查找,代码很简单,也没有复杂的刷新编号操作,在此就不再赘述。仅将代码陈述其下,以供参考。

 1 int list_number_search(linklist H,datatype x)
 2 {
 3     linklist P = NULL;
 4     if(H == NULL)
 5     {
 6         printf("linklist H is NULL\n");
 7         return -1;
 8     }else
 9     {
10         P = H;
11         while(P -> data != x)
12         {
13             P = P -> next;
14         }
15         return P -> no;
16     }
17 }
18 
19 /*按位查找的返回值是指定节点编号的数据值*/
20 int list_pos_search(linklist H,int pos)
21 {
22     linklist P = NULL;
23     if(H == NULL)
24     {
25         printf("linklist H is NULL\n");
26         return -1;
27     }else
28     {
29         P = H;
30         while(P -> no != pos)
31         {
32             P = P -> next;
33         }
34         return P -> data;
35     }
36 }

       第六个函数功能是,删除指定编号的节点。函数有两个参数,第一个参数是:要删除节点的链表的指针;第二个参数是:指定删除的节点编号。返回值是操作是否成功,若成功则返回0,若失败则返回-1。

       第一步是要找到指定编号的节点前一个节点的指针。第二步指针赋值,第三部释放删除节点的动态内存空间,第四步刷新节点编号,第五步返回操作结果。

 1 int list_delete(linklist H,int pos)
 2 {
 3     linklist P = NULL;
 4     linklist Q = NULL;
 5 /*    判断传入链表指针是否为空*/
 6     if(H == NULL)
 7     {
 8         printf("linklist H is NULL\n");
 9         return -1;
10     }else
11     {
12 /*    找到指定编号节点的前一个节点的指针*/
13         P = H;
14         while(P -> next -> no != pos)
15         {
16             P = P -> next;
17         }
18 /*    删除操作*/
19         Q = P -> next;
20         P -> next = Q -> next;
21         free(Q);
22         Q = NULL;
23 /*    刷新节点编号*/
24         while(P -> next != NULL)
25         {
26             P -> next -> no --;
27             P = P -> next;
28         }
29         P = NULL;
30         return 0;
31     }
32 }

       第七个函数功能是,将链表中的节点依次倒置。函数只有一个参数,就是传入待倒置的链表指针。返回值是操作是否成功,若成功则返回0,若失败则返回-1。

       实现倒置的原理很简单,就是将链表一分为二,然后依次从头结点重新插入,这样便实现了倒置操作。着重提示的便是节点编号的刷新问题。

 1 int list_invode(linklist H)
 2 {
 3     linklist P = NULL;
 4     linklist Q = NULL;
 5 /*    判断传入链表的指针是否为空*/
 6     if(H == NULL)
 7     {
 8         printf("linklist H is NULL\n");
 9         return -1;
10     }else
11     {
12 /*    将链表一分为二*/
13         P = H -> next;
14         H -> next = NULL;
15 /*    依次从头结点插入节点*/
16         while(P -> next != NULL)
17         {
18             Q = P -> next;
19             P -> next = H -> next;
20             H -> next = P;
21             P -> no = 0;
22 /*    刷新结点编号*/
23             while(P -> next != NULL)
24             {
25                 P -> next -> no ++;
26                 P = P -> next;
27             }
28             P = Q;
29         }
30 /*    为最后一个节点补充插入操作*/
31         P -> next = H -> next;
32         H -> next = P;
33         P -> no = 0;
34         while(P -> next != NULL)
35         {
36             P -> next -> no ++;
37             P = P -> next;
38         }
39         return 0;
40     }
41 }

       第八个函数功能是,输出显示链表数据。函数只有一个参数,待显示数据的链表指针。返回值是操作结果是否成功,若成功则返回0,若失败则返回-1。

 1 int list_show(linklist H)
 2 {
 3     linklist P = NULL;
 4 /*    判断传入链表指针是否为空*/
 5     if(H == NULL)
 6     {
 7         printf("linklist H is NULL\n");
 8         return -1;
 9     }else
10     {
11 /*    输出打印数值*/
12         P = H -> next;
13         while(P != NULL)
14         {
15             printf("H -> data number %d is %d\n",P -> no,P -> data);
16             P = P -> next;
17         }
18         return 0;
19     }
20 }

       以上便是linklist.c的文件内容,下面创建test.c的文件,用于测试函数的功能是否正确、完整。

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include "linklist.h"
 4 int main()
 5 {
 6     linklist H = NULL;
 7 /*    创建空链表*/
 8     H = list_create();
 9 /*    从头结点插入节点*/
10     list_head_insert(H,10);
11     list_head_insert(H,20);
12     list_head_insert(H,30);
13     list_head_insert(H,40);
14     list_head_insert(H,50);
15     list_show(H);
16     printf("insert 2=========================\n");
17 /*    插入操作演示*/
18     list_pos_insert(H,99,2);
19     list_show(H);
20     printf("delete 2=========================\n");
21 /*    删除操作演示*/
22     list_delete(H,2);
23     list_show(H);
24     printf("invode===========================\n");
25 /*    倒置操作演示*/
26     list_invode(H);
27     list_show(H);
28     return 0;
29 }

       之后便创建Makefile文件,进行编译。

1 CFLAGS=-c –Wall –g
2 test:linklist.o test.o
3 .PHONY:clean
4 clean:
5     rm *.o test