数据结构——顺序表

顺序表的定义

线性表（linearlist）是n个具有相同特性的数据元素的有限序列。

线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。

•  顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。

顺序表还会封装对数据元素增删查改的接口 。

用一个结构体设计顺序表

//重定义类型，便于修改（int可修改为其他类型）
typedef int SLDataType;
 
typedef struct SeqList
{
	SLDataType* arr;
	int size;//有效数据元素个数
	int capacity;//空间大小
}SL;定义的同时重命名顺序表

---

顺序表的各种接口

​
 
//顺序表初始化
void SLInit(SL* ps);
//顺序表销毁
void SLDestroy(SL* ps);
//顺序表打印
void SLPrint(SL* ps);
 
//增 删 查 改操作
//检查空间是否足够
void CheckCapacity(SL* ps);
//尾插
void SLPushBack(SL* ps, SLDataType x);
//头插
void SLPushFront(SL* ps, SLDataType x);
//尾删
void SLPopBack(SL* ps);
//头删
void SLPopFront(SL* ps);
 
//指定位置插⼊数据
void SLInsert(SL * ps, int pos, SLDataType x);
//指定位置删除数据
void SLErase(SL* ps, int pos);
//找指定的数据
int SLFind(SL* ps, SLDataType x);
 
​
 
​

---

void SLInit(SL* ps) 顺序表初始化

将顺序表里的arr、size、capacity初始化

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

---

void SLDestroy(SL* ps) 顺序表销毁

void SLDestroy(SL* ps)
{
	if (ps->arr)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

---

void SLPrint(SL* ps) 顺序表打印

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

---

void CheckCapacity(SL* ps) 检查空间是否足够

void CheckCapacity(SL* ps)
{
	//当有效数据个数size 与 有效空间大小capacity 相等时，说明空间不够了，要增容
	
	if (ps->capacity == ps->size)
	{
	    //增容，一般成倍增加，2~3倍较为合理
	    //用realloc函数，当ptr为空指针时，将分配一块新空间（调用realloc一样）
	    //此时又有一种特殊情况，一开始capacity为0时，怎样处理？
	    //三目操作符，为0时，将其赋值为4，不为0时，capacity*2
		int NewCapacity = (ps->capacity == 0 ? 4 : 2 * ps->capacity);
		SLDataType* tep = (SLDataType*)realloc(ps->arr, NewCapacity * sizeof(SLDataType));
		//判断增容成不成功
		if (tep == NULL)
		{
			perror("realloc");
			exit(1);
		}
		ps->arr = tep;
		//及时更新空间大小
		ps->capacity = NewCapacity;
	}
}

---

void SLPushBack(SL* ps, SLDataType x) 尾插

void SLPushBack(SL* ps, SLDataType x)
{
	//ps不能为空指针
	assert(ps);
	//空间是否足够
	CheckCapacity(ps);
 
	//尾插
	//ps->arr[ps->size] = x;
	//ps->size++;
	ps->arr[ps->size++] = x;
}

---

void SLPushFront(SL* ps, SLDataType x) 头插

void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	CheckCapacity(ps);
 
	//把全部数据整体往后移动一位，把第一位置空出来，再插入数据
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];//循环的最后情况：ps->arr[1] = ps->arr[0]
	}
 
	//头插
	ps->arr[0] = x;
	ps->size++;
}

---

void SLPopBack(SL* ps) 尾删

void SLPopBack(SL* ps)
{
	assert(ps);
	//删除的前提是有数据，得判断有效数据个数size是否为0
	assert(ps->size);
 
	//尾删   
	//一种方法：ps->arr[--ps->size] = -1;
	//或者直接让size-1
	--ps->size;
}

---

void SLPopFront(SL* ps) 头删

void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);
 
	//头删 把除第一位的数据整体往前移动一位，覆盖掉第一位的数据即可
	for (int i = 1; i < ps->size; i++)
	{
		ps->arr[i - 1] = ps->arr[i];//循环的最后情况：ps->arr[ps->size - 2] = ps->arr[ps->size - 1]
	}
	//及时更新size
	ps->size--;
}

---

void SLInsert(SL* ps, int pos, SLDataType x) 指定位置插入数据

不是覆盖原先数据，插入数据的结果造成部分数据后移

void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	//检查pos的有效性，pos是下标，不能为负的，pos最大只能为size
	assert(pos >= 0 && pos <= ps->size);
	CheckCapacity(ps);
 
	//指定位置插入， 先把pos位置的数据整体 往后 移一位（arr[pos] 至 arr[size - 1]），再插入
	for (int i = ps->size - 1; i >= pos; i--)
	{
		ps->arr[i + 1] = ps->arr[i];//循环的最后情况：ps->arr[pos + 1] = ps->arr[pos]
	}
	ps->arr[pos] = x;
	ps->size++;
}

---

void SLErase(SL* ps, int pos) 指定位置删除数据

void SLErase(SL* ps, int pos)
{
	assert(ps);
	//检查pos的有效性，pos是下标，不能为负的，pos最大只能为size - 1，为size就会越界
	assert(pos >= 0 && pos < ps->size);
	CheckCapacity(ps);
 
	//指定位置删除数据，让pos后面的数据往前移动（arr[pos+1] 至 arr[size -1]）,覆盖要删除的数据
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];//循环的最后情况：ps->arr[size - 2] = ps->arr[size - 1]
	}
	ps->size--;
}

