綜合算法設計實驗報告

1、學生學號學 生 實 驗 報 告 書實驗課程名稱應用數據結構開 課 學 院指導教師姓名學 生 姓 名學生專業(yè)班級2012 2013 學年 第 2 學期實驗項目名稱綜合算法設計同 組 者無實驗日期2013年 06 月 18日第一部分：實驗預習報告1、 實驗目的、意義1) 掌握查找的含義2) 掌握基本查找操作的算法和實現3) 掌握動態(tài)查找算法的實現、應用場合與優(yōu)缺點4) 能夠針對具體問題，靈活選用適宜的查找算法5) 掌握排序的基本概念，對排序的穩(wěn)定性及排序的時間復雜度有深刻的認識6) 對比折半插入排序和shell排序的異同7) 掌握選擇排序中堆排序的基本思想和算法實現8) 掌握快速排序的基本思想和算

2、法實現9) 了解歸并排序算法的基本思想和程序實現10) 了解基數排序算法的基本思想和程序實現11) 掌握hash排序算法的基本思想和程序實現12) 在上述內容的基礎上，將所有查找及排序算法整合在一個程序中2、 實驗基本原理與方法本實驗涉及各類查找和排序算法。靜態(tài)查找，折半查找的思想為：設查找表中的元素存放在數組r中，數據元素的下標范圍為low, high，要查找的關鍵字值為key，中間元素的下標為mid=|_(low + high) /2_|（向下取整），令key與rmid的關鍵字比較： 若key=rmid.key，查找成功，下標為m的記錄即為所求，返回mid。 若keyrmid.key，所要

3、找的記錄只能在右半部分記錄中，再對右半部分使用折半查找法繼續(xù)進行查找，搜索區(qū)間縮小了一半。重復上述過程，直到找到查找表中某一個數據元素的關鍵字的值等于給定的值key，說明查找成功；或者出現low的值大于high的情況，說明查找不成功。動態(tài)查找，編程實現一個開放式的高校本科招生最低錄取分數線的查詢系統，供師生和家長等查詢，高校自愿放入該校的信息，可能隨時有高校加入。要求實現的查詢功能有：查詢等于用戶給定分數的高校；查詢大于（或小于）用戶給定分數的高校查詢最低錄取分數線在用戶給定的分數段中的高校。直接插入排序：將當前無序區(qū)的第一個記錄插入到有序區(qū)中適當位置。折半查找法：在有序表中進行，先確定表的中

4、點位置，再通過比較確定下一步查找哪個半區(qū)。shell排序：先取定一個小于n的整數d1作為第一個增量，把文件的全部記錄分成d1個組，所有距離為d1倍數的記錄放在同一個組中，在各組內進行直接插入排序；然后取第二個增量重復上述分組和排序，直至所取的增量dt=1(dtdt-1d2d1)，即所有記錄放在同一組中進行直接插入排序為止。堆排序是利用大頂堆（或小頂堆）來選取當前無序區(qū)中關鍵字最大（或最小）的記錄實現排序快速排序是對冒泡法的改進，其基本思想是：通過一趟排序將待排文件分割成獨立的兩部分，其中一部分記錄的關鍵字值均比另一部分記錄的關鍵字小，然后分別對這兩部分進行排序，以達到整個序列有序。歸并的思想：

5、將兩個或兩個以上的有序表合并成一個有序表。利用歸并的思想實現排序，假設初始的序列含有n個記錄，可以看成n個有序的子序列，每個子序列的長度為m，然后把i(2)個子序列歸并，得到n/i個長度為i的子序列；再繼續(xù)歸并，如此重復直到得到一個長度為n的有序序列為止。通常使用的是i=2的二路歸并法。基數排序的基本思想是采用多關鍵字的排序。設記錄關鍵字ri由d個分量ki1, ki2, , kid組成，設每個分量的取值范圍為ti|i=1, 2, , m，且t1t2tm。準備m個箱子，先按低位分箱再按序號一次將各個非空箱子里的記錄收集起來，再對新收集起來的元素依次按較高的位分箱，直到最高位。分箱即將第s個關鍵字

