軟件課設實驗報告

1、北京信息科技大學計算機軟件基礎課程設計題 目： 鏈表多項式運算 學 院： 信息與通信工程學院 專 業(yè)： 通信工程專業(yè) 學生姓名： 班級/學號 指導老師： 起止時間： 2015年10月至 2015年11月 5日 源代碼任務書題目4鏈表多項式運算主要內容1、 掌握多項式鏈式存儲結構及運算方法，例如插入、刪除、創(chuàng)建等，完成一元多項式加法和乘法運算。2、 根據多項式求和、求積原理，實現(xiàn)多項式的建立、求和、求積、顯示、釋放，插入排序等功能。例如：輸入：5x3+1.2x+4.5x2; -1.2x+1加法結果：14.5x2+5x3;乘法結果：1.2x+3.06x2-0.4x3-6x43、 學會編寫DLL函數

2、。4、 掌握C+編程環(huán)境的基本調試方法，熟練使用可視化C+編程工具。設計要求1、 上交課程設計的書面材料，要求打印。包括課程設計任務書、主要內容，源程序，對程序的功能進行客觀評價，明確指出自己編寫了哪些具體函數。2、 上交電子版源程序，包括多項式求和、求積、插入、刪除、鏈表創(chuàng)建、排序等程序。3、自己編寫一個求素數函數，把它書寫成一個動態(tài)鏈接庫形式，并在主函數中調用它。嘗試把自己編寫的程序寫成動態(tài)鏈接庫和靜態(tài)鏈接庫形式（無需上交），并比較以下三種EXE文件的大小。A：調用靜態(tài)鏈接庫生成的EXE執(zhí)行文件。B：調用動態(tài)鏈接庫生成的EXE執(zhí)行文件。C：直接調用函數生成的EXE執(zhí)行文件。主要儀器設備計算

3、機一臺，安裝Windows XP 操作系統(tǒng)、Microsoft Visual C+ 6.0、MSDN Library。主要參考文獻1 侯俊杰. 深入淺出MFC(第二版)M. 武漢：華中科技大學出版社, 2001.2 譚浩強. C程序設計（第二版）M. 北京：清華大學出版社, 1999.3 孟彩霞. 計算機軟件基礎M. 陜西：西安電子科技大學出版社, 2003.4 嚴蔚敏, 吳偉民. 數據結構M. 北京：清華大學出版社, 2005.課程設計進度計劃（起止時間、工作內容）4 學時 了解課題背景，選題，學習DLL，學習鏈表的基本概念。4 學時 編寫求和程序。4 學時 編寫求積程序。4 學時 完善功能

4、，編寫排序程序。4 學時 調試程序，答辯。課程設計開始日期第2周周一課程設計完成日期第2周周五課程設計實驗室名稱計算中心機房地 點健翔橋校區(qū)摘要： 用C語言實現(xiàn)一元多項式的運算.利用鏈表實現(xiàn)一元多項式運算的存儲，該程序具有加法、乘法基本運算功能。程序的各個功能模塊全部用函數的形式實現(xiàn)。 關鍵字：多項式 運算 函數 鏈表內容：1、 根據多項式求和、求積原理以及程序框架，分別編寫函數createpoly,polyadd,polymulti,Clearlist,InserNode,實現(xiàn)多項式的建立、求和、求積、顯示、釋放、插入排序等功能。2、 比較多項式相加運算與歸并兩個有序表的異同3、 Inser

5、Node函數的功能是什么？ 目錄 一 概述4二 總體方案設計4三 詳細設計6四 程序的調試與運行結果說明12五 課程設計總結13參考文獻14附錄：程序源代碼14一 概述1. 課程設計的目的掌握多項式鏈式存儲結構及運算方法，例如插入、刪除、創(chuàng)建等，完成一元多項式加法和乘法運算。2. 課程設計的要求1用C語言實現(xiàn)一元多項式的運算.2利用鏈表實現(xiàn)一元多項式運算的存儲.3該程序具有加法、減法、乘法基本運算功能.4. 程序的各個功能模塊要求用函數的形式實現(xiàn).5. 完成設計任務并書寫課程設計報告。二 總體方案設計1程序設計對多項式存儲的解釋與說明：多項式，顧名思義是含有多個單項式的，所以很容易讓程序員聯(lián)想

