【数据结构】线性表的顺序存储（顺序表）及基本操作——C语言

线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在连续的物理存储单元中，即通过数据元素物理存储的连续性来反映数据元素之间逻辑上的相邻关系。采用顺序存储结构存储的线性表通常简称为顺序表。

顺序表的基本运算操作包含顺序表初始化、创建、输出、求表长、按序号查找、按值查找、插入、删除、逆置、升序排序、升序合并等。

# include
# define MAXSIZE 100
# define ERROR 0
# define OK 1

typedef int ElemType;

typedef struct {									//线性表的顺序存储结构（静态申请）
	ElemType elem[MAXSIZE];
	int last;
}SeqList;

SeqList L, LB, LC;

void InitList(SeqList* L) {							//顺序表初始化
	L->last = -1;
}

void CreatList(SeqList* L, int n) {					//创建顺序表
	InitList(L);
	int i;
	printf("请输入元素值：");
	for (i = 0; i < n; i++)
		scanf("%d", &L->elem[i]);
	L->last = n - 1;
	printf("创建成功！n");
}

void Display(SeqList* L) {							//顺序表的输出
	int i;
	if (L->last == -1)
		printf("空表！");
	for (i = 0; i <= L->last; i++)
		printf("%d ", L->elem[i]);
}

int ListLength(SeqList* L) {						//求表长
	return (L->last + 1);
}

void GetData(SeqList* L, int n) {					//按序号查找
	if (n < 1 || n > L->last + 1)
		printf("输入序号有误！n");
	else
		printf("序号%d的元素为：%dn", n, L->elem[n - 1]);
}

void Locate(SeqList* L, int n) {					//按值查找
	int i = 0;
	while ((i <= L->last) && (L->elem[i] != n))
		i++;
	if (i <= L->last)
		printf("元素%d的序号为：%dn", n, i + 1);
	else
		printf("未找到该元素！n");
}

int InsList(SeqList* L, int m, int n) {				//元素值插入
	int i;
	if (m<1 || m>L->last + 2) {
		printf("插入的位置不合法！n");
		return (ERROR);
	}
	if (L->last >= MAXSIZE - 1) {
		printf("表已满无法插入！n");
		return (ERROR);
	}
	for (i = L->last; i >= m - 1; i--) {
		L->elem[i + 1] = L->elem[i];
	}
	L->elem[m - 1] = n;
	L->last++;
	printf("插入成功！n");
	return (OK);
}

int DelList(SeqList* L, int m) {					//元素值删除
	int i, e;
	if (m<1 || m>L->last + 1) {
		printf("删除的位置不合法！n");
		return (ERROR);
	}
	e = L->elem[m - 1];
	for (i = m - 1; i <= L->last; i++) {
		L->elem[i] = L->elem[i + 1];
	}
	L->last--;
	printf("删除成功！删除的元素值为%dn", e);
	return (OK);
}

void Inversion(SeqList* L) {						//逆置
	int a, temp, i;
	a = L->last;
	for (i = 0; i <= a / 2; i++) {
		temp = L->elem[i];
		L->elem[i] = L->elem[a - i];
		L->elem[a - i] = temp;
	}
}

void SortList(SeqList* L) {							//升序排序
	int i, j, temp;
	for (i = 0; i <= L->last - 1; i++) {
		for (j = 0; j <= L->last - i - 1; j++) {
			if (L->elem[j] > L->elem[j + 1]) {
				temp = L->elem[j];
				L->elem[j] = L->elem[j + 1];
				L->elem[j + 1] = temp;
			}
		}
	}
}

void MergeList(SeqList* L, SeqList* LB, SeqList* LC) {//升序合并两个顺序表
	int i = 0, j = 0, k = 0;
	while (i <= L->last && j <= LB->last) {
		if (L->elem[i] <= LB->elem[j]) {
			LC->elem[k] = L->elem[i];
			i++;
			k++;
		}
		else {
			LC->elem[k] = LB->elem[j];
			j++;
			k++;
		}
	}
	if (i > L->last) {
		while (j <= LB->last) {
			LC->elem[k] = LB->elem[j];
			j++;
			k++;
		}
	}
	if (j > LB->last) {
		while (i <= L->last) {
			LC->elem[k] = L->elem[i];
			i++;
			k++;
		}
	}
	LC->last = L->last + LB->last + 1;
}


void Menu(int select) {
	int m, n;
	switch (select) {
	case 1:InitList(&L);							//初始化顺序表
		printf("初始化成功！n"); break;
	case 2:printf("请输入顺序表元素个数：");			//创建顺序表
		scanf("%d", &n);
		CreatList(&L, n);
		printf("顺序表元素值为：");
		Display(&L);
		printf("n"); break;
	case 3:printf("输出结果为：");					//输出顺序表
		Display(&L);
		printf("n"); break;
	case 4:printf("长度为：%dn", ListLength(&L)); break;	//求表长
	case 5:printf("请输入要查找的元素序号：");			//按序号查找
		scanf("%d", &n);
		GetData(&L, n); break;
	case 6:printf("请输入要查找的元素值：");			//按值查找
		scanf("%d", &n);
		Locate(&L, n); break;
	case 7:printf("请输入插入的位置及要插入的元素：");	//元素插入
		scanf("%d%d", &m, &n);
		InsList(&L, m, n);
		printf("插入后顺序表元素值为：");
		Display(&L);
		printf("n"); break;
	case 8:printf("请输入要删除的元素位置：");			//元素删除
		scanf("%d", &m);
		DelList(&L, m);
		printf("删除后顺序表元素值为：");
		Display(&L);
		printf("n"); break;
	case 9:printf("逆置结果为：");					//逆置
		Inversion(&L);
		Display(&L);
		printf("n"); break;
	case 10:printf("升序排序结果为：");				//升序排序
		SortList(&L);
		Display(&L);
		printf("n"); break;
	case 11:printf("创建新顺序表n");					//升序合并两个顺序表
		printf("请输入新顺序表元素个数：");
		scanf("%d", &n);
		CreatList(&LB, n);
		printf("新顺序表元素值为：");
		Display(&LB);
		SortList(&L);
		SortList(&LB);
		MergeList(&L, &LB, &LC);
		printf("n升序合并结果为：");
		Display(&LC);
		printf("n"); break;
	default:printf("输入错误！n");
	}
}

int main() {

	InitList(&L);

	printf("------------顺序表基本运算------------n");
	printf("1.初始化t2.创建顺序表n");
	printf("3.输出顺序表t4.求表长n");
	printf("5.按序号查找t6.按值查找n");
	printf("7.元素插入t8.元素删除n");
	printf("9.逆置tt10.升序排序n");
	printf("11.升序合并两个顺序表n");
	printf("0.退出程序n");
	printf("--------------------------------------n");
	int select;
	printf("请选择操作：");
	scanf("%d", &select);
	while (select) {
		Menu(select);
		printf("--------------------------------------n");
		printf("请选择下一操作：");
		scanf("%d", &select);
	}
	printf("退出成功！n");
	return 0;
}