计科数据结构实验大纲.docx
《计科数据结构实验大纲.docx》由会员分享，可在线阅读，更多相关《计科数据结构实验大纲.docx（18页珍藏版）》请在冰点文库上搜索。
计科数据结构实验大纲
《数据结构》实验教案大纲
课程编号：
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.线性表的逆置：
设有一个线性表线性表中的数据可以为整数、字符或字符串，试分别采用顺序存储结构和链式结构来实现。
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>采用单向循环链表作为存储结构模拟整个过程，循环链表可不设头节点,必须注意空表和非空表的界限。
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>初始化：
从键盘读入8个字符，以及它们的权值，建立Huffman树。
（2>编码：
根据建立的Huffman树，求每个字符的Huffman编码。
对给定的待编码字符序列进行编码。
（3>译码：
利用已经建立好的Huffman树，对上面的编码结果译码。
译码的过程是分解电文中的字符串，从根结点出发，按字符’0’和’1’确定找左孩子或右孩子，直至叶结点，便求得该子串相应的字符。
（4>打印 Huffman树。
7.学生成绩管理查询系统：
每个学生的数据信息有准考证号<主关键字）、姓名、语文、英语、数学、和总分等数据项，所有学生的信息构成一个学生成绩表。
假设准考证号的头两位表示地区编号。
请设计一个管理系统达到如下基本要求：
<1）初始化：
建立一个学生成绩表，输入准考证号、姓名、语文、英语、数学，然后计算每个学生的总分，存入相应的数据项；注意：
分析数据对象和它们之间的关系，并以合适的方式进行组织<可选择无序的顺序表、有序的顺序表或索引顺序表来进行存储表示）；
<2）查找：
综合应用基本查找算法完成数据的基本查询工作，并输出查询的结果；
<3）输出：
有选择性地输出满足一定条件的数据记录，如输出准考证号地区编号为"01"，并且总分在550分以上的学生的信息；
<4）计算：
计算在等概率情况下该查找表的平均查找长度。
8.排序：
编制程序，让机器随机产生2000个整数，放入一个数组中；对此2000个随机数序列分别用冒泡排序、快速排序、希尔排序和堆排序方法进行排序，并比较它们的运行时间。
四、实验工程与学时分配
序号
实验工程名称
学时
实验类型
实验主要仪器设备
备注
1
线性表的合并
1
设计性
选做
实验一 线性表的顺序存储实验
1
验证性
必做
2
线性表的逆置
1
设计性
选做
实验二 单链表实验
1
验证性
必做
3
约瑟夫环的实现
1
设计性
选做
实验二 单链表实验
1
验证性
必做
4
数制转换
1
设计性
选做
实验三栈、队列的实现及应用
1
验证性
必做
5
二叉树的遍历
1
设计性
选做
实验四二叉树的操作及应用
1
验证性
必做
6
赫夫曼树与赫夫曼编码
1
设计性
选做
实验四二叉树的操作及应用
1
验证性
必做
7
学生成绩管理查询系统
1
设计性
选做
实验五查找与排序
1
验证性
必做
8
排序
1
设计性
选做
实验五查找与排序
1
验证性
必做
五、实验考核办法与成绩评定
总实验成绩由验证性实验的成绩和设计性实验的成绩组成，两部分成绩加起来按百分制评定，占总成绩的50%。
验证性实验的成绩占总实验成绩的10%，教师根据学生做验证性实验的表现和验证性的电子实验报告来评定。
设计性实验的成绩占总实验成绩的40%，教师根据学生亲自动手演示代码、口头回答同学提问、以及在听了其他同学演示后提问的积极性、上交的设计性实验报告等方面综合表现评定。
六、实验教材<或参考书、指导书）
教材：
[1]严蔚敏,吴伟民.数据结构北京：
清华大学出版社.1997
参考书：
[2]SartajSahni.DataStructure,Algorithms,andApplicationinC++.TheMcGraw-HillCompanyInc.1998[M]（第一版>（数据结构、算法与应用——C++语言描述.北京:
机械工业出版社.1999
[3]WillanFord,WillianTopp.DataStructureswithC++.NewJersey:
PrenticeHallInc,AdivisionSimon&SchusterCompany,1996[M]（第一版>（数据结构——C++语言描述.北京:
清华大学出版社，1997
[4]徐孝凯.数据结构实用教程北京:
清华大学出版社.1999
[5]陈慧南.数据结构<使用C++语言描述）[M].（第一版>南京:
东南大学出版社.2001
[6]殷人昆,陶永雷,谢若阳等.数据结构<用面向对象方法与C++描述）[M].（第一版>北京:
清华大学出版社.1999
执笔人：
祁文青审核人：
祁文青<盖章）
2008年9月1日
附录1：
验证性实验报告模板
验证性实验一线性表的顺序存储实验
实验课程名：
数据结构
专业班级：
学号：
姓名：
实验时间：
实验地点：
指导教师：
一、实验目的和要求
二、实验内容
任务1**********<任务名称）
1、实验内容<写出简要原理、公式及其应用条件等，若无，可只写实验内容）
<1）
<2）
<3）
2、实验步骤<写出实验操作的总体思路、操作规范和操作主要注意事项，准确无误地记录原始数据。
若为程序设计类课程，要求写出核心代码）
<1）
<2）
<3）
3、实验结果与分析<明确地写出最后结果，并对自己得出的结果进行具体、定量的结果分析，说明其可靠性；杜绝只罗列不分析）
任务2**********<任务名称）
三、结论<写本次实验的收获）
四、教师批阅及成绩：
日期：
说明：
1.验证性实验报告填写好后，以学生的学号+实验工程名作为该word文件名保存，例如某学生学号为20080001，姓名为某某，本次实验名称是：
实验1线性表的顺序存储实验，则本次实验报告的保存文件名为：
01某某验证性实验1.doc。
2.在规定的时间内，学生将本报告提交给实验指导教师。
3.实验教师批改收到的实验报告后，将发还给学生。
附录2：
设计性实验报告模板
设计性实验二线性表的逆置
实验课程名：
数据结构
专业班级：
学号：
姓名：
实验时间：
实验地点：
指导教师：
一．实验任务：
设有一个线性表线性表中的数据可以为整数、字符或字符串，试分别采用顺序存储结构和链式结构来实现。
二．实验任务的子任务：
本人设计线性表中的数据类型为字符串，采用链式存储结构实现
三．算法分析（如图>：
文字或流程图或画图说明都可
四．源代码：
1.链表转置算法
voidtranspose（LinkList&l>//转置带头结点的链表
{
LinkListp,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.定义链表
typedefcharelemtype[10]。
//定义字符串
typedefstructLNode
{
elemtypedata。
structLNode*next。
}LNode,*LinkList。
voidCreateList_l（LinkList&L>//带头结点的链表
{
L=（LinkList>malloc（sizeof（LNode>>。
LinkListp,q。
elemtypei。
L->next=NULL。
q=L。
while（strcmp（i,"*">!
=0>
{
p=（LinkList>malloc（sizeof（LNode>>。
cin>>i。
if（strcmp（i,"*">!
=0>//结束数据输入时，用到库函数strcmp（>
{
p->next=q->next。
q->next=p。
q=p。
strcpy（q->data,i>。
}
}
}
3.链表输出：
voiddisplay（LinkList&L>
{
LinkListp。
p=L->next。
while（p!
=NULL>
{
cout<data<<""。
p=p->next。
}
cout<}
运行结果：
五．提问与回答：
1.老师提问：
可否将数据类型改为结构体类型？
回答：
上述代码做如下更改：
（1>定义结构体：
typedefstructstudent
{
charname[10]。
intage。
floatscore。
}elemtype。
（2>建立链表的时候，代码如下：
voidCreateList_l（LinkList&L>//带头结点的链表
{
L=（LinkList>malloc（sizeof（LNode>>。
LinkListp,q。
elemtypei。
L->next=NULL。
q=L。
while（strcmp（i.name,"*">!
=0>
{
p=（LinkList>malloc（sizeof（LNode>>。
cin>>i.name>>i.age>>i.score。
if（strcmp（i.name,"*">!
=0>
{
p->next=q->next。
q->next=p。
q=p。
strcpy（（q->data>.name,i.name>。
（q->data>.age=i.age。
（q->data>.score=i.score。
}
}
}
（3>链表输出代码如下：
voiddisplay（LinkList&L>
{
LinkListp。
p=L->next。
while（p!
=NULL>
{
cout<<（p->data>.name<<""<<（p->data>.age<<""<<（p->data>.score<<""<p=p->next。
}
cout<}
（4>运行结果：
2.老师提问：
不同类型的数据，输入与输出的语句不同，可不可以定义不同的方法，在对相应类型数据进行输入输出时，直接进行调用。
回答：
不同方法设置如下：
（1）输入方法：
字符型，整型，字符串型数据的输入代码：
voidInput（elemtype&i>
{
cin>>i。
}
结构体类型数据的输入代码
voidInput（elemtype&i>
{
cin>>i.name>>i.age>>i.score。
}
调用语句：
Input（i>。
（2）输出代码：
字符型，整型，字符串型数据的输入代码
voidOutput（LinkList&p>
{
cout<data<<""。
}
结构体类型数据的输入代码
voidOutput（LinkList&p>
{
cout<<（p->data>.name<<""<<（p->data>.age<<""<<（p->data>.score
<<""<}
调用语句：
Output（i>。
3.同学提问：
你的链表逆置后，原来的链表不存在了，请问能否不破坏原来链表的结构，重新生成一个逆置的单链表？
实验结论:
教师批阅及成绩：
指导教师签名：
日期：
说明：
1.设计性实验报告写好后，以学生的学号+实验工程名作为该word文件名保存，例如某学生学号为20080001，姓名为某某，本次实验名称是：
线性表的逆置，则本次实验报告的保存文件名为：
01某某线性表的逆置.doc。
2.在规定的时间内，学生将本报告提交给实验指导教师。
升级会员 