-2

I have a slight problem with sorting in linked lists. i have a doubly linked list that needs sorting after intital input, the swap function is what i intend to use, but the problem herein lies that it screws up any header pointers there may be. I cannot sort the list by jusr replacing data as there are too many variables and they can change in the course of development (new variables can be added or deleted)

task *taskHeader;

struct task{
   task *pprev;
   //large number of variables
   int number;
   task *pnext;
   task(){
     pprev = NULL;
     pnext = NULL;
   }
}
//swap function
void swap(task *task2, task *task3)
   task* task1 = task2->prev; // alias for readability
   task* task4 = task3->next; // alias for readability
   if(task1!=NULL) task1->next = task3;
   task3->prev = task1;
   task3->next = task2;
   task2->prev = task3;
   task2->next = task4;
   if(task4!=NULL) task4->prev = task2;
}

void sort(task *taskHeader){
   task *temp = taskHeader;
   while(temp != NULL){
      if(temp->number < temp->pnext->number) swap(temp, temp->pnext);

   }
}

how should i append the swap function to keep my headers intact and not crash when swapping start or end task nodes? currently i do this by adding NULL checks into the swap function to keep the function from going out of bounds and ending up with pointer faults, but is there a better way to solve this?

should i just traverse the linked list back til i reach a point where pprev == NULL and change the header to point towards that node?

4

1 回答 1

1

所以你有一个双链表，很难排序。如果你想要一个有序列表。也许你只需要编写这些函数：

一个init函数，只创建头节点并将地址存储到全局变量中。

一个insert 函数，它将节点插入到正确的位置。

现在，它是有序的，但您仍然需要其他功能才能使列表有用。

一个delete函数。

一个find函数

一个size函数。

一个empty函数。

“获取”功能

...

祝你好运。

命令后：

插入 ：

   node1 
    ||
   node2
    ||       
   node3

如果您需要在列表中插入一个新节点，就在 node1 后面。

 1. create a new node node4             
 2. find the node1                      node1
 2. node1->next->pre = node4             |
 3. node4->next = node1->next    -->     |node4
                                         | ||
                                        node2
                                         ||
                                        node3

 4.node4->pre = node1         
 5.node1->next = node4           -->    node1
                                         ||
                                        node4
                                         ||
                                        node2
                                         ||
                                        node3
于 2013-08-13T10:22:16.687 回答