數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告-一元多項式加減運算

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

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

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

文檔簡介

1、　　課程設(shè) 計　?。〝?shù)據(jù)結(jié)構(gòu)）　　2013年 1 月 7 日　　課程設(shè)計任務(wù)書及成績評定　?、?、題目的目的和要求： 　　1.鞏固和加深對數(shù)據(jù)結(jié)構(gòu)的理解，通過上機(jī)實驗

2、、調(diào)試程序，加深對課本知識的理解，最終使學(xué)生能夠熟練應(yīng)用數(shù)據(jù)結(jié)構(gòu)的知識寫程序。　　（1）通過本課程的學(xué)習(xí)，能熟練掌握幾種基本數(shù)據(jù)結(jié)構(gòu)的基本操作。　?。?）能針對給定題目，選擇相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，分析并設(shè)計算法，進(jìn)而給出問題的正確求解過程并編寫代碼實現(xiàn)。　　2.設(shè)計題目要求：<

3、;/p>　　首先判定一元多項式是否稀疏　　分別采用順序和鏈?zhǔn)浇Y(jié)構(gòu)實現(xiàn)；　　結(jié)果在M(x)中無重復(fù)階項和無零系數(shù)項；　　要求結(jié)果以升冪排列輸出　?、?、設(shè)計進(jìn)度及完成情況　　Ⅲ、主要參考文獻(xiàn)及資料</

4、p>　　[1] 嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)（C語言版）清華大學(xué)出版社 1999　　[2] 嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)題集（C語言版）清華大學(xué)出版社 1999　　[3] 譚浩強(qiáng) C語言程序設(shè)計清華大學(xué)出版社　　[4] 與所用編程環(huán)境相配套的C語言或C++相關(guān)的資料

5、;　?、?、成績評定：　　設(shè)計成績：（教師填寫）　　指導(dǎo)老師：（簽字）　　二年月日　　目錄<

6、/p>　　第一章概述……………………………………………………………1　　第二章系統(tǒng)分析………………………………………………………2　　第三章概要設(shè)計………………………………………………………3　　第四章詳細(xì)設(shè)計………………………………………………………4

7、　　第五章運行與測試……………………………………………………18　　第六章總結(jié)與心得……………………………………………………20　　參考文獻(xiàn)………………………………………………………………21　　第一章概述

8、課程設(shè)計是實踐性教學(xué)中的一個重要環(huán)節(jié)，它以某一課程為基礎(chǔ)，可以涉及和課程相關(guān)的各個方面，是一門獨立于課程之外的特殊課程。課程設(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è)計及其實現(xiàn)等方面，加深對課程基本內(nèi)容的理

9、解。同時，在程序設(shè)計方法以及上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。　　在這次的課程設(shè)計中我選擇的題目是動態(tài)鏈表結(jié)構(gòu)下的一元多項式的加法、減法和乘法的實現(xiàn)。一元多項式計算是用C語言設(shè)計一個一元多項式簡單計算器。它能夠?qū)崿F(xiàn)按指數(shù)升序排列建立并輸出多項式，并且能夠完成兩個多項式的相加、相減與相乘的運算和將其結(jié)果輸入的功能。通過設(shè)計一元多項式，初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計

10、、程序編碼、測試等基本方法和技能提高，綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的能力；加深對常用數(shù)據(jù)結(jié)構(gòu)的理解，強(qiáng)化邏輯思維能力和動手能力，鞏固良好的編程習(xí)慣，掌握工程軟件設(shè)計的基本方法，為后續(xù)課程的學(xué)習(xí)打下堅實基礎(chǔ)。　　第二章系統(tǒng)分析　　動態(tài)鏈表結(jié)構(gòu)下的一元多項式的加法、減法、乘法的實現(xiàn)?？梢苑譃閹讉€模塊：

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

