数据结构算法实现-顺序表实现

C++实现数据结构代码，本文参考部分博主代码，仅用于学习

顺序表简单实现

代码如下（示例）：

关于数据结构实现与实践可以参考
数据结构的实践应用

/*
Project: sequence_list(数据结构-顺序表)
Date:    2018/09/12  20191012修改 添加Reverse  20200819修改 添加ClearList
Author:  Frank Yu
CreateList(SqList &L,int n) 参数：顺序表L，顺序表长度n 功能：创建长度为的顺序表 时间复杂度：O(n)
InitList(SqList &L) 参数：顺序表L 功能：初始化 时间复杂度:O(1)
InsertList(SqList &L,int i,ElemType e) 参数:顺序表L,位置i,元素e 功能：位置i处插入元素e 时间复杂度:O(n)
ListDelete(SqList &L,int i) 参数:顺序表L,位置i 功能：删除位置i处元素 时间复杂度:O(n)
LocateElem(SqList L,ElemType e) 参数:顺序表L,元素e 功能：返回第一个等于e的元素的位置 时间复杂度:O(n)
Reverse(SqList &L) 参数：顺序表L 倒置函数 将原顺序表直接倒置
PrintList(SqList L) 参数:顺序表L 功能：遍历L，并输出
SplitSort(SqList &L) 参数：顺序表L 功能：分开奇偶，并分开排序
ClearList(SqList &L) 参数：顺序表L 功能：清空顺序表
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<iostream>
#define MaxSize 100
#define ElemType int
#define Status int
using namespace std;
//顺序表数据结构
typedef struct {
	ElemType data[MaxSize];
	int length;
}SqList;

//初始化顺序表，构造一个空的顺序表
Status InitList(SqList &L) {
	memset(L.data, 0, sizeof(L));
	L.length = 0;
	return 0;
}

//创建顺序表函数，初始化前m个数据
bool CreatList(SqList &L, int m) {
	if (m<0 || m>MaxSize)
		return false;
	for (int i = 0; i < m; i++) {
		cin >> L.data[i];
		L.length++;
	}
	return true;
}
//插入函数，在位置i开始插入数据e    1<=i<=length+1
bool InsertList(SqList &L, int i,ElemType e) {
	if (i<1 || i>L.length+1) {
		cout << "插入位置无效" << endl;
		return false;
	}
	if (L.length >= MaxSize) {
		cout << "当前存储空间已满" << endl;
		return false;
	}
	for (int j = L.length; j >= i; j--) {
		L.data[j] = L.data[j-1];
	}
	L.data[i-1] = e;
	L.length++;
	return true;
}
//删除函数，删除第i个的元素，其余元素依次移动 1<=i<=L.length+1
bool ListDelete(SqList &L, int i) {
	if (i<1 || i>L.length) {
		cout << "位置无效" << endl;
		return false;
	}
	for (int j = i; j < L.length - 1; j++) {
		L.data[j - 1] = L.data[j];
	}
	L.length--;
	return true;
}
//查找函数 按位置从小到大查找第一个值等于e的元素 并返回位置
int LocateElem(SqList L, ElemType e) {
	int i = 0;
	while (i < L.length) {
		if (L.data[i] == e) {
			return i+1;
		}
		i++;
	}
	return 0;
}
//倒置函数 将原顺序表直接倒置
void Reverse(SqList &L) {
	if (L.length) {
		for (int i = 0; i < L.length - 1 - i; i++) {
			int t = L.data[i];
			L.data[i] = L.data[L.length - 1 - i];
			L.data[L.length - 1 - i] = t;
		}
	}
}
//对顺序表进行排序 冒泡排序实现
void ListSort(SqList &L) {
	if (L.length) {
		int temp,flag;
		for (int i = 0; i < L.length - 1; i++) {
			flag = 0;
			for (int j = 0; j < L.length -1- i; j++) {
				if (L.data[j + 1] < L.data[j]) {
					temp = L.data[j + 1];
					L.data[j + 1] = L.data[j];
					L.data[j] = temp;
					flag = 1;
				}
			}
			if (flag == 0)
				break;
		}
	}
}
//清空顺序表
void ClearList(SqList &L) {
	L.length = 0;
}

//输出当前顺序表的元素
void CoutList(SqList L) {
	cout << "当前顺序表的元素为：" << endl;
	int len = 0;
	while (len < L.length) {
		cout << setw(4) << L.data[len];
		len++;
	}
	cout << endl;
}
//创建顺序表函数
void Creat(SqList &L) {
	int n;
	bool flag;
	cout << "输入要创建的顺序表长度: ";
	cin >> n;
	cout << endl;
	cout << "输入顺序表元素: ";
	flag = CreatList(L, n);
	if (flag) {
		cout << "创建成功！" << endl;
		CoutList(L);
	}
	else
		cout << "输入长度非法，创建失败" << endl;
	
}
//插入功能函数 调用InsertList完成顺序表元素插入 调用PrintList函数显示插入成功后的结果
void Insert(SqList &L)
{
	int place; 
	ElemType e; 
	bool flag;
	cout << "请输入要插入的位置(从1开始)及元素:\n";
	cin >> place >> e;
	flag = InsertList(L, place, e);
	if (flag)
	{
		cout << "插入成功！";
		CoutList(L);
	}
}
//删除功能函数 调用ListDelete函数完成顺序表的删除 调用PrintList函数显示插入成功后的结果
void Delete(SqList &L)
{
	int place; bool flag;
	cout << "请输入要删除的位置(从1开始):\n";
	cin >> place;
	flag = ListDelete(L, place);
	if (flag)
	{
		cout << "删除成功！！！\n";
		CoutList(L);
	}
}
//查找功能函数 调用LocateElem查找元素
void Search(SqList L)
{
	ElemType e; int flag;
	cout << "请输入要查找的值:\n";
	cin >> e;
	flag = LocateElem(L, e);
	if (flag)
	{
		cout << "该元素位置为:" << flag << endl;
	}
	else
		cout << "未找到该元素！\n";
}
void menu() {
	cout << setw(6) << "1.创建" << setw(6) << "2.插入" << endl;
	cout << setw(6) << "3.删除" << setw(6) << "4.查找" << endl;
	cout << setw(6) << "5.倒置" << setw(6) << "6.排序" << endl;
	cout << setw(6) << "7.清空" << setw(6) << "8.退出" << endl;
	cout << setw(6) << "9.输出" << endl;
}
int main() {
	SqList L;
	int choice;
	InitList(L);
	while (1) {
		menu();
		cout << "输入选项：";
		cin >> choice;
		if (choice == 8)
			break;
		switch (choice)
		{
			case 1:Creat(L); break;
			case 2:Insert(L); break;
			case 3:Delete(L); break;
			case 4:Search(L); break;
			case 5:Reverse(L); break;
			case 6:ListSort(L); break;
			case 7:ClearList(L); break;
			case 9:CoutList(L); break;
			default:cout << "输入错误！" << endl;
		}
	}
	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

更多内容请访问：https://juzihhu.github.io/