6、等于ti的全部記錄裝入第i個箱子里。按最高位分箱后，按序號一次將各個非空箱子里的記錄收集起來，得到的元素序列就是有序的。hash排序是在hash查找的基礎上演變而來。對待排序列采用單調的hash函數，并用鏈地址法處理沖突，最后用一定規(guī)則收集存儲好的數據從而得到有序序列。3、 主要儀器設備及耗材安裝有vc+ 6.0運行環(huán)境的電腦，無耗材要求。4、 實驗方案或技術路線本實驗含有五部分內容靜態(tài)查找、動態(tài)查找、插入排序與選擇排序、快速排序與歸并排序、查找及排序算法集成。a靜態(tài)查找部分查找表的存儲結構為有序表，即表中記錄按關鍵字大小排序存放。輸入待查數據元素的關鍵字進行查找。為了簡化算法，記錄只含一個整

7、型量關鍵字字段，記錄的其余數據部分忽略不考慮。此程序中要求對整型量關鍵字數據的輸入按從小到大排序輸入。b動態(tài)查找部分主要的功能是查找，查找表為高校最低錄取分數信息的集合。根據題意可知，該查找表中的元素個數可能隨時增減，所以它是一個動態(tài)查找表，可采用樹狀結構保存。為了提高查詢速度，可建立二叉排序樹并在二叉排序樹中實現查找。c排序部分考慮對20個整數的隨機輸入進行排序，各排序功能基本上都可以成為獨立調用的模塊，因此可以先寫出排序算法，然后用主函數調用。d 查找及排序算法集成部分此部分需要學生自行設計，本指導書不給出具體算法。第二部分：實驗過程記錄實驗原始記錄（包括實驗數據記錄，實驗現象記錄，實驗過

8、程發(fā)現的問題等）1 概要設計（說明本程序中用到的所有抽象數據類型的定義，主程序的流程以及 各程序模塊之間的層次或調用關系）1.1抽象數據類型： 隊列：adt queue 數據對象：d ai | aielemset, i=1,2,.,n, n0 數據關系：r1 |ai-1, aid, i=2,.,n 基本操作：void init_q(queue &q);操作結果：構造空隊列qint q_empty(queue q);初始條件：隊列q存在操作結果：若q為空隊列，則返回true,否則falseint q_length(queue q);初始條件：隊列q存在操作結果：返回隊列q的元素個數，即隊列長度i

9、nt gethead_q(queue q);初始條件：隊列q存在操作結果：返回隊列q的隊頭元素void en_q(queue &q,int e);初始條件：隊列q存在操作結果：插入元素e為q的新的隊尾元素。void de_q(queue &q,int &e);初始條件：隊列q存在操作結果：刪除q的隊頭元素。adt queue線性表： adt list數據對象： d=ai|1=i=o,ai屬于elementtype類型數據關系：r=|ai,ai+1屬于d,i=1,.,n-1基本運算：initlist(&l)destroylist(&l);.圖：adt graph 數據對象： d=ai|1=i=0

10、,ai屬于elemtype類型 類型標識符數據關系： r=|ai,aj屬于d,1=i=n,1=j=n,其中每個元素可以有零個或多個直接前驅，可以有多個直接后繼基本運算： initgraph(&g) cleargraph(&g)dfs(g)bfs(g).1.2小問題：a .隨機數的產生： srand（）函數用于設置隨機數種，rand（）用于產生一個隨機數。b.數據的儲存： 由于100000個int型數的數組，所以我采用了malloc（）函數來動態(tài)分配一數組存儲它。 對于一些特別大的數據可以用文件存儲，在采用外排序的方式排序。 c.屏幕上無法顯示100000條數據，故將數據存儲在兩個文本文件中。一

