【数据结构】之线性表（顺序存储结构）

article/2025/9/23 6:05:41

博主声明：

转载请在开头附加本文链接及作者信息，并标记为转载。本文由博主 威威喵 原创，请多支持与指教。

本文首发于此   博主：威威喵  |  博客主页：https://blog.csdn.net/smile_running

    线性表是《数据结构》课程最开始的一章的内容，是在大学计算机专业必学的课程。我们刚接触线性表时，可能会被它的几种表的结构搞得晕头转向，它有两种基本存储结构：一种是顺序存储结构，另一种是链式存储结构。接下来，我们先来看看线性表的顺序存储结构吧。

    首先，线性表的顺序存储结构用图来表示，它是这样的：

    这张图很直观的说明了线性表的结构，图中元素都是一个挨着一个，表示线性表中（顺序存储结构）数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。顺序存储结构，指的是用一组地址连续的存储单元依次存储线性表的数据元素，称为线性表的顺序存储结构或顺序映像（sequential mapping）。它以“物理位置相邻”来表示线性表中数据元素间的逻辑关系，可随机存取表中任一元素。

    既然它的地址是相邻的，我们就可以通过地址计算公式来计算出某一个元素存在的地址。下面的计算的公式：

    之前考试的时候，在线性表那一章肯定会遇到这样的题目，也是非常简单、基础的一道题，套公式就可以很快的计算出来。题目是这样的：某线性表采用顺序存储结构，每个元素占 4 个存储单元，首地址为 100，则第 12 个元素的 存储地址为（ ）？

    这题直接套用上面的公式： 100 + （12 - 1）* 4 = 144，所以此题的答案是：144。好了，其他就不做多的介绍了，我们直接看代码吧。

一、数组实现方式

    线性表的数据结构，其中 MAX 表示线性表的数组元素个数，就是线性表的最大容量，length 表示线性表当前的长度。这里有一个必要条件，就是 length <= MAX

#define MAX 20
typedef int ElemType;
typedef struct
{ElemType data[MAX];	int length;
}SqList;

初始化线性表，即使线性表的长度为 0

/** 初始化线性表 **/
void InitList(SqList *L)
{L->length = 0;
}

 获取线性表中的元素值，传入的是线性表中元素的位置（下标）

/** 获取元素 **/
int Get(SqList L, ElemType *e, int i)
{if(L.length ==0 || i<1 || i>L.length)return -1;*e = L.data[i-1];return *e;
}

向表中插入数据

/** 插入元素 **/
int Insert(SqList *L, ElemType e, int i)
{int j;if(L->length == MAX)return -1;if(i<1 || i>L->length+1)return -1;if(i<= L->length){	for(j=L->length; j>i-1; j--){L->data[j] = L->data[j-1];}}L->data[i-1] = e;L->length++;return 1;
}

删除线性表中指定位置的元素

/** 删除指定下标的元素 **/
int Delete(SqList *L,int i)
{int j;if(L->length == 0)return -1;if(i<1 || i>L->length +1)return -1;if(i<L->length){for(j=i; j<L->length; j++){L->data[j-1] = L->data[j];}}L->length--;return 1;
}

获取当前表的长度

/** 线性表的长度 **/
int Length(SqList *L)
{return L->length;
}

清除线性表

/** 清除线性表 **/
void Clear(SqList *L)
{L->length = 0;
}

打印表中的元素

/** 打印线性表 **/
void PrintList(SqList *L)
{int i;for(i=0; i<L->length; i++){printf("%d ",L->data[i]);}printf("\n");
}

最后，写一个 main() 方法来测试一下线性表的元素获取、插入、删除等操作。以下是完整的代码：

