add1.c

我的数据结构的课程设计

#include<stdio.h>

#include<malloc.h>
typedef   struct  linknode
{int  data;/*节点的值*/
struct   linknode  *left,*right;
/*左指针和右指针*/
}dnode;


dnode *r1,*r2,*r3,*head1,*head2,*head3;
dnode *head_temp,*rear_temp;
/*head1为第1个数的头指针，r1为 为第1个的尾指针*/
/*head2为第2个数的头指针，r2为 为第2个的尾指针*/
/*head3为结果的头指针，r3为结果的尾指针*/
/*head_temp为临时数的头指针，rear_temp为临时数的尾指针*/



/*产生一个长整数*/
dnode* creat()
{dnode  *head,*p,*s;
/*head为头指针，p和s为临时指针*/
int  x,cycle=1;
/*x为输入的数据，cycle为是否继续输入的标志*/
head=(dnode*)malloc(sizeof(dnode));
p=head;
/*指向头*/
while(cycle)
{scanf("%d",&x);
/*输入数据*/
if(x>=0)/*输入正数才有效*/
{s=(dnode*)malloc(sizeof(dnode));
s->data=x;
p->right=s;
s->left=p;
p=s;
/*采用的是头插法*/
}
else  cycle=0;
/*输入负数就退出*/
}
head=head->right;
/*第一个头没有用到*/
head->left=NULL;
p->right=NULL;
return  head;
}

dnode  *rear(dnode  *head)
/*根据一个数的头节点，得到尾节点，并得到这个数的段数*/
{dnode  *p;
p=head;
while(p->right)
/*向右移*/
      p=p->right;
return  p;
}







void input_and_init()
/*初始化2个数据的大小*/
{
/*符号变为对应的0或1*/
printf("input  the   first  data,input  negative  data  exit\n");
 head1=creat();
 /*产生第一个数，得到它的头指针*/
 r1=rear(head1);
 /*得到第一个数的尾指针和*/


/*符号变为对应的0或1*/
 printf("input  the  second  data,input  negative  data  exit\n");
 head2=creat();
 /*产生第2个数，得到它的头指针*/
 r2=rear(head2);
 /*得到第一个数的尾指针和段数*/
}

/*打印一个数*/
void  print(int  data)
{if(data>=1000)
/*含有4个数字*/
   printf("%d",data);
else if(data>=100)
/*含有3个数字，补1个零*/
  printf("0%d",data);
else  if(data>=10)
/*含有2个数字，补2个零*/
 printf("00%d",data);
else
/*含有1个数字，补3个零*/
 printf("000%d",data);
}

/*显示一个结果的长整数，从后向前移*/
void  display(dnode *rear)
{dnode *p;
 p=rear;
while(p)
{print(p->data);
 printf(" ");
 p=p->left;
 /*向左移*/
}
printf("\n");
}


dnode  *find_sum2(dnode  *r1,dnode  *r2)
/*得到2个正数的和*/
{dnode  *head,*p,*s,*p1,*p2;
/*head为头指针，p,s为临时指针，p1指向第1个数并向左移动，p2指向第2个数并并向左移动*/
 int  inc=0,sum=0,f1=0,f2=0;
/*inc为进位，sum为和，f1为第一个数是否结束，f2为第一个数是否结束*/
head=(dnode*)malloc(sizeof(dnode));
p=head;
/*开辟空间*/

p1=r1;/*指向第一个数的尾*/
p2=r2;/*指向第二个数的尾*/


while(p1!=NULL&&p2!=NULL)
/*2个数的某一段都不为空时 */
{sum=p1->data+p2->data+inc;
/*和为2个数之和加进位*/
inc=0;
/* 进位回0*/
if(sum>=10000)
/*当超过2位数的大小时，和减去10000，并进位*/
{sum=sum-10000;
inc=1;
}
/*用头插法建立一个新的节点*/
s=(dnode*)malloc(sizeof(dnode));
s->data=sum;
p->right=s;
s->left=p;
p=s;

/*2个数都向左移*/
p1=p1->left;
p2=p2->left;
}

if(p1==NULL&&p2==NULL)
if(inc==1)
/*当2个数据都完了，但是存在进位时，新建一个节点，值就是进位*/
{s=(dnode*)malloc(sizeof(dnode));
 s->data=1;
p->right=s;
s->left=p;
p=s;
}


while(p1!=NULL)
/*当第2个数空，第1个数不为空时，将第一个数剩下的全用新节点产生*/
{f1=1;
s=(dnode*)malloc(sizeof(dnode));
sum=p1->data+inc;
inc=0;
if(sum>=10000)
{sum=sum-10000;
inc=1;
}
s->data=sum;
p->right=s;
s->left=p;
p=s;
/*第1个数都向左移*/
p1=p1->left;
}

/*当第1个数据完了，但是存在进位时，新建一个节点，值就是进位*/
if(f1==1&&inc==1&&!p1)
{
s=(dnode*)malloc(sizeof(dnode));
s->data=1;
p->right=s;
s->left=p;
p=s;
}



/*当第1个数空，第2个数不为空时，将第一个数剩下的全用新节点产生*/
while(p2!=NULL)
{f2=1;
s=(dnode*)malloc(sizeof(dnode));
sum=p2->data+inc;
inc=0;
if(sum>=10000)
{sum=sum-10000;
inc=1;
}
s->data=sum;
p->right=s;
s->left=p;
p=s;
p2=p2->left;
/*第2个数都向左移*/
}



/*当第2个数据完了，但是存在进位时，新建一个节点，值就是进位*/
if(f2==1&&inc==1)
{s=(dnode*)malloc(sizeof(dnode));
s->data=1;
p->right=s;
s->left=p;
p=s;
}


head=head->right;
head->left=NULL;
p->right=NULL;
return  head;
/*返回头节点*/
}

