建设银行ETC的网站是哪个,osx 安装 wordpress,天津大学生专业做网站,做公司网站可以抄别人的吗1.链表的分类 链表的结构有多种多样#xff0c;以下情况组合起来就有8种#xff08;2x2x2#xff09;链表结构#xff1a; 虽然有这么多的链表结构#xff0c;但是我们实际中最常用的还是两种结构#xff1a;单链表和双向带头循环链表。 无头单向非循环链表#xff1a;结… 1.链表的分类 链表的结构有多种多样以下情况组合起来就有8种2x2x2链表结构 虽然有这么多的链表结构但是我们实际中最常用的还是两种结构单链表和双向带头循环链表。 无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶.图的邻接表等等。另外这种结构在笔试面试中出现很多。带头双向循环链表结构最为复杂一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然复杂但是用代码实现以后会发现结构会带来很多优势实现反而简单了后面我们代码实现就知道了。 2.带头双向循环链表的实现 和前面的数据结构的实现一样我们需要用三个文件List.h链表结构的声明以及链表的函数的声明List.c函数功能的实现test.c函数功能的测试文件。 2.1 List.h链表结构的定义以及链表的函数的声明 在这里我们需要理解双向是啥意思双向在结构中体现不仅有指向前一个节点的指针而且有指向下一个节点的指针。初次之外通过这两个指针让链表也构成了循环。示意图如下 故而带头双向链表在定义的时候需要用一个包含三个变量的结构变量具体定义如下 注和前面一样在这里我们操作的数据类型可变所以对类型重命名的方法。 #include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.h//带头双向链表的结构的定义 以及所要实现的函数的声明
typedef int LTDatatype;
typedef struct ListNode
{LTDatatype data;struct ListNode* prev;struct ListNode* next;
}LTNode;//打印链表
void LTPrint(LTNode* phead);//初始化 需要创建哨兵位 这样插入和删除的时候就不要考虑链表为空了
void LTInit(LTNode** pphead);
//因此双向链表为空的情况就是链表中只有一个哨兵位//插入
//头插 因为有了哨兵位就并不会影响头结点故传一级指针即可
void LTPushBack(LTNode* phead, LTDatatype x);
//头插
void LTPushFront(LTNode* phead, LTDatatype x);//对链表进行判空
bool* LTEmpty(LTNode* phead);//删除
//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);//数据的查找
LTNode* LTFind(LTNode* phead, LTDatatype x);//指定位置的操作
//指定位置之后数据的插入
void* LTInsert( LTNode* pos, LTDatatype x);//指定位置的数据的删除
void LTErase( LTNode* pos);//链表的销毁
void LTDestroy(LTNode* phead); 2.2 List.c函数功能的实现 需要包含头文件#include List.h 2.2.1 链表的初始化 LTNode* LTBuyNode(LTDatatype x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));if (newnode NULL){perror(malloc fail);exit(1);}newnode-data x;newnode-prev newnode;newnode-next newnode;return newnode;
}
void LTInit(LTNode** pphead) //需要改变头结点影响头结点所以传二级指针
{*ppheadLTBuyNode(-1);
} 实现思路 在初始化之前我们得先实现一个申请新节点的函数。实现该函数需要用到malloc函数申请一个节点的空间再进行判断看是否申请成功。如果申请成功就将数据保存在newnode-data中并且将两个指针变量newnode-pre和newnode-next都指向新节点。最后返回新节点的地址。因为我们实现的是带头的链表这个头是方便插入和删除就相当于哨兵位所以在初始化时只需要创建一个携带无效数据的节点即可。 2.2.2 链表的打印 //链表的打印
void LTPrint(LTNode* phead)
{LTNode* pcur phead-next;if(pcur-next!phead)printf(plist-);while (pcur ! phead){printf(%d-, pcur-data);pcur pcur-next;}printf(plist\n);
} 实现思路 我们需要遍历链表对链表中的数据进行打印即可。但是需要注意的是遍历链表的时候需要从头结点的下一个节点开始遍历遍历结束条件是当前节点所指向的下一个节点 不能是头结点哨兵位。 2.2.3 链表的数据的插入 //插入
//尾插 因为有了哨兵位就并不会影响头结点故传一级指针即可
void LTPushBack(LTNode* phead, LTDatatype x)
{assert(phead);LTNode* newnode LTBuyNode(x);//改变 phead-prev phead-prev-next newnode-prev newnode-nextnewnode-prev phead-prev;newnode-next phead;phead-prev-next newnode;phead-prev newnode;
}
//头插
void LTPushFront(LTNode* phead, LTDatatype x)
{assert(phead);LTNode* newnode LTBuyNode(x);//改变 phead phead-prev phead-next phead-next-prev的指向关系newnode-next phead-next;newnode-prev phead;phead-next-prev newnode;phead-next newnode;
} 实现思路 在实现头插和尾插时都需要先判断所传值的有效性以及先申请到一个新节点。 尾插 先将新节点的prev指向目前链表的尾节点再将新节点的next指向头结点。除此之外我们还需要将链表的尾节点的next指向新节点将头结点的prev指向新节点。头插 先将新节点的next指向头结点的下一个节点再将新节点的prev指向头结点。除此之外我们还需要将头节点的下一个节点的prev指向新节点再将头结点的next指向新节点。 2.2.4 链表的判空 //对链表进行判空
bool LTEmpty(LTNode* phead)
{assert(phead);return phead-next phead;
} 实现思路 返回值为bool类型先判断值的有效性。然后将判断头结点的下一个指针是否为它本身返回即可。 2.2.5 链表的数据的删除 //删除
//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//改变phead-prev-prev的next phead-prev的指向LTNode* del phead-prev;LTNode* delprev del-prev;phead-prev delprev;delprev-next phead;free(del);del NULL;
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//改变phead-next-next的prev phead的nextLTNode* del phead-next;LTNode* delnext del-next;phead-next delnext;delnext-prev phead;free(del);del NULL;
} 实现思路 在实现尾删和头删时都需要先进行对所传值的有效性进行判断再进行判断链表是否为空除头结点外是否还有其他的有效节点。 尾删 先将要删除的节点即尾节点先保存下来同时将尾节点的前一个节点保存下来delprev。要不然直接释放掉就找不到了 然后将头结点的prev指向delprev尾节点的前一个节点将delprev的next指向头节点。最后释放掉del,并将del置为空。头删 先将要删除的节点即头节点先保存下来同时将尾节点的下一个节点保存下来delnext。要不然直接释放掉就找不到了 然后将头节点的nedxt指向delnext再将delnext的prev指向头结点。 最后释放掉要删除的节点并将其置为空。 注因为每个节点都是通过动态内存申请的空间所以在删除节点的时候是通过free切记释放完需置为空避免对野指针的使用。 2.2.6 链表中数据的查找 //数据的查找
LTNode* LTFind(LTNode* phead, LTDatatype x)
{assert(phead);assert(!LTEmpty(phead));LTNode* pcur phead-next;while (pcur ! phead){if (pcur-data x)return pcur;pcur pcur-next;}return NULL;
} 实现思路 先判断所传phead 的有效性再进行判空。然后再进行链表的遍历如果当前节点的数据刚好为所要查找的数据则就返回当前节点的位置否则就返回空指针。 2.2.7 链表中指定位置的操作 // 指定位置的操作
//指定位置之后数据的插入
void* LTInsert(LTNode* pos, LTDatatype x)
{assert(pos);LTNode* newnode LTBuyNode(x);newnode-next pos-next;newnode-prev pos;pos-next-prev newnode;pos-next newnode;
}//指定位置的数据的删除
void LTErase(LTNode* pos)
{assert(pos);pos-prev-next pos-next;pos-next-prev pos-prev;free(pos);pos NULL;
} 实现思路 指定位置之后的插入和指定位置的删除都需要先对所要操作的位置的有效性进行判断。 指定位置之后的插入 申请一个新节点将新节点的next指向pos的下一个节点将新节点的prev指向pos。将pos 的下一个节点的prev指向新节点将pos的next指向新节点。指定位置的删除 先将pos之前的节点的next指向pos的下一个节点再将pos的下一个节点的prev指向pos的前一个节点。 2.2.8 链表的销毁 //链表的销毁
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur phead-next;while (pcur ! phead){LTNode* next pcur-next;free(pcur);pcur next;}free(phead);phead pcur NULL;
} 实现思路 先判断所传值的有效性因为每个节点都是通过动态内存申请的空间所以链表的销毁需要通过free函数通过遍历逐一释放节点 释放完需要将当前节点和头结点置为空。 但是值得注意的是 在释放当前节点时得先将当前节点的下一个节点保存下来。释放加点时应该从头结点的下一个节点开始销毁即从有效节点开始释放。 2.3 test.c函数功能的测试文件 #include List.h
void test()
{LTNode* lt NULL;LTInit(lt);//LTPrint(lt);LTPushBack(lt, 1);LTPushFront(lt, 29);LTPushFront(lt, 25);LTPushFront(lt, 2);LTPushFront(lt, 33);LTPrint(lt);LTPopBack(lt);//LTPushBack(lt, 1);//LTPopBack(lt);LTPrint(lt);/*LTPopFront(lt);LTPopFront(lt);LTPopFront(lt);LTPopFront(lt);LTPrint(lt);*/LTNode*retLTFind(lt, 25);if (ret)printf(ҵ%d\n,ret-data);elseprintf(δҵ\n);LTInsert(ret, 56);LTErase(ret);LTPrint(lt);LTDestroy(lt);LTPrint(lt);
}
int main()
{test();return 0;
} 如有错误还望改正
关注博主优质内容不断更新
