|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 |
/*YÊU CẦU:======================================================================================================================= ** Để lưu trữ một số nguyên lớn, ta có thể dùng danh sách liên kết chứa các chữ số của nó. ** Hãy tìm cách lưu trữ các chữ số của một số nguyên lớn theo ý tưởng trên sao cho việc cộng hai số nguyên lớn là dễ thực hiện. ** Viết chương trình cộng hai số nguyên lớn **==============================================================================================================================*/ /*Ý TƯỞNG GIẢI QUYẾT:============================================================================================================= ** Sử dụng 2 danh sách liên kết để biểu diễn cho 2 số nguyên. ** Trong đó mỗi một node trong danh sách biểu diễn cho 1 chữ số của số nguyên theo chiều đảo. ** Ví dụ số 1234 thì danh sách liên kết sẽ lưu trữ là [(root)-4]->[3]->[2]->[1] ** Tiến hành thực hiện cộng tay rồi in kết quả ra từng ký tự: ** 1234 ** + 3 ** ---- * 1237 **==============================================================================================================================*/ #include <stdio.h> #include <stdlib.h> #include <conio.h> #include <iostream.h> #include <string.h> //ĐỊNH NGHĨA CẤU TRÚC NODE typedef struct Node { int data; Node* next; } NodeType; //HÀM THÊM 1 GIÁ TRỊ (VALUE) VÀO DANH SÁCH void Insert( NodeType* &root, int value ) { if(root==NULL) { NodeType* newnode = (NodeType*)malloc( sizeof( NodeType ) ); newnode->next = NULL; newnode->data = value; root=newnode; //printf("1-%d; ",value); } else { NodeType* P=root; while(P->next!=NULL) { P=P->next; } NodeType* newnode = (NodeType*)malloc( sizeof( NodeType ) ); newnode->next = NULL; newnode->data = value; P->next=newnode; //printf("2-%d; ",value); } } void PrintList(NodeType* &root) { NodeType* P=root; while(P!=NULL) { cout<<P->data<<endl; P=P->next; } } void InTong(NodeType* &SoA, NodeType* &SoB,const int maxlen) { int ketqua[100]; NodeType* P1=SoA; NodeType* P2=SoB; int sonho=0; int continunei=0; for(int i=0;i<maxlen;i++) { int a=0; int b=0; int tong=0; if(P1!=NULL) { a=P1->data; } if(P2!=NULL) { b=P2->data; } tong=a+b+sonho; if(tong>=10) { sonho=(int)tong/10; tong=tong%10; } else { sonho=0; } //cout<<tong; ketqua[i]=tong; if(P1!=NULL) { P1=P1->next; } if(P2!=NULL) { P2=P2->next; } continunei=i; } if(sonho>0) { //cout<<sonho; continunei=continunei+1; ketqua[continunei]=sonho; } //cout<<"continunei="<<continunei<<endl; for(int y=continunei;y>=0; y--) { cout<<ketqua[y]; } } int main() { printf("===CHUONG TRINH CONG HAI SO NGUYEN CO NHIEU CHU SO [UNG DUNG DANH SACH LIEN KET]==="); NodeType* Songuyen1 = NULL; //Khởi tạo cây chứa các chữ số của số nguyên thứ nhất NodeType* Songuyen2 = NULL; //Khởi tạo cây chứa các chữ số của số nguyên thứ hai clrscr(); char sothu1[100],sothu2[100]; printf("Nhap so thu 1: "); scanf("%s",&sothu1); int i=0; int len1=strlen(sothu1); //printf("\nDo dai so thu 1: %d",len1); for(i=len1-1;i>=0;i--) { int so=(int)sothu1[i]-48; Insert(Songuyen1,so); } //printf("List so thu 1: \n"); //PrintList(Songuyen1); printf("Nhap so thu 2: "); scanf("%s",&sothu2); i=0; int len2=strlen(sothu2); //printf("\nDo dai so thu 2: %d",len2); for(i=len2-1;i>=0;i--) { int so=(int)sothu2[i]-48; Insert(Songuyen2,so); } //printf("List so thu 2: \n"); //PrintList(Songuyen2); int maxlen=0; if(len1>len2) { maxlen=len1; } else { maxlen=len2; } cout<<sothu1<<" + "<<sothu2<<" = "; InTong(Songuyen1,Songuyen2,maxlen); getch(); return 0; } |