计科数据结构实验大纲.doc
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《计科数据结构实验大纲.doc》由会员分享,可在线阅读,更多相关《计科数据结构实验大纲.doc(13页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、数据结构实验教学大纲课程编号:课程类别:专业基础必修课实验学时:实验16学时学 分:5适用专业:计算机科学与技术一、实验教学目的和任务 数据结构是信息与计算科学专业中一门重要的专业基础课程。当用计算机来解决实际问题时,就要涉及到数据的表示及数据的处理,而数据表示及数据处理正是数据结构课程的主要研究对象,通过这两方面内容的学习,为后续课程,特别是软件方面的课程打下了厚实的知识基础,同时也提供了必要的技能训练。因此,数据结构课程在计算机应用专业中具有举足轻重的作用。本课程的任务是:通过实践,学生对常用数据结构的基本概念及其不同的实现方法的理论得到进一步的掌握,并对在不同存储结构上实现不同的运算方式
2、和技巧有所体会。二、实验教学基本要求本课程是一门实践性很强的专业课,只有了解这门课程的特点和基本要求,学习时才能做到有的放矢,举一反三,本课程特点主要有以下几个方面:(1) 内容丰富,理论性强。本课程为以后学习专业基础课和专业课(如:计算机操作系统、数据库原理等)打下良好的基础。(2) 注重理论联系实际,加强实验环节的训练。只有通过实验,才能透彻理解基本原理。三、实验教学内容实验分验证性实验和设计性实验两部分,课外20学时用来完成验证性实验项目,以下的实验一至实验五为验证性实验,验证性实验的具体内容见数据结构验证性实验指导书,每个验证性实验项目完成后要提交一份电子实验报告,每份验证性实验报告至
3、少包括实验项目中的三个实验任务,电子验证性实验报告模板见附录1。实验16学时用来完成设计性实验项目, 全班学生分成小组,每组3-4人,设计性实验项目的源程序全部由学生自己设计,同组的同学可以分工协助,每人至少完成设计性实验项目中的一个子任务,必须提前准备好设计性实验项目的代码,实验课开始时马上提交自己的源代码,实验课时老师随即抽取一个小组,首先,由小组学生讲解自己编写的代码并演示执行,接着,由老师和同学根据演示同学的代码提问,由演示的同学回答,如果当堂不能解决,可下去准备,在下次实验课时再来解答。课后,被抽中的小组学生在实验课后及时上交一份设计性实验报告,记录自己演示代码及回答提问时的情况及代
4、码改进的情况,既提交电子稿又要交打印稿,设计性实验报告模板见附录2。验证性实验项目实验一 线性表的顺序存储实验1、实验目的及要求:(1) 了解线性表的顺序存储方法,掌握用在VC环境下上机调试单链表的基本方法。(2) 掌握顺序表的插入、删除、查找、求表长以及有序顺序表的合并算法的实现2、实验内容及学时分配: (4学时)(1) 顺序表基本操作的实现(2) 有序顺序表的合并,已知顺序表la和lb中的数据元素按非递减有序排列,将la和lb表中的数据元素,合并成为一个新的非递减有序顺序表lc,并且不破坏la和lb表实验二 单链表实验1、实验目的及要求:(1) 掌握用在VC环境下上机调试单链表的基本方法(
5、2) 掌握单链表、循环链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现2、实验内容及学时分配: (4学时)(1) 单链表基本操作的实现(2) 有序单链表的合并,已知单链表la和lb中的数据元素按非递减有序排列,将la和lb中的数据元素,合并为一个新的单链表lc,lc中的数据元素仍按非递减有序排列,要求不破坏la表和lb表的结构。(3) 约瑟夫环问题,设有N个人围坐一圈,现从某个人开始报数,数到M的人出列,接着从出列的下一个人开始重新报数,数到M的人以出列,如此下去,直到所有人都出列为此。试设计确定他们的出列次序序列的程序。选择单向循环链表作为存储结构模拟整个过程,并依次输出列的各人
6、的编号。(4) 编程实现两个循环单链表的合并。实验三 栈、队列的实现及应用1、实验目的及要求:(1) 掌握栈和队列的顺序存储结构和链式存储结构,以便在实际背景下灵活运用。(2) 掌握栈和队列的特点,即先进后出与先进先出的原则。(3) 掌握栈和队列的基本操作实现方法。2、实验内容及学时分配: (4学时)(1) 实现栈的顺序存储(2) 利用栈实现数制转换 (3) 实现循环队列的顺序存储(4) 顺序串的基本操作实验四二叉树的基本操作及应用1、实验目的及要求:(1) 进一步掌握指针变量、动态变量的含义。(2) 掌握二叉树的结构特性,以及各种存储结构的特点和适用范围。(3) 掌握用指针类型描述、访问和处
7、理二叉树的运算。2、实验内容及学时分配: (4学时)(1) 以二叉链表作存储结构,试编写前序、中序、后序及层次顺序遍历二叉树的算法。(2) 以二叉链表作存储结构,试编写计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数的算法(3) 编写按中序顺序建立一棵二叉树的非递归算法的C语言源程序,并且用非递归方式遍历二叉树(先序、中序或后序),输出遍历序列。(4) 赫夫曼树与赫夫曼编码,利用Huffman编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接受端将传来的数据编码进行译码(复原)。对于有些信道,
8、每端都需要一个完整的编译码系统。试为这样的信息收发站编写一个Huffman的编译码系统。给定一组权值7,9,5,6,10,1,13,15,4,8,构造一棵赫夫曼树,并计算带权路径长度WPL。实验五 查找与排序1、实验目的及要求:(1) 掌握查找的不同方法,并能用高级语言实现查找算法。(2) 熟练掌握顺序表的查找方法和有序顺序表的折半查找算法以及静态查找树的构造方法和查找算法。(3) 掌握二叉排序树的生成、插入、删除、输出运算。 (4) 掌握常用的排序方法,并能用高级语言实现排序算法。(5) 深刻理解排序的定义和各种排序方法的特点,并能加以灵活运用。(6) 了解各种方法的排序过程及依据的原则,并
9、掌握各种排序方法的时间复杂度的分析方法。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), Mi
10、n( ),试给出所有这些函数的实现。(7) 用序列(46,88,45,39,70,58,101,10,66,34)建立一个排序二叉树,编程实现二叉排序树的建立、查找、中序遍历算法,计算和输出每次查找所需和关键字进行比较的次数,以及在等概率情况下查找成功时的平均查找长度。(8) 设计一个程序读入一个字符串,统计该字符串中出现的字符及其次数,然后以表的形式输出结果。要求用一个二叉树来保存处理结果,字符串中的每个不同的字符用树中不同的结点描述,每个结点包含四个域,格式为:字符、该字符的出现次数、指向ASCII码小于该字符的左子树指针、指向ASCII码大于该字符的右子树指针。因此程序的功能是依次从输入
11、字符串中取出一个字符,把它们插入到树中(新出现字符)或修改原树中相应结点的“出现次数域”(已出现字符)。(9) 请编写一个算法,在基于单链表表示的待排序排序码序列上进行简单选择排序。(10) 采用静态单链表作为存储表示。用Vector0作为表头结点,各待排序数据对象从Vector1开始存放。算法的思想是每趟在原始链表中摘下排序码最大的结点(几个排序码相等时为最前面的结点),把它插入到结果链表的最前端。由于在原始链表中摘下的排序码越来越小,在结果链表前端插入的排序码也越来越小,最后形成的结果链表中的结点将按排序码非递减的顺序有序链接。设计性实验项目1. 线性表的合并:已知线性表La和Lb的元素按
12、值非递减排列。归并La和Lb得到新的线性表Lc,Lc的元素也按值非递减排列。分别采用顺序存储结构和链式结构来实现。2. 线性表的逆置:设有一个线性表(e0, e1, , en-2, en-1),请编写一个函数将这个线性表原地逆置,即将线性表内容置换为(en-1, en-2, , e1, e0)。线性表中的数据可以为整数、字符或字符串,试分别采用顺序存储结构和链式结构来实现。3. 约瑟夫环的实现:设有n个人围坐一圈,用整数序列1, 2, 3, , n表示顺序围坐在圆桌周围的人, 现从某个位置 s上的人开始报数,数到m的人出列,接着从出列的下一个人又从1开始重新报数,数到m的人出列,如此下去,直到
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 大纲
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内