数据结构——顺序表的合并

数据结构——顺序表的合并

具体要求：写一个函数，其函数的功能是将非递增顺序表LA和LB合并到非递增顺序表LC中

---

数据结构—顺序表的操作之合并顺序表

一、顺序表的结构

首先要定义的是顺序表的结构体，只有先定义了顺序表的结构体类型，才可以继续进行下一步操作

#define  maxsize  100 
typedef  struct {
	int  elem[maxsize];//线性表元素
	int  last;//线性表长度
}SeqList;
1
2
3
4
5

二、顺序表的操作

1.生成顺序表

在有了顺序表的结构之后，可以手动赋值顺序表，也可以动态读入顺序表，在这里我使用循环来生成我需要的顺序表的数据

代码如下（示例）：

SeqList LA, LB, LC;
	int i;

	for (i = 0; i < 10; i++)
	{
		LA.elem[i] = 20 - 2 * i;
		printf("%d	", LA.elem[i]);
	}
	LA.last = 9;
	printf("\n");

	for (i = 0; i < 8; i++)
	{
		LB.elem[i] = 24 - 3 * i;
		printf("%d	", LB.elem[i]);
	}
	LB.last = 7;
	printf("\n");

	merge(&LA, &LB, &LC);

	for (i = 0; i <= LC.last; i++)
	{
		printf("%d ", LC.elem[i]);
	}
	printf("\n");
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

2.写合成函数merge

在merge函数中，主要是对于元素顺序和个数的判断，在这里用了两个变量i和j来记录LA和LB中转移的元素个数，用一个变量k来记录转移到LC中的元素个数，所以最后的LC的最后一个元素在数组中的下标即为k-1，数组长度即为k，也可以用LA和LB的数组下标来判断，在代码注释中都有解释
merge函数代码如下（示例）：

//该函数的功能是将非递增顺序表LA和LB合并到非递增顺序表LC中
void merge(SeqList *LA, SeqList *LB, SeqList *LC)
{
	int i = 0, j = 0, k = 0;	//做初始化
	while (i <= LA->last&&j <= LB->last)	//用i和j来记录转移的循序表的个数
	{
		if (LA->elem[i] >= LB->elem[j])
		{
			LC->elem[k++] = LA->elem[i++];	//	i表示在LA中转移的个数
		}
		else
		{
			LC->elem[k++] = LB->elem[j++];	//	j表示在LB中转移的个数
		}
	}
	while (i <= LA->last)	//如果在LA中还有剩余的，则将其放到LC中
		LC->elem[k++] = LA->elem[i++];
	while (j <= LB->last)	//如果在LB中还有剩余的，则将其放到LC中
		LC->elem[k++] = LB->elem[j++];
	LC->last = LA->last + LB->last + 1;		//确定LC的数组下标
	printf("\n");
	if (k - 1 == LC->last)
	{
		printf("k-1=%d\n", k - 1);
		printf("LC的长度为 %d\n", LC->last);
	}
	


}
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

下面是该程序的完整代码

#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#define  maxsize  100 
typedef  struct {
	int  elem[maxsize];//线性表元素
	int  last;//线性表最后一个元素的下标位置
}SeqList;

//该函数的功能是将非递增顺序表LA和LB合并到非递增顺序表LC中
void merge(SeqList *LA, SeqList *LB, SeqList *LC)
{
	int i = 0, j = 0, k = 0;	//做初始化
	while (i <= LA->last&&j <= LB->last)	//用i和j来记录转移的循序表的个数
	{
		if (LA->elem[i] >= LB->elem[j])
		{
			LC->elem[k++] = LA->elem[i++];	//	i表示在LA中转移的个数
		}
		else
		{
			LC->elem[k++] = LB->elem[j++];	//	j表示在LB中转移的个数
		}
	}
	while (i <= LA->last)	//如果在LA中还有剩余的，则将其放到LC中
		LC->elem[k++] = LA->elem[i++];
	while (j <= LB->last)	//如果在LB中还有剩余的，则将其放到LC中
		LC->elem[k++] = LB->elem[j++];
	LC->last = LA->last + LB->last + 1;		//确定LC的数组下标
	printf("\n");
	if (k - 1 == LC->last)
	{
		printf("k-1=%d\n", k - 1);
		printf("LC的长度为 %d\n", LC->last);
	}
	


}

void main(void)
{
	SeqList LA, LB, LC;
	int i;

	for (i = 0; i < 10; i++)
	{
		LA.elem[i] = 20 - 2 * i;
		printf("%d	", LA.elem[i]);
	}
	LA.last = 9;
	printf("\n");

	for (i = 0; i < 8; i++)
	{
		LB.elem[i] = 24 - 3 * i;
		printf("%d	", LB.elem[i]);
	}
	LB.last = 7;
	printf("\n");

	merge(&LA, &LB, &LC);

	for (i = 0; i <= LC.last; i++)
	{
		printf("%d ", LC.elem[i]);
	}
	printf("\n");
	
}



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

---

总结

主要是完成了对于线性表的合并，操作，要注意在合并函数中对表的元素的标记，不要遗漏元素，还有就是合并后表的长度和最后一个元素的下标的关系，这是日后学习其他数据结构的基础。