北郵數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)四鏈表排序

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱(chēng)： 學(xué)生姓名： 班 級(jí)： 班內(nèi)序號(hào)： 學(xué) 號(hào)： 日 期： 實(shí)驗(yàn)描述：使用鏈表實(shí)現(xiàn)下面各種排序算法，并進(jìn)行比較。排序算法：1、插入排序2、冒泡排序3、快速排序4、簡(jiǎn)單選擇排序5、其他1 程序分析 1.存儲(chǔ)結(jié)構(gòu)：雙向鏈表 2.關(guān)鍵算法分析：a)插入排序：從有序數(shù)列和無(wú)序數(shù)列a2,a3，an開(kāi)始進(jìn)行排序； 處理第i個(gè)元素時(shí)（i=2,3，n），數(shù)列a1,a2，ai-1是已有序的，而數(shù)列ai,ai+1，an是無(wú)序的。用ai與ai-1，a i-2，a1進(jìn)行比較，找出合適的位置將ai插入； 重復(fù)第二步，共進(jìn)行n-i次插入處理，數(shù)列全部有序。b)冒泡排序： 1.比較相鄰的元素。如果第一

2、個(gè)比第二個(gè)大，就交換他們兩個(gè)。 2.對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。 3.針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。 4.持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。c)快速排序：一趟快速排序的算法是： 1.設(shè)置兩個(gè)變量i、j，排序開(kāi)始的時(shí)候：i=0，j=N-1； 2.以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給key，即key=A0； 3.從j開(kāi)始向前搜索，即由后開(kāi)始向前搜索(j-)，找到第一個(gè)小于key的值A(chǔ)j，將Aj和Ai互換； 4.從i開(kāi)始向后搜索，即由前開(kāi)始向后搜索(i+)，找到第一個(gè)大于key的A

3、i，將Ai和Aj互換； 5.重復(fù)第3、4步，直到i=j； (3,4步中，沒(méi)找到符合條件的值，即3中Aj不小于key,4中Ai不大于key的時(shí)候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進(jìn)行交換的時(shí)候i， j指針位置不變。另外，i=j這一過(guò)程一定正好是i+或j-完成的時(shí)候，此時(shí)令循環(huán)結(jié)束）。d)簡(jiǎn)單選擇排序：設(shè)所排序序列的記錄個(gè)數(shù)為n。i取1,2,n-1,從所有n-i+1個(gè)記錄（Ri,Ri+1,Rn）中找出排序碼最小的記錄，與第i個(gè)記錄交換。執(zhí)行n-1趟 后就完成了記錄序列的排序。 3.代碼詳細(xì)分析：#include<iostream>#includ

4、e<windows.h> using namespace std;struct Node /建立節(jié)點(diǎn) int data;Node* last;Node* next;Node()last=NULL;next=NULL; class List /建立鏈表 private:Node* front;Node* rear;int length;public: List();List(int a,int n); void Insert(int x,Node* p); /在p后面插入節(jié)點(diǎn) void Delete(Node* p); /刪除p節(jié)點(diǎn) void Print(); /打印 void Se

5、qSort(); /插入排序 void BubSort(); /冒泡排序 void QuiSort(); /快速排序 void Qui(Node* first,Node* end,int* c); /快速排序的遞歸函數(shù) void SelSort(); /簡(jiǎn)單選擇排序 ;List:List(int a,int n) /構(gòu)造函數(shù) front=new Node;length=n;rear=front;int i;Node* s; for(i=0;i<n;i+)s=new Node;s->data=ai;rear->next=s;s->last=rear;rear=s;void

6、 List:Insert(int x,Node* p) /插入函數(shù) Node* s=new Node;s->data=x;s->last=p->last;p->last->next=s;p->last=s;s->next=p; void List:Print() /打印函數(shù) Node* p=front->next;while(p!=NULL)cout<<p->data<<" "p=p->next;cout<<endl;void List:Delete(Node* p) /刪除函數(shù)

7、 Node* De=p;if(p=rear)rear=p->last;p->last->next=NULL;delete De;else p->last->next=p->next; p->next->last=p->last; delete De;void List:SeqSort() /插入排序 LARGE_INTEGER large_interger; double dff; _int64 c1, c2; QueryPerformanceFrequency(&large_interger); dff = large_inter

