【C】初阶数据结构2 -- 顺序表

news/2025/1/15 20:02:26/

  前面学习了数据结构的入门内容时间复杂度与空间复杂度,就可以来学第一个数据结构,也是最简单的数据结构 -- 顺序表。

  本文将会介绍线性表、顺序表的定义,以及顺序表的基础操作。


目录

 一  线性表的定义

二  顺序表

1  顺序表的定义

2  顺序表的分类

3  顺序表的结构体定义

1) 静态顺序表

2) 动态顺序表的定义

4  动态顺序表的实现

1) 文件结构

2) 方法的实现

3) 代码实现 


重点一  线性表的定义

 一  线性表的定义

  所谓线性表,就是指n个相同特性的数据元素的有限序列,也是一组具有相同特性的数据结构的集合,如:顺序表,链表,栈和队列都属于线性表,线性表有个很大的特性,就是逻辑结构上一定是连续的,而物理结构(存储结构)不一定是连续的,如顺序表在逻辑结构和物理结构上都是连续的,而链表在逻辑结构上是连续的,而在物理结构上不是连续的(以后会讲解到)。

  逻辑结构是指:人们抽象出来用来表示某种数据结构数据元素之间的逻辑上的关系,比如我们习惯上用一些矩形来表示数组,一个箭头来表示指针。

  物理结构是指:数据真正存储在计算机中的实际布局和存储方式,比如数组在在内存里面存储的时候就是一块连续的内存空间。


重点二  顺序表

二  顺序表

1  顺序表的定义

  概念: 线性表的顺序实现就是顺序表。顺序表是指用一段物理地址连续的存储单元依次存储数据元素的线性结构。其一般情况下是采用数组存储的

  其实顺序表底层就是用数组实现的,都是用一块物理地址连续的内存空间存储数据,但是他们之间是区别的:

顺序表与数组之间的区别:顺序表的底层是数组,但是顺序表对数组进行了封装,增加了
增、删、查、改等方法接口,可以直接使用这些方法来实现数据的增、删、查、改。

2  顺序表的分类

  顺序表分为两类,一种是静态顺序表,一种是动态顺序表。

  静态顺序表:开辟的空间是固定的,一旦开辟的空间使用完,就没法对顺序表进行增容增加数据

  动态顺序表:开辟的空间是不确定的,可以根据实际需要进行增容

  显然,相比于动态顺序表,静态顺序表所能使用的空间是有限的,一旦确定了空间的大小,那么空间大小就无法改变,如果数据很少,就会造成空间的浪费,如果数据很多,那么空间又不够用,所以动态顺序表在实际应用中使用的更多。

3  顺序表的结构体定义

  在顺序表中,由于顺序表的底层是数组且为了存储数据,所以顺序表的结构体中应该有一个数组;其次,应该还有一个整型变量用来记录顺序表中有效数据的个数,用来判断是否达到数组的最大容量了,以便于以后判断是否还能继续插入数据;再来,在动态顺序表中由于数组的容量是不确定的,所以应该再有一个整型变量用来记录数组的容量大小,以便于以后进行增容等操作。

1) 静态顺序表

  在静态顺序表中,只需要一个数组和一个用来记录有效数据个数的整型变量就可以了,静态顺序表的定义如下:

typedef struct SeqList //Sequence List -- 顺序表的英文
{int arr[100];//存储数据的数组int size;//顺序表中有序数据的个数
}SL;

  但是这样定义有一个缺点,就是这个顺序表只能存储整形数据,假如我们以后写了插入数据啊,删除数据等方法接口,那么就只能对整形数据进行操作,无法进行别的数据类型的操作,这就不太方便,所以我们可以通过一个 typedef 关键字对 int 进行重定义为 SLDataType ,以后都用这个数据类型,如果以后想要对别的数据类型采用顺序表这一数据结构,就可以只改 typedef 这个地方就可以了;同样的,数组的大小 100 也可通过 #define 来定义

真正的定义:

#define N 100
typedef int SLDataType;
typedef struct SeqList //Sequence List -- 顺序表的英文
{SLDataType arr[N];//存储数据的数组int size;//顺序表中有序数据的个数
}SL;

2) 动态顺序表的定义

  在动态顺序表里面,需要在以上基础上再增加一个用来表示数组容量的整型变量,且由于数组容量不确定,需要动态开辟,所以这里的数组其实是个指针。

动态顺序表结构体定义:

typedef int SLDataType;typedef struct SeqList
{SLDataType* arr;//动态开辟空间的数组int size;//有效数据个数int capacity;//数组容量大小
}SL;

  这里的arr会指向了动态开辟空间的首地址。