11、個是沒排好序的，另一個是排好序后的數據。1.3主要數據結構設計：歸并排序：typedef int keytype;typedef int datatype;typedef struct keytype key; /* 排序碼字段 */ /*datatype info; 記錄的其它字段 */ recordnode;typedef struct int n; /* n為文件中的記錄個數，nmaxnum */ recordnode recordmaxnum; sortobject;基數排序:typedef int keytype;typedef int datatype;typedef struct

12、 node radixnode;struct node keytype keyd; /* datatype info;*/ radixnode *next;typedef radixnode *radixlist;typedef struct queuenode radixnode *f; /* 隊列的頭指針 */ radixnode *e; /* 隊列的尾指針 */queue;hash排序：typedef struct hnode int data; struct hnode *next;hnode;typedef struct point struct hnode *pt;point;1.

13、4主程序流程：主程序main（）輸入隨機數種子產生隨機數，并存在nonqueue.txt文件中選擇排序方法7.哈希6.基數5.歸并4.快速3.堆2.希爾1.折半選擇排序方法，并存在queue.txt文件中退出程序主函數在main.cpp中，排序算法的在各自的頭文件中。選擇排序方法后，調用選擇的排序方法。15各函數調用關系：rand（）binsertsort()shellinsert（）fopen（）srand（）shellsort（）main（）radixsort（）heapsort（）mergesort（）quicksort（）fclose（）partition（）2詳細設計（實現程序模塊的

