资源描述：
《实验二 线性表的应用.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、实验二链表及应用从下列题目中任意选择一题，要求先设计出相应线性结构算法，然后完成实际应用题目。根据自己对学习内容的掌握选作相应的题目难度系数0.91.线性表基本操作的实现(演示顺序链表的创建、插入、删除和查找)（要求有简单实例测试算法的正确性）难度系数1（备注：下列算法完成的前提是完成或链式结构的全部算法，根据选择的题目构造对应结构）2.城市链表[问题描述] 将若干城市的信息，存入一个带头结点的单链表。结点中的城市信息包括：城市名，城市的位置坐标。要求能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。[基本要求]
2、（1）给定一个城市名，返回其位置坐标； （2）给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于D的城市。[测试数据] 由学生依据软件工程的测试技术自己确定。注意测试边界数据。3.约瑟夫环[问题描述] 约瑟夫（Joeph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人
3、全部出列为止。试设计一个程序求出出列顺序。[基本要求] 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。[测试数据] m的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。[实现提示] 程序运行后首先要求用户指定初始报数上限值，然后读取各人的密码。设n≤30。[选作内容] 向上述程序中添加在顺序结构上实现的部分。4.线性表的逆置[问题描述] 分别以不同存储结构实现线性表的就地逆置。线性表的就地逆置就是在原表的存储空间内将线性表（a1,a2,a3,…,an）逆置为（
4、an，an-1，…，a2，a1）。[基本要求] 用顺序存储结构实现线性表的就地逆置，并将结果输出。[测试数据] 由学生依据软件工程的测试技术自己确定。注意测试边界数据，如空表。[实现提示] 设三个连续的指针，分别指向当前结点、当前结点的前趋、当前结点的后继。[选作内容] 利用单链表作为存储结构。首先先建立线性表的带头结点的单链表表示形式，之后在不借助辅助结点空间的情况下实现单链表的逆置，并将结果输出。1.长整数运算[问题描述] 设计一个程序实现两个任意长的整数求和运算。[基本要求] 利用双项循环链表实现长整数的存储，每
5、个结点含一个整型变量。任何整型变量的范围是 -（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”。
6、[实现提示] （1）每个结点中可以存放的最大整数为215-1=32767，才能保证两数相加不会溢出。但若这样存，即相当于按32768进制数存，在十进制数与32768进制数之间的转换十分不方便。故可以在每个结点中仅存十进制数的4位，即不超过9999的非负整数，整个链表视为万进制数。 （2）可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结点数目。相加过程中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方法。不能给长整数位数规定上限。[选作内容] 修改上述程序，使它在整型量范围是-（2n
7、-1）~（2n-1）的计算机上都能有效地运行。其中，n是由程序读入的参量。输入数据的分组方法可以另行规定。