6、到的是鏈式單鏈表，因為鏈式的單鏈表比順序的操作靈活，鏈式的便于插入和刪除。我對多項式的存儲思考了很多常見的輸入錯誤，必須要對輸入的每個單項式進行校驗，符合條件的就存入，反之就刪除并提示重新輸入，所以我的程序中也是選擇鏈式單鏈表來存儲多項式的，這樣就給我程序后期的算法設計帶來了很多的好處。頭結點coef（0）expn（-1）next如上頭結點，是采用的結構體形式，其中大的方面分為兩個域，分別為data域和next域，其中data域又是一個嵌套的結構體，里面又分為coef 和expn兩個域，而next域是指向下一個結點的指針域。初始化頭結點時，我將coef 和expn賦初值為 0 和 -1，因為頭

7、結點在整個算法中都沒有參與計算，只是起到一個連接的作用，而其指數域expn為 -1 是起標志性的作用。整體設計思路：模仿DOS界面，用命令行來操控整個程序的運行；算法的整體思路：先寫命令行函數，然后將一元多項式運算的函數插入到命令行函數中，以達到函數調用的目的；主要特點：可以實現(xiàn)一元多項式的DOS界面命令操控；具體功能：用命令調用函數，以實現(xiàn)一元多項式的存儲、相加、相乘的功能，還有顯示、銷毀等命令。2.主要問題解決我的設計是實現(xiàn)一元多項式的存儲、相加、相乘的功能，而我就想到了模仿DOS界面命令形式，采用命令操作來實現(xiàn)本次課程設計的要求。3.程序的主要模塊如上1、2所提到的，我采用的是模仿DOS

8、命令界面來實現(xiàn)多項式的存儲以及其相加、相乘等功能。所以我設計的程序模塊主要有兩大模塊，其分別為命令行調用模塊和一元多項式的存儲、運算模塊。3.1命令行調用模塊在此模塊中，我也使用了結構體來存儲相關命令，但這里采用的是順序的鏈表，因為在使用命令行函數的時候會有指針偏移尋找相關命令的函數指針，所以用順序有利益控制循環(huán)使用。命令行的節(jié)點形式，pCmdName為命令名，pCmdInfo為命令的功能說明，pFun是自定義的一個函數指針內型，也就是存儲相關命令的函數指針。*pCmdName*pCmdInfo;pFun命令行順序表g_CmdInfo然后就寫了一個命令行輸入函數CmdProc，在此函數里面用w

9、hile循環(huán)來輸入相關的命令，用庫函數strcmp來核對輸入的命令，以達到調用相關命令函數的效果。而相關命令函數里面就調用下面模塊中的相關函數。3.2一元多項式的存儲、運算模塊在此模塊中，我使用的鏈式單鏈表來存儲多項式的，相關的介紹看上面的 1.程序設計 中的詳細說明。 此模塊主要的幾大功能函數為createLink創(chuàng)建鏈表，printList輸出鏈表，addPolyn相加函數，substractPolyn相減函數，mulPolyn相乘函數。還有相關的輔助函數copyLink復制多項式函數，locateLink核對單項式函數，destroyLink銷毀結點函數。copyLinklocateLi

10、nkdestroyLinkcreateLinkprintListaddPolynsubstractPolynmulPolyn相關的主要函數和輔助函數之間的聯(lián)系如上所示。 三 詳細設計1.一元多項式運算函數設計1.1創(chuàng)建多項式的過程編寫此過程中，我采用了鏈式單鏈表的形式，固然最后一個區(qū)域是指針next域，其中多項式結點中data域里又嵌套了一個結構體，即將data域劃分為系數coef和指數expn兩個區(qū)域。 頭結點coef（0）expn（-1）next15 2next 23 5next 17 8NULL這是創(chuàng)建多項式的過程，此多項式為15*x2+23x23+17x8 ，當然了在創(chuàng)建多項式的過程中

11、還有更為細密的校驗，如：（在輸入的過程中）1.指數為負校驗：2.系數為 0 的校驗：3.輸入指數相同的校驗：黑體函數locateLink是一個判斷指數是否與多項式中已存在的某項相同。補充： 在校驗3之前必須將每次輸入的單項式按從小到大的順序排列，這也為locateLink和下面的相加、相減函數做了簡單的鋪墊。我采用的遍歷發(fā)找到每次輸入的單項式應在的位置，然后插入。 1.2 多項式輸出實現(xiàn)過程在輸出之前必須對傳入參數指針進行校驗：本來一開始我想的是從多項式的第一個結點一次輸出，這樣很簡單啊，可是我發(fā)現(xiàn)這樣的通用性很差，所以我就想到了先將第一個結點分開輸出，然后再依次用循環(huán)輸出其它結點，這樣就大大

