《计科数据结构与算法实验大纲.doc》由会员分享，可在线阅读，更多相关《计科数据结构与算法实验大纲.doc（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构与算法实验教学大纲课程编号：B课程类别：专业基础必修课实验学时：实验16学时学 分：4适用专业：计算机科学与技术、计算机科学与技术（数字媒体艺术）一、实验教学目的和任务 数据结构与算法是信息与计算科学专业中一门重要的专业基础课程。当用计算机来解决实际问题时，就要涉及到数据的表示及数据的处理，而数据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续课程，特别是软件方面的课程打下了厚实的知识基础，同时也提供了必要的技能训练。因此，数据结构课程在计算机应用专业中具有举足轻重的作用。本课程的任务是：通过实践，学生对常用数据结构的基本概念及其不同的实现方法的理论得到进一
2、步的掌握，并对在不同存储结构上实现不同的运算方式和技巧有所体会。二、实验教学基本要求本课程是一门实践性很强的专业课，只有了解这门课程的特点和基本要求，学习时才能做到有的放矢，举一反三，基本要求主要有以下几个方面：（1）认真阅读掌握和实验相关的指导书内容。（2）自己编程，可以参考别人的程序设计方法，但不得抄袭别人的程序。（3）程序有错误时，尽量先自己调试，在自己能力达不到时，可请教同学或询问老师。（4）及时完成实验报告。三、实验教学内容数据结构与算法实验分五个实验项目，实验的具体内容见数据结构与算法实验指导书，每个实验项目完成后要提交一份电子实验报告，每份实验报告至少包括实验项目中的四个实验任务
3、，电子实验报告模板见附录1。实验一 线性表的实验1、实验目的及要求：(1) 了解线性表的顺序存储方法和链式存储方法，掌握用在VC环境下上机调试顺序表和单链表的基本方法。(2) 掌握顺序表的插入、删除、查找、求表长以及有序顺序表的合并算法的实现(3) 掌握单链表、循环链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现(4) 讨论单链表和顺序表在设计上的差别。2、实验内容及学时分配： （4学时）(1) 顺序表基本操作的实现(2) 有序顺序表的合并，已知顺序表la和lb中的数据元素按非递减有序排列，将la和lb表中的数据元素，合并成为一个新的非递减有序顺序表lc，并且不破坏la和lb表(3
4、) 单链表基本操作的实现(4) 有序单链表的合并，已知单链表la和lb中的数据元素按非递减有序排列，将la和lb中的数据元素,合并为一个新的单链表lc,lc中的数据元素仍按非递减有序排列，要求不破坏la表和lb表的结构。(5) 约瑟夫环问题，设有N个人围坐一圈，现从某个人开始报数，数到M的人出列，接着从出列的下一个人开始重新报数，数到M的人以出列，如此下去，直到所有人都出列为此。试设计确定他们的出列次序序列的程序。选择单向循环链表作为存储结构模拟整个过程，并依次输出列的各人的编号。(6) 编程实现两个循环单链表的合并。实验二 栈、队列的实现及应用1、实验目的及要求：(1) 掌握栈和队列的顺序存
5、储结构和链式存储结构，以便在实际背景下灵活运用。(2) 掌握栈和队列的特点，即先进后出与先进先出的原则。(3) 掌握栈和队列的基本操作实现方法。2、实验内容及学时分配： （2学时）(1) 实现栈的顺序存储(2) 利用栈实现数制转换 (3) 实现循环队列的顺序存储(4) 顺序串的基本操作实验三二叉树的操作及应用1、实验目的及要求：(1) 进一步掌握指针变量、动态变量的含义。(2) 掌握二叉树的结构特性，以及各种存储结构的特点和适用范围。(3) 掌握用指针类型描述、访问和处理二叉树的运算。2、实验内容及学时分配： （4学时）(1) 以二叉链表作存储结构，试编写前序、中序、后序及层次顺序遍历二叉树的
6、算法。(2) 以二叉链表作存储结构，试编写计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数的算法(3) 编写按中序顺序建立一棵二叉树的非递归算法的C语言源程序，并且用非递归方式遍历二叉树（先序、中序或后序），输出遍历序列。(4) 赫夫曼树与赫夫曼编码，利用Huffman编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接受端将传来的数据编码进行译码（复原）。对于有些信道，每端都需要一个完整的编译码系统。试为这样的信息收发站编写一个Huffman的编译码系统。给定一组权值7，9，5，6，10，1，
7、13，15，4，8，构造一棵赫夫曼树，并计算带权路径长度WPL。实验四 图的操作及应用1、实验目的及要求：(1) 熟练掌握图的邻接矩阵和邻接表的存储方式；(2) 实现图的一些基本运算，特别是深度遍历和广度遍历；(3) 掌握以图为基础的一些常用算法，如最小生成树、拓扑排序、最短路径等2、实验内容及学时分配： （2学时）(1) 定义邻接矩阵存储结构或邻接表存储结构。(2) 按照建立一个带权有向图的操作需要，编写在邻接矩阵或邻接表存储结构下，带权有向图基本操作的实现函数（如初始化图、在图中插入一个结点、在图中插入一条边、在图中寻找序号为v的结点的第一个邻接结点、在图中寻找序号为v1结点的邻接结点v2
8、的下一个邻接结点、图的深度优先遍历、图的广度优先遍历等）。(3) 设计一个测试主函数，首先创建一个图（有n个结点和e条边），然后打印图的n个结点信息和e条边信息，最后分别打印出图的深度优先遍历和广度优先遍历的结点信息序列。实验五 查找与排序1、实验目的及要求：(1) 掌握查找的不同方法，并能用高级语言实现查找算法。(2) 熟练掌握顺序表的查找方法和有序顺序表的折半查找算法以及静态查找树的构造方法和查找算法。(3) 掌握二叉排序树的生成、插入、删除、输出运算。 (4) 掌握常用的排序方法，并能用高级语言实现排序算法。(5) 深刻理解排序的定义和各种排序方法的特点，并能加以灵活运用。(6) 了解各
9、种方法的排序过程及依据的原则，并掌握各种排序方法的时间复杂度的分析方法。2、实验内容及学时分配： （4学时）(1) 作为输入给定的是已分类的数列：a1,a2,a3, , an，以及随后的问题序列：b1, b2, b3, , bn。请编写一个程序，首先顺序存储数列a1,a2,a3, , an，然后用折半查找法对每个问题bi找出使aj等于bi的一切j，当没有这样的j及有多个这样的j时，程序也应能够正常工作。(2) 给定一个用无序链表表示的集合，需要在其上执行operator+( ), operator*( ), operator- ( ), Contains(x), AddMember (x),
10、DelMember(x), Min( )，试给出所有这些函数的实现。(3) 用序列（46，88，45，39，70，58，101，10，66，34）建立一个排序二叉树，编程实现二叉排序树的建立、查找、中序遍历算法，计算和输出每次查找所需和关键字进行比较的次数，以及在等概率情况下查找成功时的平均查找长度。(4) 设计一个程序读入一个字符串，统计该字符串中出现的字符及其次数，然后以表的形式输出结果。要求用一个二叉树来保存处理结果，字符串中的每个不同的字符用树中不同的结点描述，每个结点包含四个域，格式为：字符、该字符的出现次数、指向ASCII码小于该字符的左子树指针、指向ASCII码大于该字符的右子树
11、指针。因此程序的功能是依次从输入字符串中取出一个字符，把它们插入到树中（新出现字符）或修改原树中相应结点的“出现次数域”（已出现字符）。(5) 请编写一个算法，在基于单链表表示的待排序排序码序列上进行简单选择排序。(6) 采用静态单链表作为存储表示。用Vector0作为表头结点，各待排序数据对象从Vector1开始存放。算法的思想是每趟在原始链表中摘下排序码最大的结点(几个排序码相等时为最前面的结点)，把它插入到结果链表的最前端。由于在原始链表中摘下的排序码越来越小，在结果链表前端插入的排序码也越来越小，最后形成的结果链表中的结点将按排序码非递减的顺序有序链接。四、实验项目与学时分配序号实验项
12、目名称学时实验类型实验主要仪器设备备注实验一线性表的实验4设计性必做实验二 栈、队列的实现及应用2设计性必做实验三 二叉树的操作及应用4设计性必做实验四 图的操作及应用2设计性必做实验五 查找与排序4设计性必做五、实验考核办法与成绩评定实验成绩由实验报告、实验考试两部份组成。实验报告占课程总成绩的10%，实验考试成绩占课程总成绩的10%。六、实验教材（或参考书、指导书）教材：1 严蔚敏,吴伟民.数据结构（C语言版）M. (第三版)北京：清华大学出版社.1997参考书：2 Sartaj Sahni. Data Structure, Algorithms, and Application in C
13、+. The McGraw-Hill Company Inc.1998M (第一版) (数据结构、算法与应用C+语言描述.北京:机械工业出版社.19993 Willan Ford,Willian Topp. Data Structures with C+. New Jersey:Prentice Hall Inc, Adivision Simon & Schuster Company,1996M (第一版) (数据结构C+语言描述.北京:清华大学出版社，19974 徐孝凯.数据结构实用教程（C/C+描述）M. (第一版)北京:清华大学出版社.19995 陈慧南.数据结构（使用C+语言描述）M.
14、 (第一版)南京:东南大学出版社.20016 殷人昆,陶永雷,谢若阳等.数据结构（用面向对象方法与C+描述）M. (第一版)北京:清华大学出版社.1999 执笔人：祁文青 审核人：祁文青 （盖章）2011年 9 月 1 日附录1：实验报告模板实验一 线性表的实验实验课程名：数据结构专业班级： 学号： 姓名： 实验时间： 实验地点： 指导教师： 一、实验目的和要求二、实验内容任务1 *（任务名称） 1、实验内容（写出简要原理、公式及其应用条件等，若无，可只写实验内容）（1）（2）（3） 2、实验步骤（写出实验操作的总体思路、操作规范和操作主要注意事项，准确无误地记录原始数据。若为程序设计类课程，要求写出核心代码）（1）（2）（3）3、实验结果与分析（明确地写出最后结果，并对自己得出的结果进行具体、定量的结果分析，说明其可靠性；杜绝只罗列不分析）任务2 *（任务名称）三、结论（写本次实验的收获）说明：1. 验证性实验报告填写好后，以学生的学号+实验项目名作为该word文件名保存，例如某学生学号为，姓名为某某，本次实验名称是：实验1 线性表的实验，则本次实验报告的保存文件名为：01某某实验1.doc。2. 在规定的时间内，学生将本报告提交给实验指导教师。