数据结构与算法课程实习教师用指导书

1、数据结构与算法课程实习实验指导书（教师使用）海第二工业大学计算机与信息学院软件工程系1教学大纲.教学进程表.评分标准.实验内容.实验报告示例.实验报告封面、评语得分表.参考源代码.目录1518202数据结构与算法课程实习教学大纲Practice and Training of Data Structure and Algorithm B4031001248、课程性质与任务数据结构与算法课程实习作为数据结构与算法的后续课程，它既是对数据结构与算法 课程所学知识的巩固和充实， 又是对学生实际编程和程序调试能力的进一步培养 与提高，本课程是计算机科学与技术专业的重要教学环节。本课程以上机实践为主，

2、在教师的指导下，通过集中、适量的编程训练，使学生较牢固地掌握 数据结构与算法课程中基本算法的实际编程方法， 实际应用能力，为学习后续课程和今后从事相关工作打下坚实的基础。二、课程基本要求一）能较熟练地编写有关线性表、队列、栈等基本功能程序。二）能灵活运用线性表、队列、栈等基本功能程序，编写综合性的应用程序。三）掌握应用程序调试的一般方法。三、课程内容一）静态线性表功能程序组的编制与测试二）动态链表功能程序组的编制与测试三）二叉树功能程序组的编制与测试四）综合应用（选做）选择一个综合应用的题目，按要求设计应用程序；要求提供完整的设计文档，文档应包含需求分析、详细设计说明、调试分析、使用说 明以及

3、源程序等内容。重点：通过训练，加深对数据结构与算法中基本算法的理解，提高编程能力。难点：动态地址分配与指针操作，应用程序的设计。四、课程考核方式与要求检查作品、实习报告与重点提问相结合。自主完成必做题为及格标准。五、主要仪器设备及材料1. 每人 1 台计算机；英文译名：课程代码： 学分： 总学时数：加深对基本算法的理解， 提高32. Windows 2000 Profesional ;3. VC 6.0。六、本课程与其它课程的关系先修课程：程序设计基础、数据结构与算法。七、总学时和学时分配表1.总学时：482.学时分配表:序 号实践内容实验学时实验类型实验类别实验 要求1知识回顾，任务与要求1

4、2静态线性表功能程序组的编制与测试11设计专业基础必开3动态链表功能程序组的编制与测试12设计专业基础必开4二叉树功能程序组的编制与测试12设计专业基础必开5综合应用12设计专业基础必开小计48八、选用教材及主要参考书教 材：严蔚敏.数据结构题集，清华大学出版社,数据结构与算法课程实习指导书（自编）执笔教师：陶霖审核教师：教学院长：1999.24教学进程表学年第学期周 次日期授课章节与内容摘要学时数分配课外作业月日讲课实验上机大 作业18624知识回顾，任务与要求，静态线性表操作1725静态线性表操作，动态线性表操作826动态线性表操作827二叉树操作828二叉树操作，综合81971综合8合计

5、48数据结构题集（C 语言版）主编 严蔚敏、吴伟民、米宁出版社清华大学出版社系/教研室主任签名:课程名称数据结构与算法课程实习所属学院计算机与信息考试考查考查总课时48 周课时 24授课班级授课教师所属学院计算机与信息职称教材名称5数据结构与算法课程实习评分标准平时成绩:30%:30%期末成绩:70%:70%期末成绩有以下五部分组成顺序表的基本操作（2020分）1、2、3、4、5、6、7、8、实现顺序表显示； 1 分 实现顺序表插入； 1 分 实现顺序表查找（显示比较次数） 实现顺序表删除（显示移动次数）；1 分；1 分9、实现顺序表排序（分别实现简单选择、快速,显示比较次数、移动次数） 实现

6、顺序表的折半查找（显示比较次数）；2 分编程实现一个顺序表的就地逆置,即利用原表的存储空间将顺序表逆置；顺序表有序插入（显示比较次数、移动次数） , 屏幕提示后,从键盘输入一个元素值,在经过排序的线性表中插入这个元素； 屏幕显示比较次数和移动次数,应有溢出判断和报告； 3 分要求以较高的效率实现删除顺序表中元素值在x 到 y（x 和 y 自定）之间的所有元素；3 分；2 分3 分10、编程实现将两个非递减的顺序表进行合并,要求同样的数据元素只出现一次；3 分二、链表的基本操作（ 2020分）1、2、3、4、5、6、7、实现单链表的创建； 实现单链表的显示； 1 分 实现单链表的查找（显示比较次

