[11]实验指导手册

1、数据结构 实验指导手册 计算机教研室 2008.6 1 实验教学的目的：通过实验，加深对算法与数据结构基本知识的理解， 掌握数据结构的理论和设计技术及其使用，培养学生数据结构的设计、开发能力。 2实验教学的要求：学生每次实验前必须根据实验指导手册，设计出实验 方案（程序和实验步骤）；在实验过程中要求独立进行程序调试和排错，必须学 会使用在线帮助解决实验中遇到的问题，必须应用理论知识分析问题、解决问题。 3实验内容： 实验1: VC6的使用 一、实验目的 理解和掌握如何使用 Visual C + 6.0环境编写C/C + +程序。 二、实验环境 装有Visual C + + 6.0的计算机。 本

2、次实验共计4学时。 三、实验内容 1、熟悉VC6环境 掌握如何创建控制台应用程序。 掌握一些常用快捷键，例如编译F7,运行Ctrl + F5,调试运行F5,单步运行F10/F11，设 置断点F9,格式化代码Alt + F8。 2、掌握如何编译程序 理解编译过程中的错误信息，并掌握如何排错。 3、掌握如何调试程序 掌握如何通过设置断点来单步调试程序，如何查看当前变量的值。 4、实验题: 完成实验教材的实验题 1.1、1.2、1.3。要求： 实现该实验结果。通过该实验题，熟悉VC6环境下的程序编写、编译、调试。 实验2 :顺序表基本运算 一、实验目的 (1) 掌握顺序表的各种基本运算的实现。 (2

3、) 能够利用基本运算进行顺序表的操作。 二、实验环境 装有Visual C + + 6.0的计算机。 本次实验共计2学时。 三、实验内容 1、顺序表基本运算 实现顺序表的各种基本运算；并在此基础上设计一个主程序，完成如下功能: (1) 初始化顺序表L (元素类型为char型) (2) 依次采用尾插法插入 a, b, c, d, e元素 (3) 输出顺序表L (4) 输出顺序表L的长度 (5) 判断顺序表L是否为空 (6) 输出顺序表L的第3个元素 (7) 输出元素的位置 (8) 在第4个元素位置上插入元素 (9) 输出顺序表L (10) 删除顺序表L的第3个元素 (11) 输出顺序表 (12)

4、 释放顺序表 提示：可以参考上课教材、实验教材的实验题2.1。 2、顺序表的应用(选做) (1) 设计通讯录(也可为其他应用)文件的存储格式和线性表的顺序存储结构 (2) 设计在通讯录(也可为其他应用)中添加、删除、查找某个节点信息程序 (3) 调试程序 实验3:单链表基本运算 一、实验目的 (1) 掌握链表的概念；掌握单链表的各种基本运算的实现。 (2) 能够利用基本运算进行单链表的操作。 (3) 加深对链式存储数据结构的理解，逐步培养解决实际问题的编程能力。 二、实验环境 装有Visual C + + 6.0的计算机。 本次实验共计2学时。 三、实验内容 实现单链表的各种基本运算；并在此基

5、础上设计一个主程序，完成如下功能: (1) 初始化单链表L (2) 依次采用尾插法插入 a, b, c, d, e元素 (3) 输出单链表L (4) 输出单链表L的长度 (5) 判断单链表L是否为空 (6) 输出单链表L的第3个元素 (7) 输出元素a的位置 (8) 在第4个元素位置上插入f元素 (9) 输出单链表L (10) 删除单链表L的第3个元素 (11) 输出单链表L (12) 释放单链表L 提示：可以参考上课教材、实验教材的实验题2.2。 实验4:单链表综合实验 一、实验目的 （i）能够利用单链表的基本运算进行单链表的相关操作。 （2 ）掌握文件的应用 （3）加深对链式存储数据结构的

6、理解，逐步培养解决实际问题的编程能力。 二、实验环境 装有Visual C + + 6.0的计算机。 本次实验共计4学时。 三、实验内容 1、通讯录设计 设计一个班级同学的通讯录，要求如下： ? 通讯录中每个同学的信息包含以下内容：学号（ id）、姓名（name）、电话号码（tel）。 如果需要更多其他信息，请自行添加。 ? 程序主菜单包含以下几个功能： (1) 添加记录：通过键盘输入信息，添加一条通讯录记录。 (2) 删除记录: 通过键盘输入学号，删除该学号的记录。 (3) 输出记录： 输出通讯录全部记录。 (4) 按姓名查找：通过键盘输入姓名，输出该同学的所有信息。 (5) 保存记录: 把