12、　　測試數(shù)據(jù)。輸入的一元多項式系數(shù)指數(shù)分別為7 0,3 1,9 8,5 17和8 1,22 7,-9 8。　　加法結(jié)果為：7+11x+22x^(7)+5x^(17)　　減法結(jié)果為：7-5x-22x^(7)+18x^(8)+5x^(17)　　乘法結(jié)果為：56x+24x^(2)+154x^(7)+

13、3x^(8)+45x^(9)+198x^(15)-81x^(16)+40x^(18)+110x^(24)-45x^(25)　　第三章概要設(shè)計　　數(shù)據(jù)結(jié)構(gòu)的設(shè)計　　為了節(jié)省存儲空間，只存儲多項式中系數(shù)非零的項，本程序使用鏈?zhǔn)酱鎯Y(jié)構(gòu)。&l

14、t;/p>　　算法的設(shè)計本設(shè)計從總體上劃分為3個模塊。　　主函數(shù)模塊。程序的入口，主要實現(xiàn)各個函數(shù)的調(diào)用。　　頭文件模塊。定義類和結(jié)構(gòu)體。　　函數(shù)模塊。數(shù)據(jù)處理和實現(xiàn)每個功能。　　抽象數(shù)據(jù)類型</p&

15、gt;　　ADT list{　　數(shù)據(jù)對象：D={ai | ai ∈ ElenSet, i=1,2,…,n,n≥0}　　數(shù)據(jù)關(guān)系：R1={<ai-1,ai> | ai-1,ai∈D,i=2,…,n}　　基本操作：</b

16、>　　InitLink(&head, len)　　初始條件：鏈表為空。　　操作結(jié)果：創(chuàng)建鏈表。　　Sparsity(&head, len)　　初始條件：鏈表已存在。

17、　操作結(jié)果：判斷是否稀疏。　　Display(head)　　初始條件：鏈表已存在。　　操作結(jié)果：輸出多項式。　　Merge(&head)　　初始條件：鏈表已存在。　　操作結(jié)果：合并

18、指數(shù)相同的項。　　SelectSort(&head)　　初始條件：鏈表已存在。　　操作結(jié)果：選擇排序。　　Negative(&head)　　初始條件：鏈表已存在。<b

19、>　　操作結(jié)果：取負(fù)。　　DelZero(&head)　　初始條件：鏈表已存在。　　操作結(jié)果：刪除系數(shù)為0的項。　　operator + (&head，&b);　　初始條件：鏈表已

20、存在。　　操作結(jié)果：重載+。　　operator * (&head，&b);　　初始條件：鏈表已存在。　　操作結(jié)果：重載*。<b&g

21、t;　　}　　第四章詳細(xì)設(shè)計　　類定義。polynomial.h　　#ifndef POLYNOMIAL_H_INCLUDED　　#define POLYNOMIAL_H_INCLUDED

22、　　template <typename T>　　struct Node {　　T coef; //定義系數(shù)　　T expn; //定義指數(shù)　　Node *next;　　}; //定義

23、結(jié)構(gòu)體　　template <typename T> //模板類　　class LinkList{　　private:　　Node<T> *head; //定義頭結(jié)點

24、　　public:　　LinkList(); //初始化鏈表　　void InitLink(int len); //建立鏈表　　void Sparsity(int len); //是否稀疏

25、　　void Display(); //顯示　　void Merge(); //合并指數(shù)相同的項　　void SelectSort(); //選擇排序　　void Negative(); //取負(fù)<p&g

26、t;　　void DelZero(); //刪除系數(shù)為0的項　　LinkList<T> operator + (LinkList<T> &b); //重載+　　LinkList<T> operator * (LinkList<T> &b); //重載*</p

27、>　　};　　#endif // POLYNOMIAL_H_INCLUDED　　成員函數(shù)。polynomial.cpp　　#include<iostream>　　#include"po

28、lynomial.h"　　using namespace std;　　template <typename T>　　LinkList<T>::LinkList(){　　head=new Node<T>;

29、　　head->next=NULL;　　}//初始化　　template <typename T>　　void LinkList<T>::InitLink(int len){　　Node

