数据结构----顺序表

news/2024/11/17 3:42:50/

在学习顺序表之前，我们先来了解一下数据结构。

数据是什么呢？

我们在生活中常见的名字，数字，性别等都属于数据。

结构又是什么呢？

在计算机中，结构就是用来保存数据的方式。

总的来说，数据结构就是计算机存储和组织数据的方式。

1.顺序表

顺序表是数据结构中的一种，也就是说顺序表是一种用来存储和组织数据的一种结构，并且顺序表的底层本质就是数组，只不过顺序表是在数组的的基础上，增加了增删查改的方法，也就是说顺序表里面已经提供了对数据进行增删查改的现成的方法。只不过顺序表里面的增删查改的方法需要我们通过代码来实现，实现顺序表里面的增删查改的代码之后，以后我们实现对通讯录里面数据的增删查改的操作直接用就行了。

同时顺序表是线性表的一种。

1.1线性表

线性表就是具有相同特性的的数据结构的集合。

数据结构是否具有相同特性是从物理结构和逻辑结构来判断。

物理结构：数据在内存中存储的样子。由于我们无法得知计算机是如何给数据分配内存的，所以数据结构有连续和不连续的两种。

逻辑结构：逻辑结构一定是连续的。逻辑结构是我们抽象想象的。

比如排队的时候，我们排对的时候可能排的不是一条直线，但是我们还是得一个一个按序付钱，虽然看起来是不连续的，但在逻辑上我们将其抽象想象成线性的。

前面我们提到，顺序表的底层结构就是数组，而数据又是一块连续的空间，所以顺序表在物理结构和逻辑结构上都是连续的。

 

2.顺序表的分类

我们将顺序表分为了两种，分别为静态顺序表和动态顺序表。

2.1 静态顺序表

静态顺序表简单来说就是一个定长的数组。

如下图

1255d2824f2c4bb0af1ed8d5b340029a.png

此时Seqlist就是一个静态顺序表，该顺序表能储存的数据个数大小已经确定，其只能存储100个数据。

2.1动态顺序表

动态顺序表就是一个未定长的数组，也就是动态顺序表里面的数组能存储数据的个数是未定的，但是动态顺序表能存储的数据个数是可以根据实际情况实现动态改变的。

d73fc86872a74f9581c4c3e79924a40d.png

那上面两种顺序表哪种更好用呢？

肯定是动态顺序表。因为它能够根据实际情况来动态实现增容或删除数据。

3.动态顺序表的的实现

由于顺序表的属性有点多，所以我们要用结构体来实现顺序表。

当我们实现动态顺序表的时候我们要分多个文件来实现。如下图

1594fdd1785540ceb1043213e09e269c.png

3.1 动态顺序表的创建和声明

typedef int SLDataType;  //方便以后修改要存储的数据类型
struct SeqList
{SLDataType* arr;int size;  //有效的数据个数顺序表里面int capacity;  //顺序表的总大小
};
typedef struct SeqList SL;

在一个头文件里面实现动态顺序表的声明。这里我们要将顺序表里面要存储的数据类型重命名为SLDataType,是为了以后方便修改要存储的数据类型，并且也将顺序表重命名为SL，方便后面的操作。

3.2动态顺序表的初始化

在.c源文件实现初始化

void SLInit(SL* sl)
{sl->arr = NULL;sl->size = 0;sl->capacity = 0;
}

ec01091d4d25487b99bf074eaf2240bc.png

需要注意的是，我们进行传参的时候要将sl的地址传过去。我们知道形参是实参的拷贝，我们对形参的改变是不会影响实参的，不会影响实参，初始化就会失败。所以我们要将sl的地址传过去，通过指针来实现初始化 。

8ffdfe40345e49adba5f2798db992441.png

通过调试，我们发现顺序表初始化成功了。

3.2 销毁动态顺序表

因为后面涉及到扩容等问题，要用到realloc函数，申请空间，完成程序之后我们要将申请的空间还给计算机，我们这里先把顺序表的销毁讲了，方便以后操作。

void SLBreak(SL* sl)
{if (sl->arr){free(sl->arr);}sl->size = 0;sl->capacity = 0;
}

3.3 数据插入

将数据插入顺序表中有两种方法，分别是尾插和头插。

3.3.1 尾插

什么是尾插呢？

尾插就是从顺序表的尾部插入数据。如下图

63fc300e4f8548609e1fb5c35d602782.png

此时的size==4，我们可能就会想到所以只要将ps->arr[size]改为想要插入的之就行了 。写出以下代码

