【数据结构从菜鸟到大牛】 顺序表的实现_顺序表采用数组存储有什么特别要求

目录

1.顺序表的概念以及结构

1.1静态顺序表：​

1.2动态顺序表

 2.接口实现

2.1初始化顺序表

2.2打印顺序表

2.3尾插

2.3.1检查扩容

2.4尾删

2.5 头插

2.6头删

 2.7查找

2.8指定位置插入数据

2.9指定位置删除 

 2.10修改

2.11销毁

源码

SeqList.h

SeqList.c

---

1.顺序表的概念以及结构

        顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构

        一般情况下采用数组存储。在数组上完成数据的增删查改

顺序表要求 数据必须从第一个位置开始连续存储的-（这里和数组是不同的） 

顺序表可以分为静态顺序表和动态顺序表

1.1静态顺序表：

这种静态顺序表的大小是写死的，存在很明显的缺陷：

        N不知道要定义多大，多了就会浪费，少了就不够

所以一般采用动态的顺序表

1.2动态顺序表

但是还存在一个问题，如果存满了怎么办？（即size==capacity)

那么这时候就需要考虑扩容

而扩容是存在系统资源消耗的，如果一次只扩一个空间，那么需要频繁的向操作系统发送扩容请求，而多扩一些可能又会用不完而导致浪费，所以综合解决方案就是一次扩容两倍

这里扩容要用到realloc，顺便复习一下：

       1. 如果在所扩容的空间后面找到足够的空间，那么就原地扩容

        2.如果在所扩容的空间后面找不到足够的空间，那么他就在内存中另找一块足够大的空间进行扩容，然后把新的地址传给原来的空间，

 2.接口实现

接口以动态顺序表为例

首先我们要有的接口为        

1.初始化顺序表

2.尾插，尾删

3.头插，头删

4.查找，修改，删除

5.销毁，打印

2.1初始化顺序表

由于 顺序表实际上就是数组，初始化我们只需要把顺序表的最大容量capacity设置为0，

当前存放元素个数size 设置为0，然后把a指针置为空（目前还没malloc空间）

//初始化
void SeqListInit(SeqList* ps)
{
	assert(ps);
	ps->size = ps->capacity = 0;
	ps->a = NULL;
}

2.2打印顺序表

打印顺序表思路十分明确，只需要利用变量i 遍历整个顺序表，printf每一个位置的数据就可以了

//打印
void SeqListPrint(SeqList* ps)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

2.3尾插

尾插我们首先要检查一下是否需要扩容，如果不需要扩容，那么直接把要插入的数据放到size处

（因为数组下标从0开始 所以size处就是目前需要放入的位置）然后size++就可以了

那么怎么检查是否需要扩容呢？

这里可以想一下，只要 是插入数据是不是都需要用到扩容

所以我们干脆直接把检查扩容这一功能封装成一个函数

2.3.1检查扩容

这里还会有一个问题，我们想一次扩容两倍，但是如果这是第一次怎么办？

第一次的容量capacit为0 二倍仍然是0

所以我们利用一个三目运算符，如果capacity为0 就扩容4个位置，否则扩容两倍

具体的看下面代码

//检查扩容
void CheckCapacity(SeqList* ps)
{
	assert(ps);
	int newcapacity = 0;
	if (ps->size == ps->capacity)
	{
        /*三目运算符*/
		newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcapacity);
		//如果开辟不成功
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);//扩容不成功直接退出
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	
	
}

接下来尾插就很简单了

//尾插
void SeqListPushBack(SeqList* ps, SLDataType x)
{
	assert(ps);
	//检查是否需要扩容
	CheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}

2.4尾删

 尾删，注意我们其实并不是真正意义上的删除，利用数组知识就可以知道，我们只需要让他访问不到最后一个元素不就相当于删除了吗？ 所以我们只需要让size--，不就相当于把最后一个元素删除了嘛？

