課程設(shè)計(jì)報(bào)告--一元多項(xiàng)式計(jì)算vs迷宮求解

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：docx 頁數(shù)：21 大小：65.90KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

課程設(shè)計(jì)報(bào)告--一元多項(xiàng)式計(jì)算vs迷宮求解_第1頁

已閱讀1頁，還剩20頁未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、　　課程設(shè)計(jì)報(bào)告　　一元多項(xiàng)式計(jì)算VS迷宮求解　　系別： 　　專業(yè)年級：　　學(xué)生姓名： <

2、;/p>　　學(xué) 號：　　任課老師： 　　二 ○ 一二年三月　　一、題目內(nèi)容描述　　（一）、實(shí)驗(yàn)二一元多項(xiàng)式計(jì)算*

3、*　　1、任務(wù)：能夠按照指數(shù)降序排列建立并輸出多項(xiàng)式；能夠完成兩個(gè)多項(xiàng)式的相加、相減、相乘，并將結(jié)果輸出；　　2、在上交資料中請寫明：存儲結(jié)構(gòu)、多項(xiàng)式相加的基本過程的算法（可以使用程序流程圖）、源程序、測試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；　?。ǘ?、實(shí)驗(yàn)四迷宮求解

4、　　1、任務(wù)：可以輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；　　2、要求：在上交資料中請寫明：存儲結(jié)構(gòu)、基本算法（可以使用程序流程圖）、源程序、　　測試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法。　　二、解題分析</

5、b>　?。ㄒ唬?、一元多項(xiàng)式計(jì)算分析：　　1、一元稀疏多項(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ù)

6、降序排列； 　　1.3 求多項(xiàng)式a、b的導(dǎo)函數(shù)；　　1.4 計(jì)算多項(xiàng)式在x處的值；　　1.5多項(xiàng)式a和b相加，建立多項(xiàng)式a+b；　　1.6 多項(xiàng)式a和b相減，建立多項(xiàng)式a-b。　　2、設(shè)計(jì)思路:

7、;　　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ī)終站上顯示“提示信息”之后，由用

8、戶在鍵盤上輸入演示程序中規(guī)定的運(yùn)行命令；最后根據(jù)相應(yīng)的輸入數(shù)據(jù)（濾去輸入中的非法字符）建立的多項(xiàng)式以及多項(xiàng)式相加的運(yùn)行結(jié)果在屏幕上顯示。多項(xiàng)式顯示的格式為：c1x^e1+c2x^e2+…+cnx^en　　3、設(shè)計(jì)思路分析：　　要解決多項(xiàng)式相加，必須要有多項(xiàng)式，所以必須首先建立兩個(gè)多項(xiàng)式，在這里采用鏈表的方式存儲鏈表，

9、所以我將結(jié)點(diǎn)結(jié)構(gòu)體定義為：　　運(yùn)用尾插法建立兩條單鏈表，以單鏈表polyn p和polyn h分別表示兩個(gè)一元多項(xiàng)式a和b，a+b的求和運(yùn)算等同于單鏈表的插入問題（將單鏈表polyn p中的結(jié)點(diǎn)插入到單鏈表polyn h中），因此“和多項(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)

10、，由此得到下列運(yùn)算規(guī)則：　　① 若p->expn<q->expn，則結(jié)點(diǎn)p所指的結(jié)點(diǎn)應(yīng)是“和多項(xiàng)式”中的一項(xiàng)，令指針p后移。　　② 若p->expn=q->expn，則將兩個(gè)結(jié)點(diǎn)中的系數(shù)相加，當(dāng)和不為0時(shí)修改結(jié)點(diǎn)p的系數(shù)。　　③ 若p->expn>q->expn，則

11、結(jié)點(diǎn)q所指的結(jié)點(diǎn)應(yīng)是“和多項(xiàng)式”中的一項(xiàng)，將結(jié)點(diǎn)q插入在結(jié)點(diǎn)p之前，且令指針q在原來的鏈表上后移。　?。ǘ⒚詫m求解分析：　　1、迷宮形狀由0表示可通過，用1表示是障礙。為方便用0,1輸入。并把迷宮圖形保存在二維數(shù)組grid中。而打印出的圖形中 ‘0’表示能過‘1’表示障礙。　　2、對探索過的位置加以標(biāo)記，