4  动态顺序表的实现

  由于静态顺序表类似于动态顺序表,且动态顺序表更加复杂,所以在这里我们只实现动态顺序表。

  动态顺序表的方法接口包括顺序表的初始化,顺序表的销毁,顺序表的头部插入(头插),尾插,头删,尾删,在指定位置之前插入数据,在指定位置之前删除数据,数据的查找,数据的打印这些基础操作

1) 文件结构

  首先在写代码之前,我们应该了解文件的结构,以后每次在实现一个数据结构的时候,我们都应创建3个文件,分别是:

SeqList.h
SeqList.c
test.c

  其中SeqList.h是头文件,用来包含所需的库函数的头文件,以及动态顺序表的结构定义和顺序表方法函数的声明,SeqList.c用来实现具体方法,test.c是测试文件,用来测试我们写的方法对不对。

2) 方法的实现

  我们会在前面先讲解每个方法是如何实现的,所有代码都会放到最后。

(1) 初始化和销毁

  这两个函数很简单,初始化只需要把动态顺序表里面的三个变量初始化,就是把arr = NULL,size = capacity = 0;由于arr的空间是动态开辟的,所以在销毁的时候只需把arr开辟的空间释放掉,然后不要忘记让arr = NULL,否则arr会变成野指针,最后再让size = capacity = 0就可以了。 

(2) 顺序表的打印

  这个也很容易实现,就是数组元素的打印,用一个for循环就可以实现了。

(3) 头插,头删

   头插:涉及到三种情况,需要特别注意的是插入一个数据之后,需要让size++,且原来数据的相对位置和值不能改变。

   第一种: 数组为空,这时capacity = size = 0,此时需要先开辟数组空间再进行插入,由于顺序表需要增容,所以这里使用realloc函数进行增容,刚开始我们选择开辟4个空间,插入过程如下图所示:

   第二种: 数组中已有数据且顺序表没满时,为了防止原来数据变化,需要先让之前的数据往后挪,注意这里只能从大的下标开始挪,要是从小的下标开始就会覆盖数据,然后最后在0下标处存入数据就可以了,最后不要忘记让size++,插入过程如图所示:

  第三种:数组已经满了,也就是size == capacity时,这时候需要再是使用realloc函数增容,这时候我们采取的是二倍增容,也就是在原来capacity的基础上,让顺序表的容量变成2 * capacity,当然,你也可以采用3倍增容啊,4倍增容啊都是可以的,然后采用第二种情况插入的方法,先让数据向后挪,然后在0下标位置放入数据,最后让size++就可以了,插入过程如图所示:

   头删:只要是删除数据的时候,我们都需要检查顺序表是否为空,也就是size == 0的时候,我们是不能删除数据的,因为顺序表里面连数据都没有!如果顺序表不为空,那么就只需让下标为1到下标为 size - 1 的数据依次往前挪,也就完成了头删,最后不要忘了让size--,但是这里有一个特别需要注意的问题,就是挪动数据的时候需要从前往后挪,从后往前挪的话会覆盖前面的数据的,头删除过程如图所示:

(4) 尾插,尾删

  尾插: 尾插比头插简单,没有那么多情况要分,只要让size下标位置的数据插入元素,然后让size++就可以了,因为比较简单,也就不画图了。

  尾删:前面头删的时候说到了,删除数据的时候也要检查顺序表是不是空,所以要先判断顺序表是否是空,如果不为空的话,是不是我们需要把 size 下标数据删掉呢?其实这里只需要让 size-- 就可以了,因为如果以后要插入数据的时候,插入的数据就会把原来那个要删除位置的数据覆盖,也就达到了删除数据的效果了。

(5) 数据的打印

  这个方法也比较简单,就是一个数组的打印函数,只需要把顺序表结构里面的那个数组打印一下就可以了。

(6) 在指定位置之前插入数据,在指定位置之前删除数据

  在指定位置之前插入数据: 比如我们要在pos下标位置之前插入数据,那么我们需要先让pos下标之后的数据先往后挪一位,然后再在pos下标处插入数据就可以了,同样的,既然是插入数据,我们也要让size++,需要注意的一点是,pos必须是大于等于0的,是不能在负下标位置插入数据的,在pos位置之前插入数据过程如图所示:

  我们再来看一下极端情况,就是顺序表为空的时候, 要在pos为0的位置插入数据的时候,先把0下标到 size - 1 下标的数据先向后挪一位,然后让0下标插入数据就可以了,通过分析,发现其实这个也是适用的。

  在指定位置之前删除数据: 既然是删除数据,就先需要判断顺序表是否为空,如果顺序表不为空,那就让 pos 下标即之后的数据依次向前挪动一位就可以了,这里同样的必须从pos下标开始,到size - 1下标这个顺序挪动数据,否则就会覆盖数据,最后不要忘记让 size-- 就可以了,删除过程如图所示

