Dạ mấy anh cho em hỏi , làm thế nào để khử đệ quy trên 1 cái Danh sách liên kết cho thuật toán quick sort . Theo như tài liệu em coi thì nó trình bày trên mảng như sau : 1. l:=1 ; r:=n; 2.Chọn phần tử giữa x:=a[(l+r)div 2]; 3.Phân hoạch (l,r) thành (l1,r1) và (l2,r2) bằng cách : y thuộc (l1,r1) nếu y<=x , y thuộc (l2,r2) nếu ngược lại . 4. Nếu phân hoạch (l2,r2 ) có nhiều hơn 1 phần tử thì thực hiện : -Cất (l2,r2 ) vào stack Nếu (l1,r1) có nhiều hơn 1 phần tử thì l=l1,r=r1 Goto 2 . Ngược lại : -Lấy (l,r) ra khỏi stack nếu stack khác rỗng và Goto 2 . Nếu không dừng . Em có 1 vài thắc mắc sau : 1. Mình dùng Danh sách liên kết thì sẽ không chọn được phần tử x chính giữa , do đó phải chọn ở đầu xâu . Vậy ý nghĩa của việc chỉ xét tới (l2,r2) có 1 phần tử và (l1,r1) có 1 phần tử để làm gì ? 2. Trong thao tác trên , khi mình dùng 1 stack để lưu lại thì làm sao mà mình nối lại tất cả các chuổi con khi không được dùng đệ quy ? Có ai giúp dùm em ạ , cái này là 1 bài tập thi mà làm mấy hôm rồi không ra nên mới mạo muội lên đây hỏi ::)
bạn cho mình hỏi bạn đang theo học ở trường nào thế ^^? còn cái vấn đề bạn hỏi thì lâu lắm rùi ko học nên chả nhớ gì nhìu chỉ có thể giúp bạn = đoạn code này thui ^^ Mã: // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% #include<iostream.h> #include<alloc.h> #include<conio.h> #include<iomanip.h> #include<stdio.h> #include<stdlib.h> // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% #define thoat 0 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% typedef int elem; typedef struct node { elem data; struct node *next; } nt; typedef nt *pt; // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% pt create(); int alloc(pt &tam); int empty(pt list); void nhapds(pt & ,pt &); int insertlast(pt &list, pt &last, elem item); int xuat(pt list); int hoanvi(elem &a , elem &b); int sap_xep(pt list); int Chon(pt list); void Quicksort(pt &list,pt &last); // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% void main() { pt list, last,pred; elem item; clrscr(); cout<<"\n nhap ds thu 1:\n"; nhapds(list,last); cout<<"\n danh sach ban dau la : "; xuat(list); // cout<<"\n"; // cout<<"\n danh sach sap xep doi cho la : "; // sap_xep( list); // xuat(list); // cout<<"\n"; // cout<<"\n danh sach sap xep chon la : "; // Chon( list); // xuat(list); cout<<"\n"; cout<<"\n danh sach sap xep Quicksort la : "; Quicksort(list,last); xuat(list); getch(); } // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% // ------------------------------------------------------------------------ pt create() { pt list; if(!alloc(list)) return((pt)NULL); list->next=(pt)NULL; return(list); } // ------------------------------------------------------------------------ int alloc(pt &tam) { if((tam= new nt) == NULL) return 0; return 1; } // ------------------------------------------------------------------------ int empty(pt list) { return(list==NULL); } // ------------------------------------------------------------------------ void nhapds(pt &list,pt &last) { elem item; list=last=create(); cout<<" nhap vao cac gia tri nguyen duong an 0 de thoat: "; do { cin>>item; if(item!=thoat) // insertlast(list,item,last); insertlast(list,last,item); } while(item!=thoat); } // ------------------------------------------------------------------------ int insertlast(pt &list, pt &last, elem item) { pt temp; if(! alloc(temp)) return 0; temp -> data = item; temp -> next = NULL; if(!empty(list)) last ->next = temp; else list = temp; last = temp; return 1 ; } // ------------------------------------------------------------------------ int xuat(pt list) { pt tam; // tam = list->next; tam = list; while(tam!=NULL) { cout<<tam->data<<setw(5); tam=tam->next; } return 1; } // ------------------------------------------------------------------------ int hoanvi(elem &a,elem &b) { elem t; t = a; a = b; b = t; return 1 ; } // ------------------------------------------------------------------------ int sap_xep(pt list) { pt tam,temp; tam = list->next; while(tam!=NULL) { temp =tam->next; while(temp!=NULL) { if(temp->data < tam->data) hoanvi(temp->data,tam->data); temp = temp->next; } tam = tam->next; } return 1; } // ------------------------------------------------------------------------ int Chon(pt list) { pt tam,temp1,temp2; tam = list->next; while(tam!=NULL) { temp1 = tam ; temp2 = tam->next; while(temp2!=NULL) { if(temp1->data > temp2->data) temp1 = temp2; temp2 = temp2->next; } hoanvi(tam->data,temp1->data); tam = tam->next; } return 1; } // ------------------------------------------------------------------------ void Quicksort(pt &list,pt &last) { pt temp,x,list1,list2,last1,last2; if(list==NULL) return ; list1 = list2 = last1 = last2 = NULL; x = last; list = list->next; while(list->next!=NULL) { temp = list; list = list->next; temp->next= NULL; // cout<<"Ngoai if : "<<temp->data<<" x = "<<x->data<<"\n";getch(); if(temp->data <= x->data) { insertlast(list1,last1,temp->data); cout<<"if : "<<temp->data<<" x = "<<x->data<<"\n";getch(); } else { insertlast(list2,last2,temp->data); cout<<"else : "<<temp->data<<" x = "<<x->data<<"\n";getch(); } } if(list1) list->next =list1->next; // last1->next= x; else { list->next = x; x->next=list2->next; } if(list2) list->next = list2->next; else last = x; cout<<endl; cout<<"List1 = "; xuat(list1); getch(); cout<<endl; cout<<"List2 = "; xuat(list2); getch(); cout<<endl; cout<<"List = "; xuat(list); getch(); cout<<endl; cout<<"Phan hoach xong ";getch(); // Quicksort(list1,last1); // Quicksort(list2,last2); // cout<<"x = "<<x->data<<endl;getch(); } // -----------------------------------END----------------------------------
Ặc ... mã của bác quả thiệt cao siêu, tui đọc chả hiểu gì cả. Đây là cách giải của tui. Mã: void QuickSort(List list) { Node *first, *last; Node *i, *j; int x; first = list.first; last = NULL; // find last element for(i = list.first; i != NULL; i = i->next) last = i; if(last == NULL) return; Stack<Node*> s; s.Push(first); s.Push(last); while( !s.IsEmpty() ) { s.Pop(last); s.Pop(first); x = last->value; Node t; t.next = first; i = &t; j = first; // bo qua cac phan tu nho hon x while(j->value < x) { i = i->next; j = j->next; } for( ; j != last; j = j->next) { if(j->value <= x) { i = i->next; Swap(i->value, j->value); } } if(i != &t && i != first) { s.Push(first); s.Push(i); } i = i->next; if(i != last) { Swap(i->value, last->value); i = i->next; if(i != last) { s.Push(i); s.Push(last); } } } }
