顺序表的基本操作--不使用额外辅助空间去重合并两个顺序表_有两个递增有序顺序表a和b,其中a的容量大于a+b。请把a和b按序合并后放在a中,a和b

题目

有两个递增有序顺序表A和B，其中A的容量大于A+B。请把A和B按序合并后放在A中，A和B中若有重复元素，合并后只存1次，然后输出顺序表的内容。元素由用户从键盘输入。

代码：

# include <stdio.h>
# include <malloc.h>
# include <stdlib.h>

typedef int Elemtype;
//创建整型数组结构体类型
struct Array {
	int cnt;//数组中的有效元素个数
	int len;//数组的长度
	Elemtype* elem;//数组的首元素的地址，即数组的地址,  注意地址是整型，一般只占4个字节
};

void init_arry(struct Array*, int);		//数组初始化,定义了数组类型
void show_arry(struct Array*);			//输出数组元素
bool is_empty(struct Array*);			//判断数组是否为空
bool is_full(struct Array*);			//判断数组是否为满
bool append_arry(struct Array*, int);				//增加数组元素
void sort_arry(struct Array*);			//对数组元素排序

//数组初始化,定义了数组类型
void init_arry(struct Array* pArr, int lenth)//传入数组的地址和希望创建数组的长度
{
	//给数组动态分配一整块连续的能够存放lenth个元素的内存
	pArr->elem = (Elemtype*)malloc(sizeof(Elemtype) * lenth);/*创建一个整型的数组*/
	if (NULL == pArr->elem)
	{
		printf("动态内存分配未成功，数组创建失败！\n");
		exit(-1);
	}
	else//内存分配成功，对数组结构体进行初始化
	{
		pArr->cnt = 0;//数组刚开始的有效元素个数为0
		pArr->len = lenth;//创建的数组的能够存储元素的个数
	}
	return;
}
//判断数组是否为满
bool is_full(struct Array* pArr)
{
	if (pArr->cnt == pArr->len)
	{
		//printf("该数组已满！\n");
		return true;
	}
	else
	{
		return false;
	}
}
//判断数组是否为空
bool is_empty(struct Array* pArr)
{
	if (pArr->cnt == 0)
	{
		//printf("该数组为空！\n");
		return true;
	}
	else
	{
		return false;
	}
}

//增加数组元素
bool append_arry(struct Array* pArr, int val)
{
	if (is_full(pArr))
	{
		printf("is_full()数组内存已满，无法继续追加元素！\n");
		return false;
	}
	else
	{
		pArr->elem[pArr->cnt] = val;//数组的有效元素位置赋值一个整型元素val
		pArr->cnt++;//追加一个元素成功后，数组有效元素个数自增
		return true;
	}

}

//对数组元素进行升序排序
void sort_arry(struct Array* pArr)
{
	int i, j;
	int t;

	//选择升序排序	
	for (i = 0; i < pArr->cnt-1; i++)
	{
		for (j = i + 1; j < pArr->cnt; j++)
		{
			if (pArr->elem[i] > pArr->elem[j])
			{
				t = pArr->elem[i];
				pArr->elem[i] = pArr->elem[j];
				pArr->elem[j] = t;
			}
		}
	}
	
	return;
}

//输出数组所有效元素
void show_arry(struct Array* pArr)
{
	if (is_empty(pArr))
	{
		printf("show_arry数组为空,输出失败！\n");
		return;
	}

	int i;
	for (i = 0; i < pArr->cnt; i++)
	{
		printf("%d ", pArr->elem[i]);
	}
	printf("\n");

	return;
}

void combine(struct Array* A, struct Array* B)
{
	Elemtype * C = (Elemtype*)realloc(A->elem, sizeof(Elemtype) * (A->len + B->len + 2));
	if (C)
	{
		A->elem = C;
		int i, j, k;
		for (i = 0; i < A->cnt; i++)
			A->elem[A->cnt - 1 - i + B->cnt] = A->elem[A->cnt - 1 - i];

		i = B->cnt, j = 0, k = 0;
		
		
		while (i < A->cnt+B->cnt && j < B->cnt)
		{
			if (k == 0 || (A->elem[i] != A->elem[k - 1] && B->elem[j] != A->elem[k - 1]))
				A->elem[k++] = A->elem[i] < B->elem[j] ? A->elem[i++] : B->elem[j++];
			else
			{
				if (A->elem[i] == A->elem[k - 1])
					i++;
				if (B->elem[j] == A->elem[k - 1])
					j++;
			}
		}
		while (i < A->cnt + B->cnt)
			if (A->elem[i] != A->elem[k - 1])
				A->elem[k++] = A->elem[i++];
			else
				i++;
		while (j < B->cnt)
			if (B->elem[j] != A->elem[k - 1])
				A->elem[k++] = B->elem[j++];
			else
				j++;
		A->cnt = k;
	}
	return;
}

int main()
{
	//声明一个整型数组，数组的类型可以在inin_arry()函数内部自行定义，此程序已默认定义为int类型数组
	struct Array A,B;
	int n;
	printf("请输入顺序表A的元素个数：");
	scanf("%d", &n);
	init_arry(&A, n);
	int i,e;
	for (i = 0; i < n; i++)
	{
		scanf("%d", &e);
		append_arry(&A, e);
	}
	printf("请输入顺序表B的元素个数：");
	scanf("%d", &n);
	init_arry(&B, n);
	for (i = 0; i < n; i++)
	{
		scanf("%d", &e);
		append_arry(&B, e);
	}

	//排序
	sort_arry(&A);
	sort_arry(&B);
	//合并
	combine(&A, &B);
	//输出结果		
	printf("合并后：");
	show_arry(&A);

	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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196

运行结果：