青少年宫网站开发,计算机前端和后端,淮南医院网站建设,典型的营销型企业网站目录
一#xff0c;链表的概念及结构
二#xff0c;接口实现 1#xff0c;单链表的创建 2#xff0c;接口函数 3#xff0c;动态创立新结点 4#xff0c;打印 5#xff0c;头插 6#xff0c;头删 7#xff0c;尾插 8#xff0c;尾删 9#xff0c;查找 10#xff…目录
一链表的概念及结构
二接口实现 1单链表的创建 2接口函数 3动态创立新结点 4打印 5头插 6头删 7尾插 8尾删 9查找 10单链表在pos位置之后插入x 11单链表删除pos位置之后的值 12销毁
三源代码
LKList.h
LKList.c
四总结 一链表的概念及结构 链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 而在数据结构中 注意
1从上图可以看出链式结构在逻辑上是连续的但是在物理上不一定连续 2现实中的结点一般都是从堆上申请出来的 3从堆上申请的空间是按照一定的策略来分配的两次申请的空间可能连续也可能不连续 实际中链表的结构非常多样今天我们来写一下单链表此表一会其他的自然水到渠成 二接口实现 1单链表的创建
//无头 单向 非循环链表增删查改实现
typedef int LKLDataType;
typedef struct LinKedListNode
{LKLDataType data;struct LinKedListNode* next;
}LKLNode;
首先创建一个结构体表示单链表data是存储的值LKLDataType是储存的值的数据类型next是结点----指向下一个
这里的LKLDataType是int的重命名也可以说是数据类型的重命名这样统一化方便后续更改 2接口函数
// 动态创立新结点
LKLNode* BuyLKLNode(LKLDataType x);
// 打印
void LKLPrint(LKLNode* phead);
// 头插
void LKLNodePushFront(LKLNode** phead, LKLDataType x);
// 头删
void LKLNodeBackFront(LKLNode** phead);
// 尾插
void LKLNodePushBack(LKLNode** phead, LKLDataType x);
// 尾删
void LKLNodePopBack(LKLNode** phead);
// 查找
LKLNode* LKLFind(LKLNode* phead, LKLDataType x);
// 单链表在pos位置之后插入x
void LKLInsertAfter(LKLNode* pos, LKLDataType x);
// 单链表删除pos位置之后的值
void LKLEraseAfter(LKLNode* pos);
// 销毁
void LKLDestroy(LKLNode** plist); 这是以上要实现的接口函数 3动态创立新结点
//动态创立新结点
LKLNode* BuyLKLNode(LKLDataType x)
{LKLNode* newnode (LKLNode*)malloc(sizeof(LKLNode));newnode-data x;newnode-next NULL;return newnode;
}
后面创立新节点时直接调用此函数一定要向堆区申请空间这样函数结束空间会保留不会被回收 4打印
//打印
void LKLPrint(LKLNode* phead)
{assert(phead);LKLNode* cur phead;while (cur){printf(%d-, cur-data);cur cur-next;}printf(NULL);
}
打印也就是打印data的值用curphead然后每次打印完都让cur走向下一个直到为空结束 5头插
//头插
void LKLNodePushFront(LKLNode** phead, LKLDataType x)
{assert(phead);LKLNode* newnode BuyLKLNode(x);newnode-next *phead;*phead newnode;
}
先断言一下既然插入数据那就要申请一个新节点然后令新节点的next指向phead然后再令phead指向新节点 6头删
//头删
void LKLNodeBackFront(LKLNode** phead)
{assert(phead);//为空assert(*phead);//非空LKLNode* newnode (*phead)-next;free(*phead);*phead newnode;
}
还是先断言有人会问为什么要断言两次其实很好判断哪个需要解引用那个就需要断言
令一个变量newnode等于头结点的下一个在释放头结点在令头结点指向newnode即可 7尾插
//尾插
void LKLNodePushBack(LKLNode** phead, LKLDataType x)
{assert(phead);assert(*phead);LKLNode* newnode BuyLKLNode(x);LKLNode* cur *phead;//为空if (*phead NULL){*phead newnode;}//非空else{while (cur-next){cur cur-next;}cur-next newnode;}
}
还是先断言判断然后要插入一个新的数据先申请一个新结点如果头结点为空则直接让头结点指向新结点即可如果头结点不为空则需要找到next为空的结点这里用一个循环搞定然后再直接让next为空的结点指向新节点即可 8尾删
//尾删
void LKLNodePopBack(LKLNode** phead)
{assert(phead);//为空assert(*phead);//一个if ((*phead)-nextNULL){free(*phead);*phead NULL;}//两个及以上else{LKLNode* tail *phead;/*LKLNode* prev NULL;while (tail-next){prev tail;tail tail-next;}free(prev-next);prev-next NULL;*/while (tail-next-next){tail tail-next;}free(tail-next);tail-next NULL;}
}
还是先断言一下然后这里有两种情况链表只有一个结点两个以上结点的时候
当链表只有一个结点也就是头结点直接头删即可
两个以上结点的时候我这里有两种解决方案
方案一常规法先用循环找到next为空的结点并且在循环里保留上一个结点prev然后释放next为空的结点再让prev的next指向空即可
方案二不需要标记上一个结点直接原地判断判断结点的next的next是否为空否则继续向后推进是则释放结点的next然后再令自己的next指向空也就相当于变成了尾结点 9查找
// 单链表查找
LKLNode* LKLFind(LKLNode* phead, LKLDataType x)
{assert(phead);LKLNode* pos phead;while (pos){if (pos-data x){return pos;}pos pos-next;}return NULL;
}
老样子先断言一下然后直接用循环遍历链表找到data是x的值然后返回此结点即可 10单链表在pos位置之后插入x
// 单链表在pos位置之后插入x
void LKLInsertAfter(LKLNode* pos, LKLDataType x)
{assert(pos);LKLNode* newnode BuyLKLNode(x);LKLNode* cur pos;newnode-next cur-next;cur-next newnode;
}
先断言要插入数据先申请一个新结点然后令新结点的next指向pos的next再返回来让pos的next指向新结点 11单链表删除pos位置之后的值
// 单链表删除pos位置之后的值
void LKLEraseAfter(LKLNode* pos)
{assert(pos);assert(pos-next);LKLNode* cur pos;LKLNode* newnode cur-next-next;free(cur-next);cur-next newnode;
}
要删除值首先要确保得有值所以开始断言
先定义一个变量newnode指向pos的next的next然后再释放pos的next再令pos指向newnode以达到删除之后的效果 12销毁
// 单链表的销毁
void LKLDestroy(LKLNode** phead)
{assert(phead);assert(*phead);LKLNode* cur *phead;LKLNode* next NULL;while (cur){next cur-next;free(cur);cur next;}
}
老样子那个需要解引用那个就先断言一下然后用循环遍历先标记下一个结点然后释放自己再让自己指向标记的结点直到为空结束 三源代码
LKList.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h//无头 单向 非循环链表增删查改实现
typedef int LKLDataType;
typedef struct LinKedListNode
{LKLDataType data;struct LinKedListNode* next;
}LKLNode;// 动态创立新结点
LKLNode* BuyLKLNode(LKLDataType x);
// 打印
void LKLPrint(LKLNode* phead);
// 头插
void LKLNodePushFront(LKLNode** phead, LKLDataType x);
// 头删
void LKLNodeBackFront(LKLNode** phead);
// 尾插
void LKLNodePushBack(LKLNode** phead, LKLDataType x);
// 尾删
void LKLNodePopBack(LKLNode** phead);
// 查找
LKLNode* LKLFind(LKLNode* phead, LKLDataType x);
// 单链表在pos位置之后插入x
void LKLInsertAfter(LKLNode* pos, LKLDataType x);
// 单链表删除pos位置之后的值
void LKLEraseAfter(LKLNode* pos);
// 销毁
void LKLDestroy(LKLNode** plist);LKList.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeLKList.h//动态创立新结点
LKLNode* BuyLKLNode(LKLDataType x)
{LKLNode* newnode (LKLNode*)malloc(sizeof(LKLNode));newnode-data x;newnode-next NULL;return newnode;
}
//头插
void LKLNodePushFront(LKLNode** phead, LKLDataType x)
{assert(phead);LKLNode* newnode BuyLKLNode(x);newnode-next *phead;*phead newnode;
}
//头删
void LKLNodeBackFront(LKLNode** phead)
{assert(phead);//为空assert(*phead);//非空LKLNode* newnode (*phead)-next;free(*phead);*phead newnode;
}
//尾插
void LKLNodePushBack(LKLNode** phead, LKLDataType x)
{assert(phead);assert(*phead);LKLNode* newnode BuyLKLNode(x);LKLNode* cur *phead;//为空if (*phead NULL){*phead newnode;}//非空else{while (cur-next){cur cur-next;}cur-next newnode;}
}
//尾删
void LKLNodePopBack(LKLNode** phead)
{assert(phead);//为空assert(*phead);//一个if ((*phead)-nextNULL){free(*phead);*phead NULL;}//两个及以上else{LKLNode* tail *phead;/*LKLNode* prev NULL;while (tail-next){prev tail;tail tail-next;}free(prev-next);prev-next NULL;*/while (tail-next-next){tail tail-next;}free(tail-next);tail-next NULL;}
}
// 单链表查找
LKLNode* LKLFind(LKLNode* phead, LKLDataType x)
{assert(phead);LKLNode* pos phead;while (pos){if (pos-data x){return pos;}pos pos-next;}return NULL;
}
// 单链表在pos位置之后插入x
void LKLInsertAfter(LKLNode* pos, LKLDataType x)
{assert(pos);LKLNode* newnode BuyLKLNode(x);LKLNode* cur pos;newnode-next cur-next;cur-next newnode;
}
// 单链表删除pos位置之后的值
void LKLEraseAfter(LKLNode* pos)
{assert(pos);assert(pos-next);LKLNode* cur pos;LKLNode* newnode cur-next-next;free(cur-next);cur-next newnode;
}// 单链表的销毁
void LKLDestroy(LKLNode** phead)
{assert(phead);assert(*phead);LKLNode* cur *phead;LKLNode* next NULL;while (cur){next cur-next;free(cur);cur next;}
}
//打印
void LKLPrint(LKLNode* phead)
{assert(phead);LKLNode* cur phead;while (cur){printf(%d-, cur-data);cur cur-next;}printf(NULL);
}
四总结
做数据结构的题目画图很重要小伙伴们刚开始喜欢用脑子去构图想象但遇到复杂的情况会紊乱的画图最为可观方便可以培养一个良好的画图习惯
如有不足之处欢迎来补充交流
完结。。。
