課程設計報告一元多項式計算VS迷宮求解

1、課程設計報告一元多項式計算VS迷宮求解 系 別： 專業(yè)年級：學生姓名： 學 號：任課老師： 二 一 二 年 三 月一、題目內容描述（一）、實驗二 一元多項式計算*1、任務：能夠按照指數降序排列建立并輸出多項式；能夠完成兩個多項式的相加、相減、相乘，并將結果輸出；2、在上交資料中請寫明：存儲結構、多項式相加的基本過程的算法（可以使用程序流程圖）、源程序、測試數據和結果、算法的時間復雜度、另外可以提出算法的改進方法；（二）、實驗四 迷宮求解1、任務：可以輸入一個任意大小的迷宮數據，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；2、要求：在上交資料中請寫明：存儲結構、基本算法（可以使用程序流程

2、圖）、源程序、測試數據和結果、算法的時間復雜度、另外可以提出算法的改進方法。二、解題分析（一）、一元多項式計算分析：1、一元稀疏多項式簡單計算器的功能是：1.1 輸入并建立多項式；1.2 輸出多項式，輸出形式為整數序列：n，c1,e1,c2,e2,cn,en,其中n是多項式的項數，ci和ei分別是第i項的系數和指數，序列按指數降序排列； 1.3 求多項式a、b的導函數；1.4 計算多項式在x處的值；1.5多項式a和b相加，建立多項式a+b；1.6 多項式a和b相減，建立多項式a-b。2、設計思路:2.1 定義線性表的動態(tài)分配順序存儲結構；2.2 建立多項式存儲結構，定義指針*next2.3利用

3、鏈表實現隊列的構造。每次輸入一項的系數和指數，可以輸出構造的一元多項式2.4演示程序以用戶和計算機的對話方式執(zhí)行，即在計算機終站上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中規(guī)定的運行命令；最后根據相應的輸入數據（濾去輸入中的非法字符）建立的多項式以及多項式相加的運行結果在屏幕上顯示。多項式顯示的格式為：c1xe1+c2xe2+cnxen3、設計思路分析：要解決多項式相加，必須要有多項式，所以必須首先建立兩個多項式，在這里采用鏈表的方式存儲鏈表，所以我將結點結構體定義為：序數coef指數expn指針域next運用尾插法建立兩條單鏈表，以單鏈表polyn p和polyn h分別表示兩個一元

4、多項式a和b，a+b的求和運算等同于單鏈表的插入問題（將單鏈表polyn p中的結點插入到單鏈表polyn h中），因此“和多項式”中的結點無須另生成。為了實現處理，設p、q分別指向單鏈表polya和polyb的當前項，比較p、q結點的指數項，由此得到下列運算規(guī)則： 若p->expn<q->expn，則結點p所指的結點應是“和多項式”中的一項，令指針p后移。 若p->expn=q->expn，則將兩個結點中的系數相加，當和不為0時修改結點p的系數。 若p->expn>q->expn，則結點q所指的結點應是“和多項式”中的一項，將結點q插入在結點p

5、之前，且令指針q在原來的鏈表上后移。（二）、迷宮求解分析：1、 迷宮形狀由0表示可通過，用1表示是障礙。為方便用0,1輸入。并把迷宮圖形保存在二維數組grid中。而打印出的圖形中 0表示能過1表示障礙。2、 對探索過的位置加以標記，輸入起點終點后可由相應函數來完成搜索。到目的點就可退出該調用程序。把每步路徑保存到二維數組中，通過反向進行退步可把完整的路徑保存在相應結構體數組內，通過標記的路徑可將串作相應的改變就能輸出的帶路徑的圖。3、根據二維字符數組和加標記的位置坐標，輸出迷宮的圖形。4、 該程序在獲取迷宮圖結構后，可對迷宮任意入口到出口的路線進行搜索，主要由廣度優(yōu)先搜索完成該操作。它可以是3

