實(shí)驗(yàn)五：查找算法的設(shè)計(jì)

1、學(xué)校代碼： 10128學(xué) 號(hào)： 201220905048 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告（題 目：查找算法的設(shè)計(jì)學(xué)生姓名：孫躍學(xué) 院：理學(xué)院系 別：數(shù)學(xué)系專 業(yè)：信息與計(jì)算科學(xué)班 級(jí)：信計(jì)12-2班任課教師：杜雅娟 二 一 四 年 十 一 月一、實(shí)驗(yàn)?zāi)康恼莆詹檎宜惴ǖ闹R(shí)，學(xué)會(huì)設(shè)計(jì)查找算法。2、 實(shí)驗(yàn)內(nèi)容 1、順序表查找 2、有序表查找 3、二叉查找樹(shù)3、 概要設(shè)計(jì)1、查找 在同一個(gè)文件夾中建立如下五個(gè)文件c1.h;c9.h;c9-1.h;bo9-1.cpp;algo9-1.cpp;對(duì)于algo9-1.cpp進(jìn)行編譯、構(gòu)建和運(yùn)行；建立c1.h放程序名；#include<string.h>#inc

2、lude<ctype.h>#include<malloc.h>#include<limits.h>#include<stdio.h>#include<stdlib.h>#include<io.h>#include<math.h>#include<process.h>#include<iostream.h>/狀態(tài)代碼#define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1typedef int

3、 Status;typedef int Boolean;建立文件c9-1.h放靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu)/c9-1.h typedef structElemType *elem; int length; SSTable;建立文件c9.h放對(duì)兩個(gè)數(shù)值型關(guān)鍵字的比較約定為如下宏定義/c9.h#define EQ(a,b)(a)=(b)#define LT(a,b)(a)<(b)#define LQ(a,b)(a)<=(b)建立文件bo9-1.cpp放靜態(tài)查找表的基本操作Status Creat_Seq(SSTable &ST,int n)int i;ST.elem=(ElemTy

