顺序表_设计一个算法,判断顺序表是否是有序表(有序表是指表中所有元素是递增的或递减

动态顺序表

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#define InitSize 10//默认最大长度
#define NULLVal INT_MIN;
typedef int ElemType;

typedef struct {
	ElemType *data;//指示动态分配数组的指针
	int length;//顺序表的最大容量
	int MaxSize;//顺序表的当前长度
}SqList;

//初始化顺序表
bool InitList(SqList& L) {
	//用malloc函数申请一片连续的存储空间
	L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);
	if (L.data == NULL) {
		return false;
	}
	L.length = 0;
	L.MaxSize = InitSize;
	return true;
}

//增加动态数组长度
void IncreaseSize(SqList& L, int len) {
	ElemType* p = L.data;
	L.data = (ElemType *)malloc(sizeof(ElemType) * (InitSize+len));
	for (int i = 0; i < L.length; i++) {
		L.data[i] = p[i];//将数据复制到新区域
	}
	L.MaxSize = L.MaxSize + len;//顺序表最大长度增加len
	free(p);//释放原来的内存空间
}


//顺序表插入 时间复杂度:O(n)
bool ListInsert(SqList& L, int i, ElemType e) {
	if (i <= 0 || i > L.length + 1) {//判断i的范围是否有效
		return false;
	}
	if (L.length >= L.MaxSize) {//当前存储空间已满,不能插入
		return false;
	}
	for (int j = L.length; j >= i; j--) {//第i个元素之后的元素后移
		L.data[j] = L.data[j - 1];
	}
	L.data[i - 1] = e;//在位置插入
	L.length++;//长度加1
	return true;
}

//顺序表的删除 时间复杂度O(n)
bool ListDelete(SqList& L, int i, ElemType& e) {
	if (i <= 0 || i > L.length) {//判断i的范围是否有效
		return false;
	}
	e = L.data[i - 1];//将被删除的元素赋值给e
	for (int j = i; j < L.length; j++) {//将第i个位置后的元素前移
		L.data[j - 1] = L.data[j];
	}
	L.data[L.length - 1] = 0;
	L.length--;//线性表长度减一
	return true;
}


//顺序表的按位查找 时间复杂度O(1)
ElemType GetElem(SqList L, int i) {
	if (i <= 0 || i > L.length) {
		return NULLVal;
	}
	return L.data[i - 1];
}

//顺序表的按值查找 时间复杂度O(n)
int LocateElem(SqList L, int e) {
	for (int i = 0; i < L.length; i++) {
		if (L.data[i] == e) {//如果数据类型为结构体类型,需比较结构体内的元素相等
			return i + 1;//数组下标为i的元素值等于e，返回其位序i+1
		}
	}
	return 0; //退出循环，说明查找失败
}

//判断顺序表是否为空
bool ListEmpty(SqList L) {
	return L.length == 0;
}

//创建
bool ListCreate(SqList& L) {
	int  n;
	printf("请输入创建数据的个数:");
	scanf("%d", &n);
	//printf("\n");
	for (int i = 1; i <= n; i++) {
		ElemType e;
		printf("请输入第%d个数据:", i);
		scanf("%d", &e);
		//printf("\n");
		bool b = ListInsert(L, i, e);
		if (b == false)
			printf("插入失败\n");
	}
	return true;
}

//打印
void PrintList(SqList L) {
	for (int i = 0; i < L.length; i++) {
		printf("%5d", L.data[i]);
	}
	printf("\n");
}