7、通讯录中所有的记录保存到文件中。 (6) 清空记录： 删除通讯录中的全部记录，并删除文件。 (7) 退出 提示： ? 程序启动时应判断是否存在记录文件，如果存在，则读取每条记录到链表中。 ? 用户选择并完成主菜单某功能后，除了退出程序，应该返回主菜单。 ? 添加一条记录时，插入到链表的尾部。 ? 查找、删除记录时，如果该记录不存在，则应该输出不存在的提示。 ? 添加记录、删除记录时不需要写文件。 ? 保存记录时，用覆盖写文件的方法。（或者先删除原文件，再保存全部记录信息） ? 各个功能模块写成函数，由主函数调用。 选做： ? 主菜单增加一个排序功能选项， 可以按照学号从小到大进行排序。排序方法

8、可以用冒泡 排序或者插入排序。 实验5:链栈的基本操作 一、实验目的 1) 熟悉栈的定义和栈的基本操作。 2) 掌握链式存储栈的基本运算。 3) 加深对栈数据结构的理解，逐步培养解决实际问题的编程能力。 二、实验环境 装有Visual C + + 6.0的计算机。 本次实验共计2学时。 三、实验内容 必做内容：链栈的基本操作 编写栈的基本操作函数 1. 栈类型的定义，数据域使用char型 typedef char ElemType; typedef struct no de ElemType data; struct node *n ext; Lin kStack; 2 初始化空栈：函数原型如

