線性表實(shí)現(xiàn)大整數(shù)運(yùn)算實(shí)驗(yàn)報(bào)告

1、石家莊經(jīng)濟(jì)學(xué)院實(shí) 驗(yàn) 報(bào) 告網(wǎng)址：實(shí)驗(yàn)名稱：線性表實(shí)現(xiàn)大整數(shù)運(yùn)算學(xué)號(hào)：413109030111實(shí)驗(yàn)日期：2015.03姓名：孫曉穎設(shè)備編號(hào)：實(shí)驗(yàn)室：152一、 實(shí)驗(yàn)內(nèi)容1. 實(shí)現(xiàn)線性表鏈?zhǔn)浇Y(jié)構(gòu)的插入、刪除、查找以及合并等操作的算法、編程實(shí)現(xiàn)；2. 使用雙向鏈表結(jié)構(gòu)，設(shè)計(jì)并實(shí)現(xiàn)長(zhǎng)整數(shù)數(shù)據(jù)類型的表示及相關(guān)運(yùn)算二、 概要設(shè)計(jì)ADT Longint 數(shù)據(jù)對(duì)象：D=ai,bj|ai,bj0,1,2,3,4,5,6,7,8,9,i=1,2,n,n>=0,j=0,1,2,m,m>=0數(shù)據(jù)關(guān)系：R=<ai,ai+1>&&<ai+1,ai>,i=1,2,n基本

2、操作： shuru(DuLinkList &L) 操作結(jié)果：構(gòu)造一個(gè)雙向循環(huán)鏈表。 shuchu(DuLinkList L) 初始條件：雙向鏈表s已存在。 操作結(jié)果：將輸入雙向循環(huán)鏈表輸出。 shu(DuLinkList L) 操作結(jié)果：將操作結(jié)果雙向循環(huán)鏈表輸出。 add(DuLinkList LA, DuLinkList LB,DuLinkList &LC)初始條件：兩雙向循環(huán)鏈表p,q已存在。 操作結(jié)果：將存放長(zhǎng)整型數(shù)據(jù)的兩雙向鏈表進(jìn)行加法運(yùn)算, 得到新的鏈表。 minus(DuLinkList LA, DuLinkList LB,DuLinkList &LC)初

3、始條件：兩雙向循環(huán)鏈表p,q已存在 操作結(jié)果：兩雙向循環(huán)鏈表進(jìn)行減法運(yùn)算，得到新的鏈表。mul(DuLinkList LA, DuLinkList LB,DuLinkList &LC)初始條件：兩雙向循環(huán)鏈表已存在。 操作結(jié)果：將存放長(zhǎng)整型數(shù)據(jù)的兩雙向鏈表進(jìn)行乘法運(yùn)算，得到新鏈表。 ADT Longint三、 詳細(xì)設(shè)計(jì)/-存儲(chǔ)結(jié)構(gòu)表示-typedef struct DuLNode ElemType data; struct DuLNode *prior; struct DuLNode *next;DuLNode,*DuLinkList; /*定義鏈表結(jié)構(gòu)*/ /-基本操作的實(shí)現(xiàn)-voi