#include <stdio.h>/*** 数据结构 - 线性表的顺序存储* 博客：https://vvcat.blog.csdn.net/**/
#define MAX 20
typedef int ElemType;
typedef struct
{ElemType data[MAX];	int length;
}SqList;/** 初始化线性表 **/
void InitList(SqList *L)
{L->length = 0;
}/** 获取元素 **/
int Get(SqList L, ElemType *e, int i)
{if(L.length ==0 || i<1 || i>L.length)return -1;*e = L.data[i-1];return *e;
}/** 插入元素 **/
int Insert(SqList *L, ElemType e, int i)
{int j;if(L->length == MAX || i<1 || i>L->length+1)return -1;// 如果插入的位置不在末尾，要移动元素if(i<= L->length){	for(j=L->length; j>i-1; j--){L->data[j] = L->data[j-1];}}L->data[i-1] = e;L->length++;return 1;
}/** 删除指定下标的元素 **/
int Delete(SqList *L,int i)
{int j;if(L->length == 0 || i<1 || i>L->length +1)return -1;// 如果删除位置不在末尾，移动元素if(i<L->length){for(j=i; j<L->length; j++){L->data[j-1] = L->data[j];}}L->length--;return 1;
}/** 清除线性表 **/
void Clear(SqList *L)
{L->length = 0;
}/** 线性表的长度 **/
int Length(SqList *L)
{return L->length;
}/** 打印线性表 **/
void PrintList(SqList *L)
{int i;for(i=0; i<L->length; i++){printf("%d ",L->data[i]);}printf("\n");
}/*** 数据结构 - 线性表的顺序存储* 博客：https://vvcat.blog.csdn.net/* 博主：威威喵**/
void main()
{int i;int status = 0;int arr[10] = {3,7,11,6,5,14,36,9,4,19}; SqList list;ElemType e;InitList(&list);/** 插入 10 个数据 **/for(i=1; i<=10; i++){	Insert(&list, arr[i-1], i);}printf("线性表的顺序存储，长度 = %d \n", Length(&list));PrintList(&list);printf("\n");/** 在位置 5 插入一个数据 **/ Insert(&list, 45, 5);printf("插入元素 45，长度为 = %d \n", Length(&list));PrintList(&list);printf("\n");/** 获取下标为 5 的元素的值 **/printf("获取的元素为 %d \n", Get(list, &e, 5));printf("\n");/** 删除位置 5 的数据 **/ Delete(&list, 5);printf("删除元素 45，长度为 = %d \n", Length(&list));PrintList(&list);printf("\n");/** 清空数据 **/ Clear(&list);printf("清除，长度为 = %d \n", Length(&list));
}

其运行结果为：

二、动态扩容

    线性表的另一种实现方法：动态扩容的线性表，因为上面的数组实现方式，其数组大小是固定的，如果数据添加满了话，再添加数据则会导致数组溢出，不容易进行动态扩容。以下是完整代码如下：