9、下： void InitLinkStack ( LinkStack * 否则 返回0。 例如：abcba”和abba”都是对称字符串。 实验6:队列的基本操作 一、实验目的 1）熟悉队列的定义和队列的基本操作。 2）掌握顺序循环队列和链式存储队列的基本运算。 3）加深对队列数据结构的理解，逐步培养解决实际问题的编程能力。 二、实验环境 装有Visual C + + 6.0的计算机。 本次实验共计2学时。 三、实验内容 队列的基本操作 队列的存储结构从 顺序循环队列 或者链队任选一种。 编写一个程序，实现队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能: (1) 初始化队列q (2)

10、 判断q是否非空 (3) 依次进队兀素a, b, c (4) 出队一个兀素，输出该兀素 (5) 输出队列q的兀素个数 (6) 依次进队列兀素 d, e, f (7) 输出队列q的兀素个数 (8) 输出出队序列 (9) 释放队列 实验7:栈和队列综合实验 一、实验目的 （i）能够利用栈和队列的基本运算进行相关操作。 （2 ）进一步熟悉文件的应用 （3 ）加深队列和栈的数据结构理解，逐步培养解决实际问题的编程能力。 二、实验环境 装有Visual C + + 6.0的计算机。 本次实验共计4学时。 三、实验内容 以下两个实验任选一个。 1、迷宫求解 设计一个迷宫求解程序，要求如下： ? 以M X

11、N表示长方阵表示迷宫，求出一条从入口到出口的通路，或得出没有通路的结 论。 ? 能任意设定的迷宫 ?（选作）如果有通路，列出所有通路 提示： ? 以一个二维数组来表示迷宫，0和1分别表示迷宫中的通路和障碍， 如下图迷宫数据为: 1111111111 1001000101 1001000101 1000011001 1011100001 1000100001 1010001001 1011101101 1100000001 1111111111 入口位置：1 1 出口位置：8 8 ? 探索过程可采用如下算法，设定当前位置的初值为入口位置； do 若当前位置可通， 则 将当前位置插入栈顶； 若该位

12、置是出口位置，则结束； 否则切换当前位置的东邻方块为新的当前位置； 否则， 若栈不空且栈顶位置尚有其他方向未经探索， 则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块; 若栈不空但栈顶位置的四周均不可通， 则删去栈顶位置；/从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块出栈至栈空； while （栈不空）； 2、机场飞机起降的过程模拟 熟悉队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能： 模拟一个机场飞机起降的过程 机场仅有一条跑道，要求起飞与降落不能同时进行 进场飞机若暂时没有跑道可用须在空中盘旋等候 离场飞机若暂时没有跑道可用

13、须在地面排队等候 仅当空中无飞机等待降落时地面飞机方可起飞 飞机的申请进场、降落、申请离场和起飞分别视为独立事件 每个事件的发生占用一个时间单位。除降落和起飞外，各事件可以同时发生 提示： ? 设定一个待飞队列用于存放排队等候的航班信息 ? 设定一个待降落队列用于存放等待降落的航班信息 ? 飞机的申请进场、 降落、申请离场和起飞可以通过航班事先设定的起飞时间、飞行时间 长度或者降落时间信息来确定，这些信息可以存放在一个文件中，程序运行时从文件中 读出。 ? 航班当前状态可表示为：起飞，降落，申请进场，申请离场，空闲 ? 每个事件的发生占用一个时间单位可以自己约定，起飞，降落可以设定为30分钟

14、实验 int len; SeqStri ng; (1) 串赋值 Assig n(s,t) 将一个字符串常量赋给串s,即生成一个其值等于t的串s (2) 串复制 StrCopy(s,t) 将串t赋给串s (3) 计算串长度 StrLe ngth(s) 返回串s中字符个数 (4) 判断串相等 StrEqual(s,t) 若两个串s与t相等则返回1;否则返回0。 (5) 串连接Con cat(s,t) 返回由两个串s和t连接在一起形成的新串。 (6) 求子串 SubStr(s,i,j) 返回串s中从第i(1 iw StrLength(s)个字符开始的、由连续j个字符组成的 子串。 (7) 插入 In

15、sStr (s,i,t) 将串t插入到串s的第i(1 w i w StrLength(s)+1)个字符中，即将t的第一个字符 作为s的第i个字符，并返回产生的新串 (8) 串删除 DelStr (s,i,j) 从串s中删去从第i(1 w iw StrLength(s)个字符开始的长度为j的子串 并返回 产生的新串。 (9) 串替换 RepStr (s,s1,s2) 在串s中，将所有出现的子串si均替换成s2。 (10) 输出串 DispStr(s) 输出串s的所有元素值 (11) 判断串是否为空IsEmpty(s) 编写主函数 调用上述函数实现下列操作： (1) 建立串 s= abcdefgh

16、ijklmn ”,串 s仁xyz ”，串 t = hijk ” (2) 复制串t到t1,并输出t1的长度 (3) 在串s的第9个字符位置插入串s1而产生串s2,并输出s2 (4) 删除s第2个字符开始的5个字符而产生串S3,并输出S3 (5) 将串s第2个字符开始的3个字符替换成串s1而产生串S4,并输出S4 (6) 提取串s的第8个字符开始的4个字符而产生串S5,并输出S5 (7) 将串s1和串t连接起来而产生串 S6,并输出S6 (8) 比较串s1和S5是否相等，输出结果 实验9:矩阵的基本操作 一、实验目的 1) 熟悉数组、矩阵的定义和基本操作。 2) 掌握对称矩阵、稀疏矩阵等特殊矩阵的

17、存储方式和基本运算。 3) 加深对数组、矩阵的理解，逐步培养解决实际问题的编程能力。 二、实验环境 装有Visual C + + 6.0的计算机。 本次实验共计2学时。 三、实验内容 以下两个实验任选一个。 1、实现稀疏矩阵的转置、求和 假设mxn的稀疏矩阵用三元组表示，编写一个程序实现如下功能： (1) 生成如下两个稀疏矩阵的三元组a和b,并输出三元组表示。 提示：程序中可以用int A44和B44二维数组表示原始矩阵A和B。 (2) 输出a的转置矩阵的三元组表示。 (3) 设c= a+ b，输出c的三兀组表示。 2、求对称矩阵之和、乘积 已知A和B为两个nxn阶的对称矩阵，编写一个程序实现

18、: (1) 将其下三角元素存储在一维数组 a和b中，并输出。 提示：程序中可以用int A44和B44二维数组表示原始矩阵A和B。 (2) 设C= A + B,以矩阵方式输出C。 (3) 设D = A X B,以矩阵方式输出D。 实验10:字符串综合实验 一、实验目的 1）熟悉串的定义和串的基本操作。 2）加深对串数据结构的理解，逐步培养解决实际问题的编程能力。 二、实验环境 装有Visual C + + 6.0的计算机。 本次实验共计4学时。 三、实验内容 以下两个实验任选一个。 1、凯撒加密算法 凯撒密码（caeser）是罗马扩张时期朱利斯？凯撒（Julius Caesar）创造的，用于加