7、数）实现单链表的插入； 2 分 实现单链表的删除（显示比较次数）；2 分；2 分对已创建的链表（数据不限）进行直接插入排序； 将链接存储线性表逆置，即最后一个结点变成第2 个结点，如此等等； 2 分8、 生成有序的两个单链表 A 和 B （链表的数据和个数自定），其首结点指针分别为 a 和 b, 要求将两个单链表合并为一个有序的单链表C,其首结点指针为 C,并且合并后的单链表的 数据不重复； 3 分9、 将一个首结点指针为 a 的单链表 A 分解成两个单链表 A 和 B，b,使得链表 A 中含有原链表 A 中序号为奇数的元素，而链表B偶数的元素，且保持原来的相对顺序；10、 请编程实现链栈的基

8、本操作函数, 的功能。 3 分2 分1 个结点，原来倒数第 2 个结点变成第3 分并通过调用这些基本函数，其首结点指针分别为 a 和 中含有原链表 A 中序号为实现十进制和八进制转换67、二叉树的基本操作（ 2020 分）1、实现二叉树的创建；2、用递归方法分别先序、中序、后序遍历以Tree 为根指针的二叉树；3、编写递归算法，计算二叉树中叶子结点的数目；2 分4、编写递归算法，计算二叉树的深度；2 分5、编写递归算法，将二叉树中所有结点的左、右子树相互交换；2 分6、使用数组 elem 中的随机数序列（以 0 表示结束，不包括 0），生成以 叉排序树；2 分7、在以 Tree 为根指针的二叉

9、排序树中查找结点；2 分8、从以 Tree 为根指针的二叉排序树中删除结点（适用各种位置的结点）9、 用非递归算法，先序遍历以Tree 为根指针的二叉树；2 分10、 用广义表表示以 Tree 为根指针的二叉树 1 分11、 对以 Tree 为根指针的二叉树，从根结点开始，逐层从左到右输出各结点的数据。2 分12、 根据 Huffman 编码原理，使用数组 elem 中的随机数序列（以 0 表示结束，不包括 0） 作为结点的权重，生成赫夫曼树，以及赫夫曼编码，计算平均带权径长度。2 分四、综合题（ 2020 分）没有完成设计给定要求 0-11 分 错误不算太多，大部分算法及实现程序都能通过 在

10、设计的算法和实现中有少量错误 14-15 算法和实现正确，对设计有一定改进和完善16-18 在设计中有创新 19-20五、实验报告（ 2020 分）不符合规范要求 0-11 符合规范要求，图表质量尚可 12-14 内容正确详尽 15-18 体会深刻，对系统设计有进一步思考注：第一至第三部分的各题小分可有教师选择题目后自行给出。1 分Tree 为根指针的二；2 分12-1319-208【实验目的】1、 掌握顺序存储的概念，学会对顺序表的基本操作。2、加深对顺序存储数据结构的理解，逐步培养解决实际问题的能力。实验性质】设计型实验实验内容】实现顺序表显示； 实现顺序表插入； 实现顺序表查找（显示比较

11、次数） ； 实现顺序表删除（显示移动次数） ； 实现顺序表选择排序（显示比较次数、移动次数） ； 实现顺序表快速排序（显示比较次数、移动次数） ； 实现顺序表的折半查找（显示比较次数） ； 编程实现一个顺序表的就地逆置，即利用原表的存储空间将顺序表逆置； 顺序表有序插入（显示比较次数、移动次数） ，屏幕提示后，从键盘输入一个元素值，在经过排序的线性表中插入这个元素； 屏幕显示比较次数和移动次数，应有溢出判断和报告；10、要求以较高的效率实现删除顺序表中元素值在x 到 y（x 和 y 自定 ）之间的所有元素；11、编程实现将两个非递减的顺序表进行合并，要求同样的数据元素只出现一次；12、编程实现

12、顺序表的 shell 排序（步长为 5，3， 1）；13、编程实现堆排序算法；14、利用三元组顺序表存储矩阵，实现矩阵的转置（请独立写程序实现）实验环境】VC+ 6.0实验要求】将如上文件保存在命名为 “学号+姓名 ”的文件夹中并上传到指定的服务器。注：教师可选择1010题左右为本次实验内容。实验顺序表的基本操作1、2、3、4、5、6、7、8、9、9【实验目的】1、 掌握链表的概念，学会对链表进行操作。2、 加深对链式存储结构的理解，逐步培养解决实际问题的编程能力。实验性质】设计型实验【实验内容】1、实现单链表的创建；2、实现单链表的显示；3、实现单链表的查找（显示比较次数） ；4、实现单链表

13、的插入；5、实现单链表的删除（显示比较次数） ；6、对已创建的链表（数据不限）进行直接插入排序；7、 将链接存储线性表逆置,即最后一个结点变成第1 个结点,原来倒数第 2 个结点变 成第 2个结点,如此等等；8、 生成有序的两个单链表A 和 B （链表的数据和个数自定）和 b，要求将两个单链表合并为一个有序的单链表C，其首结点指针为链表的数据不重复；9、将一个首结点指针为 a 的单链表 A 分解成两个单链表 A 和 B， a 和 b，使得链表 A 中含有原链表 A 中序号为奇数的元素，而链表 B 号为偶数的元素，且保持原来的相对顺序；10、 请编程实现链栈的基本操作函数，并通过调用这些基本函数

