數(shù)據(jù)結構利用線性表鏈式存儲實現(xiàn)一元多項式相加減課程方案實驗報告

1、個人資料整理僅限學習使用課題名稱利用線性表鏈式存儲實現(xiàn)一元多項式相加減院系學號姓名數(shù)據(jù)結構課程設計設計題目：利用線性表鏈式存儲實現(xiàn)一元多項式相加減個人資料整理僅限學習使用1、課題設計目的：了解數(shù)據(jù)結構與算法的設計方法，獨立分析和設計一元多項式加減的程序編碼，通過程序編寫掌握軟件開發(fā)過程的問題分析、系統(tǒng)設計、程序編碼、測試等基本方法和技能，提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力，通過這次實踐將實際問題中所涉及的對象在計算機中表示出來并對它們進行處理，掌握線性表的鏈式存儲如何實現(xiàn)一元多項式的加減。1、課題設計意義：課題設計通過完成此次課題，可以了解各種數(shù)據(jù)結構內在的邏輯關系，目的

2、與討論它在計算機中的存儲表示，以及在其上進行各種運算時的算法實現(xiàn)，并對算法的效率和優(yōu)化進行簡單的分析和討論，不僅加強了設計意義學生對于線性表鏈式存儲的理解，也提高了學生的思維能力，促進學生的綜合應用能力和專業(yè)素質的提高。指導教師：年月日目錄第一章、課題描述1第二章、課題設計目的1第三章、課題設計意義1第四章、設計思路1第五章、需求分析2個人資料整理僅限學習使用第六章、概要設計26.1 、存儲結構： 26.2 、基本算法： 26.2.1、輸入輸出 26.2.2、構造數(shù)據(jù)類型 36.2.3、多項式的加法 46.2.4、多項式的減法 4第七章、程序結果及截圖4第八章、算法的時間復雜度及改進5第九章、

3、總結及心得體會5第十章、附錄 6第十一章、參考文獻13個人資料整理僅限學習使用第一章、課題描述能夠完成兩個或多個多項式的輸出，并且實現(xiàn)兩個多項式的相加和相減，并且輸出結果。第二章、課題設計目的了解數(shù)據(jù)結構與算法的設計方法，獨立分析和設計一元多項式加減的程序編碼，通過程序編寫掌握軟件開發(fā)過程的問題分析、系統(tǒng)設計、程序編碼、測試等基本方法和技能，提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力，通過這次實踐將實際問題中所涉及的對象在計算機中表示出來并對它們進行處理，掌握線性表的鏈式存儲如何實現(xiàn)一元多項式的加減，通過不斷探索程序的算法，不斷優(yōu)化程序，使得學生的知識掌握更加牢固，實踐能力加強，

4、也激發(fā)了學生對于數(shù)據(jù)結構這門課的興趣，為以后這門課的深入研究做了準備，這次實踐使同學更加深入了解了數(shù)據(jù)結構內在的邏輯關系。第三章、課題設計意義通過完成此次課題，可以了解各種數(shù)據(jù)結構內在的邏輯關系，討論它在計算機中的存儲表示，以及在其上進行各種運算時的算法實現(xiàn)，并對算法的效率和優(yōu)化進行簡單的分析和討論，不僅加強了學生對于線性表鏈式存儲的理解，也提高了學生的思維能力，促進學生的綜合應用能力和專業(yè)素質的提高，解決了現(xiàn)實生活中復雜繁瑣的計算過程，不僅提高了效率，也增加了正確率，學生對于線性表和指針等知識的理解更加深入深刻，也靈活運用了理論知識解決了實際問題，活學活用，加強了學生的實踐能力，同時完成作業(yè)

