网站经营性质,wordpress seo免费主题,网站建设优化服务渠道,网站整站下载器下载utf8网页乱码文章目录 1. 单链表1.1 概念、结构1.2 结点1.2.1 链表的性质 2. 链表的打印3. 尾插、头插创建结点尾插头插 4. 尾删、头删尾删头删 5. 查找指定结点6. 指定位置之前、之后插入数据指定位置之前插入数据指定位置之后插入数据 7. 删除指定位置结点7.1 删除指定位置之后结点8. 链表… 文章目录 1. 单链表1.1 概念、结构1.2 结点1.2.1 链表的性质 2. 链表的打印3. 尾插、头插创建结点尾插头插 4. 尾删、头删尾删头删 5. 查找指定结点6. 指定位置之前、之后插入数据指定位置之前插入数据指定位置之后插入数据 7. 删除指定位置结点7.1 删除指定位置之后结点8. 链表的销毁9. 单链表代码实现 1. 单链表
1.1 概念、结构
链表也是线性表的一种。
概念链表是⼀种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。(即链表在物理结构上不一定连续在逻辑结构上一定连续)
1.2 结点
每节车厢都是独立申请下来的空间我们称之为“节点/结点”。
结点的组成主要有两个部分 1. 当前结点要保存的数据 2. 保存下⼀个结点的地址指针变量。
上图指针变量 plist保存的是第一个结点的地址我们称plist此时“指向”第一个结点如果我们希望plist“指向”第二个结点时只需要修改plist保存的内容为0x0012FFA0。 链表中每个结点都是独立申请的即需要插入数据时才去申请一块结点的空间我们需要通过指针变量来保存下⼀个结点位置才能从当前结点找到下一个结点。
对应实现结点的结构体代码
1.2.1 链表的性质
链式机构在逻辑上是连续的在物理结构上不一定连续结点⼀般是从堆上申请的从堆上申请来的空间是按照⼀定策略分配出来的每次申请的空间可能连续可能不连续
2. 链表的打印 结点创建 void SLTTest01()
{SLTNode* node1 (SLTNode*)malloc(sizeof(SLTNode));node1-data 1;SLTNode* node2 (SLTNode*)malloc(sizeof(SLTNode));node2-data 2;SLTNode* node3 (SLTNode*)malloc(sizeof(SLTNode));node3-data 3;SLTNode* node4 (SLTNode*)malloc(sizeof(SLTNode));node4-data 4;将4个节点连接起来node1-next node2;node2-next node3;node3-next node4;node4-next NULL;SLTPrint(plist);
} 显然我们每次都要一个接一个创建结点并让结点连接起来过于麻烦。因此我们可以考虑封装成一个函数这个函数用来创建结点。
3. 尾插、头插
创建结点
需要进行尾插头插的操作首先需要创建结点
尾插
在尾插的时候需要考虑以下几点
如果为空链表该如何处理如何让两个结点相连如何找到尾部结点 头插
相比于尾插头插不需要考虑链表是否为空的情况因为只要让新的结点头插到NULL即可
4. 尾删、头删
尾删
进行尾删操作需要考虑以下因素
链表是否为空空的话不能进行尾删遍历链表找到尾结点保存尾结点的前一个结点释放尾结点让前一个结点指向NULL
头删
头删需要考虑以下因素
链表是否为空保存第二个有效结点释放第一个有效结点让pphead指向第二个有效结点
5. 查找指定结点 6. 指定位置之前、之后插入数据
指定位置之前插入数据
链表是否为空指定位置值的结点是否存在如果指定位置的结点时头节点则头插即可遍历链表找到指定结点的前一个结点
指定位置之后插入数据 7. 删除指定位置结点
链表是否为空指定位置结点是否存在指定位置结点是否是头结点遍历链表找到pos结点的前一个结点释放pos结点
7.1 删除指定位置之后结点 8. 链表的销毁 9. 单链表代码实现 Slist.h #define _CRT_SECURE_NO_WARNINGS 1
#includestdlib.h
#includestdio.h
#includeassert.h
//针对顺序表:中间/头部插入效率低下、增容降低运行效率、增容造成空间浪费
//因此有了单链表
//链表也是线性表的一种
//链表是由一个一-个的节点组成
//组成:数据 指向下一个节点的指针typedef int DataType;//可能存储整形字符型等等typedef struct SlistNode
{DataType data;//节点数据struct SlistNode* next;//指向下一个节点的指针
}SLTNode;//链表的打印
void SLTPrint(SLTNode* phead);
//创建节点
SLTNode* SLTBuyNode(DataType x);
//尾插
void SLTPushBack(SLTNode** pphead, DataType x);
//头插
void SLTPushFront(SLTNode** pphead, DataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, DataType x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, DataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, DataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos后节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SLTDesTroy(SLTNode** pphead);Slist.c #define _CRT_SECURE_NO_WARNINGS 1#includeSlist.h//链表的打印
void SLTPrint(SLTNode* phead)
{SLTNode* pcur phead;while (pcur){printf(%d-, pcur-data);pcur pcur-next;}printf(NULL\n);
}
//创建节点
SLTNode* SLTBuyNode(DataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL){perror(malloc fail!);exit(1);}//创建成功newnode-data x;newnode-next NULL;return newnode;
}
//尾插
void SLTPushBack(SLTNode** pphead, DataType x)
{assert(pphead);//空链表和非空链表SLTNode* newnode SLTBuyNode(x);//如果是空链表if (*pphead NULL){*pphead newnode;}else {//找尾节点SLTNode* ptail *pphead;while (ptail-next){ptail ptail-next;}//ptail指向的就是尾节点ptail-next newnode;}
}
//头插
void SLTPushFront(SLTNode** pphead, DataType x)
{assert(pphead);SLTNode* newnode SLTBuyNode(x);newnode-next *pphead;*pphead newnode;
}
//尾删
void SLTPopBack(SLTNode** pphead)
{//链表不能为空assert(pphead *pphead);//链表只有一个节点if ((*pphead)-next NULL) //- 优先级高于*{free(*pphead);*pphead NULL;}else {//链表有多个节点SLTNode* prev *pphead;SLTNode* ptail *pphead;while (ptail-next){prev ptail;ptail ptail-next;}free(ptail);ptail NULL;prev-next NULL;}
}
//头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead *pphead);SLTNode* next (*pphead)-next;free(*pphead);*pphead next;
}
//查找
SLTNode* SLTFind(SLTNode* phead, DataType x)
{SLTNode* pcur phead;while (pcur){if (pcur-data x){return pcur;}pcur pcur-next;}//pcur NULLreturn NULL;
}
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, DataType x)
{assert(pphead *pphead);assert(pos);SLTNode* newnode SLTBuyNode(x);//若pos *pphead 说明是头插if (pos *pphead){SLTPushFront(pphead, x);}else {SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}newnode-next pos;prev-next newnode;}
}
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, DataType x)
{assert(pos);SLTNode* newnode SLTBuyNode(x);//先连接后面在前面newnode-next pos-next;pos-next newnode;
}
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead *pphead);assert(pos);//pos是头节点if (pos *pphead){SLTNode* next (*pphead)-next;free(*pphead);*pphead next;}else{//pos不是头节点SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;}
}
//删除pos后节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos pos-next);SLTNode* del pos-next;pos-next del-next;free(del);del NULL;
}
//销毁链表
void SLTDesTroy(SLTNode** pphead)
{assert(pphead *pphead);SLTNode* pcur *pphead;while (pcur){SLTNode* next pcur-next;free(pcur);pcur next;}//pcur为NULL*pphead NULL;
}test.c #define _CRT_SECURE_NO_WARNINGS 1
#includeSlist.h//链表是由一个一个的节点组成
//创建几个节点//第一个节点 *plist --- **pphead
//指向第一个节点的指针 plist --- *pphead
//指向第一个节点的指针的地址 plist --- pphead
void SLTTest01()
{//SLTNode* node1 (SLTNode*)malloc(sizeof(SLTNode));//node1-data 1;//SLTNode* node2 (SLTNode*)malloc(sizeof(SLTNode));//node2-data 2;//SLTNode* node3 (SLTNode*)malloc(sizeof(SLTNode));//node3-data 3;//SLTNode* node4 (SLTNode*)malloc(sizeof(SLTNode));//node4-data 4;//将4个节点连接起来//node1-next node2;//node2-next node3;//node3-next node4;//node4-next NULL;//调用链表的打印SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushFront(plist, 5);SLTPrint(plist);//SLTPopBack(plist);//SLTPopBack(plist);//SLTPopBack(plist);SLTPopBack(plist);SLTPopBack(plist);//SLTPrint(plist);//SLTPopFront(plist);//SLTPopFront(plist);SLTPrint(plist);//测试查找SLTNode* find SLTFind(plist, 5);if (find NULL){printf(没有找到\n);}else {printf(找到了\n);}SLTInsert(plist, find, 6);//SLTErase(plist, find);//SLTEraseAfter(find);//SLTErase(plist, find);SLTPrint(plist);SLTDesTroy(plist);SLTPrint(plist);}int main()
{SLTTest01();return 0;
}
