第一篇：數據結構課程設計：動態查找表
編號： 139
數據結構與算法課程設計
說明書
動態查找表
學
院：
海洋信息工程學院
專
業：
計算機科學與技術
學生姓名：
學
號：
指導教師：
2015年月 26 日
動態查找表
學生姓名：銀杰
指導老師：王曉瑩
摘 要
本課程設計說明書系統地闡述了我使用C語言在Code::Blocks軟件編寫的動態查找表程序的整個過程，編寫的環境是win7 64位操作系統。根據題目要求，編寫動態查找表使用二叉排序樹，即二叉鏈表作為存儲結構。該程序具有建立數據功能、具有數據查找功能、具有數據插入功能、具有數據刪除功能等基本功能操作。
關鍵詞：動態查找表，Code::Blocks軟件，win7 64位操作系統，C#
dynamic lookup table
Author :yinjie
Tutor :Wangxiaoying
Abstract
This course design specification system to explain the whole process of using C language in Code:: Blocks software written in the dynamic look-up table program, the preparation of the environment is win7 64 bit operating system.According to the topic request, the preparation of the dynamic look-up table using the two fork sort tree, that is, the two binary list as the storage structure.The program has the function of building data, data searching, data insertion, data deletion and so on.Key words:dynamic lookup table, Code::Blocks software,win7 64 bit operating system，C #
目 錄
引言.........................................................................................................................................................................1 查找的基本概念.................................................................................................................................................1 小結.....................................................................................................................................................................1 題目.....................................................................................................................................................................1 第1章 程序的構圖設計.....................................................................................................................................2 1.1動態查詢表：...............................................................................................................................................2 1.2程序功能流程圖：.......................................................................................................................................2(1)、主函數模塊............................................................................................................................................2(2)、二叉排序樹的生成................................................................................................................................3(3)、二叉排序樹的查找模塊........................................................................................................................4(4)、二叉排序樹的插入模塊........................................................................................................................4(5)、二叉排序樹刪除連接模塊....................................................................................................................5(6)、二叉排序樹的刪除模塊........................................................................................................................5(7)、二叉排序樹的遍歷模塊........................................................................................................................6 第2章 詳細設計的程序.....................................................................................................................................6 各函數模塊.........................................................................................................................................................6(1)主函數模塊................................................................................................................................................6(2)二叉排序樹的生成模塊............................................................................................................................8(3)二叉排序樹的查找模塊............................................................................................................................8(4)二叉排序樹的插入模塊............................................................................................................................9(5)多態查找表刪除模塊..............................................................................................................................10(6)二叉排序樹的中序遍歷模塊..................................................................................................................12 第3章 程序測試和運行.....................................................................................................................................12 3.1 程序測試....................................................................................................................................................12 3.2 程序運行....................................................................................................................................................13
1、主界面
...................................................................................................................................................13
2、建立二叉排序樹模塊界面.....................................................................................................................13
3、二叉排序樹查找模塊界面.....................................................................................................................14
4、二叉排序樹插入模塊界面.....................................................................................................................14
5、二叉排序樹刪除模塊界面
...................................................................................................................14
6、退出程序的界面.....................................................................................................................................14 總 結.....................................................................................................................................................................15 程序完成情況...................................................................................................................................................15 有待改進之處...................................................................................................................................................15 課程設計期間的收獲.......................................................................................................................................15 附錄源代碼如下...................................................................................................................................................17
桂林電子科技大學課程設計說明書
引言
查找的基本概念
查找又稱為檢索，就是從一個數據元素集合中找出某個特定的數據元素。查找是數據處理中最為常用的一種操作，查找算法的優劣對整個軟件系統的效率影響很大，尤其當所涉及的數據量較大時，更是如此。在一個數據集合中進行查找操作可選用的方法與該數據元素集合的存儲結構有很大關系。
查找是根據某個給定的值，在數據元素構成的集合中確定是否在這樣一個數據元素，它的關鍵字等于給定值的關鍵字。
要進行查找，必須明確要查找對象的特征，也就是要查找元素的關鍵值。如果在數據集合中能找到與給定值相等的關鍵字，則該關鍵字所屬的數據元素就是所要查找的數據元素，此時稱該查找成功；如果查遍了整個數據元素集合也未能找到與給定值相等的關鍵字，則稱該查找失敗。小結
當然對于這個說明書，我不可能做得至善至美，但是一些基本的格式內容還是符合要求的。首先，我對查找表進行一個簡要的概述。然后，我就查找表進行了詳細的分析，這是設計中很重要的一步。接下來，我把查找表中所有的設計簡明清晰地展現出來，并把我在設計中遇到的問題和分析解決問題的辦法做了分析。最后，在結論中，我對自己的課程設計做了總體的評價同時簡述了我在這次課程設計中的收獲和經驗。
題目
選題十二：動態查找表
【問題描述】
利用二叉排序樹完成動態查找表的建立、指定關鍵字的查找、插入與刪除指定關鍵字結點。【任務要求】
算法輸入：指定一組數據。
桂林電子科技大學課程設計說明書
算法輸出：顯示二叉排序樹的中序遍歷結果、查找成功與否的信息、插入和刪除后的中序遍歷結果(排序結果)。
算法要點：二叉排序樹建立方法、動態查找方法,對樹進行中序遍歷。【測試數據】
自行設定，注意邊界等特殊情況。
第1章 程序的構圖設計
1.1動態查詢表：
依照輸入的一組數據{56,80,65,20}所得的二叉排序樹如下（a）所示：當插入11的時候就如（b）所示。
562065801
156206580
（a）
（b）1.2程序功能流程圖：
(1)、主函數模塊
桂林電子科技大學課程設計說明書
開始打印輸出動態表的6個功能選擇欄do循環輸入選擇號hSwitch(h)執行對應函數模塊程序退出結束
(2)、二叉排序樹的生成
開始輸入數據個數Xfor循環輸入X個數據調用插入函數Insert二叉樹建成結束
桂林電子科技大學課程設計說明書
(3)、二叉排序樹的查找模塊
開始二叉排序樹是否為空否根結點關鍵字？key是大于遞歸返回在左子樹查找遞歸返回等于小于在右子樹查找查找失敗查找成功結束
(4)、二叉排序樹的插入模塊
開始調用查詢函數Search()是否查詢成功否被插入結點*s為新的根結點是插入的節點根結點<被插結點*s為左孩子插入成功結束
>被插結點*s為右孩子
桂林電子科技大學課程設計說明書
(5)、二叉排序樹刪除連接模塊
開始左右子樹是否為空是While循環否向右走到盡頭重接它的左右子樹將被刪結點的前驅s的內容直接替代該結點的內容被刪除結點的左子樹的右子樹是否為空否重接*q的右子樹是重接*q的左子樹連接成功結束(6)、二叉排序樹的刪除模塊
開始輸入要刪除的的數據是否存在關鍵字等于n的數據元素否調用刪除的連接函數Delete()結束返回是找到關鍵字并刪除
桂林電子科技大學課程設計說明書
(7)、二叉排序樹的遍歷模塊
開始二叉樹根是否為空否對左子樹按中序遍歷進行訪問根結點對右子樹按中序遍歷進行遍歷完成結束是遞歸調用
第2章 詳細設計的程序
各函數模塊
(1)主函數模塊：
用主函數main()來實現。主要是通過設計一個do()函數并讓主函數調用它來顯示主菜單，讓用戶選擇操作。在do()函數中，我應用了switch-case語句來進行選擇，是個比較簡單實現的模塊。最后若選擇“5”退出循環。否則繼續循環。主要代碼如下：
int main(){
bitree T=NULL,p;ElemType e;int n;int h;char c;
do{
printf(“********************************************************n”);
桂林電子科技大學課程設計說明書
printf(“*
*n”);
printf(“*
動態查找表
*n”);
printf(“*
1.建立二叉排序樹
*n”);
printf(“*
2.二叉排序樹查找元素
*n”);
printf(“*
3.二叉排序樹插入元素
*n”);
printf(“*
4.二叉排序樹刪除元素
*n”);
printf(“*
5.退出
*n”);
printf(“*
*n”);
printf(“********************************************************n”);
printf(“請輸入你的選擇: n”);
scanf(“%d”,&h);
switch(h)
{
case 1:Init(T);printf(“中序遍歷二叉排序樹: ”);Zhongxu(T);printf(“n”);
break;
case 2:printf(“請輸入要查找的數據:n”);scanf(“%d”,&n);e.key=n;
if(Search(T,e,NULL,p))
printf(“數據已經存在!n”);
else
{ printf(“數據不存在!n”);}
break;
case 3:printf(“請輸入要插入的數據:n”);scanf(“%d”,&n);e.key=n;
if(Search(T,e,NULL,p))
printf(“已經存在!n”);
else{Insert(T, e);printf(“成功插入!n”);printf(“中序遍歷二叉排序樹: ”);Zhongxu(T);printf(“n”);}
break;
case 4:printf(“請輸入要刪除的數據:n”);scanf(“%d”,&n);e.key=n;
if(Search(T,e,NULL,p))
{ Deletebit(T,n);printf(“已經成功刪除!n”);printf(“中序遍歷二叉排序
桂林電子科技大學課程設計說明書
樹: ”);Zhongxu(T);printf(“n”);}
else printf(“數據不存在!n”);
break;
case 5:printf(“退出！n”);
break;
default:printf(“選擇錯誤，重新開始!n”);
}
} while(h!=5);}(2)二叉排序樹的生成模塊：
二叉排序樹的生成，是從空的二叉排序樹開始，每輸入一個結點數據，就調用一次插入算法將它插到當前已經生成的二叉排序樹中。主要代碼如下：
void Init(bitree &T)//構造一個動態查找表T {
int x;int i;int n;
ElemType e;printf(“請輸入結點個數: ”);scanf(“%d”,&x);
for(i=1;i<=x;i++)
{
printf(“第%d個結點數據值:”,i);scanf(“%d”,&n);
e.key=n;Insert(T,e);
}
printf(“二叉排序樹已經建立!n”);}
(3)二叉排序樹的查找模塊： 二叉排序樹的查找方法如下。當二叉排序樹為空時，查找失敗。
當二叉排序樹根結點的關鍵字等于key時，查找成功。
桂林電子科技大學課程設計說明書
當二叉排序樹根結點的關鍵字大于key時，從根結點的左子樹中以同樣方法進行查找。當二叉樹根結點的關鍵字小于key時，從根結點的右子樹以同樣方法進行查找。顯然，該過程是一個遞歸過程，下面給出這一算法的實現。
主要代碼：
bitree Search(bitree T,ElemType e,bitree f,bitree &p)//在二叉排序樹中查找數據 {
if(!T)
{
p=f;
return NULL;
}//查找不成功
else if(T->data.key==e.key)
{
p=T;return T;
} //查找成功
else if(T->data.key>e.key)
return Search(T->lchild,e,T,p);
else return Search(T->rchild,e,T,p);}//在二叉排序樹中查找數據(4)二叉排序樹的插入模塊：
若要將一個關鍵字值為key的結點t插到二叉排序樹中，只需要使該結點插入后，二叉排序樹中的元素依然按照原來的規律排列即可。二叉排序樹的插入方法如下。
若二叉排序樹是空樹，則key稱為二叉排序樹的根。
若二叉排序樹為非空，則將key與二叉排序樹的根結點進行比較：如果key的值等于根結點的值，則停止插入；如果key的值小于根結點的值，則將key插到左子樹；如果key的值大于根結點的值，則將key插到右子樹中。主要代碼如下：
void Insert(bitree &T,ElemType e)//在二叉排序樹中插入數據
桂林電子科技大學課程設計說明書
{
bitree p,s;
if(!Search(T,e,NULL,p))//查找不成功
{
s=(bitree)malloc(sizeof(bitnode));
s->data=e;s->lchild=s->rchild=NULL;
if(!p)T=s;//被插入結點*s為新的根結點
else if(e.key
data.key)
p->lchild=s;//被插結點*s為左孩子
else
p->rchild=s;//被插結點*s為右孩子
} }(5)多態查找表刪除模塊：
從二叉排序樹中刪除一個結點，不能簡單地把以該結點為根的子樹都刪除，只能刪除掉該結點，并且還應該保證刪除后所得到的二叉樹依然滿足二叉樹的性質不變。也就是說，在二叉排序樹中刪除一個結點相當于刪除有序序列中的一個結點。
假設要刪除的結點為P，其雙親結點為F，同時假設結點P是結點F的左孩子（右孩子的情況類似）。刪除操作首先要確定被刪結點P是否在二叉排序樹中。若不在，則不做任何操作；若在，分為以下三種情況討論。若P為葉子結點，可直接將其刪除。
若結點P只有左子樹，或只有右子樹，則可將P的左子樹或右子樹直接改為其雙親結點F的左子樹或右子樹。
若P既有左子樹，又有右子樹此時有兩種處理方法。
方法1：首先找到結點P在中序序列中的直接前驅結點S，然后用結點P的左子樹改為F的左子樹，而將P的右子樹改為S的右子樹。
方法2：首先找到結點P在中序序列中的直接前驅結點s，然后用結點s的值替代結點p的值，再將結點s刪除，原結點s的左子樹改為s的雙親結點q的右子樹。主要代碼如下：
桂林電子科技大學課程設計說明書
void Delete(bitree &p)//從二叉排序樹中刪除結點p，并重接它的左或右子樹 {
bitree q,s;
if(!p->rchild)//右子樹空，只需重接它的左子樹
{
q=p;p=p->lchild;free(q);q=NULL;
}
else if(!p->lchild)//左子樹空，只需重接它的右子樹
{
q=p;p=p->rchild;free(q);q=NULL;
}
else{//左右子樹均不空
q=p;s=p->lchild;
while(s->rchild)//向右走到盡頭
{
q=s;s=s->rchild;
}
p->data=s->data;//將被刪結點的前驅s的內容直接替代該結點的內容
if(q!=p)//若被刪除結點的左子樹的右子樹不為空
q->rchild=s->lchild;//重接*q的右子樹
else
q->lchild=s->lchild;//重接*q的左子樹
free(s);s=NULL;
} }//刪除結點
void Deletebit(bitree &T,int n)//刪除二叉排序樹中的數據 {
if(!T)return;//不存在關鍵字等于n的數據元素
桂林電子科技大學課程設計說明書
else{
if(T->data.key==n)return(Delete(T));//找到關鍵字等于n的數據元素并刪除它
else if(T->data.key>n)Deletebit(T->lchild,n);//繼續在左子樹中刪除
else Deletebit(T->rchild,n);//繼續在右子樹中刪除
} }
(6)二叉排序樹的中序遍歷模塊：
中序遍歷二叉樹定義：若二叉樹根為空，則返回；否則，中序遍歷左子樹；訪問根結點；中序遍歷右子樹。主要代碼如下：
void Zhongxu(bitree T)//中序遍歷 {
if(T!=NULL)
{
Zhongxu(T->lchild);
printf(“%d ”,T->data.key);
Zhongxu(T->rchild);
} }
第3章 程序測試和運行
3.1 程序測試
程序測試是程序質量保證的主要活動之一，在程序編寫的過程中，在各個階段都有可能存在錯誤和缺陷。通過測試是可以發現程序設計中存在的種種問題，并可以及時改正。避免在程序運行時才出現不必要的錯誤。測試是質量保證一個臨界和決定懲罰，它提供對程序說明、設計和編碼的最終評審。是發現程序缺陷和錯誤的有力手段。根據系統設計目標和功能，對系統進行測試。
桂林電子科技大學課程設計說明書
1、功能性
（1）程序實現的主要功能，包括查詢，插入，刪除等。
（2）題目要求的輸入輸出字段，以及題目要求的輸入限制。
2、可靠性
程序正確實現了對動態查找表的查詢、插入、刪除等各種功能。
3、易用性
現有程序實現了如下易用性：
（1）查詢，插入，刪除，操作相關提示信息的一致性，可理解性 ?
（2）輸入限制的正確性
（3）輸入限制提示信息的正確性，可理解性，一致性
（4）界面排版簡潔完整 3.2 程序運行
1、主界面 ：
2、建立二叉排序樹模塊界面 ：
桂林電子科技大學課程設計說明書
3、二叉排序樹查找模塊界面 ：
4、二叉排序樹插入模塊界面 ：
5、二叉排序樹刪除模塊界面 ：
6、退出程序的界面 ：
桂林電子科技大學課程設計說明書
總 結
程序完成情況
在編寫程序寫課程設計的時間里，雖然歷經重重困難和挫折，但是在我自己的努力和老師的幫助下終于完成了動態查找表的設計。盡管該程序在功能和性能上可能還有一些缺陷，但是我已經完成了課程設計的任務和目標，達到了題目基本要求，成功完成了算法與數據結構課程設計。有待改進之處
有待改進：
1、我在編寫程序的時候，用的是C++格式去保存編譯的，用了C語言來編寫，但是有一些C++的形式，當我用C來新建保存的時候卻出現問題。所以程序我是用C++來新建保存的。
2、流程圖畫的不是很規范表準，在一些邏輯表達上不夠簡潔清晰。課程設計期間的收獲
在完成此次的課程設計的過程中，我跨越了傳統方式下的教與學的體制束縛，桂林電子科技大學課程設計說明書
通過自己的思考和設計，培養了自學能力和動手能力。并且由原先的被動的接受知識轉換為主動的尋求知識，這可以說是學習方法上的一個很大的突破。在以往的傳統的學習模式下，我們可能會記住很多的書本知識，但是通過課程設計，我們學會了如何將學到的知識轉化為自己的東西，學會了怎么更好的處理知識和實踐相結合的問題。
通過這次課程設計，我認識到數據結構與算法是計算機科學的基礎課程，是我們學習的核心課程。我對數據結構和算法又有了新的認識。數據結構的研究不僅涉及到計算機軟件，而且和計算機硬件的研究也有著密切的關系，無論是編譯程序還是操作系統，都涉及到數據元素在存儲器中的分配問題。在研究信息檢索時也必須考慮如何組織數據，以便使查找和存取數據元素更為方便。可以認為數據結構是介于數學、計算機硬件和計算機軟件三者之間的一個核心內容，是從事計算機科學研究及其應用的人必須掌握的重要內容。
這次的課程設計有效的培養了我們獨立思考的能力，提高了我們的動手操作水平。在具體設計中，我們鞏固了上學期所學的數據結構與算法的理論知識，進一步提高了自己的編程能力。這也是課程設計的目的所在。通過編程實踐，不僅開發了自己的邏輯思維能力，培養了分析問題、解決問題的能力，更充分鍛煉了我們的編程能力。
在這次課程設計中我也知道了的編程能力不強，有很多程序與算法是借鑒別人的，我想只要我有自己寫程序，并且結合他人的程序算法，把程序完成，那我還是學習到東西了的。
在課程設計中我體會到：一個好的程序應該是一個高內聚低耦合的程序。而要做出一個好的程序則應該通過對算法與其數據結構的時間復雜度和空間復雜度進行實現與改進。然而，實際上很難做到十全十美，原因是各要求有時相互制約，要節約算法的執行時間往往要以犧牲更多的存儲空間為代價：而為了節省存儲空間又可能要以更多的時間為代價。因此，只能根據具體情況有所側重：如果程序的使用次數較少，則應該力求算法簡單易懂；如果程序反復多次使用，則應該盡可能選用快速算法或者設置為內聯函數；如果解決問題的數據量極大，但是機器的內存空間不是很充足，則在編寫算法時應該考慮如何節省空間。
學習了《數據結構與算法》這門課，我們在編寫程序時就應該注意到所編寫程序的時間復雜度和空間復雜度，以及是否運用了良好的算法，而不是只是象以前編寫程序時單純使用C++的知識。我們要充分考慮程序的性能，從而編寫出更好的程序。
桂林電子科技大學課程設計說明書
在設計報告的寫作過程中我也學到了做任何事情都要有的心態，首先我明白了做學問要一絲不茍，對于出現的任何問題都不要輕視，要通過正確的途徑去解決，在做事情的過程中要有耐心和毅力，不要一遇到困難就打退堂鼓，只要堅持下去就可以找到思路去解決問題的，在遇到問題時，有必要向老師和同學請教，合作溝通的意義是巨大的。
在這次課程設計中，我認識到了自己的不足之處同時我也收獲了很多知識和經驗，在今后的學習中，我一定勤于思考，并靈活運用所學知識，多進行編程實踐。在總結反思和編程訓練中，不斷提升自己的編程能力。相信在我的努力下，我的程序設計水平一定會不斷提高。
參考文獻
[1]數據結構與算法/汪沁，奚李峰主編.-北京：清華大學出版社，2012.9（第8章 查找）
[2]百度文庫>專業資料>IT/計算機>計算機軟件及應用>動態查找表實驗報告
http://wenku.baidu.com/link?url=crizbdK6WO86YXeSJWwkHNdXpaxUDkRJnoShcVDJqBfGO03Cbk6LAdVwBYHxE82kYHkuIjC1HFCiOrSiEWJXOOspWGIo3PNSDjbeY1jHbJu
附錄源代碼如下：
數據結構與算法的課程設計1.cpp
第二篇：數據結構課程設計-查找排序
查找及排序算法實現
一、實驗目的
1、熟練掌握二叉排序樹查找算法及C語言描述。
2、熟練掌握折半查找算法及C語言描述。
3、熟練掌握簡單選擇排序算法及C語言描述。
4、熟練掌握簡單插入排序算法及C語言描述。
5、熟練掌握冒泡（起泡）排序算法及C語言描述。
6、了解各種查找及排序算法的優缺點、實用性及應用。
7、將理論與實際相結合，切實提高自己的邏輯能力和動手能力。
二、設計內容
1.折半查找算法
折半查找算法的思路：
初始狀態：假設表長為n，low、high和mid分別指向待查元素所在區間的下界、上界和中點,key為給定值，初始時，令low=0,high=n-1,mid=(low+high)/2 讓key與mid指向的記錄比較
若key==r[mid].key，查找成功,算法結束；若key
起泡排序的思路：
首先將第一個記錄的關鍵字和第二個記錄的關鍵字進行比較，若為逆序（即L.r[1].key>L.r[2].key），則將兩個記錄交換之，然后比較【第二個記錄和第三個記錄】的關鍵字。以此類推，直至第n-1個記錄和第n個記錄的關鍵字進行過比較為止。上述過程稱做第一趟起泡排序，其結果使得關鍵字最大的記錄被安置到最后一個記錄的位置上，然后進行第二趟起泡排序，對前n-1個記錄進行同樣操作，其結果是使關鍵字次大的記錄被安置到第n-1個記錄的位置上。一般地，第i躺起泡排序是從L.r[1]到L.r[n-i+1]以此比較相鄰兩個記錄的關鍵字，并在“逆序”時交換相鄰記錄，其結果是這n-i+1個記錄中關鍵字最大的記錄被交換到第n-i+1的位置上。整個排序過程需進行k(1<=k 首先以一個元素為基準，從一個方向開始掃描，比如從左至右掃描，以a[0]為基準，接下來從a[0]...a[9] 中找出最小的元素，將其與a[0]交換，然后將基準位置右 移一位，重復上面的動作，比如，以a[1]為基準，找出a[1]至a[9]中最小的，將其與a[1]交換，一直進行到基準位置移到數組最后一個元素時排序結束（此時基準左邊所有元素均遞增有序，而基準為最后一個元素，故完成排序）。4.直接插入排序算法 直接插入排序是一種最簡單的排序方法，它的基本操作是將一個記錄插入到已排好序的有序表中，從而得到一個新的，記錄數增1的有序表。 一般情況下，第i趟直接插入排序的操作為：在含有i-1個記錄的有序子序列r[1...i-1]中插入一個記錄r[i]后，變成含有i個記錄的有序子序列r[1....i].在自i-1起往前搜索的過程中，可以同時后移記錄。 整個排序過程為進行n-1躺插入，即：先將序列中的第一個記錄看成是一個有序的子序列，然后從第二個記錄起逐個進行插入，直至整個序列變成按關鍵字非遞減有序序列為止 三、程序源代碼 1.二叉排序樹的創建、遍歷和查找刪除算法 #include void Insert(Tree &T,KeyType key){ if(!T){ T=new LNode;T->data=key;T->lchild=T->rchild=NULL;} else } { } if(key } int num;char c;while(scanf(“%d”,&num)){ } Insert(T,num);c=getchar();if(c=='n')return;void In_Order(Tree T)//中序遍歷 { if(T){ In_Order(T->lchild);printf(“%d ”,T->data);} In_Order(T->rchild);} void Delete(Tree &p){ Tree q,s;if(!p->rchild){ q = p;p=p->lchild;free(q);} else if(!p->lchild){ } q = p;p=p->rchild;free(q); else { } q = p;s = p->lchild;while(s->rchild){ } q = s;s = s->rchild;p->data = s->data;if(q!=p)q->rchild = s->lchild;else q->lchild = s->lchild;free(s);} void DelNode(Tree &T,KeyType key){ } if(!T){ printf(“n該結點不存在n”);return;} else { } if(key == T->data)Delete(T);else if(key < T->data)DelNode(T->lchild, key);else DelNode(T->rchild,key);Tree Search(Tree T,KeyType key)//二叉排序樹查找 { if(!T){ } printf(“該結點不存在”);return 0;else if(key == T->data)return T;else if(key < T->data) return(Search(T->lchild, key));else return(Search(T->rchild, key));} int main()//主函數 { Tree T,p;T=NULL;KeyType x; printf(“請輸入二叉樹各結點：n”); CreatTree(T); printf(“中序遍歷為：n”);In_Order(T);printf(“n請輸入要查找和刪除的結點：n”);scanf(“%d”,&x);p=Search(T, x);if(p){ } DelNode(T, x);printf(“中序遍歷為：n”);In_Order(T); } 2、冒泡排序和折半查找算法 #include int BubbleSort(int c[]){ int i,t,j;for(i=0;i<9;i++){ } for(j=0;j<9-i;j++){ } if(c[j]>c[j+1]){ } t=c[j];c[j]=c[j+1];c[j+1]=t; printf(“n您所輸入的數字的升序排列是:nn”);for(i=0;i<10;i++){ printf(“%d”,c[i]);printf(“ ”);} return 1;} //折半查找 int BinarySearch(int b[]){ } int t,mid;int i=0;int j=9;printf(“nn請輸入您要查找的數字：”);scanf(“%d”, &t);while(i<=j){ mid=i+(j-i)/2; } return 1;if(t==b[mid]){ printf(“n您要查找的數字的排列位置是：%dn”,mid+1);break;} else if(t int main(int argc,char *argv[]){ int a[10];printf(“請您輸入數據:nn”);for(int i=0;i<10;i++){ scanf(“%d”,&a[i]); } } BubbleSort(a);BinarySearch(a);return 0; 3、簡單選擇排序和簡單插入排序算法 #include int i,j,min,p,key,k; for(i=0;i { key=0; min=a[i]; } for(j=i;j if(a[j] if(key==1){a[p]=a[i]; a[i]=min;} for(k=0;k printf(“%d ”,a[k]);printf(“n”); return 1;} int InserSort(int*a,int n){ int i,j,k;for(i=2;i<=n;i++){ a[0]=a[i];for(j=1;j { if(a[j]>a[i]){for(k=i;k>j;k--) a[k]=a[k-1]; a[k]=a[0]; } } break;} } for(j=1;j<=n;j++){ } printf(“%d ”,a[j]);printf(“n”);return 1;int main(){ int a[80],i,n,b;printf(“請輸入關鍵字的個數：”);scanf(“%d”,&n);printf(“排序類型：n”);printf(“1.選擇排序n”);printf(“2.插入排序n”);printf(“請選擇：”);scanf(“%d”,&b);switch(b){ case 1: printf(“請輸入關鍵字：n”);for(i=0;i SelectionSort(a,n); return 1; break; case 2: printf(“請輸入關鍵字：n”); for(i=1;i<=n;i++){ scanf(“%d”,&a[i]);} printf(“插入排序的流程以及結果：n”); InserSort(a,n);return 1; } break;}while(a!=0); 四、實驗運行結果 1.二叉排序樹的創建、遍歷和查找刪除算法 2、冒泡排序和折半查找算法 3、簡單選擇排序和簡單插入排序算法 七、心得體會 通過本次的數據結構課程設計報告，掌握了查找和排序的幾種基本排序算法，了解了他們各自的特點和優缺點，完成了對于他們C語言的描述和實際應用，對他們有了一個更加具體、深刻的認識，同時也鍛煉了我們的邏輯思維能力和動手實踐能力，使我們受益匪淺，給我們今后的計算機專業課程學習帶來很大的幫助。 武漢理工大學《數據結構》課程設計說明書 課程設計任務書 學生姓名： 劉穎 專業班級： 計科1003班 指導教師： 譚新明 工作單位： 計算機科學系 題 目: 哈希表的設計與實現 初始條件： 針對某個集體（比如你所在的班級）中的“人名”設計并實現一個哈希表，使得平均查找長度不超過R，完成相應的建表和查表程序。 （1）假設人名為中國人姓名的漢語拼音形式。待填入哈希表的人名共有30個，取平均查找長度的上限為2。 （2）哈希函數用除留余數法構造 （3）用偽隨機探測再散列法處理沖突。 （4）測試用例見嚴蔚敏《數據結構習題集(C語言版)》p166。 要求完成的主要任務:（包括課程設計工作量及其技術要求，以及說明書撰寫等具體要求） 課程設計報告按學校規定格式用A4紙打印（書寫），并應包含如下內容： 1.問題描述 簡述題目要解決的問題是什么。2.設計 存儲結構設計、主要算法設計（用類C/C++語言或用框圖描述）、測試用例設計； 3.調試報告 調試過程中遇到的問題是如何解決的；對設計和編碼的討論和分析。4.經驗和體會（包括對算法改進的設想） 5.附源程序清單和運行結果。源程序要加注釋。如果題目規定了測試數據，則運行結果要包含這些測試數據和運行輸出。 說明： 1.設計報告、程序不得相互抄襲和拷貝；若有雷同，則所有雷同者成績均為0分。2.凡拷貝往年任務書或課程設計充數者，成績一律無效，以0分記。 時間安排： 1、6月15日～6月21日完成。2、6月22日上午和下午在實驗中心檢查程序、交課程設計報告、源程序（U盤）。 指導教師簽名： 2012年6月14日 系主任（或責任教師）簽名： 年 月 日 武漢理工大學《數據結構》課程設計說明書 目錄 1問題分析和任務定義...............................................3 1.1問題描述.......................................................3 1.2問題分析.......................................................3 2開發平臺.........................................................3 3數據類型和系統設計...............................................3 3.1存儲結構設計...................................................3 3.2主要算法設計...................................................4 3.2.1姓名結構體數組初始化.........................................4 3.2.2獲取關鍵碼...................................................5 3.2.3哈希表結構體數組初始化.......................................5 3.2.4構造哈希表...................................................5 3.2.5打印哈希表...................................................6 3.2.6在哈希表中查找姓名...........................................6 4調試結果與運行情況分析...........................................8 4.1程序運行結果...................................................8 4.2運行情況分析...................................................9 4.3算法的時間復雜度...............................................9 5自我評價與總結...................................................9 6參考文獻........................................................10 7附：源代碼......................................................11 武漢理工大學《數據結構》課程設計說明書 哈希表的設計與實現 1問題分析和任務定義 1.1問題描述 設計哈希表，要求用除留余數法構造哈希函數，用偽隨機探測再散列法處理沖突，使平均查找長度的上限為2。待填入哈希表的人名共有30個，且為中國人姓名的漢語拼音形式。 1.2問題分析 （1）待填入哈希表的人名有30個，平均查找長度的上限為2。用除留余數法構造哈希表，用偽隨機探測再散列法處理沖突，完成相應的建立和查表程序。 （2）人名為漢語拼音形式，最長不超過20個字符。 （3）查找成功時，顯示姓名、關鍵字、初散列值、再散列值、哈希表中的位置及查找長度；查找失敗時，顯示無此記錄。 （4）可多次查找，繼續查找輸入1，退退出輸入0。 2開發平臺 系統：Windows 7 開發工具：Visual studio 2008 語言：C++ 3數據類型和系統設計 3.1 存儲結構設計 typedef struct { int key; char *p;}NAME; 武漢理工大學《數據結構》課程設計說明書 typedef struct { int key;//關鍵字 int hash;//初始地址 int reha;//再散列值 char *p;//名字 int l;//查找長度 }HASH;3.2主要算法設計 3.2.1 NAME（結構體數組）初始化 NAME a[30];a[0].p=“wangjunzhe”;a[1].p=“mahaiping”;a[2].p=“luozijian”;a[3].p=“luoxiangzhou”;a[4].p=“zhangkai”;a[5].p=“fengyuyang”;a[6].p=“wuzhenzhen”;a[7].p=“haokaiqi”;a[8].p=“caopu”;a[9].p=“liuying”;a[10].p=“cuijuan”;a[11].p=“hanqianqiqn”;a[12].p=“lixiaoyu”;a[13].p=“caoyingnan”;a[14].p=“jinbaoyu”;a[15].p=“zhaduo”;a[16].p=“wenbo”;a[17].p=“cuichangwei”;a[18].p=“zhangqiu”;a[19].p=“luopeng”;a[20].p=“hudie”;a[21].p=“xieshanshan”;a[22].p=“liming”;a[23].p=“zhangshuai”;a[24].p=“qiuyajun”;a[25].p=“yanruibin”;a[26].p=“jiangwei”;a[27].p=“fangzhaohua”;a[28].p=“yujia”; 武漢理工大學《數據結構》課程設計說明書 a[29].p=“liuzhenzhen”;3.2.2獲取關鍵碼 字符串的各個字符所對應的ASCII碼相加，所得的整數做為關鍵字。 int i,s,r;for(i=0;i<30;i++){ s=0;for(r=0;*(a[i].p+r)!='
主站蜘蛛池模板：
乱人伦xxxx国语对白|
一区二区三区国产精品保安|
夜夜躁很很躁日日躁麻豆|
国产成人+亚洲欧洲+综合|
香港三级韩国三级日本三级|
动漫精品无码h在线观看|
日本极品少妇videossexhd|
亚洲国产精品无码中文在线|
久久9精品区-无套内射无码|
国产美女口爆吞精普通话|
亚洲高请码在线精品av|
中文字幕人妻中文|
人妻熟女久久久久久久|
亚洲国产精品久久久久制服|
日韩在线不卡免费视频一区|
国产精品久久久久久av福利|
欧美中文亚洲v在线|
天堂…中文在线最新版在线|
中文字幕欧美人妻精品一区|
亚洲乳大丰满中文字幕|
天天鲁在视频在线观看|
99精品丰满人妻无码a片|
少妇高潮毛片免费看|
国产女人精品视频国产灰线|
国语自产精品视频在线区|
婷婷中文字幕综合在线|
在线日韩日本国产亚洲|
av无码精品一区二区三区宅噜噜|
国语精品自产拍在线观看网站|
国产成人高清亚洲一区|
国产精品线路一线路二|
久久无码人妻一区二区三区午夜|
亚洲中文无码精品卡通|
忘忧草社区在线播放日本韩国|
天天综合亚洲色在线精品|
国产成人精品无码片区在线观看|
精品国产这么小也不放过|
免费99精品国产自在在线|
久久国产精品老女人|
亚洲va久久久噜噜噜久久4399|
久久久久成人精品免费播放动漫|
第三篇：數據結構課程設計之姓名哈希表的建立及查找