4、d shuru(DuLinkList &L)/輸入 建立LA LB 鏈表無空頭節(jié)點(diǎn)char ch;int opra,i;DuLinkList p,q; printf("請(qǐng)輸入長(zhǎng)整數(shù) 每3位加'，' 輸入以#結(jié)束 n"); L=(DuLinkList)malloc(sizeof(DuLNode);/新建空鏈表 L->prior=NULL; p=L; scanf("%d",&opra);/輸入數(shù)據(jù) p->data=opra;ch=getchar();while(ch!='#')/讀取未結(jié)束q=(Du

5、LinkList)malloc(sizeof(DuLNode);q->data =0;for (i=0;i<3;i+)ch=getchar();q->data =q->data * 10 +(ch-'0');p->next =q;/連入鏈表q->prior =p;p=q;/后移ch=getchar();p->next =NULL; printf("提示：輸入成功 ! n"); void shuchu(DuLinkList L)/輸出 （無空頭節(jié)點(diǎn)） DuLinkList p; int number,i; ElemTy

6、pe e; printf(" 輸出結(jié)果n"); number=0;/計(jì)算元素個(gè)數(shù) p=L; while(p!=NULL) number+; p=p->next; p=L; for(i=1;i<=number;i+) e=p->data;/對(duì)當(dāng)前結(jié)點(diǎn)輸出結(jié)果進(jìn)行分情況討論 p=p->next; if (i=1) /對(duì)最高位為0 if(e!=0) printf("%d",e); else/其他位分情況 if(e=0) /數(shù)值為0 printf("000");else if(e<10) /如果數(shù)值為1位 pri

7、ntf("00%d",e); else if(e<100)/如果數(shù)值為2位 printf("0%d",e); else printf("%d",e); /逗號(hào) if(i!=number) if (i!=1) printf(","); else if (e!=0) printf(","); printf(" n 輸出成功 !n ");void shu(DuLinkList L)/輸出運(yùn)算結(jié)果 DuLinkList p; int number,i; ElemType e;

8、printf(" 輸出結(jié)果n"); number=0;/計(jì)算元素個(gè)數(shù) p=L; while(p->next !=NULL) number+; p=p->next; p=L->next ; for(i=1;i<=number;i+) e=p->data;/對(duì)當(dāng)前結(jié)點(diǎn)輸出結(jié)果進(jìn)行分情況討論 p=p->next; if (i=1) /對(duì)最高位為0 if(e!=0) printf("%d",e); else/其他位分情況 if(e=0) /數(shù)值為0 printf("000");else if(e<10

9、) /如果數(shù)值為1位 printf("00%d",e); else if(e<100)/如果數(shù)值為2位 printf("0%d",e); else printf("%d",e); /逗號(hào) if(i!=number) if (i!=1) printf(","); else if (e!=0) printf(","); printf(" n 輸出成功 !n ");/加法void add(DuLinkList LA, DuLinkList LB,DuLinkList &

10、;LC) DuLinkList p,q,m,n,tail; ElemType tempa,tempb,tempc,temp;printf("提示： 加法運(yùn)算 n"); p=LA; while (p->next !=NULL)/指向LA尾p=p->next ;q=LB; while (q->next!=NULL)/指向LB尾q=q->next ; /新建鏈表LC LC=(DuLinkList)malloc(sizeof(DuLinkList); LC->prior=NULL;m=(DuLinkList)malloc(sizeof(DuLinkLi

11、st);tail=m;temp=0;/進(jìn)位 while( (p!=NULL)|(q!=NULL) )/當(dāng)短鏈結(jié)束后，繼續(xù)計(jì)算，視為當(dāng)前結(jié)點(diǎn)運(yùn)算數(shù)為0if(p!=NULL) tempa=p->data;else tempa=0; if(q!=NULL) tempb=q->data;else tempb=0;tempc=tempa+tempb+temp;if (tempc /1000 =0)/若不需要進(jìn)位 temp=0; if (tempc/1000 >0 )/若需要進(jìn)位 temp=1; tempc=tempc % 1000; n=(DuLinkList)malloc(sizeo

12、f(DuLinkList);/新建節(jié)點(diǎn) m->data =tempc; n->next=m;m->prior=n;m=n; p=p->prior;/向前移一位q=q->prior;/向前移一位 tail->next=NULL; LC->next=m->next; m->next->prior =LC; free(m); shu(LC);/減法void minus(DuLinkList LA, DuLinkList LB,DuLinkList &LC) DuLinkList p,q,m,n,tail; ElemType temp

13、a,tempb,tempc,temp;printf("提示： 減法運(yùn)算 n"); p=LA;/指向LA頭結(jié)點(diǎn) while (p->next !=NULL) p=p->next ;q=LB;/指向LB頭結(jié)點(diǎn) while (q->next !=NULL)q=q->next ;/新建鏈表LC LC=(DuLinkList)malloc(sizeof(DuLinkList); LC->prior=NULL; m=(DuLinkList)malloc(sizeof(DuLinkList);tail=m;temp=0;/借位 while( (p!=NULL

14、)|(q!=NULL) )/當(dāng)短鏈結(jié)束后，繼續(xù)計(jì)算，視為當(dāng)前結(jié)點(diǎn)運(yùn)算數(shù)為0if(p!=NULL) tempa=p->data;else tempa=0; if(q!=NULL) tempb=q->data;else tempb=0;tempc=tempa-tempb+temp; if (tempc >=0 )/若不需要借位 temp=0; if (tempc<0 )/若需要借位 temp=-1; tempc=tempc+1000; n=(DuLinkList)malloc(sizeof(DuLinkList);/新建節(jié)點(diǎn) m->data =tempc;n->

15、next =m;m->prior=n;m=n;p=p->prior;/向前移一位q=q->prior;/向前移一位 tail->next=NULL; LC->next=m->next ; m->next->prior =LC;free(m); shu(LC);/乘法void mul(DuLinkList LA,DuLinkList LB,DuLinkList &LC) DuLinkList p,q,m,n,tail; int temp,s; p=LA; q=LB;LC=(DuLinkList)malloc(sizeof(DuLNode);

16、/新建LC->prior=NULL;LC->next=NULL;m=(DuLinkList)malloc(sizeof(DuLNode);m->next=NULL; tail=m; /末尾的值m->prior=NULL;m->data=0;n=m;while (q->next!=NULL) /乘數(shù)移至最后一個(gè)節(jié)點(diǎn)q=q->next ;temp=0; /進(jìn)位while (q!=NULL) /乘數(shù)未結(jié)束m=tail;/LC尾部p=LA;while (p->next!=NULL)/被乘數(shù)移至最后一個(gè)節(jié)點(diǎn)p=p->next ;while (p!=N

17、ULL) /被乘數(shù)未結(jié)束if(m=NULL) m=(DuLinkList)malloc(sizeof(DuLNode);m->prior=NULL; m->data=(p->data*q->data+temp)%1000; temp=(p->data*q->data+temp)/1000; /進(jìn)位n->prior=m;/相連m->next=n; n=m;m=m->prior ;/向前挪else s=m->data+p->data*q->data+temp; /存放相乘的數(shù)與需要進(jìn)位的和m->data=s%1000;

18、if (m->next!=NULL) temp=s/1000; /判斷是否是第一次運(yùn)算 else temp=(p->data*q->data)/1000+temp; n=m;m=m->prior; p=p->prior ; /被乘數(shù)向前挪一位if (temp!=0) /判斷進(jìn)位m=(DuLinkList)malloc(sizeof(DuLNode);m->data=temp;m->prior=NULL;n->prior =m;m->next=n;n=m;m=m->prior;temp=temp/1000; /判斷進(jìn)位值是否大于1000

19、q=q->prior ; /乘數(shù)向前挪tail=tail->prior ; /錯(cuò)位相加LC->next=n; /與頭節(jié)點(diǎn)相連n->prior=LC; shu(LC);四、 程序的調(diào)試與測(cè)試圖1 雙向鏈表1的建立圖2 雙向鏈表2的建立圖3 加法運(yùn)算圖4 減法運(yùn)算圖5 乘法運(yùn)算 圖一表示輸入數(shù)213100234鏈表的建立。以字符串形式輸入轉(zhuǎn)化為相應(yīng)數(shù)值，保存至節(jié)點(diǎn)中。圖二表示輸入數(shù)100234456鏈表的建立，過程同鏈表一。圖三表示213100234、100234456兩數(shù)的加法運(yùn)算結(jié)果，在進(jìn)行加法運(yùn)算的過程中，要從兩鏈表從后往前對(duì)應(yīng)節(jié)點(diǎn)數(shù)值相加，每個(gè)結(jié)點(diǎn)中只存放三位數(shù)字，

20、當(dāng)相加的結(jié)果大于或者等于1000時(shí)，要進(jìn)位，對(duì)該結(jié)果進(jìn)行取余，結(jié)果即為該結(jié)點(diǎn)數(shù)值，整除后的結(jié)果即為當(dāng)前進(jìn)位數(shù)值。注意輸出的過程中，零輸出與逗號(hào)輸出。圖四表示213100234、100234456兩數(shù)的減法運(yùn)算結(jié)果，在進(jìn)行減法運(yùn)算的過程中，同樣是要從兩鏈表的尾部向前進(jìn)行，在減法的過程中，若被減數(shù)大于減數(shù)，要向前一節(jié)點(diǎn)數(shù)值借位，同時(shí)前一結(jié)點(diǎn)數(shù)值減一，當(dāng)減法結(jié)束后，輸出時(shí)要從第一個(gè)非零數(shù)開始輸出，注意零輸出。圖五表示213100234、100234456兩數(shù)的乘法運(yùn)算結(jié)果，在進(jìn)行乘法運(yùn)算的過程中，同樣是要從兩鏈表的尾部向前進(jìn)行，乘數(shù)的最后一結(jié)點(diǎn)與被乘數(shù)的每一結(jié)點(diǎn)數(shù)值進(jìn)行乘法運(yùn)算，之后被乘數(shù)結(jié)點(diǎn)向前移位，再次與被乘數(shù)的每一節(jié)點(diǎn)進(jìn)行乘法運(yùn)算，乘數(shù)繼續(xù)前移，直到移至第一個(gè)結(jié)點(diǎn)為止，同時(shí)將相乘結(jié)果進(jìn)行錯(cuò)位相加，在乘法運(yùn)算的過程中，當(dāng)相乘所得大于等于1000時(shí)，要進(jìn)位，對(duì)該結(jié)果取余，取余后的結(jié)果即為該結(jié)點(diǎn)保存數(shù)值，整除后的結(jié)果即為要進(jìn)位的數(shù)，若輸出的過程中注意零輸出。五