排序的实验报告

数据结构与算法设计

实验报告

（2016 — 2017 学年第1 学期）

实验名称：

年 级：

专 业：

班 级：

学 号：

姓 名：

指导教师：

成都信息工程大学 通信工程学院 一、 实验目的

验证各种简单的排序算法。在调试中体会排序过程。

二、实验要求

（1） 从键盘读入一组无序数据，按输入顺序先创建一个线性表。

（2） 用带菜单的主函数任意选择一种排序算法将该表进行递增排序，并显示出每一趟排序过程。

三、实验步骤

1、 创建工程（附带截图说明）

2、 根据算法编写程序（参见第六部分源代码）

3、 编译

4、 调试

四、实验结果图

图 1-直接输入排序

图 2-冒泡排序

图 3-直接选择排序

五、心得体会

与哈希表的操作实验相比，本次实验遇到的问题较大。由于此次实验中设计了三种排序方法导致我在设计算法时混淆了一些概念，设计思路特别混乱。虽然在理清思路后成功解决了直接输入和直接选择两种算法，但冒泡排序的算法仍未设计成功。虽然在老师和同学的帮助下完成了冒泡排序的算法，但还需要多练习这方面的习题，平时也应多思考这方面的问题。而且，在直接输入和直接选择的算法设计上也有较为复杂的地方，对照书本做了精简纠正。

本次实验让我发现自己在算法设计上存在一些思虑不周的地方，思考问题过于片面，逻辑思维能力太过单薄，还需要继续练习。

六、源代码

要求：粘贴个人代码，以便检查。

#include

#define MAXSIZE 100

typedef int KeyType;

typedef int DataType;

实验报告

课程 计算机算法设计与分析 实验名称 合并排序、快速排序

学号 姓名 实验日期：

实验一 合并排序、快速排序

一．实验目的

（1） 学习合并排序和快速排序算法的思想，掌握原理。

（2） 运用合并排序和快速排序算法的思想进行编程实现，以加深理解。

二．实验内容

（1）输入几个整数，运用合并排序的思想进行编程实现，输出正确的排序结果。

（2）输入10个整数，运用快速排序的思想进行编程实现，输出正确的排序结果

三．实验代码

(1)合并排序源代码如下：

#include //调用setw

#include //将b[0]至b[right-left+1]拷贝到a[left]至a[right]

template

void Copy(T a[],T b[],int left,int right)

{ int size=right-left+1;

for(int i=0;i

{

a[left++]=b[i];

}

} //合并有序数组a[left:i],a[i+1:right]到b,得到新的有序数组b

template

void Merge(T a[],T b[],int left,int i,int right)

{ int a1cout=left,//指向第一个数组开头

a1end=i,//指向第一个数组结尾

a2cout=i+1,//指向第二个数组开头

a2end=right,//指向第二个数组结尾

bcout=0;//指向b中的元素

for(int j=0;j

{ if(a1cout>a1end)

{ b[bcout++]=a[a2cout++];

continue; } //如果第一个数组结束，拷贝第二个数组的元素到b

if(a2cout>a2end)

实验四：查找与排序

【实验目的】

1. 掌握顺序查找算法的实现。

2. 掌握折半查找算法的实现。

【实验内容】

1. 编写顺序查找程序，对以下数据查找37所在的位置。

5，13，19，21，37，56，64，75，80，88，92

2. 编写折半查找程序，对以下数据查找37所在的位置。

5，13，19，21，37，56，64，75，80，88，92

【实验步骤】

1.打开VC++。

2.建立工程：点File->New，选Project标签，在列表中选Win32 Console

Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。

3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source

File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。

4．写好代码

5．编译－＞链接－＞调试

#include "stdio.h"

#include "malloc.h"

#define OVERFLOW -1

#define OK 1

#define MAXNUM 100

typedef int Elemtype;

typedef int Status;

typedef struct

{ Elemtype *elem;

int length;

}SSTable;

Status InitList(SSTable &ST )

{

int i,n;

ST.elem = (Elemtype*) malloc (MAXNUM*sizeof (Elemtype));

if (!ST.elem) return(OVERFLOW);

printf("输入元素个数和各元素的值:");

scanf("%d\n",&n);

for(i=1;i<=n;i++)

实 验 报 告

（ 2016 / 2017 学年 第 2 学期）

课程名称数据结构及应用算法教程实验内容 快速排序的实现

实验时间2017年5月19 日指导教师专 业 学院(系)计算机工程学院学生姓名学号 

实 验 报 告

实验名称 快速排序的实现

一、 实验目的和要求

对以下进行快速排序

32,12,7, 78, 23,45，54,78

二、实验内容 #include

#include

#define N 8

int partition(int arr[], int low, int high){

int key;

key = arr[low];

while(low

while(low = key )

high--;

if(low

arr[low++] = arr[high];

while( low

low++;

if(low

arr[high--] = arr[low];

}

arr[low] = key;

return low;

}

void quick_sort(int arr[], int start, int end){

int pos;

if (start

pos = partition(arr, start, end);

quick_sort(arr,start,pos-1);

quick_sort(arr,pos+1,end);

}

return;

}

int main(void){

int i;

int arr[N]={32,12,7, 78, 23,45，54,78};