數據結構課程設計——多項式及猴子吃桃問題

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數：21 大?。?14.00KB 人氣指數：12 舉報 版權申訴

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

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　課程設計任務書　　課程設計課題：　　第一題：在順序結構、動態(tài)鏈表結構下實現一元多項式的加法、減法、乘法運算。　　設有一元多項式和

2、　請實現求：　　要求：1）首先判定多項式是否稀疏；　　2）分別采用順序和動態(tài)存儲結構實現；　　3）結果中無重復階項、無零系數項；　　4）要求輸出結果的升冪和降冪兩種排列情況。　　第二題：猴子吃桃問題：</

3、p>　　有一群猴子摘了一堆桃子，它們每天都吃當前桃子的一半再多吃一個，到了第10天就剩下一個桃子，用多種方法實現求出原來這群猴子共摘了多少桃子。　　要求：1）采用數組數據結構實現上述求解；　　2）采用鏈式數據結構。　　一、課程設計工作日自 2012 年 2 月

4、 21 日至 2012 年 3 月 2 日　　二、同組學生：無。　　三、課程設計任務要求（包括課題來源、類型、目的和意義、基本要求、完成時間、主要參考資料等）：&

5、lt;b>　　課題來源：教師提供　　課題類型：設計　　目的和意義：通過數據結構課程設計掌握在C語言中結構體的建立和使用，并能用合適的數據結構設計大型程序　　完成時間：2012年2月29日

6、主要參考資料：　　[1] 嚴蔚敏．數據結構（C語言版）．清華大學出版社，2007　　[2] 嚴蔚敏．數據結構題集（C語言版）．清華大學出版社，2007　　[3] 譚浩強．C語言程序設計．清華大學出版社，2005　　[4] 與所用編程環(huán)境相配套的C語言或

7、C++相關的資料　　指導教師簽字：教研室主任簽字： 　　2012年2月29日　　一、設計分析　　順序結構、動態(tài)鏈表結構下的一元多項式的加法、減法、乘法的實現?？梢苑譃閹讉€模塊：輸入模塊、輸出模塊（升冪

8、降冪）、數據處理模塊（多項式的加減乘）、主程序模塊。　　在程序過程中加入漢字提示符，讓讀者清楚明白的操作該程序。運行程序時看起來簡潔有序，操作簡單明了。　　程序執(zhí)行時的命令：①選擇創(chuàng)建兩個一元多項式②輸入第一個一元多項式的項數③依次輸入一元多項式的系數和指數④以相同方式輸入第二個一元多項式⑤選擇操作方式⑥選擇降冪或升冪排序⑦輸出結果⑧是否退出</p

9、>　　4.測試數據。輸入的一元多項式系數指數分別為7 0,3 1,9 8,5 17和8 1,22 7，-9 8。加法結果為；升冪降冪　　減法結果為：升冪降冪　　乘法結果為：升冪降冪&l

10、t;p>　　二、具體設計概要　　1、數據結構的設計 　　在該程序中分別分為順序存儲和鏈式存儲結構。　　2、算法的設計　　本程序主要分為四大模塊<

11、;b>　?、僦鞒绦蚰K　?、谳斎肽K：通過Getpolyn函數輸入　　③輸出模塊（升冪降冪）：PrintPolyn函數實現輸出　?、軘祿幚砟K（多項式的加減乘）：通過一元多項式的Polynomial基本操作實現　　3、抽象數據類型的設計<

12、/p>　　一元多項式抽象數據類型的定義：　　抽象數據類型Polynomial的定義：　　三、詳細程序設計及運行結果：　　第一題　　程序及運行結果：

13、　　#include<iostream>　　using namespace std;　　struct term　　{　　float xishu; //系數

14、　int zhishu; //指數　　};　　struct LNode　　{ 　　term data; //term多項式值