14、， 转换的功能。实验环境】VC+ 6.0实验要求】将如上文件保存在命名为 “学号+姓名 ”的文件夹中并上传到指定的服务器。实验链表的基本操作，其首结点指针分别为 ac,并且合并后的单其首结点指针分别为中含有原链表 A 中序实现十进制和八进制10实验三叉树的基本操作【实验目的】1、 掌握二叉树的概念，学会对二叉链表进行操作。2、 加深对链式存储结构的理解，逐步培养解决实际问题的编程能力。实验性质】设计型实验【实验内容】1、实现二叉树的创建；2、用递归方法分别先序、中序、后序遍历以Tree 为根指针的二叉树；3、编写递归算法，计算二叉树中叶子结点的数目；4、编写递归算法，计算二叉树的深度；5、编写

15、递归算法，将二叉树中所有结点的左、右子树相互交换；6、使用数组 elem 中的随机数序列 （以 0 表示结束，不包括 0），生成以 Tree 为根指针的 二叉排序树；在以 Tree 为根指针的二叉排序树中查找结点；从以 Tree 为根指针的二叉排序树中删除结点（适用各种位置的结点） ； 用非递归算法，先序遍历以 Tree 为根指针的二叉树；提示：用数组 BiTNode *stackmax 构成堆栈，利用这个堆栈实现功能。7、8、9、10、用凹入表示法的表示以 Tree 为根指针的二叉树，例如：/32412374669056711、用广义表表示以 Tree 为根指针的二叉树，例如/ （324（1

16、23（746,690）,567）12、 对以 Tree 为根指针的二叉树， 从根结点开始， 逐层从左到右输出各结点的数据。提示： 用数组 BiTNode*queuemax 构成队列，利用这个队列实现功能13、 根据 Huffman 编码原理，使用数组 elem 中的随机数序列（以 0 表示结束，不包括 0） 作为结点的权重，生成赫夫曼树，以及赫夫曼编码，计算平均带权径长度。14、（ 1 ）随机生成二叉树。保存的一对输出序列恢复出二叉树。2）生成并保存先（后）序、中序输出序列。（4）生成先（后）序输出序列。3）按照实验环境】VC+ 6.0实验要求】将如上文件保存在命名为学号+姓名”的文件夹中并上

17、传到指定的服务器。1112实验四 综合应用、运动会分数统计问题描述参加运动会的 n 个学校编号为 1n。比赛分成 m 个男子项目和 w 个女子项目，项目编 号分别为 1m 和m+1m+w。由于各项目参加人数差别较大，有些项目取前五名， 得分顺序为 7， 5， 3， 2， 1；还有些项目只取前三名，得分顺序为5， 3， 2。写一个统计程序产生各种成绩单和得分报表。基本要求 产生各学校的成绩单，内容包括各校所取得的每项成绩的项目号、名次（成绩） 和得分；产生团体总分报表，内容包括校号、男子团体总分、女子团体总分和团体总分。测试数据对于 n=4,m=3,w=2，编号为奇数的项目取前五名，编号为偶数的

18、项目取前三名，组实例数据。实现提示可以假设 n=20,m=30,w=20 ，姓名长度不超过 20 个字符。每个项目结束时，将其编 号、类型符（区分取前五名还是前三名）输入，并按名次顺序输入运动员姓名、校名（和成 绩）。选作内容允许用户指定某项目采取其他名次取法。、姓名设计一二、一元稀疏多项式简单计算器问题描述设计一个一元稀疏多项式简单计算器 基本要求一元稀疏多项式简单计算器的基本功能是：（ 1 ）输入并建立多项式；（2）输出多项式，输出形式为整数序列：n,C1,e1,C2,e2,数， Ci和 ei分别是第 i 项的系数和指数，序列按指数降序排列； 多项式 a 和 b 相加，建立多项式 a+b;

19、 多项式 a 和 b 相减，建立多项式 a-b。,Cn,en，其中 n 是多项式的项（3）（4） 测试数据（1）（2）（3）（4） 实现提示用带表头结点的单链表存储多项式。 选作内容（1） 计算多项式在 X 处的值。311891192x+5x3-3.1x11)+(7-5x8+11x9)=(-3.1x11+11x9+2x+7)-329-32215159-3(6x-3-X+4.4X2-1.2X9)-(-6X-3+5.4X2-X2+7.8X15)=(-7.8X15-1.2X9+12X-3-X) (1+X+X2+X3+X4+X5)+(-X3-X4)=(1+X+X2+X5)(X+X3)+(-X-X3)=