5、還需要與同學的討論，增強了學生的團隊合作能力。第四章、 設計思路這個程序的關鍵是多項式的創(chuàng)建和排列，以及相加時相同指數(shù)的系數(shù)相加。由于多項式擁有指數(shù)和系數(shù)，所以可以定義一個包含指數(shù)系數(shù)的結構體，用單鏈表存儲多項式的數(shù)據(jù)，所以結構體包含 next 指針。數(shù)據(jù)插入時比較兩數(shù)的指數(shù)，按照降序排列，從表頭的 next 開始，直至找到合適的位置，然后開始鏈表中數(shù)值的插入，如果相等則直接將指數(shù)相加，如果大于就將新數(shù)據(jù)插入到當前指向的前面，否則將新數(shù)據(jù)插入到最后。輸入完數(shù)據(jù)后選擇計算方式，多項式運算時要循環(huán)遍歷整個多項式，多項式的每一組數(shù)據(jù)都要和另一個多項式整組數(shù)據(jù)相運算 <每一個運算值都存儲到新建的

6、“多項式”鏈表中），直至兩個多項式都遍歷完結束。個人資料整理僅限學習使用第五章、 需求分析1界面輸出，提示如何輸入數(shù)據(jù)。要求先輸入多項式的項數(shù)。2創(chuàng)建多項式。接收輸入的數(shù)據(jù)，并保存到鏈表中。3顯示程序的功能表，允許使用者選擇運算類型。4顯示已經創(chuàng)建好的多項式。6實現(xiàn)加法運算。7實現(xiàn)減法運算。9清除內存內容，銷毀創(chuàng)建的鏈表，退出程序。第六章、 概要設計6.1 、存儲結構：一元多項式的表示在計算機內可以用鏈表來表示，為了節(jié)省存儲空間，只存儲多項式中系數(shù)非零項。鏈表中的每一個結點存放多項式的一個系數(shù)非零項，它包含三個域，分別存放該項的系數(shù)、指數(shù)以及指向下一個多項式項結點的指針。創(chuàng)建一元多項式鏈表，對

7、一元多項式的運算中會出現(xiàn)的各種可能情況進行分析，實現(xiàn)一元多項式的加減。6.2 、基本算法：、輸入輸出<1）功能：將要進行運算的多項式輸入輸出。<2）數(shù)據(jù)流入：要輸入的多項式的系數(shù)與指數(shù)。<3）數(shù)據(jù)流出：合并同類項后的多項式。<4）程序流程圖：多項式輸入流程圖如圖1 所示。<5 ） 測試要點：輸入的多項式是否正確，若輸入錯誤則重新輸入。否則進行運算。個人資料整理僅限學習使用開始申請結點空間輸入多項式的項數(shù)輸入多項式各項的系數(shù)x, 指數(shù) y輸出已輸入的多項式否是否輸入正確是合并同類項結束圖表 1 輸入輸出流程圖、構造數(shù)據(jù)類型根據(jù)上面的解決途徑可以對指數(shù)，系數(shù)及指針進行

8、以下說明：typedef struct pnodeint exp 。/* 指數(shù) */float coef 。/* 系數(shù) */struct pnode *next 。個人資料整理僅限學習使用polynode 。、多項式的加法<1）功能：將兩多項式相加。<2）數(shù)據(jù)流入：輸入函數(shù)。<3）數(shù)據(jù)流出：多項式相加后的結果。<4）程序流程圖：多項式的加法流程圖如圖2 所示。<5 ）測試要點：兩多項式是否為空，為空則提示重新輸入，否則，進行運算。、多項式的減法<1）功能：將兩多項式相減。<2）數(shù)據(jù)流入：調用輸入函數(shù)。<3）數(shù)據(jù)流出：多項式相減后的結果。<4

