大數(shù)據(jù)結(jié)構(gòu)試驗七查找

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

2、inorder ( t ) if (t!=Null) inorder(t 一 lchild);printf("4d , t -key);inorder(t f rchild); bstnode *insertbst(t, s)bstnode *s,*t; bstnode *f,*p;p=t;文案大全實用標(biāo)準(zhǔn)while(p!=Null) f=P；if (s - key= =p -key)return t;if (s f key<p-key)p=pTchild;elsep=pf rchild;if(t= =Null) return s;if (s f key<f-key) f

3、 Tchild=s;elsef frchild=s;return t;bstnode *creatord( ) bstnode *t, * s;int key;t=Null;scanf( "d ,&key);while (key!=0) s=malloc(sizeof (bitree); sfkey=key;s-lchild=Null;s 一 rchild=Null;scanf( "d , &data);sfother=data;t=insertbst(t, s); scanf( "d ,&key);文案大全實用標(biāo)準(zhǔn)return t;五、思

4、考與提高1 .用其它的查找方法完成該算法。2 .比較各種算法的時間及空間復(fù)雜度。六、完整參考程序1.折半查找#include <conio.h>#include <stdio.h>#define MAX 30 /定義有序查找表的最大長度typedef structchar elemMAX; /有序查找表int length;/length指示當(dāng)前有序查找表的長度SSTable;void initial(SSTable &);/初始化有序查找表int search(SSTable,int);/在有序查找表中查找元素void print(SSTable);/顯示有序

5、查找表中所有元素void main()SSTable ST; /ST為一有序查找表int ch,loc,flag=1;文案大全實用標(biāo)準(zhǔn)char j;initial(ST); /初始化有序查找表while(flag) printf("請選擇：n");printf("1.顯示所有元素n");printf("2.查找一個元素 n");printf("3.退出 n");scanf(" %c",&j);switch(j)case '1':print(ST); break; /顯示所

6、有元素case '2':printf("請輸入要查找的元素：");scanf("%d",&ch); /輸入要查找的元素的關(guān)鍵字loc=search(ST,ch); /查找if(loc!=0) printf("該元素所在位置是：dn",loc);/顯示該元素位置else printf("%d不存在!n",ch);/當(dāng)前元素不存在break;default:flag=0;文案大全實用標(biāo)準(zhǔn)printf("程序運(yùn)行結(jié)束！按任意鍵退出！n");void initial(SSTabl

7、e &v)/初始化有序查找表int i;printf("請輸入靜態(tài)表的元素個數(shù)：");/輸入有序查找表初始化時的長度scanf("%d”,&v.length);printf("請從小到大輸入元素(整形數(shù))：n",v.length);getchar();for(i=1;i<=v.length;i+) scanf("%d”,&v.elemi); / 從小到大輸入有 序查找表的各元素int search(SSTable v,int ch)/在有序查找表中查找ch的位置，成功返回其位置，失敗返回 0int low

8、,high,mid;文案大全實用標(biāo)準(zhǔn)low=1;high=v.length; / 置區(qū)間初值while(low<=high)找到待查元素繼續(xù)在前半?yún)^(qū)間進(jìn)行查找mid=(low+high)/2;if(v.elemmid=ch) return mid; /else if(v.elemmid>ch) high=mid-1; /else low=mid+1;/繼續(xù)在后半?yún)^(qū)間進(jìn)行查找return 0;/ 找不到時，i為0void print(SSTable v) /顯示當(dāng)前有序查找表所有元素int i；for(i=1;i<=v.length;i+) printf("%d &q

9、uot;,v.elemi);printf("n");2.二叉排序樹的建立與查找#include <conio.h>#include <math.h>#include <stdio.h>文案大全實用標(biāo)準(zhǔn)#include <stdlib.h>定義二叉樹節(jié)點結(jié)構(gòu)enum BOOLFalse,True;typedef struct BiTNode /char data;/為了方便，數(shù)據(jù)域只有關(guān)鍵字一項左右孩子指針域在二叉排序樹中插入元素在二叉排序樹中刪除元素刪除二叉排序樹的根結(jié)點中序遍歷二叉排序樹，即從小到大struct BiTNod

10、e *lchild,*rchild; /BiTNode,*BiTree;BOOlSearchBST(BiTree,char,BiTree,BiTree&);/ 在二叉排序樹中查找元素BOOL InsertBST(BiTree &,char); /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

11、!='n')文案大全實用標(biāo)準(zhǔn)printf("1.display'n");printf("2.search'n");printf("3.insert'n");printf("4.delete'n");printf("5.exit'n");scanf(" %c",&ch); /輸入操作選項switch(ch)case '1':if(!T) printf("The BST has no ele

12、m.n");else InorderBST(T);printf("n");break;case '2':printf("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); /el

13、se printf("%c has been found!n”,keyword); /break;case '3':printf("Input the keyword of elem to be inserted(a char):");文案大全該元成功插入該元素不成功刪除實用標(biāo)準(zhǔn)scanf(" %c",&keyword); /輸入要插入元素的關(guān)鍵字temp=InsertBST(T,keyword);if(!temp) printf("%c has been existed!n",keyword); /

14、素已經(jīng)存在else printf("Sucess to inert %c!n",keyword); /break;case '4':printf("Input the keyword of elem to be deleted(a char):");scanf(" %c",&keyword); /輸入要刪除元素的關(guān)鍵字temp=DeleteBST(T,keyword);if(!temp) printf("%c isn't existed!n",keyword); /存在else pr

15、intf("Sucess to delete %cn",keyword); /break;default: j='n'printf("The program is over!nPress any key to shut off the window!n");getchar();getchar();文案大全實用標(biāo)準(zhǔn)void InorderBST(BiTree T)/以中序方式遍歷二叉排序樹T,即從小到大顯示二叉排序樹的所有元素if(T->lchild) InorderBST(T->lchild);printf("%2c

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

17、=T->data) p=T;return True; /查找成功else if(key<T->data) tmp1=SearchBST(T->lchild,key,T,p); /在左子樹中繼續(xù)查找文案大全實用標(biāo)準(zhǔn)else tmp2=SearchBST(T->rchild,key,T,p); 在右子樹中繼續(xù)查找if(tmp111tmp2) return True; 若在子樹中查找成功，向上級返回Trueelse return False; /否貝U返回 FalseBOOL InsertBST(BiTree &T,char e)/當(dāng)二叉排序樹T中不存在元素e時

18、，插入e并返回True,否則返回FalseBiTree p,s;if(!SearchBST(T,e,NULL,p) 查找不成功s=(BiTree)malloc(sizeof(BiTNode);s->data=e;s->lchild=s->rchild=NULL;if(!p) T=s; /被插結(jié)點*s為新的根結(jié)點else if(e<p->data) p->lchild=s; /被插結(jié)點 *s 為左孩子else p->rchild=s; /被插結(jié)點*s為右孩子return True; / 成功插入else return False; /樹中已存在關(guān)鍵字為e的數(shù)據(jù)元素文案大全實用標(biāo)準(zhǔn)BOOL DeleteBST(BiTree &T,char key)/若二叉排序樹T中存在關(guān)鍵字等于key的數(shù)據(jù)元素時，則刪除該數(shù)據(jù)元 素結(jié)點/并返回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)鍵字