数据结构实验教学计划10学时.pdf

数据结构 实验教学计划 （ 10 学时） 计算机软件教学研究部计算机专业实验中心联合制定 数据结构实验教学计划（ 10 学时） 前言 数据结构是计算机程序设计的重要理论基础， 它不仅是计算机学科的核心课程，而且已成为其他理工专业的热门选修课数据结构是计算机科学中一门综合性的专业基础课，是介于数学、计算机硬件和计算机软件三者之间的一门核心课程该课程主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法进行分析和评价该课程不仅是一般程序设计的基础，而且是设计和实现编译原理、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础因此，数据结构课程一直是计算机科学与技术专业的一门理论性和实践性并重的核心课程 课程的目标是使学生掌握数据的基本的逻辑结构和存储结构、 一些典型的数据结构算法及程序设计方法和技巧，要求学会分析数据对象特征，掌握数据组织方法和计算机的表示方法，为数据选择适当的逻辑结构、存储结构以及相应的处理算法，要求具备算法分析的基本技术和能力，并培养良好的程序设计风格，掌握开发复杂、高效程序的技能 因此， 本实验教学计划是为本科学生 学习数据结构实验而设计的(分成两大部分， 正式实验和补充实验 构成， 实验指导教师可以根 据学生需要进行适当调整 )， 并 且根据本实验教学计划， 任课教师可 以根据学生实际情况制定具体的实验指导文档。

I 数据结构实验教学计划（ 10 学时） 目录 补充实验一： C语言结构体与指针 .................................................................... - 1 - 补充实验二： 线性表的实例及分析 .................................................................. - 1 - 补充实验三： 线性顺序表的实现及操作 .......................................................... - 2 - 补充实验四： 串的匹配与替换 .......................................................................... - 3 - 补充实验五： 哈夫曼编码的程序设计 .............................................................. - 4 - 补充实验六： 排序算法的实现及比较 .............................................................. - 5 - 实验一： 线性链表的实现及操作 ..................................................................... - 2 - 实验二： 栈和队列的应用 ................................................................................. - 3 - 实验三： 二叉树的实现及遍历 ......................................................................... - 4 - 实验四： 图的实现及遍历 ................................................................................. - 4 - 实验五： 查找算法的实现及比较 ..................................................................... - 5 - II 数据结构实验教学计划（ 10 学时） 详细实验教学计划 补充实验一： C 语言结构体与指针 1、 实验目的： 巩固复习前期所学 C 语言的函数参数传递、指针和结构体等知识点，加强学习数据结构语言基础。

2、 实验内容： 1) 学生信息的显示，具体要求如下： z 定义一个结构体描述学生信息 (学号， 姓名， 性别， 年龄， 住址 )； z 设计一个函数，用于显示单个学生信息，函数的参数为前面定义的结构体类型； z 设计一个主函数，在主函数中输入学生的信息，并调用前面定义的函数进行显示（学生人数不少于 5 人） 2) 输入若干个整数作为数组元素值，然后按输入时顺序的就地逆置排序，最后打印出逆置后的元素值 要求用指针和动态内存分配方法实现例如 输入： 10 2 30 4 5 ，逆置后显示为：5 4 30 2 10 3、 思考题： 分析结果是否正确，如果不正确是什么原因  补充实验二： 线性表的实例及分析 1、 实验目的： 1) 了解和掌握线性表的逻辑结构和链式存储结构； 2) 掌握用 C 语言上机调试线性表的基本方法； 3) 掌握线性表的基本操作： 2、 实验内容： 1) 认真阅读和掌握本实验的实例程序，并上机验证本程序 2) 保存和打印出程序的运行结果，并结合程序进行结构分析 3) 按照你对线性表的操作需要， 重新改写主程序并运行， 打印出文件- 1 - 数据结构实验教学计划（ 10 学时） 清单和运行结果。

3、 思考题： 尝试对该程序使用另外一种存储结构来改写 补充实验三： 线性顺序表的实现及操作 1、 实验目的： 1) 掌握建立线性顺序表的基本方法 2) 理解和掌握线性顺序表元素查找算法 3) 掌握线性顺序表的插入、删除算法的思想和实现 2、 实验内容： 1) 建立一个线性顺序表，要求从键盘输入 10 个整数，并将该线性顺序表的元素从屏幕显示出来； 2) 编写查找函数， 在上面的线性顺序表中查找其中一个元素， 如果找到，返回该元素性顺序表中的 位置和该元素的值，否则提示无此元素要求被查找元素从键盘输入 3) 编写插入和删除函数， 由用户输入待插入元素及插入位置， 将完成插入后的线性顺序表输出；由用户 输入删除第几个元素，将完成删除后的线性顺序表输出 3、 思考题： 分析线性顺序表结构下插入和删除算法的时间复杂度 实验一： 线性链表的实现及操作 1、 实验目的： 1) 深入理解线性链表的逻辑结构和链式存储结构； 2) 掌握线性链表的基本操作及应用： 3) 培养学生灵活使用结构解决实际问题的能力 2、 实验内容： 1) 设计一个 100 位以内的长整数加减运算的程序。