6、0以內大小的迷宮，有自行提供的迷宮圖，本課程設計是以二維數組作為迷宮的存儲結構。而廣度優(yōu)先搜索用的隊列一步一步完成的，從而找到的是最短路徑，并能輸出打印。三、所用數據結構的描述（用偽代碼）（一）、一元多項式計算：1、元素類型、結點類型和指針類型：typedef struct Polynomialfloat coef; /系數 int expn; /指數 struct Polynomial *next;*Polyn,Polynomial;2、建立一個頭指針為head、項數為m的一元多項式, 建立新結點以接收數據, 調用Insert函數插入結點: Polyn CreatePolyn(Polyn h

7、ead,int m) int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial); head->next=NULL; for(i=0;i<m;i+)p=(Polyn)malloc(sizeof(struct Polynomial); printf("請輸入第%d項的系數與指數:",i+1); scanf("%f %d",&p->coef,&p->expn); Insert(p,head); return head;3、調用關系圖：（二）、迷宮求解：1

8、、各個函數說明：int InitStack(Stack *s) /制造空棧int StackEmpty(Stack *s) /若s為空返回TURE,否則返回FALSEint StackIsFull(Stack *s) /判斷棧是否為滿int Push(Stack *s,MazeNode mn) /插入元素e為新的棧頂元素int Pop(Stack *s,MazeNode *mn) /若棧不空刪除棧頂元素用e返回OK,否則返回ERRORint DestroyStack(Stack *s) /銷毀棧sint MazeInit(MazeType *maze) /初始化迷宮int Pass(MazeT

9、ype *maze,Coordinate pos) /判斷n指定坐標是否可通過int MarkerPass(MazeType *maze,Coordinate pos) /標記可通過Coordinate NextCoord(Coordinate pos,int i) /獲取下一位置int MarkerNoPass(MazeType *maze,Coordinate pos)/曾走過但不是通路標記并返回OKint MazePath(MazeType *maze,Coordinate start,Coordinate end)/從迷宮maze的入口到出口查找路徑void PrintMaze(Maz

10、eType *maze) /輸出迷宮四、部分算法的描述（用偽代碼）（一）、一元多項式計算：1、加法：Polyn AddPolyn(Polyn pa,Polyn pb) /求解并建立多項式a+b，返回其頭指針 Polyn qa=pa->next; Polyn qb=pb->next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial); /建立頭結點 hc->next=NULL; headc=hc; while(qa|qb) qc=(Polyn)malloc(sizeof(struct Polynomial

11、); switch(compare(qa,qb) case 1: qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; case 0: 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(

12、qc->coef!=0) qc->next=hc->next; hc->next=qc; hc=qc; else free(qc); /當相加系數為0時，釋放該結點 return headc;2、減法：Polyn SubtractPolyn(Polyn pa,Polyn pb) /求解并建立多項式a-b，返回其頭指針 Polyn h=pb; Polyn p=pb->next; Polyn pd; while(p) /將pb的系數取反 p->coef*=-1; p=p->next; pd=AddPolyn(pa,h); for(p=h->next;

13、p;p=p->next) /恢復pb的系數 p->coef*=-1; return pd;3、求解x：float ValuePolyn(Polyn head,int x) /輸入x值，計算并返回多項式的值 Polyn p; int i,t; float sum=0; for(p=head->next;p;p=p->next) t=1; for(i=p->expn;i!=0;) if(i<0)t/=x;i+;/指數小于0，進行除法 elset*=x;i-;/指數大于0，進行乘法 sum+=p->coef*t; return sum;4、求導：Polyn

14、Derivative(Polyn head) /求解并建立導函數多項式，并返回其頭指針 Polyn q=head->next,p1,p2,hd; hd=p1=(Polyn)malloc(sizeof(struct Polynomial);/建立頭結點 hd->next=NULL; while(q) if(q->expn!=0)/該項不是常數項時 p2=(Polyn)malloc(sizeof(struct Polynomial); p2->coef=q->coef*q->expn; p2->expn=q->expn-1; p2->next=

15、p1->next; /連接結點 p1->next=p2; p1=p2; q=q->next; return hd;5、乘法：Polyn MultiplyPolyn(Polyn pa,Polyn pb) /求解并建立多項式a*b，返回其頭指針 Polyn hf,pf; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial);/建立頭結點 hf->next=NULL; for(;qa;qa=qa->next) for(qb=pb->next;qb

16、;qb=qb->next) pf=(Polyn)malloc(sizeof(struct Polynomial); pf->coef=qa->coef*qb->coef; pf->expn=qa->expn+qb->expn; Insert(pf,hf); /調用Insert函數以合并指數相同的項 return hf;（二）、迷宮求解：1、初始化：int MazeInit(MazeType *maze) /初始化迷宮 int m,n,i,j; printf("輸入迷宮的行數和列數:"); scanf("%d%d"

17、,&maze->row,&maze->column); /迷宮行和列數 for(i=0;i<=maze->column+1;i+) /迷宮行外墻 maze->grid0i='1' /設置為障礙墻 maze->gridmaze->row+1i='1' for(i=0;i<=maze->row+1;i+) /迷宮列外墻 maze->gridi0='1' /設置為障礙墻 maze->gridimaze->column+1='1' for(i=1;i&

18、lt;=maze->row;i+) /初始化迷宮 for(j=1;j<=maze->column;j+) maze->gridij='0' /設置為可通過 printf("輸入障礙墻的坐標（輸入坐標0,0結束）:"); while(1)scanf("%d%d",&m,&n); /接收障礙的坐標 if(m=0) /輸入0 break; /結束坐標的輸入 if(m<=0|n<=0|m>maze->row|n>=maze->column) /越界 printf(&quo

19、t;坐標越界，重新輸入!n"); continue; maze->gridmn='1' /迷宮障礙用1標記 return 1;2、獲取下一位置：Coordinate NextCoord(Coordinate pos,int i) /獲取下一位置 switch(i) /1,2,3,4分別代表東南西北方向 case 1: /向右查找 pos.column+=1; break; case 2: /向下查找 pos.row+=1; break; case 3: /向左查找 pos.column-=1; break; case 4: /向上查找 pos.row-=1; b

20、reak; default: exit(0); return pos;3、路徑查找：int MazePath(MazeType *maze,Coordinate start,Coordinate end)/從迷宮maze的入 口到出口查找路徑 Stack s; /定義棧 Coordinate pos; int curstep; /當前序號1,2,3,4分別表示東南西北方向 MazeNode e; InitStack(&s); /初始化棧 pos=start; /從入口位置開始查找路徑 curstep=1; /探索第一步 doif(Pass(maze,pos) /若指走位置可通過 Mar

21、kerPass(maze,pos); /標記能通過 e.ord=curstep; /保存步數 e.seat=pos; /保存當前坐標 e.di=1; /向右探測 Push(&s,e); /將節(jié)點添加到棧中（保存路徑） if(pos.row=end.row&&pos.column=end.column) /若當前位置是出口坐標 DestroyStack(&s); /釋放棧已用空間return 1; /返回查找成功 else /與出口坐標不同 pos=NextCoord(pos,1); /向右探測 curstep+; /增加前進步數 else /若指定位置不通（為障

22、礙墻或已走過） if(!StackEmpty(&s) /若棧不為空（之前有走過的位置） Pop(&s,&e); /出棧（返回上一步的位置） while(e.di=4&&!StackEmpty(&s) /上一步4個方向都得測完， 且棧不為空MarkerNoPass(maze,e.seat); /標記該位置不為空Pop(&s,&e); /出棧（返回上一步） if(e.di<4) /若為探測完4個方向 e.di+; /準備探測下一個方向 Push(&s,e); /將當前節(jié)點入棧（保存當前位置，準備下一位置的探測） pos=

23、NextCoord(e.seat,e.di); /查找下一個應該探測位置的坐標 while(!StackEmpty(&s); /程序運行到這里，表示沒有能通達的路徑 DestroyStack(&s); /釋放棧占用的空間 return 0; /返回失敗 五、算法復雜度的簡單分析（一）、一元多項式計算：1、加法：O(n)2、減法：O(n+m)3、求解x：O(n2)4、求導：O(n)5、乘法：O(n2)（二）、迷宮求解：1、初始化：O(n2)2、獲取下一位置：O(n)3、路徑查找：O(n)六、程序測試數據（一）、一元多項式計算：1、(2x+5x8-3.1x11)+(7-5x8+11

24、x9)=(-3.1x11+11x9+2x+7);2、(6x-3-x+4.4x2-1.2x9+1.2x9)-(-6x-3+5.4x2-x2+7.8x15)=(-7.8x15-1.2x9+12x-3-x);3、(1+x+x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5);4、(x+x3)+(-x-x3)=0;5、(x+x100)+(x100+x200)=(x+2x100+x200);6、(x+x2+x3)+0=x+x2+x3.（二）、迷宮求解：5 0 0 0 0 0 1 1 1 1 0 0 0 0 0 00 1 1 1 10 0 0 0 0路徑：七、出現問題及解決方法1、我編程時最

25、常見的問題就是馬虎，常常丟三落四，如：經常忘記語句后的分號，經常忘記地址符號，經常丟一半括號等一些細小的問題沒有注意好。我的解決方法是反復檢查或編譯檢查，寫代碼時多多提醒自己，注意小問題的發(fā)生。2、剛拿到題時急于完成作業(yè)，沒有對題仔細分析就忙于做，結果在編程過程中思路不清晰，思維不連貫，想到哪里就做到哪里，常忽略一些細節(jié)上的問題和整體連貫的問題，并且對題意理解不夠全面。我的解決方法是靜下心來，仔細讀題審題，分析題意，做出大體設計，條理清晰，不要慌忙編寫代碼。3、我對書中鏈表，文件等部分掌握的都不夠好，所以寫程序時遇到不少問題。我的解決方法是：邊編程邊看書；找學長學姐請教；參考有關方面的書籍等。

26、4、在函數編寫過程中也遇到了或大或小的問題，對各類函數掌握的不是很熟練，運行時常常出現問題。我的解決方法是：上網查找相關內容參考研究；問學長學姐；查找課本類似函數加以修改等。5、在寫迷宮求解程序的時候發(fā)現，求出起點到終點的路徑的函數，經過反復運行求出的結果總是無任何現象。我的解決方法是查找資料，詢問學姐后發(fā)現原因是把相關重要的變量重復定義以至賦過的值被覆蓋，改正后運行正確。八、設計總結通過本次課程設計，我對數據結構(c 語言版)這門課程有了很深入的理解。數據結構是計算機程序設計的重要理論技術基礎，它不僅是計算機科學的核心課程，而且已成為其他理工專業(yè)的熱門專業(yè)熱門選修課程。因此熟練掌握數據結構知

27、識對我們計算機專業(yè)的學習非常必要，為以后我們對編程、軟件設計等打下堅實的基礎。經過本次課程設計，我深刻地明白了理論與實踐應用相結合的重要性，并努力克服自己在分析復雜問題的弱點。這次課程設計同時也考驗我的綜合運用所學知識的能力和操作能力。虛心求教，敢于懷疑，敢于發(fā)現問題，并及時動腦解決問題，提出自己新的見解和構思思想。個人的力量是薄弱的，集體的力量是強大的。獨立思考問題的同時也要適當合作，相互交流意見，讓你我在編程方面都有所進步，有所收獲。在發(fā)現彼此各自優(yōu)缺點時，吸取各自的優(yōu)點，克服缺點，善于發(fā)揮自己的長處。一開始寫一元多項式計算的程序時調理不清晰，遇到了一些問題，在看書查資料或是問同學之后都能

28、解決，在查資料時發(fā)現了題目要求以外的功能，嘗試了一下，效果還好。可是迷宮求解的程序就沒那么簡單了，曾一度讓我想放棄，就算看書查資料還是有好些不懂得，還好有位同專業(yè)的學姐，找她詢問了好多次，才有所了解，在她的幫助下完成了迷宮求解程序的編寫。最后要將兩個程序寫到一起，這個以前接觸過所以寫起來還比較容易。就這樣我的程序在歷經艱辛后終于誕生了。雖然寫程序的道路崎嶇并艱辛，但經過努力得到收獲時的喜悅卻又無與倫比。總之-痛并快樂著，這是此次寫程序我最大的感受。這次寫程序也同樣提醒著我在以后的學習中要更努力，更細心，更刻苦，這樣才會快樂多一點，痛苦少一點。九、參考文獻1、C語言大學實用教程（第2版） 蘇小紅

29、等 著 電子工業(yè)出版社2、數據結構(C語言版) 秦鋒 著 清華大學出版社3、數據結構（C語言版） 嚴蔚敏、吳偉民 著 清華大學出版社十、附錄：源程序#include<stdio.h>#include<stdlib.h>#include<string.h>#include<conio.h>#define MAXLEN 30 /迷宮包括外墻最大行列數目#define INIT_SIZE 100 /存儲空間初始分配量typedef struct int row; /迷宮的行數 int column; /迷宮的列數 char gridMAXLENMAXL

30、EN;/1表示障礙，0表示空，2表示可通，3表示已經走過但不通MazeType; /迷宮類型typedef struct /迷宮中的坐標 int row; /行號 int column; /列號Coordinate;typedef struct int ord; /當前位置在路徑上的序號 Coordinate seat; /當前坐標 int di; /往下一坐標的方向MazeNode; /棧元素類型typedef struct MazeNode baseINIT_SIZE; /迷宮節(jié)點信息 int top; /棧頂元素Stack;typedef struct Polynomial /定義多項式

31、的項 float coef; /系數 int expn; /指數 struct Polynomial *next;*Polyn,Polynomial;void Insert(Polyn p,Polyn h) if(p->coef=0) free(p); /系數為0的話釋放結點 elsePolyn q1,q2; q1=h; q2=h->next; while(q2&& p->expn < q2->expn) /查找插入位置 q1=q2; q2=q2->next; if(q2&& p->expn = q2->expn)

32、 /將指數相同相合并 q2->coef += p->coef; free(p); if(!q2->coef) /系數為0的話釋放結點 q1->next=q2->next; free(q2); else /指數為新時將結點插入 p->next=q2; q1->next=p;Polyn CreatePolyn(Polyn head,int m) /建立一個頭指針為head、項數為m的一元多項式 int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial); head->next=NULL

33、; for(i=0;i<m;i+)p=(Polyn)malloc(sizeof(struct Polynomial); /建立新結點以接收數據 printf("請輸入第%d項的系數與指數:",i+1); scanf("%f %d",&p->coef,&p->expn); Insert(p,head); /調用Insert函數插入結點 return head;void DestroyPolyn(Polyn p) /銷毀多項式p Polyn q1,q2; q1=p->next; q2=q1->next; whil

34、e(q1->next) free(q1); q1=q2; q2=q2->next;void PrintPolyn(Polyn P)Polyn q=P->next; int flag=1; /項數計數器 if(!q) /若多項式為空，輸出0 putchar('0'); printf("n"); return; while(q) if(q->coef>0&& flag!=1) putchar('+'); /系數大于0且不是第一項 if(q->coef!=1&&q->coef

35、!=-1) /系數非1或-1的普通情況 printf("%g",q->coef); if(q->expn=1) putchar('X'); else if(q->expn) printf("X%d",q->expn); elseif(q->coef=1) if(!q->expn) putchar('1'); else if(q->expn=1) putchar('X'); else printf("X%d",q->expn); if(q-&

36、gt;coef=-1) if(!q->expn) printf("-1"); else if(q->expn=1) printf("-X"); else printf("-X%d",q->expn); q=q->next; flag+; printf("n");int compare(Polyn a,Polyn b) if(a&&b) if(!b|a->expn>b->expn) return 1; else if(!a|a->expn<b-&g

37、t;expn) return -1; else return 0; else if(!a&&b) return -1; /a多項式已空，但b多項式非空 else return 1; /b多項式已空，但a多項式非空Polyn AddPolyn(Polyn pa,Polyn pb) /求解并建立多項式a+b，返回其頭指針 Polyn qa=pa->next; Polyn qb=pb->next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial); /建立頭結點 hc->next=NULL;

38、headc=hc; while(qa|qb)qc=(Polyn)malloc(sizeof(struct Polynomial); switch(compare(qa,qb) case 1:qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; case 0: qc->coef=qa->coef+qb->coef; qc->expn=qa->expn; qa=qa->next; qb=qb->next; break; case -1:qc->coef=qb-

39、>coef; qc->expn=qb->expn; qb=qb->next; break; if(qc->coef!=0)qc->next=hc->next; hc->next=qc; hc=qc; else free(qc); /當相加系數為0時，釋放該結點 return headc;Polyn SubtractPolyn(Polyn pa,Polyn pb) /求解并建立多項式a-b，返回其頭指針 Polyn h=pb; Polyn p=pb->next; Polyn pd; while(p) /將pb的系數取反 p->coef*

40、=-1; p=p->next; pd=AddPolyn(pa,h); for(p=h->next;p;p=p->next) /恢復pb的系數 p->coef*=-1; return pd;float ValuePolyn(Polyn head,int x) /輸入x值，計算并返回多項式的值 Polyn p; int i,t; float sum=0; for(p=head->next;p;p=p->next)t=1; for(i=p->expn;i!=0;) if(i<0)t/=x;i+; /指數小于0，進行除法 elset*=x;i-; /指數

41、大于0，進行乘法 sum+=p->coef*t; return sum;Polyn Derivative(Polyn head) /求解并建立導函數多項式，并返回其頭指針 Polyn q=head->next,p1,p2,hd; hd=p1=(Polyn)malloc(sizeof(struct Polynomial);/建立頭結點 hd->next=NULL; while(q)if(q->expn!=0) /該項不是常數項時 p2=(Polyn)malloc(sizeof(struct Polynomial); p2->coef=q->coef*q->

42、;expn; p2->expn=q->expn-1; p2->next=p1->next; /連接結點 p1->next=p2; p1=p2; q=q->next; return hd;Polyn MultiplyPolyn(Polyn pa,Polyn pb) /求解并建立多項式a*b，返回其頭指針 Polyn hf,pf; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial);/建立頭結點 hf->next=NULL; for(;

43、qa;qa=qa->next)for(qb=pb->next;qb;qb=qb->next) pf=(Polyn)malloc(sizeof(struct Polynomial); pf->coef=qa->coef*qb->coef; pf->expn=qa->expn+qb->expn; Insert(pf,hf); /調用Insert函數以合并指數相同的項 return hf;void Polynomial_solve(void)int m,n,a,x; char flag; Polyn pa=0,pb=0,pc; printf(&q

44、uot; 歡迎使用一元多項式計算程序!n"); printf("請輸入a的項數:"); scanf("%d",&m); pa=CreatePolyn(pa,m); /建立多項式a printf("請輸入b的項數:"); scanf("%d",&n); pb=CreatePolyn(pb,n); /建立多項式b /輸出菜單 printf(" *n");printf(" * 一元多項式計算 *n"); printf(" *n"); p

45、rintf(" * A:輸出多項式a B:輸出多項式b *n");printf(" * C:輸出a的導數 D:輸出b的導數 *n");printf(" * E:代入x的值計算a F:代入x的值計算b *n");printf(" * G:輸出a+b H:輸出a-b *n");printf(" * I:輸出a*b J:退出程序 *n");printf(" *n");while(a)printf("n請選擇操作："); scanf(" %c",&flag); switch(flag) case'A': case'a':printf("n 多項式a=");PrintPolyn(pa);break;case'B':case'b':printf("n 多項式b=");P