15、　　struct LNode *next;　　};　　typedef LNode* polynomail;　　/*合并同類項*/　　polynomail hebing(polynomail Hea

16、d)　　{　　polynomail r,q,p,Q;　　for(q=Head->next;q!=NULL;q=q->next)//合并同類項　　for(p=q->next,r=q;p!=NULL;)

17、;　　if(q->data.zhishu==p->data.zhishu)　　{ 　　q->data.xishu=q->data.xishu+p->data.xishu;　　r->next=p->next;<

18、;/p>　　Q=p;p=p->next;　　delete Q;　　}　　else　　{

19、　　r=r->next;　　p=p->next;　　}　　return Head;　　}　　/*由小

20、到大排列*/　　void arrange1(polynomail pa)　　{　　polynomail h=pa,p,q,r;　　for(p=pa;p->next!=NULL;p=p->next);r=p;</p&g

21、t;　　while(h->next!=r)//大的沉底　　{　　for(p=h;p->next!=r&&p!=r;p=p->next)　　if(p->next->data.zhishu>p->ne

22、xt->next->data.zhishu)　　{　　q=p->next->next;　　p->next->next=q->next;　　q->next=p->next;</

23、p>　　p->next=q;　　}　　r=p;//r指向參與比較的最后一個，不斷向前移動　　}　　}

24、　　/*由大到小排序*/　　void arrange2(polynomail pa)　　{ 　　polynomail h=pa,p,q,r;　　for(p=pa;p->next!=NULL;p=p->ne

25、xt); r=p;　　while(h->next!=r)//小的沉底　　{　　for(p=h;p->next!=r&&p!=r;p=p->next)　　if(p->next->data.

26、zhishu<p->next->next->data.zhishu)　　{ 　　q=p->next->next;　　p->next->next=q->next;　　q->ne

27、xt=p->next;　　p->next=q;　　}　　r=p;//r指向參與比較的最后一個，不斷向前移動　　} 　　}&l

28、t;/b>　　bool judge(polynomail Head)　　{　　arrange2(Head);　　polynomail p;　　p=Head->next;</p

29、>　　bool xi=false;　　while(p!=NULL&&p->next!=NULL&&!xi)　　{　　if(p->data.zhishu-p->next->data.zhishu

30、>1)　　xi=true;　　p=p->next;　　}　　return xi;　　}

31、;　　/*打印多項式,求項數*/　　void printpolyn(polynomail P)　　{　　int i;　　polynomail q;&l

32、t;p>　　if(P==NULL)　　cout<<"無項\n";　　else if(P->next==NULL)　　cout<<"Y=0\n";　　else&

33、lt;/p>　　{　　cout<<"該多項式為Y=";　　q=P->next;　　i=1;　　if(q->data.xish

34、u!=0&&q->data.zhishu!=0)　　{　　cout<<q->data.xishu<<"X^"<<q->data.zhishu;　　i++; </b

35、>　　}　　if(q->data.zhishu==0&&q->data.xishu!=0)　　cout<<q->data.xishu;//打印第一項　　q=q->next;&l

36、t;/p>　　if(q==NULL)　　{　　cout<<"\n";　　return ;　　}&l

37、t;/p>　　while(1)//while中，打印剩下項中系數非零的項， 　　{　　if(q->data.xishu!=0&&q->data.zhishu!=0)　　{

38、　　if(q->data.xishu>0) 　　cout<<"+";　　cout<<q->data.xishu<<"X^"<<q->data.zhishu;&l

39、t;b>　　i++;　　}　　if(q->data.zhishu==0&&q->data.xishu!=0)　　{ 　　if(q->da

40、ta.xishu>0) cout<<"+";　　cout<<q->data.xishu;　　}　　q=q->next;　　if(q==NULL)&

41、lt;p>　　{　　cout<<"\n";　　break; 　　}　　}</

42、p>　　}　　}　　/*1、創(chuàng)建并初始化多項式鏈表*/　　polynomail creatpolyn(int m)　　{</

43、p>　　polynomail Head,r,s;　　int i;　　Head=new LNode;　　r=Head;　　for(i=0;i<m;i++)</

44、p>　　{ 　　s=new LNode;　　cout<<"請輸入第"<<i+1<<"項的系數和指數：";　　cin>>s->data.xishu>&

45、gt;s->data.zhishu;　　r->next=s; r=s;　　}　　r->next=NULL;　　if(m>1)<

46、;b>　　{　　Head=hebing(Head);　　}　　return Head;　　}　　/*2、兩多項式相加*/<