---

int SLFind(SL* ps, SLDataType x) 查找整型指定数据

返回下标

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

---

完整代码

SeqList.h

#include
#include
#include
#include
#include"Contact.h"
 
//定义顺序表的结构
 
//动态顺序表
//重定义类型，便于修改（int可修改为其他类型）
typedef int SLDataType;
 
typedef struct SeqList
{
	SLDataType* arr;
	int size;//有效数据元素个数
	int capacity;//空间大小
}SL;
 
//顺序表初始化
void SLInit(SL* ps);
//顺序表销毁
void SLDestroy(SL* ps);
//顺序表打印
void SLPrint(SL* ps);
 
//检查空间是否足够
void CheckCapacity(SL* ps);
 
//增 删 查 改操作
//尾部插入
void SLPushBack(SL* ps, SLDataType x);
//头部插入
void SLPushFront(SL* ps, SLDataType x);
//尾部删除
void SLPopBack(SL* ps);
//头部删除
void SLPopFront(SL* ps);
 
//指定位置插⼊数据
void SLInsert(SL * ps, int pos, SLDataType x);
//指定位置删除数据
void SLErase(SL* ps, int pos);
//找指定的数据
int SLFind(SL* ps, SLDataType x);

SeqList.c

#include "SeqList.h"
 
//顺序表初始化
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}
 
//顺序表销毁
void SLDestroy(SL* ps)
{
	if (ps->arr)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}
 
void SLPrint(SL* ps)
{
	assert(ps);
 
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}
 
//“增”的操作检查空间是否足够，不够就向内存申请空间
void CheckCapacity(SL* ps)
{
	//当有效数据个数size 与 有效空间大小capacity 相等时，说明空间不够了，要增容
	
	if (ps->capacity == ps->size)
	{
	    //增容，一般成倍增加，2~3倍较为合理
	    //用realloc函数，当ptr为空指针时，将分配一块新空间（调用realloc一样）
	    //此时又有一种特殊情况，一开始capacity为0时，怎样处理？
	    //三目操作符，为0时，将其赋值为4，不为0时，capacity*2
		int NewCapacity = (ps->capacity == 0 ? 4 : 2 * ps->capacity);
		SLDataType* tep = (SLDataType*)realloc(ps->arr, NewCapacity * sizeof(SLDataType));
		//判断增容成不成功
		if (tep == NULL)
		{
			perror("realloc");
			exit(1);
		}
		ps->arr = tep;
		//及时更新空间大小
		ps->capacity = NewCapacity;
	}
}
 
//尾部插入
void SLPushBack(SL* ps, SLDataType x)
{
	//ps不能为空指针
	assert(ps);
	//空间是否足够
	CheckCapacity(ps);
 
	//尾插
	//ps->arr[ps->size] = x;
	//ps->size++;
	ps->arr[ps->size++] = x;
}
 
//头部插入
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	CheckCapacity(ps);
 
	//把全部数据整体往后移动一位，把第一位置空出来，再插入数据
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];//循环的最后情况：ps->arr[1] = ps->arr[0]
	}
 
	//头插
	ps->arr[0] = x;
	ps->size++;
}
 
//尾部删除
void SLPopBack(SL* ps)
{
	assert(ps);
	//删除的前提是有数据，得判断有效数据个数size是否为0
	assert(ps->size);
 
	//尾删   
	//一种方法：ps->arr[--ps->size] = -1;
	//或者直接让size-1
	--ps->size;
}
 
//头部删除
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);
 
	//头删 把除第一位的数据整体往前移动一位，覆盖掉第一位的数据即可
	for (int i = 1; i < ps->size; i++)
	{
		ps->arr[i - 1] = ps->arr[i];//循环的最后情况：ps->arr[ps->size - 2] = ps->arr[ps->size - 1]
	}
	//及时更新size
	ps->size--;
}
 
//指定位置插⼊数据(不是覆盖原先数据，插入数据的结果造成部分数据后移) pos是下标
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	//检查pos的有效性，pos是下标，不能为负的，pos最大只能为size
	assert(pos >= 0 && pos <= ps->size);
	CheckCapacity(ps);
 
	//指定位置插入， 先把pos位置的数据整体 往后 移一位（arr[pos] 至 arr[size - 1]），再插入
	for (int i = ps->size - 1; i >= pos; i--)
	{
		ps->arr[i + 1] = ps->arr[i];//循环的最后情况：ps->arr[pos + 1] = ps->arr[pos]
	}
	ps->arr[pos] = x;
	ps->size++;
}
 
//指定位置删除数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	//检查pos的有效性，pos是下标，不能为负的，pos最大只能为size - 1，为size就会越界
	assert(pos >= 0 && pos < ps->size);
	CheckCapacity(ps);
 
	//指定位置删除数据，让pos后面的数据往前移动（arr[pos+1] 至 arr[size -1]）,覆盖要删除的数据
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];//循环的最后情况：ps->arr[size - 2] = ps->arr[size - 1]
	}
	ps->size--;
}
 
//查找整型指定数据
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	assert(ps->size);
 
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
}

---

拜拜，下期再见😏

摸鱼ing😴✨🎞