4、pe*)calloc(n+1,sizeof(ElemType);if(!ST.elem) return ERROR;for(i=1;i<=n;i+)*(ST.elem+i)=ri-1;ST.length=n;return OK;void Ascend(SSTable &ST)int i,j,k;for(i=1;i<ST.length;i+)k=i;ST.elem0=ST.elemi;for(j=i+1;j<=ST.length;j+)if LT(ST.elemj.key,ST.elem0.key)k=j;ST.elem0=ST.elemj;if(k!=i)ST.ele

5、mk=ST.elemi;ST.elemi=ST.elem0;Status Creat_Ord(SSTable &ST,int n)Status f;f=Creat_Seq(ST,n);if(f)Ascend(ST);return f;Status Destroy(SSTable &ST)free(ST.elem);ST.elem=NULL;ST.length=0;return OK;int Search_Seq(SSTable ST,KeyType key)int i;ST.elem0.key=key;for(i=ST.leng;!EQ(ST.elemi.key,key);-i

6、) return i;int Search_Bin(SSTable ST,KeyType key)int low,high,mid; low=1; high=ST.length; while(low<=high) mid=(low+high)/2; if EQ(key,ST.elemmid.key) return mid; else if LT(key,ST.elemmid.key) high=mid-1; else low=mid+1; return 0;Status Traverse(SSTable ST,void(*Visit)(ElemType)Elemtype *p;int i

7、;p=+ST.elem;for(i=1;i<=ST.length;i+) Visit(*p+);return OK;建立程序algo9-1.cpp檢驗(yàn)bo9-1.cpp的程序/alog9-1.cpp 檢驗(yàn)bo9-1.cpp(順序表部分)的程序#include"c1.h"#define N 5typedef int KeyType;struct ElemType long number; char name9; int politics; int Chinese; int English; int math; int physics; int chemistry; in

8、t biology; KeyType key; rN=179324,"何芳芳",85,89,98,100,93,80,47,179325,"陳紅",85,86,88,100,92,90,45,179326,"陸華",78,75,90,80,95,88,37,179327,"張平",82,80,78,98,84,96,40,179328,"趙小怡",76,85,94,57,77,69,44;#define total key#include"c9.h"#include"

9、;c9-1.h"#include"bo9-1.cpp"void print(ElemType c)printf("%-8ld%-8s%4d%5d%5d%5d%5d%5d%5d%5d"n,c.number,,c.politics,c.Chinese,c.English,c.math,c.chemistry,c.biology,c.total);void main() SSTable st; int i,s; for(i=0;i<N;i+) ri.total=ri.politics+ri.Chinese+ri.English+ri

10、.math+ri.physics+ri.chemistry+ri.biology; Creat_Seq(st,N); printf("準(zhǔn)考證號(hào) 姓名 政治 語(yǔ)文 外語(yǔ) 數(shù)學(xué) 物理 化學(xué) 生物 總分n"); Traverse(st,print); printf("請(qǐng)輸入待查找人的總分"); scanf("%d",&s); i=Search_Seq(st,s); if(i) print(*(st.elem+i); else print("沒(méi)找到n"); Destroy(st);2、有序表查找，同一個(gè)文件夾中建立

11、如下五個(gè)文件c1.h;c9.h;c9-1.h;bo9-1.cpp;algo9-2.cpp;對(duì)于algo9-2.cpp進(jìn)行編譯、構(gòu)建和運(yùn)行；建立文件algo9-2.cpp并利用實(shí)驗(yàn)一的文件編譯#include"c1.h"#define N 11typedef int KeyType;struct ElemTypeKeyType key;int others;rN=5,1,13,2,19,3,21,4,37,5,56,6,64,7,75,8,80,9,88,10,92,11;#include"c9.h"#include"c9-1.h"#i

12、nclude"bo9-1.cpp"void print(ElemType c)printf("(%d %d)",c.key,c.others);void main()SSTable st;int i;KeyType s;Creat_Ord(st,N);Traverse(st,print);printf("n");printf("請(qǐng)輸入待查找值的關(guān)鍵字")；scanf("%d",&s);i=Search_Bin(st,s);if(i)printf("(%d %d)%d是第%d個(gè)記

13、錄的關(guān)鍵字n",st.elemi.key,st.elemi.others,s,i);elseprintf("沒(méi)有找到n");Destroy(st);3、樹(shù)在同一個(gè)文件夾中建立如下五個(gè)文件c1.h;c6-2.h;bo9-2.cpp;algo9-4.cpp;對(duì)于algo9-1.cpp進(jìn)行編譯、構(gòu)建和運(yùn)行；建立c6-2.h放二叉樹(shù)的二叉鏈表存儲(chǔ)表示typedef struct BiTNode TElemType data; BiTNode *lchild,*rchild;BiTNode,*BiTree;建立文件bo9-2.cpp存儲(chǔ)動(dòng)態(tài)查找表的基本操作typedef E

14、lemType TElemType#include"c6-2.h"Status InitDSTable(BiTree &DT) DT=NULL; return OK;void DestroyDSTable(BiTree &DT) if(DT) if(DT->lchild) DestroyDSTable(DT->lchild); if(DT->rchild) DestroyDSTable(DT->rchild); free(DT); DT=NULL; BiTree SearchBST(BiTree T,KeyType key) if(!

15、T)|EQ(key,T->data.key) return T; else if LT(key,T->data.key) return SearchBST(T->lchild,key); else return SearchBST(T->rchild,key);void SearchBST(BiTree &T,KeyType key,BiTree f,BiTree &p,Status &flag) if(!T) p=f; flag=FALSE; else if EQ(key,T->data.key) p=T;flag=TRUE; else

16、if LT(key,T->data.key) SearchBST(T->lchild,key,T,p,flag); else SearchBST(T->rchild,key,T,p,flag);Status InsertBST(BiTree &T,ElemType e) BiTree p,s; Status flag; SearchBST(T,e.key,NULL,p,flag); if(!flag) s=(BiTree)malloc(sizeof(BiTNode); s->data=e; s->lchild=s->rchild=NULL; if(!

17、p) T=s; else if LT(e.key,p->data.key) p->lchild=s; else p->rchild=s; return TRUE; else return FALSE;void Delete(BiTree &p) BiTree 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;

18、s=s->rchild; p->data=s->data; if(q!=p) q->rchild=s->lchild; else q->lchild=s->lchild; free(s); Status DeleteBST(BiTree &T,KeyType key)/若二叉排序樹(shù)T中存在關(guān)鍵字等于key的數(shù)據(jù)元素時(shí)，則刪除該數(shù)據(jù)元素結(jié)點(diǎn)，/并返回TRUE；否則返回FALSE。算法9.7if(!T)/不存在關(guān)鍵字等于key的數(shù)據(jù)元素return FALSE;elseif EQ(key,T->data.key)/找到關(guān)鍵字等于key的數(shù)據(jù)元

19、素Delete(T);else if LT(key,T->data.key)DeleteBST(T->lchild,key);elseDeleteBST(T->rchild,key);return TRUE;void TraverseDSTable(BiTree DT,void(*Visit)(ElemType)/初始條件：動(dòng)態(tài)查找表DT存在，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)/操作結(jié)果：按關(guān)鍵字的順序?qū)T的每一個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit（）一且至多一次if(DT)TraverseDSTable(DT->lchild,Visit);Visit(DT->data);TraverseDSTable(DT->rchild,Visit);建立algo9-4.cpp檢驗(yàn)bo9-2.cpp的程序/alog9-4.cpp的程序#include"c1.h"#define N 10typedef int KeyType;struct ElemTypeKeyType key;int others;#include"c9.h"#include"bo9-2.cpp"void print(ElemType c)printf("(%