数据结构——顺序表详解

目录

前言

一.线性表

1.概念

二.顺序表

1.概念

2.分类

2.1静态顺序表

2.2动态顺序表

前言

数据结构是计算机存储、组织数据的方式.

一.线性表

1.概念

线性表（linear list）是n个具有相同特性的数据元素的有限序列.线性表是一种在实际中广泛使用的数据结构

2.分类

顺序表、链表、栈、队列、字符串.....

3.性质

在逻辑上是线性结构,也就是说是连续的一条直线

在物理结构上并不一定连续,在物理上存储时，通常以数组和链式结构的形式存储

二.顺序表

1.概念

逻辑结构是线性的，物理结构是连续的

2.分类

2.1静态顺序表

2.1.1概念

使用定长数组存储元素

2.1.2弊端

给定的数组长度，若不够会导致后续的数据保存失败；若多了会导致空间的大量浪费

严重的会导致重大的技术事故

2.1.3实现

静态顺序表
#define N 100
struct SeqList
{
	SLDataType a[N];//定长数组
	int size;//有效数据个数
};

2.2动态顺序表

2.2.1概念

使用动态开辟的数组存储

 三.接口实现

通过顺序表，我们可以实现创建、初始化、扩容、尾插、头插、尾删、头删、指定位置删除、指定位置添加、查找、打印、销毁

为了有一个好习惯以及将来处理多的代码，我们进行分装处理

将函数的声明、类型的声明放在头文件(.h)中,函数的实现放在源文件(.c)中

typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* arr;//存储数据的底层结构
	int capacity;//记录顺序表的空间大小
	int size;//记录顺序表当前有效的数据个数
}SL;
typedef struct SeqList SL;
//初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(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);

1.创建及初始化

在这里我们使用typedef定义一个新的数据类型，方便我们进行后续的修改（如将int->char）

typedef int SLDataType;
typedef struct SeqList SL;

typedef struct SeqList
{
	SLDataType* arr;//存储数据的底层结构
	int capacity;//记录顺序表的空间大小
	int size;//记录顺序表当前有效的数据个数
}SL;

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

 2.扩容

针对后续的添，我们需要判断空间是否足够，若不够我们就需要进行动态内存开辟(realloc函数)

我们创建一个临时变量去接收新开辟的空间，然后在安全的情况下再给原变量

void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* temp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (temp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		//扩容成功
		ps->arr = temp;
		ps->capacity = newCapacity;
	}
}

3.尾插头插与尾删头删

3.1尾插头插

对于尾插，先判断空间是否足够，之后直接插入即可

对于头插，我们也是需要先判断空间，之后将下标前一位的值赋给后一位

void SLPushBack(SL* ps, SLDataType x)
{
	//断言--粗暴的解决方式
	//assert(ps != NULL);
	assert(ps);
	//if判断--温柔的方式
	/*if (ps == NULL)
	{
		return;
	}*/
	//空间不够，扩容
	SLCheckCapacity(ps);
	//空间足够,直接插入
	ps->arr[ps->size++] = x;
	//ps->size++;
}
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	
	//判断是否扩容
	SLCheckCapacity(ps);
	//旧数据往后挪动一位
	for (int i=ps->size;i>0;i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}

3.2尾删头删

对于尾删，我们可以直接删除size即可

对于头删，我们将后一位赋给前一位

void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);
	//顺序表不为空
	//ps->arr[ps->size - 1] = -1;
	ps->size--;
}
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps ->size);
	//不为空执行挪移操作
	for (int i=0;isize-1;i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

4.指定位置删除添加

添加

void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos size);
	{
		SLCheckCapacity(ps);
		//pos及以后的数据往后挪动一位，pos空出来
		for (int i=ps->size;i>pos;i--)
		{
			ps->arr[i] = ps->arr[i - 1];
		}
		ps->arr[pos] = x;
		ps->size++;
	}
}

删除 

void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos size);
	//pos以后的数据往前挪动一位
	for (int i=pos;isize-1;i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

5.查找打印销毁

查找

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

打印 

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

销毁

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

如果上述内容对您有帮助，希望给个三连谢谢