20、01314计算多项式 a 的导函数 a。 多项式 a 和 b 相乘，建立乘积多项式ab。多项式的输出形式为类数学表达式。例如，多项式-3x8+6x3-18 的输出形式为-3xA8+6xA3-18。注意，系数为 1 的非零次项的输出形式中略去系数 的输出形式为x8。计算器的仿真界面。三、停车场管理问题描述设停车场是一个可停放 n 辆汽车的狭长通道， 且只有一个大门可供汽车进出。 车场内按车辆到达时间的先后顺序， 依次由北向南排列 (大门在最南端， 最先到达的第一辆 停放在车场的最北端) ，若车厂内已停满 n 辆汽车，则后来的汽车只能在门外的便道上等候， 一旦有车开走， 则排在便道上的第一辆车即可

21、开入； 当停车场内某辆车要离开时， 在它之后 进入的车辆必须先退出车场为它让路， 待该辆车开出大门外， 其他车辆再按原次序进入车场， 每辆停放在车场的车在它离开停车场时必须按它停留的时间长短缴纳费用。 试为停车场编制 按上述要求进行管理的模拟程序。基本要求以栈模拟停车场， 以队列模拟车场外的便道， 按照从终端读入的输入数据序列进行模拟 管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及 到达或离去的时刻。 对每一组输入数据进行操作后的输出信息为： 若是车辆到达， 则输出汽 车在停车场内或便道上的停车位置； 若是车辆离去， 则输出汽车在停车场内停留的时间和应 缴纳的

22、费用(在便道上停留的时间不收费)。 /栈以顺序结构实现，队列以链表结构实现。测试数据设 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)四、航空客运订票系统81，如

23、 1x8汽车在停也用顺序存包含两个数两个栈共享空间，思考应开辟数组的空间是多少。 汽车可有不同种类，则他们的占地面积不同，收费标准也不同，如 1.5 辆小汽车的占地面积相同， 1 辆十轮卡车占地面积相当于 面积。汽车可以直接从便道上开走， 次排到队尾。停放在便道上的汽车也收费， 改结构以满足这种要求。1 辆客车和3 辆小汽车的占地此时排在它前面的汽车要先开走让路，然后再依收费标准比停放在停车场的车低，请思考如何修15问题描述 航空客运订票的业务活动包括：运订票系统，基本要求（1）（ 2）（ 3）查询航线 ：根据旅客提出的终点站名输出下列信息：航班号、飞机号、星期几飞行，最 近一天航班的日期和余

24、票额；承办定票业务 ：根据客户提出的要求（航班号、订票数额）查询该航班票额情况，若尚 有余票，则为客户办理订票手续，输出座位号；若以满员或余票额少于定票额，则需重 新询问客户要求。若需要，可登记排队候补；承办退票业务 ：根据客户提供的情况（日期、航班） ，为客户办理退票手续，然后查询 该航班是否有人排队候补， 首先询问排在第一的客户， 若所退票额能满足他的要求， 则 为他办理订票手续，否则依次询问其他排队候补的客户。测试数据 自行指定。实现提示两个客户名单可分别由线性表和队列实现。 为查找方便， 已订票客户的线性表应按客户 姓名有序，并且，为插入和删除方便，应以链表作为存储结构，由于预约人数无

25、法预计，队 列也应以链表作为存储结构。整个系统需汇总各条航线的情况登录在一张线性表上， 由于航 线基本不变， 可采用顺序存储结构， 并按航班有序或按终点站名有序。 每条航线是这张表上 的一个记录， 包含上述 8 个域，其中乘员名单域为指向乘员名单链表的头指针， 等候替补的 客户名单域为分别指向队头和队尾的指针。选作内容当客户订票要求不能满足时， 系统可向客户提供到达同一目的地的其它航线情况。 以充分发挥自己的想象力，增加系统的功能和其他服务项目。五、简单行编辑程序问题描述 文本编辑程序是利用计算机进行文字加工的基本软件工具， 实现对文本文件的插入、 删 除等修改操作。限制这些操作以行为单位进行

26、的编辑程序称为行编辑程序。被编辑的文本文件可能很大，全部读入编辑程序的数据空间（内存）的做法既不经济，也不总能实现。一种解决方法是逐段编辑。 任何时刻只能把待编辑的文件的一段放在内存中， 称为活区。 试按照这种方法实现一个简单的行编辑程序。 设文件每行不超过 320 个字符， 很 少超过 80 个字符。基本要求实现以下 4 条基本编辑命令：（1） 行插入。格式：i 将文本插入活区中第 行之后。查询航线、 客票预订和办理退票等。 试设计一个航空客 以使上述业务可以借助计算机来完成。每条航线所涉及的信息有：终点站名、航班号、飞机型号、飞行周日（星期 几）、乘员定额、余票量、已定票的客户名单（包括姓