#include <stdio.h>
#include <stdlib.h>/*** 数据结构 - 线性表的顺序存储* 博客：https://vvcat.blog.csdn.net/**/
#define LIST_SIZE 10
#define CAPACITY 5
typedef int ElemType;
typedef struct
{ElemType *data;	int length;int size;
}SqList;/** 动态的初始化线性表 **/
int InitList(SqList *L)
{// 申请分配的内存空间大小L->data = (ElemType *)malloc(sizeof(ElemType) * LIST_SIZE);if(L->data == NULL)return -1;L->length = 0;L->size = LIST_SIZE;return 1;
}/** 获取元素 **/
int Get(SqList L, ElemType *e, int i)
{if(L.length ==0 || i<1 || i>L.size)return -1;*e = L.data[i-1];return *e;
}/** 插入元素 **/
int Insert(SqList *L, ElemType e, int i)
{ElemType *p = NULL;ElemType *q = NULL;if(i<1 || i>L->size)return -1;/** 如果内存空间不足，动态的扩容，每次扩容 CAPACITY 个大小 **/if(L->length == LIST_SIZE){L->data = (ElemType *)realloc(L->data, sizeof(ElemType) * (CAPACITY + LIST_SIZE));L->size += CAPACITY;if(!L->data){printf("扩容失败！");return -1;}}p = &L->data[i-1];//插入的位置for(q=&L->data[L->length-1]; q>=p; q--){*(q+1) = *q;	}*p = e;L->length++;return 1;
}/** 删除指定下标的元素 **/
int Delete(SqList *L, ElemType *e, int i)
{ElemType *p = NULL;ElemType *q = NULL;if(L->length == 0 || i<1 || i>L->size)return -1;p = &L->data[i-1];//删除的位置*e = *p;q = &L->data[L->length-1];while(p<=q){*p = *(p+1);p++;}L->length--;return 1;
}/** 清除线性表 **/
void Clear(SqList *L)
{while(!L->data){free(L->data);}L->length = 0;L->size = 0;
}/** 判断是否为空表 **/
int Empty(SqList *L)
{if(L->length == 0)return -1;elsereturn 1;
}/** 线性表的长度 **/
int Length(SqList *L)
{return L->length;
}/** 线性表的大小 **/
int Size(SqList *L)
{return L->size;
}/** 打印线性表 **/
void PrintList(SqList *L)
{int i;for(i=0; i<L->length; i++){printf("%d ",L->data[i]);}printf("\n");
}/*** 数据结构 - 线性表的顺序存储* 博客：https://vvcat.blog.csdn.net/* 博主：威威喵**/
void main()
{int i;int status = 0;int arr[10] = {3,7,11,6,5,14,36,9,4,19}; SqList list;ElemType e;InitList(&list);/** 插入 10 个数据 **/for(i=1; i<=10; i++){	Insert(&list, arr[i-1], i);}printf("线性表的顺序存储，Length = %d \n", Length(&list));printf("线性表的顺序存储，Size = %d \n", Size(&list));PrintList(&list);printf("\n");/** 在位置 5 插入一个数据 **/ Insert(&list, 45, 5);Insert(&list, 95, 9);printf("插入元素 45、95，长度为 = %d \n", Length(&list));printf("线性表的顺序存储，Size = %d \n", Size(&list));PrintList(&list);printf("\n");/** 获取下标为 5 的元素的值 **/printf("获取的元素为 %d \n", Get(list, &e, 5));printf("\n");/** 删除位置 5 的数据 **/ Delete(&list, &e, 5);printf("删除元素 45，长度为 = %d \n", Length(&list));printf("线性表的顺序存储，Size = %d \n", Size(&list));PrintList(&list);printf("\n");/** 清空数据 **/ Clear(&list);printf("清除，长度为 = %d \n", Length(&list));printf("线性表的顺序存储，Size = %d \n", Size(&list));
}

以上代码的运行结果：

     线性表的动态扩容，就如上面的例子，刚开始添加了 10 个元素，线性表已经满了，然后每次扩容的个数是 5 个，所以再次插入数据时，会以每 5 个空间大小进行扩容操作。

三、学生信息表

    以下代码是我个人写的一个练手的线性表顺序存储结构的案例，主要是通过输入学生的用户信息（包括学号、姓名），然后使用线性表来保存起来。

学生信息数据结构与学生表的数据结构如下：

/** 学生信息的数据结构 **/
typedef struct
{char number[20]; // 学号char name[30]; // 姓名
}Student;/** 学生表的数据结构 **/
typedef struct
{Student student[MAXSIZE];int length;
}SqList;

这里，我使用的是数组的方式，没用动态扩容，其中定义了 MAXSIZE 为 20 个，用于保存学生信息。完整代码如下：

