数据库实验

实验一 线性表及其应用

一、 实验目的和要求

1、掌握线性表的插入、删除、查找等基本操作设计与实现

2、学习利用线性表提供的接口去求解实际问题

3、熟悉线性表的的存储方法

二、 实验内容和原理

1、实验内容：设计一个一元多项式的简单计算器，其基本功能有

①输入并建立多项式；②输出多项式；③多项式相加。可利用单链

Visual C++ 6.0 及 PC 机

四、 算法描述及实验步骤

思想算法：

以线性表来描述一元多项式，存储结构采用单链表，每个结点存储的多项

式中某一项的系数和指数，建立单链表时指数高的结点列于指数低的结点之后，

即线性表的元素按指数递增有序排列。

例如构造两个多项式 ha: 5X3+4X2+3X+2

hb: X2+X+1

多项式加法：定义指针 p,q 分别指向 ha,hb

多项式乘法：定义指针 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. p<maxp, gp=gp->next;

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

五、 实验结果

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

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

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

mulpoly *creatpoly()/*建立多项式列表*/

{mulpoly *head,*r,*s;/*设中间变量*/

int m,n;

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

printf("\ninput coef and exp:\n");

scanf("%d%d",&n,&m);/*输入多项式系数和指数*/

r=head;/*尾指针指向头指针*/

while(n!=0)/*将输入的多项式存放在 S 中*/

{s=(mulpoly*)malloc(sizeof(mulpoly));

r=s;

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

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));/*申请结点空间*/

r->exp=q->exp;

r->coef=x;

s->next=r;

s=r;

}

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

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

}

else if(p->exp<q->exp)/*比较指数大小*/

{r=(mulpoly *)malloc(sizeof(mulpoly));

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 中不为空时照抄*/