但是 注意！如果你顺序表已经为空了，就不能再删除了，所以需要先检查一个 是不是顺序表已经为空了

void SeqListPopBack(SeqList* ps)
{
	assert(ps);
	//判断是不是空
	assert(ps->size > 0);
	//如果不是空
	ps->size--;
 
}

这里我使用暴力检查 assert ，断言size大于0

当然也可以使用 if语句 ---
 

void SeqListPopBack(SeqList* ps)
{
	assert(ps);
	//判断是不是空
	if(ps->size==0) 
    {
        printf("顺序表已空，无法删除\n");
        return;
    }
	//如果不是空
	ps->size--;
 
}

2.5 头插

头插需要在顺序表的首元素前面插入一个数据，而顺序表是数组，如果想在顺序表最前面插入数据，必须要做的一件事就是把数组所有的元素整体向后挪动，把前面空出一个位置，把要插入的数据放进去就可以了

显然 头插的时间复杂度为O(N)

下面就是代码：

使用一个end变量标识数组的最后一个元素

因为如果从第一个元素开始向后挪动，一定会把后面的元素给覆盖，出错！

所以从最后一个元素开始向后挪动，当end每次挪动向前走，直到end走到0 也就是第一个元素再结束

//头插
void SeqListPuchFront(SeqList* ps, SLDataType x)
{
	assert(ps);
	CheckCapacity(ps);
	int end = ps->size - 1;
	
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[0] = x;
	ps->size++;
}

2.6头删

 首先，头删就需要检查一下顺序表是不是空

然后头删显然需要把第一个位置的元素删除，仍然需要挪动数据，把后面的元素依次向前挪动，只要把第一个位置的元素覆盖，就相当于删除了

注意：头删需要从前面开始向后走 来挪动数据，否则也会导致原来的数据被覆盖

//头删
void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	assert(ps->size > 0);
	//从前向后挪动(覆盖)
	int begin = 0;
	while (begin < ps->size-1)
	{
		ps->a[begin] = ps->a[begin + 1];
		++begin;
	}
	ps->size--;
}

 2.7查找

查找十分简单，只需要利用一个变量遍历顺序表，找到目标元素，返回下标，否则返回-1

之所以这样设计，是因为这样方便之后利用返回值配合修改函数和删除指定位置元素进行操作

（数组下标不会为-1，所以-1就代表了找不到）

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

2.8指定位置插入数据

 既然是指定位置，那么就需要先找到那个数据的位置，这就用到了查找函数（函数复用）

注意，需要对查找函数的返回值进行检查 