9、）程序流程圖：多項式的減法流程圖如圖3 所示。<5）測試要點：兩多項式是否為空，為空則提示重新輸入，否則，進行運算。第七章、程序結果及截圖個人資料整理僅限學習使用第八章、算法的時間復雜度及改進1、算法的時間復雜度：一元多項式的加法運算的時間復雜度為O(m+ n） , 減法運算的時間復雜度為O(m-n>，其中 m，n 分別表示二個一元多項式的項數(shù)。2、問題和改進思想：在設計該算法時，出現(xiàn)了一些問題，例如在建立鏈表時頭指針的設立導致了之后運用到相關的指針時沒能很好的移動指針出現(xiàn)了數(shù)據(jù)重復輸出或是輸出系統(tǒng)缺省值，不能實現(xiàn)算法。實現(xiàn)加法時該鏈表并沒有向通常那樣通過建立第三個鏈表來存放運算結

10、果，而是再度利用了鏈表之一來進行節(jié)點的比較插入刪除等操作。為了使輸入數(shù)據(jù)按指數(shù)降序排列，可在數(shù)據(jù)的輸入后先做一個節(jié)點的排序函數(shù)，通過對鏈表排序后再進行之后加減運算第九章、總結及心得體會此次上機實驗應用了線性表實現(xiàn)了一次實際操作，完成了一個一元多項式的簡單計算器，不僅對此次編譯程序的算法思想有了新的認識，還讓我深刻的體會到了線性表的重要性以及其應用的方便，并且對指針加深了印象，應用了書本中的算法思想，對我以后的編譯以及完成新的程序有很大的幫助。通過這次課程設計練習，使我更深刻地理解了語言的精髓-指針的使用。完成整個程序設計有，對指針掌握的更加熟練。同時通過直接對鏈表的操作，加深了對數(shù)據(jù)結構的理解

11、和認識。并在完成課程設計的過程主動查閱了相關資料，學到了不少課本上沒有的技術知識。經過這次課程設計，我深刻認識到算法在程序設計中的重要性，一個完整的個人資料整理僅限學習使用程序總是由若干個函數(shù)構成的，這些相應的函數(shù)體現(xiàn)了算法的基本思想。編程是一件枯燥乏味工作，但是只要認真鉆研，我們會從中學到很多在課本上學不到或者無法在課堂上掌握的知識，同時也能從中感受到編程的樂趣。興趣是可以培養(yǎng)的，只要堅持下去，面對困難我們總能夠找到解決問題的方法。計算多項式的加、減、乘法運算-該程序雖然不是很大，這次還是由幾位同學合作才完成這一任務。在這個小組中我是組長，通過分工與合作，使我充分認識到在工程團隊開發(fā)過程中合

12、作的重要性，也更加理解了溝通協(xié)作能力在軟件開發(fā)行業(yè)中的重要性。另外也需要提出的是在這次程序設計的過程中，非常感謝老師對我們的耐心指導。老師在教案過程中表現(xiàn)出來的對學術鉆研一絲不茍的精神讓我非常有收獲。同樣也是老師的嚴格要求才使得小組成員能夠順利的完成任務。第十章、附錄#include<stdio.h>#include<stdlib.h>typedef struct pnodeint exp。float coef。struct pnode *next。polynode 。polynode *A,*B,*C,*D 。polynode *creatA(>polynode

13、 *p1,*r 。int i,n 。A=(polynode*>malloc(sizeof(polynode>> 。A->next=NULL 。r=A 。printf(" 請輸入 A 多項式的項數(shù) :"> 。scanf("%d",&n> 。for(i=1 。i<=n 。i+>p1=(polynode*>malloc(sizeof(polynode>> 。printf(" 請輸入 A 的第 i 項的系數(shù)和指數(shù) :",i> 。個人資料整理僅限學習使用scanf(

14、"%f%d",&p1->coef,&p1->exp> 。r->next=p1。r=p1。r->next=NULL 。return A。polynode *creatB(>polynode *p2,*r 。int i,n 。B=(polynode*>malloc(sizeof(polynode>> 。B->next=NULL 。r=B。printf(" 請輸入 B 多項式的項數(shù) :"> 。scanf("%d",&n> 。for(i=1 。i&

15、lt;=n 。i+>p2=(polynode*>malloc(sizeof(polynode>> 。printf(" 請輸入 B 的第 i 項的系數(shù)和指數(shù) :",i> 。scanf("%f%d",&p2->coef,&p2->exp> 。r->next=p2。r=p2。r->next=NULL 。return B。void printA(polynode *A>polynode *p1。p1=A->next 。while(p1->next!=NULL>if

16、(p1->next->coef>0>printf("%.2fx%d+",p1->coef,p1->exp> 。else個人資料整理僅限學習使用printf("%.2fx%d",p1->coef,p1->exp> 。p1=p1->next。printf("%.2fx%d",p1->coef,p1->exp> 。void printB(polynode *B>polynode *p2。p2=B->next。while(p2->next!=

17、NULL>if(p2->next->coef>0>printf("%.2fx%d+",p2->coef,p2->exp> 。elseprintf("%.2fx%d",p2->coef,p2->exp> 。p2=p2->next。printf("%.2fx%d",p2->coef,p2->exp> 。void printC(polynode *C>polynode *p=C->next。while(p->next!=NULL>

18、;if(p->next->coef>0>printf("%.2fx%d+",p->coef,p->exp> 。elseprintf("%.2fx%d",p->coef,p->exp> 。p=p->next。printf("%.2fx%d",p->coef,p->exp> 。void printD(polynode *D>個人資料整理僅限學習使用polynode *p=D->next 。while(p->next!=NULL>if

19、(p->next->coef>0>printf("%.2fx%d+",p->coef,p->exp> 。elseprintf("%.2fx%d",p->coef,p->exp> 。p=p->next。printf("%.2fx%d",p->coef,p->exp> 。polynode *polyadd(polynode *A,polynode *B>polynode *p1,*p2,*p,*C 。float x 。p1=A->next 。p

20、2=B->next。p=(polynode*>malloc(sizeof(polynode>> 。p->next=NULL 。C=p。while(p1&&p2>if(p1->exp=p2->exp>x=p1->coef+p2->coef。if(x!=0>p->next=(polynode*>malloc(sizeof(polynode>> 。p=p->next。p->coef=x。p->exp=p1->exp。p1=p1->next。p2=p2->

21、next。else個人資料整理僅限學習使用p->next=(polynode*>malloc(sizeof(polynode>> 。p=p->next。if(p1->exp>p2->exp>p->coef=p2->coef。p->exp=p2->exp。p2=p2->next。elsep->coef=p1->coef。p->exp=p1->exp。p1=p1->next。while(p1!=NULL>p->next=(polynode*>malloc(sizeof

22、(polynode>>。p=p->next。p->coef=p1->coef。p->exp=p1->exp。p1=p1->next。while(p2!=NULL>p->next=(polynode*>malloc(sizeof(polynode>>。p=p->next。p->coef=p2->coef。p->exp=p2->exp。p2=p2->next。p->next=NULL 。return C。個人資料整理僅限學習使用polynode *polyminus(polyno

23、de *A,polynode *B>polynode *p1,*p2,*p,*D 。float x 。p1=A->next 。p2=B->next。p=(polynode*>malloc(sizeof(polynode>> 。p->next=NULL 。D=p。while(p1&&p2>if(p1->exp=p2->exp>x=p1->coef-p2->coef。if(x!=0>p->next=(polynode*>malloc(sizeof(polynode>> 。p=

24、p->next。p->coef=x。p->exp=p1->exp。p1=p1->next。p2=p2->next。elsep->next=(polynode*>malloc(sizeof(polynode>> 。p=p->next。if(p1->exp>p2->exp>p->coef=p2->coef。p->exp=p2->exp。p2=p2->next。else個人資料整理僅限學習使用p->coef=p1->coef。p->exp=p1->exp。p1=p1->next。while(p1!=NULL>p->next=(polynode*>malloc(sizeof(polynode>>。p=p->next。p->coef=p1->coef。p->exp=p1->ex