-
2.3 带头结点的单链表：理论+编程实战（C语言详细）
2.1 链式存储概述 和 2.2 线性表的链式存储–单链表（C语言详细实现）
2.3 带头结点的单链表
1、 带头结点的单链表基本概念
单连表的缺点：
- 单链表的插入和删除操作必须对在空的单链表插入新结点、删除结点后单链表成为空表等特殊情况做特殊处理。
- 为减少对特殊情况的判断处理，可以在单链表中设置一个特殊的结点，这个结点有单链表的首指针指示，只要有这个单链表，该结点就永远不会被删除。
2、ADT描述
数据集合 K：K={k1,k2,k3…,kn},n≥0，K中的元素是datatype类型；
数据关系R：R={r} ， r = {
操作集合如下：
函数 功能 node *init() 建立一个空的带头结点的单链表 void display(node *head, int i) 输出带头结点的单链表中各个结点的值 node *findth(node *head, int i) 按序号查找，在带头结点的单链表中查找第i个结点 node* find(node* head, datatype x) 按值查找，在带头结点的链表中查找值为x的结点 node *insert(node *head , datatype x) 在带头结点的单链表中插入一个值为x的结点 node *dele(node *head, datatype x) 在带头结点的单链表中删除一个值为x的结点 int length(node *head) 查询带头结点的链表的长度 3、重要操作
- 插入（在第i-1(1<= i <=n+1 )）个结点后插入一个值为x的新结点
- 1 先构造一个新结点，用s指向
- 2 在找到链表的第i-1个结点，用p指向
- 3 然后修改指针，插入结点（p之后插入新结点是s）
2. 删除（删除链表的第i(1<=i<=n)）个位置上的结点- 1 先找到链表的第i-1个结点，用p指向
- 2 再用指针s指向要删除的结点（p的下一个结点）
- 3 然后修改指针，删除s所指结点
- 最后释放s所指结点的空间，这样内存空间才不会泄漏
3、编程实战
-
头文件：head_single_linked_list.h
#pragma once #ifndef __HEAD_SINGLE_LINKED_LIST_H #define __HEAD_SINGLE_LINKED_LIST_H #include#include #define error NULL typedef int datatype; typedef struct hslink_list { datatype info; struct hslink_list* next; }hs_node; //建立一个空的带头结点的单链表 hs_node* init(); //输出带头结点的单链表中各个结点的值 void display(hs_node* head); //按序号查找，在带头结点的单链表中查找第i个结点 hs_node* findth(hs_node* head, int i); //按值查找，在带头结点的链表中查找值为x的结点 int find(hs_node* head, datatype x); //在带头结点的单链表中插入一个值为x的结点 void insert(hs_node* head, datatype x, int pos); //在带头结点的单链表中删除一个值为x的结点 void dele(hs_node* head, datatype x); //查询带头结点的链表的长度 int length(hs_node* head); #endif // !__HEAD_SINGLE_LINKED_LIST_H - 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
-
函数定义：head_single_linked_list.c
#include"head_single_linked_list.h" /* //带头结点的单链表初始化 参数：空 返回值：指向hs_node类型的指针 */ hs_node* init() { hs_node* head; head = (hs_node*)malloc(sizeof(hs_node)); head->next = NULL; printf("链表创建成功！\n"); return head; } /* 功能：输出带头结点的单链表中从头到尾各个结点的值 */ void display(hs_node* head) { hs_node* p; p = head->next; if (!p) { printf("The head single linked list is empty, can not display\n"); //exit(1); } else { printf("The head single linked list's value is :\n"); while (p) { printf("%5d", p->info); p = p->next; } printf("\n"); } } hs_node* findth(hs_node* head, int i) { hs_node* p=head; int j = 0; //p = head; if (i < 0) { printf("this--%d node is not exit!\n", i); } else if (i == 0) return p; else { while (p&&j!=i) //当p不为空且j小于i时，往下查找 { p = p->next; j++; } return p; //如果找到则返回指向i结点的指针；否则返回指向为NULL尾结点的指针 } } /* 功能：定值查找，给定一个值，找到返回其位置序号，否则返回0 */ int find(hs_node* head, datatype x) { hs_node* p; p = head->next; int i = 1; while (p!=NULL&&p->info!=x) { p = p->next; i++; } if (!p) { return 0; } else { return i; } } /* 功能：指定链表位置pos插入一个值为x的结点 返回：链表头结点的指针 */ void insert(hs_node* head, datatype x, int pos) { hs_node* p, * q; q=findth(head, pos); if (!q) { printf("链表中不存在第%d个结点！不能插入%d", pos, x); exit(1); //return 0; } p = (hs_node*)malloc(sizeof(hs_node)); p->info = x; p->next = q->next; q->next = p; printf("%3d插入成功！\n",x); //return 1; } /* 功能：删除值为x的结点 */ void dele(hs_node* head, datatype x) { hs_node* pre=head, * q; q = head->next; while (q&&q->info!=x) { pre = q; q = q->next; } if (q) //当q指针不为空时，说明找到了值为x的结点 { pre->next = q->next; //跳过q指向的结点 free(q); //释放q指向的结点，防止内存泄漏 printf("删除操作成功！\n"); } else printf("删除失败！\n"); } /* 计算链表的长度（不包含头结点） */ int length(hs_node* head) { int len = 0; hs_node* p ; p = head->next; while (p) { len++; p = p->next; } return len; }- 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
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
-
main.c
#include"head_single_linked_list.h" void main() { struct hslink_list* head; head = init(); int command = 0, position; while (command<5) { insert(head, command, command ); command++; } while (command<10) { printf("input command:1:init 2:findth 3:find 4:insert 5:dele 6:length 7:display\n"); scanf_s("%d", &command); switch (command) { case 1:free(head); head = init(); break; case 2: { printf("请输入要查找结点的序号：\n"); scanf_s("%d", &command); findth(head, command); break; } case 3: { printf("请输入要查找结点的值：\n"); scanf_s("%d", &command); command=find(head, command); printf("该结点在第%d个位置\n", command); break; } case 4: { printf("请输入要查找结点的值和位置：\n"); scanf_s("%d%d", &command,&position); insert(head, command, position); break; } case 5: { printf("请输入要删除结点的值：\n"); scanf_s("%d", &command); dele(head, command); break; } case 6:printf("该链表不包含头结点一共有%d个结点\n", length(head)); break; case 7:display(head); break; default:printf("The command is error ,please input again!\n");break; } } }- 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
4、程序运行结果：
-
相关阅读:
MyCat的安装
在linux服务器运行python脚本异常ModuleNotFoundError: No module named '_ssl'
jeesite添加多数据源
STM8的C语言编程（11）－－+切换时钟源
[SDR] GNU Radio 系列教程（二） —— 绘制第一个信号分析流程图
把JS中的map方法玩出花来
Unity 之Material 类型和 MeshRenderer 组件中的 Materials 之间有一些重要的区别
UML 用户指南
ACM学习书籍简介
Keep a good habit Privacy Policy
- 原文地址：https://blog.csdn.net/qq_45986997/article/details/126022132
