最新数据结构一元多项式课程设计报告

《数据结构课程设计》

报告

学 号： JV144033 姓 名： 朱凌 年 级： 2014级 专 业： 软件工程 指导老师： 施东东 黄晓梅 完成日期： 2016 年 9 月

安徽大学江淮学院

理工部

一元多项式计算

一、实验内容

（一元多项式的计算问题）要求能够按照指数降序排列建立并输出一元多项式；能够完成两个一元多项式的相加、相减，并将结果输入

二、需求分析

本程序关键点是如何将输入的两个多项式相加、相减操作。 ①如何将输入的一元多项式按指数的降序排列 ②如何确定要输入的多项式的项数；

③如何将输入的两个一元多项式显示出来。

④如何将输入的两个一元多项式进行相加操作。 ⑤如何将输入的两个一元多项式进行相减操作。 本程序是通过链表实现一元多项式的相加减操作。

三、概要设计、详细设计

（1）多项式的输入

先输入多项式的项数，采用尾插法的方式，输入多项式中一个项的系数和指数，就产生一个新的节点，建立起它的右指针，并用头节点指向它； （2） 两个多项式的加法

“和多项式”链表中的结点无需另生成，而应该从两个多项式的链表中摘取。其运算规则如下：

假设指针A和B分别指向多项式a和多项式b中当前进行比较的某个结点，则比较两个结点中的指数项，有下列3种情况：

①指针A所指结点的指数值<指针B所指结点的指数值，则应摘取A指针所指结点插入到“和多项式”链表中去；

②指针A所指结点的指数值>指针B所指结点的指数值，则应摘取指针A所指结点插入到“和多项式”链表中去；

③指针A所指结点的指数值=指针B所指结点的指数值，则将两个结点中的系数相加， 若和数不为零，则修改A所指结点的系数值，同时释放B所指结点；反之，从多项式A的链表中删除相应结点，并释放指针A和B所指结点。例如，由图2中的两个链表表示的多项式相加得到的“和多项式”链表如图2所示，图中的长方框表示已被释放的结点。

图2 相加得到的和多项式

上述多项式的相加过程归并两个有序表的过程极其类似，不同之处仅在于，后者在比较数据元素时只出现两种情况。因此，多项式相加的过程也完全可以利用线性链表的

1

基本操作来完成。

（3）两个多项式的减法

两个多项式的减法实现，依然调用的是多项式加法的函数，只是在调用前，把多项式二的系数全部变为相反数c.coef=-c.coef;，然后多项式一和多项式二相加，这样就实现了多项式的相减。流程图如上。

（4）两个多项式相加就是两个多项式中同指数项的对应系数相加，若和不为零，则形成“和多形式”中的一项，所有指数不同的项均直接移位至“和多项式”中，流程图如图4： 1、算法思想：

（1） 输入并建立多项式——InitList()

（2） 输入多项式，输出形式为整数序列，这个输入功能在主函数实现

（3） 多项式a和b相加，建立多项式a+b，输出相加的多项式——AddPolyn(A，B) （4） 多项式a和b相减，建立多项式a-b，相减的功能调用的依然是相加的子函数 2、算法描述： A:建立多项式链表

多项式单链表可以用尾插法建表来生成。

LNode *InitList()//创建链表 {

LNode *L;

L=(LNode*)malloc(sizeof(LNode)); L->next=NULL; return(L); }

void ChaLNode(LNode *L,ElemType x)//插入链表函数 {

LNode *s,*p;

s=(LNode*)malloc(sizeof(LNode)); s->data=x; p=L;

while(p->next) p=p->next; s->next=NULL; p->next=s; }

B: 按照指数降序排列

void Invert(LNode *L)//逆序输出链表 {LNode *p,*q,*r; p=L->next; q=p->next; while(q!=NULL) {r=q->next; q->next=p; p=q; q=r; }

2

L->next->next=NULL; L->next=p; }

C：比较

if (a->expn < b->expn)｛ pre=p;

p=p->next;｝//如果多项式a的指数小于多项式b的指数，则指针P后移 if (a->expn > b->expn)｛ pre->next=q; pre=pre->next;

q=q->next;｝ //如果多项式a的指数小于多项式b的指数，q后移 这个模块主要是比较两个多项式的指数大小 D、两个一元多项式的相加

