|
|
HUBEI UNIVERSITY OF AUTOMOTIVE TECHNOLOGY
数据结构
课程设计报告
课设题目：
| | 专 业：
| | 班 级：
| | 姓 名：
| | 完成日期：
| | 指导教师：
| |
一．设计题目
Ø课程设计题目：多种查找方式的比较
Ø实现的功能：
1. 顺序查找
2. 二分查找
3. 哈希查找
v顺序查找
1. 随机产生随机数 2. 手动输入产生随机数 3. 建立线性表进行顺序查找
v二分查找
1. 随机产生随机数 2. 对产生的随机数进行冒泡排序（由大到小） 3. 进行二分查找
v哈希查找
1.手动输入产生随机数 2. 进行哈希查找
Ø各种查找的简单介绍：
1> 顺序查找
查找是在程序设计中最常用到的算法之一，假定要从n个整数中查找x的值是否存在，
最原始的办法是从头到尾逐个查找，这种查找的方法称为顺序查找。
顺序查找的程序如下：
# include <stdio.h>
# define N 15
int main(void)
{
void bi_search(int a[],int n,int x);
int a[100];
int x, i;
int n = 15;
printf("input the numbers:\n");
for(i=0; i<n;i++ )
scanf("%d",&a)
printf("input x:\n");
scanf("%d", &x);
bi_search(a,n,x);
}
void bi_search(int a[], int n, int x)
{
int i = 0;
int find = 0;
while(i<n)
{
if(x==a)
{
printf("find:%3d,it is a[%d]",x,i);
printf("\n");
find = 1;
}
i++;
if(i!=find)
printf("%3d not been found!\n", x);
}
2> 二分查找
/* 当前查找区间R[low..high]非空,使用(low+high)/2会有整数溢出的问题,问题
会出现在当low+high的结果大于表达式结果类型所能表示的最大值时，这样，产生
溢出后再/2是不会产生正确结果的，而low+((high-low)/2)不存在这个问题*/
int BinSearch(SeqList*R, int n, KeyType K)
{
/* 在有序表R[0..n-1]中进行二分查找，成功时返回结点的位置，失败时返回-1 */
int low = 0, high = n-1, mid; /* 置当前查找区间上、下界的初值 */
while(low <= high)
{
if(R[low].key == K)
return low;
if(R[high].key == k)
return high;
mid = low+((high-low)/2);
if(R[mid].key == K)
return mid;//查找成功返回
if(R[mid].key > K)
high = mid-1;//继续在R[low..mid-1]中查找
else
low = mid+1;//继续在R[mid+1..high]中查找
}
if(low > high)
return-1;//当low>high时表示所查找区间内没有结果，查找失败
}
3> 哈希查找
① 常用的哈希函数构造方法有：
l直接定址法
l除留余数法
l乘余取整法
l数字分析法
l平方取中法
l折叠法
l随机数法
② 本程序采用的是除留余数法:
Hash(key)=key mod p (p是一个整数)
2特点：以关键码除以p的余数作为哈希地址。
2关键：如何选取合适的p？p选的不好，容易产生同义词
2技巧：若设计的哈希表长为m，则一般取p≤m且为质数
（也可以是合数，但不能包含小于20的质因子）。
二．设计目的
通过此三种算法的比较，突出各自的优缺点:
顺序查找过程：从表中的最后一个记录开始，逐个进行记录的关键字与给定值进行比较，若某个记录的关键字与给定值相等，则查找成功，找到所查的记录；反之，若直到第一个记录，其关键字和给定值比较都不相等，则表明表中没有所查的记录，查找失败。
算法描述为
int Search(int d,int a[],int n)
{
/*在数组a[]中查找等于D元素，若找到，则函数返回d在数组中的位置，否则为0。其中n为数组长度*/
int i ；
/*从后往前查找*/
for(i=n-1;a!=d;--i)
return i ;
/*如果找不到，则i为0*/
}
此算法在数据的复杂度比较小的时候比较方便和占有优势，但当查找的数据量很庞大时，此算法就显得有点不适用了。
二分查找又称折半查找，它是一种效率较高的查找方法。
其流程图如下：
【二分查找要求】 1. 必须采用顺序存储结构 2. 必须按关键字大小有序排列。
【优 缺 点】 折半查找法的优点是比较次数少，查找速度快，平均性能好;其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
哈希查找
1. 基本原理
我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数， 也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素"分类"，然后将这个元素存储在相应"类"所对应的地方。
但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了"冲突"，换句话说，就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。
总的来说，"直接定址"与"解决冲突"是哈希表的两大特点。
2. 函数构造
构造函数的常用方法（下面为了叙述简洁，设 h(k) 表示关键字为 k 的元素所对应的函数值）：
a) 除余法：
选择一个适当的正整数 p ，令 h(k ) = k mod p
这里， p 如果选取的是比较大的素数，效果比较好。而且此法非常容易实现，因此是最常用的方法。
三．总体设计
Ø程序框架图：
Ø函数调用流程图：
四．详细设计步骤
1.搭建程序的整个框架
# include<stdio.h>
void printSeq();//随机顺序查找法
void printBin();//二分查找法
void hashtable();//哈希查找
int main(void)
{
return 0;
}
printSeq();//随机顺序查找法
{
}
printBin();//二分查找法
{
}
hashtable();//哈希查找
{
}
2.头文件的添加
# include "iostream"
# include "stdlib.h"
# include "stdio.h"
# include <time.h>
# include "malloc.h"//动态内存分配的头文件
3.定义相关的结构体数据类型
using namespace std;
typedef int ElemType; //ElemType类型为int类型 即ElemType等价于int
int size = 0; //哈希表的长度
4.相关参数的宏定义
# define maxsize 100
# define m 19 //m = 19
# define free 0 //free = 0
# define sucess 1 //sucess = 1
# define unsucess 0 //unsucess = 0
# define MAX 11 //MAX = 11
# define hm 20 //hm = 20
# define keytype int //keytype类型为int型
5.主函数中调用其它功能模块的函数
6.写出主函数中被调用的函数
üvoid printSeq()//随机顺序查找法
üvoid printBin()//二分查找法
üvoid hashtable()//哈希查找
üvoid Sort(SSTable *table )
üvoid stable create_s(stable r)
üvoid PrintTable(SSTable *table)
üvoid Destroy(SSTable *table)/* 函数：销毁 */
üvoid FillTable(SSTable *table)/* 函数：判断是否已满 */
üvoid Create(SSTable **table, int length)/* 创建 */
üvoid hashcreate(hashtable ht[], keytype key)
üvoid search_shoudong()//随机顺序手动查找法
üint show()
üint search_s(keytype k,stable *r)
üint HashFunction(keytype key)/*散列函数*/
üint hashsearch(hashtable ht[], keytype key)
üint Search_Bin(SSTable *table, ElemType key)
üint Search_Seq(SSTable *table, ElemType key)/* 函数：查找 */
7.先写出相关被调函数的伪代码
举例：判断建立的时间表是否已满
If（时间表长度为满）
Printf(“创建失败！\n”);
else
Printf(“创建成功！\n”);
8.用C或C++……等语言将伪代码描述出来
9.若被调函数放在主函数之后，则要进行函数的声明；相反则不需要
10.进行程序的简单调试及修改
11.对用户的违法输入的操作的调试及修改
12.进一步的对程序中的bug进行调试及修改
13.功能的进一步扩充及完善
五．设计结果与分析
1)设计的运行结果
2运行菜单的主界面：
2顺序查找界面：
u顺序随机查找的三种调试结果：
u顺序手动输入查找的三种调试结果：
2二分查找界面：
2哈希查找界面：
2) 调试分析
l调试时注意哪些问题
1. 除了输入的信息提示外还可以进行非法的输入
2. 对垃圾的垃圾字符的回收
3. 注意缓冲和清屏
l如何去调试程序
1. 调试时具有随机性和非法性输入
2. 调试的结果不能太单一，如产生的随机种子要有正、负数和零
l如何去修改程序的bug（漏洞）
1. 一个好的程序是调试出来的
2. 边试边调试不断地修改
3. 通过非法或任意输入来修改程序的漏洞
l如何去排除掉用户的非法输入
1. 对输入的垃圾字符进行回收
2. 对相关的菜单界面进行缓冲和清屏
3. 调试程序时要全面，防止出现用户的非法输入
l如何去使自己的程序更全面
1. 不断地调试和完善
2. 通过不同的用户来调试反馈相关问题并完善之
3. 使程序更加精简和通俗易懂
l找用户进行调试来反馈问题
1. 这是一个产品进入市场前的一个关键步骤，如一款游戏或软件会标注试用版，通
过用户的试用来反馈一些问题
l进一步完善程序中的漏洞
[color=#ff0000,strength=3)"]六．总结（收获和不足）
总结是对所学的知识的一种总结，是一种很好的学习方法，不管是现在的学习总结还是今后走向工作岗位时的工作总结都会让自己受益匪浅。
通过多天的漫长学习，自己和组员终于完成了此课程设计，自己不断是收获了知识也收获了团队精神。
大的程序的开发周期都是很漫长的，长的会达两年或两年以上的开发期。所以一个人是无法完成这样巨大的工作量的，必须靠一个团队去完成。俗话说：“三个臭皮匠赛过诸葛亮”，这句话是很有道理的，自己的能力即使很强，也要靠团队去完成。不过话说回来，现在的这种意识还不是很强，搞技术的很多人更多的是个人的抱负。希望自己能搞出点惊天动地的东西出来，但是要是在公司的话，这绝对是不允许的。因为公司开发一个产品的周期时间还有限的，需要一个团队在最短的时间内去完成产品的设计。
从这次的数据结构的课程设计过程中深有体会，如何更好地去完成一个大的程序，就像开发一个大的软件。得有明确的分工，所以我们要去了解程序的特点，其中函数和指针是很有用的东西，通过这些可以将很大的程序高效的完成。
这就像好比开发一个大的软件，项目的负责人将程序的主框架搭好，定义一些全局变量，并，列举出要调用的功能函数名称，项目负责组只要完成主函数的调用很简单的编写。而那些功能函数模块则交给下面那些程序员来分组完成。最后将所有的功能函数整合到一起。一个大的软件的开发过程就完成的四分之一了。还有二分之一的时间是来调试错误和完善功能，所以说好的程序不是写出来的而是调试出来的。所以我们小组三人在这次程序调试过程中实现了很好的分工，老师看完程序后要求进行三个功能方面的修改：1. 程序产生的随机数是随机的要包括正、负数和零。 2. 查找实现随机查找和手动输入查找。 3.对二分查找中的冒泡排序由低到高排序改为从高到低排序。 4. 完善哈希查找的功能。
我们小组进行了分工，每人完成一个功能的修改，最后整合到一个程序中。我们很快各自完成了自己的那块，最后整合到了一起。当然由于能力的有限，小组对最后的哈希查找功能的完善没有实现。最后在验收的过程中还是通过了。
当然此次的课程设计走了很多弯路，在刚开始的时候没有确定目标对象，所以导致了后面出现了两个备案，两个任务进行来回之间的切换，造成了时间的浪费。这是我们此次学习过程中吸取的一个教训。
通过此次的课程设计，自己对数据结构的学习和理解又上升了一个层次，自己不断地在进步。自己所希望对的就是要达到这个效果。
此次的学习让自己意识到很多方面的不足，对哈希查找和二叉树的相关知识还不够熟悉，导致最后一个功能模块没能很好的完成，所以后面还需要不断地学习。这门课程是计算机课程中的一门核心课程，学完后感觉眼界大开。
学完这门课程后，对函数的理解又上升了一个层次。原来在学习C语言时还不懂什么是函数，也不知道函数是用来干什么的。那时区分不清楚编程中的函数与数学中的函数有什么区别。所以当我们对一个东西不理解时，我们是无法去驾驭它的，更谈不上去编写出优秀的代码。
学习编程是一个漫长的过程，从大一的文盲到现在的菜鸟是一种进步，是一个漫长的过程，也是一个漫长的积累。自己在这方面走了不少弯路，也下了不少功夫，但是效果不是很明显。
在后面的学习过程中，这门课程的地位依然是显得那么重要，后面的计算机课程、单片机学习课程是和数据结构的学习是离不开的。
说了这么还是说明了这门课程的重要性，要学好这门课程，不是一两年就能搞定的，要不断的运用到实践中和反复的去理解和体会。
还有一点是：老师上课讲的更多是伪代码而不是实际程序，理解一个伪代码几分钟就可以搞定，但是理解代码的话不就那么简单了。要把它写出来更是难上加难了。所以不能停留在表面，程序必须要自己去写和调试，这样才能真正的理解和掌握，不然永远都不可能写出一手好的代码。
通过数据结构的学习，自己对计算机的底层一些东西也是有了一些理解。如，伪代码、编译和链接等等。
“伪代码”很明显是假代码的意思，它是由编译器来识别的，计算机是不承认它的，因为计算机跑的只有“0”和“1”，这些伪代码当然有它的作用，它会告诉编译器从何处执行，执行到何处时该怎么办。
所以通过数据结构的学习将前前后后的知识都穿插了起来，就像指针一样。前前后后学习的知识是离散的，分布在大脑的各个部分，数据结构就好比这个指针，将它们前前后后串起来了。这是比较有意思的，似乎好多的东西和思想是相通的，不管是什么专业领域。可谓“万变不离其宗”。
[color=#ff0000,strength=3)"]附源代码：
/*
课题名称：各种查找方法的比较
小组成员：曾奕云 袁能峰 汪一帆
时 间：2014年7月5日
*/
# include "iostream"
# include "stdlib.h"
# include "stdio.h"
# include "malloc.h"//动态内存分配的头文件
# define MAX 11 //MAX = 11
# define hm 20 //hm = 20
using namespace std;
# include <time.h>
typedef int ElemType; //ElemType类型为int类型 即ElemType等价于int
# define keytype int //keytype类型为int型
#define maxsize 100
# define m 19 //m = 19
# define free 0 //free = 0
# define sucess 1 //sucess = 1
# define unsucess 0 //unsucess = 0
int size = 0; //哈希表的长度
/*定义一个名为sstable结构体数据类型 包含两部分int *elem 和 int length */
typedef struct sstable
{
ElemType *elem;
ElemType length;
} SSTable; //SSTable 等价于 struct sstable
typedef struct hashtable
{
keytype key;
}hashtable;//hashtable 等价于 struct hashtable
/*顺序表结构体定义*/
typedef struct
{
keytype key[maxsize];
int len;
}stable;
int show();
void Create(SSTable *table, int length);//创建
void Destroy(SSTable *table);//销毁
int Search_Seq(SSTable *table, ElemType key);//查找 有返回值
/* 创建 */
void Create(SSTable **table, int length)
{
SSTable *t = (SSTable*) malloc(sizeof(SSTable));
t->elem = (ElemType*)malloc(sizeof(ElemType)*(length+1));
t->length = length;
*table = t;
}
/* 函数：判断是否已满 */
void FillTable(SSTable *table)
{
ElemType *t = table->elem;
srand(time(NULL));
for(int i=0; i<table->length; i++)
{
t++;
*t = 90-rand()%100;
}
}
/* 函数：销毁 */
void Destroy(SSTable *table)
{
free(table->elem); //先保存后释放
free(table);
}
/* 函数：显示 */
void PrintTable(SSTable *table)
{
int i;
ElemType *t = table->elem;
for(i=0; i<table->length; i++)//进入循环，依次打印表中元素
{
t++;
printf("%d ", *t);
}
printf("\n");
}
/* 函数：查找 */
int Search_Seq(SSTable *table, ElemType key)
{
int result;
int i;
for (i=table->length; i>=1; i--)
{
if (table->elem==key)
{
result = i;
break;
}
}
return result; //将result的只返回到函数：顺序查找 void printSeq()
}
/* 顺序查找 */
void printSeq()
{
SSTable *table;
int r;
int n;
ElemType key;//等价于int key;
printf("请输入元素个数:");
scanf("%d", &n);
rewind(stdin);/* 清缓冲 */
Create(&table, n); //随机创建 n 个元素
FillTable(table); //判断所输入的个数 n 是否溢出
printf("您输入的%d 个值是：", n);
PrintTable(table);
printf("请输入关键字的值:");
scanf("%d", &key);
rewind(stdin);/* 清缓冲 */
printf("\n");
printf("顺序查找法运行结果如下：\n\n ");
Search_Seq(table, key);
r = Search_Seq(table, key);
if(r > 0)
{
printf("关键字%d 在表中的位置是：%d\n", key, r);
printf("\n");
system("pause");
system("cls");
}
else
{
printf ("查找失败，表中无此数据。\n\n");
system("pause");
system("cls");
}
}
/* 函数：冒泡排序 */
void Sort(SSTable *table )
{
int i, j;
ElemType temp;
for (i=table->length; i>=1; i--)
{
for (j=1; j<i; j++)
{
if(table->elem[j]<table->elem[j+1])
{
temp = table->elem[j];
table->elem[j] = table->elem[j+1];
table->elem[j+1] = temp;
}
}
}
}
/* 函数：二分法查找 */
int Search_Bin(SSTable *table, ElemType key)
{
int low = 1;
int high = table->length;
int result = 0;
while(low <= high)
{
int mid = (low+high)/2;
if(table->elem[mid]==key)
{
result = mid;
break;
}
else if(key<table->elem[mid])
{
low = mid+1;
}
else
{
high = mid-1;
}
}
return result;
}
/* 函数：二分法查找、排序及输出 */
void printBin()
{
SSTable *table;
int r;
int n;
ElemType key;
printf("请输入元素个数:");
scanf("%d", &n);
if (n<0)
{
printf("输入有误，请重新选择!\n");
system("pause");
system("cls");
n = show();
system("pause");
system("cls");
printf("\n");
}
else
{
Create(&table, n);
FillTable(table);
printf("您输入的%d 个值是：\n",n);
PrintTable(table);
printf("请输入关键字的值:");
scanf("%d", &key);
rewind(stdin);/* 清缓冲 */
printf("\n");
Sort(table);
printf("数据排序后的顺序如下：\n\n ");
PrintTable(table);
printf("\n");
printf("二分查找法的运行结果如下：\n\n ");
r = Search_Bin(table, key);
if( r > 0)
{
printf("关键字%d 在表中的位置是：%d\n", key, r);
system("pause");
system("cls");
}
else
{
printf ("查找失败，表中无此数据。\n\n");
system("pause");
system("cls");
}
}
}
/*散列函数*/
int HashFunction(keytype key)
{
return key % (hm - 5);
}
/*创建hash表*/
void hashcreate(hashtable ht[], keytype key)
{
int index = HashFunction(key);
if(size == hm-1 || ht[index].key == key) //hash表已满
return;
//无冲突
if(ht[index].key==0)
ht[index].key = key;
else//冲突
{
do{
index = (index + 1) % hm; //解决冲突函数
}while(ht[index].key != 0);
ht[index].key = key;
}
size++;
}
/* 函数：哈希查找 */
int hashsearch(hashtable ht[], keytype key)
{
int f = 0; //查找失败次数
int index = HashFunction(key);
while(f <= hm)
{
if(ht[index].key == key)
return index;
else
index = (index + 1) % hm;
f++;
}
return -1;
}
/* 哈希查找 */
void hashtable()
{
int val;
printf("请输入要建立哈希表的元素：\n");
scanf("%d", &val);
system("pause");
system("cls");
//1. 建立哈希表
//2. 创建是否成功
//3. 输入要查找的元素
}
/* 主界面菜单 */
int show()
{
int i = -1;
printf("\n\n\n\n\n");
printf("\t\t\t***********主菜单界面***********\n");
printf("\t\t\t*** ***\n");
printf("\t\t\t*** 1. 顺序查找 ***\n");
printf("\t\t\t*** 2. 二分查找 ***\n");
printf("\t\t\t*** 3. 哈希查找 ***\n");
printf("\t\t\t*** 4. 退出程序 ***\n");
printf("\t\t\t*** ***\n");
printf("\t\t\t********************************\n");
printf("\t\t\t请输入选项(1-4):");
scanf("%d", &i);//输入要数字选择要使用的查找方法
return i;
}
/*建立线性表*/
stable create_s(stable r)
{
int i, j = 0, k = 1;
printf("请输入顺序表元素，要为整形，用空格分开，-99为结束标志：\n");
scanf("%d",&i);
while(i!=-99)
{
j++;
r.key[k]=i;
k++;
scanf("%d",&i);
}
r.len=j;
return r;
}
/*手动顺序表查找*/
int search_s(keytype k,stable *r)
{
int j;
j=r->len;
r->key[0]=k;
while(r->key[j]!=k)
j--;
return j;
}
void search_shoudong()
{
stable a;
int i;
int k;
a = create_s(a);
while(i!=-1)
{
printf("\n输入待查关键字(输入-1结束查找)：");
scanf("%d",&i);
k=search_s(i,&a);
if(i==-1)
{
getchar();
break;
}
if(k==0)
{
printf("顺序表中待查元素不存在\n");
}
else
{
printf("顺序表中待查元素位置是：%d",k);
printf("\n");
}
}
system("pause");
system("cls");
//1.输入元素建立线性表
//2.判断是否建立成功
//3.输入查找的元素
//4.if(查找成功)
// 输出查找的结果
// else
// 查找失败
}
/* 主函数 */
int main(int argc, char* argv[])
{
int i, choice;
system("color 5");
do
{
i = show();
switch(i)
{
case 1:
printf("\n");
printf("*********************************** 顺序查找 *********************************** \n");
printf("查找的方法：1. 随即查找 2. 手动输入查找 \n");
scanf("%d", &choice);
if(1 == choice)
printSeq();//随机顺序查找法
else
{
search_shoudong();
}
break;//跳出循环}
case 2:
printf("\n");
printf("*********************************** 二分查找 *********************************** \n");
printBin();//二分查找法
break; //跳出循环
case 3:
printf("\n");
printf("*********************************** 哈希查找 *********************************** \n");
hashtable();//哈希查找
break; //跳出循环
case 4:
printf("\n");
printf("\n欢迎使用该系统，再见!\n");
system("pause");
exit(0);
default:
printf("输入选项有误，请重新输入!\n");
rewind(stdin);//等价于fflush(stdin);清缓冲 不然输入垃圾字符就陷入了死循环
system("pause");
system("cls");
break;
}
}while(i!=4);
return 0;
}
|
|