#include <stdio.h>#define MAXSIZE 20 // 定义存储学生信息的最大容量
#define OK 1;
#define ERROR -1;
typedef int Status;/*** 数据结构 - 线性表的顺序存储* 博客：https://vvcat.blog.csdn.net/**/
/** 学生信息的数据结构 **/
typedef struct
{char number[20]; // 学号char name[30]; // 姓名
}Student;/** 学生表的数据结构 **/
typedef struct
{Student student[MAXSIZE];int length;
}SqList;/** 初始化 **/
void Init(SqList *L)
{L->length = 0;
}/** 插入学生信息 **/
Status Insert(SqList *L, Student stu, int i)
{int k;if(L->length == MAXSIZE){printf("插入失败，表溢出! \n");return ERROR;}if(i<1 || i>L->length+1)// 下标从 0 开始{printf("插入失败，下标异常! \n");return ERROR;}/** 如果插入位置不在表尾，移动表中元素 **/if(i <= L->length){for(k=L->length; k>=i-1; k--){L->student[k] = L->student[k-1];}}L->student[i-1] = stu;L->length++;//	printf("插入的数据为：学号：%s 姓名：%s \n", stu.number, stu.name);printf("插入成功! \n");return OK;
}/** 删除学生信息 **/
Status Delete(SqList *L, int i)
{int k;if(L->length == 0){printf("表中空数据! \n");return ERROR;}if(i<1 || i>L->length+1){printf("删除失败，下标异常! \n");return ERROR;}if(i <= L->length){for(k=i-1; k<=L->length; k++){L->student[k] = L->student[k+1];}}printf("删除成功! \n");L->length--;return OK;
}/** 获取学生信息 **/
Student Get(SqList *L, int i)
{if(L->length == 0){printf("空表! \n");}else if(i<1 || i>L->length){printf("下标异常! \n");}else{return  L->student[i-1];}
}int Length(SqList *L)
{return L->length;
}/** 打印表 **/
void Print(SqList *L)
{int i;for(i=0; i<L->length; i++){printf("学号：%s 姓名：%s \n", L->student[i].number, L->student[i].name);}
}void main()
{int i=1;int n;SqList sqList;Student stu, stu2, stu3;printf("请输入学生的人数：");scanf("%d", &n);/** 初始化 **/Init(&sqList);while(i<=n){printf("学号：");scanf("%s", stu.number);printf("姓名：");scanf("%s", stu.name);Insert(&sqList, stu, i);i++;}Print(&sqList);/** 插入数据 **/printf("插入学号：");scanf("%s", stu2.number);printf("插入姓名：");scanf("%s", stu2.name);Insert(&sqList, stu2, 2);Print(&sqList);/** 删除数据 **/Delete(&sqList, 2);Print(&sqList);/** 获取数据 **/stu3 = Get(&sqList, 1);printf("学号：%s \n", stu3.number);printf("姓名：%s \n", stu3.name);
}

当然了，你也可以改为动态扩容的方式。好了，下面是案例运行结果：


http://chatgpt.dhexx.cn/article/J1WuDIT7.shtml

相关文章

线性表顺序存储结构的基本实现

线性表顺序存储结构的基本实现

在上一篇博客中我们只是简单得了解了线性表的一些基本的概念。那么这一篇博客我们就来说说线性表的两种物理结构中的第一种—顺序存储结构。 一、顺序存储定义 线性表的顺序存储结构指的是用一段地址连续的存储单元依次线性表的数据元素。顺序存储的示意图如下&#xff1a; 二…
阅读更多...
线性表之顺序存储结构与链式存储结构 及 应用

线性表之顺序存储结构与链式存储结构 及 应用

前言 我们常用的线性表是顺序存储结构和链式存储结构表示&#xff0c;是最基本、最简单、也是最常用的一种数据结构&#xff1b;一个线性表是由n个相同特性的数据的有限序列&#xff1b;比如java中的数组 &#xff0c;链表&#xff1b;所以学习这两种结构表示是非常必要的。 …
阅读更多...
线性表的顺序存储结构及实现

线性表的顺序存储结构及实现

