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

1、.山東理工大學(xué)計算機(jī)學(xué)院課程設(shè)計（數(shù)據(jù)結(jié)構(gòu)）班級姓名學(xué)號指導(dǎo)教師二一二年一月十日;.課程設(shè)計任務(wù)書及成績評定順序結(jié)構(gòu)、 動態(tài)鏈表結(jié)構(gòu)下的一元多項式的加法、減法、乘法的課題名稱實(shí)現(xiàn)。、題目的目的和要求：1. 鞏固和加深對數(shù)據(jù)結(jié)構(gòu)的理解，通過上機(jī)實(shí)驗、調(diào)試程序，加深對課本知識的理解，最終使學(xué)生能夠熟練應(yīng)用數(shù)據(jù)結(jié)構(gòu)的知識寫程序。1）通過本課程的學(xué)習(xí)，能熟練掌握幾種基本數(shù)據(jù)結(jié)構(gòu)的基本操作。2）能針對給定題目，選擇相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，分析并設(shè)計算法，進(jìn)而給出問題的正確求解過程并編寫代碼實(shí)現(xiàn)。2設(shè)計題目要求：1) 首先判定多項式是否稀疏2) 分別采用順序和動態(tài)存儲結(jié)構(gòu)實(shí)現(xiàn)；3) 結(jié)果 M(x) 中無重復(fù)階項和

2、無零系數(shù)項；4) 要求輸出結(jié)果的升冪和降冪兩種排列情況；、設(shè)計進(jìn)度及完成情況日期內(nèi)容1.2-1.31.41.5選取參考書，查閱有關(guān)文獻(xiàn)資料，完成資料搜集和系統(tǒng)分析工作。創(chuàng)建相關(guān)數(shù)據(jù)結(jié)構(gòu) , 錄入源程序。1.61.7調(diào)試程序并記錄調(diào)試中的問題，初步完成課程設(shè)計報告。上交課程設(shè)計報告打印版并進(jìn)行課程設(shè)計答辯，要求每個同學(xué)1.9針對自己的設(shè)計回答指導(dǎo)教師3-4 個問題?？己私Y(jié)束后將課程設(shè)計報告和源程序的電子版交班長統(tǒng)一刻光盤上交。;.、主要參考文獻(xiàn)及資料1 嚴(yán)蔚敏 數(shù)據(jù)結(jié)構(gòu)（ C語言版）清華大學(xué)出版社 19992 嚴(yán)蔚敏 數(shù)據(jù)結(jié)構(gòu)題集（ C語言版）清華大學(xué)出版社 19993 譚浩強(qiáng) C 語言程序設(shè)計

3、 清華大學(xué)出版社4 與所用編程環(huán)境相配套的 C 語言或 C+相關(guān)的資料、成績評定：設(shè)計成績：（教師填寫）指導(dǎo)老師：（簽字）二一二年一月十日;.目錄 1 2 3 4 17 19 20;.第一章概述課程設(shè)計是實(shí)踐性教學(xué)中的一個重要環(huán)節(jié)，它以某一課程為基礎(chǔ)，可以涉及和課程相關(guān)的各個方面，是一門獨(dú)立于課程之外的特殊課程。課程設(shè)計是讓同學(xué)們對所學(xué)的課程更全面的學(xué)習(xí)和應(yīng)用，理解和掌握課程的相關(guān)知識。數(shù)據(jù)結(jié)構(gòu)是一門重要的專業(yè)基礎(chǔ)課，是計算機(jī)理論和應(yīng)用的核心基礎(chǔ)課程。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，要求學(xué)生在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)用、算法的設(shè)計及其實(shí)現(xiàn)等方面，加深對課程基本內(nèi)容的理解。同時，在程序

4、設(shè)計方法以及上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。在這次的課程設(shè)計中我選擇的題目是順序結(jié)構(gòu)、動態(tài)鏈表結(jié)構(gòu)下的一元多項式的加法、減法、乘法的實(shí)現(xiàn)。分別采用順序結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，利用多項得結(jié)果，最后得多項式中不含有重復(fù)階項和零系數(shù)得項。除此之外，還得分為降冪和升冪兩種排序方式。;.第二章系統(tǒng)分析1 順序結(jié)構(gòu)、動態(tài)鏈表結(jié)構(gòu)下的一元多項式的加法、減法、 乘法的實(shí)現(xiàn)?？梢苑譃閹讉€模塊：輸入模塊、輸出模塊（升冪降冪） 、數(shù)據(jù)處理模塊（多項式的加減乘） 、主程序模塊。2 在程序過程中加入漢字提示符，讓使用者清楚明白的操作該程序。運(yùn)行程序時看起來簡潔有序，操作簡單明了。3 程序執(zhí)行時的命

5、令： 選擇創(chuàng)建兩個一元多項式輸入第一個一元多項式的項數(shù)依次輸入一元多項式的系數(shù)和指數(shù)以相同方式輸入第二個一元多項式選擇操作方式選擇降冪或升冪排序輸出結(jié)果是否退出。4. 測試數(shù)據(jù)。輸入的一元多項式系數(shù)指數(shù)分別為 7 0,3 1,9 8,5 17和81,227，-98。加法結(jié)果為；升冪降冪減法結(jié)果為：升冪降冪乘法結(jié)果為：升冪降冪;.第三章概要設(shè)計1、數(shù)據(jù)結(jié)構(gòu)的設(shè)計在該程序中分別分為順序存儲和鏈?zhǔn)酱鎯Y(jié)構(gòu)。2、算法的設(shè)計本程序主要分為四大模塊主程序模塊輸入模塊：通過main 函數(shù)輸入輸出模塊（升冪降冪）：PrintPolyn 函數(shù)實(shí)現(xiàn)輸出數(shù)據(jù)處理模塊（多項式的加減乘）：通過一元多項式的Polynom

