资源描述：
《数据结构与算法实验指导》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、实习一线性表木次实习的主要目的在于熟悉线性表的基木运算在两种存储结构上的实现，其屮以熟悉各种琏表的操作为重点。木次实习还可以起到复习c语言的作川。1.1①合并线性表问题描述：将两个按元素值递增有序排列的线性衣A和B合并为一个按元素值递减有序排列的线性表C(允许值相同)。基本要求：(1)采用顺序存储结构，可另外开辟空间存放C。(2)以单链表作存储结构，利用原表空间(即A和B的结点空间)存放C。1・2①多项式相乘问题描述：己知一元n次多项式的形式为：F(x)=a0+aix+a2x2+...+anxr',求两个一元多项式的乘积。基本要求：以单
2、循环链表作多项式的存储结构，链表中每一个结点为：系数指数指针coefexpnext①定位运算问题描述：定位运算LOCATE(L,x)的功能是：查找值为x的结点在线性表L中的位置。当线性表L屮存在一个值为x的结点时，结果就是该结点的位置；若线性表L中存在多个值为x的结点，则是首次找到的结点的位置；当线性表L中不存在值为x的结点，将给出一个特殊的值农示值为x的结点不存在。基本要求：编写符合以F要求的LOCATE运算算法：采用双向链表作存储结构，链表中毎个结点的结构为:priorfreqdatanext其中：freq是访问频度域，在链表起用之
3、前，其值均初始化为零。每当在链表进行一次LOCATED,x）运算时，令元素值为x的结点屮freq域的值增1,并使此链表中结点保持按访问频度递减的顺序排列，以便使频繁访问的结点总是靠近农头。1.4②运动会分数统计问题描述：参加运动会的n个学校编号分别为l~n。比赛分成in个男子项廿和w个女子项H,项H编号分别为l~m和m+1〜m+w。由于各项H的参加人数差别较大，有些项H取前五名，得分顺序为7,5,3,2,1；还有些项目取前三名，得分顺序为5,3,2。写一个统计程序产生各种成绩单和得分报表。基本要求：产牛各学校的成绩单，内容包括各校所得的
4、每项成绩的项日号，名次（成绩），姓名和得分；产牛团体总分报表，内容包括学校编号、男子团体总分、女子团体总分和团体总分。测试数据：对于n=4,m=3,w=2,编号为奇数的项目取前五名,编号为偶数的项目取前三名,设计一组实例数据。实现提示：可以假设n<20,m<20,姓名长度不超过20个字符，每个项目结束时，将其编号,类型符（区分前五名还是前三名）输入，并按名次顺序输入运动员姓名，学校编号（和成绩）。选作内容：允许用户指定某项H采取其它名次取法。1.5③约瑟夫环问题描述：约瑟夫（Joseph）问题的一种描述是：编号为1,2,...»n的n个
5、人按顺时针方向围处一圈，每人持有一个密码（止整数）。一开始任选一个止整数作为报数的上限m,从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报到m的人出列，将他的密码作为新的m值，从他在顺吋针方向的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。基本要求：利用单向循环链表存储结构模拟此过程，按出列的顺序打印个人的编号。测试数据：m的初始值为20；密码是3,1,7,2,4,8,4(正确的结果应为：6,1,4,7,2,3,5)实现提示：程序运行后首先要求用户指定初始报数的上限值，然后读収各
6、人的密码。设n<30o选作内容：向上述程序中添加在顺序结构上实现的部分。1.6④长整数的运算问题描述：设计一个程序实现两个任意长的整数求和运算。基本要求：利用双向循环链表实现长整数的存储，每个结点含一个整型变量。任何整型变量的范围是-2l542,5-I)o输入和输出形式：按中国对于长整数的表示习惯，每四位一组,组间川逗号隔开。测试数据：(1)0；0；应输出“0”。(2)-2345,6789；-7654,3211；应输出“・1,0000,0000”。(3)-9999,9999；1,0000,0000,0000；应输出“9999,0000,
7、0001”。(4)1,()(X)1,0001；・1,(X)()l,0001；应输出“0”。(5)1,0001,0001；・1,0001,0000；输出“1”。实现提示：(1)每个结点中可以存放的最大整数为215-1=32767,才能保证两数相加不会溢出。但若这样存，相当于按32768进制数存，在十进制数与32768进制数之间的转换十分不便。故可以在每个结点中仅存十进制数的4位，即不超过9999的非负整数，整个链表视为万进制数。(2)可以利川头结点的数据域的符号代表长整数的符号。川其绝对值表示元素结点数目。相加过程不耍破坏两个操作数链表。
8、两操作数的头指针存于指针数组中是简化程序结构的一种方法。不能给长整数规定上限。选作内容：修改上述程序，使它在整型量范围是-2=~(2n-l)的计算机上都能令效地运行。其屮，n是由程序读入的参量。输入数据的分
