[問題] C語言 Bubble Sort with linked-list

看板C_and_CPP (C/C++)作者airwaves (airwaves)時間6年前 (2019/10/08 11:19)推噓3(3推 0噓 9→)

留言12則, 4人參與討論串1/1

各位大神好，最近在學習C語言。想要用linked-list寫bubble sort 這是我參考網路上的做法，最後有成功排序的程式碼 #include <stdio.h> #include <stdlib.h> struct node { int data; struct node *next; }; void printLinkedList(struct node *start); void swap(struct node *node1, struct node *node2); void bubbleSort(struct node *start); // ================================================ int main() { int arry[10]; struct node *prev, *first = NULL, *current; printf("Please type in the 01st number:"); scanf("%d", &arry[0]); printf("Please type in the 02nd number:"); scanf("%d", &arry[1]); printf("Please type in the 03rd number:"); scanf("%d", &arry[2]); printf("Please type in the 04th number:"); scanf("%d", &arry[3]); printf("Please type in the 05th number:"); scanf("%d", &arry[4]); printf("Please type in the 06th number:"); scanf("%d", &arry[5]); printf("Please type in the 07th number:"); scanf("%d", &arry[6]); printf("Please type in the 08th number:"); scanf("%d", &arry[7]); printf("Please type in the 09th number:"); scanf("%d", &arry[8]); printf("Please type in the 10th number:"); scanf("%d", &arry[9]); int i; for (i = 0; i < 10; i++) { current = (struct node*)malloc(sizeof(struct node)); current -> data = arry[i]; if (i == 0) { first = current; } else { prev -> next = current; } current -> next = NULL; prev = current; } printf("\n"); printf("List before sorting:"); printLinkedList(first); printf("\n"); bubbleSort(first); printf("List after sorting:"); printLinkedList(first); printf("\n\n"); return 0; } // ================================================ void printLinkedList(struct node *start) { struct node *tmp = start; while(tmp != NULL) { printf("%d,", tmp -> data); tmp = tmp -> next; } } // ------------------------------------------------ void swap(struct node *node1, struct node *node2) { int tmp = node2 -> data; node2 -> data = node1 -> data; node1 -> data = tmp; } // ------------------------------------------------ void bubbleSort(struct node *start) { struct node *startSort; struct node *endSort = NULL; int swapped; if (start == NULL) { return; } do { swapped = 0; startSort = start; while (startSort -> next != endSort) { if (startSort -> data >= startSort -> next -> data) { swap(startSort, startSort -> next); swapped = 1; } startSort = startSort -> next; } endSort = startSort; } while (swapped); } 以下是我的問題，我原本的做法在bubbleSort子程式沒有加入swapped這個參數(如下)，但是網路上找到的做法都有這種旗標。想請問兩種是否只差在我會多執行幾次多餘的while (startSort -> next != endSort)？還是說我的做法會有什麼bug呢？？謝謝大家~ void bubbleSort(struct node *start) { struct node *startSort; struct node *endSort = NULL; int swapped; if (start == NULL) { return; } while(1) { startSort = start; while (startSort -> next != endSort) { if (startSort -> data >= startSort -> next -> data) { swap(startSort, startSort -> next); } startSort = startSort -> next; } endSort = startSort; if (endSort == start -> next) { break; } } } -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.44.82.152 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1570504758.A.3A4.html ※ 編輯: airwaves (114.44.82.152 臺灣), 10/08/2019 11:22:21 ※ 編輯: airwaves (114.44.82.152 臺灣), 10/08/2019 11:27:33