【数据结构】顺序表

时间：2024-03-16 13:32:30

????博客主页：小王又困了

????系列专栏：数据结构

????人之为学，不日近则日退

❤️感谢大家点赞????收藏⭐评论✍️

????️前言

在我们很多时候都要对数据进行增删查改等操作，而这些操作又依赖于线性表。今天就让我们学习顺序表和链表是怎么对数据进行增删查改。

一、线性表

什么是线性表？

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

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

二、顺序表 

 2.1顺序表的概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

注意：顺序表在数据结构中要求数据必须时连续存储的。

顺序表一般分为：

1. 静态顺序表：使用定长数组存储元素。

2. 动态顺序表：使用动态开辟的数组存储。

2.2静态顺序表

静态顺序表的定义：


struct SeqList
{
	int arr[100];
	int size;
};

size：用来记录当前存储信息的个数。

 2.3动态顺序表

动态顺序表的定义：

#define N 100

typedef int SLDateType;

typedef struct SeqList
{
	SLDateType* arr;
	int size;			//存储有效数据的个数
	int capacity;		//空间的大小
}SeqList;

 size：用来记录当前存储信息的个数。

capacoity：空间的大小

2.4顺序表管理数据 

 数据结构就是管理数据，对数据增删查改，所以下面我们就用顺序标来实现这些功能。那我们该使用那种顺序标呢？

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

????2.4.1初始化

在实现这些功能之前，我们先要对数据进行初始化

void IninSeqList(SeqList* s)
{
	s->arr = NULL;
	s->size = 0;
	s->capacity = 0;
}

void test()
{
	SeqList s;
	IninSeqList(&s);
}

  

注意：我们要将结构体的地址传过去,这样我们改变的是指针指向的对象，就是实参。

 这种初始化比不是很好，我们最好在初始化时就先开辟一点空间，可以存放数据。

void IninSeqList(SeqList* s)
{
    assert(s)；
	s->arr = (SLDateType*)malloc(capacity*sizeof(SLDateType));
    if(s->arr==NULL)
    {
        perror("malloc");
        exit(-1);
    }
	s->size = 0;
	s->capacity = 5;
}

exit(-1)是让程序以异常方式退出整个程序。

return是返回函数，如果后面有程序还会继续执行。

????2.4.2销毁

我们使用动态开辟内存，要及时释放空间并置为空指针，不然会造成数据泄露。

void DestroySeqList(SeqList* s)
{
    assert(s)；
	free(s->arr);
	s->arr = NULL;
	s->size = 0;
	s->capacity = 0;
}

????2.4.3尾插

注意：size是数据个数，前面的数据个数都是后一个数据的下标。 

//判断是否增容
void CheckCapacity(SeqList* s)
{
	assert(s);
	if (s->capacity == s->size)
	{
		SLDateType* ptr = (SLDateType*)realloc(s->arr, 2 * s->capacity * sizeof(SLDateType));
		if (ptr == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		s->arr = ptr;
		s->capacity *= 2;
	}
}


//尾插
void PushBackSeqList(SeqList* s, SLDateType x)
{
	assert(s);
	CheckCapacity(s);
	s->arr[s->size] = x;
	s->size++;
}

 ????2.4.4尾删

 删除时只需要让size--就行。

//尾删
void PopBackSeqList(SeqList* s)
{
	//检查
	//if (s->size == 0)
	//{
	//	return;
	//}

	//检查
	assert(s->size > 0);
	s->size--;
}

????2.4.5头插

在插入前，我们要先把数据向后挪，再将数据插入表中。在挪动过程中我们要注意增容问题，空间不足时，要及时增容。

//头插
void PushFrontSeqList(SeqList* s, SLDateType x)
{
	assert(s);
	CheckCapacity(s);

	int i = 0;
	for (i = s->size - 1; i >= 0; i--)
	{
		s->arr[i+1] = s->arr[i];
	}
	s->arr[0] = x;
	s->size++;
}

????2.4.6头删

头删时数据要从前向后挪动。

//头删
void PopFrontSeqList(SeqList* s)
{
	assert(s);
    assert(s->size > 0);
	int i = 0;
	for (i = 0; i <s->size - 1; i++)
	{
		s->arr[i] = s->arr[i + 1];
	}

	s->size--;
}

???? 2.4.7在pos位置插入

在插入前，我们要先判断pos位置是否有效。

//在pos位置插入
void InsertSeqList(SeqList* s, int pos, SLDateType x)
{
	assert(s);
	assert(pos >= 0 && pos <= s->size);
	CheckCapacity(s);
	int i = 0;
	for (i = s->size - 1; i >= pos; i--)
	{
		s->arr[i + 1] = s->arr[i];
	}
	s->arr[pos] = x;
	s->size++;
}

???? 2.4.8在pos位置删除

void EraseSeqList(SeqList* s, int pos)
{
	assert(s);
	assert(pos >= 0 && pos < s->size);
	int i = 0;
	for (i = pos; i < s->size - 1; i++)
	{
		s->arr[i] = s->arr[i + 1];
	}
	s->size--;
}

 2.5顺序表问题

????️问题：

1.我们在从开头或中间插入数据时，要先挪动数据才能插入，这样会有时间上的浪费。

2.增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗。

3.增容一般是呈2倍的增长，势必会有一定的空间浪费。当我们增容100个空间，而只需要插入5个数据，这就会浪费95个空间。

 那如何解决以上问题呢？下一期我们将会介绍链表。

本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位读者三连支持。文章有问题可以在评论区留言，博主一定认真认真修改，以后写出更好的文章。你们的支持就是博主最大的动力。

相关文章