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

即开辟一块连续的内存空间，相当于数组arr

在定义的时候，定义一个length记录下标

所以在尾插和尾删的时候，下标就是length，可以直接进行插入和删除（时间复杂度O（1））

但是 但是 但是 在其他位置插入和删除的时候，需要挪动数据（时间复杂度O（n））

在查找的时候时间复杂度也是O（n）因为需要将顺序表遍历到需要查找的位置

这里我们先定义顺序表的头文件

#pragma once
typedef int ElemType;//可以把下面所有int改为ElemType   ElemType对基本数据类型实现泛型操作
typedef struct Array {
	int* arr;//可动态开辟内存
	int size;//有效数据个数
	int lenght;//记录数组长度
}Array, * PArr;

//初始化结构体成员
void init(PArr parr,int num);
//判满操作
bool isfull(PArr parr);
//判空操作
bool isempty(PArr parr);
// 扩容操作
bool grow_capacity(PArr parr);
//插入操作
void addhead(PArr parr,int value);//头插
void addtail(PArr parr,int value);//尾插
void add_indexvalue(PArr parr,int index,int value);//定向插入
//删除操作
void removehead(PArr parr);//头删
void removetail(PArr parr);//尾删
void removeindex(PArr parr,int index);//定向删除
void removerange(PArr parr,int from_index,int end_index);//区间删除
void removevalue(PArr parr, int value);//定值删除
//修改操作
void change(PArr parr, int oldvalue, int newvalue);//将原有的旧值改为新值
//查找操作
bool contains(PArr parr, int value);//全范围查找
bool containsrange(PArr parr, int begin,int end,int value);//区间查找
//销毁函数
void destory(PArr parr);//内存释放
void show(PArr parr);

这里来定义.cpp文件

需要引入刚才定义过的头文件（#include"array_op.h"）(注意引入自定义的头文件用双引号)

#include"array_op.h"
#include
#include
#include
//初始化结构体成员
void init(PArr parr,int num) {
	assert(parr != NULL);//断言不为空
	parr->arr = (ElemType*)malloc(num*sizeof(ElemType));
	assert(parr->arr!=NULL);
	parr->lenght = num;
	parr->size = 0;
}
//判满操作    针对插入
bool isfull(PArr parr) {
	assert(parr != NULL);
	return parr->size == parr->lenght;
}
//判空操作    针对删除
bool isempty(PArr parr) {
	assert(parr != NULL);
	return parr->size == 0;
}
// 扩容操作
bool grow_capacity(PArr parr) {
	ElemType* p = (int*)realloc(parr->arr, ((parr->lenght)*2)*sizeof(ElemType));
	if (p == NULL) {//扩容失败
		return false;
	}
	parr->arr = p;
	parr->lenght *= 2;
	return true;
}

插入操作

这里的头插和按位置插入需要挪动数据

尾插根据length直接找到尾部进行插入

//插入操作
void addhead(PArr parr, ElemType value) {//头插
	if (parr == NULL) {
		return;
	}
	if (isfull(parr)) {
		grow_capacity(parr);
	}
	for (int i = parr->size - 1; i >= 0; i--) {
		parr->arr[i + 1] = parr->arr[i];
	}
	parr->arr[0] = value;
	parr->size = parr->size + 1;
}
void addtail(PArr parr, int value) {//尾插
	if (parr == NULL) {
		return;
	}
	if (isfull(parr)) {
		grow_capacity(parr);
	}
	parr->arr[parr->size] = value;
	parr->size++;
}
void add_indexvalue(PArr parr, int index, int value) {//定向插入
	if (parr == NULL) {
		return;
	}
	if (isfull(parr)) {
		grow_capacity(parr);
	}
	for (int i = parr->size - 1; i >= index; i--) {
		parr->arr[i + 1] = parr->arr[i];
	}
	parr->arr[index] = value;
	parr->size++;
}

删除：

与插入相同  头删和按位置删除需要挪动数据（区间删除是需要删除区间的头和尾，定值删除是由查找函数返回该值对应的下标，相当于按位置删除）

尾删也是根据length来找到对应的尾部

//删除操作
void removehead(PArr parr) {//头删
	assert(parr != NULL);//removeindex(parr,0);
	if (isempty(parr)) return;
	for (int i = 0; i < parr->size; i++) {
		parr->arr[i - 1] = parr->arr[i];
	}
	parr->size--;
}
void removetail(PArr parr) {//尾删
	assert(parr != NULL);//removeindex(parr,parr->size-1);
	if (isempty(parr)) return;
	parr->size--;
}
void removeindex(PArr parr, int index) {//定向删除
	if (parr == NULL || index >= parr->size || index < 0) return;
	if (isempty(parr)) return;
	for (int i = index + 1; i < parr ->size;i++) {
		parr->arr[i - 1] = parr->arr[i];
	}
	parr->size--;
}
void removerange(PArr parr, int from_index, int end_index) {//区间删除
	if (parr == NULL || end_index >= parr->size || from_index< 0) return;
	if (isempty(parr)) return;
	int num= end_index -from_index + 1;
	for (int i = 0; i < parr->size-end_index-1; i++) {
		parr->arr[from_index+i] = parr->arr[end_index+i+1];
	}
	parr->size = parr->size -num;
}
void removevalue(PArr parr, int value) {//定值删除
	assert(parr != NULL);
	for (int i = 0; i < parr->size;) {
		if (parr->arr[i] == value) {
			for (int j = i+1; j < parr->size;j++) {
				parr->arr[j - 1] = parr->arr[j];
			}
			parr->size--;
		}
		else {
			i++;
		}
	}
}

查找，修改，清空，销毁，打印

//修改操作
void change(PArr parr, int oldvalue, int newvalue) {//将原有的旧值改为新值
	assert(parr != NULL);
	for (int i = 0; i < parr->size - 1;i++) {
		if (parr->arr[i] == oldvalue) {
			parr->arr[i] = newvalue;
		}
	}
}
//查找操作
bool contains(PArr parr, int value) {//全范围查找
	return containsrange(parr,0,parr->size,value);
	
}
bool containsrange(PArr parr, int begin, int end, int value) {//区间查找
	assert(parr != NULL);
	assert(begin > 0||end<=parr->size);
	for (int i = begin; i <=end;i++) {
		if (parr->arr[i] == value) {
			return true;
		}
	}
	return false;
}
//销毁函数
void destory(PArr parr) {
	free(parr->arr);
	parr->arr = NULL;
}
void show(PArr parr) {
	for (int i = 0; i < parr->size; i++) {
		printf("%5d", parr->arr[i]);
	}
	printf("n");
}

测试文件：

#include
#include"array_op.h"
int main(){//测试代码
	Array array;//声明结构体变量，封装数组有效数据个数 size
	init(&array,5);//初始化函数
	for (int i = 1; i <= 10; i++) {
		addtail(&array,i);//1 2 3 4 5 6 7 8 9 10
	}
	addtail(&array,11);//1 2 3 4 5 6 7 8 9 10 11
	add_indexvalue(&array,1,8);//1 8 2 3 4 5 6 7 8 9 10 11
	removehead(&array);//8 2 3 4 5 6 7 8 9 10 11
	removetail(&array);//8 2 3 4 5 6 7 8 9 10
	removeindex(&array, 2);//8 2 4 5 6 7 8 9 10
	removerange(&array,1,3);//8 6 7 8 9 10
	removevalue(&array,8);//6 7 9 10
	change(&array,7,8);//6 8 9 10
	show(&array);
	printf("%5dn", contains(&array, 9));//存在9
	printf("%5dn", containsrange(&array,0,2,9));//存在9
	return 0;
}