C++数据结构设计程序

实验课的内容，一筹莫展，万望高手给与解答,C写还是C++不限，功能界面越完善越好，程序好有追加。题目一:基本查找算法比较1)对以下3种基本的查找算法的性能进行比较：顺序查... 实验课的内容，一筹莫展，万望高手给与解答,C写还是C++不限，功能界面越完善越好，程序好有追加。
题目一: 基本查找算法比较
1) 对以下3 种基本的查找算法的性能进行比较：顺序查找，二叉查找树，哈希。算法
包含两步：第一步：从文件中读取数据建查找表；第二步从文件中读取查找关键字
静态查找。
2) 待查找记录的个数不大于n ( n<=1000000)，关键 字 key 互不相同，取值范围 0 -10的9次幂
；
查询操作的次数为m(m=100 000 )，每次查询的关键字随机生成，取值范围0 -10的9次幂
.
3) 比较的指标为关键字的比较次数（包含建立查找表和查找操作）、内存空间和实际
运行时间。至少用5 组不同的数据作比较，至少包含完全正序(n=1 0 000)、完全逆
序(n=1 0 000 )及随机(n=10000 、100000 ，1000000)情况。
4) 为提高比较的可信度，待查找数据和查询关键字数据的生成及排序等预处理要设计
成一个独立功能，并将结果数据保留在data .in 文件中，格式如下：第1 行，用空
格分隔的两个非负整数，分别表示 n 和m；接下来的 n 行，每行一个非负整数，表
示待查询数据；接下来的m 行，每行一个非负整数，表示查询的关键字。
5) 每次查询都输出到结果文件data.out中，一共m 行。每行包含对应的查询关键字的
查询结果。查询结果：成功输出“Ye s”, 不成功输出“No”。
6) 哈希的散列函数建议使用key mod P，P 是大于n 的质数，注意内存限制；冲突
消解建议使用简单的线性探查法。当然，有能力的同学可以自己设计哈希函数，使
用统计结果较好的冲突消解方法，如平方探测法。
7) 对结果作简单分析，包括对各组数据得出结果波动大小的解释。
待查找个数不小于n（n>=1000000),跪求大神给完整可运行的代码，不要让我自己补了。。 展开
 我来答
2个回答
#合辑# 机票是越早买越便宜吗？
山寨版东北小伙
推荐于2018-04-21
知道答主
回答量：1
采纳率：0%
帮助的人：2.5万
我也去答题访问个人页
展开全部

苦逼的吉大孩子,你几班的啊，

#include<iostream>
#include<stdlib.h>
#include<time.h>
#include<fstream>
//#include<math>
using namespace std;
void search(int,int,int *,int *);
template<class T>

int Find_s(T data[], int n,T key,int &icmp)
//顺序查找(从n维数组中查找key,并且给出比较的次数icmp
{
icmp=0;
for(int i=0;i<n;i++)
{
   icmp++;
   if(data[i]==key)
    return i;
}
   return -1;
}
///以下是二叉查找树查找法
template<class T>
class BintreeNode
{
public:
T data;
BintreeNode* left;
BintreeNode*right;

BintreeNode():left(0),right(NULL){}
BintreeNode(T item):data(item),left(NULL),right(NULL){}
~BintreeNode(){
   if(left!=0)
    delete left;
   if(right!=0)
    delete right;
}
};
template<class T>
class Bintree
{
public:
int num;
BintreeNode<T>* root;
BintreeNode<T>* Find_bt(T key,int &icmp,int itype=0)//一个二叉树查找算法
{
   icmp=0;
   if(root==0)
   {
    icmp++;
    if(itype==0)//itype=1时有插入功能（不同的值时）
     return NULL;
    else
    {
     num++;
     return root=new BintreeNode<T>(key);
    }
   }
   else
   {
    BintreeNode<T>* ptr=root,*p;
    while(ptr!=NULL)
    {
     icmp++;
     p=ptr;
     if(ptr->data==key)
      return ptr;
     else
     {
      if(ptr->data>key)
       ptr=ptr->left;
      else
       ptr=ptr->right;
     }
    }
    if(itype)
    {
     num++;
     if(p->data>key)
      return p->left=new BintreeNode<T>(key);
     else
      return p->right=new (BintreeNode<T>)(key);
    }
    return NULL;
   }//else
}//Find_bt
Bintree():root(0),num(0){}
~Bintree(){delete root;}
};
/*int compare(const void* a,const void* b)
{
return *(int *)a-*(int *)b;
}*/
template<class T>
class Link
{
public:
T data;
Link<T>* next;
Link<T>():next(0){}
Link<T>(T item):data(item),next(0){}
~Link<T>(){if(next) delete next;}
};
template<class T>
class LinkList
{
public:
Link<T>* first;
LinkList<T>():first(0){}
~LinkList<T>(){if(first)delete first;}
Link<T>* Find_hash(T key,int &icmp,int ntype=0)//查找与插入
{
   icmp=0;
   if(first==0)
   {
    icmp++;
    if(ntype)
     return first=new Link<T>(key);
    else
     return NULL;
   }
   else
   {
    Link<T>*ptr=first,*p;
    while(ptr!=NULL)
    {
     icmp++;
     p=ptr;
     if(ptr->data==key)
      return ptr;
     ptr=ptr->next;
    }
    if(ntype)
     return p->next=new Link<T>(key);
    return NULL;
   }
}
};
template<class T>
class Hash
{
public:
LinkList<T>* hashlist;
int size;
Hash<T>(int n=113):size(n)
{
   hashlist=new LinkList<T>[n];
}
~Hash<T>(){delete []hashlist;}
void init_hash(T data[],int n)//初始化哈希查找表（拉链法）
{
   int t;
   for(int i=0;i<n;i++)
   {
    int pos=data[i]%size;
    hashlist[pos].Find_hash(data[i],t,1);
   }
}
Link<T>* Find_hash(T key,int &icmp)    //查找关键词   除法杂凑函数
{
   int pos=key%size;
   return hashlist[pos].Find_hash(key,icmp);
}
};
int compare1(const void* a,const void* b)
{
 return *(int *)a-*(int *)b;
}
int compare2(const void* a,const void* b)
{
 return *(int *)b-*(int *)a;
}
 
