广东宏福建设有限公司网站,wordpress图片列表,安徽电子工程学校,字体设计软件 免费一、链表表示和实现
顺序表的问题及思考 问题#xff1a; 1. 中间/头部的插入删除#xff0c;时间复杂度为O(N) 2. 增容需要申请新空间#xff0c;拷贝数据#xff0c;释放旧空间。会有不小的消耗。 3. 增容一般是呈2倍的增长#xff0c;势必会有一定的空间浪费。例如当…一、链表表示和实现
顺序表的问题及思考 问题 1. 中间/头部的插入删除时间复杂度为O(N) 2. 增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗。 3. 增容一般是呈2倍的增长势必会有一定的空间浪费。例如当前容量为100满了以后增容到 200我们再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间。 思考 如何解决以上问题呢下面给出了链表的结构来看看。
1.1 链表的概念及结构
概念链表是一种物理存储结构上非连续、非顺序的存储结构用于存储逻辑关系为 “一对一” 的数据。链表中每个数据的存储都由以下两部分组成 1.数据元素本身其所在的区域称为数据域。 2.指向直接后继元素的指针所在的区域称为指针域。 单链表的节点 数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 二、链表的分类
2.1实际中要实现的链表的结构非常多样以下情况组合起来就有8种链表结构
1. 单向、双向 2. 带头、不带头 3. 循环、非循环 头节点是一个节点本质上是一个结构体变量区分数据域和指针域不存放任何数据只存放指向链表中真正存放数据的第一个节点的地址仅用于辅助管理整个链表的结构。 头指针是一个指针本质上是一个结构体类型的指针变量不区分数据域和指针域它仅存储链表中第一个节点的地址。 带头节点也就意味着不需要传二级指针了 1.无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结 构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。 2. 带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都 是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带 来很多优势实现反而简单了后面我们代码实现了就知道了。 2.2链表和顺序表的对比 三、单链表
3.1单链表的优劣 1、查找速度慢
2、 不能从后往前
3、找不到前驱
4、单向链表不能自我删除需要靠辅助节点 。 无头单向非循环链表增删查改实现
无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结 构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
3.2SList.h
#pragma once //防止重复包含
#includestdio.h
#includestring.h
#includestdlib.h
#includeassert.htypedef int SLTDataType;//方便改变数据类型
struct SListNode
{SLTDataType data;struct SListNode* next;//下一个地址//结构体中嵌套指针,但不能嵌套自己,会死循环
}SLTNode;
typedef struct SListNode STLNode;// 不会改变链表的头指针传一级指针
void SListPrint(STLNode* phead);// 可能会改变链表的头指针传二级指针
void SListPushBack(STLNode** pphead, SLTDataType x);
void SListPushFront(STLNode** pphead, SLTDataType x);//分有节点头插和无节点头插,尾插得分开处理
void SListPopFront(STLNode** pphead);
void SListPopBack(STLNode** pphead);// 不会改变链表的头指针传一级指针
STLNode* SListFind(STLNode* pphead, SLTDataType x);
// 在pos的前面插入x
void SListInsert(STLNode** pphead, STLNode* pos, SLTDataType x);
// 删除pos位置的值
void SListErase(STLNode** pphead, STLNode* pos);有些地方也有这样定义在pos的前面插入x
//void SListInsert(STLNode** phead, int i, SLTDataType x);删除pos位置的值
//void SListErase(STLNode** phead, int i);
3.3打印链表
第一步输出第一个节点的数据域输出完毕后让指针保存后一个节点的地址 第二步输出移动地址对应的节点的数据域输出完毕后指针继续后移 第三步以此类推直到节点的指针域为NULL void SListPrint(STLNode* phead)
{STLNode* cur phead;while (cur ! NULL)//第一个地址不为空{printf(%d-, cur-data);cur cur-next;//令cur下一个地址}printf(NULL\n);}
3.4新建一个节点
函数中的 malloc 用于在堆上分配内存。它返回一个指向新分配内存的指针该指针被转换为 stlNode* 类型并存储在 newnode 变量中。这个新节点被初始化为包含一个 data 字段和一个 next 字段其中 data 字段被设置为参数 x 的值而 next 字段被初始化为 NULL。
STLNode* BuySListNode(SLTDataType x)
{STLNode* newnode (STLNode*)malloc(sizeof(STLNode));newnode-data x;newnode-next NULL;
}
3.5尾插 void SListPushBack(STLNode** pphead, SLTDataType x)
//void SListPushBack(STLNode* pphead, SLTDataType x)
//在 C语法中可以加,引用,别名
{STLNode* newnode (STLNode*)malloc(sizeof(STLNode));newnode-data x;newnode-next NULL;// 找尾节点的指针if (*pphead NULL)//pphead是plist的地址{*pphead newnode;//在尾部创建新节点}else {STLNode* tail *pphead;//phead在开始时为空while (tail-next ! NULL)//判断下一个指针是否为空{tail tail-next;//指向下一个节点}// 尾节点链接新节点tail-next newnode;}
}
3.6头插 void SListPushFront(STLNode** pphead, SLTDataType x)
{STLNode* newnode BuySListNode(x);//新建一个节点newnode-next *pphead;//在第一个地址前建立一个新节点*pphead newnode;//使新节点变为第一个地址
}
3.7头删
void SListPopFront(STLNode** pphead)
{STLNode* next (*pphead)-next;//保存下一个地址free(*pphead);//释放空间*pphead next;//令其指针指向下一个地址
}
3.8尾删 尾删的目的是从给定的单链表中删除最后一个节点所以分三种情况
1、链表为空
2、链表只有一个节点
3、链表有多个节点
链表为空
如果链表为空*pphead NULL那么就没有什么可以删除的内容所以函数直接返回。
只有一个节点时 有多个节点时 如果链表有多个节点我们需要找到链表的最后一个节点并删除它。为了找到最后一个节点我们设置两个指针 prev 和 tail开始时都指向链表头。然后我们遍历链表直到找到最后一个节点。找到后我们释放最后一个节点的内存然后把倒数第二个节点的 next 设置为 NULL表示链表最后一个节点已经被删除。
void SListPopBack(STLNode** pphead)
{//1.空//2.一个节点//3.一个以上节点if (*pphead NULL)//1.空//如果为空说明链表已经为NULL没有可以删除的内容了{return;}else if ((*pphead)-next NULL)//2.一个节点{free(*pphead);//1.先释放*pphead NULL;//2.把plist置成空}else {//3.一个以上节点STLNode* prev NULL;STLNode* tail *pphead;while (tail-next ! NULL){prev tail;tail tail-next;}free(tail);prev-next NULL;}
}
3.9查找
其实就是遍历一遍链表但是只能返回第一次出现的地址。我们查找到节点的地址后就可以通过地址去修改数据域中存储的数据。
TLNode* SListFind(STLNode* phead, SLTDataType x)
{STLNode* cur phead;while (cur ! NULL)//while (cur){if (cur-data x){return cur;//找到了}cur cur-next;}return NULL;
}
3.10在pos的前面插入 //创建新节点 stlNode* newnode BuySListNode(x); // 初始时prev 指向链表的头节点 pphead。 stlNode* prev *pphead; while (cur ! pos) // 这个 while 循环用于找到 pos 节点。 prev prev-next; cur cur-next; //如果 cur 不等于 pos那么移动 prev 和 cur。prev 移动到 cur 的下一个节点。cur 移动到下一个节点。 prev-next newnode;//现在prev 指向 pos 的前一个节点cur 指向 pos 节点本身。我们将新节点插入到 prev 和 cur 之间。 prev-next newnode; // 然后我们将新节点的 next 指向 pos这样新节点就位于 pos 之前了。
void SListInsert(STLNode** pphead, STLNode* pos, SLTDataType x)
{if (pos *pphead){SListPushFront(pphead, x);}else {STLNode* newnode BuySListNode(x);STLNode* prev *pphead;/*while (prev-next ! pos)*/STLNode* cur *pphead;while (cur ! pos){prev prev-next;}prev-next newnode;newnode-next pos;}
}
3.11删除pos位置的值
void SListErase(STLNode** pphead, STLNode* pos)
{if (pos *pphead)//如果要删除的是头节点{SListPopFront(pphead);//头删}else {STLNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;//删除指定位置的节点free(pos);//释放要删除节点的内存}
} 四、SList.c
#includeSeqList.hvoid SListPrint(STLNode* phead)
{STLNode* cur phead;while (cur ! NULL)//第一个地址不为空{printf(%d-, cur-data);cur cur-next;//令cur下一个地址}printf(NULL\n);}STLNode* BuySListNode(SLTDataType x)
{STLNode* newnode (STLNode*)malloc(sizeof(STLNode));newnode-data x;newnode-next NULL;
}//尾插
void SListPushBack(STLNode** pphead, SLTDataType x)
//void SListPushBack(STLNode* pphead, SLTDataType x)
//在 C语法中可以加,引用,别名
{STLNode* newnode (STLNode*)malloc(sizeof(STLNode));newnode-data x;newnode-next NULL;// 找尾节点的指针if (*pphead NULL)//pphead是plist的地址{*pphead newnode;}else {STLNode* tail *pphead;//phead在开始时为空while (tail-next ! NULL)//判断下一个指针是否为空{tail tail-next;}// 尾节点链接新节点tail-next newnode;}
}void SListPushFront(STLNode** pphead, SLTDataType x)
{STLNode* newnode BuySListNode(x);newnode-next *pphead;*pphead newnode;
}void SListPopFront(STLNode** pphead)
{STLNode* next (*pphead)-next;//保存下一个地址free(*pphead);//释放空间*pphead next;//令其指针指向下一个地址
}void SListPopBack(STLNode** pphead)
{//1.空//2.一个节点//3.一个以上节点if (*pphead NULL){return;}else if ((*pphead)-next NULL){free(*pphead);//1.先释放*pphead NULL;//2.把plist置成空}else {STLNode* prev NULL;STLNode* tail *pphead;while (tail-next ! NULL){prev tail;tail tail-next;}free(tail);prev-next NULL;}
}STLNode* SListFind(STLNode* phead, SLTDataType x)
{STLNode* cur phead;while (cur ! NULL)//while (cur){if (cur-data x){return cur;//找到了}cur cur-next;}return NULL;
}// 在pos的前面插入x
void SListInsert(STLNode** pphead, STLNode* pos, SLTDataType x)
{if (pos *pphead){SListPushFront(pphead, x);}else {STLNode* newnode BuySListNode(x);STLNode* prev *pphead;/*while (prev-next ! pos)*/STLNode* cur *pphead;while (cur ! pos){prev prev-next;}prev-next newnode;newnode-next pos;}
}
// 删除pos位置的值
void SListErase(STLNode** pphead, STLNode* pos)
{if (pos *pphead){SListPopFront(pphead);}else {STLNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);}
}
五、Test.c
#includeSeqList.hvoid TestSList1()
{STLNode* plist NULL;//先让plist指向空SListPushBack(plist, 1);SListPushBack(plist, 2);//插入几个值,用节点存起来SListPushBack(plist, 3);SListPushBack(plist, 4);SListPushFront(plist, 0);SListPrint(plist);SListPopFront(plist);SListPopFront(plist);SListPopFront(plist);SListPrint(plist);SListPopFront(plist);SListPopFront(plist);SListPrint(plist);
}
void TestSList3()
{STLNode* plist NULL;//先让plist指向空SListPushBack(plist, 1);SListPushBack(plist, 2);//插入几个值,用节点存起来SListPushBack(plist, 3);SListPushBack(plist, 4);SListPrint(plist);/*SListPopBack(plist);SListPopBack(plist);SListPrint(plist);*///想在3的前面插入一个数字STLNode* pos SListFind(plist, 1);if (pos){SListInsert(plist, pos, 10);}SListPrint(plist);pos SListFind(plist, 3);if (pos){SListInsert(plist, pos, 30);}SListPrint(plist);
}void TestSList4()
{STLNode* plist NULL;//先让plist指向空SListPushBack(plist, 1);SListPushBack(plist, 2);SListPushBack(plist, 3);SListPushBack(plist, 4);SListPrint(plist);STLNode* pos SListFind(plist, 3);if (pos){SListErase(plist, pos);}SListPrint(plist);pos SListFind(plist, 4);if (pos){SListErase(plist, pos);}SListPrint(plist);
}int main()
{TestSList4();return 0;
}
今天就先到这了
看到这里了还不给博主扣个 ⛳️ 点赞☀️收藏 ⭐️ 关注
你们的点赞就是博主更新最大的动力 有问题可以评论或者私信! 关注必回
