長整數(shù)的運(yùn)算_算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)1 精品.doc

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