注意 这里pos是<=size (因为考虑到如果是尾插）

找到位置之后，需要把从这个位置开始向后到最后的所有元素整体向后挪动一个位置，把指定位置处空出来，然后把数据放入就可以了

所以需要从最后一个位置开始向后挪动（防止覆盖）

最后别忘了size++(毕竟插入了数据）

（其实指定位置插入数据 可以复用到尾插和头插里面，是完全没有问题的）

//指定位置插入数据
void SeqListInsert(SeqList* ps, int pos, SLDataType x)
{
	assert(ps);
	if (pos == -1)
	{
		printf("找不到\n");
		return;
	}
	assert(pos >= 0 && pos <= ps->size);
	//从pos位置向后移动
	int end = ps->size-1;
	while (end>=pos)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[pos] = x;
	ps->size++;
}

2.9指定位置删除 

 首先需要用查找函数找到目标元素的位置（下标）

然后 把该位置之后的数据整体向前挪动一个位置，把指定位置覆盖就可以了

这里利用begin（因为要从前面开始向前挪动）

别忘了对pos检查

//指定位置删除
void SeqListErase(SeqList* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	//往前移动
	int begin = pos;
	while (begin < ps->size-1)
	{
		ps->a[begin] = ps->a[begin + 1];
		++begin;
	}
	ps->size--;
}

 2.10修改

首先用查找函数找到下标，有了下标直接访问数组该位置元素进行修改就可以了

（检查pos的有效性）

//修改
void SeqListModify(SeqList* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	ps->a[pos] = x;
}

2.11销毁

销毁就更简单了：

1.把size和capacity置空

2.把malloc的空间释放

void SeqListDestory(SeqList* ps)
{
	assert(ps);
	ps->size = ps->capacity = 0;
	free(ps->a);
	ps->a = NULL;
}

源码

SeqList.h

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable:6031)
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define SLDataType int
typedef struct SeqList {
	SLDataType* a;//指向动态开辟的数组
	int size;//数据的个数
	int capacity;//容量
 
}SeqList;
 
 
//顺序表初始化
void SeqListInit(SeqList* ps);
//打印
void SeqListPrint(SeqList* ps);
//尾插
void SeqListPushBack(SeqList* ps,SLDataType x);
//尾删
void SeqListPopBack(SeqList* ps);
//头插
void SeqListPuchFront(SeqList* ps, SLDataType x);
//头删
void SeqListPopFront(SeqList* ps);
//查找
int SeqListFind(SeqList* ps, SLDataType x);
//指定位置插入
void SeqListInsert(SeqList* ps, int pos, SLDataType x);
//删除pos位置的元素
void SeqListErase(SeqList* ps, int pos);
//修改
void SeqListModify(SeqList* ps, int pos, SLDataType x);
//销毁
void SeqListDestory(SeqList* ps);

SeqList.c

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable:6031)
#include"SeqList.h"
 
//打印
void SeqListPrint(SeqList* ps)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}
//初始化
void SeqListInit(SeqList* ps)
{
	assert(ps);
	ps->size = ps->capacity = 0;
	ps->a = NULL;
}
 
//检查扩容
void CheckCapacity(SeqList* ps)
{
	assert(ps);
	int newcapacity = 0;
	if (ps->size == ps->capacity)
	{
		newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcapacity);
		//如果开辟不成功
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	
	
}
//尾插
void SeqListPushBack(SeqList* ps, SLDataType x)
{
	assert(ps);
	//检查是否需要扩容
	CheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}
//尾删
void SeqListPopBack(SeqList* ps)
{
	assert(ps);
	//判断是不是空
	assert(ps->size > 0);
	//如果不是空
	ps->size--;
 
}
//头插
void SeqListPuchFront(SeqList* ps, SLDataType x)
{
	assert(ps);
	CheckCapacity(ps);
	int end = ps->size - 1;
	
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[0] = x;
	ps->size++;
}
 
//头删
void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	assert(ps->size > 0);
	//从前向后挪动(覆盖)
	int begin = 0;
	while (begin < ps->size-1)
	{
		ps->a[begin] = ps->a[begin + 1];
		++begin;
	}
	ps->size--;
}
 
//查找
int SeqListFind(SeqList* ps, SLDataType x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
			return i;
	}
	//找不到返回-1
	return -1;
}
//指定位置插入数据
void SeqListInsert(SeqList* ps, int pos, SLDataType x)
{
	assert(ps);
	if (pos == -1)
	{
		printf("找不到\n");
		return;
	}
	assert(pos >= 0 && pos <= ps->size);
	//从pos位置向后移动
	int end = ps->size-1;
	while (end>=pos)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[pos] = x;
	ps->size++;
}
 
//指定位置删除
void SeqListErase(SeqList* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	//往前移动
	int begin = pos;
	while (begin < ps->size-1)
	{
		ps->a[begin] = ps->a[begin + 1];
		++begin;
	}
	ps->size--;
}
 
//修改
void SeqListModify(SeqList* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	ps->a[pos] = x;
}
 
//销毁
void SeqListDestory(SeqList* ps)
{
	assert(ps);
	ps->size = ps->capacity = 0;
	free(ps->a);
	ps->a = NULL;
}