大二下小学期《数据结构》课程设计报告1

前端之家收集整理的这篇文章主要介绍了大二下小学期《数据结构》课程设计报告1前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
题目一: 基本查找算法比较
1) 对以下 3 种基本的查找算法的性能进行比较:顺序查找,二叉查找树,哈希。算法
包含两步:第一步:从文件中读取数据建查找表;第二步从文件中读取查找关键字
静态查找。
2) 待查找记录的个数不小于 n ( n<=1000000),关键字key 互不相同,取值范围0-109;
查询操作的次数为m(m=100000),每次查询的关键字随机生成,取值范围0-109.
3) 比较的指标为关键字的比较次数(包含建立查找表和查找操作)、内存空间和实际
运行时间。至少用5 组不同的数据作比较,至少包含完全正序(n=10000)、完全逆
序(n=10000)及随机(n=10000、100000,1000000)情况。
4) 为提高比较的可信度,待查找数据和查询关键字数据的生成及排序等预处理要设计
成一个独立功能,并将结果数据保留在data.in 文件中,格式如下:第1 行,用空
格分隔的两个非负整数,分别表示n 和m;接下来的n 行,每行一个非负整数,表
示待查询数据;接下来的m 行,每行一个非负整数,表示查询的关键字。
5) 每次查询输出到结果文件 data.out 中,一共m 行。每行包含对应的查询关键字的
查询结果。查询结果:成功输出“Yes”,不成功输出“No”。
6) 哈希的散列函数建议使用 key mod P,P 是大于n 的质数,注意内存限制;冲突
消解建议使用简单的线性探查法。当然,有能力的同学可以自己设计哈希函数,使
统计结果较好的冲突消解方法,如平方探测法。

7) 对结果作简单分析,包括对各组数据得出结果波动大小的解释。



我的解答:

由题目分析得,设计2个程序,其中一个来产生随机数据和key,另外一个程序用来进行对数据的分析。由于rand()函数只能产生0~32767之间的随机数,但是题目要求随机数的范围会很大,怎么才能生成很大的随机数,又不破坏均匀性?我采用的方法是按位随机,每次产生0~9之间的随机数,做为9位数的其中一位,然后生成9次,组合起来就是一个9位的随机数。

对于线性分析,在全局定义一个很大的数组,每次程序将数据读入到数组中,用一个2重循环进行分析。对于二叉树查找,首先构造二叉排序树,然后在对每个key进行查找。对于哈希算法,我才用拉链法,取质数10007进行哈希。

如何得到每种方法的比较次数?我才用设置全局量(longlong),在3种方法查询函数中,在有比较的时候,全局量自加一,然后在屏幕上输出程序运行完成后的各个次数,对其进行分析。

//============================================================================
// Name        : creat_rand.cpp
// Author      : menglei
// Version     : 2013.8.13  20:19
// Copyright   : Your copyright notice
// Description : 此程序产生5组随机的数据
//============================================================================

#include <iostream>
#include <fstream>
using namespace std;


int min_rand(){
	//返回一个0到9的随机数

	//srand((unsigned)time(NULL));
	return rand()%10;
}
int myRand(int bit){
	//hit表示多少位,返回一个在int范围内bit位的一个随机数
	int randdata = 0;
	while(bit--){
		randdata = 10*randdata +min_rand();
	}
	return randdata;
}

