算法设计与分析实验

《算法设计与分析》选做实验

实验一单链表的建立插入及删除

［实验目的］

1.掌握单链表的建立插入及删除的算法；

2.进一步熟悉指针的用法；

［预习要求］

1.认年阅读教材或叁考书，掌握线性表笄法的基本思想;

2.写出求解本实验的程序；

3.设计好相应的测试用例。

［类型定义］

typedefstructLnode

(intdata;

structLnode*next;

}Lnode,*linklist;

［实验提示］

voidcreate(link*h,intn)

{〃创建单链表

linkp,q;

inti;

p=(1ink)malloc(sizeof(node));

p->next=null;

*h=p;q=p;

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

{p=(1ink)malloc(sizeof(node));

scauf("机T,&p->dctLci);

p->next=nul1;q->next=p;q=p;

)

}

voidprint(linkh)

{〃输出单链表

linkp;

p=h->next;

while(p)

{printf(，z%d”,p->data);

p=p->next;

)

)

voidinsertlist(linklist*L,inti,inte)

{〃在单链表的第i个元素之前插入元素值为e的结点}

voiddellist(linklist*L,inti,int*e)

{〃删除单链表的第i个结点，被删结点通过。返回}

［实验步骤］

1.先用插表头或插表尾的方法建立单链表并输出，并测试你的程序，直至正确为止;

2.再进行插入和删除程序的设计；

3.将你的程序和实录的界面存盘备用。

［实验报告要求］

1.阐述实验目的和实脸内容；

2.提交模块化的实脸程序源代码；

3.简述程序的测试过程，提交实录的输入、输出文件；

4.提交思考与练习题的代码和测试结果。

［思考与练习］

怎样用链表实现循环队列。

实验二多项式加法

［实验目的］

1.熟练掌握在单链表中进行结点的插入和删除操作；

2.进一步熟悉指针的用法；

［预习要求］

1.认年阅读教材或叁考书，掌握线性表笄法的基本思想；

2.写出求解本实验的程序；

3.设计好相应的测试用例。

［类型定义］

typedefstructLnode

(intcoef,exp;

structLnode*next;

}Lnode,*linklist;

［实验提示］

voidcreate(link*h,intn)

{〃创建一元多项式

linkp,q;

inti;

p=(1ink)mal1oc(sizeof(node));

p->next=null;

*h=p;q=p;

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

{p=(1ink)malloc(sizeof(node));

scctiif&p->cuef,&p->exp);

p->next=nul1;q->next=p;q=p;

)

}

voidprint(linkh)

{〃输出单链表

linkp;

p=h->next;

while(p)

{printf(z，%d,%d”,p->coef,p->exp);

p=p->next;

)

)

voidaddlist(linklist*A,linklistB)

{〃将A和B相加并通过A返回}

［实验步骤］

1.先用插表尾的方法建立一元多项式，并将一元多项式输出，并测试你的程序，直至

正确为止；

2.进行一元多项式相加程序的设计；

3.将你的程序和实录的界面存盘备用。

［实验报告要求］

1.阐述实验目的和实验内容；

2.提交模块化的实脸程序源代码；

3.简述程序的测试过程，提交实录的输入、输出文件；

4.提交思考与练习题的代码和测试结果。

［思考与练习］

写出约瑟夫问题的求解算法，即n个人坐成一圈，报m出国，输出最后一个报m的人。

实验三集合的表示与操作算法设计

［实验目的］

1.了解集合的不同表示方法，掌握集合的树结构表示方法；

2.掌握树结构表示下集合的并运算与查找算法；

3.编程实现集合的表示与操作算法.

［预习要求］

1.认真阅读教材内容，熟悉树结构表示的原理和碟作算法；

2.设计和编制实验程序.

［参考数据类型或变量］

typcdcfElcmTypcint/*实型或任意其它元素类型*!

typedefstruct{

ElemTypeelem;

inttag;/*根节点为负的整数，表示该集合的基数的负值，否则为父节点索引指针*/

}NODE;

