- 微信
- 微博
  
  分享文章到微博
- 复制链接
  
  复制链接到剪贴板

【数据结构】顺序表

春人. 发表于 2023/11/28 00:49:21 2023/11/28

【摘要】 📖线性表在了解线性表之前先让我们来了解一下什么是线性表。线性表(linear list)是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表有：顺序表、链表i、栈、队列、字符串等。之所以叫线性表是因为其在逻辑结构上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。📖顺序表...

📖线性表

在了解线性表之前先让我们来了解一下什么是线性表。线性表(linear list)是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表有：顺序表、链表i、栈、队列、字符串等。
之所以叫线性表是因为其在逻辑结构上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

📖顺序表

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

顺序表一般可分为以下两类：

静态顺序表：使用定长数组存储元素（缺陷：开少了不够用、开多了浪费）
动态顺序表：使用动态开辟的数组存储（按需申请）

📖动态顺序表

上面说动态顺序表就是动态开辟数组来存储嘛，那这里我们为什么不直接去开辟数组，而是要先定义一个结构体呢？因为一个顺序表它不只是简单的去动态申请一块空间就结束了，我们还需要在这个顺序表上执行一系列操作，比如说插入数据、删除数据、修改数据、查找数据等等。插入数据时如果当顺序表满了就不能再插了，因此我们需要知道顺序表中有效元素的个数以及顺序表的容量，当有效个数等于容量时我们就该对顺序表进行扩容，所以有效元素个数和容量是每一个顺序表都应该具备的属性，还记得我们之前学的嘛？当一个事物具有多个属性的时候，我们就可用结构体将事物的所有属性放在一起。这就是为什么在创建一个顺序表的时候需要先定义一个结构体，这个结构体就是用来表示一个顺序表的，它们的关系如下图所示：

🔖结构

#define INIT_CAPACITY 4

typedef int SLDataType;
//动态顺序表，按需申请
typedef struct SeqList
{
	SLDataType* arr;//使当前的顺序表具有普适性
	int size;     //有效数据个数
	int capacity; //空间容量
}SL;

顺序表只是一种数据存储结构，这就意味任何类型的数据都应该可以按照顺序表的结构进行存储，所以为了使我们的顺序表更加具有普适性，结构体里arr指向的数组类型是我们重定义的SLDataType，这样当我们想创建其它类型的顺序表时只需要对typedef后面的类型进行需改即可；size是用来计数的，统计当前顺序表一共有多少个有效元素；capacity是用来表示当前顺序表的容量，当size==capacity时说明当前顺序表已经“装满了”，需要扩容。

🔖初始化

void SLInit(SL* ps)
{
	assert(ps);
	ps->arr = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);//开一定大小的空间
	if (ps->arr == NULL)
	{
		perror("malloc");
		return;
	}
	ps->size = 0;
	ps->capacity = INIT_CAPACITY;
}

需要注意：形参是结构体类型的指针，千万不能是结构体类型的变量，因为如果只是单纯的进行值传递那么形参的改变不会影响实参，因此这里我们需要传递地址，形参就需要用一个指针来接受。

🔖销毁

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

为什么要销毁？根据上面说的顺序表本质上不就是一个结构体变量嘛，结构体变量和其他基本数据类型一样都是数据类型用来定义变量，我们平时在使用基本数据类型定义的变量时，用完之后也没有专门对其进行销毁，那为什么到了线性表这里就需要专门去销毁呢？不要忘了！！！我们这里是动态顺序表，arr是通过动态申请空间得到的，只要是动态申请的内存在使用结束的时候都需要进行释放，将空间使用权限归还给操作系统，否则就会导致内存泄漏。所以我们需要写一个销毁函数在顺序表使用结束的时候主动将其动态申请的空间释放。在释放前我们可以先对传过来的地址用assert进行断言检查，判断其是否为空，为空就无需进行释放。

🔖尾插