27、名、订票量、舱位等级 1，2 或 3）以及等候替补的客户名单（包括姓名、所需票量）；作为示意系统，全部数据可以只放在内存中； 系统能实现的操作和功能如下：还可161行（到第 行号 2行）。例如“ d10”和“ d10 14” n回车并从输入文件中读入下一段，作为新的活区。p回车设活区的大小用行数 ActiveMaxLen （可设为 100）来描述。考虑到文本文件 行长通常为正态分布，且峰值在 60 到 70 之间，用 320*ActiveMaxLen 大小 的字符数组实现存储将造成大量浪费，可以以标准行块为单位为各行分配存 储，每个标准行块可含 81 个字符。 这些行块可以组成一个数组， 也可

28、以利用 动态链表连接起来。一行文字可能占多个行块。行尾可用一个特殊的ASCII字符（如 （012）8）标识。此外，还应记住活区起始行号。行插入将引起随后各 行行号的顺序下推。 初始化函数包括：请用户提供输入文件名（空串表示无输入文件）和输出文 件名，两者不能相同。然后尽可能多地从输入文件中读入各行，但不超过 ActiveMaxLen-x 。 x 的值可以自定，例如 20。 在执行行插入命令的过程中，每接收到一行时都要检查活区大小是否已达 ActiveMaxLen 。如果是，则为了在插入这一行之后仍保持活区大小不超过 ActiveMaxLen ，应将插入点之前的活区部分中第一行输出到输出文件中；

29、若 插入点为第一行之前，则只得将新插入的这一行输出。 若输入文件尚未读完，活区切换命令可将原活区中最后几行留在活区顶部， 以保持阅读连续性；否则，它意味着结束编辑或开始编辑另一个文件。 可令前三条命令执行后自动调用活区显示。对于命令格式非法等一切错误作严格检查和适当处理。加入更复杂的编辑操作，如对某行进行串替换；在活区内进行模式匹配等，格式可以为 S行号串 1串 2回车和 m串 回车。六、约瑟夫生者死者游戏问题描述该游戏的大意是：假设有 30 个游客同乘一条船，因为严重超载，加上风高浪大，危险 万分；因此船长告诉乘客，只有将全船一半的游客投入海中，其余人才能幸免遇难。无奈，大家只得同意这种办法

30、，并议定 30个人围成一圈，由第一个人数起，依次报数，数到第 9 人，便把他投入大海中，然后再从他的下一个人数起，（2） 行删除。格式：d行号 1空格 行号 2回车删除活区中第 行号（ 3） 活区切换。格式：将活区写入输出文件，（ 4） 活区显示。格式：逐页的（每页 20 行）显示活区内容，每显示一页之后请用户决定是否继续显示以 后各页（如果存在） 。印出的每一行要前置行号和一个空格符，行号固定占 4 位，增量 为 1。各条命令中的行号均须在活区中各行行号范围之内， 只有插入命令的行号可以等于 活区第一行行号减一，表示插入当前屏幕中第一行之前，否则命令参数非法。测试数据 自行设定， 实现提示（

31、1）注意测试将活区删空等特殊情况。（5）选作内容（1）（2）17如此循环地进行，直到剩下15 个乘客为止。请按照投入大海的顺序，输出哪些位置是将被扔下大海的位置。实现提示 利用单向循环链表存储结构模拟此过程。七、学生通讯录管理系统问题描述 纸质的通讯录已经不能满足大家的要求，容易丢失，查找困难等问题是纸质通讯录所 不能克服的缺点。 “学生通讯录管理系统”是为了帮助老师、同学，或者其它一些需要使用 通讯录的人员进行管理和分析的一种应用程序。1、输入数据建立通讯录2、查询通讯录中满足要求的信息3、插入新的通讯录信息4、删除不需要的通讯录信息5、查看所有的通讯录信息18实验报告示例“学生通讯录管理系

32、统”的设计与实现设计要求1 1、问题描述纸质的通讯录已经不能满足大家的要求，容易丢失，查找困难等问题是纸质通 讯录所不能克服的缺点。“学生通讯录管理系统”是为了帮助老师、同学，或者其 它一些需要使用通讯录的人员进行管理和分析的一种应用程序。2 2、需求分析(1)输入数据建立通讯录(2)查询通讯录中满足要求的信息(3)插入新的通讯录信息(4)删除不需要的通讯录信息(5)查看所有的通讯录信息概要设计为了实现需求分析中的功能，可以从3 个方面着手设计主界面设计为了实现学生通讯录管理系统各功能的管理，设计一个含有多个菜单项的主控菜单子程序以链接系统的各项子功能，方便用户使用本系统。存储结构设计本系统主

