10计科数据结构实验大纲.docx资源-CSDN文库

版权申诉

36 浏览量 2022-07-12 20:15:22 上传评论收藏 356KB DOCX 举报

资源推荐

资源详情

资源评论

黄石理工学院计算机学院计算机科学与技术专业教学大纲

《数据结构》实验教学大纲

课程编号：404511043

课程类别：专业基础必修课

实验学时：实验 16 学时

学

分：5

适用专业：计算机科学与技术

一、实验教学目的和任务

数据结构是信息与计算科学专业中一门重要的专业基础课程。当用计算机来解决实际问

题时，就要涉及到数据的表示及数据的处理，而数据表示及数据处理正是数据结构课程的主

要研究对象，通过这两方面内容的学习，为后续课程，特别是软件方面的课程打下了厚实的

知识基础，同时也提供了必要的技能训练。因此，数据结构课程在计算机应用专业中具有举

足轻重的作用。

本课程的任务是：通过实践，学生对常用数据结构的基本概念及其不同的实现方法的理

论得到进一步的掌握，并对在不同存储结构上实现不同的运算方式和技巧有所体会。

二、实验教学基本要求

本课程是一门实践性很强的专业课，只有了解这门课程的特点和基本要求，学习时才能

做到有的放矢，举一反三，本课程特点主要有以下几个方面：

(1) 内容丰富，理论性强。本课程为以后学习专业基础课和专业课(如：计算机操作系统、

数据库原理等)打下良好的基础。

(2) 注重理论联系实际，加强实验环节的训练。只有通过实验，才能透彻理解基本原理。

三、实验教学内容

实验分验证性实验和设计性实验两部分，课外20 学时用来完成验证性实验项目，以下

的实验一至实验五为验证性实验，验证性实验的具体内容见《数据结构验证性实验指导书》，

每个验证性实验项目完成后要提交一份电子实验报告，每份验证性实验报告至少包括实验项

目中的三个实验任务，电子验证性实验报告模板见附录1。

实验 16 学时用来完成设计性实验项目，全班学生分成小组，每组3-4 人，设计性实验

项目的源程序全部由学生自己设计，同组的同学可以分工协助，每人至少完成设计性实验项

目中的一个子任务，必须提前准备好设计性实验项目的代码，实验课开始时马上提交自己的

源代码，实验课时老师随即抽取一个小组，首先，由小组学生讲解自己编写的代码并演示执

行，接着，由老师和同学根据演示同学的代码提问，由演示的同学回答，如果当堂不能解决，

可下去准备，在下次实验课时再来解答。课后，被抽中的小组学生在实验课后及时上交一份

设计性实验报告，记录自己演示代码及回答提问时的情况及代码改进的情况，既提交电子稿

又要交打印稿，设计性实验报告模板见附录 2。

验证性实验项目

实验一线性表的顺序存储实验

1、实验目的及要求：

(1) 了解线性表的顺序存储方法，掌握用在 VC 环境下上机调试单链表的基本方法。

(2) 掌握顺序表的插入、删除、查找、求表长以及有序顺序表的合并算法的实现

2、实验内容及学时分配：（4 学时）

(1) 顺序表基本操作的实现

黄石理工学院计算机学院计算机科学与技术专业教学大纲

(2) 有序顺序表的合并，已知顺序表 la 和 lb 中的数据元素按非递减有序排列，将 la

和 lb 表中的数据元素，合并成为一个新的非递减有序顺序表 lc，并且不破坏 la

和 lb 表

实验二单链表实验

1、实验目的及要求：

(1) 掌握用在 VC 环境下上机调试单链表的基本方法

(2) 掌握单链表、循环链表的插入、删除、查找、求表长以及有序单链表的合并算法的

实现

2、实验内容及学时分配：（4 学时）

(1) 单链表基本操作的实现

(2) 有序单链表的合并，已知单链表 la 和 lb 中的数据元素按非递减有序排列，将 la

和 lb中的数据元素,合并为一个新的单链表lc,lc中的数据元素仍按非递减有序排

