线性链表的实现及操作

1、.数据结构实验报告学生姓名学生班级学生学号指导老师；.一实验内容1、设计一个100位以内的长整数加减运算的程序。要求如下： 输入输出要求：每四位一组，组间用逗号分隔； 加和减分别用不同的程序实现 程序应考虑输入数据的符号 2、用循环链表实现约瑟夫环问题二、 需求分析1、使用链表进行超长数据的储存，减法时需要判断减数与被减数的长短关系，再进行对比与运算。在链表前一个节点进行加减来代替进位操作（每个节点数据满十即在前一个节点加一）。使用if(ch=0&chprior=NULL;List-data=0;/加法时，放最高位进的1，否者 999+1=000ch=getchar();while(ch!=n

2、)if(ch=0&chdata=ch-0;p-next=q;q-prior=p;p=q;ch=getchar();p-next=NULL;List-prior=NULL;return List;2. 加法分两种情况长度相同与不同Number *JiaFa(Number *num_1,Number *num_2) /返回的数据为逆序Number *p,*q,*r,*s,*num=NULL;int i=0,j=0;r=num;p=num_1;while(p-next!=NULL)i+;p=p-next;/i表示number1数字的长度 p指向number节点q=num_2;while(q-next

3、!=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-data9)s-data-=10;/处理两数相加大于9的情况，后面还有if(ij)/在长的数据上调整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

4、;/去掉最后一个没数据的节点free(s-next);s-next=NULL;if(ij)while(i-)if(p-data9)p-data-=10;p-prior-data+;s=(Number *)malloc(LEN);s-data=p-data;p=p-prior;r-next=s;s-prior=r;r=s;if(p-data0)s=(Number *)malloc(LEN);s-data=p-data;r-next=s;s-prior=r;r=s;elsewhile(j-)if(q-data9)q-data-=10;q-prior-data+;s=(Number *)malloc

5、(LEN);s-data=q-data;q=q-prior;r-next=s;s-prior=r;r=s;if(q-data0)s=(Number *)malloc(LEN);s-data=q-data;r-next=s;s-prior=r;r=s;s-next=NULL;/将最后一个next置空return num;3. 减法分3中情况：被减数长度大于、小于、等于减数长度Number *JianFa(Number *num_1,Number *num_2) /返回的数据也为逆序Number *p,*q,*r,*s,*num=NULL;int i=0,j=0;r=num;p=num_1;whi

6、le(p-next!=NULL)/i表示number1数字的长度 p指向number节点i+;p=p-next;q=num_2;while(q-next!=NULL)/j表示number2数字的长度 q指向number节点j+;q=q-next;s=(Number *)malloc(LEN);s-prior=NULL;s-next=NULL;num=s;if(idata=q-data-p-data;if(s-datadata+=10;q-prior-data-;r=(Number *)malloc(LEN);s-next=r;r-prior=s;s=r;p=p-prior;q=q-prior;

7、j-;/使i，j同时变化r=s=s-prior;/去掉最后一个没数据的节点free(s-next);s-next=NULL;while(j-)if(q-datadata+=10;q-prior-data-;s=(Number *)malloc(LEN);s-data=q-data;q=q-prior;r-next=s;s-prior=r;r=s;s-data=0-s-data;/反号，因为节点里不能放符号，而直接在最高位前加负号最简单s-next=NULL;elseif(i=j)i=j=1;p=num_1;q=num_2;while(p-data=q-data)p=p-next;q=q-nex

8、t;num_1=(Number *)malloc(LEN);num_1-prior=NULL;num_1-data=0;num_1-next=p;num_2=(Number *)malloc(LEN);num_2-prior=NULL;num_2-data=0;num_2-next=q;while(p-next!=NULL)/i表示number1数字的长度 p指向number节点i+;p=p-next;q=num_2;while(q-next!=NULL)/j表示number2数字的长度 q指向number节点j+;q=q-next;if(num_1-next-datanum_2-next-d

9、ata)while(i-)s-data=p-data-q-data;if(s-datadata+=10;p-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);while(s-data=0&s-prior!=NULL)/去掉前面多余的0，否则111112-111111=000001s=s-prior;free(s-next);if(num_1-next-datanext-data)while(i-)s-data=q

10、-data-p-data;if(s-datadata+=10;q-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);while(s-data=0&s-prior!=NULL)/去掉前面多余的0，否则111112-111111=000001s=s-prior;free(s-next);s-data=0-s-data;/反号，因为节点里不能放符号，而直接在最高位前加负号最简单s-next=NULL;elseif(ij

11、)while(j-)s-data=p-data-q-data;if(s-datadata+=10;p-prior-data-;r=(Number *)malloc(LEN);s-next=r;r-prior=s;s=r;p=p-prior;q=q-prior;i-;r=s=s-prior;/去掉最后一个没数据的节点free(s-next);s-next=NULL;while(i-)if(p-datadata+=10;p-prior-data-;s=(Number *)malloc(LEN);s-data=p-data;p=p-prior;r-next=s;s-prior=r;r=s;while

12、(s-data=0&s-prior!=NULL)/去掉前面多余的0，否则1000-1=0999s=s-prior;free(s-next);/s-data=0-s-data;/反号，因为节点里不能放符号，而直接在最高位前加负号最简单s-next=NULL;return num;4. 链表的合并void PutNumber(Number *num) /链表的合并Number *p;int k=1,i;/k为数据长度，i控制,p=num;while(p-next!=NULL)p=p-next;k+;i=4-k%4;while(k-)i+;printf(%d,p-data);p=p-prior;if

13、(k!=0&i%4=0)/长度为k的数据，在k%4个数字后开始输出,数据输出完后不输出,putchar(,);putchar(n);五、 遇到的问题及解决方法问题：对getchar函数运用不熟练心得体会熟悉了链表及一些库函数，一定程度上锻炼了对复杂函数的解决能力。附录：全部代码：100位以内的长整数加减运算的源代码：#include#include#define LEN sizeof(Number)typedef struct number Number;struct numberint data;Number *next;Number *prior;void main()void Desto

14、ryList(Number *);/释放链表void PutNumber(Number *);/将求得的结果输出Number *GetNumber();/创建链表，放被加数与加数Number *JiaFa(Number *num_1,Number *num_2);/加法函数Number *JianFa(Number *num_1,Number *num_2);/减法函数Number *number_1,*number_2,*number;char ch;/存放运算符号printf(Enter the first long number:n);number_1=GetNumber();print

15、f(put +or-:n);ch=getchar();fflush(stdin);/吸收不相关的字符printf(Enter the second long number:n);number_2=GetNumber();if(ch=+)number=JiaFa(number_1,number_2);elseif(ch=-)number=JianFa(number_1,number_2);printf(=n);PutNumber(number);DestoryList(number);DestoryList(number_1);DestoryList(number_2);Number *GetN

16、umber() /得到两个链表Number *p,*q,*List;char ch;p=(Number *)malloc(LEN);List=p;List-prior=NULL;List-data=0;/加法时，放最高位进的1，否者 999+1=000ch=getchar();while(ch!=n)if(ch=0&chdata=ch-0;p-next=q;q-prior=p;p=q;ch=getchar();p-next=NULL;List-prior=NULL;return List; /加法分两种情况长度相同与不同Number *JiaFa(Number *num_1,Number *n

17、um_2) /返回的数据为逆序Number *p,*q,*r,*s,*num=NULL;int i=0,j=0;r=num;p=num_1;while(p-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-data9)s-dat

18、a-=10;/*处理两数相加大于9的情况，后面还有if(ij)/在长的数据上调整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(ij)while(i-)if(p-data9)p-data-=10;p-prior-data+;s=(Number *)malloc(LEN);s-data=p-data;p=p-prior;r-next=s;s-p

19、rior=r;r=s;if(p-data0)s=(Number *)malloc(LEN);s-data=p-data;r-next=s;s-prior=r;r=s;elsewhile(j-)if(q-data9)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-data0)s=(Number *)malloc(LEN);s-data=q-data;r-next=s;s-prior=r;r=s;s-next=NULL;/将最后一个next置空r

20、eturn num; /减法分3中情况：被减数长度大于、小于、等于减数长度Number *JianFa(Number *num_1,Number *num_2) /返回的数据也为逆序Number *p,*q,*r,*s,*num=NULL;int i=0,j=0;r=num;p=num_1;while(p-next!=NULL)/i表示number1数字的长度 p指向number节点i+;p=p-next;q=num_2;while(q-next!=NULL)/j表示number2数字的长度 q指向number节点j+;q=q-next;s=(Number *)malloc(LEN);s-pr

21、ior=NULL;s-next=NULL;num=s;if(idata=q-data-p-data;if(s-datadata+=10;q-prior-data-;r=(Number *)malloc(LEN);s-next=r;r-prior=s;s=r;p=p-prior;q=q-prior;j-;/使i，j同时变化r=s=s-prior;/去掉最后一个没数据的节点free(s-next);s-next=NULL;while(j-)if(q-datadata+=10;q-prior-data-;s=(Number *)malloc(LEN);s-data=q-data;q=q-prior;

22、r-next=s;s-prior=r;r=s;s-data=0-s-data;/反号，因为节点里不能放符号，而直接在最高位前加负号最简单s-next=NULL;elseif(i=j)i=j=1;p=num_1;q=num_2;while(p-data=q-data)p=p-next;q=q-next;num_1=(Number *)malloc(LEN);num_1-prior=NULL;num_1-data=0;num_1-next=p;num_2=(Number *)malloc(LEN);num_2-prior=NULL;num_2-data=0;num_2-next=q;while(p

23、-next!=NULL)/i表示number1数字的长度 p指向number节点i+;p=p-next;q=num_2;while(q-next!=NULL)/j表示number2数字的长度 q指向number节点j+;q=q-next;if(num_1-next-datanum_2-next-data)while(i-)s-data=p-data-q-data;if(s-datadata+=10;p-prior-data-;r=(Number *)malloc(LEN);s-next=r;r-prior=s;s=r;p=p-prior;q=q-prior;r=s=s-prior;/去掉最后一

24、个没数据的节点free(s-next);while(s-data=0&s-prior!=NULL)/去掉前面多余的0，否则111112-111111=000001s=s-prior;free(s-next);if(num_1-next-datanext-data)while(i-)s-data=q-data-p-data;if(s-datadata+=10;q-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);w

25、hile(s-data=0&s-prior!=NULL)/去掉前面多余的0，否则111112-111111=000001s=s-prior;free(s-next);s-data=0-s-data;/反号，因为节点里不能放符号，而直接在最高位前加负号最简单s-next=NULL;elseif(ij)while(j-)s-data=p-data-q-data;if(s-datadata+=10;p-prior-data-;r=(Number *)malloc(LEN);s-next=r;r-prior=s;s=r;p=p-prior;q=q-prior;i-;r=s=s-prior;/去掉最后一

26、个没数据的节点free(s-next);s-next=NULL;while(i-)if(p-datadata+=10;p-prior-data-;s=(Number *)malloc(LEN);s-data=p-data;p=p-prior;r-next=s;s-prior=r;r=s;while(s-data=0&s-prior!=NULL)/去掉前面多余的0，否则1000-1=0999s=s-prior;free(s-next);/s-data=0-s-data;/反号，因为节点里不能放符号，而直接在最高位前加负号最简单s-next=NULL;return num;void PutNumber(Number *num) /链表的合并Number *p;int k=1,i;/k为数据长度，i控制,p=num;while(p-next!=NULL)p=p-ne