反转双向链表 returns 无

Question

我正在尝试反转双向链表中的元素，但我似乎无法反转列表中的元素。它一直显示一个空白列表。输入列表中的节点并打印出来后，此函数应该反转列表中的节点，但在打印时显示空白。（没有分段错误）

这是函数：

void reverse(List it) {
    Node *temp;
    Node *corr;
    temp = malloc(sizeof(Node));
    corr = malloc(sizeof(Node));

    corr = it->curr;

    while (corr != NULL) {
        temp = corr->prev;
        corr->prev = corr->next;
        corr->next = temp;  
        corr = corr->prev;
    }
}

Answer 1

考虑到这一点后，我建议以下基于旧功能的新功能可能会起作用，但这有点猜测...-关键更改是循环中的新行，请参见下面的代码片段

  while(corr!=NULL)
   {

     temp=corr->prev;
     corr->prev=corr->next;
     corr->next=temp;  
     it->curr=corr;  //this should make the last member the new first member
     corr=corr->prev;

    }

这有点不雅，因为 it->corr 将在循环的每个循环中不断更改，但是当它完成时 it->corr 应该有列表的第一个成员 - 这可能会使您的打印声明有效，但正如我上面所说，这有点猜测。

我删除了 malloc 因为不需要它

工作版本 - 下面测试的完整程序

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

struct Node{
  struct Node * prev;
  struct Node * next;
  int ndata;
};

struct List {
  struct Node node[20];
  struct Node * curr;
};


void reverse(struct List *);
void printlist(struct List *);

int main()
{
  struct List it;

  int n;

  for (n=0;n<20;n++)  //set up a simple double linked list
    {
      it.node[n].ndata=n;
      if (n>1) 
    {
      it.node[n].prev=&(it.node[n-1]);
    }
      else
    {
      it.node[n].prev=NULL;
    }
      if (n<19) 
    {
      it.node[n].next=&(it.node[n+1]);
    }
      else
    {
      it.node[n].next=NULL;
    }
    }
  it.curr=&(it.node[0]);

  printlist(&it);
  reverse(&it);
  printlist(&it);
}

void printlist(struct List * it)
{

  struct Node *corr;

  corr = it->curr;

  while(corr!=NULL)
    {
      printf("%d\n",corr->ndata);
      corr=corr->next;
    }
  return;
}
void reverse(struct List * it)
{

  struct Node *temp;
  struct Node *corr;

  corr = it->curr;

  while(corr!=NULL)
    {
      temp=corr->prev;
      corr->prev=corr->next;
      corr->next=temp;  
      it->curr=corr;
      corr=corr->prev;
    }
  return;
}

输出如下 - 注意我已经更改了节点和列表的格式，因为它们现在是示例代码开头定义的结构

(此版本没有内存泄漏。)

Answer 2

您的代码中有 2 个问题：

不需要分配新的节点，事实上，当你将新值存储到corr和temp.
[时，这些分配的节点就会丢失=29=]
您必须更新 it->curr 以指向反转列表的第一个节点，即原始列表的最后一个节点

这是更正后的版本：

void reverse(List it) {
    Node *last = NULL;
    Node *corr = it->curr;

    while (corr != NULL) {
        Node *temp = corr->prev;
        corr->prev = corr->next;
        corr->next = temp; 
        last = corr; 
        corr = corr->prev;
    }
    it->curr = last;
}

另请注意，将指针隐藏在 typedef 后面被认为是糟糕的风格和容易出错的做法。 List 是指针的 typedef，但困惑的 reader 一开始可能会认为您按值将结构传递给 reverse 函数...

Answer 3

我认为你没有更新头指针，我不知道它在你的代码中的什么位置所以我将在下面提供示例 snipper，算法的其余部分看起来没问题：

node* head = 0;

void rotate(node** h) {
    node *curr = *h, *tmp = 0;

    while (curr) {
        node* tmp = curr->prev;
        curr->prev = curr->next;
        curr->next = tmp;
        if (!tmp) {
            break;
        }
        curr = tmp;
    }
    //Update head!
    *h = curr;
}

void print(node* head) {
    while (head) {
        printf("%d", head->v);
        head = head->next;
    }
}

反转双向链表 returns 无

Reversing a doubly linked list returns nothing

c

doubly-linked-list