线性链表的实现及操作-

1、数据结构【第七次】实验报告 学院： 班级： 学号： 姓名： 实验七（一）实验名称：线性链表的实现及操作（二）实验目的：1) 深入理解线性链表的逻辑结构和链式存储结构； 2) 掌握线性链表的基本操作及应用： 3) 培养学生灵活使用结构解决实际问题的能力。（三）实验要求：1) 设计一个100位以内的长整数加减运算的程序。要求如下： 􀁺 输入输出要求：每四位一组，组间用逗号分隔； 􀁺 加和减分别用不同的程序实现 􀁺 程序应考虑输入数据的符号 2) 用循环链表实现约瑟夫环问题 （4） 源代码：1）100位以内的长整数加减运算的源代码：#includ

2、e<stdio.h>#include<stdlib.h>#define LEN sizeof(Number)typedef struct number Number;struct numberint data;Number *next;Number *prior; void main()void DestoryList(Number *);/释放链表void PutNumber(Number *);/将求得的结果输出Number *GetNumber();/创建链表，放被加数与加数Number *JiaFa(Number *num_1,Number *num_2);/加

3、法函数Number *JianFa(Number *num_1,Number *num_2);/减法函数Number *number_1,*number_2,*number;char ch;/存放运算符号printf("Enter the first long number:");number_1=GetNumber();printf("put +or-:");ch=getchar();fflush(stdin);/吸收不相关的字符printf("Enter the second long number:");number_2=Get

4、Number();if(ch='+')number=JiaFa(number_1,number_2);elseif(ch='-')number=JianFa(number_1,number_2);printf("n=n");PutNumber(number);DestoryList(number);DestoryList(number_1);DestoryList(number_2);printf("链表释放完成。n");Number *GetNumber() /得到两个链表Number *p,*q,*List;char

5、ch;p=(Number *)malloc(LEN);List=p;List->prior=NULL;List->data=0;/加法时，放最高位进的1，否者 999+1=000ch=getchar();while(ch!='n')if(ch>='0'&&ch<='9')/过滤非数字字符q=(Number *)malloc(LEN);q->data=ch-'0'p->next=q;q->prior=p;p=q;ch=getchar();p->next=NULL;Lis

6、t->prior=NULL;return List; /加法分两种情况长度相同与不同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!=NULL)j+;q=q->next;/j表示number2数字的长度 q指向number节点s=(Num

7、ber *)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>j)/在长的数据上调整p->prior->data+;elseq->prior->data+;r=(Number *)malloc(LEN);s->next=r;r->prior=s;s=r;p=p->prior;

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

9、p->data;r->next=s;s->prior=r;r=s;elsewhile(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)/*s=(Number *)malloc(LEN);s->data=q->data;r->next=s;s->prior=r;r=

10、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;while(q->next!=NULL)/j表示number2数字的长度 q指向numb

11、er节点j+;q=q->next;s=(Number *)malloc(LEN);s->prior=NULL;s->next=NULL;num=s;if(i<j)/对于被减数长度小于减数的，用减数减去被减数，最后反号while(i-)s->data=q->data-p->data;if(s->data<0)/*s->data+=10;q->prior->data-;r=(Number *)malloc(LEN);s->next=r;r->prior=s;s=r;p=p->prior;q=q->pri

12、or;j-;/使i，j同时变化r=s=s->prior;/去掉最后一个没数据的节点free(s->next);s->next=NULL;while(j-)if(q->data<0)/*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;s->data=0-s->data;/反号，因为节点里不能放符号，而直接在最高位前加负号最简单s->next=N

13、ULL;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->next!=NULL)/i表示number1数字的长度 p指向

14、number节点i+;p=p->next;q=num_2;while(q->next!=NULL)/j表示number2数字的长度 q指向number节点j+;q=q->next;if(num_1->next->data>num_2->next->data)while(i-)s->data=p->data-q->data;if(s->data<0)/*s->data+=10;p->prior->data-;r=(Number *)malloc(LEN);s->next=r;r->prio

15、r=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->data<num_2->next->data)while(i-)s->data=q->data-p->data;if(s->data

16、<0)/*s->data+=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-&g

17、t;data;/反号，因为节点里不能放符号，而直接在最高位前加负号最简单s->next=NULL;elseif(i>j)while(j-)s->data=p->data-q->data;if(s->data<0)/*s->data+=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-

18、>next=NULL;while(i-)if(p->data<0)/*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;while(s->data=0&&s->prior!=NULL)/去掉前面多余的0，否则1000-1=0999s=s->prior;free(s->next);/s->data=0-s->data;/反号

19、，因为节点里不能放符号，而直接在最高位前加负号最简单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->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('

20、,');putchar('n');void DestoryList(Number *list) /销毁链表Number *p,*q;p=list;while(p)q=p->next;free(p);p=q;2）用循环链表实现约瑟夫环问题的源代码：#include<stdio.h>#include<stdlib.h>struct Lnode int number; int password; struct Lnode *next; Lnode,*p,*q,*head;int main(void)int n; int i; int m; int

21、 j; printf("please enter the number of people n:"); scanf("%d",&n); loop:if(n<=0|n>30) printf("n n is erorr!nn"); printf("please enter the number of people again n:"); scanf("%d",&n); goto loop; for(i=1;i<=n;i+) if(i=1) head=p=(struc

22、t Lnode*)malloc(sizeof(struct Lnode); else q=(struct Lnode*)malloc(sizeof(struct Lnode); p->next=q; p=q; printf("please enter the %d people's password:",i); scanf("%d",&(p->password); p->number=i; p->next=head; p=head; printf("please enter the number m:"); scanf("%d",&m); printf("The password is:n"); for (j=1;j<=n;j+) for(i=1;i<m;i+,p=