《算法与数据结构》实验指导书J的元索。这种算法比删除一个元素后立即移动其后面的元素的效率高得多。4．利用单向链表完成一个班级的一个学期的所有课程的管理：能够增加、删除、修改学生的成绩记录。5.对于同样的一组整数，比较线性表的两种不同存储结构的特点和使用场合。26
《算法与数据结构》实验指导书 26 J 的元索。这种算法比删除一个元素后立即移动其后面的元素的效率高得多。 4．利用单向链表完成一个班级的一个学期的所有课程的管理：能够增加、删除、修改学生的成绩记录。 5．对于同样的一组整数，比较线性表的两种不同存储结构的特点和使用场合
《算法与数据结构》实验指导书实验二：线性表的综合应用（选做：2学时）一、实验目的：：掌握顺序表和链表的概念，学会对问题进行分析，选择恰当的逻辑结构和物理结构：加深对顺序表和链表的理解，培养解决实际问题的编程能力二、实验内容：实现一元稀疏多项式的表示及基本操作（建立、销毁、输出、加法、减法、乘法等操作）1.问题描述：一元多项式一定要包含系数项和指数项的描述，对一元多项式的基本运算，可应用两个有序链表合并的思想进行。2.实现要求：：“建立多项式算法”操作结果：输入m项的系数和指数，建立一元多项式P“销毁多项式算法”初始条件：一元多项式p已存在；操作结果：销毁一元多项式“输出多项式算法”初始条件：一元多项式p已存在；操作结果：打印一元多项式p；：“多项式加法算法”初始条件：两个多项式的Pa,Pb已存在；操作结果：pa=pa+pb，并销毁pb；“多项式减法算法”初始条件：两个多项式的Pa,Pb已存在；操作结果：pa=pa一pb，并销毁pb;“多项式乘法算法”初始条件：两个多项式的Pa，Pb已存在；操作结果：pa=pa*pb，并销毁pb；：“求多项式项数算法”初始条件：一元多项式p已存在；操作结果：返回p中的项数；27
《算法与数据结构》实验指导书 27 实验二：线性表的综合应用（选做： 2 学时） 一、实验目的： 一、实验目的： 一、实验目的： 一、实验目的： . 掌握顺序表和链表的概念，学会对问题进行分析，选择恰当的逻辑结构和物理结构 . 加深对顺序表和链表的理解，培养解决实际问题的编程能力 二、实验内容: 实现一元稀疏多项式的表示及基本操作（建立、销毁、输出、加法、减法、乘法等操作）； 1．问题描述： . 一元多项式一定要包含系数项和指数项的描述，对一元多项式的基本运算，可应用两个有序链表合并 的思想进行。 2．实现要求： . “建立多项式算法”操作结果： 输入 m 项的系数和指数，建立一元多项式 P； . “销毁多项式算法”初始条件： 一元多项式 p 已存在； 操作结果：销毁一元多项式 . “输出多项式算法”初始条件： 一元多项式 p 已存在； 操作结果：打印一元多项式 p； . “多项式加法算法” 初始条件：两个多项式的 Pa,Pb 已存在 ； 操作结果：pa = pa + pb，并销毁 pb； . “多项式减法算法” 初始条件：两个多项式的 Pa,Pb 已存在 ； 操作结果：pa = pa － pb，并销毁 pb； . “多项式乘法算法” 初始条件：两个多项式的 Pa,Pb 已存在 ； 操作结果：pa = pa * pb，并销毁 pb； . “求多项式项数算法” 初始条件：一元多项式 p 已存在； 操作结果：返回 p 中的项数；
《算法与数据结构》实验指导书三、编程指导1.由于一元多项式包含系数项和指数项，其系数为float型，指数项为int型，往往将其两项组合成为一个结构元素类型，将多项式看成是一个有序表，则多项式定义中的各个操作均可利用有序表操作来完成。定义抽象类型数据polynomial：typedef structt//项的表示，多项式的项作为LinkList的数据元素Ⅱ系数float coef;I/指数int expn;Iterm,ElemType；/两个类型名：term用于本ADT，ElemType为LinkList的数据对象名typedefLinkListpolynomial：l/用带表头结点的有序链表表示多项式；再根据算法的描述和实现要求，分别实现如下算法：CreatePolyn、DestroyPolyn、PrintPolyn、AddPolyn、SubtractPolyn、MultiplyPolyn、PolynLength，可以组合成在一个头文件之中，如取名Polyn.h。2.对单向循环链表的类型定义与单链表相同，无需重复定义，只是对单向循环链表的判断，要对最后一个结点作特殊的处理，建链表时最后一个结点的指针域不能是p->next=NULL，而是指向第一个结点，即p->next-head；p=head；3．对双向循环链表的操作，要从数据结构类型定义重新开始，对其操作的算法均要重写，如插入和删除算法，比单链要灵活，可以通过修改向前、向后指针以实现。其定义、实现及应用与单链表的过程相似，在此不复述。四、参考程序1.文件Polyn.h为一元多项式类型定义的带头结点的线性链表类型定义和基本操作描述typedefstructLNode/*结点类型*/tElemType data;structLNode*next;}LNode,*Link,*Position;typedefstructLinkList/*链表类型*/tLink head,tail;/*分别指向线性链表中的头结点和最后一个结点*/int len;/*指示线性链表中数据元素的个数*28
《算法与数据结构》实验指导书 28 三、编程指导 1．由于一元多项式包含系数项和指数项，其系数为 float 型，指数项为 int 型，往往将其两项组合成为 一个结构元素类型，将多项式看成是一个有序表，则多项式定义中的各个操作均可利用有序表操作来完成。 定义抽象类型数据 polynomial： typedef struct{ //项的表示，多项式的项作为 LinkList 的数据元素 float coef； //系数 int expn； //指数 }term, ElemType； //两个类型名：term 用于本 ADT，ElemType 为 LinkList 的数据对象名 typedef LinkList polynomial； //用带表头结点的有序链表表示多项式； 再根据算法的描述和实现要求，分别实现如下算法：CreatePolyn、 DestroyPolyn、PrintPolyn、AddPolyn、 SubtractPolyn、 MultiplyPolyn、 PolynLength，可以组合成在一个头文件之中，如取名 Polyn.h。 2．对单向循环链表的类型定义与单链表相同，无需重复定义，只是对单向循环链表的判断，要对最后 一个结点作特殊的处理，建链表时最后一个结点的指针域不能是 p->next=NULL，而是指向第一个结点， 即 p->next=head；p=head； 3．对双向循环链表的操作，要从数据结构类型定义重新开始，对其操作的算法均要重写，如插入和删 除算法，比单链要灵活，可以通过修改向前、向后指针以实现。 其定义、实现及应用与单链表的过程相 似，在此不复述。 四、参考程序 1. 文件 Polyn.h 为一元多项式类型定义的带头结点的线性链表类型定义和基本操作描述 typedef struct LNode /* 结点类型 */ { ElemType data； struct LNode *next； }LNode,*Link,*Position； typedef struct LinkList /* 链表类型 */ { Link head,tail； /* 分别指向线性链表中的头结点和最后一个结点 */ int len； /* 指示线性链表中数据元素的个数 */
《算法与数据结构》实验指导书LinkList;typedef struct//项的表示，多项式的项作为LinkList的数据元素float coef;1系数1/指数intexpn;//两个类型名：term用于本ADT，ElemType为LinkList的数据对象名}term,ElemType;typedefLinkListpolynomial//用带表头结点的有序链表表示多项式；intcmp(terma，termb)//比较多项式的项，a的指数值<b的指数值返回-1l/a的指数值）b的指数值返回0//a的指数值=b的指数值返回1（*算法略*}void CreatePolyn(polynomial &p, int m)(polynomial h;ElemTypee;//输入m项的系数和指数，建立表示一元多项式的有序链表PInitList(p);h=p;e.coef=0.0:e.expn=-l;I/SetCurElem(P,e)//置头结点的数据元素for(i=-l; <=m : i++)1依次输入m个非零项tscanf(“%f%d”,&e.coef,&e.expn);if(! LocateElem(p, e, (*cmp)O)//当前链表中不存在该指数项Listlnsert_Link(p,ie)：I/在第一个大于插入项指数的数据项前插入/新的数据项132.准备测试数据，对main函数和其他算法改写，请同学们自我完成。29
《算法与数据结构》实验指导书 29 }LinkList； typedef struct{ //项的表示，多项式的项作为 LinkList 的数据元素 float coef； //系数 int expn； //指数 }term, ElemType； //两个类型名：term 用于本 ADT，ElemType 为 LinkList 的数据对象名 typedef LinkList polynomial； //用带表头结点的有序链表表示多项式； int cmp(term a , term b) //比较多项式的项，a 的指数值<b 的指数值 返回-1 //a 的指数值 〉b 的指数值 返回 0 //a 的指数值 = b 的指数值 返回 1 { /* 算法略 */ } void CreatePolyn(polynomial &p, int m) { polynomial h； ElemType e； //输入 m 项的系数和指数，建立表示一元多项式的有序链表 P InitList(p)； h=p； e.coef = 0.0； e.expn = -1； //SetCurElem(P, e) //置头结点的数据元素 for(i=1； i<= m ； i++) //依次输入 m 个非零项 { scanf(“%f%d”,&e.coef, &e.expn)； if(! LocateElem(p, e, (*cmp)() ) //当前链表中不存在该指数项 ListInsert_Link(p,i e)； //在第一个大于插入项指数的数据项前插入/新的数据项 } } 2．准备测试数据，对 main 函数 和其他算法改写，请同学们自我完成
《算法与数据结构》实验指导书五、实验步骤实验环境：利用VisualC++集成开发环境进行本实验的操作。六、思考题：1.设计一元稀疏多项式简单计数器（1）输入并建立多项式（2）输出多项式，输出形式为整数序列：n，cl，el，c2，e...cn，en，其中n是多项式的项数，ci,ei分别为第i项的系数和指数。序列按指数降序排列。（3）多项式a和b相加，建立多项式a+b，输出相加的多项式。（4）多项式a和b相减，建立多项式a-b，输出相减的多项式。用带表头结点的单链表存储多项式。测试数据为：(1)(2x+5x-3.1x")+(7-5x+11x(2)(6x-x+4. 4x*-1.2x)-(-6x+5. 4x+7. 8x15)(3)(x+x+x)+0(4) (x+x)-(-x-x)2.实现两个链表的合并基本功能要求：（1）建立两个链表A和B，链表元素个数分别为m和n个。（2）假设元素分别为（x1,x2...xm），和(y1,y2，..yn)。把它们合并成一个线性表C，使得：当m>=n时，C=xl,yl,x2,y2,..xn,yn,.,xm当n>m时，C=yl,xl,y2,x2,..m,xm,.yn输出线性表C。3.实现约瑟夫环问题描述：编号为1，2…：n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。基本功能要求：30
《算法与数据结构》实验指导书 30 五、实验步骤 实验环境： 利用 Visual C++集成开发环境进行本实验的操作。 六、思考题： 1．设计一元稀疏多项式简单计数器 （1） 输入并建立多项式 （2） 输出多项式，输出形式为整数序列：n，c1，e1，c2，e2.cn，en，其中 n 是多项式的项数，ci， ei 分别为第 i 项的系数和指数。序列按指数降序排列。 （3） 多项式 a 和 b 相加，建立多项式 a+b，输出相加的多项式。 （4） 多项式 a 和 b 相减，建立多项式 a-b，输出相减的多项式。 用带表头结点的单链表存储多项式。 测试数据为： （1）(2x+5x 8-3.1x 11)+(7-5x 8+11x 9) （2） (6x -3-x+4.4x 2-1.2x 9)-(-6x -3+5.4x 2+7.8x 15) （3）(x+x 2+x 3)+0 （4）(x+x 3)-(-x-x 3) 2．实现两个链表的合并 基本功能要求： （1）建立两个链表 A 和 B，链表元素个数分别为 m 和 n 个。 （2）假设元素分别为(x1,x2,.xm)，和(y1,y2, .yn)。把它们合并成一个线性表 C，使得： 当 m>=n 时，C=x1,y1,x2,y2,.xn,yn,.,xm 当 n>m 时，C=y1,x1,y2,x2,.ym,xm,.,yn 输出线性表 C。 3．实现约瑟夫环 问题描述：编号为 1，2. n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任 选一个正整数作为报数的上限值 m，从第一个人开始按顺时针方向自 1 开始顺序报数，报到 m 时停止报数， 报 m 的人出列，将他的密码作为新的 m 值，从他的顺时针方向上的下一个开始重新从 1 报数，如此下去， 直至所有人全部出列为止，设计一个程序求出出列顺序。 基本功能要求：