第一篇：实验一线性表的创建与访问算法设计
内蒙古工业大学信息工程学院
四、编译程序：
#include
typedef char ElemType;typedef struct LNode
//定义单链表结点类型 {
ElemType data;
struct LNode *next;}LinkList;
LinkList *CreatlinkR(LinkList *L)
//用尾插法建立带头结点的单链表 {
LinkList *s, *r;char ch;r =(LinkList *)malloc(sizeof(LinkList));
//创建头结点
L = r;s = r;r->next = NULL;printf(“单链表元素值为单个字符, 连续输入，$为结束字符:”);while((ch = getchar())!= '$'){
r =(LinkList *)malloc(sizeof(LinkList));
//创建新结点
r->data = ch;
r->next = NULL;
s->next = r;
s = r;
} r->next=NULL;
//终端结点
return(L);}
void Sort(LinkList *h)
//单链表元素排序 { LinkList *p=h->next,*q,*t;
if(p!=NULL){
t=p->next;
p->next=NULL;
p=t;
while(p!=NULL)
{
t=p->next;
q=h;
第 页
内蒙古工业大学信息工程学院
while(q->next!=NULL&&q->next->data
data)
q=q->next;
//在有序表中找插入*p的前驱结点*q
p->next=q->next;
//将*p插到*q之后
q->next=p;
p=t;
} } }
void DispList(LinkList *L)
//输出单链表L {
LinkList *p=L->next;
while(p!=NULL){
printf(“%c ”,p->data);
p=p->next;} }
LinkList *Union(LinkList *La,LinkList *Lb,LinkList *Lc)
{ LinkList *pa=La->next,*pb=Lb->next,*s,*tc;
Lc=(LinkList *)malloc(sizeof(LinkList));
tc=Lc;while(pa!=NULL&&pb!=NULL){
if(pa->data
data)
{
s=(LinkList *)malloc(sizeof(LinkList));
s->data=pa->data;
tc->next=s;
tc=s;
pa=pa->next;
}
else if(pa->data>pb->data)
{
s=(LinkList *)malloc(sizeof(LinkList));
s->data=pb->data;
tc->next=s;
tc=s;
pb=pb->next;
}
else
{
第 页
//求两有序集合的并集 //复制结点
内蒙古工业大学信息工程学院
s=(LinkList *)malloc(sizeof(LinkList));
s->data=pa->data;
tc->next=s;
tc=s;
pa=pa->next;
//重复元素只复制一个
pb=pb->next;
} } if(pb!=NULL)
//复制余下结点
pa=pb;while(pa!=NULL){
s=(LinkList *)malloc(sizeof(LinkList));
s->data=pa->data;
tc->next=s;
tc=s;
pa=pa->next;
} tc->next=NULL;return(Lc);}
LinkList *InsterSect(LinkList *La,LinkList *Lb,LinkList *Lc)
//求两有序集合的交集 {
LinkList *pa=La->next,*pb,*s,*tc;
Lc=(LinkList *)malloc(sizeof(LinkList));
tc=Lc;
while(pa!=NULL){
pb=Lb->next;
while(pb!=NULL&&pb->data
data)
pb=pb->next;
if(pb!=NULL&&pb->data==pa->data)
//若pa结点值在pb中
{
s=(LinkList *)malloc(sizeof(LinkList));
s->data=pa->data;
tc->next=s;
tc=s;
}
pa=pa->next;}
tc->next=NULL;return(Lc);
第 页
内蒙古工业大学信息工程学院
}
LinkList *Subs(LinkList *La,LinkList *Lb,LinkList *Lc)
//求两有序集合的差集 {
LinkList *pa=La->next,*pb,*s,*tc;
Lc=(LinkList *)malloc(sizeof(LinkList));
tc=Lc;
while(pa!=NULL){
pb=Lb->next;
while(pb!=NULL&&pb->data
data)
pb=pb->next;
if(!(pb!=NULL&&pb->data==pa->data))
{
s=(LinkList *)malloc(sizeof(LinkList));
s->data=pa->data;
tc->next=s;
tc=s;
}
pa=pa->next;} tc->next=NULL;return(Lc);}
void main(){
LinkList *La,*Lb,*Lc;
int num=0,loop,j;loop=1;La=CreatlinkR(La);Lb=CreatlinkR(Lb);Sort(La);Sort(Lb);
printf(“有序集合A＝{ ”);
DispList(La);
printf(“}n”);
printf(“有序集合B＝{ ”);
DispList(Lb);printf(“}n”);while(loop){
printf(“请选择您要执行的操作：1.求并集
scanf(”%d“,&j);printf(”n%d“,j);
第 页
//若pa结点值不在pb中 2.求交集
3.求差集n”);
内蒙古工业大学信息工程学院
if(j>=1&&j<=3)
switch(j)
{
case 1: Lc=Union(La,La,Lc);
printf(“集合A与集合B的并集C＝{ ”);
DispList(Lc);
printf(“}n”);
break;
case 2: Lc=InsterSect(La,Lb,Lc);
printf(“集合A与集合B的交集C＝{ ”);
DispList(Lc);
printf(“}n”);
break;
case 3: Lc=Subs(La,Lb,Lc);
printf(“集合A与集合B的差集C＝{ ”);
DispList(Lc);
printf(“}n”);
break;
} printf(“0.结束
1.继续n”);scanf(“%d”,&loop);printf(“n”);} }
五、运行结果：
1．输入两个无序集合，排序后输出：
第 页
内蒙古工业大学信息工程学院
2．求集合的并集：
3．选1继续：
第 页
内蒙古工业大学信息工程学院
4．求集合的交集：
5．求集合的差集：
第 页
内蒙古工业大学信息工程学院
6．选0结束：
第 页
第二篇：二叉树的创建与访问算法设计
内蒙古工业大学信息工程学院
实 验 报 告
课程名称： 数据结构（C语言版）实验名称： 二叉树的创建与访问算法设计 实验类型： 验证性□ 综合性□ 设计性□ 实验室名称： c机房 班级：xxxxxxxxx 学号： xxxxxxxxxxxxxxx 姓名： xxx 组别： 同组人：
成绩：
实验日期： 2011年 6月
内蒙古工业大学信息工程学院
预习报告成绩： 指导教师审核（签名）： 2011年 月 日
预习报告
一.实验目的
本实验以二叉树的创建与访问算法设计作为实验内容，掌握树型结构的实现方法，培养解决负责问题的能力。
二.实验内容
1、编写生成二叉树的函数，二叉树的元素从键盘输入；
2、编写在二叉树中插入元素的函数；
3、编写在二叉树中删除元素的函数；
4、编写遍历并输出二叉树的函数。
方案一采用递归算法实现二叉树遍历算法。方案二采用非递归算法实现二叉树遍历算法。三.实验要求
1、掌握树型结构的机器内表示；
2、掌握树型结构之上的算法设计与实现；
3、列表对比分析两种数据结构的相应操作的时间复杂度、空间复杂度，阐明产生差异的原因。四.问题描述
从键盘输入二叉树的元素，建立二叉树，实现二叉树的遍历算法。
五.基本要求
实现以下基本操作：
（1）从键盘输入二叉树的元素，建立二叉树。（2）实现二叉树的先序遍历算法。
内蒙古工业大学信息工程学院
实验报告成绩： 指导教师审核（签名）： 2011年 月 日
实验报告
一 程序清单
#include “stdio.h” #include “string.h” #include
typedef struct BiTNode{ char data;
struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;
BiTree Create(BiTree T){
char ch;
ch=getchar();if(ch=='#')T=NULL;else{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))printf(“Error!”);T->data=ch;
T->lchild=Create(T->lchild);T->rchild=Create(T->rchild);}
return T;}
int Depth(BiTree T){
int dep=0,depl,depr;if(!T)dep=0;else {
depl=Depth(T->lchild);depr=Depth(T->rchild);
dep=1+(depl>depr?depl:depr);}
return dep;}
void main(){ BiTree T;int dep;printf(“请输入您要创建的二叉树！!n
'#'表示空元素！n”);T=Create(T);
printf(“nn您要求的二叉树的深度：”);dep=Depth(T);
printf(“%dnn”,dep);} }
内蒙古工业大学信息工程学院
二 测试结果
三 调试程序出现的问题及解决的方法
编程中出现很多的编译错误，主要采用对每个函数调试，设断点，运用自己的程序中，让我更好的掌握了递归算法。四 实验心得体会
通过这次试验，让我巩固了链式存储结构和递归算法的使用，用模块化思路设计程序，编写程序要小心谨慎，要细化到每个函数，通过多次调试，才使得整个程序正确运行，达到预期结果。
第三篇：算法与数据结构实验
金陵科技学院实验报告
学 生 实 验 报 告 册
课程名称：
学生学号：
所属院部：
（理工类）
算法与数据结构 专业班级： 13网络工程
1305106009 学生姓名： 陈韬
网络与通信工程学院 指导教师： 沈奇 14 ——20 15 学年 第 1 学期
金陵科技学院教务处制
金陵科技学院实验报告
实验报告书写要求
实验报告原则上要求学生手写，要求书写工整。若因课程特点需打印的，要遵照以下字体、字号、间距等的具体要求。纸张一律采用A4的纸张。
实验报告书写说明
实验报告中一至四项内容为必填项，包括实验目的和要求；实验仪器和设备；实验内容与过程；实验结果与分析。各院部可根据学科特点和实验具体要求增加项目。
填写注意事项
（1）细致观察，及时、准确、如实记录。（2）准确说明，层次清晰。
（3）尽量采用专用术语来说明事物。
（4）外文、符号、公式要准确，应使用统一规定的名词和符号。（5）应独立完成实验报告的书写，严禁抄袭、复印，一经发现，以零分论处。
实验报告批改说明
实验报告的批改要及时、认真、仔细，一律用红色笔批改。实验报告的批改成绩采用百分制，具体评分标准由各院部自行制定。
实验报告装订要求
实验批改完毕后，任课老师将每门课程的每个实验项目的实验报告以自然班为单位、按学号升序排列，装订成册，并附上一份该门课程的实验大纲。
金陵科技学院实验报告
实验项目名称： 顺序表 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间：
金陵科技学院实验报告
实验1 顺序表
一、实验目的和要求
掌握顺序表的定位、插入、删除等操作。
二、实验仪器和设备
Turbo C 2.0/ Visual C++
三、实验内容与过程（含程序清单及流程图）
1、必做题
（1）编写程序建立一个顺序表，并逐个输出顺序表中所有数据元素的值。编写主函数测试结果。
（2）编写顺序表定位操作子函数，在顺序表中查找是否存在数据元素x。如果存在，返回顺序表中和x值相等的第1个数据元素的序号（序号从0开始编号）；如果不存在，返回－1。编写主函数测试结果。（3）在递增有序的顺序表中插入一个新结点x，保持顺序表的有序性。
解题思路：首先查找插入的位置，再移位，最后进行插入操作；从第一个元素开始找到第一个大于该新结点值x的元素位置i即为插入位置；然后将从表尾开始依次将元素后移一个位置直至元素i；最后将新结点x插入到i位置。
（4）删除顺序表中所有等于X的数据元素。
2、选做题
（5）已知两个顺序表A和B按元素值递增有序排列，要求写一算法实现将A和B归并成一个按元素值递减有序排列的顺序表（允许表中含有值相同的元素）。
程序清单：
#include
金陵科技学院实验报告
} sequenlist;sequenlist L={{1,3,5,5,7,8,10,12,17},8};void print_list(){ int i;for(i=0;i<=L.last;i++)printf(“%4d”,L.data[i]);} void find_all_x(int x){ int found=0,i;for(i=0;i<=L.last;i++)if(L.data[i]==x){ printf(“%3d”,i+1);found=1;} if(found==0)printf(“-1n”);} void insert_x(int x){ int loc,i;for(i=0;i<=L.last;i++)if(x 金陵科技学院实验报告 loc=i;for(i=L.last;i>=loc;i--)L.data[i+1]=L.data[i];L.data[loc]=x;L.last++;} void delete_x(int x){ int i,j,found=0;for(i=0;i<=L.last;i++)if(x==L.data[i]){ found=1;for(j=i+1;j<=L.last;j++)L.data[j-1]=L.data[j];i--;L.last--;} if(found==0)printf(“x is not foundn”);else { printf(“x is deletedn”);printf(“the list after deletion is:n”);print_list(); 金陵科技学院实验报告 } } void main(){ int x,choice;while(1){ printf(“**********menu**********n”);printf(“ 1--printn”);printf(“ 2--searchn”);printf(“ 3--insertn”);printf(“ 4--deleten”);printf(“ 5--exitn”);printf(“please input your choice:”);scanf(“%d”,&choice); switch(choice){case 1: printf(“the original list is:n”);print_list();break;case 2: printf(“pls input x you want to search:n”); 金陵科技学院实验报告 scanf(“%d”,&x);find_all_x(x);break;case 3: printf(“pls input x you want to insert:n”);scanf(“%d”,&x);insert_x(x);printf(“the list after insertion is:n”);print_list();break;case 4: printf(“pls input x you want to delete:n”);scanf(“%d”,&x);delete_x(x);printf(“the list after deletion is:n”);print_list();break;case 5: exit(0);} } } 金陵科技学院实验报告 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 单链表 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验2 单链表 一、实验目的和要求 1、实验目的 掌握单链表的定位、插入、删除等操作。 2、实验要求 （1）注意链表的空间是动态分配的，某结点不用之后要及时进行物理删除，以便释放其内存空间。 （2）链表不能实现直接定位，一定注意指针的保存，防止丢失。 二、实验仪器和设备 Turbo C 2.0/ Visual C++ 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）编写程序建立一个单链表，并逐个输出单链表中所有数据元素。（2）在递增有序的单链表中插入一个新结点x，保持单链表的有序性。 解题思路：首先查找插入的位置然后进行插入操作；从第一个结点开始找到第一个大于该新结点值的结点即为插入位置；然后在找到的此结点之前插入新结点；注意保留插入位置之前结点的指针才能完成插入操作。 （3）编写实现带头结点单链表就地逆置的子函数，并编写主函数测试结果。 2、选做题 已知指针LA和LB分别指向两个无头结点单链表的首元结点。要求编一算法实现，从表LA中删除自第i个元素起共len个元素后，将它们插入到表LB中第j个元素之前。程序清单： 金陵科技学院实验报告 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 堆栈和队列 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验3 堆栈和队列 一、实验目的和要求 （1）掌握应用栈解决问题的方法。（2）掌握利用栈进行表达式求和的算法。 （3）掌握队列的存储结构及基本操作实现，并能在相应的应用问题中正确选用它们。 二、实验仪器和设备 Turbo C 2.0/ Visual C++ 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）判断一个算术表达式中开括号和闭括号是否配对。（2）测试“汉诺塔”问题。 （3）假设称正读和反读都相同的字符序列为”回文”，试写一个算法判别读入的一个以’@’为结束符的字符序列是否是“回文”。 2、选做题 在顺序存储结构上实现输出受限的双端循环队列的入列和出列算法。设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。程序清单： 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 金陵科技学院实验报告 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 串 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验4 串 一、实验目的和要求 掌握串的存储及应用。 二、实验仪器和设备 Turbo C 2.0/ Visual C++ 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）编写输出字符串s中值等于字符ch的第一个字符的函数，并用主函数测试结果。 （2）编写输出字符串s中值等于字符ch的所有字符的函数，并用主函数测试结果。 解题思路：可以将第一题程序改进成一个子函数，在本题中循环调用。（3）设字符串采用单字符的链式存储结构，编程删除串s从位置i开始长度为k的子串。 2、选做题 假设以链结构表示串，编写算法实现将串S插入到串T中某个字符之后，若串T中不存在这个字符，则将串S联接在串T的末尾。 提示：为提高程序的通用性，插入位置字符应设计为从键盘输入。程序清单： 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 金陵科技学院实验报告 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 二叉树 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验5 二叉树 一、实验目的和要求 （1）掌握二叉树的生成，以及前、中、后序遍历算法。（2）掌握应用二叉树递归遍历思想解决问题的方法。 二、实验仪器和设备 Turbo C 2.0/ Visual C++ 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）建立一棵二叉树。对此树进行前序遍历、中序遍历及后序遍历，输出遍历序列。 （2）在第一题基础上，求二叉树中叶结点的个数。（3）在第一题基础上，求二叉树中结点总数。（4）在第一题基础上，求二叉树的深度。 2、选做题 已知一棵完全二叉树存于顺序表sa中，sa.elem[1…sa.last]存储结点的值。试编写算法由此顺序存储结构建立该二叉树的二叉链表。 解题思路：根据完全二叉树顺序存储的性质来确定二叉树的父子关系即“还原”了二叉树，之后再按照二叉树二叉链表的构造方法进行建立。完全二叉树顺序存储的一个重要性质为，第i个结点的左孩子是编号为2i的结点，第i个结点的右孩子是编号为2i+1的结点。程序清单： 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 金陵科技学院实验报告 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 图 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验6 图 一、实验目的和要求 （1）熟练掌握图的基本概念、构造及其存储结构。 （2）熟练掌握对图的深度优先搜索遍历和广度优先搜索遍历的算法。 二、实验仪器和设备 Turbo C 2.0/ Visual C++ 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）构造一个无向图（用邻接矩阵表示存储结构）。 （2）对上面所构造的无向图，进行深度优先遍历和广度优先遍历，输出遍历序列。 2、选做题 采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。简单路径是指其顶点序列中不含有重复顶点的路径。提示：两个顶点及k值均作为参数给出。程序清单： 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 排序 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验7 排序 一、实验目的和要求 （1）熟练掌握希尔排序、堆排序、直接插入排序、起泡排序、快速排序、直接选择排序、归并排序和基数排序的基本概念。 （2）掌握以上各种排序的算法。区分以上不同排序的优、缺点。 二、实验仪器和设备 Turbo C 2.0/ Visual C++ 三、实验内容与过程（含程序清单及流程图） 1、必做题 用随机数产生100000个待排序数据元素的关键字值。测试下列各排序函数的机器实际执行时间（至少测试两个）：直接插入排序、希尔排序（增量为4，2，1）、冒泡排序、快速排序、直接选择排序、堆排序。 2、选做题 假设含n个记录的序列中，其所有关键字为值介于v和w之间的整数，且其中很多关键字的值是相同的。则可按如下方法排序：另设数组number[v…w]，令number[i]统计关键字为整数i的纪录个数，然后按number重排序列以达到有序。试编写算法实现上述排序方法，并讨论此种方法的优缺点。程序清单： 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 金陵科技学院实验报告 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 查找 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验8 查找 一、实验目的和要求 （1）掌握顺序表查找、有序表查找、索引顺序表查找的各种算法。（2）掌握哈希表设计。 二、实验仪器和设备 Turbo C 2.0/ Visual C++ 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）在一个递增有序的线性表中利用二分查找法查找数据元素X。 2、选做题 （2）构造一个哈希表，哈希函数采用除留余数法，哈希冲突解决方法采用链地址法。设计一个测试程序进行测试。 提示：构造哈希表只是完成查找的第一步，大家应该掌握在哈希表上进行查找的过程，可以试着编程序实现。程序清单： 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 五、实验体会（遇到问题及解决办法，编程后的心得体会） 实验1 递归与分治 一、实验目的： 利用C/C++/JAVA等程序设计语言，实现本章节中分治算法、递归，汉诺塔问题/二分搜索算法/合并排序/快速排序等经典算法。通过本实验章节掌握递归、分治算法的设计思想及实现技巧，加深对课程知识的理解。 二、实验学时：2 三、实验任务： 利用高级程序设计语言，编程实现以下问题： 1）递归：排列问题，汉诺塔问题； 2）分治：递归实现的合并排序及非递归的自然合并排序； 四、实验要求 1，设计过程 理解课本中源代码或伪代码的思想，结合流程图等工具描述实验任务的设计过程，并独自完成代码编写、调试及测试过程。2，代码及注释 提交包含完整源代码及关键代码注释的实验报告。3，运行效果图及测试数据 实验报告中应有能体现源代码正确编译、运行的实验运行效果图及多组测试数据集。 4，心得体会 将实验过程中所遇到的问题以及解决问题的方式、方法以及调试过程加以概括，并总结该实验过程中的收获。 计算机科学与技术学院 算法分析与设计 实验指导书 于洪 编写 2011年8月 目 录 实验一实验二实验三实验四附录1 附录2 排序问题求解…………………………..…..………3 背包问题求解…………………………..…………..5 最短路径问题求解………………..………………..8 N-皇后问题求解…………………………………..10关于文件的操作……………………………….….12 关于如何统计运算时间…………………………..13 实验一 排序问题求解 实验目的 1）以排序（分类）问题为例，掌握分治法的基本设计策略。2）熟练掌握一般插入排序算法的实现； 3）熟练掌握快速排序算法的实现； 4)理解常见的算法经验分析方法； 实验环境 计算机、C语言程序设计环境 实验学时 2学时，必做实验。实验内容与步骤 1.生成实验数据.要求：编写一个函数datagenetare，生成2000个在区间[1,10000]上的随机整数，并将这些数输出到外部文件data.txt中。这些数作为后面算法的实验数据。2.实现直接插入排序算法.要求：实现insertionsort算法。 算法的输入是data.txt； 输出记录为文件：resultsIS.txt；同时记录运行时间为TimeIS。直接插入算法思想： Procedure insertionsort(A,n) A(0)=- for j=2 to n do item=A(j);i=j-1 while item repeat End insertionsort 3.实现快速排序算法.要求：实现QuickSort 算法。 算法的输入是data.txt； 输出记录为文件：resultsQS.txt；同时记录运行时间为TimeQS。 快速排序算法思想： Procedure QuickSort（p,q） integer p,q；global n,A(1:n) if p< q then j ← q+1 call Partition(p, j) call QuickSort(p, j-1) call QuickSort(j+1, q) end if end QuickSort 实验报告： 实验报告应包括以下内容： 用A(m)划分集合A的函数： Procedure partition(m,p) integer m,p, I;global A(m:p-1)v=A(m);I=m Loop loop I=I+1 until A(I)>=v repeat loop p=p-1 until A(p)<=v repeat if I then call interchange(A(i), A(p)) Else exit Endif Repeat A(m)=A(p);A(p)=v End partition（1）题目； （2）2个算法的基本思想描述；（3）算法理论分析（参考教材）； （4）程序流程图； （5）给出data.txt、resultsIS.txt、resultsQS.txt三个文件任选其一的清单； TimeIS、TimeQS的记录结果； （6）实验分析；以表或者图的形式给出这2个算法的经验对比分析结果；并和理论分析结论进行对比。 （7）说明本次调试实验的心得体会、经验等。如果程序未通过，应分析其原因。 实验二 背包问题求解 实验目的 1）以背包问题为例，掌握贪心法的基本设计策略。 2）熟练掌握各种贪心策略情况下的背包问题的算法并实现；其中：量度标准分别取：效益增量P、物品重量w、P/w比值； 3)分析实验结果来验证理解贪心法中目标函数设计的重要性。 实验环境 计算机、C语言程序设计环境 实验学时 2学时，必做实验。 实验内容与步骤 1.理解需要求解背包问题.（1）背包问题的描述：已知有n种物品和一个可容纳M重量的背包，每种物品i的重量为益，这里，0xi1wi。假定将物品i的一部分 xi放入背包就会得到 pixi的效，pi0。显然，由于背包容量是M，因此，要求所有选中要装入背包的物品总重量不得超过M.。如果这n件物品的总重量不超过M，则把所有物品装入背包自然获得最大效益。现需解决的问题是，在这些物品重量的和大于M的情况下，该如何装包，使得得到更大的效益值。由以上叙述，可将这个问题形式表述如下： 极 大 化目标函数 约束条件 1inpixi w1inixiM 0xi1,pi0,wi0,1in（2）用贪心策略求解背包问题 首先需确定最优的量度标准。这里考虑三种策略： 策略1：按物品价值p降序装包，策略2：按物品重w升序装包 策略3：按物品价值与重量比值p/w的降序装包 （3）分别以上面三种策略分别求以下情况背包问题的解： n=7，M=15，（p1,,p7）=（10，5，15，7，6，18，3）（w1,,w7）=（2，3，5，7，1，4，1）。以策略3为例的背包问题的贪心算法描述： procedure GREEDY-KNAPSACK(P,W,M,X,n)//P（1：n）和W（1：n）分别含有按P（i）/W（i）≥P（i+1）/ W（i+1）排序的n件物品的效益值和重量。M是背包的容量，而X（1：n）是解向量。// real P(1：n)，W（1：n）,X（1：n），M，cu； integer i，n;X0 //将解向量初始化为零 cuM //cu是背包剩余容量 for i1 to n do if W(i)>cu then exit endif X(i)1 cucu-W(i)repeat if i≤n then X(i)cu/W(i)endif end GREEDY-KNAPSACK 2.以策略1作为量度标准求解要求问题，记录解向量为X1、目标函数的值fp1（即最后装好包后背包的效益值 1in、背包的重量fw1； pixi）3.以策略2作为量度标准求解要求问题，记录解向量为X21、目标函数的值fp2（即最后装好包后背包的效益值 1in、背包的重量fw2； pixi）4.以策略3作为量度标准求解要求问题，记录解向量为X3、目标函数的值fp3即最后装好包后背包的效益值实验报告： 实验报告应包括以下内容： 1in、背包的重量fw3； pixi）（1）题目； （2）算法的基本思想描述；（3）程序流程图； （4）给出3个程序任意之一的程序清单； （5）实验分析；通过实验结果对比分析说明哪种策略好。 （6）说明本次调试实验的心得体会、经验等。如果程序未通过，应分析其原因。 Tips： 1.解向量的表示。需要注意：因为算法中涉及到排序，如何保证各种物品的原始命名（如果以第几种，即序号，来命名物品）关系需要考虑。 #define MAX 200 typedef struct Solution //定义的解向量 { int x[MAX];表示该号物品放了多少在背包里，这里0xi 1int order[MAX];表示物品的序号，相当于其名字 }Solution;Solution X;所以，初始化时，为： for(i=0;i { X.order[i]=i; X.x[i]=0; } 2.主要函数： void GreedyKnapsack(float profit[],float weight[],float x[],int m, int n){ float cu; int i; cu=float(m); for(i=0;i { x[i]=0; } for(i=0;i { if(weight[i]>cu) break; x[i]=1; cu=cu-weight[i]; } if(i { x[i]=cu/weight[i]; } } 实验三 最短路径问题求解 实验目的： 1）以最短路径问题为例，掌握动态规划的基本设计策略； 2）掌握dijkstra贪心法求解最短路径问题并实现； 3）掌握动态规划方法Floyd算法求解最短路径问题并实现； 3）分析实验结果。实验环境 计算机、C语言程序设计环境 实验学时 2学时，必做实验。实验内容与步骤 1.以下图作为输入，利用dijkstra贪心法获取由结点1到其余结点最短路径长度，输出保存到外部文件dijkstra－output1.txt 3 4 5 2 1 2.然后改写你的程序，求得所有各点之间的最短距离;输出保存到文件dijkstra－output2.txt.3.以上图作为输入，利用Floyd算法求得所有各点直接的最短距离;输出保存到文件floyd－output1.txt.实验报告 实验报告应包括以下内容： （1）题目； （2）写出算法设计思想； （3）程序清单；（4）运行的结果； （5）对运行情况所作的分析以及本次调试程序所取的经验。如果程序未通过，应分析其原因。 Tips: 主要函数 void dijkstra::algorithm()//算法函数 { initialize();int count=0;int i;int u;while(count u=minimum(); set[++count]=u; mark[u]=1; for(i=1;i<=num_of_vertices;i++) { if(graph[u][i]>0) { if(mark[i]!=1) { if(pathestimate[i]>pathestimate[u]+graph[u][i]) { pathestimate[i]=pathestimate[u]+graph[u][i]; predecessor[i]=u; } } }} }} //-------------float graph[maxsize][maxsize];//成本矩阵，邻接矩阵 //floyd algorithm for(k = 0;k < n;k ++) { // graph[i][j] = min {graph[i][j]}, graph[i][k] + graph[k][j] for(i = 0;i < n;i ++) //每次找到最优的路径代替原来的路径 for(j = 0;j < n;j ++) if(graph[i][j] > graph[i][k] + graph[k][j])//状态转换条件 { graph[i][j] = graph[i][k] + graph[k][j];//状态转换方程 } } 实验四：N-皇后问题求解 实验目的： 1）以Q-皇后问题为例，掌握回溯法的基本设计策略。2）掌握回溯法解决Q-皇后问题的算法并实现； 3）分析实验结果。 实验环境 计算机、C语言程序设计环境 实验学时 2学时，必做实验。 实验内容与步骤 1.用回溯法求解N-Queen，参考教材算法思想，并实现你的算法。要求：用键盘输入N；输出此时解的个数，并统计运算时间。2.给出N=4,5,6时，N-Queen解的个数。 3.尝试增大N，观察运行情况；并理解该算法的时间复杂度。实验报告 实验报告应包括以下内容： （1）题目； （2）写出算法设计思想； （3）运行的结果； （4）对运行情况所作的分析以及本次调试程序所取的经验。（5）如果程序未通过，应分析其原因。 Tips: 主要函数等 while(k>0)//对所有行执行以下语句 { X[k] = X[k]+1;//移到下一列 while(X[k]<=n &&!PLACE(k)) { X[k] = X[k]+1;//移到下一列，再判断 } if(X[k] <= n)//找到一个位置 { if(k==n)//一个完整的解 { //print printf(“the soution is:n”); for(t=1;t<=n;t++) printf(“%3d”,X[t]); printf(“n”); count +=1; } else {k=k+1;X[k]=0;} //转向下一行 } else k=k-1;//回溯 } printf(“n the number of the solutions is %d n”, count); bool PLACE(int k){ i=1;while(i if(X[i]==X[k] || abs(X[i]-X[k])==abs(i-k)) return false; i=i+1;} return true;} 附录1关于文件的操作 以背包问题为例： 1，例如外部文件为knapsack-input.txt： 2, 读入文件的操作： FILE* fp; /* Open for read(will fail if file “knapsack-input.txt” does not exist)*/ if((fp = fopen(“knapsack-input.txt”, “r”))== NULL) printf(“The file 'knapsack-input.txt' was not openedn”); else printf(“The file 'knapsack-input.txt' was openedn”); //读输入文件，写n,M,p[MAX],w[MAX] fscanf(fp,“n=%dn”,&n); fscanf(fp,“M=%dn”,&M); for(i=0;i for(i=0;i fscanf(fp,“%f”,&weight[i]);fscanf(fp,“n”); /* Close stream */ if(fclose(fp)) printf(“The file 'knapsack-input.txt' was not closedn”);附录2关于如何统计运算时间 #include “time.h” …….//----start time-----设置计时开始 double duration; clock_t finish, start;start = clock(); …… //----finish time-----设置计时结束 finish = clock(); duration =(double)(finish-start)/ CLOCKS_PER_SEC; printf(“nThe CPU time is %2.6f seconds:n”, duration); // 统计时间duration第四篇：算法设计与分析 实验指导书1
第五篇：《算法分析与设计》实验指导书-
点击咨询 