[精品]数据结构基础实验

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

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

2、f'元素；（9）输出顺序表L；（10）删除L的第3个元素；（11）输出顺序表L；（12）释放顺序表Lo2.2（选做）编写一个程序algol-2.cpp,可利用以上基本操作算法，实现A=AUB算法。2.3编写一个程序algol-3.卬p,实现单链表的各种基木运算，并在此基础上设计一个主程序expl-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

3、）输出单链表H；（10）删除H的第3个元素；（11）输出单链表H；（12）释放单链表H。2.4（选做）编写一个程序algol-4.卬p,可利用以上基木操作算法，实现递增有序的两个单链表A、B的交集运算A=AnB31•实验目的：（1）学握顺序栈和链栈的各种基木运算（2）掌握循环队列的各种基木运算（3）利用栈先进后岀的特点，解决一些实际问题。2.实验内容：2.1编写一个程序algo2-l.卬p,实现顺序栈的各种基木运算，并在此基础上设计一个主函数完成如下功能：（1）初始化顺序栈S；（2）判断栈S是否非空；（3）依次进栈元素a,b,c,d,e；（4）判断栈S是

4、否非空；（5）输出栈的长度;（6）输出从栈顶到栈底元素；（7）元素出栈，输出岀栈序列；（8）判断栈S是否非空；（9）释放栈。2.2（选做）编写一个程序algo2-2.卬p,町用以上基本算法，实现：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数；2.3（选做）编写一个程序algo2-3.app,实现：将屮缀表示的算术表达式转换成后缀表示，并计算表达式的值。（为了方便，假定变量名为单个数字（0~9）,运算符只有+、・、*、/）。2.4编写一个程序algo2-4.卬p,实现链栈的各种苹本运算，并在此棊础上设计一个主函数完成如下功能：（1）初始化链

5、栈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）!1!队一个元素，输出该元素；（5）输出队列Q的元素个数；（6）依次进队列元素d,e,f；（7）输出队列Q的元素个数；（8）元素岀队，输岀出队序列；（9）释放队

6、列。2.6（选做）利用递归实现汉诺塔算法。三、串——上机实验题1•实验目的：（1）学握顺序串的各种基本运算（2）掌握模式匹配算法2.实验内容：2.1编写一个程序algo3-l.卬p,实现顺序串的各种基木运算，并在此基础上设计一个主函数完成如下功能：（1）建立串s=wabcdefghefghijklmnw和串sl="xyz〃；（2）输出串s：（3）输出串s的长度；（4）在串s的第9个字符位置插入串si而产生串S2；（5）输出串S2；（6）删除冷s第2个字符开始的5个字符而产生冷s2；（7）输出串S2；（8）将串s第2个字符开始的5个字符替换成串si而产生串

7、s2；（9）输岀和串s2.（10）提取串s的第2个字符开始的10个字符而产生串S3；（11）输出串S3；（12）将串si和串s2连接起來而产生串s4；（13）输出串s4o2.2编写一个程序，实现顺序串的各种模式匹配运算，并在此基础上完成如下功能：（1）建立"abcabcdabcdeabcdefabcdefg"目标串s和"abcdeabcdefab"模式串t；（2）釆用简单匹配算法求t在s中的位置；（3）由模式串t求出next值，并打印出來。（4）采用KMP算法求t在s中的位置。1•实验目的：（1）学握数组的定义、赋值和输入输出方法等基木操作（2）掌握稀疏

8、矩阵的生成方法及转置方法2.实验内容：2.1已知Fibonacci数列为：0,1