NODE*set;/*用动态存储分配实现集合的树表示与存储*/

［参考子程序接口与功能描述1

voidInitSet(NODE*se。

功能：根据集合的基数动态分配存储，输入各元素，初始化子集森林.

intFind(NODE*set,ElemTypeeleni)

功能：在数组se［中顺序查找元素elem,如果不成功，返回-1;否则,使用带压缩规则的查

找算法，返回所在子集的根节点索引.

intUnion(NODE*set,ElemTypeelemi,ElemTypeelem2)

功能：应用Find算法首先找到elemi和elem2所在的子集，然后应用带加权规则的并运

算算法合并两个子集.不成功时，返回-1;否则，返回并巢的根节点索引.

［实验步骤］

1.设计Find的测试方案和程序,输入测试数据，修改并调试程序，直至正确为止；

2.设计Union的测试方案和程序,输入测试数据，修改并调试程序，直至正确为止；

3.待各功能子程序调试完毕，去掉测试程序，将你的程序整理成功能模块存盘备用.

［实验报告要求］

1.阐述实验目的和实脸内容；

2.提交实脸程序的功能模块；

3.记录最终测试数据和测试结果。

［思考题］

试用C语言实现集合的位向量表示，并设计相应的并、交与查找运算算法.

实验四迷宫问题求解

[实验目的]

1.熟悉栈用法；

2.掌握回朔法及试探法的程序设计；

[预习要求]

1.认真阅读教材或参考书，学搪栈用法的用法：

2.写出求解本实验的程序；

3.设计好相应的测试用例。

[实验提示]

设迷宫中数组的元素为1表示该点道路主的阻塞，为0表示可通。

设maze[1][1]为入口，maze[m][n]为出口。

在maze在][1]和maze[m][r>]的元素值必为0。

在任意时刻，老鼠在迷宫中的位置可以用所在点的吁下标与列下标（i,j）来表示，这

样，老鼠在迷宫中的某点maze[i][j]时，其可能的运动方向有八个。下图+表示某时刻老鼠

所在的位置（i,j）,相邻妁八个位置分别标以N、NE、E、SE、S、SW、W、NW（分别代发+点

的北、东北、东、东南、南、西南、西、西北方向）：同时，相对于（i,j）,这八个相邻位

置的坐标的值都可以计算出来。

但是，并非迷宫中的每一个点都有八个方向可走，四个角上就只有三个方向可供选择，

边上只有五个方向可供选择。为了不在算法中每次都去检查这些边界条件，在迷宫外面套上

一图，其元素值均为1。

NWNNE

(1-1,J-1)(1-1,J)(1-1,J+1)

W+E

(I,J-1)(I,J)(I,J+1)

SWSSE

(1+1,J-1)(1+1,J)(1+1,J+1)

为了简化算法，根据上图所示的位置（i,j）与其相邻的八个位置的坐标关系，建立一

个下图所示的表move,表中给出相对于位置（l,j）的八个方向上的i与j的增量值。

Move

-10

-11

01

11

10

1-1

0-1

-1-1

若老鼠在（i,j）位置，要进入SW方向（g,h）点，则由该增量值表来修改坐标。

g=i+move[5][0];

h=j+move[5][1];

例如：若（i,j）为：3,4）,则SW的相邻点的坐标为（3+1,4-1）。

在每个位置上都从N方向试起,若不通.则顺时针方向试NE方向.其余类推。

当选定一个可通的方向后，要把目前所在的位置以及所选的方向记录下来，以使往下走

时可依次一点一点退回来，每退一步后接着试在该点未试过的方向。为了避免走回到已经进

入过的点，maze[i][j]=2.

为了记录当前位置以及该位置上所选择的方向数需设一个堆栈。

#definein6

#defingn9

voidpath()

