我正在尝试为双向链表编写函数，但在实现">位置删除">功能时遇到了问题。
它按预期工作，用于删除第一个和最后一个位置的节点。
但是，对于中间位置的删除，它会在第一次按预期删除它(至少在表面上，它是这样出现的)，但是，下次它会为中间位置输入垃圾值。
我的位置删除功能：
void delete_pos(struct node **p, int pos)
{
struct node *q;
q=*p;
int i=1;
while((q->next!=NULL)&&(i<pos))
{
q=q->next;
i++;
}
if(q==NULL) //empty list or invalid position
printf("Invalid Positionn");
else //position found
{
if(q->prev==NULL) //1st position
{
if(q->next==NULL) //only 1 node
*p=NULL;
else //more than 1 node
{
q->next->prev=NULL;
*p=q->next;
}
}
else if(q->next!=NULL) //intermediate position
{
printf("Yesn"); //debugging check to make sure that it's going to the right condition
q->prev->next=q->next;
}
else //last position
q->prev->next=NULL; //
free(q);
}
}
我在输出中遇到的问题示例：
1<->2<->3<->4<->5<->NULL
是我的双重链表。
如果我调用位置删除函数并输入中间值：
Enter position
2
1<->3<->4<->5<->NULL
它似乎第一次按预期工作。 但是，下次我打电话时：
Enter the position..
2
1<->6564704<->4<->5<->NULL
在另一次尝试中，它的行为很奇怪，因为它没有产生垃圾值，只是第二次不起作用，输出：
1<->3<->4<->5<->NULL
Enter the position..
2
1<->4<->5<->NULL
Enter the position..
2
1<->4<->5<->NULL
Enter the position..
2
1<->4<->5<->NULL
我的调试尝试： 通过打印语句，我确保它进入中间条件：
else if(q->next!=NULL) //intermediate position
{
printf("Yesn"); //debugging check to make sure that it's going to the right condition
q->prev->next=q->next;
}
然而，我无法弄清楚这句话是如何做到的：
q->prev->next=q->next;
在双向链表中删除中间位置节点是错误的，因为这是唯一可能出错的突出内容。
感谢您抽出宝贵时间阅读本文！
每当从链表中删除时，总是从右边开始，向左移动。
假设这里p是您要删除的节点，然后假设您的列表为
1-2-3-4-5
现在假设您要删除节点3然后p该节点。
现在做，
p-> right{4} -> left{3 at the moment} = p -> left{2 at the moment}
p-> left{2} -> right{3 at the moment} = p-> right{4}
p->left = NULLp->right = NULL
这样，您的删除将完成，如果需要，您可以另外释放p的内存。
乍一看这似乎很棘手，所以我建议您在纸上尝试一下，按照上面的 3 个步骤操作，您的删除将起作用。
删除中间节点时，您执行
q->prev->next=q->next;
这意味着你让 q 之前的节点指向 q 之后的节点。
这很好，但由于它是一个双向链表，您还需要使 q 之后的节点指向 q 之前的节点。
像这样：
q->prev->next=q->next;
q->next->prev=q->prev;
进一步解释：
如果我们像这样绘制您的列表：
---------- ---------- ----------
| | | | | |
| next|------>| next|------>| next|
| NB | | Q | | NA |
|prev |<------|prev |<------|prev |
| | | | | |
---------- ---------- ----------
然后你做
q->prev->next=q->next;
将列表更改为
--------------
---------- / ---------- ----------
| | / | | -->| |
| next|--/ | next|------>| next|
| NB | | Q | | NA |
|prev |<------|prev |<------|prev |
| | | | | |
---------- ---------- ----------
但这只是指针的一半。您还需要
q->next->prev=q->prev;
要得到
--------------
---------- / ---------- ----------
| | / | | -->| |
| next|--/ | next|------>| next|
| NB | | Q | | NA |
|prev |<------|prev | ---|prev |
| |<- | | / | |
---------- ---------- / ----------
---------------
现在你可以删除Q来获取
--------------
---------- / ----------
| | / -->| |
| next|--/ | next|
| NB | | NA |
|prev | ---|prev |
| |<- / | |
---------- / ----------
---------------
当表达式最初*p是空指针时，该函数调用未定义的行为，当函数由于使用此空指针访问内存而处理空列表时
void delete_pos(struct node **p, int pos)
{
struct node *q;
q=*p;
int i=1;
while((q->next!=NULL)&&(i<pos))
^^^^^^^^
//...
您需要在 while 循环之前检查函数开头的列表是否为空。
在 while 循环之后
while((q->next!=NULL)&&(i<pos))
{
q=q->next;
i++;
}
如果列表最初不为空，则指针q不能等于NULL因为仅当条件q->next!=NULL为 true 时才将下一个值分配给指针。 这意味着用户可以指定一个不存在的位置(例如太大的位置)，但最后一个节点在任何情况下都会被删除。 或者，函数的用户可以将负数作为仓位的值传递，在这种情况下，第一个节点将被删除。
指定位置的参数应声明为具有无符号整数类型，例如size_t并且位置应从零开始。
该函数应报告是否成功删除了给定位置的节点。也就是说，函数应该像
int delete_pos( struct node **p, size_t pos );
如果删除的节点不是头节点或尾节点，那么您忘记更新已删除节点之后下一个节点的数据成员prev。
else if(q->next!=NULL) //intermediate position
{
printf("Yesn"); //debugging check to make sure that it's going to the right condition
q->prev->next=q->next;
}
您只更新了已删除节点之前节点旁边的数据成员。
该函数可以如下所示
int delete_pos( struct node **head, size_t pos )
{
while ( *head && pos-- )
{
head = &( *head )->next;
}
int success = *head != NULL;
if ( success )
{
struct node *current = *head;
if ( ( *head )->next != NULL )
{
( *head )->next->prev = ( *head )->prev;
}
*head = ( *head )->next;
free( current );
}
return success;
}
这是一个演示程序，显示了实际功能。
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *prev;
struct node *next;
};
size_t create( struct node **head, const int a[], size_t n )
{
while ( *head )
{
struct node *current = *head;
*head = ( *head )->next;
free( current );
}
size_t i = 0;
for ( struct node *prev = NULL;
i != n && ( *head = malloc( sizeof( **head ) ) ) != NULL;
i++ )
{
( *head )->data = a[i];
( *head )->prev = prev;
( *head )->next = NULL;
prev = *head;
head = &( *head )->next;
}
return i;
}
void display( const struct node *head )
{
const struct node *tail = NULL;
for ( ; head != NULL; head = head->next )
{
printf( "%d -> ", head->data );
tail = head;
}
puts( "null" );
for ( ; tail != NULL; tail = tail->prev )
{
printf( "%d -> ", tail->data );
}
puts( "null" );
}
int delete_pos( struct node **head, size_t pos )
{
while ( *head && pos-- )
{
head = &( *head )->next;
}
int success = *head != NULL;
if ( success )
{
struct node *current = *head;
if ( ( *head )->next != NULL )
{
( *head )->next->prev = ( *head )->prev;
}
*head = ( *head )->next;
free( current );
}
return success;
}
int main(void)
{
struct node *head = NULL;
int a[] = { 1, 2, 3, 4, 5 };
create( &head, a, sizeof( a ) / sizeof( *a ) );
display( head );
putchar( 'n' );
delete_pos( &head, 0 );
display( head );
putchar( 'n' );
delete_pos( &head, 3 );
display( head );
putchar( 'n' );
delete_pos( &head, 1 );
display( head );
putchar( 'n' );
delete_pos( &head, 1 );
display( head );
putchar( 'n' );
delete_pos( &head, 0 );
display( head );
putchar( 'n' );
return 0;
}
程序输出为
1 -> 2 -> 3 -> 4 -> 5 -> null
5 -> 4 -> 3 -> 2 -> 1 -> null
2 -> 3 -> 4 -> 5 -> null
5 -> 4 -> 3 -> 2 -> null
2 -> 3 -> 4 -> null
4 -> 3 -> 2 -> null
2 -> 4 -> null
4 -> 2 -> null
2 -> null
2 -> null
null
null