1、文檔來源為：從網(wǎng)絡收集整理.word版本可編輯.歡迎下載支持課程設計(論文)任務書軟件學院學 院 專 業(yè) 班一、課程設計(論文)題目 各種查找算法演示二、課程設計(論文)工作自2009年12月28日起至2010 年1月2 日止。三、課程設計(論文)地點：多媒體實驗室(5-302,303)四、課程設計(論文)內(nèi)容要求：1 .本課程設計的目的(1)熟練掌握C語言的基本知識和技能;(2)掌握各種查找(順序、二分法、二叉排序樹、哈希)方法及適用場合，并能 在解決實際問題時靈活應用。(3)鞏固在散列查找時解決沖突的方法及特點；(5)培養(yǎng)分析、解決問題的能力；提高學生的科技論文寫作能力。2 .課程設計的任

2、務及要求1)基本要求：(1)設計一個的菜單將在實現(xiàn)的功能顯示出來，并有選擇提示;(2)分別實現(xiàn)順序、二分法、二叉排序樹、哈希表的查找(3)哈希表可選取其中任一種方法實現(xiàn)；(4)二叉排序樹必須實現(xiàn)構建、查找、插入、刪除四個基本操作(5)輸出各種排序的結果并進行比較。2)創(chuàng)新要求：提高算法效率，降低時間復雜度和空間復雜度3 )課程設計論文編寫要求(1)要按照課程設計模板的規(guī)格書寫課程設計論文(2)論文包括目錄、正文、心得體會、參考文獻等(3)課程設計論文用 B5紙統(tǒng)一打印，裝訂按學校的統(tǒng)一要求完成4 )答辯與評分標準：(1)完成原理分析：20分；(2)完成設計過程：40分；(3)完成調試：20分；

