1.1 顺序表_查找元素e是否存在,如果存在输出元素e是顺序表中的第几个元素,如果不存在给

这一章是线性表中顺序表的实现和代码分析。

顺序表的数据结构：

#define MaxSize 50			//线性表最大长度
#define InitSize 100		//表长度的初始定义

/*静态分配*/
typedef struct {
	ElemType data[MaxSize];
	int length;
}SqList;
1
2
3
4
5
6
7
8

有以下主要的功能函数：

1. bool CreateList(SqList &L, int n) 创建顺序表；参数 L：顺序表，n：顺序表长度；功能：创建长度为n的顺序表；时间复杂度O(n)。
2. bool InsertElem(SqList& L, int i, ElemType e) 插入；参数 L：顺序表，i：插入位置（不是下标），e：插入的元素； 功能：在顺序表位置i插入一个元素e；时间复杂度O(n)。
3. bool DeleteElem(SqList& L, int i) 删除；参数 L：顺序表，i：要删除的位置；功能：删除顺序表位置i的元素；时间复杂度O(n)。
4. int LocateElem(SqList& L, ElemType e) 查找；参数 L：顺序表，e：要查找的元素；功能：查找元素e第一次出现的位置并返回；时间复杂度O(n)。
5. bool ReviseElem(SqList& L, int n, ElemType e) 修改；参数 L：顺序表，n：要修改的元素的位置，e：要改成的元素；功能：将n位置的元素修改为e；时间复杂度O(1)。
6. void PrintList(SqList& L) 打印表；参数 L：顺序表；功能：输出顺序表的所有元素；时间复杂度O(n)。

以下是完整代码：

#include<cstdio>
#include<cstdlib>
#include<iostream>

#define ElemType int
#define MaxSize 50			//线性表最大长度
#define InitSize 100		//表长度的初始定义

/*静态分配*/
typedef struct {
	ElemType data[MaxSize];
	int length;
}SqList;

/*初始化*/
void InitList(SqList &L) {
	memset(L.data, 0, sizeof(L));			//将表中的数据初始化0
	L.length = 0;							//表长初始化0
}

/*输入n个数据创建表*/
bool CreateList(SqList& L, int n) {
	InitList(L);							//记得先初始化
	if (n<0 || n>MaxSize)					//判断表长是否合法
		return false;
	for (int i = 0; i < n; i++) {
		scanf("%d", &L.data[i]);
		L.length++;
	}
	return true;
}

/*插入, 在第i个位置插入，i之后的后移*/
bool InsertElem(SqList& L, int i, ElemType e) {
	if (i < 1 || 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;					//在第i个位置上插入e
	L.length++;							//线性表长度+1
	return true;
}

/*删除，将第i个位置的删除,i之后的前移*/
bool DeleteElem(SqList& L, int i) {
	if (i<1 || i>L.length)				//判断i的范围是否有效
		return false;
	for (int j = i; j <= L.length - 1; j++)
		L.data[j - 1] = L.data[j];
	L.length--;
	return true;
}

/*查找，查找表中第一个等于e的元素，若找到则返回此元素第一次出现的位置（不是下标），未找到返回-1*/
int LocateElem(SqList& L, ElemType e) {
	for (int i = 0; i < L.length; i++) {
		if (L.data[i] == e)
			return i + 1;
	}
	return -1;
}

/*修改,输入要修改的元素的位置n将其修改成e*/
bool ReviseElem(SqList& L, int n, ElemType e) {
	if (n<1 || n>L.length)
		return false;
	L.data[n - 1] = e;
	return true;
}

/*输出表的所有元素*/
void PrintList(SqList& L) {
	for (int i = 0; i < L.length; i++) {
		printf("%d ", L.data[i]);
	}
	printf("\n");
}

/*创建表功能*/
void Create(SqList &L) {
	int n;
	printf("输入表长n(n<=50):");
	scanf("%d", &n);
	printf("输入数据:\n");
	CreateList(L, n);
}

/*插入功能*/
void Insert(SqList& L) {
	int n,e;
	while (true)
	{
		printf("输入要插入的位置:");
		scanf("%d", &n);
		if (n >= 1 && n <= L.length+1)
			break;
		printf("输入的位置有误，重新输入!\n");
	}
	printf("输入要插入的元素:");
	scanf("%d", &e);
	InsertElem(L, n, e);
	printf("插入“%d”到位置“%d”！", e, n);
}

/*修改功能*/
void Revise(SqList& L) {
	int n, e;
	while (true)
	{
		printf("输入要被修改的元素的位置：");
		scanf("%d", &n);
		if (n>=1 && n<=L.length)
			break;
		printf("输入的位置有误，重新输入!\n");
	}
	printf("修改为：");
	scanf("%d", &e);
	ReviseElem(L, n, e);
	printf("修改成功！");
}

/*删除功能*/
void Delete(SqList& L) {
	int n;
	while (true)
	{
		printf("输入要删除的元素的位置:");
		scanf("%d", &n);
		if (DeleteElem(L, n)) {
			printf("删除成功!\n");
			break;
		}
		printf("输入的位置有误，重新输入!\n");
	}
}

void Search(SqList& L) {
	int e;
	printf("输入要查找的元素:");
	scanf("%d", &e);
	int n = LocateElem(L, e);
	if (n == -1)
		printf("未找到“%d”\n", e);
	else
		printf("“%d”的位置在%d\n", e, n);
}

void menu() {
	printf("\n\n");
	printf("--------①创建表--------\n");
	printf("--------②插入--------\n");
	printf("--------③修改--------\n");
	printf("--------④删除--------\n");
	printf("--------⑤查找--------\n");
	printf("--------⑥打印表--------\n");
	printf("按“0”退出\n");
	printf("\n\n");
}
int main() {
	SqList L;
	int choice;
	
	while (true) {
		menu();
		scanf("%d", &choice);
		switch (choice)
		{
			case(1):
				Create(L);
				break;
			case(2):
				Insert(L);
				break;
			case(3):
				Revise(L);
				break;
			case(4):
				Delete(L);
				break;
			case(5):
				Search(L);
				break;
			case(6):
				PrintList(L);
				break;
			case(0):
				exit(0);
			default:
				break;
		}
	}
	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