在头插法中,我们就是将一个个结点在表头后的第一个元素处插入,这么说吧,我们插入结点的位置就只是在表头后的第一个结点处。在这里,我们先是处理1+1=2的结点放到了C的第一个结点处,接着就是0+1=1的结点放到了C的第一个结点处,那么之前的那个2的结点呢?它在现在插入的1的结点后面。因此,我们一旦输出C的整个链表的值就是我们要求的和的值了。下面就是处理进位了,这个怎么实现呢?我们将进位与存入的整数的位数一起考虑。在这里要注意,如果位数的相加处理完了,可是还是进位没有处理怎么办?因此,我们需要一个if语句来处理这种情况!
在这里,我们最需要考虑的就是进位与位数的问题,正如上面说的,我们利用if语句来判断。如果满足条件,我们将多余的位数的结点赋给另外一个结点,然后在处理。主要的代码:
if (pa->next!=NULL)
{
p=pa->next;
}
if (pb->next!=NULL)
{
p=pb->next;
}
while (p!=NULL||carry==1)
{
pc=(LinkList)malloc(sizeof(LinkList)*10);
pc->data=0;
if (carry==1)
{
pc->data+=carry;
carry=0;
}
if (p!=NULL)
{
pc->data+=p->data+carry;
carry=0;
if (pc->data>=10)
{
carry=pc->data/10;
pc->data=pc->data%10;
}
p=p->next;
}
pc->next=C->next;
C->next=pc;
}
首先是两个if语句来判断是否还是位数没有相加,如果没有,我们就将其赋值给一个结点。然后就是while循环,while就是完成进位的判断以及位数剩余的判断。如果,位数相同,但是还有进位1,那么我们就是一个结点pc来存储这个进位的值,同时将进位赋值0.如果有进位又有位数剩余,那么我们就得再重新思考。我们用pc的data域来存储进位1,然后再将位数有多的结点的data也加到pc的data域里,不过我们在data域里还是要加上carry,以防位数相差两位而两位同时有进位。对于整个程序的分析,我说的或许比较难懂。因此,就需要你看懂程序了。
先看看实现:
完整的代码:
#include "windows.h"
#include "iostream"
#include "stdio.h"
using namespace std;
int len;
typedef struct node{
int data;
struct node *next;
}*LinkList, ListNode;
LinkList InitList()
{
LinkList H;
H=(LinkList)malloc(sizeof(LinkList)*100);
if(H==NULL)
{
exit(-1);
}
H->next=NULL;//创建有头结点的空链表
return H;
}
int InsertList(LinkList head, int i, int e)//在第i-1的位置插入结点
{
LinkList p,pre;
int j=0;
pre=head;
while(pre->next!=NULL && j<i-1)//找到前驱结点
{
pre=pre->next;
j++;
}
if(j!=i-1)
{
cout<<"插入出错!"<<endl;
}
p=(LinkList)malloc(sizeof(LinkList));
p->data=e;//以上这两句构造一个实实在在的结点
//插入操作
p->next=pre->next;
pre->next=p;
return 0;
}
int Length_List(LinkList head)
{
LinkList p;
p=head->next;
int index=0;
while(p)
{
index++;
p=p->next;
}
return index;
}
LinkList GetList(LinkList head,int i)
{
LinkList p;
int j=0;
p=head;
while(p->next &&j!=i)
{
j++;
p=p->next;
}
if(j==i)
{
return p;
}
else
{
return NULL;
}
}
void Add(LinkList A,LinkList B)
{
LinkList p=NULL,C,l;
ListNode *pa, *pb, *pc;
pa=A;
pb=B;
C=(LinkList)malloc(sizeof(LinkList)*100);
C->next=NULL;//生成头结点
int carry=0;
while (pa->next!=NULL&&pb->next!=NULL)
{
pa=pa->next;
pb=pb->next;
pc=(LinkList)malloc(sizeof(LinkList)*10);
pc->data=(pa->data+pb->data+carry)%10;//个位值
carry=(pa->data+pb->data+carry)/10;//判断进位
pc->next=C->next;
C->next=pc;
}
if (pa->next!=NULL)
{
p=pa->next;
}
if (pb->next!=NULL)
{
p=pb->next;
}
while (p!=NULL||carry==1)
{
pc=(LinkList)malloc(sizeof(LinkList)*10);
pc->data=0;
if (carry==1)
{
pc->data+=carry;
carry=0;
}
if (p!=NULL)
{
pc->data+=p->data+carry;
carry=0;
if (pc->data>=10)
{
carry=pc->data/10;
pc->data=pc->data%10;
}
p=p->next;
}
pc->next=C->next;
C->next=pc;
}
for(int i=1; i<=Length_List(C); i++)
{
l=GetList(C,i);
cout<<l->data;
}
cout<<endl;
}
int main()
{
LinkList L,p,M,C;
L=InitList();
M=InitList();
int a[10];
int b[10];
int k;
int n;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
scanf("%d",&n);
for(int i=0; i<n; i++)
{
scanf("%d",&a[i]);
}
scanf("%d",&k);
for(int i=0; i<k; i++)
{
scanf("%d",&b[i]);
}
for(int i=1; i<=n; i++)
{
InsertList(L,i,a[i-1]);
}
for(int i=1; i<=k; i++)
{
InsertList(M,i,b[i-1]);
}
Add(L,M);
system("pause");
return 0;
}
这个算法实现花了我很大的力气,大概两天才做出来了,不得不承认,我的算法能力还是很差。还得好好练!