重慶大學本科學生課程設計任務書——長整數(shù)運算

《重慶大學本科學生課程設計任務書——長整數(shù)運算》由會員分享，可在線閱讀，更多相關《重慶大學本科學生課程設計任務書——長整數(shù)運算（17頁珍藏版）》請在裝配圖網(wǎng)上搜索。

數(shù)據(jù)結構課程設計 方案設計重慶大學本科學生課程設計任務書課程設計題目 長整數(shù)運算學院 軟件學院 專業(yè) 軟件工程 年級 16 級已知參數(shù)和設計要求：[問題描述]設計一個程序?qū)崿F(xiàn)兩個任意長的整數(shù)求和運算。學生應完成的工作：[基本要求]利用雙項循環(huán)鏈表實現(xiàn)長整數(shù)的存儲，每個結點含一個整型變量。任何整型變量的范圍是- （2 15-1）~（2 15-1） 。輸入和輸出形式：按中國對于長整數(shù)的表示習慣，每四位一組，組間用逗號隔開。[測試數(shù)據(jù)]（1） 0；0；應輸出“0” 。（2） -2345,6789；-7654,3211；應輸出“-1,0000,0000” 。（3） -9999,9999；1,0000,0000,0000 ；應輸出“9999,0000,0001” 。（4） 1,0001,000；-1,0001,0001 ；應輸出“0” 。（5） 1,0001,0001；-1,0001,0000 ；應輸出“1” 。目前資料收集情況（含指定參考資料）：1. Robert L. Kruse 編. Data Structures and Program Design in C++. 高等教育出版社，2001.2. 嚴蔚敏編. 數(shù)據(jù)結構. 清華大學出版社，2000.3. 李春葆編. 數(shù)據(jù)結構教程. 清華大學出版社，2002.4. Clifford A.Shaffer 著. 張銘，劉曉丹等譯. 數(shù)據(jù)結構與算法分析(第三版).電子工業(yè)出版社，2013.10.課程設計的工作計劃：第 1~4 天 完成方案設計與程序框圖 第 4~10 天 編寫程序代碼第 10~15 天 程序調(diào)試分析和結果第 15~20 天 課程設計報告和總結任務下達日期 2017 年 12 月 15 日完成日期 2018 年 1 月 12 日指導教師 文俊浩 （簽名） 學 生 陳勇 （簽名）說明：1、學院、專業(yè)、年級均填全稱，如：光電工程學院、測控技術、2003。2、本表除簽名外均可采用計算機打印。本表不夠，可另附頁，但應在頁腳添加頁碼。數(shù)據(jù)結構課程設計 方案設計1.方案設計1.1 問題描述利用雙項循環(huán)鏈表實現(xiàn)長整數(shù)的存儲，每個結點含一個整型變量。任何整型變量的范圍是- （ 215-1） ~（2 15-1） 。輸入和輸出形式：按中國對于長整數(shù)的表示習慣，每四位一組，組間用逗號隔開。1.2 需求分析核心問題：長整形數(shù)的進行拆分再加減數(shù)據(jù)模型（邏輯結構）：類似匯編的帶進位加法和帶進位減法存儲結構：循環(huán)鏈表，字符數(shù)組核心算法：字符數(shù)組提取數(shù)字，鏈表的加減輸入數(shù)據(jù)：兩個長整形數(shù)字輸出數(shù)據(jù)：加減結果通過以上分析，該程序具有可行性。1.3 運行環(huán)境硬件開發(fā)環(huán)境：PC 機軟件開發(fā)環(huán)境：VS2015操作系統(tǒng)環(huán)境 Window 1.4 概要設計整個設計的流程圖數(shù)據(jù)結構課程設計 方案設計主函數(shù)輸入數(shù)據(jù) 存入鏈表 判斷運算輸出運算圖 1.1數(shù)據(jù)結構課程設計 算法設計2.算法設計2.1 算法設計思想用兩個字符數(shù)組儲存輸入的字符串，再將字符串中的每個 4 位整數(shù)轉(zhuǎn)入成鏈表的關鍵節(jié)點分別儲存到兩個鏈表中，這樣就讓長整數(shù)分割開來，使得儲存成為現(xiàn)實，然后再分別把兩個鏈表的節(jié)點相加儲存到另一個鏈表中，用 flag 來判斷有無進位與借位，有進位flag 置為 1，無進位 flag 置為-1，最后將結果鏈表按照要求的格式輸出即可2.2 算法設計的對應方式如 1,1111,4444,5555,3334,0000,0001 與 1,0000,2321,9000,5555,0000 相加圖 2長整數(shù) 1 1111 4444 5555 3334 0000 0001長整數(shù) 1 0000 2321 9000 5555 0000flag 0 0 0 1(有進位)0 0 0相加1 1112 4444 7877 2334 5555 0001數(shù)據(jù)結構課程設計 詳細設計3.詳細設計3.1 設計思想用字符數(shù)組來存儲輸入的數(shù)，用循環(huán)鏈表的儲存整數(shù)的節(jié)點，以及計算的結果。用鏈表的好處可以節(jié)約空間，它可以隨著數(shù)據(jù)的長短來調(diào)整大小，同時，雙向循環(huán)鏈表也方便了查找和刪除。3.2 設計關鍵算法節(jié)點類：public:E element; // Value for this nodeLink* next; // Point to next node in listLink*prev; //Pointer to previous node// ConstructorsLink(const E& it, Link* prevp,Link*nextval){element = it; next = nextval;prev = prevp;}Link(Link*prevp = NULL,Link* nextval = NULL) { next = nextval; prev = prevp; }雙向循環(huán)鏈表類：template class DoubleLList {private:Link* head; // Pointer to list headerLink* tail; // Pointer to last elementLink* curr; // Access to current elementint cnt; // Size of listpublic:void init() { // Intialization helper methodcurr = tail = head = new Link(0,NULL,NULL);tail->next = head;head->prev = tail;數(shù)據(jù)結構課程設計 詳細設計cnt = 1;}void removeall() { // Return link nodes to free storewhile (head != tail) {curr = head;head = head->next;delete curr;}delete head;}//DoubleLList() { init(); } // ConstructorDoubleLList(const E&it) //constructor{curr = tail = head = new Link(it, NULL, NULL);tail->next = head;head->prev = tail;cnt = 0;}DoubleLList() //Constructor,make the head element with 0{curr = tail = head = new Link(0, NULL, NULL);head->next = head->prev = head;cnt = 1;}// Destructor~DoubleLList() {removeall(); }void clear() { removeall(); init(); } // Clear list// Insert "it" at current positionvoid insert(const E&it) {curr->next = curr->next->prev = new Link(it, curr, curr->next);if (tail == head){tail = curr->next;}cnt++;}數(shù)據(jù)結構課程設計 詳細設計void append(const E& it) { // Append "it" to listif (cnt == 1) //當節(jié)點為1的時候{head->next=head->prev=tail = new Link(it, head, head);}elsetail=head->prev = tail->next = new Link(it, tail, head);cnt++;}輸入：void input(char *a, char *b) //輸入字符串{cout > a;cout > b;}轉(zhuǎn)化：（將輸入的輸入轉(zhuǎn)化到鏈表中）//將儲存在字符串數(shù)組中的整數(shù)轉(zhuǎn)化到鏈表中void charTransformList(DoubleLList &L1, char a[]){int temp=0, r,count,flag=0 ; //temp用于存儲中間每個4位整數(shù)，r用于表示在4位整數(shù)的哪個位上,count用于表示a的字符串長度,flag=0表示整數(shù)，1表示負數(shù)count = strlen(a);if (a[0] == '-')flag = 1;for (int i = count - 1, j = 0; i >= 0+flag; i--, j++){int m = j / 5; //m用于記錄第幾個數(shù)r = j % 5;if (r == 4){continue;}else if (r!=4&&(a[i] '9')) { //當輸入格式錯誤的時候，退出cout strlen(b)&&a[0] == '-'&&b[0] != '-'))return -1;else if(a[0]=='-'&&b[0]!='-'&&strlen(a)-1==strlen(b)) //當兩整數(shù)長度相同，符號相反時{for (int i = 0; i b[i]) {return -1;break;}if (a[i+1] b[i + 1]) {return 1;break;}if (a[i] strlen(b) || a[0] != '-'&&strlen(a) > strlen(b) - 1) //當?shù)谝粋€整數(shù)絕對值長度大于第二個整數(shù)絕對值長度，返回truereturn 1;else if (a[0] == '-'&&strlen(a) - 1 b[i]) {return 1;break;}if (a[i + 1] b[i + 1]) {return 1;break;}if (a[i] &L1, DoubleLList&L2, DoubleLList&L3, char charArray1[100], char charArray2[100]){int flag = 0, temp; //保存是否有進位或則是借位，進位為1，未進位為0，借位為-1;temp用為暫時存儲鏈表相加的結果cout = 10000) //處理進位{flag = 1;temp = temp - 10000;}L3.append(temp);if ((i == (L1.length() - 2)) && flag == 1) //當最后有進位的時候L3.append(1);}}else if (L1.length() > L2.length()) //當L1的長度大于L2的長度{L1.moveToStart();L2.moveToStart();for (int i = 0; i = 10000){flag = 1;temp -= 10000;}L3.append(temp);if ((i == L1.length() - 2) && flag == 1) //當最后有進位的時候L3.append(1);}}else //當L2的長度大于L1的長度{L1.moveToStart();L2.moveToStart();for (int i = 0; i = 10000){flag = 1;temp -= 10000;}L3.append(temp);if ((i == L2.length() - 2) && flag == 1) //當最后有進位的時候L3.append(1);}}}else //當符號不相同時{if (aboluteValue(charArray1, charArray2) == 0) //如果兩個整數(shù)絕對值大小相等，結果為0L3.append(0);else if (aboluteValue(charArray1, charArray2) > 0) //如果第一個整數(shù)絕對值大于數(shù)據(jù)結構課程設計 詳細設計第二個整數(shù)的絕對值{L1.moveToStart();L2.moveToStart();for (int i = 0; i = L2.getValue()){temp = L1.getValue() - L2.getValue() + flag;flag = 0; //沒有借位}else{temp = L1.getValue() + 10000 - L2.getValue();flag = -1; //有借位}}else{if (L1.getValue() + flag >= 0){temp = L1.getValue() + flag;flag = 0; //沒有借位}else{temp = L1.getValue() + flag + 10000;flag = -1; //有借位}}L3.append(temp);}}//第二個整數(shù)大于第一個整數(shù)絕對值的時候else{L1.moveToStart();L2.moveToStart();for (int i = 0; i = L1.getValue()){temp = L2.getValue() - L1.getValue() + flag;flag = 0; //沒有借位}else{temp = L2.getValue()+flag + 10000 - L1.getValue();flag = -1; //有借位}}else //L1中整數(shù)遍歷完后，只剩下L2的整數(shù){if (L2.getValue() + flag >= 0){temp = L2.getValue() + flag;flag = 0; //沒有借位}else{temp = L2.getValue() + flag + 10000;flag = -1; //有借位}}L3.append(temp);}}}}輸出：void resultPrint(DoubleLListL3,int flag) //L3存儲了相加的結果，flag儲存了結果的正負,結果顯示到屏幕上{if(flag=1000){cout = 100){cout = 10){cout << "00" << L3.getValue();}else{cout << "000" << L3.getValue();}}cout << endl;}數(shù)據(jù)結構課程設計 調(diào)試分析4.調(diào)試分析_ 圖 6數(shù)據(jù)結構課程設計 參考文獻5.總結通過半個多月的學習和實踐，解決實際問題，讓我對鏈表有了更深的了解，對數(shù)據(jù)結構產(chǎn)生了濃厚的興趣，同時也讓我提高了解決實際問題的能力。我們要不斷的通過上機來提高自己的學習水平，在上機的同時改正了自己對某些算法的錯誤使用，使自己在通過程序解決問題時抓住關鍵算法，有了算法設計思想和流程圖，并用 C++語言描繪出關鍵算法。以前我對數(shù)據(jù)結構（C++語言描述）的一些標準庫函數(shù)不太了解，還有對函數(shù)調(diào)用的正確使用不夠熟悉，還有對 C 語言中經(jīng)常出現(xiàn)的錯誤也不了解，通過實踐，使我在這幾個方面的認識有所提高。讓自己有一定的能力去改正一些常見的錯誤語法，很高興這半個多月的學習讓我對數(shù)據(jù)結構（C++語言描述）有了新的認識，所以后在學習過程中，我會更加注視實踐操作，使自己便好地學好計算機。在這次課程設計的實驗中，我收獲了許多知識，通過查找大量資料，請教老師，以及不懈的努力，也培養(yǎng)了獨立思考、動手操作的能力。我也學會了許多學習和解決實際問題的方法，讓我受益匪淺。時間的緊缺成為一個很大的問題。也希望老師可以為我們知道一下以后的發(fā)展方向。如果可以讓每個人都有動手焊接以及參與其他的各個流程，有專門的知道就更好了。課程設計對我來說，趣味性強，不僅鍛煉能力，而且可以學到很多東西，在與老師和同學的交流過程中，互動學習，將知識融會貫通，也增強了我和同學之間的團隊合作的能力。讓我們知道只要努力，集中精力解決問題，一定會有收獲的，過程也是很重要的。在這次課程設計中我們要學會利用時間，在規(guī)定的時間內(nèi)完成我們的任務，要逐漸養(yǎng)成用 C++語言編寫程序的良好習慣。這些對我來說都是一種鍛煉，一個知識積累的過程，一種能力的提高。要打好基礎，才能用更好的辦法，更簡潔明了的程序解決實際問題，只有這樣才能進一步的取得更好的成績。我們會更加努力，努力的去彌補自己的缺點，發(fā)展自己的優(yōu)點，去充實自己，只有在了解了自己的長短之后，我們會更加珍惜擁有的，更加努力的去完善它，增進它。參考文獻《數(shù)據(jù)結構與算法分析第三版》 （C++）數(shù)據(jù)結構課程設計 參考文獻17