47、/p>　　polynomail addpolyn(polynomail pa,polynomail pb)　　{　　polynomail s,newHead,q,p,r;int j;　　p=pa->next;<p

48、>　　q=pb->next;　　newHead=new LNode;　　r=newHead;　　while(p)　　{ 　　s=new LNo

49、de;　　s->data.xishu=p->data.xishu;　　s->data.zhishu=p->data.zhishu;　　r->next=s; r=s;　　p=p->next;&l

50、t;b>　　}　　while(q)　　{ 　　s=new LNode;　　s->data.xishu=q->data.xishu;&l

51、t;p>　　s->data.zhishu=q->data.zhishu;　　r->next=s; r=s;　　q=q->next;　　}　　r->next=NULL;&l

52、t;p>　　if(newHead->next!=NULL&&newHead->next->next!=NULL)//合并同類項　　newHead=hebing(newHead);　　cout<<"升序 1 , 降序 2\n";　　cout&

53、lt;<"選擇:";　　cin>>j;　　if(j==1) 　　arrange1(newHead);　　else <p&g

54、t;　　arrange2(newHead);　　return newHead;　　}　　/*3、兩多項式相減*/　　polynomail subpolyn(polynomail pa,polynomail pb)

55、　　{　　polynomail s,newHead,q,p,r; int j;　　p=pa->next;q=pb->next;　　newHead=new LNode;　　r=newHead;</p

56、>　　while(p)　　{　　s=new LNode;　　s->data.xishu=p->data.xishu;　　s->data.zhishu=

57、p->data.zhishu;　　r->next=s; r=s;　　p=p->next;　　}　　while(q)

58、　{　　s=new LNode;　　s->data.xishu=-q->data.xishu;　　s->data.zhishu=q->data.zhishu;　　r->next=s; r=s;&l

59、t;p>　　q=q->next;　　}　　r->next=NULL;　　if(newHead->next!=NULL&&newHead->next->next!=NULL)//合并同類項<p&g

60、t;　　newHead=hebing(newHead);　　cout<<"升序 1 , 降序 2\n";　　cout<<"選擇:";　　cin>>j;<

61、;b>　　if(j==1) 　　arrange1(newHead);　　else　　arrange2(newHead);　　return newHead;<b&

62、gt;　　}　　/*4兩多項式相乘*/　　polynomail mulpolyn(polynomail pa,polynomail pb)　　{ 　　polynomail s,newHead,q,p,r;</

63、p>　　int j;　　newHead=new LNode;　　r=newHead;　　for(p=pa->next;p!=NULL;p=p->next)　　for(q=pb->next;

64、q!=NULL;q=q->next)　　{　　s=new LNode;　　s->data.xishu=p->data.xishu*q->data.xishu;　　s->data.zhishu=p->

65、data.zhishu+q->data.zhishu;　　r->next=s;　　r=s;　　}　　r->next=NULL;　　cou

66、t<<"升序 1 , 降序 2\n";　　cout<<"選擇:";　　cin>>j;　　if(j==1) arrange1(newHead);　　else

67、 arrange2(newHead);　　if(newHead->next!=NULL&&newHead->next->next!=NULL)//合并同類項　　newHead=hebing(newHead);　　return newHead;&l

68、t;p>　　}　　/*5、銷毀已建立的兩個多項式*/　　void delpolyn(polynomail pa,polynomail pb)　　{　　polynomail p,q;</

69、p>　　p=pa;　　while(p!=NULL)　　{ 　　q=p;　　p=p->next;<

70、;p>　　free(q);　　}　　p=pb;　　while(p!=NULL)　　{ &l

71、t;p>　　q=p;　　p=p->next;　　free(q);　　}　　cout<<"兩個多項式已經銷毀\n";

72、　　}　　void main()　　{ 　　polynomail pa=NULL,pb=NULL;　　polynomail addp=NULL,subp=

73、NULL,mulp=NULL;　　int n,m;　　while(1)　　{　　cout<<"1、創(chuàng)建兩個一元多項式\n";&

74、lt;/p>　　cout<<"2、兩多項式相加得一新多項式\n";　　cout<<"3、兩多項式相減得一新多項式\n";　　cout<<"4、兩多項式相乘得一新多項式\n";　　cout&l

75、t;<"5、銷毀已建立的兩個多項式\n";　　cout<<"6、退出\n";　　cout<<"請選擇：";　　cin>>n;<

76、b>　　switch(n)　　{　　case 1:　　if(pa!=NULL)　　{

77、cout<<"已建立兩個一元多項式，請選擇其他操作！";　　break;　　}　　cout<<"請輸入第一個多項式：\n";　　co

78、ut<<"要輸入幾項：";　　cin>>m;　　while(m==0)　　{ 　　cout<<"m不能為0，請重新輸入m:&quo

79、t;;　　cin>>m;　　}　　pa=creatpolyn(m);　　printpolyn(pa);　　if(judge(pa))</

80、p>　　cout<<"該多項式稀疏\n";　　else　　cout<<"該多項式稠密\n";　　cout<<"請輸入第二個多項式：\n";</p&

81、gt;　　cout<<"要輸入幾項：";　　cin>>m;　　pb=creatpolyn(m);　　printpolyn(pb);　　if(judge(pb))<

82、/p>　　cout<<"該多項式稀疏\n";　　else　　cout<<"該多項式稠密\n";　　break;<p&

83、gt;　　case 2:　　if(pa==NULL)　　{ 　　cout<<"請先創(chuàng)建兩個一元多項式！\n";　　break;

84、　　}　　addp=addpolyn(pa,pb);　　printpolyn(addp);　　break;　　case 3:</b

85、>　　if(pa==NULL)　　{　　cout<<"請先創(chuàng)建兩個一元多項式！\n";　　break;<b&g

86、t;　　}　　subp=subpolyn(pa,pb);　　printpolyn(subp);　　break;　　case 4:　　i

87、f(pa==NULL)　　{　　cout<<"請先創(chuàng)建兩個一元多項式！\n";　　break;　　}

88、　　mulp=mulpolyn(pa,pb);　　printpolyn(mulp);　　break;　　case 5: 　　if(pa==NULL)

89、{　　cout<<"請先創(chuàng)建兩個一元多項式！\n";　　break;　　}　　delpolyn(pa,pb);<p

90、>　　pa=pb=NULL;　　break;　　case 6:　　delpolyn(pa,pb);　　exit(0);<p

91、>　　}　　}　　}　　s　　第二題

