1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 |
/*--------------------------------------------------- -Thuat Toan: Bubble Sort (Sap Xep Noi Bot) -Kieu: Pointer (Dung con tro). ----------------------------------------------------*/ #include <stdio.h> #include <conio.h> #include <stdlib.h> #include <dos.h> struct Node { int Value; Node *Next; }; typedef Node *List; typedef Node *Position; // Tao DS Rong void MakeNullList(List L) { L->Next=NULL; } //Nhap DS void InsertList(List L) { Node *newnode=new Node; Position P; L->Next=newnode; P=newnode; int Sophantu=2; printf("Nhap phan tu thu 1:"); scanf("%d",&newnode->Value); // cac phan tu tiep theo while(1) { Node *newnode=new Node; newnode->Next=NULL; printf("Phan tu thu %d: ",Sophantu); Sophantu+=1; scanf("%d",&newnode->Value); if(newnode->Value==0) { free(newnode); break; } P->Next=newnode; P=newnode; } } //In DS void ShowList(List L) { Position P=L->Next; while(P!=NULL) { printf("|%d|",P->Value); P=P->Next; } } // Vi tri con tro cua phan tu cuoi DS Position LastList(List L) { Position P=L->Next; while(P->Next!=NULL) { P=P->Next; } return P; } // Vitri con tro truoc vi tri P0 trong DS L Position TruocP(List L,Position P0) { Position P1=L; while(P1->Next!=P0&&P1!=NULL) { P1=P1->Next; } return P1; } //Doi cho 2 phan tu co vi dia chi con tro la P1,P2 trong DS L void Swap(List L,Position P1,Position P2) { Node *newnode1=new Node; Node *newnode2=new Node; newnode1->Value=P1->Value; newnode2->Value=P2->Value; newnode1->Next=P2->Next; TruocP(L,P2)->Next=newnode1; newnode2->Next=P1->Next; TruocP(L,P1)->Next=newnode2; free(P1); free(P2); } // So Phan tu trong DS int LengthList(List L) { int len=0; Position P=L; while(P->Next!=NULL) { len+=1; P=P->Next; } return len; } //Lay dia chi con tro cua phan tu co thu tu "vitri" trong DS Position ConverntXToP(List L,int vitri) { Position P=L; for(int index=1;index<=vitri;index++) { P=P->Next; } return P; } // Sap xep noi bot void BubbleSort(List L) { for(int index1=1;index1<LengthList(L);index1++) { for(int index2=LengthList(L);index2>index1;index2--) { Position P1=ConverntXToP(L,index2-1); Position P2=ConverntXToP(L,index2); if(P1->Value>P2->Value) { Swap(L,P1,P2); } } } } void main() { clrscr(); List L1; MakeNullList(L1); InsertList(L1); ShowList(L1); BubbleSort(L1); printf("\n"); ShowList(L1); getch(); } |
nosomovo
Xem thêm Code cài đặt thuật toán sắp xếp nổi bọt dùng con trỏ – Code Bubble Sort use pointer