{intmaze[m+2][n+2];

intmove[8][2];

ints[541[3];

inttop=0;

inti,j,k,pf=O;

for(i=0;i<m+2;++i)

for(j=0;j<n+2;++j)

scanf("%d”,&maze[i][j]);

maze[l][l]=2;

s[top][0]=l;

s[top][l]=l;

s[top][2]=0;

++top;

while(top!=0&&f==0)

{-top;

i=s[top][OJ;

j=s[top][l];

k=s[topl[2];

while(k<8)

g=i+move[k][0];

h=j+move[k][l];

if(g==m&&h==n&&maze[g][h]==O)

{for(p=0;p<top;++p)

printf(s[p][O],s[p][l]);

printf(i,j);

printf(m,n);

f=l；

}//if

if(maze[g][h]==O)

{maze[g][h]=2;

s[topl[01=i;

s[top][l]=j;

s[top][2]=k;

++top:

i=g；

j=h；

k=0;

}//if

k=k+l;

}//while

}//while

if(f==O)

printff'nopath\nM);

}//palh

[实验步骤]

1.先设计好迷宫，并测试你的程序，直至正确为止;

2.将你的程序和实录的界面存盘备用。

［实验报告要求］

1.阐述实脸目的和实验内容；

2.提交模块化的实险程序源代码；

3.简述程序的测试过程，提交实录的输入、输出文件:

4.提交思考与练习题的代码和测试结果。

［思考与练习］

写出用队列求解迷宫问题的算法。

实验五树的建立及遍历

［实验目的］

1.进一步掌握指针变量的含义。

2.掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。

3.掌握用指针类型描述、访问和处理二叉树的运算。

［预习要求］

1.认真阅读教材或参考书，掌握树的三种遍历方法算法的基本思想:

2.写出求解本实验的程序；

3.设计好相应的测试用例。

［类型定义］

typedefstructBitnode

{intcoef,exp;

structBitnode*next;

}Bitnode,*Bitree;

r实验提示i

按先序次序输入二叉树中结点的值（一个字符），p'表示空树，生成二叉树的二叉链

表存储结构，t为指向根结点的指针。然后按先序、中序及后序等方法遍历二又树。

voidcreate(Bitree*t)

{〃创建二叉树}

voidpreorder(Bitreet)

{〃二叉树的先序遍历}

voidinorder(Bitreet)

{〃二叉树的中序遍历}

voidinorder(Bitreet)

{〃二叉树的后序遍历}

［实验步骤］

1.先用先序次序输入二叉树中结点的值建立二叉梢，并测试你的程序，直至正确为止:

2.用递归方法进行三种不同的遍历：

3.用非递归方法进行三种不同的遍历；。

［实验报告要求］

1.阐述实验目的和实险内容；

2.提交模块化的实脸程序源代码；

3.简述程序的测试过程，提交实录的输入、输出文件；

4.提交思考与练习题的代码和测试结果。

［思考与练习］

1.写出一个算法统计树的叶子结点个数。

2.不用栈不用递归写一算法求树的后序遍历的第一个结点。

实验六图的遍历的演示

［实验目的］

1.熟练掌握图的邻接表存储方法和邻接表的建立算法；

2.掌握图的图的深度和广度遍历算法思想；

［预习要求］

1.认真阅读教材或参考书，掌握图的深度和广度遍历算法思想;

2.写出求解本实睑的程序：

3.设计好相应的测试用例。

［类型定义］

/*邻接点及顶点的定义*/

typedefstructnode

{intadjvex;

structnode*next;}node;

/*顶点的定义*/

typedefstruct

{intvex;

node*firstadj;

}vertex;

/*邻接表的定义*/

typedefstruct

{vertexdata［100］;

intm;/*ni表示图中顶点的个数*/

}adjlist;

［实验提示］

voidcrcatcgraph(adjlist*g)

{intn,e;/*n表示图中的顶点个数,e表示边的条数*/

intj,i,k;

node*p,*q;

/*由键盘输入图的顶点个数及边的条数*/

printf(^inputn=");

scanf("*d”,&n);

printf(，zinpute=");

scanf&e):

/*初始化邻接表*/

g->m=n;

for(j=0;j<=n-l;++j)

{g->data［j］.firstadj=NULL;

g->data［j］.vex=j;

}

for(j=0;j<e;++j)

{/*由键盘输入一对边

printf("inputi,k:");

scanf("%d%d”,&i,&k);

/*申请一个邻结点*/

p=(node*)malloc(sizeof(node));

p->adjvex=k;

p->next=NULL;

if(g->data[i].firstadj==MULL)

g->data[i].firstadj=p;

else

{q=g->data[i].firstadj;

while(q->next)

q=q->next;

q->next=p;

)

)

}

/*向图的深度优先遍历*/

voiddfs(adjlistg,intv)

{node*p;

printf("%3d”,v);

visited[v]=l;

p=g.data[v].firstadj;

while(p)

{if(visited[p->adjvex]==0)dfs(g,p->adjvex);

p=p->next;

)

)

/*图的广度优先遍历程序*/

/*voidbfs(adjlistg,intv){*/

/*定义空队列*/

/*intQ[100];

intfront=0,rear=();

node*p;

visited[v]=l;

printf(飞3d〃，v);

Q[rcar++]=v;

while(front!=rear)

{v-Q[front++];

p=g.data[v].firstadj;

while(p)

{if(visited[p->adjvex]==0)

{visited[p->adjvex]=l;

printf(*%3d，/,p->adjvex);

Q[rear++]=p->adjvex;

}

p=p->next;

)

}*/

voidprint(adjlistg)

{inti;

node*p;

for(i=0;i<g.m;++i)

{p=g.data［i］.firstadj;

while(p)

{printf(，z%d—%d,”,i,p->adjvex);

p=p->next;

)

printf("\n");

)

)

［实验步骤］

1.先建立图的邻接表，并将邻接表榆出，并测试你的程序，直至正确为止;

3.进行深度优先遍历和广度优先遍历；

4.将你的程序和实录的界面存盘备用。

［实验报告要求］

1.阐述实验目的和实脸内容；

2.提交模块化的实脸程序源代码；

3.简述程序的测试过程，提交实录的榆入、输出文件；

4.提交思考与练习题的代码和测试结果。

［思考与练习］

写出图的邻接矩阵表示法的定义，并实现求最短路径的算法。

实验七哈希表的设计

［实验目的］

1.掌握的哈希表定义和存储

2.掌握查找常用方法及过程

3.实现哈希表的综合操作

［预习要求］

1.认真阅读和掌握本实验的算法。

2.上机将本算法实现。

3.保存和打印出程序的运行结果，并结合程序进行分析。

［类型定义］

#defineMAXSIZE12〃哈希表的最大容量，与所采用的哈希函数有关

enumBOOL{FaIse,True);

enumHAVEORNOT{NULLKEY,HAVEKEY,DELKEY}；

//哈希表元素的三种状态，没有记录、有记录、有过记录但已被删除

typedefstruct〃定义哈希表的结构

(intclcm［MAXSIZE］;//数据元素体

HAVEORNOTeIemfIag［MAXSIZE］;〃元素状态标志,没有记录、有记录、有过记录但已被删

除

intcount;//哈希表中当前元素的个数

}HashTabIe;

typedefstruct

{intkeynum；〃记录的效据域，只有关键字一项

}Record;

［实验提示1

voidInitiaIHash(HashTabIe&H)

{〃哈希表初始化

)

voidPrintHash(HashTableH)

{〃显示哈希表所有元素及其所在位置

)

BOOLSearchHash(HashTabIeH,intk,int&p)

{//在开放定址哈希表H中查找关键字为k的数据元素，若查找成功，以p指示

〃待查数据元素在表中的位置，并返回True;否则，以p指示插入位置，并

//返回FaIse

I

BOOLInsertHash(HashTabIe&H,Recorde)

{〃查找不成功时插入元素e到开放定址哈希表H中，并返回True,否则返回False

)

BOOLDeIeteHash(HashTabIe&H,Recorde)

{〃在查找成功时删除待删元素e,并返回True,否则返回False

intHash(intkn)

]〃哈希函数：H(key)二keyMOD11

return(kn%11);

［实验步骤］

1.先将哈希表初始化并显示哈希表所有元素及其所在位置，并测试你的程序，直至正确

为止；

2.在开放定址哈希表中查找关键字为的数据元素；

3.查找不成功时插入元素到开放定址哈希表中。

［实验报告要求］

1.阐述实险目的和实验内容；

2.提交模块化的实险程序源代码；

3.简述程序的测试过程，提交实录的输入、输出文件；

4.提交思考与练习题的代码和测试结果。

［思考与练习］

写出约瑟夫问题的求解算法，即n个人坐成一圈，报m出圈，榆出最后一个报m的人。

实验八Kruskal算法的设计

［实验目的］

1.根据算法设计需要，掌握连通网的灵活表示方法；

2.掌握最小生成树的Kruskal算法；

3.基本掌握贪心算法的一般设计方法；

4.进一步掌握集合的表一示与操作算法的应用.

［预习要求］

1.认真阅读算法设A教材和数据结构教材内容，熟习连通网的不同表示方法和最小生

成树算法；

2.设计Kruskal算法实验程序.

［参考数据类型或变量］

typcdefNodeNumberint;/*节点编号*/

typcdcfCostTypcint;/*成本值类型*/

typedefElemTypeNodeNumber/*实型或任意其它元素类型*/

typedefstruct{intElemType;inttag;}NODE;

typcdcfstruct{CostTypccost;NodeNumbernodcl,nodc2;}EDGE;

NODEset[]={{l,-l},...,{n,-l}};N节点集，n为连通网的节点数*/

EDGEes[]={{valuesofe(valuesofem}};/*边集,m为连通网的边数*/

EDGEst［n-l］;/*最小生成树的边集*/

［参考子程序接口与功能描述1

intFind(NODE*set,ElemTypeelem)

功能：在数组set中顺序查找元素elem,如果不成功，返回-I;否则，使用带压缩规则的

查找算法，返回所在子集的根节点索引.

intUnion(NODE*set,ElemTypeelemi,ElemTypeelem2)

功能:应用Find算法首先找到elemi和elcm2所在的子集，然后应用带加权规则的并运

算算法合并两个子集.不成功时，返回-1;否则，返回并集的根节点索引.

voidSort(EDGE*cs,intn)

功能：用任意分类算法将连通图的边集按成本值的非降次序分类.

voidKruskal(EDGE*es,intm,NODE*set,intn,EDGE*st)

功能：对有n个节点,m条边的连通网，应用Kruskal算法生成最小生成树，最小生成树

的边存储在数组st中.

voidOutput(EDGE*st,intn)

功能：榆出最小生成树的各条边.

［实验步骤I

1.设计测试问题，修改并调试程序，揄出最小生成树的各条边，直至正确为止;

2.待各功能子程序调试完毕，去掉测试程序，将你的程序整理成功能模块存盘备用.

［实验报告要求］

1.阐述实脸目的和实验内容；

2.阐述Kruskal算法的原理方法；

3.提交实验程序的功能模块；

4.提供测试数据和相应的最小生成树.

［思考与练习1

1.设计由连通网初始边集数组生成最小堆的算法；

2.设计输出堆顶元素，并将轲余元素调整成最小堆的算法；

3.针对连通网初始边集最小堆表示，设计Kruskal算法；

4.采用成本邻接矩阵表示连通网时，在轲余边中如何实现最小成本边的查找?

采用成本邻接矩阵表示连通网时，用C语言实现Prim算法.

实验九归并排序的分治策略设计

[实验目的]

1.熟悉二分检索问题的线性结构表示和二分检索树表示；

2.熟悉不同存储表示下求解二分检索问题的递归算法设计；

3.通过实例转换,掌握将递归算法转换成迭代算法的方法；

4.掌握应用递归或迭代程序设计实现分治法求解问题的抽象控制爰略.

[预习要求]

1.认真阅读算法设尸教材和数据结构教材内容，熟悉不同存储表示下求解二分检索问

题的原理或方法；

2.针对线性结构表示和二分检索树表示设计递归算法；

3.参考教材和课堂教学内容，根据将递归算法转换成迭代算法的一般步骤将二分检索

递归算法转换成相应的迭代算法.

[算法或程序设计参考]

线性结构

intdata[10]={/*10个互异的、无序的原始整数*/};

(ypedefstruct{ints[100];inttop;}STACK;

intPartition(int*data,intlow,inthigh)

功能：将data[low,high]进行快速分类划分，返回枢轴记录关键字的位置索引.

intQSortl(int*data,intlow,inthigh)

功能：将data[low,high]进行快速分类的递归算法.

intQSort2(int*data,intlow,inthigh)

功能：将data[low,high]进行快速分类的迭代算法.

intBSearchl(in(*data.intkey)

功能：在data数组中检索key的二分检索递归算法，成功时返回位矍索引，否则返回-1.

intBSearch2(int*data.intkey)

功能：在data数组中检索key的二分检索迭代算法，成功时返回位置索引，否则返回-1.

树结构

typedefstructNODE{intkey;structNODE*lch,*rch;}TNODE,*BT;

(ypedefstructParameters{BTintkey;BTf;BT"'p}PARA;

typedefstruct{PARAs[100];inttop;}STACK;

intInsertBT(BT*t,intkey)

功能：在二分检索树：中插入关键字为key的元素，成功时返回1,否则返回0.

intTSearchKBT*t,imkey,BTf,BT*p)

功能：用递归算法在二分检索树l中查找关键字为key的元素，成功时返回l,p指向该

元素节点，否则p指向查找路径上最后一个节点并返回0,f指向t的双亲，其初始调用值为

NULL.

iniTSearch2(BT*t,inikey,BTf,BT*p)

功能：用迭代算法在二分检索树t中查找关键字为key的元素，成功时返回l,p指向该

元素节点，否则p指向查找路径上最后一个节点并返回()，f指向t的双亲，其初始调用值为

NULL.

［实验步骤］

1.调试线性结构表示下的快速分类与二分检索递归程序，直至正确为止；

2.调试线性结构表示下的快速分类与二分检索迭代程序，直至正确为止；

3.待各功能子程序调试完毕，去掉测试程序，将程序整理成功能模块存盘备用.

［实验报告要求］

1.阐述实脸目的和实检内容；

2.提交实睑程序的功能模块；

3.阐述将递归算法改写成迭代算法的一般方法；

4.用类C语言阐述分治法递归与迭代实现抽象控制策略.

［思考与练习］

1.怎样优化由递归程序改写的迭代程序？

2.设计二分检索树的构造与检索递归程序，并将其改写成相应的迭代算法.

实验十哈夫曼编码的贪心算法设计

［实验目的］

1.根据算法设计需要,掌握哈夫曼编码的二叉树结构表示方法；

2.编程实现哈夫曼编译码器；

3.掌握贪心算法的一般设计方法。

［预习要求］

1.认真阅读数据结构教材和算法设计教材内容，熟悉哈夫曼编码的原理；

2.设计和编制哈夫曼编译码器。

［参考数据类型或变量］

typedefElemTypechar；

typcdcfstructnodc{

intw;

intHag;

ElemTypec;

structnode*plink.*llink,*rlink:

charcode［m］;

}Nodc;

Node*nuni［n］,*root;

［参考子程序接口与功能描述1

voidSetTree(NODE*root)

功能：从终端读入字符集大小n,以及n个字符和n个权值，建立哈夫曼树

voidEnCode(Node*p)

功能：利用已建好的哈夫曼树，对输入的正文进行编码

voidDeCode(void)

功能：利用已建好的哈夫曼树，将输入的代码进行译码

I实验步骤I

1.设计SetTree的测试方案和程序,输入测试数据，修改并调试程序，直至正确为止;

2.设计EnCode的测试方案和程序,榆入测试数据，修改并调试程序，直至正确为止;

3.设计DeCode的测试方案和程序,输入测试数据，修改并调试程序，直至正确为止;

4.将你的程序整理成功能模块存盘备用。

［实验报告要求］

1.阐述实险目的和实验内容；

2.提交实验程序的功能模块；

3.记录最终测试数据和测试结果。

［思考题］

1.试证明哈夫曼问题具有贪心选择性质；

2.试证明哈夫曼问题具有最优子结构性质。

实验递归与迭代程序设计

［实验目的］

5.熟悉二分检索问题的线性结构表示和二分检索树表示；

6.熟悉不同存储表示下求解二分检索问题的递归算法设计；

7.通过实例转换，掌握将递归算法转换成迭代算法的方法；

8.掌握应用递归缸迭代卷序设计实现分治法求解问题的抽象控制第一略.

I预习要求］

4.认其阅读算法设齐教材和数据结构教材内容，熟悉不同存储表示下求解二分检索问

题的原理或方法；

5.针对线性结构表示和二分检索树表示设计递归算法；

6.参考教材和课堂教学内容，根据将递旧算法转换成迭代算法的一般步骤将二分检索

递归算法转换成相应的迭代算法.

［算法或程序设计参考］

线性结构

imdata［IO］={/*1()个互异的、无序的原始整数*/};

typcdcfstruct{ints［HM)］;inttop;}STACK;

iniPartition(inl*da(a,intlow,in(high)

功能：将data［low,high］进行快速分类划分，返回枢轴记录关键字的位置索引.

intQSortl(int*data,intlow,inthigh)

功能：将dataflow,high］进行快速分类的递归算法.

intQSort2(int*data,intlow,inthigh)

功能：将data［low,high］进行快速分类的迭代算法.

intBSearch1(int*data.intkey)

功能：在data数组中检索key的二分检索递归算法，成功时返回位置索引，否则返回-1.

intBSearch2(in(*data.in(key)

功能：在data数组中检索key的二分检索迭代算法，成功时返回位置•索引，否则返回-1.

树结构

typedefstructNODE{intkey;structNODE*lch,*rch;}TNODE,*BT;

typcdcfstructBaramcters{Bl*t;intkey;Blf;Bl*p}EAKA;

typedefstruct{PARAsf100］;inttop:}STACK;

intInscrtBT(BT*t,intkey)

功能：在二分检索树：中插入关键字为key的元素，成功时返回I,否则返回0.

intTScarchl(BT*t,inckey,BTf,BT*p)

功能：用递归算法在二分检索树t中查找关键字为key的元素，成功时返回l,p指向该

元素节点，否则p指向查找路径上最后一个节点并返回()，f指向t的双亲，其初始调用值为

NULL.

iniTSearch2(BT*t,inikey,BTf,BT*p)

功能：用迭代算法在二分检索树t中查找关键字为key的元素，成功时返回l,p指向该

元素节点，否则p指向查找路径上最后一个节点并返回()，f指向t的双亲，其初始调用值为

NULL.

［实验步骤］

1.调试线性结构表示下的快速分类与二分检索递归程序，直至正确为止；

2.调试线性结构表示下的快速分类与二分检索迭代程序，直至正确为止；

3.待各功能子程序调试完毕，去掉测试程序，将程序整理成功能模块存盘备用.

［实验报告要求］

1.阐述实脸目的和实检内容；

2.提交实睑程序的功能模块；

3.阐述将递归算法改写成迭代算法的一般方法；

4.用类C语言阐述分治法递归与迭代实现抽象控制策略.

［思考与练习］

1.怎样优化由递归程序改写的迭代程序？

2.设计二分检索树的构造与检索递归程序，并将其改写成相应的迭代算法.

实验十二多段图问题的动态规划算法设计

[实验目的]

1.掌握有向网的成本邻接矩阵表示法；

2.能用程序设计语言实现多段图问题的动态规划递推算法；

3.基本掌握动态规划法的原理方法.

[预习要求]

1.认真阅读数据结构教材和算法设计教材，熟习有向网的成本邻接矩阵表示法和动态

规划求解多段图问题的递推原理；

2.设计用动态规划算法求解多段图问题的数据结杓和递推程序.

[参考数据类型或变量]

typedefNodeNumberint;/*节点编号*/

typedefCoslTypeint;/*成本值类型*/

CostTypecost[n][n]={...}；/*成本邻接矩阵，n为顶点数*/

NodeNumberpath[k];/*k段图最短路径上的节点编号数组*/

NodeNumbercur=-1;/*当前邻接节点*/

[参考子程序接口与功能描述]

intFindForward(CostType*cost[n],NodeNumberi,NodeNumbercur)

功能：根据邻接矩阵查找节点i的下一个前向邻接节点，成功时返回节点编号，否则返

回-l;cur为当前的前向邻接节点，第一次调用时其值为-1.

intFindBackward(CostTypc*cost[n],NodeNumberi,NodeNumbercur)

功能：根据邻接矩阵查找节点i的下--个后向邻接节点，成功时返回节点编号，否则返

回-1;cur为当前的后向邻接节点，第一次调用时其值为-1.

voidFPath(CostType*cost[n],intk,intn,NodeNumber*path)

功能：n个节点的k段图前向递推算法,palh口存储最短路径节点序列.

voidBPath(CostTypcxcost[nJ,intk,intn,NodeNumber*path)

功能：n个节点的k段图后向递推算法，path。存储最短路径节点序列.

voidOutPath(intk,NodeNumber*path)

功能：输出k段图的最短路径序列，path[]存储最短路径节点序列.

[实验步骤]

1.设计程序和测试数据，修改并调试程序，直至正确为止；

2.应用设计的算法和程序输出给定多段图问题的最短路径序列；

3.去掉测试程序，将你的程序整理成功能模块存盘备用.

[实验报告要求]

1.阐述实验目的和实验内容；

2.阐述求解多段图问题的动态规划递推原理；

3.提交实脸程序的功能模块；

4.记录最终测试数据和测试结果。

［思考与练习］

1.试用C语言实现求有向网每对节点之间最短路径的数据结构和动态规划递推算法，要

求算法能输出每条最短路径节点序列.

试用动态规划法求解最长公共子序列问题：

2.若给定序列X={x1,x2,-,xm),则另一序列Z={z1,z2,-,zk},是X的子序列是指存

在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…，k有：zj=xijo例如，序列

Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列，相应的递增下标序列为［2,3,

5,7)o给定2个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时，称Z是序

列X和Y的公共子序列。给定2个序列X={x1,x2,xm)Y=Iy1,y2,yn},找出X和Y

的最长公共于序列。

实验十三作业调度问题

［实验目的］

1.熟悉多机调度问题的算法：

2.进一步掌握贪心算法

3.提高分析与解决问题的能力。

［预习要求］

1.认真阅读教材或参考书，掌握贪心算法的基本思想；

2.写出求解“作业调度”的程序；

3.设计好测试用例。

［实验题］

要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处

理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作

业不能拆分成更小的子作业。

［实验提示］

1.把作业按加工所用的时间从大到小排序：

2.如果作业孰目比机器的数目少页,相等，则直接把作业分配下去：

3.如果作业数目比机器的数目多，则每台机器上先分配一个作业，如下的作业分配时，

是选那个表头上s最小的犍表加入新作业。

typedefstructJob

(

intID;//作业号

inttime；〃作业所花费的时间

}Job;

typedefstructJobNode//作业链表的节点

1

intID;

inttime;

JobNode*next;

)JobNode,*pJobNode；

typedefstructHeader〃链表的表头

(

ints；

pJobNodenext;

)Header,pHeader；

intSeIectMin(Header*M,intm)

(

intk=0;

for(inti=1;i<m；i++)

(

if(M［i］.s<m［k］.s)k=i;

1

returnk；

1

［实验步骤］

1先用贪心算法求解该问题，并测试你的程序，直至正确为止；

2针对问题实例，实