33、要采用链表结构类型来表示存储在“学生通讯录管理系统”中的信息。其 中，链表结点有 4 个分量构成：通讯录成员学号、姓名、电话号码、指向该结构体 的指针。此外，本系统还设置一个全局变量seat表示成员序号。系统功能设计1 1、2 2、3 3、本系统设置 5 个子功能:(1)建立通讯录系统:(2)插入通讯录记录:(3)查询通讯录记录:是按姓名查询。(4)删除通讯录记录:按姓名删除。(5)显示通讯录记录:可以一次输入多个成员的信息，建立通讯录。每次可以插入一个成员的信息。可以按两种方式查询所要的记录，一是按学号查询，二可以按三种方式删除信息，按序号删除，按学号删除,可以查看通讯录中所有成员信息。1

34、1、2 2、模块设计模块设计本程序包含两个模块：主程序模块和链表操作模块，其调用关系如下:主程序模块*链表操作模块系统子程序及功能设计19四、五、本系统共设置 10 个子程序，各程序的函数名及功能说明如下:（1）（2）（3）（4）（5）（6）Lin kList Create In creL in k()deleteElem(Li nkList L, intdelName(Li nkList L,char n)delNum(Li nkList L, int void insertYouXu(L in kList printList(Li nkListL)L, Lin kList（7）Prior（

35、LinkList（8）searchName（LinkList（9）int searchNum（LinkList（10）void main（）3 3、函数主要调用关系图i)n)L, LinkList/链表的创建从通讯录中按序号删除第i 各元素/按姓名删除通讯者纪录/按学号删除通讯者纪录Elem） /插入一条通讯录/打印通讯录P） /查找位于当前地址元素的前一元素的地址L, int n /按姓名查找通讯者记录L, i nt n)/按学号查找通讯者记录/主函数。设定界面的颜色和大小，调用链表操作模块详细设计1 1、数据类型定义本系统采用链式结构存储通讯录结点。结点定义如下:typ edef stru

36、ct LNodeint nu mber; double telenum;char n ame20; structLNode *n ext;LNode,*Lin kList;2 2、系统主要子程序详细设计（1）建立链表的函数，主要用来建立通讯录。（流程图略）（2）显示链表中所有节点的信息，用于查看通讯录所有的纪录。（流程图略）测试分析2021本程序执行文件为“学生通讯录管理系统 .exe”。 进入本系统之后，随即显示系统主菜单界面。用户可在该界面下输入各子菜单 前对应的数字并按回车，执行相应子菜单命令。本系统没有提供直接修改通讯录信息的功能，可通过删除和插入操作完成修改 功能。系统运行主界面，各

37、子功能测试运行结果如下：略）、六、源程序清单（略）七、用户手册22实验报告封面、评语得分表数据结构与算法课程实习实习报告学院:计算机与信息专业:班级:学号:姓名:20122012. 6 6.23评语:成绩:24部分程序源代码（参考）/*源文件名： P1.cpp功能：静态线性表操作 */#include #include #include #include #include #include #include #include const max=10000;struct SqListint elemmax;int length;int BJ;int YD;/存放元素的数组/当前长度/比较次数/

38、移动次数void init(SqList &list);void display(SqList &list);void insert(SqList &list);void search(SqList &list);void del(SqList &list);void simpleSort(SqList &list);void quickSort(SqList &list,int low,int high); int Partition(SqList&list,int low,int high); void binarySearc

39、h(SqList &list);void nzlist(SqList &list);void Deletemany(SqList &list);void Insertorderedlist(SqList &list);void Bing(SqList &list,SqList &A);SqList list,A;void main()char choice;/删除从 X 到 Y 之间的所有值/有序插入/两个有序表合并case 4:25while (1)case 1:init(list); break;case 2:display(list);ge

40、tch(); break;case 3:insert(list); display(list); getch(); break;system(cls); cout nnnn;cout tt静态线性表操作n;cout tt=cout nn;cout tt1：初始化n;cout tt2：显示n;cout tt3：单个插入n;cout tt4：查找n;cout tt5：删除n;cout tt6：简单排序n;cout tt7：快速排序n;cout tt8：折半查找n;cout tt9：逆置线性表n;cout tta：删除多个值/. J、亠 r .n;cout ttb ：有序表中插入n;cout ttc

41、 :有序表合并n;cout n;cout tt0 ：退出n;cout n;cout tt 请选择： flush;choice = getch();system(cls);switch(choice)H.26search(list); getch();break;case 5：del(list);getch();break;case 6：simpleSort(list);printf( 排序成功并输出线性表。display(list); getch();break;case 7：quickSort(list,0,list.length-1);printf( 快排成功并输出线性表：display(

42、list);cout 比较次数为：list.BJ 次， ; cout 移动次数为：list.YD 次。 endl; getch();break;case 8：binarySearch(list); getch();break;case 9：nzlist(list); display(list); getch(); break;case a: Deletemany(list); printf( 删除成功 !n);display(list); getch(); break;case b:Insertorderedlist(list); display(list);printf(” 比较次数为：d，

43、移动次数为：dn,list.BJ,list.YD); getch();break;case c：printf( 再建一个线性表 An);n););27init(A);printf(n 将新表排序 :); quickSort(A,0,A.length-1); printf( 已成功排序 !n);printf(n 打印有序表 list:); display(list);printf( 打印有序表 A:); display(A);printf(n 现将两表合并 :n); Bing(list,A);printf( 打印合并后的表 :n); display(list);getch();break;cas

