程序员社区
当前位置：IDEA激活码 > 未分类 > 正文

初阶数据结构——线性表——顺序表

2022-02-05 分类：未分类 阅读(220)

🎉🎉想快速入门数据结构，推荐订阅作者的初阶数据结构专栏！此专栏预计更新：顺序表，链表，栈，队列，二叉树，排序算法等等

🎉🎉初阶数据结构我们通过c语言实现，所以此专栏也可以帮助大家巩固大家的c语言知识

⭐️写在前面

首先非常感谢各位小伙伴对我的支持，在大家的支持下，我们的c进阶专栏已经完结撒花啦！通过对c语言的学习，想必大家的代码能力已经得到了一定的提升

在这里插入图片描述

所以今天我们开始入坑计算机中最重要的学科之一：数据结构

在这里插入图片描述

这是度娘对数据结构的定义

**数据结构是计算机存储、组织数据的方式。**数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

解决的问题是：如何让计算机存储，组织我们需要存储的数据

我们今天从最简单的数据结构开始介绍：线性表中的顺序表

目录

  • 一些定义
    • 线性表
    • 顺序表
  • 顺序表的定义
    • 初始化
  • 增加元素
    • 尾插
    • 头插
    • 任意位置插入
  • 删除元素
    • 尾删
    • 头删
    • 任意位置删除
  • 查找
  • 其它函数
    • 打印函数
    • 顺序表销毁
  • 完整实现代码

一些定义

线性表

同样，先给出度娘上的定义

线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。
线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位结点）。

划重点板块：

线性表是一个有限的序列，存储具有相同特性的元素

线性表可能在物理上不连续，但在逻辑结构上一定是连续的

线性表的逻辑结构

在这里插入图片描述

链表的逻辑结构

在这里插入图片描述

可以显然观察到，它们是全部呈线性的

顺序表

本质是一个数组，在物理上连续存放

而我们今天要实现的，就是顺序表的增删查改

顺序表的定义

线性表的定义一般分为两种方法：静态的和动态的

我们先介绍线性表的基本框架

因为是采用数组存放，所以我们需要定义一个数组

另外，为了方便后续的操作和判断，需要引入变量来记录顺序表中已存储的元素个数

所以，我们用一个结构体来定义顺序表

struct SeqList
{
	int a[];//存储元素的数组
	int size;//数组此时的大小
}

逻辑结构就是这样的

在这里插入图片描述
但这样定义我们并没有给出数组的容量，所以这样定义不正确

所以，我们可以用#define定义这个数组的最大储存容量，这也是我们的静态实现方法

#define MAX 1000//定义一个最多能存储1000个元素的顺序表

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

在这里插入图片描述
但是，静态顺序表有一个很大的缺陷，就是定义多大的数组无法确定

例如，1000容量的数组只需存储10个元素，会造成空间的大量浪费

或者，存储100个元素我们只定义了10容量，存储空间显然不够

所以我们可以考虑，要多少容量，我们就开多少容量

这就是引入了我们的动态定义方式

注意，这里用到了动态内存管理的知识，如果对动态内存管理还不太了解的小伙伴，可以看看我的文章.

因为动态内存开辟需要指针，所以我们可以定义一个指针变量arr，作为数组

int* arr;

我们同样需要size来记录当前数组存储了多少元素

但是，我们现在要引入一个新的变量，用于记录当前数组的容量，当我们需要插入元素的时候，可以用这个变量检查是否需要增容

struct SeqList
{
	int* arr;
	int size;
	int capacity;//记录当前数组的最大容量
}

在这里插入图片描述
当然，我们还需要做一些改进
首先是typedef，简化顺序表的名称

typedef struct SeqList
{
	int* arr;
	int size;
	int capacity;//记录当前数组的最大容量
}SL;

其次，为了后续方便修改存储类型，我们可以将数据类型重命名

typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* a;
	int size;
	int capacity;//记录当前数组的最大容量
}SL;

至此，我们的顺序表定义全部完成

接下来是增删查改的实现

初始化

注意！在使用顺序表前，需要将顺序表初始化！

void SeqListInit(SL* ps)
{
	ps->a=NULL;//将数组置空
	ps->size=ps->capacity=0;//已存储数据和容量都为0
}

增加元素

尾插

先讲最容易实现的尾插

首先，我们刚初始化的数组，容量为0，肯定不够我们增加元素

而且后面也存在容量不够需要开辟新空间的问题

所以我们可以先实现一个增容函数

void SeqListCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)//检查是否存储个数达到容量上限
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//我们一次增容两倍，初始容量设定为4
		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcapacity);
		if (!tmp)
		{
			printf("%s\n", strerror(errno));
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;

	}
}

在这里插入图片描述

尾插，我们直接在数组后面添加新元素即可，不需要过多的介绍

在这里插入图片描述

void SeqListPushBack(SL* ps, SLDataType x)
{
	SeqListCheckCapacity(ps);//先检查容量是否达到上限
	ps->a[ps->size] = x;//直接在最后插入元素
	ps->size++;//最后不要忘了将存储个数+1
}

头插

在顺序表的最前面插入元素，实现要稍微复杂一点

因为顺序表的存储是按物理顺序的，所以我们要存储元素时，也需要将后面的数据依次往后挪动一位

在这里插入图片描述

void SeqListPushFront(SL* ps, SLDataType x)
{
	SeqListCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}//while里面实现数据的挪动
	ps->a[0] = x;
	ps->size++;
}

任意位置插入

插入同样需要挪动数据

为了避免数据覆盖，我们需要从后往前进行挪动数据

函数定义

void SeqListInsert(SL* ps, int pos, SLDataType x)

pos表示需要插入的位置

在这里插入图片描述

