数据结构——顺序表

用户11352420

发布于 2024-11-07 21:34:40

650

发布于 2024-11-07 21:34:40

文章被收录于专栏：编程学习

今天我们来进入数据结构的下一节——顺序表，在正式开始说顺序表之前，我们首先需要知道线性表的概念！

线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列（集合）

线性表有两个特点：

在逻辑结构[我们认为想象出来的数据组织形式]上，都是线性的，也就说是连续的⼀条直线。在物理结构[数据在内存上的存储形式]上，不一定是线性的，通常以数组和链式结构的形式存储。

线性表是⼀种在实际中广泛使用的数据结构

常⻅的线性表：顺序表、链表、栈、队列、字符串……

根据定义[线性表（linear list）是n个具有相同特性的数据元素的有限序列（集合）]

我们可以与日常生活中的水果进行类比，水果：苹果，梨，香蕉……

我们可以看到，顺序表是线性表的一种，那么顺序表到底是什么呢？

我们一起来看看

顺序表

概念

顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采用数组存储。

一般情况下采用数组存储，那么顺序表和数组有什么区别呢？

我们来举一个形象的例子, 苍蝇馆子和米其林餐厅，就像数组和顺序表

我们可以看到，顺序表的底层结构就是数组，顺序表是对数组的封装，实现了常用的增删查改等接口操作。

顺序表如何对数组的封装呢？也就是使用了结构体。

分类

静态顺序表

概念

使用定长数组来进行存储元素

形式

一般结构形式如下：

#define N 7
struct SeqList
{
	int a[N];//定义定长数组
	int size;//size有效数据的个数
};

我们也可以对它进行优化，有时候我们存储的元素可能不是int类型，如果是其他类型呢？我们可以使用重命名的方式进行优化。

typedef int SLDataType;//重命名顺序表的数据类型
//注意：重命名后面有分号

#define N 7

typedef struct SeqList
{
	SLDataType a[N];//定义定长数组
	int size;//size有效数据的个数
}SL;//重命名整个结构体（顺序表）为SL，方便后面进行使用

缺陷

静态顺序表使用定长数组来存储元素，这样就会有一些缺陷：

空间给少了不够用，给多了又会造成空间的浪费

所以我们一般使用的顺序表是另外一种，也就是动态顺序表。

动态顺序表

概念

按需申请内存空间来存储元素

形式

typedef int SLDataType;//重命名顺序表的数据类型
//注意：重命名后面有分号

typedef struct SeqList
{
	SLDataType* a;
	int capacity;//capacity数组容量大小
	int size;//size有效数据的个数
}SL;//重命名整个结构体（顺序表）为SL，方便后面进行使用

我们可以使用动态内存管理对动态顺序表进行增容

动态顺序表的实现

实现动态顺序表，我们需要三个不同的文件

SeqList.h 定义顺序表结构，声明要提供的操作 SeqList.c 具体实现各种操作 test.c 进行函数的测试

初始化

首先我们需要在头文件中进行初始化函数的声明

然后在源文件SeqList.c中定义函数

初始化函数写好了之后可以在test.c函数中进行测试

通过监视，我们可以发现成功完成了初始化

这里需要注意的是我们进行函数调用的时候

如果进行传值调用，即使形参的值改变，实参的值并不会发生改变，这里我们想要的是实参的值也发生改变就需要进行的是传址调用，传址调用操作的是同一块内存空间。

后面的函数代码使用的方式差不多，我们接下来会展现的是SeqList.c中函数实现的代码。

销毁

有了这两个操作，接下来我们就可以进行顺序表的增删查改的操作了

尾插

增容

我们在顺序表末尾进行一个数据的插入，插入一个数据我们首先就需要检查顺序表的容量与有效数据个数的大小关系。

如果有效数据个数等于顺序表容量就说明容量满了需要进行增容操作

增容操作需要使用realloc进行操作，如果增加顺序表容量时一个一个这样进行增加，会有一定的损耗，所以一般情况下当容量不足时，进行两倍的增容。

检查容量

void CheckCapacity(SL* ps)
{
//判断空间是否充足
	if (ps->size >= ps->capacity)//说明空间不够
	{
		//增容  
		//如果容量==0,容量扩大为默认值4，除此之外，容量扩大为原来的两倍
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
			//如果没有创建空间成功就退出
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
}

尾插

void SLPushBack(SL* ps,SLDataType x)
{
	assert(ps);//等价于assert(ps!=NULL);
	//if(ps==NULL)
	//{
	//    return;
	//}
	CheckCapacity(ps);
	ps->a[ps->size++] = x;
	//后置++，先使用后++
}

头插

void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	CheckCapacity(ps);
	if (ps->size != 0)
	{
		for (int i = ps->size; i > 0; i--)
		{
			ps->a[i] = ps->a[i - 1];
		}//每一个数据往后面移动一个位置
	}
	ps->a[0] = x;
	ps->size++;
}

