数据结构——顺序表

#include<stdlib.h>
#include<iostream>
using namespace std;

#define MAXSIZE 100
#define OVERFLOW -2
#define ERROR -1
#define OK 1

typedef int Status;
typedef int ElemType;  // 非整型

// 结点结构体
typedef struct {
	ElemType* elem;
	int length;
	// int listsize;
}Sqlist;

// 初始化顺序表
Status InitList_Sq(Sqlist& L)
{
	L.elem = new ElemType[MAXSIZE];
	if (!L.elem) exit(OVERFLOW);
	L.length = 0;
	return OK;
}

// 销毁顺序表
void DestroyList(Sqlist& L)
{
	if (!L.elem)
		delete[] L.elem;
}

// 清空顺序表
void ClearList(Sqlist& L)
{
	L.length = 0;
}

// 获取顺序表的长度
int GetLength(Sqlist L)
{
	return L.length;
}

// 判断顺序表是否为空
int IsEmpty(Sqlist L)
{
	if (!L.elem)
		return 1;
	else
		return 0;
}

/*Status insert(Sqlist& L, int i, ElemType e)
{
	int j;
	if (i < 1 || i > L.length + 1)
		return ERROR;
	if (L.length == MAXSIZE)
		return OVERFLOW;
	for (j = L.length - 1; j >= i - 1; j--)
		L.elem[j + 1] = L.elem[j];
	L.elem[i - 1] = e;
	L.length++;
	return OK;
}*/

// 在 i 处插入元素
Status ListInsert_Sq(Sqlist& L, int i, ElemType e)
{
	// 在顺序表L的第 i 个元素之前插入新的元素e
	if (i < 1 || i > L.length + 1)
		return ERROR;
	if (L.length == MAXSIZE)
		return OVERFLOW;
	ElemType* p, * q;
	q = &(L.elem[i - 1]);
	for (p = &(L.elem[L.length - 1]); p >= q; p--)
		* (p + 1) = *p;
	*q = e;
	L.length++;
	return OK;
}


/*Status insert(Sqlist& L, int i, ElemType e)
{
	if (i < 1 || i > L.length + 1)
		return ERROR;
	if (L.length == MAXSIZE)
		return OVERFLOW;
	int* p, * q;
	q = L.elem + i - 1;
	for (p = L.elem + L.length - 1; p >= q; p--)
		* (p + 1) = *p;
	*q = e;
	L.length++;
	return OK;
}*/

// 获取 i 处元素的值，并将其保存在 e 中
Status GetElem(Sqlist L, int i, ElemType& e)
{
	if (i < 1 || i > L.length) return ERROR;
	e = L.elem[i - 1];
	return OK;
}

// 在顺序表中查找值为 e 的元素，并返回其位置
int Search(Sqlist L, ElemType e) // 多种查找方式
{
	int i;
	for (i = 0; L.elem[i] != e && i < L.length; i++);
	if (i < L.length) return i + 1;
	else return 0;
}

/*int LocateElem(Sqlist L, ElemType e)
{
	// 在顺序表 L 中查找值为 e 的数据元素， 返回其序号
	for(i = 0; i < L.length; i ++)
		if(L.elem[i] == e) return i + 1;
	return 0;
}*/

// 删除顺序表中位置为 i 的元素，并将其值保存在 e 中
Status ListDelete(Sqlist &L, int i, ElemType& e) 
{
	if (i < 1 || i > L.length) return ERROR;
	e = L.elem[i - 1];
	int j;
	for (j = i; j < L.length; j++)
		L.elem[j - 1] = L.elem[j];
	L.length--;
	return OK;
}

// 创建顺序表
Status Create(Sqlist& L, int n)
{
	int i;
	if (n < 0) return ERROR;
	for (i = 0; i < n; i++)
		cin >> L.elem[i];
	L.length = n;
	return OK;
}

// 输出顺序表
void OutPut(Sqlist L)
{
	int i;
	for (i = 0; i < L.length; i++)
		cout << L.elem[i] << " ";
	cout << endl;
}

int main()
{
	// 以下为测试代码
	Sqlist L;
	int n, i, e;
	cout << "请输入顺序表的长度：";
	cin >> n;
	InitList_Sq(L);
	cout << "请输入数据：";
	Create(L, n);
	cout << "输出数据：";
	OutPut(L);
	cout << "顺序表的长度为：" << GetLength(L) << endl;  // 获取顺序表长度
	cout << IsEmpty(L) << endl;  // 查看顺序表是否为空
	cout << "请输入要查找的值：";
	cin >> e;
	cout << e << "所在位置为：" << Search(L, e) << endl;  // 查找
	cout << "请输入删除值的位置：";
	cin >> i;
	ListDelete(L, i, e);
	cout << "删除成功！ " << "您删除的值为：" << e << endl;
	cout << "此时的顺序表为：";
	OutPut(L);
	cout << "请输入您插入的位置：";
	cin >> i;
	cout << "请输入您要插入的值：";
	cin >> e;
	cout << ListInsert_Sq(L, i, e) << endl;
	cout << "此时的顺序表为：";
	OutPut(L);
	cout << "此时顺序表的长度为：" << GetLength(L) << endl;
	ClearList(L);
	cout << "此时顺序表的长度为：" << GetLength(L) << endl;
	DestroyList(L);
	return 0;
}

请输入顺序表的长度：5

请输入数据：1 2 3 4 5

输出数据：1 2 3 4 5

顺序表的长度为：5

0

请输入要查找的值：2

2所在位置为：2

请输入删除值的位置：3

删除成功！ 您删除的值为：3

此时的顺序表为：1 2 4 5

请输入您插入的位置：3

请输入您要插入的值：6

1

此时的顺序表为：1 2 6 4 5

此时顺序表的长度为：5

此时顺序表的长度为：0

请按任意键继续. . .