数据结构实验五 查找的实现(6页).doc
-实验五 查找的实现 一、 实验内容 1、建立一个线性表，对表中数据元素存放的先后次序没有任何要求。输入待查数据元素的关键字进行查找。为了简化算法，数据元素只含一个整型关键字字段，数据元素的其余数据部分忽略不考虑。建议采用前哨的作用，以提高查找效率。 2、查找表的存储结构为有序表，输入待查数据元素的关键字利用折半查找方法进行查找。此程序中要求对整型量关键字数据的输入按从小到大排序输入。二、 源代码和执行结果1、#include<iostream>using namespace std ;#define MAX 100#define KeyType inttypedef structKeyType key ;DataType ;typedef structDataType elemMAX ;int length ;SeqTable , *PSeqTable ;PSeqTable Init_SeqTable()PSeqTable p = (PSeqTable)malloc(sizeof(SeqTable) ;if(p != NULL)p->length = 0 ;return p ;elsecout<<"Out of space!"<<endl ;return NULL ;int insert_SeqTable(PSeqTable p ,KeyType x)if(p->length >= MAX)cout<<"overflow!"<<endl ;return 0 ;p->elemp->length.key = x ;p->length + ;return 1 ;int SeqSearch(SeqTable s ,KeyType k)int n , i = 0 ;n = s.length ;s.elemn.key = k ;while(s.elemi.key != k)i + ;if(i = n)return -1 ;else return i ;void main()PSeqTable p ;int i , n ;KeyType a ;p = Init_SeqTable() ;cout<<"请输入数据个数：" ;cin>>n ;cout<<"请输入数据："<<endl ;for(i = 0 ; i < n ; i +)cin>>a ;insert_SeqTable(p , a) ;cout<<"请输入要查找的数据，输入32767结束：" ;cin>>a ;while(a != 32767)i =SeqSearch(*p , a) ;if(i = -1)cout<<"无此数据！请重新输入："<<endl ;cin>>a ;elsecout<<"该数据的位置是："<<i+1<<endl ;cout<<"请输入要查找的数据：" ;cin>>a ;2、#include<iostream>using namespace std ;#define MAX 100#define KeyType inttypedef structKeyType key ;DataType ;typedef structDataType elemMAX ;int length ;BinTable , *PBinTable ;PBinTable Init_BinTable()PBinTable p = (PBinTable)malloc(sizeof(BinTable) ;if(p != NULL)p->length = 0 ;return p ;elsecout<<"Out of space!"<<endl ;return NULL ;int insert_BinTable(PBinTable p ,KeyType x)if(p->length >= MAX)cout<<"overflow!"<<endl ;return 0 ;p->elemp->length.key = x ;p->length + ;return 1 ;int BinSearch(BinTable s ,KeyType k)int low , mid , high ;low = 0 ;high = s.length-1 ;while(low <= high)mid = (low+high)/2 ;if(s.elemmid.key = k)return mid ;else if(s.elemmid.key > k)high = mid - 1 ;elselow = mid +1 ;return -1 ;void main()PBinTable p ;int i , n ;KeyType a ;p = Init_BinTable() ;cout<<"请输入数据个数：" ;cin>>n ;cout<<"请按从小到大的顺序输入数据："<<endl ;for(i = 0 ; i < n ; i +)cin>>a ;insert_BinTable(p , a) ;cout<<"请输入要查找的数据，输入32767结束：" ;cin>>a ;while(a != 32767)i =BinSearch(*p , a) ;if(i = -1)cout<<"无此数据！请重新输入："<<endl ;cin>>a ;elsecout<<"该数据的位置是："<<i+1<<endl ;cout<<"请输入要查找的数据：" ;cin>>a ;-第 6 页-