int main() {
	/*如何产生一个很大范围的随机数?
	 *采用按位结合法和丢弃法结合
	 *每位随机0到9,---按位结合
	 超过范围的数字就丢弃掉----丢弃法
	*/
	ofstream fout1("data1_in.txt");
	fout1<<"10000"<<" "<<"100000"<<endl;
	//有序的10000个数字,前面的表示n和m
	for(int i=0;i<10000;i++){
		fout1<<i<<endl;
	}
	//产生100000个key
	for(int i=0;i<100000;i++){
		fout1<<myRand(9)<<endl;
	}
	fout1.close();
	cout<<"finish_data1_in.txt"<<endl;

	ofstream fout2("data2_in.txt");//逆序
	fout2<<"10000"<<" "<<"100000"<<endl;
	for(int i=10000;i>0;i--){
		fout2<<i<<endl;
	}
	for(int i=0;i<100000;i++){
		fout2<<myRand(9)<<endl;
	}
	fout2.close();
	cout<<"finish_data2_in.txt"<<endl;

	ofstream fout3("data3_in.txt");//随机10000三种
	fout3<<"10000"<<" "<<"100000"<<endl;
	for(int i=0;i<10000;i++){
		fout3<<myRand(9)<<endl;
	}
	for(int i=0;i<100000;i++){
		fout3<<myRand(9)<<endl;
	}
	fout3.close();
	cout<<"finish_data3_in.txt"<<endl;

	ofstream fout4("data4_in.txt");//随机100000三种
	fout4<<"100000"<<" "<<"100000"<<endl;
	for(int i=0;i<100000;i++){
		fout4<<myRand(9)<<endl;
	}
	for(int i=0;i<100000;i++){
		fout4<<myRand(9)<<endl;
	}
	fout4.close();
	cout<<"finish_data4_in.txt"<<endl;

	ofstream fout5("data5_in.txt");//随机1000000三种
	fout5<<"1000000"<<" "<<"100000"<<endl;
	for(int i=0;i<1000000;i++){
		fout5<<myRand(9)<<endl;
	}
	for(int i=0;i<100000;i++){
		fout5<<myRand(9)<<endl;
	}
	fout5.close();
	cout<<"finish_data5_in.txt"<<endl;

	return 0;
}


//============================================================================
// Name        : temp1.cpp
// Author      : menglei
// Version     :
// Copyright   : Your copyright notice
// Description : 数据的分析
//============================================================================
#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std;

class node{
public:
	node(int value):value(value),left(NULL),right(NULL){};//构造函数
	node(){right = NULL;left =NULL;value = -1;}
	node*getleft(){return left;}
	node*getright(){return right;}
	int getvalue(){return value;}
	void setvalue(int t){value = t;}
	void setleft(node * l){left = l;}
	void setright(node * r){right = r;}
	node *right;
	node *left;
	int value;
};

class searchTree{
public:
	searchTree(int i){init(i);}
	void init(int);
	void deleteTree(node*);
	void insert (node *,int);
	bool find(node *,int,long long & );
	node getRoot(){return root;}
	void midOder(node *);

private:
	node root;
};

void searchTree::init(int a){
	root.left = NULL;
	root.right = NULL;
	root.value = a;
}
void searchTree::deleteTree(node * a){
	if(a != NULL){
		deleteTree(a->getleft());
		deleteTree(a->getright());
		delete a;
	}
}
void searchTree::insert(node *n,int i){
	node * pointer = NULL;
	if(n == NULL){init(i);return ;}
	else pointer = n;
	while(1){
		if(pointer->getvalue() == i) return ;//要插入的节点value和根节点的value相同则返回
		else if(pointer->getvalue() >i){
			if(pointer->getleft() == NULL){ //左侧无节点了,插入
				pointer->left = new node(i);
				return ;
			}else
				pointer = pointer->left;
		}
		else
		{
			if(pointer->getright() == NULL){
				pointer->right = new node(i);
				return;
			}else
				pointer = pointer->right;
		}
	}
}
void searchTree::midOder(node *t){
	if(t != NULL){

		midOder(t->getleft());
		cout<<t->getvalue()<<" ";
		midOder(t->getright());
	}
}
bool searchTree::find(node *t,int v,long long &y){
	//find node value equal to 'v' in tree whose root named 't'

	if(t == NULL){y++;return false; }
	if(t->getvalue() == v){y++; return true;}
	if(t->getvalue() > v){
		y++;
		return find(t->left,v,y);}
	if(t->getvalue() < v){
		y++;
		return find(t->right,y);}
}

