关于幼儿建设网站ppt,网站流量优化,wordpress控制,国内优秀wordpress主题各位读者老爷好#xff0c;鼠鼠我又来了哈。鼠鼠我呀现在来基于C语言实现以下单链表#xff0c;希望对你有所帮助#xff01; 目录
1.链表的概念及结构
2.链表的分类
3.无头单向非循环链表的实现
3.1.单链表打印
3.2.单链表尾插
3.3.单链表头插
3.4.单链表尾删
3.5…各位读者老爷好鼠鼠我又来了哈。鼠鼠我呀现在来基于C语言实现以下单链表希望对你有所帮助 目录
1.链表的概念及结构
2.链表的分类
3.无头单向非循环链表的实现
3.1.单链表打印
3.2.单链表尾插
3.3.单链表头插
3.4.单链表尾删
3.5.单链表头删
3.6.单链表查找
3.7.单链表在pos位置之和插入值
3.8.单链表删除pos位置之后的值
3.9.在pos的前面插入值
3.10.删除pos位置的值
3.11.销毁单链表
4.单链表的小应用
4.1.slist.h
4.2.slist.c
4.3.test.c
5.ending
鼠鼠我上次浅谈了顺序表。但是吧Any coin has two sides。
顺序表有一些缺陷 1.尾部插入效率还不错。头部或者中间插入删除需要挪动数据效率低下。 2.顺序表满了以后只能扩容。扩容是有一定消耗的扩容一般是存在一定的空间浪费一次扩得越多可能浪费越多一次扩得少可能需要频繁扩容。 当然顺序表也有它的优势 得益于它的物理空间连续顺序表支持随机的下标访问。 So我们有链表可以避免顺序表的缺陷那我们先来看看链表哈
1.链表的概念及结构
概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表 中的指针链接次序实现的 。
不带头非循环单向链表的逻辑结构如下图 链表是由节点或者结点构成的。这些个节点一般是动态内存申请得来的所以每个节点的地址没有关联是随机的也就是说链表的物理结构不连续。既然每个节点的地址是随机的那我们如何管理链表呢 其实也很简单如上逻辑结构可知只要节点有俩个数据域即可一个数据域存放所需存入的值另一个数据域存放下一个节点的地址最后一个节点保存空指针。这样我们就可以通过第一个节点找到第二个节点、第二个节点找到第三个节点……这样就可以管理链表了。 了解了链表的特点那我们对于数据的增删改等操作更改节点内存储的地址即可不必挪动数据。而且节点是一个个动态申请得到的想要多少就申请多少自然就避免了扩容有浪费的情况。这样子就很好避免的顺序表的缺陷 画图方便理解 2.链表的分类
实际中链表的结构非常多样以下情况组合起来就有8种链表结构
1.单向或者双向 2.带头或者不带头 3.循环或者非循环 虽然有这么多的链表的结构但是我们实际中最常用还是两种结构 1. 无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。 2. 带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带来很多优势实现反而简单了。 咱们这篇博客实现的是无头单向非循环链表。
3.无头单向非循环链表的实现
具体我们实现这些无头单向非循环链表以下简称单链表的增删查改等等功能
typedef int SLTDateType;typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SListNode;// 单链表打印
void SListPrint (SListNode * plist);// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);// 单链表的尾删
void SListPopBack(SListNode** pplist);// 单链表头删
void SListPopFront(SListNode** pplist);// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);// 单链表在pos位置之后插入值
void SListInsertAfter(SListNode* pos, SLTDateType x);// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);// 在pos的前面插入值
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x);// 删除pos位置的值
void SLTErase(SListNode** pphead, SListNode* pos);//销毁单链表
void SLTDestroy(SListNode** pphead);
好了好了一个个来实现吧
3.1.单链表打印
//单链表打印
void SListPrint(SListNode* plist)
{SListNode* cur plist;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}
这个打印的实现还是很简单的我们只要遍历单链表在将每个节点的数据打印出来即可。
3.2.单链表尾插
//动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{SListNode* newnode (SListNode*)malloc(sizeof(SListNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-data x;newnode-next NULL;return newnode;
}
//单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{assert(pplist);if (*pplist NULL)//单链表为空{*pplist BuySListNode(x);}else//单链表不为空{SListNode* tail *pplist;while (tail-next ! NULL)//找尾{tail tail-next;}SListNode* newnode BuySListNode(x);tail-next newnode;}
}
这个尾插的实现来说正常情况下先找到单链表的最后一个节点找尾在让最后一个节点存储新申请节点的地址即可所以要调用动态申请一个节点的函数BuySListNode这个函数已经让新申请的节点存储空指针和需要保存的数据了。 但是要区别单链表是否为空如果不加以区分单链表是否为空的话就会访问空指针如果为空的话直接让*pplist保存新申请的节点地址即可。
3.3.单链表头插
//动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{SListNode* newnode (SListNode*)malloc(sizeof(SListNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-data x;newnode-next NULL;return newnode;
}
//单链表头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{assert(pplist);SListNode* newnode BuySListNode(x);newnode-next *pplist;*pplist newnode;
}
对于头插的实现只要让新申请的节点 存储原来*pplist的地址让*pplist保存新申请的节点的地址即可。
3.4.单链表尾删
//单链表尾删
void SListPopBack(SListNode** pplist)
{assert(pplist);assert(*pplist);SListNode* tail *pplist;SListNode* fronttail *pplist;while (tail-next ! NULL)//找尾节点和尾节点前一个节点{fronttail tail;tail tail-next;}if (fronttail-next NULL)//一个节点{*pplist NULL;free(tail);tail NULL;fronttail NULL;}else//多个节点{free(tail);tail NULL;fronttail-next NULL;}
}
对于尾删我们要区分单链表为空、单链表有一个节点和单链表有多个节点的情况。如果单链表为空就不能删除断言即可。单链表一个节点的话让*pplist保存空指针free掉尾节点也是头节点。 单链表有多个节点的话free掉尾节点让尾节点前一个节点保存空指针即可。如果不区分一个节点和多个节点的情况一律按多个节点情况来处理的话当只有一个节点时fronttail会成为野指针。。
3.5.单链表头删
//单链表头删
void SListPopFront(SListNode** pplist)
{assert(pplist);assert(*pplist);SListNode* next (*pplist)-next;free(*pplist);*pplist next;
}
这个简单只要free掉头节点free掉之前需要保存头节点下一个节点地址不然的话就找不到头节点下一个节点了*pplist保存头节点下一个节点地址即可。
3.6.单链表查找
//单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{SListNode* cur plist;while (cur ! NULL){if (cur-data x){return cur;}cur cur-next;}return NULL;
}
这个实现的话只要遍历单链表找到单链表节点中第一个出现的与x相等的val 再返回该节点的地址即可找不到就返回空指针。
3.7.单链表在pos位置之和插入值
//动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{SListNode* newnode (SListNode*)malloc(sizeof(SListNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-data x;newnode-next NULL;return newnode;
}
// 单链表在pos位置之后插入值
void SListInsertAfter(SListNode* pos, SLTDateType x)
{assert(pos);SListNode* newnode BuySListNode(x);SListNode* next pos-next;pos-next newnode;newnode-next next;
}
实现这个功能的话我们需要知道pos的值这个值是某个节点的地址可以通过单链表查找获得然后的话让pos指向的节点存储新申请节点的地址新申请的节点存储pos指向的节点的下一个节点的地址即可这个地址记得提前用变量存储下来如果在改变pos指向的节点存储的地址之前没有存储下来的话就找不到pos指向节点的下一个节点了。
3.8.单链表删除pos位置之后的值
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{assert(pos);assert(pos-next);//防止删pos指向尾节点 SListNode* next pos-next-next;free(pos-next);pos-next next;
}
这里需要注意防止单链表为空和防止pos指向尾节点尾节点后面为空不可删断言即可。这个实现大致就是让pos指向的节点存储pos指向节点的后两个节点的地址free掉pos指向节点后一个节点即可。
3.9.在pos的前面插入值
//动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{SListNode* newnode (SListNode*)malloc(sizeof(SListNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-data x;newnode-next NULL;return newnode;
}
// 在pos的前面插入值
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
{assert(pphead);assert((!*pphead !pos) || (*pphead pos));if (*pphead pos){SListPushBack(pphead, x);}else{SListNode* frontpos *pphead;while (frontpos-next ! pos)//找pos前一个节点{frontpos frontpos-next;}SListNode* newnode BuySListNode(x);SListNode* next frontpos-next;frontpos-next newnode;newnode-next next;}
}
如果单链表为空直接调用单链表尾插单链表头插也行即可。不为空就找到pos指向节点的前一个节点让pos指向节点的前一个节点存储新申请节点地址让新申请节点存储pos指向节点的地址即可。
3.10.删除pos位置的值
// 删除pos位置的值
void SLTErase(SListNode** pphead, SListNode* pos)
{assert(pphead);assert(*pphead);//没有节点assert(pos);if ((*pphead)-next NULL)//一个节点{SListPopFront(pphead);}else{SListNode* frontpos *pphead;while (frontpos-next ! pos)//找pos前一个节点{frontpos frontpos-next;}SListNode* next pos-next;free(pos);frontpos-next next;}
}
注意断言防止单链表为空为空不能删除。如果单链表有一个节点直接调用单链表头删单链表尾删也行即可。如果有单链表有多个节点大致的话让pos指向的节点前一个节点存储pos指向节点后一个节点地址free掉pos指向节点即可。
3.11.销毁单链表
//销毁单链表
void SLTDestroy(SListNode** pphead)
{assert(pphead);SListNode* cur *pphead;while (cur){SListNode* next cur-next;free(cur);cur next;}*pphead NULL;
}
如果不再使用单链表的话可以销毁单链表。虽然单链表是动态申请的不手动销毁的话结束程序也会自动销毁 但手动销毁是一个好习惯。这个实现也简单遍历单链表一一销毁节点即可。
4.单链表的小应用
对于上面的单链表增删查改等等实现来说鼠鼠我讲解的只是大概思想我们只要懂得这些思想再注意一些细节就可完成上面代码的实现。单链表的实现不是唯一的上面代码只是一种参考最重要要懂得单链表的含义和增删查改等等思想。
鼠鼠我还是一样写了一个工程来验证单链表增删查改等等功能的实现有兴趣的读者老爷可以将一下三个文件上面的实现代码都在slist.c里面了放到一个工程玩玩
4.1.slist.h
#pragma once
#includestdio.h
#includeassert.h
#includestdlib.htypedef int SLTDateType;typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SListNode;// 单链表打印
void SListPrint (SListNode * plist);// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);// 单链表的尾删
void SListPopBack(SListNode** pplist);// 单链表头删
void SListPopFront(SListNode** pplist);// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);// 单链表在pos位置之后插入值
void SListInsertAfter(SListNode* pos, SLTDateType x);// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);// 在pos的前面插入值
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x);// 删除pos位置的值
void SLTErase(SListNode** pphead, SListNode* pos);//销毁单链表
void SLTDestroy(SListNode** pphead);
4.2.slist.c
#define _CRT_SECURE_NO_WARNINGS
#includeslist.h//动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{SListNode* newnode (SListNode*)malloc(sizeof(SListNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-data x;newnode-next NULL;return newnode;
}//单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{assert(pplist);if (*pplist NULL)//单链表为空{*pplist BuySListNode(x);}else//单链表不为空{SListNode* tail *pplist;while (tail-next ! NULL)//找尾{tail tail-next;}SListNode* newnode BuySListNode(x);tail-next newnode;}
}//单链表打印
void SListPrint(SListNode* plist)
{SListNode* cur plist;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}//单链表头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{assert(pplist);SListNode* newnode BuySListNode(x);newnode-next *pplist;*pplist newnode;
}//单链表尾删
void SListPopBack(SListNode** pplist)
{assert(pplist);assert(*pplist);SListNode* tail *pplist;SListNode* fronttail *pplist;while (tail-next ! NULL)//找尾节点和尾节点前一个节点{fronttail tail;tail tail-next;}if (fronttail-next NULL)//一个节点{*pplist NULL;free(tail);tail NULL;fronttail NULL;}else//多个节点{free(tail);tail NULL;fronttail-next NULL;}
}//单链表头删
void SListPopFront(SListNode** pplist)
{assert(pplist);assert(*pplist);SListNode* next (*pplist)-next;free(*pplist);*pplist next;
}//单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{SListNode* cur plist;while (cur ! NULL){if (cur-data x){return cur;}cur cur-next;}return NULL;
}// 单链表在pos位置之后插入值
void SListInsertAfter(SListNode* pos, SLTDateType x)
{assert(pos);SListNode* newnode BuySListNode(x);SListNode* next pos-next;pos-next newnode;newnode-next next;
}// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{assert(pos);assert(pos-next);//防止删pos指向尾节点 SListNode* next pos-next-next;free(pos-next);pos-next next;
}// 在pos的前面插入值
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
{assert(pphead);assert((!*pphead !pos) || (*pphead pos));if (*pphead pos){SListPushBack(pphead, x);}else{SListNode* frontpos *pphead;while (frontpos-next ! pos)//找pos前一个节点{frontpos frontpos-next;}SListNode* newnode BuySListNode(x);SListNode* next frontpos-next;frontpos-next newnode;newnode-next next;}
}// 删除pos位置的值
void SLTErase(SListNode** pphead, SListNode* pos)
{assert(pphead);assert(*pphead);//没有节点assert(pos);if ((*pphead)-next NULL)//一个节点{SListPopFront(pphead);}else{SListNode* frontpos *pphead;while (frontpos-next ! pos)//找pos前一个节点{frontpos frontpos-next;}SListNode* next pos-next;free(pos);frontpos-next next;}
}//销毁单链表
void SLTDestroy(SListNode** pphead)
{assert(pphead);SListNode* cur *pphead;while (cur){SListNode* next cur-next;free(cur);cur next;}*pphead NULL;
}
4.3.test.c
#define _CRT_SECURE_NO_WARNINGS
#includeslist.h
void menu()
{printf(**********************\n);printf(********0.退出********\n);printf(****1.头插 2.头删****\n);printf(****3.尾插 4.尾删****\n);printf(****5.查找 6.打印****\n);printf(*7.在pos位置之后插入值\n);printf(*8.删除pos位置之后的值\n);printf(*9.在pos的前面插入值**\n);printf(*10.删除pos位置的值***\n);printf(**********************\n);
}
int main()
{SListNode* pplist NULL;int input;do{menu();printf(请输入你想操作的数字-);scanf(%d, input);if (input 0){SLTDestroy(pplist);printf(\n);break;}else if (input 1){int number 0;printf(请输入你要头插数据的个数-);scanf(%d, number);printf(请输入你要头插的数据-);while (number--){SLTDateType x 0;scanf(%d, x);SListPushFront(pplist, x);}printf(\n);}else if (input 2){SListPopFront(pplist);printf(\n);}else if (input 3){int number 0;printf(请输入你要尾插数据的个数-);scanf(%d, number);printf(请输入你要尾插的数据-);int i 0;for (i 0; i number; i){SLTDateType x 0;scanf(%d, x);SListPushBack(pplist, x);}printf(\n);}else if (input 4){SListPopBack(pplist);printf(\n);}else if (input 5){SLTDateType x 0;printf(请输入你要查找的值-);scanf(%d, x);SListNode* p SListFind(pplist, x);if (p ! NULL){printf(你要查找的值地址是%p\n, p);}else{printf(找不到\n);}printf(\n);}else if (input 6){SListPrint(pplist);printf(\n);}else if (input 7){SLTDateType x 0,pos 0;printf(请分别输入你要插入的值及pos指向的值-);scanf(%d %d, x, pos);SListInsertAfter( SListFind(pplist,pos), x);printf(\n);}else if (input 8){SLTDateType pos 0;printf(请输入pos指向的值-);scanf(%d, pos);SListEraseAfter(SListFind(pplist, pos));printf(\n);}else if (input 9){SLTDateType x 0, pos 0;printf(请分别输入你要插入的值及pos指向的值-);scanf(%d %d, x, pos);SLTInsert(pplist, SListFind(pplist, pos), x);printf(\n);}else if (input 10){SLTDateType pos 0;printf(请输入pos指向的值-);scanf(%d, pos);SLTErase(pplist, SListFind(pplist, pos));printf(\n);}else{printf(输入错误请重新输入-);}} while (input);return 0;
}
5.ending
鼠鼠我呀不怎么会写博客读者老爷看到这里如果觉得不好就多多包涵看看图一乐也不是不行。当然如有不足恳请斧正哈