列，要求不破坏 la 表和 lb 表的结构。

(3) 约瑟夫环问题，设有N 个人围坐一圈，现从某个人开始报数，数到M 的人出列，接

着从出列的下一个人开始重新报数，数到 M 的人以出列，如此下去，直到所有人都

出列为此。试设计确定他们的出列次序序列的程序。选择单向循环链表作为存储结

构模拟整个过程，并依次输出列的各人的编号。

(4) 编程实现两个循环单链表的合并。

实验三栈、队列的实现及应用

1、实验目的及要求：

(1) 掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。

(2) 掌握栈和队列的特点，即先进后出与先进先出的原则。

(3) 掌握栈和队列的基本操作实现方法。

2、实验内容及学时分配：（4 学时）

(1) 实现栈的顺序存储

(2) 利用栈实现数制转换

(3) 实现循环队列的顺序存储

(4) 顺序串的基本操作

实验四二叉树的基本操作及应用

1、实验目的及要求：

(1) 进一步掌握指针变量、动态变量的含义。

(2) 掌握二叉树的结构特性，以及各种存储结构的特点和适用范围。

(3) 掌握用指针类型描述、访问和处理二叉树的运算。

2、实验内容及学时分配：（4 学时）

(1) 以二叉链表作存储结构，试编写前序、中序、后序及层次顺序遍历二叉树的算法。

(2) 以二叉链表作存储结构，试编写计算二叉树深度、所有结点总数、叶子结点数、双

孩子结点个数、单孩子结点个数的算法

(3) 编写按中序顺序建立一棵二叉树的非递归算法的C 语言源程序，并且用非递归方式

遍历二叉树（先序、中序或后序），输出遍历序列。

(4) 赫夫曼树与赫夫曼编码，利用 Huffman 编码进行通信可以大大提高信道利用率，缩

短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传

数据预先编码，在接受端将传来的数据编码进行译码（复原）。对于有些信道，每

端都需要一个完整的编／译码系统。试为这样的信息收发站编写一个 Huffman 的编

／译码系统。给定一组权值{7，9，5，6，10，1，13，15，4，8}，构造一棵赫夫

曼树，并计算带权路径长度 WPL。

实验五查找与排序

黄石理工学院计算机学院计算机科学与技术专业教学大纲

1、实验目的及要求：

(1) 掌握查找的不同方法，并能用高级语言实现查找算法。

(2) 熟练掌握顺序表的查找方法和有序顺序表的折半查找算法以及静态查找树的构造

方法和查找算法。

(3) 掌握二叉排序树的生成、插入、删除、输出运算。

(4) 掌握常用的排序方法，并能用高级语言实现排序算法。

(5) 深刻理解排序的定义和各种排序方法的特点，并能加以灵活运用。

(6) 了解各种方法的排序过程及依据的原则，并掌握各种排序方法的时间复杂度的分析

方法。

2、实验内容及学时分配：（4 学时）

(5) 作为输入给定的是已分类的数列：a1,a2,a3,„„„, an，以及随后的"问题"序列：

b1, b2, b3, „„, bn。请编写一个程序，首先顺序存储数列 a1,a2,a3, „„„,

an，然后用折半查找法对每个问题 bi找出使 aj等于 bi的一切 j，当没有这样的 j

及有多个这样的 j 时，程序也应能够正常工作。

(6) 给定一个用无序链表表示的集合，需要在其上执行operator+( ), operator*( ),

operator- ( ), Contains(x), AddMember (x), DelMember(x), Min( )，试给出

所有这些函数的实现。

(7) 用序列（46，88，45，39，70，58，101，10，66，34）建立一个排序二叉树，编

程实现二叉排序树的建立、查找、中序遍历算法，计算和输出每次查找所需和关键

字进行比较的次数，以及在等概率情况下查找成功时的平均查找长度。

(8) 设计一个程序读入一个字符串，统计该字符串中出现的字符及其次数，然后以表的

形式输出结果。要求用一个二叉树来保存处理结果，字符串中的每个不同的字符用

