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

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

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

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

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

5、情况、调试表现、是否上网、玩游戏。2 程序质量（ 50%）3 实习报告（ 20%）数据结构课程实验指导书实习一 线性表本次实习的主要目的在于熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉各种链表的操作为侧重点。通过本次实习还可帮助读者复习高级语言的使用方法。1、城市链表 问题描述 将若干城市的信息， 存入一个带头结点的单链表。结点中的城市信息包括：城市名，城 市的位置坐标。要求能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。 基本要求 （ 1） 给定一个城市名，返回其位置坐标；（2）给定一个位置坐标 P和一个距离D,返回所有和P的距离小于等于 D的城市。 测试数据 由学生

6、依据软件工程的测试技术自己确定。注意测试边界数据。2、约瑟夫环 问题描述 约瑟夫（Joeph）问题的一种描述是：编号为1,2,n的n个人按顺时针方向围坐一圈， 每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值 m,从第一个人开始 按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的 m值，从他在顺时针方向上的下一个人开始重新从 1报数，如此下去，直至所有人全部出列 为止。试设计一个程序求出出列顺序。 基本要求 利用单向循环链表存储结构模拟此过程,按照出列的顺序印出各人的编号。 测试数据 m的初值为20;密码：3, 1, 7, 2, 4, 8, 4 （正

7、确的结果应为 6, 1, 4, 7, 2, 3, 5）。 实现提示 程序运行后首先要求用户指定初始报数上限值，然后读取各人的密码。设nW 30。 选作内容 向上述程序中添加在顺序结构上实现的部分。3、线性表的逆置 问题描述 分别以不同存储结构实现线性表的就地逆置。 线性表的就地逆置就是在原表的存储空间内将线性表（a1,a2,a3,an）逆置为（ an, an-1，a2, al）。 基本要求 用顺序存储结构实现线性表的就地逆置,并将结果输出。 测试数据 由学生依据软件工程的测试技术自己确定。注意测试边界数据,如空表。 实现提示 设三个连续的指针,分别指向当前结点、当前结点的前趋、当前结点的后继。

8、 选作内容 利用单链表作为存储结构。 首先先建立线性表的带头结点的单链表表示形式, 之后在不 借助辅助结点空间的情况下实现单链表的逆置,并将结果输出。4、长整数运算 问题描述 设计一个程序实现两个任意长的整数求和运算。 基本要求 利用双项循环链表实现长整数的存储, 每个结点含一个整型变量。 任何整型变量的范围 是 -（215-1 ） （215-1 ）。输入和输出形式：按中国对于长整数的表示习惯,每四位一组, 组间用逗号隔开。 测试数据 （1）0 ；0；应输出“ 0”。（2）-2345,6789 ；-7654,3211 ；应输出“ -1,0000,0000”。（3）-9999,9999 ；1,0

9、000,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） 可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示

10、元素结点数目。相加过程中不要破坏两个操作数链表。 两操作数的头指针存于指针数组中是简化程序结构的 一种方法。不能给长整数位数规定上限。 选作内容 修改上述程序,使它在整型量范围是 - （ 2n-1 ） （ 2n-1 ）的计算机上都能有效地运行。 其中, n 是由程序读入的参量。输入数据的分组方法可以另行规定。实习二 栈、队列和递归算法设计仅仅认识到栈和队列是两种特殊的线性表是远远不够的, 本次实习的目的在于使读者深 入了解栈和队列的特征, 以便在实际问题背景下灵活运用它们； 同时还将巩固这两种结构的 构造方法,接触较复杂问题的递归算法设计。1 、数制转换问题 问题描述 将十进制数N和其它d进制

11、数的转换是计算机实现计算的基本问题，其解决方案很多, 其中最简单方法基于下列原理：即除 d 取余法。例如： （1348）10=（2504）8NN div 8N mod 8134816841682102125202从中我们可以看出，最先产生的余数 4 是转换结果的最低位， 这正好符合栈的特性即后进先出的特性。所以可以用顺序栈来模拟这个过程。 基本要求 对于键盘输入的任意一个非负的十进制整数， 打印输出和其等值的八进制数。 由于上述 的计算过程是从低位到高位顺序产生的八进制数的各个数位，而打印输出， 一般来说应从高位到地位进行， 恰好和计算过程相反。 因此可以先将计算过程中得到的八进制数的各位进栈

