数据结构-试验8查找的算法

1、.1实现顺序查找的算法一,实验目的1 .熟悉掌握各种查找方法,深刻理解各种查找算法及其执行的过程；2 .学会分析各种查找算法的性能.二,实验内容2.1 实现顺序查找的算法编写一个程序,输出在顺序表3,6,2,10,1,8,5,7,4,9中采用顺序查找法查找关键字5的结果.2.2 实现折半查找算法编写一个程序,输出在顺序表1,2,3,4,5,6,7,8,9,10中采用折半查找方法查找关键字9的结果.要求：(1)用非递归方法；(2)用递归方法.2.3 实现二叉排序树的根本运算编写一个程序实现二叉排序树的根本运算,并在此根底上完成如下功能：(1)由4,9,0,1,8 , 6,3,5,2,7创立一个二

2、叉排序树 bt ;(2)判断bt是否为一棵二叉排序树(提示：在遍历过程中检查是否符合二叉排序树定义)；(3)采用非递归方法查找关键字为 6的结点,并输出其查找路径(提示：查找 过程中保存经过的结点信息,找到后顺序输出之).2.4 实现哈希表的相关运算编写一个程序,实现哈希表的相关运算,并在此根底上完成如下功能：(1)建立16,74,60,43,54,90,46,31,29,88,77 哈希表 A0 12,哈希函数为H(k)=key % 11 ,并采用线性探测法解决冲突.输出哈希表；(2)在上述哈希表中查找关键字为 29的记录；(3)在上述哈希表中删除关键字为 77的记录,再将其插入,然后输出哈

3、希表.要求：输出格式哈希地址：0 1 2 12关键字值：三,源代码及结果截图8.1/实现顺序查找的算法 #include <stdio.h>/定义表中最多记录个数/KeyType为关键字的数据类型/其他数据#define MAXL 100 typedef int KeyType; typedef int InfoType; typedef struct KeyType key;InfoType data; NodeType;typedef NodeType SeqListMAXL;/ 顺序表类型int Search(SeqList R,int n,KeyType k) /顺序查找算

4、法(int i=0;while (i<n && Ri.key!=k) (printf("%d ",Ri.key);i+;/从表头往后找) if (i>=n) return -1; else (printf("%d",Ri.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<n;i+)/ 建立顺序表Ri.key=ai;printf("查找结果：n&quo

5、t;);if (i=Search(R,n,k)!=-1)printf("n元素的位置是:d",k,i);elseprintf("n元素不在表中 n",k);printf("n");IS：3 6 2 10 1 8 5 元素5的位置是通 Press any key to continue8.2/实现折半查找算法#include <stdio.h>#define MAXL 100typedef int KeyType;typedef char InfoType10;typedef struct KeyType key;InfoT

6、ype data; NodeType;typedef NodeType SeqListMAXL;int BinSearch1(SeqList R,int n,KeyType k)/定义表中最多记录个数/KeyType为关键字的数据类型其他数据/顺序表类型/非递归二分查找算法int low=0,high=n-1,mid,count=0;while (low<=high)mid=(low+high)/2;printf(" 第 d 次查找：在 %d,%d 中查找到元素R%d:%dn",+count,low,high,mid,Rmid.key);if (Rmid.key=k)

7、查找成功返回return mid;if (Rmid.key>k)继续在Rlow.mid-1 中查找high=mid-1;elselow=mid+1;继续在 Rmid+1.high 中查找)return -1;)int BinSearch2(SeqList R,KeyType k,int low,int high,int count)递归二分查找算法int mid;if(low<=high)mid=(low+high)/2;printf(" 第 d 次查找：在 %d,%d 中查找到元素R%d:%dn,+count,low,high,mid,Rmid.key);if (Rmi

8、d.key=k)查找成功返回return mid;else if (Rmid.key>k)继续在 Rlow.mid-1 中查找BinSearch2(R, k,low,mid-1,count);elseBinSearch2(R, k,mid+1,high,count);继续在 Rmid+1.high 中查找)else return -1;)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<n;i+)/ 建立顺序表Ri.key=ai;printf("用非递归方法：n&q

9、uot;);if (i=BinSearch1(R,n,k)!=-1)printf("元素 d 的位置是 dn",k,i);elseprintf("元素d不在表中n,k);printf("用递归方法:n");if (i=BinSearch2(R,k,0,9,0)!=-1)printf("元素 d 的位置是 dn",k,i);elseprintf("元素d不在表中n,k);二烹 RE4ns 无富R福 兀章R81二9耋R 耋Rm 素R【81查查查查查查9* 07 9continue期查杳查的方查查查的司腱次次次次次9 s

