《编程实训》
实验报告
专 业:计算机科学与技术
班 级:151班
学 号:
姓 名:
指导教师:
日 期:2016年6月30日
目录
一、需求
…………………………………………………………………………………3
1.任务要求……………………………………………………………………………………3
2.软件功能分析………………………………………………………………………………3
3.数据准备……………………………………………………………………………………3
二、概要设计…………………………………………………………………………………3
1.功能模块图………………………………………………………………………………4
2.模块间调用关系…………………………………………………………………………4
3.主程序模块………………………………………………………………………………5
4.抽象数据类型描述…………………………………………………………………………5
三、详细设计…………………………………………………………………………………6
1.存储结构定义………………………………………………………………………………6
2.各功能模块的详细设计……………………………………………………………………7
四、实现和调试………………………………………………………………………………7
1.主要的算法………………………………………………………………………………7
2.主要问题及解决…………………………………………………………………………8
3.测试执行及结果……………………………………………………………………………8
五、改进………………………………………………………………………………………9
六、附录……………………………………………………………………………………9
1.查找源程序………………………………………………………………………………9
2.排序源程序………………………………………………………………………………9
目录
1 需求分析
1.1 任务要求
对于从键盘随机输入的一个序列的数据,存入计算机内,给出各种查找算法的实现;以及各种排序算法的实现。
1.2 软件功能分析
任意输入n个正整数,该程序可以实现各类查找及排序的功能并将结果输出。
1.3 数据准备
任意输入了5个正整数如下:
12 23 45 56 78
2 概要设计(如果2,3合并可以省略2.4)
2.1 功能模块图(注:含功能说明)
2.2 模块间调用关系
2.3 主程序模块
2.4 抽象数据类型描述
存储结构:数据结构在计算机中的表示(也称映像)叫做物理结构。又称为存储结构。数据类型(data type)是一个“值”的集合和定义在此集合上的一组操作的总称。
3 详细设计
3.1 存储结构定义
查找:
typedef int ElemType ;
//顺序存储结构
typedef struct
{
ElemType *elem; //数据元素存储空间基址,建表时按实际长度分配,号单元留空
int length; //表的长度
}SSTable;
排序:
typedef struct
{ //定义记录类型
int key; //关键字项
}RecType;
typedef RecType SeqList[Max+1]; //SeqList为顺序表,表中第0个元素作为哨兵
3.2 各功能模块的详细设计
查找:
void Create(SSTable *table, int length); // 构建顺序表
void FillTable(SSTable *table) // 无序表的输入
int Search_Seq(SSTable *table, ElemType key); //哨兵查找算法
void Sort(SSTable *table ) // 排序算法
int Search_Bin(SSTable *table, ElemType key) // 二分法查找(非递归)
排序:
void InsertSort(SeqList R) //对顺序表R中的记录R[1‥n]按递增序进行插入排序
void BubbleSort(SeqList R) //自下向上扫描对R做冒泡排序
int Partition(SeqList R,int i,int j)//对R[i‥j]做一次划分,并返回基准记录的位置
void QuickSort(SeqList R,int low,int high) //R[low..high]快速排序
void SelectSort(SeqList R) //直接选择排序
void Heapify(SeqList R,int low,int high) //大根堆调整函数
void MergePass(SeqList R,int length) //归并排序
4 实现和调试
4.1 主要的算法
查找:
①建立顺序存储结构,构建一个顺序表,实现顺序查找算法。
typedef struct {
ElemType *elem; //数据元素存储空间基址,建表时按实际长度分配,号单元留空
int length; //表的长度
} SSTable;
②对顺序表先排序后,实现行二分法查找相关操作。
③定义二叉树节点,根据节点的值进行查找,并且实现节点的插入,删除等操作。
typedef struct BiTnode { //定义二叉树节点
int data; //节点的值
struct BiTnode *lchild,*rchild;
}BiTnode,*BiTree;
④定义哈希表以及要查找的节点元素,创建哈希表,实现其相关查找操作。
typedef struct {
int num;
} Elemtype; //定义查找的结点元素
typedef struct {
Elemtype *elem; //数据元素存储基址
int count; //数据元素个数
int sizeindex;
}HashTable;//定义哈希表
排序:
2. 排序相关实验内容及步骤。
①定义记录类型。
typedef struct{
int key; //关键字项
}RecType;
②实现直接插入排序:每次将一个待排序的记录,按其关键字大小插入到前面已排序好的子文件中的适当位置,直到全部记录插入完成为止。
③实现冒泡排序:设想被排序的记录数组R[1‥n]垂直排序。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R,凡扫描到违反本原则的轻气泡,就使其向上“漂浮”(交换),如此反复进行,直到最后任意两个气泡都是轻者在上,重者在下为止。
④实现快速排序:在待排序的n个记录中任取一个记录(通常取第一个记录),把该记录作为支点(又称基准记录)(pivot),将所有关键字比它小的记录放置在它的位置之前,将所有关键字比它大的记录放置在它的位置之后(称之为一次划分过程)。之后对所分的两部分分别重复上述过程,直到每部分只有一个记录为止。
⑤实现直接选择排序:第i趟排序开始时,当前有序区和无序区分别为R[1‥i-1]和R[i‥n](1≤i≤n-1),该趟排序则是从当前无序区中选择出关键字最小的记录R[k],将它与无序区的的第一个记录R[i]交换,有序区增加一个记录,使R[1‥i],和R[i+1‥n]分别为新的有序区和新的无序区。如此反复进行,直到排序完毕。
⑥实现堆排序:它是一种树型选择排序,特点是:在排序的过程中,将R[1‥n]看成是一个完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系,在当前无序区中选择关键字最大(或最小)的记录。即:把待排序文件的关键字存放在数组R[1‥n]子中,将R看成是一棵二叉树,每个结点表示一个记录,源文件的第一个记录R[1]作为二叉树的根,以下各记录R[2‥n]依次逐层从左到右排列,构成一棵完全二叉树,任意结点R[i]的左孩子是R[2i],右孩子是R[2i+1],双亲是R[i/2]。
⑦实现二路归并排序:假设初始序列n个记录,则可看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到[n/2]个长度为2或1的有序子序列;再两两归并,……,如此重复,直到一个长度为n的有序序列为止。
4.2 主要问题及解决
在实验前对于各种查找和排序的算法不是很熟悉,所以花了一些时间去复习。有些代码反复测试还是找不出错误,最后也是翻阅了书本并仔细思考才改进了算法并成功测试出了结果。这次试验大大提升了我对排序算法及查找算法的熟练程度。
4.3 测试执行及结果
查找算法:
任意输入若干正整数并测试如下:
排序算法:
任意输入数字并测试如下:
5 改进
根据提示的代码,经过一系列调试后最终出了结果。在一开始运行时总是出错,特别是二叉树的测试,代码有些小错误导致测试的时候程序总是出错。最后改动了一下提高了程序的稳定性并成功运行出了结果。
6 附录
【附录1----查找源程序】
#include"iostream"
#include"stdlib.h"
#include"stdio.h"
#include "malloc.h"
#define MAX 11
using namespace std;
typedef int ElemType ;
//顺序存储结构
typedef struct
{
ElemType *elem; //数据元素存储空间基址,建表时按实际长度分配,号单元留空
int length; //表的长度
}SSTable;
void Create(SSTable *table, int length);
void Destroy(SSTable *table);
int Search_Seq(SSTable *table, ElemType key);
void Traverse(SSTable *table, void (*visit)(ElemType elem));
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;
for(int i=0; i
length; i++) //for循环,输入各个元素
{
t++;
scanf("%d", t); //输入元素
getchar();
}
}
void Destroy(SSTable *table) // 销毁表
{
free(table->elem);//释放元素空间
free(table);//释放表的空间
}
void PrintTable(SSTable *table) // 打印查找表
{
int i; //定义变量
ElemType *t=table->elem;
for(i=0; ilength; i++) //进入循环,依次打印表中元素
{
t++;
printf("%d ", *t); //打印输出
}
printf("\n");
}
int Search_Seq(SSTable *table, ElemType key) //哨兵查找算法
{
table->elem[0]=key; //设置哨兵
int result=0; // 找不到时,返回
int i;
for (i=table->length; i>=1;i--)
{
if (table->elem[i]==key)
{
result=i;
break;
}
}
return result; //返回结果
}
void printSeq()
{
SSTable *table; //先设置几个变量
int r;
int n;
ElemType key;
printf("请输入元素个数:");
scanf("%d",&n); //输入元素个数
Create(&table, n); //建立表
printf("请输入");cout<0)
{
printf(" 关键字%d 在表中的位置是:%d\n",key, r);//打印关键字在表中的位置
printf("\n");
}
else //查找失败
{
printf ("查找失败,表中无此数据。\n\n");
}
}
void Sort(SSTable *table ) // 排序算法
{
int i, j;
ElemType temp;
for (i=table->length; i>=1 ;i--) // 从前往后找
{
for (j=1; jelem[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) //low不大于high时
{
int mid=(low+high)/2;
if(table->elem[mid]==key) //如果找到
{
result=mid;
break;
}
else if(keyelem[mid]) //如果关键字小于mid对应的值
{
high=mid-1;
}
else
{
low=mid+1;
}
}
return result; //返回结果
}
void printBin()
{
SSTable *table; //声明变量
int r;
int n;
ElemType key;
printf("请输入元素个数:");
scanf("%d",&n);
Create(&table, n); //建立表
printf("请输入");cout<0)
printf("关键字%d 在表中的位置是:%d\n",key, r);
else
{
printf ("查找失败,表中无此数据。\n\n");
}
}
//二叉排序树
typedef struct BiTnode //定义二叉树节点
{
int data; //节点的值
struct BiTnode *lchild,*rchild; //节点的左孩子,节点的右孩子
}BiTnode,*BiTree;
//查找(根据节点的值查找)返回节点指针
BiTree search_tree(BiTree T,int keyword,BiTree *father)
{
BiTree p; // 临时指针变量
*father = NULL; //先设其父亲节点指向空
p = T; //p赋值为根节点(从根节点开始查找)
while (p && p->data!=keyword) //如果不是p不指向空且未找到相同值的节点
{
*father = p;//先将父亲指向自己(注意:这里传过来的father是二级指针)
if (keyword < p->data) //如果要找的值小于自己的值
p = p->lchild; // 就向自己的左孩子开始找
else
p = p->rchild; //否则向自己的右孩子开始查找
}
return p; //如果找到了则返回节点指针
}
BiTree creat_tree(int count)
{
BiTree T,p; //设置两个临时变量T,p
int i = 1;
while (i <= count)
{
if (i == 1) //如果i=1,说明还是空树
{
p = (BiTnode *)malloc(sizeof(BiTree));//使p指向新分配的节点
if (!p)//分配未成功
return NULL;
T = p;//分配成功,T=p( 这里实际上T就是根节点)
scanf("%d",&p->data);//输入p指向节点的值
p->lchild = p->rchild = NULL;//p的左孩子和右孩子都指向空