【正文】 第一篇：數(shù)據(jù)結構實驗8查找的算法 實現(xiàn)順序查找的算法一，實驗目的，深刻理解各種查找算法及其執(zhí)行的過程； 。二，實驗內(nèi)容 實現(xiàn)順序查找的算法編寫一個程序，輸出在順序表{3,6,2,10,1,8,5,7,4,9}中采用順序查找法查找關鍵字5的結果。 實現(xiàn)折半查找算法編寫一個程序，輸出在順序表{1,2,3,4,5,6,7,8,9,10}中采用折半查找方法查找關鍵字9的結果。要求：（1）用非遞歸方法；（2）用遞歸方法。 實現(xiàn)二叉排序樹的基本運算編寫一個程序?qū)崿F(xiàn)二叉排序樹的基本運算，并在此基礎上完成如下功能：（1）由{4,9,0,1,8，6,3,5,2,7}創(chuàng)建一個二叉排序樹bt；（2）判斷bt是否為一棵二叉排序樹（提示：在遍歷過程中檢查是否符合二叉排序樹定義）；（3）采用非遞歸方法查找關鍵字為6的結點，并輸出其查找路徑（提示：查找過程中保留經(jīng)過的結點信息，找到后順序輸出之）。 實現(xiàn)哈希表的相關運算編寫一個程序，實現(xiàn)哈希表的相關運算，并在此基礎上完成如下功能：（1）建立{16,74,60,43,54,90,46,31,29,88,77}哈希表A[0…12]，哈希函數(shù)為H(k)=key % 11，并采用線性探測法解決沖突。輸出哈希表；（2）在上述哈希表中查找關鍵字為29的記錄；（3）在上述哈希表中刪除關鍵字為77的記錄，再將其插入，然后輸出哈希表。要求：輸出格式哈希地址：0 1 2 ………..12 關鍵字值：……………………三，源代碼及結果截圖 //實現(xiàn)順序查找的算法 include define MAXL 100//定義表中最多記錄個數(shù) typedef int KeyType。typedef int InfoType。typedef struct {KeyType key。//KeyType為關鍵字的數(shù)據(jù)類型 InfoType data。//其他數(shù)據(jù) } NodeType。typedef NodeType SeqList[MAXL]。//順序表類型 int Search(SeqList R,int n,KeyType k)//順序查找算法{ int i=0。while(iprintf(“%d ”,R[i].key)。i++。//從表頭往后找} if(i=n)return1。else {printf(“%d”,R[i].key)。return i。} } void main(){ SeqList R。int n=10。KeyType k=5。InfoType a[]={3,6,2,10,1,8,5,7,4,9}。int i。for(i=0。i//建立順序表R[i].key=a[i]。printf(“查找結果：n”)。if((i=Search(R,n,k))!=1)printf(“n元素%d的位置是:%d”,k,i)。elseprintf(“n元素%d不在表中n”,k)。printf(“n”)。}//實現(xiàn)折半查找算法 include define MAXL 100//定義表中最多記錄個數(shù)typedef int KeyType。typedef char InfoType[10]。typedef struct { KeyType key。//KeyType為關鍵字的數(shù)據(jù)類型InfoType data。//其他數(shù)據(jù) } NodeType。typedef NodeType SeqList[MAXL]。//順序表類型int BinSearch1(SeqList R,int n,KeyType k)//非遞歸二分查找算法 { int low=0,high=n1,mid,count=0。while(low{ mid=(low+high)/2。printf(“第%d次查找:在[%d,%d]中查找到R[%d]:%dn”,++count,low,high,mid,R[mid].key)。if(R[mid].key==k)//查找成功返回return mid。if(R[mid].keyk)//繼續(xù)在R[low..mid1]中查找元素}} high=mid1。else low=mid+1。//繼續(xù)在R[mid+1..high]中查找return1。int BinSearch2(SeqList R,KeyType k,int low,int high,int count)//遞歸二分查找算法 {int mid。if(low次查找:在[%d,%d]中查找到元素printf(“R[%d]:%dn”,++count,low,high,mid,R[mid].key)。if(R[mid].key==k)//查找成功返回return mid。else if(R[mid].keyk)//繼續(xù)在R[low..mid1]中查找BinSearch2(R, k,low,mid1,count)。else BinSearch2(R, k,mid+1,high,count)。//繼續(xù)在R[mid+1..high]中查找}else return1。} void main(){} SeqList R。KeyType k=9。int a[]={1,2,3,4,5,6,7,8,9,10},i,n=10。for(i=0。i//建立順序表printf(“用非遞歸方法:n”)。if((i=BinSearch1(R,n,k))!=1)printf(“元素%d的位置是%dn”,k,i)。else printf(“元素%d不在表中n”,k)。printf(“用遞歸方法:n”)。if((i=BinSearch2(R,k,0,9,0))!=1)printf(“元素%d的位置是%dn”,k,i)。else printf(“元素%d不在表中n”,k)。 //實現(xiàn)二叉排序樹的基本運算 include //EOF,NULL include //atoi()include //cout,cin typedef int Status。typedef struct BTNode {int key。struct BTNode *lchild。struct BTNode *rchild。}BTNode。//定義二叉排序樹插入結點的算法 int BSTInsert(BTNode *amp。T,int k){if(T==NULL){T=(BTNode *)malloc(sizeof(BTNode))。Tlchild=Trchild=NULL。Tkey=k。return 1。}else{if(k==Tkey)return 0。else if(kkey)return BSTInsert(Tlchild, k)。elsereturn BSTInsert(Trchild, k)。} } //定義二叉排序樹的創(chuàng)建算法 BTNode *createBST(int k[],int n){BTNode *T。T=NULL。for(int i=0。iBSTInsert(T,k[i])。}return T。} //判斷是否為二叉排序樹 Status Judge(BTNode *amp。T){} //定義二叉排序樹的查找算法BTNode *BSTSearch(BTNode *amp。T,int k){if(T==NULL)return NULL。else if(T==NULL)return 1。else if((TTlchild)amp。amp。(Trchild)){} else return 0。Judge(Tlchild)。Judge(Trchild)。{printf(“%d ”,Tkey)。if(Tkey==k)return T。else if(kkey){return BSTSearch(Tlchild, k)。}else{return BSTSearch(Trchild, k)。}} } void main(){int a[50]={4,9,0,1,8,6,3,5,2,7}。BTNode *bt=createBST(a,10)。if(Judge(bt)==0)cout} //實現(xiàn)哈希表的相關運算 include define MaxSize 100//定義最大哈希表長度 define NULLKEY 0//定義空關鍵字值define DELKEY1//定義被刪關鍵字值typedef int KeyType。//關鍵字類型typedef char * InfoType。//其他數(shù)據(jù)類型 typedef struct { KeyType key。//關鍵字域InfoType data。//其他數(shù)據(jù)域 int count。//探查次數(shù)域} HashTable[MaxSize]。//哈希表類型void InsertHT(HashTable ha,int *n,KeyType k,int p)中 {//將關鍵字k插入到哈希表int i,adr。adr=k % p。if(ha[adr].key==NULLKEY || ha[adr].key==DELKEY)//x[j]可以直接放在哈希表中}