10、THT 12 312 38.3/实现二叉排序树的根本运算#include<stdio.h> /EOF,NULL#include<stdlib.h> /atoi()#include<iostream.h> /cout,cintypedef int Status;typedef struct BTNodeint key;struct BTNode *lchild;struct BTNode *rchild;BTNode;/定义二叉排序树插入结点的算法int BSTInsert(BTNode *&T,int k)if尸NULL)T=(BTNode *)ma

11、lloc(sizeof(BTNode);T->lchild=T->rchild=NULL;T->key=k;return 1;else(if(k=T->key)return 0;else if(k<T->key)return BSTInsert(T->lchild, k);elsereturn BSTInsert(T->rchild, k);/定义二叉排序树的创立算法BTNode *createBST(int k口,int n)(BTNode *T;T=NULL;for(int i=0;i<=n-1;i+)BSTInsert(T,ki);r

12、eturn T;)判断是否为二叉排序树Status Judge(BTNode *&T)(if(T=NULL)return 1;else if(T>T->lchild)&&(T<T->rchild)(Judge(T->lchild);Judge(T->rchild);)else return 0;)/定义二叉排序树的查找算法BTNode *BSTSearch(BTNode *&T,int k)(if(T=NULL)return NULL; printf("%d ",T->key);if(T->ke

13、y=k)return T;else if(k<T->key)return BSTSearch(T->lchild, k);elsereturn BSTSearch(T->rchild, k);void main()int a50=4,9,0,1,8,6,3,5,2,7;BTNode *bt=createBST(a,10);if(Judge(bt)=0) cout<<"bt不是二叉排序树"<<endl;else cout<<"bt 是二叉排序树"<<endl;cout<<&

14、quot;查找关键字6的查找路径:"<<endl;BTNode *t=BSTSearch(bt,6);cout<<endl;)8.4实现哈希表的相关运算#include <stdio.h>#define MaxSize 100#define NULLKEY 0#define DELKEY -1typedef int KeyType;typedef char * InfoType;typedef structKeyType key;InfoType data;int count; HashTableMaxSize;/定义最大哈希表长度/定义空关键字值

15、/定义被删关键字值/关键字类型/其他数据类型/关键字域其他数据域/探查次数域哈希表类型将关键字k插入到哈希表void InsertHT(HashTable ha,int *n,KeyType k,int p)int i,adr;adr=k % p;if (haadr.key=NULLKEY | haadr.key=DELKEY)/xj 可以直接放在哈希表中haadr.key=k;haadr.count=1;else/发生冲突时采用线性探查法解决冲突i=1;/i记录xj发生冲突的次数doadr=(adr+1) % p;i+; while (haadr.key!=NULLKEY &&

16、; haadr.key!=DELKEY);haadr.key=k;haadr.count=i;n+;/创立哈希表 void CreateHT(HashTable ha,KeyType x,int n,int m,int p)int i,n1=0;for (i=0;i<m;i+)哈希表置初值hai.key=NULLKEY;hai.count=0;for (i=0;i<n;i+)在哈希表中查找关键字kInsertHT(ha,&n1,xi,p);int SearchHT(HashTable ha,int p,KeyType k)int i=0,adr;adr=k % p;whil

17、e (haadr.key!=NULLKEY && haadr.key!=k)i+;/采用线性探查法找下一个地址adr=(adr+1) % p;if (haadr.key=k)/查找成功return adr;else/查找失败return -1;)int DeleteHT(HashTable ha,int p,int k,int *n)删除哈希表中关键字 k(int adr;adr=SearchHT(ha,p,k);if (adr!=-1)在哈希表中找到该关键字(haadr.key=DELKEY;n-;哈希表长度减1return 1;)else在哈希表中未找到该关键字return

18、 0;)void DispHT(HashTable ha,int n,int m)输出哈希表(float avg=0;int i;printf("哈希表地址:t");for (i=0;i<m;i+)printf(" %3d",i);printf(" n");printf(" 哈希表关键字:t");for (i=0;i<m;i+)if (hai.key=NULLKEY | hai.key=DELKEY)printf(" ");输出3个空格elseprintf(" %3d&qu

19、ot;,hai.key);printf(" n");printf("搜索次数:t");for (i=0;i<m;i+)if (hai.key=NULLKEY | hai.key=DELKEY)printf(" ");输出3个空格elseprintf(" %3d",hai.count);printf(" n");for (i=0;i<m;i+)if (hai.key!=NULLKEY && hai.key!=DELKEY)avg=avg+hai.count;avg=avg/n;printf(" 平均搜索长度 ASL(%d)=%gn",n,avg);void main() (int x=16,74,60,43,54,90,46,31,29,88,77);int n=11,m=13,p=13,i,k=29;HashTable ha;CreateHT(ha,x,n,m,p);printf("n");DispHT(ha,n,m);printf("查找关键字 29:n");i=SearchHT(ha,p,k);if