19、密通 过信使传递的作战命令。它将字母表中的字母移动一定位置而实现加密。 他的原理很简单，说到底就是字母与字母之间的替换。每一个字母按字母表顺序向后移 3位，如a加密后变成d, b加密后变成e,x加密后变成a, y加密后变成b, z加密 后变成c。 例如：baidu ”用凯撒密码法加密后字符串变为edlgx ”。 试写一个算法，将键盘输入的文本字符串（只包含az的字符）进行加密后输出。 另写一个算法，将已加密后的字符串解密后输出。 提示： ? 如果有字符变量c加密后则=+（ c-a+ 3）% 26 ? 采用顺序结构存储串，键盘输入字符串后保存到顺序串中；输出用顺序串的输出函数。 2、求一个串中出

20、现的第一个最长重复子串 采用顺序结构存储串，编写一个程序，求串s中出现的第一个最长重复子串的下标和长 度。 实验11:递归综合实验 一、实验目的 1）熟悉递归的定义和递归的算法设计。 2）加深对递归算法的理解，逐步培养解决实际问题的编程能力。 二、实验环境 装有Visual C + + 6.0的计算机。 本次实验共计4学时。 三、实验内容 以下两个实验任选一个。 1、求解n皇后问题 编写一个程序，求解皇后问题：在nxn的方格棋盘上，放置 n个皇后，要求每个皇后 不同行、不同列、不同对角线。 要求：使用递归算法求解；皇后的个数n由用户输入，其值不能超过 20。 2、求解汉诺塔问题 设有3个分别命

21、名为X,Y和Z的塔座，在塔座X上有n个直径各不相同，从小到大依次编 号为1,2,n的盘片,现要求将X塔座上的n个盘片移到塔座 Z上并仍按同样顺序叠放，盘片 移动时必须遵守以下规则：每次只能移动一个盘片；盘片可以插在X,Y和Z中任一塔座； 任何时候都不能将一个较大的盘片放在较小的盘片上。设计递归求解算法。 要求：使用递归算法求解；盘片的个数n由用户输入，其值不能超过12。 实验12:二叉树的操作 一、实验目的 1) 熟悉二叉树树的基本操作。 2) 掌握二叉树的实现以及实际应用。 3) 加深二叉树的理解，逐步培养解决实际问题的编程能力。 二、实验环境 装有Visual C + + 6.0的计算机。

22、 本次实验共计4学时。 三、实验内容 1、二叉树的基本操作 【问题描述】 现需要编写一套二叉树的操作函数，以便用户能够方便的利用这些函数来实现自己的应 用。其中操作函数包括： 1创建二叉树CreateBTNode(*b,*str)：根据二叉树括号表示法的字符串*str生成对应的 链式存储结构。 2 输出二叉树 DispBTNode(*b):以括号表示法输出一棵二叉树。 3查找结点FindNode(*b,x):在二叉树b中寻找data域值为x的结点，并返回指向该结 点的指针。 4求高度BTNodeDepth(*b):求二叉树b的高度。若二叉树为空，则其高度为0;否则， 其高度等于左子树与右子树中

23、的最大高度加I。 5求二叉树的结点个数 NodesCount(BTNode *b) 6先序遍历的递归算法：void PreOrder(BTNode *b) 7中序遍历的递归算法：void InOrder(BTNode *b) 8 后序遍历递归算法：void PostOrder(BTNode *b) 9 层次遍历算法 void LevelOrder(BTNode *b) 【基本要求】 实现以上9个函数。 主函数中实现以下功能： 创建下图中的树b 输出二叉树b 找到节点，输出其左右孩子值 输出b的高度 输出b的节点个数 输出b的四种遍历顺序 【实验提示】 数据结构的定义: #i nclude #i

24、n elude /*数据元素*/ /*指向左孩子*/ /*指向右孩子*/ #defi ne MaxSize 100 typedef char ElemType; typedef struct node ElemType data; struct node *lchild; struct node *rchild; BTNode; 各个函数的定义： void CreateBTNode(BTNode * BTNode *FindNode(BTNode *b,ElemType x); int BTNodeDepth(BTNode *b); void DispBTNode(BTNode *b); in

