数据结构【第七次】实验报告
学院：
班级： 学号： 姓名：
实验七
（一）实验名称：线性链表的实现及操作 （二）实验目的：
1) 深入理解线性链表的逻辑结构和链式存储结构； 2) 掌握线性链表的基本操作及应用：
3) 培养学生灵活使用结构解决实际问题的能力。 （三）实验要求：
1) 设计一个100位以内的长整数加减运算的程序。要求如下：
输入输出要求：每四位一组，组间用逗号分隔； 加和减分别用不同的程序实现 程序应考虑输入数据的符号 2) 用循环链表实现约瑟夫环问题 （四）源代码：
1）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 *); //将求得的结果输出 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:"); number_1=GetNumber(); printf("put +or-:"); ch=getchar(); fflush(stdin); //吸收不相关的字符 printf("Enter the second long number:"); number_2=GetNumber(); if(ch=='+') number=JiaFa(number_1,number_2); else if(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 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 *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数字的长度指向number 节点
q=num_2; while(q->next!=NULL) { j++; q=q->next; } //j表示number2数字的长度指向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)
p q
{
s->data-=10;
if(i>j)
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(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=p->data; r->next=s; s->prior=r; r=s; } }
else
//**处理两数相加大于9的情况，后
//在长的数据上调整
//去掉最后一个没数据的节点
//**
//**
面还有
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) //** { s=(Number *)malloc(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数字的长度number 节点
{ i++; p=p->next; } q=num_2; while(q->next!=NULL) //j表示number2数字的长度number 节点
p 指向q 指向
j++; q=q->next; } s=(Number *)malloc(LEN); s->prior=NULL; s->next=NULL; num=s; if(i
{ 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; 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; }
//对于被减数长度小于减数的，
//**
//使i ，j 同时变化
//去掉最后一个没数据的节点
//**
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; 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->data>num_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; //去掉最后一个没数据的节点 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->prior; } 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(i>j) { while(j--) { s->data=p->data-q->data; 1000-1=0999
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(s->data==0&&s->prior!=NULL)//去掉前面多余的0，否则 { s=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;
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)
开始输出‘, ’数据输出完后不输出‘, ’
putchar(',');
}
putchar('\n');
}
void DestoryList(Number *list)
{
Number *p,*q;
p=list;
while(p)
{
q=p->next;
free(p);
p=q;
}
}
2）用循环链表实现约瑟夫环问题的源代码：
#include //k为数据长度，i 控制‘, ’ //长度为k 的数据，在k%4个数字后//销毁链表
#include
struct Lnode
{int number;
int password;
struct Lnode *next;
}Lnode,*p,*q,*head;
int main(void)
{int n;
int i;
int m;
int j;
printf("please enter the number of people n:");
scanf("%d",&n);
loop:if(n30)
{printf("\n n is erorr!\n\n");
printf("please enter the number of people again n:");
scanf("%d",&n);
goto loop;
}
for(i=1;i
{if(i==1)
{head=p=(struct 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;jnext);
m=p->password;
printf("%d ",p->number);
p->number=p->next->number;
p->password=p->next->password;
q=p->next;
p->next=p->next->next;
free(q);
}
printf("\n\n");
system("pause");
}
（五）运行结果：
1）100位以内的长整数加减运算的程序运行结果：
2）用循环链表实现约瑟夫环问题的程序运行结果
：
（六）需求分析
1、输入的形式和输出值的范围：1) 每四位整数（0到9）一组，组间用逗号分隔；不超过100位的长整数。2）输入人数n 和每个人依次对应的编号1,2,3,4,5，、、、，n ；所以人的编号。
2、输出的形式：1）每四位一组，组间用逗号分隔。2）输出所以人编号的出列顺序。
3、程序所能达到的功能：1）一百位以内的长整数之间的加减法运算。
2）解答约瑟夫环问题。
（七）用到的函数或结构体：
1）100位以内的长整数加减运算的源代码：
typedef struct
void main()
void DestoryList()
void PutNumber()
Printf()
2）用循环链表实现约瑟夫环问题的源代码：
struct Lnode
V oid main()
Printf()
Scanf()
(八) 心得体会：
通过此次实验，我更加深入的理解了线性链表的逻辑结构和链式存储结构。认识并掌握了线性链表的基本操作及应用： 同时，加强了我用已有知识解决实际问题的能力，让我更有信心去学好即将面临的新知识。
数据结构【第七次】实验报告
学院：
班级： 学号： 姓名：
实验七
（一）实验名称：线性链表的实现及操作 （二）实验目的：
1) 深入理解线性链表的逻辑结构和链式存储结构； 2) 掌握线性链表的基本操作及应用：
3) 培养学生灵活使用结构解决实际问题的能力。 （三）实验要求：
1) 设计一个100位以内的长整数加减运算的程序。要求如下：
输入输出要求：每四位一组，组间用逗号分隔； 加和减分别用不同的程序实现 程序应考虑输入数据的符号 2) 用循环链表实现约瑟夫环问题 （四）源代码：
1）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 *); //将求得的结果输出 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:"); number_1=GetNumber(); printf("put +or-:"); ch=getchar(); fflush(stdin); //吸收不相关的字符 printf("Enter the second long number:"); number_2=GetNumber(); if(ch=='+') number=JiaFa(number_1,number_2); else if(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 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 *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数字的长度指向number 节点
q=num_2; while(q->next!=NULL) { j++; q=q->next; } //j表示number2数字的长度指向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)
p q
{
s->data-=10;
if(i>j)
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(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=p->data; r->next=s; s->prior=r; r=s; } }
else
//**处理两数相加大于9的情况，后
//在长的数据上调整
//去掉最后一个没数据的节点
//**
//**
面还有
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) //** { s=(Number *)malloc(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数字的长度number 节点
{ i++; p=p->next; } q=num_2; while(q->next!=NULL) //j表示number2数字的长度number 节点
p 指向q 指向
j++; q=q->next; } s=(Number *)malloc(LEN); s->prior=NULL; s->next=NULL; num=s; if(i
{ 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; 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; }
//对于被减数长度小于减数的，
//**
//使i ，j 同时变化
//去掉最后一个没数据的节点
//**
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; 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->data>num_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; //去掉最后一个没数据的节点 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->prior; } 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(i>j) { while(j--) { s->data=p->data-q->data; 1000-1=0999
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(s->data==0&&s->prior!=NULL)//去掉前面多余的0，否则 { s=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;
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)
开始输出‘, ’数据输出完后不输出‘, ’
putchar(',');
}
putchar('\n');
}
void DestoryList(Number *list)
{
Number *p,*q;
p=list;
while(p)
{
q=p->next;
free(p);
p=q;
}
}
2）用循环链表实现约瑟夫环问题的源代码：
#include //k为数据长度，i 控制‘, ’ //长度为k 的数据，在k%4个数字后//销毁链表
#include
struct Lnode
{int number;
int password;
struct Lnode *next;
}Lnode,*p,*q,*head;
int main(void)
{int n;
int i;
int m;
int j;
printf("please enter the number of people n:");
scanf("%d",&n);
loop:if(n30)
{printf("\n n is erorr!\n\n");
printf("please enter the number of people again n:");
scanf("%d",&n);
goto loop;
}
for(i=1;i
{if(i==1)
{head=p=(struct 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;jnext);
m=p->password;
printf("%d ",p->number);
p->number=p->next->number;
p->password=p->next->password;
q=p->next;
p->next=p->next->next;
free(q);
}
printf("\n\n");
system("pause");
}
（五）运行结果：
1）100位以内的长整数加减运算的程序运行结果：
2）用循环链表实现约瑟夫环问题的程序运行结果
：
（六）需求分析
1、输入的形式和输出值的范围：1) 每四位整数（0到9）一组，组间用逗号分隔；不超过100位的长整数。2）输入人数n 和每个人依次对应的编号1,2,3,4,5，、、、，n ；所以人的编号。
2、输出的形式：1）每四位一组，组间用逗号分隔。2）输出所以人编号的出列顺序。
3、程序所能达到的功能：1）一百位以内的长整数之间的加减法运算。
2）解答约瑟夫环问题。
（七）用到的函数或结构体：
1）100位以内的长整数加减运算的源代码：
typedef struct
void main()
void DestoryList()
void PutNumber()
Printf()
2）用循环链表实现约瑟夫环问题的源代码：
struct Lnode
V oid main()
Printf()
Scanf()
(八) 心得体会：
通过此次实验，我更加深入的理解了线性链表的逻辑结构和链式存储结构。认识并掌握了线性链表的基本操作及应用： 同时，加强了我用已有知识解决实际问题的能力，让我更有信心去学好即将面临的新知识。