44、e 0:exit(0);/屏幕提示后，voidinit(SqList &list)int i; while (1)cout 输入元素个数( 0 max )： list.length;if (list.length = 0 & list.length = max) break;cout endl;while (1)cout 输入随机数种子( 032767)： i;if (i = 0 & i = 32767)break;cout endl;srand(i); /指定随机数种子，相同的种子将产生相同的数据序列rand();for (i = 0; i list.length;

45、i+)list.elemi = rand() % 10000;for (i = list.length; i max; i+)list.elemi = 0;/在屏幕上依次显示线性表 list 中的元素个数和全部元素/格式应便于观察/如果需要指定输出的宽度， 可以使用 cout setw(W) X ，其中 X 是输出的数值， W 是 占据的列数void display(SqList &list)int i;从键盘输入线性表长度和随机数种子，生成指定长度的线性表list28printf( 输出线性表元素个数： %dn,list.length); printf( 输出这些元素： );for(

46、i=0;ilist.length;i+)cout list.elemi ;cout endl;/屏幕提示后，从键盘输入一个元素值，然后把这个新元素插到线性表 /应有溢出判断和报告void insert(SqList &list)int x;printf( 请输入一个新元素： ); scanf(%d,&x);if(list.length+1)max)list.elemlist.length=x;list.length+;elseprintf( 线性表溢出！ );/屏幕提示后，从键盘输入一个元素值，在线性表/屏幕显示搜索结果和搜索过程中的比较次数 voidsearch(SqList

47、 &list)list 的末尾list 中搜索这个元素29int x,i=0;printf( 请输入需要查找的值： );scanf(%d,&x);while(x!=list.elemi&i=list.length)i+;/查找 /比较完所有元素仍未找到 xprintf（ 该值不在线性表中！ n）;printf（”比较次数为：%d次”,i）;/找不到时比较次数即为表长elseprintf（ 该值在线性表中找到。 n）;printf（”比较次数为：%d次”,+i）;list 中删除这个元素/屏幕显示删除成功与否的信息，并显示比较次数和移动次数 void del（SqList

48、&list）/屏幕提示后，从键盘输入一个元素值，在线性表int x,j,i=0;printf( 请输入需要删除的值： );scanf(%d,&x);while(x!=list.elemi&i=list.length)i+;/查找printf（ 该值不在线性表中，不能删除！ n）;printf（”比较次数为：%d 次n,i）;elseprintf( 找到该值并删除。 n);printf(” 比较次数为：%d 次n,+i);for(j=i;jlist.length;j+)/找到后将其后的元素依次向前移动list.elemj=list.elemj+1;printf( 已成功删

49、除。 n);printf(移动次数为： %d 次n,listength-i);list.length-;/删除一个元素后表长减/ 比较次数与移动次数之和即为表长30/对线性表 list 进行简单排序 /屏幕显示比较次数和移动次数 voidsimpleSort(SqList &list)int x,i,j,a;for(j=0;jj;i-)if(xlist.elemi)/使用简单选择排序/ 定义哨兵 ,用 x 进行比较/从第一个元素开始/选出该元素之后所有中的最小值/可直接用 X 作比较得最小值x=list.elemi;a=i;list.BJ=list.BJ+list.length-1-j

50、;y=n(n-1)/2 来计算( n 为元素个数) 。因为是作为哨兵的元素与之后的所有元素比较，成一个 等差数列。所以，简单选择排序的比较次数都可由该公式计算。if(x=list.elemj)相等 ,则可以省略移动步骤 ,以此减少移动次数/比较次数的计算.亦可由/如果得出的最小值与原哨兵continue;list.elema=list.elemj;list.elemj=x;list.YD+;构体中新加入的成员 ,用于比较次数与移动次数的计算/list.BJ 与 list.YD 是在结printf( 比较次数为： %d,list.BJ);printf( 移动次数为： %dn,list.YD);/

51、对线性表 list 进行快速排序 /屏幕显示比较次数和移动次数 void quickSort(SqList&list,int low,int high)int pivot;if(lowhigh)pivot=Partition(list,low,high);quickSort(list,low,pivot-1);quickSort(list,pivot+1,high);/调用 Partition 函数/分块进行排序list.elemlist.length=0;3132int Partition(SqList &list,int low,int high)int pivotkey;

