数据结构是最近纳入电院的必修主课，但是其期末考核是笔试形式（，日常有上机安排。
这门课还是需要一定的课后上机练习和调试来增加对其的认识程度、发现自己欠缺的知识、可能犯下的错误，包括但不限于语法等
这里主要收录几次上机安排的报告和自己的答案，作为记录
第一次上机
问题一：顺序表的合并
1.问题描述：
线性表的基本操作：p20算法2.2，已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列。
例如：设LA=（3,5,8,11），LB=（2,6,8,9,11,15,20），则LC=（2,3,5,6,8,8,9,11,15,20）
2.数据结构设计
考虑用顺序表或者数组来实现
3.算法设计
首先初始化三个空表，利用Insert函数往表中输入元素，for循环存到a,b表中，利用标识数字-1结束输入，注意到表长不能超过Maxsize;然后封装一个Funtion函数来处理比较和合并的问题。
由于题目要求非递减顺序有序排列，那么在循环中逐个将A,B表元素比对，将符合条件的也就是小或者相等的存入到C表中，最后用一个循环输出C表即可
4.源代码
1 /*
2 1.问题描述：
3 已知线性表LA和LB中的数据元素按值非递减有序排列，
4 现要求将LA和LB归并为一个新的线性表LC，
5 且LC中的数据元素仍按值非递减有序排列。
6 例如：设
7 LA=（3,5,8,11），LB=（2,6,8,9,11,15,20），则LC=（2,3,5,6,8,8,9,11,15,20）
8
9 2.数据结构和算法设计
10 这里分析用线性表存储数据并进行合并，考虑静态数组？把处理放在函数funtion里；
11 首先建立顺序表的存储结构，建立空表C来存放数据，求出a,b表的长度，并新定义表C的长度；
12 在循环里比较表A,B的元素大小来决定是否存入C，同时计数器自增，计数器判定依据是两表表长；
13 如果其中一表的长度大于另一表，显然需要处理剩余项，也就是计数器继续自增并存入数据到表C
14 直到计数结束；
15 最后把表打印出来即可
16 */
17 #include<stdio.h>
18 #include<stdlib.h>
19 #define Maxsize 100
20
21 typedef int Elemtype;
22 typedef struct
23 {
24 Elemtype data[Maxsize];
25 int Length;
26
27 }Orderlist;//建立存储结构
28
29 void InitList(Orderlist **L);
30 _Bool Insert(Orderlist *L,Elemtype data,int i);
31 int Get_Length(Orderlist *L);
32 void Funtion(Orderlist *LA,int a,Orderlist *LB,int b,Orderlist *LC);
33 void Print(Orderlist *L,int sum_length);//表是指针的集合，可以看到传参都是*L
34
35 int main()
36 {
37 //怎么建立一个动态输入的顺序表?
38 Orderlist *La,*Lb,*Lc;
39 InitList(&La);
40 InitList(&Lb);
41 InitList(&Lc);//初始化三个表
42
43 int data;
44
45 for(int i=1;i<=Maxsize;i++)
46 {
47 scanf("%d",&data);
48 if(data==-1)
49 break;
50 Insert(La,data,i);
51 }
52 for(int j=1;j<=Maxsize;j++)
53 {
54 scanf("%d",&data);
55 if(data==-1)
56 break;
57 Insert(Lb,data,j);
58 }//分别输入两个表的内容，用-1来作为结束判定的标识符，Insert函数逐个插入
59
60 int length_a=Get_Length(La);
61 int length_b=Get_Length(Lb);
62 int length_c=length_a+length_b;//获取表长，输出和后面处理用
63
64 Funtion(La,length_a,Lb,length_b,Lc);
65
66 Print(Lc,length_c);
67
68 return 0;
69
70 }
71
72 void InitList(Orderlist **L)//二级指针法建立空表
73 {
74 *L=(Orderlist*)malloc(sizeof(Orderlist));
75 (*L)->Length=0;
76 }
77
78 int Get_Length(Orderlist *L)//获取表长，直接返回L->length
79 {
80 return L->Length;
81 }
82
83 _Bool Insert(Orderlist *L,Elemtype data,int i)//插入的函数
84 {
85 if(i<-1||i>L->Length+1||L->Length>=Maxsize)//判断i异常或者长度异常
86 return 0;
87 for(int j=L->Length;j>=i;j--)
88 {
89 L->data[j]=L->data[j-1];
90 }
91 L->data[i-1]=data;
92 L->Length++;
93 return 1;
94 }
95
96 void Print(Orderlist *L,int sum_length)//输出
97 {
98
99 printf("------------------------\n");
100 for(int i=1;i<=sum_length;i++)
101 {
102 printf("%d\t",L->data[i-1]);
103 }
104 }
105 void Funtion(Orderlist *LA,int a,Orderlist *LB,int b,Orderlist *LC)
106 {
107 int i=0,j=0,k=0;
108 while(i<a&&j<b)
109 {
110 if((LA->data[i])<(LB->data[j]))//逐个比对，小的存入C表并自增
111 {
112 LC->data[k]=LA->data[i];
113 i++;
114 }
115 else
116 {
117 LC->data[k]=LB->data[j];
118 j++;
119 }
120 k++;
121 }
122
123 while(i<a)//处理剩余的，有的表比较长
124 {
125 LC->data[k]=LA->data[i];
126 i++;
127 k++;
128 }
129
130 while(j<b)
131 {
132 LC->data[k]=LB->data[j];
133 j++;
134 k++;
135 }
136 }
问题二：链表
1.问题描述：约瑟夫环。
编号为1,2,...,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。
现在给定一个随机数m>0，从编号为1的人开始，按顺时针方向1开始顺序报数，报到m时停止。
报m的人出圈，从他在顺时针方向上的下一个人开始，重新从1开始报数，如此下去，直至所有的人全部出列为止。
请编写程序求出圈的顺序。
上机实现提示：
① 编写建立循环链表算法
②编写结点输出算法(带输入参数k)
③编写主程序
要求，把程序看懂，然后进行调试，得出正确的结果。
1,2,3,4,5,6,7。从第1个人开始报数，报到3的人出列，出列顺序为3,6,2,7,5,1,4
2.数据结构分析
如题，用循环链表实现这个环
3.算法分析
考虑新建一个循环链表来实现这个环，问题一是建立循环链表和存数据，问题二是怎么样实现约瑟夫的求解
解决约瑟夫，设一共n人，报数m的时候第m个出列，然后重新报数，同时用flag来标记出列的人数，显然当flag=n-1时完成 4.源代码
/*
约瑟夫环。
编号为1,2,...,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。
现在给定一个随机数m>0，从编号为1的人开始，按顺时针方向1开始顺序报数，报到m时停止。
报m的人出圈，从他在顺时针方向上的下一个人开始，重新从1开始报数，
如此下去，直至所有的人全部出列为止。请编写程序求出圈的顺序。
1,2,3,4,5,6,7。从第1个人开始报数，报到3的人出列，出列顺序为3,6,2,7,5,1,4
考虑新建一个循环链表来实现这个环，问题一是建立循环链表和存数据，问题二是怎么样实现约瑟夫的求解
解决约瑟夫，设一共n人，报数m的时候第m个出列，然后重新报数，同时用flag来标记出列的人数，显然当flag=n-1时完成
*/
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node *next;
}Lnode;//建立链表的存储结构
Lnode*Tail_Creat(int n);
void YuesefuHuan(Lnode *L,int n,int m,int a[]);//声明调用的两个函数，一个尾插法一个处理约瑟夫环
int main()
{
int n,m;
scanf("%d\t%d",&n,&m);//输入总人数n和报数m
Lnode*tail=NULL;//声明一个尾指针指向空，并在下面用尾插法返回值赋值
tail=Tail_Creat(n);
int a[n];//新建一个输出数组
YuesefuHuan(tail,n,m,a);
for(int i=0;i<n;i++)
{
printf("%d\t",a[i]);
}
return 0;
}
Lnode*Tail_Creat(int n)//尾插法建立新循环链表，这里假定了链表必定不为空表
{
Lnode *head,*new_elem,*tail;
head=NULL,new_elem=NULL,tail=NULL;//建立头指针，存放数据的指针和尾指针且初始指向空
int i;
for(i=1;i<=n;i++)//遍历，从1开始到n，并把i依次存入到链表中
{
new_elem=(Lnode*)malloc(sizeof(Lnode));//开辟空间
new_elem->data=i;
if(head==NULL)//考虑到每个结点都存数据，这里是不带头结点的尾插法，head是头指针指向第一个元素。如果带头结点呢？
{
head=new_elem;//初始状态，头指针存入第一个元素
}
else
{
tail->next=new_elem;//如果不是初始状态，用尾插法，将尾指针的后继指向新元素
}
tail=new_elem;//无论是第一个还是后续，都将尾指针指向更新后最后一个元素
}
tail->next=head;//构建循环链表，将尾指针的后继指向头指针
return tail;//返回尾指针，考虑到约瑟夫实现里面循环链表不是双向，返回tail相当于返回i-1位指针
}
void YuesefuHuan(Lnode *L,int n,int m,int a[])//传入的是指针
{
int cnt=0,flag=0,i=0;//cnt计数用判断是否到m，flag计数出列人数，到n-1时只剩下最后一个，结束
Lnode*s=L,*p=L->next;//初始L传入的是尾指针，s指向一个结点，p指向s的下一个结点,实际上要出列看的是p,初始cnt从0自增1对照的是p的序号1
while(flag!=n-1)
{
cnt++;//计数器从0自增，序号和p相同；
if(cnt!=m)//如果还没到要出列的位置，后移两个指针，注意先s=p避免丢失
{
s=p;
p=p->next;
}
else if(cnt==m)//如果到了要出列的位置（画图看比较容易看出）
{
cnt=0;
flag++;//重新开始计数，出列人数自增1
a[i++]=p->data;//存数据到要输出的数组中
s->next=p->next;
free(p);
p=s->next;//注意这里s还是在上一个位置，只是把p（每次遍历判断是否要出列的结点）移向出列结点的后一个结点，所以不是写s=p->next
}
}
a[i]=p->data;//传入最后一个数据
free(p);
p=NULL;
}
这里补充一个要求高一点的约瑟夫环的实现，其题目要求做了一些改动：
时间限制2 S 内存限制10000 Kb
问题描述
习题集P79。编号为1,2,...,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。现在给定一个随机数m>0，从编号为1的人开始，按顺时针方向1开始顺序报数，报到m时停止。报m的人出圈，同时留下他的密码作为新的m值，从他在顺时针方向上的下一个人开始，重新从1开始报数，如此下去，直至所有的人全部出圈为止。
问题输入
输入数据第一行为两个正整数n和m，分别表示人的个数及初始随机数，每组数据的第二行为n个整数，表示每个人持有的密码。
问题输出
用一行输出n个整数表示依次出圈人的编号，整数之间用空格分隔
输入样例
7 20
3 1 7 2 4 8 4
输出样例
6 1 4 7 2 3 5
提示
使用不带头节点的循环链表
这里多了一个m值作为下一次循环用，那么新建一个数组来存
对约瑟夫环处理函数里面的elseif分支改动一下即可
给出改动后的源代码，对应xdoj_264题
1 /*
2 约瑟夫环
3 时间限制
4 2 S
5 内存限制
6 10000 Kb
7 问题描述
8 编号为1,2,...,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。
9 现在给定一个随机数m>0，从编号为1的人开始，按顺时针方向1开始顺序报数，报到m时停止。
10 报m的人出圈，同时留下他的密码作为新的m值，从他在顺时针方向上的下一个人开始，重新从1开始报数，
11 如此下去，直至所有的人全部出圈为止。
12 问题输入
13 输入数据第一行为两个正整数n和m，分别表示人的个数及初始随机数，每组数据的第二行为n个整数，表示每个人持有的密码。
14 问题输出
15 用一行输出n个整数表示依次出圈人的编号，整数之间用空格分隔
16 输入样例
17 7 20
18 3 1 7 2 4 8 4
19 输出样例
20 6 1 4 7 2 3 5
21 提示
22 使用不带头节点的循环链表
23
24 考虑新建一个循环链表来实现这个环，问题一是建立循环链表和存数据，问题二是怎么样实现约瑟夫的求解
25 解决约瑟夫，设一共n人，怎么出列？报数m的时候第m个出列，然后重新报数，同时用flag来标记出列的人数，怎么结束？显然当flag=n-1时完成
26 这个问题输出的还是编号，只是m值作为变量会发生变化，每个人随身带有一个m值需要建立数组额外存取（考虑到结构体的思想，也写在链表的结构体里！另写一个c代码）
27 */
28 #include<stdio.h>
29 #include<stdlib.h>
30
31 typedef struct node
32 {
33 int data;
34 struct node *next;
35 }Lnode;//建立链表的存储结构
36
37 Lnode*Tail_Creat(int n);
38 void YuesefuHuan(Lnode *L,int n,int m,int a[],int b[]);//声明调用的两个函数，一个尾插法一个处理约瑟夫环
39
40 int main()
41 {
42 /*
43 流程描述
44 输入 总人数和报数的值m
45 建立两个新数组，一个存m值，一个输出编号
46 for循环输入m值到一个数组
47
48 尾插法建立链表
49 函数处理约瑟夫环问题
50
51 for循环输出另一个数组（显然上一个函数已经把数据存到了存编号的数组中）
52 */
53 int n,m,m_data,i;
54 scanf("%d\t%d",&n,&m);//输入总人数n和报数m
55 int a[n];//新建一个输出数组
56 int b[n];//新建一个存储数组存储每个人的m值
57
58 for(i=0;i<n;i++)
59 {
60 scanf("%d",&m_data);
61 b[i]=m_data;
62 }
63
64 Lnode*tail=NULL;//声明一个尾指针指向空，并在下面用尾插法返回值赋值
65 tail=Tail_Creat(n);
66 YuesefuHuan(tail,n,m,a,b);
67 for(i=0;i<n;i++)
68 {
69 printf("%d\t",a[i]);
70 }
71 return 0;
72 }
73
74
75 Lnode*Tail_Creat(int n)//尾插法建立新循环链表，这里假定了链表必定不为空表，同时不带头结点
76 {
77 Lnode *head,*new_elem,*tail;
78 head=NULL,new_elem=NULL,tail=NULL;//建立头指针，存放数据的指针和尾指针且初始指向空
79
80 int i;
81 for(i=1;i<=n;i++)//遍历，从1开始到n，并把编号i依次存入到链表中
82 {
83 new_elem=(Lnode*)malloc(sizeof(Lnode));//开辟空间
84 new_elem->data=i;
85 if(head==NULL)//考虑到每个结点都存数据，这里是不带头结点的尾插法，head是头指针指向第一个元素。如果带头结点呢？
86 {
87 head=new_elem;//初始状态，头指针存入第一个元素
88 }
89 else
90 {
91 tail->next=new_elem;//如果不是初始状态，用尾插法，将尾指针的后继指向新元素
92 }
93 tail=new_elem;//无论是第一个还是后续，都将尾指针指向更新后最后一个元素
94 }
95 tail->next=head;//构建循环链表，将尾指针的后继指向头指针
96 return tail;//返回尾指针，考虑到约瑟夫实现里面循环链表不是双向，返回tail相当于返回i-1位指针
97
98 }
99
100 void YuesefuHuan(Lnode *L,int n,int m,int a[],int b[])
101 {
102 int cnt=0,flag=0,i=0;//cnt计数用判断是否到m，flag计数出列人数，到n-1时只剩下最后一个，结束
103 Lnode*s=L,*p=L->next;//初始L传入的是尾指针，s指向一个结点，p指向s的下一个结点,实际上要出列看的是p,初始cnt从0自增1对照的是p的序号1
104 while(flag!=n-1)
105 {
106 cnt++;//计数器从0自增，序号和p相同；
107 if(cnt!=m)//如果还没到要出列的位置，后移两个指针，注意先s=p避免丢失
108 {
109 s=p;
110 p=p->next;
111 }
112 else if(cnt==m)//如果到了要出列的位置（画图看比较容易看出）
113 {
114 cnt=0;
115 flag++;//重新开始计数，出列人数自增1
116 m=b[p->data-1];//把b数组存的m值更新到函数里即可，注意到数组的位序要比表的位序少1
117 a[i++]=p->data;//存数据到要输出的数组中
118 s->next=p->next;//避免断开
119 free(p);
120 p=s->next;//注意这里s还是在上一个位置，只是把p（每次遍历判断是否要出列的结点）移向出列结点的后一个结点，所以不是写s=p->next
121
122 }
123 }
124 a[i]=p->data;//传入最后一个数据（这种细节不要忽视）
125 free(p);
126 p=NULL;
127 }
标签：上机,int,电专,next,链表,指针,data,报数,电院 From： https://www.cnblogs.com/WCMS-XDU688/p/17793917.html