开发者社区> ghost丶桃子> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

动态单链表的传统存储方式和10种常见操作-C语言实现

简介:
+关注继续查看

顺序线性表的优点:方便存取(随机的),特点是物理位置和逻辑为主都是连续的(相邻)。但是也有不足,比如;前面的插入和删除算法,需要移动大量元素,浪费时间,那么链式线性表 (简称链表) 就能解决这个问题。

 

一般链表的存储方法

一组物理位置任意的存储单元来存放线性表的数据元素,当然物理位置可以连续,也可以不连续,或者离散的分配到内存中的任意位置上都是可以的。故链表的逻辑顺序和物理顺序不一定一样。

 

因为,链表的逻辑关系和物理关系没有必然联系,那么表示数据元素之间的逻辑映象就要使用指针,每一个存储数据元素的逻辑单元叫结点(node)。

结点里有两个部分,前面存储数据元素内容,叫数据域,后面部分存储结点的直接后继在内存的物理位置,叫指针域。那么就可以实现用指针(也叫链)把若干个结点的存储映象链接为表,就是链式线性表。

 

上面开始介绍的是最简单的链表,因为结点里只有一个指针域,也就是俗称的单链表(也叫线性链表)。

 

单链表可以由一个叫头指针的东东唯一确定,这个指针指向了链表(也就是直接指向第一个结点)。因此单链表可以用头指针的名字来命名。且最后一个结点指针指向NULL。

 

链表类别

1、实现的角度:动态链表,静态链表(类似顺序表的动态和静态存储)

2、链接方式的角度:单链表,双向链表,循环链表

 

单链表

 

单链表的头结点

一般是使用单链表的头指针指向链表的第一个结点,有的人还这样做,在第一个结点之前再加一个结点(不保存任何数据信息,只保存第一个结点的地址,有时也保存一些表的附加信息,如表长等),叫头结点(头结点是头结点,第一个结点是第一个结点)。那么此时,头指针指向了头结点。并且有无头结点都是可以的。链表还是那个链表,只不过表达有差异。

 

那么问题来了!为什么还要使用头结点?

作用是对链表进行操作时,可以对空表、非空表的情况以及对首元结点进行统一处理,编程更方便。

 

描述动态单链表

有两种做法,一种是传统的动态链表结构,暨只定义结点的存储结构,使用4个字节的指针变量表示线性表。还有一种是直接采用结构体变量(类似顺序表)来表示线性表。

顾名思义,肯定是第二种方法比较方便。


先看传统存储动态单链表结构的操作

 View Code

C变量的随用随定义,可以确定C99之后新增加的,和c++一样,貌似一些编译器还不支持

复制代码
 1 #include "ADT.h"
 2 
 3 /*
 4     1、查找(按值)算法
 5     找到第一个值等于value的结点,找到则返回存储位置
 6 */
 7 LinkList getElemByValue(LinkList L, char value)
 8 {
 9     //定义指示指针指向L第一个结点
10     LinkList p = L->next;//L开始指向了头结点,L->next指向的就是第一个结点
11 
12     while (p && p->data != value)
13     {
14         //p++;显然错误,离散存储,非随机结构
15         p = p->next;//指针顺链移动,直到找到或者结束循环
16     }
17     //当找不到,则p最终指向NULL,循环结束
18     return p;//返回存储位置或NULL
19 }
复制代码

算法执行时间和value有关,时间复杂度为0(n),n表长

复制代码
 1 /*
 2     2、查找(按序号)算法
 3     查找第i个元素,并用变量value返回值,否则返回提示,即使知道了序号,也必须使用指针顺次查访
 4 */
 5 void getElemByNum(LinkList L, int num, char *value)
 6 {
 7     int count = 1;
 8     LinkList p = L->next;
 9     //控制指针p指向第num个结点
10     while (p && count < num)//num若为0或者负数直接跳出循环,若超出表长则遍历完毕,跳出循环,找到了元素也跳出循环
11     {
12         p = p->next;//p指向第num个结点,count此时为num值
13         count++;
14     }
15     //如果num大于表长,则count值增加到表长度时,p恰好指向表尾结点,遍历完整个链表也找不到结点,此时再循环一次
16     //p指向null,count = 表长 + 1,循环结束,这里也隐含说明了num大于 表长 的不合法情况
17     if (!p || count > num)//说明num至少比 表长 大
18     {
19         //num <= 0或者num大于表长时,跳出while循环,来到if语句,判断不合法
20         puts("num值非法!");
21     }
22     else
23     {
24         *value = p->data;
25         printf("找到第%d个元素的值 = %c\n", num, *value);
26     }
27 }
复制代码

