目录
创新互联是一家专注于
网站设计制作、成都网站建设与策划设计,临漳网站建设哪家好?
创新互联做网站,专注于网站建设十余年,网设计领域的专业建站公司;建站业务涵盖:临漳等地区。临漳做网站价格咨询:028-86922220
前言
一、什么是链表
1.1链表的结构和概念
1.2 链表的分类
二、无头单向非循环链表
2.1 创建结构体
2.2 动态申请一个节点
2.3 单链表打印
2.4 单链表尾插/尾删
2.4.1 单链表尾插
2.4.2 单链表尾删
2.5 单链表头插/头删
2.5.1 头插
2.5.2 头删
2.6 单链表查找
2.7 单链表中间插入/中间删除
2.7.1 中间插入
2.7.2 中间删除
2.8 单链表销毁
三、双向带头循环链表
3.1 结构体的创建
3.2 创造节点
3.3 创建返回链表的头结点(哨兵位)
3.4 双链表打印
3.5 双链表的尾插/尾删
3.5.1 尾插
3.5.2 尾删
3.6 双链表的头插/头删
3.6.1 头插
3.6.2 头删
3.7 双链表的查找
3.8 双链表的中间插入/中间删除
3.8.1 中间插入
3.8.2 中间删除
3.9 双链表的销毁
四、链表和顺序表的区别
五、代码及代码展示
5.1 单向链表
5.1.1 效果展示
5.1.2 代码
5.2 双向带头循环链表
5.2.1 效果展示
5.2.2 代码
总结
前言
大家好，本篇文章主要带领大家了解一下什么是链表，链表的两个主要结构，以及链表和顺序表的差别。
一、什么是链表
1.1链表的结构和概念
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
链表就像是火车，每块空间都独立存在，彼此通过指针相链接。
链表的数据结构如下所示：
注意：
1.从上图看出，链式结构逻辑上是连续的，但在内存中的存储可能是不连续的。
2.现实中的节点一般都是在堆上面申请的。
3.从堆上面申请空间是有其规律的，两次申请的空间可能连续也可能不连续。
1.2 链表的分类
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
1.单向或者双向
2.带头(哨兵位)或者不带头
3.循环或者非循环
8种链表结构分别是：单向链表，单向带头，单向循环，单向带头循环，双向链表，双向带头，双向循环，双向带头循环
其中最常用的有两个分别是单向链表，双向带头循环链表。
1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等
2.带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。
接下来我们就带领大家实现这两个最常用的链表结构
ps：建议大家在完成链表时，每完成一个功能都测试一下，以免最后调bug调崩溃
二、无头单向非循环链表
本次链表我们将其分成三个文件SList.c，SList.h，test.c，分别用来实现，声明，测试。
ps：链表的全部代码以及效果展示会在文章末尾贴出
2.1 创建结构体
创建结构体，其中有两个成员，一个用来存储数据，一个用来指向下一个空间，并将其名字定义为SListNode方便后续使用
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;
}SListNode;
2.2 动态申请一个节点
申请节点我们用malloc函数，申请成功后返回空间地址，需要注意此时未和其他节点链接
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
SListNode* ptr = (SListNode*)malloc(sizeof(SListNode));
if (ptr == NULL)
{
perror("malloc");
exit(-1);
}
SListNode* Phead = ptr;
Phead->data = x;
Phead->next = NULL;
return Phead;
}
2.3 单链表打印
先写打印的函数，方便后续测试，将链表遍历一遍即可
// 单链表打印
void SListPrint(SListNode* plist)
{
SListNode* tail = plist;
while (tail)
{
printf("%d->", tail->data);
tail = tail->next;
}
printf("NULL\n");
}
2.4 单链表尾插/尾删
2.4.1 单链表尾插
先判断链表是否为空，为空则直接为其创建一个节点即可，不为空则需要遍历到最后一个节点进行插入。
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
if (*pplist == NULL)
{
*pplist=BuySListNode(x);
}
else
{
SListNode* tail = *pplist;
while (tail->next)
{
tail = tail->next;
}
tail->next = BuySListNode(x);
}
}
2.4.2 单链表尾删
尾删也就是尾插反着来即可，但是需要判断是否为空，为空则无法删除
// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
assert(*pplist);
SListNode* tail = *pplist;
while (tail->next->next)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
2.5 单链表头插/头删
2.5.1 头插
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
if (*pplist == NULL)
{
*pplist = BuySListNode(x);
}
else
{
SListNode* cur = BuySListNode(x);
cur->next = *pplist;
*pplist = cur;
}
}
2.5.2 头删
// 单链表头删
void SListPopFront(SListNode** pplist)
{
assert(*pplist);
SListNode* cur = *pplist;
*pplist = cur->next;
free(cur);
}
2.6 单链表查找
单链表查找主要是为了后面的中间插入删除，需要先找到要删的位置，遍历一遍链表就可以
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
assert(plist);
SListNode* cur = plist;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
2.7 单链表中间插入/中间删除
由于单链表只能从前往后走，而想要从中间位置插入或者删除数据，则需要改变前一个结构体的指针，所以只能插入或者删除指定位置后面的数据。
2.7.1 中间插入
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
assert(pos);
SListNode* a=BuySListNode(x);
SListNode* cur = pos->next;
pos->next = a;
a->next = cur;
}
2.7.2 中间删除
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
assert(pos);
if (pos->next == NULL)
{
return;
}
SListNode* cur = pos->next;
pos->next = cur->next;
free(cur);
}
2.8 单链表销毁
遍历一遍，一个一个释放即可
// 单链表的销毁
void SListDestroy(SListNode** pplist)
{
assert(*pplist);
while (*pplist)
{
SListNode* cur = (*pplist)->next;
free(*pplist);
*pplist = cur;
}
*pplist = NULL;
}
三、双向带头循环链表
本次链表我们将其分成三个文件List.c，List.h，test.c，分别用来实现，声明，测试。
ps：链表的全部代码以及效果展示会在文章末尾贴出
3.1 结构体的创建
创建结构体，其中有三个成员，一个用来存放数据，另外两个指针，分别指向前一个空间和后一个空间
// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
LTDataType _data;
struct ListNode* _next;
struct ListNode* _prev;
}ListNode;
3.2 创造节点
创造节点我们仍用malloc函数
//创造节点
ListNode* BuyLTNode(LTDataType x)
{
ListNode* cur = (ListNode*)malloc(sizeof(ListNode));
if (cur == NULL)
{
perror("malloc");
exit(-1);
}
cur->_data = x;
return cur;
}
3.3 创建返回链表的头结点(哨兵位)
当创建哨兵位时，我们一般将其中的数据赋为0，而且创建哨兵位的时候，链表只有哨兵位一个数据，所以其前后指针都指向自己以达到循环的目的。
// 创建返回链表的头结点.
ListNode* ListCreate()
{
ListNode* head = BuyLTNode(0);
head->_next = head;//循环列表创建头时头的首尾都指向自己
head->_prev = head;
return head;
}
3.4 双链表打印
从头的下一个节点开始遍历，当重新遍历到头部时，说明遍历完成。
// 双向链表打印
void ListPrint(ListNode* pHead)
{
assert(pHead);
ListNode* cur = pHead->_next;
while (cur!=pHead)
{
printf("%d->", cur->_data);
cur = cur->_next;
}
printf("head\n");
}
3.5 双链表的尾插/尾删
3.5.1 尾插
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* newnode = BuyLTNode(x);
newnode->_prev = pHead->_prev;//要尾插的节点的prev指向原来的尾节点
newnode->_next = pHead;//要尾插的节点的next指向头
pHead->_prev->_next = newnode;//原来的尾节点的next指向新尾
pHead->_prev = newnode;//头的prev指向新尾
}
3.5.2 尾删
// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
assert(pHead);
assert(pHead->_next!=pHead);
ListNode* tail = pHead->_prev;//用一个指针保存尾巴
tail->_prev->_next = pHead;//将倒数第二个节点的next指向头
pHead->_prev = tail->_prev;//头节点的prev指向倒数第二节点
free(tail);
}
3.6 双链表的头插/头删
3.6.1 头插
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* newnode = BuyLTNode(x);
newnode->_next = pHead->_next;//新空间的next指向原来的第一个数据
newnode->_prev = pHead;//新空间的prev指向头
pHead->_next->_prev = newnode;//原来的的一个数据的prev指向newnode
pHead->_next = newnode;//头的next指向newnode
}
3.6.2 头删
// 双向链表头删
void ListPopFront(ListNode* pHead)
{
assert(pHead);
assert(pHead->_next != pHead);//先判断链表中除了头有无其他数据
ListNode* oldnode = pHead->_next;//将要删除的数据的位置保存起来，以防后面丢失
pHead->_next = oldnode->_next;//头的next指向第二个数据
oldnode->_next->_prev = pHead;//第二个数据的prev指向头
free(oldnode);//释放数据空间即可
}
3.7 双链表的查找
主要是为后面的中间插入删除服务
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* cur = pHead->_next;
while (cur != pHead)
{
if (cur->_data == x)
{
return cur;
}
cur = cur->_next;
}
return NULL;
}
3.8 双链表的中间插入/中间删除
3.8.1 中间插入
要插入指定位置，其实就是插入到指定位置的前面即可
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);
//调整pos newnode pos前面的数据这三个空间的prev和next即可
ListNode* newnode = BuyLTNode(x);
ListNode* prev = pos->_prev;
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = pos;
pos->_prev = newnode;
}
3.8.2 中间删除
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
assert(pos);
ListNode* prev = pos->_prev;
ListNode* next = pos->_next;
free(pos);
prev->_next = next;
next->_prev = prev;
}
3.9 双链表的销毁
// 双向链表销毁
void ListDestory(ListNode* pHead)
{
assert(pHead);
ListNode* cur = pHead->_next;
ListNode* next = cur->_next;
while (cur != pHead)//先释放除头以外的所有节点，再释放头
{
free(cur);
cur = next;
next = next->_next;
}
free(cur);
}
四、链表和顺序表的区别
顺序表：
优点：尾删尾插效率高，访问随机下标快
缺点：空间不够需扩容（扩容代价大）；头插头删及中间插入删除需要挪动数据，效率低
链表
优点：需要扩容时，按需申请小块空间；任意位置插入效率都高（O(1)）
缺点：不支持下标随机访问
五、代码及代码展示
5.1 单向链表
5.1.1 效果展示
5.1.2 代码
SList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
SListNode* ptr = (SListNode*)malloc(sizeof(SListNode));
if (ptr == NULL)
{
perror("malloc");
exit(-1);
}
SListNode* Phead = ptr;
Phead->data = x;
Phead->next = NULL;
return Phead;
}
// 单链表打印
void SListPrint(SListNode* plist)
{
SListNode* tail = plist;
while (tail)
{
printf("%d->", tail->data);
tail = tail->next;
}
printf("NULL\n");
}
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
if (*pplist == NULL)
{
*pplist=BuySListNode(x);
}
else
{
SListNode* tail = *pplist;
while (tail->next)
{
tail = tail->next;
}
tail->next = BuySListNode(x);
}
}
// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
assert(*pplist);
SListNode* tail = *pplist;
while (tail->next->next)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
if (*pplist == NULL)
{
*pplist = BuySListNode(x);
}
else
{
SListNode* cur = BuySListNode(x);
cur->next = *pplist;
*pplist = cur;
}
}
// 单链表头删
void SListPopFront(SListNode** pplist)
{
assert(*pplist);
SListNode* cur = *pplist;
*pplist = cur->next;
free(cur);
}
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
assert(plist);
SListNode* cur = plist;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
assert(pos);
SListNode* a=BuySListNode(x);
SListNode* cur = pos->next;
pos->next = a;
a->next = cur;
}
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
assert(pos);
if (pos->next == NULL)
{
return;
}
SListNode* cur = pos->next;
pos->next = cur->next;
free(cur);
}
// 单链表的销毁
void SListDestroy(SListNode** pplist)
{
assert(*pplist);
while (*pplist)
{
SListNode* cur = (*pplist)->next;
free(*pplist);
*pplist = cur;
}
*pplist = NULL;
}
SList.h
#define _CRT_SECURE_NO_WARNINGS 1
#include#include#include
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;
}SListNode;
// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
// 单链表的销毁
void SListDestroy(SListNode** pplist);
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
void menu()
{
printf("*******************************\n");
printf("****1.尾部插入 2.尾部删除 ****\n");
printf("****3.头部插入 4.头部删除 ****\n");
printf("****5.中间插入 6.中间删除 ****\n");
printf("****7.打印 0.退出 ****\n");
printf("*******************************\n");
}
int main()
{
menu();
SListNode* Phead = NULL;
int input;
do
{
printf("请选择:");
scanf("%d", &input);
switch (input)
{
case 1:
printf("请输入要写入的数字：");
SLTDateType i;
scanf("%d", &i);
SListPushBack(&Phead,i);
break;
case 2:
SListPopBack(&Phead);
break;
case 3:
printf("请输入要写入的数字：");
SLTDateType a;
scanf("%d", &a);
SListPushFront(&Phead, a);
break;
case 4:
SListPopFront(&Phead);
break;
case 5:
printf("会将数据插入进输入数字之后的位置\n");
printf("请输入要插入位置的数字及要插入的数字：");
SLTDateType b, j;
scanf("%d %d", &b, &j);
SListNode* ret1 = SListFind(Phead, b);
if (ret1 != NULL)
{
SListInsertAfter(ret1, j);
}
else
{
printf("该数字不存在");
}
break;
case 6:
printf("请输入要删除的数字之前的数字:");
SLTDateType c;
scanf("%d", &c);
SListNode* ret2 = SListFind(Phead, c);
if (ret2 != NULL)
{
SListEraseAfter(ret2);
}
else
{
printf("未找到该数字");
}
break;
case 7:
SListPrint(Phead);
break;
case 0:
printf("退出");
SListDestroy(&Phead);
break;
default:
printf("输入错误，请重新输入");
break;
}
} while (input);
return 0;
}
5.2 双向带头循环链表
5.2.1 效果展示
5.2.2 代码
List.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
// 创建返回链表的头结点.
ListNode* ListCreate()
{
ListNode* head = BuyLTNode(0);
head->_next = head;//循环列表创建头时头的首尾都指向自己
head->_prev = head;
return head;
}
//创造节点
ListNode* BuyLTNode(LTDataType x)
{
ListNode* cur = (ListNode*)malloc(sizeof(ListNode));
if (cur == NULL)
{
perror("malloc");
exit(-1);
}
cur->_data = x;
return cur;
}
// 双向链表打印
void ListPrint(ListNode* pHead)
{
assert(pHead);
ListNode* cur = pHead->_next;
while (cur!=pHead)
{
printf("%d->", cur->_data);
cur = cur->_next;
}
printf("head\n");
}
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* newnode = BuyLTNode(x);
newnode->_prev = pHead->_prev;//要尾插的节点的prev指向原来的尾节点
newnode->_next = pHead;//要尾插的节点的next指向头
pHead->_prev->_next = newnode;//原来的尾节点的next指向新尾
pHead->_prev = newnode;//头的prev指向新尾
}
// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
assert(pHead);
assert(pHead->_next!=pHead);
ListNode* tail = pHead->_prev;//用一个指针保存尾巴
tail->_prev->_next = pHead;//将倒数第二个节点的next指向头
pHead->_prev = tail->_prev;//头节点的prev指向倒数第二节点
free(tail);
}
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* newnode = BuyLTNode(x);
newnode->_next = pHead->_next;//新空间的next指向原来的第一个数据
newnode->_prev = pHead;//新空间的prev指向头
pHead->_next->_prev = newnode;//原来的的一个数据的prev指向newnode
pHead->_next = newnode;//头的next指向newnode
}
// 双向链表头删
void ListPopFront(ListNode* pHead)
{
assert(pHead);
assert(pHead->_next != pHead);//先判断链表中除了头有无其他数据
ListNode* oldnode = pHead->_next;//将要删除的数据的位置保存起来，以防后面丢失
pHead->_next = oldnode->_next;//头的next指向第二个数据
oldnode->_next->_prev = pHead;//第二个数据的prev指向头
free(oldnode);//释放数据空间即可
}
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
assert(pHead);
ListNode* cur = pHead->_next;
while (cur != pHead)
{
if (cur->_data == x)
{
return cur;
}
cur = cur->_next;
}
return NULL;
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);
//调整pos newnode pos前面的数据这三个空间的prev和next即可
ListNode* newnode = BuyLTNode(x);
ListNode* prev = pos->_prev;
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = pos;
pos->_prev = newnode;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
assert(pos);
ListNode* prev = pos->_prev;
ListNode* next = pos->_next;
free(pos);
prev->_next = next;
next->_prev = prev;
}
// 双向链表销毁
void ListDestory(ListNode* pHead)
{
assert(pHead);
ListNode* cur = pHead->_next;
ListNode* next = cur->_next;
while (cur != pHead)//先释放除头以外的所有节点，再释放头
{
free(cur);
cur = next;
next = next->_next;
}
free(cur);
}
List.h
#define _CRT_SECURE_NO_WARNINGS 1
#include#include
#include// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
LTDataType _data;
struct ListNode* _next;
struct ListNode* _prev;
}ListNode;
//创造节点
ListNode* BuyLTNode(LTDataType x);
// 创建返回链表的头结点.
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);
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
void menu()
{
printf("*******************************\n");
printf("****1.尾部插入 2.尾部删除 ****\n");
printf("****3.头部插入 4.头部删除 ****\n");
printf("****5.中间插入 6.中间删除 ****\n");
printf("****7.打印 0.退出 ****\n");
printf("*******************************\n");
}
int main()
{
menu();
ListNode* head = ListCreate();
int input;
do
{
printf("请选择:");
scanf("%d", &input);
switch (input)
{
case 1:
printf("请输入要写入的数字：");
LTDataType i;
scanf("%d", &i);
ListPushBack(head, i);
break;
case 2:
ListPopBack(head);
break;
case 3:
printf("请输入要写入的数字：");
LTDataType a;
scanf("%d", &a);
ListPushFront(head, a);
break;
case 4:
ListPopFront(head);
break;
case 5:
printf("会将数据插入进输入数字之前的位置\n");
printf("请输入要插入位置的数字及要插入的数字：");
LTDataType b,j;
scanf("%d %d", &b,&j);
ListNode* ret1 = ListFind(head, b);
if (ret1 != NULL)
{
ListInsert(ret1, j);
}
else
{
printf("该数字不存在");
}
break;
case 6:
printf("请输入要删除的数字:");
LTDataType c;
scanf("%d", &c);
ListNode* ret2 = ListFind(head, c);
if (ret2 != NULL)
{
ListErase(ret2);
}
else
{
printf("未找到该数字");
}
break;
case 7:
ListPrint(head);
break;
case 0:
printf("退出");
ListDestory(head);
break;
default:
printf("输入错误，请重新输入");
break;
}
} while (input);
return 0;
}
总结
以上就是今天文章的内容，希望铁子们可以有所收货。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
文章标题：C语言数据结构——链表-创新互联
文章出自：
http://cdkjz.cn/article/dhpgcg.html
