數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)七查找

1、實(shí)驗(yàn)七 查找、實(shí)驗(yàn)?zāi)康?. 掌握查找的不同方法，并能用高級(jí)語言實(shí)現(xiàn)查找算法；2. 熟練掌握二叉排序樹的構(gòu)造和查找方法。3. 熟練掌握靜態(tài)查找表及哈希表查找方法。二、實(shí)驗(yàn)內(nèi)容 設(shè)計(jì)一個(gè)讀入一串整數(shù)，然后構(gòu)造二叉排序樹，進(jìn)行查找。三、實(shí)驗(yàn)步驟1. 從空的二叉樹開始，每輸入一個(gè)結(jié)點(diǎn)數(shù)據(jù)，就建立一個(gè)新結(jié)點(diǎn)插入到當(dāng) 前已生成的二叉排序樹中。2. 在二叉排序樹中查找某一結(jié)點(diǎn)。3. 用其它查找算法進(jìn)行排序(課后自己做) 。四、實(shí)現(xiàn)提示1. 定義結(jié)構(gòu) typedef struct node int key;int other;struct node *lchild, *rchild; bstnode;void

2、 inorder ( t ) if (t!=Null) in order(tIchild);printf(“ %4key)；inorder(trchild); bstnode *insertbst(t, s)bstnode *s, *t; bstnode *f, *p; p=t;while(p!=Null) f=p;if (s key= =k key) return t;if (s key<p key) p=p Ichild; elsep=prchild;if(t= =Null) return s;if (skey<fkey) flchild=s;elsef rchild=s;re

3、turn t;bstnode *creatord( ) bstnode *t, * s;int key;t=Null;scanf( “ %d”,&key);while (key!=0) s=malloc(sizeof (bitree); skey=key;slchild=Null; srchild=Null;scanf( “%d”, &data); sother=data; t=insertbst(t, s);scanf( “%d”,&key);return t;五、思考與提高1. 用其它的查找方法完成該算法。2.比較各種算法的時(shí)間及空間復(fù)雜度。六、完整參考程序1.折半

4、查找#include <conio.h>#include <stdio.h>#define MAX 30/ 定義有序查找表的最大長(zhǎng)度typedef structchar elemMAX;/ 有序查找表int length;/length 指示當(dāng)前有序查找表的長(zhǎng)度SSTable;void initial(SSTable &);/初始化有序查找表int search(SSTable,int);/在有序查找表中查找元素void print(SSTable);/ 顯示有序查找表中所有元素void main()SSTable ST; /ST 為一有序查找表int ch,l

5、oc,flag=1;char j;initial(ST);/ 初始化有序查找表while(flag) printf(" 請(qǐng)選擇： n");printf("1. 顯示所有元素 n");printf("2. 查找一個(gè)元素 n");prin tf("3.退出 n");scanf(" %c",&j);switch(j)case '1':print(ST); break; /顯示所有元素case 2:pri ntf("請(qǐng)輸入要查找的元素：");scanf(&qu

6、ot;%d",&ch);/輸入要查找的元素的關(guān)鍵字loc=search(ST,ch);/查找 if(loc!=0) printf(" 該元素所在位置是： %dn",loc); / 顯示該元素位elseprintf("%d不存在!n",ch);當(dāng)前元素不存在break;default:flag=0;printf(" 程序運(yùn)行結(jié)束 ! 按任意鍵退出 !n");void initial(SSTable &v)/初始化有序查找表int i;printf("請(qǐng)輸入靜態(tài)表的元素個(gè)數(shù)：");/輸入有序查

7、找表初始化時(shí)的長(zhǎng)度 scanf("%d",&v.length);printf(" 請(qǐng)從小到大輸入 %d 個(gè)元素(整形數(shù))： n",v.length);getchar();for(i=1;i<=v.length;i+) scanf("%d",&v.elemi); / 從小到大輸入有序查找表的各元素int search(SSTable v,int ch)/在有序查找表中查找 ch 的位置，成功返回其位置，失敗返回 0 int low,high,mid;low=1;high=v.length; /置區(qū)間初值while(

8、low<=high)mid=(low+high)/2;if(v.elemmid=ch) return mid; / 找到待查元素else if(v.elemmid>ch) high=mid-1; / 繼續(xù)在前半?yún)^(qū)間進(jìn)行查找else low=mid+1;/繼續(xù)在后半?yún)^(qū)間進(jìn)行查找return 0;/找不到時(shí)， i 為 0void print(SSTable v)/顯示當(dāng)前有序查找表所有元素int i;for(i=1;i<=v.length;i+) printf("%d ",v.elemi);printf("n");2.二叉排序樹的建立與查找