void SLPushBack(SL* sl, SLDataType x)
{sl->arr[sl->size] = x;
}

但事情并没有那么简单。

我们要知道插入数据时，首先要清楚顺序表内有没有足够的空间来存储插入的数据呢？一开始我们已经将顺序表的内存大小设置为0，这时侯肯定是没有空间插入数据的，所以这时候我们要向内存申请空间，并且以后我们要根据实际情况来实现扩容，所以这时候最好的选择是通过realloc函数来申请空间。

接着再来分析，我们要申请多大的空间呢？

一搬来说，是原来capacity的两倍或者三倍是最好的的选择。

但原来的capacity为0，所以这时候要用上三目操作符。

尾插代码如下

void SLPushBack(SL* sl, SLDataType x)
{assert(sl);if (sl->size == sl->capacity){//实现扩容int SLNewCapacity = sl->capacity == 0 ? 4 : 2 * sl->capacity;SLDataType* tmp =(SLDataType*) realloc(sl->arr, SLNewCapacity * sizeof(SLDataType));//判断空间是否申请成功if (tmp==NULL){perror("realloc fail");exit(1);}//代码运行到这里，空间就申请成功了sl->arr = tmp;sl->capacity = SLNewCapacity;}sl->arr[sl->size] = x;sl->size++;
}

易错点：扩容那里后面是两个==。

 我们需要注意的是我们申请空间成功时返回的地址不能直接传给原来顺序表的数组，因为申请空间会存在失败的情况，空间申请失败就会退出程序，并销毁该空间了。假设我们之前的顺序表已经存有数据，但因为空间申请失败也把原来的空间释放掉，那么原来的数据也没了，这就功亏一篑了，所以我们要设计一个中间变量存储申请空间返回的地址，有这个中间变量来判断空间是否申请成功。

由于我们插入了数据，不要忘了让size的个数进行增加。

3.3.2 头插

什么是头插呢？

头插就是从顺序表的头部插入一个数据。

下面来分析一下如何实现头插。

59731d29ed6244f49c61eaa16f847859.png

假设上图是我们要进行头插的一个数组？

我们要将一个数据插入1的位置，那么我们就要将原有的数据向后移一位。如下图

2a69ca80fd8e4aaab72e8a5a79e65afa.png

既然插入数据，我们就涉及到空间申请了，这里的空间申请于尾插的一莫一样，既然一样，那我们干脆把空间申请的那部分代码单独写为一个函数，需要的时候调用这个函数就行了。

空间申请的代码如下

void SLSpace(SL* sl)
{assert(sl);if (sl->size == sl->capacity){//实现扩容int SLNewCapacity = sl->capacity == 0 ? 4 : 2 * sl->capacity;SLDataType* tmp = (SLDataType*)realloc(sl->arr, SLNewCapacity * sizeof(SLDataType));if (tmp == NULL){perror("realloc fail");exit(1);}//代码运行到这里，空间就申请成功了sl->arr = tmp;sl->capacity = SLNewCapacity;}
}

尾插代码

void SLPushHead(SL* sl, SLDataType x)
{assert(sl);//调用空间申请函数SLSpace(sl);//实现顺序表原数据向后移1位for (int i = sl->size; i > 0; i--){sl->arr[i] = sl->arr[i - 1];//arr[1]=arr[0]}sl->arr[0] = x;sl->size++;
}

运行效果如下图，头插的数据为5。

4b6c1f2b18a745ffb76c090d28b52099.png

3.4.数据删除

既然有数据的插入，那么就有数据的删除。删除我们也分为尾删和头删的两种。

3.4.1 尾删

什么是尾删？

尾删就是将顺序表里面的的最后一个元素删除掉。

465d00ffed8f4f8389eb8f20bb27e750.png

如上图，尾删将4给除掉了。

代码实现

void SLPopBack(SL* sl)
{assert(sl);assert(sl->size);  //检测顺序表不为空sl->size--;
}

尾删我们直接让size（ 顺序表中的有效个数）减减就行了。我们没必要将要尾删的数据改为其他，我们只要求尾删的操作不影响后面的增删查改的操作就行了。

运行效果

c4d2832165374ad595bdc6f56d295d42.png

3.4.2 头删

什么是头删呢？

头删就是将顺序表的第一个元素删除掉 。

eb4632f13a9b4a068f8da951c8fb4764.png

头删如上图所示，也就是将第一个元素除外其他元素向前移动一位。

代码实现 

void SLPopHead(SL* sl)
{assert(sl);assert(sl->size);//实现数据向前移动一位for (int i = 0; i<sl->size-1; i++){sl->arr[i] = sl->arr[i + 1];  //arr[2]=arr[3]}sl->size--;
}

运行效果

30b1ec68d75a449db11afb822975d488.png

3.5 在指定位置插入数据

分析如何实现？

思路：将指定位置的数据及以从后向前的顺序向后移动一位。

如下图

4cd8c68bfc26492596a41558b1a42245.png

代码实现

 

void SLPopPos(SL* sl, int pos, SLDataType x)
{assert(sl);assert(sl->size && pos <= sl->size);//插入数据之前要申请空间SLSpace(sl);for (int i = sl->size; i > pos; i--){sl->arr[i] = sl->arr[i - 1];}sl->arr[pos] = x;sl->size++;
}

运行效果

31b8e5fdbb4f44fb9bba6ace53a2b049.png

3.6 在指定位置删除数据

 思路

将指定位置之后的数据向前移动一位。

如下图

195180e0bd55478a92ad80eaaacb2731.png

代码实现

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

运行效果

84665d2439864f168b556732e63dd126.png

3.7 查找数据

代码实现

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

运行效果

a6e21b25e3fe44cfbb2d3e58974795de.png

 这里就结束了对顺序表的介绍

下面给大家列处全部代码

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
int main()
{SL sl;  //创建一个结构体变量SLInit(&sl);SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPrint(sl);SLPushHead(&sl, 5);SLPrint(sl);SLPopBack(&sl);SLPrint(sl);SLPopHead(&sl);SLPrint(sl);SLPushPos(&sl, 1, 3);SLPrint(sl);SLPopPos(&sl, 2);SLPrint(sl);int find = SLFind(&sl, 3);if (find < 0){printf("不存在");}else{printf("数据位于下标为%d",find);}//要在顺序表销毁之前完成增删查改的操作SLBreak(&sl);return 0;
}

SeqList.h

#include <assert.h>
typedef int SLDataType;  //方便以后修改要存储的数据类型
struct SeqList
{SLDataType* arr;int size;int capacity;
};
typedef struct SeqList SL; 
void SLInit(SL* sl);
void SLPrint(SL sl);
void SLBreak(SL* sl);
void SLPushHead(SL* sl, SLDataType x);
void SLPushBack(SL* sl, SLDataType x);
void SLPopBack(SL* sl);
void SLPopHead(SL* sl);
void SLPushPos(SL* sl, int pos, SLDataType x);
void SLPopPos(SL* sl, int pos);
int SLFind(SL* sl, SLDataType x);

Seqlist.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
void SLInit(SL* sl)
{sl->arr = NULL;sl->size = 0;sl->capacity = 0;
}
void SLSpace(SL* sl)
{assert(sl);if (sl->size == sl->capacity){//实现扩容int SLNewCapacity = sl->capacity == 0 ? 4 : 2 * sl->capacity;SLDataType* tmp = (SLDataType*)realloc(sl->arr, SLNewCapacity * sizeof(SLDataType));if (tmp == NULL){perror("realloc fail");exit(1);}//代码运行到这里，空间就申请成功了sl->arr = tmp;sl->capacity = SLNewCapacity;}
}
void SLPrint(SL sl)
{for (int i = 0; i < sl.size; i++){printf("%d ", sl.arr[i]);}printf("\n");
}
void SLBreak(SL* sl)
{if (sl->arr){free(sl->arr);}sl->arr = NULL;sl->size = 0;sl->capacity = 0;
}
void SLPushBack(SL* sl, SLDataType x)
{SLSpace(sl);sl->arr[sl->size] = x;sl->size++;
}
void SLPushHead(SL* sl, SLDataType x)
{assert(sl);//调用空间申请函数SLSpace(sl);//实现顺序表原数据向后移1位for (int i = sl->size; i > 0; i--){sl->arr[i] = sl->arr[i - 1];//arr[1]=arr[0]}sl->arr[0] = x;sl->size++;
}
void SLPopBack(SL* sl)
{assert(sl);assert(sl->size);  //检测顺序表不为空sl->size--;
}
void SLPopHead(SL* sl)
{assert(sl);assert(sl->size);//实现数据向前移动一位for (int i = 0; i<sl->size-1; i++){sl->arr[i] = sl->arr[i + 1];  //arr[2]=arr[3]}sl->size--;
}
void SLPushPos(SL* sl, int pos, SLDataType x)
{assert(sl);assert(sl->size && pos <= sl->size);//插入数据之前要申请空间SLSpace(sl);for (int i = sl->size; i > pos; i--){sl->arr[i] = sl->arr[i - 1];}sl->arr[pos] = x;sl->size++;
}
void SLPopPos(SL* sl, int pos)
{assert(sl&&sl->size);assert(pos && pos < sl->size);for (int i = pos; i<sl->size-1; i++){sl->arr[pos] = sl->arr[pos + 1];}sl->size--;
}
int SLFind(SL* sl, SLDataType x)
{assert(sl);for (int i = 0; i < sl->size; i++){if (sl->arr[i] == x){return i;}}return -1;}

 感谢观看。

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


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

相关文章

单片机入门还能从51开始吗？

单片机入门还能从51开始吗？

选择从51单片机开始入门还是直接学习基于ARM核或RISC核的单片机&#xff0c;取决于学习目标、项目需求以及个人兴趣。每种单片机都有其特定的优势和应用场景&#xff0c;了解它们的特点可以帮助你做出更合适的选择。 首先&#xff0c;我们说一下51单片机的优势&#xff1a; 成熟…
阅读更多...
Vue的虚拟DOM是什么

Vue的虚拟DOM是什么

核心思想 虚拟DOM/Virtual DOM&#xff0c;是数据驱动视图的一种解决方案。核心思想&#xff1a;使用 js对象的形式来表现html的dom结构。 背景 由于现代网络和浏览器的发展&#xff0c;网页的内容也变得很复杂&#xff0c;ajax 诞生让用户可以在不刷新页面的条件下获取到数…
阅读更多...
Spring Boot 学习（3）——Spring Initializr 创建项目问题解决

Spring Boot 学习（3）——Spring Initializr 创建项目问题解决

产生问题的原因&#xff0c;各种的版本都较老&#xff0c;所以导致出现问题。目前暂未打到合适的教程&#xff0c;按老教程学起来先。 小白瞎学&#xff0c;大神勿喷&#xff01; 再次强调环境&#xff1a;maven 3.3.9、jdk 1.8、idea 2017、Spring 4.3.13、Spring Boot 1.5.…
阅读更多...
关键里程碑：自然语言处理的发展历程

关键里程碑：自然语言处理的发展历程

关键里程碑&#xff1a;自然语言处理的发展历程 自然语言处理&#xff08;NLP&#xff09;是计算机科学和人工智能的一个分支&#xff0c;致力于使计算机能够理解和处理人类语言。以下是NLP发展过程中的一些关键里程碑&#xff1a; 1950s & 60s&#xff1a;NLP的基础 1954…
阅读更多...
什么是交叉连接：全面概述

什么是交叉连接：全面概述

交叉连接是数据中心上下文中使用的术语&#xff0c;指的是在两个单独的硬件单元之间建立直接链接所需的物理电缆和连接。这些连接在促进数据中心内各个组件之间的高效和安全通信方面发挥着至关重要的作用。通过在硬件单元之间创建专用网络链接&#xff0c;交叉连接消除了对基于…
阅读更多...
【域适应】基于深度域适应MMD损失的典型四分类任务实现

【域适应】基于深度域适应MMD损失的典型四分类任务实现

关于 MMD &#xff08;maximum mean discrepancy&#xff09;是用来衡量两组数据分布之间相似度的度量。一般地&#xff0c;如果两组数据分布相似&#xff0c;那么MMD 损失就相对较小&#xff0c;说明两组数据/特征处于相似的特征空间中。基于这个想法&#xff0c;对于源域和目…
阅读更多...
Sherlocks/Brutus

Sherlocks/Brutus

Brutus 和上一次做的 Recollection 机器一样&#xff0c;主要学习一下相关的知识&#xff0c;练习一下。按照机器描述&#xff0c;在学习完成后将熟悉 auth.log 和 wtmp 日志 auth.log auth.log 是 Linux 系统中一个重要的日志文件&#xff0c;它记录了所有与用户认证相关的行…
阅读更多...
MobX入门指南:快速上手状态管理库

MobX入门指南:快速上手状态管理库

一、什么是MobX MobX 是一个状态管理库&#xff0c;它可以让你轻松地管理应用程序的状态&#xff0c;并且可以扩展和维护。它使用观察者模式来自动传播你的状态的变化到你的 React 组件。 二、安装及配置 安装 MobX 和 MobX-React&#xff1a;你可以使用 npm 或 yarn 安装这…
阅读更多...
最新文章

Copyright @ 2022~2023