30、<T> *p, *q;　　q=head;　　cout << "系數(shù) 指數(shù)：" << endl;　　while(len--){　　p=new Node<T>;<

31、/p>　　cin >> p->coef >> p->expn;　　p->next=NULL;　　q->next=p;　　q=p;　　}<

32、;/b>　　}//建立多項式　　template <typename T>　　void LinkList<T>::Display(){　　DelZero();

33、Node<T> *q;　　q=head->next;　　if (!q){ //空鏈表輸出0　　cout << "0" << endl;　　return ;&l

34、t;/p>　　}　　if (q->coef){　　if (q->coef == 1){　　if (q->expn == 0){　　cout << q->coef;<

35、/p>　　}　　else if(q->expn == 1){　　cout << "x";　　}　　else{&l

36、t;/b>　　cout << "x^" << "(" << q->expn << ")";　　}　　}</p&g

37、t;　　else if (q->coef == -1){　　if (q->expn == 0){　　cout << q->coef;　　}　　else if(q->expn =

38、= 1){　　cout << "-x";　　}　　else{　　cout << "-x^" << "(&quo

39、t; << q->expn << ")";　　}　　}　　else{　　if (q->expn ==

40、0){　　cout << q->coef;　　}　　else if(q->expn == 1){　　cout << q->coef << "x";</p&

41、gt;　　}　　else{　　cout << q->coef << "x^" << "(" << q->expn << ")"

42、;　　}　　}　　}　　q=q->next;　　while(q){<

43、;/p>　　if (q->coef){　　if (q->coef > 0){　　if (q->coef == 1){　　if (q->expn == 0){　　cout << "+"

44、;　　}　　else if (q->expn == 1){　　cout << "+x";　　}

45、else{　　cout << "+x^" << "(" << q->expn << ")";　　}　　}

46、　　else{　　if (q->expn == 0){　　cout << "+" << q->coef;　　}<

47、;p>　　else if(q->expn == 1){　　cout << "+" << q->coef << "x";　　}　　else{<

48、;/p>　　cout << "+" << q->coef << "x^" << "(" << q->expn << ")";　　}<p&g

49、t;　　}　　}　　else{　　if (q->coef == -1){　　if (q->expn == 0){<p

50、>　　cout << q->coef;　　}　　else if (q->expn == 1){　　cout << "-x";　　}&l

51、t;/p>　　else{　　cout << "-x^" << "(" << q->expn << ")";　　}&

52、lt;p>　　}　　else{　　if (q->expn == 0){　　cout << q->coef;　　}</p&g

53、t;　　else if(q->expn == 1){　　cout << q->coef << "x";　　}　　else{<p&g

54、t;　　cout << q->coef << "x^" << "(" << q->expn << ")";　　}　　}<

55、;p>　　}　　}　　q=q->next;　　}　　cout << endl;<b&g

56、t;　　}//輸出多項式　　template <typename T>　　void LinkList<T>::Sparsity(int len){　　if (head->next == NULL){　　cout <&

57、lt; "0" << endl;　　cout << "不稀疏！" << endl;　　return ;　　}　　Node

58、<T> *p, *q;　　q=head;　　p=head->next;　　while(q->next){　　q=q->next;　　}</

59、b>　　double x=1.0*len/(q->expn-p->expn);　　Display();　　if (x <= 0.05)　　cout << "稀疏！" << endl;

60、　　else　　cout << "不稀疏！" << endl;　　}//判斷是否稀疏　　template <typename T><

61、p>　　void LinkList<T>::Merge(){　　Node<T> *p, *q, *t;　　for (q=head->next; q; q=q->next){　　for (p=q->next; p && p->expn == q-

62、>expn; ){　　q->coef+=p->coef;　　q->next=p->next;　　t=p;　　p=p->next;　　fre

63、e(t);　　}　　}　　}//合并指數(shù)相同的項　　template <typename T>　　void LinkLis

