西 安 邮 电 大 学
（计算机学院）
数据结构课内实验报告
实验名称： 线性表的应用
专业名称： 网络工程 班 级： 学生姓名： 学号（8位）： 指导教师：
实验日期： 2015年 月 日
一. 实验目的及实验环境 目的:对线性表的运用 环境：VC++; 二. 实验内容
（1）.约瑟夫环问题：编号为1，2，，，，n的n个人按顺时针方向围坐在一张圆桌周围，给定一个正整数m<=n；从第一个人开始顺时针方向自1开始报数，每报到m时就让其出列，且计数继续进行下去。如此下去，直至圆桌周围的人全部出列为止。最后出列者为优胜者。每个人的出列次序定义了整数1,2,3，...，n的一个排列。这个排列称为一个(n,m)Josephus排列。例如：(7,3)Josephhus排列为3,6,2,7,5,1,4。对于给定的1,2,3,...,n中的k个数，Josephus想知道是否存在一个正整数m，使得Josephus(n,m)排列的最后k个数恰好为事先指定的k个数。
（2）.一元多项式的加法与减法的实现，如：P0+P1X+P2X^1+,,,,,,,,,,,,+PnX^n;
（3）带头结点的线性单链表a=（a1,a2,a3,,,,,,,,,,an）,b=(b1,b2,b3,,,,,,,,,bm)； 需编写一程序将a,b安以下方式合并成一个线性单链表 C=(a1,b1,a2,b2,,,,,,,,,,,,an,bm);m<=n; C=(b1,a1,b2,a2,,,,,,,,,,,,,bm,an);m>n;
三．方案设计 （1）。A.建立n个结点（无头结点）的单向循环链表。B.从链表第一个结点起循环计数寻找第m个结点C.id值，将该节点的password作为新的m值，删除该结点。D.根据m值不断从链表中删除结点，知道链表为空。
（2）.（A）.建立多项式：通过键盘输入一组多项式的系数和指数，用尾插法建立一元多项式的链表，通过控制输入0来结束建立，并在输入时指数要按照从小到大输入（B）.，建立输出多项式的函数：从单链表第一个节点开始，逐项输出其指数和系数，并按多项式的形式输出即可。（C）.实现两多项式的加法：分别建立两个多项式单链表a,b，并新建里一个链表用来存放相加后结果的指数和系数。用两个指针p,q,,p指向a链表的头结点，q指向b链表的头结点。若（p->index
（3）.A.先建立线性单链表，通过函数的调用可建立,a,b,两个线性单链表，链表的结点数可通过在主函数中输入n,m，来控制。B.进行两连表的合并，可新创一个链表进行插入，也可在原链表中直接将另一个链表插入。我选择了第二种，直接将b插入a中。C.合并的实现：将b的节点删除一个，然后隔一个a的节点插入一个，a需要两个指针，联动跑，而b则只需一个指针即可。 四．测试数据及运行结果
1．正常测试数据（3组）及运行结果； （1）约
瑟夫环：
（2）多项
式：
（3）合并多项
式