数据结构基础实验

《数据结构基础实验》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一、线性表——上机实验题1.实验目的：（1）掌握顺序表的基本操作的实现方法。（2）应用顺序表的基本操作算法实现集合A=AUB算法。（3）掌握链式线性表的基本操作的实现方法。（4）利用链表的基本操作算法实现集合A=A∩B算法。2.实验内容：2.1编写一个程序algo1-1.cpp，实现顺序表的各种基本运算，并在此基础上设计一个主函数完成如下功能：（1）初始化顺序表L；（2）依次插入a，b，c，d，e元素；（3）输出顺序表L；（4）输出顺序表L长度；（5）判断顺序表L是否为空；（6）输出顺序表L的第3个元素；（7）输出元素‘a’的位置；（8）在第4

2、个元素位置上插入‘f’元素；（9）输出顺序表L；（10）删除L的第3个元素；（11）输出顺序表L；（12）释放顺序表L。2.2编写一个程序algo1-2.cpp，可利用以上基本操作算法，实现A=AUB算法。2.3编写一个程序algo1-3.cpp，实现单链表的各种基本运算，并在此基础上设计一个主程序exp1-2.cpp完成如下功能：（1）初始化单链表H；（2）依次插入a，b，c，d，e元素；（3）输出单链表H；（4）输出单链表H长度；（5）判断单链表H是否为空；（6）输出单链表H的第3个元素；（7）输出元素‘a’的位置；（8）在第4个元素位置上

3、插入‘f’元素；（9）输出单链表H；（10）删除H的第3个元素；（11）输出单链表H；（12）释放单链表H。2.4编写一个程序algo1-4.cpp，可利用以上基本操作算法，实现递增有序的两个单链表A、B的交集运算A=A∩B。二、栈和队列——上机实验题1.实验目的：（1）掌握顺序栈和链栈的各种基本运算（2）掌握循环队列的各种基本运算（3）利用栈先进后出的特点，解决一些实际问题。2.实验内容：2.1编写一个程序algo2-1.cpp，实现顺序栈的各种基本运算，并在此基础上设计一个主函数完成如下功能：（1）初始化顺序栈S；（2）判断栈S是否非空；（

4、3）依次进栈元素a，b，c，d，e；（4）判断栈S是否非空；（5）输出栈的长度；（6）输出从栈顶到栈底元素；（7）元素出栈，输出出栈序列；（8）判断栈S是否非空；（9）释放栈。2.2编写一个程序algo2-2.cpp，可用以上基本算法，实现：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数；2.3（选做）编写一个程序algo2-3.app，实现：将中缀表示的算术表达式转换成后缀表示，并计算表达式的值。（为了方便，假定变量名为单个数字（0~9），运算符只有+、-、*、/）。2.4编写一个程序algo2-4.cpp，实现链栈的各种基本运

5、算，并在此基础上设计一个主函数完成如下功能：（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）

6、输出队列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个字符位置插入串s1而产生串s2；（5）输出串s2；（6）删除串s第2个字符开始的5个字符而产生串s2

7、；（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中

8、的位置。四、数组——上机实验题1.实验目的：（1）掌握数组的定义、赋值和输入输出方法等基本操作（2）掌握稀疏矩阵的生成方法及转置方法2.实验内容：2.