14、具體算法）2.1主函數：void main()int *p,n,way,dlta4=5,3,2,1,l=11;long i;file *fp,*fp1;if(!(fp=fopen(queue.txt,w+)printf(打開文件 queue.txt 失敗!);if(!(fp1=fopen(nonqueue.txt,w+)printf(打開文件 nonqueue.txt 失敗!);printf(請輸入隨機種子:n);scanf(%d,&n);p=(int *)malloc(max*sizeof(int);for(i=1;imax;i+)pi=rand();fprintf(fp1,%-8d,pi)

15、;fclose(fp1);printf(ntt *n);printf(tt| 請選擇排序方式 |n);printf(tt| |n);printf(tt| 1.折半插入排序算法 |n);printf(tt| 2.希爾排序算法 |n);printf(tt| 3:堆排序算法 |n);printf(tt| 4.快速排序算法 |n);printf(tt| 5.歸并排序算法 |n);printf(tt| 6.基數排序算法 |n);printf(tt| 7.哈希排序算法 |n);printf(tt| 0.退出程序 |n);printf(tt *n);printf(請輸入你的選擇：n);scanf(%d,&w

16、ay);switch(way)case 0:exit(1);case 1:binsertsort(p, max-1);break;case 2:shellsort(p,max-1,dlta,4);break;case 3:heapsort(p,max-1);break;case 4: quicksort(p,max-1);break;case 5: vector.n = max-1;for(i=0;imax-1;i+)vector.record i.key =pi+1;mergesort(&vector);for(i=0;imax-1;i+)fprintf(fp,%-8d,vector.rec

17、ord i.key );fclose(fp);exit(1);case 6: radixlist hp;for(i=0;imax-1;i+)elementi.key0=0;elementi.key1=pi+1/10000%10;elementi.key2=pi+1/1000%10;elementi.key3=pi+1/100%10;elementi.key4=pi+1/10%10;elementi.key5=pi+1%10;elementi.next=null;for (i=0; inext;while(hp)fprintf(fp,%-8d,hp-key1*10000+hp-key2*1000

18、+hp-key3*100+ hp-key4*10+hp-key5);hp=hp-next;fclose(fp);exit(1);case 7:hashsort(p,max-1,max-1);break; for(i=1;imax;i+)fprintf(fp,%-8d,pi);fclose(fp); 2.2各排序算法：(1)歸并排序：#define max 100001#define maxnum 100001#define true 1#define false 0typedef int keytype;typedef int datatype;typedef struct keytype k

19、ey; /* 排序碼字段 */ /*datatype info; 記錄的其它字段 */ recordnode;typedef struct long n; /* n為文件中的記錄個數，nmaxnum */ recordnode recordmaxnum; sortobject; void merge(recordnode r, recordnode r1, long low, long m, long high) long i=low, j=m+1, k=low; while ( i=m &j=high ) /* 反復復制兩個段的第一個記錄中較小的 */ if (ri.key=rj.key)

20、r1k+=ri+; else r1k+=rj+; while (i=m) r1k+=ri+; /* 復制第一個段的剩余記錄 */ while (j=high) r1k+=rj+;/* 復制第二個段的剩余記錄 */* 對 r 做一趟歸并，結果放到 r1 中 */void mergepass(recordnode r, recordnode r1, long n, long length) long i=0, j; /* length為本趟歸并的有序子段的長度 */ while (i+2*length-1n) merge(r,r1,i,i+length-1,i+2*length-1); /*歸并長

21、length的兩個子段*/ i+=2*length; if(i+length-1n-1) /* 剩下兩段，后一段長度小于length */ merge(r, r1, i, i+length-1, n-1); else for(j=i; jn; j+) r1j=rj; /* 將剩下的一段復制到數組r1 */void mergesort(sortobject * pvector) recordnode recordmaxnum; long length = 1; while (lengthn) /*一趟歸并，結果存放在數組record中*/ mergepass(pvector-record, re

22、cord, pvector-n, length); length*=2; /* 一趟歸并，結果存回 */ mergepass(record, pvector-record, pvector-n, length); length *= 2; sortobject vector ;(2)折半插入排序：void binsertsort(int d, long l) long i, j, l, r, m; for (i=2; i=l; i+) d0=di; l=1; r=i-1; while (l=r) m=(l+r)/2; if(d0=r+1; j-) dj+1=dj; dr+1=d0; (3)sh

23、ell排序：void shellinsert(int d, long l, long dk) long i, j; for (i=dk+1; i=l; i+=dk) if ( di0 & d0dj; j=j-dk) dj+dk=dj; dj+dk=d0; void shellsort (int d, long l, int dlta, long t) long k; for (k=0; kt; k+) shellinsert(d, l, dltak);(4)堆排序算法：void heapadjust(int d, long s, long m) long j; d0=ds; for (j=2*

24、s; j=m; j*=2) if (jm & dj=dj) break; /* 已經符合堆定義，無須浪費時間 */ ds=dj; s=j; /* 交換，并使s指向新堆 */ ds=d0; /* 找到合適的地點就將原堆頂元裝進去 */void heapsort(int d, long l) long i; for (i=l/2; i0; i-) heapadjust(d, i, l); /* 將原始序列調整為堆 */ for (i=l; i1; i-) d0=d1; d1=di; di=d0; heapadjust(d, 1, i-1); (5)快速排序算法：int partition(int

25、d, long l, long r) d0=dl; while (lr) while (lr & d0dr) r-; dl=dr; while (l=dl) l+; dr=dl; dr=d0; return r;void qsort(int d, long l, long r) long p; if (lnext;for(j=d-1; j=0; j-) /* 進行d次分配和收集*/ p=head;for(i=0; ikeyj; /* 按排序碼的第j個分量進行分配*/if (!queuek.f) queuek.f=p; /* 若第k個隊列空，當前記錄為隊首*/else (queuek.e)-ne

26、xt=p; /* 否則當前記錄鏈接到第k隊的隊尾*/queuek.e=p;p=p-next; for(i=0; queuei.f=null; i+) ; /* 找出第一個非空隊列*/p=queuei.e;head=queuei.f; /* head為收集鏈表的頭指針*/for(i+; inext=queuei.f; /* 收集非空隊列 */p=queuei.e; p-next=null; (*plist)-next=head;struct node elementmax-1= 0,0,0,0,0,0,null,/*表頭*/0,0,0,0,3,6,null,/*36*/0,0,0,0,0,5,n

27、ull,/*5*/0,0,0,0,1,6,null,/*16*/0,0,0,0,9,8,null,/*98*/0,0,0,0,9,5,null,/*95*/0,0,0,0,4,7,null,/*47*/0,0,0,0,3,2,null,/*32*/0,0,0,0,3,6,null,/*36*/0,0,0,0,4,8,null,/*48*/0,0,0,0,1,0,null /*10*/ ;(7) hash排序: typedef struct hnode int data;struct hnode *next;hnode;typedef struct point struct hnode *pt;

28、point;void hashsort(int d,int l,int m) hnode *h,*g;point *p;int i,j;p=(point *)calloc(m,sizeof(point);for (i=0; ipt=null;for (i=1; idata=di;h-next=null;if (p+j)-pt) g=(p+j)-pt;if (g-datah-data) h-next=g;(p+j)-pt=h; else while (g-next) if(g-next-datadata) g=g-next;else h-next=g-next;break; g-next=h;

29、else (p+j)-pt=h; j=0; h=p-pt;for(i=1;idata;h=h-next; free(p+j+)-pt);h=(p+j)-pt; free(p);3調試分析（內容包括：a）調試過程中遇到的問題是如何解決的以及對設計與實現的回顧討論和分析；b)算法的時空分析包括基本操作和相關算法的時間復雜度和空間復雜度的分析以及改進設想；c) 經驗和體會等）3.1調試過程中的問題及解決方案：在本次程序的編寫和調試過程中，我曾多次修改代碼，并根據調試顯示的界面一次次調整代碼。在調試成功之前，我的程序因為3個錯誤而無法運行，在經過完整并且仔細的檢查后，發(fā)現3處錯誤分別是沒有定義變量就直

30、接套用、忘記加指針符號、忘記在嵌套語句后加大括號，這些看似不顯眼的小問題卻導致整個程序無法運行，所以我認為在編程過程中要及其嚴謹，盡量少犯或避免犯語法錯誤，保證代碼的完整性。a .隨機數的產生： srand（）函數用于設置隨機數種，rand（）用于產生一個隨機數。b.數據的儲存： 由于100000個int型數的數組，所以我采用了malloc（）函數來動態(tài)分配一數組存儲它。 對于一些特別大的數據可以用文件存儲，在采用外排序的方式排序。 c.屏幕上無法顯示100000條數據，故將數據存儲在兩個文本文件中。一個是沒排好序的，另一個是排好序后的數據。3.2算法的時空分析：1.穩(wěn)定性比較： 插入排序、冒

31、泡排序、簡單選擇排序及其他線形排序是穩(wěn)定的； 希爾排序、快速排序、堆排序是不穩(wěn)定的。2.時間復雜性比較： 插入排序、冒泡排序、選擇排序的時間復雜性為o(n2)； 其它非線形排序的時間復雜性為o(nlog2n)； 線形排序的時間復雜性為o(n)。3.輔助空間的比較： 線形排序的輔助空間為o(n)，其它排序的輔助空間為o(1)。4.其它比較：插入、冒泡排序的速度較慢，但參加排序的序列局部或整體有序時，這種排序能達到較快的速度。反而在這種情況下，快速排序反而慢了：當n較小時，對穩(wěn)定性不作要求時宜用選擇排序，對穩(wěn)定性有要求時宜用插入或冒泡排序；當n較大時，關鍵字元素比較隨機，對穩(wěn)定性沒要求宜用快速排序。當n較大時，關鍵字元素可能出現本身是有序的，對穩(wěn)定性有要求時，空間允許的情況下，宜用歸并排序。當n較大時，關鍵字元素可能出現本身是有序的，對穩(wěn)定性沒有要求時宜用堆排序。 3.3經驗體會：記得大一學習c語言的時候，只接觸過