//销毁
bool DestroyList(SqList& L) {
	free(L.data);
	L.length = 0;
	L.MaxSize = 0;
	return true;
}
int main() {
	SqList L;//声明一个顺序表
	InitList(L);//初始化顺序表
	//数据的插入
	ListCreate(L);//创建顺序表
	printf("%d\n", L.length);
	//数据的位置
	int i = LocateElem(L, 5);
	printf("查找的数字位置是%d\n", i);
	//数据的值
	ElemType e = GetElem(L, 3);
	printf("查找的位置数字是%d\n", e);
	//数据的删除
	ListDelete(L, 1, e);
	printf("删除的值是%d,删除后的长度为%d\n", e, L.length);
	//顺序打印
	PrintList(L);
	//顺序表销毁
	DestroyList(L);
	//判断顺序表是否为空
	if (ListEmpty(L) == true) {
		printf("顺序表为空\n");
	}
	else {
		printf("顺序表不为空\n");
	}
	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

静态顺序表

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define NULLVal INT_MIN;
#define MaxSize 100//定义最大长度
typedef int ElemType;

typedef struct {
	ElemType data[MaxSize];//用静态的"数组"存储数据元素
	int length;//顺序表
	int maxsize;
}SqList;//顺序表的类型定义

//初始化静态顺序表
bool InitList(SqList& L) {
	for (int i = 0; i < MaxSize; i++) {
		L.data[i] = 0;//将所有元素设为默认初始值
	}
	L.length = 0;//顺序表初始长度为0
	L.maxsize = MaxSize;
	return true;
}

//顺序表插入 时间复杂度:O(n)
bool ListInsert(SqList& L, int i, ElemType e) {
	if (i <= 0 || i > L.length+1) {//判断i的范围是否有效
		return false;
	}
	if (L.length >= MaxSize) {//当前存储空间已满,不能插入
		return false;
	}
	for (int j = L.length; j >= i; j--) {//第i个元素之后的元素后移
		L.data[j] = L.data[j - 1];
	}
	L.data[i - 1] = e;//在位置插入
	L.length++;//长度加1
	return true;
}

//顺序表的删除 时间复杂度O(n)
bool ListDelete(SqList& L, int i, ElemType& e) {
	if (i <= 0 || i > L.length) {//判断i的范围是否有效
		return false;
	}
	e = L.data[i - 1];//将被删除的元素赋值给e
	for (int j = i; j < L.length; j++) {//将第i个位置后的元素前移
		L.data[j-1] = L.data[j];
	}
	L.data[L.length - 1] = 0;
	L.length--;//线性表长度减一
	return true;
}


//顺序表的按位查找 时间复杂度O(1)
ElemType GetElem(SqList L, int i) {
	if (i <= 0 || i > L.length) {
		return NULLVal;
	}
	return L.data[i - 1];
}

//顺序表的按值查找 时间复杂度O(n)
int LocateElem(SqList L, int e) {
	for (int i = 0; i < L.length; i++) {
		if (L.data[i] == e) {//如果数据类型为结构体类型,需比较结构体内的元素相等
			return i+1;//数组下标为i的元素值等于e，返回其位序i+1
		}
	}
	return 0; //退出循环，说明查找失败
}

//判断顺序表是否为空
bool ListEmpty(SqList L) {
	return L.length == 0;
}

//顺序表的创建
bool ListCreate(SqList& L) {
	int  n;//元素个数
	printf("请输入创建数据的个数:");
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		ElemType e;//元素值
		printf("请输入第%d个数据:", i);
		scanf("%d", &e);
		bool b = ListInsert(L, i, e);//后插法
		if (b == false)//是否插入成功
		printf("插入失败\n");
	}
	return true;
}