12、輸入起點(diǎn)終點(diǎn)后可由相應(yīng)函數(shù)來完成搜索。到目的點(diǎn)就可退出該調(diào)用程序。把每步路徑保存到二維數(shù)組中，通過反向進(jìn)行退步可把完整的路徑保存在相應(yīng)結(jié)構(gòu)體數(shù)組內(nèi)，通過標(biāo)記的路徑可將串作相應(yīng)的改變就能輸出的帶路徑的圖。　　3、根據(jù)二維字符數(shù)組和加標(biāo)記的位置坐標(biāo)，輸出迷宮的圖形。　　4、該程序在獲取迷宮圖結(jié)構(gòu)后，可對迷宮任意入口到出口的路線進(jìn)行搜索，主要由廣度優(yōu)先搜索完

13、成該操作。它可以是30以內(nèi)大小的迷宮，有自行提供的迷宮圖，本課程設(shè)計(jì)是以二維數(shù)組作為迷宮的存儲結(jié)構(gòu)。而廣度優(yōu)先搜索用的隊(duì)列一步一步完成的，從而找到的是最短路徑，并能輸出打印。　　三、所用數(shù)據(jù)結(jié)構(gòu)的描述（用偽代碼）　　（一）、一元多項(xiàng)式計(jì)算：　　1、元素類型、結(jié)點(diǎn)類型和指針類型：<p&

14、gt;　　typedef struct Polynomial{float coef; //系數(shù)　　int expn; //指數(shù)　　struct Polynomial *next;}*Polyn,Polynomial;　　2、建立一個(gè)頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式, 建立新結(jié)點(diǎn)以接收

15、數(shù)據(jù), 調(diào)用Insert函數(shù)插入結(jié)點(diǎn):　　Polyn CreatePolyn(Polyn head,int m){ int i;　　Polyn p;　　p=head=(Polyn)malloc(sizeof(struct Polynomial));　　head

16、->next=NULL;　　for(i=0;i<m;i++){p=(Polyn)malloc(sizeof(struct Polynomial)); 　　printf("請輸入第%d項(xiàng)的系數(shù)與指數(shù):",i+1);　　scanf("%f %d",&p-&

17、gt;coef,&p->expn);　　Insert(p,head); }　　return head;}　　3、調(diào)用關(guān)系圖：　?。ǘ?、迷宮求解：<p&

18、gt;　　1、各個(gè)函數(shù)說明：　　int InitStack(Stack *s) //制造空棧　　int StackEmpty(Stack *s) //若s為空返回TURE,否則返回FALSE　　int StackIsFull(Stack *s) //判斷棧是否為滿

19、　　int Push(Stack *s,MazeNode mn) //插入元素e為新的棧頂元素　　int Pop(Stack *s,MazeNode *mn) //若棧不空刪除棧頂元素用e返回OK,否則返回ERROR　　int DestroyStack(Stack *s) //銷毀棧s

20、　　int MazeInit(MazeType *maze) //初始化迷宮　　int Pass(MazeType *maze,Coordinate pos) //判斷n指定坐標(biāo)是否可通過　　int MarkerPass(MazeType *maze,Coordinate pos) //標(biāo)記可通過

21、　　Coordinate NextCoord(Coordinate pos,int i) //獲取下一位置　　int MarkerNoPass(MazeType *maze,Coordinate pos)//曾走過但不是通路標(biāo)記并返回OK　　int MazePath(MazeType *maze,Coordinate start,C

22、oordinate end)//從迷宮maze的入口到出口查找路徑　　void PrintMaze(MazeType *maze) //輸出迷宮　　四、部分算法的描述（用偽代碼）　　（一）、一元多項(xiàng)式計(jì)算：　　1、加法：</