64、t<T>::SelectSort(){　　Node<T> *p, *q;　　for (q=head->next; q; q=q->next){　　for (p=q->next; p; p=p->next){　　if (q-&

65、gt;expn > p->expn){　　swap(q->coef,p->coef);　　swap(q->expn,p->expn);　　}　　}</p&

66、gt;　　}　　Merge();　　}//選擇排序升冪　　template <typename T>　　void LinkList<T>::Neg

67、ative(){　　Node<T> *p;　　p=head->next;　　while(p){　　p->coef=0-p->coef;　　p=p->next

68、;　　}　　}//取負(fù)　　template <typename T>　　void LinkList<T>::DelZero(){

69、　Node<T> *p, *q, *t;　　p=head->next;　　q=head;　　while(p){　　if (p->coef == 0){

70、　　q->next=p->next;　　t=p;　　p=p->next;　　free(t);　　}

71、　　else{　　q=p;　　p=p->next;　　}　　}<

72、p>　　}//刪除系數(shù)為0的項　　template <typename T>　　LinkList<T> LinkList<T>::operator+ (LinkList<T> &b){　　LinkList<T> m;

73、　　Node<T> *q, *p;　　Node<T> *pa, *pb;　　pa=head->next;　　pb=b.head->next;　　q=m.head;

74、;　　while(pa && pb){　　T x=pa->expn - pb->expn;　　if (x < 0){　　p=new Node<T>;　　p->coef=pa->coef;<

75、;/p>　　p->expn=pa->expn;　　p->next=NULL;　　q->next=p;　　q=p;　　pa=pa->next;<p&

76、gt;　　}　　else if(x > 0){　　p=new Node<T>;　　p->coef=pb->coef;　　p->expn=pb->expn;<p&g

77、t;　　p->next=NULL;　　q->next=p;　　q=p;　　pb=pb->next;　　}　　else

78、{　　T coef=pa->coef+pb->coef;　　if (coef){　　p=new Node<T>;　　p->coef=coef;　　p->expn=pa->

79、;expn;　　p->next=NULL;　　q->next=p;　　q=p;　　pa=pa->next;　　pb=pb->next;<p

80、>　　}　　else{　　pa=pa->next;　　pb=pb->next;　　}<b&g

81、t;　　}　　}　　while(pa){　　p=new Node<T>;　　p->coef=pa->coef;　　p->expn=pa->

82、;expn;　　p->next=NULL;　　q->next=p;　　q=p;　　pa=pa->next;　　}

83、　　while(pb){　　p=new Node<T>;　　p->coef=pb->coef;　　p->expn=pb->expn;　　p->next=NULL;　　q-

84、>next=p;　　q=p;　　pb=pb->next;　　}　　return m;

85、　}//重載+　　template <typename T>　　LinkList<T> LinkList<T>::operator* (LinkList<T> &b){　　LinkList<T> m;&

86、lt;p>　　Node<T> *q, *p;　　Node<T> *pa, *pb;　　q=m.head;　　for (pa=head->next; pa; pa=pa->next){　　for

87、 (pb=b.head->next; pb; pb=pb->next){　　p=new Node<T>;　　p->coef=pa->coef*pb->coef;　　p->expn=pa->expn+pb->expn;<p&g

88、t;　　p->next=NULL;　　q->next=p;　　q=p;　　}　　}

89、return m;　　}//重載*　　void menu(){　　for (int i=0; i<80; i++)　　cout << "*";<p

90、>　　cout << endl;　　cout << "1.建立多項式\t\t2.輸出多項式\t\t3.多項式相加" << endl;　　cout << "4.多項式相減\t\t5.多項式相乘\t\t0.退出系統(tǒng)" << endl;

91、　　for (i=0; i<80; i++)　　cout << "*";　　cout << endl;　　cout << "請選擇：";　　}<

92、/b>　　主函數(shù)。main.c　　#include <iostream>　　#include <string>　　#include <cmath>　　#include <cstdli

93、b>　　#include <fstream>　　#include "polynomial.cpp"　　using namespace std;　　int main(){　　//freopen(