52、list.elemlist.length=list.elemlow;pivotkey=list.elemlow;while(lowhigh)while(low=pivotkey) 比哨兵小的放左边/对原序列进行分块high-; list.BJ+;list.elemlow=list.elemhigh; /记录比较次数和移动次数list.YD+; list.BJ+;while(lowhigh&list.elemlow=pivotkey)/比哨兵大的放右边 list.elemhigh=list.elemlow;list.YD+; list.BJ+;list.elemlow=list.elem

53、list.length;当 low,high 指向同一位置时找到哨兵的位置 list.YD+;return /以哨兵元素所在位置为标志分左右块/屏幕提示后，从键盘输入一个元素值，对经过排序的线性表 /屏幕显示查找结果，并显示比较次数 void binarySearch(SqList&list)int x,y=0,low=1,high=list.length,mid;标low+;/定义哨兵list 进行折半查找/在有序数列中排序/list.BJ+;/low;/low 与 high 用的是元素序号而非数组下printf( 请输入需要查找的值： );scanf(%d,&x);whil

54、e(lowlist.elemmid-1) 均用了元素序号，而数组中是从 0 开始计数的/ 用 list.elemmid-1 是因为 low 与 highy+; low=mid+1;elseif(xlist.elemmid-1) 比,否则与之右边比/ 计算比较次数/ 若 X 小于 list.elemmid-1, 则与之左边33y+;high=mid-1;else一拿出来在 while 中,这里的 y+不能省/其实，三个语句中的 y+;可以统/不过,在 else 中会 break 出，所以y+;break;if（x=list.elemmid-1）printf（ 该值已找到。 n 比较次数为： %d

55、n,y）;elseprintf（ 该值未在线性表中找到。 n 比较次数为： %dn,y）; 时比较次数最多，为表长一半取上限/没找到/编程实现一个顺序表的就地逆置，void nzlist(SqList &list)int x,i=0,j=list.length-1;while(ij)x=list.elemi;与倒数第二个 .如此交换即利用原表的存储空间将顺序表逆置。/将表中第一个与最后一个,第二个list.elemi=list.elemj;list.elemj=x;j-;i+;printf( 逆置成功并打印该表。n);void Deletemany(SqList &list)i

56、nt x,y,i,j;printf( 请输入两个范围值：scanf(%d%d,&x,&y);for(i=0;ilist.length;i+)/在有序表中 ,从小到大);if(xy)/因为 X,Y 的大小不定34for(j=i;jlist.length;j+)list.elemj=list.elemj+1; elseif(list.elemi=y)for(j=i;jlist.length;j+)list.elemj=list.elemj+1;list.length-;void Insertorderedlist(SqList &list)void Bing(SqList

57、&list,SqList &A)int i,m,j;if(list.elemi=x)/ 经判断 X,Y 大小后再确定须删除的范list.length-;/删除一个值后需将表长减一/有序插入int x,i=0,j;printf( 请输入一个数 :);scanf(%d,&x);while(list.elemii;j-)list.elemj=list.elemj-1; list.YD+;list.elemi=x;list.length+;/找到须插入的位置/计算移动次数/将该位置之后的数依次后移/计算移动次数/插入之后表长加一/两个有序表的合并35m=list.length+

58、A.length;for(i=list.length;im;i+)list.elemi=A.elemi-list.length;list.length=m;quickSort(list,0,list.length-1);for(i=0;ilist.length;i+)if(list.elemi=list.elemi+1)for(j=i;jlist.length;j+)list.elemj=list.elemj+1;list.length-;/合并后的表长/ 将 A 表接到 LIST 之后/重新排序/删除新表中的重复值36源文件名： P2.cpp 功能：动态链表操作*/#include #inc

59、lude #include #include #include #include #include #include /定义结点类型struct Nodeint data;Node *next; ;Node Head,A,B,C;Node *DLList,*a,*b,*c;void wait();voidinit(Node*DLList);voiddisplay(Node*DLList);voidinsert(Node *DLList); void search(Node *DLList); void del(Node*DLList); void reverse(Node *DLList);

60、void merge(Node A,Node B);void Sort(Node *c);void divide(Node A);void main()char choice;DLList=&Head;/ 使头指针指向头结点Head.next=NULL;a=&A;A.next=NULL;/*/头结点/头指针37b=&B;B.next=NULL; c=&C;C.next=NULL;while (1)case 1:init(DLList);printf( 已成功建立链表！ wait();break;case 2:display(DLList);wait();break;case 3:insert(DLList); display(DLList); wait(); break;case 4:system(cls); cout nnnn; cout tt单链表操作n;cout tt=cout nn;cout tt1：初始化n;cout tt2：显示n;cout tt3：单个插入n;cout tt4：查找n;cout tt5：删除n