Question

设计一个数据结构可存储任意长整数

要求：
1、对输入的数据进行合法性检查
2、输出形式：每四位为一组，组间用逗号隔开
3、设计的数据结构应有利于任意长整数的运算
高手请进，他人勿扰。用C/C++编写程序
TO PcrazyC :
有一点不知可否修改，就是将输入数据的格式变为
data1<空格>data2<回车> 即可输出结果，而不用分号。
(另有一关于二叉树的，我将在中午提问，还请赐教。)

Answer 1

这个可以啊,定义两个字符串,接受输入数据后,对字符串进行处理,从后面开始,每4位一组进行储存,插入到链表中的就改成插在最前面,因为前面的是高位

用一个双向链表就可以了,下面的头文件就是你需要的部分,主程序只是对其中加法的一个实现,其它的运算,你自己写

头文件(DLNODE.H)

#include<stdlib.h>

typedef int DataType;
typedef struct DoubleNode //定义链表元素
{
DataType data;
struct DoubleNode *prior;
struct DoubleNode *next;
}DLNode;

void InitNode(DLNode **head) //初始化链表
{
if((*head=(DLNode*)malloc(sizeof(DLNode)))==NULL)
exit(1);
(*head)->prior=*head;
(*head)->next=*head;
}

int InsertNode(DLNode *head,int n,DataType x) //向链表第N个位置插入元素X
{
DLNode *p,*nt;
int i=0;
p=head->next;
while(p!=head&&i<n)
{
p=p->next;
i++;
}
if(i!=n)
{
printf("插入位置错误\n");
return 0;
}
if((nt=(DLNode *)malloc(sizeof(DLNode)))==NULL)
exit(1);
nt->data=x;
nt->prior=p->prior;
nt->prior->next=nt;
nt->next=p;
p->prior=nt;
return 1;
}

int digit(int n) //判断整数N有几位
{
int i;
for(i=1;;n/=10,i++)
{
if(n/10==0)
return i;
}
}

void PrintNode(DLNode *head) //打印链表
{
DLNode *p=head->next;
int i;
while(p->data==0) //去掉前面的一串0
{
p=p->next;
if(p==head)
{
printf("0\n");
return;
}
}
printf("%d",p->data); //最前面的一个数进行特殊处理,不用补零
p=p->next;
while(p!=head) //打印后面的数字
{
printf(",");
if(p->data==0)
{
printf("0000");
p=p->next;
continue;
}
for(i=0;i<4-digit(p->data);i++) //补零
printf("0");
printf("%d",p->data);
p=p->next;
}
printf("\n");
}

void DestroyNode(DLNode **head)
{
DLNode *p,*p1;
p=(*head)->next;
while(p!=*head)
{
p1=p;
p=p->next;
free(p1);
}
free(p);
head=NULL;
}

主程序(.CPP文件)

/*****************************************************

由于计算机所提供的数据类型其范围和有效数字太少,处理比较大的数时非常不精确,下面我们用
双向链表作来处理大整数的加法,还可以用来处理乘法除法之类的,在这就不说了.

*****************************************************/
#include<stdio.h>
#include"DLNode.h"
#include<string.h>
#include<stdlib.h>
#include<math.h>

#define N 100

void plus(DLNode *h1,DLNode *h2) //两数相加
{
DLNode *p1=h1->prior,*p2=h2->prior;
while(p1!=h1&&p2!=h2) //每个链表元素相加
{
p1->data+=p2->data ;
p1=p1->prior;
p2=p2->prior;
}
p1=h1->prior;
while(p1!=h1->next) //处理链表元素
{
if(p1->data>=10000)
{
p1->prior->data+=p1->data/10000;
p1->data%=10000;
}
if(p1->data<0) //处理负数
{
if(h1->next!=0)
{
p1->prior->data-=1;
p1->data+=10000;
}
}
p1=p1->prior;
}

if(h1->next->data>=10000) //处理最前面的数
{
InsertNode(h1,0,h1->next->data/10000);
h1->next->next->data%=10000;
}
if(h1->data<=-10000)
{
InsertNode(h1,0,h1->next->data/10000);
h1->next->next->data%=-10000;
}
PrintNode(h1);
}

