在双 link 列表中插入和删除元素

Question

#include<stdio.h>
#include<stdlib.h>

typedef struct dlist
{
    int data;
        struct dlist *next, *prev;
}dlist;

dlist* insert_begin(dlist *h,int d)
{
    dlist *temp = (dlist*)malloc(sizeof(dlist));
    temp->data = d;
    temp->next = temp->prev= NULL;
    if(h==NULL)
    {
        h=temp;
      //  t=temp;
    }
    else
    {
        temp->next = h;
        h->prev = temp;
        h = temp;
    }
    return h;
}
dlist* delete_begin(dlist *h)
{
    dlist *r = h;
    if(r==NULL)
    {
        printf("empty list");
        return 0;
    }
    else
    {
        dlist *ptr = r;
        //ptr = r;
        r=r->next;
        r->prev = NULL;
        free(ptr);
    }
    return r;
}
dlist* delete_end(dlist *h)
{
    dlist *r = h;
    if(r==NULL)
    {
        printf("empty list");
        return 0;
    }
    else
    {
        while(r->next)
            r=r->next;

        dlist *p = r;
        (r->prev)->next= NULL;
        free(p);
        return r;
    }

    //return r;
}
void display(dlist *h)
{
    dlist *r = h;
  //  printf("%d",r->data);

    //printf("ajay");
    while(r)
    {
        printf("%d ---- >",r->data);

        r=r->next;
    }
}
void main()
{
    dlist *d=NULL;

    d = insert_begin(d,2);
   d=  insert_begin(d,3);
   d= insert_begin(d,4);
  d=  insert_begin(d,5);
    display(d);
    d = delete_begin(d);
    printf("After deletion1");
    display(d);
    d= delete_end(d);
    printf("After deletion2");
     display(d);                              // infinite elements are displaying on screen

}

以上是我尝试编写的用于在双 link 列表中插入和删除元素的代码。我从头开始插入部分和删除一个节点，两者都工作得很好。我在 delete_end() 函数中遇到问题。当我编译运行代码时，它不断地打印在屏幕上。需要帮助。

Answer 1

在 delete_end() 中，代码不处理 1 节点列表的情况，其中 r != NULL，但 r->prev == NULL 和 r->next == NULL。当代码尝试 (r->prev)->next = NULL.

时会出现问题

delete_begin() 也不处理 1 节点列表。 r=r->next 可以设置 r == NULL，然后设置 r->prev == NULL。

回到delete_end()，代码应该是returnh，而不是r.

Answer 2

函数至少有两个严重问题。

首先是return由于循环

导致的指针r可能不等于头节点的地址

while(r->next)
    r=r->next;

但是你需要return指向列表头节点的指针。

同样如果指针r指向头节点则r->prev等于NULL。因此这个声明

(r->prev)->next= NULL;

可能会导致程序出现未定义的行为。

我可以建议以下功能实现

dlist* delete_end( dlist *h )
{
    if( h == NULL )
    {
        printf("empty list");
    }
    else
    {
        dlist **r = &h;

        while ( ( *r )->next ) r = &( *r )->next;

        dlist *p = *r;

        if ( ( *r )->prev )
        {        
            ( *r )->prev->next = NULL;
        }

        *r = ( *r )->prev;

        free( p );
    }

    return h;
}

在双 link 列表中插入和删除元素

Inserting and removing element in a double link list

c

data-structures

doubly-linked-list