当前位置： 首页 > news >正文

数据结构——考研笔记（二）线性表的定义和线性表之顺序表

news 2025/7/10 3:31:09

文章目录

    • 二、线性表
      • 2.1 定义、基本操作
        • 2.1.1 知识总览
        • 2.1.2 线性表的定义
        • 2.1.3 线性表的基本操作
        • 2.1.4 知识回顾与重要考点
      • 2.2 顺序表
        • 2.2.1 知识总览
        • 2.2.2 顺序表的定义
        • 2.2.3 顺序表的实现——静态分配
        • 2.2.4 顺序表的实现——动态分配
        • 2.2.5 知识回顾与重要考点
        • 2.2.6 顺序表的插入和删除
          • 2.2.6.1 插入
          • 2.2.6.2 插入操作的时间复杂度
          • 2.2.6.3 删除
          • 2.2.6.4 删除操作的时间复杂度
          • 2.2.6.5 知识回顾与重要考点
        • 2.2.7 顺序表的查找
          • 2.2.7.1 按位查找
          • 2.2.7.2 按值查找
          • 2.2.7.3 知识回顾与重要考点

二、线性表

2.1 定义、基本操作

2.1.1 知识总览

image-20240712133857838

  • 线性表：
    1. 定义（逻辑结构）
    2. 基本操作（运算）
2.1.2 线性表的定义

线性表：线性表是具有相同数据类型的n（n$>=$0）个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则其一般表示为

image-20240712134643909

以下是几个概念

  1. ai是线性表中的“第i个”元素线性表中的位序
  2. a1是表头元素；an是表尾元素
  3. 除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继
2.1.3 线性表的基本操作
  • InitList(&L)：初始化表。构造一个空的线性表L，分配内存空间。
  • DestoryList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间
  • ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e
  • ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值
  • LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。
  • GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。

其他常用操作

  • Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数。
  • PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。
  • Empty(L)：判空操作。若L位空表，则返回true，否则返回false。

Tips：

  1. 对数据的操作（记忆思路）——创销、增删改查
  2. C语言函数的定义—— <返回值类型> 函数名(<参数1类型>参数1，<参数2类型>参数2，……)
  3. 实际开发中，可根据实际需求定义其他的基本操作
  4. 函数名和参数的形式、命名都可改变（命名要有可读性）
  5. 什么时候要传入“&”——对参数的修改结果需要“带回来”

image-20240713193937792

为什么要实现对数据结构的基本操作》

  1. 团队合作编程，你定义的数据结构要让别人能够很方便的使用（封装）
  2. 将常用的操作/运算封装成函数，避免重复工作，降低出错风险
2.1.4 知识回顾与重要考点

image-20240713194422400

2.2 顺序表

2.2.1 知识总览

image-20240713194628446

2.2.2 顺序表的定义

image-20240713195014881

顺序表：用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

2.2.3 顺序表的实现——静态分配
#define MaxSize 10			//定义最大长度
typeof struct{ElemType data[MaxSize];	//用静态的“数组”存放数据元素int length;			   //顺序表的当前长度
}SqList;				  //顺序表的类型定义（静态分配方式）

image-20240713200229686

上述代码中给各个数据元素分配连续的存储空间，大小位MaxSize*sizeof(ElemType)

image-20240713202046731

  • 代码实现

    #include <stdio.h>
#define MaxSize 10	//定义最大长度typedef struct {int data[MaxSize];	//用静态的“数组”存放数据元素int length;		//顺序表的当前长度
}SqList;			//顺序表的类型定义//基本操作——初始化一个顺序表
void InitList(SqList& L) {for (int i = 0; i < MaxSize; i++)L.data[i] = 0;	//将所有数据元素设置位默认初始值L.length = 0;		//顺序表初始长度为0
}int main() {SqList L;	//声明一个顺序表InitList(L);//初始化顺序表//……未完待续，后续操作return 0;
}

如果“数组”存满了怎么办？

可以放弃治疗，顺序表的表长刚开始确定后就无法更改（存储空间是静态的）

思考：如果刚开始就声明一个很大的内存空间呢？存在什么问题？

2.2.4 顺序表的实现——动态分配

image-20240713202736316

Key：动态申请和释放内存空间

C —— malloc、free函数

malloc函数返回一个指针，需要强制转型为你定义数据元素类型指针

eg：L.data = (ElemType *)malloc(sizeof(ElemType)*InitSize)

表示要申请的一整片连续的内存空间

