-
个人资料整理
仅限学习使用
算法设计与分析
实
验
指
导
书
信息科学技术学院
目录
个人资料整理
仅限学习使用
实验一常见简单算法的设计、实现与分析
[
实验目的
]
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
.
掌握树结构表示下集合的并运算与查找算法。
3
.
编程实现集合的表示与操作算法
.
[
预习要求
]
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
。
否则
,
返回并集的根节点索引
.
[
实验步骤
]
1
.
设计
Find
的
测试方案和程序
,
输入测试数据
,
修改并调试程序
,
直至正确为止。
2
.
设计
Union
的
测试方案和程序
,
输入测试数据
,
修改并调试程序
,
直至正确为止。
3
.
待各功能子程序调试完毕
,
去掉测试程序
,
将你的程序整理成功能模块存盘备用
.
[
实验报告要求
]
1
.
阐述实验目的和实验内容。
2
.
提交实验程序的功能模块。
3
.
记录最终测试数据和测试结果。
[
思考题
]
试用
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>
。
-
-
-
-
-
-
-
-
本文更新与2021-01-25 09:17,由作者提供,不代表本网站立场,转载请注明出处:https://www.bjmy2z.cn/gaokao/565049.html
-
上一篇:路作文之英语作文丝绸之路
下一篇:2013--2016年大学英语六级翻译真题及答案