数据结构基础实验.docVIP

一、线性表——上机实验题 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个元素位置上插入‘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个元素位置上插入‘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是否非空； （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，实现链栈的各种基本运算，并在此基础上设计一个主函数完成如下功能： （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个字符位置插入串s1而产生串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求