25、t NodesCou nt(BTNode *b); void PreOrder(BTNode *b); void In Order(BTNode *b); void PostOrder(BTNode *b); void TravLevel(BTNode *b); 主函数的结构： void mai n() BTNode *b,*p,*lp,*rp; char str=A(B(D,E(H(J,K(L,M(,N),C(F,G(,l); CreateBTNode(b,str); prin tf(n); printf(输出二叉树:);DispBTNode(b);printf(n); printf(H结点

26、:”); p=Fi ndNode(b,H); if (p!=NULL) 此处输出p的左右孩子节点的值 prin tf(n); printf(” 二叉树 b 的深度:%dn”,BTNodeDepth(b); printf(二叉树 b 的结点个数：dn,NodesCount(b); prin tf(n); printf(先序遍历序列 prin tf(递归算法 prin tf(中序遍历序列 prin tf(递归算法 printf(后序遍历序列 prin tf(递归算法 printf(层次遍历序列 n); ”);PreOrder(b);pri ntf(n); n); );I nOrder(b);pri

27、 ntf(n ”); n); );PostOrder(b);pri ntf(n ”); );prin tf(n ”); TravLevel(b); prin tf(n); 2.2二叉树的线索化 【问题描述】 编写一个程序，实现中序线索化二叉树，输出线索中序序列。 【基本要求】 用上图的二叉树 b来验证你的程序。 【实验提示】 数据结构的定义： #i nclude #i nclude #defi ne MaxSize 100 typedef char ElemType; typedef struct node ElemType data; int ltag,rtag;/*增加的线索标记*/ st

28、ruct node *lchild; struct node *rchild; TBTNode; TBTNode *pre; 各个函数的定义： void CreateTBTNode(TBTNode * CreateTBTNode(b,A(B(D,E(H(J,K(L,M(,N),C(F,G(,l); printf(二叉树:);DispTBTNode(b);printf(n); tb=CreaThread(b); printf(线索中序序列:);ThInOrder(tb);printf(n); 3 .实验结果 此处填写程序运行结果。 4 .实验心得 此处填写你的实验心得体会。 实验13:哈夫曼编码

29、 一、实验目的 1) 熟悉哈夫曼树的基本操作。 2) 掌握哈夫曼编码的实现以及实际应用。 3) 加深对哈夫曼树、哈夫曼编码的理解，逐步培养解决实际问题的编程能力。 二、实验环境 装有Visual C + + 6.0的计算机。 本次实验共计4学时。 三、实验内容 【问题描述】 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。 但是，这要求发送端通过一个编码系统对数据进行编码，在接受端将传来的数据进行译码。 试为这样的信息收发站写一个哈夫曼编码/译码系统。 【基本要求】 本系统应实现以下功能：(功能13必做，4为选做，请课后自行完成) (1) 初始化：字符集(字母 a

30、z，空格)共27个字符，以及其权值。建立哈夫 曼树。并建立各个字符的哈夫曼编码。 (2) 打印字符集的哈夫曼编码。 (3) 编码：从终端读入字符串，实现该字符串的编码。 (4) 译码：实现刚才生成的哈夫曼编码还原为字符串。(选做) 【已知条件】 (1)字符集的权值如下表: A H C D E F G H 1 1 K JS度 13S 64 J5 22 32 IM l 15 17 57 I 5 32 20 a P Q R S T U V W X Y Z 57 63 15 1 48 51 so 23 a 18 I 1 【实验提示】 数据结构的定义: #defi ne N 50 #define M 2

31、*N-1 /*叶子结点数*/ /*树中结点总数*/ typedef struct char data; int weight; int pare nt; int lchild; int rchild; HTNode; /*结点值*/ /*权重*/ /*双亲结点*/ /*左孩子结点*/ /*右孩子结点*/ typedef struct char cdN; int start; HCode; /*存放哈夫曼码*/ 各个函数的定义： void CreateHT(HTNode ht,int n)/* 创建哈夫曼树 */ void CreateHCode(HTNode ht,HCode hcd,int

32、n)/*创建哈夫曼编码 */ void DispHCode(HTNode ht,HCode hcd,i nt n)/* 显示各个字符的哈夫曼编码 */ void Encode(char *s,HTNode ht,HCode hcd,int n) /* 显示字符串 s 的哈夫曼编码 */ 主函数的结构： char str= ,a,b,c,d,e,f,g,h,i,j,k,T,m, n, o,p,q,r,s,t,u,v,w,x,y,z; /* 字符集 */ int fnum=186,64,13,22,32,103,21,15,47,57,1,5,32,20,57, 63,15,1,48,51,80,

33、23,8,18,1,16,1; /* 字符集对应的权值 */ CreateHT(); CreateHCode(); DispHCode(); gets(s); En code(); 实验14:图的存储和遍历 、实验目的 1）熟悉图的基本操作。 2）掌握图的存储实现以及遍历操作。 3）加深对图的理解，逐步培养解决实际问题的编程能力。 、实验环境 装有Visual C + + 6.0的计算机。 本次实验共计2学时。 三、实验内容 【基本要求】 1、用邻接矩阵存储方式，表示下面的图，并输出。 2、由上面的邻接矩阵产生邻接表，并输出。 3、编程完成从顶点 0开始的深度优先遍历和广度优先遍历。 【输出结

34、果】 输出结果例子如下: 有向图G的邻接矩阵： 050700 004000 800009 005006 000500 300010 图G的邻接矩阵转换成邻接表 0:13 1:2 2:05 3:25 4:3 5:04 从顶点0开始的DFS: 012543 从顶点0开始的BFS: 013254 /*INF 表示a */ 【提示】 #i nclude #i nclude #defi ne MAXV 100 #defi ne INF 32767 typedef int In foType; /*以下定义邻接矩阵类型*/ typedef struct int no; In foType info; Ve

35、rtexType; typedef struct int edgesMAXVMAXV; int vexnu m,arc num; VertexType vexsMAXV; MGraph; /*以下定义邻接表类型*/ typedef struct ANode int adjvex; struct ANode *n extarc; /*最大顶点个数*/ /*顶点编号*/ /*顶点其他信息*/ /*顶点类型*/ /*图的定义*/ /*邻接矩阵*/ /*顶点数，弧数*/ /*存放顶点信息*/ /*图的邻接矩阵类型*/ /*弧的结点结构类型*/ /*该弧的终点位置*/ /*指向下一条弧的指针*/ In

36、foType info; ArcNode; /*该弧的相关信息，这里用于存放权值*/ typedef int Vertex; typedef struct Vnode Vertex data; ArcNode *firstarc; VNode; typedef VNode AdjListMAXV; typedef struct AdjList adjlist; int n ,e; ALGraph; /*邻接表头结点的类型*/ /*顶点信息*/ /*指向第一条弧*/ /*AdjList是邻接表类型*/ /*邻接表*/ /*图中顶点数n和边数e*/ /*图的邻接表类型*/ /*全局数组*/ /*邻

37、接矩阵转为邻接表*/ /*输出邻接矩阵*/ /*输出邻接表*/ /*深度优先遍历*/ /*广度优先遍历*/ in t visitedMAXV; void MatToList(MGraph,ALGraph * void DispMat(MGraph); void DispAdj(ALGraph *); void DFS(ALGraph *G ,int v); void BFS(ALGraph *G ,int v); void mai n() int i,j; MGraph g; ALGraph *G; int AMAXV 6= 0,5,0,7,0,0, 0,0,4,0,0,0, 8,0,0,0,

38、0,9, 0,0,5,0,0,6, 0,0,0,5,0,0, 3,0,0,0,1,0; g.vex num=6;g.arc num=10; for (i=0;ig.vex nu m;i+) for (j=0;jg.vex nu m;j+) g.edgesij=Aij; prin tf(n); printf(”有向图G的邻接矩阵:n); DispMat(g); G=(ALGraph *)malloc(sizeof(ALGraph); printf(”图G的邻接矩阵转换成邻接表:n); MatToList(g,G); DispAdj(G); prin tf(n); printf(从顶点0开始的DF

39、S:n); DFS(G,O); prin tf(n); printf(从顶点0开始的BFS:n”); BFS(G,0); prin tf(n); void MatToList(MGraph g,ALGraph *如果不存在，则按照二叉排序树的要求插入该字 符结点，同时设置出现次数为1。 ? 全部字符读完以后，调用二叉树的中序遍历，有序的输出每个字符及其出现的次数。 2、二叉排序树 【基本要求】 编写一个程序，实现二叉排序树的基本运算，并在此基础上完成如下功能： (1) 由4 , 9, 0, 1 , 8, 6, 3, 5, 2, 7创建一棵二叉排序树 bt,并以括号表示法输出。 (2) 判断bt是否为一棵二叉排序树。 (3) 采用递归和非递归两种方法查找关键字为6的结点，并输出其查找路径。 (4) 分别删除bt中的关键字为4和5的结点，并输出删除后的二叉排序。 【输出结果】 输出结果例子如下: 创建一棵BST树: 第1步，插入4:4 第2步，插入9:4(