12、， 待相对应的八进制数的各位均产生以后， 再使其按顺序出栈， 并打印输出。 即得到了和输入 的十进制数相对应的八进制数。 测试数据 由学生依据软件工程的测试技术自己确定。注意测试边界数据。2、回文判断 问题描述 试写一个算法，判断依次读入的一个以为结束符的字母序列，是否为形如序列1 &序列 2'模式的字符序列。其中序列1和序列 2 中都不含字符 &'，且序列 2 是序列 1的逆序列。例如， a+b&b+a是属该模式的字符序列，而1+3 &3 1'则不是。 实现提示 首先，序列 1 进栈，然后序列 1 出栈并和序列 2 比较。 测试数据 由

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

14、用“期待的紧迫程度”这个概念来描述。例如：考虑下列的括号序列： （ ） 1 2 3 4 5 6 7 8当计算机接受了第 1 个括号以后， 他期待着和其匹配的第 8 个括号的出现， 然而等来的 却是第 2个括号，此时第 1个括号“ ”只能暂时靠边， 而迫切等待和第 2 个括号相匹配的 第 7 个括号“）”的出现，类似的，因只等来了第3 个括号“ ”，此时，其期待的紧迫程度较第2个括号更紧迫， 则第2个括号只能靠边， 让位于第 3个括号，显然第 3个括号的期待 紧迫程度高于第 2 个括号，而第 2 个括号的期待紧迫程度高于第 1 个括号；在接受了第 4 个括号之后， 第 3个括号的期待得到了满足，

15、 消解之后， 第 2个括号的期待匹配就成了最急 迫的任务了，依次类推。可见这个处理过程正好和栈的特点相吻合。 基本要求 读入圆括号和方括号的任意序列，输出“匹配”或“此串括号匹配不合法”。 测试数据 输入（ （），结果“匹配”输入 （ ） ，结果“此串括号匹配不合法” 实现提示 设置一个栈，每读入一个括号，若是左括号，则作为一个新的更急迫的期待压入栈中； 若是右括号， 并且和当前栈顶的左括号相匹配， 则将当前栈顶的左括号退出， 继续读下一个 括号， 如果读入的右括号和当前栈顶的左括号不匹配， 则属于不合法的情况。 在初始和结束 时，栈应该是空的。 选作内容 考虑增加大括号的情况。5、停车场管理

16、 问题描述 设停车场内只有一个可停放 n 辆汽车的狭长通道， 且只有一个大门可供汽车进出。 汽车 在停车场内按车辆到达时间的先后顺序， 依次由北向南排列 （大门在最南端， 最先到达的第 一辆车停放在车场的最北端） ，若车场内已停满 n 辆汽车，则后来的汽车只能在门外的便道 上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时， 在它之后开入的车辆必须先退出车场为它让路， 待该辆车开出大门外， 其它车辆再按原次序 进入车场， 每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 测试数据 设 n=2,输入数据为：

17、（ 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'表示输入结束。 基本要求 以栈模拟停车场, 以队列模拟车场外的便道, 按照从终端读入的输入数据序列进行模拟 管理。 每一组输入数据包括三个数据项： 汽车“到达”

18、或“离去”信息、 汽车牌照号码及到 达或离去的时刻, 对每一组输入数据进行操作后的输出数据为： 若是车辆到达, 则输出汽车 在停车场内或便道上的停车位置； 若是车离去； 则输出汽车在停车场内停留的时间和应交纳 的费用（在便道上停留的时间不收费） 。栈以顺序结构实现,队列以链表实现。 实现提示 需另设一个栈, 临时停放为给要离去的汽车让路而从停车场退出来的汽车,也用顺序存 储结构实现。 输入数据按到达或离去的时刻有序。 栈中每个元素表示一辆汽车， 包含两个数 据项：汽车的牌照号码和进入停车场的时刻。 选作内容 （ 1） 两个栈共享空间，思考应开辟数组的空间是多少？（ 2） 汽车可有不同种类，则它

