发布时间 : 星期一 文章2010级计算机科学与技术专业数据结构实验更新完毕开始阅读3755df094a7302768e9939a3
2010级数据结构实验 （计算机科学与技术专业用）
一、 线性表的顺、链式存储结构的实现（4学时，验证性实验） 1．线性表的顺序存储结构
要求：利用书本上的线性表的顺序存储结构定义， #define LIST_INIT_SIZE 100 // 线性表存储空间的初 //始分配量
#define LISTINCREMENT 10 // 线性表存储空间的分配增量 typedef struct{
ElemType *elem; // 存储空间基址 int length; // 当前长度
int listsize; // 当前分配的存储容量(以sizeof(ElemType)为单位) } SqList;
1）编写完成下列功能的函数：（1）初始化一个线性表；（2）创建一个包含15个不大于100的正整数值的线性表（15个值由计算机随机产生）；（3）将一个数插在第i个元素前（i在程序运行时输入）；（4）删除第i个元素（i在程序运行时输入）；（5）输出线性表中所有元素。
2）用主函数调用你所编写的函数，并在使线性表有所变化的每一步输出线性表的内容，以验证你编程序的正确性。
备注：stdlib.h中有srand( )接受随机数的种子； rand( )产生0～RAND_MAX的一个整数的函数。用rand( )0+1可以产生不大于100的正整数值。 2．线性表的链式存储结构
要求同顺序存储结构，只是用链表作为存储结构完成以上操作。 二、 栈的顺序存储结构、链队列的实现（4学时，验证性实验） 1． 栈的顺序存储结构
要求：利用书本上的栈的顺序存储结构定义，
#define STACK_INIT_SIZE 100; // 存储空间初始分配量 #define STACKINCREMENT 10; // 存储空间分配增量 typedef struct {
SElemType *base; // base的初值为NULL SElemType *top; // 栈顶指针
int stacksize; // 当前已分配的存储空间，以元素为单位 } SqStack;
1）编写完成下列功能的函数：（1）初始化一个栈；（2）创建一个包含5个不大于100的正整数值的栈（5个值由计算机随机产生）；（3）将一个数插在栈顶；（4）将栈顶元素弹出栈顶；（5）求栈中元素的个数；（6）输出从栈顶到栈底的所有元素。
2）用主函数调用你所编写的函数，并在使栈有所变化的每一步输出栈的所有元素，以验证你编程序的正确性。 2．链队列的实现
要求：利用书本上的链队列有关类型定义， typedef struct QNode { // 结点类型 QElemType data; struct QNode *next; } QNode, *QueuePtr;
typedef struct { // 链队列类型 QueuePtr front; // 队头指针 QueuePtr rear; // 队尾指针 } LinkQueue;
1）编写完成下列功能的函数：（1）初始化一个带头结点的空队列；（2）创建一个包含5个不大于100的正整数值的队列（5个值由计算机随机产生）；（3）将一个数插队尾；（4）删除队头元素；（5）输出队列中所有元素。
2）用主函数调用你所编写的函数，并在使队列有所变化的每一步输出队列中的从队头到队尾的元素，以验证你编程序的正确性。
三、银行业务模拟系统的设计与实现（6学时，综合性实验，交实验报告） 1．问题描述
假设某银行有四个窗口对外接待客户，从早晨银行开门起不断有客户进入银行。由于每个窗口在某个时刻只能接待一个客户，因此在客户人数众多时需在每个窗口前顺次排队，对于刚进入银行的客户，如果某个窗口的业务员正空闲，则可上前办理业务，反之，若四个窗口均有客户所占，他便会排在人数最少的队伍后面。现在需要编制程序以模拟银行的这种业务活动并计算一天中客户在银行逗留的平均时间。 2．一个完整的系统应具有以下功能：
初始化（OpenForDay），模拟银行开门时各数据结构的状态。 事件驱动（EventDrived）, 对客户到达和离开事件做相应处理。
下班处理（CloseForDay）, 模拟银行关门时的动作，统计客户平均逗留时间 。 实验目的：
1）通过实验掌握对离散事件模拟的认识； 2）进一步理解队列的实现与应用；
3）对链表的操作有更深层次的理解；
该实验涉及到线性表的建立、插入、删除等操作，涉及到了队列的建立、插入、删除，涉及到了离散事件的应用思想，还涉及到了排序的概念。完成这个实验对线性表、队列及C语言编程等多方面的知识将是一个很好的利用，对离散事件也将有一个初步的认识。
实验条件：学院提供公共机房，1台/学生微型计算机。 实验步骤：实验分3次完成
第1次：完成程序的主框架设计，进行调试，验证其正确性；（2学时） 第2次：详细设计，进行调试，验证其正确性；（2学时）
第3次：进行整体调试，运行程序，对运行结果进行分析，完成实验报告。（2学时） 四、稀疏矩阵的压缩存储（4学时，验证性实验）
要求：利用书本上的稀疏矩阵的三元组顺序存储结构定义， #define MAXSIZE 12500 // 非零元素最大个数 typedef struct {
int i, j; //该非零元的行下标和列下标 ElemType e; // 该非零元的值 } Triple; // 三元组类型 typedef struct {
Triple data[MAXSIZE + 1];//非零元三元组表中0号单元未用 int mu, nu, tu; //行、列及非零元个数 } TSMatrix; // 稀疏矩阵类型
1）编写完成下列功能的函数：（1）构建你所给的6行7列稀疏矩阵的压缩存储；（2）求稀疏矩阵压缩存储的转置矩阵（快速算法）；（3）以行、列形式输出矩阵中的元素。
2）用主函数调用你所编写的函数，并在每一步后以行、列形式输出矩阵中的元素，以验证你编程序的正确性。
五、二叉树的二叉链表存储结构的建立及操作的实现（4学时，验证性实验）
要求：利用书本上的二叉树的二叉链表存储结构的定义， typedef struct BiTNode { // 结点结构 TElemType data;
struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree;
1）编写完成下列功能的函数：（1）构建二叉树；（2）中序遍历二叉树的；（3）就二叉树的深度；（4）求二叉树中叶子结点个数。
2）用主函数调用你所编写的函数，以验证你编程序的正确性。 六、哈夫曼编/译码系统的设计与实现（6学时，设计性实验，交实验报告） 1． 问题描述：
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编/译码系统。 2．一个完整的系统应具有以下功能：
1）初始化（Initialzation）。从数据文件DataFile.data中读入字符及每个字符的权值，建立哈夫曼树HuffTree；
2）编码（EnCoding）。用已建好的哈夫曼树，对文件ToBeTran.data中的文本进行编码形成报文，将报文写在文件Code.txt中；
3）译码（Decoding）。利用已建好的哈夫曼树，对文件CodeFile.data中的代码进行解码形成原文，结果存入文件Textfile.txt中；
4）输出（Output）: 输出DataFile.data中出现的字符以及各字符出现的频度（或概率）；输出ToBeTran.data及其报文Code.txt；输出CodeFile.data及其原文Textfile.txt；
要求：所设计的系统应能在程序执行的过程中，根据实际情况（不同的输入）建立DataFile.data、ToBeTran.data和CodeFile.data三个文件，以保证系统的通用性。 实验目的：
理解哈夫曼树的特征及其应用；在对哈夫曼树进行理解的基础上，构造哈夫曼树，并用构造的哈夫曼树进行编码和译码；通过该实验，使学生对数据结构的应用有更深层次的理解。 实验条件：学院提供公共机房，1台/学生微型计算机。 实验步骤：实验分3次完成
第1次：完成程序的主框架设计，进行调试，验证其正确性；（2学时） 第2次：详细设计，进行调试，验证其正确性；（2学时）
第3次：进行整体调试，运行程序，对运行结果进行分析，完成实验报告。（2学时） 七、旅游景点咨询系统（6学时，设计性实验，交实验报告） 1．问题描述
创建一个至少有15个点的有向网表示的某个旅游景点的导游图。顶点代表景点,类型为字符串（例如，泰山导游图：“天地广场门”，“十八盘”，“冯玉祥墓”，“桃花峪门”，“中天门”，“南天门”，“玉皇顶”等），弧表示两个景点之间可以直达，弧上的权值表示两个景点之间的路程（公里数），弧上还有到达方法的信息（有步行和索道两种）。建立一个游客咨询系统。完成：1）输入两个景点名，就可以得到从一个景点到达另一个景点的所有简单路径、相应路径的路程公里数、行走的方法（每一段是步行，还是坐索道）；2）输入两个景点名，就可以得到其最短路径，即：路程最短的行进方法；如果两者无路径可通，就得出“两景点不可达的信息”。
2．一个完整的系统应具有以下功能：
1）创建图的存储结构。（根据需要自行选择存储结构）
2）输入两个景点名，就可以得到从一个景点到达另一个景点的所有简单路径、相应路径的路程公里数、行走方法（每一段是步行，还是坐索道）。
3）输入两个景点名，就可以得到其最短路径，即：路程最短的行进方法；如果两者无