//尾插
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);//进行容量检查
	//ps->a[ps->size] = x;
	//ps->size++;
	ps->arr[ps->size++] = x;
}

尾插时需要先判断顺序表是否满了，满了要先进行扩容才能继续进行扩容。size表示有效元素个数，同时也是顺序表中最后一个元素后一个位置的下标。成功插入后要对有效数据个数size加一。这里因为扩容逻辑不仅在尾插中会用到，在头插和随即插入中也可能用上，因此可以把扩容逻辑单独写成一个函数，这是程序设计的一种思路，可以降低代码的的冗余。扩容函数将在下面展示。

🔖扩容

//检查容量
void SLCheckCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * ps->capacity * 2);//一次扩大二倍比较合适，你也可以按照你的需求进行扩容
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		ps->arr = tmp;
		ps->capacity *= 2;
	}
}

扩容时需要调用realloc函数进行扩容，在使用realloc函数的时候需要注意他的第一个参数指向待扩容的空间，第二个参数是待扩容的大小单位是字节，其次就是扩容的两种形式：原地扩容和异地扩容。关于realloc的具体用法忘了的小伙伴可以去看看我之前分享的一篇文章：【C语言进阶】动态内存管理

🔖尾删

//尾删
void SLPopBack(SL* ps)
{
	//assert(ps->size > 0)//暴力检查
	if (ps->size == 0)//如果size==0说明顺序表已经没有数据了，也就不用再尾删
	{
		return;
	}
	ps->size--;
}

由于顺序表是用连续的物理空间来进行数据存储的，因此尾删数据只需要把有限数据个数减一就行，这样我们就无法访问到原链表中的最后一个数据，进而实现了顺序表的尾删，删掉后，顺序表中剩下的多余空间不能单独释放，在堆上动态申请的一块连续空间只能同时释放。就类似于你参加团购，购买时是一起购买的，退货时也不允许你一个人退货。

🔖头插

//头插
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	//进行容量检查
	SLCheckCapacity(ps);
	//对数据进行挪动
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->arr[end + 1] = ps->arr[end];
		end--;
	}
	ps->arr[0] = x;
	ps->size++;
}

头插需要先进行容量检查，再把原顺序表中的元素全部往后挪动一位，最后再进行插入。

🔖头删

//头删
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);
	//从第二个元素开始把后面的元素全部往前挪动一位
	int str = 1;
	while (str < ps->size)
	{
		ps->arr[str - 1] = ps->arr[str];
		str++;
	}
	ps->size--;
}

头删需要从第二个元素开始把后面的所有元素往前挪动一位。

🔖在pos位置插入

//在pos位置处插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLCheckCapacity(ps);
	//把从pos位置开始的所有数据往后挪动一位
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->arr[end + 1] = ps->arr[end];
		end--;
	}

	ps->arr[pos] = x;
	ps->size++;
}

🔖删除pos位置元素

//删除pos位置元素
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);//size位置不能删，不是顺序表中的有效位置
	//把pos位置后面的所有元素往前挪动一位
	int str = pos + 1;
	while (str < ps->size)
	{
		ps->arr[str - 1] = ps->arr[str];
		str++;
	}
	ps->size--;
}

🔖查找

//查找
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	int str = 0;
	while (str < ps->size)
	{
		if (ps->arr[str] == x)
		{
			return str;
		}
		str++;
	}
	return -1;
}

🔖打印顺序表元素

void SLPrint(SL* ps)
{
	assert(ps);

	int i = 0;
	for (i = 0; i < ps->size; i++)//遍历一遍
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}

🔖时间复杂度分析

尾插和尾删是直接进行的没有涉及到对顺序表的遍历，因此当插入N个数据的时候他俩的时间复杂度都是 $O (N)$ ，而头插和头删都需要遍历顺序表将元素进行挪动，所以当头插或者头删一个数据的时候时间复杂度都是 $O (N)$ ，当插入或者删除N个数据的时候时间复杂度就是 $O (N^{2})$ 。同理，在pos位置进行插入和删除以及查找的时间复杂度也是 $O (N^{2})$ 。

