在C中对链表进行排序

我试图通过找到最大值,从其位置删除它,然后将其插入列表顶部来对链表进行排序。

我遇到的困难是实际删除和插入顶部。 问题似乎是在sortList函数中包含的while循环中的if条件,但我不确定如何修复它。

任何帮助,将不胜感激。

#include  #include  typedef struct node{ int num; struct node *next; } Node, *NodePtr; void printList(NodePtr np); NodePtr makeList(void); NodePtr makeNode(int n); NodePtr sortList(NodePtr list); int main(void) { NodePtr list; printf("Enter numbers for the list (0 to end)\n"); list = makeList(); printList(list); list = sortList(list); printList(list); return 0; } NodePtr makeList(void) { NodePtr makeNode(int), np, top, last; int n; top = NULL; if(scanf("%d", &n) != 1)n = 0; while(n != 0) { np = makeNode(n); if(top == NULL)top = np; else last->next = np; last = np; if(scanf("%d", &n)!=1)n=0; } return top; } void printList(NodePtr np) { while(np != NULL) { printf("%d\n", np->num); np = np->next; } } NodePtr makeNode(int n) { NodePtr np = (NodePtr)malloc(sizeof(Node)); np->num = n; np->next = NULL; return np; } NodePtr sortList(NodePtr list) { NodePtr top = list; NodePtr curr = NULL; NodePtr largest; NodePtr prev; prev = NULL; curr = top; largest = top; while(curr != NULL) { prev = curr; if(curr->num > largest->num) { largest = curr; prev->next = curr->next; largest->next = top; } curr = curr->next; } if(prev == NULL) { largest->next = top; return largest; } return largest; } 

sortList函数中存在问题。

此函数仅在列表的开头放置一些大节点。 它不是所有的清单。 你可以使用排序算法来对文件进行排序:quicksort / bubblesort / …我在这个答案的最后给出了一个代码。

这是一个代码列表的代码:

//它用第一个替换最大的节点然后用子列表执行相同的操作(list-first元素)

 NodePtr sortList(NodePtr list) { // if(list == null || list->next == null) return list; // the list is sorted. //replace largest node with the first : //1- find largest node : NodePtr curr, largest,largestPrev; curr = list; largest = list; prev = list; largestPrev = list; while(curr != NULL) { if(curr->num > largest->num) { largestPrev = prev; largest = curr; } prev = curr; curr = curr->next; } //largest node is in largest. //2- switching firt node and largest node : NodePtr tmp; if(largest != list) { largestPrev->next = list; tmp = list->next; list->next = largest->next; largest->next = tmp; } // now largest is the first node of the list. // calling the function again with the sub list : // list minus its first node : largest->next = sortList(largest->next); return largest; } 

这是我尝试使用QuickSort算法对单个链接列表进行排序。 如果你知道n那么运行时间将是O(n log n)。 检查这是否有帮助。

 #include "malloc.h" typedef struct node { struct node *next; int val; } node; bool insert_node(struct node **head, int val) { struct node *elem; elem = (struct node *)malloc(sizeof(struct node)); if (!elem) return false; elem->val = val; elem->next = *head; *head = elem; return true; } int get_lval(struct node *head, int l) { while(head && l) { head = head->next; l--; } if (head != NULL) return head->val; else return -1; } void swap(struct node *head, int i, int j) { struct node *tmp = head; int tmpival; int tmpjval; int ti = i; while(tmp && i) { i--; tmp = tmp->next; } tmpival = tmp->val; tmp = head; while(tmp && j) { j--; tmp = tmp->next; } tmpjval = tmp->val; tmp->val = tmpival; tmp = head; i = ti; while(tmp && i) { i--; tmp = tmp->next; } tmp->val = tmpjval; } struct node *Quick_Sort_List(struct node *head, int l, int r) { int i, j; int jval; int pivot; i = l + 1; if (l + 1 < r) { pivot = get_lval(head, l); printf("Pivot = %d\n", pivot); for (j = l + 1; j <= r; j++) { jval = get_lval(head, j); if (jval < pivot && jval != -1) { swap(head, i, j); i++; } } swap(head, i - 1, l); Quick_Sort_List(head, l, i); Quick_Sort_List(head, i, r); } return head; } struct node *Sort_linkedlist(struct node *head) { struct node *tmp = head; // Using Quick sort. int n = 0; while (tmp) { n++; tmp = tmp->next; } printf("n = %d\n", n); head = Quick_Sort_List(head, 0, n); return head; } void print_list(struct node *head) { while(head) { printf("%d->", head->val); head = head->next; } printf("\n"); } int _tmain(int argc, _TCHAR* argv[]) { struct node *head = NULL; struct node *shead = NULL; insert_node(&head, 10); insert_node(&head, 12); insert_node(&head, 9); insert_node(&head, 11); insert_node(&head, 7); insert_node(&head, 1); insert_node(&head, 3); insert_node(&head, 8); insert_node(&head, 5); insert_node(&head, 2); insert_node(&head, 4); insert_node(&head, 6); print_list(head); shead = Sort_linkedlist(head); print_list(shead); return 0; } 

这真的可以帮到你。 这是一个非常好的post。

通过写入largest->next你覆盖了curr->next 。 所以你总是从头顶重新开始。

确保:

  1. 清单保持一致
  2. 列表迭代器保持一致

但总体而言,您的代码似乎被严重破坏,我相信您的排序逻辑中可能还有其他一些错误。

以下是排序逻辑中存在的一些问题:

  1. 您正在将循环指针设置为循环开头的curr,这是不正确的。 通过执行此操作,您将使当前指针和前一个节点指针相同,这使得无法删除该节点。
  2. 您应该将最大的指针也分配给top,从而有助于设置最大 – >真实顶级节点旁边的可能性。

代码可以修改如下(只需一个指针,你需要自己检查其他问题):

 while(curr != NULL) { if(curr->num > largest->num) { largest = curr; prev->next = curr->next; largest->next = top; top = largest; } prev = curr; curr = curr->next; } 
 // Program to sort a single linked list in ascending order // (without exchanging data in the nodes) /************************************************************************** There are two methods of sorting presented here(At a time,we can use any of these two functions to sort our single linked list.) - 1. Function 'void Sort()' - This function uses selection sort method(I think). In this function,a node whose data is the smallest in the list is made as 'head' node(ie starting node of the list) by scanning the whole list once.Then from the remaining list,again a node with the smallest data is found out whose address is kept in the 'next' field of previous node(head node).This process continues to sort the whole list. 2. Function 'void Sort_method2()' - This function uses insertion sort method(I think). In this function,starting from second node in the list, all previous node data(starting from 'head' node) are compared with current reference node (which is initially second node in the list).If 'data' field of current reference node is smaller than that of any of its previous nodes,then suitable changes in the 'next' field of corresponding nodes are made.If data in the current reference node is smaller than that in the 'head' node, then the current reference node is made as 'head' node. *********************************************************************/ #include #include #include #include struct node { int data; struct node *next; }; struct node *head,*head1; void Create_node(int data); void display(); void Sort(); void Sort_method2(); void main() { int choice,d; clrscr(); while(1) { printf("\n 1.Create new node"); printf("\n 2.Sort in ascending order"); printf("\n 3.Exit"); printf("\nEnter your choice : "); scanf("%d",&choice); switch(choice) { case 1: printf("\nEnter data :"); scanf("%d",&d); Create_node(d); break; case 2: Sort(); // At a time,we can use any of these two //Sort_method2(); // functions to sort our single linked list. break; case 3: exit(0); default:exit(0); } } // end of while(1) } // end of main() //-------------------------------------------- void Create_node(int d) { struct node *newnode,*temp; newnode = (struct node *)malloc(sizeof(struct node)); newnode -> data = d; newnode -> next = NULL; if(head == NULL) head = newnode; else { temp = head; while(temp -> next != NULL) temp = temp -> next; temp -> next = newnode; } // end of 'else' } // end of 'Create_node(int d)' //--------------------------------------------- void display() // Print linked list contents { struct node *temp; printf("\nList contents are :\n"); temp = head; while(temp != NULL) { printf(" Data = %d Address = %u\n",temp->data,temp); temp = temp->next; } printf("\n"); } //-------------------------------------------- void Sort() { struct node *t,*t1,*t2,*t3; t1 = head; head1 = head; if(head == NULL) printf("\nThe linked list is empty!"); else { while( (t2 = t1 -> next) != NULL) { while(t2 != NULL) { t3 = t2 -> next; if( t1 -> data > t2 -> data) { t2 -> next = t1; for(t = t1; t -> next != t2;t = t -> next); t -> next = t3; t1 = t2; // t1 = Node with smaller data t2 = t3; // t2 = Node to be compared with t1 } // end of 'if' else { // t1 = t1; // That is,no change in t1. t2 = t3; } } // end of ' while(t2 != NULL)' if(head == head1) // We want this action only for first pass of { // outer while() loop.Only initially, head = head1. head = t1; head1 = t1 -> next; } // end of 'if(head == head1)' else { for(t = head;t -> next != head1; t = t -> next); t -> next = t1; head1 = t1 -> next; } // end of 'else' t1 = t1 -> next; } // end of 'while( (t2 = t1 -> next) != NULL)' display(); // Display the list. } // end of 'else' of 'if(head == NULL)' } // end of 'Sort()' //-------------------------------------------- void Sort_method2() { struct node *t,*t1,*t2,*tt; if(head == NULL) printf("\nThe linked list is empty!"); else { t1 = head -> next; while(t1 != NULL) // This is i-loop(outer loop). { t2 = t1 -> next; for(t = head; t != t1; t = t -> next) // This is j-loop(inner loop). { if(t1->data < t->data) { t1 -> next = t; for(tt=head; tt->next != t1; tt=tt->next); //end of for loop in 'if' tt -> next = t2; if(t == head) head = t1; // There is only one statement in this 'if'. else // ie,'if(t != head)' { for(tt=head; tt->next != t; tt=tt->next); tt -> next = t1; } break; } // end of 'if' } // end of outer 'for' loop t1 = t2; } // end of 'while' display(); // Display the list. } // end of 'else' of 'if(head == NULL)' } // end of 'Sort_method2()'