長整數(shù)的運算_算法與數(shù)據(jù)結構課程設計1 精品.doc

*實踐教學* 蘭州理工大學 軟件學院 算法與數(shù)據(jù)結構 課程設計題 目： 長整數(shù)的運算 專業(yè)班級： 軟件二班 目 錄摘 要數(shù)據(jù)結構該設計要求學生設計程序，實現(xiàn)兩個任意長的整數(shù)求和及差的運算問題。通過該題目的設計過程，可以加深理解線性表的邏輯結構、存儲結構，掌握線性表上基本運算的實現(xiàn)，進一步理解和熟練掌握課本中所學的各種數(shù)據(jù)結構，學會如何把學到的知識用于解決實際問題，培養(yǎng)學生的動手能力關鍵詞：雙循環(huán)鏈表；插入；刪除；長整數(shù)加減前 言利用雙向循環(huán)鏈表來實現(xiàn)對長整數(shù)的存儲。每個節(jié)點只存儲四位十進制數(shù)字，即不超過9999的非負整數(shù)。雙向鏈表有頭指針，它的data值存儲長整數(shù)的符號，1為正，-1為負，0代表長整數(shù)為0；它的over值存儲除頭節(jié)點外節(jié)點的個數(shù)。其他節(jié)點的data值存儲四位整數(shù)，over存儲該四位整數(shù)溢出09999范圍的情況，一般over0表示四位數(shù)超出9999，overnext; while(p!=head&inext; i+; if(i!=n) printf(插入位置錯誤n); return 0; 3.加法函數(shù)設計思路：先將各位做加減，然后根據(jù)所得長整數(shù)正負和各結點data值進位或退位計算所得長整數(shù)的值并輸出。void add(DLNode *h1,DLNode *h2) /兩數(shù)相加 DLNode *p1=h1-prior,*p2=h2-prior; while(p1!=h1&p2!=h2) /每個鏈表元素相加 p1-data+=p2-data ; p1=p1-prior; p2=p2-prior; p1=h1-prior; while(p1!=h1-next) /處理鏈表元素 if(p1-data=10000) p1-prior-data+=p1-data/10000; p1-data%=10000; if(p1-datanext!=0) p1-prior-data-=1; p1-data+=10000; p1=p1-prior; if(h1-next-data=10000) /處理最前面的數(shù) InsertNode(h1,0,h1-next-data/10000); h1-next-next-data%=10000; if(h1-datanext-data/10000); h1-next-next-data%=-10000; PrintNode(h1); 4.減法函數(shù)設計思路：void jian(DLNode *h1,DLNode *h2) /兩數(shù)相減 DLNode *p1=h1-prior,*p2=h2-prior; while(p1!=h1&p2!=h2) /每個鏈表元素相減 p1-data-=p2-data ; p1=p1-prior; p2=p2-prior; p1=h1-prior; while(p1!=h1-next) /處理鏈表元素 if(p1-data=10000) p1-prior-data+=p1-data/10000; p1-data%=10000; if(p1-datanext!=0) p1-prior-data-=1; p1-data+=10000; p1=p1-prior; if(h1-next-data=10000) /處理最前面的數(shù) InsertNode(h1,0,h1-next-data/10000); h1-next-next-data%=10000; if(h1-datanext-data/-10000); h1-next-next-data%=-10000; PrintNode(h1); 3. 函數(shù)的調(diào)用關系圖開始主函數(shù)調(diào)運void add(DLNode *h1,DLNode *h2)建立鏈表主函數(shù)結束束)調(diào)運void InitNode(DLNode *h1)建立運算4. 調(diào)試分析a、 調(diào)試中遇到的問題及對問題的解決方法調(diào)試過程中的困難：在數(shù)據(jù)的運算中，應為是根據(jù)數(shù)的大小來選擇運算的，所以過程相對比較繁瑣。而且對于雙向鏈表的兩個指針的定位以及鏈表的插入和刪除等操作花費的較多的時間。在這查閱參照了大量的網(wǎng)絡資料。b、算法的時間復雜度和空間復雜度由于鏈表采用雙向循環(huán)鏈表結構，可以從鏈表兩頭操作，各種操作的算法時間復雜度比較合理，各函數(shù)以及確定鏈表中的結點位置都是O（n）,n為鏈表長度。5. 測試結果a、 輸入0和0做加法運算，輸出“0”，結果如下圖：b、 輸入2345，6789和-7654，3211做減法運算，輸出“1，0000，0000”，結果如下圖：c、 輸入1，0000，0000，0000和9999，9999做減法運算，輸出“9999，0000，0001”，結果如下圖：d、 輸入1，0001，0001和1，0001，0001做減法運算，輸出“0”，結果如下圖：e、 輸入1,2345,6789 和9,8765,4321做加法運算，結果如下圖：6. 源程序（帶注釋）#include #include #include#include #define N 100 typedef int DataType; typedef struct DoubleNode /定義鏈表元素 DataType data; struct DoubleNode *prior; struct DoubleNode *next; DLNode; void InitNode(DLNode *head) /初始化鏈表 if(*head=(DLNode*)malloc(sizeof(DLNode)=NULL) exit(1); (*head)-prior=*head; (*head)-next=*head; int InsertNode(DLNode *head,int n,DataType x) /向鏈表第N個位置插入元素X DLNode *p,*nt; int i=0; p=head-next; while(p!=head&inext; i+; if(i!=n) printf(插入位置錯誤n); return 0; if(nt=(DLNode *)malloc(sizeof(DLNode)=NULL) exit(1); nt-data=x; nt-prior=p-prior; nt-prior-next=nt; nt-next=p; p-prior=nt; return 1; int digit(int n) /判斷整數(shù)N有幾位 int i; for(i=1;n/=10,i+) if(n/10=0) return i; void PrintNode(DLNode *head) /打印鏈表 DLNode *p=head-next; int i; while(p-data=0) /去掉前面的一串0 p=p-next; if(p=head) printf(0n); return; printf(%d,p-data); /最前面的一個數(shù)進行特殊處理,不用補零 p=p-next; while(p!=head) /打印后面的數(shù)字 printf(,); if(p-data=0) printf(0000); p=p-next; continue; for(i=0;idata);i+) /補零 printf(0); printf(%d,p-data); p=p-next; printf(n); void DestroyNode(DLNode *head) DLNode *p,*p1; p=(*head)-next; while(p!=*head) p1=p; p=p-next; free(p1); free(p); head=NULL; void add(DLNode *h1,DLNode *h2) /兩數(shù)相加 DLNode *p1=h1-prior,*p2=h2-prior; while(p1!=h1&p2!=h2) /每個鏈表元素相加 p1-data+=p2-data ; p1=p1-prior; p2=p2-prior; p1=h1-prior; while(p1!=h1-next) /處理鏈表元素 if(p1-data=10000) p1-prior-data+=p1-data/10000; p1-data%=10000; if(p1-datanext!=0) p1-prior-data-=1; p1-data+=10000; p1=p1-prior; if(h1-next-data=10000) /處理最前面的數(shù) InsertNode(h1,0,h1-next-data/10000); h1-next-next-data%=10000; if(h1-datanext-data/10000); h1-next-next-data%=-10000; PrintNode(h1); void jian(DLNode *h2,DLNode *h1) /兩數(shù)相減 DLNode *p1=h1-prior,*p2=h2-prior; while(p1!=h1&p2!=h2) /每個鏈表元素相減 p1-data-=p2-data ; p1=p1-prior; p2=p2-prior; p1=h1-prior; while(p1!=h1-next) /處理鏈表元素 if(p1-data=10000) p1-prior-data+=p1-data/10000; p1-data%=10000; if(p1-datanext!=0) p1-prior-data-=1; p1-data+=10000; p1=p1-prior; if(h1-next-data=10000) /處理最前面的數(shù) InsertNode(h1,0,h1-next-data/10000); h1-next-next-data%=10000; if(h1-datanext-data/-10000); h1-next-next-data%=-10000; PrintNode(h1); int main() /入口函數(shù) DLNode *head1,*head2; char data1N,data2N; char d110,d210; int i,j,k; int xun; InitNode(&head1); InitNode(&head2); while(1) printf(輸入數(shù)據(jù)：n);scanf(%s %s,data1,data2); InitNode(&head1); InitNode(&head2); i=0;k=0; while(data1i!=;) /將數(shù)1用鏈表儲存 for(j=0;j10;j+) d1j=0; j=0; while(data1i!=;&data1i!=,) d1j+=data1i+; if(data1i=,) i+; if(data10=-) /處理正負數(shù) j=-(int)fabs(atoi(d1); else j=atoi(d1); InsertNode(head1,k+,j); i=0; k=0; while(data2i!=;) /將數(shù)2用鏈表儲存 for(j=0;jstrlen(data2) /較長的數(shù)作為被加數(shù) add(head1,head2); else add(head2,head1); break; case 2:if(strlen(data1)strlen(data2) /較長的數(shù)作為被減數(shù) jian(head1,head2); else jian(head2,head1); break;default:break; DestroyNode(&head1); DestroyNode(&head2); return 0; 總 結關于實驗本身的收獲是掌握了雙向鏈表，通過該題目的設計過程，可以加深理解線性表的邏輯結構、存儲結構，掌握線性表上基本運算的實現(xiàn)，進一步理解和熟練掌握課本中所學的各種數(shù)據(jù)結構，學會如何把學到的知識用于解決實際問題，培養(yǎng)學生的動手能力。而實驗外的就是更好的利用了網(wǎng)路資源，通過網(wǎng)絡的搜索引擎等。加深了自己在這方面知識的補充。并且在于同學交流中分析了彼此算法的優(yōu)劣程度。我覺得這是本次實驗最大的收獲。 參考文獻1 嚴蔚敏，吳偉民.數(shù)據(jù)結構（C語言版）.清華大學出版社.2 嚴蔚敏，吳偉民.數(shù)據(jù)結構題集（C語言版）.清華大學出版社.3 DATA STRUCTURE WITH C+. William Ford,William Topp .清華大學出版社（影印版）. 4 譚浩強.c語言程序設計. 清華大學出版社. 5數(shù)據(jù)結構與算法分析（Java版） , A Practical Introduction to Data Structures and Algorithm Analysis Java Edition , 張銘,劉曉丹譯電子工業(yè)出版社 20XX 年1月致 謝首先，我要感謝我的算法與數(shù)據(jù)結構及課程設計老師王連相老師，謝謝王老師對我的諄諄教導，讓我懂得了算法與數(shù)據(jù)結構的理論知識，為我做課程設計奠定了理論基礎。另外，感謝王老師在我做課程設計的過程中給我提出的寶貴意見和建議，我根據(jù)王老師的建議對我的程序進行了改進，從而使程序