链表：如何对双向链表进行排序？

Question

这是我的双向链表的代码。它工作正常。我需要帮助对这个链表的数据元素进行排序。

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

struct Node{
int data;
struct Node* next;
struct Node* prev;
};
struct Node* head;//global variable

int GetNewNode(int x)
{
struct Node* newNode=(struct Node*)malloc(sizeof(struct Node));
newNode->data=x;
newNode->prev=NULL;
newNode->next=NULL;
return newNode;
}

int InsertAtHead(int x)
{
struct Node* newNode =GetNewNode(x);
if(head==NULL)//list empty
{
    head=newNode;
    return;
}
head->prev=newNode;
newNode->next=head;
head=newNode;
}

void print()
{
struct Node* temp=head;//start printing from head
printf("Forward: ");
while(temp!=NULL)
{
    printf("%d ",temp->data);
    temp=temp->next;
}
    printf("\n");
}

   int main()
   {
   head=NULL;// initially taking it as null
   InsertAtHead(2);print();
   InsertAtHead(5);print();
   InsertAtHead(3);print();
   InsertAtHead(9);print();

   return 0;
   }

我想在这里对数据元素进行排序。我试过这个：

void sort()
{
struct Node* temp=head;
int numTemp;
while(temp!=NULL)
{
    if(temp->prev > temp->next)
    {
        numTemp=temp->next;
        temp->next= temp->prev;
        temp->prev=numTemp;
    }
}
}

但是这里比较的是地址，而不是链表的数据，我该如何比较数据并相应地对它们进行排序？

Answer 1

head、next 和 prec 在你的 Node 结构中是指针，因此，它们将指向相应的节点，与 temp(在sort()函数中)是指向你当前访问的节点的指针。

要访问 temp 指向的节点的 data，您将执行 temp->data。同样，如果你想访问下一个节点（地址为temp->next）的数据，你会做temp->next->data.

看来，遍历链表也有问题。要在链表中向前迭代，你必须让 temp 指向下一个节点。

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

这是循环访问列表的方法。

链表：如何对双向链表进行排序？

Linked List: How to Sort Doubly Linked List?

c

linked-list

data-structures

doubly-linked-list