《数据结构课程实验》大纲一、《数据结构课程实验》的地位与作用“数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。

本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。

本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。

由于以下原因，使得掌握这门课程具有较大的难度：（1）内容丰富，学习量大，给学习带来困难；（2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点；（3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度；（4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。

根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。

通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。

实验学时为18。

二、《数据结构课程实验》的目的和要求不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。

实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。

为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。

数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。

在掌握基本算法的基础上，掌握分析、解决实际问题的能力。

三、《数据结构课程实验》内容课程实验共18学时，要求完成以下六个题目：实习一约瑟夫环问题（2学时）用循环链表实现约瑟夫环问题，熟悉链表结构的使用。

实习二停车场管理（4学时）利用栈和队列模拟停车场管理，学习利用栈和队列解决实际问题。

实习三二叉树基本操作（3学时）创建、遍历、插入、删除、显示二叉树，通过二叉树的基本操作，掌握树结构的处理方法。

实习四图的基本操作（3学时）分别用邻接矩阵和邻接表实现以下操作：图的创建、遍历、插入、删除、最短路径。

熟悉图的常用存储结构和基本操作。

实习五哈希表设计（3学时）给定30个人的姓名，用除留余数法构造哈希函数，用线性探测再散列法处理冲突，构造哈希表，掌握哈希表的设计与使用。

实习六常用排序算法的对比分析（3学时）分别实现直接插入排序、冒泡排序、简单选择排序、希尔排序、快速排序、堆排序，并随机生成30个数，比较各算法的时、空性能和稳定性。

掌握常用排序算法的特点，以便根据实际情况选择使用。

四、《数据结构课程实验》考核方式采用上机情况、程序质量、实习报告相结合的形式，满分为100分。

1．上机情况（30%）包括出勤情况、调试表现、是否上网、玩游戏。

2．程序质量（50%）3．实习报告（20%）实习一线性表本次实习的主要目的在于熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉各种链表的操作为侧重点。

通过本次实习还可帮助读者复习高级语言的使用方法。

约瑟夫环[问题描述]约瑟夫（Joeph）问题的一种描述是：编号为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）。

[实现提示]程序运行后首先要求用户指定初始报数上限值，然后读取各人的密码。

设n≤30。

[选作内容]向上述程序中添加在顺序结构上实现的部分。

长整数运算[问题描述]设计一个程序实现两个任意长的整数求和运算。

[基本要求]利用双项循环链表实现长整数的存储，每个结点含一个整型变量。

任何整型变量的范围是-（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）每个结点中可以存放的最大整数为215-1=32767，才能保证两数相加不会溢出。

但若这样存，即相当于按32768进制数存，在十进制数与32768进制数之间的转换十分不方便。

故可以在每个结点中仅存十进制数的4位，即不超过9999的非负整数，整个链表视为万进制数。

（2）可以利用头结点数据域的符号代表长整数的符号。

用其绝对值表示元素结点数目。

相加过程中不要破坏两个操作数链表。

两操作数的头指针存于指针数组中是简化程序结构的一种方法。

不能给长整数位数规定上限。

[选作内容]修改上述程序，使它在整型量范围是-（2n-1）~（2n-1）的计算机上都能有效地运行。

其中，n是由程序读入的参量。

输入数据的分组方法可以另行规定。

实习二栈、队列与递归算法设计仅仅认识到栈和队列是两种特殊的线性表是远远不够的，本次实习的目的在于使读者深入了解栈和队列的特征，以便在实际问题背景下灵活运用它们；同时还将巩固这两种结构的构造方法，接触较复杂问题的递归算法设计。

停车场管理[问题描述]设停车场内只有一个的停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。

汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。

试为停车场编制按上述要求进行管理的模拟程序。

[测试数据]设n=2,输入数据为：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3， 20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。

其中，‘A’表示到达；‘D’表示离去，‘E’表示输入结束。

[基本要求]以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。

每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。

栈以顺序结构实现，队列以链表实现。

[实现提示]需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。

输入数据按到达或离去的时刻有序。

栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。

[选作内容]（1）两个栈共享空间，思考应开辟数组的空间是多少？（2）汽车可有不同种类，则它们的占地面积不同，收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。

（3）汽车可以直接从便道上开走，此时派在它前面的汽车要先开走让路，然后再依次排到队尾。

（4）停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。

实习三串及其应用本次实习的目的是熟悉串类型的实现方法和文本模式匹配方法，熟悉一般文字处理软件的设计方法，较复杂问题的分解求精方法，在第二次实习的基础上，进一步强化这样一个观念：程序是数据结构结合定义在其上的操作，此外还希望起到训练合作能力和熟悉文件操作的目的。

本次实习的难度较大。

文学研究助手[问题描述]文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。

试写一个实现这一目标的文字统计系统，称为“文学研究助手”。

[基本要求]英文小说存于一个文本文件中。

待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。

程序的输出结果是每个词的出现次数和出现位置所在行的行号，格式自行设计。

[测试数据]以你的源程序模拟英文小说，程序语言保留字集作为待统计的词汇集。

[实现提示]设小说中的词汇一律不跨行。

这样，每读入一行，就统计每个词在这行中的出现次数。

出现位置所在行的行号可以用链表存储。

若某行中出现了不止一次，不必存多个相同的行号。

如果读者希望达到选作部分（1）和（2）所提出的要求，则首先应把KMP算法改写成如下的等价形式，再将它推广到多个模式的情形。

[选作内容]（1）模式匹配要基于KMP算法。

（2）整个统计过程中只对小说文字扫描一遍以提高效率。

（3）假设小说中的每个单词或者从行首开始，或者前置以一个空格符。

利用单词匹配特点另写一个高效的统计程序，与KMP算法统计程序进行效率比较。

（4）推广到更一般的模式集匹配问题，并设待查模式串可以跨行（提示：定义操作getachar）简单行编辑程序[问题描述]文本编辑程序是利用计算机进行文字加工的基本软件工具，实现对文本文件的插入、删除等修改操作。

限制这些操作以行为单位进行的编辑程序称为行编辑程序。

被编辑的文本文件可能很大，全部读入编辑程序的数据空间（内存）的做法既不经济，也不总能实现。

一种解决方法是逐段地编辑。

任何时刻只把待编辑文件的一段放在内存，称为活区。

试按照这种方法实现一个简单的行编辑程序。

设文件每行不超过320个字符，很少超过80字符。

[基本要求]实现以下4条基本编辑命令：（1）行插入。

格式：i<行号><回车><文本><回车>将<文本>插入活区中第<行号>行之后（2）行删除。

格式：d<行号1>[□<行号2>]<回车>删除活区中第<行号1>行（到第<行号2>行）。