1、 目：長整數的加法運算 題 院：計算機科學與工程學院 學 業：信息安全專 姓名：農錦文 1200360220 號： 學 指導教師：張瑞霞 日 10 年月 182014 1 2 目 錄 引言 . 4 1、 系統概述 . 4 2、 系統分析 . 5 2.1 需求分析 . 5 2.2 系統功能 . 5 2.3 開發環境 . 5 3、 詳細設計 . 5 3.1 功能結構框圖 . 6 3.2 軟件設計 . 6 3.2.1 定義鏈表與接收數據輸入 . 6 3.2.2 長整數的加法運算 . 8 3.2.3 顯示長整數相加結果 . 10 4、 所遇到的問題和分析解決 . 10 5、 系統特色及關鍵技術 . 1

2、1 6、 結論 . 11 參考文獻 . 12 3 引言 隨著計算機技術的發展，人們利用計算機開發了許許多多方便的，實用的應用軟件，在信息化的現代社會里，人們依賴著很多的應用軟件，這些軟件在推進社會發展的同時，也豐富了人們的生活，然而，在開發過程中，由于計算機系統的局限性，在需要某些功能時，總會遇到困難。例如在開發某些工程項目時，有時需要對很大的數進行計算。但是計算機本身無法計算某些較大的數，所以我們有必要設計專門的算法對一些較大的數進行相應的計算，通過簡化運算之后，對其他程序功能的編寫能起到良好的促進作用，大大的減輕了程序員的負擔。此次設計的程序將用于長整數的加法運算，程序運行時，將提示用戶輸

3、入兩個長整數，然后將兩個長整數相加的結果輸出。 1、系統概述 在該長整數加法運算系統中，我將定義雙向循環鏈表來表示長整數，按照中 國對長整數的表示方法，如 199999999 表示為 1,9999,9999。雙向循環鏈表數據域存儲的是長整數的每 4 位。雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直接后繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點。通過造雙向循環鏈表，可以對長整數進行方便的存儲，在對長整數進行數學運算時，也能通過方便的操作鏈表，從而對長整數進行需要的計算。 在實現該長整數加法運算的系統中，我將會編程實

4、現以下功能。定義一個函數，用于接收長整數的輸入，同時將長整數存儲到雙向循環鏈表當中，為了檢驗是否按預期要求進行存儲，我還會編寫一個函數，將雙向循環鏈表中數據域的值打印出來。定義一個長整數相加的函數，實現兩個長整數加法運算的功能，實際上是對雙向循環鏈表進行操作，這里包括結點空間的申請，插入結點，修改指針所保存的值。 當兩個長整數完成加法運算后，我會定義一個顯示結果的函數，將它們相加的結果打印出來。一些較大的整數，在單純的用計算機進行相加運算的時候可能會產生溢出現象，但該系統每次只對 4 位整數進行運算，避免了數據過大在計算時產生的溢出問題。 4 2、系統分析 2.1 需求分析 設計一個計算兩個長

5、整數加法的程序，要求長整數的位數不能規定上限。根據中國對于長整數的表示習慣，長整數每 4 位用逗號隔開。故可以利用雙向循環鏈表對長整數進行存儲，每個結點可以存儲長整數的 4 位，即每個結點的數據域最大值為 9999，頭結點的數據域的值的正負號可以表示長整數的正負，其絕對值可以表示結點數目。為了運算與編程的方便，在相加過程中不要破壞兩個操作數鏈表。 2.2 系統功能 （1）建立雙向循環鏈表，用于保存長整數及長整數的運算。 （2）接收長整數的輸入，長整數的每 4 位都保存到鏈表的結點中。 （3) 對存入雙向鏈表的長整數進行加法運算，在進行運算時，能很好的處理進位，借位問題以及對長整數的正負能做出判

6、斷，然后進行相應的運算處理，保證運算結果能與預期結果一致。 （4）正確的輸出運算后的結果，這里的運算結果也是長整數，故對數的存儲也是采用雙向循環鏈表，輸出結果即是按長整數的顯示方式打印出雙向循環鏈表數據域的值。 2.3 開發環境 所用開發環境為微軟公司開發的 VC+6.0 軟件，該軟件可將“高級語言”翻譯為“機器語言” ，該程序開發語言為 C 語言。 3、詳細設計 5 3.1 功能結構框圖 圖 3-1 系統功能結構框圖 這是長整數相加運算的一個設計思路。在該系統中，我會設置幾個函數，分別實現不同的功能，如接收數據輸入的函數，將兩個長整數進行相加的函數，顯示出長整數相加結果的函數。重點是在加法運