92、;　　程序及運行結果：　　public class Monkey {　　//主函數　　public static void main(String[] args) {　　List l = new

93、List();　　l.array();　　l.link();　　}　　}　　//構成鏈表的結點定義

94、;　　public class Node {　　public Node next;　　public Object data;　　public Node(Object data, Node next) {　　this.data = data;</

95、p>　　this.next = next;　　}　　}　　public class List {　　private Node Head = null;

96、;　　private Node Tail = null;　　private Node Pointer = null;　　private int Length = 0;　　//在當前結點前插入一個結點，并使其成為當前結點　　public void in

97、sert(Object d) {　　Node e = new Node(d, null);　　if(Length == 0) {　　Tail = e;　　Head = e;

98、　　} else {　　Node temp = cursor();　　e.next = temp;　　if(Pointer == null)　　Head = e;</p&g

99、t;　　else　　Pointer.next = e;　　}　　Length ++;　　}

100、//將當前結點移出鏈表，下一個結點成為當前結點，如果移出的結點是最后一個結點，則第一個結點成為當前結點　　public Object remove() {　　Object temp;　　if(Length == 0)　　return 0;</b&g

101、t;　　else if(Length == 1) {　　temp = Head.data;　　deleteAll();　　}　　else {</p&

102、gt;　　Node cur = cursor();　　temp = cur.data;　　if(cur == Head)　　Head = cur.next;　　else if(cur == Tail) {

103、Pointer.next = null;　　Tail = Pointer;　　reset();　　}　　else

104、Pointer.next = cur.next;　　Length --;　　}　　return temp;　　}　　//返回當前結點的指針</p&g

105、t;　　private Node cursor() {　　if(Head == null)　　return null;　　else if(Pointer == null)　　return Head;<b

106、>　　else　　return Pointer.next;　　}　　//返回當前結點的值　　public Object currentNode() {　　Node t

107、emp = cursor();　　return temp.data;　　}　　public void deleteAll() {　　Head = null;　　Tail = null;<

108、/p>　　Pointer = null;　　Length = 0;　　}　　public void reset() {　　Pointer = null;<b&

109、gt;　　}　　//鏈表實現　　public void link() {　　int s = 0;　　List a=new List ();　　for(int i=1;i&l

