深圳网站开发语言,插画师个人网站是怎么做的,汶上网站建设公司,中国建设银行甘肃省分行网站#xff08;图像由AI生成#xff09;
0.前言
在计算机科学中#xff0c;数据结构是存储和组织数据的一种方式#xff0c;它不仅影响数据的存储#xff0c;也影响数据的检索和更新效率。C语言#xff0c;作为一种经典的编程语言#xff0c;提供了灵活的方式来处理数据…
图像由AI生成
0.前言
在计算机科学中数据结构是存储和组织数据的一种方式它不仅影响数据的存储也影响数据的检索和更新效率。C语言作为一种经典的编程语言提供了灵活的方式来处理数据结构其中链表是最基本且重要的一种。
1.链表的概念及结构
1.1概念
链表Linked List是一种在物理上非连续、非顺序的数据结构由一系列节点Node组成。链表的每个节点由两部分构成一是存储数据元素的数据域二是存储下一个节点地址的指针域。这种结构允许在不重新整理整个数据结构的情况下有效地插入和删除节点。
1.2结构特点
动态存储管理链表的大小不是在编译时确定的而是在运行时通过申请内存来构建的这意味着它可以根据需要动态地扩展或缩减。节点构成链表的每个节点通常是一个对象或结构体包含至少两个元素 数据域存储数据值。指针域指向列表中下一个节点的指针。头指针链表通过一个外部引用通常是一个指针来访问这个引用指向链表的第一个节点称为头指针。如果链表为空头指针指向NULL。尾节点链表的最后一个节点指向NULL这标志着链表的结束。
1.3链表与数组的比较
存储分配数组在内存中占用连续空间而链表由一系列非连续的节点组成。大小灵活性数组的大小在定义时固定而链表的大小可以动态变化。内存利用链表可以更有效地管理内存因为它只需要根据实际需要分配内存。插入和删除效率在链表中插入或删除节点通常更快因为不需要移动其他元素除非是数组实现的链表。
2.链表的分类
按照单双向性、是否循环、以及是否带头节点链表可以被分为以下八种主要类型 单向不循环不带头链表 特点最基本的链表形式每个节点只有一个指向下一个节点的指针尾节点指向NULL不含额外的头节点。用途简单的数据存储和遍历操作。 单向不循环带头链表 特点类似于基本的单向链表但增加了一个不存储实际数据的头节点头节点的指针指向第一个实际数据节点。用途简化某些链表操作特别是插入和删除操作。 单向循环不带头链表 特点单向链表的尾节点指向链表的第一个节点形成一个闭环。用途适用于需要循环访问数据的场景。 单向循环带头链表 特点单向循环链表但有一个额外的头节点头节点的指针指向第一个实际数据节点。用途循环链表操作的简化尤其在处理循环链表的起始和终止条件时。 双向不循环不带头链表 特点每个节点有两个指针分别指向前一个和后一个节点尾节点的后向指针指向NULL没有头节点。用途方便的双向遍历易于节点的前后插入和删除。 双向不循环带头链表 特点双向链表加上一个头节点头节点的前向指针通常指向NULL后向指针指向第一个实际节点。用途简化插入、删除操作尤其是在链表头部的操作。 双向循环不带头链表 特点双向链表中的尾节点指向第一个节点第一个节点的前向指针指向尾节点形成一个双向闭环不含头节点。用途复杂的双向循环遍历常用于需要频繁正反向操作的场景。 双向循环带头链表 特点在双向循环链表的基础上增加了头节点头节点的前向指针指向尾节点后向指针指向第一个实际节点。用途在需要循环遍历的同时简化链表头部和尾部的操作。 在深入探讨链表的不同分类后我们将先集中讨论单链表的实现与操作。单链表作为链表家族中最简单的成员提供了对链表基本概念的清晰理解。我们将详细介绍单链表单向不带头不循环链表的实现方法和各种操作函数。
3.单链表单向不带头不循环链表
单链表是一种基础的数据结构由一系列节点Node组成。每个节点包含一个数据域和一个指向下一个节点的指针域。
3.1单链表的实现
我们先来看一下单向不带头不循环链表的具体实现包括3个文件头文件SList.h、源文件SList.c和test.c.
//SList.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.htypedef int SLTDataType;
typedef struct SListNode {SLTDataType data;struct SListNode* next;
}SLTNode;//打印
void SLTPrint(SLTNode* phead);
//获取新节点
SLTNode* BuyNewNode(SLTDataType x);
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在pos位置之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos位置之后的节点
void SLTEraseAfter(SLTNode* pos);
//删除pos位置的节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在pos位置之前插入x
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//销毁
void SLTDestroy(SLTNode** pphead);//SList.c
#define _CRT_SECURE_NO_WARNINGS 1#includeSList.h//打印
void SLTPrint(SLTNode* phead)
{//assert(phead);SLTNode* pcur phead;while (pcur){printf(%d-, pcur-data);pcur pcur-next;}printf(NULL\n);
}
//获取新节点
SLTNode* BuyNewNode(SLTDataType x)
{SLTNode* pnewnode (SLTNode*)malloc(sizeof(SLTNode));if (pnewnode NULL){assert(0);return NULL;}pnewnode-data x;pnewnode-next NULL;return pnewnode;}
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* pnewnode BuyNewNode(x);if (*pphead NULL){*pphead pnewnode;}else{SLTNode* pcur *pphead;while (pcur-next ! NULL){pcur pcur-next;}pcur-next pnewnode;}
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* pnewnode BuyNewNode(x);if (*pphead NULL){*pphead pnewnode;}else{pnewnode-next *pphead;*pphead pnewnode;}
}
//尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead);SLTNode* pcur *pphead;//链表为空if (*pphead NULL){return;}//链表只有一个节点else if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}//链表有多个节点else{while (pcur-next-next ! NULL){pcur pcur-next;}free(pcur-next);pcur-next NULL;}
}
//头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead);SLTNode* pcur *pphead;if (pcur NULL){return;}else{*pphead pcur-next;free(pcur);}
}
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* pcur phead;while (pcur){if (pcur-data x){return pcur;}pcur pcur-next;}//没找到return NULL;
}
//在pos位置之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* pnewnode BuyNewNode(x);pnewnode-next pos-next;pos-next pnewnode;}
//删除pos位置之后的节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos);SLTNode* pcur pos-next;//pos之后没有节点if (pcur NULL){return;}//pos之后有节点else{pos-next pcur-next;free(pcur);}
}
//删除pos位置的节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);if(pos*pphead){SLTPopFront(pphead);}else{SLTNode* pcur *pphead;while (pcur-next ! pos){pcur pcur-next;}pcur-next pos-next;free(pos);}
}
//在pos位置之前插入x
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);assert(*pphead);//链表不为空SLTNode* pnewnode BuyNewNode(x);//pos为头节点if (*pphead pos){/* pnewnode-next *pphead;*pphead pnewnode;*/SLTPushFront(pphead, x);}//pos不为头结点else{SLTNode* pcur *pphead;while (pcur-next ! pos){pcur pcur-next;}pnewnode-next pos;pcur-next pnewnode;}
}
//销毁
void SLTDestroy(SLTNode** pphead)
{assert(pphead);SLTNode* pcur *pphead;while (pcur){*pphead pcur-next;free(pcur);pcur *pphead;}
}//test.c
#define _CRT_SECURE_NO_WARNINGS 1#includeSList.hvoid SListTest01()
{printf(SListTest01()\n);SLTNode* node1 BuyNewNode(1);SLTPushBack(node1, 2);SLTPushBack(node1, 3);SLTPushBack(node1, 4);SLTPushBack(node1, 5);SLTPrint(node1);SLTPushFront(node1, 0);SLTPrint(node1);SLTNode* ToFind SLTFind(node1, 0);if(ToFind){printf(Find it!\n);}else{printf(Not Find!\n);}SLTInsertAfter(ToFind, 500);SLTPrint(node1);SLTInsertBefore(node1, ToFind, 100);SLTPrint(node1);SLTErase(node1, ToFind);SLTPrint(node1);
}
void SListTest02()
{printf(SListTest02()\n);SLTNode* node1 BuyNewNode(1);SLTPushBack(node1, 2);SLTPushBack(node1, 3);SLTPushBack(node1, 4);SLTPushBack(node1, 5);SLTPrint(node1);SLTPopBack(node1);SLTPrint(node1);SLTPopFront(node1);SLTPrint(node1);SLTNode* ToFind SLTFind(node1, 3);SLTEraseAfter(ToFind);SLTPrint(node1);SLTDestroy(node1);SLTPrint(node1);}
int main()
{SListTest01();SListTest02();return 0;
}
3.2单链表函数详解
在单链表的实现中以下是关键的数据类型定义和各个函数的实现原理与作用
3.2.1数据类型定义 typedef int SLTDataType; 定义 SLTDataType 作为链表节点存储的数据类型这里设为整型int。 typedef struct SListNode { SLTDataType data; struct SListNode* next; } SLTNode; 定义单链表的节点结构 SLTNode包含数据data和指向下一个节点的指针next。
3.3.2函数详解 打印链表SLTPrint 参数头节点指针 phead。功能遍历链表打印每个节点的数据值。实现使用循环遍历链表直到遇到 NULL 结束。 获取新节点BuyNewNode 参数节点数据 x。功能创建并返回一个新的链表节点。实现分配内存初始化数据和指针。 尾插SLTPushBack 参数头节点指针的指针 pphead节点数据 x。功能在链表尾部插入一个新节点。实现找到链表的最后一个节点将其 next 指向新节点。 头插SLTPushFront 参数头节点指针的指针 pphead节点数据 x。功能在链表头部插入一个新节点。实现新节点的 next 指向原头节点然后更新头节点。 尾删SLTPopBack 参数头节点指针的指针 pphead。功能删除链表的最后一个节点。实现找到倒数第二个节点将其 next 设置为 NULL。 头删SLTPopFront 参数头节点指针的指针 pphead。功能删除链表的第一个节点。实现将头节点指针更新为第二个节点。 查找SLTFind 参数头节点指针 phead要查找的数据 x。功能查找链表中数据为 x 的节点。实现遍历链表比较节点数据。 指定位置后插入SLTInsertAfter 参数目标节点指针 pos节点数据 x。功能在指定节点之后插入新节点。实现新节点的 next 指向 pos 的 next然后 pos 的 next 指向新节点。 指定位置后删除SLTEraseAfter 参数目标节点指针 pos。功能删除指定节点之后的节点。实现将 pos 的 next 指向要删除节点的 next。 指定位置删除SLTErase 参数头节点指针的指针 pphead要删除的节点指针 pos。功能删除指定的节点。实现找到 pos 的前一个节点更新其 next 指针。 指定位置前插入SLTInsertBefore 参数头节点指针的指针 pphead目标节点指针 pos节点数据 x。功能在指定节点之前插入新节点。实现遍历链表找到 pos 的前一个节点执行插入操作。 销毁链表SLTDestroy 参数头节点指针的指针 pphead。功能销毁整个链表释放所有节点。实现遍历链表释放每个节点的内存。
3.2.3test.c运行结果 继单链表之后我们将转向更为复杂的双向链表。双向链表双向带头循环链表不仅在节点结构上比单链表复杂其操作也更为多样。通过比较这两种链表类型我们可以更好地理解链表作为一种数据结构的灵活性和多功能性。
4.双向链表双向带头循环链表
双向链表是一种常见的线性数据结构与单链表不同它每个节点有两个指针域一个指向前一个节点一个指向后一个节点因此可以从前往后或从后往前遍历链表。本文将详细介绍双向带头循环链表的实现以及双向链表的各种常用操作函数。
4.1双向链表的实现
我们先来看一下双向带头循环链表的具体实现包括3个文件头文件List.h、源文件List.c和test.c.
//List.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.htypedef int LTDataType;
typedef struct ListNode {LTDataType data;struct ListNode* prev;struct ListNode* next;
}LTNode;void LTPrint(LTNode* phead);//打印
void LTInit(LTNode** pphead);//初始化通过传参
LTNode* LTInit2();//初始化通过返回值
void LTDestroy(LTNode** pphead);//销毁
LTNode* BuyLTNode(LTDataType x);//创建新节点
void LTPushBack(LTNode* phead, LTDataType x);//尾插
void LTPopBack(LTNode* phead);//尾删
void LTPushFront(LTNode* phead, LTDataType x);//头插
void LTPopFront(LTNode* phead);//头删
LTNode* LTFind(LTNode* phead, LTDataType x);//查找
void LTInsertBefore(LTNode* pos, LTDataType x);//在pos位置之前插入x
void LTInsertAfter(LTNode* pos, LTDataType x);//在pos位置之后插入x
void LTRemove(LTNode* pos);//删除pos位置的节点
void LTCheckNode(LTNode* phead);//打印有效节点个数//List.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeList.h//打印
void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur phead-next;printf(head-);while(cur ! phead){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}
//初始化通过传参的方式
void LTInit(LTNode** pphead)
{*pphead (LTNode*)malloc(sizeof(LTNode));if(*pphead NULL){assert(0);return;}(*pphead)-data -1;(*pphead)-next *pphead;(*pphead)-prev *pphead;
}
//初始化通过返回值的方式
LTNode* LTInit2()
{LTNode* phead (LTNode*)malloc(sizeof(LTNode));if(phead NULL){assert(0);return NULL;}phead-data -1;phead-next phead;phead-prev phead;return phead;
}
//销毁
void LTDestroy(LTNode** pphead)
{LTNode* cur (*pphead)-next;while(cur ! *pphead){LTNode* next cur-next;free(cur);cur next;}free(*pphead);*pphead NULL;
}
//创建新节点
LTNode* BuyLTNode(LTDataType x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));if(newnode NULL){assert(0);return NULL;}newnode-data x;newnode-next NULL;newnode-prev NULL;return newnode;
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* ptail phead-prev;LTNode* newnode BuyLTNode(x);newnode-next phead;newnode-prev ptail;ptail-next newnode;phead-prev newnode;
}
//尾删
void LTPopBack(LTNode* phead)
{assert(phead);LTNode* ptail phead-prev;if(ptail phead){return;}LTNode* prev ptail-prev;prev-next phead;phead-prev prev;free(ptail);
}
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode BuyLTNode(x);LTNode* next phead-next;newnode-next next;newnode-prev phead;next-prev newnode;phead-next newnode;}
//头删
void LTPopFront(LTNode* phead)
{assert(phead);LTNode* next phead-next;if(next phead){return;}LTNode* nextnext next-next;phead-next nextnext;nextnext-prev phead;free(next);}
//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur phead-next;while(cur ! phead){if(cur-data x){return cur;}cur cur-next;}return NULL;}
//在pos位置之前插入x
void LTInsertBefore(LTNode* pos, LTDataType x)
{assert(pos);LTNode* prev pos-prev;LTNode* newnode BuyLTNode(x);newnode-next pos;newnode-prev prev;prev-next newnode;pos-prev newnode;
}
//在pos位置之后插入x
void LTInsertAfter(LTNode* pos, LTDataType x)
{assert(pos);LTNode* next pos-next;LTNode* newnode BuyLTNode(x);newnode-next next;newnode-prev pos;next-prev newnode;pos-next newnode;
}
//删除pos位置的节点
void LTRemove(LTNode* pos)
{assert(pos);LTNode* prev pos-prev;LTNode* next pos-next;prev-next next;next-prev prev;free(pos);
}
//打印有效节点个数
void LTCheckNode(LTNode* phead)
{assert(phead);LTNode* cur phead-next;int count 0;while(cur ! phead){count;cur cur-next;}printf(有效节点个数为%d\n, count);
}//test.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeList.h
void test01()
{printf(test01()\n);LTNode* plist NULL;LTInit(plist);LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTPopBack(plist);LTPrint(plist);
}
void test02()
{printf(test02()\n);LTNode* plist LTInit2();LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTNode* toFind LTFind(plist, 2);if (toFind){printf(找到了\n);}else{printf(没找到\n);}LTInsertAfter(toFind, 5);LTInsertBefore(toFind, 6);LTPrint(plist);LTRemove(toFind);LTPrint(plist);LTCheckNode(plist);
}
int main()
{test01();test02();return 0;
}
4.2双向链表函数详解
4.2.1数据类型定义
在双向链表的实现中我们使用了以下数据类型的定义
typedef int LTDataType;
typedef struct ListNode {LTDataType data;struct ListNode* prev;struct ListNode* next;
} LTNode;LTDataType链表节点存储的数据类型这里使用整数作为示例。LTNode链表节点的结构体包含数据域 data前驱指针 prev 和后继指针 next。这三个部分组成了链表节点的基本结构。
4.2.2 函数详解
以下是双向链表实现中的各个函数的详细介绍
1. 初始化链表
void LTInit(LTNode** pphead);参数头节点指针的指针 pphead。功能初始化链表创建一个头节点使其 next 和 prev 指向自身形成循环链表。这个函数用于链表的初始化操作。
2. 创建新节点
LTNode* BuyLTNode(LTDataType x);参数节点存储的数据 x。返回值新节点的指针。功能创建一个新节点为其分配内存并设置数据域为 x前驱和后继指针为空。这个函数用于创建待插入的新节点。
3. 插入节点到尾部
void LTPushBack(LTNode* phead, LTDataType x);
参数头节点指针 phead要插入的数据 x。功能在双向链表的尾部插入一个新节点更新尾节点的指针。这个函数用于在链表尾部添加新元素。
4. 删除尾部节点
void LTPopBack(LTNode* phead);
参数头节点指针 phead。功能删除双向链表的尾部节点更新尾节点的指针并释放内存。这个函数用于删除链表尾部的元素。
5. 插入节点到头部
void LTPushFront(LTNode* phead, LTDataType x);
参数头节点指针 phead要插入的数据 x。功能在双向链表的头部插入一个新节点更新头节点的指针。这个函数用于在链表头部添加新元素。
6. 删除头部节点
void LTPopFront(LTNode* phead);
参数头节点指针 phead。功能删除双向链表的头部节点更新头节点的指针并释放内存。这个函数用于删除链表头部的元素。
7. 查找节点
LTNode* LTFind(LTNode* phead, LTDataType x);
参数头节点指针 phead要查找的数据 x。返回值找到的节点的指针如果未找到则返回 NULL。功能在双向链表中查找存储特定数据 x 的节点。这个函数用于查找链表中的元素。
8. 在指定节点之前插入新节点
void LTInsertBefore(LTNode* pos, LTDataType x);
参数要插入的位置节点 pos要插入的数据 x。功能在双向链表中的指定节点 pos 之前插入一个新节点更新前驱和后继节点的指针。这个函数用于在指定位置之前
9. 在指定节点之后插入新节点
void LTInsertAfter(LTNode* pos, LTDataType x);
参数要插入的位置节点 pos要插入的数据 x。功能在双向链表中的指定节点 pos 之后插入一个新节点更新前驱和后继节点的指针。这个函数用于在指定位置之后插入新元素。
10. 删除指定节点
void LTRemove(LTNode* pos);
参数要删除的节点 pos。功能从双向链表中删除指定节点 pos更新前驱和后继节点的指针并释放内存。这个函数用于删除链表中的特定元素。
4.2.3test.c运行结果 5.结语
在本篇博客中我们详细介绍了C语言中的链表数据结构包括单向链表和双向链表。我们从链表的基本概念和结构开始然后分别讨论了不同类型的链表包括单向不带头不循环链表和双向带头循环链表。通过学习链表的实现和操作我们可以更好地理解数据结构和算法的基本原理为编程和问题解决提供强大的工具。希望本篇博客能够帮助你更深入地理解链表并在编程中应用它们。
