热门标签
热门文章
- 1mediapipe KNN 基于mediapipe和KNN的引体向上计数/深蹲计数/俯卧撑计数【mediapipe】【KNN】【BlazePose】【K邻近算法】【python】_python mediapipe knn
- 2小程序wxcharts绘制曲线图_小程序 曲线图
- 3Qt 配置 FFmpeg
- 4OutOfMemoryError: CUDA out of memory.Tried to allocate 128.00 MiB.......却未占用显存，个人方法简单实用_pytorch_cuda_alloc_conf=expandable_segments:true
- 5搭建docker的shipyard管理平台(中文)_shipyard平台
- 6Harmony - Apache Top-Level project - 简介
- 7ChatGPT Alpha 与 GPT-3.5 、GPT-4 详细对比评测
- 8白帽子讲web安全-第二章 http协议和web应用_web安全协议
- 9C# 异步编程_c# 异步方法没有返回程序执行完问题
- 10【Python】判断素数的三种方法以及for-else语句的介绍_python判断素数
当前位置: article > 正文
单链表(C语言版）_c语言单链表
作者：你好赵伟 | 2024-04-29 04:47:16
赞
踩
c语言单链表
单链表(C语言版）
1.单链表的概念和结构
1.1 概念
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表
中的指针链接次序实现的 ，逻辑上是连续的，有顺序的。
1.2 结构
1.3 链表的8种结构
实际中要实现的链表的结构非常多样，以下情况组合起来就有8种链表结构：
- 单向、双向
- 带头、不带头
- 循环、非循环
2.单链表的实现
2.1 定义结点
单链表的英文是：Single Linked List（简称：SL,区别于顺序表的 SeqList 或 SQL)
typedef int SLTDataType;
struct SListNode
{
SLTDataType data;//int data;
struct SListNode* next;//为结构体指针，是指针，不是结构体，结构体里面不可嵌套结构体
};
typedef struct SListNode SLTNode;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
2.2 打印单链表
void SListPrint(SLTNode* phead) //头结点：phead,plist表示 { SLTNode* cur = phead; while (cur != NULL) { printf("%d->", cur->data);//data数据域 cur = cur->next; //next指向指针域 } printf("NULL\n"); } SLTNode* BuySListNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); newnode->data = x; newnode->next = NULL; return newnode; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
2.3 尾插单链表
//尾插单链表 void SListPushBack(SLTNode** pphead, SLTDataType x)//传二级指针，不然为形参，不改变 { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); newnode->data = x; newnode->next = NULL; if (*pphead == NULL) { *pphead = newnode; //newnode:尾插的元素数 } else { SLTNode* tail = *pphead; while (tail->next != NULL) //尾指针：tail表示 { tail = tail->next; } tail->next = newnode; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
2.4 头插单链表
//头插单链表
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
SLTNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
2.5 头删单链表
//头删单链表 PopFront
void SListPopFront(SLTNode** pphead)
{
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
2.6 尾删单链表
//尾删单链表 PopBack //1.链表为空 //2.只有一个结点 //3.至少有两个结点（正常情况） void SListPopBack(SLTNode** pphead) { if (*pphead = NULL) { return; } else if((*pphead)->next=NULL) { free(*pphead); *pphead = NULL; } else { SLTNode* prev = NULL; SLTNode* tail = *pphead; while (tail->next != NULL) { prev = tail; tail = tail->next; } free(tail); prev->next = 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
2.7 查找某个结点（pos)
//找x Find
SLTNode* SListFind(SLTNode* pphead, SLTDataType x)
{
SLTNode* cur = pphead;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
2.7.1 在pos前插入newnode
//在pos前面插入x Insert void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { if (pos == *pphead) { SListPushFront(pphead, x); } else { SLTNode* newnode = BuySListNode(x);; SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = newnode; newnode->next = pos; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
2.7.2 删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)//删除pos位置的值 //1.删的为头指针 //2.其他正常情况 { if (pos == *pphead) { SListPopFront(pphead); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
2.8 销毁单链表
//销毁单链表
void SListDestory(SLTNode** pphead)
{
assert(pphead);
SLTNode* cur = *pphead;
while (cur)
{
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
3.代码集
Slist.h
#pragma once//防止重复定义头文件 #include<stdio.h> #include<stdlib.h> typedef int SLTDataType; struct SListNode { SLTDataType data;//int data; struct SListNode* next;//为结构体指针，是指针，不是结构体，结构体里面不可嵌套结构体 }; typedef struct SListNode SLTNode; //不会改变链表的头指针，传一级指针 void SListPrint(SLTNode* phead);//打印 //可能会改变链表的头指针，传二级指针 void SListPushBack(SLTNode** pphead,SLTDataType x);//尾插 void SListPushFront(SLTNode** pphead, SLTDataType x);//头插 void SListPopBack(SLTNode** pphead);//尾删 void SListPopFront(SLTNode** pphead);//头删 SLTNode* SListFind(SLTNode** pphead, SLTDataType x);//找x void SListInsert(SLTNode** pphead,SLTNode* pos, SLTDataType x);//在pos前面插入x void SListErase(SLTNode** pphead, SLTNode* pos);//删除pos位置的值 void SListDestory(SLTNode** pphead);//销毁单链表
- 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
Slist.c
#include"SList.h" //打印单链表 void SListPrint(SLTNode* phead) //头结点：phead,plist表示 { SLTNode* cur = phead; while (cur != NULL) { printf("%d->", cur->data);//data数据域 cur = cur->next; //next指向指针域 } printf("NULL\n"); } SLTNode* BuySListNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); newnode->data = x; newnode->next = NULL; return newnode; } //尾插单链表 void SListPushBack(SLTNode** pphead, SLTDataType x)//传二级指针，不然为形参，不改变 { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); newnode->data = x; newnode->next = NULL; if (*pphead == NULL) { *pphead = newnode; //newnode:尾插的元素数 } else { SLTNode* tail = *pphead; while (tail->next != NULL) //尾指针：tail表示 { tail = tail->next; } tail->next = newnode; } } //头插单链表 void SListPushFront(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuySListNode(x); newnode->next = *pphead; *pphead = newnode; } //头删单链表 PopFront void SListPopFront(SLTNode** pphead) { SLTNode* next = (*pphead)->next; free(*pphead); *pphead = next; } //尾删单链表 PopBack //1.链表为空 //2.只有一个结点 //3.至少有两个结点（正常情况） void SListPopBack(SLTNode** pphead) { if (*pphead = NULL) { return; } else if((*pphead)->next=NULL) { free(*pphead); *pphead = NULL; } else { SLTNode* prev = NULL; SLTNode* tail = *pphead; while (tail->next != NULL) { prev = tail; tail = tail->next; } free(tail); prev->next = NULL; } } //找x Find SLTNode* SListFind(SLTNode* pphead, SLTDataType x) { SLTNode* cur = pphead; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } //在pos前面插入x Insert void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { if (pos == *pphead) { SListPushFront(pphead, x); } else { SLTNode* newnode = BuySListNode(x);; SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = newnode; newnode->next = pos; } } void SListErase(SLTNode** pphead, SLTNode* pos)//删除pos位置的值 //1.删的为头指针 //2.其他正常情况 { if (pos == *pphead) { SListPopFront(pphead); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); } } //销毁单链表 void SListDestory(SLTNode** pphead) { assert(pphead); SLTNode* cur = *pphead; while (cur) { SLTNode* next = cur->next; free(cur); cur = next; } *pphead = 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
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
Test.c
#include "SList.h" //尾插 void TestSList1() { SLTNode* plist = NULL; SListPushBack(&plist, 1); SListPushBack(&plist, 2); SListPushBack(&plist, 3); SListPushBack(&plist, 4); SListPushFront(&plist,0); SListPrint(plist); SListPopFront(&plist); SListPopFront(&plist); SListPopFront(&plist); SListPrint(plist); SListPopFront(&plist); SListPrint(plist); } void TestSList3() { SLTNode* plist = NULL; SListPushBack(&plist, 1); SListPushBack(&plist, 2); SListPushBack(&plist, 3); SListPushBack(&plist, 4); SListPrint(plist); // 想在1的前面插入一个10 SLTNode* pos = SListFind(plist, 1); if (pos) { SListInsert(&plist, pos, 10); } SListPrint(plist); //想在3的前面插入一个30 pos = SListFind(plist, 3); if (pos) { SListInsert(&plist, pos, 30); } SListPrint(plist); } void TestSList4() { SLTNode* plist = NULL; SListPushBack(&plist, 1); SListPushBack(&plist, 2); SListPushBack(&plist, 3); SListPushBack(&plist, 4); SListPrint(plist); SLTNode* pos = SListFind(plist, 1);//删除1 if (pos) { SListErase(&plist, pos); } SListPrint(plist); pos = SListFind(plist, 4);//删除4 if (pos) { SListErase(&plist, pos); } SListPrint(plist); pos = SListFind(plist, 2);//删除2 if (pos) { SListErase(&plist, pos); } SListPrint(plist); } int main() { TestSList4(); 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
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/506027?site
推荐阅读
![[转载] 在IIS上启用https的免费ssl证书使用教程](https://img-blog.csdnimg.cn/img_convert/928e3871e848410eb3c0f49443499229.png?x-oss-process=image/resize,m_fixed,h_300,image/format,png)
相关标签
Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。