3、(4)回答問題：20分。5 )參考文獻：(1)嚴蔚敏，吳偉民.數(shù)據(jù)Z勾.北京：清華大學出版社，2006.(2.2006.（3）譚浩強.C清華大學出版社，2006.6天數(shù)構思及收集資料2圖書館編程設計與調試5實驗室3學生簽名：2009年12月28日課程設計（論文）評審意見（1）完成原理分析（20優(yōu)()()、中()差（);（2）設計分析(20 分):優(yōu)(）、良()、中()、T (）、差（);（3）完成調試(20 分):優(yōu)(）、良()、中()、T (）、差（);（4）翻譯能力(20 分):優(yōu)(）、良()、中()、T (）、差（);（5）回答問題(20 分):優(yōu)(）、良()、中()、T (）、差（);

4、（6）格式規(guī)范性及考!勤是否降名亭級:是(）、否()評閱人職稱:講師2010年1 月3日1文檔來源為：從網(wǎng)絡收集整理.word版本可編輯.歡迎下載支持.文檔來源為 :從網(wǎng)絡收集整理.word 版本可編輯.歡迎下載支持5文檔來源為:從網(wǎng)絡收集整理.word 版本可編輯.歡迎下載支持.2.1. 基本要求：2.2. 算法思想：2.3. 模塊劃分：2.4. 數(shù)據(jù)結構：2.5. 源程序：2.6. 測試情況：.錯誤.!未定義書簽。錯誤.! 未定義書簽。錯誤.! 未定義書簽。.錯誤.!未定義書簽。錯誤.!未定義書簽。錯誤.!未定義書簽。錯誤.!未定義書簽。.錯誤.!未定義書簽。錯誤.!未定義書簽。三、小結

5、錯誤.!未定義書簽。四、參考文獻一、 問題描述（ 1）設計一個的菜單將在實現(xiàn)的功能顯示出來，并有選擇提示；（ 2）分別實現(xiàn)順序、二分法、二叉排序樹、哈希表的查找（ 3）哈希表可選取其中任一種方法實現(xiàn)；（ 4）二叉排序樹必須實現(xiàn)構建、查找、插入、刪除四個基本操作 輸出各種排序的結果并進行比較。二、 內(nèi)容簡介2.1. 基本要求：設計程序分別可以實現(xiàn)順序查找、二分查找、二叉排序樹查找和哈希表查找。其中，哈希表查找只需要選擇其中的一種，二叉排序樹必須實現(xiàn)構建、查找、插入和刪除四個基本操作。能輸出各種排序的結果并進行比較。在運行結果中，可以選擇各種查找方法，并且輸入數(shù)據(jù)后能完成查找并輸出結果。2.2.

6、算法思想：利用主程序調用四個查找的子程序的絕對路徑。(1) 主程序設計方法用 a b c d 代表四種子程序的查找調用。例如假如用戶輸入 a 即代表用戶希望通過順序查找來找到結果。程序段為： case 'a': printf(" 順序查找： n");system(""E:shtuiDebugtui.exe""); break;(2) 子程序設計方法(3) 順序查找設置 0 號單元為哨兵從數(shù)組末尾逐次向前查找，返回數(shù)組下標。當下標為 0 時說 明查找失敗，反之查找成功。(4) 折半查找把 low 指針和 high 指針分

7、別指向數(shù)組的上界和下界， Mid 指針指向數(shù)組的中間位置。把 mid 指針與所要查找的關鍵字比較，如果相等返回數(shù)組下標；當關鍵字大于mid 指向的數(shù)據(jù)時，把mid+1 賦值給 low ；小于時，把mid-1 賦給 high 。如此循環(huán)，當 low=high 時，循環(huán)停止，返回 mid 值；當返回值為0 時，查找失敗，否則成功。(3)二叉樹查找二叉樹查找的數(shù)據(jù)鍵入方式有兩種：手動查找，自動查找。根據(jù)要查找的數(shù)據(jù)與“根結點”大小的比較來查找。若數(shù)據(jù)小于根結點值則從左子樹切入查找，若大于根結點則從右子樹切入查找，假如等于根結點即表明查找到返回根結點的地址值。若查找完畢沒有找到該數(shù)據(jù)即返回空值。(5)

8、 哈希表用除留余數(shù)法創(chuàng)建哈希函數(shù)，當遇到?jīng)_突時用開放定址法的線性探測解決沖突問題。把字符定義在數(shù)組中，再給定 k 值。根據(jù)造表時設定的哈希函數(shù)求得哈希地址，文檔來源為 :從網(wǎng)絡收集整理.word 版本可編輯.歡迎下載支持若表中此位置上沒有記錄，則查找不成功；否則比較關鍵字，若和給定值相等則查找 成功。2.3. 模塊劃分：void main () ：主函數(shù)，用來調用四個查找的子函數(shù)system(""E:shtuiDebugtui.exe"") ： E 盤中實現(xiàn)順序查找的程序 system(""E:shzhebanDebugzheban.

9、exe"") ： E 盤中實現(xiàn)二分查找的程序 system(""E:shertDebugert.exe"") ： E 盤中實現(xiàn)二叉排序樹查找的程序 system(""E:shgfDebuggf.exe"") ： E 盤中實現(xiàn)哈希查找的程序 void Insert(BSTree *tree, ElemType item) ：二叉排序樹查找 void CreateHashList() ：哈希表查找2.4. 數(shù)據(jù)結構：1 . 順序查找 順序存儲結構typedef int KeyType;typedef

10、 struct KeyType *elem;/ 數(shù)據(jù)元素存儲空間基址， 建表時按實際長度分配， 0號單元留空 int length; / 表長度SSTable; / 順序表的存儲結構2 .折半查找-順序存儲結構typedef struct int key;RedType;/定義結構體RedTypetypedef RedType ElemType; /RedType 型變量typedef struct ElemType elem100; / 表的空間大小 int length; / 表長度SSTable;3 .二叉樹查找-鏈式存儲結構typedef int ElemType;typedef st

11、ruct BSTNode/ 定義存儲結構 ElemType data;7文檔來源為:從網(wǎng)絡收集整理.word 版本可編輯.歡迎下載支持.struct BSTNode *lchild, *rchild; BSTNode, *BSTree;4 .哈希表 -鏈式存儲結構typedef struct NAMEchar *py;/ 名字的拼音int k;/拼音所對應的整數(shù)NAME;NAME NameListNAME_NO;typedef struct hterm /哈希表char *py; /名字的拼音int k;/拼音所對應的整數(shù)int si;/查找長度HASH;2.5. 源程序：#include&l

12、t;stdio.h>#include<stdlib.h>#include<windows.h>void main() char m=0;printf("請選擇查找方式：a-順序查找，b-二分查找，。二叉排序樹查找，d-哈希表查 找： ");scanf("%c",&m);switch(m) case 'a': printf(" 順序查找： n");system(""E:shtuiDebugtui.exe""); break;case '

13、b': printf(" 二分查找： n");system(""E:shzhebanDebugzheban.exe""); break;case 'c': printf(" 二叉排序樹查找： n");system(""E:shertDebugert.exe""); break;case 'd': printf(" 哈希表查找： n");system(""E:shgfDebuggf.exe"

14、;"); break;6文檔來源為:從網(wǎng)絡收集整理.word 版本可編輯.歡迎下載支持. / 主函數(shù)/*typedef struct /順序查找KeyType *elem;/ 數(shù)據(jù)元素存儲空間基址， 建表時按實際長度分配， 0號單元留空int length; / 表長度SSTable; / 順序表的存儲結構int Search_Seq(SSTable ST, KeyType key)int i;ST.elem0 = key; / “哨兵” ，如果順序表中不存在要查找的數(shù)據(jù)的話，則查找指針必/定指向該哨兵for(i = ST.length; ST.elemi != key; i-)re

15、turn i; /找到的話，則 i != 0, 否則 i = 0void main() int i, key;SSTable T;T.elem = (KeyType *)malloc(sizeof(KeyType);printf("How Many Entries Do You Want inputn");/ 輸入順序表長度scanf("%d", &T.length);for(i=1; i<=T.length; i+)printf("Please input the %dth entries n", i);/ 一個一個的

16、輸入元素scanf("%d", &T.elemi);for (i=1; i<=T.length; i+)printf("%5d",T.elemi); / 顯示已經(jīng)輸入的所有數(shù)據(jù)printf("nPlease input the data you want to searchn");scanf("%d", &key);typedef struct /折半查找int key;RedType;/定義一個包含關鍵字的結構體typedef RedType ElemType;typedef struct

17、ElemType elem100;/redtype 結構體類型的數(shù)組int length;/ 表的長度SSTable;/定義一個int Search_Bin ( SSTable ST, int key ) 文檔來源為 :從網(wǎng)絡收集整理.word 版本可編輯.歡迎下載支持/ 在有序表 ST 中折半查找其關鍵字等于key 的數(shù)據(jù)元素。/ 若找到，則函數(shù)值為該元素在表中的位置，否則為 0。int low, high, mid;low = 1; high = ST.length; / 置區(qū)間初值while (low <= high) mid = (low + high) / 2;if (key

18、=ST.elemmid.key) return mid; / 找到待查元素else if (key< ST.elemmid.key) high = mid - 1; /key 小于 mid 所對應的 k 值時/ 繼續(xù)在前半?yún)^(qū)間進行查找else low = mid + 1;/ 繼續(xù)在后半?yún)^(qū)間進行查找 return 0;/ 順序表中不存在待查元素 / Search_Bin void main() SSTable T;int key,i=1;int postion;int n=1;/記錄輸入的關鍵字個數(shù)printf(" 如果不想輸入 ,則輸入0，當此數(shù)的位置為0 時，查找不到該數(shù)。

19、n");printf(" 請輸入第 %d 個數(shù) :n",n);scanf("%d",&key);while(key!=0)n+;T.elemi+.key=key;printf(" 請輸入第 %d 個數(shù) ,大于 %dn",n,T.elemi-1.key);scanf("%d",&key);T.length=i; printf(" 請輸入要查的數(shù):n");scanf("%d",&key);postion=Search_Bin(T, key);pr

20、intf(" 此數(shù)的位置是： %dn",postion); void Insert(BSTree *tree, ElemType item)/二叉排序樹查找 BSTree node = (BSTree)malloc(sizeof(BSTNode);node->data = item;node->lchild = node->rchild = NULL;if (!*tree) *tree = node;HashListadr.py=NameListi.py;9文檔來源為:從網(wǎng)絡收集整理.word 版本可編輯 .歡迎下載支持else BSTree cursor

21、 = *tree;while (1) if (item < cursor->data)if (NULL = cursor->lchild)cursor->lchild = node;Break ； cursor = cursor->lchild ； elseif (NULL = cursor->rchild) cursor->rchild = node;break; cursor = cursor->rchild; return;BSTree Search(BSTree tree, ElemType item)BSTree cursor = tr

22、ee;while (cursor)if (item = cursor->data)return cursor;else if ( item < cursor->data)cursor = cursor->lchild;else cursor = cursor->rchild; return NULL;void CreateHashList() /哈希表查找int i;for (i=0;i<=50;i+) HashListi.py=""HashListi.k=0;HashListi.si=0;for (i=0;i<=30;i+) int sum=0;int adr=(NameListi.k) % M;/哈希函數(shù)intd=adr;if(HashListadr.si=0)/如果不沖突HashListadr.k=NameListi.k;HashListadr.si=1; else/沖突 do d=(d+(NameListi.k)%10+1)%M;/偽散列sum=sum+1;/查找次數(shù)加1while (HashListd.k!=0);HashListd.k=Na