C++ —— new、delete关键字

image-20240713205744540

  • 代码实现
#include <stdlib.h>
#define InitSize 10	//默认的最大长度typedef struct {int* data;		//指示动态分配数组的指针int MaxSize;	//顺序表的最大容量int length;		//顺序表的当前长度
}SeqList;void InitList(SeqList& L) {//用malloc函数申请一片连续的内存空间L.data = (int*)malloc(InitSize * sizeof(int));L.length = 0;L.MaxSize = InitSize;
}//增加动态数组的长度
void IncreaseSize(SeqList& L, int len) {int* p = L.data;L.data = (int*)malloc((L.MaxSize + len) * sizeof(int));for (int i = 0; i < L.length; i++) {L.data[i] = p[i];	//将数据复制到新区域}L.MaxSize = L.MaxSize + len;	//顺序表最大长度增加lenfree(p);				//释放原来的内存空间
}int main() {SeqList L;		//声明一个顺序表InitList(L);	//初始化顺序表//……往顺序表中随便插入几个元素……IncreaseSize(L, 5);return 0;
}

顺序表的特点：

  1. 随机访问，即可以在O(1)时间内找到第i个元素。（代码实现：data[i-1]）
  2. 存储密度高，每个节点只存储数据元素。
  3. 拓展容量不方便（即便采用动态分配的方式实现。拓展长度的时间复杂度也比较高）
  4. 插入、删除操作不方便，需要移动大量元素。
2.2.5 知识回顾与重要考点

image-20240713210235135

2.2.6 顺序表的插入和删除

image-20240713210450311

2.2.6.1 插入

image-20240713210621170

ListInsert(&L,i,e)：插入操作。在表L中的第i个位置插入指定元素e。

  • 代码实现
#include <stdio.h>
#define MaxSize 10	//定义最大长度typedef struct {int data[MaxSize];	//用静态的“数组”存放数据元素int length;		//顺序表的当前长度
}SqList;			//顺序表的类型定义//基本操作——初始化一个顺序表
void InitList(SqList& L) {for (int i = 0; i < MaxSize; i++)L.data[i] = 0;	//将所有数据元素设置位默认初始值L.length = 0;		//顺序表初始长度为0
}
//插入
bool ListInsert(SqList& L, int i, int e) {if (i<1 || i>L.length + 1)	//判断i的范围是否有效return false;if (L.length >= MaxSize)	//当前存储空间已满，不能插入return false;for (int j = L.length; j >= i; j--) {L.data[j] = L.data[j - 1];	//将第i个元素及之后的元素后移}L.data[i - 1] = e;		//在位置i出放入eL.length++;				//长度加1return true;
}int main() {SqList L;	//声明一个顺序表InitList(L);//初始化顺序表//……此处省略一些代码，插入几个元素ListInsert(L, 3, 3);printf("data[2]=%d", L.data[2]);return 0;
}
2.2.6.2 插入操作的时间复杂度

image-20240713212517218

2.2.6.3 删除

ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。

image-20240713213854316

  • 代码实现
#include <stdio.h>
#define MaxSize 10	//定义最大长度typedef struct {int data[MaxSize];	//用静态的“数组”存放数据元素int length;		//顺序表的当前长度
}SqList;			//顺序表的类型定义//基本操作——初始化一个顺序表
void InitList(SqList& L) {for (int i = 0; i < MaxSize; i++)L.data[i] = 0;	//将所有数据元素设置位默认初始值L.length = 0;		//顺序表初始长度为0
}
//插入
bool ListInsert(SqList& L, int i, int e) {if (i<1 || i>L.length + 1)	//判断i的范围是否有效return false;if (L.length >= MaxSize)	//当前存储空间已满，不能插入return false;for (int j = L.length; j >= i; j--) {L.data[j] = L.data[j - 1];	//将第i个元素及之后的元素后移}L.data[i - 1] = e;		//在位置i出放入eL.length++;				//长度加1return true;
}
//删除
bool ListDelete(SqList& L, int i, int& e) {if (i<1 || i>L.length)		//判断i的范围是否有效return false;e = L.data[i - 1];			//将被删除的元素赋值给efor (int j = i; j < L.length; j++) {L.data[j - 1] = L.data[j];	//将第i个位置后的元素前移}L.length--;		//线性表长度减1return true;
}
int main() {SqList L;	//声明一个顺序表InitList(L);//初始化顺序表//……此处省略一些代码，插入几个元素ListInsert(L, 3, 3);int e = -1;	//用变量e把删除的元素“带回来”if (ListDelete(L, 3, e))printf("已删除第3个元素，删除元素为=%d\n", e);elseprintf("位序i不合法，删除失败\n");return 0;
}
2.2.6.4 删除操作的时间复杂度