树中不同的结点描述，每个结点包含四个域，格式为：字符、该字符的出现次数、

指向 ASCII码小于该字符的左子树指针、指向 ASCII码大于该字符的右子树指针。

因此程序的功能是依次从输入字符串中取出一个字符，把它们插入到树中（新出现

字符）或修改原树中相应结点的“出现次数域”（已出现字符）。

(9) 请编写一个算法，在基于单链表表示的待排序排序码序列上进行简单选择排序。

(10)采用静态单链表作为存储表示。用Vector[0]作为表头结点，各待排序数据对象从

Vector[1]开始存放。算法的思想是每趟在原始链表中摘下排序码最大的结点(几个

排序码相等时为最前面的结点)，把它插入到结果链表的最前端。由于在原始链表

中摘下的排序码越来越小，在结果链表前端插入的排序码也越来越小，最后形成的

结果链表中的结点将按排序码非递减的顺序有序链接。

设计性实验项目

1. 线性表的合并：已知线性表 La和 Lb的元素按值非递减排列。归并 La和 Lb得到新的线

性表 Lc，Lc的元素也按值非递减排列。分别采用顺序存储结构和链式结构来实现。

2. 线性表的逆置：设有一个线性表（e , e , „, e , e ），请编写一个函数将这个线性

n-2

表原地逆置，即将线性表内容置换为（e , e , „, e , e ）。线性表中的数据可以为整数、

n-1

n-2

字符或字符串，试分别采用顺序存储结构和链式结构来实现。

3. 约瑟夫环的实现：设有 n 个人围坐一圈，用整数序列 1, 2, 3,„„, n 表示顺序围坐在

圆桌周围的人，现从某个位置 s 上的人开始报数，数到 m 的人出列，接着从出列的下一个

人又从 1 开始重新报数，数到m 的人出列，如此下去，直到所有人都出列为此。试设计确定

他们的出列次序序列的程序。如 n=8, m=4 ,s=1时，设每个人的编号依次为 1，2，3，„

开始报数，则得到的出列次序为 4，8，5，2，1，3，7，6。检查程序的正确性和健壮性。

(1)采用数组表示作为求解过程中使用的数据结构。

(2) 采用单向循环链表作为存储结构模拟整个过程，循环链表可不设头节点,必须注意空表

和非空表的界限。

剩余12页未读，继续阅读

评论收藏

内容反馈

版权申诉

คิดถึง643

粉丝: 3879
资源: 1万+

10计科数据结构实验大纲.docx

数据结构算法实验指导书(计科1021).docx

计科数据结构实验\数据结构答案.rar

数据库原理实验指导书(06计科)(金山)(10学时)

2018计算机网络实验题目D-计科一（周二9-10）1

数据结构 实验课程教学大纲.docx

《算法与数据结构》实验教学大纲.docx

数据结构实验教学大纲.docx

数据结构实验大纲.docx

2012级计科专业《算法与数据结构》课程设计题 (2).docx

华科计科第一次数据结构实验源代码

2012级计科专业《算法与数据结构》课程设计题.docx

《数据结构实验》教学大纲.docx

山东大学《数据结构》实验教学大纲.docx

《数据结构》课程实验教学大纲.docx

《数据结构实验》课程教学大纲.docx

《数据结构Ⅰ实验》教学大纲.docx

《空间数据结构实验》课程教学大纲.docx

《数据结构实验Ⅰ》课程教学大纲.docx

《数据结构与算法实验》教学大纲.docx

《数据结构Ⅰ实验》课程教学大纲.docx

《数据结构课程设计》实验课教学大纲.docx

《数据结构》实验教学大纲 (2).docx

《数据结构与算法》实验大纲.docx

《数据结构与算法 》(实验大纲 ).docx

数据库系统概论(基础篇)教学大纲.docx

KepOPC DA2UA实现从OPCDA到OPCUA的转换及读写互操作

Midjourney-关键词大全

“未来工厂”建设导则.pdf

最新资源

数据结构实验课程教学大纲.docx

《数据结构与算法》(实验大纲 ).docx