int main() //入口函数
{
DLNode *head1,*head2;
InitNode(&head1);
InitNode(&head2);
char data1[N],data2[N];
char d1[10],d2[10];
int i,j,k;
while(scanf("%s %s",data1,data2))
{
InitNode(&head1);
InitNode(&head2);
i=0;k=0;
while(data1[i]!=';') //将数1用链表储存
{
for(j=0;j<10;j++)
d1[j]=0;
j=0;
while(data1[i]!=';'&&data1[i]!=',')
d1[j++]=data1[i++];
if(data1[i]==',')
i++;
if(data1[0]=='-') //处理正负数
j=-(int)fabs(atoi(d1));
else
j=atoi(d1);
InsertNode(head1,k++,j);
}

i=0;
k=0;
while(data2[i]!=';') //将数2用链表储存
{
for(j=0;j<10;j++)
d2[j]=0;
j=0;
while(data2[i]!=';'&&data2[i]!=',')
d2[j++]=data2[i++];
if(data2[i]==',')
i++;
if(data2[0]=='-') //处理正负数
j=-(int)fabs(atoi(d2));
else
j=atoi(d2);
InsertNode(head2,k++,j);
}
if(strlen(data1)>strlen(data2)) //较长的数作为被加数
plus(head1,head2);
else
plus(head2,head1);
DestroyNode(&head1);
DestroyNode(&head2);
}

return 0;
}

/************************************************************

基本算法:

将一个大的整数分解成若干部分,每四位一部分,分别储存在链表的每个元素中.
正数直接储存进去,而负数全部转换为负数然后储存进去. 然后从最后一个元素
开始,对应相加,直到有一个链表的数据元素处理完为止.在相加的过程中,两个四
位数相加有可能会出现五位数,正数和负数相加有可能会正负不一的情况,这些情
况都要进行处理.另个在打印的时候对一些少于四位数的也要进行一下处理.

测试数据:(数据以逗号分组,以分号结束,两个数字之间用空格分开)

0; 0;
0
-2345,6789; -7654,3211;
-1,0000,0000;
-9999,9999; 1,0000,0000,0000;
9999,0000,0001;
1,0001,0001; -1,0001,0001;
0
1,0001,0001; -1,0001,0000;
1;
1234,5648,2345,6217; 5689,7565,3245,3576;
6924,3213,5590,9793;
9999,9999,9999,9999; 1,0000,0000,0000,00001;
2,0000,0000,0000,0000;

************************************************************/

Answer 2

#include <stdio.h>
#include <malloc.h>
#define NULL 0
#define LEN sizeof(struct student)
struct student
{
int num;
int score;
struct student *next;
};
int n;
struct student *create(void)
{
struct student *head,*p1,*p2;
p1=(struct student *)malloc(LEN);
p2=p1;
printf("Qing ni shu ru shu ju :\n");
scanf("%d%d",&p1->num,&p1->score);
head=NULL;
n=0;
while(p1->num!=0)
{
n++;
if(n==1)
head=p1;
else
p2->next=p1;
p2=p1;
p1=(struct student *)malloc(LEN);
printf("Qing ni shu ru shu ju :\n");
scanf("%d%d",&p1->num,&p1->score);
}
p2->next=NULL;
return head;
}

void print(struct student *head)
{
struct student *p;
p=head;
while(p!=NULL)
{
printf("%d\t%d\n",p->num,p->score);
p=p->next;
}
}
struct student *del(struct student *head,int num)
{
struct student *p1,*p2;
p1=head;
while(p1->num!=num && p1->next!=NULL)
{
p2=p1;
p1=p1->next;
}
if(p1->num==num)
{
if(head==p1)
head=p1->next;
else
p2->next=p1->next;
}
return head;
}

struct student *insert(struct student *head,struct student *stud)
{
struct student *p1,*p2;
p1=head;
if(head==NULL)
{
head=stud;
stud->next=NULL;
}
else
{
while(p1->num < stud->num && p1->next!=NULL)
{
p2=p1;
p1=p1->next;
}
if(p1->num>stud->num)
{
if(head==p1)
head=stud;
else
p2->next=stud;
stud->next=p1;
}
else
{
p1->next=stud;
stud->next=NULL;
}
}
n++;
return head;
}
main()
{
struct student *head;
struct student ss,*pp;
int num;
head=create();
print(head);
printf("Qing shu ru yao shan chu de jie dian:\n");
scanf("%d",&num);
head=del(head,num);
print(head);

printf("qing shu ru yao cha ru de shu ju:\n");
scanf("%d%d",&ss.num,&ss.score);
pp=&ss;
head=insert(head,pp);
print(head);
}