19、们的占地面积不同，收费标准也不同，如1 辆客车和1.5 辆小汽车的占地面积相同， 1 辆十轮卡车占地面积相当于 3 辆小汽车的占地面积。（ 3） 汽车可以直接从便道上开走， 此时排在它前面的汽车要先开走让路，然后再依次 排到队尾。（ 4） 停放在便道上的汽车也收费， 收费标准比停放在停车场的车低， 请思考如何修改 结构以满足这种要求。实习三 串及其使用本次实习的目的是熟悉串类型的实现方法和文本模式匹配方法， 熟悉一般文字处理软件 的设计方法， 较复杂问题的分解求精方法， 在第二次实习的基础上， 进一步强化这样一个观 念：程序是数据结构结合定义在其上的操作， 此外还希望起到训练合作能力和熟悉文件

20、操作 的目的。本次实习的难度较大。1、文学研究助手 问题描述 文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。 试写一个实现这 一目标的文字统计系统，称为“文学研究助手”。 基本要求 英文小说存于一个文本文件中。 待统计的词汇集合要一次输入完毕， 即统计工作必须在 程序的一次运行之后就全部完成。 程序的输出结果是每个词的出现次数和出现位置所在行的 行号，格式自行设计。 测试数据 以你的源程序模拟英文小说，程序语言保留字集作为待统计的词汇集。 实现提示 设小说中的词汇一律不跨行。这样，每读入一行，就统计每个词在这行中的出现次数。 出现位置所在行的行号可以用链表存储。 若某行中出现了

21、不止一次， 不必存多个相同的行号。如果读者希望达到选作部分（1 ）和（2）所提出的要求，则首先应把 KMP算法改写成如 下的等价形式，再将它推广到多个模式的情形。 选作内容 （1）模式匹配要基于 KMP算法。（ 2） 整个统计过程中只对小说文字扫描一遍以提高效率。（ 3） 假设小说中的每个单词或者从行首开始，或者前置以一个空格符。利用单词匹配 特点另写一个高效的统计程序，和KMP算法统计程序进行效率比较。（ 4） 推广到更一般的模式集匹配问题，并设待查模式串可以跨行（提示：定义操作 getachar ）2、简单行编辑程序 问题描述 文本编辑程序是利用计算机进行文字加工的基本软件工具，实现对文本

22、文件的插入、 删除等修改操作。限制这些操作以行为单位进行的编辑程序称为行编辑程序。被编辑的文本文件可能很大，全部读入编辑程序的数据空间（内存）的做法既不经济， 也不总能实现。 一种解决方法是逐段地编辑。 任何时刻只把待编辑文件的一段放在内存， 称 为活区。 试按照这种方法实现一个简单的行编辑程序。 设文件每行不超过 320 个字符， 很少 超过 80 字符。 基本要求 实现以下 4 条基本编辑命令：(1) 行插入。格式： i 行号回车文本回车 将文本 插入活区中第 行号行之后(2) 行删除。格式：d行号1 行号2回车删除活区中第 行号1行(到第 行号2行)。两种格式的例子是：“ d10/”和“

23、 d10口 14/”(3) 活区切换。格式： *回车将活区写入输出文件，并从输入文件中读入下一段，作为新的活区。(4) 活区显示。格式：p回车逐页地(每页 20 行)显示活区内容，每显示一页之后请用户决定是否继续显示以后各 页(如果存在) 。印出的每一行要前置以行号和一个空格符，行号固定占4 位，增量为 1。各条命令中的行号均须在活区中各行行号范围之内， 只有插入命令的行号可以等于活区 第一行行号减 1，表示插入当前屏幕中第一行之前，否则命令参数非法。 测试数据 由学生依据软件工程的测试技术自己确定。注意测试边界数据，如首行、尾行。 实现提示 (1) 设活区的大小用行数 activemaxle

24、n (可设为 100)来描述。考虑到文本文件行长通常为正态分布，且峰值在60到70之间，用320x activemaxlen 大小的字符数组实现存储 将造成大量浪费。可以以标准行块为单位为各行分配存储，每个标准行块含81 个字符。这些行块可以组成一个数组， 也可以利用动态链表连接起来。 一行文字可能占多个行块。 行尾 可用一个特殊的 ASCII 字符(如 (012)8 )标识。此外，还应记住活区起始行号。行插入将引 起随后各行行号的顺序下推。( 2) 初始化过程包括： 请用户提供输入文件名 (空串表示无输入文件) 和输出文件名， 两者不能相同。然后尽可能多地从输入文件中读入各行，但不超过act

