数据结构_1__线性表的应用

《数据结构_1__线性表的应用》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、1线性表的应用1.1约瑟夫环问题一．问题描述设编号为1、2、……n的n个人按顺时针方向围坐一圈，约定编号为k（1<=k<=n）的人按顺时针方向从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。试设计算法求出n个人的出列顺序。二．基本要求程序运行时，首先要求用户指定人数n、第一个开始报数的人的编号k及报数上限值m。然后，按照出列的顺序打印出相应的编号序列。三．提示与分析1．由于报到m的人出列的动作对应着数据元素的删除操作，而且这种删

2、除操作比较频繁，因此单向循环链表适于作为存储结构来模拟此过程。而且，为了保证程序指针每一次都指向一个具体的数据元素结点，应使用不带头结点循环链表作为存储结构。相应地，需要注意空表和非空表的区别。2．算法思路：先创建一个含有n个结点的单循环链表，然后由第一个结点起从1开始计数（此时假设k=1），计到m时，对应结点从链表中删除，接下来从被删除结点的下一个结点重新开始从1开始计数，计到m时，从链表中删除对应结点，如此循环，直至最后一个结点从链表中删除，算法结束。3．数据类型定义：①设单向循环链表的头指针为L，对应的数据类型定

3、义描述如下：typedefstructlnode{intnumber；/*每个人的编号*/structlnodenext;/*指向表示下一个人的结点的指针*/}LNode,*LinkList;/*单向循环链表的结点及指针类型的定义*/LinkListL;②为了记录退出的人先后顺序，采用一个顺序表进行存储。程序结束后再输出依次退出的人的编号顺序。由于只记录各个结点的number值就可以，所以定义一个整型一维数组就可以：intquit[N]；N为一个根据实际问题定义的一个足够大的整数。四．测试数据1．n=7，m=5，从第1

4、个人开始报数，则正确的出列顺序应为5、3、2、4、7、1、6。2．n=30，m=9，正确的出列顺序应为9、18、27、6、16、26、7、19、30、12、24、8、22、5、23、21、25、28、29、1、2、3、4、10、11、13、14、15、17、20。五．选作内容1．在顺序结构上实现本算法。需要考虑如何实现循环的顺序结构。2．m不再固定。假设n个人每人持有一个密码（正整数），从编号为k的人开始从1开始顺序报数，报到m的人出列，此时将他的密码作为新的m值，从他顺时针方向上的下一个人开始重新从1报数，报到m的人

5、出列，而后将他的密码作为新的m值，如此循环下去，直到所有人全部出列为止。3．显示仿真的运行界面。1.2一元多项式运算一．问题描述设计一个简单的一元稀疏多项式加法运算器。二．基本要求一元稀疏多项式简单计算器的基本功能包括：1．按照指数升序次序，输入并建立多项式A与B。2．计算多项式A与B的和，即建立多项式A+B。3．按照指数升序次序，输出多项式A、B、A+B。三．提示与分析1．一元n次多项式：P(x,n)=P0+P1X1+P2X2+…+PnXn，其每一个子项都是由“系数”和“指数”两部分来组成的，因此可以将它抽象成一个由

6、“系数、指数对”构成的线性表，其中，多项式的每一项都对应于线性表中的一个数据元素。由于对多项式中系数为0的子项可以不记录它的指数值，对于这样的情况就不再付出存储空间来存放它了；基于此，可以采用一个带有头结点的单链表来表示一个一元多项式。例如，多项式A=3+6X3-2X8+12X20、B=2X-2-6X3+8X10可分别表示为：2-2-63810∧B3063281220∧A图10.1用单链表存储的多项式2．数据类型定义可描述如下：typedefstructpnode{intcoef;/*系数域*/intexp;/*指数域

7、*/structpnode*next;/*指针域，指向下一个系数不为0的子项*/}PolyNode,*PolyLink;PolyLinkA,B,C;/*单链表存储的多项式A、B、C*/3．基本功能分析（1）输入多项式，建立多项式链表首先创建带头结点的单链表；然后按照指数递增的顺序和一定的输入格式输入各个系数不为0的子项：“系数、指数对”，每输入一个子项就建立一个结点，并将其插入到多项式链表的表尾，如此重复，直至遇到输入结束标志的时候停止，最后生成按指数递增有序的链表。（2）多项式相加多项式加法规则：对于两个多项式中指数

8、相同的子项，其系数相加，若系数的和非零，则构成“和多项式”中的一项；对于指数不同的项，直接构成“和多项式”中的一项。将（1）中单链表表示的两个多项式A和B相加，运算的结果是利用原表空间生成一个新链表，表示和多项式C。运算规则如下：设指针pa、pb分别指向多项式链表A、B的第一个结点，比较pa、pb所指两结点中的指数项：①若pa->