數(shù)據(jù)結(jié)構(gòu)課程設(shè)計——多項式及猴子吃桃問題

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

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

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認(rèn)領(lǐng)

文檔簡介

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

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

3、p>　　有一群猴子摘了一堆桃子，它們每天都吃當(dāng)前桃子的一半再多吃一個，到了第10天就剩下一個桃子，用多種方法實現(xiàn)求出原來這群猴子共摘了多少桃子。　　要求：1）采用數(shù)組數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解；　　2）采用鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)。　　一、課程設(shè)計工作日自 2012 年 2 月

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

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

6、主要參考資料：　　[1] 嚴(yán)蔚敏．?dāng)?shù)據(jù)結(jié)構(gòu)（C語言版）．清華大學(xué)出版社，2007　　[2] 嚴(yán)蔚敏．?dāng)?shù)據(jù)結(jié)構(gòu)題集（C語言版）．清華大學(xué)出版社，2007　　[3] 譚浩強．C語言程序設(shè)計．清華大學(xué)出版社，2005　　[4] 與所用編程環(huán)境相配套的C語言或

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

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

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

10、t;p>　　二、具體設(shè)計概要　　1、數(shù)據(jù)結(jié)構(gòu)的設(shè)計 　　在該程序中分別分為順序存儲和鏈?zhǔn)酱鎯Y(jié)構(gòu)。　　2、算法的設(shè)計　　本程序主要分為四大模塊<

11、;b>　?、僦鞒绦蚰K　?、谳斎肽K：通過Getpolyn函數(shù)輸入　　③輸出模塊（升冪降冪）：PrintPolyn函數(shù)實現(xiàn)輸出　?、軘?shù)據(jù)處理模塊（多項式的加減乘）：通過一元多項式的Polynomial基本操作實現(xiàn)　　3、抽象數(shù)據(jù)類型的設(shè)計<

12、/p>　　一元多項式抽象數(shù)據(jù)類型的定義：　　抽象數(shù)據(jù)類型Polynomial的定義：　　三、詳細(xì)程序設(shè)計及運行結(jié)果：　　第一題　　程序及運行結(jié)果：

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

14、　int zhishu; //指數(shù)　　};　　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、;　　/*打印多項式,求項數(shù)*/　　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中，打印剩下項中系數(shù)非零的項， 　　{　　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<<"項的系數(shù)和指數(shù)：";　　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<<"兩個多項式已經(jīng)銷毀\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、;　　程序及運行結(jié)果：　　public class Monkey {　　//主函數(shù)　　public static void main(String[] args) {　　List l = new

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

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;　　//在當(dāng)前結(jié)點前插入一個結(jié)點，并使其成為當(dāng)前結(jié)點　　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、//將當(dāng)前結(jié)點移出鏈表，下一個結(jié)點成為當(dāng)前結(jié)點，如果移出的結(jié)點是最后一個結(jié)點，則第一個結(jié)點成為當(dāng)前結(jié)點　　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;　　}　　//返回當(dāng)前結(jié)點的指針</p&g

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

106、>　　else　　return Pointer.next;　　}　　//返回當(dāng)前結(jié)點的值　　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;　　}　　//鏈表實現(xiàn)　　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("鏈表實現(xiàn)：");　　System.out.println("桃子總數(shù): " + s);　　} else a.insert(new Integer(i)

112、);　　}　　}　　//數(shù)組實現(xiàn)　　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("數(shù)組實現(xiàn)：");　　System.out.println("桃子總數(shù): " + 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;　　//構(gòu)成鏈表的結(jié)點定義　　public class Node {　　public Node next;　　public Object data;　　public

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

119、/具體方法實現(xiàn)要求　　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;　　//在當(dāng)前結(jié)點前插入一個結(jié)點，并使其成為當(dāng)前結(jié)點　　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 ++;　　}　　//將當(dāng)前結(jié)點移出鏈表，下一個結(jié)點成為當(dāng)前結(jié)點，如果移出的結(jié)點是最后一個結(jié)點，則第一個結(jié)點成為當(dāng)前結(jié)點

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;　　}　　//返回當(dāng)前結(jié)點的指針　　private Node cursor() {　　if(Head == null)&l

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

130、p>　　}　　//返回當(dāng)前結(jié)點的值　　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;　　}　　//鏈表實現(xiàn)<

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("鏈表實現(xiàn)：");　　System.out.println("桃子總數(shù)= " + s);　　} else a.insert(new Integer(i));　　}&l

136、t;p>　　}　　//數(shù)組實現(xiàn)　　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("數(shù)組實現(xiàn)：");<

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

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

溫馨提示

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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計——多項式及猴子吃桃問題

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計——多項式及猴子吃桃問題

文檔簡介

溫馨提示

最新文檔

評論

免費下載