线性表的顺序存储结构定义 一、线性表的介绍 线性表是最基本、最简单、也是最常用的一种数据结构。 线性表中数据元素之间的关系是一对一的关系&#xff0c;即除了第一个和最后一个数据元素之外&#xff0c;其它数据元素都是首尾相接的(注意&#xff0c;这句话只适用大部分线…
阅读更多...
线性表顺序存储结构图书管理

线性表顺序存储结构图书管理

线性表顺序存储结构图书管理 一开始看书里面的线性表的顺序存储结构&#xff0c;感觉简单&#xff0c;觉得动态链表才能做出一点东西&#xff0c;但是顺序存储不仅于此&#xff0c;也能做出来。顺序结构相比链式结构&#xff0c;内容上有较大差异&#xff0c;各有难点 文章目录…
阅读更多...
C++实现线性表的顺序存储结构

C++实现线性表的顺序存储结构

C实现线性表的顺序存储结构 线性表是最基本、最简单、也是最常用的一种数据结构。线性表&#xff08;linear list&#xff09;是数据结构的一种&#xff0c;一个线性表是n个具有相同特性的数据元素的有限序列。 线性表的特点 除第一个元素外&#xff0c;其他每一个元素有且仅有…
阅读更多...
顺序表（详解）- C++（线性表顺序存储结构）

顺序表（详解）- C++（线性表顺序存储结构）

问题引入 在数据结构中&#xff0c;线性表是一种很重要的线性结构。线性表分为多种类型&#xff0c;常见的如顺序表、链表等&#xff0c;如果此时此刻你对“顺序表&#xff08;顺序存储&#xff09;”感到困惑&#xff0c;那就继续看下去&#xff0c;我们一步一步去剖析。 如果…
阅读更多...
顺序存储结构的线性表

顺序存储结构的线性表

1.0. 什么是线性表&#xff1f; 所谓线性&#xff0c;即一条线&#xff0c;这条线可以是直线&#xff0c;也可以是曲线。 所谓表&#xff0c;肯定都不陌生&#xff0c;生活中有各种各样的表或者表格。我们在表格中填写各种各样的信息&#xff0c;通过表格&#xff0c;能够很好…
阅读更多...
数据结构线性表顺序存储结构和主要算法实现

数据结构线性表顺序存储结构和主要算法实现

(1) 线性表的定义。 零个或多个数据元素的有限序列 序列线性表中有直接后继元素&#xff0c;有且仅有一个直接后继&#xff0c;有且仅有一个直接前驱&#xff0c;数据元素之间的关系是一对一的关系 常用的List操作&#xff1a; Operation InitList&#xff08;*L&#xf…
阅读更多...
线性表顺序存储结构

线性表顺序存储结构

1.什么是线性表? 线性表可以看作一条链子除了第一个元素和最后一个元素&#xff0c;其他每个元素都有一个前驱 元素和一个后继元素有且只有一个。 若一个元素都没有&#xff0c;则称为空表。 元素之间的关系是一一对应的关系。(就比如a2的前驱元素只有一个并且一定是a1&#…
阅读更多...
线性表的顺序存储结构

线性表的顺序存储结构

线性表的基本概念 线性结构习惯称为线性表&#xff0c;线性表是n(n>0)个数据元素构成的有限序列&#xff0c;表中除第一个元素外的每一个元素&#xff0c;有且只有一个一个前件&#xff1b;除最后一个元素外&#xff0c;有且只有一个后件。 非空数据表具有&#xff1a; 只…
阅读更多...
【数据结构】线性表的顺序存储结构及实现——C语言版

【数据结构】线性表的顺序存储结构及实现——C语言版

文章目录 顺序表1. 顺序表的存储结构定义2. 顺序表的实现2.1 初始化顺序表2.2 建立顺序表2.3 销毁顺序表2.4 判空操作2.5 求顺序表的长度2.6 遍历操作2.7 按值查找2.8 按位查找2.9 插入操作2.10 删除操作 3. 顺序表的使用4. 暖暖树洞 顺序表 线性表的顺序存储结构称为顺序表&a…
阅读更多...
VUE activated,deactivated使用

