《数据结构课程实验》大纲

《《数据结构课程实验》大纲》由会员分享，可在线阅读，更多相关《《数据结构课程实验》大纲（16页珍藏版）》请在金锄头文库上搜索。

1、数据结构课程实验大纲 一、 数据结构课程实验的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。由于以下原因，使得掌握这门课程具有较大的难度：（1） 内容丰富，学习量大，给学习带来困难；（2） 贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点；（3） 所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习

2、难度；（4） 隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据数据结构课程课程本身的技术特性，设置数据结构课程实验实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为10。二、数据结构课程实验的目的和要求不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，

3、要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。三、 数据结构课程实验内容课程实验共10学时，要求完成以下五个题目：实习一 约瑟夫环问题（2学时）用循环链表实现约瑟夫环问题，熟悉链表结构的使用。实习二 八皇后问题 （2学时） 在88的棋盘上放置彼此不受攻击的8个

4、皇后，熟悉递归与回溯程序设计方法。实习三 二叉树基本操作（2学时）创建、遍历、显示二叉树，通过二叉树的基本操作，掌握树结构的处理方法。实习四 哈夫曼编码与译码针对字符集A及其各字符的频率值（可统计获得）给出其中给字符哈夫曼编码，并针对一段文本（定义在A上）进行编码和译码，实现一个哈夫曼编码/译码系统。实习五 最小生成树问题（2学时）在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。 四、 数据结构课程实验考核方式采用上机情况、程序质量、实习报告相结合的形式，满分为100分。1 上机情况（30%）包括出勤情况、调试表现、是否上网、玩游戏。2 程序质量（50%）3 实习报告（20%）数

5、据结构课程实验指导书实习一 线性表本次实习的主要目的在于熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉各种链表的操作为侧重点。通过本次实习还可帮助读者复习高级语言的使用方法。 1、城市链表问题描述将若干城市的信息，存入一个带头结点的单链表。结点中的城市信息包括：城市名，城市的位置坐标。要求能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。基本要求（1） 给定一个城市名，返回其位置坐标；（2） 给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于D的城市。测试数据由学生依据软件工程的测试技术自己确定。注意测试边界数据。2、约瑟夫环问题描述约瑟夫（Joeph）问题的一种描

6、述是：编号为1,2,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。基本要求利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。测试数据m的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。实现提示程序运行后首先要求用户指定初始报数上限值，然后读取各人的密码。设n30。选作内容向上述程序

7、中添加在顺序结构上实现的部分。3、线性表的逆置问题描述分别以不同存储结构实现线性表的就地逆置。线性表的就地逆置就是在原表的存储空间内将线性表（a1,a2,a3,an）逆置为（an，an-1，a2，a1）。基本要求用顺序存储结构实现线性表的就地逆置，并将结果输出。测试数据由学生依据软件工程的测试技术自己确定。注意测试边界数据，如空表。实现提示设三个连续的指针，分别指向当前结点、当前结点的前趋、当前结点的后继。选作内容利用单链表作为存储结构。首先先建立线性表的带头结点的单链表表示形式，之后在不借助辅助结点空间的情况下实现单链表的逆置，并将结果输出。4、长整数运算问题描述设计一个程序实现两个任意长的

8、整数求和运算。基本要求利用双项循环链表实现长整数的存储，每个结点含一个整型变量。任何整型变量的范围是-（215-1）（215-1）。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。测试数据（1） 0；0；应输出“0”。（2） -2345,6789；-7654,3211；应输出“-1,0000,0000”。（3） -9999,9999；1,0000,0000,0000；应输出“9999,0000,0001”。（4） 1,0001,000；-1,0001,0001；应输出“0”。（5） 1,0001,0001；-1,0001,0000；应输出“1”。实现提示（1） 每个结点

9、中可以存放的最大整数为215-1=32767，才能保证两数相加不会溢出。但若这样存，即相当于按32768进制数存，在十进制数与32768进制数之间的转换十分不方便。故可以在每个结点中仅存十进制数的4位，即不超过9999的非负整数，整个链表视为万进制数。（2） 可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点数目。相加过程中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方法。不能给长整数位数规定上限。选作内容修改上述程序，使它在整型量范围是-（2n-1）（2n-1）的计算机上都能有效地运行。其中，n是由程序读入的参量。输入数据的分组方法可以另行规定。