23、p>　　Polyn AddPolyn(Polyn pa,Polyn pb){ //求解并建立多項(xiàng)式a+b，返回其頭指針　　Polyn qa=pa->next;　　Polyn qb=pb->next;　　Polyn headc,hc,qc;<p&

24、gt;　　hc=(Polyn)malloc(sizeof(struct Polynomial)); //建立頭結(jié)點(diǎn)　　hc->next=NULL;　　headc=hc;　　while(qa||qb){　　qc=(Polyn)ma

25、lloc(sizeof(struct Polynomial));　　switch(compare(qa,qb)){　　case 1:{　　qc->coef=qa->coef;　　qc->expn=qa->exp

26、n;　　qa=qa->next;　　break;}　　case 0: { 　　qc->coef=qa->coef+qb->coef;　　qc->expn=qa-&

27、gt;expn;　　qa=qa->next;　　qb=qb->next;　　break;}　　case -1:{　　qc->coef=q

28、b->coef;　　qc->expn=qb->expn;　　qb=qb->next;　　break;} 　　}　　if(qc-&g

29、t;coef!=0){　　qc->next=hc->next;　　hc->next=qc;　　hc=qc;}　　else free(qc); //當(dāng)相加系數(shù)為0時(shí)，釋放該結(jié)點(diǎn)

30、　　}　　return headc;}　　2、減法：　　Polyn SubtractPolyn(Polyn pa,Polyn pb){ //求解并建立多項(xiàng)式a-b，返回其頭指針　　Polyn h=

31、pb;　　Polyn p=pb->next;　　Polyn pd;　　while(p){ //將pb的系數(shù)取反　　p->coef*=-1;　　p=p->next;}</

32、p>　　pd=AddPolyn(pa,h);　　for(p=h->next;p;p=p->next) //恢復(fù)pb的系數(shù)　　p->coef*=-1;　　return pd;}　　3、求解x：

33、;　　float ValuePolyn(Polyn head,int x){ //輸入x值，計(jì)算并返回多項(xiàng)式的值　　Polyn p;　　int i,t;　　float sum=0;</p&g

34、t;　　for(p=head->next;p;p=p->next){　　t=1;　　for(i=p->expn;i!=0;){　　if(i<0){t/=x;i++;}//指數(shù)小于0，進(jìn)行除法

35、;　　else{t*=x;i--;}//指數(shù)大于0，進(jìn)行乘法　　}　　sum+=p->coef*t;}　　return sum;}　　4、求導(dǎo)：

36、Polyn Derivative(Polyn head){ //求解并建立導(dǎo)函數(shù)多項(xiàng)式，并返回其頭指針　　Polyn q=head->next,p1,p2,hd;　　hd=p1=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點(diǎn)　　hd->next=NUL

37、L;　　while(q){　　if(q->expn!=0){//該項(xiàng)不是常數(shù)項(xiàng)時(shí)　　p2=(Polyn)malloc(sizeof(struct Polynomial));　　p2->coef=q->coef*q-&

38、gt;expn;　　p2->expn=q->expn-1;　　p2->next=p1->next; //連接結(jié)點(diǎn)　　p1->next=p2;　　p1=p2;}

39、q=q->next;}　　return hd;}　　5、乘法：　　Polyn MultiplyPolyn(Polyn pa,Polyn pb){ //求解并建立多項(xiàng)式a*b，返回其頭指針　　Polyn hf,pf;</p&

40、gt;　　Polyn qa=pa->next;　　Polyn qb=pb->next;　　hf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點(diǎn)　　hf->next=NULL;　　fo

41、r(;qa;qa=qa->next){　　for(qb=pb->next;qb;qb=qb->next){　　pf=(Polyn)malloc(sizeof(struct Polynomial));　　pf->coef=qa->coef*qb->coef;

42、　　pf->expn=qa->expn+qb->expn;　　Insert(pf,hf); //調(diào)用Insert函數(shù)以合并指數(shù)相同的項(xiàng)　　}　　}　　retu

43、rn hf;}　?。ǘ?、迷宮求解：　　1、初始化：　　int MazeInit(MazeType *maze) {//初始化迷宮　　int m,n,i,j;<p

44、>　　printf("輸入迷宮的行數(shù)和列數(shù):");　　scanf("%d%d",&maze->row,&maze->column); //迷宮行和列數(shù)　　for(i=0;i<=maze->column+1;i++) { //迷宮行外墻<

45、;p>　　maze->grid[0][i]='1'; //設(shè)置為障礙墻　　maze->grid[maze->row+1][i]='1';}　　for(i=0;i<=maze->row+1;i++) {//迷宮列外墻　　maze->g

46、rid[i][0]='1'; //設(shè)置為障礙墻　　maze->grid[i][maze->column+1]='1';} 　　for(i=1;i<=maze->row;i++) //初始化迷宮　　for(j=1;j<=maze->col

47、umn;j++)　　maze->grid[i][j]='0'; //設(shè)置為可通過　　printf("輸入障礙墻的坐標(biāo)（輸入坐標(biāo)0,0結(jié)束）:");　　while(1){scanf("%d%d",&m,&n); //接收障礙的坐標(biāo)

48、　　if(m==0) //輸入0　　break; //結(jié)束坐標(biāo)的輸入　　if(m<=0||n<=0||m>maze->row||n>=maze->column) { //越界　　printf("坐標(biāo)越界，重新輸入!\

49、n");　　continue;}　　maze->grid[m][n]='1'; //迷宮障礙用‘1’標(biāo)記　　}　　return 1;}

50、2、獲取下一位置：　　Coordinate NextCoord(Coordinate pos,int i) {//獲取下一位置　　switch(i) {//1,2,3,4分別代表東南西北方向　　case 1: //向右查找　　pos.colum

51、n+=1; 　　break;　　case 2: //向下查找　　pos.row+=1; 　　break;　　case 3: //向左查找

52、 　　pos.column-=1;　　break;　　case 4: //向上查找　　pos.row-=1;　　break;&

53、lt;p>　　default:　　exit(0); }　　return pos;}　　3、路徑查找：　　int MazePath(MazeType *maze,Coordinate star

54、t,Coordinate end){//從迷宮maze的入 　　口到出口查找路徑　　Stack s; //定義棧　　Coordinate pos;　　int curstep; //當(dāng)前序號1,2,3,4分別表

55、示東南西北方向　　MazeNode e;　　InitStack(&s); //初始化棧　　pos=start; //從入口位置開始查找路徑　　curstep=1; //探索第一步　　do{if(Pass(maz

56、e,pos)) {//若指走位置可通過　　MarkerPass(maze,pos); //標(biāo)記能通過　　e.ord=curstep; //保存步數(shù)　　e.seat=pos; //保存當(dāng)前坐標(biāo)　　e.di=1; //向右探測<p

57、>　　Push(&s,e); //將節(jié)點(diǎn)添加到棧中（保存路徑）　　if(pos.row==end.row&&pos.column==end.column) {//若當(dāng)前位置是出口坐標(biāo)　　DestroyStack(&s); //釋放棧已用空間　　return 1;

58、//返回查找成功　　}　　else {//與出口坐標(biāo)不同　　pos=NextCoord(pos,1); //向右探測　　curstep++; //增加前進(jìn)步數(shù)　　}&l

59、t;/b>　　}　　else {//若指定位置不通（為障礙墻或已走過）　　if(!StackEmpty(&s)) { //若棧不為空（之前有走過的位置）　　Pop(&s,&e); //出棧（返回上一

60、步的位置）　　while(e.di==4&&!StackEmpty(&s)) {//上一步4個(gè)方向都得測完，且棧不為空　　MarkerNoPass(maze,e.seat); //標(biāo)記該位置不為空　　Pop(&s,&e); //出棧（返回上一步）

61、　　}　　if(e.di<4) //若為探測完4個(gè)方向　　e.di++; //準(zhǔn)備探測下一個(gè)方向 　　Push(&s,e); //將當(dāng)前節(jié)點(diǎn)入棧（保存當(dāng)前位置，準(zhǔn)備下一位置的探測）　　p

62、os=NextCoord(e.seat,e.di); //查找下一個(gè)應(yīng)該探測位置的坐標(biāo)　　}　　}　　}while(!StackEmpty(&s)); //程序運(yùn)行到這里，表示沒有能通達(dá)的路徑<

63、;p>　　DestroyStack(&s); //釋放棧占用的空間　　return 0; //返回失敗 　　}　　五、算法復(fù)雜度的簡單分析　?。ㄒ唬?、一元多項(xiàng)式計(jì)算：&l

64、t;b>　　1、加法：O(n)　　2、減法：O(n+m)　　3、求解x：O(n^2)　　4、求導(dǎo)：O(n)　　5、乘法：O(n^2)　?。ǘ?、迷宮

65、求解：　　1、初始化：O(n^2)　　2、獲取下一位置：O(n)　　3、路徑查找：O(n)　　六、程序測試數(shù)據(jù)　?。ㄒ唬?、一元多項(xiàng)式計(jì)算：<p

66、>　　1、(2x+5x^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7);　　2、(6x^-3-x+4.4x^2-1.2x^9+1.2x^9)-(-6x^-3+5.4x^2-x^2+7.8x^15　　)=(-7.8x^15-1.2x^9+12x^-3-x);

67、3、(1+x+x^2+x^3+x^4+x^5)+(-x^3-x^4)=(1+x+x^2+x^5);　　4、(x+x^3)+(-x-x^3)=0;　　5、(x+x^100)+(x^100+x^200)=(x+2x^100+x^200);　　6、(x+x^2+x^3)+0=x+x^2+x^3.

68、　?。ǘ?、迷宮求解：　　5　　0 0 0 0 0　　1 1 1 1 0　　0 0

69、0 0 0　　0 1 1 1 1　　0 0 0 0 0　　路徑：　　七、出現(xiàn)問題及解決方法　　1

70、、我編程時(shí)最常見的問題就是馬虎，常常丟三落四，如：經(jīng)常忘記語句后的分號，經(jīng)常忘記地址符號，經(jīng)常丟一半括號等一些細(xì)小的問題沒有注意好。　　我的解決方法是反復(fù)檢查或編譯檢查，寫代碼時(shí)多多提醒自己，注意小問題的發(fā)生。　　2、剛拿到題時(shí)急于完成作業(yè)，沒有對題仔細(xì)分析就忙于做，結(jié)果在編程過程中思路不清晰，思維不連貫，想到哪里就做到哪里，常忽略一些細(xì)節(jié)上的問題和整體

71、連貫的問題，并且對題意理解不夠全面。　　我的解決方法是靜下心來，仔細(xì)讀題審題，分析題意，做出大體設(shè)計(jì)，條理清晰，不要慌忙編寫代碼。　　3、我對書中鏈表，文件等部分掌握的都不夠好，所以寫程序時(shí)遇到不少問題。　　我的解決方法是：邊編程邊看書；找學(xué)長學(xué)姐請教；參考有關(guān)方面的書籍等。<p&g

72、t;　　4、在函數(shù)編寫過程中也遇到了或大或小的問題，對各類函數(shù)掌握的不是很熟練，運(yùn)行時(shí)常常出現(xiàn)問題。　　我的解決方法是：上網(wǎng)查找相關(guān)內(nèi)容參考研究；問學(xué)長學(xué)姐；查找課本類似函數(shù)加以修改等。　　5、在寫迷宮求解程序的時(shí)候發(fā)現(xiàn)，求出起點(diǎn)到終點(diǎn)的路徑的函數(shù)，經(jīng)過反復(fù)運(yùn)行求出的結(jié)果總是無任何現(xiàn)象。　　我的解決方法是查找資料

73、，詢問學(xué)姐后發(fā)現(xiàn)原因是把相關(guān)重要的變量重復(fù)定義以至賦過的值被覆蓋，改正后運(yùn)行正確。　　八、設(shè)計(jì)總結(jié)　　通過本次課程設(shè)計(jì)，我對《數(shù)據(jù)結(jié)構(gòu)(c 語言版)》這門課程有了很深入的理解。數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)程序設(shè)計(jì)的重要理論技術(shù)基礎(chǔ)，它不僅是計(jì)算機(jī)科學(xué)的核心課程，而且已成為其他理工專業(yè)的熱門專業(yè)熱門選修課程。因此熟練掌握數(shù)據(jù)結(jié)構(gòu)知

74、識對我們計(jì)算機(jī)專業(yè)的學(xué)習(xí)非常必要，為以后我們對編程、軟件設(shè)計(jì)等打下堅(jiān)實(shí)的基礎(chǔ)。經(jīng)過本次課程設(shè)計(jì)，我深刻地明白了理論與實(shí)踐應(yīng)用相結(jié)合的重要性，并努力克服自己在分析復(fù)雜問題的弱點(diǎn)。這次課程設(shè)計(jì)同時(shí)也考驗(yàn)我的綜合運(yùn)用所學(xué)知識的能力和操作能力。虛心求教，敢于懷疑，敢于發(fā)現(xiàn)問題，并及時(shí)動腦解決問題，提出自己新的見解和構(gòu)思思想。個(gè)人的力量是薄弱的，集體的力量是強(qiáng)大的。獨(dú)立思考問題的同時(shí)也要適當(dāng)合作，相互交流意見，讓你我在編程方面都有所進(jìn)步，有所收獲

75、。在發(fā)現(xiàn)彼此各自優(yōu)缺點(diǎn)時(shí)，吸取各自的優(yōu)點(diǎn)，克服缺點(diǎn)，善于發(fā)揮自己的長處。　　一開始寫一元多項(xiàng)式計(jì)算的程序時(shí)調(diào)理不清晰，遇到了一些問題，在看書查資料或是問同學(xué)之后都能解決，在查資料時(shí)發(fā)現(xiàn)了題目要求以外的功能，嘗試了一下，效果還好?？墒敲詫m求解的程序就沒那么簡單了，曾一度讓我想放棄，就算看書查資料還是有好些不懂得，還好有位同專業(yè)的學(xué)姐，找她詢問了好多次，才有所了解，在她的幫助下完成了迷宮求解程序的編

76、寫。最后要將兩個(gè)程序?qū)懙揭黄?，這個(gè)以前接觸過所以寫起來還比較容易。就這樣我的程序在歷經(jīng)艱辛后終于誕生了。　　雖然寫程序的道路崎嶇并艱辛，但經(jīng)過努力得到收獲時(shí)的喜悅卻又無與倫比?？傊?--痛并快樂著，這是此次寫程序我最大的感受。這次寫程序也同樣提醒著我在以后的學(xué)習(xí)中要更努力，更細(xì)心，更刻苦，這樣才會快樂多一點(diǎn)，痛苦少一點(diǎn)。　　九、參考文獻(xiàn)

77、　　1、C語言大學(xué)實(shí)用教程（第2版）蘇小紅等著電子工業(yè)出版社　　2、數(shù)據(jù)結(jié)構(gòu)(C語言版) 秦鋒著清華大學(xué)出版社　　3、《數(shù)據(jù)結(jié)構(gòu)》（C語言版）嚴(yán)蔚敏、吳偉民著清華大學(xué)出版社<

78、;/p>　　十、附錄：源程序　　#include<stdio.h>　　#include<stdlib.h>　　#include<string.h>　　#include&l

79、t;conio.h>　　#define MAXLEN 30 //迷宮包括外墻最大行列數(shù)目　　#define INIT_SIZE 100 //存儲空間初始分配量　　typedef struct {int row; //迷宮的行數(shù)　　int colum

80、n; //迷宮的列數(shù)　　char grid[MAXLEN][MAXLEN];//1表示障礙，0表示空，2表示可通，3表示已經(jīng)走過但不通　　}MazeType; //迷宮類型　　typedef struct {//迷宮中的坐標(biāo)　　int row; //行號&

81、lt;/p>　　int column; //列號　　}Coordinate;　　typedef struct {int ord; //當(dāng)前位置在路徑上的序號　　Coordinate seat; //當(dāng)前坐標(biāo)　　int di; /

82、/往下一坐標(biāo)的方向　　}MazeNode; //棧元素類型　　typedef struct {MazeNode base[INIT_SIZE]; //迷宮節(jié)點(diǎn)信息　　int top; //棧頂元素　　}Stack;<

83、/p>　　typedef struct Polynomial { //定義多項(xiàng)式的項(xiàng)　　float coef; //系數(shù)　　int expn; //指數(shù)　　struct Polynomial *

84、next;　　}*Polyn,Polynomial;　　void Insert(Polyn p,Polyn h){ if(p->coef==0) free(p); //系數(shù)為0的話釋放結(jié)點(diǎn)　　else{Polyn q1,q2;　　q1

85、=h;　　q2=h->next;　　while(q2&& p->expn < q2->expn) { //查找插入位置 　　q1=q2;　　q

86、2=q2->next;}　　if(q2&& p->expn == q2->expn) { //將指數(shù)相同相合并 　　q2->coef += p->coef;　　free(p);</

87、p>　　if(!q2->coef) {//系數(shù)為0的話釋放結(jié)點(diǎn) 　　q1->next=q2->next;　　free(q2);}　　}　　else {

88、//指數(shù)為新時(shí)將結(jié)點(diǎn)插入 　　p->next=q2;　　q1->next=p;}　　}　　}　　P

89、olyn CreatePolyn(Polyn head,int m) {//建立一個(gè)頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式 　　int i;　　Polyn p;　　p=head=(Polyn)malloc(sizeof(struct Polynomial));</

90、p>　　head->next=NULL;　　for(i=0;i<m;i++){p=(Polyn)malloc(sizeof(struct Polynomial)); //建立新結(jié)點(diǎn)以接收數(shù)據(jù)　　printf("請輸入第%d項(xiàng)的系數(shù)與指數(shù):",i+1);

91、　　scanf("%f %d",&p->coef,&p->expn);　　Insert(p,head); //調(diào)用Insert函數(shù)插入結(jié)點(diǎn)　　}　　return head;}&l

92、t;p>　　void DestroyPolyn(Polyn p){ //銷毀多項(xiàng)式p 　　Polyn q1,q2;　　q1=p->next;　　q2=q1->next;　　while(q1->next

93、){　　free(q1);　　q1=q2;　　q2=q2->next;}　　}　　void PrintPoly

94、n(Polyn P){Polyn q=P->next; 　　int flag=1; //項(xiàng)數(shù)計(jì)數(shù)器　　if(!q){ //若多項(xiàng)式為空，輸出0　　putchar('0'); <

95、;p>　　printf("\n");　　return;} 　　while(q){ if(q->coef>0&& flag!=1) putchar('+'); //系數(shù)大于0且不是第一項(xiàng)　　if(q->coef!=1&&a

96、mp;q->coef!=-1){ //系數(shù)非1或-1的普通情況　　printf("%g",q->coef); 　　if(q->expn==1) putchar('X');　　else if(q->expn) printf("X^%d"

97、,q->expn);}　　else{if(q->coef==1){　　if(!q->expn) putchar('1'); 　　else if(q->expn==1) putchar('X'); 　　else pri

98、ntf("X^%d",q->expn);}　　if(q->coef==-1){　　if(!q->expn) printf("-1"); 　　else if(q->expn==1) printf("-X");

99、　　else printf("-X^%d",q->expn);}　　}　　q=q->next; 　　flag++;}　　printf("

100、;\n");}　　int compare(Polyn a,Polyn b){ if(a&&b){　　if(!b||a->expn>b->expn) return 1;　　else if(!a||a->expn<b->expn) return -1;&l

101、t;/p>　　else return 0;}　　else if(!a&&b) return -1; //a多項(xiàng)式已空，但b多項(xiàng)式非空　　else return 1; //b多項(xiàng)式已空，但a多項(xiàng)式非空</p&g

102、t;　　}　　Polyn AddPolyn(Polyn pa,Polyn pb) {//求解并建立多項(xiàng)式a+b，返回其頭指針 　　Polyn qa=pa->next;　　Polyn qb=pb->next;<

103、/p>　　Polyn headc,hc,qc;　　hc=(Polyn)malloc(sizeof(struct Polynomial)); //建立頭結(jié)點(diǎn)　　hc->next=NULL;　　headc=hc;<p

104、>　　while(qa||qb){qc=(Polyn)malloc(sizeof(struct Polynomial));　　switch(compare(qa,qb)){　　case 1:{qc->coef=qa->coef;　　qc->expn=qa->expn;</p&g

105、t;　　qa=qa->next;　　break;}　　case 0:{ qc->coef=qa->coef+qb->coef;　　qc->expn=qa->expn;　　qa=

106、qa->next;　　qb=qb->next;　　break;}　　case -1:{qc->coef=qb->coef;　　qc->expn=qb->expn;<p&

107、gt;　　qb=qb->next;　　break;} 　　}　　if(qc->coef!=0){qc->next=hc->next;　　hc->next=qc;<

108、;/p>　　hc=qc;}　　else free(qc); //當(dāng)相加系數(shù)為0時(shí)，釋放該結(jié)點(diǎn)　　}　　return headc;}

109、　　Polyn SubtractPolyn(Polyn pa,Polyn pb) { //求解并建立多項(xiàng)式a-b，返回其頭指針 　　Polyn h=pb;　　Polyn p=pb->next;　　Polyn pd;

110、　　while(p){ //將pb的系數(shù)取反　　p->coef*=-1;　　p=p->next;}　　pd=AddPolyn(pa,h);　　for(p=

111、h->next;p;p=p->next) //恢復(fù)pb的系數(shù)　　p->coef*=-1;　　return pd;}　　float ValuePolyn(Polyn head,int x) { //輸入x值，計(jì)算并返回多項(xiàng)式的值 &l

112、t;/p>　　Polyn p;　　int i,t;　　float sum=0;　　for(p=head->next;p;p=p->next){t=1;　　f

113、or(i=p->expn;i!=0;){　　if(i<0){t/=x;i++;} //指數(shù)小于0，進(jìn)行除法　　else{t*=x;i--;} //指數(shù)大于0，進(jìn)行乘法　　}<p

114、>　　sum+=p->coef*t;}　　return sum;}　　Polyn Derivative(Polyn head) {//求解并建立導(dǎo)函數(shù)多項(xiàng)式，并返回其頭指針 　　Polyn q=head->next,p1,p2,hd;<p&g

115、t;　　hd=p1=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點(diǎn)　　hd->next=NULL;　　while(q){if(q->expn!=0){ //該項(xiàng)不是常數(shù)項(xiàng)時(shí)　　p2=(Polyn)malloc(sizeof(st

116、ruct Polynomial));　　p2->coef=q->coef*q->expn;　　p2->expn=q->expn-1;　　p2->next=p1->next; //連接結(jié)點(diǎn)　　p1->ne

117、xt=p2;　　p1=p2;}　　q=q->next;}　　return hd;}　　Polyn MultiplyPolyn(Polyn pa,Polyn pb) {//求解并建立多項(xiàng)式a*b，返回其頭指針

118、;　　Polyn hf,pf;　　Polyn qa=pa->next;　　Polyn qb=pb->next;　　hf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點(diǎn)　　hf->ne

119、xt=NULL;　　for(;qa;qa=qa->next){for(qb=pb->next;qb;qb=qb->next){　　pf=(Polyn)malloc(sizeof(struct Polynomial));　　pf->coef=qa->coef*qb->coef;&

120、lt;/p>　　pf->expn=qa->expn+qb->expn;　　Insert(pf,hf); //調(diào)用Insert函數(shù)以合并指數(shù)相同的項(xiàng)　　}　　}</b&g

121、t;　　return hf;}　　void Polynomial_solve(void){int m,n,a,x;　　char flag;　　Polyn pa=0,pb=0,pc;　　printf("

122、歡迎使用一元多項(xiàng)式計(jì)算程序!\n");　　printf("請輸入a的項(xiàng)數(shù):");　　scanf("%d",&m);　　pa=CreatePolyn(pa,m); //建立多項(xiàng)式a</p&g

123、t;　　printf("請輸入b的項(xiàng)數(shù):");　　scanf("%d",&n);　　pb=CreatePolyn(pb,n); //建立多項(xiàng)式b　　//輸出菜單<

124、;/p>　　printf(" **************************************************\n");　　printf(" * 一元多項(xiàng)式計(jì)算 *\n");　　printf(

125、" **************************************************\n");　　printf(" * A:輸出多項(xiàng)式a B:輸出多項(xiàng)式b *\n");　　printf(" * C:輸出a的導(dǎo)數(shù)

126、 D:輸出b的導(dǎo)數(shù) *\n");　　printf(" * E:代入x的值計(jì)算a F:代入x的值計(jì)算b *\n");　　printf(" * G:輸出a+b H:輸出a-b *\n");</p

127、>　　printf(" * I:輸出a*b J:退出程序 *\n");　　printf(" **************************************************\n");　　while(a){

128、printf("\n請選擇操作：");　　scanf(" %c",&flag); 　　switch(flag){ case'A':　　case'a':{printf("\n 多項(xiàng)式a=")

129、;　　PrintPolyn(pa);　　break;}　　case'B':　　case'b':{printf("\n 多項(xiàng)式b=")

130、;　　PrintPolyn(pb);　　break;}　　case'C':　　case'c':{pc=Derivative(pa);<

131、p>　　printf("\n 多項(xiàng)式a的導(dǎo)函數(shù)為：a'=");　　PrintPolyn(pc);　　break;}　　case'D':

132、　　case'd':{pc=Derivative(pb);　　printf("\n 多項(xiàng)式b的導(dǎo)函數(shù)為：b'=");　　PrintPolyn(pc);　　break;}<b

133、>　　case'E':　　case'e':{printf("輸入x的值：x=");　　scanf("%d",&x);　　printf("\n x=%d時(shí)，a=%.3f\n",x

眾賞文庫> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

課程設(shè)計(jì)報(bào)告--一元多項(xiàng)式計(jì)算vs迷宮求解

文檔簡介

溫馨提示

最新文檔

評論

課程設(shè)計(jì)報(bào)告--一元多項(xiàng)式計(jì)算vs迷宮求解

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載