[数据结构与算法]（一）顺序表

（一）顺序表

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

顺序表的数据结构：

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

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

有以下主要的功能函数：

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;
}