dnode * find_sub_mult(dnode * r1,int  data ,int  i)
/*将r1指向的数全乘于data，并向左位移i段*/
{dnode *head,*p,*s,*rr;
/*head为头指针，p,s为临时指针，rr为尾指针*/
int  k,inc=0;
/*k为循环用的，inc为进位*/
long  sum=0; 
/*求和*/

rr=r1;
head=(dnode*)malloc(sizeof(dnode));
p=head;
/*开辟空间*/

/*先将需要位移的段数全用0补齐*/
if(i!=0)
{for(k=1;k<=i;k++)
{
s=(dnode*)malloc(sizeof(dnode));
s->data=0;
p->right=s;
s->left=p;
p=s;
}
}

while(rr!=NULL)
/* 当rr没有到头时*/
{s=(dnode*)malloc(sizeof(dnode));
sum=rr->data*data+inc;
if(sum>10000)
{inc=sum/10000;
/*得到和的高4位*/
s->data=sum-inc*10000;
/*值为低4位的值*/
} 
else
{s->data=sum;
/*直接给值*/
inc=0;
}
p->right=s;
s->left=p;
p=s;
/*左移*/
rr=rr->left;
}


if(inc!=0)
/*如果还有进位，就需要新建一个节点*/
{
s=(dnode*)malloc(sizeof(dnode));
s->data=inc;
p->right=s;
s->left=p;
p=s;
}

head=head->right;
head->left=NULL;
p->right=NULL;
/*返回头指针*/
return  head;
}




/*由一个数的尾指针得到头指针*/
dnode * return_head(dnode *rear)
{
dnode *p;
p=rear;
while(p->left)
p=p->left;
return  p;
}

/*由一个数的头指针得到尾指针*/
dnode * return_rear(dnode *head)
{
dnode *p;
p=head;
while(p->right)
p=p->right;
return  p;
}



/*将一个数的数据前后交换*/
dnode * tansfer_rear2(dnode *rear_temp)
{dnode *head,*p,*s,*rear;
rear=rear_temp;
head=(dnode*)malloc(sizeof(dnode));
p=head;
while(rear!=NULL)
/*将后面的节点向左一个一个用头插法建立，就和原来相反了*/
{s=(dnode*)malloc(sizeof(dnode));
s->data=rear->data;
p->right=s;
s->left=p;
p=s;
rear=rear->left;
}
head=head->right;
head->left=NULL;
p->right=NULL;
return p;
}

/*2个数相乘，将第1个数乘于第2个数的每一段，要进行响应的移位处理，得到一系列的数，再相加*/
void multy(dnode  *r1,dnode  *r2)
{dnode  * p;int i=0,flag=0;
p=r2;
while(p!=NULL)
{head_temp=find_sub_mult(r1,p->data,i);
/*将r1中所有的数乘于p->data，并向左位移i段*/
 rear_temp=return_rear(head_temp);
 /*得到尾*/
 rear_temp=tansfer_rear2(rear_temp);
 /*求反*/
if(flag==0)
/*如果是第一个段，直接给r3*/
{r3=rear_temp;
flag=1;
}
else 
{
/*如果不是第一个段，将r3和当前的结果相加*/
head3=find_sum2(r3,rear_temp);
r3=return_rear(head3);
r3=tansfer_rear2(r3);
}

i++;
/*需要位移的段数增加*/

/*p左移*/
p=p->left;
}
r3=tansfer_rear2(r3);
/*交换*/
display(r3);
/*显示最后结果*/
}










void  main()
{

input_and_init();


multy(r1,r2);


getchar();

}