110、t;=10;i++) {　　if(a.Length == 9) {　　s = 1;　　while(a.Length != 0) {　　s = s*2 + 2;　　a.remove();<

111、/p>　　}　　System.out.println("鏈表實現：");　　System.out.println("桃子總數: " + s);　　} else a.insert(new Integer(i)

112、);　　}　　}　　//數組實現　　public void array() {　　int a[] = new int

113、[10];　　a[9] = 1;　　for(int i=a.length-2; i>=0; i--) {　　a[i] = 2 * a[i+1] +2;　　}<p

114、>　　System.out.println("數組實現：");　　System.out.println("桃子總數: " + a[0]);　　System.out.println("****************");　　}&

115、lt;/b>　　}　　1)package com.zw.tute.list;　　public class Monkey {　　public static void main(String[] args) {

116、　　List l = new List();　　l.array();　　l.link();　　}　　}<p&

117、gt;　　2)package com.zw.tute.list;　　//構成鏈表的結點定義　　public class Node {　　public Node next;　　public Object data;　　public

118、Node(Object data, Node next) {　　this.data = data;　　this.next = next;　　}　　}　　/

119、/具體方法實現要求　　3)package com.zw.tute.list;　　public class List {　　private Node Head = null;　　private Node Tail = null;

120、private Node Pointer = null;　　private int Length = 0;　　//在當前結點前插入一個結點，并使其成為當前結點　　public void insert(Object d) {　　Node e = new Node(d, nu

121、ll);　　if(Length == 0) {　　Tail = e;　　Head = e;　　} else {　　N

122、ode temp = cursor();　　e.next = temp;　　if(Pointer == null)　　Head = e;　　else　　P

123、ointer.next = e;　　}　　Length ++;　　}　　//將當前結點移出鏈表，下一個結點成為當前結點，如果移出的結點是最后一個結點，則第一個結點成為當前結點

124、　　public Object remove(Object temp, int k) {　　if(Length == 0)　　return 0;　　else if(Length == 1) {　　temp = He

125、ad.data;　　deleteAll();　　}　　else {　　Node cur = cursor();　　temp = cur.data;<

126、/p>　　if(cur == Head)　　Head = cur.next;　　else if(cur == Tail) {　　Pointer.next = null;　　Tail = Pointer;

127、　　reset();　　}　　else　　Pointer.next = cur.next;　　Length --;&

128、lt;b>　　}　　return temp;　　}　　//返回當前結點的指針　　private Node cursor() {　　if(Head == null)&l

129、t;/p>　　return null;　　else if(Pointer == null)　　return Head;　　else　　return Pointer.next;<

130、p>　　}　　//返回當前結點的值　　public Object currentNode() {　　Node temp = cursor();　　return temp.data;<

131、;b>　　}　　public void deleteAll() {　　Head = null;　　Tail = null;　　Pointer = null;　　Length = 0;

132、　　}　　public void reset() {　　Pointer = null;　　}　　//鏈表實現<

133、;p>　　public void link() {　　int s = 0;　　List a=new List ();　　for(int i=1;i<=10;i++) {　　if(a.Length == 9) {<

134、b>　　s = 1;　　while(a.Length != 0) {　　s = s*2 + 2;　　a.remove(new Integer(10-i), s);　　}

135、;　　System.out.println("鏈表實現：");　　System.out.println("桃子總數= " + s);　　} else a.insert(new Integer(i));　　}&l

136、t;p>　　}　　//數組實現　　public void array() {　　int a[] = new int[10];　　a[9] = 1;<

137、;/p>　　for(int i=a.length-2; i>=0; i--) {　　a[i] = 2 * a[i+1] +2;　　}　　System.out.println("數組實現：");<

138、;p>　　System.out.println("桃子總數= " + a[0]);　　System.out.println("****************");　　}　　}</p&

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

溫馨提示

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

數據結構課程設計——多項式及猴子吃桃問題

文檔簡介

溫馨提示

最新文檔

評論

數據結構課程設計——多項式及猴子吃桃問題

文檔簡介

溫馨提示

最新文檔

評論

免費下載