25、ivemaxlen-x °x的值可以自定，例如 20。( 3) 在执行行插入命令的过程中，每接收到一行时到要检查活区大小是否已达 activemaxlen 。如果是，则为了在插入这一行之后仍保持活区大小不超过activemaxlen ，应将插入点之前的活区部分中第一行输出到输出文件中； 若插入点为第一行之前， 则只得将 新插入的这一行输出。( 4) 若输入文件尚未读完，活区切换命令可将原活区中最后几行留在活区顶部，以保持阅读连续性；否则，它意味着结束编辑或开始编辑另一个文件。( 5) 可令前三条命令执行后自动调用活区显示。 选作内容 ( 1 ) 对于命令格式非法等一切错误作严格检查和

26、适当处理。(2) 加入更复杂的编辑操作，如对某行进行串替换；在活区内进行模式匹配等，格式可以为S亍号串1串 2回车和口串 回车。实习四 树、图及其使用树和图是两种使用极为广泛的数据结构， 也是这门课程的重点。 它们的特点在于非线性。广义表本质上是树结构；稀疏矩阵的十字链表存储结构也是图的一种存储结构，故也把它们归在这次实习中。本章实习继续突出了数据结构加操作的程序设计观点，但根据这两种结构的非线性特点，将操作进一步集中在遍历操作上，因为遍历操作是其他众多操作的基础。遍历逻辑的（或符号形式的）结构，访问动作可是任何操作。本次实习还希望达到熟悉各种存 储结构的特征，以及如何使用树和图结构解决具体问

27、题（即原理和使用的结合）等目的。1、二叉树的建立和遍历问题描述建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。基本要求从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。测试数据ABG © DE©F© ©© （其中©表示空格字符）则输出结果为先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA选作内容采用非递归算法实现二叉树遍历。2、打印树结构问题描述按凹入表形式打印树形结构。CFEADB测试数据由学生依据软件工程

28、的测试技术自己确定。注意测试边界数据，如空树。 实现提示（1）利用树的先根遍历方法；（2）禾U用结点的深度控制横向位置。3、哈夫曼编码/译码器重复地显示并处理以下项目，直到选择退出为【问题描述】 设计一个利用哈夫曼算法的编码和译码系统， 止。【基本要求】(1) 初始化：键盘输入字符集大小 n、n个字符和n个权值，建立哈夫曼树；(2) 编码：利用建好的哈夫曼树生成哈夫曼编码；(3) 输出编码；(4) 设字符集及频度如下表：字符 空格 A B C D E F G H I J K L M频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 N O P Q R

29、S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 【选做内容】(1) 译码功能；(2) 显示哈夫曼树；(3) 界面设计的优化。4、图遍历的演示 问题描述 很多涉及图上操作的算法都是以图的遍历操作为基础的。 试写一个程序， 演示无向图的 遍历操作。 基本要求 以邻接表为存储结构， 实现连通无向图的深度优先和广度优先遍历。 以用户指定的结点 为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。 测试数据 由学生依据软件工程的测试技术自己确定。注意测试边界数据，如单个结点。 实现提示 设图的结点不超过 30 个，每个结点用一个编号表示

30、(如果一个图有 n 个结点，则它们 的编号分别为1,2,n )。通过输入图的全部边输入一个图，每个边为一个数对，可以对边 的输入顺序作出某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。 选作内容 (1) 借助于栈类型(自己定义和实现)将深度优先遍历用非递归算法实现。( 2) 以邻接多重表为存储结构建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树(3) 实现有向图的遍历操作。实习五 查找和排序本次实习旨在集中对几个专门的问题作较为深入的探讨和理解，不强调对某些特定的编程技术的训练。1 、二叉排序树 问题描述 从键盘读入一组数据， 建立二叉排序树并对其进行查找、 遍历、格式化打

