数据结构课上的一份实验报告
主要是应对实验报告,应该存在逻辑错误的地方没改。
#include <iostream>
typedef int KeyType;
typedef int InfoType ;
#define MAXSIZE 100
typedef struct
{
KeyType key;
InfoType otherinfo;
}ElemType;
typedef struct
{
ElemType *R;
int lenght;
}SSTable;
int InitList_SSTable(SSTable &L)
{
L.R = new ElemType[MAXSIZE];
if (!L.R)
{
std::cout << "初始化错误";
return 0;
}
L.lenght = 0;
return 1;
}
int Create_list(SSTable &ST){
int i,n,p;
std::cout << "所需建立表的个数:" ;
std::cin >> n;
ST.lenght = n;
for(i=1;i<=n;i++){
std::cout << "输入表中第" << i << "个数:";
std::cin >> p;
ST.R[i].key = p;
}
return 0;
}//建表
int Insert_List(SSTable &ST, int e){
std::cout << "没有此元素,自动为您将元素插入最后。" << std::endl;
ST.R[ST.lenght].key = e;
ST.lenght += 1;
return 0;
}//插入
int Search_Seq(SSTable ST, KeyType key)
{
std::cout << "顺序查找法:" << std::endl;
int i,sum=0;
std::cout << "当前比较的元素是:";
for(i=ST.lenght;i>=1;--i){
if(ST.R[i].key==key) {
std::cout << "最终比较了" << sum << "次。" << std::endl;
return i;
}
else{
std::cout << ST.R[i].key;
std::cout << ";";
sum += 1;
}
}
std::cout << std::endl;
std::cout << "最终比较了" << sum << "次。" << std::endl;
Insert_List(ST,key);
return 0;
}//顺序查找
int Search_Bin(SSTable ST,KeyType key) {
int i=0;
std::cout << "二分查找法:" << std::endl;
int low=1;
int hight=ST.lenght;
while(low<=hight) {
int mid = (low + hight) / 2;
if (key == ST.R[mid].key) {
std::cout << "最终比较了" << i << "次。" << std::endl;
return mid;
} else if (key < ST.R[mid].key) {
std::cout << ST.R[mid].key << ";";
hight = mid - 1;
i++;
} else {
std::cout << ST.R[mid].key << ";";
low = mid + 1;
i++;
}
}
std::cout << std::endl;
std::cout << "最终比较了" << i << "次。" << std::endl;
Insert_List(ST,key);
return 0;
}//二分
int main()
{
SSTable ST;
int key,Bin_num,Seq_num;
InitList_SSTable(ST);
std::cout << "********************当前建立第一个表********************" << std::endl;
Create_list(ST);
std::cout << "请输入需要查询的元素:";
std::cin >> key;
Seq_num = Search_Seq(ST,key);
if(Seq_num){
std::cout << "此元素在表中的位置是" << Seq_num << std::endl;
}
std::cout << "-------------------------------------------------" << std::endl;
std::cout << "请输入第二次需要查询的元素:";
std::cin >> key;
Seq_num = Search_Seq(ST,key);
if(Seq_num){
std::cout << "此元素在表中的位置是" << Seq_num << std::endl;
}
std::cout << "********************当前建立第二个表********************" << std::endl;
Create_list(ST);
std::cout << "请输入需要查询的元素:";
std::cin >> key;
Bin_num = Search_Bin(ST,key);
if(Bin_num){
std::cout << "此元素在表中的位置是" << Bin_num << std::endl;
}
std::cout << "-------------------------------------------------" << std::endl;
std::cout << "请输入第二次需要查询的元素:";
std::cin >> key;
Bin_num = Search_Bin(ST,key);
if(Bin_num){
std::cout << "此元素在表中的位置是" << Bin_num << std::endl;
}
}
标签:二分,std,顺序,cout,int,ST,查找,num,key
From: https://www.cnblogs.com/qianyuzz/p/17059906.html