尾删

void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);//数据个数不为0
	ps->size--;
}

头删

void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);//数据个数不为0
	for (int i = 0 ; i < ps->size ; i++ )
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

指定下标处插入

void SLPushPos(SL* ps, SLDataType x,int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	//注意下标的范围
	CheckCapacity(ps);
	for (int i = ps->size; i > pos; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[pos] = x;
	ps->size++;
}

指定下标处删除

void SLPopPos(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

查找指定数据

int FindSLData(SL* ps, SLDataType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
			return i;//返回下标
	}
	return -1;
}

更改指定下标的数据

void SLAlterPos(SL* ps, SLDataType x, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	ps->a[pos] = x;
}

总代码

通过上面的代码我们可以实现顺序表的增删查改操作

为了大家更加清楚的明白这些代码的实现，在下面把不同文件代码复制出来。

SeqList.h

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


typedef int SLDataType;//重命名顺序表的数据类型
//注意：重命名后面有分号

typedef struct SeqList
{
	SLDataType* a;
	int capacity;//capacity数组容量大小
	int size;//size有效数据的个数
}SL;//重命名整个结构体（顺序表）为SL，方便后面进行使用


//动态顺序表的初始化
void SLInit(SL* ps);
//销毁
void SLDestory(SL* ps);

//检查容量
void CheckCapacity(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 SLPushPos(SL* ps, SLDataType x,int pos);
//指定下标处删除
void SLPopPos(SL* ps, int pos);
//查找指定数据
int FindSLData(SL* ps, SLDataType x);
//更改指定下标的数据
void SLAlterPos(SL* ps, SLDataType x, int pos);

SeqList.c

#include"SeqList.h"

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


//销毁
void SLDestory(SL* ps)
{
	if (ps->a)//if(ps->a!=NULL)
	{
		free(ps->a);
	}
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

void CheckCapacity(SL* ps)
{
//判断空间是否充足
	if (ps->size >= ps->capacity)//说明空间不够
	{
		//增容  
		//如果容量==0,容量扩大为默认值4，除此之外，容量扩大为原来的两倍
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
			//如果没有创建空间成功就退出
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
}


void SLPushBack(SL* ps,SLDataType x)
{
	assert(ps);//等价于assert(ps!=NULL);
	//if(ps==NULL)
	//{
	//    return;
	//}
	CheckCapacity(ps);
	ps->a[ps->size++] = x;
	//后置++，先使用后++
}


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


void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	CheckCapacity(ps);
	if (ps->size != 0)
	{
		for (int i = ps->size; i > 0; i--)
		{
			ps->a[i] = ps->a[i - 1];
		}//每一个数据往后面移动一个位置
	}
	ps->a[0] = x;
	ps->size++;
}

void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);//数据个数不为0
	ps->size--;
}

void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);//数据个数不为0
	for (int i = 0 ; i < ps->size ; i++ )
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}


void SLPushPos(SL* ps, SLDataType x,int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	//注意下标的范围
	CheckCapacity(ps);
	for (int i = ps->size; i > pos; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[pos] = x;
	ps->size++;
}


void SLPopPos(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}


int FindSLData(SL* ps, SLDataType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
			return i;//返回下标
	}
	return -1;
}

void SLAlterPos(SL* ps, SLDataType x, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	ps->a[pos] = x;
}

test.c

#include"SeqList.h"
testSL1()
{
	SL s;
	SLInit(&s);
	/*SLPushBack(&s, 1);
	SLPrint(&s);
	SLPushBack(&s, 2);
	SLPrint(&s);
	SLPushBack(&s, 3);
	SLPrint(&s);
	SLPushBack(&s, 4);
	SLPrint(&s);*/
	SLPushFront(&s, 1);
	SLPrint(&s);
	SLPushFront(&s, 2);
	SLPrint(&s);
	SLPushFront(&s, 3);
	SLPrint(&s);
	SLPushFront(&s, 4);
	SLPrint(&s);
	/*SLPopBack(&s);
	SLPrint(&s);
	SLPopBack(&s);
	SLPrint(&s);*/
	/*SLPopFront(&s);
	SLPrint(&s);
	SLPopFront(&s);
	SLPrint(&s);*/
	/*SLPushPos(&s, 7, 3);
	SLPrint(&s);*/
	/*SLPopPos(&s, 2);
	SLPrint(&s);
	SLPopPos(&s, 2);
	SLPrint(&s);*/
	SLAlterPos(&s, 6, 2);
	SLPrint(&s);
	int ret = FindSLData(&s, 6);
	if (ret == -1)
		printf("没有找到\n");
	else
		printf("找到了，下标是%d\n", ret);
	SLDestory(&s);
}
int main()
{
	testSL1();
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-10-16，如有侵权请联系 cloudcommunity@tencent.com 删除

存储