双向链表插入

Question

我编写了一个程序，在下面给出的双向链表中插入一个元素（忽略创建和显示功能 它工作得很好，直到发现要插入的索引是 5 ，它失败了。虽然我制作了另一个程序来遇到这个问题，但现在它没有显示任何内容。我使用了聊天 gpt，但得到了错误的答案。请帮助我，以及当我认为程序及其算法完美运行但当我实际编译它时的任何指导。它不起作用，即使我已经跟踪了我的程序，例如10倍 另一个程序：

     #include<stdio.h>
#include<stdlib.h>
typedef struct Node {
  struct Node *prev;
  int data;
  struct Node *next;
}new;
new *insert (new *head,int index,int num);
void display(new *head);
void create(new *head,int A[],int n);
void create(new *head,int A[],int n)
{
  head->data=A[0];
  head->next=head->prev=NULL;
  new *last=head;
  for(int i=1;i<n;i++)
  {
      new *t=(new *)malloc(sizeof(new));
      t->data=A[i];
      t->prev=last;
      t->next=NULL;
      last->next=t;
      last=t;
  }
}
void display(new *head)
{
  new * temp=NULL;
  int flag=0;
  printf("Next:");
  while(head)
  {
      printf("%d ",head->data);
      if(!head->next||flag==0){
          temp=head;
          flag=1;
      }
      head=head->next;
  }
  printf("\nPREV:");
  while(temp)
  {
      printf("%d ",temp->data);
      temp=temp->prev;
  }
  printf("\n");
}
new *insert (new *head,int index,int num)
{
  new*q=NULL,*temp=NULL;
  int flag=0;
  if(index==0)
  {
      return insert(head,0,9);
  }
  int i=0;
  while(i!=index)
  {
      if(!q->next&&flag==1)temp=q; 
      flag=1;
      q=head;
      head=head->next;
      i++;
  }
  new*t=(new*)malloc(sizeof(new));
  t->next=head;
  int y=0;
  t->data=num;
  if(!(head&&q))
  {
      temp->next=t;
      t->prev=temp;
      y=1;
  }
  if(y==0)
  {
  q->next=t;
  t->prev=q;
  head->prev=t;
  }
}
int main()
{
  new * head=(new *)malloc(sizeof(new));
  int A[5]={1,2,3,6,7};
  create(head,A,5);
  display(head);
  int i=3;
  insert(head,i,87);
  display(head);
}
  ```

Answer 1

对于初学者来说，typedef 名称

new

并不好。例如使用 typedef name 会更好

Node

typedef struct Node
{
    struct Node *prev;
    int data;
    struct Node *next;
} Node;

如果指定的索引大于列表中当前的节点数，您应该决定做什么：是追加新节点还是报告错误。

至于你的代码则无法正常运行。

例如，如果指定的索引等于 0，则此代码片段

if(index==0)
{
    return insert(head,0,9);
}

调用函数本身的无限递归调用。另外还不清楚为什么第三个参数是整数常量 9。

如果指定的索引不等于 0，该函数也不会返回任何内容。

main 中的这个声明

new * head=(new *)malloc(sizeof(new));

没有意义。例如，如果用户不会调用函数

create

，则调用函数

insert

将调用未定义的行为。

最初列表应该是空的。这是你应该写的主要内容

new (head = NULL;

我将按以下方式声明和定义函数

insert

。

int insert( Node **head, size_t index, int data )
{
    if (index != 0)
    {
        while ( head != NULL && --index != 0 )
        {
            head = &( *head )->next;
        }
    }

    int success = index == 0;

    if (success)
    {
        Node *node = ( Node * )malloc( sizeof( *node ) );
        success = node != NULL;

        if (success)
        {
            node->data = data;

            if (*head == NULL)
            {
                node->prev = NULL;
                node->next = NULL;
                *head = node;
            }
            else
            {
                node->prev = *head;
                node->next = ( *head )->next;
                ( *head )->next = node;
            }
        }
    }

    return success;
}

如果给定位置的节点已插入到列表中，则该函数返回

1

；如果指定索引超出可接受的范围，则该函数返回

0

[0, number of existent nodes]

或未为新节点分配内存。

返回类型的插入

int

您可以引入一个枚举来对可能的错误或成功进行分类。

这是一个演示程序。

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

typedef struct Node
{
    struct Node *prev;
    int data;
    struct Node *next;
} Node;

int insert( Node **head, size_t index, int data )
{
    if (index != 0)
    {
        while ( head != NULL && --index != 0 )
        {
            head = &( *head )->next;
        }
    }

    int success = index == 0;

    if (success)
    {
        Node *node = malloc( sizeof( *node ) );
        success = node != NULL;

        if (success)
        {
            node->data = data;

            if (*head == NULL)
            {
                node->prev = NULL;
                node->next = NULL;
                *head = node;
            }
            else
            {
                node->prev = *head;
                node->next = ( *head )->next;
                ( *head )->next = node;
            }
        }
    }

    return success;
}

FILE *display( const Node *head, FILE *fp )
{
    for (; head != NULL; head = head->next)
    {
        fprintf( fp, "%d -> ", head->data );
    }

    fputs( "null", fp );

    return fp;
}

void clear( Node **head )
{
    while (*head)
    {
        Node *tmp = *head;
        *head = ( *head )->next;
        free( tmp );
    }
}

int main( void )
{
    Node *head = NULL;

    int a[] = { 1, 2, 3, 6, 7 };
    const size_t N = sizeof( a ) / sizeof( *a );

    int success = 1;
    for (size_t i = 0; success && i < N; i++)
    {
        success = insert( &head, i, a[i] );
    }

    fputc( '\n', display( head, stdout ) );

    clear( &head );

    fputc( '\n', display( head, stdout ) );
}

程序输出为

1 -> 2 -> 3 -> 6 -> 7 -> null
null

尝试自己编写函数

create

。应该这样声明

size_t create( Node **head, const int a[], size_t n );

该函数返回数组中实际添加元素的数量到列表中。