7、算的函數里，在功能結構框圖中只是大致的介紹出設計思路，分 3 種情況考慮，具體在每種情況里，也分許多細小的情況進行處理。該系統重要的部分是對雙向循環鏈表進行操作。 3.2 軟件設計 3.2.1 定義鏈表與接收數據輸入 因為該系統的功能是對長整數進行運算，所以對長整數是用雙向循環鏈表進行存儲，鏈表每個結點均存儲絕對值不超過 9999 的整數，在進行運算時，依次對每個結點進行運算，再判斷是否需要進位和借位。該系統主要使用的數據結構是雙向循環鏈表，無任何特殊的算法，只有對雙向循環鏈表的一些簡單操作，如插入操作，注意前驅指針和后繼指針發生變化時的修改即可。 （1）定義雙向循環鏈表的抽象數據類型 6 雙

8、向循環鏈表的結點定義圖 3-2 此雙向循環鏈表中，定義了一個頭結點來保存長整數的信息，即頭結點的 頭結點數據域的絕對值表示雙向循環鏈表除頭結點外正負表示該長整數的正負，。頭結點數據域 PNODE 的結點個數。為了后面的編程方便，將結點類型重命名為避免了長用雙向循環鏈表來保存長整數，的信息對于加法運算起到一定的作用。整數位數達到上限的問題，間接的解決了計算機無法計算某些較大整數的問題。對雙向循環鏈表的頭指針和尾指針進行定義了一個雙鏈表類型的結構體，同時，封裝，雙鏈表類型的結構體可以準確的表示長整數。同樣為了后續的編程方便， 。數據類型如下圖所示，將雙向循環鏈表類型的結構體重命名為 List Li

9、st 指針表示雙向循環鏈表圖 3-2 定義 2）接收長整數的輸入（定義一個函數，用于接收長整數的輸入，將長整數保存到雙向循環鏈表中， 位分別保存到鏈表的結點數據域中。長整數的每 4 的格式輸入，該程序 XXXX,XXXX,XXXX;在接收數據輸入時，提示用戶按，當用戶輸入分號時表示結束輸入，逗”,”和“;定義了一個 char ch 用于保存“采用的方法是先讓用戶輸入整型在接收用戶的輸入時，號用于間隔開每個結點。就輸入逗號或 4 位整數，然后再輸入字符型變量，變量，即提示用戶每輸入一個位整數，申請分號，若用戶輸入分號，則表示用戶輸入數據完畢，每輸入一個 4（申請結點空間的時候要注意判斷結點空間是

10、否申請型的結點空間一個 PNODE，然后將成功，若申請結點空間失敗，則打印提示信息，然后退出函數的操作）新申請結點的前驅指針保存原鏈該結點空間插入表示長整數的雙向循環鏈表中，循表最后一個結點的地址，后繼指針保存最高位結點的地址，這里是通過 while 的值為分號時，結束鏈表的建環的方式把雙向循環鏈表建立起來，直到輸入 ch 長整數已經用雙向循環鏈表 4 這時位整數已經存儲到鏈表的結點數據域中，立。的正負以及統計出除頭結點外的其 head-next-data 表示。輸入完成后，判斷出7 他結點個數，然后將結果保存到頭結點的數據域中，用于表示長整數的正負及長整數的位數長度。為了確定長整數已經按預期

11、的形式保存到雙向循環鏈表當中，我設置了一個打印鏈表的函數，從頭結點的后繼結點開始對鏈表進行訪問，直到訪問到鏈表最后一個結點為止，將鏈表中的每個結點數據域打印出來，觀察其結果。如果某個結點的數據域的值為 0000，打印鏈表時顯示出來的結果是0，這對后面的計算沒有影響，類似于這樣的問題在計算完長整數后，顯示結果時會進行處理，此時僅是確認鏈表中數據域的信息。 長整數接收輸入完畢后，已經保存到一個帶有頭結點的鏈表當中了，為了后續的計算方便，需要對該雙向循環鏈表設置一個尾指針。定義一個函數，用于設置雙向循環鏈表的尾指針，在該函數中定義一個 PNODE 類型的變量 p，p 從鏈表的頭結點的后繼結點開始進行

12、訪問，當 p 訪問到鏈表的最后一個結點時，結束循環，將 p 作為函數的返回值返回，此時 p 表示的便是該雙向循環鏈表的尾指針。因為在加法的操作中，都是先對雙向循環鏈表的最后一個結點進行操作，所以設置尾指針是很方便的，很有必要的。 3.2.23.2.2 長整數的加法運算長整數的加法運算 長整數是用雙向循環鏈表進行存儲的，對長整數進行加法運算，相當于對雙向循環鏈表操作。在此程序當中，進行加法運算時，可分為 3 種不同的情況，即兩正數相加，兩負數相加，兩符號互異的數進行相加，符號互異的兩數在進行運算時，可視為做減法運算。下面進行詳細的介紹。鏈表相加操作時，采用的思路是將長度較短的鏈表加到長度較長的鏈

