ç圆形双链表delete_node - 迭代遍历在第一轮被删除节点中删除后 [英] c circular double linked-list delete_node - iterate traverses deleted node on first pass after delete
问题描述
所有，在GNU C中，我有一个循环双向链表我想实现一个功能delete_node。它工作正常，所有节点的节点除外0它删除（免费的（））节点0，但第一次的名单中删除节点后0走过，它仍然是present为第一遍导致有条件停止迭代失败。实施的基础是：
All, in GNU c, I have a circular doubly linked-list I am trying to implement a delete_node function on. It works fine for all nodes except node 0. It does delete (free()) node 0, but the first time the list is traversed after deleting node 0, it is still present for the first pass causing the conditional to stopping the iteration to fail. The basics of the implementation are:
struct record
{
char *line;
int lineno;
int linetype;
struct record *prev;
struct record *next;
};
typedef struct record rec;
void
iterfwd (rec *list) {
rec *iter = list; // second copy to iterate list
if (iter == NULL) {
fprintf (stdout,"%s(), The list is empty\n",__func__);
} else {
do {
printf ("%2d - prev: %p cur: %p next: %p\n", iter->lineno, iter->prev, iter, iter->next);
iter = iter->next;
} while (iter != list);
}
}
void
delete_node (rec *list, int num) {
rec *iter = list; // second copy to iterate list
int cnt = 0;
int found = 0;
if (iter == NULL) {
fprintf (stdout,"%s(), The list is empty\n",__func__);
} else {
// traverse list forward (check cnt == num, else if end -> Out Of Range)
do {
if (cnt == num) {
found=1;
(iter->prev)->next = iter->next;
(iter->next)->prev = iter->prev;
free (iter);
break;
}
iter = iter-> next;
cnt++;
} while (iter != list);
if (found != 1) {
fprintf (stderr, "%s(), Error: record to delete is out of range (%d)\n", __func__, num);
}
}
}
int main (int argc, char *argv[]) {
struct record *textfile = NULL; // instance of record, pointer to list
int node = 0;
node = (argc >= 2) ? atoi (argv[1]) : 0;
textfile = fillrecord (); // fill textfile circular linked-list
iterfwd (textfile);
delete_node (textfile, node);
iterfwd (textfile);
return 0;
}
一个完整列表是在这里： HTTP： //www.3111skyline.com/dl/dev/prg/src/ll-double-cir.c.txt
A complete listing is here: http://www.3111skyline.com/dl/dev/prg/src/ll-double-cir.c.txt
该列表填充50条记录测试数据，我已经插入的printf声明确认指针操作。删除任何节点，除了节点0按预期工作（以下是ITER指针地址 - > preV，ITER，iter->其次为受影响的行[pre型和后删除]的缺失节点10）：
The list is filled with 50 records of data for testing and I have inserted printf statements to confirm the pointer operations. Deleting any node except node 0 works as expected (the following is the pointer addresses for iter->prev, iter, iter->next for the affected rows [pre- and post- delete] for a deletion of node 10):
9 - prev: 0x603490 cur: 0x603520 next: 0x6035b0
10 - prev: 0x603520 cur: 0x6035b0 next: 0x603640 <-- delete_node
11 - prev: 0x6035b0 cur: 0x603640 next: 0x6036d0
9 - prev: 0x603490 cur: 0x603520 next: 0x603640
10 - prev: 0x603520 cur: 0x6035b0 next: 0x603640 <-- (node deleted)
11 - prev: 0x603520 cur: 0x603640 next: 0x6036d0
在列表中的下一个导线，如预期的所有作品：
On the next traverse of the list, all works as expected:
7 - prev: 0x603370 cur: 0x603400 next: 0x603490
8 - prev: 0x603400 cur: 0x603490 next: 0x603520
9 - prev: 0x603490 cur: 0x603520 next: 0x603640
11 - prev: 0x603520 cur: 0x603640 next: 0x6036d0
12 - prev: 0x603640 cur: 0x6036d0 next: 0x603760
然而，如果节点0被删除，delete_node正确处理的指针：
However, if node 0 is deleted, the delete_node properly handles the pointers:
49 - prev: 0x604b10 cur: 0x604ba0 next: 0x603010
0 - prev: 0x604ba0 cur: 0x603010 next: 0x6030a0 <-- delete_node
1 - prev: 0x603010 cur: 0x6030a0 next: 0x603130
49 - prev: 0x604b10 cur: 0x604ba0 next: 0x6030a0
0 - prev: 0x604ba0 cur: 0x603010 next: 0x6030a0 <-- (node deleted)
1 - prev: 0x604ba0 cur: 0x6030a0 next: 0x603130
但随后的拳头试图穿越删除后的列表中，节点0在第一次出现从而导致迭代条件，而（ITER =名单！）'失败，并成为死循环：
But then on the fist attempt to traverse the list after deletion, node 0 appears on the first pass causing the iterator conditions 'while (iter != list)' to fail and become stuck in a loop:
0 - prev: 0x604ba0 cur: 0x603010 next: 0x6030a0
1 - prev: 0x604ba0 cur: 0x6030a0 next: 0x603130
2 - prev: 0x6030a0 cur: 0x603130 next: 0x6031c0
3 - prev: 0x603130 cur: 0x6031c0 next: 0x603250
4 - prev: 0x6031c0 cur: 0x603250 next: 0x6032e0
<snip>
47 - prev: 0x6049f0 cur: 0x604a80 next: 0x604b10
48 - prev: 0x604a80 cur: 0x604b10 next: 0x604ba0
49 - prev: 0x604b10 cur: 0x604ba0 next: 0x6030a0
1 - prev: 0x604ba0 cur: 0x6030a0 next: 0x603130
2 - prev: 0x6030a0 cur: 0x603130 next: 0x6031c0
3 - prev: 0x603130 cur: 0x6031c0 next: 0x603250
如上所示，迭代遍历后0-49，被删除的节点0消失，它再次开始适当地遍历1-49，但在这一点上，它是在一个循环中，因为在条件（ITER！=名单）总是真（节点0从不断等于列表中消失preventing ITER）。这是一个纯粹的循环列表，还有设置为null没有头部或尾部节点，给最终> next指向列表的开始和第一 - > $ P $光伏点结束。什么是特技具有用于节点delete_node（）函数工作0，使得在第一次迭代之后删除与1开始，而不是旧0那然后消失
As shown above, after the iterator traverses 0-49, the deleted node 0 disappears and it begins traversing properly 1-49 again, but at that point it is in a loop because the conditional (iter != list) is always true (node 0 disappears preventing iter from ever equaling list). This is a pure circular list, there are no HEAD or TAIL nodes set to null, the end->next points to the beginning of the list and the first->prev points to the end. What is the trick to having the delete_node() function work for node 0 such that the first iteration after delete starts with 1 and not the old 0 that then disappears?
推荐答案
你不修改的主叫方的的指针，要求非常节点的是的点为删除时请求。下面的一些您的code的削减版，演示做到这一点的一种方法：
You're not modifying the caller's pointer when requesting the very node it points to as the delete request. The following, a cut down version of some of your code, demonstrates one way to do this:
#include <stdio.h>
#include <stdlib.h>
typedef struct record rec;
struct record
{
int data;
rec *prev, *next;
};
void delete_node (rec ** pp, int num)
{
if (!*pp)
return;
// find the num'th node
while (num-- && *pp)
pp = &(*pp)->next;
// setup victim
rec *victim = *pp;
// non-self-reference node means just rewire
if (victim && (victim != victim->next))
{
victim->prev->next = victim->next;
victim->next->prev = victim->prev;
*pp = victim->next;
}
else
{ // deleted node was self-referenced. last node
*pp = NULL;
}
free(victim);
}
void iterfwd(const rec* list)
{
const rec *p = list;
printf("list: %p\n", list);
if (p)
{
for (; p; p = (p->next != list ? p->next : NULL))
printf("prev: %p, self:%p, next:%p, data = %d\n", p->prev, p, p->next, p->data);
}
puts("");
}
void insert(rec **pp, int data)
{
// setup new node
rec *newp = malloc(sizeof(*newp));
newp->data = data;
if (!*pp)
{
newp->next = newp->prev = newp;
*pp = newp;
}
else
{ // insert between prev and head.
newp->next = *pp;
(*pp)->prev->next = newp;
newp->prev = (*pp)->prev;
(*pp)->prev = newp;
}
}
int main()
{
rec *list = NULL;
int i;
for (i=1; i<=5; ++i)
insert(&list, i);
iterfwd(list);
// delete fourth node (0-based)
delete_node(&list, 3);
iterfwd(list);
// delete first node (0-based)
delete_node(&list, 0);
iterfwd(list);
// delete first node (0-based)
delete_node(&list, 0);
iterfwd(list);
// delete first node (0-based)
delete_node(&list, 0);
iterfwd(list);
// delete first node (0-based)
delete_node(&list, 0);
iterfwd(list);
return 0;
}
输出（显然依赖于系统）
请注意如何传入的指针（传地址）时请求0元素被删除修改。
Note how the passed-in pointer (pass by address) is modified when requesting the 0-element is removed.
list: 0x100103af0
prev: 0x100103b70, self:0x100103af0, next:0x100103b10, data = 1
prev: 0x100103af0, self:0x100103b10, next:0x100103b30, data = 2
prev: 0x100103b10, self:0x100103b30, next:0x100103b50, data = 3
prev: 0x100103b30, self:0x100103b50, next:0x100103b70, data = 4
prev: 0x100103b50, self:0x100103b70, next:0x100103af0, data = 5
list: 0x100103af0
prev: 0x100103b70, self:0x100103af0, next:0x100103b10, data = 1
prev: 0x100103af0, self:0x100103b10, next:0x100103b30, data = 2
prev: 0x100103b10, self:0x100103b30, next:0x100103b70, data = 3
prev: 0x100103b30, self:0x100103b70, next:0x100103af0, data = 5
list: 0x100103b10
prev: 0x100103b70, self:0x100103b10, next:0x100103b30, data = 2
prev: 0x100103b10, self:0x100103b30, next:0x100103b70, data = 3
prev: 0x100103b30, self:0x100103b70, next:0x100103b10, data = 5
list: 0x100103b30
prev: 0x100103b70, self:0x100103b30, next:0x100103b70, data = 3
prev: 0x100103b30, self:0x100103b70, next:0x100103b30, data = 5
list: 0x100103b70
prev: 0x100103b70, self:0x100103b70, next:0x100103b70, data = 5
list: 0x0
这篇关于ç圆形双链表delete_node - 迭代遍历在第一轮被删除节点中删除后的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