image-20240713214236102

2.2.6.5 知识回顾与重要考点

image-20240713214339687

2.2.7 顺序表的查找

image-20240713214626035

2.2.7.1 按位查找
  • 静态分配实现按位查找

image-20240713214804963

  • 动态分配实现按位查找

image-20240713214848940

  • 按位查找的时间复杂度

image-20240713215136821

2.2.7.2 按值查找

LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。

image-20240713215403694

注意：数组下标为i的元素值等于e，返回其位序i+1

  • 代码实现
#include <stdio.h>
#define MaxSize 10	//定义最大长度typedef struct {int data[MaxSize];	//用静态的“数组”存放数据元素int length;		//顺序表的当前长度
}SqList;			//顺序表的类型定义//基本操作——初始化一个顺序表
void InitList(SqList& L) {for (int i = 0; i < MaxSize; i++)L.data[i] = 0;	//将所有数据元素设置位默认初始值L.length = 0;		//顺序表初始长度为0
}
//插入
bool ListInsert(SqList& L, int i, int e) {if (i<1 || i>L.length + 1)	//判断i的范围是否有效return false;if (L.length >= MaxSize)	//当前存储空间已满，不能插入return false;for (int j = L.length; j >= i; j--) {L.data[j] = L.data[j - 1];	//将第i个元素及之后的元素后移}L.data[i - 1] = e;		//在位置i出放入eL.length++;				//长度加1return true;
}
//删除
bool ListDelete(SqList& L, int i, int& e) {if (i<1 || i>L.length)		//判断i的范围是否有效return false;e = L.data[i - 1];			//将被删除的元素赋值给efor (int j = i; j < L.length; j++) {L.data[j - 1] = L.data[j];	//将第i个位置后的元素前移}L.length--;		//线性表长度减1return true;
}
//在顺序表L中查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SqList L, int e) {for (int i = 0; i < L.length; i++) {if (L.data[i] == e)return i + 1;}return 0;
}
int main() {SqList L;	//声明一个顺序表InitList(L);//初始化顺序表//……此处省略一些代码，插入几个元素ListInsert(L, 3, 3);int i = LocateElem(L, 3);printf("位序为%d", i);return 0;
}
  • 按值查找的时间复杂度

image-20240713220415874

2.2.7.3 知识回顾与重要考点

image-20240713220505150

http://www.lryc.cn/news/399517.html

相关文章：

  • quota使用
  • 解决fidder小黑怪倒出JMeter文件缺失域名、请求头
  • 智慧城市的神经网络：Transformer模型在智能城市构建中的应用
  • 产品经理-研发流程-敏捷开发-迭代-需求评审及产品规划（15）
  • Ansible 安装及使用说明
  • MyBatisPlus实现增删改查
  • 【Rust】——不安全Rust
  • 使机器人在执行任务时更加稳定
  • FFmpeg学习（五）-- libswresample使用说明及函数介绍
  • 车载视频监控管理方案：无人驾驶出租车安全出行的保障
  • 05STM32EXIT外部中断中断系统
  • MetaGPT和LangGraph对比
  • 基于SpringBoot+Hadoop+python的物品租赁系统(带1w+文档)
  • 关于 RK3588刷镜像升级镜像”没有发现设备“ 的解决方法
  • docker 上传镜像到hub仓库
  • 查询(q_proj)、键(k_proj)和值(v_proj)投影具体含义
  • 超详细版阿里云控制台环境配置+数据库配置
  • Linux：Linux网络总结(附下载链接)
  • Cxx Primer-CP-2
  • OpenCV距离变换函数distanceTransform的使用
  • Service Mesh 是一种用于处理服务间通信的基础设施层
  • QML界面控件加载与显示顺序
  • C++从入门到起飞之——缺省参数/函数重载/引用全方位剖析！
  • tkinter-TinUI-xml实战（12）pip可视化管理器
  • Java中标识符和关键字
  • 电子版pdf格式标书怎么加盖公章？
  • 【开放集目标检测】Grounding DINO
  • 东莞酷得 PMS134应广8位OTP单片机
  • [终端安全]-7 后量子密码算法
  • uniapp 支付宝小程序 芝麻免押 免押金