int data_array[1000001];   //all scorp
long long x,y,z;//x表示顺序查找次数,y表示二叉树,z表示哈希法
void shunxu(){
		int n,m;   int t;
		ifstream fin3("data_in.txt");
		ofstream fout3("shunxu_out.txt");
		fin3>>n>>m;
		cout<<"n和m的值分别为:"<<n<<" "<<m<<endl;//
		for(int i=0;i<n;i++){
			fin3>>data_array[i];
		}
		//顺序查找,m*n   all "NO" ?
		bool flag = false;
		for(int i=0;i<m;i++){
			fin3>>t;
			for(int j=0;j<n;j++){
				x++;
				if(t == data_array[j]){
					flag = true;
					//找到了就跳出循环
					break;}
			}
			if(flag)
				fout3<<"YES"<<endl;
			else
				fout3<<"No"<<endl;
			flag = false;
		}
		fin3.close();
		fout3.close();
		cout<<"shunxu_finished"<<endl;
}

void tree(){
		int n,m;   int t;
		ifstream fin3("data_in.txt");
		ofstream fout3("tree_out.txt");
		fin3>>n>>m;
		cout<<"n和m的值分别为:"<<n<<" "<<m<<endl;//

		//二叉树查找
		searchTree tree(t);
		node * tempNode = &tree.getRoot();
		for(int i=1;i<n;i++)
		{
			fin3>>t;
			tree.insert(tempNode,t);
		}
		bool flag;
		for(int i=0;i<m;i++){
			fin3>>t;
			flag = tree.find(tempNode,t,y);
			if(flag)
				fout3<<"YES"<<endl;
			else
				fout3<<"NO"<<endl;
		}
		fin3.close();
		fout3.close();
		//tree.midOder(tempNode);
		cout<<"tree_finished"<<endl;
}
struct cnode{
	cnode(){}
	cnode(int n){value = n;next = NULL;}
	int value;
	struct cnode *next;
};
struct cnode nodearray[10007];

void haxi(){
	int n,m,haxi;
	ifstream fin3("data_in.txt");
	ofstream fout3("haxi_out.txt");
	fin3>>n>>m;
	cout<<"n和m的值分别为:"<<n<<" "<<m<<endl;//

	struct cnode *temp_cnode,*t_cnode;
	for(int i=0;i<n;i++){
		//构建哈希表(拉链法)
		fin3>>t;
		haxi = t % 10007;     //10007,为比10000大的质数
		temp_cnode = new cnode(t);
		t_cnode = nodearray[haxi].next;
		nodearray[haxi].next = temp_cnode;
		temp_cnode->next = t_cnode;
	}
	for(int i=0;i<m;i++){
		//查找哈希表
		bool flag = false;
		fin3>>t;
		haxi = t % 10007;
		temp_cnode = nodearray[haxi].next;
		while(temp_cnode != NULL){
			z = z + 1;
			if(temp_cnode->value == t){
				flag = true;

				break;}
			temp_cnode = temp_cnode->next;
		}
		if(flag)
			fout3<<"YES"<<endl;
		else
			fout3<<"NO"<<endl;
	}
	fin3.close();
	fout3.close();
	cout<<"haxi_finished"<<endl;
}
int main() {
	//每次分析一组数据,每组数据的文件标为data_in.txt 。输出文件为3种
	//分别为shunxu_out.txt  tree_out.txt   haxi_out.txt
	shunxu();
	tree();
	haxi();
	cout<<"3种方法的比较次数分别为:"<<endl;
	cout<<x<<"  "<<y<<"  "<<z;
	return 0;
}



测试结果:

第一组:(正序)

顺序查找所需时间为:10

二叉排序树查找时间为:4

哈希表法所用查找时间为:1

3种方法的比较次数分别为:

99999888284762413199917

第二组:(逆序)

顺序查找所需时间为:9

二叉排序树查找时间为:3

哈希表法所用查找时间为:1

3种方法的比较次数分别为:

99999546326485899926

第三组:(随机10000)

顺序查找所需时间为:9

二叉排序树查找时间为:2

哈希表法所用查找时间为:1

3种方法的比较次数分别为:

9999856681741928100014

第四组:(随机100000)

顺序查找所需时间为:82

二叉排序树查找时间为:2

哈希表法所用查找时间为:1

3种方法的比较次数分别为:

99996023492324639998328

第五组:(随机1000000)

顺序查找所需时间为:871

二叉排序树查找时间为:5

哈希表法所用查找时间为:3

3种方法的比较次数分别为:

9994500525528387819985419


ps,第一个交的

原文链接:https://www.f2er.com/datastructure/383191.html

猜你在找的数据结构相关文章