本部分实现双向循环链表的：

• 统计链表中结点个数
• 删除某个结点
  （根据结构体中某个成员的值、根据处于链表中的位置）
  （有头节点、无头结点的处理区别）
• 链表的销毁及野指针处理

双向循环链表_第2部分

• 1 统计链表中的结点个数
• • 1.1 带头结点
  • 1.2 不带头结点
• 2 查找链表中的数据
• • 2.1 查找带头结点的链表
  • 2.2 查找不带头节点的链表
• 3 根据位置删除某个节点
• • 3.1 带头结点
  • • 3.1.1 正数第k个位置
    • 3.1.2 倒数第k个位置
    • 3.1.3 合二为一：过程的抽象
  • 3.2 不带头结点
  • • 3.2.1 正数第k个位置
    • 3.2.2 倒数第k个位置
    • 3.2.3 能合二为一吗？
• 4 销毁链表
• • 野指针问题

1 统计链表中的结点个数

1.1 带头结点

int CountingNodesOfListWithHead(node *list){if(list == NULL){ // Defensive programmingreturn 0;}int cnt = 0;for(node *p = list->pNext; p != list; p = p->pNext){cnt++;}return cnt;
}

1.2 不带头结点

int CountingNodesOfList(node *list){if(list == NULL){ // Defensive programmingreturn 0;} int cnt = 0;node *p = list;do{cnt++;p = p->pNext;}while(p != list);return cnt;
}

2 查找链表中的数据

2.1 查找带头结点的链表

node *SearchListWithHead(node *list, int value){for(node *p = list->pNext; p != list; p = p->pNext){if(p->num == value){ // foundedreturn p;}}return NULL; // not founded
}

2.2 查找不带头节点的链表

node *SearchList(node *list, int value){node *p = list;do{if(p->num == value){return p;}p = p->pNext;}while(p != list);return NULL;
}

3 根据位置删除某个节点

3.1 带头结点

3.1.1 正数第k个位置

int RemoveNodeFromListWithHead_ByHeadPos(node *list, int pos_from_head){// The range of "pos_from_head" is [1 .. n]if(pos_from_head < 1){ // Defensive programmingreturn -1;}int cnt = CountingNodesOfListWithHead(list);if(pos_from_head > cnt){ // Defensive programmingreturn 0;}node *p = list;for(int i = 0; i < pos_from_head; i++){p = p->pNext; // Locating the position from the head}p->pPrev->pNext = p->pNext;p->pNext->pPrev = p->pPrev;free(p);return 1;
}

3.1.2 倒数第k个位置

对于“删除倒数第k个结点”这种操作，“双向循环链表”比“单向链表”方便得多！单向链表实现删除倒数第k个结点时，由于没有“前驱”，需要使用“双指针”进行操作，并定位到待删除结点的前1个结点上面！

int RemoveNodeFromListWithHead_ByBackPos(node *list, int pos_from_head){// The range of "pos_from_head" is [1 .. n]if(pos_from_head < 1){ // Defensive programmingreturn -1;}int cnt = CountingNodesOfListWithHead(list);if(pos_from_head > cnt){ // Defensive programmingreturn 0;}node *p = list;for(int i = 0; i < pos_from_head; i++){p = p->pPrev; // Locating the position from the head}p->pPrev->pNext = p->pNext;p->pNext->pPrev = p->pPrev;free(p);return 1;
}

3.1.3 合二为一：过程的抽象

通过观察可以发现，删除正数第k个位置和删除倒数第k个位置的实现上，只有指针移动方向的区别（就1条代码），所以为什么不将这两个合二为一，有区别的操作（过程）通过一个函数封装起来，然后将这个函数作为参数传入呢？

void moveFromBack(node **p){*p = (*p)->pPrev;
}void moveFromHead(node **p){*p = (*p)->pNext;
}int RemoveNodeFromListWithHead_ByPos(node *list, int pos, void (*move_from)(node **)){// The range of "pos_from_head" is [1 .. n]if(pos < 1){ // Defensive programmingreturn -1;}int cnt = CountingNodesOfListWithHead(list);if(pos > cnt){ // Defensive programmingreturn 0;}node *p = list;for(int i = 0; i < pos; i++){move_from(&p);}p->pPrev->pNext = p->pNext;p->pNext->pPrev = p->pPrev;free(p);return 1;
}

使用这个函数的案例：

int arr[] = {1, 2, 3};
node *list = createList_UsingArray(arr, sizeof(arr) / sizeof(arr[0]));int pos = 2;
RemoveNodeFromListWithHead_ByPos(list, pos, moveFromHead);

3.2 不带头结点

3.2.1 正数第k个位置

int RemoveNodeFromList_ByHeadPos(node **list, int pos_from_head){// The range of "pos_from_head" is [1 .. n]if(pos_from_head < 1){ // Defensive programmingreturn -1;}int cnt = CountingNodesOfList(*list);if(pos_from_head > cnt){ // Defensive programmingreturn 0;}node *p = *list;for(int i = 0; i < pos_from_head - 1; i++){p = p->pNext; // Locating the position from the head}p->pPrev->pNext = p->pNext;p->pNext->pPrev = p->pPrev;if(p == *list){  // Target value is at the head*list = p->pNext;}free(p);return 1;
}

3.2.2 倒数第k个位置

int RemoveNodeFromList_ByBackPos(node **list, int pos_from_head){// The range of "pos_from_head" is [1 .. n]if(pos_from_head < 1){ // Defensive programmingreturn -1;}int cnt = CountingNodesOfList(*list);if(pos_from_head > cnt){ // Defensive programmingreturn 0;}node *p = *list;for(int i = 0; i < pos_from_head; i++){p = p->pPrev; // Locating the position from the head}p->pPrev->pNext = p->pNext;p->pNext->pPrev = p->pPrev;if(p == *list){  // Target value is at the head*list = p->pNext;}free(p);return 1;
}

3.2.3 能合二为一吗？

下面这个代码对于“$删除正数第k个结点$” 是 “$有问题$” 的！！！

int RemoveNodeFromList_ByPos(node **list, int pos, void (*move_from)(node **)){// The range of "pos_from_head" is [1 .. n]if(pos < 1){ // Defensive programmingreturn -1;}int cnt = CountingNodesOfList(*list);if(pos > cnt){ // Defensive programmingreturn 0;}node *p = *list;for(int i = 0; i < pos; i++){move_from(&p);}p->pPrev->pNext = p->pNext;p->pNext->pPrev = p->pPrev;if(p == *list){  // Target value is at the head*list = p->pNext;}free(p);return 1;
}

问题就出在这个用于遍历链表的辅助指针 p 的初始值上！

• 把 p 设到 list 上面，对于“删除倒数第k个结点” 没问题，但是删除正数第k个结点出问题了！
• 你把 p 设到 list->pPrev 上面，对于“删除正数第k个结点” 没问题，但是删除倒数第k个结点出问题了！

二者不可兼得？这就是没有 “头节点” 的坏处！带头结点的链表完全没有这个问题！

4 销毁链表

void DestroyList(node *list){node *p = list->pNext;while(p != list){node *tmp = p; // saved firstp = p->pNext;free(tmp); // then releasing}free(list);
}

野指针问题

答：会打印出来一堆乱七八糟的数据！

其实这是一个“野指针”问题：链表是摧毁了，但是 “指向链表的指针” 还没有指向空（NULL）！它指向了一块“垃圾”！！！这是很危险的！咋办捏？请看下面这段代码的处理方式！

void DestroyList(node **list){node *p = (*list)->pNext;while(p != *list){node *tmp = p; // saved firstp = p->pNext;free(tmp); // then releasing}free(*list);*list = NULL;
}

把这个会变成野指针的指针也传进 “销毁函数” 里面，最后把它指向 $NULL$。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！