94、"data1.in", "r", stdin); //輸入重定向　　//freopen("data1.out", "w", stdout); //輸出重定向　　LinkList <double> a, b, m1, m2, m3;

95、;　　int n, flag;　　int ALen, BLen;　　menu();　　while(cin >> n, n)　　{<p

96、>　　system("cls");　　switch(n)　　{　　case 0: {　　cout << "歡迎

97、下次使用！" << endl;　　exit(0);　　}　　case 1:{　　flag=0;&l

98、t;/p>　　cout << "請輸入第一個一元多項式的長度：";　　cin >> ALen;　　a.InitLink(ALen); //建立一元多項式　　a.SelectSort(); //升冪排序

99、　　cout << "請輸入第二個一元多項式的長度：";　　cin >> BLen;　　b.InitLink(BLen); //建立一元多項式　　b.SelectSort(); //升序排序</p&

100、gt;　　break;　　}　　case 2:{　　cout << "a=";　　a.Sparsity(

101、ALen); //判斷是否稀疏　　cout << "b=";　　b.Sparsity(BLen); //判斷是否稀疏　　break;　　}&

102、lt;/p>　　case 3:{　　m1=a+b;　　m1.SelectSort();　　cout << "a+b=";　　m1.Dis

103、play(); //輸出a+b　　break;　　}　　case 4:{　　if (flag == 0){　　b

104、.Negative(); //對b取負(fù)　　flag=1;　　}　　m2=a+b;　　m2.SelectSort();<p&g

105、t;　　cout << "a-b=";　　m2.Display(); //輸出a-b　　break;　　}　　case 5:{</b&g

106、t;　　if (flag == 1){　　b.Negative(); //b取負(fù)　　flag=0;　　}　　m3=a*b;</

107、b>　　m3.SelectSort();　　cout << "a*b=";　　m3.Display(); //輸出a*b　　break;<b&g

108、t;　　}　　default:　　cout << "輸入錯誤，請重新輸入！" <<endl;　　}　　menu()

109、;　　}　　return 0;　　}　　第五章運行與測試

110、　　程序開始界面。　　選擇 1，分別輸入兩個一元多項式　　選擇2，輸出兩個一元多項式　　分別選擇3、4、5　　輸入0結(jié)束程序<p

111、>　　總結(jié)與心得　　這次課程設(shè)計使本學(xué)期所學(xué)的數(shù)據(jù)結(jié)構(gòu)知識得到了鞏固和應(yīng)用，并且對C++也有了更進(jìn)一步的了解。雖然在設(shè)計過程中遇到了一些困難，但感覺收獲還是挺多的，自己擴(kuò)充了很多知識點。通過這周的課程設(shè)計，我意識到好的學(xué)習(xí)方法的重要性，在學(xué)習(xí)中要學(xué)會主動，學(xué)會自學(xué)，不要什么東西都指望別人，要靠自己去細(xì)心觀察，多問自己一個為什么，多動手查查、看看，不會的

112、問題，抬頭是google，這樣自己學(xué)到手的東西才會更多！　　參考文獻(xiàn):　　[1] 嚴(yán)蔚敏、吳偉民主編《數(shù)據(jù)結(jié)構(gòu)》（C語言版）清華大學(xué)出版社 2002　　[2] 殷人昆等著《數(shù)據(jù)結(jié)構(gòu)》（C++版）清華大學(xué)出版社 2001<

113、/p>　　[3] 金遠(yuǎn)平著《數(shù)據(jù)結(jié)構(gòu)》（C++描述）清華大學(xué)出版社 2005 　　[4] 許卓群等著《數(shù)據(jù)結(jié)構(gòu)與算法》高等教育出版社 2004　　[5] Frank M.Carrano 等著《數(shù)據(jù)結(jié)構(gòu)與Ｃ++高級教程》清華大學(xué)出版社 2004<

眾賞文庫> 全部分類> 畢業(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)方式做保護(hù)處理，對用戶上傳分享的文檔內(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è)計報告-一元多項式加減運算

文檔簡介

溫馨提示

最新文檔

評論

免費下載