//时间复杂度0(n),n为表长

复制代码
 1 /*
 2     3、删除结点
 3     删除第i个元素,并用value返回值
 4 */
 5 
 6 void deleteList(LinkList L, int i, char *value)
 7 {
 8     LinkList p = L;//头脑一定要清晰!这里p应该指向头结点
 9     LinkList temp;
10     int j = 0;//对应着头结点的序号0
11 
12     /*while (p && j < i)
13     {
14         p = p->next;此时,p指向的是i元素位置,要删除i元素,需要知道i的前驱!
15         j++;
16     }*/
17         
18     while (p->next && j < i - 1)//i - 1可以保证指向其前驱 ,j=0需要注意,删除是从1-n都可以
19     {
20         p = p->next;//指向i元素前驱(i-1)
21         j++;
22     }
23     //必须想到判断合法性
24     if (!(p->next) || j > i - 1)//同样判断i的下边界,和上边界
25     {
26         puts("i值不合法!");
27     }
28     else
29     {
30         //找到了前驱p
31         temp = p->next;//temp指针指向i元素
32         //p->next = p->next->next;等价于
33         p->next = temp->next;//链表删除结点的关键逻辑
34         *value = temp->data;
35         free(temp);//释放temp指向的结点的内存空间
36         temp = NULL;
37         puts("删除成功!");
38     }
39 }
复制代码

时间复杂度,虽然没有移动任何元素,还是0(n),因为最坏时核心语句频度为n(表长)

为什么不是p?

//判断表为非空,因为不止一次删除操作!总会删空,则p还是指向的头结点!如果依然是while(p &&……),表空时,按道理函数不应该再执行核心语句,提前判断出错,但此时却还要执行循环体,循环结束才能到if(!p),而使用while(p->next && ……),表空就直接跳出循环,到if语句,提示错误。这是删除算法总是需要注意的细节,插入算法则是如果内存有限,或者是顺序的表,或者静态链表,那么总是要注意存储空间满足大小的问题

 

复制代码
 1 /*
 2     4、插入结点
 3     在第i个位置之前插入结点e,换句话说就是在第i-1个位置之后插入,类似前面的删除操作思想
 4 */
 5 void insertList(LinkList L, int i, char value)
 6 {
 7     LinkList p = L;
 8     LinkList s;
 9     int j = 0;
10     //和删除不同,插入操作不用注意表空的情况
11     while (p && j < i - 1)
12     {
13         p = p->next;
14         j++;
15     }
16 
17     if (!p || j > i - 1)//i小于1或者大于表长+1不合法
18     {
19         puts("i不合法!");
20     }
21     else
22     {
23         //先分配结点存储空间
24         s = (LinkList)malloc(sizeof(Node));
25         //依次传入插入的元素内容和修改逻辑链接
26         s->data = value;
27         //链表插入算法的关键逻辑
28         s->next = p->next;
29         p->next = s;//顺序不可颠倒,原则是指针在修改前,先保留再修改,不能先修改再保留
30         puts("插入成功!");
31     }
32 }
复制代码

插入算法时间复杂度分析:0(n),最坏情况下频度是n

/插入和删除算法,还有一个思路,就是既然需要每次都找前驱,那么为什么不弄两个指针呢?一个指向当前位置,一个紧随其后指向前,个人其实感觉是脱裤子放屁……

 

复制代码
 1 //以删除为例
 2 void deleteList(LinkList L, int i, char *value)
 3 {
 4     LinkList prePoint = L;//前驱指针初始化指向头结点
 5     LinkList point = L->next;//当前指针初始化指向第一个结点
 6     LinkList temp = NULL;
 7     int j = 1;
 8     //i要>0,且小于等于表长
 9     while (point && j < i)//如果表非空,找到要删除的元素位置
10     {
11         point = point->next;
12         prePoint = prePoint->next;//分别顺次后移
13         j++;
14     }
15 
16     if (!point || j > i)
17     {
18         puts("i不合法!");
19     }
20     else
21     {
22         temp = point;
23         prePoint->next = point->next;
24         *value = temp->data;
25         free(temp);
26         temp = NULL;
27         puts("删除成功!");
28     }
29 }
复制代码

时间复杂度依然是O(n)

 

