Đề bài tập: Viết chương trình cộng và nhân 2 số nguyên vô cùng lớn (hàng chục chữ số), dùng Danh sách liên kết đôi (C++).Powered by Tran Minh Tam.
/*BAI TAP*/
// Cong,nhan 2 so nguyen lon tren DSLK doi
#include<stdio.h>
#include<conio.h>
#include<string.h>
#define TRUE 1;
#define FALSE 0;
typedef int datatype; //khai niem kieu du lieu duoc dung trong dslk
typedef struct _node{ //dinh nghia cau truc node
datatype info;
_node* next;
_node* pre;
}node;
typedef node* nodeptr; //dat ten lai kieu DL luu dia chi kieu node
//khai bao cau truc DSLK
typedef struct _DSLK{
// int sign;
nodeptr phead; //luu dia chi node dau tien cua ds
nodeptr ptail; //luu dia chi node cuoi cung cua ds
}DSLK;
//kiem tra dslk rong
int Isempty(DSLK &ds)
{
return ds.phead==NULL?1:0;
}
//ham khoi tao dslk rong
void InitDSLK(DSLK &ds)
{
ds.phead=NULL;
ds.ptail=NULL;
}
//ham khoi tao node moi cho dslk kep
nodeptr getnode(datatype x)
{
nodeptr p=new node;
p->info=x; //gan giai tri x cho node
p->next=p->pre=NULL;
return p; //tra ve node vua tao
}
//ham chen them node vao dau ds
void chendau(DSLK &ds,datatype x)
{
nodeptr p=getnode(x);
if(ds.phead==NULL) //neu ds rong
{
ds.phead=p; //thi node p vua tao ra vua la node dau
ds.ptail=p; //vua la node cuoi
return;
}
else //neu ds co it nhat 1 ptu
{
p->next=ds.phead; //chen p vao truoc node dau
ds.phead->pre=p;
ds.phead=p; //cap nhat lai node dau bay gio la p
}
}
//ham chen them node vao sau 1 node khac
void chengiua(DSLK &ds,nodeptr p,datatype x)
{
nodeptr q,r;
if(p==NULL) //neu ds rong ta ko chen
printf("is empty!\n");
if(p==ds.phead) //neu ds chi co 1 ptu ta goi ham chen dau
chendau(ds,x);
else
{ //neu ds co hon 1ptu
q=getnode(x); //ta khoi tao 1 node moi q
p->next=q;; //dua node q vao sau node p
q->pre=p;
r->pre=q; //node r dung sau node q
q->next=r;
}
}
//ham chen vao cuoi ds
void chencuoi(DSLK &ds,datatype x)
{
nodeptr p=getnode(x); //khoi tao node moi p
if(ds.phead==NULL) //neu ds chua co ptu nao
{
ds.phead=p; //thi p dua vao vua la node dau vua la node cuoi
ds.ptail=p;
return;
} //neu ds co it nhat 1 ptu ta tien hanh chen
else
{
ds.ptail->next=p; //dua p vao sau node ptail
p->pre=ds.ptail;
ds.ptail=p; //cap nhat lai node cuoi cung bay gio la p
}
}
//ham nhap vao gia tri cho dslk
void input(DSLK &ds)
{
char *gitri;
int t;
InitDSLK(ds); //khoi tao 1 ds rong
fflush(stdin);
// printf("\nnhap vao day so nguyen can tinh:");
gets(gitri); //nhan vao 1 chuoi cac so nguyen
for(int i=0;i<strlen(gitri);i++)
{
t=gitri[i]-'0'; //t luu tru cac gia tri vua nhap vao danh dau chuoi ket thuc =0
chencuoi(ds,t); //lan luot dua t vao cuoi ds
}
}
//ham xuat ra gia tri 1 node
void show(datatype x)
{
printf("%d",x);
}
//ham xuat ra gia tri cac node trong 1 dslk
void showlist(DSLK &ds)
{
nodeptr p=ds.phead;
while(p!=NULL)
{
show(p->info);
p=p->next;
}
}
//ham cong 2 so nguyen luu trong 2 DSLK
void cong(DSLK &kqua,DSLK ds1,DSLK ds2 )
{
nodeptr p=ds1.ptail; //cho node p di tu cuoi dslk ds1
nodeptr q=ds2.ptail; //node q di tu cuoi dslk ds2
int s1,s2,sonho=0;
while(p!=NULL && q!=NULL) //trong khi di tu cuoi len ma 2 ds van con gia tri
{
s1=p->info+q->info+sonho; //cong 2 gia tri tu cuoi cua 2 day
s2=s1%10; //s2 luu gia tri chu so hang don vi
//cua s1 neu co
sonho=s1/10; //so nho bjo la so nam o hang chuc neu co;
//neu p va q la 2 gia tri dau cua 2 ds
if(p==ds1.phead&&q==ds2.phead)
{
chendau(kqua,s1); //luu gitri s1 vao dslk kqua
}
else //neu ko,tuc la ca 2 day so deu con gia tri
{
chendau(kqua,s2); //luu giatri s2 vao dslk kqua
}
p=p->pre; //p di tiep ve truoc 1 node
q=q->pre; //q di tiep ve truoc 1 node
}
while(p!=NULL) //trong khi ds1 van con gia tri
//thi ta tinh phep toan cong tuong tu chi tren ds1
{
s1=p->info+sonho;
s2=s1%10;
if(p==ds1.phead)
{
chendau(kqua,s1);
}
else
{
chendau(kqua,s2);
}
sonho=s1/10;
p=p->pre;
}
while(q!=NULL) //nguoc lai khi ds2 van con giatri
{ //thi ta tinh toan cong chi tren ds2
s1=q->info+sonho;
s2=s1%10;
if(q==ds2.phead)
{
chendau(kqua,s1);
}
else
{
chendau(kqua,s2);
}
sonho=s1/10;
q=q->pre;
} return ;
}
void nhan1(DSLK &tich,DSLK &p1,nodeptr &N)
{
int s=0;
int t;
nodeptr p;
InitDSLK (tich);
for(p=p1.ptail;p!=NULL;p=p->pre)
{
t=((p->info)*( N->info)+s);
chendau(tich,t%10);
s=s/10;
}
if(s!=0)
{
chendau(tich,s);
}
return;
}
void nhanso(DSLK &kqnhan,DSLK day1,DSLK day2)
{
DSLK tam1,tam2;
InitDSLK (tam2);
InitDSLK (tam1);
nodeptr p1,p2;
for(p2=day2.ptail;p2!=NULL;p2=p2->pre)
{
p1=day2.ptail;
nhan1(tam1,day1,p2);
while(p2!=p1)
{
chencuoi(tam1,0); //tien hanh thut lui vao hnag thu 2 de thuc hien phep cong
p2=p2->pre;
}
cong(kqnhan,tam1,tam2);
// temp=tam;
}
/* if((d1.sign*d2.sign)==1)
kqnhan.sign=1;
else
kqnhan.sign=-1;*/
}
void main()
{
DSLK ds,kqua,ds1,ds2;
DSLK day1,day2;
DSLK kqnhan;
clrscr();
printf("nhap vao day so can tinh thu 1:");
input(ds1);
printf("\nnhap vao day so can tinh thu 2:");
input(ds2);
InitDSLK (kqua);
cong(kqua,ds1,ds2);
printf("\nket qua cong 2 day so da nhap =");
showlist(kqua);
printf("\n");
printf("\nket qua nhan 2 day so da nhap la:");
nhanso(kqnhan,day1,day2);
showlist(kqnhan);
getch();
}
Xin mời các bạn đóng góp ý kiến xây dựng.
Labels:
Học tập