10、实习二 栈、队列与递归算法设计仅仅认识到栈和队列是两种特殊的线性表是远远不够的，本次实习的目的在于使读者深入了解栈和队列的特征，以便在实际问题背景下灵活运用它们；同时还将巩固这两种结构的构造方法，接触较复杂问题的递归算法设计。 1、数制转换问题问题描述将十进制数N和其它d进制数的转换是计算机实现计算的基本问题，其解决方案很多，其中最简单方法基于下列原理：即除d取余法。例如：（1348）10=（2504）8NN div 8N mod 81348 168 416821021 2 520 2从中我们可以看出，最先产生的余数4是转换结果的最低位，这正好符合栈的特性即后进先出的特性。所以可以用顺序栈来模

11、拟这个过程。基本要求对于键盘输入的任意一个非负的十进制整数，打印输出与其等值的八进制数。由于上述的计算过程是从低位到高位顺序产生的八进制数的各个数位，而打印输出，一般来说应从高位到地位进行，恰好和计算过程相反。因此可以先将计算过程中得到的八进制数的各位进栈，待相对应的八进制数的各位均产生以后，再使其按顺序出栈，并打印输出。即得到了与输入的十进制数相对应的八进制数。测试数据由学生依据软件工程的测试技术自己确定。注意测试边界数据。2、回文判断问题描述试写一个算法，判断依次读入的一个以为结束符的字母序列，是否为形如序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&，且序列2是序列1的逆序

12、列。例如，a+b&b+a是属该模式的字符序列，而+&则不是。实现提示首先，序列1进栈，然后序列1出栈并与序列2比较。测试数据由学生依据软件工程的测试技术自己确定。注意测试边界数据，如序列1和序列2均为空串。3、商品货架管理问题描述商品货架可以看成一个栈，栈顶商品的生产日期最早，栈底商品的生产日期最近。上货时，需要倒货架，以保证生产日期较近的商品在较下的位置。基本要求针对一种特定商品，实现上述管理过程。实现提示用栈模拟货架和周转空间。测试数据由学生依据软件工程的测试技术自己确定。注意测试边界数据，如空栈。4、括号匹配的检验问题描述假设表达式中允许有两种括号：圆括号和方括号，其嵌套的顺序随意，即（

13、） ）或（ ）等为正确格式，（ ）或（均为不正确的格式。检验括号是否匹配的方法可用“期待的紧迫程度”这个概念来描述。例如：考虑下列的括号序列：()12345678当计算机接受了第1个括号以后，他期待着与其匹配的第8个括号的出现，然而等来的却是第2个括号，此时第1个括号“”只能暂时靠边，而迫切等待与第2个括号相匹配的 第7个括号“）”的出现，类似的，因只等来了第3个括号“”，此时，其期待的紧迫程度较第2个括号更紧迫，则第2个括号只能靠边，让位于第3个括号，显然第3个括号的期待紧迫程度高于第2个括号，而第2个括号的期待紧迫程度高于第1个括号；在接受了第4个括号之后，第3个括号的期待得到了满足，消解

14、之后，第2个括号的期待匹配就成了最急迫的任务了， ，依次类推。可见这个处理过程正好和栈的特点相吻合。基本要求读入圆括号和方括号的任意序列，输出“匹配”或“此串括号匹配不合法”。测试数据 输入（ （），结果“匹配”输入 （ ），结果“此串括号匹配不合法”实现提示设置一个栈，每读入一个括号，若是左括号，则作为一个新的更急迫的期待压入栈中；若是右括号，并且与当前栈顶的左括号相匹配，则将当前栈顶的左括号退出，继续读下一个括号，如果读入的右括号与当前栈顶的左括号不匹配，则属于不合法的情况。在初始和结束时，栈应该是空的。选作内容考虑增加大括号的情况。5、停车场管理问题描述设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路