-
数据结构C语言：单链表和双链表的实现（不带头节点的单链表、带头的双链表）
单链表
- 写不带头节点的单链表的一些注意点：
单链表的头节点可能经常会变化，所以函数中常用二级指针。因为改变指针自身，写的函数参数需要是二级指针来接收。如果打印或者不需要改变头指针，用一级指针即可，如双链表。
1. 头文件
// SeqList.h #pragma once #include#include #include typedef int SLDateType; typedef struct SeqList { SLDateType* a; size_t size; size_t capacity; // unsigned int }SeqList; // 对数据的管理:增删查改 void SeqListInit(SeqList* ps); void SeqListDestroy(SeqList* ps); void SeqListPrint(SeqList* ps); void SeqListPushBack(SeqList* ps, SLDateType x); void SeqListPushFront(SeqList* ps, SLDateType x); void SeqListPopFront(SeqList* ps); void SeqListPopBack(SeqList* ps); // 顺序表查找 int SeqListFind(SeqList* ps, SLDateType x); // 顺序表在pos位置插入x void SeqListInsert(SeqList* ps, size_t pos, SLDateType x); // 顺序表删除pos位置的值 void SeqListErase(SeqList* ps, size_t pos); - 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
2. 头文件函数的实现
#include "ds_1_seqlst.h" // 1. ??** 初始化给一点吧?视频怎么给的 void SeqListInit(SeqList* ps) { // 落了这个？ 让a为NULL ps->a = NULL; // 容量 ps->capacity = 0; // 当前size ps->size = 0; } // 注意free申请的空间 void SeqListDestroy(SeqList* ps) { // free并置空，忘了free free(ps->a); ps->a = NULL; ps->size = 0; ps->capacity = 0; } void SeqListPrint(SeqList* ps) { assert(ps); for (int i = 0; i < ps->size; i++) { // 可以用： ps->(a[i]); printf("%d ", ps->a[i]); } printf("\n"); } void CheckCapacity(SeqList* ps) { assert(ps); if (ps->capacity == ps->size) { // 1. 定义新的大小 防止初始化是0，扩容给2倍仍是0 //int newcapacity = ps->capacity*2; int newcapacity = ps->capacity == 0?2: ps->capacity* 2; // 2. malloc申请全新arr空间：(类型)malloc(大小) 和realloc不一样 //SLDateType* newp = (SLDateType*)malloc(sizeof(SLDateType)*newcapacity); // 2. realloc直接对原来申请：参数要给原空间 都要强转，比malloc多一个原始指向 SLDateType* newp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * newcapacity); if (newp==NULL) { printf("realloc fail"); exit(-1); } ps->a = newp; ps->capacity = newcapacity; // capacity是最大容量 } } void SeqListPushBack(SeqList* ps, SLDateType x) { assert(ps); CheckCapacity(ps); ps->a[ps->size] = x; ps->size++; } void SeqListPushFront(SeqList* ps, SLDateType x) { CheckCapacity(ps); int end = ps->size - 1; while (end >= 0) { ps->a[end+1] = ps->a[end]; end--; } // 挪完才放 ps->a[0] = x; // 大小一定得加 ps->size++; } void SeqListPopFront(SeqList* ps) { assert(ps); assert(ps->size>0); // for (int i = 0; i < ps->size - 1; i++) { ps->a[i] = ps->a[i + 1]; } ps->size--; } void SeqListPopBack(SeqList* ps) { assert(ps); assert(ps->size > 0); ps->size--; } int SeqListFind(SeqList* ps, SLDateType x) { assert(ps); // 做O(n)的遍历 for(int i = 0;i < ps->size;i++) { if (ps->a[i] == x) { return i; } } return -1; } void SeqListInsert(SeqList* ps, size_t pos, SLDateType x) { assert(ps); // 标记 ，看它有没有内容 //assert(ps->size > 0); // 应该检查它插入位置合法吗 assert(pos >= 0 && pos <= ps->size); CheckCapacity(ps); for (int i = ps->size;i>pos;i--) { ps->a[i] = ps->a[i-1]; } ps->a[pos] = x; ps->size++; } void SeqListErase(SeqList* ps, size_t pos) { assert(ps); // 标记 ，看它有没有内容 //assert(ps->size > 0); // 保证pos合法 assert(pos >= 0 && pos < ps->size); // ?????????有一个位置的出入 for (int i = pos;i<ps->size-1;i++) { ps->a[i] = ps->a[i+1]; } ps->size--; } // 移除题：双指针做法和开辟新空间做法。- 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
- 143
- 144
- 145
- 146
- 147
3. 测试
#include "ds_1_seqlst.h" int main() { SeqList s; // 函数中全是地址，用指针接收 SeqListInit(&s); SeqListInsert(&s, 0, 1); SeqListPushBack(&s, 5); SeqListPrint(&s); SeqListPushFront(&s, 6); SeqListPrint(&s); int pos = SeqListFind(&s, 6); printf("找到在%d\n", pos); printf("popfront之后\n", pos); SeqListPopFront(&s); SeqListPrint(&s); int pos2 = SeqListFind(&s, 15); printf("找个不在的，结果是%d\n", pos2); printf("下面是销毁\n"); SeqListDestroy(&s); 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
4. 效果
双链表
- 写带头节点的双链表的一些注意点：
- 插入必涉及4个指针，头插和尾插都是
- pop()，不管是头出还是尾出，都涉及2个指针
- 断言assert()的使用：assert(q)中q应是正确条件，当q==null时，会报错，比如下面代码中assert(cur->next!=null)就不会报错，简言之，它替你检查某值是否成立，你应放入你希望的情况。
- 带头节点的双链表因为不改变头节点，只改指向，所以只需要传一级指针。只要头节点，或尾节点本身发生改变才需要用二级指针接收。
- 因为带头节点且头节点不存值并永不变，只改变指向，即内容，用一级指针即可。如4中所说。
1. 头文件
#include#include #include typedef int LTDataType; typedef struct ListNode { LTDataType _data; struct ListNode* _next; struct ListNode* _prev; }ListNode; // 创建返回链表的头结点. ListNode* ListCreate(); // 双向链表销毁 void ListDestory(ListNode* pHead); // 双向链表打印 void ListPrint(ListNode* pHead); // 双向链表尾插 void ListPushBack(ListNode* pHead, LTDataType x); // 双向链表尾删 void ListPopBack(ListNode* pHead); // 双向链表头插 void ListPushFront(ListNode* pHead, LTDataType x); // 双向链表头删 void ListPopFront(ListNode* pHead); // 双向链表查找 ListNode* ListFind(ListNode* pHead, LTDataType x); // 双向链表在pos的前面进行插入 void ListInsert(ListNode* pos, LTDataType x); // 双向链表删除pos位置的节点 void ListErase(ListNode* pos); - 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
2. 头文件函数的实现
#include "ds_1_link_loop.h" // 创建返回链表的头结点. // 用指针类型的create创建，返回该类型即可，不需要用二级指针参数 ListNode* ListCreate() { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); newnode->_data = 0; newnode->_next = newnode; newnode->_prev = newnode; // malloc申请的空间，返回不会被撤销 return newnode; } ListNode* BuyListNode(LTDataType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); newnode->_data = x; newnode->_next = NULL; newnode->_prev = NULL; return newnode; } void ListPrint(ListNode* pHead) { assert(pHead); // 打印不打印头节点，因为双向循环的头，只是摆设 ListNode* cur = pHead->_next; // **判断有无节点的方法就是看头下一是否是头** printf("pead<=>"); while (cur!=pHead) { printf("%d<=>", cur->_data); cur = cur->_next; } printf("\n"); } void ListPushBack(ListNode* pHead, LTDataType x) { // 只要带头节点，就不会有空 assert(pHead); ListNode* newnode = BuyListNode(x); // 双链表一定是有4条语句的 /*pHead->_prev->_next = newnode; newnode->_next = pHead; newnode->_prev = pHead->_prev; pHead->_prev = newnode;*/ ListInsert(pHead, x); } // 要改变的是pHead里面的指针，没有变pHead本身，头插法是给头下一个插 void ListPushFront(ListNode* pHead, LTDataType x) { // 头插也得4条，我还是少了一条 assert(pHead); ListNode* newnode = BuyListNode(x); newnode->_next = pHead->_next; pHead->_next->_prev = newnode; pHead->_next = newnode; newnode->_prev = pHead; } // pop出必须检查两次，assert是不是出头 // assert不成立才报错： assert(pHead-_next!=pHead); void ListPopFront(ListNode* pHead) { // 如果链表空或链表只有头节点，不然不能pop assert(pHead); assert(pHead->_next != pHead); ListErase(pHead->_next); } // pop出不能只有链表头节点 void ListPopBack(ListNode* pHead) { assert(pHead); assert(pHead->_next!=pHead); ListErase(pHead->_prev); } // 主要是节点不能是头节点 // 擦除：必须左两个指针变化 void ListErase(ListNode* pos) { assert(pos); pos->_next->_prev = pos->_prev; pos->_prev->_next = pos->_next; free(pos); } ListNode* ListFind(ListNode* pHead, LTDataType x) { assert(pHead); ListNode* cur = pHead->_next; // cur不可以空 assert(cur!=pHead); // 寻找过程中，只有当前没到头 while (cur!= pHead) { if (cur->_data == x) { return cur; } cur=cur->_next; } return NULL; } // 在pos之前插 void ListInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* newnode = BuyListNode(x); pos->_prev->_next = newnode; newnode->_prev = pos->_prev; pos->_prev = newnode; newnode->_next = pos; } // 直接全部销毁 用一级指针是因为不改变pHead本身 只改变它里面的指针指向11 void clear(ListNode* pHead) { assert(pHead); ListNode* cur = pHead->_next; while (cur != pHead) { ListNode* next = cur->_next; free(cur); cur = next; } pHead->_next = pHead; pHead->_prev = pHead; } // 直接全部销毁 需要二级 void ListDestory(ListNode** pHead) { assert(*pHead); clear(*pHead); free(*pHead); *pHead = NULL; }- 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
- 143
- 144
- 145
- 146
- 147
- 148
- 149
3. 测试函数
#include "ds_1_link_loop.h" int main() { ListNode* head = ListCreate(); // node指针接收node指针 没问题 ListPrint(head); printf("头插1、2、3，结果变成3、2、1\n"); // 传节点本身，用地址接收： // 我今天需要弄懂传 &head和传head的区别,，分别要用什么来接 // 我现在感觉传head本身，head是指针，因为访问节点用结构体指针 // 接收可以用一级指针，因为这里只是输出，用同级的东西，传 // 而一般指针接收变量，才给&，如果是二级指针，那就传 &一级指针 ListPushFront(head, 1); ListPushFront(head, 2); ListPushFront(head, 3); ListPrint(head); printf("尾插4、5、6，结果加上4、5、6\n"); ListPushBack(head, 4); ListPushBack(head, 5); ListPushBack(head, 6); ListPrint(head); printf("尾出两个还有4个\n"); ListPopBack(head); ListPopBack(head); ListPrint(head); printf("头出两个还有2个\n"); ListPopFront(head); ListPopFront(head); ListPrint(head); printf("寻找值为3的节点\n"); ListNode* node = ListFind(head, 3); if (node == NULL) { printf("找不到某特值的节点\n"); } else { printf("找得到，该节点值为%d\n", node->_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
4. 运行效果
-
相关阅读:
springboot如何返回中文json，保证顺序。LinkedHashMap应用实例
从地址中如何提取或者识别街道？支持模糊地址
java-net-php-python-04海信集团售后管理系统计算机毕业设计程序
MySQL - 对字符串字段创建索引
Laravel9版本的CMS出现Invalid datetime format异常
python+django协同过滤算法的美食O2O外卖点餐系统vue
springboot集成redisson
基于Python的接口自动化-构建mock接口服务
大白话讲解MySQL 索引，页分裂，行溢出，事务
Go语言入门(一)
- 原文地址：https://blog.csdn.net/myscratch/article/details/126197581
