在C语言中反转双向链表的元素

Question

这是我的思路-在列表的开头和结尾各保留一个指针。将头指针向前移动，将尾指针向后移动，直到它们指向相同的位置。然后交换指针所指位置的值，并继续向前移动。当调用该函数时，会抛出分段错误。为什么会这样呢？ 这是我用于列表节点的结构体：

struct dll
{
 int number;
 struct dll *next;
 struct dll *prev;
};

这是我反转列表和主函数的功能。

    int count=0;
void reverse(struct dll **root)
{
 int temp;
 struct dll *tail=NULL;
 struct dll *temproot=NULL;
 temproot =(*root);
 for(;(temproot)->next !=NULL;(temproot)=(temproot)->next); //traversing to the end
 tail= temproot;
 while(((*root)->next != tail->prev) || ((*root)->next != tail))//one for even no. of nodes and one for odd no.of nodes
 {
  temp=(*root)->number; //swapping the numbers
  (*root)->number=tail->number;
  tail->number=temp;
  (*root)=(*root)->next;
  tail=tail->prev;
 } //even after they are same, values need to be changed one last time
   temp=(*root)->number;
  (*root)->number=tail->number;
  tail->number=temp;
  (*root)=(*root)->next;
  tail=tail->prev;
}
void insert(struct dll **root,int num)
{
 struct dll *temp;
 if(count==0)
 {
  if((*root)==NULL)  
  {
  (*root)=(struct dll *)malloc(sizeof(struct dll));
  (*root)->next=NULL;
  (*root)->prev=NULL;
  (*root)->number=num;
  count++;
  printf("\n%d",count);
  }
 }
 else if((*root)->next==NULL) 
  {
  temp=(struct dll *)malloc(sizeof(struct dll));
  temp->next=NULL;
  temp->prev=(*root);
  temp->number=num;
  (*root)->next=temp;
  count++;
  printf("\n%d",count);
  }
 else
 {
  insert(&(*root)->next,num);
 }

}
main()
{
 struct dll *head=NULL;
 int i,n,num;
 while(1)
 {
  printf("Enter 1 for insert, 3 for reverse, 0 for exit\n");
  scanf("%d",&n);
  switch(n)
  {
   case 1:printf("Enter number\n");
      scanf("%d",&num);
      insert(&head,num);
      break;
   case 3:reverse(&head);break;
   case 0:exit(0);
   default:printf("Enter correct value\n");
  }
 }

}

- srk

---

哪一行代码出现了段错误？ - interjay

我是一个初学者，如何检查段错误发生在哪一行？ - srk

最好的方法是在调试器中运行它。我想，如果你现在不想学习如何使用调试器，甚至可以在每一行后面放一个“printf”语句，看看哪一个是最后一个被打印出来的。 - interjay

您需要提供一个小的完整的可复制程序，这样别人就可以在不进行任何修改的情况下编译和运行。问题可能不在上述代码中，而是其他地方。 - Sagar Masuti

我在调试器中运行它，它在 while 语句中报告了分段错误。 - srk

我已经单独为你的segfault问题给出了可能的答案，但还有另一件事要指出。在reverse函数中更改*root几乎肯定是错误的。按照这种写法，实际上会更改在main()中保留的head指针的值。在reverse函数完成后，head实际上将指向列表中的最后一个元素。我认为你想做的是在循环开始时将temproot = *root赋值，并使用temproot遍历列表。 - Tim Pierce

Answer 1

我写了这个函数，使用递归方法来反转双向链表。

void Node::Swap(){
 if(m_pNext != NULL){
   m_pNext->Swap();
   m_pNext->m_pNext = this;
 }
}

void List::Reverse(){
  if(m_pHead!=NULL){
    m_pHead->Swap();
    m_pHead->SetNext(NULL);
  }
  Node* pTemp=m_pHead;
  m_pHead = m_pTail;
  m_pTail = pTemp;
}

- Sergey

Answer 2

通过颠倒列表的顺序，您是指交换所有项的下一个和上一个指针吗？这段未经检查的代码可能会起到作用：

void reverse(struct dll **root)
{
  struct dll *buff=NULL;
  struct dll *start=*root;

  unsigned char stop=0;
  while(stop==0){
   if(*root==NULL){
    stop=1;
    break;
   }
   buff=(*root)->prev;
   (*root)->prev=(*root)->next;
   (*root)->next=buff;

   *root=(*root)->prev;//the next to treat is the previous one now
   if(*root==start){
    //this test handle the case of "looping" double linked list
    stop=1;
    break;
  }
 }
}

该代码假设*root是列表在开始时的起点。最后，*root仍然是列表的起点。

再见，

弗朗西斯

- francis

---

谢谢您的回答。虽然这是更好的逻辑，但我正在使用问题中解释的另一种逻辑。在我的逻辑中，列表的链接将是相同的，根也将是相同的。它只是交换数字，就像对于一个数组一样。 - srk

正如我在我的答案中指出的那样，*root在您的程序运行后将不再相同。 - Tim Pierce

Answer 3

很难确定这段代码在哪里出现了分段错误。但是如果你的调试器显示它在while语句所在的行上引发了错误：

 while(((*root)->next != tail->prev) || ((*root)->next != tail))//one for even no. of nodes and one for odd no.of nodes

那么几乎可以确定，在这一点上，root、*root或tail中的一个是NULL，或者是未初始化的指针。

一种可能性：如果您使用仅包含一个元素的链表调用此函数，则tail和*root将在此循环开始时指向同一元素。由于程序认为需要继续反转元素并继续向后移动tail和*root，因此以这种方式编写条件，程序将继续向后移动。由于程序从不检查*root == NULL或tail == NULL，最终它将走到列表的末尾，并尝试解引用空指针，这将导致分段错误。

在移动指针和解引用指针之间检查指针是否为NULL是一个非常好的主意。通常还有助于思考如果使用0个元素的列表、1个元素的列表等调用函数会发生什么。

- Tim Pierce

Answer 4

首先，我非常坚持要求您使用哨兵节点来管理您的链表，这将大大简化代码。

一旦您已经转换为使用哨兵节点，创建reverse就变得相当容易：

struct dll* prev = sentry;

struct dll* curr = sentry->next;
if(curr==sentry) return; // empty list dont need reversing

struct dll* next = curr->next;
if(next==sentry) return; // list size 1 is already its reverse

while( curr != sentry )
{
    // reverse links
    prev->prev = curr;
    curr->next = prev;
    // move to next
    prev = curr;
    curr = next;
    next = next->next;
}

// close loop (first item is the one we found last)
sentry->next = prev;
prev->prev = sentry;

如果你需要一个哨兵节点运作的例子，可以看一下这里

- sp2danny

Answer 5

结构体 node {

         int data;


         struct node *prev;


         struct node *next;


       };

使用typedef来缩短代码：

list temp=NULL,head=NULL,last=NULL,r=NULL,p=NULL;

/在这里使用Create函数，所以last和head现在分别指向最后一个节点和第一个节点/

我的反转函数（可能是最短的）=>

{

last = head;

r = head;

while (r != NULL)

{

  temp=r->next;


  r->next=r->prev;


  r->prev=temp;  //swapping next and previous using temp


  r=r->prev; //since now values swapped so reverse traversing

}

p=last;

当(p->prev!=NULL)时

{

  p=p->prev;

}

head=p;

}

- UTKARSH