9、#include <conio.h>#include <math.h>#include <stdio.h>#include <stdlib.h>enum BOOLFalse,True;typedef struct BiTNode/定義二叉樹節(jié)點(diǎn)結(jié)構(gòu)char data;/為了方便，數(shù)據(jù)域只有關(guān)鍵字一項(xiàng)struct BiTNode *lchild,*rchild; / 左右孩子指針域BiTNode,*BiTree;BOOL SearchBST(BiTree,char,BiTree,BiTree&); /在二叉排序樹中查找元素BOOL Inse

10、rtBST(BiTree &,char);/ 在二叉排序樹中插入元素/刪除二叉排序樹的根結(jié)點(diǎn)/中序遍歷二叉排序樹， 即從小到大顯示BOOL DeleteBST(BiTree &,char);/ 在二叉排序樹中刪除元素void Delete(BiTree &);void InorderBST(BiTree); 各元素void main()BiTree T,p;char ch,keyword,j='y'BOOL temp;T=NULL;while(j!='n')printf("1.displayn");printf(&qu

11、ot;2.searchn");printf("3.insertn");printf("4.deleten");printf("5.exitn");scanf(" %c",&ch); / 輸入操作選項(xiàng)switch(ch)case '1':if(!T) printf("The BST has no elem.n");else InorderBST(T);printf("n");break;case '2':printf("

12、;Input the keyword of elem to be searched(a char):");scanf(" %c",&keyword); / 輸入要查找元素的關(guān)鍵字temp=SearchBST(T,keyword,NULL,p);if(!temp) printf("%c isn't existed!n",keyword); / 沒有找到else printf("%c has been found!n",keyword); /成功找到break;case '3':printf(&q

13、uot;Input the keyword of elem to be inserted(a char):");scanf(" %c",&keyword); / 輸入要插入元素的關(guān)鍵字temp=InsertBST(T,keyword);if(!temp) printf("%c has been existed!n",keyword); / 該元素已經(jīng)存在else printf("Sucess to inert %c!n",keyword); /成功插入break;case '4':printf(&qu

14、ot;Input the keyword of elem to be deleted(a char):");scanf(" %c",&keyword); / 輸入要?jiǎng)h除元素的關(guān)鍵字 temp=DeleteBST(T,keyword);if(!temp) printf("%c isn't existed!n",keyword); / 該元素不存在else printf("Sucess to delete %cn",keyword); /成功刪除break;default: j='n'printf

15、("The program is over!nPress any key to shut off the window!n"); getchar();getchar();void InorderBST(BiTree T)/以中序方式遍歷二叉排序樹 T,即從小到大顯示二叉排序樹的所有元素if(T->lchild) InorderBST(T->lchild);printf("%2c",T->data);if(T->rchild) InorderBST(T->rchild);BOOL SearchBST(BiTree T,char

16、 key,BiTree f,BiTree &p)/在根指針T所指二叉排序樹中遞歸的查找其關(guān)鍵字等于key的元素，若查找成功則指針p指向該數(shù)據(jù)元素，并返回True,否則指針指向查找路徑上訪問的 最后一個(gè)結(jié)點(diǎn)并返回False,指針f指向T的雙親，其初始調(diào)用值為NULLBOOL tmp1,tmp2;tmp1=tmp2=False;if(!T) p=f;return False; /查找不成功else if(key=T->data) p=T;return True; /查找成功else if(key<T->data) tmp1=SearchBST(T->lchild,k

17、ey,T,p); /在/ 左子樹中繼續(xù) 查找else tmp2=SearchBST(T->rchild,key,T,p); /在/ 右子樹中繼續(xù)查找if(tmp1|tmp2) return True; /若在子樹中查找成功，向上級(jí)返回Trueelse return False;/否則返回 FalseBOOL InsertBST(BiTree &T,char e)/當(dāng)二叉排序樹T中不存在元素e時(shí)，插入e并返回True,否則返回FalseBiTree p,s;if(!SearchBST(T,e,NULL,p) / 查找不成功 s=(BiTree)malloc(sizeof(BiTNo

18、de);s->data=e;s->lchild=s->rchild=NULL;if(!p) T=s; /被插結(jié)點(diǎn) *s 為新的根結(jié)點(diǎn)else if(e<p->data) p->lchild=s; /被插結(jié)點(diǎn) *s 為左孩子else p->rchild=s; / 被插結(jié)點(diǎn) *s 為右孩子return True; /成功插入else return False; /樹/ 中已存在關(guān)鍵字為 e 的數(shù)據(jù)元素BOOL DeleteBST(BiTree &T,char key)/若二叉排序樹T中存在關(guān)鍵字等于key的數(shù)據(jù)元素時(shí)，則刪除該數(shù)據(jù)元素 結(jié)點(diǎn)并返回True否則返回FalseBOOL tmp1,tmp2;tmp1=tmp2=False;if(!T) return False; /不存在關(guān)鍵字等于 key 的數(shù)據(jù)元素elseif(key=T->data) Delete(T); return True;/找到關(guān)鍵字等于