3) 代码实现 

(1) SeqList.h 头文件:

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLDataType;
typedef struct SeqList
{SLDataType* arr; //顺序表数组int size; //有效数据个数int capacity; //容量
}SL;//初始化
void SLInit(SL* ps);
//销毁
void SLDestroy(SL* ps);
//打印
void SLPrint(SL* ps);
//头插
void SLPushFront(SL* ps, SLDataType x);
//头删
void SLPopFront(SL* ps);
//尾插
void SLPushBack(SL* ps, SLDataType x);
//尾删
void SLPopBack(SL* ps);
//扩容
void SLCheckCapacity(SL* ps);
//指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x);
//指定位置之前删除数据
void SLErase(SL* ps, int pos);
//查找
int SLFind(SL* ps, SLDataType x);

  这里增加了一个函数,是增容函数,因为这个函数经常使用,所以这里增加了一个函数用来使用。

(2) SeqList.c实现文件:

#include"SeqList.h"//初始化
void SLInit(SL* ps)
{assert(ps);//传过来的ps不能是空指针,要对空指针进行断言ps->arr = NULL;ps->size = ps->capacity = 0;
}
//时间复杂度:O(1)//销毁
void SLDestroy(SL* ps)
{assert(ps);//传过来的ps也不能为空指针free(ps->arr);//销毁动态开辟的数组空间ps->arr = NULL;//要把指针置为空ps->size = ps->capacity = 0;//再把有效数据和容量置为0
}
//时间复杂度:O(1)//打印
void SLPrint(SL* ps)
{assert(ps);for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}
//时间复杂度:O(n)//头插
void SLPushFront(SL* ps, SLDataType x)
{SLCheckCapacity(ps);//先判断顺序表是否满了//先让前面数据往后挪for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];//从下标大的开始往后挪}//再让0下标位置放入数据ps->arr[0] = x;//最后别忘了让size++ps->size++;
}
//时间复杂度:O(n)//头删
void SLPopFront(SL* ps)
{assert(ps && ps->size);//要先判断ps是否是NULL或者顺序表为空//直接让数据向前挪--这里要从下标小的往前挪for (int i = 0; i < ps->size; i++){ps->arr[i] = ps->arr[i + 1];}//最后让size--ps->size--;
}
//时间复杂度:O(n)//尾插
void SLPushBack(SL* ps, SLDataType x)
{//要先判断顺序表是否为满SLCheckCapacity(ps);//直接让size下标位置插入数据,并让size++ps->arr[ps->size++] = x;
}
//时间复杂度:O(1)//尾删
void SLPopBack(SL* ps)
{//先判断ps是否为NULL和顺序表是否为空assert(ps && ps->size);//直接让size--ps->size--;
}
//时间复杂度:O(1)//扩容
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//三目操作符,判断容量是否为0SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * newCapacity);//增容里面必须是字节数//开辟失败if (tmp == NULL){perror("realloc fail!\n");exit(1);}//开辟成功ps->arr = tmp;ps->capacity = newCapacity;}
}
//时间复杂度:O(1)//指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{//先判断是否为满SLCheckCapacity(ps);//先让pos下标及之后的数据向后挪for (int i = ps->size; i >= pos; i--){ps->arr[i] = ps->arr[i - 1];}//让pos下标插入数据ps->arr[pos] = x;//最后让size++ps->size++;
}
//时间复杂度:O(n)//指定位置之前删除数据
void SLErase(SL* ps, int pos)
{//先判断ps是否为NULL与顺序表是否为空assert(ps && ps->size);assert(pos > 0);//先让pos及之后的数据向前挪for (int i = pos; i < ps->size; i++){ps->arr[i - 1] = ps->arr[i];}//再让size--ps->size--;
}
//时间复杂度:O(n)//查找
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;//返回-1表示没有找到
}
//时间复杂度:O(n)

测试文件test.c:

