建设网站的技术,校园招聘网站策划书,武当王也高清壁纸,南京seo公司1、链表种类大全 1、链表严格来说可能用2*2*28种结构#xff0c;从是否带头#xff0c;是否循环#xff0c;是否双向三个角度区分。
2、无头单向循环链表一般不会在实际运用中直接存储数据#xff0c;而会作为某些更复杂结构的一个子结构#xff0c;毕竟它只在头插、头删…1、链表种类大全 1、链表严格来说可能用2*2*28种结构从是否带头是否循环是否双向三个角度区分。
2、无头单向循环链表一般不会在实际运用中直接存储数据而会作为某些更复杂结构的一个子结构毕竟它只在头插、头删时具有效率上的优势。
3、带哨兵卫的头有利于解决尾插时多种讨论的复杂情况。
双向有利于insert、erase的实现这两个函数涉及到对pos位置结点的前一个结点的操作而双向链表由于存放了prev指针可以轻松找到前一个结点不用为了找前一个结点而再次遍历从而完成相关功能。
循环有利于直接通过phead-prev找到tail不用遍历提高尾部操作的效率。
2、接口函数
//打印
void LTPrint(LTNode* phead);
//初始化
LTNode* LTInit();
//销毁
void LTDestroy(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead,LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPustFront(LTNode* phead,LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//查找链表中某个值的位置
LTNode* LTFind(LTNode* phead,LTDataType x);
//pos位置之前插入
void LTInsert(LTNode* pos, LTDataType x);
//pos位置删除
void LTErase(LTNode* pos);
结点的创建
typedef int LTDataType;typedef struct LTNode
{struct LTNode* prev;struct LTNode* next;LTDataType data;}LTNode;
与之前相同以int类型作为链表存储的数据类型。
3、初始化
在之前的无头单向非循环链表中我们用一个plist指针指向链表创建时只需要将plist置空即可操作简单不需要通过函数实现。
在顺序表的实现中要考虑到sz顺序表当前存储的数据个数capacity顺序表当前容量还有一个指向顺序表的初始指针避免使用数组导致的一些缺点过程较复杂需要通过函数。
在带头双向循环链表中由于需要创建一个哨兵卫的头结点且为循环结构nextprev都指向tail无元素时tail为自己可以通过init函数来实现。
//初始化
LTNode* LTInit()
{//初始化时创建一个哨兵卫头结点LTNode* phead (LTNode*)malloc(sizeof(LTNode));if (NULL phead){perror(malloc fail);return NULL;}phead-next phead-prev phead;phead-data -1;return phead;}
phead的data暂且设置一个-1其它值也可以。
4、打印
//打印
void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur phead-next;printf(head);while (cur ! phead){printf(%d, cur-data);cur cur-next;}printf(\n);
}
phead一定不为NULL因此可以assert(phead)防止使用者误传入NULL。
phead头结点不为实际值因此从phead-next开始遍历cur只要不为phead的都要进入循环完成打印。
5、尾部操作
1、创建新结点
LTNode* BuyLTNode(LTDataType x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));if (NULL newnode){perror(malloc fail);return NULL;}newnode-data x;newnode-next newnode-prev NULL;return newnode;}
插入操作前需要malloc一个新结点。为防止野指针在创建过程中就将其next和prev置为空 2、判断链表是否为空
删除操作前需要判断链表是否为空。
//判断链表原来是否为空的函数
bool IsEmpty(LTNode* phead)
{return phead-next phead;
}
这里采用bool值返回值为true非0和false0两种需要包含stdbool.h头文件这里的phead-next如果等于phead即链表中只有哨兵卫头结点即为空返回为1非0代表链表的状态为空 3、尾插
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode BuyLTNode(x);if (NULL newnode){perror(BuyLTNode fail);return;}//按照之前的思路尾插需要先找尾// 这里phead的prev直接找尾 需要4步指针操作LTNode* tail phead-prev;tail-next newnode;newnode-prev tail;phead-prev newnode;newnode-next phead;}
先利用phead-prev找到原来的尾结点tail然后创建新的尾结点随后通过4步指针操作建立newnode与tail和phead的联系。不用遍历找尾提高了效率 带哨兵卫的头结点的优势不用讨论原链表为空的情况。 4、尾删
//尾删
void LTPopBack(LTNode* phead)
{assert(phead);//先判断原来是否为空assert(!IsEmpty(phead));LTNode* tail phead-prev;LTNode* prev tail-prev;free(tail);tail NULL;phead-prev prev;prev-next phead; }
assert内为IsEmpty即为空时报错。
分别用tail和prev标记要删除的尾结点以及前一个结点free掉tail利用两个指针建立prev与phead的联系使其成为新尾。 多删除时assert报错
6、头部操作
1、头插
//头插
void LTPustFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode BuyLTNode(x);if (NULL newnode){perror(BuyLTNode fail);return;}newnode-next phead-next;phead-next-prev newnode;newnode-prev phead;phead-next newnode;}
通过4个指针建立newnode与phead、phead-next的联系要注意顺序先建立与phead-next
的否则其会被改变无法找到。
当然在开始时新建立一个next指针指向phead-next的结点也可以。 2、头删 //头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(!IsEmpty(phead));LTNode* first phead-next;phead-next first-next;first-next-prev phead;free(first);first NULL;}
先利用first标记要删除的头结点然后用两个指针建立phead与first的next结点之间的关系最后free掉first。 头部操作本身就是链表的优势因此仍不需要遍历 7、查找及指定位置pos操作
1、查找函数
//查找链表中某个值的位置
LTNode* LTFind(LTNode* phead,LTDataType x)
{assert(phead);assert(!IsEmpty(phead));LTNode* pos phead-next;while (pos ! phead){if (pos-data x){return pos;}pos pos-next;}printf(没找到\n);exit(0);
}从phead-next的位置开始遍历找到了则用pos返回该结点的地址使用者可以用一个ret指针在外部接收找不到则终止程序。查找前先确认链表不为空。 通过调试观察到ret拿到了值为3的结点的地址 还可以继续展开观察带头双向循环链表的内部结构是怎样完成循环的。 2、insert指定位置前插入
//pos位置之前插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode BuyLTNode(x);LTNode* prevptr pos-prev;prevptr-next newnode;newnode-next pos;newnode-prev prevptr;pos-prev newnode;} 先用prevptr找到pos的前一个结点然后利用4个指针建立newnode与这两个结点的关系完成中间位置插入。 可以用pos-prev指针直接找到前一个结点不需要查找外的额外遍历提高了效率。 3、erase指定位置删除
//pos位置删除
void LTErase(LTNode* pos)
{assert(pos);//LTNode* prevpos pos-prev;//LTNode* nextpos pos-next;//prevpos-next nextpos;//nextpos-prev prevpos;//free(pos);//pos NULL;pos-prev-next pos-next;pos-next-prev pos-prev;free(pos);pos NULL;
} 同样找到pos前一个位置的结点连接pos前一个与后一个结点然后free掉pos 4、优化头尾操作
只要有了insert和erase两个函数就可以轻易完成头尾的4个操作函数只需要复用上述两个即可
例如在pos前插入一个节点实际效果为尾插。
insert(pos-next)效果为头插
erase(phead-next)为头删
erase(phead-prev)为尾删 8、链表的销毁
//销毁
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){LTNode* next cur-next;free(cur);cur next;}free(phead);printf(销毁成功\n);
}从phead-next位置开始遍历销毁即可最后使用者在外部对创建的链表手动置空 掌握了以上操作20分钟写一个链表不是难事 目录
1、链表种类大全
2、接口函数
3、初始化
4、打印
5、尾部操作
1、创建新结点
2、判断链表是否为空
3、尾插
4、尾删
6、头部操作
1、头插
2、头删 7、查找及指定位置pos操作
1、查找函数 2、insert指定位置前插入 3、erase指定位置删除 4、优化头尾操作
8、链表的销毁