复制代码
 1 /*
 2     5、头插法建立单链表(逆序建表)
 3     从一个空结点开始,逐个把 n 个结点插入到当前链表的表头
 4 */
 5 
 6 //开始就空表,则肯定先分配结点(带头结点)
 7 void createListByHead(LinkList *L, int n)
 8 {
 9     LinkList p = NULL;
10     int i = 0;
11     *L = (LinkList)malloc(sizeof(Node));//L指向头结点
12     (*L)->next = NULL;//空表建立
13     //头插法
14     for (i = 1; i <= n; i++)
15     {
16         p = (LinkList)malloc(sizeof(Node));//先创建要插入的结点
17         scanf("%c", &(p->data));//给结点数据域赋值    再次验证 -> 优先级高于取地址 &
18 
19         while (getchar() != '\n')
20         {
21             continue;
22         }
23 
24         p->next = (*L)->next;//再让插入的结点的next指针指向后继(链接的过程),注意后继不能为空(除去第一次插入)
25         //p->next = NULL;//错误
26         (*L)->next = p;//最后保证插入结点是第一个结点,把头结点和第一个结点链接起来。
27     }
28 
29     printf("头插法建表成功\n");
30 }
复制代码

时间复杂度:必然是O(n),插入了n个元素

链表和顺序表存储结构不同,动态,整个可用内存空间可以被多个链表共享,每个链表无需事先分配存储容量,由系统应要求自动申请。建立链表是动态的过程。

//如a b c d,依次头插法(头插 总是在第一个结点前插入,暨插入的结点总是作为第一个结点)到空链表里,那么完成之后是

//d c b a

 

下面是正序的尾插法,如图

复制代码
 1 /*
 2     6、尾插法建立单链表(顺序建表)
 3     //对 5 算法的改进
 4 */
 5 //头插法算法简单,但生成的链表结点次序和输入的顺序相反。有时不太方便。
 6 //若希望二者次序一致,可采用尾插法建表。该方法是将新结点顺次的插入到当前链表的表尾上,为此必须增加一个尾指针tail,
 7 //使其始终指向当前链表的尾结点。
 8 void createListByTail(LinkList *L, int n)
 9 {
10     LinkList tail = NULL;//尾指针
11     int i = 0;
12     LinkList p = NULL;//代表前驱
13     *L = (LinkList)malloc(sizeof(Node));
14     (*L)->next = NULL;
15     tail = *L;
16 
17     for (i = 1; i <= n; i++)
18     {
19         p = (LinkList)malloc(sizeof(Node));
20         //_CRTIMP int __cdecl scanf(_In_z_ _Scanf_format_string_ const char * _Format, ...);返回int,传入的参数个数
21         /*如果被成功读入,返回值为参数个数
22         如果都未被成功读入,返回值为0
23             如果遇到错误或遇到end of file,返回值为EOF*/
24         scanf("%c", &(p->data));
25         //清空输入队列的剩余的所有字符
26         while (getchar() != '\n')
27         {
28             continue;
29         }
30         //尾插操作,后继总是空的
31         p->next = NULL;
32         //链接前驱   
33         tail->next = p;//万万不能写成*L->next = p;
34         //保证尾指针tail总是指向最后一个结点
35         tail = p;
36     }
37 
38     printf("尾插法建表成功! \n");
39 }
复制代码

这样操作,输入的序列和输出的序列是正序的,且时间复杂度为O(n)

 

复制代码
 1 /*
 2     7、尾插法建立有序单链表(归并链表)
 3     把两个有序(非递减)链表LA LB合并为一个新的有序(非递减)链表LC(空表)
 4     要求:不需要额外申请结点空间来完成
 5 */
 6 
 7 //1、比较数据域,保证有序
 8 //2、尾插法思想
 9 //3、不需要额外申请结点空间来完成!
