數(shù)據(jù)結(jié)構(gòu)課程設(shè)計模板結(jié)構(gòu)設(shè)計說明

1/1數(shù)據(jù)結(jié)構(gòu)課程設(shè)計模板結(jié)構(gòu)設(shè)計說明數(shù)據(jù)結(jié)構(gòu)課程設(shè)計模板結(jié)構(gòu)設(shè)計一．課程設(shè)計概述

共完成4個題目：

1.一元稀疏多項式計算器

2.成果分析問題

3.背包問題

4.八皇后問題

編程語言：VC6.0

運行環(huán)境：Windows8.0

二．一元稀疏多項式計算器

問題描述：

1.1輸入并建立多項式；

1.2輸出多項式，輸出形式為整數(shù)序列：n，c1,e1,c2,e2,………cn,en,

其中n是多項式的項數(shù)，ci和ei分別是第i項的系數(shù)和指數(shù)，序列按指數(shù)降序排列；

1.3多項式a和b相加，建立多項式a+b；

1.4多項式a和b相減，建立多項式a-b。

1.5多項式a和b相乘，建立乘積多項式ab。

需求分析：

2.1定義線性表的動態(tài)安排挨次存儲結(jié)構(gòu)；

2.2建立多項式存儲結(jié)構(gòu)，定義指針*next

2.3利用鏈表實現(xiàn)隊列的構(gòu)造。每次輸入一項的系數(shù)和指數(shù)，可以輸出構(gòu)

造的一元多項式

2.4演示程序以用戶和計算機的對話方式執(zhí)行，即在計算機終站上顯示

“提示信息”之后，由用戶在鍵盤上輸入演示程序中規(guī)定的運行命令；最終依據(jù)相應(yīng)的輸入數(shù)據(jù)（濾去輸入中的非法字符）建立的多項式以及多項式相加的運行結(jié)果在屏幕上顯示。多項式顯示的格式為：c1x^e1+c2x^e2+…

+cnx^en

設(shè)計思路：

要解決多項式相加，必需要有多項式，所以必需首先建立兩個多項式，在這里采納鏈表的方式存儲鏈表，所以我將結(jié)點結(jié)構(gòu)體定義為

運用尾插法建立兩條單鏈表，以單鏈表polynp和polynh分別表示兩個一元多項式a和b，a+b的求和運算等同于單鏈表的插入問題（將單鏈表polynp中的結(jié)點插入到單鏈表polynh中），因此“和多項式”中的結(jié)點無須另生成。

為了實現(xiàn)處理，設(shè)p、q分別指向單鏈表polya和polyb的當前項，比較p、q結(jié)點的指數(shù)項，由此得到下列運算規(guī)章：

①若p->expnexpn，則結(jié)點p所指的結(jié)點應(yīng)是“和多項式”中的一項，

令指針p后移。

②若p->expn=q->expn，則將兩個結(jié)點中的系數(shù)相加，當和不為0時修改結(jié)

點p的系數(shù)。

③若p->expn>q->expn，則結(jié)點q所指的結(jié)點應(yīng)是“和多項式”中的一項，

將結(jié)點q插入在結(jié)點p之前，且令指針q在原來的鏈表上后移。

4、數(shù)據(jù)測試

（1）、(2x+5x^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7);

（2）、(2x+5x^8-3.1x^11)-(7-5x^8+11x^9)=-3.1x^11-11x^9+10x^8+12x-7;

(3)(2x+5x^8-3.1x^11)*(7-5x^8+11x^9)=34.1x^20+15.5x^19+55x^17-25x^16-21.7x^11+22x^10-10x^9+35x^8+14x

概要設(shè)計

1.元素類型、結(jié)點類型和指針類型：

typedefstructPolynomial{

floatcoef;//系數(shù)

intexpn;//指數(shù)

structPolynomial*next;

}*Polyn,Polynomial;

2、建立一個頭指針為head、項數(shù)為m的一元多項式,建立新結(jié)點以接收數(shù)據(jù),調(diào)用Insert函數(shù)插入結(jié)點:

PolynCreatePolyn(Polynhead,intm){

inti;

Polynp;

p=head=(Polyn)malloc(sizeof(structPolynomial));

head->next=NULL;

for(i=0;i

#include//定義多項式的項

typedefstructPolynomial{

floatcoef;//系數(shù)

intexpn;//指數(shù)

structPolynomial*next;

}*Polyn,Polynomial;

voidInsert(Polynp,Polynh){

if(p->coef==0)free(p);//系數(shù)為0的話釋放結(jié)點

else

{

Polynq1,q2;

q1=h;

q2=h->next;

while(q2

q2=q2->next;

}

if(q2

free(p);

if(!q2->coef)

{//系數(shù)為0的話釋放結(jié)點

q1->next=q2->next;

free(q2);

}

}

else

{//指數(shù)為新時將結(jié)點插入

p->next=q2;

q1->next=p;

}

}

}

PolynCreatePolyn(Polynhead,intm){//建立一個頭指針為head、項數(shù)為m的一元多項式

inti;

Polynp;

p=head=(Polyn)malloc(sizeof(structPolynomial));

head->next=NULL;

for(i=0;inext;

q2=q1->next;

while(q1->next)

{

free(q1);

q1=q2;

q2=q2->next;

}

}

voidPrintPolyn(PolynP){

Polynq=P->next;

intflag=1;//項數(shù)計數(shù)器

if(!q)

{//若多項式為空，輸出0

putchar('0');

printf("\n");

return;

}

while(q)

{

if(q->coef>0//系數(shù)大于0且不是第一項

if(q->coef!=1

if(q->expn==1)putchar('X');

elseif(q->expn)printf("X^%d",q->expn);

}

else

{

if(q->coef==1)

{

if(!q->expn)putchar('1');

elseif(q->expn==1)putchar('X');

elseprintf("X^%d",q->expn);

}

if(q->coef==-1)

{

if(!q->expn)printf("-1");

elseif(q->expn==1)printf("-X");

elseprintf("-X^%d",q->expn);

}

}

q=q->next;

flag++;

}

printf("\n");

}

intcompare(Polyna,Polynb){

if(a

elseif(!a||a->expnexpn)return-1;

elsereturn0;

}

elseif(!a//a多項式已空，但b多項式非空

elsereturn1;//b多項式已空，但a多項式非空

}

PolynAddPolyn(Polynpa,Polynpb){//求解并建立多項式a+b，返回其頭指針

Polynqa=pa->next;

Polynqb=pb->next;

Polynheadc,hc,qc;

hc=(Polyn)malloc(sizeof(structPolynomial));//建立頭結(jié)點

hc->next=NULL;

headc=hc;

while(qa||qb)

{

qc=(Polyn)malloc(sizeof(structPolynomial));

switch(compare(qa,qb)){

case1:

{

qc->coef=qa->coef;

qc->expn=qa->expn;

qa=qa->next;

break;

}

case0:

{

qc->coef=qa->coef+qb->coef;

qc->expn=qa->expn;

qa=qa->next;

qb=qb->next;

break;

}

case-1:

{

qc->coef=qb->coef;

qc->expn=qb->expn;

qb=qb->next;

break;

}

}

if(qc->coef!=0)

{

qc->next=hc->next;

hc->next=qc;

hc=qc;

}

elsefree(qc);//當相加系數(shù)為0時，釋放該結(jié)點

}

returnheadc;

}

PolynSubtractPolyn(Polynpa,Polynpb){//求解并建立多項式a-b，返回其頭指針

Polynh=pb;

Polynp=pb->next;

Polynpd;

while(p)