线性链表的实现及操作.doc

《线性链表的实现及操作.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《数据结构》实验报告学生姓名学生班级学生学号指导老师一．实验内容1、设计一个100位以内的长整数加减运算的程序。要求如下：输入输出要求：每四位一组，组间用逗号分隔；加和减分别用不同的程序实现程序应考虑输入数据的符号2、用循环链表实现约瑟夫环问题二、需求分析1、使用链表进行超长数据的储存，减法时需要判断减数与被减数的长短关系，再进行对比与运算。在链表前一个节点进行加减来代替进位操作（每个节点数据满十即在前一个节点加一）。使用if(ch>='0'&&ch<='9')语句确保链表中只存放数字。2、建立链表，输入数据，循环输出同时删除节点。三、概

2、要设计1、创建链表储存数据，每个节点存一位，过滤非数字字符如‘，’。调整最高位数字的正负来代表整串数字的正负。进位操作是在前一个节点进行加减。2、创建链表储存数据，设计循环输出并删除节点。四、详细设计1.得到两个链表Number*GetNumber(){Number*p,*q,*List;charch;p=(Number*)malloc(LEN);List=p;List->prior=NULL;List->data=0;//加法时，放最高位进的1，否者999+1=000ch=getchar();while(ch!=''){if(ch>

3、='0'&&ch<='9')//过滤非数字字符{q=(Number*)malloc(LEN);q->data=ch-'0';p->next=q;q->prior=p;p=q;}ch=getchar();}p->next=NULL;List->prior=NULL;returnList;}2.加法分两种情况长度相同与不同Number*JiaFa(Number*num_1,Number*num_2)//返回的数据为逆序{Number*p,*q,*r,*s,*num=NULL;inti=0,j=0;r=num;p=num_1;while(p->

4、next!=NULL){i++;p=p->next;}//i表示number1数字的长度p指向number节点q=num_2;while(q->next!=NULL){j++;q=q->next;}//j表示number2数字的长度q指向number节点s=(Number*)malloc(LEN);s->prior=NULL;s->next=NULL;num=s;while(i--&&j--){s->data=p->data+q->data;if(s->data>9){s->data-=10;//处理两数相加大于9的情况，后面还有if(i

5、>j)//在长的数据上调整p->prior->data++;elseq->prior->data++;}r=(Number*)malloc(LEN);s->next=r;r->prior=s;s=r;p=p->prior;q=q->prior;}r=s=s->prior;//去掉最后一个没数据的节点free(s->next);s->next=NULL;if(i>j){while(i--){if(p->data>9){p->data-=10;p->prior->data++;}s=(Number*)malloc(LEN);s->data=p

6、->data;p=p->prior;r->next=s;s->prior=r;r=s;}if(p->data>0){s=(Number*)malloc(LEN);s->data=p->data;r->next=s;s->prior=r;r=s;}}else{while(j--){if(q->data>9){q->data-=10;q->prior->data++;}s=(Number*)malloc(LEN);s->data=q->data;q=q->prior;r->next=s;s->prior=r;r=s;}if(q->data>0

7、){s=(Number*)malloc(LEN);s->data=q->data;r->next=s;s->prior=r;r=s;}}s->next=NULL;//将最后一个next置空returnnum;}3.减法分3中情况：被减数长度大于、小于、等于减数长度Number*JianFa(Number*num_1,Number*num_2)//返回的数据也为逆序{Number*p,*q,*r,*s,*num=NULL;inti=0,j=0;r=num;p=num_1;while(p->next!=NULL)//i表示number1数字的

8、长度p指向number节点{i++;p=p->next;}q=num_2;while(q->next!=NULL)//j表示number2数字的长度q指向number节点{j++;q=q->n