13、表中，所以在相加之前，先計算出兩個鏈表的長度，用長度較長的鏈表先保存計算結果，最后將結果賦給“結果”鏈表。 為了說明及編程方便，用 p 指向長鏈表的尾結點，用 q 指向短鏈表的尾結點，此次設計的思想是長鏈表的值加上短鏈表的值，最后保存長鏈表。 （1）兩正數相加 如果兩個都是絕對值不超過 9999 的整數，則將兩個數進行相加，即將 p 的數據域的值加上 q 的數據域的值，然后判斷相加結果即 p 結點的數據域的值是否超過 9999，如果超過 9999，則需要進行進位處理，即申請一個 PNODE 型結點空間，其數據域用于保存進位值，進位值為 1，將該結點插入頭結點的后面，頭結點的后繼指針保存該結點的

14、地址，該結點的前驅指針保存頭結點的地址，后繼指針保存原頭結點后繼結點的地址。若不產生進位，則用 result_list 保存所得到的結果鏈表，result_list 為 List 類型的變量，即它表示雙向循環鏈表。 如果兩個長整數當中，有超過 9999 的數，即該鏈表中存在多個結點，則對其從最后一個結點進行操作，即 p 結點數據域的值加上 q 結點數據域的值,p q 指針依次往前訪問鏈表，重復如上的相加操作，直到 p 或 q 訪問到頭結點為止，出現需要進位的情況時，前驅結點數據域進行加一操作，該結點數據域進行減10000 的操作，若在最高 4 位結點產生進位，則申請一個 PNODE 型的結點空

15、間，其數據域保存進位值，將該結點插入頭結點的后繼結點，注意保持鏈表最后一個結點的后繼指針一直保存頭結點后繼指針的地址，保證該鏈表一直是雙向循環的，否則在打印鏈表時會出現指針異常的情況。最后用 result_list 保存所得到的結果鏈表。 （2）兩負數相加 當兩個長整數均為負數時，進行以下操作。如果兩數當中存在一個數，其絕8 對值小于 9999 時，分為兩種情況，一種是兩個數的絕對值都小于 9999，另一種則是只有一個數的絕對值小于 9999。 當兩個數的絕對值都小于 9999 時，將兩個雙向循環鏈表的尾結點數據域進行相加，即 p 結點數據域的值加上 q 結點數據域的值，若相加結果data 進

16、行取反操作，再將其與 p-data 進行相加，同時從 p 指向的結點開始進行進位判斷，直到判斷到最高位結點為止，此處的進位處理情況與（1）中的進位處理相同，但在處理最高位時，要注意符號的正負性。若在最高位產生進位，則申請新的 PNODE 型結點空間，命名為 high，high-data 的值為-1，此時p 指向的是最高位結點，則 p 的數據域的值先加上 10000，然后進行取反操作，這是為了將第 2 個 4 位整數的負號去除。 除上述兩種情況，其他情況下可對表示長整數的鏈表，從其尾結點處開始，將 q-data 加到 p-data 中，在進行相加的過程中判斷是否需要進位，若相加結果絕對值超過 9

17、999，則需要進行進位處理（最高位進位做特殊處理） ，即前驅結點進行+1 操作，該結點數據域進行-10000 的操作。若操作到最高位的數據域，則申請新的 PNODE 型結點空間，命名為 high，high-data 的值為-1，此時 p 指向的是最高位結點，則 p 的數據域的值先加上 10000，然后進行取反操作，這是為了將負號去除。最后所得的結果用 result_list 鏈表進行存儲，將該變量作為相加函數的返回值。若兩個鏈表長短不同，q 已經訪問到最高位結點而 p 還未訪問到最高位結點，則先將 q 的數據域的值進行取反操作，然后與 p 數據域的值進行相加，這里判斷進位，處理進位的方法與上述

18、情況相同。 （3）兩符號互異的長整數相加，做相減運算 當且僅當兩個長整數絕對值均不大于 9999 時，直接將兩個鏈表的尾結點數據域進行相加，即 p 結點數據域的值加上 q 結點數據域的值，將所得結果的鏈表用 result_list 進行存儲。兩個絕對值不超過 9999 的數，且兩數的符號互異（即兩數為一正一負） ，它們在做加法運算時，所得的結果長整數的絕對值不會超過 9999，故這里不用考慮進位的問題，兩數直接相加即可。 兩個長整數當中存在一個長整數的絕對值不超過 9999 時，若 q-data 為負數，判斷 p-data 與 q-data 的絕對值大小，若 p-data 的絕對值小于 q-d