void SeqListInsert(SL* ps, int pos, SLDataType x)
{
	SeqListCheckCapacity(ps);
	if (pos <= 1)
	{
		SeqListPushFront(ps, x);
	}
	else if (pos >= ps->size)
	{
		SeqListPushBack(ps, x);
	}
	else
	{
		int end = ps->size - 1;
		while (end >= pos - 1)
		{
			ps->a[end + 1] = ps->a[end];
			end--;
		}
		ps->a[pos - 1] = x;
		ps->size++;
	}
}

删除元素

尾删

同样从最简单的尾删开始

假如我们的最初数据是这样

在这里插入图片描述
我们的尾删可以直接将size-1，让顺序表访问不到我们删的元素就行了

在这里插入图片描述
但如果数组为空的话，我们的删除将会出现size为负数的问题

所以需要注意：在删除前，我们需要判断数组是否为空

void SeqListPopBack(SL* ps)
{
	assert(ps->size);//判断数组是否为空
	ps->size--;//直接进行删除
}

头删

根据顺序表的定义，我们进行头删同样需要挪动数组，与头插相似

将数据往前挪动即可

在这里插入图片描述

void SeqListPopFront(SL* ps)
{
	assert(ps->size);
	int start = 0;
	while (start < ps->size - 1)
	{
		ps->a[start] = ps->a[start + 1];
		start++;
	}//while里面是挪动数据
	ps->size--;
}

任意位置删除

聪明的你，应该能举一反三了吧！

所以这个函数我不画图实现，大家可以尝试自己理解~

void SeqListErase(SL* ps, int pos)
{
	assert(ps->size);
	if (pos == 1)
	{
		SeqListPopFront(ps);
	}
	else if (pos == ps->size)
	{
		SeqListPopBack(ps);
	}
	else
	{
		int cur = pos - 1;
		while (cur < ps->size)
		{
			ps->a[cur] = ps->a[cur + 1];
			cur++;
		}
		ps->size--;
	}
}

查找

我们这里直接暴力查找

函数返回值为某数据在数组中的位置，如果没有找到则返回-1

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

使用方法：

我们可以使用这个函数来找某个数据在顺序表中存在的位置

int pos=0;
int x=0;//某个查找的数字
pos=SeqListFind(ps,x);

其它函数

打印函数

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

顺序表销毁

因为是动态开辟的内存，所以我们使用完需要销毁以防止内存泄露

void SeqListDestory(SL* ps)
{
	free(ps->a);//释放内存
	ps->a = NULL;//指针置空
	ps->size = ps->capacity = 0;//容量设置为0
}

完整实现代码

//SeqLish.h
#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<windows.h>
#include<assert.h>
#include<errno.h>

typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* a;
	int size;
	int capacity;
}SL;

void SeqListInit(SL* ps);

void SeqListPrint(SL* ps);

void SeqListDestory(SL* ps);

void SeqListCheckCapacity(SL* ps);

void SeqListPushBack(SL* ps, SLDataType x);

void SeqListPushFront(SL* ps, SLDataType x);

void SeqListPopBack(SL* ps);

void SeqListPopFront(SL* ps);

int SeqListFind(SL* ps, SLDataType x);

void SeqListInsert(SL* ps, int pos, SLDataType x);

void SeqListErase(SL* ps, int pos);

//SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"

void SeqListInit(SL* ps)
{
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

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

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

void SeqListCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcapacity);
		if (!tmp)
		{
			printf("%s\n", strerror(errno));
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;

	}
}

void SeqListPushBack(SL* ps, SLDataType x)
{
	SeqListCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}
void SeqListPushFront(SL* ps, SLDataType x)
{
	SeqListCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}
void SeqListPopBack(SL* ps)
{
	assert(ps->size);
	ps->size--;
}
void SeqListPopFront(SL* ps)
{
	assert(ps->size);
	int start = 0;
	while (start < ps->size - 1)
	{
		ps->a[start] = ps->a[start + 1];
		start++;
	}
	ps->size--;
}

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

void SeqListInsert(SL* ps, int pos, SLDataType x)
{
	SeqListCheckCapacity(ps);
	if (pos <= 1)
	{
		SeqListPushFront(ps, x);
	}
	else if (pos >= ps->size)
	{
		SeqListPushBack(ps, x);
	}
	else
	{
		int end = ps->size - 1;
		while (end >= pos - 1)
		{
			ps->a[end + 1] = ps->a[end];
			end--;
		}
		ps->a[pos - 1] = x;
		ps->size++;
	}
}

void SeqListErase(SL* ps, int pos)
{
	assert(ps->size);
	if (pos == 1)
	{
		SeqListPopFront(ps);
	}
	else if (pos == ps->size)
	{
		SeqListPopBack(ps);
	}
	else
	{
		int cur = pos - 1;
		while (cur < ps->size)
		{
			ps->a[cur] = ps->a[cur + 1];
			cur++;
		}
		ps->size--;
	}
}

赞(0) 打赏
未经允许不得转载：IDEA激活码 » 初阶数据结构——线性表——顺序表

相关推荐

IDEA永久激活破解教程,IDEA激活码

pycharm激活破解教程,pycharm激活码

Java视频资源

Java电子书

DataGrip激活教程 Docker Git教程 IntellIJ idea IntelliJ IDEA激活码 Java Java IO Java基础 Java基础面试题 Java集合面试题 Java面试题 JVM JVM面试题 Linux MySQL MySQL面试题 Nginx PyCharm PyCharm激活 redis Redis SpringBoot SpringBoot SpringBoot面试题 Web开发 剑指Offer系列 多线程 多线程并发面试题 字符串面试题 数据库 数据库 数据结构与算法 未分类 爬虫 电子书 软件下载

一个分享Java & Python知识的社区