操作	时间复杂度
尾插、尾删	$O (N)$
头插、头删	$O (N^{2})$
pos位置插入、删除	$O (N^{2})$
查找	$O (N^{2})$

📖动态顺序表完整版源码

SeqList.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define N 10
#define INIT_CAPACITY 4

typedef int SLDataType;

//动态顺序表，按需申请
typedef struct SeqList
{
	SLDataType* arr;
	int size;     //有效数据个数
	int capacity; //空间容量
}SL;

//增删查改

void SLInit(SL* ps);
void SLDestory(SL* ps);
void SLPrint(SL* ps);
void SLCheckCapacity(SL* ps);

void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
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)
{
	assert(ps);
	ps->arr = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);
	if (ps->arr == NULL)
	{
		perror("malloc");
		return;
	}
	ps->size = 0;
	ps->capacity = INIT_CAPACITY;
}

void SLDestory(SL* ps)
{
	assert(ps);

	free(ps->arr);
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

void SLPrint(SL* ps)
{
	assert(ps);

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

//检查容量
void SLCheckCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * ps->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		ps->arr = tmp;
		ps->capacity *= 2;
	}
}


//增删查改

//尾插
void SLPushBack(SL* ps, SLDataType x)
{
	// 
	assert(ps);
	SLCheckCapacity(ps);
	//ps->a[ps->size] = x;
	//ps->size++;
	ps->arr[ps->size++] = x;
}

//尾删
void SLPopBack(SL* ps)
{
	if (ps->size == 0)
	{
		return;
	}
	ps->size--;
}

//头插
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->arr[end + 1] = ps->arr[end];
		end--;
	}
	ps->arr[0] = x;
	ps->size++;
}

//头删
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);
	int str = 1;
	while (str < ps->size)
	{
		ps->arr[str - 1] = ps->arr[str];
		str++;
	}
	ps->size--;
}

//在pos位置处插入
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->arr[end + 1] = ps->arr[end];
		end--;
	}

	ps->arr[pos] = x;
	ps->size++;
}


//删除pos位置元素
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);

	int str = pos + 1;
	while (str < ps->size)
	{
		ps->arr[str - 1] = ps->arr[str];
		str++;
	}

	ps->size--;
}

//查找
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	int str = 0;
	while (str < ps->size)
	{
		if (ps->arr[str] == x)
		{
			return str;
		}
		str++;
	}
	return -1;
}

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，您的支持就是春人前进的动力！

点赞
收藏
关注作者

0/1000

抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认取消

加入云驻计划，成为创作者

华为云周边好礼
免费体验产品
特殊身份标识
线下官方门票
内部专家零距离
与10000+优质创作者共同成长

立即加入

【数据结构】顺序表

📖线性表

📖顺序表

📖动态顺序表

🔖结构

🔖初始化

🔖销毁

🔖尾插

🔖扩容

🔖尾删

🔖头插

🔖头删

🔖在pos位置插入

🔖删除pos位置元素

🔖查找

🔖打印顺序表元素

🔖时间复杂度分析

📖动态顺序表完整版源码

全部回复

设置昵称

关于作者

目录

加入云驻计划，成为创作者

【数据结构】顺序表

📖线性表

📖顺序表

📖动态顺序表

🔖结构

🔖初始化

🔖销毁

🔖尾插

🔖扩容

🔖尾删

🔖头插

🔖头删

🔖在pos位置插入

🔖删除pos位置元素

🔖查找

🔖打印顺序表元素

🔖时间复杂度分析

📖动态顺序表完整版源码

全部回复

设置昵称

关于作者

目录

加入云驻计划，成为创作者

推荐阅读

相关产品