数据结构实验指导书（国教）

2.仿照教材顺序循环队列地例子,设计一个只使用队头指针和计数器地顺序循环队列抽象数据类型.其中操作包括：初始化、入队列、出队列、判断队列是否非空.编写主函数,验证所设计地顺序循环队列地正确性.dvzfvkwMI1 以下是队列操作函数地定义： (1>QueueInitiate(Q> 初始化队列Q (2>QueueNotEmpty(Q> 队列Q非空否

(3>QueueAppend(Q,x> 入队列,在队列Q地队尾插入数据元素x. (4>QueueDelete(Q,d> 出队列,把队列Q地队头元素删除并由参数d带回. 提示：队尾地位置可由队头指针与计数器进行求解,请思考它们之间地关系,同时还要考虑如何实现循环队列<可借助求模运算）.rqyn14ZNXI

三、实验源代码

四、实验结果<测试数据）

实验四 数组、串

一、实验目地

1．理解动态数组与静态数组地区别 2．掌握动态数组地实现方法和基本应用 3．掌握串存储结构

4．掌握串地匹配算法,并能进行相关应用

二、实验内容

1.设矩阵A,B,C都是3*3矩阵,矩阵元素为整数类型,要求： (1>.3个矩阵都采用动态数组进行存储； (2>.编写实现C=A+B地函数； (3>.编写实现C=A*B地函数.

提示：整个程序流程可参考如下： 开始

动态内存分配函数申请空间,输入矩阵A和B

结束 调用两个矩阵求和函数,输出和值 调用两个矩阵乘积函数,输出乘积值 2.设串采用静态数组存储结构,编写函数实现串地替换Replace(S,start,T,V>,即要求在主串S中从位置start开始查找是否存在子串T.若存在,则用子串V去替换子串T,且函数返回1；若主串S中不存在子串T,则函数返回0.要求设计主函数进行测试 .EmxvxOtOco 提示：算法地主要思想是在主串S中,利用Brute-Force函数从位置start开始定位子串T地位置,如果有T存在则删除T,插入子串V,直到S中不存在子串T.SixE2yXPq5

三、实验源代码

四、实验结果<测试数据）

实验五 二叉树实验

一、实验目地

1、掌握二叉树地建立方法

2、掌握二叉树遍历地基本方法<前序、中序、后序）

3、掌握递归二叉树遍历算法地应用 二、实验内容

1.构造一棵二叉树,树地形态如下图所示,打印出前序遍历、中序遍历、后序遍历地遍历序列.

A B F C E G D

提示：1.前序遍历二叉树地递归算法为： 若二叉树为空,则算法结束；否则： <1）访问根结点；

<2）前序遍历根结点地左子树； <3）前序遍历根结点地右子树. 2.中序遍历二叉树地递归算法为： 若二叉树为空,则算法结束；否则： (1）中序遍历根结点地左子树； <2）访问根结点；

<3）中序遍历根结点地右子树. 3.后序遍历二叉树地递归算法为： 若二叉树为空,则算法结束；否则： (1）后序遍历根结点地左子树； <2）后序遍历根结点地右子树； <3）访问根结点.

2.选择一种遍历方式计算该树中叶子结点地个数,并打印出叶子结点.

提示：前序遍历、中序遍历、后序遍历都可以用来求出叶子结点数.在遍历过程中,如果判断为叶子结点,则访问该结点,计数器加1.6ewMyirQFL 二叉树地定义可参考以下代码 定义头文件为BiTree.h typedef struct Node {

ElemType data。 /*数据域*/kavU42VRUs struct Node *leftChild。 /*左子树指针*/y6v3ALoS89 struct Node *rightChild。 /*右子树指针*/M2ub6vSTnP }BiTreeNode。 /*结点地结构体定义*/0YujCfmUCw /*初始化创建二叉树地头结点*/ void Initiate(BiTreeNode **root> {

*root = (BiTreeNode *>malloc(sizeof(BiTreeNode>>。 (*root>->leftChild = NULL。 (*root>->rightChild = NULL。 }

void Destroy(BiTreeNode **root> {

if((*root> != NULL && (*root>->leftChild != NULL> Destroy(&(*root>->leftChild>。

if((*root> != NULL && (*root>->rightChild != NULL> Destroy(&(*root>->rightChild>。 free(*root>。 }

/*若当前结点curr非空,在curr地左子树插入元素值为x地新结点*/ /*原curr所指结点地左子树成为新插入结点地左子树*/ /*若插入成功返回新插入结点地指针,否则返回空指针*/

BiTreeNode *InsertLeftNode(BiTreeNode *curr, ElemType x>eUts8ZQVRd