算法方案与分析实验指导书

2021年1月25日发(作者：第二十二)

个人资料整理

仅限学习使用



算法设计与分析



实


验


指


导


书






信息科学技术学院


目录






个人资料整理

仅限学习使用






















实验一常见简单算法的设计、实现与分析


[
实验目的
]

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

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

[
预习要求
]

1.
认真阅读教材或参考书
,
掌握线性表算法的基本思想；

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

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


[
类型定义
]
typedef struct Lnode

{int data
。

struct Lnode *next
。

}Lnode,*linklist
。


[
实验提示
]

个人资料整理

仅限学习使用

void create(link *h,int n>
{//
创建单链表

link p,q
。

int i
。

p=(link>malloc(sizeof(node>>
。

p->next=null
。

*h=p
。
q=p
。

for(i=1
。
i<=n
。
++i>
{p=(link>malloc(sizeof(node>>
。

scanf(
。

p->next=null
。
q->ne xt=p
。
q=p
。

}
}
void print(link h>
{//
输出单链表

link p
。

p=h->next
。

while(p>
{printf(
。

p=p->next
。

}
}
void insertlist(linklist *L,int i,int e>
{//
在单链表的第
i
个元素之前插入元素值为
e
的 结点
}
void dellist(linklist *L,int i,int *e>
{//
删除单链表的第
i
个结点，被删结点通过
e
返回
}

[
实验步骤
]
1.

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

2.

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

3.

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

[
实验报告要求
]
1.

2.

3.

4.

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

提交模块化的实验程序源代码；

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

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

[
思考与练习
]
怎样用链表实现循环队列。

实验二多项式加法



[
实验目的
]

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

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

[
预习要求
]

1.
认真阅读教材或参考书
,
掌握线性表算法的基本思想；

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

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


[
类型定义
]
typedef struct Lnode


个人资料整理

仅限学习使用

{int coef,exp
。

struct Lnode *next
。

}Lnode,*linklist
。


[
实验提示
]
void create(link *h,int n>
{//
创建一元多项式

link p,q
。

int i
。

p=(link>malloc(sizeof(node>>
。

p->next=null
。

*h=p
。
q=p
。

for(i=1
。
i<=n
。
++i>
{p=(link>malloc(sizeof(node>>
。

scanf(
。

p->next=null
。
q->ne xt=p
。
q=p
。

}
}
void print(link h>
{//
输出单链表

link p
。

p=h->next
。

while(p>
{printf(
。

p=p->next
。

}
}
void addlist(linklist *A, linklist B> < br>{//
将
A
和
B
相加并通过
A
返回
}

[
实验步骤
]
1
．

先用插表尾的方法建立一元多项式，并将一元多项式输出，并测试你的程序，直至正确为止；

2
．

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

3
．

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

[
实验报告要求
]
1
．

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

2
．

提交模块化的实验程序源代码；

3
．

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

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

[
思考与练习
]
写出约瑟夫问题的求解算法，即
n
个人坐 成一圈，报
m
出圈，输出最后一个报
m

的人。

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

[
实验目的
]
１
.

了解集合的不同表示方法
,
掌握集合的树结构表示方法。

２
.

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

３
.

编程实现集合的表示与操作算法
.
[
预习要求
]
1.

认真阅读教材内容
,
熟悉树结构表示的原理和操作算法。


个人资料整理

仅限学习使用

2.

设计和编制实验程序
.
[
参考数据类型或变量
]






typedef ElemType int /*
实型或任意其它元素类型
*/
typedef struct {


ElemType elem
。

int tag
。
/*
根节点为负的整数
,
表示该集合的基数的负值,
否则为父节点索引指针
*/
}NODE
。

NODE *set
。
/*
用动态存储分配实现集合的树表示与存储
*/
[
参考子程序接口与功能描述
]


void InitSet(NODE *set>
int Find(NODE *set, ElemType elem>
功能
:
根据集合的基数动态分配存储
,
输入各元素
,
初始化子集森林
.
功能
:
在数组
set
中顺序查找元素
elem,
如果不成功
,
返回
-1
。

否则
,
使用带压缩规则的查找算法< br>,
返回所在子集
的根节点索引
.


int Union(NODE *set, ElemType elem1, ElemType elem2>

功能
:
应用
Find
算法首先找到
elem1
和
elem2
所在的子集
,
然后应用带加权规则的并运算算法合并两个
子集
.
不成功时
,
返回
-1
。

否则
,
返回并集的根节点索引
.

[
实验步骤
]
１
.

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

２
.

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

３
.

待各功能子程序调试完毕
,
去掉测试程序
,
将你的程序整理成功能模块存盘备用
.
[
实验报告要求
]
１
.

阐述实验目的和实验内容。

２
.

提交实验程序的功能模块。

３
.

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

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


实验四

迷宫问题求解

[
实验目的
]

1
．熟悉栈用法；

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

[
预习要求
]

1.
认真阅读教材或参考书
,
掌握栈用法的用法；

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

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

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

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

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

在任意时刻，老鼠在迷宫中的位置可以用所在 点的行下标与列下标
）来表示，这样，老鼠在迷宫中
的某点
maze [i][j]
时，其可能的运动方向有八个。下图
+
表示某时刻老鼠所在的位置
）
,
相邻的八个位
置分别标以
N
、
NE
、
E
、
SE
、
S
、
SW
、
W
、
NW<
分别代表
+
点的北、东北、东、东南、南、西南、西、 西北方
向）；同时，相对于
），这八个相邻位置的坐标的值都可以计算出来。


个人资料整理

仅限学习使用

但是，并非迷宫中的每一个点都有 八个方向可走，四个角上就只有三个方向可供选择，边上只有五个方
向可供选择。为了不在算法中每次都 去检查这些边界条件，在迷宫外面套上一圈，其元素值均为
1
。

NW
N
NE
，
J-1
）

，
J
）

，
J+1
）

W
+
E
，
J-1
）

，
J
）

，
J+1
）

SW
S
SE
，
J-1
）

，
J
）

，
J+1
）

为了简化算法，根据上图所示的位置
）与其相邻的八个位置的坐标关系，建立一个下图所示的表
move,
表中给出相对于位置
）的八个方向上的
i
与
j
的 增量值。

Move

-1
0
-1
1
0
1
1
1
1
0
1
-1
0
-1
-1
-1

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

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

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

例如：若
）为
<3
，
4
），则
SW
的相邻点的坐标为
<3+1
，
4-1
）。

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

当选定一个可通的方向后，要把目前所在 的位置以及所选的方向记录下来，以便往下走时可依次一点一
点退回来，每退一步后接着试在该点未试过 的方向。为了避免走回到已经进入过的点，
maze[i][j]=2.

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

#define m 6
#defing n 9
void path(>
{int maze[m+2][n+2]
。

int move[8][2]
。

int s[54][3]
。

int top=0
。

int i,j,k,pf=0
。

for(i=0
。
i。
++i>
for(j=0
。
j。
++j>
scanf(“%d”,&maze[i][j]>
。

maze[1][1]=2
。

s[top][0]=1
。

s[top][1]=1
。

s[top][2]=0
。

++top
。

while (top!=0&&f==0>
{--top
。

i= s[top][0]
。

j= s[top][1]
。

k= s[top][2]
。

while(k<8>
g=i+move[k][0]
。

h=j+move[k][1]
。

if (g==m&&h==n&&maze[g][h]==0>
{for(p=0
。
p。
++p>
printf(s[p][0],s[p][1]>
。

printf(i,j>
。

printf(m,n>
。