如何将带头双向循环链表（二）改写为长尾？

本文共计1061个文字，预计阅读时间需要5分钟。

c

3.打印链表

void ListPrint(LTNode *phead) { assert(phead); LTNode *cur=phead->next; while (cur !=phead) { printf(%d , cur->val); cur=cur->next; } printf(\n);}注意：while循环的结束条件，确保能够打印链表中的所有有效节点。

3.打印链表

void ListPrint(LTNode* phead)//打印 { assert(phead); LTNode* cur = phead->next; while (cur != phead) { printf("%d ", cur->val); cur = cur->next; } printf("\n"); }

注意while循环的结束条件，保证能够打印链表中的所有有效值。要对头结点进行assert判断，不能为空。

4.尾插

//不用二级指针，因为是带头结点的链表，所以不会改变头节点 void ListPushBack(LTNode* phead, ListDataType x)//尾插 { assert(phead);//断言 //创建新结点 LTNode* newnode = BuyListNode(x); //改变指针指向，插入数据 LTNode* tail = phead->prev; newnode->next = tail->next; phead->prev = newnode; newnode->prev = tail; tail->next = newnode; //ListInsert(phead, x); }

5.尾删

void ListPopBack(LTNode* phead)//尾删 { assert(phead);//断言 assert(phead->next != phead);//判断不是头节点 LTNode* prevnode = phead->prev; //将结点从链表中移除 prevnode->prev->next = phead; phead->prev = prevnode->prev; free(prevnode);//释放结点 //ListErase(phead->prev); }

尾删时要注意判断phead->next != phead，不能删除头结点，同时记得要free(prevnode)释放删除后的空间。

6.头插

void ListPushFront(LTNode* phead, ListDataType x)//头插 { assert(phead); LTNode* tail = phead->next; //申请新节点 LTNode* newnode = BuyListNode(x); //改变指针指向，插入数据 tail->prev = newnode; newnode->next = tail; newnode->prev = phead; phead->next = newnode; //ListInsert(phead->next,x); }

7.头删

void ListPopFront(LTNode* phead)//头删 { assert(phead); assert(phead->next != phead);//判断不是头节点 //移除元素 LTNode* tail = phead->next; phead->next = tail->next; tail->next->prev = phead; free(tail);//释放结点 //ListErase(phead->next); }

8.查找某个数并返回其指针

LTNode* ListFind(LTNode* phead, ListDataType x)//找某个数返回其指针 { assert(phead); LTNode* cur = phead->next;//从第一个结点开始 //遍历查找 while (cur != phead) { if (cur->val == x) { return cur;//相等就返回 } cur = cur->next; } return NULL; }

9.在某个位置之前插入

void ListInsert(LTNode* pos, ListDataType x)//在pos之前插入 { assert(pos); LTNode* newnode = BuyListNode(x); LTNode* tail = pos->prev; //改变指针指向，插入数据 tail->next = newnode; newnode->prev = tail; newnode->next = pos; pos->prev = newnode; }

10.删除某个位置

void ListErase(LTNode* pos)//删除pos位置 { assert(pos); LTNode* prevnode = pos->prev; LTNode* nextnode = pos->next; free(pos); prevnode->next = nextnode; nextnode->prev = prevnode; /*pos->next->prev = pos->prev; pos->prev->next = pos->next; free(pos);*/ }

11.判断链表是否为空

bool ListEmpty(LTNode* phead)//判断是否为空,如果是空，返回true { assert(phead); return phead->next == phead; //如果头节点的next指针指向自己说明链表为空 }

12.计算链表中有效值的个数

size_t ListSize(LTNode* phead)//计算链表中有效值的个数 { assert(phead); size_t size = 0; LTNode* tail = phead->next; //遍历计算有效值个数 while (tail != phead) { size++; tail = tail->next; } return size; }

13.销毁链表

void ListDestroy(LTNode* phead)//销毁链表 { assert(phead); LTNode* tail = phead->next; //一个一个销毁 while (tail != phead) { LTNode* nextnode = tail->next; free(tail); tail = nextnode; } //最后在这里将头节点也释放 free(phead); }

销毁链表时要注意要保证每个结点都释放，同时最后也要将头结点释放free(phead)。但是注意这里的参数LTNode* phead是形参，释放空间之后（只要知道地址就可以释放空间），如果在这个函数内想把phead置空，注意形参的改变不会影响实参，所以不能置空。如果想在函数内置空需要传递phead的指针，即链表的二级指针。但是双链表之前的操作没有使用过二级指针，这里为了保持一致性，也不再使用二级指针，可以在函数外面手动把phead置空。