#include"SeqList.h"void Test()
{SL sl;SLInit(&sl);//测试尾插SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPrint(&sl);//测试头插//SLPushFront(&sl, 1);//SLPushFront(&sl, 2);//SLPushFront(&sl, 3);//SLPushFront(&sl, 4);//SLPrint(&sl);//测试头删//SLPopFront(&sl);//SLPopFront(&sl);//SLPopFront(&sl);//SLPopFront(&sl);//SLPopFront(&sl);//SLPrint(&sl);//测试尾删//SLPopBack(&sl);//SLPopBack(&sl);//SLPopBack(&sl);//SLPopBack(&sl);//SLPopBack(&sl);//SLPrint(&sl);//测试在指定位置之前插入数据SLInsert(&sl, 0, 5);SLInsert(&sl, 2, 6);SLPrint(&sl);SLErase(&sl, 2);SLPrint(&sl);SLErase(&sl, 1);SLPrint(&sl);int ret = SLFind(&sl, 10);if (ret == -1)printf("找不到!\n");elseprintf("找到了!\n");SLDestroy(&sl);
}int main()
{Test();return 0;
}

  在测试文件里面你当然也可以采用其他的测试用例,但是我们在测试方法的时候我们要测试所有可能出现的情况,比如要看顺序表为空的时候还能不能删除数据啊,再指定位置之前插入数据能不能在0下标之前插入数据啊等等极端情况,这时候我们才能保证我们写的方法是适用于所有情况的。

  另外,还是想要说一句,这个的实现代码并不是唯一的,如果代码不一样,只要能实现功能就可以了;当然,你也可以增加其他的方法,比如在指定位置之后插入数据,删除数据啊等等都可以。

  在SeqList.c实现文件里,写了每个方法代码实现对应的时间复杂度,所以我们可以看到顺序表有一些缺点

(1)头插,头删,中间插入,中间删除这四个方法的时间复杂度为O(n)

(2)顺序表是需要增容的,增容的时候需要先开辟空间,然后再拷贝数据,这个时间开销也很大

(3)在顺序表满了之后增容的时候,我们采用二倍增容,一旦顺序表的占用空间很大且满了之后,我们使用二倍增容后,但是只使用几个空间,就会造成空间的浪费

  顺序表的这些缺点都会在链表中得到解决,之后我们会讲解。 


http://www.ppmy.cn/news/1563415.html

相关文章

为ARM64架构移植Ubuntu20.04换源的发现

在为ARM64架构(RK3566)移植ubuntu20.04的时候发现在更换为国内源之后&#xff0c;无法正常完成apt update,报错为: Ign:25 http://mirrors.aliyun.com/ubuntu focal-updates/main arm64 Packages …

45. 跳跃游戏2

题目 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说&#xff0c;如果你在 nums[i] 处&#xff0c;你可以跳转到任意 nums[i j] 处: 0 < j < nums[i] i j < n 返回到达 nums[n - 1…

LeetCode | 图文详细描述动态规划DP算法及经典题型

本文将用简单直白的方式&#xff0c;从零开始带你掌握动态规划的精髓。你会发现&#xff1a; 动态规划其实没那么难——它就是递归的“记性”版。状态转移方程不再玄学——从题目思路到实现&#xff0c;手把手教你推导。经典题型剖析——从“爬楼梯”到“背包问题”&#xff0…

web.xml常用配置

web.xml是Java Web应用程序的部署描述文件&#xff0c;它位于WEB-INF目录下。web.xml文件主要用于配置Servlet、Filter、Listener、MIME类型、欢迎页面等组件&#xff0c;以及一些Web应用的上下文参数。以下是一些常见的web.xml配置说明&#xff1a; Servlet配置&#xff1a; …

如何将json字符串格式化

文章目录 如何对json字符串进行格式化显示hutool方案的示例和不足使用fastjson的方案 如何对json字符串进行格式化显示 将json字符串内容进行格式化的输出显示。本文介绍 hutool的方案和alibaba 的fastjson方案 hutool方案的示例和不足 引入依赖 <dependency><grou…

【SVN】版本发布快捷操作

摘要&#xff1a;因为每次发版都需要制作一份相同的文件夹&#xff0c;而大部分的包都不需要变更&#xff0c;但是文件又非常大&#xff0c;记录自己的操作经验。 首先在SVN Repository Browser 界面把上一次的版本复制一份&#xff0c;复制的时候重命名为新的版本号 右击要复…

Win11远程桌面怎么设置?

通过Windows自带的远程桌面功能&#xff0c;可以轻松的远程访问另一台电脑。不过&#xff0c;在使用这一功能之前&#xff0c;需要先进行相关的设置。那么&#xff0c;Win11远程桌面怎么设置&#xff1f;接下来&#xff0c;我们将为您提供详细的Win11远程桌面设置步骤。 步骤 …

【51项目】51单片机自制小霸王游戏机

视频演示效果: 纳新作品——小霸王游戏机 目录: 目录 视频演示效果: 目录: 前言: