、线性表上机实验题1. 实验目的：(1) 掌握顺序表的基本操作的实现方法。(2 )应用顺序表的基本操作算法实现集合A=AUB算法。( 3)掌握链式线性表的基本操作的实现方法。(4)利用链表的基本操作算法实现集合A=AAB算法。2. 实验内容：2.1 编写一个程序数完成如下功能：(1)( 2)( 3 )( 4)( 5 )( 6 )( 7 )( 8 )( 9 )初始化顺序表 依次插入 a， 输出顺序表 输出顺序表 判断顺序表 输出顺序表 输出元素algol-l.cpp，实现顺序表的各种基本运算，并在此基础上设计一个主函L；b， c， d， e 元素； L；L长度；L 是否为空；L的第3个元素；a的位置；在第4个元素位置上插入f元素;输出顺序表 L；( 10 )删除 L 的第 3 个元素； (11)输出顺序表 ( 12 )释放顺序表2.2 编写一个程序2.3 编写一个程序L；Loalgo1-2.cpp，可利用以上基本操作算法，实现A=AUB算法。algo1-3.cpp，实现单链表的各种基本运算，并在此基础上设计一个主程序 exp1-2.cpp 完成如下功能：(1)( 2)( 3 )( 4)( 5 )( 6 )( 7 )( 8 )( 9 )初始化单链表 H； 依次插入 a， b， c， d， e 元素； 输出单链表 输出单链表 判断单链表 输出单链表 输出元素H；H 长度；H是否为空；H 的第 3 个元素；a的位置；在第4个元素位置上插入f元素; 输出单链表 H；( 10)删除 H 的第 3 个元素； (11)输出单链表 ( 12 )释放单链表2.4编写一个程序algo1-4.cpp，可利用以上基本操作算法，实现递增有序的两个单链表 B的交集运算A=AABoH；HoA、栈和队列上机实验题1. 实验目的：（1）掌握顺序栈和链栈的各种基本运算（2）掌握循环队列的各种基本运算（3）利用栈先进后出的特点，解决一些实际问题。2. 实验内容：2.1编写一个程序 algo2-1.cpp，实现顺序栈的各种基本运算，并在此基础上设计一个主函 数完成如下功能：（1）初始化顺序栈 S；（2）判断栈S是否非空；（ 3）依次进栈元素 a， b， c， d， e；（4）判断栈S是否非空；（ 5）输出栈的长度；（ 6）输出从栈顶到栈底元素；（ 7）元素出栈，输出出栈序列；（8）判断栈S是否非空；（ 9）释放栈。2.2编写一个程序 algo2-2.cpp，可用以上基本算法，实现：对于输入的任意一个非负十进 制整数，打印输出与其等值的八进制数；2.3 （选做）编写一个程序 algo2-3.app，实现：将中缀表示的算术表达式转换成后缀表示， 并计算表达式的值。 （为了方便，假定变量名为单个数字（09），运算符只有 +、-、*、/）。2.4编写一个程序 algo2-4.cpp，实现链栈的各种基本运算，并在此基础上设计一个主函数 完成如下功能：（ 1 ）初始化链栈 S；（2）判断栈S是否非空；（ 3）依次进栈元素 a， b， c， d， e；（4）判断栈S是否非空；（ 5）输出栈的长度；（ 6）输出从栈顶到栈底元素；（ 7）元素出栈，输出出栈序列；（8）判断栈S是否非空；（ 9）释放栈。2.5编写一个程序 algo2-5.cpp，实现循环队列的各种基本运算，并在此基础上设计一个主 函数完成如下功能：（ 1 ）初始化队列 Q；（ 2）判断队列 Q 是否非空；（ 3）依次入队元素 a， b， c；（ 4）出队一个元素，输出该元素；（ 5）输出队列 Q 的元素个数；（ 6）依次进队列元素 d， e， f；（7）输出队列 Q 的元素个数；（8）元素出队，输出出队序列；（ 9）释放队列。2.6（选做）利用递归实现汉诺塔算法。三、串上机实验题1. 实验目的：（ 1 ）掌握顺序串的各种基本运算（2）掌握模式匹配算法2. 实验内容：个主函2.1编写一个程序algo3-1.cpp，实现顺序串的各种基本运算，并在此基础上设计-数完成如下功能：（ 1 ）建立串 s=”abcdefghefghijklmn ”和串 s1=”xyz”；（ 2）输出串 s；（3）输出串 s 的长度；（4）在串s的第9个字符位置插入串si而产生串S2;（ 5）输出串 s2；（ 6）删除串 s 第 2 个字符开始的 5 个字符而产生串 s2;（ 7）输出串 s2;（ 8）将串 s 第 2 个字符开始的 5 个字符替换成串 s1 而产生串 s2;（ 9）输出和串 s2.（10）提取串s的第2个字符开始的10个字符而产生串S3；（11）输出串 s3;（ 12 ）将串 s1 和串 s2 连接起来而产生串 s4；（ 13 ）输出串 s4。2.2 编写一个程序，实现顺序串的各种模式匹配运算，并在此基础上完成如下功能：（1）建立abcabcdabcdeabcdefabcdefg 目标串 s 禾口 abcdeabcdefab 模式串 t ；（2） 采用简单匹配算法求t在s中的位置；（ 3）由模式串 t 求出 next 值，并打印出来。（4）采用KMP算法求t在s中的位置。四、数组一一上机实验题1. 实验目的：(1 )掌握数组的定义、赋值和输入输出方法等基本操作(2 )掌握稀疏矩阵的生成方法及转置方法2. 实验内容：2.1已知Fibonacci数列为：0,1,1,2,3,，即即Fib (0) =0Fib (1) =1?Fib (n) =Fib (n-1) +Fib (n-2)试编写一个程序求 Fibonacci数列中的前20项，并用数组存放，按一行5个数输出。2.2实现稀疏矩阵(采用三元组表示)的基本运算：假设nxn的稀疏矩阵A采用三元组表示，编写一个程序实现如下功能：(1) 生成如下两个稀疏矩阵的三元组a和borl03 OiU10000100011r3 000iU 4000 0 10 0 0 2(2) 输出a转置矩阵的三元组。(3) (选做)输出a+b的三元组c (算法思想：从a、b的第一个元素开始比较，若行号相等，则比较列号：若 a元素的列号小于b元素的列号，则将 a元素添加到c中，a的下 一个元素继续与 b当前元素比较；若 a元素的列号大于b元素的列号，则将 b元素添加 到c中，b的下一个元素继续与 a的当前元素比较；若a元素的列号等于b元素的列号， 则c元素的值为a元素的值+b元素的值，c元素的行号列号与 a或b的行号列号相等，a 的下一个元素继续与 b的下一个元素比较。 若行号不等：a元素的行号小于b元素的行号， 则将a元素添加到c中，a的下一个元素继续与 b当前元素比较；若 a元素的行号大于b 元素的行号，则将 b元素添加到c中，b的下一个元素继续与 a的当前元素比较。)1. 实验目的:（1）掌握二叉树的创建及各种遍历算法（2）掌握二叉树遍历算法的应用（3）掌握二叉树的中序线索化方法及对中序线索二叉树的遍历算法（4）掌握哈夫曼树的构造及哈夫曼编码2. 实验内容:2.1编写一个程序，实现二叉树的各种运算，并在此基础上设计一个主函数完成如下功能:（1 ）按先序遍历的字符序列创建二叉链表存储的二叉树，二叉树如下图所示:（2）用递归算法先序遍历创建的这棵二叉树（3）用递归算法后序遍历创建的这棵二叉树（4）用递归算法中序遍历创建的这棵二叉树（5）输出二叉树的结点个数（6）输出二叉树的高度（7）输出二叉树每层结点个数2.2编写一个程序，实现以下功能：（1）对上题中的二叉树进行中序线索化（2）对中序线索二叉树进行中序遍历，输出线索中序序列。2.3构造哈夫曼树:编写一个程序，构造一棵哈夫曼树，输出对应的哈夫曼编码。并对如下表所示的数据进行 验证。单词TheofatoandinthatheisatonforHisarebe出现频度1192677541518462450242195190181174157138124123六、图一一上机实验题1. 实验目的：（1）掌握图的邻接矩阵及邻接表存储（2）掌握图的深度优先遍历和广度优先遍历（3） 掌握构造最小生成树的Prim算法及Kruskal算法（4 ）掌握图中从一个源点到其他各点的最短路径2. 实验内容:2.1编写一个程序，实现图相关的运算，并在此基础上设计一个主函数，完成如下功能:（1）（2）（3）（4）建立如图1 建立有向图 输出有向图 输出有向图所示的有向图G的邻接矩阵，并输出。 G的邻接表，并输出。0开始的深度优先遍历序列0开始的广度优先遍历序列G从顶点G从顶点12.2编写一个程序，对如图2所示的无向带权图 G,采用Prim算法输出从顶点0出发的最 小生成树（边及对应的权）。2.3编写一个程序，对图2所示的无向带权图 G,采用Kruskal算法输出从顶点0出发的最小生成树（边及对应的权）。2.4编写一个程序，输出如图1所示的有向带权图 G中顶点0到其他各顶点的最短路径长度和最短路径。