31、印等有关操作。 基本要求 建立二叉排序树并对其进行查找，包括成功和不成功两种情况，并给出查找长度。 测试数据 由学生依据软件工程的测试技术自己确定。注意测试边界数据。 选作内容 实现二叉排序树的插入、删除操作。2、哈希表设计 问题描述 针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R,并完成相应的建表和查表程序。 基本要求 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30 个，取平均查找长度的上限为 2。哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。 测试数据 取读者周围较熟悉的 30 个人名。 选作内容 （1）从教科书上介绍的集中哈希函数构造方法中选

32、出适用者并设计几个不同的哈希函 数，比较他们的地址冲突率（可以用更大的名字集合作实验） 。（2）研究这 30 个人名的特点，努力找一个哈希函数，使得对于不同的拼音名一定不 发生地址冲突。（3） 在哈希函数确定的前提下尝试各种不同处理冲突的方法，考察平均查找长度的变 化和造好的哈希表中关键字的聚集性。3、内部排序算法比较 问题描述 各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时 间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。 基本要求 （1）对以下 10 种常用的内部排序算法进行比较：直接插入排序；折半折入排序；二 路插入排序；希尔排

33、序；起泡排序；快速排序；简单选择排序；堆排序；归并排序；基数排 序。（2）待排序表的表长不少于 100；其中的数据要用伪随机数产生程序产生；至少要用5 组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字移动次数（关 键字交换计为 3 次移动）。 测试数据 由随机产生器决定。 实现提示 主要工作是设法在程序中适当的地方插入计数操作。 程序还可以包括计算几组数据得出 结果波动大小的解释。注意分块调试的方法。 选作内容 对不同的输入表长做试验， 观察检查两个指标相关于表长的变化关系。 还可以对稳定性 做验证。3、统计成绩 问题描述 给出n个学生的m门测试的成绩表，每个学生的信息由学号

34、、姓名以及各科成绩组成。 对学生的测试成绩进行有关统计，并打印统计表。 基本要求 （1）按总数高低次序，打印出名次表，分数相同的为同一名次；（2）按名次打印出每个学生的学号、姓名、总分以及各科成绩。 测试数据 由学生依据软件工程的测试技术自己确定。注意测试边界数据。 选作内容 对各科成绩设置不同的权值。附录 2 实验报告示例级 班 年 月日 姓名 学号 电话1实验题目编制一个演示单链表插入、删除、查找等操作的程序2需求分析本演示程序用TC编写，完成单链表的生成，任意位置的插入、删除，以及确定某一元 素在单链表中的位置。 输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元

35、素时输入删除元素的位置； 查找操作时需要输入元素的值。 在所有输入中， 元素的值都是整 数 输出的形式：在所有三种操作中都显示操作是否正确以及操作后单链表的内容。其 中删除操作后显示删除的元素的值，查找操作后显示要查找元素的位置。 程序所能达到的功能：完成单链表的生成(通过插入操作) 、插入、删除、查找操作 测试数据：A 插入操作中依次输入B 查找操作中依次输入C 删除操作中依次输入11， 12， 13， 14， 15， 16，生成一个单链表12， 15， 22 返回这 3 个元素在单链表中的位置2， 5，删除位于 2 和 5 的元素3概要设计1) 为了实现上述程序功能，需要定义单链表的抽象数

36、据类型：ADT LinkList 数据对象：D=ai|ai IntegerSet,i=0,1,2,n,n > 0数据关系：R=<ai,ai+1>|ai,ai+1 D基本操作：InitLinkList(&L)操作结果：构造一个空的单链表 L.InsLinkList(&L,pos,e)初始条件：单链表 L 已存在操作结果：将元素 e插入到单链表L的pos位置DelLinkList(&L,pos,&e)初始条件：单链表 L 已存在操作结果：将单链表 L 中 pos 位置的元素删除， 元素值置入 e 中返回LocLinkList(L,e)初始条件：单链表 L 依存在操作结果：单链表 L 中查找是否元素 e，若存在，返回元素在表中的位置；若不存在，返回 -1.Menu()操作结果：在屏幕上显示操作菜单2) 本程序包含7个函数： 主函数 main() 初始化单链表函数InitLinkList() 显示操作菜单函数menu() 显示单链表内容函数dispLinkList() 插入元素函数InsLinkList() 删除元素函数DelLinkList() 查找元素函数LocLinkList()各函数间关系如下：mainInitLinkListJlenuDispLinkList InsLinkListDelLinkList L