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

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

2、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;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指向n

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

4、=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-prior=r; r=s; if(p-data0) s=(Number *)malloc(LEN); s-data=p-data; r-next=s; s-prior=r

5、; r=s; else while(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置空 return num;3. 减法分3中情况：被减数长度大于、小于、等于减数长度Number *JianFa(Numb

6、er *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-prior=NULL; s-next=NULL; num=s; if(idata=q-

7、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; r-next=s; s-prior

8、=r; r=s; s-data=0-s-data; /反号，因为节点里不能放符号，而直接在最高位前加负号最简单 s-next=NULL; else if(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; whi

9、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; 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-p

10、rior; r=s=s-prior; /去掉最后一个没数据的节点 free(s-next); while(s-data=0&s-prior!=NULL) /去掉前面多余的0，否则111112-111111=000001 s=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-prio

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

12、t=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(s-data=0&s-prior!=NULL)/去掉前面多余的0，否则1000-1=0999 s=s-prior; free(s-next);

13、/ 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(k!=0&i%4=0) /长度为k的数据，在k%4个数字后开始输出,数据输出完后不输出, putchar

14、(,); putchar(n);五、 遇到的问题及解决方法问题：对getchar函数运用不熟练心得体会熟悉了链表及一些库函数，一定程度上锻炼了对复杂函数的解决能力。附录：全部代码：100位以内的长整数加减运算的源代码：#include#include#define LEN sizeof(Number)typedef struct number Number;struct number int data; Number *next; Number *prior;void main() void DestoryList(Number *); /释放链表 void PutNumber(Number

15、*); /将求得的结果输出 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(); printf(put +or-:n); ch=getchar(); ff

16、lush(stdin); /吸收不相关的字符 printf(Enter the second long number:n); number_2=GetNumber(); if(ch=+) number=JiaFa(number_1,number_2); else if(ch=-) number=JianFa(number_1,number_2); printf(=n); PutNumber(number); DestoryList(number); DestoryList(number_1); DestoryList(number_2);Number *GetNumber() /得到两个链表

17、Number *p,*q,*List; char ch; p=(Number *)malloc(LEN); List=p; List-prior=NULL; List-data=0; /加法时，放最高位进的1，否者 999+1=000 ch=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 *

18、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!=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-d

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

20、oc(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; else while(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

21、(LEN); s-data=q-data; r-next=s; s-prior=r; r=s; s-next=NULL; /将最后一个next置空 return 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; wh

22、ile(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; j-; /使i，j同时变化 r=s=s-prior; /去掉最后一个没数据的节点 free(s-next); s-next=NULL; while(j-)