【数据结构】——线性表（顺序表）——内有代码详解

目录

 一、引言

二、线性表

2.1 定义

2.2 特点 

三、顺序表

3.1 顺序表的概念

3.2 顺序表的特点 

 3.3 顺序表的定义

3.3.1 静态定义

3.3.2 动态定义

3.4 顺序表的初始化

 3.4.1 静态初始化

3.4.2 动态初始化 

 

3.5 顺序表的销毁

3.6 顺序表元素的打印

3.7 顺序表的插入

3.7.1 检查空间，如果满了，进行增容

3.7.2 尾插

3.7.3 头插

3.7.4 中间插入

3.8 顺序表的删除

3.8.1 尾删

检查

1 温柔判断

2 暴力判断 

 代码：

3.8.2 头删

3.8.3 中间删除

3.9 顺序表的查询

四、总结

---

 一、引言

我们学完了算法和算法效率的度量，接下来我们将进入线性表的学习了，也是数据结构较为重要的一部分，

---

二、线性表

2.1 定义

线性表（linear list）：是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结 构，常见的线性表：顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物 理上存储时，通常以数组和链式结构的形式存储。

2.2 特点 

• 表中元素的个数有限。
• 表中元素具有逻辑上的顺序性，表中元素有其先后次序。
• 表中元素都是数据元素，每个元素都是单个元素。
• 表中元素的数据类型都相同，这意味着每个元素占有的相同大小的存储空间。
• 表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。

*线性表是一种逻辑结构 ，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层次的概念，因此不可以混淆哦。

---

三、顺序表

下面我们就有进入线性表的顺序表示——顺序表的学习了。

3.1 顺序表的概念

顺序表是一种线性表的存储结构，它通过一组地址连续的存储单元来表示线性表的元素集合。顺序表中的元素按照逻辑顺序依次存放在存储单元中，可以通过元素的下标来访问和操作元素。顺序表可以是静态分配的，也可以是动态分配的。

3.2 顺序表的特点 

顺序表的优点是元素的访问速度快，可以随机访问任意位置的元素；缺点是插入和删除操作需要移动大量的元素，时间复杂度为O(n)。因此，适合于元素的频繁访问和较少的插入删除操作的场景。

 3.3 顺序表的定义

3.3.1 静态定义

假设现线性表的元素类型为SLDataType，数组最大长度为N

顺序表的静态定义：

typedef int SLDataType;//元素数据类型
#define N 100    //顺序表的最大长度
 
//静态顺序表
struct SeqList
{
	SLDataType a[N];//顺序表的元素
	int size;//表中数据长度
};

静态顺序表因为数组的大小和空间以及固定，一定长度定义太小就会导致数据溢出程序崩溃。

3.3.2 动态定义

但是动态顺序表就能解决，它在执行中一旦发现空间占满可以通过语句进行扩充空间大小或者开辟一段更大的空间用来存储。所以我们一般用动态定义。

顺序表的动态定义：

typedef int SLDataType;//元素类型
#define INIT_CAPACITY 4//表长的初始定义
 
//动态顺序表
typedef struct SeqList
{
	SLDataType* a;//动态分配数组的指针
	int size;     //表的长度
	int capacity; //表的空间容量
}SL;              //类型定义

 

3.4 顺序表的初始化

 3.4.1 静态初始化

因为静态定义时已经定义了数组的长度，因此只需要将顺序表长度设为0就行了

//静态初始化
SL s;           //声明一个顺序表
void SLInit(SL s)
{
	s.size = 0;
}

3.4.2 动态初始化 

动态分配的初始化为顺序表分配一个预定义的数组空间，并将顺序表的当前长度设为0

//动态初始化
void SLInit(SL* ps)
{
    assert(ps);//检验ps
	ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);//分配存储空间
	if (ps->a == NULL)//检验是否分配成功
	{
		perror("malloc fail");
		return;
	}
	ps->capacity = INIT_CAPACITY;//初始存储容量
	ps->size = 0;//表长初始为0
}

 

3.5 顺序表的销毁

void SLDestroy(SL* ps)
{
	free(ps->a);    //释放顺序表空间
	ps->a = NULL;    //防止野指针
	ps->capacity = ps->size = 0;//归0
}

3.6 顺序表元素的打印

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

 

3.7 顺序表的插入

3.7.1 检查空间，如果满了，进行增容

插入时，要保证内存足够用不能存在溢出，而我们在初始化时运用了malloc分配内存空间，当内存不够用时就可以用realloc进行扩容。

void CheckCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)//检查空间是否够用
	{
		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity * 2);
		//扩大内存空间
		if (tmp == NULL)//检验扩容是否成功
		{
			perror("realloc fail");
			return;
		}
		ps->a = tmp;//将顺序表指向扩容的空间
		ps->capacity *= 2;//空间容量随之扩大
	}
 
}

3.7.2 尾插

顾名思义就是从顺序表的最后插入数据：

void SLPushBack(SL* ps, SLDataType x)
{
    assert(ps);//检查指针
    CheckCapacity(ps)；//扩容
 
 
	//ps->a[ps->size] = x;
	//ps->size++;
 
	ps->a[ps->size++] = x;//尾部插入数据
}

3.7.3 头插

顾名思义就是从顺序表的前面插入数据：

void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);//检查指针
    CheckCapacity(ps)；//扩容
 
	int end = ps->size-1;//设置最后的数据位置
	while (end + 1)//数据整体后移
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;//头插
	ps->size++;//增加数据长度
}

3.7.4 中间插入

void SeqListInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);//检查pos范围
    CheckCapacity(ps);//扩容
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
 
}

3.8 顺序表的删除

3.8.1 尾删

检查

尾删顺序表时可能会删除过头，所以我们要进行判断：

1 温柔判断

顾名思义如果删除过头了则安安静静的不执行本次删除：

	//温柔检查
	if (ps->size < 0)
		return;

2 暴力判断 

如果删除过头则会弹出弹窗提醒你：

	//暴力检查
	assert(ps->size > 0);

如同还会告诉你错误行： 

 代码：

void SLPopBack(SL* ps)
{
	//暴力检查
	assert(ps->size > 0);
 
	//温柔检查
	//if (ps->size < 0)
	//	return;
 
	ps->size--;//减少数组个数
}

 

3.8.2 头删

void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);//防止删减过头
	int begin = 0;
	while (begin < ps->size)
	{
		ps->a[begin] = ps->a[begin + 1];
		begin++;
	}
	ps->size--;
}

 

3.8.3 中间删除

void SeqListErase(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);//判断pos范围
	int begin = pos;
	while (begin < ps->size-1)
	{
		ps->a[begin] = ps->a[begin + 1];
		begin++;
	}
	ps->size--;
 
}

3.9 顺序表的查询

 
int SLFind(SL* ps, SLDataType x)
{
    assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;//找到就返回
		}
	}
	return -1;//没找到返回-1
}

---

四、总结

       经过观察我们也发现头插和尾插可以用中间插入表示；头删和尾删也可以用中间删除表示。而头插和头删的时间复杂度是O(N^2),刚好是插入和删除的最坏情况；尾插和尾删的时间复杂度为O(N)，刚好是它们的最好情况所以改选什么知道了吗。

        顺序表仅仅是线性表的一种，而线性表也仅仅是数据结构的一种，接下来姜糖还会给大家带去更好的作品，大家记得一键三连呀，谢谢大家支持。