6、ial 基本操作實(shí)現(xiàn)3、抽象數(shù)據(jù)類型的設(shè)計一元多項式抽象數(shù)據(jù)類型的定義：抽象數(shù)據(jù)類型 Polynomial 的定義：;.第四章詳細(xì)設(shè)計#include<iostream>using namespace std;struct term/順序表和鏈表的的定義float xishu;/系數(shù)int zhishu;/指數(shù);struct LNodeterm data;/term多項式值struct LNode *next;typedef LNode* polynomail;/* 合并同類項 */polynomail hebing(polynomail Head)polynomail r,q,p

7、,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;/得到不含同類項的多項式/* 又小到大排列 */v

8、oid 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.zhishu>p->next->next->data.zhishu)/比較指數(shù)的大小q=p->next->next;p->next->next=q

9、->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.zhishu<p->

10、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指向參與比較的最后一個，不斷向前移動/* 判斷多項式的稀疏*/bool judge(polynomail Head)/邏輯變量字符 boolarrange2(Head);polynomail p;p=Head->next;bool xi=false;while(p!=NULL&&p->nex

11、t!=NULL&&!xi)if(p->data.zhishu-p->next->data.zhishu>1)xi=true;p=p->next;return xi;/* 打印多項式 , 求項數(shù) */void printpolyn(polynomail P)int i;.polynomail q;if(P=NULL)cout<<" 無項 "<<endl;else if(P->next=NULL)cout<<"Y=0"<<endl;elsecout<&l

12、t;" 該多項式為 Y="q=P->next;i=1;if(q->data.xishu!=0&&q->data.zhishu!=0)cout<<q->data.xishu<<"X"<<q->data.zhishu;i+;if(q->data.zhishu=0&&q->data.xishu!=0)cout<<q->data.xishu;/打印第一項q=q->next;if(q=NULL)cout<<endl;re

13、turn ;while(1)/while中，打印剩下項中系數(shù)非零的項，if(q->data.xishu!=0&&q->data.zhishu!=0)if(q->data.xishu>0)cout<<"+"cout<<q->data.xishu<<"X"<<q->data.zhishu;.i+;if(q->data.zhishu=0&&q->data.xishu!=0)if(q->data.xishu>0) cout&

14、lt;<"+"cout<<q->data.xishu;q=q->next;if(q=NULL)cout<<endl;break;/*1 、創(chuàng)建并初始化多項式鏈表*/polynomail creatpolyn(int m)polynomail Head,r,s;int i;Head=new LNode;r=Head;for(i=0;i<m;i+)s=new LNode;cout<<" 請輸入第 "<<i+1<<" 項的系數(shù)和指數(shù)： "cin>>

15、;s->data.xishu>>s->data.zhishu;r->next=s; r=s;.r->next=NULL;if(m>1)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.

16、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)/合并同類項

17、newHead=hebing(newHead);cout<<" 升序 1 ,降序 2"<<endl;cout<<" 選擇 :"cin>>j;if(j=1)arrange1(newHead);elsearrange2(newHead);return newHead;/*3 、兩多項式相減 */polynomail subpolyn(polynomail pa,polynomail pb)polynomail s,newHead,q,p,r; int j;p=pa->next;q=pb->next;

18、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-

19、>next!=NULL&&newHead->next->next!=NULL)/ 合并同類項 newHead=hebing(newHead);cout<<" 升序 1 ,降序 2"<<endl;cout<<" 選擇 :"cin>>j;if(j=1)arrange1(newHead);elsearrange2(newHead);return newHead;/*4 兩多項式相乘 */polynomail mulpolyn(polynomail pa,polynomail pb

20、)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<&

21、lt;" 升序 1 ,降序 2"<<endl;cout<<" 選擇 :"cin>>j;if(j=1) arrange1(newHead);elsearrange2(newHead);if(newHead->next!=NULL&&newHead->next->next!=NULL)/ 合并同類項 newHead=hebing(newHead);return newHead;/*5 、銷毀已建立的兩個多項式*/void delpolyn(polynomail pa,polynomail

22、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)cout<<"1 、創(chuàng)建兩個一元多項式 "<<endl;

23、cout<<"2 、兩多項式相加得一新多項式"<<endl;cout<<"3 、兩多項式相減得一新多項式"<<endl;cout<<"4 、兩多項式相乘得一新多項式"<<endl;cout<<"5 、銷毀已建立的兩個多項式"<<endl;cout<<"6 、退出 "<<endl;cout<<" 請選擇： "cin>>n;switch(

24、n)case 1:if(pa!=NULL)cout<<" 已建立兩個一元多項式，請選擇其他操作！"break;cout<<" 請輸入第一個多項式 :"<<endl;cout<<" 要輸入幾項： ".cin>>m;while(m=0)cout<<"m 不能為 0，請重新輸入 m:"cin>>m;pa=creatpolyn(m);printpolyn(pa);if(judge(pa)cout<<" 該多項式稀疏 &

25、quot;<<endl;elsecout<<" 該多項式稠密 "<<endl;cout<<" 請輸入第二個多項式 :"<<endl;cout<<" 要輸入幾項： "<<endl;cin>>m;pb=creatpolyn(m);printpolyn(pb);if(judge(pb)cout<<" 該多項式稀疏 "<<endl;elsecout<<" 該多項式稠密 "&

26、lt;<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)建兩個一元多項式!&quo