欢迎来到白刘的领域 Miracle_86.-CSDN博客
系列专栏 数据结构与算法
先赞后看,已成习惯
创作不易,多多支持!
目录
一、数据结构的概念
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成,即数据由哪部分构成,以什么方式构成,以及数据之间存在的相互关系。
数据结构可以分为两类:线性数据结构和非线性数据结构。线性数据结构以线性的方式组织数据,例如数组、链表和栈。非线性数据结构是一种通过多个节点之间的关联来组织数据的方式,例如树和图。数据结构的选取和设计对于解决特定问题和提高算法效率非常重要。
我们可以将这个词拆分成“数据”和“结构”两部分。
什么是数据?数据可以是数字、文字、图像等。比如超市购物时的价格、数量,天气预报中的温度、湿度,或是社交媒体上的浏览量、点赞数,都是数据。它们为我们提供信息,帮助我们做出决策,让生活更加便捷。
什么是结构?当我们想要使用大量使用同类型的数据时,通过手动定义大量的独立的变量对于程序来说,可读性非常差,我们可以借助数组这样的数据结构将大量的数据组织在一起,结构也可以理解为组织数据的方式。
比如,想要在世界上找到“喜羊羊”的这只羊很难,但是我告诉你在青青草原找,那就特别好找。青青草原这一块地方就可以看成一个结构,有效地将羊群组织起来。
总结:
1.数据结构可以存储数据。
2.存储的数据能够方便查找。
那为什么我们需要数据结构呢?
在生活中,假如我们开了个餐馆,不借助排队的方式来管理客户,会导致客户就餐感受差、等餐时间长、餐厅营业混乱等情况。同理,程序中如果不对数据进行管理,可能会导致数据丢失、操作数据困难、野指针等情况。
良好的数据结构和算法设计对于确保程序的稳定性和效率至关重要。通过合理地组织和管理数据,我们可以提高程序的性能,减少错误,并为用户提供更好的体验。
我们曾学过最基础的数据结构:数组。
C语言中的百宝箱——数组(1)-CSDN博客
C语言中的百宝箱——数组(2)-CSDN博客
既然我们已经学过数组这种数据结构了,那我们还需要学其它的数据结构嘛?存在即合理,显然数组是有一定的局限性的。
假定数组有10个空间,已经使用了5个,向数组中插入数据的步骤应该是:
1. 求数组的长度(这里是10)。
2. 求数组的有效数据个数(这里是5)。
3. 判断数组是否已满(如果有效数据个数等于数组长度,则数组已满)。
4. 如果数组未满,向下标为有效数据个数的位置插入数据。
注意:在插入数据之前,必须判断数组是否已满。如果数组已满,则不能再继续插入数据,否则可能会导致数据覆盖或程序崩溃等严重问题。
假设数据量非常大,频繁的获取数组有效数据个数确实可能会影响程序执行效率。
所以我们可以得出结论:最基础的数据结构能提供的操作不能满足复杂算法的实现。
二、顺序表(Sequence List)
2.1 线性表的概念以及结构
线性表(linear list)是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构,常见的线性表包括顺序表(Sequence List)、链表、栈、队列、字符串等。
线性表在逻辑上是线性结构,也就是说它表现为一条连续的直线。然而,在物理结构上,线性表并不一定是连续的。线性表在物理上存储时,通常以数组和链式结构的形式存在。数组存储方式使得元素在内存中连续排列,便于通过下标快速访问;而链式存储方式则通过指针或引用将元素链接在一起,允许在动态环境中灵活地进行插入和删除操作。
如何来理解逻辑结构和物理结构呢?
简单来说,逻辑结构关注的是数据元素之间的逻辑关系,它描述的是数据应该如何被组织,而不关心数据具体是如何在计算机内存中存放的。例如,我们可以说一个列表是一系列有序的元素,这就是它的逻辑结构。
而物理结构,或者叫存储结构,则关心数据在计算机内存中的具体存放方式。比如,这个列表是用数组的形式连续存储在内存中,还是用链表的形式分散存储在内存中,这就是物理结构所关心的问题。
2.2 顺序表分类
2.2.1 顺序表和数组的区别
其实顺序表的底层逻辑是数组,对数组进行了封装,并且实现了常用的增删查改等接口。
2.2.2 顺序表的分类
顺序表分为静态顺序表和动态顺序表,顾名思义,一个静态动不了,一个动态可调节。
• 静态顺序表:
刚刚我们说了,顺序表是基于数组实现的,那静态顺序表就是基于定长数组实现的。
//静态顺序表
typedef int SLDataType;
#define N 7
typedef struct SeqList{
SLDataType a[N];
int size;
}SL;
• 动态顺序表:
动态一词,我们不由得想起之前提到的动态内存管理,没错动态顺序表确实是需要动态申请的。
内存地产风云录:malloc、free、calloc、realloc演绎动态内存世界的楼盘开发与交易大戏-CSDN博客
// 动态顺序表 -- 按需申请
typedef struct SeqList
{
SLDataType* a;
int size; // 有效数据个数
int capacity; // 空间容量
}SL;
2.3 顺序表的实现
还记得扫雷嘛各位,当时我们创建了三个文件,分别是:game.c,game.h和test.c。game.c用来存放函数的实现,game.h用来存放头文件以及宏,而test.c用来测试。写完函数进行测试,这是一个良好的习惯,今天我们实现顺序表也会这样操作,但这里不介绍test.c文件,着重讲解函数的实现。
首先,我们需要定义一个动态顺序表,我们将定义放在头文件中。
//定义顺序表中的数据类型,可以随时修改int
typedef int SLDataType;
//动态
typedef struct SeqList
{
SLDataType *arr;
int size; //有效数据个数
int capacity; //空间大小
}SL;
2.3.1 初始化
接下来我们需要对这个顺序表进行初始化(initialize)。
这个函数没什么好解释的,只需要将顺序表的成员,指针指向NULL,数变成0。唯一一点重要的是:我们传参的时候,需要传顺序表的地址。
要区别传值和传址,我们在这篇文章中解释过:
灵魂指针,教给(一)-CSDN博客
实参传递给形参的时候,形参会单独创建⼀份临时空间来接收实参,对形参的修改不影响实参。如果我们想修改顺序表里的值,那必然得传它的地址。代码如下:
//初始化,注意传址
void SLInit(SL* ps)
{
ps->arr = NULL;
ps->capacity = ps->size = 0;
}
2.3.2 销毁
这个函数也很简单,我们既然是动态申请的空间,就需要将其free掉。
函数实现:
//销毁
void SLDestroy(SL* ps)
{
if (ps->arr)
{
free(ps->arr);
}
ps->arr = NULL;
ps->capacity = ps->size = 0;
}
2.3.3 尾插
我们在尾插的时候,试想一下,如果空间不够,是不是就没位置插了,这个时候我们要重新开辟空间,并且,我们在初始化后,空间是0,肯定需要申请。所以这里我们需要一个函数来进行扩容:
//扩容
void SLCheckCapacity(SL* ps)
{
assert(ps);
//先判断空间是否足够,不够需要扩容
if (ps->capacity == ps->size) //不够扩容
{
//申请空间
//三目判断初始空间大小
int NewCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(ps->arr, NewCapacity * sizeof(SLDataType));
if (tmp == NULL)
{
perror("realloc fail");
exit(1);
}
ps->arr = tmp;
ps->capacity = NewCapacity;
}
}
首先我们用assert断言防止空指针,之后我们用到了if语句来判断空间是否足够,如果不够则进入if扩容。判断条件我们仔细想想,什么情况是空间不够,是不是当空间大小和有效数据个数相等时,就没法插入了,所以我们将这个作为判断条件。
扩容搞定后,我们就可以进行插入操作了,在尾插中,我们需要传入两个参数:一个是顺序表的地址,另一个是要插入的元素。
尾插其实很简单,我们只需要将最后的位置赋值为要插入的元素就可以了,最后别忘了既然插进去了一个元素,有效数据个数肯定要++。
//尾插
void SLPushBack(SL* ps, SLDataType x)
{
SLCheckCapacity(ps);
//足够尾插
ps->arr[ps->size++] = x;
/*ps->arr[ps->size] = x;
ps->size++;*/
}
2.3.4 头插
尾插我们直接在尾巴后面插入元素即可,头插意味着我们要在头部插入一个元素,那么我们就需要在头部为其留出位置,同时原有元素还不可以改变。有了位置再进行插入,思路清晰,直接上代码。
//头插
void SLPushFront(SL* ps, SLDataType x)
{
SLCheckCapacity(ps);
//整体挪动,再插入
for (int i = ps->size; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[0] = x;
ps->size++;
}
这里注意,for循环遍历时,从后往前遍历,防止覆盖。
2.3.5 尾删
大家想想,怎么删,将最后一个元素置为-1?还是别的什么数字?其实我们根本不需要管最后一个元素,我们直接将size进行 – – 即可。因为不影响其它功能,所以我们不用考虑那么复杂。
//尾删
void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->size);
//删完数据,size--
//ps->arr[ps->size - 1] = -1;要不要这行都可以
ps->size--;
}
2.3.6 头删
头删也很简单,直接覆盖即可。
//头删
void SLPopFront(SL* ps)
{
assert(ps);
assert(ps->size);
//直接覆盖即可
for (int i = 1; i < ps->size; i++)
{
ps->arr[i - 1] = ps->arr[i];
}
ps->size--;
}
2.3.7 在指定位置插入
我们效仿头插遍历,为元素留位置,在指定位置插入也是如此。
//在指定位置插入
void SLInsert(SL* ps, int pos, SLDataType x)//注意pos是下标
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
SLCheckCapacity(ps);
for (int i = ps->size; i > pos; i--)
{
ps->arr[i] = ps->arr[i - 1];//arr[pos+1]=arr[pos];
}
ps->arr[pos] = x;
ps->size++;
}
2.3.8 在指定位置删除
同样是遍历,同样是覆盖,不多解释,直接上代码。
//在指定位置删除
void SLErase(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
for (int i = pos; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];//arr[size-2]=arr[size-1]
}
ps->size--;
}
2.3.9 查找
其实查找也是遍历,我们可以发现,但凡我们弄清原理之后,顺序表还是蛮简单的。
//查找
int SLFind(SL* ps, SLDataType x)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return i;
}
}
return -1;
}
2.4 总代码
2.4.1 SeqList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//定义顺序表的结构
//#define N 100
//静态顺序表
//struct SeqList
//{
// int arr[N];
// int size;//有效数据个数
//};
//定义顺序表中的数据类型,可以随时修改int
typedef int SLDataType;
//动态
typedef struct SeqList
{
SLDataType *arr;
int size; //有效数据个数
int capacity; //空间大小
}SL;
//typedef struct SeqList SL;
//初始化
void SLInit(SL* ps);
//销毁
void SLDestroy(SL* ps);
//打印
void SLPrint(SL* ps);
//扩容
void SLCheckCapacity(SL* ps);
//尾部插入删除 / 头部插入删除
void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPopFront(SL* ps);
//指定位置之前插入/删除数据
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
//查找
int SLFind(SL* ps, SLDataType x);
2.4.2 SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
//初始化,注意传址
void SLInit(SL* ps)
{
ps->arr = NULL;
ps->capacity = ps->size = 0;
}
//销毁
void SLDestroy(SL* ps)
{
if (ps->arr)
{
free(ps->arr);
}
ps->arr = NULL;
ps->capacity = ps->size = 0;
}
//打印
void SLPrint(SL* ps)
{
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}
//扩容
void SLCheckCapacity(SL* ps)
{
assert(ps);
//先判断空间是否足够,不够需要扩容
if (ps->capacity == ps->size) //不够扩容
{
//申请空间
//三目判断初始空间大小
int NewCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(ps->arr, NewCapacity * sizeof(SLDataType));
if (tmp == NULL)
{
perror("realloc fail");
exit(1);
}
ps->arr = tmp;
ps->capacity = NewCapacity;
}
}
//尾插
void SLPushBack(SL* ps, SLDataType x)
{
SLCheckCapacity(ps);
//足够尾插
ps->arr[ps->size++] = x;
/*ps->arr[ps->size] = x;
ps->size++;*/
}
//头插
void SLPushFront(SL* ps, SLDataType x)
{
SLCheckCapacity(ps);
//整体挪动,再插入
for (int i = ps->size; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[0] = x;
ps->size++;
}
//尾删
void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->size);
//删完数据,size--
//ps->arr[ps->size - 1] = -1;要不要这行都可以
ps->size--;
}
//头删
void SLPopFront(SL* ps)
{
assert(ps);
assert(ps->size);
//直接覆盖即可
for (int i = 1; i < ps->size; i++)
{
ps->arr[i - 1] = ps->arr[i];
}
ps->size--;
}
//在指定位置插入
void SLInsert(SL* ps, int pos, SLDataType x)//注意pos是下标
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
SLCheckCapacity(ps);
for (int i = ps->size; i > pos; i--)
{
ps->arr[i] = ps->arr[i - 1];//arr[pos+1]=arr[pos];
}
ps->arr[pos] = x;
ps->size++;
}
//在指定位置删除
void SLErase(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
for (int i = pos; i < ps->size - 1; i++)
{
ps->arr[i] = ps->arr[i + 1];//arr[size-2]=arr[size-1]
}
ps->size--;
}
//查找
int SLFind(SL* ps, SLDataType x)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return i;
}
}
return -1;
}
完
版权声明:本文为博主作者:Miracle_86.原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/Miracle_86/article/details/138042116