华中科技大学文华学院《算法分析与设计》课程设计报告
专业：计算机科学与技术
班级：2班
姓名：肖红红
学号：0701********
指导老师：秦明
设计时间：5周-12周
目录
实验1 用分治法进行归并分类
1.1归并分类思想........................................... (3)
1.2归并分类流程图 (3)
1.3归并分类源程序 (4)
1.4归并分类结果截图 (5)
实验2 用分治法进行快速分类
2.1快速分类思想及代码 (6)
2.2快速分类流程图 (7)
2.3快速分类源程序 (8)
2.4快速分类结果截图 (8)
实验3 贪心算法求背包问题
3.1 背包问题思想................................... (9)
3.2 背包问题流程图 (9)
3.3背包问题源程序 (10)
3.3 背包问题结果截图 (11)
实验4 贪心算法求单源点最短路径
4.1单源点最短路径思想 (12)
4.2单源点最短路径流程图 (12)
4.3单源点最短路径源程序 (13)
4.4单源点最短路径结果截图 (14)
心得体会 (15)
实验一：《归并排序》
1.1归并排序设计思想：
归并排序采用的是分治策略，主要分为3个过程。
第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素。
第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作。
第三, 合并: 将已分类的两个序列合并成一个含有n个元素的分好累的序列,并生成最后的排序结果。
1.2归并排序流程图如下：
1.3源程序如下：
#include
#define LENGTH 50
int a[LENGTH],b[LENGTH]; 设置数组
void Mergr(int low,int mid,int high) //使用辅助数组归并两个已经分类的集合{
int h,j,k,i;
h=low;
j=mid+1;
k=low;
while(h<=mid&&j<=high) //当2个集合都没有取尽时
{
if(a[h]<=a[j])
{
b[k]=a[h];
h++;
}
else
{
b[k]=a[j];
j++;
}
k++;
}
if(h>mid) //处理剩余的元素
{
for(i=j;i<=high;i++)
{
b[k]=a[i];
k++;
}
}
else
{
for(i=h;i<=mid;i++)
{
b[k]=a[i];
k++;
}
}
for(i=low;i<=high;i++) //将已经归并的集合复制到数组A {
a[i]=b[i];
}
}
void Mergesort(int low,int high) //归并分类
{
int mid;
if(low{
mid=(int)((high+low)/2);
Mergesort(low,mid); //将一个子集合分类
Mergesort(mid+1,high); //将另一个子集合分类 Mergr(low,mid,high); //归并2个已经分类的集合 }
}
void main()
{
int i,length;
printf("Please input the total numbers:\n");
scanf("%d",&length);
printf(" input your members:\n");
for(i=0;iscanf("%d",&a[i]);
}
Mergesort(0,length-1);
printf("The new Mergesort numbers:\n");
for(i=0;iprintf("%d ",a[i]);
}
}
1.4结果截图：
实验二：《快速分类》
2.1快速分类设计思想：
快速分类是通过反复对产生的文件进行划分来实现的。其主要过程大致可以分为以下3个步骤。
第一，划分元素：将A[p..q]划分成两个非空的子序列A[p..j]和A[j+1..q]，使得A[p..j]中的任一元素小于或等于A[j+1..q]中的任一元素。下标j在划分过程中确定.
具体的划分过程可由如下的方法来实现：选取A[p..q]的某个元素，譬如说v=A(s)，然后将其它元素重新排列，使A[p..q]中所有在v以前出现的元素都小于或等于v，而所有在v后面出现的元素都大于或等于v。
第二，递归求解：通过递归调用快速分类算法分别对A[p..j-1]和A[j+1..q]进行分类第三，合并(Merger) ：由划分的特点知，在A[p..j-1]和A[j+1..q]都分好类后不就已分好类。
1.2快速分类算法流程图如下：
