短学期数据结构.doc

数 理 信 息 学 院课 程 设 计 报 告 书题目 ：一元多项式相乘数理信息 学院 信息与计算科学 专业 信计091 班 学 生： 肖娅玲 指导教师： 徐淑华 日 期：2011.8.23 2011.9.3一元多项式相乘一、题目内容的描述，程序完成的主要功能。目的：（1）掌握线性表的插入、删除、查找等基本操作设计与实现（2）学习利用线性表提供的接口去求解实际问题（3）熟悉线性表的存储方法要求： （1）编写一个主函数，在主函数中设计一个简单的菜单，分别调用下列算法（2）编写函数，实现输入并建立多项式；（3）编写函数，实现输出多项式；（4）编写函数，实现利用单链表实现多项式的加法运算。（5）编写函数，实现利用单链表实现多项式的乘法运算二、对题目的分析1根据题意，要实现两个一元多项式相乘的算法，可以利用两个一元项式相加来实现，因为乘法运算以分解为一系列的加法运算。假设A(x)和B(x)为一元n次多项式：其中ai、bj分别是指数为ei、fj的项的非零系数，且满足：则有)（）=其中，每一项都是一个一元多项式。2一元多项式相乘转换为一元多项式相加之后，得了解一元多项式的加法运算：可以按升幂写成：它们分别由n+1和m+1(假设nm)系数唯一确定，因此，它们可以分别用线性表P和Q来表示：则两个多项式相加的结果可以用线性表R表示：。显然。我们可以对P、Q和R采用顺序存储结构。然而，再通常应用中，多项式的次数可能很高而且变化很大，使得顺序存储结构的最大长度很难确定。即此种存储结构适用于只对多项式进行求值等不改变多项式的系数和指数的运算以及次数较小的多项式。对于其它类型的多项式运算我门可以采用链式存储表示，即一元n次多项式其中pi是指数为ei的项的非零系数,且满足，则用一个长度为m且每个元素有两个数据项的序数项和指数项的线性表：便可唯一确定一个多项式。3要实现一元多项式较复杂的运算（加法、减法、乘法、除法），我们首先得知道一元多项式的简单运算：一元多项式的存储（即线性表的存储），以及与其相关的线性表的插入、删除、查找等基本操作设计与实现。（1）线性表的顺序存储、插入、删除、查找；我们首先定义一个结构体：typedef structfloat *elem;int length;int listsize;sqlist; 顺序存储的线性表的插入、删除和查找的测试数据、代码和运行结果如下；要实现简单一元多项式（即一元多项式的第i项系数存储在线性表的第i个位置）的各种运算，用线性表的顺序存储来存储其各项系数，再进行简单一元多项式的输入、输出、加法和乘法运算；其测试数据、代码和运行结果如下面的模块；（2） 线性表的链式存储、查找、删除、插入：然而，再通常应用中，多项式的次数可能很高而且变化很大，使得顺序存储结构的最大长度很难确定，特别是在处理形如：的多项式时，仅有三个元素，如果用顺序表来存储则要用20001个空间来存储，而且属于空间的极度浪费，在此种情况下我们可以采用只存储非零项系数项，同时存储相应的指数。此种情况下，我们可以采用链式存储结构，定义一个结构体来存储其中的每一项元素：Typedef struct LNode float xishu； int zhishu； struct LNode *next； LNode，*LinkList；线性表的链式存储的线性表的查找、删除和插入的测试数据、代码和运行结果如下；进而也就可以实现线性表的链式存储的加法和乘法，在其中使用的结构一如下：typedef struct linknode /定义节点float coef;int exp;struct linknode * next;polynomial;总之，由上面的分析可知，此次课题主要通过对一元多项式的两种不同存储方式（线性存储和链式存储）下的乘法来让我们熟悉顺序表和链表的存储、查找、删除、插入、加法和乘法，下面我们将两存储方式下各种运算对比学习。三、主要模块的算法描述(1) save( ):将线性表的各个元素（或结点）输入并存储起来,然后输出；输入ni = ni o输入p-xishu输入p-zhishu 将p 结点插入到L中(2) search( )：查找线性表的第i个元素；L，i = 1,flag = 0输入m , nL !=NULL不成立 成立 L-xishu!=m|L-zhishu!=nflag = 0flag = 1输出元素在线性表中的位置输出线性表中不存在该元素(3) del( )删除线性表的第i个元素； p=L，q ，j = 0输入ip-next &jnext+jq=p-next;p-next=q-next(4) insert( ) 在线性表的第i个元素之前插入一个元素；p=L；j=0；q输入i, m,n;p-next &jnext+j !p 成立 | ji-1 不成立exit (0);q=(LinkList)malloc(sizeof(LNode)q-xishu=m;q-zhishu=n;q-next=p-nextp-next=q(5)polyand( )将两个一元多项式相加；polynomial *p,*q,*s,*r; float x;p=A-next;q=B-next;s=p;Y (p-exp)(q-exp) Nr=q-next;s-next=q;free(B);return A;p=s-next;r=q;q=q-next;free(r);x=(p-coef)+(q-coef);q-next=p;s-next=q;Y x！=0 Ns=q; (p-exp)exp)N Y(p!=NULL)&(q!=NULL)q=r;p-coef=x;s=p;s-next=p-next;free(p);s=p;p=p-next; q!=NULLY (7) polyadd( ) 将两个一元多项式相乘polynomial * p,* q,* n,* head,* r,* temp,* m;int exp；float coef；head=(polynomial *)malloc(sizeof(polynomial); head-next=NULL;p=A-next;temp=(polynomial *)malloc(sizeof(polynomial);temp-next=NULL; m=temp;q=B-next;n=(polynomial *)malloc(sizeof(polynomial);exp=p-exp+q-exp; coef=p-coef*q-coef; n-coef=coef; n-exp=exp; m-next=n; m=m-next; q=q-next;p!=NULL;q!=NULL;p=p-next; m-next=NULL; polyadd(head,temp);return head;四 源代码（1） 线性表的顺序存储、输入以及输出、查找、删除、插入、加法和乘法：（1）线性表的顺序存储、输入以及输出：#include#include#define LIST_INIT_SIZE 500#define INSTINCREMENT 4typedef structfloat *elem;int length;int listsize;sqlist;sqlist save() int i,n;scanf(%d,&n);float a50;sqlist L;L.elem=(float *)malloc(sizeof(float);L.length=n;for (i=0;iL.length;i+)scanf(%f,&ai);L.elemi=ai;return L; void main()int i;sqlist L;L=save();for (i=0;iL.length;i+)printf(%f ,L.elemi);printf(n);（2） 线性表的顺序存储下的查找：#include#include#define LIST_INIT_SIZE 500#define LISTINCREMENT 10typedef structfloat *elem;int length;int listsize;sqlist; void save(sqlist &L) int i;float a50;L.elem=(float *)malloc(LIST_INIT_SIZE*sizeof(float);scanf(%d,&L.length);for (i=0;iL.length;i+)scanf(%f,&ai);L.elemi=ai;L.listsize=LIST_INIT_SIZE; void search(sqlist L)/查找线性表中的元素nint i,flag=0;float n;scanf(%f,&n);for(i=0;iL.length;i+) if(L.elemi=n)flag=1;break;if(flag=1)printf(元素%f在线性表中的第%d个位置n,n,i+1);elseprintf(线性表中不存在元素nn);void main()sqlist L;save(L);search(L);（3） 线性表的顺序存储下的删除：#include#include#define LIST_INIT_SIZE 500#define LISTINCREMENT 10typedef structfloat *elem;int length;int listsize;sqlist;sqlist save() int i;float a50;sqlist L;L.elem=(float *)malloc(sizeof(float);scanf(%d,&L.length);for (i=0;iL.length;i+)scanf(%f,&ai);L.elemi=ai;L.listsize=LIST_INIT_SIZE;return L; sqlist del()/删除线性表的第m个元素int j,m;sqlist L;L=save();scanf(%d,&m);if(mL.length)exit (-1);for(j=m-1;jL.length;j+)L.elemj=L.elemj+1;L.length=L.length-1;return L;void main()int i;sqlist L;L=del();for (i=0;iL.length;i+)printf(%fn ,L.elemi);（4） 线性表的顺序存储下的插入：#include#include#include#define LIST_INIT_SIZE 500#define LISTINCREMENT 10typedef structfloat *elem;int length;int listsize;sqlist;sqlist save() int i;float a50;sqlist L;L.elem=(float *)malloc(sizeof(float);scanf(%d,&L.length);for (i=0;iL.length;i+)scanf(%f,&ai);L.elemi=ai;L.listsize=LIST_INIT_SIZE;return L; /*sqlist insert()/在线形表的第m个位置插入一个元素kint j,m;float k;sqlist L;L=save();scanf(%d,%f,&m,&k);if(mL.length)exit (-1);if(L.length=L.listsize)L.elem=(float *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(float);if(!L.elem)exit(0);for(j=L.length-1;j=m;-j)L.elemj+1=L.elemj;L.elemj+1=k;+L.length;return L;void main()int i;sqlist L;L=insert();for (i=0;iL.length;i+)printf(%fn ,L.elemi);（5） 线性表的顺序存储下的加法：#include#include#define LIST_INIT_SIZE 500#define INSTINCREMENT 10typedef structfloat *elem;int length;int listsize;sqlist;sqlist save() int i;float a50;sqlist L;L.elem=(float *)malloc(sizeof(float);scanf(%d,&L.length);for (i=0;iL.length;i+)scanf(%f,&ai);L.elemi=ai;return L; sqlist add() int k;sqlist L1,L2,L;L1.elem=(float *)malloc(sizeof(float);L1=save();L2.elem=(float *)malloc(sizeof(float);L2=save();L.elem=(float *)malloc(sizeof(float);if(L1.length=L2.length)for(k=0;k=L1.length;k+)L.elemk=L1.elemk+L2.elemk;for(k=L1.length+1;k=L2.length;k+)L.elemk=L2.elemk;L.length=L2.length;elsefor(k=0;k=L2.length;k+)L.elemk=L1.elemk+L2.elemk;for(k=L2.length+1;k=L1.length;k+)L.elemk=L1.elemk;L.length=L1.length;return L; void main()int i;sqlist L;L=add();for (i=0;iL.length;i+)printf(%f ,L.elemi);（6） 线性表的顺序存储下的乘法：#include#include#define LIST_INIT_SIZE 500#define INSTINCREMENT 10typedef structfloat *elem;int length;int listsize;sqlist;sqlist save() int i;float a50;sqlist L;L.elem=(float *)malloc(sizeof(float);scanf(%d,&L.length);for (i=0;iL.length;i+)scanf(%f,&ai);L.elemi=ai;return L; sqlist multiply()int i,j,k;sqlist L1,L2,L;float a2020;L1=save();L2=save();L.elem=(float *)malloc(sizeof(float);L.length=L1.length+L2.length-1;for(i=0;iL1.length;i+)for(j=0;jL2.length;j+)aij=L1.elemi*L2.elemj;for(k=0;kL.length;k+)L.elemk=0;for(i=0;iL1.length;i+)for(j=0;jL2.length;j+)if(i+j=k)L.elemk+=aij;return L;void main()int i;sqlist L;L=multiply();for (i=0;iL.length;i+)printf(%f ,L.elemi);（二）线性表在链式存储下的输入以及输出、查找、删除、插入、加法和乘法：（1）线性表的链式存储、输入以及输出：#include#includetypedef struct LNode float xishu; int zhishu; struct LNode *next; LNode,*LinkList;LinkList save( )int i,n;scanf(%d,&n);LinkList L,p;L=(LinkList)malloc(sizeof(LNode);L-next=NULL;for(i=n;i0;-i)p=(LinkList)malloc(sizeof(LNode);scanf(%f,&p-xishu);scanf(%d,&p-zhishu);p-next=L-next;L-next=p;return L;void main()LinkList L;L=save();L=L-next;while(L!=NULL)printf(%f,%d,L-xishu,L-zhishu);L=L-next;printf(n);（2） 线性表在链式存储下的查找：#include#includetypedef struct LNode float xishu; int zhishu; struct LNode *next; LNode,*LinkList;LinkList save( )int i,n;scanf(%d,&n);LinkList L,p;L=(LinkList)malloc(sizeof(LNode);L-next=NULL;for(i=n;i0;-i)p=(LinkList)malloc(sizeof(LNode);scanf(%f,&p-xishu);scanf(%d,&p-zhishu);p-next=L-next;L-next=p;return L;void main()LinkList L;L=save();L=L-next;while(L!=NULL)printf(%f,%d,L-xishu,L-zhishu);L=L-next;printf(n);（3） 线性表在链式存储下的删除：#include#includetypedef struct LNode float xishu; int zhishu; struct LNode *next; LNode,*LinkList;LinkList save( )int i,n;scanf(%d,&n);LinkList L,p;L=(LinkList)malloc(sizeof(LNode);L-next=NULL;for(i=n;i0;-i)p=(LinkList)malloc(sizeof(LNode);scanf(%f,&p-xishu);scanf(%d,&p-zhishu);p-next=L-next;L-next=p;return L;LinkList del(LinkList L,LinkList &e)/删除单链线性表的第i个元素int i,j;LinkList p,q;scanf(%d,&i);p=L;j=0;while(p-next &jnext ;+j;q=p-next;p-next=q-next;return L;void print(LinkList L)L=L-next;while(L)printf(%f,%dn,L-xishu,L-zhishu);L=L-next;void main()LinkList L,e;L=save();print(L);del(L,e);print(L);（4） 线性表在链式存储下的插入：#include#includetypedef struct LNode float xishu; int zhishu; struct LNode *next; LNode,*LinkList;LinkList save( )int i,n;scanf(%d,&n);LinkList L,p;L=(LinkList)malloc(sizeof(LNode);L-next=NULL;for(i=n;i0;-i)p=(LinkList)malloc(sizeof(LNode);scanf(%f,&p-xishu);scanf(%d,&p-zhishu);p-next=L-next;L-next=p;return L;LinkList insert(LinkList L,LinkList &e)/在单链线性表的第i个位置之前插入元素e(m,n) int i,j,n;float m;LinkList p,q;scanf(%d,&i);p=L;j=0;scanf(%f,&m);scanf(%d,&n);while(p-next &jnext ;+j;if(!p|ji-1)exit (0);q=(LinkList)malloc(sizeof(LNode);q-xishu=m;q-zhishu=n;q-next=p-next;p-next=q;return L;void print(LinkList L)L=L-next;while(L)printf(%f,%dn,L-xishu,L-zhishu);L=L-next;void main()LinkList L,e;L=save();print(L);insert(L,e);print(L);（5） 线性表在链式存储下的加法、乘法：#include #include typedef struct linknode /定义节点float coef;int exp;struct linknode * next;polynomial;polynomial * creatlist() /创建单链表float x; /节点中存放项系数和指数int z;polynomial *head,*r,*n; /下指针,分别是头指针、尾指针和新建立节点的指针head=(polynomial *)malloc(sizeof(polynomial);/malloc分配内存单元给头指针申请空间head-next=NULL; /头指针next指向空位空链表状态r=head; printf(建立一元多项式:(以系数0结束)n);/打印文字提醒用户输入while(x!=0) /建立单链表n=(polynomial *)malloc(sizeof(polynomial); /建立新节点,将用户输入的数据分别作为项(各节点)的系数和指数n-coef=x;n-exp=z;r-next=n; /为指针指向下一新建节点r=r-next; /后移尾指针/r=n;printf(请按升幂输入系数和指数:); scanf(%f%d,&x,&z);r-next=NULL;head=head-next; /链接节点使之勾成链表return (head); /还回head指针(链表头标志或是说地址)给函数调用者void print(polynomial * head) /打印输出函数polynomial *p; /为传入的链表设立当前指针p=head-next; /将指针后移指向包含实际数据的节点while(p!=NULL) /判断需要打印的链表是否为空printf(%.2fX(%d) ,p-coef,p-exp);/打印当前指针所指项的数据p=p-next; /后移指针指向下一节点printf(n); polynomial * polyadd(polynomial *A,polynomial *B) /核心算法实现两链表的加法运算并将结果保存在A中polynomial *p,*q,*s,*r; /为链表设立指针分别指向链表A和链表B(多项式A和B)，s为临时存放为后续移动指针做地址保留float x;p=A-next;q=B-next;s=A;/*/ /s作为p的前驱while(p!=NULL)&(q!=NULL) /判断所比较链表是否为空不同时为空时反复执行下列函数if(p-exp)(q-exp) /将q插入p之前 r=q-next; /保存当前q的下一结点地址为r后移作准备q-next=p; /将p接到到q之后s-next=q; /将q彻底的插入到A链表中p之前作为结果项之一s=q; /修改当前指针为下一节点作比较准备q=r;else if(p-exp)exp) /将p作为结果项之一，后移p进行下一结点比较s=p; /后移sp=p-next; /后移当前指针p指向下一节点else /当前链表中节点的指数相等进行系数加法运算x=(p-coef)+(q-coef); /实现系数相加赋给x，节点中的系数单元 if(x!=0) /判断系数和是否为零,不为零执行系数替换原有数据p-coef=x;s=p; /p的前驱指针后移else /系数和为零s-next=p-next; /为释放p准备free(p);p=s-next; /p指针指向下一节点 r=q; /为释放q作准备q=q-next; /q 指向下一节点free(r); if(q!=NULL) /循环结束将q中剩余节点直接插入p的为节点之后作为结果项s-next=q;free(B); /运算结束释放B链锁占空间return A; /还回A链给函数调用者 polynomial * polyand(polynomial *A,polynomial *B) /核心算法实现两链表的乘法运算polynomial * p,* q,* n,* head,* r,* temp,* m; /定义当前指针p，q风别指向两链表和头指针，尾指针，及新生成节点n int exp; /定义整型指数float coef; /定义浮点型系数head=(polynomial *)malloc(sizeof(polynomial); /创头节点为新生链表准备head-next=NULL; /置空链表 r=head; /临时变量，为后移指针做准备p=A-next; /当前指针跳过A链表头指向实际运算数while(p!=NULL) /控制操作，循环A链表与内部while所控制B链表进行项之间的运算temp=(polynomial *)malloc(sizeof(polynomial); /在内部创头节点为新生链表准备 即A中每一项与B中各项相乘构成一新链表temp-next=NULL; /置空链表 m=temp; /临时变量，为后移指针做准备q=B-next; /当前指针跳过B链表头指向实际运算数while(q!=NULL) n=(polynomial *)malloc(sizeof(polynomial); /建立新节点exp=p-exp+q-exp; /进行系数相加操作 coef=p-coef*q-coef; / /进行指数相乘操作n-coef=coef; /赋值新节点的系数域n-exp=exp; /赋值新节点的指数域 m-next=n; /链接节点至头结点，构成链表m=m-next; /后移指针，为下一节点做准备q=q-next; /控制B链表下一项/printf(%f %d ,coef,exp); /调试用p=p-next; /控制A链表下一项m-next=NULL; /链表尾置空/head=head-next;polyadd(head,temp); /return head; void selet(polynomial * A,po