19、ata，則需要進行借位操作，即 p 的前驅結點數據域進行-1 操作，p 結點數據域進行+10000 操作，如果不需要借位，則 p 的數據域和 q 的數據域直接進行相加。最后結果用 result_list 存儲，將 result_list 返回。如果 q-data 為正數，判斷 p 結點數據域與 q 結點數據域的大小，若 p-datadata，則需要進行借位操作，然后 p 結點的數據域減掉 q 結點數據域的值。若不需要借位操作，則 p 的數據域直接減去 q 的數據域的值。 兩個長整數的絕對值均大于 9999,時，均從鏈表的尾結點開始進行相減操作，在需要借位時，前驅結點的數據域-1，自身結點的數據

20、域+10000，若 q 已到達最高位，p 還未到達最高位時，判斷 p 的數據域與 q 的數據域的值，看是否需要進行借位操作，然后 p 的數據域的值直接加上 q 的數據域的值。若 p 和q 同時指向最高位的結點，則它們的數據域的值可以直接進行相加操作。最后所得到的的結果鏈表用 result_list 進行存儲，將 result_list 返回。 9 3.2.33.2.3 顯示長整數相加結果顯示長整數相加結果 由程序可知，兩個長整數相加的結果是用 List 類型的雙向循環鏈表進行存儲，可以通過定義一個簡單的打印鏈表數據域的值的函數，將長整數相加的結果打印出來。在打印鏈表的過程中，可做一些處理，使得

21、顯示結果不影響長整數的數值大小。在打印每個結點數據域之前對數據域的值進行判斷，若結點數據域的值小于 1000，可在顯示數據前面“補 0” ，使得每個結點顯示出來的都是“4位整數” 。 在打印鏈表時，定義一個 PNODE 類型的 p，用 p 從最高位結點開始，依次訪問鏈表中的每個結點，直到尾結點，然后將結點的數據域的值“按要求”顯示在屏幕上，即打印出來的結點數據域的值用逗號隔開，這就是中國對于長整數的傳統表示方法。程序運行結果如下圖所示： 圖 3-3 程序運行結果 4、所遇到的問題和分析解決 4.14.1 對雙向循環鏈表進行操作時，總是出現指針異常的情況，如在做插入操作時，需要修改指針的值，無意

22、間使某些指針成為“野指針” 。通過分析每個指針變量所存儲的信息，便可找出異常指針，然后將其賦為 NULL 指針或者修改其信息，使該指針成為正確的指針，同時，在定義指針的時候要將指針的值初始化為 NULL，這樣可以避免指針成為“野指針” 。 4.24.2 在進行相加（相減）操作時，所得到的相加（相減）結果不是預期結果。解決該問題，要通過分析測試數據的性質，觀察兩個測試長整數滿足了什么條件，執行了程序當中的哪條語句，是哪條語句或語句塊沒有考慮到功能的完善性，再進一步的從數學角度分析數的性質，最后通過修改部分語句，完善其功能。 4.34.3 在輸出長整數相加結果的函數當中，輸出的長整數產生“錯誤”

23、，如1,0001 的數輸出為 1,1。要解決該問題，先分析長整數的性質，通過分析，發現除最高位結點外，其他結點的數據域的值，小于 1000 的數要在前面補上“0” ，使他們10 以 4 位整數的形式輸出，這樣才不會影響整個長整數的大小及表示方法。 5、系統特色及關鍵技術 該系統的特色在于能計算較大的，位數較長的長整數。無論多長的整數，運用該系統進行計算時，都可以將該整數按每 4 位的“分割”方法，將 4 位整數保存到雙向循環鏈表的結點數據域中，然后再進行計算（即對鏈表進行操作，如修改指針，數據域的值） ，相當于每次只進行 4 位數的計算。解決了計算機無法計算一些較大數據的問題。關鍵技術在于雙向循環鏈表的操作以及在做長整數相加操作時的進位，借位操作。做相加操作之前，先計算出兩個鏈表的長度，將較短的鏈表“加進”較長的鏈表中，最后直接用較長的鏈表表示相加結果，這樣就不需要額外建立一個鏈表來保存兩個長整數相加的結果，減少了結點空間的申請。 6、結論 在本次的數據結構與算法課程設計中，該系統提供了長整數加法運算的功能，根據課程設計指導書的測試數據進行測試，該系統也成功實現了這些數據的加法運算。與加法算法類似，該系統中也可以增加長