数据结构实验报告
数据结构实验报告
课题名称：数据结构实验课学号：
姓名：
班号：
2015年12月
目录
一、实验目的，要求及任务 (4)
1.1目的
1.2要求
1.3任务
二、算法设计、程序运行结果 (4)
2.1 实验一 (4)
1题目
2算法设计
（1）设计思路
（2）程序关系图
（3）实验功能描述
3实验数据与结果
2.2实验二 (11)
1题目
2算法设计
（1）设计思路
（2）程序关系图
（3）实验功能描述
3 实验数据与结果
2.3实验三 (13)
1题目
2算法设计
（1）设计思路
（2）程序关系图
（3）实验功能描述
3 实验数据与结果
2.4实验四 (18)
1题目
2算法设计
（1）设计思路
（2）程序关系图
（3）实验功能描述
3 实验数据与结果
2.5实验五 (24)
1题目
2算法设计
（1）设计思路
（2）程序关系图
（3）实验功能描述
3 实验数据与结果
三、实验小结 (31)
一、实验目的、要求及任务
1.1目的
通过实验，使学生熟悉常用的数据结构，掌握其算法设计方法，重点掌握单链表、栈和队列、二叉树、图等几种数据结构的设计与应用。
1.2要求
进行数据结构应用有关的程序设计，使用VC++环境(或其他C编译环境)上机测试通过，并提交实验报告。
1.3任务
必做题（教材）：
P63 上机实验题2 实验题2.5、2.6、2.7
P96 上机实验题3 实验题3.3、3.5/3.8
P119 上机实验题4 实验题4.3
P152 上机实验题6 实验题6.2、6.4
P202 上机实验题7 实验题7.1、7.2、7.4
P152 上机实验题8 实验题8.1、8.2、8.5
选做题：
1、选部分作业上机验证；
2、教材上机实验2~8 中未布置的感兴趣的题；
3、补充设计题见后。
二、算法设计、程序与运行结果
2.1 实验1(exp2-5)
1、题目
编写一个程序algo2-5.cpp，实现循环双单链表的各种基本运算（假设循环双链表的元素类型为char），并在此基础上设计一个主程序完成如下功能：
（1）初始化循环双链表h
（2）一次采用尾插法插入a,b,c,d,e元素
（3）输出循环双链表h
（4）输出循环双链表h的长度
（5）判断循环双链表h是否为空
（6）输出循环双链表h的第三个元素
（7）输出元素a的位置
（8）在第4个元素位置上插入f元素
（9）输出循环双链表h
（10）删除L的第3个元素
（11）输出循环双链表h
（12）释放循环双链表h
2、算法设计
(1) 设计思路
首先我们应该写出所有的关于循环双链表的最基本的运算函数，完成个如下功能，比如初始化，释放，判断是否为空，计算链表元素个数，输出链表，取得第i个位置的值，插入和删除第i个元素等功能，然后在主函数中调用这些函数即可。
(2) 程序关系图
(3) 函数功能描述
InitList（）
用来初始化线性表
DestoryLIst（）
销毁线性表
ListEmpty（）
判断线性表是否为空，空返回真，不空返回假ListLength（）
求线性表的长度
DisplayList（）
输出线性表的元素GetElem（）
求线性表中第i个元素的值LocateElem（）
按照元素查找某元素在第几个位置ListInsert（）
在某一位置插入某个元素ListDelete（）
删除第i个位置的元素CreateLinklist（）
尾插法创建链表
3、实验数据与结果
2.2 实验2(exp3-3)
1、题目
编写一个程序algo3-3.cpp，实现唤醒队列的各种基本运算（假设队列中元素类型为char），并在此基础上设计一个程序exp3-3.cpp完成如下功能
（1）初始化队列q
（2）判断队列q是否为空
（3）以此进队元素a,b,c,d,e,f
（4）出队一个元素，输出该元素
（5）依次进队元素g,h,i,j,k,l
（6）输出出队序列
（7）释放队列
2、算法设计
(1) 设计思路
改程序涉及到的几个函数主要需要实现的功能是入队和进队，应该考虑对空的条件——队首指针等于队尾指针，队满的条件——（队尾指针+1）%Maxsize=队首指针
(2) 程序关系图
(3) 函数功能描述
InitQueue（）
初始化队列DestoryQueue（）
销毁队列
QueueEmpty（）
判断队列是否为空
enQueue（）
进队
deQueue（）
出队
3、实验数据与结果
2.3实验3(exp4-3)
1、题目
编写一个程序exp4-3.cpp，实现顺序串的各种匹配模式运算，并在此基础上完成如下功能：
(1)建立“abcabcdabcdeabcdefabcdefg”目标串和“abcdeabcdefab”模式串t；
(2)简单匹配算法求t在s中过的位置；
(3)由模式串t求出next的值和nextval的值
(4)采用KMP算法求t在s中的位置
(5)采用改进的KMP算法求t在s中的位置
2、算法设计
(1) 设计思路
本题的关键是KMP算法的思路以及改进后的KMP算法思路，一般的模式串匹配算法是按个扫描目标串和模式串，如果不匹配，则目标串跳转到下一个字母重新匹配，这在很大程度上做了很多重复匹配的工作，所以KMP算法就是在此基础上的改进
(2) 程序关系图
(3) 函数功能描述
StrAssign（）
将str[]中的字符串复制到s中DispStr（）
输出字符串
Index（）
简单的匹配算法
GetNext（）
根据模式串求出下一个字符的下标KMPIndex（）
KMP算法GetNextval（）
由t求出nextval的值KMPIndexpro（）
改进后的KMP算法
3、实验数据与结果
2.4实验4(exp6-4)
1、题目
假设n*n的稀疏矩阵A采用三元组表示，设计一个程序exp6-4.cpp实现如下功能（1）生成如下两个稀疏矩阵的三元组a，b
1 0 3 0 3 0 0 0
0 1 0 0 0 4 0 0
0 0 1 0 0 0 1 0
0 0 1 1 0 0 0 2
（2）输出a转置矩阵的三元组；
（3）输出a+b的三元组
（4）输出a*b的三元组
2、算法设计
(1) 设计思路
用一个结构体创建三元组，加法只需要将行号和列号相同的数相加即可，如果连个数都是零，就可以不必计算，乘法的话可以根据矩阵乘法的规则，用循环求行和列的和，得出结果。转置矩阵的算法类似，先理解转置矩阵的意思，然后交换行号和列号即可。
(2) 程序关系图
(3) 函数功能描述
CreateMat（）
创建稀疏矩阵的三元组表示法DispMat（）
输出矩阵
TransMat（）