10 //使用现有的内存空间,完成操作,那么可以想到用LC的头指针去指向其中某个表的头结点,内存共享
11 
12 void mergeListsByTail(LinkList LA, LinkList LB, LinkList LC)
13 {
14     //因为要比较数据大小,需要两个标记指针,分别初始化为标记AB的第一个结点
15     LinkList listA = LA->next;
16     LinkList listB = LB->next;
17     //还要不开辟内存,那么内存共享,需要把表C让其他表去表示
18     LinkList listC;//声明一个标记C的指针
19     LC = LA;//比如表A。C表的头指针指向A表的头结点,做自己的头结点
20     listC = LA;//C表的标记指针需要初始化,指向A的头结点,待命
21     //接下来比较AB表数据,标记指针会顺次后移,早晚有一个先指向末尾之后的NULL,故判断是哪一个表的
22     while (listA && listB)
23     {
24         //判断数据大小,非递减
25         if (listA->data <= listB->data)
26         {
27             //则A的结点插入到C表(尾插),单链表不可使用头指针做遍历
28             listC->next = listA;//先把A的结点链到C表
29             listC = listA;//listC等价于尾指针
30             //A指针后移,继续循环比较
31             listA = listA->next;
32         }
33         else
34         {
35             //把B的结点插入到C(尾插)
36             listC->next = listB;
37             listC = listB;
38             listB = listB->next;
39         }//end of if
40     }//end of while
41     //循环结束,只需要把剩下的某个表的结点一次性链接到C表尾
42     if (listA)
43     {
44         //说明B空
45         listC->next = listA;
46     }
47 
48     if (listB)
49     {
50         //A空
51         listC->next = listB;
52     }
53     //最后AB表比较之前一定有一个表都被遍历了(也就是链接到了C),剩下的结点比如属于某个表的,最后也都链接到C尾部
54     //那么,此时就还有一个结点,那就是B表的头结点!勿忘把B表头结点释放,这才是完全的两个归并为一个
55     free(LB);
56     LB = NULL;//杜绝野指针
57 }
复制代码

算法时间复杂度,和头插法比较的话,还是O(n),其实顺序表的有序归并也是这个时间复杂度O(A.length + B.length),但是链表的尾插法归并没有移动元素,只是解除和重建链接的操作,也没有额外开辟内存空间。空间复杂度不同。

 

复制代码
 1 /*
 2     8、销毁单链表
 3 */
 4 void destoryLinkList(LinkList *L)
 5 {
 6     LinkList p = NULL;
 7 
 8     while (*L)
 9     {
10         p = (*L)->next;
11         free(*L);//free不能对指向NULL的指针使用多次!
12         *L = p;
13         //彻底搞掉指针本身,free(L)仅仅是销毁指针指向的内存,故还要连头结点一起干掉,不过while循环里隐形的包含了
14     }
15 
16     *L = NULL;
17     puts("链表L已经销毁,不存在!");
18 }
复制代码

函数内部有动态分配内存的情形,应该把参数设定为指向指针的指针,当然还有别的方法,我习惯而已。

记得说:值传递函数,是把实参的一个拷贝送到函数体,函数体修改的是那份传入的拷贝,不是函数跑到main里去给它修改。

且形参和传入的拷贝,还有函数体内的变量(栈中分配的内存),都是是代码块内的自动存储类型的变量,也就是局部变量,函数执行完毕,变量自动销毁,改变就不起作用。

指针形参可以改变实参,但是如果是针对函数内动态分配了内存的情况,把堆分配的内存地址赋给了指针参数,改变的是指针指向的内容,而指针变量(形参)本身的内存地址没有改变,故根本句不会成功修改实参。

指向指针的指针,存放的是指向实参内存地址A的指针的地址B,修改B地址,改变了B指向的内容,而B指向的内容恰恰就是一级指针A本身,一级指针A的修改,使得实参被改变,对实参(指针变量C),需要取出指针C自己的的地址,传入函数。达到间接修改实参的目的。

 

复制代码
 1 /*
 2     9、求表长,长度保存在头结点
 3 */
 4 void getLength(LinkList L)
 5 {
 6     int length = 0;
 7     LinkList p = NULL;
 8 
 9     if (L)
10     {
11         p = L->next;
12 
13         while (p)
14         {
15             p = p->next;
16             length++;
17         }
18 
19         L->data = length;
20         printf("%d\n", L->data);
21     }
22     else
23     {
24         puts("表已经销毁!无法计算长度了……");
25     }
26 }
复制代码

 

复制代码
 1 /*
 2     10、遍历链表    
 3 */
 4 void traversalList(LinkList L)
 5 {
 6     int i = 0;
 7     int length = 0;
 8     LinkList p = L->next;
 9     length = L->data;//遍历之前,务必先求表长!
10     puts("遍历之前,务必先求表长!");
11     
12     for (; i < length; i++)
13     {
14         putchar(p->data);
15         p = p->next;
16     }
17     putchar('\n');
18 }
复制代码

 

测试

