2012级计算机科学与技术专业数据结构实验

20122012 级数据结构实验级数据结构实验 计算机科学与技术专业用 计算机科学与技术专业用 一 一 线性表的顺 链式存储结构的实现 线性表的顺 链式存储结构的实现 4 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 将一个数 x 插在第 i 个 元素前 x 和 i 在程序运行时输入 4 删除第 i 个元素 i 在程序运行时输入 并在 删除结束后输出删除元素的值 5 输出线性表中所有元素 2 用主函数调用你所编写的函数 并在使线性表有所变化的每一步输出线性表的内 容 以验证你编程序的正确性 备注 备注 stdlib hstdlib h 中有中有 srand srand 接受随机数的种子 接受随机数的种子 rand rand 产生产生 0 0 RAND MAXRAND MAX 的一的一 个整数的函数 用个整数的函数 用 rand rand 100 1 100 1 可以产生不大于可以产生不大于 100100 的正整数值 的正整数值 2 线性表的链式存储结构 要求要求同顺序存储结构 只是用链表作为存储结构完成以上操作 二 二 栈的顺序存储结构 链队列的实现 栈的顺序存储结构 链队列的实现 4 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 将一个数 x 插在栈顶 x 在程序运 行时输入 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 将一个数 x 插 到队尾 x 在程序运行时输入 4 删除队头元素 并在删除结束后输出删除元素的值 5 输出队列中所有元素 2 用主函数调用你所编写的函数 并在使队列有所变化的每一步输出队列中的从队 头到队尾的元素 以验证你编程序的正确性 三 银行业务模拟系统的设计与实现 三 银行业务模拟系统的设计与实现 6 6 学时 综合性实验 交实验报告 学时 综合性实验 交实验报告 1 问题描述 假设某银行有四个窗口对外接待客户 从早晨银行开门起不断有客户进入银行 由于 每个窗口在某个时刻只能接待一个客户 因此在客户人数众多时需在每个窗口前顺次排队 对于刚进入银行的客户 如果某个窗口的业务员正空闲 则可上前办理业务 反之 若四 个窗口均有客户所占 他便会排在人数最少的队伍后面 现在需要编制程序以模拟银行的 这种业务活动并计算一天中客户在银行逗留的平均时间 2 一个完整的系统应具有以下功能 初始化 OpenForDay 模拟银行开门时各数据结构的状态 事件驱动 EventDrived 对客户到达和离开事件做相应处理 下班处理 CloseForDay 模拟银行关门时的动作 统计客户平均逗留时间 实验目的 实验目的 1 通过实验掌握对离散事件模拟的认识 2 进一步理解队列的实现与应用 3 对链表的操作有更深层次的理解 该实验涉及到线性表的建立 插入 删除等操作 涉及到了队列的建立 插入 删除 涉及到了离散事件的应用思想 还涉及到了排序的概念 完成这个实验对线性表 队列及 C 语言编程等多方面的知识将是一个很好的利用 对离散事件也将有一个初步的认识 实验条件 实验条件 学院提供公共机房 1 台 学生微型计算机 实验步骤 实验步骤 实验分 3 次完成 第 1 次 完成程序的主框架设计 进行调试 验证其正确性 2 学时 第 2 次 详细设计 进行调试 验证其正确性 2 学时 第 3 次 进行整体调试 运行程序 对运行结果进行分析 完成实验报告 2 学时 四 四 稀疏矩阵的压缩存储 稀疏矩阵的压缩存储 4 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 4 学时 验证性实验 学时 验证性实验 要求 要求 利用书本上的二叉树的二叉链表存储结构的定义 typedef struct BiTNode 结点结构 TElemType data struct BiTNode lchild rchild 左右孩子指针 BiTNode BiTree 1 编写完成下列功能的函数 1 构建二叉树 2 中序遍历二叉树的 3 求 二叉树的深度 4 求二叉树中叶子结点个数 2 用主函数调用你所编写的函数 以验证你编程序的正确性 六 哈夫曼编六 哈夫曼编 译码系统的设计与实现 译码系统的设计与实现 6 6 学时 设计性实验 交实验报告 学时 设计性实验 交实验报告 1 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 6 学时 设计性实验 交实验报告 学时 设计性实验 交实验报告 1 问题描述 问题描述 创建一个至少有 15 个点的有向网表示的某个旅游景点的导游图 顶点代表景点 类型 为字符串 例如 泰山导游图 天地广场门 十八盘 冯玉祥墓 桃花峪门 中天门 南天门 玉皇顶 等 弧表示两个景点之间可以直达 弧上的权值表示两 个景点之间的路程 公里数 弧上还有到达方法的信息 有步行和索道两种 建立一个 游客咨询系统 完成 1 输入两个景点名 就可以得到从一个景点到达另一个景点的所有 简单路径 相应路径的路程公里数 行走的方法 每一段是步行 还是坐索道 2 输入 两个景点名 就可以得到其最短路径 即 路程最短的行进方法 如果两者无路径可通 就得出 两景点不可达的信息 2 一个完整的系统应具有以下功能 一个完整的系统应具有以下功能 1 创建图的存储结构 根据需要自行选择存储结构 2 输入两个景点名 就可以得到从一个景点到达另一个景点的所有简单路径 相应 路径的路程公里数 行走方法 每一段是步行 还是坐索道 3 输入两个景点名 就可以得到其最短路径 即 路程最短的行进方法 如果两者 无路径可通 就得出 两景点不可达的信息 实验目的 实验目的 1 通过实验掌握对图的存储 遍历 运算等各种操作 2 深入理解图的特征及应用 该实验涉及到图的存储 遍历等操作 也要用到线性链表 栈 数组等结构 培养学 生综合运用所学结构的能力 实验条件 实验条件 学院提供公共机房 1 台 学生微型计算机 实验步骤 实验步骤 实验分 3 次完成 第 1 次 完成程序的主框架设计 进行调试 验证其正确性 2 学时 第 2 次 详细设计 进行调试 验证其正确性 2 学时 第 3 次 进行整体调试 运行程序 对运行结果进行分析 完成实验报告 2 学时 八 排序算法性能实验分析 八 排序算法性能实验分析 2 2 学时 验证性实验 学时 验证性实验 要求 要求 利用书本上待排元素顺序存储结构定义 typedef int KeyType 关键字类型为整数类型 typedef struct KeyType key 关键字项 InfoType otherinfo 其它数据项 RedType 记录类型 typedef struct RedType r MAXSIZE 1 r 0 闲置 int length 顺序表长度 SqList 顺序表类型 1 编写完成下列功能的函数 1 创建一个包含 20 万个非负整数值的待排元素表 20 万个值由计算机随机产生 2 对原始数据进行直接插入排序 3 对原始数据 进行简单选择排序 4 对原始数据进行快速排序 2 用主函数调用你所编写的函数 统计各排序方法所用时间 分析各算法的优劣 备注 备注 sys timeb h 中有 ftime 函数 可计算运行时间 可精确到毫秒级 有关知识 struct timeb time t time unsigned s