要求如下： z 输入输出要求：每四位一组，组间用逗号分隔； z 加和减分别用不同的程序实现 z 程序应考虑输入数据的符号 - 2 - 数据结构实验教学计划（ 10 学时） 2) 用循环链表实现约瑟夫环问题 3、 思考题： 尝试按照指数降序排列建立并输出多项式；能 够完成两个多项式的相加、相减，并将结果输出 实验二： 栈和队列的应用 1、 实验目的： 掌握栈与队列的基本结构和操作方法，培养学 生灵活使用结构解决实际问题的能力 2、 实验内容： 1) 利用栈深度优先进行迷宫求解 z 用数组表示迷宫 z 建立栈，利用栈实现深度优先搜索 2) 利用队列宽度优先进行迷宫求解 z 用数组表示迷宫 z 建立队列，利用队列实现宽度优先搜索 3、 思考题： 1) 考虑用栈结构实现数制转换问题和字符匹配问题； 2) 考虑用队列结构实现杨辉三角输出问题和回文问题； 3) 利用栈和队列模拟停车场管理 补充实验四： 串的匹配与替换 1、 实验目的： 1) 掌握串存储结构； 2) 掌握串的匹配算法，并能进行相关应用 2、 实验内容： 设串采用静态数组存储结构， 编写函数实现串的替换 Replace(S， start， T，V)，即要求在主串 S 中从位置 start 开始查找是否存在子串 T。

若存在，则用子串 V 去替换子串 T， 且函数返回 1；若 主 串 S 中不存在子串 T， 则函数返回0要求设计主函数进行测试 3、 思考题： - 3 - 数据结构实验教学计划（ 10 学时） 使用串的块链存储结构，改写上述程序 实验三： 二叉树的实现及遍历 1、 实验目的： 1) 掌握二叉树的定义、 结构特征， 以及各种存储结构的特点及使用范围 2) 掌握用指针类型描述、访问和处理二叉树的运算 3) 掌握二叉树的建立方法 4) 掌握二叉树遍历的基本方法（前序、中序、后序） 2、 实验内容： 1) 采用二叉树链表作为存储结构， 完成二叉树的建立， 先序、 中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作 2) 输出树的深度，最大元，最小元 3、 思考题： 画出所设计的二叉树，以后序遍历算法为例，画出执行踪迹示意图 补充实验五： 哈夫曼编码的程序设计 1、 实验目的： 1) 掌握哈夫曼树的建立过程； 2) 熟悉哈夫曼编码的实现 2、 实验内容： 1) 设有字符集 {A， B， C， D}， 各字符在电文中出现的次数集为 {1， 3，4， 7}； 2) 要求编程实现哈夫曼树的构造，并在此基础上编程实现哈夫曼编码。

3、 思考题： 计算哈夫曼树的构造时间复杂度 实验四： 图的实现及遍历 1、 实验目的： 1) 掌握有向图和无向图的概念； - 4 - 数据结构实验教学计划（ 10 学时） 2) 掌握邻接矩阵和邻接链表建立图的存储结构； 3) 掌握 DFS 及 BFS 对图的遍历操作和过程； 4) 了解图结构在人工智能、工程等领域的广泛应用 2、 实验内容： 1) 采用邻接矩阵作为图的存储结构，完成有向图和无向图的 DFS 和BFS 操作； 2) 采用邻接链表作为图的存储结构，完成有向图和无向图的 DFS 和BFS 操作 3、 思考题： 1) 画出 DFS 方法和 BFS 方法遍历图 G 的示意图 2) 画出你所设计的图，写出两种方法的遍历序列 实验五： 查找算法的实现及比较 1、 实验目的： 1) 掌握线性结构 （顺序查找、 折半查找） 上查找的基本思想和算法实现，了解怎样对各种查找方法进行时间性能（平均查找长度）分析 2) 掌握树形结构 （二叉排序树） 实现查找的基本思想和算法实现， 了解怎样对各种查找方法进行时间性能（平均查找长度）分析 2、 实验内容： 1) 有序表的二分查找 z 建立有序表，然后进行二分查找 2) 二叉排序树的查找 z 建立二叉排序树，然后查找 3、 思考题： 比较顺序查找、折半查找和二叉排序树查找的性能。

补充实验六： 排序算法的实现及比较 1、 实验目的： 1) 理解各类排序算法的基本思想、排序过程、实现过程； 2) 理解不同排序算法的时间复杂度及适用环境； 3) 了解算法性能测试的基本方法 - 5 - 数据结构实验教学计划（ 10 学时） 2、 实验内容： 1) 实现直接插入排序、冒泡、直接选择、快速排序算法 z 数据的存储使用数组，数据个数和数据由键盘输入 z 设计并实现一个用户选择菜单 2) 设计并实现一个利用随机数来测试各类排序算法的程序 从所学的排序算法中任选四种排序算法进行测试，记录运行时间； 3、 思考题： 1) 请写出输入数据及程序执行的结果 2) 请比较各种排序算法的运行速度 - 6 - 。