目 录
1. 课程目标.........................................................................1
2. 实验内容.........................................................................1
2.2 实验二 串模式匹配算法（串实验）.................................................................................1
2.3 实验三 二叉树遍历与路径查找（二叉树实验）.............................................................2
3.实验步骤..........................................................................2
3.1 实验一 一元多项式相加（链表应用实验）.....................................................................2
3.1.1 程序流程图................................................................................................................2
3.1.2 源程序........................................................................................................................4
3.1.3 运行结果截图..........................................................................................................15
3.2 实验二 串模式匹配算法（串实验）...............................................................................16
3.2.1 程序流程图..............................................................................................................16
3.2.2 源程序......................................................................................................................19
3.2.3 运行结果截图..........................................................................................................31
3.3 实验三 二叉树遍历与路径查找（二叉树实验）...........................................................37
3.3.1 程序流程图..............................................................................................................37
3.3.2 源程序......................................................................................................................42
3.3.3 运行结果截图..........................................................................................................55
4.总结与体会.....................................................................59
I
5
1. 课程目标
知识目标
课程目标 1：能够应用单链表存储结构及操作算法，采用结构化程序设计思想，编程实现客房数据信
息的创建、输出、查找、修改、插入、删除、排序和复杂综合应用等功能；
课程目标 2：能够应用串的顺序存储结构，编程实现 BF 算法和 KMP 改进算法(Next[ ])和 KMP 改进
算法(NextVal[ ])等模式匹配算法；
课程目标 3：能够应用二叉链表存储结构，编程实现二叉树的建立、遍历和路径查找等操作算法；
能力目标
课程目标 4：能够针对实际问题选择合适的数据结构和方法，设计出结构清晰、正确易读和复杂度较
优的算法，以及合理美观的人机界面，从而具备综合运用多种数据结构与算法解决复杂工程问题的基本
能力；
课程目标 5：具有社会责任感，树立劳动意识，能自觉遵守纪律，爱护公共财物；能够具有工程实践
自主学习意识和开拓创新精神，就任务需求可以独立分析问题和解决问题。
2. 实验内容
2.1 实验一 一元多项式相加（链表应用实验）
定义一元多项式链表结点结构 HLink
(1)实现创建一元多项式链表函数 void Build(HLink &H)；
(2)实现输出一元多项式链表函数 void Exp(HLink H)；
(3)实现函数 void showH(HLink &H, int beds, char *state)，显示已经建立的多项式。
(4) 容错处理：检测任何不合规的输入，并给出必要提示。
(5)函数 void Add(HLink &H，HLink A，HLink B)，将多项式 A、B 相加，结果放入 H；
*(6)函数 HLink MultH(HLink &H，HLink A，HLink B)，选做，将多项式 A、B 相乘，结果放入 H；
(7)优化交互界面，让非专业者（陌生人）也能顺利完成运算。
2.2 实验二 串模式匹配算法（串实验）
实现功能： 从主串中第 K 个字符起，求出子串在主串中首次出现的位置，即模式匹配或串匹配。
要求用三种模式匹配算法分别实现：
朴素的模式匹配算法（BF 算法）
KMP 改进算法(Next[ ])
KMP 改进算法(NextVal[ ])
实验机时：8
设计要求：
首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。
程序运行后，给出 5 个菜单项的内容和输入提示：
1．输入主串、子串和匹配起始位置
2．朴素的模式匹配算法
3．KMP 改进算法(Next[ ])
4．KMP 改进算法(NextVal[ ])
0．退出管理系统
请选择 0—4：
6
菜单设计要求：使用数字 0—4 来选择菜单项，其它输入则不起作用。
输出结果要求：输出各趟匹配详细过程（其中 3、4，首先输出 Next[ ]或者 NextVal[ ]的各元素的
数值），然后输出匹配总趟数、单个字符比较次数、匹配成功时的位置序号或者匹配失败提示
信息。
2.3 实验三 二叉树遍历与路径查找（二叉树实验）
实现功能：建立二叉树存储结构、求二叉树的先序遍历、求二叉树的中序遍历、求二叉树的后
序遍历、求二叉树的层次遍历、求根到给定结点的路径。
实验机时：8
设计要求：
数据结构：
typedef struct node{
char data;//数据域
struct node *lchild , *rchild; //左右孩子指针
}BinTNode, *BinTree; //树中结点类型
首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。
程序运行后，给出如下菜单项的内容和输入提示，使用数字 0—6 来选择菜单项，其它输入则不起作
用：
1．建立二叉树存储结构
2．求二叉树的先序遍历
3．求二叉树的中序遍历
4．求二叉树的后序遍历
5．求二叉树的层次遍历
6．求给定结点的路径
0．退出系统
请选择 0—6：
3.实验步骤
按以上实验内容的要求，给出实验步骤，包括程序流程图、源程序和运行结果截图等。
3.1 实验一 一元多项式相加（链表应用实验）
3.1.1 程序流程图
在 Microsoft Visio 中画出程序流程图，主函数画一张图，各子函数分别各画一张图，再粘贴过来。
main 函数
评论0