河北建设信息平台网站,新洲建设局网站,网站规划与设计大作业怎么做,泰州网站开发不可否认的是#xff0c;前几节我们讲解的顺序表存在一下几点问题#xff1a; 1. 中间、头部的插入和删除#xff0c;需要移动一整串数据#xff0c;时间复杂度O(N) 2. 增容需要申请新空间#xff0c;拷贝数据#xff0c;释放旧空间。会有不小的消耗 3. 增容一般是2倍的增… 不可否认的是前几节我们讲解的顺序表存在一下几点问题 1. 中间、头部的插入和删除需要移动一整串数据时间复杂度O(N) 2. 增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗 3. 增容一般是2倍的增长这势必会造成空间的浪费 那如何解决这些问题呢此时链表出现了
1. 链表的概念和结构 我们之前说过线性表的特点就是逻辑上是连续的物理上不一定连续。顺序表是逻辑上是连续的物理上也是连续的。而今天的链表就是逻辑上是连续的但是物理上是不连续的 最简单的链表是由节点们串在一起组成的每个节点包含了两个内容 1. 要存入的有效数据 2. 下一个节点的地址 可以看出每个节点在物理上都是独立的不连续的。但是每个节点在逻辑上又有关联每个节点都知道下一个节点的指针要找到下一个节点就访问那个指针就好了 具体来讲就是把 plist 当成一个钥匙最开始保存的是第一个节点的地址用完第一个节点的数据之后把第一个节点中存储的地址再给到plist这样plist就可以开第二个节点了以此类推··· 下面我们依照上面的图片做一个简单的节点结构 到这里链表的地基就学会了下面我们尝试实现一下 2. 单链表(Single linked list)的实现 跟顺序表一样先是把准备工作三个文件准备好 再把链表节点写出来 在这里我要重点声明一下接下来如果从主函数前去访问链表时用的都是plist参数从主函数中给子函数传参也是plist就像这样 然后就正式进入链表实现啦大家伙坐稳喽 2.1 链表的打印 打印的逻辑就是先拿到第一个节点的地址 pcur把这个地址访问到 data 打印出来然后将pcur的内容变成下一个要打印的节点的地址直到pcur的内容是NULL为止 2.2 链表的插入 因为插入就一定需要申请一个新的节点所以我们先把这个功能封装好 向堆区申请一块空间用来存放节点记录这个节点的地址 当然如果你想把newnode的类型改成 SLTNode 也可以不过后面要用到节点地址的时候就要取地址一下很麻烦所以我们干脆直接返回节点的地址
2.2.1 尾插 在链表的尾端插入一个数据。 因为如果链表为空(没有节点)的时候要修改 plist 的内容让它指向我们新添加的第一个节点所以我们传参的时候要传 plist 因此函数参数要用二级指针来接收这个可能会被修改的plist 如果链表不为空就去找尾节点把为节点的next成员内容从NULL变成我们新添加的节点地址可以这么理解 这个图里有一点不恰当就是这个 pphead 要解引用一次 (*pphead) 才能找到第一个节点的地址 接下来我们运行一下看看效果 2.2.2 头插 头插比尾插好理解一点直接上思路图(画的太丑了QAQ) 很明显链表是否为空对于需要的操作是没有影响的上代码 最后运行一下看结果 因为每次都是把节点插到最前面所以反着打出来是对的 2.3 链表的删除
2.3.1 尾删 尾删的逻辑就是找到最后一个节点 ptail 和倒数第二个节点 prev 把倒数第二个节点的next成员置为空指针释放掉最后一个节点。当然如果链表为空也就是说没有节点的话就不能执行删除操作用assert断言报错 上代码 2.3.2 头删 头删也是需要两个指针控制要注意的就是要先释放掉*pphead也就是第一个节点然后再把*pphead的内容改成第二个节点的地址接上第二个节点 代码如下 2.4 查找 链表的查找很简单就是遍历链表找到了就返回节点地址没找到就返回空指针 2.5 在任意位置插入数据
2.5.1 在指定位置前插入数据 可以用SLTFind找到要被前插的节点的地址pos在这个节点前面插入节点还需要直到它前面那个节点的地址prev 在实现这个功能的时候我们要注意当pos是头节点的情况 下面使用一下 2.5.2 在指定位置后插入数据 这个比较简单但是要注意给地址的顺序要先把后面那个节点的地址给到新节点再把指定位置pos节点的地址成员改成新节点的地址否则就会导致后面那个节点地址的丢失没办法接到新节点后面了 还有就是我们不需要知道链表的头节点是什么了只需要关注pos就行了 2.6 在任意位置删除节点
2.6.1 删除pos节点 删除pos节点要先知道它前面的那个节点prev然后把prev跟pos后面那个节点先连起来最后再把pos释放掉。还有要注意的一点就是当pos就是链表头节点的时候要特殊处理一下 2.6.2 删除pos后面的一个节点 这个功能也是只需要关注pos后面的内容就行所以只需要传pos一个参数。还要注意一点就是pos不能是链表中的最后一个节点否则它后面没有节点了还删什么 2.7 链表的销毁 两个变量pcur记录当前要准备销毁的节点地址next记录下一个节点地址防止销毁上一个节点之后找不到下一个节点了。然后两个变量一直循环向后扫描销毁直到pcur指向NULL 3. 链表的分类 链表按带头或不带头单向或双向循环或不循环排列组合有8种 我们刚刚学的单链表全称就是不带头单向不循环链表 带头不带头是说链表有没有一个不存储有效数据的节点放在第一个存放有效数据节点之前 单向双向是说链表能通过后一项找到前一项就是双向的如果只能根据前一项找到后一项链表就是单项的。或者说双向链表的节点中的两个存放地址的成员中一个存下一个节点的地址一个存上一个节点的地址。 循环不循环是说最后一个节点指向第一个节点就是循环链表要是最后一个节点指向NULL就是不循环链表 虽然链表的种类很多但是常用的只有两种 1.单链表(不带头单向不循环链表) 单链表结构简单一般不会单独用来存贮数据它一般作为其他数据结构的子结构出现 2.双向链表(带头双向循环链表) 双向链表结构最复杂一般用来单独存储数据。它虽然复杂但是之后实现它的实际就会发现它有很多优势致使实现它反而变得简单了后面会有实现它的章节的。 4. 本节代码 SList.h
#includestdio.h
#includestdlib.h
#includeassert.h//链表是由节点构成的
typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;//链表的打印
void SLTPrint(SLTNode* phead); //链表的插入
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);//链表的头删和尾删
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x);//在任意位置插入数据
//在指定位置前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//在任意位置删除节点
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos后面的一个节点
void SLTEraseAfter(SLTNode* pos);//销毁链表
void SLTDestory(SLTNode** pphead); SList.c
#includeSList.h//链表的打印
void SLTPrint(SLTNode* phead)
{SLTNode* pcur phead;while (pcur){printf(%d - , pcur-data);pcur pcur-next;}printf(NULL\n);
}//申请一个新节点
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));newnode-data x;newnode-next NULL;return newnode;
}//链表的插入
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);//申请一个新节点SLTNode* newnode SLTBuyNode(x);//链表为空新节点作为头if (*pphead NULL){*pphead newnode;return;}//链表不为空找尾节点SLTNode* ptail *pphead;while (ptail-next){ptail ptail-next;}//找到尾节点了ptail-next newnode;
}//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);//申请一个新节点SLTNode* newnode SLTBuyNode(x);//链表为不为空操作都一样//斩断第一个连接再把新节点接进去newnode-next *pphead;*pphead newnode;
}//链表的头删和尾删
//尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead);//链表不能为空assert(*pphead);//链表不为空//链表只有一个节点if ((*pphead)-next NULL){free(*pphead);*pphead NULL;return;}//链表有多个节点SLTNode* ptail *pphead;SLTNode* prev NULL;//找到尾节点while (ptail-next){prev ptail;ptail ptail-next;}prev-next NULL;free(ptail);ptail NULL;}//头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead);//链表不能为空assert(*pphead);//让第二个节点变成新的头节点//释放旧的头节点SLTNode* sec (*pphead)-next;free(*pphead);*pphead sec;
}//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{assert(pphead);//遍历链表SLTNode* pcur *pphead;while (pcur){if (pcur-data x){return pcur;}pcur pcur-next;}return NULL;
}//在任意位置插入数据
//在指定位置前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//这里断言*pphead不能为空//因为指定节点的地址pos不能为空所以这个链表也不能为空assert(*pphead);//当pos是头节点,执行头插if (pos *pphead){SLTPushFront(pphead, x);return;}//当pos不是头节点//申请一个新节点SLTNode* newnode SLTBuyNode(x);SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next newnode;newnode-next pos;
}//在指定位置后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);//申请一个新节点SLTNode* newnode SLTBuyNode(x);newnode-next pos-next;pos-next newnode;
}//在任意位置删除节点
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);assert(*pphead);//如果pos指向头节点执行头删if (*pphead pos){SLTPopFront(pphead);return;}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不能为空//就是说pos不能是最后一个节点assert(pos-next);SLTNode* del pos-next;pos-next pos-next-next;free(del);del NULL;
}//销毁链表
void SLTDestory(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* pcur *pphead;SLTNode* next NULL;while (pcur){next pcur-next;free(pcur);pcur next;}*pphead NULL;
}