12、地提高了此函數的通用效果。同時在輸出各結點時，我還對系數、指數進行了討論，（系數不可能為0）以多項式的第一項系數大于0的情況輸出為例，如下：如果指數為0時，只輸出系數如果系數和指數都為1時就不用輸出1，只輸出x如果系數或指數其中一個為1的時候，也不用輸出1，其它的照原樣輸出： 1.3多項式相加過程在兩個多項式相加對其進行了保護，將兩個多項式分別復制給了另外兩個多項式中。同樣也對兩個多項式進行了校驗： 如果校驗正確，則進行相加，如下：1. 兩個多項式沒有指數相同時，算法中結點的變化如下：（“蛇形連接”的尾是“和”的next域，而頭就從在“加數”和“被加數”中尋找指數小的項，然后通過指針偏移連接。

13、）2. 兩個多項式中如果有指數相同的的項，則先相加存到其中一個多項式， 然后再用上面1的“蛇形連接”的方法連接，不過唯一要注意的就是要將指數相同的項中未被累加存儲的那項給跳過，不用連接。3. 但是在指數相同的項相加時還要注意一點，那就核對相加的結果，即對存到其中一個多項式中的項的系數，必須進行非0 的校驗。因為兩種情況的結點連接方式不同：當然了如果校驗不正確，則有： 補充：黑體函數destroyLink是銷毀單鏈表的函數，是為了釋放內存空間的：具體的函數代碼如下： 同時destroyLink函數也是命令行DesPolyn調用的主要函數。1.5多項式相乘過程 由于相乘過程中只需用其中一個多項式的

14、每一項依次去乘另一個多項式的每一項，依次形成多項式，并累加到同一個多項式中，這樣最后得到了所要的結果了，并及時銷毀臨時的多項式：2.模仿DOS命令行設計命令行函數中定義的是順序單鏈表，第一個域為字符串指針（命令名），第二個域也是字符串指針域（命令功能），第三個域為函數指針域（命令函數）。"create""創(chuàng)建多項式"create"display""顯示多項式"display"add""多項式相加"add"cheng""多項式相乘"che

15、ng/*命令行函數*/void CmdProc(const char *pTitle);int create();int display();int add();int cheng();CMDINFO shuzu = "create", "創(chuàng)建多項式", create,"display", "顯示多項式", display,"add", "多項式相加", add,"cheng", "多項式相乘", cheng,;int g_nCmdSi