//主函数
int main()
{
int p;
int m;
int n;
while(true)
{
cout<<"请选择数据类型 :1.正序排列2.逆序排列3.随机排列"  <<endl;
cin>>p;
switch(p){
case 1 :
 {
   FILE *fp;
 char *filename="data.in";
 if((fp=fopen(filename,"w+"))==NULL)
 {
  printf("cannot open this flie\n");
  exit(0);
 }
 
 
srand(time(0));
cout<<"  请输入数据规模n "<<endl;
cin>>n;
 fprintf(fp,"\t\t%d\t",n);
  cout<<" 请输入查找比较的操作次数 m "<<endl;
cin>>m;
 fprintf(fp,"\t\t%d\t\n",m);

int *a=new int[n];
for(int i=0;i<n;i++)
{
   a[i]=rand()%1000000001;
 fprintf(fp,"\t\t%d\t\n",a[i]);
}
qsort(a,n,sizeof(int),compare1);   //对数组进行升序排序
qsort(a,n,sizeof(int),compare2);   //对数组进行降序排序
//随机生成m个随机数，并存入data.in
int *b=new int[m];
for(int k=0;k<m;k++)
{
   b[k]=rand()%1000000001;
 fprintf(fp,"\t\t%d\t\n",b[k]);
}
 fclose(fp);//关闭文件
 search(m,n,a,b);
 }
break;
case 2 :
 {
 FILE *fp;
 char *filename="data.in";
 if((fp=fopen(filename,"w+"))==NULL)
 {
  printf("cannot open this flie\n");
  exit(0);
 }
 
 
srand(time(0));
cout<<"  请输入数据规模n "<<endl;
cin>>n;
 fprintf(fp,"\t\t%d\t",n);
 
  cout<<" 请输入查找比较的操作次数 m "<<endl;
cin>>m;
 fprintf(fp,"\t\t%d\t\n",m);

int *a=new int[n];
for(int i=0;i<n;i++)
{
   a[i]=rand()%1000000001;
 fprintf(fp,"\t\t%d\t\n",a[i]);
}
qsort(a,n,sizeof(int),compare2);   //对数组进行降序排序
//随机生成m个随机数，并存入data.in
int *b=new int[m];
for(int k=0;k<m;k++)
{
   b[k]=rand()%1000000001;
 fprintf(fp,"\t\t%d\t\n",b[k]);
}
 fclose(fp);//关闭文件
 search(m,n,a,b);
 }
 break;
case 3 :
 {
   FILE *fp;
 char *filename="data.in";
 if((fp=fopen(filename,"w+"))==NULL)
 {
  printf("cannot open this flie\n");
  exit(0);
 }
 
 
srand(time(0));
//输入n,并存入data.in
//int n;
cout<<"  请输入数据规模n "<<endl;
cin>>n;
 fprintf(fp,"\t\t%d\t",n);
//输入m,并存入data.in
 cout<<" 请输入查找比较的操作次数 m "<<endl;
//int m;
cin>>m;
 fprintf(fp,"\t\t%d\t\n",m);
//随机生成n个随机数，并存入data.in
int *a=new int[n];
for(int i=0;i<n;i++)
{
   a[i]=rand()%1000000001;
 fprintf(fp,"\t\t%d\t\n",a[i]);
}
//随机生成m个随机数，并存入data.in
int *b=new int[m];
for(int k=0;k<m;k++)
{
   b[k]=rand()%1000000001;
 fprintf(fp,"\t\t%d\t\n",b[k]);
}
 fclose(fp);//关闭文件
 search(m,n,a,b);
}
}
 

}
return 0;
}
//search函数
void search(int m,int n,int *a,int *b){
  FILE *fp;
 char *filename="data.out";
 if((fp=fopen(filename,"w+"))==NULL)
 {
  printf("cannot open this flie\n");
  exit(0);
 }
  
 
clock_t start1 = clock();
for(int h=0;h<m;h++)
{
 int key=b[h];
 int icmp;
 int j=Find_s(a,n,key,icmp);//使用顺序查找法查找key值的位置
 if(j==-1)
 {
  cout<<"数据总数:"<<n<<"\t查找关健字key:"<<key<<
   "\t查找比较次数:icmp\n顺序查找法：\n是否找到:"
<<"no"<<"   icmp:"<<icmp<<endl;
   fprintf(fp,"\t\t%s\t\n","no");
 }
   else
 {
 
 cout<<"数据总数:"<<n<<"\t查找关健字key:"<<key<<
   "\t查找比较次数:icmp\n顺序查找法：\n是否找到:"
<<"yes"<<"   icmp:"<<icmp<<endl;
  fprintf(fp,"\t\t%s\t\n","yes");
 }
}
 clock_t end1 = clock();
 
 clock_t start2 = clock();
 for(int f=0;f<m;f++)
{
 int key=b[f];
 int icmp;
Bintree<int> btree;
for(int i=0;i<n;i++)
   btree.Find_bt(a[i],icmp,1);//未排序之前插入到二叉查找树中
qsort(a,n,sizeof(int),compare1);//对数组进行升序排序
 
cout<<"二叉查找树："<<endl;
int p = (btree.Find_bt(key,icmp)==NULL?-1:btree.Find_bt
(key,icmp)->data );
if(p==-1)
{
 
  cout<<"数据总数:"<<n<<"\t查找关健字key:"<<key<<
   "\t查找比较次数:icmp\n二叉树查找法：\n是否找到:"
<<"no"<<"   icmp:"<<icmp<<endl;
   fprintf(fp,"\t\t%s\t\n","no");
 
}
else
{
  cout<<"数据总数:"<<n<<"\t查找关健字key:"<<key<<
   "\t查找比较次数:icmp\n二叉树查找法：\n是否找到:"
<<"no"<<"   icmp:"<<icmp<<endl;
   fprintf(fp,"\t\t%s\t\n","no");
}
 }
 clock_t end2 = clock();
 
clock_t start3 = clock();
 for(int g=0;g<m;g++)
{
 int key=b[g];
 int icmp;
Hash<int > hash(1000);
hash.init_hash(a,n);
cout<<"哈希表查找："<<endl;
int q = ((hash.Find_hash(key,icmp)==NULL)?-1:(hash.Find_hash
(key,icmp))->data);
if(q==-1){
cout<<"数据总数:"<<n<<"\t查找关健字key:"<<key<<
   "\t查找比较次数:icmp\n哈希查找法：\n是否找到:"
<<"no"<<"   icmp:"<<icmp<<endl;
  fprintf(fp,"\t\t%s\t\n","no");
}
else{
 cout<<"数据总数:"<<n<<"\t查找关健字key:"<<key<<
   "\t查找比较次数:icmp\n二叉树查找法：\n是否找到:"
<<"yes"<<"   icmp:"<<icmp<<endl;
  fprintf(fp,"\t\t%s\t\n","yes");
}
 }
 clock_t end3 = clock();
cout<<"顺序查找时间    :"<<(double)(end1-start1)/CLOCKS_PER_SEC<<endl<<endl;//输出时间
cout<<"二叉树查找时间    :"<<(double)(end2-start2)/CLOCKS_PER_SEC<<endl<<endl;//输出时间
cout<<"哈希查找时间    :"<<(double)(end3-start3)/CLOCKS_PER_SEC<<endl<<endl;//输出时间
fclose(fp);//关闭文件
}
 
 

不过 运行结果 不能排序 只能是随机的，你看看能改好吗？改好了 说给我  我11级12班的

已赞过 已踩过<
你对这个回答的评价是？
评论 收起
上海华然企业咨询
2024-10-21 广告
上海华然企业咨询有限公司专注于AI与数据合规咨询服务。我们的核心团队来自头部互联网企业、红圈律所和专业安全服务机构。凭借深刻的AI产品理解、上百个AI产品的合规咨询和算法备案经验，为客户提供专业的算法备案、AI安全评估、数据出境等合规服务，... 点击进入详情页
本回答由上海华然企业咨询提供
 yunxiaoxue027
2013-08-15 · 超过23用户采纳过TA的回答
知道答主
回答量：81
采纳率：0%
帮助的人：56.2万
我也去答题访问个人页
展开全部
你分开提问估计回答的人会多点，呵呵，
已赞过 已踩过<
你对这个回答的评价是？
评论 收起
推荐律师服务： 若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询

为你推荐：

下载百度知道APP，抢鲜体验
使用百度知道APP，立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

京ICP证030173号-1   京网文【2023】1034-029号     ©2025Baidu  使用百度前必读 | 知道协议 | 企业推广

辅 助

模 式