一、实验目的
- 掌握程序设计的基本方法，要求能够利用C语言实现简单的算法设计。
- 熟练掌握指针的应用。
- 熟练掌握线性表的基本运算在顺序存储结构和链式存储结构上的实现。
- 掌握顺序表以及线性链表的基本操作及实现。
- 能使用线性表来解决实际中遇到的问题。
二、实验内容
(一)验证实验
- 定义顺序表类型。
- 基于 1 所设计的线性表数据结构，实现线性表的初始化、插入、删除、求表长、按值查找、按位置查找操作。
- 建立一个单链表，实现建立，插入，删除，查找操作。
(二)设计实验
- 编写一个算法实现两个有序（从小到大）顺序表合并成为一个顺序表，合并后的结果放在第一个顺序表中，不另设新的顺序表存储（假设这两个有序顺序表中没有相同的元素）。
- 有一个已按递增次序排好序的线性表，输入一个数，要求按原来的排序规律将它插入到线性表中。
- 将两个有序链表合并成一个有序的单链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。
- 实现约瑟夫环算法，设有n个人坐在圆桌周围，从第s个人开始报数，报到m的人出列，然后再从下一个人开始报数，报到m 的人又出列，┅如此重复，直到所有的人都出列为止。要求按出列的先后顺序输出每个人的信息。
三、详细设计及运行结果
设计实验一，合并顺序表，用结构体定义一个线性表SqList,定义函数void Merge_List()对两个有序顺序表进行合并，并不创建新的表（于是对于表A选择传入其地址，而表B只是传入表，并不传入地址）。该函数从顺序表的末尾对线性表数据进行排序。运行情况如下：
![image-20240721114134453]()
设计实验二，在有序表中插入一个数据，并保持有序性。首先，需要判断该数据应当插入的位置，记为k，而后用循环，将第K个元素后面的全部向后移动一位，（从末尾开始移动)，再将要插入的值E插入到第K个位置。
运行结果如下:
![img]()
设计实验三，将两个有序链表合并成一个有序的单链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。定义链表，创建链表，打印链表中元素，将两个有序链表合并。在创建链表过程中，先是将创建的链表的头结点传入函数，在函数内部，定义一个新的指针，使用p指针来遍历链表，保持L指向头结点；再进行接下来的运算，此外，创建新节点时需要将 新节点的next指针赋值为NULL。运行结果如下：
![img]()
四、调试情况，设计技巧及体会
主要在第三个程序中出现了大问题。已解决，应当重新创建一个指针用于遍历链表，保持L指向头结点。此外，新建节点之后，其next指针应当赋值为null。
1 | // 创建链表 |
五、源程序清单
- 合并顺序表
1 | // 编写一个算法实现两个有序（从小到大）顺序表合并成为一个顺序表， |
插入一个数据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
typedef struct
{
int elem[Maxsize];
int length;
} SqList;
// 插入
void Insert_List(SqList *L, int n)
{
if (L->length + 1 > Maxsize)
{
printf("Error:Exceeds max size of sequencn list\n");
}
int k;
for (int i = 0; i < L->length; i++)
{
if (L->elem[i] >= n && L->elem[i - 1] <= n)
{
k = i;
}
if (L->elem[L->length - 1] < n)
{
k = L->length;
}
}
for (int j = L->length; j > k; j--)
{
L->elem[j] = L->elem[j - 1];
}
L->elem[k] = n;
L->length++;
}
// 主函数
int main()
{
SqList La = {{2, 4, 5, 8, 9, 14}, 6};
int n;
printf("请输入要插入的数据：");
scanf("%d", &n);
Insert_List(&La, n);
printf("插入后的顺序表为：");
for (int j = 0; j < La.length; j++)
{
printf("%d ", La.elem[j]);
}
system("pause");
return 0;
}合并两个有序链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
typedef struct LNode
{
int data; // 数据域
struct LNode *next; // 指向自己类型的指针域
} LNode, *LinkList; // LinkList为LNode类型的指针
// 创建链表
void CreatLink(LinkList L, int n)
{
LinkList p = L;
printf("请输入链表的元素:");
for (int i = 0; i < n; i++)
{
LinkList newNode = (LinkList)malloc(sizeof(LNode));
newNode->next = NULL;
p->next = newNode;
scanf("%d", &newNode->data);
p = p->next;
}
}
// 打印链表中元素。
void PrintList_L(LinkList L)
{
LinkList p = L->next;
while (p)
{
printf("%d ", p->data);
p = p->next;
}
}
void MergeList_L(LinkList La, LinkList Lb)
{
LinkList pa = La->next; // 表La和表Lb,其中LA,LB都表示其头结点。
LinkList pb = Lb->next;
LinkList pc = La; // 使用LA的头结点，作为合成后的头结点。
while (pa && pb)
{
if (pa->data < pb->data)
{
pc->next = pa;
pc = pa;
pa = pa->next;
}
else if (pa->data > pb->data)
{
pc->next = pb;
pc = pb;
pb = pb->next;
}
else
{
pc->next = pa;
pc = pa;
pa = pa->next;
LinkList temp = pb;
pb = pb->next;
free(temp);
}
}
pc->next = pa ? pa : pb;
free(Lb);
}
int main()
{
LinkList La, Lb;
La = (LinkList)malloc(sizeof(LNode)); // 生成一个LNode类型的头结点
La->next = NULL;
Lb = (LinkList)malloc(sizeof(LNode));
Lb->next = NULL;
int a, b;
printf("请输入第一个链表和第二个链表的长度：");
scanf("%d %d", &a, &b);
CreatLink(La, a);
CreatLink(Lb, b);
MergeList_L(La, Lb);
printf("合并后的链表如下：");
PrintList_L(La);
system("pause");
return 0;
}