綜合算法設(shè)計(jì)實(shí)驗(yàn)報(bào)告

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

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

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

4、點(diǎn)位置，再通過比較確定下一步查找哪個(gè)半?yún)^(qū)。shell排序：先取定一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把文件的全部記錄分成d1個(gè)組，所有距離為d1倍數(shù)的記錄放在同一個(gè)組中，在各組內(nèi)進(jìn)行直接插入排序；然后取第二個(gè)增量重復(fù)上述分組和排序，直至所取的增量dt=1(dtdt-1d2d1)，即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹?。堆排序是利用大頂堆（或小頂堆）來選取當(dāng)前無序區(qū)中關(guān)鍵字最大（或最?。┑挠涗泴?shí)現(xiàn)排序快速排序是對(duì)冒泡法的改進(jìn)，其基本思想是：通過一趟排序?qū)⒋盼募指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字值均比另一部分記錄的關(guān)鍵字小，然后分別對(duì)這兩部分進(jìn)行排序，以達(dá)到整個(gè)序列有序。歸并的思想：

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

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

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

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

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

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

11、個(gè)是沒排好序的，另一個(gè)是排好序后的數(shù)據(jù)。1.3主要數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：歸并排序：typedef int keytype;typedef int datatype;typedef struct keytype key; /* 排序碼字段 */ /*datatype info; 記錄的其它字段 */ recordnode;typedef struct int n; /* n為文件中的記錄個(gè)數(shù)，nmaxnum */ recordnode recordmaxnum; sortobject;基數(shù)排序: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; /* 隊(duì)列的頭指針 */ radixnode *e; /* 隊(duì)列的尾指針 */queue;hash排序：typedef struct hnode int data; struct hnode *next;hnode;typedef struct point struct hnode *pt;point;1.

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

14、具體算法）2.1主函數(shù)：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(請(qǐng)輸入隨機(jī)種子: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| 請(qǐng)選擇排序方式 |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.基數(shù)排序算法 |n);printf(tt| 7.哈希排序算法 |n);printf(tt| 0.退出程序 |n);printf(tt *n);printf(請(qǐng)輸入你的選擇：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為文件中的記錄個(gè)數(shù)，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 ) /* 反復(fù)復(fù)制兩個(gè)段的第一個(gè)記錄中較小的 */ if (ri.key=rj.key)

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

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

22、cord, pvector-n, length); length*=2; /* 一趟歸并，結(jié)果存回 */ 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; /* 已經(jīng)符合堆定義，無須浪費(fèi)時(shí)間 */ ds=dj; s=j; /* 交換，并使s指向新堆 */ ds=d0; /* 找到合適的地點(diǎn)就將原堆頂元裝進(jìn)去 */void heapsort(int d, long l) long i; for (i=l/2; i0; i-) heapadjust(d, i, l); /* 將原始序列調(diào)整為堆 */ 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-) /* 進(jìn)行d次分配和收集*/ p=head;for(i=0; ikeyj; /* 按排序碼的第j個(gè)分量進(jìn)行分配*/if (!queuek.f) queuek.f=p; /* 若第k個(gè)隊(duì)列空，當(dāng)前記錄為隊(duì)首*/else (queuek.e)-ne

26、xt=p; /* 否則當(dāng)前記錄鏈接到第k隊(duì)的隊(duì)尾*/queuek.e=p;p=p-next; for(i=0; queuei.f=null; i+) ; /* 找出第一個(gè)非空隊(duì)列*/p=queuei.e;head=queuei.f; /* head為收集鏈表的頭指針*/for(i+; inext=queuei.f; /* 收集非空隊(duì)列 */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調(diào)試分析（內(nèi)容包括：a）調(diào)試過程中遇到的問題是如何解決的以及對(duì)設(shè)計(jì)與實(shí)現(xiàn)的回顧討論和分析；b)算法的時(shí)空分析包括基本操作和相關(guān)算法的時(shí)間復(fù)雜度和空間復(fù)雜度的分析以及改進(jìn)設(shè)想；c) 經(jīng)驗(yàn)和體會(huì)等）3.1調(diào)試過程中的問題及解決方案：在本次程序的編寫和調(diào)試過程中，我曾多次修改代碼，并根據(jù)調(diào)試顯示的界面一次次調(diào)整代碼。在調(diào)試成功之前，我的程序因?yàn)?個(gè)錯(cuò)誤而無法運(yùn)行，在經(jīng)過完整并且仔細(xì)的檢查后，發(fā)現(xiàn)3處錯(cuò)誤分別是沒有定義變量就直

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

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