复制代码
 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <assert.h>
 4 #include "ADT.h"
 5 
 6 int main(void)
 7 {
 8     LinkList L = NULL;//完全的空表,连头结点都没有
 9     LinkList LTwo = NULL;
10     LinkList val = NULL;
11     int i = 0;
12     char value = '0';
13 
14     puts("请输入5个字符变量(一行一个):");
15     puts("使用尾插法建立单链表L,5个结点,一个头结点");
16     //输入 12345
17     createListByTail(&L, 5);//尾插法建表
18 
19     //12345正确的存入到了5个结点里,尾插法创建了一个单链表L
20     
21     //先求长度
22     puts("L长度为");
23     getLength(L);
24 
25     //遍历  12345
26     puts("遍历这个链表结点元素");
27     traversalList(L);
28 
29     //用完必须销毁
30     puts("把链表L销毁,L = NULL;");
31     destoryLinkList(&L);
32 
33     //头插法 abcde  
34     //void createListByHead(&LTwo, 5);//报错;语法错误 : 缺少“;”(在“类型”的前面)
35     puts("使用头插法建立新的单链表LTwo,5个结点,一个头结点");
36     createListByHead(&LTwo, 5);
37 
38     //求长度
39     getLength(LTwo);
40 
41     //遍历  edcba
42     puts("遍历表中结点元素");
43     traversalList(LTwo);
44 
45     //按值查找
46     puts("查找LTwo表的结点数据 = ‘2’的结点");
47     val = getElemByValue(LTwo, '2');
48 
49     if (val)
50     {
51         printf("找到了val,地址 = %p \n", &val);
52     }
53 
54     puts("‘2’在表 LTwo 里没找到!");
55 
56     //插入结点
57     puts("在位置 1 之后插入一个结点,里面数据是 ‘p’");
58     insertList(LTwo, 1, 'p');
59 
60     //遍历  pedcba
61     puts("开始遍历表LTwo");
62     traversalList(LTwo);
63 
64     //按序查找
65     puts("查找位置=2的结点,并打印出它的数据内容");
66     getElemByNum(LTwo, 2, &value);
67     
68 
69     //删除结点
70     puts("删除位置 1 的结点,并打印出删除结点的数据");
71     deleteList(LTwo, 1, &value);
72     printf("%c\n", value);
73 
74     //遍历  pedcba
75     puts("再次遍历链表LTwo");
76     traversalList(LTwo);
77 
78     //求链表长度,把长度保存的头结点
79     puts("计算链表长度,并把长度保存到了LTwo的头结点");
80     getLength(LTwo);
81     printf("%d\n", LTwo->data);
82 
83     //必须有销毁
84     puts("动态存储的结构用完一定要销毁");
85     destoryLinkList(&LTwo);
86 
87     //此时销毁的表长规定是0
88     puts("销毁之后,链表长度:");
89     getLength(LTwo);
90 
91     system("pause"); 
92     return 0;
93 }
复制代码

scanf函数的特点是接受单词,而不是字符串,字符串一般是gets函数,单个字符接收是getchar函数,因为scanf函数遇到空白字符(tab,空格,回车,制表符等)就不再读取输入,那字符串怎么能方便输入?

但是输入队列里如果还有字符,那么会留到缓存内,需要在定义里使用getchar函数来消除回车带来的影响。

 

辛苦的劳动,转载请注明出处,谢谢……
http://www.cnblogs.com/kubixuesheng/p/4057063.html

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
C语言OJ项目参考(2417) 字符串长度
2417: 字符串长度 Description 写一函数,求一个字符串的长度。在main函数中输入字符串,并输出其长度。 Input 一行字符串 Output 字符串长度 Sample Input** t9g(*&WE3@#$fw2adECWEr Sample Output 22 HINT 主函数已给定如下,提交时不需要包含下述主函数 /* C代码
744 0
谈谈C语言的字面字符串
通过几段小程序深入分析了C语言中字面字符串(literal string)的特点以及正确的使用方式。
2603 0
C语言---递归反向输出任意长度的字符串
(该字符串可以包含空格和回车!) 【题目要求】 编写一个递归函数,实现将输入的任意长度的字符串反向输出的功能。 例如输入字符串:ABCD,输出字符串:DCBA。 【题目分析】 应用递归的思想有时可以很轻松地解决一些看似不太容易实现的功能。
1056 0
C语言 复制字符串 malloc
今天在看前辈的代码,对其中字符串复制有时候直接把指针赋给另一个指针,有的malloc一个内存,然后把整个字符串的值拷贝过来,有点费解,就研究了一下,会了之后发现也没什么奥秘,其实很简单,不过还是记录一下比较好。
596 0
文章
问答
文章排行榜
最热
最新
相关课程
更多
相关电子书
更多
探究高性能的海量节点树
立即下载
存储分层企业数据存储类型选择与优化
立即下载
如何使用Tair增强数据结构构建丰富在线实时场景
立即下载