数据结构—顺序表的基本操作和实现（C++）

顺序表是采用顺序储存结构的线性表

顺序表相邻的数据元素储存在相邻的物理储存单元中

顺序表的基本操作包括初始化、查找、插入、删除、交换、逆序和更改，本文以C++为例实现了这些操作

#include

using namespace std;

#define ElemType int
#define LIST_INIT_SIZE 100   //初始化最大表长为100
#define LISTINCREMENT 10     //约定每次扩容时增加10个元素

typedef struct {
	ElemType* elem;     //本实现方式不直接储存数组，而是初始化顺序表时动态开辟数组，这里储存该数组的指针
	int length;         //顺序表元素个数
	int listsize;       //顺序表最大长度，初始为LIST_INIT_SIZE（以ElemType为单位）
	int incrementsize;  //约定每次扩表增加incrementsize个元素，以LISTINCREMENT为初始值（以ElemType为单位）
}SqList;

//顺序表初始化函数
void InitList_Sq(SqList& L) {
	L.elem = new ElemType[LIST_INIT_SIZE];
	L.length = 0;
	L.listsize = LIST_INIT_SIZE;
	L.incrementsize = LISTINCREMENT;
}

//构建顺序表，依次输入前n个数据
bool CreateList_Sq(SqList& L, int n) {
	if (n<0 || n>L.listsize) { return false; }
	L.length = n;
	for (int i = 0; i < L.length; i++) {
		cin >> L.elem[i];
	}
	return true;
}

//查找函数（查找表内是否含有特定元素，若存在该元素，则返回该序列（从1开始）,未找到则返回0）
int LocateElem_sq(SqList& L, ElemType a) {
	ElemType* p = L.elem;
	for (int i = 0; i < L.length; i++) {
		if (p[i] == a) { return i + 1; }   //注意顺序表序号从1开始，而数组从0开始
	}
	return 0;
}

//插入函数（在第i个元素前插入元素e）
void increment(SqList& L);           //顺序表扩容函数的声明，定义下面给出
bool ListInsert_Sq(SqList& L, int i, ElemType e) {
	if (i<1 || i>L.length) { return false; }
	if (L.length >= L.listsize) { increment(L); }   //若表长已经等于当前允许的最大值，则顺序表扩容
	ElemType tem1, tem2;
	tem1 = e;
	for (int j = 0; j < L.length - i + 1; j++) {
		tem2 = L.elem[i + j - 1];
		L.elem[i + j - 1] = tem1;
		tem1 = tem2;
	}
	L.elem[L.length] = tem2;
	L.length++;
	return true;
}
void increment(SqList &L) {
	ElemType* p = new ElemType[L.listsize + L.incrementsize];
	for (int i = 0; i < L.length; i++) {
		p[i] = L.elem[i];
	}
	delete[] L.elem;
	L.elem = p;
	L.listsize += L.incrementsize;
 }

//删除函数（删除第i项数据）
bool DeleteElem_Sq(SqList& L, int i) {
	if (i<1 || i>L.length) { return false; }
	for (int j = i; j < L.length; j++) {
		L.elem[j - 1] = L.elem[j];
	}
	L.length--;
	return true;
}

//交换函数（交换顺序表第i项和第j项）
bool SwapList_Sq(SqList& L, int i, int j) {
	if (i<1 || i>L.length) { return false; }
	if (j<1 || j>L.length) { return false; }
	ElemType tem;
	tem = L.elem[i - 1];
	L.elem[i - 1] = L.elem[j - 1];
	L.elem[j - 1] = tem;
	return true;
}

//逆序函数（将顺序表反向排列，即第一位变为最后一位）
void ReverseList_Sq(SqList& L) {
	for (int i = 0; i < L.length / 2; i++) {
		ElemType tem;
		tem = L.elem[i];
		L.elem[i] = L.elem[L.length - i - 1];
		L.elem[L.length - i - 1] = tem;
	}
}

//更改函数（将第i个元素改为e）
bool ChangeElem_Sq(SqList& L, int i, ElemType e) {
	if (i<1 || i>L.length) { return false; }
	L.elem[i - 1] = e;
	return true;
}

//输出顺序表
void showlist(SqList& L) {
	for (int i = 0; i < L.length; i++) {
		cout << L.elem[i] << ' ';
	}
	cout << endl;
}


int test01() {
	SqList L;
	InitList_Sq(L);
	CreateList_Sq(L, 5); showlist(L);
	LocateElem_sq(L, 3); showlist(L);
	ListInsert_Sq(L, 2, 100); showlist(L);
	DeleteElem_Sq(L, 2); showlist(L);
	SwapList_Sq(L, 1, 5); showlist(L);
	ReverseList_Sq(L); showlist(L);
	ChangeElem_Sq(L, 1, 100); showlist(L);
	return 0;
}



int test02() {
	SqList L;
	InitList_Sq(L);
	for (int i = 0; i < L.listsize; i++) {
		L.elem[i] = i;
	}
	L.length = 100;
	ListInsert_Sq(L, 1, 100);
	showlist(L);
	return 0;
}