while(p&&q)//判断q,p是不是为空，如果不为空则继续往下进行 {

a=p->data.expn;b=q->data.expn; if(a

pre=p;p=p->next;//p后移 }

if(a==b) {

sum=p->data.coef+q->data.coef;//当a，b相等，即指数相同，则系数相加 if(sum!=0)//判断sum是为0，如果不为0则保留该节点 {

p->data.coef=sum; B=q; pre=p; p=p->next; q=q->next； free(B); }

Else //如果sum为0即系数为0，则删除该节点 {

temp=p;p=p->next;

pre->next=p;free(temp); B=q;q=q->next;free(B);

} }

if(a>b) {

pre->next=q; pre=pre->next; q=q->next; }}

if(q) //如果q中还有剩余，那么把q中剩余的项加到pre->next中 pre->next=q; return(A); }

3

两个一元多项式相加的法则是：两个多项式中同指数项的对应系数相加，若和不为零，则形成“和多项式”中的一项；所有指数不同的项均直接移位至“和多项式”中。如果和为零，则删除该节点。 E：输出一个一元多项式

void Print(LNode *L)//输出多项式 {

LNode *p;

int flag = 0;float i = 1.0; p=L->next; while(p) {

if (p->data.coef<0) //系数小于0直接输出 {

if (p->data.coef != -1) {

if (p->data.expn != 0)

{if(p->data.expn!=printf(\if (p->data.expn == 1) printf(\}

if (p->data.expn == 0 printf(\}

if (p->data.coef == -1) {

if (p->data.expn != 0) {

if (p->data.expn != 1)printf(\if (p->data.expn == 1) printf(\

}if (p->data.expn == 0) printf(\}}

if (p->data.coef>0) //系数大于0时，考虑是否为第一项，是则去掉加号输出，不是则输出第一项 {if (flag)

{if (p->data.coef != 1) {if (p->data.expn != 0) {if(p->data.expn!=1)

printf(\if (p->data.expn == 1) printf(\}

if (p->data.expn == 0)

printf(\}

if (p->data.coef == 1) {

if (p->data.expn != 0) {if (p->data.expn != 1)

4

printf(\else printf(\}

if (p->data.expn == 0) printf(\} }

if (!flag) //是第一项 {

if (p->data.coef!=1) {

if (p->data.expn != 0) {

if(p->data.expn!=1)

printf(\else printf(\}

if (p->data.expn == 0)

printf(\}

if (p->data.coef== 1) {

if (p->data.expn != 0) {

if (p->data.expn != 1)

printf(\else printf(\}

if (p->data.expn == 0) printf(\} } }

if (p->data.coef== 0) //系数为0直接输出0 {

printf(\}

p = p->next; flag++; }

printf(\

}F：一元多项式相减

两个多项式的减法实现，并没有单独的建立一个子函数来实现这个功能，和多项式的相加一样，依然调用的是多项式加法的函数，只是在调用前，把多项式二的系数全部变为相反数c.coef=-c.coef;，然后多项式一和多项式二相加，这样就实现了多项式的相减，开

5

始我建立一个实现多项式减法的子函数，最后为了程序的简洁最后还是改成了调用多项式相加函数

G：逆序输出链表的实现

void Invert(LNode *L)//逆序输出链表 {LNode *p,*q,*r; p=L->next; q=p->next; while(q!=NULL) {r=q->next; q->next=p; p=q; q=r; }

L->next->next=NULL; L->next=p; }

H、main（）主函数 void main()

{LNode *La,*Lb;ElemType c; int a,i,k; for(;1;){

La=InitList(); Lb= InitList(); Menu();

printf(\请选择功能：\

switch(k){ case 1 :

printf(\一元多项式相加===========\\t\\t\ printf(\输入多项式一的项数:\ scanf(\if(a<=0){

printf(\不能小于1!\\n\

printf(\请从新输入多项式一的项数：\scanf(\ } for(i=0;i

printf(\输入多项式一第%d项系数和指数:\ scanf(\while((int)c.expn!=c.expn) {

printf(\输入指数不是整数，请重新输入! scanf(\

6

\

ChaLNode(La,c); }

printf(\输入多项式二的项数:\ scanf(\

if(a<=0){

printf(\不能小于1!\\n\

printf(\请从新输入多项式一的项数：\scanf(\

for(i=0;i

printf(\输入多项式二第%d项系数和指数:\ scanf(\while((int)c.expn!=c.expn) {

}

printf(\输入指数不是整数，请重新输入! \ scanf(\

ChaLNode(Lb,c); }

printf(\多项式一为：\ printf(\多项式二为：\ printf(\多项式和为：\ Invert(La)； Print(La);printf(\ case 0: break;

default: printf(\输入错误，重新输入!\}

if(k==0)break;

printf(\

在主函数中调用函数进行多项式的输入、输出，运用选择语句来选择加法、减法进行操作

四、调试分析

调试中遇到的问题与解决办法

1、语法错误及修改，编译中出现的语法问题主要在于子函数和变量的定义，括号的

7

配对，关键字和函数名的书写，以及库函数的规范使用，这些问题都 可以通过提示，对应的将其解决

2、我通过调试运行后发现，计算完成打印结果后马上就会退出。程序在运行起来以后，没有一个可以让程序暂时停止的地方，比如要求用户输入，或者什么的，程序顺序执行之后就退出了。

3、运行成功后，但是到最后输出结果的时候总是出现错误。通过对算法的分析发现，算法不正确，修改后最终完成了程序的调试

五、测试结果、使用说明

如

图

：

一

元

多

项

式

加

法

运

算

结

果

如

下

：

使用说明：根据提示选择多项式的加法：1。相加2.退出，比如选1，然后再根据提示输入一个一元多项式的项数。按enter键，依次输入非零项，例如3个非零项，要输入6个数，有3个指数，3个系数。按enter键，然后就会自动输出刚才输入的两个多项式

8

及相加后的结果，然后还可以继续选择运算。如果退出选择0.

停车场管理系统

一、实验内容

设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。

二、需求分析

1、以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行 模拟管理。

2、栈以顺序结构实现，队列以链表实现。

三、概要设计

为实现上述算法，需用到抽象数据类型栈、队列定义如下：

void InitStack(SeqStackCar *); 当栈未满时，就把到达的车辆进栈。 int InitQueue(LinkQueueCar *); 当栈满了时，车辆就进入便道上的队列中

9

int Arrival(SeqStackCar *,LinkQueueCar *); 车辆到达时，先登记车辆车牌号码。然后再判断停车场有没 有停满，没停满就进栈，停满了就停在便道上，即进队列。

void Leave(SeqStackCar *,SeqStackCar *,LinkQueueCar *;

通过输入离开车辆的位置处理，然后调用PRINT(CarNode *p,int room)函数进行收 费。然后再判断便道上有没有车，如果有，就把便道上的车进停车场内。 void List(SeqStackCar,LinkQueueCar);

用个switch()函数选择显示车场内或是便道上的车辆情况。包括对下面两个子函数的 调用: void List1(SeqStackCar *S); void List2(LinkQueueCar *W);

void PRINT(CarNode *p,int room);

这个函数由车辆离开的函数调用，以分钟计时算费，但只能计算当天之内的费用，如 果第二天的话会导致计费为负或减少。即只能当天停，当天开走。

四、详细设计

1.栈的初始化

void InitStack(SeqStackCar *s){ int i;

s->top=0;

for(i=0;i<=MAX;i++) s->stack[s->top]=NULL; }

2.队列的初始化

int InitQueue(LinkQueueCar *Q){

Q->head=(QueueNode *)malloc(sizeof(QueueNode)); if(Q->head!=NULL) {

Q->head->next=NULL; Q->rear=Q->head; return(1); }

else return(-1); }

3.车辆收费

void PRINT(CarNode *p,int room){ int A1,A2,B1,B2;

printf(\车辆离开的时间:\

scanf(\ printf(\离开车辆的车牌号为:\ puts(p->num);

10

printf(\其到达时间为: %d:%d\ printf(\离开时间为: %d:%d\ A1=p->reach.hour; A2=p->reach.min; B1=p->leave.hour; B2=p->leave.min;

printf(\应交费用为: %2.1f元\free(p); }

4.车辆的到达登记

int Arrival(SeqStackCar *Enter,LinkQueueCar *W){ CarNode *p; int a=0;

QueueNode *t;

p=(CarNode *)malloc(sizeof(CarNode)); flushall();

printf(\请输入车牌号(例:豫B1234):\ gets(p->num); a=Enter->top; if(a!=0) {

/***********************************************************/ if(strcmp(p->num,Enter->stack[a]->num)==0) { printf(\输入的车牌号重复，请重新输入\ return(1); }

/********************************************************/ }

if(Enter->top

Enter->top++;

printf(\车辆在车场第%d位置.\ printf(\车辆到达时间:\

scanf(\

if((p->reach.hour>=24)||(p->reach.hour<0)||(p->reach.min>59)||(p->reach.min<0)) { printf(\时间输入错误！\ return (1); }

Enter->stack[Enter->top]=p; return(1); } else

11

{

printf(\该车须在便道等待!有车位时进入车场\ t=(QueueNode *)malloc(sizeof(QueueNode)); t->data=p;

t->next=NULL; W->rear->next=t; W->rear=t; return(1); } }

5.车辆的离开

void Leave(SeqStackCar *Enter,SeqStackCar *Temp,LinkQueueCar *W) {

int room;

CarNode *p,*t; QueueNode *q; if(Enter->top>0)

// 判断车场是否为空 {

while(1) {

printf(\请输入车在车场的位置/1--%d/：\ scanf(\

if(room>=1&&room<=Enter->top) break; else printf(\输入有误,请重输: \ }

while(Enter->top>room)

// 把要删除的车辆的前面的车开出来，进临时栈。 {

Temp->top++;

Temp->stack[Temp->top]=Enter->stack[Enter->top]; Enter->stack[Enter->top]=NULL; Enter->top--; }

p=Enter->stack[Enter->top]; // 把要删除的车辆节点赋给p。 Enter->stack[Enter->top]=NULL; Enter->top--;

while(Temp->top>=1)

// 再把临时栈里德车辆进停车场 {

Enter->top++;

Enter->stack[Enter->top]=Temp->stack[Temp->top]; Temp->stack[Temp->top]=NULL; Temp->top--; }

PRINT(p,room);

12

// 调用计费函数计费。

if((W->head!=W->rear)&&Enter->top

q=W->head->next; t=q->data;

Enter->top++;

printf(\便道的%s号车进入车场第%d位置.\ printf(\请输入%s号车进入车场的时间:\ scanf(\

W->head->next=q->next;

if(q==W->rear) W->rear=W->head; Enter->stack[Enter->top]=t; free(q); }

else printf(\便道里没有车.\\n\ }

else printf(\车场里没有车.\ }

6.显示车场里的车辆情况

void List1(SeqStackCar *S) { int i;

if(S->top>0) {

printf(\车场:\

printf(\位置到达时间车牌号\\n\ for(i=1;i<=S->top;i++) {

printf(\

printf(\ puts(S->stack[i]->num); } }

else printf(\车场里没有车\ }

7.显示便道上的车辆情况

void List2(LinkQueueCar *W) {

QueueNode *p; int i;

p=W->head->next; if(W->head!=W->rear) {

printf(\等待车辆的号码为:\ for(i=1; (p!=NULL); i++)

13

{

printf(\第%d 车辆.\ puts(p->data->num); p=p->next ; } }

else printf(\便道里没有车.\ printf(\ }

8.显示,遍历

void List(SeqStackCar S,LinkQueueCar W) { int flag,tag; flag=1; while(flag) {

printf(\查看车辆列表显示:\

printf(\车场列表\\n 2.便道列表\\n 3.返回主菜单\\n\ printf(\请选择1~3:\ while(1) {

scanf(\

if(tag>=1 && tag<=3) break;

else printf(\输入有误,请重新选择1~3:\ }

switch(tag) {

case 1:List1(&S);break; case 2:List2(&W);break; case 3:flag=0;

system(\ break; default: break; } } }

9.main函数 void main()

{

SeqStackCar Enter,Temp; LinkQueueCar Wait; int ch;

system(\InitStack(&Enter); InitStack(&Temp); InitQueue(&Wait); while(1)

14

本文来源：https://www.bwwdw.com/article/1w92.html