|
|
HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY
數(shù)據(jù)結(jié)構(gòu)
課程設(shè)計(jì)報(bào)告
課設(shè)題目：
| | 專(zhuān) 業(yè)：
| | 班 級(jí)：
| | 姓 名：
| | 完成日期：
| | 指導(dǎo)教師：
| |
一．設(shè)計(jì)題目
Ø課程設(shè)計(jì)題目：多種查找方式的比較
Ø實(shí)現(xiàn)的功能：
1. 順序查找
2. 二分查找
3. 哈希查找
v順序查找
1. 隨機(jī)產(chǎn)生隨機(jī)數(shù) 2. 手動(dòng)輸入產(chǎn)生隨機(jī)數(shù) 3. 建立線性表進(jìn)行順序查找
v二分查找
1. 隨機(jī)產(chǎn)生隨機(jī)數(shù) 2. 對(duì)產(chǎn)生的隨機(jī)數(shù)進(jìn)行冒泡排序（由大到小） 3. 進(jìn)行二分查找
v哈希查找
1.手動(dòng)輸入產(chǎn)生隨機(jī)數(shù) 2. 進(jìn)行哈希查找
Ø各種查找的簡(jiǎn)單介紹：
1> 順序查找
查找是在程序設(shè)計(jì)中最常用到的算法之一，假定要從n個(gè)整數(shù)中查找x的值是否存在，
最原始的辦法是從頭到尾逐個(gè)查找，這種查找的方法稱(chēng)為順序查找。
順序查找的程序如下：
# include <stdio.h>
# define N 15
int main(void)
{
void bi_search(int a[],int n,int x);
int a[100];
int x, i;
int n = 15;
printf("input the numbers:\n");
for(i=0; i<n;i++ )
scanf("%d",&a)
printf("input x:\n");
scanf("%d", &x);
bi_search(a,n,x);
}
void bi_search(int a[], int n, int x)
{
int i = 0;
int find = 0;
while(i<n)
{
if(x==a)
{
printf("find:%3d,it is a[%d]",x,i);
printf("\n");
find = 1;
}
i++;
if(i!=find)
printf("%3d not been found!\n", x);
}
2> 二分查找
/* 當(dāng)前查找區(qū)間R[low..high]非空,使用(low+high)/2會(huì)有整數(shù)溢出的問(wèn)題,問(wèn)題
會(huì)出現(xiàn)在當(dāng)low+high的結(jié)果大于表達(dá)式結(jié)果類(lèi)型所能表示的最大值時(shí)，這樣，產(chǎn)生
溢出后再/2是不會(huì)產(chǎn)生正確結(jié)果的，而low+((high-low)/2)不存在這個(gè)問(wèn)題*/
int BinSearch(SeqList*R, int n, KeyType K)
{
/* 在有序表R[0..n-1]中進(jìn)行二分查找，成功時(shí)返回結(jié)點(diǎn)的位置，失敗時(shí)返回-1 */
int low = 0, high = n-1, mid; /* 置當(dāng)前查找區(qū)間上、下界的初值 */
while(low <= high)
{
if(R[low].key == K)
return low;
if(R[high].key == k)
return high;
mid = low+((high-low)/2);
if(R[mid].key == K)
return mid;//查找成功返回
if(R[mid].key > K)
high = mid-1;//繼續(xù)在R[low..mid-1]中查找
else
low = mid+1;//繼續(xù)在R[mid+1..high]中查找
}
if(low > high)
return-1;//當(dāng)low>high時(shí)表示所查找區(qū)間內(nèi)沒(méi)有結(jié)果，查找失敗
}
3> 哈希查找
① 常用的哈希函數(shù)構(gòu)造方法有：
l直接定址法
l除留余數(shù)法
l乘余取整法
l數(shù)字分析法
l平方取中法
l折疊法
l隨機(jī)數(shù)法
② 本程序采用的是除留余數(shù)法:
Hash(key)=key mod p (p是一個(gè)整數(shù))
2特點(diǎn)：以關(guān)鍵碼除以p的余數(shù)作為哈希地址。
2關(guān)鍵：如何選取合適的p？p選的不好，容易產(chǎn)生同義詞
2技巧：若設(shè)計(jì)的哈希表長(zhǎng)為m，則一般取p≤m且為質(zhì)數(shù)
（也可以是合數(shù)，但不能包含小于20的質(zhì)因子）。
二．設(shè)計(jì)目的
通過(guò)此三種算法的比較，突出各自的優(yōu)缺點(diǎn):
順序查找過(guò)程：從表中的最后一個(gè)記錄開(kāi)始，逐個(gè)進(jìn)行記錄的關(guān)鍵字與給定值進(jìn)行比較，若某個(gè)記錄的關(guān)鍵字與給定值相等，則查找成功，找到所查的記錄；反之，若直到第一個(gè)記錄，其關(guān)鍵字和給定值比較都不相等，則表明表中沒(méi)有所查的記錄，查找失敗。
算法描述為
int Search(int d,int a[],int n)
{
/*在數(shù)組a[]中查找等于D元素，若找到，則函數(shù)返回d在數(shù)組中的位置，否則為0。其中n為數(shù)組長(zhǎng)度*/
int i ；
/*從后往前查找*/
for(i=n-1;a!=d;--i)
return i ;
/*如果找不到，則i為0*/
}
此算法在數(shù)據(jù)的復(fù)雜度比較小的時(shí)候比較方便和占有優(yōu)勢(shì)，但當(dāng)查找的數(shù)據(jù)量很龐大時(shí)，此算法就顯得有點(diǎn)不適用了。
二分查找又稱(chēng)折半查找，它是一種效率較高的查找方法。
其流程圖如下：
【二分查找要求】 1. 必須采用順序存儲(chǔ)結(jié)構(gòu) 2. 必須按關(guān)鍵字大小有序排列。
【優(yōu) 缺 點(diǎn)】 折半查找法的優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，平均性能好;其缺點(diǎn)是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表。
哈希查找
1. 基本原理
我們使用一個(gè)下標(biāo)范圍比較大的數(shù)組來(lái)存儲(chǔ)元素。可以設(shè)計(jì)一個(gè)函數(shù)（哈希函數(shù)， 也叫做散列函數(shù)），使得每個(gè)元素的關(guān)鍵字都與一個(gè)函數(shù)值（即數(shù)組下標(biāo)）相對(duì)應(yīng)，于是用這個(gè)數(shù)組單元來(lái)存儲(chǔ)這個(gè)元素；也可以簡(jiǎn)單的理解為，按照關(guān)鍵字為每一個(gè)元素"分類(lèi)"，然后將這個(gè)元素存儲(chǔ)在相應(yīng)"類(lèi)"所對(duì)應(yīng)的地方。
但是，不能夠保證每個(gè)元素的關(guān)鍵字與函數(shù)值是一一對(duì)應(yīng)的，因此極有可能出現(xiàn)對(duì)于不同的元素，卻計(jì)算出了相同的函數(shù)值，這樣就產(chǎn)生了"沖突"，換句話說(shuō)，就是把不同的元素分在了相同的"類(lèi)"之中。后面我們將看到一種解決"沖突"的簡(jiǎn)便做法。
總的來(lái)說(shuō)，"直接定址"與"解決沖突"是哈希表的兩大特點(diǎn)。
2. 函數(shù)構(gòu)造
構(gòu)造函數(shù)的常用方法（下面為了敘述簡(jiǎn)潔，設(shè) h(k) 表示關(guān)鍵字為 k 的元素所對(duì)應(yīng)的函數(shù)值）：
a) 除余法：
選擇一個(gè)適當(dāng)?shù)恼麛?shù) p ，令 h(k ) = k mod p
這里， p 如果選取的是比較大的素?cái)?shù)，效果比較好。而且此法非常容易實(shí)現(xiàn)，因此是最常用的方法。
三．總體設(shè)計(jì)
Ø程序框架圖：
Ø函數(shù)調(diào)用流程圖：
四．詳細(xì)設(shè)計(jì)步驟
1.搭建程序的整個(gè)框架
# include<stdio.h>
void printSeq();//隨機(jī)順序查找法
void printBin();//二分查找法
void hashtable();//哈希查找
int main(void)
{
return 0;
}
printSeq();//隨機(jī)順序查找法
{
}
printBin();//二分查找法
{
}
hashtable();//哈希查找
{
}
2.頭文件的添加
# include "iostream"
# include "stdlib.h"
# include "stdio.h"
# include <time.h>
# include "malloc.h"//動(dòng)態(tài)內(nèi)存分配的頭文件
3.定義相關(guān)的結(jié)構(gòu)體數(shù)據(jù)類(lèi)型
using namespace std;
typedef int ElemType; //ElemType類(lèi)型為int類(lèi)型 即ElemType等價(jià)于int
int size = 0; //哈希表的長(zhǎng)度
4.相關(guān)參數(shù)的宏定義
# define maxsize 100
# define m 19 //m = 19
# define free 0 //free = 0
# define sucess 1 //sucess = 1
# define unsucess 0 //unsucess = 0
# define MAX 11 //MAX = 11
# define hm 20 //hm = 20
# define keytype int //keytype類(lèi)型為int型
5.主函數(shù)中調(diào)用其它功能模塊的函數(shù)
6.寫(xiě)出主函數(shù)中被調(diào)用的函數(shù)
üvoid printSeq()//隨機(jī)順序查找法
üvoid printBin()//二分查找法
üvoid hashtable()//哈希查找
üvoid Sort(SSTable *table )
üvoid stable create_s(stable r)
üvoid PrintTable(SSTable *table)
üvoid Destroy(SSTable *table)/* 函數(shù)：銷(xiāo)毀 */
üvoid FillTable(SSTable *table)/* 函數(shù)：判斷是否已滿 */
üvoid Create(SSTable **table, int length)/* 創(chuàng)建 */
üvoid hashcreate(hashtable ht[], keytype key)
üvoid search_shoudong()//隨機(jī)順序手動(dòng)查找法
üint show()
üint search_s(keytype k,stable *r)
üint HashFunction(keytype key)/*散列函數(shù)*/
üint hashsearch(hashtable ht[], keytype key)
üint Search_Bin(SSTable *table, ElemType key)
üint Search_Seq(SSTable *table, ElemType key)/* 函數(shù)：查找 */
7.先寫(xiě)出相關(guān)被調(diào)函數(shù)的偽代碼
舉例：判斷建立的時(shí)間表是否已滿
If（時(shí)間表長(zhǎng)度為滿）
Printf(“創(chuàng)建失敗！\n”);
else
Printf(“創(chuàng)建成功！\n”);
8.用C或C++……等語(yǔ)言將偽代碼描述出來(lái)
9.若被調(diào)函數(shù)放在主函數(shù)之后，則要進(jìn)行函數(shù)的聲明；相反則不需要
10.進(jìn)行程序的簡(jiǎn)單調(diào)試及修改
11.對(duì)用戶的違法輸入的操作的調(diào)試及修改
12.進(jìn)一步的對(duì)程序中的bug進(jìn)行調(diào)試及修改
13.功能的進(jìn)一步擴(kuò)充及完善
五．設(shè)計(jì)結(jié)果與分析
1)設(shè)計(jì)的運(yùn)行結(jié)果
2運(yùn)行菜單的主界面：
2順序查找界面：
u順序隨機(jī)查找的三種調(diào)試結(jié)果：
u順序手動(dòng)輸入查找的三種調(diào)試結(jié)果：
2二分查找界面：
2哈希查找界面：
2) 調(diào)試分析
l調(diào)試時(shí)注意哪些問(wèn)題
1. 除了輸入的信息提示外還可以進(jìn)行非法的輸入
2. 對(duì)垃圾的垃圾字符的回收
3. 注意緩沖和清屏
l如何去調(diào)試程序
1. 調(diào)試時(shí)具有隨機(jī)性和非法性輸入
2. 調(diào)試的結(jié)果不能太單一，如產(chǎn)生的隨機(jī)種子要有正、負(fù)數(shù)和零
l如何去修改程序的bug（漏洞）
1. 一個(gè)好的程序是調(diào)試出來(lái)的
2. 邊試邊調(diào)試不斷地修改
3. 通過(guò)非法或任意輸入來(lái)修改程序的漏洞
l如何去排除掉用戶的非法輸入
1. 對(duì)輸入的垃圾字符進(jìn)行回收
2. 對(duì)相關(guān)的菜單界面進(jìn)行緩沖和清屏
3. 調(diào)試程序時(shí)要全面，防止出現(xiàn)用戶的非法輸入
l如何去使自己的程序更全面
1. 不斷地調(diào)試和完善
2. 通過(guò)不同的用戶來(lái)調(diào)試反饋相關(guān)問(wèn)題并完善之
3. 使程序更加精簡(jiǎn)和通俗易懂
l找用戶進(jìn)行調(diào)試來(lái)反饋問(wèn)題
1. 這是一個(gè)產(chǎn)品進(jìn)入市場(chǎng)前的一個(gè)關(guān)鍵步驟，如一款游戲或軟件會(huì)標(biāo)注試用版，通
過(guò)用戶的試用來(lái)反饋一些問(wèn)題
l進(jìn)一步完善程序中的漏洞
[color=#ff0000,strength=3)"]六．總結(jié)（收獲和不足）
總結(jié)是對(duì)所學(xué)的知識(shí)的一種總結(jié)，是一種很好的學(xué)習(xí)方法，不管是現(xiàn)在的學(xué)習(xí)總結(jié)還是今后走向工作崗位時(shí)的工作總結(jié)都會(huì)讓自己受益匪淺。
通過(guò)多天的漫長(zhǎng)學(xué)習(xí)，自己和組員終于完成了此課程設(shè)計(jì)，自己不斷是收獲了知識(shí)也收獲了團(tuán)隊(duì)精神。
大的程序的開(kāi)發(fā)周期都是很漫長(zhǎng)的，長(zhǎng)的會(huì)達(dá)兩年或兩年以上的開(kāi)發(fā)期。所以一個(gè)人是無(wú)法完成這樣巨大的工作量的，必須靠一個(gè)團(tuán)隊(duì)去完成。俗話說(shuō)：“三個(gè)臭皮匠賽過(guò)諸葛亮”，這句話是很有道理的，自己的能力即使很強(qiáng)，也要靠團(tuán)隊(duì)去完成。不過(guò)話說(shuō)回來(lái)，現(xiàn)在的這種意識(shí)還不是很強(qiáng)，搞技術(shù)的很多人更多的是個(gè)人的抱負(fù)。希望自己能搞出點(diǎn)驚天動(dòng)地的東西出來(lái)，但是要是在公司的話，這絕對(duì)是不允許的。因?yàn)楣鹃_(kāi)發(fā)一個(gè)產(chǎn)品的周期時(shí)間還有限的，需要一個(gè)團(tuán)隊(duì)在最短的時(shí)間內(nèi)去完成產(chǎn)品的設(shè)計(jì)。
從這次的數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)過(guò)程中深有體會(huì)，如何更好地去完成一個(gè)大的程序，就像開(kāi)發(fā)一個(gè)大的軟件。得有明確的分工，所以我們要去了解程序的特點(diǎn)，其中函數(shù)和指針是很有用的東西，通過(guò)這些可以將很大的程序高效的完成。
這就像好比開(kāi)發(fā)一個(gè)大的軟件，項(xiàng)目的負(fù)責(zé)人將程序的主框架搭好，定義一些全局變量，并，列舉出要調(diào)用的功能函數(shù)名稱(chēng)，項(xiàng)目負(fù)責(zé)組只要完成主函數(shù)的調(diào)用很簡(jiǎn)單的編寫(xiě)。而那些功能函數(shù)模塊則交給下面那些程序員來(lái)分組完成。最后將所有的功能函數(shù)整合到一起。一個(gè)大的軟件的開(kāi)發(fā)過(guò)程就完成的四分之一了。還有二分之一的時(shí)間是來(lái)調(diào)試錯(cuò)誤和完善功能，所以說(shuō)好的程序不是寫(xiě)出來(lái)的而是調(diào)試出來(lái)的。所以我們小組三人在這次程序調(diào)試過(guò)程中實(shí)現(xiàn)了很好的分工，老師看完程序后要求進(jìn)行三個(gè)功能方面的修改：1. 程序產(chǎn)生的隨機(jī)數(shù)是隨機(jī)的要包括正、負(fù)數(shù)和零。 2. 查找實(shí)現(xiàn)隨機(jī)查找和手動(dòng)輸入查找。 3.對(duì)二分查找中的冒泡排序由低到高排序改為從高到低排序。 4. 完善哈希查找的功能。
我們小組進(jìn)行了分工，每人完成一個(gè)功能的修改，最后整合到一個(gè)程序中。我們很快各自完成了自己的那塊，最后整合到了一起。當(dāng)然由于能力的有限，小組對(duì)最后的哈希查找功能的完善沒(méi)有實(shí)現(xiàn)。最后在驗(yàn)收的過(guò)程中還是通過(guò)了。
當(dāng)然此次的課程設(shè)計(jì)走了很多彎路，在剛開(kāi)始的時(shí)候沒(méi)有確定目標(biāo)對(duì)象，所以導(dǎo)致了后面出現(xiàn)了兩個(gè)備案，兩個(gè)任務(wù)進(jìn)行來(lái)回之間的切換，造成了時(shí)間的浪費(fèi)。這是我們此次學(xué)習(xí)過(guò)程中吸取的一個(gè)教訓(xùn)。
通過(guò)此次的課程設(shè)計(jì)，自己對(duì)數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)和理解又上升了一個(gè)層次，自己不斷地在進(jìn)步。自己所希望對(duì)的就是要達(dá)到這個(gè)效果。
此次的學(xué)習(xí)讓自己意識(shí)到很多方面的不足，對(duì)哈希查找和二叉樹(shù)的相關(guān)知識(shí)還不夠熟悉，導(dǎo)致最后一個(gè)功能模塊沒(méi)能很好的完成，所以后面還需要不斷地學(xué)習(xí)。這門(mén)課程是計(jì)算機(jī)課程中的一門(mén)核心課程，學(xué)完后感覺(jué)眼界大開(kāi)。
學(xué)完這門(mén)課程后，對(duì)函數(shù)的理解又上升了一個(gè)層次。原來(lái)在學(xué)習(xí)C語(yǔ)言時(shí)還不懂什么是函數(shù)，也不知道函數(shù)是用來(lái)干什么的。那時(shí)區(qū)分不清楚編程中的函數(shù)與數(shù)學(xué)中的函數(shù)有什么區(qū)別。所以當(dāng)我們對(duì)一個(gè)東西不理解時(shí)，我們是無(wú)法去駕馭它的，更談不上去編寫(xiě)出優(yōu)秀的代碼。
學(xué)習(xí)編程是一個(gè)漫長(zhǎng)的過(guò)程，從大一的文盲到現(xiàn)在的菜鳥(niǎo)是一種進(jìn)步，是一個(gè)漫長(zhǎng)的過(guò)程，也是一個(gè)漫長(zhǎng)的積累。自己在這方面走了不少?gòu)澛罚蚕铝瞬簧俟Ψ颍切Ч皇呛苊黠@。
在后面的學(xué)習(xí)過(guò)程中，這門(mén)課程的地位依然是顯得那么重要，后面的計(jì)算機(jī)課程、單片機(jī)學(xué)習(xí)課程是和數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)是離不開(kāi)的。
說(shuō)了這么還是說(shuō)明了這門(mén)課程的重要性，要學(xué)好這門(mén)課程，不是一兩年就能搞定的，要不斷的運(yùn)用到實(shí)踐中和反復(fù)的去理解和體會(huì)。
還有一點(diǎn)是：老師上課講的更多是偽代碼而不是實(shí)際程序，理解一個(gè)偽代碼幾分鐘就可以搞定，但是理解代碼的話不就那么簡(jiǎn)單了。要把它寫(xiě)出來(lái)更是難上加難了。所以不能停留在表面，程序必須要自己去寫(xiě)和調(diào)試，這樣才能真正的理解和掌握，不然永遠(yuǎn)都不可能寫(xiě)出一手好的代碼。
通過(guò)數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)，自己對(duì)計(jì)算機(jī)的底層一些東西也是有了一些理解。如，偽代碼、編譯和鏈接等等。
“偽代碼”很明顯是假代碼的意思，它是由編譯器來(lái)識(shí)別的，計(jì)算機(jī)是不承認(rèn)它的，因?yàn)橛?jì)算機(jī)跑的只有“0”和“1”，這些偽代碼當(dāng)然有它的作用，它會(huì)告訴編譯器從何處執(zhí)行，執(zhí)行到何處時(shí)該怎么辦。
所以通過(guò)數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)將前前后后的知識(shí)都穿插了起來(lái)，就像指針一樣。前前后后學(xué)習(xí)的知識(shí)是離散的，分布在大腦的各個(gè)部分，數(shù)據(jù)結(jié)構(gòu)就好比這個(gè)指針，將它們前前后后串起來(lái)了。這是比較有意思的，似乎好多的東西和思想是相通的，不管是什么專(zhuān)業(yè)領(lǐng)域。可謂“萬(wàn)變不離其宗”。
[color=#ff0000,strength=3)"]附源代碼：
/*
課題名稱(chēng)：各種查找方法的比較
小組成員：曾奕云 袁能峰 汪一帆
時(shí) 間：2014年7月5日
*/
# include "iostream"
# include "stdlib.h"
# include "stdio.h"
# include "malloc.h"//動(dòng)態(tài)內(nèi)存分配的頭文件
# define MAX 11 //MAX = 11
# define hm 20 //hm = 20
using namespace std;
# include <time.h>
typedef int ElemType; //ElemType類(lèi)型為int類(lèi)型 即ElemType等價(jià)于int
# define keytype int //keytype類(lèi)型為int型
#define maxsize 100
# define m 19 //m = 19
# define free 0 //free = 0
# define sucess 1 //sucess = 1
# define unsucess 0 //unsucess = 0
int size = 0; //哈希表的長(zhǎng)度
/*定義一個(gè)名為sstable結(jié)構(gòu)體數(shù)據(jù)類(lèi)型 包含兩部分int *elem 和 int length */
typedef struct sstable
{
ElemType *elem;
ElemType length;
} SSTable; //SSTable 等價(jià)于 struct sstable
typedef struct hashtable
{
keytype key;
}hashtable;//hashtable 等價(jià)于 struct hashtable
/*順序表結(jié)構(gòu)體定義*/
typedef struct
{
keytype key[maxsize];
int len;
}stable;
int show();
void Create(SSTable *table, int length);//創(chuàng)建
void Destroy(SSTable *table);//銷(xiāo)毀
int Search_Seq(SSTable *table, ElemType key);//查找 有返回值
/* 創(chuàng)建 */
void Create(SSTable **table, int length)
{
SSTable *t = (SSTable*) malloc(sizeof(SSTable));
t->elem = (ElemType*)malloc(sizeof(ElemType)*(length+1));
t->length = length;
*table = t;
}
/* 函數(shù)：判斷是否已滿 */
void FillTable(SSTable *table)
{
ElemType *t = table->elem;
srand(time(NULL));
for(int i=0; i<table->length; i++)
{
t++;
*t = 90-rand()%100;
}
}
/* 函數(shù)：銷(xiāo)毀 */
void Destroy(SSTable *table)
{
free(table->elem); //先保存后釋放
free(table);
}
/* 函數(shù)：顯示 */
void PrintTable(SSTable *table)
{
int i;
ElemType *t = table->elem;
for(i=0; i<table->length; i++)//進(jìn)入循環(huán)，依次打印表中元素
{
t++;
printf("%d ", *t);
}
printf("\n");
}
/* 函數(shù)：查找 */
int Search_Seq(SSTable *table, ElemType key)
{
int result;
int i;
for (i=table->length; i>=1; i--)
{
if (table->elem==key)
{
result = i;
break;
}
}
return result; //將result的只返回到函數(shù)：順序查找 void printSeq()
}
/* 順序查找 */
void printSeq()
{
SSTable *table;
int r;
int n;
ElemType key;//等價(jià)于int key;
printf("請(qǐng)輸入元素個(gè)數(shù):");
scanf("%d", &n);
rewind(stdin);/* 清緩沖 */
Create(&table, n); //隨機(jī)創(chuàng)建 n 個(gè)元素
FillTable(table); //判斷所輸入的個(gè)數(shù) n 是否溢出
printf("您輸入的%d 個(gè)值是：", n);
PrintTable(table);
printf("請(qǐng)輸入關(guān)鍵字的值:");
scanf("%d", &key);
rewind(stdin);/* 清緩沖 */
printf("\n");
printf("順序查找法運(yùn)行結(jié)果如下：\n\n ");
Search_Seq(table, key);
r = Search_Seq(table, key);
if(r > 0)
{
printf("關(guān)鍵字%d 在表中的位置是：%d\n", key, r);
printf("\n");
system("pause");
system("cls");
}
else
{
printf ("查找失敗，表中無(wú)此數(shù)據(jù)。\n\n");
system("pause");
system("cls");
}
}
/* 函數(shù)：冒泡排序 */
void Sort(SSTable *table )
{
int i, j;
ElemType temp;
for (i=table->length; i>=1; i--)
{
for (j=1; j<i; j++)
{
if(table->elem[j]<table->elem[j+1])
{
temp = table->elem[j];
table->elem[j] = table->elem[j+1];
table->elem[j+1] = temp;
}
}
}
}
/* 函數(shù)：二分法查找 */
int Search_Bin(SSTable *table, ElemType key)
{
int low = 1;
int high = table->length;
int result = 0;
while(low <= high)
{
int mid = (low+high)/2;
if(table->elem[mid]==key)
{
result = mid;
break;
}
else if(key<table->elem[mid])
{
low = mid+1;
}
else
{
high = mid-1;
}
}
return result;
}
/* 函數(shù)：二分法查找、排序及輸出 */
void printBin()
{
SSTable *table;
int r;
int n;
ElemType key;
printf("請(qǐng)輸入元素個(gè)數(shù):");
scanf("%d", &n);
if (n<0)
{
printf("輸入有誤，請(qǐng)重新選擇!\n");
system("pause");
system("cls");
n = show();
system("pause");
system("cls");
printf("\n");
}
else
{
Create(&table, n);
FillTable(table);
printf("您輸入的%d 個(gè)值是：\n",n);
PrintTable(table);
printf("請(qǐng)輸入關(guān)鍵字的值:");
scanf("%d", &key);
rewind(stdin);/* 清緩沖 */
printf("\n");
Sort(table);
printf("數(shù)據(jù)排序后的順序如下：\n\n ");
PrintTable(table);
printf("\n");
printf("二分查找法的運(yùn)行結(jié)果如下：\n\n ");
r = Search_Bin(table, key);
if( r > 0)
{
printf("關(guān)鍵字%d 在表中的位置是：%d\n", key, r);
system("pause");
system("cls");
}
else
{
printf ("查找失敗，表中無(wú)此數(shù)據(jù)。\n\n");
system("pause");
system("cls");
}
}
}
/*散列函數(shù)*/
int HashFunction(keytype key)
{
return key % (hm - 5);
}
/*創(chuàng)建hash表*/
void hashcreate(hashtable ht[], keytype key)
{
int index = HashFunction(key);
if(size == hm-1 || ht[index].key == key) //hash表已滿
return;
//無(wú)沖突
if(ht[index].key==0)
ht[index].key = key;
else//沖突
{
do{
index = (index + 1) % hm; //解決沖突函數(shù)
}while(ht[index].key != 0);
ht[index].key = key;
}
size++;
}
/* 函數(shù)：哈希查找 */
int hashsearch(hashtable ht[], keytype key)
{
int f = 0; //查找失敗次數(shù)
int index = HashFunction(key);
while(f <= hm)
{
if(ht[index].key == key)
return index;
else
index = (index + 1) % hm;
f++;
}
return -1;
}
/* 哈希查找 */
void hashtable()
{
int val;
printf("請(qǐng)輸入要建立哈希表的元素：\n");
scanf("%d", &val);
system("pause");
system("cls");
//1. 建立哈希表
//2. 創(chuàng)建是否成功
//3. 輸入要查找的元素
}
/* 主界面菜單 */
int show()
{
int i = -1;
printf("\n\n\n\n\n");
printf("\t\t\t***********主菜單界面***********\n");
printf("\t\t\t*** ***\n");
printf("\t\t\t*** 1. 順序查找 ***\n");
printf("\t\t\t*** 2. 二分查找 ***\n");
printf("\t\t\t*** 3. 哈希查找 ***\n");
printf("\t\t\t*** 4. 退出程序 ***\n");
printf("\t\t\t*** ***\n");
printf("\t\t\t********************************\n");
printf("\t\t\t請(qǐng)輸入選項(xiàng)(1-4):");
scanf("%d", &i);//輸入要數(shù)字選擇要使用的查找方法
return i;
}
/*建立線性表*/
stable create_s(stable r)
{
int i, j = 0, k = 1;
printf("請(qǐng)輸入順序表元素，要為整形，用空格分開(kāi)，-99為結(jié)束標(biāo)志：\n");
scanf("%d",&i);
while(i!=-99)
{
j++;
r.key[k]=i;
k++;
scanf("%d",&i);
}
r.len=j;
return r;
}
/*手動(dòng)順序表查找*/
int search_s(keytype k,stable *r)
{
int j;
j=r->len;
r->key[0]=k;
while(r->key[j]!=k)
j--;
return j;
}
void search_shoudong()
{
stable a;
int i;
int k;
a = create_s(a);
while(i!=-1)
{
printf("\n輸入待查關(guān)鍵字(輸入-1結(jié)束查找)：");
scanf("%d",&i);
k=search_s(i,&a);
if(i==-1)
{
getchar();
break;
}
if(k==0)
{
printf("順序表中待查元素不存在\n");
}
else
{
printf("順序表中待查元素位置是：%d",k);
printf("\n");
}
}
system("pause");
system("cls");
//1.輸入元素建立線性表
//2.判斷是否建立成功
//3.輸入查找的元素
//4.if(查找成功)
// 輸出查找的結(jié)果
// else
// 查找失敗
}
/* 主函數(shù) */
int main(int argc, char* argv[])
{
int i, choice;
system("color 5");
do
{
i = show();
switch(i)
{
case 1:
printf("\n");
printf("*********************************** 順序查找 *********************************** \n");
printf("查找的方法：1. 隨即查找 2. 手動(dòng)輸入查找 \n");
scanf("%d", &choice);
if(1 == choice)
printSeq();//隨機(jī)順序查找法
else
{
search_shoudong();
}
break;//跳出循環(huán)}
case 2:
printf("\n");
printf("*********************************** 二分查找 *********************************** \n");
printBin();//二分查找法
break; //跳出循環(huán)
case 3:
printf("\n");
printf("*********************************** 哈希查找 *********************************** \n");
hashtable();//哈希查找
break; //跳出循環(huán)
case 4:
printf("\n");
printf("\n歡迎使用該系統(tǒng)，再見(jiàn)!\n");
system("pause");
exit(0);
default:
printf("輸入選項(xiàng)有誤，請(qǐng)重新輸入!\n");
rewind(stdin);//等價(jià)于fflush(stdin);清緩沖 不然輸入垃圾字符就陷入了死循環(huán)
system("pause");
system("cls");
break;
}
}while(i!=4);
return 0;
}
|
|
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