16、ze = sizeof(shuzu) / sizeof(CMDINFO);Link La = NULL, Lb = NULL;int main()CmdProc("多項式");void CmdProc(const char *pTitle) /Dos界面命令行函數char szCmdBuf50 = ""int i = 0;while (true)cout << ">"cin >> szCmdBuf;for (i = 0; i < g_nCmdSize; i+)if (!strcmp(szCmdBuf

17、, shuzui.pCmdName)shuzui.pFun();break;用函數指針執(zhí)行了對應的函數，隨后寫了個調用命令的函數CmdProc，在這里面進行循環(huán)輸入命令字符串，然后用strcmp比較輸入的字符串與命令名，如果相同則調用相應函數指針所指向的函數。 四 程序的調試與運行結果說明1.程序的源代碼：（見附錄）2. 程序的調試與運行結果說明：運行結果:3時間復雜度分析：在createPolyn創(chuàng)建多項式的函數中，用了個while對多項式進行指數由小到大的排序，是為后面的相加函數做鋪墊。時間復雜度為O(n) 。由于addPolyn函數中采用的是“蛇形連接”，所以其時間復雜度為O(m+n)。

18、由于mulPolyn函數中采用的是用其中一個多項式中每一項依次去乘另一個多項式，所以時間復雜度為O(n*m)。其它的輔助函數，如：輸出多項式函數printList、復制多項式函數copyLink、校驗輸入單項式有沒有指數相同的函數locateLink 的時間復雜度都為O(n)。五 課程設計總結1.程序總結：通過這個的課程設計，我進一步的鞏固了鏈式單鏈表的使用，以及寫命令行的大致步驟。而且我已掌握一元多項式所要求的基本算法。我的程序代碼完全符合這次的課程要求，我通過模仿DOS命令行的形式來實現(xiàn)一元多項式的具體功能，其中的命令基本上很完善，初步的展現(xiàn)了我對命令行的理解與使用。在一元多項式的算法實現(xiàn)

19、中，也幾乎是盡善盡美的，由于整個過程是采用的鏈式單鏈表，所以全部輸入和輸出的過程都有指針或者是數據的校驗內容，這樣就更加增強了代碼的可行性。2.程序進一步設想：我的程序代碼滿足了這次課程設計的要求，但我想我還沒有做到最完美的，因為在一元多項式的運算中應該是有減法和除法的，所以這樣就有問題了，那我的程序里面還應該加上指數為負數的操作，也就是除法的間接性實現(xiàn)的步驟。對于一元多項式的除法以及指數為負的運算提出假設：我想應該可以寫個一元多項式相除的函數，是乘法函數的逆過程，只不過要在相除之前先確定兩者之間的關系是能夠除得盡的，不然這樣就很麻煩了。3. 對數據結構課程的思考：通過這次課程，我更深入的了解

20、到數據結構這門課程對于程序員來說很重要，因為程序的兩大組成成員之一就是數據結構。程序的核心是算法，同時程序的實現(xiàn)也要靠數據結構，所以數據結構也是程序的主要成員，所以說學好數據結構是必須的。參考文獻1 譚浩強，C程序設計題解與上機指導（第二版），北京，清華大學出版社，2000年9月。2 嚴蔚敏 吳偉民 ，數據結構（C語言版），北京，清華大學出版社，2007年3 美 James P.Cohoon ，Jack W.Davidson 著，劉瑞挺 韓毅剛 盛素英 劉海嘉 等譯 ， C+ 程序設計（第三版），北京，電子工業(yè)出版社，2002年1月4 繆淮扣 顧訓穰 沈俊 ，數據結構(C+實現(xiàn)) ，北京，科學

21、出版社，2001年附錄：程序源代碼#include <iostream>using namespace std;#include <stdlib.h>#include <string.h>#include "stdio.h"typedef structfloat coef;/結點類型int expn;polynomial;typedef struct LNodepolynomial data;/鏈表類型struct LNode *next;LNode, *Link;typedef int(*PFUN)();struct CMDINFOco

22、nst char *pCmdName;const char *pCmdInfo;PFUN pFun;/*調用的函數*/void createLink(Link &L, int n);void printList(Link L);void addPolyn(Link &pc, Link pa, Link pb);void mulPolyn(Link &pc, Link pa, Link pb);void copyLink(Link &pc, Link pa);int locateLink(Link pa, Link e);void destroyLink(Link

23、 &L);/*命令行函數*/void CmdProc(const char *pTitle);int create();int display();int add();int cheng();CMDINFO shuzu = "create", "創(chuàng)建多項式", create,"display", "顯示多項式", display,"add", "多項式相加", add,"cheng", "多項式相乘", cheng,;int g

24、_nCmdSize = sizeof(shuzu) / sizeof(CMDINFO);Link La = NULL, Lb = NULL;int main()CmdProc("多項式");void CmdProc(const char *pTitle) /Dos界面命令行函數char szCmdBuf50 = ""int i = 0;while (true)cout << ">"cin >> szCmdBuf;for (i = 0; i < g_nCmdSize; i+)if (!strcmp(s

25、zCmdBuf, shuzui.pCmdName)shuzui.pFun();break;int create() /創(chuàng)建多項式int n;cout << "請輸入你要運算的第一個一元多項式的項數: "cin >> n;createLink(La, n);cout << "請輸入你要運算的第二個一元多項式的項數: "cin >> n;createLink(Lb, n);return 0;int display() /顯示多項式if (La = NULL | Lb = NULL) /多項式校驗cout <

26、;< "您還未創(chuàng)建多項式，請先創(chuàng)建!" << endl;return 0;cout << "第一個一元多項式為：" << endl;printList(La);cout << "第二個一元多項式為：" << endl;printList(Lb);return 0;int add() /多項式相加Link L;if (La = NULL | Lb = NULL) /多項式校驗cout << "您還未創(chuàng)建多項式，請先創(chuàng)建!" <<

27、 endl;return 0;addPolyn(L, La, Lb);cout << "兩個多項式相加后的結果為：" << endl;printList(L);destroyLink(L);return 0;int cheng() /多項式相乘Link L;if (La = NULL | Lb = NULL) /多項式校驗cout << "您還未創(chuàng)建多項式，請先創(chuàng)建!" << endl;return 0;mulPolyn(L, La, Lb);cout << "兩個多項式相乘后的結果為

28、：" << endl;printList(L);destroyLink(L);return 0;void destroyLink(Link &L) /清空鏈表Link p;p = L->next;while (p)L->next = p->next;delete p;p = L->next;delete L;L = NULL;/*判斷指數是否與多項式中已存在的某項相同*/int locateLink(Link L, Link e)Link p;p = L->next;while (p != NULL && (e->

29、;data.expn != p->data.expn)p = p->next;if (p = NULL)return 0;elsereturn 1;void createLink(Link &L, int n) /創(chuàng)建鏈表Link p, newp;L = new LNode;L->next = NULL;(L->data).expn = -1;/創(chuàng)建頭結點p = L;for (int i = 1; i <= n; i+)newp = new LNode;cout << "請輸入第" << i << &

30、quot;項的系數和指數:" << endl;cin >> (newp->data).coef >> (newp->data).expn;if (newp->data.expn < 0) /指數校驗cout << "您輸入有誤，指數不允許為負值!" << endl;delete newp;i-;continue;newp->next = NULL;p = L;if (newp->data.coef = 0) /系數校驗cout << "系數為零，重

31、新輸入!" << endl;delete newp;i-;continue;newp->next = NULL;p = L;while (p->next != NULL) && (p->next->data).expn < (newp->data).expn) /指數排序p = p->next;if (!locateLink(L, newp)newp->next = p->next;p->next = newp;elsecout << "輸入的該項指數與多項式中已存在的某項相

32、同,請重新創(chuàng)建一個正確的多項式" << endl;delete newp;destroyLink(L);createLink(L, n);break;/*輸出鏈表*/void printList(Link L)Link p;if (L = NULL | L->next = NULL) /校驗cout << "該一元多項式為空 !"elsep = L->next; /跳過頭結點if (p->data).coef > 0)if (p->data).expn = 0)cout << (p->data

33、).coef;elseif (p->data).coef = 1 && (p->data).expn = 1)cout << "x"elseif (p->data).coef = 1 && (p->data).expn != 1)cout << "x" << (p->data).expn;elseif (p->data).expn = 1 && (p->data).coef != 1)cout << (p->da

34、ta).coef << "x"elsecout << (p->data).coef << "x" << (p->data).expn;if (p->data).coef < 0)if (p->data).expn = 0)cout << (p->data).coef;elseif (p->data.coef = -1 && p->data.expn = 1)cout << "-x"elseif (p-

35、>data.coef = -1 && p->data.expn != 1)cout << "-x" << p->data.expn;elseif (p->data.expn = 1)cout << p->data.coef << "x"elsecout << (p->data).coef << "x" << (p->data).expn;p = p->next;while (p != NU

36、LL)if (p->data).coef > 0)if (p->data).expn = 0)cout << "+" << (p->data).coef;elseif (p->data).expn = 1 && (p->data).coef != 1)cout << "+" << (p->data).coef << "x"elseif (p->data).expn = 1 && (p->da

37、ta).coef = 1)cout << "+x"elseif (p->data).coef = 1 && (p->data).expn != 1)cout << "+x" << (p->data).expn;elsecout << "+" << (p->data).coef << "x" << (p->data).expn;if (p->data).coef < 0)if

38、(p->data).expn = 0)cout << (p->data).coef;elseif (p->data.coef = -1 && p->data.expn = 1)cout << "-x"elseif (p->data.coef = -1 && p->data.expn != 1)cout << "-x" << p->data.expn;elseif (p->data.expn = 1)cout << p

39、->data.coef << "x"elsecout << (p->data).coef << "x" << (p->data).expn;p = p->next;cout << endl;/*把一個鏈表的內容復制給另一個鏈表*/void copyLink(Link &pc, Link pa)Link p, q, r;pc = new LNode;pc->next = NULL;r = pc;p = pa;while (p->next != NULL)q = new LNode;q->data.coef = p->next->data.coef; /跳過頭結點q->data.expn = p->next->data.expn;r->next = q;q->next = NULL;r = q;p = p->next;/*將兩