实验2. 线性表及其应用.

【实验题目】

实验2. 线性表及其应用.

【问题描述】

用C 或C++语言设计并实现一个一元稀疏多项式的简单计算器。

【基本要求】

一元稀疏多项式简单计算器的基本功能是：

① 输入并建立多项式

② 输出多项式，序列按指数降序排列

③ 多项式A (x ) 和B (x ) 相加，并建立多项式A (x )+B (x )

④ 多项式A (x ) 和B (x ) 相减，并建立多项式A (x )-B (x )

⑤ 给定 x 的值，计算多项式。

【实现提示】

用带头节点的单链表作为多项式的存储结构。

一、【概要设计】

(1)定义结构体如下：

ADT List{

数据对象：D={ai|ai属于ElemSet,I=1,2,3,4,…….n,n>=0}

数据关系:R1={|ai-1,ai属于D,I=1,2,3,…n}

typedef struct node

{

float coef;

int expn;

struct node *next;

}Lnode, *polynmial;

创建结构体

create(L);

操作结果：创建链表L

display(L);

初始条件：L 必须存在

操作结果：显示L

sort(L);

初始条件：L 必须存在

操作结果：对L 进行排序

reverse(L);

初始条件：heada,headb 必须存在

操作结果：对L 进行逆置

select();

操作结果：进行选择操作

add(La, Lb, Lc);

初始条件：La Lb Lc 必须存在

操作结果：La Lb相加 结果存在Lc 中

subtract(La, Lb, Ld);

初始条件：La Lb Ld必须存在

操作结果：La Lb 相减 结果存在Ld 中

2主程序模块、各子程序模块的伪码说明

typedef struct node

{

float coef;

int expn;

struct node *next;

}Lnode, *polynmial;

void create(polynmial &L);

//输入并建立多项式L

void display(polynmial L);

//显示，输出多项式L

void sort(polynmial &L);

//多项式L 按指数排序

void reverse(polynmial &L);

//逆置

void select();

//用户选择加减操作

void add(polynmial La, polynmial Lb, polynmial &Lc); //多项式La,Lb 相加

void subtract(polynmial La, polynmial Lb, polynmial &Ld); //多项式La 减去Lb ，结果给Ld

3主程序模块与各子程序模块间的调用关系如图所示：

create(La);

sort(La)

create(Lb);

sort(Lb);

display(Lc)

subtract(La, Lb, Ld)

display(Ld)

二、【详细设计】

typedef struct node

{

float coef;

int expn;

struct node *next;

}Lnode, *polynmial;

void create(polynmial &L);

//输入并建立多项式L

void display(polynmial L);

//显示，输出多项式L

void sort(polynmial &L);

//多项式L 按指数排序

void reverse(polynmial &L);

//逆置

void select();

//用户选择加减操作

void add(polynmial La, polynmial Lb, polynmial &Lc); //多项式La,Lb 相加

void subtract(polynmial La, polynmial Lb, polynmial &Ld); //多项式La 减去Lb ，结果给Ld

三、【测试结果】

typedef struct node

{

float coef;

int expn;

struct node *next;

}Lnode, *polynmial;

void create(polynmial &L) //输入并建立多项式L

{

int i, n;

static struct node *p;

scanf("%d", &n);

L = (struct node *)malloc (sizeof(struct node));

L->next = NULL;

for(i = 0; i

{

p = (struct node *)malloc(sizeof(struct node));

scanf("%f %d", &p->coef, &p->expn);

p->next = L->next;

L->next = p;

}

}

void display(polynmial L)//显示，输出多项式L

{

struct node *p, *q;

int flag = 0;

int k = 0;

q = L->next;

while(q)

{

if(q->coef != 0)

k++;

q = q->next;

}

printf("%d, ", k);

p = L->next;

if(p->coef != 0)

{

printf("%.1f,%d, ", p->coef, p->expn);

flag++;

}

for(p = p->next; p; p = p->next)

{

if(p->coef != 0)

{

printf("%.1f,%d, ", p->coef, p->expn);

flag++;

}

}

if(flag == 0)

printf("%d\n", flag);

else

printf("\n");

}

void sort(polynmial &L)//多项式L 按指数排序

{

polynmial p, q, r, u;

p = L->next;

L->next = NULL;

while(p != NULL)

{

r = L;

q = L->next;

while((q != NULL) && (q->expn expn))

{

r = q;

q = q->next;

}

u = p->next;

r->next = p;

p->next = q;

p = u;

}

}

void reverse(polynmial &L)//逆置

{

polynmial H;

static struct node *p, *q, *s;

H = (struct node*)malloc(sizeof(struct node));

H->next = NULL;

p = (struct node*)malloc(sizeof(struct node));

s = L->next;

p->coef = s->coef;

p->expn = s->expn;

p->next = s->next;

while(s)

{

p->coef = s->coef;

p->expn = s->expn;

p->next = s->next;

q = H->next;

H->next = p;

p->next = q;

p = (struct node*)malloc(sizeof(struct node));

s = s->next;

}

p = H->next;

q = L->next;

while(p)

{

q->coef = p->coef;

q->expn = p->expn;

q = q->next;

p = p->next;

}

}

void select() //用户选择加减操作

{

printf("请选择加减操作\n");

printf("1.两个一元多项式相加\n");

printf("2.两个一元多项式相减\n");

}

void add(polynmial La, polynmial Lb, polynmial &Lc)//多项式La,Lb 相加 {

struct node *pa, *pb;

static struct node *pc;

Lc = (struct node*)malloc(sizeof(struct node));

pa = La->next;

pb = Lb->next;

Lc->next = NULL;

while(pa && pb)

{

pc = (struct node*)malloc(sizeof(struct node));

if(pa->expn expn)

{

pc->next = Lc->next;

Lc->next = pc;

pc->coef = pa->coef;

pc->expn = pa->expn;

pa = pa->next;

}

else

if(pa->expn == pb->expn)

{

pc->next = Lc->next;

Lc->next = pc;

pc->expn = pa->expn;

pc->coef = pa->coef + pb->coef;

pa = pa->next;

pb = pb->next;

}

else

{

pc->next = Lc->next;

Lc->next = pc;

pc->coef = pb->coef;

pc->expn = pb->expn;

pb = pb->next;

}

}

while(pa)

{

pc = (struct node*)malloc(sizeof(struct node)); pc->next = Lc->next;

Lc->next = pc;

pc->coef = pa->coef;

pc->expn = pa->expn;

pa = pa->next;

}

while(pb)

{

pc = (struct node*)malloc(sizeof(struct node)); pc->next = Lc->next;

Lc->next = pc;

pc->coef = pb->coef;

pc->expn = pb->expn;

pb = pb->next;

}

}

void subtract(polynmial La, polynmial Lb, polynmial &Ld)//多项式La 减去Lb ，结果给Ld

{

struct node *pa, *pb;

static struct node *pd;

Ld = (struct node*)malloc(sizeof(struct node));

pa = La->next;

pb = Lb->next;

Ld->next = NULL;

while(pa && pb)

{

pd = (struct node*)malloc(sizeof(struct node));

if(pa->expn expn)

{

pd->next = Ld->next;

Ld->next = pd;

pd->coef = pa->coef;

pd->expn = pa->expn;

pa = pa->next;

}

else

if(pa->expn == pb->expn)

{

pd->next = Ld->next;

Ld->next = pd;

pd->expn = pa->expn;

pd->coef = pa->coef - pb->coef;

pa = pa->next;

pb = pb->next;

}

else

{

pd->next = Ld->next;

Ld->next = pd;

pd->coef = pb->coef;

pd->expn = pb->expn;

pb = pb->next;

}

}

while(pa)

{

pd = (struct node*)malloc(sizeof(struct node));

pd->next = Ld->next;

Ld->next = pd;

pd->coef = pa->coef;

pd->expn = pa->expn;

pa = pa->next;

}

while(pb)

{

pd = (struct node*)malloc(sizeof(struct node));

pd->next = Ld->next;

Ld->next = pd;

pd->coef = -pb->coef;

pd->expn = pb->expn;

pb = pb->next;

}

}

3主程序模块与各子程序模块间的调用关系如图所示：

create(Lb)

三、【测试结果】

多项式相加：

多项式相减

四、【实验总结】

通过此次编写程序，可知线性表的特点有：

数据->数据元素

具有特定关系的数据元素集合->数据结构

在实际写的过程中，出现了很多的问题，主要是因为对C 语言不够熟练，所以会出现许多语法错误，这些是需要在以后改进的地方

五、【代码】

例如：

#include

#include

typedef struct pnode

{ int coef;

int exp;

struct pnode *next;

} pnode;

pnode * creat()

{int m,n;

pnode *head,*rear,*s;

head=(pnode *)malloc(sizeof(pnode)); rear=head;

printf("\n输入指数(按递增顺序输入) ："); scanf("%d",&m);

printf("输入一元式系数(0为退出) ："); scanf("%d",&n);

do

{

s=(pnode *)malloc(sizeof(pnode)); s->coef=n;

s->exp=m;

rear->next=s;

s->next=NULL;

rear=s;

printf("\n输入指数(按递增顺序输入) ："); scanf("%d",&m);

printf("输入一元式系数(0为退出) ："); scanf("%d",&n);

}while(n);

return head;

}

pnode * add(pnode *heada,pnode *headb) {pnode *headc,*a,*b,*s,*rearc;

int sum;

a=heada->next;b=headb->next;

headc=(pnode *)malloc(sizeof(pnode)); rearc=headc;

while(a!=NULL&&b!=NULL)

{

if(a->exp==b->exp)

{ sum=a->coef+b->coef;

if(sum)

{s=(pnode *)malloc(sizeof(pnode)); s->coef=sum;

s->exp=a->exp;

rearc->next=s;

rearc=s;

a=a->next;

b=b->next;}

else

{a=a->next;

b=b->next;

}

}

else if(a->expexp)

//a指数如果小于b ，则a 放到s 中// { s=(pnode *)malloc(sizeof(pnode)); s->coef=a->coef;

s->exp=a->exp;

rearc->next=s;

//用下一个结点s 取代下一个c// rearc=s;

a=a->next;

}

else //如果a 的指数大，则b 放到s 中// { s=(pnode *)malloc(sizeof(pnode)); s->coef=b->coef;

s->exp=b->exp;

rearc->next=s;

rearc=s;

b=b->next;

}

}

if(a)

{while(a!=NULL) //b空了放a 中的项// {s=(pnode *)malloc(sizeof(pnode)); s->coef=a->coef;

s->exp=a->exp;

rearc->next=s;

s->next=NULL;

rearc=s;

a=a->next;

}

}

else if(b)

{while(b!=NULL) //a空了放b 中的项// {s=(pnode *)malloc(sizeof(pnode)); s->coef=b->coef;

s->exp=b->exp;

rearc->next=s;

s->next=NULL;

rearc=s;

b=b->next;

}}

return headc;

}

void main()

{pnode *a,*b,*c;

printf("建立A:");

a=creat();

printf("\n建立B:");

b=creat();

c=add(a,b);

c=c->next;

printf("%dx^%d",c->coef,c->exp); c=c->next;

while(c!=NULL)

{printf("+%dx^%d",c->coef,c->exp); c=c->next;

}

}