數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告(順序結(jié)構(gòu)、動態(tài)鏈表結(jié)構(gòu)下的一元多項式的加法、減法、乘法的實現(xiàn)).doc

山東理工大學計算機學院課 程 設(shè) 計（數(shù)據(jù)結(jié)構(gòu)）班 級姓 名學 號 指導教師二一二年一月十日課程設(shè)計任務(wù)書及成績評定課題名稱順序結(jié)構(gòu)、動態(tài)鏈表結(jié)構(gòu)下的一元多項式的加法、減法、乘法的實現(xiàn)。、題目的目的和要求： 1. 鞏固和加深對數(shù)據(jù)結(jié)構(gòu)的理解，通過上機實驗、調(diào)試程序，加深對課本知識的理解，最終使學生能夠熟練應(yīng)用數(shù)據(jù)結(jié)構(gòu)的知識寫程序。1）通過本課程的學習，能熟練掌握幾種基本數(shù)據(jù)結(jié)構(gòu)的基本操作。2）能針對給定題目，選擇相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，分析并設(shè)計算法，進而給出問題的正確求解過程并編寫代碼實現(xiàn)。2設(shè)計題目要求：1) 首先判定多項式是否稀疏2) 分別采用順序和動態(tài)存儲結(jié)構(gòu)實現(xiàn)；3) 結(jié)果M(x)中無重復階項和無零系數(shù)項；4) 要求輸出結(jié)果的升冪和降冪兩種排列情況；、設(shè)計進度及完成情況日 期內(nèi) 容1.2-1.3選取參考書，查閱有關(guān)文獻資料，完成資料搜集和系統(tǒng)分析工作。1.41.5創(chuàng)建相關(guān)數(shù)據(jù)結(jié)構(gòu),錄入源程序。1.61.7調(diào)試程序并記錄調(diào)試中的問題，初步完成課程設(shè)計報告。1.9上交課程設(shè)計報告打印版并進行課程設(shè)計答辯，要求每個同學針對自己的設(shè)計回答指導教師3-4個問題?？己私Y(jié)束后將課程設(shè)計報告和源程序的電子版交班長統(tǒng)一刻光盤上交。、主要參考文獻及資料1 嚴蔚敏 數(shù)據(jù)結(jié)構(gòu)（C語言版）清華大學出版社 19992 嚴蔚敏 數(shù)據(jù)結(jié)構(gòu)題集（C語言版）清華大學出版社 19993 譚浩強 C語言程序設(shè)計 清華大學出版社4 與所用編程環(huán)境相配套的C語言或C+相關(guān)的資料、成績評定：設(shè)計成績： （教師填寫）指導老師： （簽字）二一二 年 一 月 十 日目 錄第一章 概述1第二章 系統(tǒng)分析2第三章 概要設(shè)計3第四章 詳細設(shè)計4第五章 運行與測試17第六章 總結(jié)與心得19參考文獻20第一章 概述課程設(shè)計是實踐性教學中的一個重要環(huán)節(jié)，它以某一課程為基礎(chǔ)，可以涉及和課程相關(guān)的各個方面，是一門獨立于課程之外的特殊課程。課程設(shè)計是讓同學們對所學的課程更全面的學習和應(yīng)用，理解和掌握課程的相關(guān)知識。數(shù)據(jù)結(jié)構(gòu)是一門重要的專業(yè)基礎(chǔ)課，是計算機理論和應(yīng)用的核心基礎(chǔ)課程。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，要求學生在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)用、算法的設(shè)計及其實現(xiàn)等方面，加深對課程基本內(nèi)容的理解。同時，在程序設(shè)計方法以及上機操作等基本技能和科學作風方面受到比較系統(tǒng)和嚴格的訓練。在這次的課程設(shè)計中我選擇的題目是順序結(jié)構(gòu)、動態(tài)鏈表結(jié)構(gòu)下的一元多項式的加法、減法、乘法的實現(xiàn)。分別采用順序結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)，利用多項得結(jié)果，最后得多項式中不含有重復階項和零系數(shù)得項。除此之外，還得分為降冪和升冪兩種排序方式。第二章 系統(tǒng)分析1 順序結(jié)構(gòu)、動態(tài)鏈表結(jié)構(gòu)下的一元多項式的加法、減法、乘法的實現(xiàn)?？梢苑譃閹讉€模塊：輸入模塊、輸出模塊（升冪降冪）、數(shù)據(jù)處理模塊（多項式的加減乘）、主程序模塊。2 在程序過程中加入漢字提示符，讓使用者清楚明白的操作該程序。運行程序時看起來簡潔有序，操作簡單明了。3 程序執(zhí)行時的命令：選擇創(chuàng)建兩個一元多項式輸入第一個一元多項式的項數(shù)依次輸入一元多項式的系數(shù)和指數(shù)以相同方式輸入第二個一元多項式選擇操作方式選擇降冪或升冪排序輸出結(jié)果是否退出。4. 測試數(shù)據(jù)。輸入的一元多項式系數(shù)指數(shù)分別為7 0,3 1,9 8,5 17和8 1,22 7，-9 8。加法結(jié)果為；升冪 降冪減法結(jié)果為：升冪 降冪乘法結(jié)果為：升冪 降冪 第三章 概要設(shè)計1、數(shù)據(jù)結(jié)構(gòu)的設(shè)計 在該程序中分別分為順序存儲和鏈式存儲結(jié)構(gòu)。2、算法的設(shè)計本程序主要分為四大模塊主程序模塊輸入模塊：通過main函數(shù)輸入輸出模塊（升冪降冪）：PrintPolyn函數(shù)實現(xiàn)輸出數(shù)據(jù)處理模塊（多項式的加減乘）：通過一元多項式的Polynomial基本操作實現(xiàn)3、抽象數(shù)據(jù)類型的設(shè)計一元多項式抽象數(shù)據(jù)類型的定義：抽象數(shù)據(jù)類型Polynomial的定義：第四章 詳細設(shè)計#includeusing namespace std;struct term/順序表和鏈表的的定義float xishu; /系數(shù)int zhishu; /指數(shù);struct LNode term data; /term多項式值struct LNode *next;typedef LNode* polynomail;/*合并同類項*/polynomail hebing(polynomail Head)polynomail r,q,p,Q;for(q=Head-next;q!=NULL;q=q-next)/合并同類項for(p=q-next,r=q;p!=NULL;)if(q-data.zhishu=p-data.zhishu)/指數(shù)相等 系數(shù)相加 q-data.xishu=q-data.xishu+p-data.xishu;r-next=p-next;Q=p;p=p-next;delete Q;/釋放pelser=r-next;p=p-next;return Head;/得到不含同類項的多項式/*又小到大排列*/void arrange1(polynomail pa)polynomail h=pa,p,q,r;for(p=pa;p-next!=NULL;p=p-next);r=p;/r指向參與比較的最后一個while(h-next!=r)/大的沉底for(p=h;p-next!=r&p!=r;p=p-next)if(p-next-data.zhishup-next-next-data.zhishu)/比較指數(shù)的大小q=p-next-next;p-next-next=q-next;/指數(shù)大的向前移動q-next=p-next;p-next=q;r=p;/r指向參與比較的最后一個，不斷向前移動 /*由大到小排序*/void arrange2(polynomail pa) polynomail h=pa,p,q,r;for(p=pa;p-next!=NULL;p=p-next); r=p;while(h-next!=r)/小的沉底for(p=h;p-next!=r&p!=r;p=p-next)if(p-next-data.zhishunext-next-data.zhishu)/指數(shù)比較大小 q=p-next-next;p-next-next=q-next;/指數(shù)小的向后移動q-next=p-next;p-next=q;r=p;/r指向參與比較的最后一個，不斷向前移動 /*判斷多項式的稀疏 */bool judge(polynomail Head)/邏輯變量字符boolarrange2(Head);polynomail p;p=Head-next;bool xi=false;while(p!=NULL&p-next!=NULL&!xi)if(p-data.zhishu-p-next-data.zhishu1)xi=true;p=p-next;return xi;/*打印多項式,求項數(shù)*/void printpolyn(polynomail P)int i;polynomail q;if(P=NULL)cout無項next=NULL)coutY=0endl;elsecoutnext;i=1;if(q-data.xishu!=0&q-data.zhishu!=0)coutdata.xishuXdata.zhishu;i+; if(q-data.zhishu=0&q-data.xishu!=0)coutdata.xishu;/打印第一項q=q-next;if(q=NULL)coutdata.xishu!=0&q-data.zhishu!=0)if(q-data.xishu0) cout+;coutdata.xishuXdata.zhishu;i+;if(q-data.zhishu=0&q-data.xishu!=0) if(q-data.xishu0) cout+;coutdata.xishu;q=q-next;if(q=NULL)coutendl;break; /*1、創(chuàng)建并初始化多項式鏈表*/polynomail creatpolyn(int m)polynomail Head,r,s;int i;Head=new LNode;r=Head;for(i=0;im;i+) s=new LNode;cout請輸入第i+1s-data.xishus-data.zhishu;r-next=s; r=s;r-next=NULL;if(m1)Head=hebing(Head);return Head;/*2、兩多項式相加*/polynomail addpolyn(polynomail pa,polynomail pb)polynomail s,newHead,q,p,r;int j;p=pa-next;q=pb-next;newHead=new LNode;r=newHead;while(p) s=new LNode;s-data.xishu=p-data.xishu;s-data.zhishu=p-data.zhishu;r-next=s; r=s;p=p-next;while(q) s=new LNode;s-data.xishu=q-data.xishu;s-data.zhishu=q-data.zhishu;r-next=s; r=s;q=q-next;r-next=NULL;if(newHead-next!=NULL&newHead-next-next!=NULL)/合并同類項newHead=hebing(newHead);cout升序 1 , 降序 2endl;coutj;if(j=1) arrange1(newHead);else arrange2(newHead);return newHead;/*3、兩多項式相減*/polynomail subpolyn(polynomail pa,polynomail pb)polynomail s,newHead,q,p,r; int j;p=pa-next;q=pb-next;newHead=new LNode;r=newHead;while(p)s=new LNode;s-data.xishu=p-data.xishu;s-data.zhishu=p-data.zhishu;r-next=s; r=s;p=p-next;while(q)s=new LNode;s-data.xishu=-q-data.xishu;s-data.zhishu=q-data.zhishu;r-next=s; r=s; q=q-next;r-next=NULL; if(newHead-next!=NULL&newHead-next-next!=NULL)/合并同類項newHead=hebing(newHead);cout升序 1 , 降序 2endl;coutj;if(j=1) arrange1(newHead); elsearrange2(newHead);return newHead;/*4兩多項式相乘*/polynomail mulpolyn(polynomail pa,polynomail pb) polynomail s,newHead,q,p,r; int j;newHead=new LNode;r=newHead;for(p=pa-next;p!=NULL;p=p-next)for(q=pb-next;q!=NULL;q=q-next)s=new LNode;s-data.xishu=p-data.xishu*q-data.xishu;s-data.zhishu=p-data.zhishu+q-data.zhishu;r-next=s;r=s;r-next=NULL;cout升序 1 , 降序 2endl;coutj;if(j=1) arrange1(newHead);else arrange2(newHead);if(newHead-next!=NULL&newHead-next-next!=NULL)/合并同類項newHead=hebing(newHead);return newHead;/*5、銷毀已建立的兩個多項式*/void delpolyn(polynomail pa,polynomail pb)polynomail p,q;p=pa;while(p!=NULL) q=p;p=p-next;free(q);p=pb;while(p!=NULL) q=p;p=p-next;free(q);cout兩個多項式已經(jīng)銷毀endl;void main() polynomail pa=NULL,pb=NULL;polynomail addp=NULL,subp=NULL,mulp=NULL;int n,m;while(1)cout1、創(chuàng)建兩個一元多項式endl;cout2、兩多項式相加得一新多項式endl;cout3、兩多項式相減得一新多項式endl;cout4、兩多項式相乘得一新多項式endl;cout5、銷毀已建立的兩個多項式endl;cout6、退出endl;coutn;switch(n)case 1:if(pa!=NULL) cout已建立兩個一元多項式，請選擇其他操作！;break;cout請輸入第一個多項式:endl;coutm;while(m=0) coutm;pa=creatpolyn(m);printpolyn(pa);if(judge(pa)cout該多項式稀疏endl;elsecout該多項式稠密endl;cout請輸入第二個多項式:endl;cout要輸入幾項：m;pb=creatpolyn(m);printpolyn(pb);if(judge(pb)cout該多項式稀疏endl;elsecout該多項式稠密endl;break;case 2:if(pa=NULL) cout請先創(chuàng)建兩個一元多項式！endl;break;addp=addpolyn(pa,pb);/多項式相加printpolyn(addp);break;case 3:if(pa=NULL)cout請先創(chuàng)建兩個一元多項式!endl;break;subp=subpolyn(pa,pb);/多項式相減printpolyn(subp);/打印輸出break;case 4:if(pa=NULL)cout請先創(chuàng)建兩個一元多項式!endl;break; mulp=mulpolyn(pa,pb);/多項式相乘printpolyn(mulp);/打印輸出break;case 5: if(pa=NULL)cout請先創(chuàng)建兩個一元多項式endl;break;delpolyn(pa,pb);/多項式的刪除pa=pb=NULL;break;case 6:de