VUE activated,deactivated使用

项目中keepalive用得不多&#xff0c;记录一下以免遗忘。 页面第一次进入&#xff0c;钩子的触发顺序created-> mounted-> activated&#xff0c;退出时触发deactivated。当再次进入&#xff08;前进或者后退&#xff09;时&#xff0c;只触发activated。 事件挂载的方…
阅读更多...
vue activated，deactivated生命周期的使用

vue activated，deactivated生命周期的使用

1.当组件在 内被切换&#xff0c;它的 activated 和 deactivated 这两个生命周期钩子函数将会被对应执行。 2.activated()&#xff1a;在vue对象存活的情况下&#xff0c;进入当前存在activated()函数的页面时&#xff0c;一进入页面就触发&#xff1b;可用于初始化页面数据等…
阅读更多...
vue 中 keep-alive，activated，deactivated

vue 中 keep-alive，activated，deactivated

keep-alive 在组件反复切换时&#xff0c;会反复渲染&#xff0c;造成性能问题。用一个 <keep-alive></keep-alive> 标签将他包裹起来&#xff0c;组件会在第一次被创建的时候缓存下来。避免性能问题。 首先准备好组件&#xff0c;配置好路由。准备了Home,Keep,Abo…
阅读更多...
【Vue】学习笔记-Vue Router activated deactivated 路由守卫

【Vue】学习笔记-Vue Router activated deactivated 路由守卫

Vue Router activated deactivated 路由守卫 activated deactivated路由守卫1.全局守卫2.独享守卫3.组件内守卫全局路由守卫路由器的两种工作模式 activated deactivated activated 和 deactivated 是路由组件所独有的两个钩子&#xff0c;用于捕获路由组件的激活状态 具体使用…
阅读更多...
vue 生命周期图 + activated + deactivated

vue 生命周期图 + activated + deactivated

一、vue 生命周期图 From the network 二、activated deactivated 除此之外&#xff0c;简单介绍一下在被keep-alive包含的组件/路由中&#xff0c;会多出两个生命周期的钩子:activated 与 deactivated。在 2.2.0 及其更高版本中&#xff0c;activated 和 deactivated 将会…
阅读更多...
[Vue]缓存路由组件 activated()与deactivated()

[Vue]缓存路由组件 activated()与deactivated()

前言 系列文章目录&#xff1a; [Vue]目录 老师的课件笔记&#xff0c;不含视频 https://www.aliyundrive.com/s/B8sDe5u56BU 笔记在线版&#xff1a; https://note.youdao.com/s/5vP46EPC 视频&#xff1a;尚硅谷Vue2.0Vue3.0全套教程丨vuejs从入门到精通 文章目录 前言1. 缓存…
阅读更多...
Vue 钩子函数activated未触发

Vue 钩子函数activated未触发

activated()和deactivated()只有在<keep-alive></keep-alive>包裹的时候才有效&#xff1b;
阅读更多...
搞明白activated和deactivated

搞明白activated和deactivated

文章目录 写到前面什么是activatedactivated解决了一个什么问题Demomain.vueassembly1(组件1)assembly2(组件2) 执行结果要点速记个人建议写到最后 写到前面 今天简单的将activated讲一下&#xff0c;前面有人问了&#xff0c;既然有问的&#xff0c;说明还有人不是很明白的&am…
阅读更多...
vue中activated

vue中activated

keep-alive <keep-alive>包裹动态组件的时候&#xff0c;会缓存不活动的组件实例&#xff0c;而不是摧毁他们。其是一个抽象的组件&#xff0c;自身不会渲染一个DOM元素&#xff0c;也不会出现在父组件链中。 说白了被<keep-alive>包裹的组件其会被缓存。 没有被…
阅读更多...
推荐文章

Copyright @ 2022~2023