线性表的应用 - 图文 

实验一 线性表及其应用

一、 实验目的和要求

1、掌握线性表的插入、删除、查找等基本操作设计与实现 2、学习利用线性表提供的接口去求解实际问题 3、熟悉线性表的的存储方法 二、 实验内容和原理

1、实验内容：设计一个一元多项式的简单计算器，其基本功能有①输入并建立多项式；②输出多项式；③多项式相加。可利用单链表或单循环链表实现之。

2、实验原理：以线性表来描述一元多项式，存储结构采用单链表，每个结点存储的多项式中某一项的系数和指数，建立单链表时指数高的结点列于指数低的 结点之后，即线性表的元素按指数递增有序排列。 三、 实验环境

Visual C++ 6.0 及PC机

四、 算法描述及实验步骤

思想算法：

以线性表来描述一元多项式，存储结构采用单链表，每个结点存储的多项式中某一项的系数和指数，建立单链表时指数高的结点列于指数低的结点之后，即线性表的元素按指数递增有序排列。

例如构造两个多项式ha: 5X3+4X2+3X+2 hb: X2+X+1 多项式加法：定义指针p,q分别指向ha,hb

i.p->exp==q->exp ,r->coef=p->coef+q->coef,pa,pb下移;

1

ii.p->expexp ,r->coef=q->coef;r->exp=q->exp;,q下移 iii.pa->exp>pb->exp, r->exp=p->exp;r->coef=p->coef;,p下移 iv.p!=NULL,pb==NULL.相当于iii. V.q==NULL,pb!=NULL.相当于ii. 其流程图如下：

多项式乘法：定义指针fp,gp分别指向f,g

1.将两多项式最大指数相加并赋于maxp，并置g 2.用for循环求指数等于maxp时相乘的系数 3. (fp!=NULL)&&(gp!=NULL), p=fp->exp+gp->exp 1.p>maxp, fp=fp->next; 2. pnext;

3.p=maxp, x+=fp->coef*gp->coef; fp=fp->next;gp=gp->next;

2

五、 实验结果

1.分别输入两个多项式: 5X3+4X2+3X+2 和X2+X+1,然后输出结果如下:

2.分别输入两个多项式：6X4+4X2+2和5X+6，然后输出结果如下：

3

六、 总结

此次上机实验应用了线性表实现了一次实际操作，完成了一个一元多项式的简单计算器，不仅对此次编译程序的算法思想有了新的认识，还让我深刻的体会到了线性表的重要性以及其应用的方便，并且对指针加深了映象，应用了书本中的算法思想，对我以后的编译以及完成新的程序有很大的帮助。

附录：

1.建立多项式列表代码如下：

mulpoly *creatpoly()/*建立多项式列表*/ {mulpoly *head,*r,*s;/*设中间变量*/ int m,n;

head=(mulpoly *)malloc(sizeof(mulpoly));/*头结点申请空间*/ printf(\

scanf(\输入多项式系数和指数*/ r=head;/*尾指针指向头指针*/

while(n!=0)/*将输入的多项式存放在S中*/ {s=(mulpoly*)malloc(sizeof(mulpoly)); s->coef=n; s->exp=m; r->next=s; r=s;

/*printf(\

scanf(\再次输入多项式系数和指数*/ }

r->next=NULL;/*将尾指针置空*/

4

head=head->next;/*将head哑结点向前跑一个结点，使其不为空*/ return (head);/*返回多项式*/ }

2.两个多项式相加代码如下：

mulpoly *polyadd(mulpoly *ha,mulpoly *hb)/*两个多项式相加*/ {mulpoly *hc,*p,*q,*s,*r;/*声明结构体型*/ int x; p=ha; q=hb;

hc=(mulpoly *)malloc(sizeof(mulpoly));/*申请结点空间*/ s=hc;

while((p!=NULL)&&(q!=NULL))/*两多项式不为空*/ if(p->exp==q->exp)/*指数相等*/ {x=p->coef+q->coef;/*系数相加*/ if(x!=0)/*系数不为零*/

{r=(mulpoly*)malloc(sizeof(mulpoly));/*结果放r中存放*/ r->exp=q->exp; r->coef=x; s->next=r; s=r; }

p=p->next;/*多项式前进一项*/ q=q->next;/*多项式前进一项*/ }

else if(p->expexp)/*比较指数大小*/ {r=(mulpoly *)malloc(sizeof(mulpoly)); r->coef=q->coef; r->exp=q->exp; s->next=r; s=r;

q=q->next; } else

{r=(mulpoly *)malloc(sizeof(mulpoly)); r->exp=p->exp; r->coef=p->coef; s->next=r; s=r;

p=p->next; }

while(p!=NULL)/*当多项式p中不为空时照抄*/ {r=(mulpoly *)malloc(sizeof(mulpoly)); r->exp=p->exp;

5