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

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

共完成4個題目：

1.一元稀疏多項(xiàng)式計(jì)算器

2.成果分析問題

3.背包問題

4.八皇后問題

編程語言：VC6.0

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

二．一元稀疏多項(xiàng)式計(jì)算器

問題描述：

1.1輸入并建立多項(xiàng)式；

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

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

1.3多項(xiàng)式a和b相加，建立多項(xiàng)式a+b；

1.4多項(xiàng)式a和b相減，建立多項(xiàng)式a-b。

1.5多項(xiàng)式a和b相乘，建立乘積多項(xiàng)式ab。

需求分析：

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

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

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

造的一元多項(xiàng)式

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

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

+cnx^en

設(shè)計(jì)思路：

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

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

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

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

令指針p后移。

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

點(diǎn)p的系數(shù)。

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

將結(jié)點(diǎn)q插入在結(jié)點(diǎn)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è)計(jì)

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

typedefstructPolynomial{

floatcoef;//系數(shù)

intexpn;//指數(shù)

structPolynomial*next;

}*Polyn,Polynomial;

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

PolynCreatePolyn(Polynhead,intm){

inti;

Polynp;

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

head->next=NULL;

for(i=0;i

#include//定義多項(xiàng)式的項(xiàng)

typedefstructPolynomial{

floatcoef;//系數(shù)

intexpn;//指數(shù)

structPolynomial*next;

}*Polyn,Polynomial;

voidInsert(Polynp,Polynh){

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

else

{

Polynq1,q2;

q1=h;

q2=h->next;

while(q2

q2=q2->next;

}

if(q2

free(p);

if(!q2->coef)

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

q1->next=q2->next;

free(q2);

}

}

else

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

p->next=q2;

q1->next=p;

}

}

}

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

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;//項(xiàng)數(shù)計(jì)數(shù)器

if(!q)

{//若多項(xiàng)式為空，輸出0

putchar('0');

printf("\n");

return;

}

while(q)

{

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

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多項(xiàng)式已空，但b多項(xiàng)式非空

elsereturn1;//b多項(xiàng)式已空，但a多項(xiàng)式非空

}

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

Polynqa=pa->next;

Polynqb=pb->next;

Polynheadc,hc,qc;

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

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);//當(dāng)相加系數(shù)為0時，釋放該結(jié)點(diǎn)

}

returnheadc;

}

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

Polynh=pb;

Polynp=pb->next;

Polynpd;

while(p)