//顺序表顺序打印
void PrintList(SqList L) {
	for (int i = 0; i < L.length; i++) {
		printf("%5d", L.data[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
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

提升

//扩展提升
//删除顺序表中最小元素,并由函数返回被删元素,空出的位置由最后一个元素填充
bool Del_Min(SqList &L, ElemType& e) {
	if (L.length == 0) {
		return false;
	}
	e = L.data[0];
	int pos = 0;
	for (int i = 1; i < L.length; i++) {
		if (L.data[i] < e) {
			e = L.data[i];
			pos = i;
		}
	}
	L.data[pos] = L.data[L.length - 1];
	L.length--;
	return true;
}

//元素逆置
void Reverse(SqList& L) {
	//交换前后对称位置的值
	for (int i = 0; i < L.length/2; i++) {
		ElemType temp = L.data[i];
		L.data[i] = L.data[L.length - i - 1];
		L.data[L.length - i - 1] = temp;
	}
}

//删除所有值为x的元素,时间复杂度O(n),空间复杂度O(1)
//方法一
void Del_x_1(SqList& L, ElemType x) {
	int k = 0;//记录值等于x的元素个数
	for (int i = 0; i < L.length; i++) {
		if (L.data[i] == x) {
			k++;
		}
		else {
			L.data[i - k] = L.data[i];//当前元素前移k个位置
		}
	}
	L.length -= k;//顺序表L的长度减少k个
}
//方法二
void Del_x_2(SqList& L, ElemType x) {
	int k = 0;//记录值不等于x的元素个数
	for (int i = 0; i < L.length; i++) {
		if (L.data[i] != x) {
			L.data[k] = L.data[i];
			k++;//不等于x的元素增一
		}
	}
	L.length = k;//顺序表长度等于k
}

//删除顺序表元素值在s与t之间的所有元素,包含s和t
bool Del_s_t1(SqList& L, ElemType s, ElemType t) {
	if (s >= t || L.length == 0) {//线性表为空,s或t不符合,返回
		return false;
	}
	int k = 0;
	for (int i = 0; i < L.length; i++) {
		if (L.data[i] < s|| L.data[i] > t) {
			L.data[k] = L.data[i];//当前元素前移k个位置
			k++;
		}
	}
	L.length = k;//长度减小
	return true;
}

//删除有序顺序表元素值在s与t之间,包含s和t
bool Del_s_t2(SqList& L, ElemType s, ElemType t) {
	if (s >= t || L.length == 0) {
		return false;
	}
	int i = 0;
	for (; i < L.length && s > L.data[i]; i++);//寻找大于等于s的第一个元素
	if (i >= L.length) {
		return false;//所有值均小于s,返回
	}
	int j = i;
	for (; j < L.length && t >= L.data[j]; j++);//寻找大于t的第一个元素
	for (; j < L.length; i++, j++) {
		L.data[i] = L.data[j];//前移,填补被删元素的位置
	}
	L.length = i;
	return true;
}

//从有序表中删除值重复的元素,使表中所有元素均不同
bool Del_Same(SqList& L) {
	if (L.length == 0) {
		return false;
	}
	int k = 0;//k存储第一个不相同元素位置
	for (int i = 1; i < L.length; i++) {
		if (L.data[i] != L.data[k]) {//查找下一个与上一个元素值不同的元素
			L.data[++k] = L.data[i];//找到后将元素前移
		}
	}
	L.length = k+1;
	return true;
}

//将两个有序表合并为一个有序表
bool Merge(SqList L1, SqList L2, SqList& L3) {
	if (L1.length + L2.length > L3.maxsize) {
		return false;
	}
	int i = 0, j = 0, k = 0;
	while (i < L1.length || j < L2.length) {
		if (i >= L1.length) {//当L1遍历完,只需存储L2的剩余元素
			L3.data[k++] = L2.data[j++];
		}
		else if (j >= L1.length) {//当L2遍历完,只需存储L1的剩余元素
			L3.data[k++] = L2.data[i++];
		}
		else if (L1.data[i] <= L2.data[j]) {//当L1比L2小,存储L1的当前元素
			L3.data[k++] = L1.data[i++];
		}
		else {//当L2比L1小,存储L2的当前元素
			L3.data[k++] = L2.data[j++];
		}
	}
	L3.length = k;
	return true;
}

//将顺序表[M+N]切分为两部分A和B,将AB调换位置,变为BA,如{a1,a2,a3,a4,a5},A={a1,a2},B={a3,a4,a5},调换为{a3,a4,a5,a1,a2}
void reverse(SqList& L, int left, int right) {
	while (left < right) {
		ElemType temp = L.data[left];
		L.data[left] = L.data[right];
		L.data[right] = temp;
		left++;
		right--;
	}
}

void Exchange(SqList& L, int m, int n) {
	if (m<0||n<0||m + n > L.length) {
		return;
	}
	reverse(L, 0, m + n - 1);
	reverse(L, 0, m - 1);
	reverse(L, m, m + n - 1);
}

//用最少时间查找有序顺序表值为x的元素,若存在与其后继元素交换位置,不存在则将其插入表中,是顺序表依然有序
void SearchExchangeInsert(SqList& L, ElemType x) {
	int left = 0, right = L.length - 1, mid;
	while (left <= right) {//二分查找
		mid = (left + right) / 2;
		if (L.data[mid] == x) {
			break;
		}
		else if (L.data[mid] < x) {
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}
	if (mid!=L.length-1&&L.data[mid] == x) {//位置调换
		ElemType temp = L.data[mid];
		L.data[mid] = L.data[mid + 1];
		L.data[mid + 1] = temp;
	}
	if(left>right){
		for (int i = L.length; i > right; i--) {//插入元素
			L.data[i] = L.data[i - 1];
		}
		L.data[mid] = x;
		L.length++;
	}
}

//找数组中未出现的最小正数
int findMissMin(int A[], int n) {
	int *B = (int *)malloc(sizeof(int) * n);
	memset(B, 0, sizeof(int) * n);
	for (int i = 0; i < n; i++) {
		if (A[i] >= 1 && A[i] <= n) {
			B[A[i]-1] = 1;
		}
	}
	int i;
	for (i = 0; i < n; i++) {
		if (B[i] == 0)
			break;
	}
	return i+1;
}

//找非负整数数组中的主元素,主元素:出现次数超过数组长度一半的数,找到返回该数,找不到返回-1
//方法一:hash
//例[1,2,1,1]主元素为1,例[1,2,1,2]无主元素
//时间复杂度O(n),空间复杂度O(n)
int findMainElem(int A[], int n){
	int *hash = (int *)malloc(sizeof(int)*n);
	for(int i = 0; i < n; i++){
		hash[i] = 0;
	}
	for(int i = 0; i < n; i++){
		hash[A[i]]++;
		if(hash[A[i]] > n/2){
			return A[i];
		}
	}
	return -1;
}

//方法二
//时间复杂度O(n),空间复杂度O(1)
int findMainElem(int A[], int n){
	int count = 0, mainElem;
	for(int  i = 0; i < n; i++){
		if(count==0 || mainElem == A[i]){
			mainElem = A[i];
			count++;
		}else{
			count--;
		}
	}
	if(count == 0){
		return -1;	
	}
	count = 0;
	for(int i = 0; i < n; i++){
		if(A[i] == mainElem){
			count++;
		}
	}
	if(count >n/2){
		return mainElem;
	}else{
		return -1;
	}
}


int main() {
	SqList L;//声明一个顺序表
	InitList(L);//初始化顺序表
	//数据的插入
	ListCreate(L);//创建顺序表
	printf("%d\n", L.length);
	数据的位置
	//int i = LocateElem(L, 5);
	//printf("查找的数字位置是%d\n", i);
	数据的值
	//ElemType e = GetElem(L, 3);
	//printf("查找的位置数字是%d\n", e);
	数据的删除
	//ListDelete(L,1,e);
	//printf("删除的值是%d,删除后的长度为%d\n", e,L.length);
	判断顺序表是否为空

	删除最小值
	//ElemType e;
	//Del_Min(L, e);
	//printf("删除的最小值是%d\n", e);
	//printf("长度%d\n", L.length);

	逆置元素
	//Reverse(L);
	//PrintList(L);

	删除值为x的元素
	//Del_x_1(L, 5);
	//PrintList(L);
	//printf("长度%d\n", L.length);
	//Del_x_2(L, 2);
	//PrintList(L);
	//printf("长度%d\n", L.length);
	
	//删除s和t之间的元素
	/*Del_s_t2(L, 2, 5);
	PrintList(L);
	printf("长度%d\n", L.length);*/

	//删除重复元素
	/*Del_Same(L);
	PrintList(L);
	printf("长度%d\n", L.length);*/

	//合并有序表
	/*SqList L3;
	InitList(L3);
	Merge(L, L, L3);
	PrintList(L3);
	printf("长度%d\n", L3.length);*/

	//交换顺序表
	/*Exchange(L, 2, 3);
	PrintList(L);
	printf("长度%d\n", L.length);*/

	//查找交换插入元素
	for (int i = 0; i < 5; i++) {
		ElemType x;
		printf("输入插入的数据:");
		scanf("%d", &x);
		SearchExchangeInsert(L, x);
		PrintList(L);
		printf("长度%d\n", L.length);
	}
	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
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310