顺序表（C/C++）

        本篇将讲解一些关于顺序表的内容，顺序表分为静态顺序表和动态顺序表，其中经常用到的为动态顺序表，所以本篇将以动态顺序表为重点给出一些关于动态顺序表的操作。

        因为顺序表的实现逻辑较为简单，对于代码的讲解大多以注释给出。

1.顺序表相关操作

        以下包括顺序表的抽象类型定义、两种顺序表的定义方式、以及一些相关操作：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

//元素类型
typedef int DataType;
//静态表元素个数
#define MAX_SIZE 10

//静态顺序表
typedef struct {       
	DataType arr[MAX_SIZE];
	int size;
}SL;

//动态顺序表
typedef struct {       
	DataType* arr;
	int size;         
	int capacity;
}SqList;

//顺序表初始化
void SLInit(SqList* ps);	

//顺序表尾插/头插
void SLPushBack(SqList* ps,DataType x); 
void SLPushFront(SqList* ps, DataType x);

//顺序表尾部删除/头部删除
void SLPopBack(SqList* ps);
void SLPopFront(SqList* ps);

//指定位置之前插入/删除数据
void SLInsert(SqList* ps, int position, DataType x);
void SLErase(SqList* ps, int position);

//在顺序表中找到相关的元素
int SLFind(SqList* ps, DataType x);

//打印顺序表
void SLPrint(SqList* ps);				

2.顺序表的插入与初始化 

        顺序表的插入包括头插和尾插，头插就是在顺序表的第一个元素位置插入，尾插就是在最后一个元素后面插入。

//顺序表的初始化
void SLInit(SqList* ps) {
	ps->arr = NULL;
	ps->capacity = 0;
	ps->size = 0;
}

//检查顺序表的当前容量
void SLCheckCapacity(SqList* ps) {
	if (ps->capacity == ps->size) {
        //三目操作符对容量进行分配
		int newCapacity = (ps->capacity == 0) ? 4 : 2 * ps->capacity; 
		DataType* newBase = (DataType*)realloc(ps->arr, newCapacity * sizeof(DataType));
		if (newBase == NULL) {
			perror("realloc:");
			exit(1);
		}
		ps->arr = newBase;
		ps->capacity = newCapacity;
	}
}


//头插
void SLPushFront(SqList* ps, DataType x) {
	SLCheckCapacity(ps);
	int count = ps->size;
    //将所有元素都向后移一位
	while (count != 0) {
		ps->arr[count] = ps->arr[count - 1];
		count--;
	}
	ps->arr[count] = x;
	ps->size++;
}

//尾插
void SLPushBack(SqList* ps,DataType x) {
	SLCheckCapacity(ps);
	ps->arr[ps->size] = x;
	ps->size++;
}

3.顺序表的删除 

        以下为顺序表的头部删除和尾部删除。

//尾删
void SLPopBack(SqList* ps) {
    //检查顺表是否存在，以及容量是否为0
	assert(ps);
	assert(ps->size);
	ps->size--;
}

void SLPopFront(SqList* ps) {
	assert(ps);
	assert(ps->size);
    //将所有元素都向前覆盖
	for (int i = 0; i < ps->size - 1; i++) {
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

4.顺序表的指定插入与删除

        以下的代码对指定位置的插入与删除：

//指定位置插入
void SLInsert(SqList* ps, int position, DataType x) {
    //判断位置是否合法
	assert(position >= 0 && position <= ps->size);
    assert(ps);
	for (int i = ps->size; i > position; i--) {
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[position] = x;
	ps->size++;
}

//指定位置删除
void SLErase(SqList* ps, int position) {
	assert(ps);
	assert(position >= 0 && position < ps->size);
    //从指定位置开始往前覆盖
	for (int i = position; i < ps->size - 1; i++) {
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

5.顺序表的查找以及遍历 

        顺序表的查找为在表中找到对应的元素，遍历就是将所有元素给打印出来：

//顺序表的遍历
void SLPrint(SqList* ps) {
	assert(ps);
	assert(ps->size);
	for (int i = 0; i < ps->size; i++) {
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}

//顺序表的查找
int SLFind(SqList* ps, DataType x) {
	assert(ps);
	assert(ps->size);
	int i = 0;
	for (i = 0; i < ps->size; i++) {
		if (ps->arr[i] == x) {
			return i + 1;
		}
	}
	return -1;
}

6.全部代码

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

//元素类型
typedef int DataType;

//动态顺序表
typedef struct {       
	DataType* arr;
	int size;         
	int capacity;
}SqList;

void SLInit(SqList* ps) {
	ps->arr = NULL;
	ps->capacity = 0;
	ps->size = 0;
}

void SLCheckCapacity(SqList* ps) {
	if (ps->capacity == ps->size) {
		int newCapacity = (ps->capacity == 0) ? 4 : 2 * ps->capacity;
		DataType* newBase = (DataType*)realloc(ps->arr, newCapacity * sizeof(DataType));
		if (newBase == NULL) {
			perror("realloc:");
			exit(1);
		}
		ps->arr = newBase;
		ps->capacity = newCapacity;
	}
}

//尾插
void SLPushBack(SqList* ps,DataType x) {
	SLCheckCapacity(ps);//检验容量
	ps->arr[ps->size] = x;
	ps->size++;
}

//头插
void SLPushFront(SqList* ps, DataType x) {
	SLCheckCapacity(ps);
	int count = ps->size;
	while (count != 0) {
		ps->arr[count] = ps->arr[count - 1];
		count--;
	}
	ps->arr[count] = x;
	ps->size++;
}

void SLPrint(SqList* ps) {
	assert(ps);
	assert(ps->size);
	for (int i = 0; i < ps->size; i++) {
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}
	
void SLPopBack(SqList* ps) {
	assert(ps);
	assert(ps->size);
	ps->size--;
}

void SLPopFront(SqList* ps) {
	assert(ps);
	assert(ps->size);
	for (int i = 0; i < ps->size - 1; i++) {
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

void SLInsert(SqList* ps, int position, DataType x) {
	assert(position >= 0 && position <= ps->size);
	for (int i = ps->size; i > position; i--) {
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[position] = x;
	ps->size++;
}

void SLErase(SqList* ps, int position) {
	assert(ps);
	assert(position >= 0 && position < ps->size);
	for (int i = position; i < ps->size - 1; i++) {
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

int SLFind(SqList* ps, DataType x) {
	assert(ps);
	assert(ps->size);
	int i = 0;
	for (i = 0; i < ps->size; i++) {
		if (ps->arr[i] == x) {
			return i + 1;
		}
	}
	return -1;
}

int main() {
	SqList SL;
	SLInit(&SL);
	SLPushBack(&SL, 1);
	SLPushBack(&SL, 2);
	SLPushBack(&SL, 3);
	SLPushBack(&SL, 4);
	SLPrint(&SL);  //1 2 3 4

	SLPushFront(&SL, 7);
	SLPushFront(&SL, 6);
	SLPushFront(&SL, 5);
	SLPrint(&SL);  //5 6 7 1 2 3 4

	SLPopBack(&SL);
	SLPopBack(&SL);
	SLPopFront(&SL);
	SLPrint(&SL);  //6 7 1 2

	SLErase(&SL, 0);
	SLInsert(&SL, 2, 9);
	SLPrint(&SL);  //7 1 9 2

	int ret = SLFind(&SL, 9);
	if (ret == -1) {
		printf("have not the element\n");
	}
	else {
		printf("the location of element is %d\n", ret);
	}
	return 0;
}

7.测试