2022年计科数据结构实验大纲 .pdf

《2022年计科数据结构实验大纲 .pdf》由会员分享，可在线阅读，更多相关《2022年计科数据结构实验大纲 .pdf（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 / 12 数据结构实验教案大纲课程编号： 404511043课程类别： 专业基础必修课实验学时： 实验 16 学时学分： 5适用专业： 计算机科学与技术一、实验教案目的和任务数据结构是信息与计算科学专业中一门重要的专业基础课程。当用计算机来解决实际问题时，就要涉及到数据的表示及数据的处理，而数据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续课程，特别是软件方面的课程打下了厚实的知识基础，同时也提供了必要的技能训练。因此，数据结构课程在计算机应用专业中具有举足轻重的作用。本课程的任务是：通过实践，学生对常用数据结构的基本概念及其不同的实现方法的理论得到进一步的掌

2、握，并对在不同存储结构上实现不同的运算方式和技巧有所体会。二、实验教案基本要求本课程是一门实践性很强的专业课，只有了解这门课程的特点和基本要求，学习时才能做到有的放矢，举一反三，本课程特点主要有以下几个方面：(1 内容丰富，理论性强。本课程为以后学习专业基础课和专业课(如：计算机操作系统、数据库原理等打下良好的基础。(2 注重理论联系实际，加强实验环节的训练。只有通过实验，才能透彻理解基本原理。三、实验教案内容实验分验证性实验和设计性实验两部分，课外20学时用来完成验证性实验工程，以下的实验一至实验五为验证性实验，验证性实验的具体内容见数据结构验证性实验指导书，每个验证性实验工程完成后要提交一

3、份电子实验报告，每份验证性实验报告至少包括实验工程中的三个实验任务，电子验证性实验报告模板见附录1。实验 16 学时用来完成设计性实验工程，全班学生分成小组，每组3-4 人，设计性实验工程的源程序全部由学生自己设计，同组的同学可以分工协助，每人至少完成设计性实验工程中的一个子任务，必须提前准备好设计性实验工程的代码，实验课开始时马上提交自己的源代码，实验课时老师随即抽取一个小组，首先，由小组学生讲解自己编写的代码并演示执行，接着，由老师和同学根据演示同学的代码提问，由演示的同学回答，如果当堂不能解决，可下去准备，在下次实验课时再来解答。课后，被抽中的小组学生在实验课后及时上交一份设计性实验报告

4、，记录自己演示代码及回答提问时的情况及代码改进的情况，既提交电子稿又要交打印稿，设计性实验报告模板见附录2。验证性实验工程实验一线性表的顺序存储实验1、实验目的及要求：(1)了解线性表的顺序存储方法，掌握用在VC环境下上机调试单链表的基本方法。(2)掌握顺序表的插入、删除、查找、求表长以及有序顺序表的合并算法的实现2、实验内容及学时分配：4 学时）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 12 页2 / 12 (1)顺序表基本操作的实现(2)有序顺序表的合并，已知顺序表la 和 lb 中的数据元素按非递减有序排列，将la和 lb表

5、中的数据元素，合并成为一个新的非递减有序顺序表lc ，并且不破坏la和 lb 表实验二单链表实验1、实验目的及要求：(1)掌握用在VC环境下上机调试单链表的基本方法(2)掌握单链表、循环链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现2、实验内容及学时分配：4 学时）(1)单链表基本操作的实现(2)有序单链表的合并，已知单链表la 和 lb 中的数据元素按非递减有序排列，将la和 lb中的数据元素, 合并为一个新的单链表lc,lc中的数据元素仍按非递减有序排列，要求不破坏la 表和 lb 表的结构。(3)约瑟夫环问题，设有N 个人围坐一圈，现从某个人开始报数，数到M的人出列，接着从

6、出列的下一个人开始重新报数，数到M 的人以出列，如此下去，直到所有人都出列为此。试设计确定他们的出列次序序列的程序。选择单向循环链表作为存储结构模拟整个过程，并依次输出列的各人的编号。(4)编程实现两个循环单链表的合并。实验三栈、队列的实现及应用1、实验目的及要求：(1)掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。(2)掌握栈和队列的特点，即先进后出与先进先出的原则。(3)掌握栈和队列的基本操作实现方法。2、实验内容及学时分配：4 学时）(1)实现栈的顺序存储(2)利用栈实现数制转换(3)实现循环队列的顺序存储(4)顺序串的基本操作实验四二叉树的基本操作及应用1、实验目

7、的及要求：(1)进一步掌握指针变量、动态变量的含义。(2)掌握二叉树的结构特性，以及各种存储结构的特点和适用范围。(3)掌握用指针类型描述、访问和处理二叉树的运算。2、实验内容及学时分配：4 学时）(1)以二叉链表作存储结构，试编写前序、中序、后序及层次顺序遍历二叉树的算法。(2)以二叉链表作存储结构，试编写计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数的算法(3)编写按中序顺序建立一棵二叉树的非递归算法的C 语言源程序，并且用非递归方式遍历二叉树先序、中序或后序），输出遍历序列。(4)赫夫曼树与赫夫曼编码，利用Huffman 编码进行通信可以大大提高信道利用率，缩短

8、信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接受端将传来的数据编码进行译码复原）。对于有些信道，每端都需要一个完整的编译码系统。试为这样的信息收发站编写一个Huffman的编译码系统。给定一组权值7，9， 5，6，10，1，13，15，4，8 ，构造一棵赫夫曼树，并计算带权路径长度WPL 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 12 页3 / 12 实验五查找与排序1、实验目的及要求：(1)掌握查找的不同方法，并能用高级语言实现查找算法。(2)熟练掌握顺序表的查找方法和有序顺序表的折半

9、查找算法以及静态查找树的构造方法和查找算法。(3)掌握二叉排序树的生成、插入、删除、输出运算。(4)掌握常用的排序方法，并能用高级语言实现排序算法。(5)深刻理解排序的定义和各种排序方法的特点，并能加以灵活运用。(6)了解各种方法的排序过程及依据的原则，并掌握各种排序方法的时间复杂度的分析方法。2、实验内容及学时分配：, operator*( , operator- ( , Contains(x, AddMember (x, DelMember(x, Min( ，试给出所有这些函数的实现。(7)用序列 46， 88， 45， 39，70， 58，101，10，66， 34）建立一个排序二叉树，

10、编程实现二叉排序树的建立、查找、中序遍历算法，计算和输出每次查找所需和关键字进行比较的次数，以及在等概率情况下查找成功时的平均查找长度。(8)设计一个程序读入一个字符串，统计该字符串中出现的字符及其次数，然后以表的形式输出结果。要求用一个二叉树来保存处理结果，字符串中的每个不同的字符用树中不同的结点描述，每个结点包含四个域，格式为：字符、该字符的出现次数、指向ASCII 码小于该字符的左子树指针、指向ASCII 码大于该字符的右子树指针。因此程序的功能是依次从输入字符串中取出一个字符，把它们插入到树中新出现字符）或修改原树中相应结点的“出现次数域”，把它插入到结果链表的最前端。由于在原始链表中

11、摘下的排序码越来越小，在结果链表前端插入的排序码也越来越小，最后形成的结果链表中的结点将按排序码非递减的顺序有序链接。设计性实验工程1. 线性表的合并：已知线性表La 和 Lb 的元素按值非递减排列。归并La 和 Lb 得到新的线性表 Lc，Lc 的元素也按值非递减排列。分别采用顺序存储结构和链式结构来实现。2. 线性表的逆置：设有一个线性表e0, e1, , en-2, en-1），请编写一个函数将这个线性表原地逆置，即将线性表内容置换为 采用数组表示作为求解过程中使用的数据结构。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 12

12、页4 / 12 (2 采用单向循环链表作为存储结构模拟整个过程，循环链表可不设头节点, 必须注意空表和非空表的界限。4. 数制转换：利用顺序栈和链栈实现数制转换5. 二叉树的遍历：分别以顺序存储结构和二叉链表作存储结构，试编写前序、中序、后序及层次顺序遍历二叉树的算法。6. 赫 夫 曼 树 与 赫 夫 曼 编 码 ： 已 知 某 系 统 在 通 信 联 络 中 只 可 能 出 现8种 字 符a,b,c,d,e,f,g,h，其概率分别为0.05 ，0.29 ，0.07 ，0.08 ，0.14 ，0.23 ，0.03 ，0.11 ，试设计 Huffman 编码，并计算其平均码长。(1 初始化：从键

13、盘读入8 个字符，以及它们的权值，建立Huffman 树。(2 编码：根据建立的Huffman 树，求每个字符的Huffman 编码。对给定的待编码字符序列进行编码。(3 译码：利用已经建立好的Huffman 树，对上面的编码结果译码。译码的过程是分解电文中的字符串，从根结点出发，按字符0和 1确定找左孩子或右孩子，直至叶结点，便求得该子串相应的字符。(4 打印Huffman 树。7. 学生成绩管理查询系统：每个学生的数据信息有准考证号主关键字）、姓名、语文、英语、数学、和总分等数据项，所有学生的信息构成一个学生成绩表。假设准考证号的头两位表示地区编号。请设计一个管理系统达到如下基本要求：1）

14、 初始化：建立一个学生成绩表，输入准考证号、姓名、语文、英语、数学，然后计算每个学生的总分，存入相应的数据项；注意：分析数据对象和它们之间的关系，并以合适的方式进行组织可选择无序的顺序表、有序的顺序表或索引顺序表来进行存储表示）；2） 查找：综合应用基本查找算法完成数据的基本查询工作，并输出查询的结果；3） 输出：有选择性地输出满足一定条件的数据记录，如输出准考证号地区编号为01 ，并且总分在550 分以上的学生的信息；4） 计算：计算在等概率情况下该查找表的平均查找长度。8. 排序：编制程序，让机器随机产生2000 个整数，放入一个数组中；对此2000 个随机数序列分别用冒泡排序、快速排序、

15、希尔排序和堆排序方法进行排序，并比较它们的运行时间。四、实验工程与学时分配序号实验工程名称学时实验类型实验主要仪器设备备注1 线性表的合并1 设计性选做实验一线性表的顺序存储实验1验证性必做2 线性表的逆置1设计性选做实验二单链表实验1验证性必做3 约瑟夫环的实现1设计性选做精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 12 页5 / 12 实验二单链表实验1验证性必做4 数制转换1设计性选做实验三栈、队列的实现及应用1验证性必做5 二叉树的遍历1设计性选做实验四 二叉树的操作及应用1验证性必做6 赫夫曼树与赫夫曼编码1设计性选做实验

16、四 二叉树的操作及应用1验证性必做7 学生成绩管理查询系统1设计性选做实验五 查找与排序1验证性必做8 排序1设计性选做实验五 查找与排序1验证性必做五、实验考核办法与成绩评定总实验成绩由验证性实验的成绩和设计性实验的成绩组成，两部分成绩加起来按百分制评定，占总成绩的50%。验证性实验的成绩占总实验成绩的10%，教师根据学生做验证性实验的表现和验证性的电子实验报告来评定。设计性实验的成绩占总实验成绩的40%，教师根据学生亲自动手演示代码、口头回答同学提问、以及在听了其他同学演示后提问的积极性、上交的设计性实验报告等方面综合表现评定。六、实验教材 或参考书、指导书）教材：1 严蔚敏 , 吴伟民

17、. 数据结构 北京：清华大学出版社.1997 参考书：2 Sartaj Sahni. Data Structure, Algorithms, and Application in C+. The McGraw-Hill Company Inc.1998M ( 第一版 ( 数据结构、算法与应用C+ 语言描述 .北京 : 机械工业出版社.1999 3 Willan Ford,Willian Topp. Data Structures with C+. New Jersey:Prentice Hall Inc, Adivision Simon & Schuster Company,1996M ( 第

18、一版 ( 数据结构C+语言描述 .北京 : 清华大学出版社，1997 4 徐孝凯 . 数据结构实用教程北京 : 清华大学出版社.1999 5 陈慧南 . 数据结构 南京 : 东南大学出版社.2001 6 殷人昆 , 陶永雷 , 谢若阳等 . 数据结构 北京 :清华大学出版社.1999 执笔人：祁文青审核人：祁文青盖章）2008 年 9 月 1 日附录 1：验证性实验报告模板验证性实验一线性表的顺序存储实验实验课程名：数据结构专业班级：学号：姓名：实验时间：实验地点：指导教师：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 12 页6 /

19、 12 一、实验目的和要求二、实验内容任务 1 *任务名称） 1、实验内容 写出简要原理、公式及其应用条件等，若无，可只写实验内容）1）2）3） 2、实验步骤 写出实验操作的总体思路、操作规范和操作主要注意事项，准确无误地记录原始数据。若为程序设计类课程，要求写出核心代码）1）2）3）3、实验结果与分析 明确地写出最后结果，并对自己得出的结果进行具体、定量的结果分析，说明其可靠性；杜绝只罗列不分析）任务 2 *任务名称）三、结论 写本次实验的收获）四、教师批阅及成绩：日期：说明：1.验证性实验报告填写好后，以学生的学号+实验工程名作为该word 文件名保存，例如某学生学号为20080001，姓

20、名为某某，本次实验名称是：实验1 线性表的顺序存储实验，则本次实验报告的保存文件名为：01 某某验证性实验1.doc。2.在规定的时间内，学生将本报告提交给实验指导教师。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 12 页7 / 12 3.实验教师批改收到的实验报告后，将发还给学生。附录 2：设计性实验报告模板设计性实验二线性表的逆置实验课程名：数据结构专业班级：学号：姓名：实验时间：实验地点：指导教师：一实验任务：设有一个线性表 e0, e1, , en-2, en-1），请编写一个函数将这个线性表原地逆置，即将线性表内容置换为：

21、文字或流程图或画图说明都可精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 12 页8 / 12 四源代码： 1.链表转置算法void transpose(LinkList &l/ 转置带头结点的链表 LinkList p,q 。p=l-next。/让 p 指向第一个元素l-next=NULL 。/让 Head的指针域为空while(p!=NULL q=p-next。/让 q 指向第二个元素p-next=l-next。/让 p 的指针域为空l-next=p。p=q。 2. 定义链表typedef char elemtype10 。/定义字

22、符串typedef struct LNode elemtype data 。struct LNode *next。LNode,*LinkList 。void CreateList_l(LinkList &L/ 带头结点的链表 L=(LinkListmalloc(sizeof(LNode 。LinkList p,q 。elemtype i。L-next=NULL 。q=L。while(strcmp(i,*!=0 p=(LinkListmalloc(sizeof(LNode 。cini 。if(strcmp(i,*!=0/ 结束数据输入时，用到库函数strcmp( p-next=q-next。q-

23、next=p。q=p。strcpy(q-data,i。 3.链表输出：void display(LinkList &L 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 12 页9 / 12 LinkList p 。p=L-next。while(p!=NULL coutdatanext。 cout定义结构体：typedef struct student char name10。int age。float score。elemtype。(2建立链表的时候，代码如下：void CreateList_l(LinkList &L/ 带头结点的链表

24、 L=(LinkListmalloc(sizeof(LNode 。LinkList p,q 。elemtype i。L-next=NULL 。q=L。while(strcmp(i.name,*!=0 p=(LinkListmalloc(sizeof(LNode 。cini.namei.agei.score。if(strcmp(i.name,*!=0 p-next=q-next。q-next=p。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 12 页10 / 12 q=p。strcpy(q-data.name,i.name 。(q-da

25、ta.age=i.age 。(q-data.score=i.score 。 (3链表输出代码如下：void display(LinkList &L LinkList p 。p=L-next。while(p!=NULL coutdata.name data.age data.score next。 cout运行结果：2.老师提问：不同类型的数据，输入与输出的语句不同，可不可以定义不同的方法，在对相应类型数据进行输入输出时，直接进行调用。回答：不同方法设置如下：(1) 输入方法：字符型，整型，字符串型数据的输入代码：void Input(elemtype &i cini。 结构体类型数据的输入代码

26、void Input(elemtype &i 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 12 页11 / 12 cini.namei.agei.score。 调用语句：Input(i。(2) 输出代码：字符型，整型，字符串型数据的输入代码void Output(LinkList &p coutdata coutdata.name data.age data.score 。3. 同学提问：你的链表逆置后，原来的链表不存在了，请问能否不破坏原来链表的结构，重新生成一个逆置的单链表？实验结论 : 教师批阅及成绩：指导教师签名：日期：说明：1.设计性实验报告写好后，以学生的学号+实验工程名作为该word 文件名保存，例如某学生学号为20080001，姓名为某某，本次实验名称是：线性表的逆置，则本次实验报告的保存文件名为：01 某某线性表的逆置.doc。2.在规定的时间内，学生将本报告提交给实验指导教师。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 12 页12 / 12 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 12 页