8、ger.QuadPart; QueryPerformanceCounter(&large_interger); c1 = large_interger.QuadPart;int ccom=0; int cmove=0;Node* p=front->next->next;Node* q;Node* De;bool ifdelete;while(p!=NULL)ifdelete=0;q=front->next;while(q!=p) ccom+;if(q->data>=p->data)De=p;Insert(p->data,q);ifdelete=

9、1;break;q=q->next;p=p->next;if(ifdelete=1)Delete(De);QueryPerformanceCounter(&large_interger); c2 = large_interger.QuadPart; cout<<"SeqSort:"Print();cout<<"比較次數(shù)："<<ccom<<endl;cout<<"移動(dòng)次數(shù)："<<cmove<<endl;cout<<&quo

10、t;用時(shí)："<<(c2 - c1) * 1000*1000/dff<<"微秒"<<endl; cout<<endl;void List:BubSort() /冒泡排序 LARGE_INTEGER large_interger; double dff; _int64 c1, c2; QueryPerformanceFrequency(&large_interger); dff = large_interger.QuadPart; QueryPerformanceCounter(&large_interg

11、er); c1 = large_interger.QuadPart; int ccom=0; int cmove=0;Node* p;Node* q=rear;int temp;int j;for(j=0;j<length-1;j+) p=front->next; while(p!=q) ccom+; if(p->data>p->next->data) temp=p->next->data; p->next->data=p->data; p->data=temp; cmove+=3; p=p->next; q=q-&

12、gt;last; QueryPerformanceCounter(&large_interger); c2 = large_interger.QuadPart; cout<<"BubSort:" Print();cout<<"比較次數(shù)："<<ccom<<endl;cout<<"移動(dòng)次數(shù)："<<cmove<<endl;cout<<"用時(shí)："<<(c2 - c1) * 1000*1000/dff<&

13、lt;"微秒"<<endl; cout<<endl;void List:Qui(Node* first,Node* end,int* c) /快速排序（有參數(shù)） Node* p1=first;Node* p2=end;int pivot=p1->data;while(p1!=p2) while(p1!=p2&p2->data>=pivot)p2=p2->last;c0+;c0+;p1->data=p2->data;c1+;while(p1!=p2&p1->data<=pivot)p1=p

14、1->next;c0+;c0+;p2->data=p1->data;c1+;p1->data=pivot;if(p1->last!=first&p1!=first)Qui(first,p1->last,c);if(p2->next!=end&&p2!=end)Qui(p1->next,end,c); void List:QuiSort() /快速排序（轉(zhuǎn)化為無(wú)參）LARGE_INTEGER large_interger; double dff; _int64 c1, c2; QueryPerformanceFrequenc

15、y(&large_interger); dff = large_interger.QuadPart; QueryPerformanceCounter(&large_interger); c1 = large_interger.QuadPart; int count2=0;Qui(front->next,rear,count);QueryPerformanceCounter(&large_interger); c2 = large_interger.QuadPart; cout<<"QuiSort:"Print();cout<&

16、lt;"比較次數(shù)："<<count0<<endl;cout<<"移動(dòng)次數(shù)："<<count1<<endl;cout<<"用時(shí)："<<(c2 - c1) * 1000*1000/dff<<"微秒"<<endl; cout<<endl;void List:SelSort() /簡(jiǎn)單選擇排序 LARGE_INTEGER large_interger; double dff; _int64 c1, c2;

17、 QueryPerformanceFrequency(&large_interger); dff = large_interger.QuadPart; QueryPerformanceCounter(&large_interger); c1 = large_interger.QuadPart; int ccom=0; int cmove=0;Node* p=front->next;Node* q;int temp;while(p!=rear)q=rear;while(q!=p)ccom+;if(q->data<p->data)temp=q->dat

18、a;q->data=p->data;p->data=temp; cmove+=3;q=q->last;p=p->next;QueryPerformanceCounter(&large_interger); c2 = large_interger.QuadPart; cout<<"SelSort:" Print();cout<<"比較次數(shù)："<<ccom<<endl;cout<<"移動(dòng)次數(shù)："<<cmove<<end

19、l;cout<<"用時(shí)："<<(c2 - c1) * 1000*1000/dff<<"微秒"<<endl; cout<<endl;main()const int n=5;int an;cout<<"輸入一組"<<n<<"個(gè)數(shù)據(jù)："<<endl; int i;for(i=0;i<n;i+)cin>>ai;List L1(a,n);List L2(a,n);List L3(a,n);List L4(a,n); int Menu;while(1) cout<<"Menu:"<<endl; cout<<"1.插入排序"<<endl; cout<<"2.冒泡排序"&l