-
[一篇读懂]C语言十讲：单链表的新建、查找
[一篇读懂]C语言十讲：单链表的新建、查找
1. 与408关联解析及本节内容介绍
1 与408关联解析
【2019年单链表】
41.(13分)设线性表 L = ( a 1 , a 2 , a 3 , … , a n − 2 , a n − 1 , a n ) L=(a_1,a_2 ,a_3,…,a_{n-2},a_{n-1},a_n) L=(a1,a2,a3,…,an−2,an−1,an)采用带头结点的单链表保存，链表中的结点定义如下：typedef struct node { int data; struct node* next; }NODE;- 1
- 2
- 3
- 4
请设计一个空间复杂度为O(1)且时间上尽可能高效的算法，重新排列L中的各结点，得到线性表 L = ( a 1 , a n , a 3 , a n − 1 , a 3 , a n − 2 , … ) L=(a_1,a_n ,a_3,a_{n-1},a_3,a_{n-2},…) L=(a1,an,a3,an−1,a3,an−2,…)。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
（3）说明你所设计的算法的时间复杂度。2 本节内容介绍
本节分为五小节讲解。
第一小节是针对头插法新建链表进行实战
第二小节是针对尾插法新建链表进行实战
第三小节是链表按位置查找及按值查找实战
第四小节是往第i个位置插入元素实战
第五小节是链表的调试方法解析
2. 头插法新建链表实战
- 一切数据结构 - 增删查改
上一讲介绍了链表的新增、删除、查找的原理。
- 头插法新建链表流程图：
画流程图很关键。
使用头插法来新建链表：
#include#include typedef int ElemType; //写分号 typedef struct LNode { ElemType data; //数据域 struct LNode* next; }LNode,*LinkList; //输入3，4，5，6，7，9999 void list_head_insert(LNode*& L)//LNode*是结构体指针 等价于 LinkList(常用) { //申请头结点空间，头指针指向头结点 L = (LinkList)malloc(sizeof(LNode));//不能写LinkList和LNode* - 结构体指针 - 大小8个字节 L->next = NULL;//头结点的next为NULL - 第一次读取时s->next = L->next =NULL //第一个结点 ElemType x;//第一个结点的数据 scanf("%d", &x); LNode *s;//指针s指向第一个结点 //s = (LinkList)malloc(sizeof(LNode)); //s->data = x;//x存放到数据域中 //s->next = NULL;//第一个结点最后会成为最后一个结点 - next指针应该为NULL //L->next = s;//头结点的next，就指向了第一个结点 while (x != 9999)//输入9999代表输入结束 - 不想把9999存入链表 { //scanf("%d", &x); s = (LinkList)malloc(sizeof(LNode)); s->data = x; //头插法，把插入的元素插到第一个位置 s->next = L->next;//s的next指向原本链表的第一个结点 L->next = s;//头结点的next指向新结点 scanf("%d", &x);//读取放在最后，读到结束的9999时就不会存入链表 } } void print_list(LinkList L) { L = L->next; while (L != NULL) { printf("%3d", L->data); L = L->next; } printf("\n"); } //头插法新建链表 int main() { LinkList L; //L是链表头指针，是结构体指针类型 - 大小8个字节 list_head_insert(L); //输入数据可以为3 4 5 6 7 9999，头插法新建链表 print_list(L); //链表打印 return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
3. 尾插法新建链表实战
- 尾插法新建链表流程图：
使用尾插法来新建链表：
#include#include typedef int ElemType; //写分号 typedef struct LNode { ElemType data; //数据域 struct LNode* next; }LNode, * LinkList; void list_tail_insert(LNode*& L) { L = (LinkList)malloc(sizeof(LNode));//申请头结点空间，头指针指向头结点 L->next = NULL;//头结点的next为NULL ElemType x; scanf("%d", &x); LNode* s, * r = L;//s用来指向申请的新节点，r始终指向列表尾部 while (x != 9999) { s = (LinkList)malloc(sizeof(LNode));//为新节点申请空间 s->data = x; r->next = s;//新节点给尾节点的next指针 r = s;//r要指向新的尾部 scanf("%d", &x); } r->next = NULL;//让尾节点的next为NULL } void print_list(LinkList L) { L = L->next; while (L != NULL) { printf("%3d", L->data); L = L->next; } printf("\n"); } //尾插法新建链表 int main() { LinkList L; //L是链表头指针，是结构体指针类型 - 大小8个字节 list_tail_insert(L); print_list(L); //链表打印 return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
4. 按位置查找及按值查找实战
- 按位置查找流程图：
- 查找位置时需要判断位置是否合法。
#include#include typedef int ElemType; //写分号 typedef struct LNode { ElemType data; //数据域 struct LNode* next; }LNode, * LinkList; void list_tail_insert(LNode*& L) { L = (LinkList)malloc(sizeof(LNode));//申请头结点空间，头指针指向头结点 L->next = NULL;//头结点的next为NULL ElemType x; scanf("%d", &x); LNode* s, * r = L;//s用来指向申请的新节点，r始终指向列表尾部 while (x != 9999) { s = (LinkList)malloc(sizeof(LNode));//为新节点申请空间 s->data = x; r->next = s;//新节点给尾节点的next指针 r = s;//r要指向新的尾部 scanf("%d", &x); } r->next = NULL;//让尾节点的next为NULL } void print_list(LinkList L) { L = L->next; while (L != NULL) { printf("%3d", L->data); L = L->next; } printf("\n"); } //按位置查找 LinkList GetElem(LinkList L, int SearchPos) { int j = 0; while (L && j < SearchPos)//L!=NULL，地址不为NULL { L = L->next; j++; } return L; } //按值查找 LinkList LocateElem(LinkList L, ElemType SearchVal) { while (L) { if (L->data == SearchVal)//如果找到对应的值，返回那个节点的地址 { return L; } L = L->next; } return NULL; } //尾插法新建链表 int main() { LinkList L; //L是链表头指针，是结构体指针类型 - 大小8个字节 list_tail_insert(L); print_list(L); //链表打印 LinkList search;//用来存储拿到的某一个节点 //按位置查找 search = GetElem(L, 2); if (search != NULL) { printf("Secceeded in searching by serial number\n"); printf("%d\n", search->data); } //按值查找 search = LocateElem(L, 6); if (search != NULL) { printf("Secceeded in searching by serial number\n"); printf("%d\n", search->data); } return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
5. 往第i个位置插入元素实战
- 往第i个位置插入元素流程图：
- 如果要从函数调用位置，跳转到函数定义位置，ctrl+鼠标左键点击。
#include#include typedef int ElemType; //写分号 typedef struct LNode { ElemType data; //数据域 struct LNode* next; }LNode, * LinkList; void list_tail_insert(LNode*& L) { L = (LinkList)malloc(sizeof(LNode));//申请头结点空间，头指针指向头结点 L->next = NULL;//头结点的next为NULL ElemType x; scanf("%d", &x); LNode* s, * r = L;//s用来指向申请的新节点，r始终指向列表尾部 while (x != 9999) { s = (LinkList)malloc(sizeof(LNode));//为新节点申请空间 s->data = x; r->next = s;//新节点给尾节点的next指针 r = s;//r要指向新的尾部 scanf("%d", &x); } r->next = NULL;//让尾节点的next为NULL } void print_list(LinkList L) { L = L->next; while (L != NULL) { printf("%3d", L->data); L = L->next; } printf("\n"); } //按位置查找 LinkList GetElem(LinkList L, int SearchPos) { int j = 0; if (SearchPos < 0) { return NULL; } while (L && j < SearchPos)//L!=NULL，地址不为NULL { L = L->next; j++; } return L; } //按值查找 LinkList LocateElem(LinkList L, ElemType SearchVal) { while (L) { if (L->data == SearchVal)//如果找到对应的值，返回那个节点的地址 { return L; } L = L->next; } return NULL; } //i代表插入到第几个位置 bool ListFrontInsert(LinkList L, int i, ElemType InsertVal) { LinkList p = GetElem(L, i - 1); if (NULL == p) { return false; } LinkList q; q = (LinkList)malloc(sizeof(LNode));//为新节点申请空间 q->data = InsertVal; q->next = p->next; p->next = q; return true; } //尾插法新建链表 int main() { LinkList L; //L是链表头指针，是结构体指针类型 - 大小8个字节 list_tail_insert(L); print_list(L); //链表打印 LinkList search;//用来存储拿到的某一个节点 bool ret; ret = ListFrontInsert(L, 2, 99);//新节点插入第i个位置 print_list(L); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
6. 链表的调试方法
- 链表中每一个结点在内存中是不连续的，通过单步调试，在变量窗口，依次点开头指针L，观察每一个结点是否符合自己的预期。
总结
2
- 头插法新建链表流程图：
3
- 尾插法新建链表流程图：
4
- 按位置查找流程图：
5
- 往第i个位置插入元素流程图：
6
- 链表中每一个结点在内存中是不连续的，通过单步调试，在变量窗口，依次点开头指针L，观察每一个结点是否符合自己的预期。
-
相关阅读:
Android面试每日一题(4)： 哪些情况下会导致oom问题？
SCP命令在不同远程服务器之间发送文件（指定端口）
源码分享-HTML文档解析---GoLang实现
自动化测试框架Pytest（八）——断言
VS五子棋大战
docker 安装 nginx
来自多彩世界的控制台——C#控制台输出彩色字符画
一文总结现代 C++ 中的初始化
【Azure】微软 Azure 基础解析（九）Azure 标识、身份管理、Azure AD 的功能与用途
java源码系列：HashMap源码验证，自己写的HashMap性能高吗？为什么在JDK8中新增红黑树？
- 原文地址：https://blog.csdn.net/m0_58991879/article/details/128002472
