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

文章目录

    • 二、线性表
      • 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;	//顺序表最大长度增加len
	free(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出放入e
	L.length++;				//长度加1
	return 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出放入e
	L.length++;				//长度加1
	return true;
}
//删除
bool ListDelete(SqList& L, int i, int& e) {
	if (i<1 || i>L.length)		//判断i的范围是否有效
		return false;
	e = L.data[i - 1];			//将被删除的元素赋值给e
	for (int j = i; j < L.length; j++) {
		L.data[j - 1] = L.data[j];	//将第i个位置后的元素前移
	}
	L.length--;		//线性表长度减1
	return 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);
	else
		printf("位序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出放入e
	L.length++;				//长度加1
	return true;
}
//删除
bool ListDelete(SqList& L, int i, int& e) {
	if (i<1 || i>L.length)		//判断i的范围是否有效
		return false;
	e = L.data[i - 1];			//将被删除的元素赋值给e
	for (int j = i; j < L.length; j++) {
		L.data[j - 1] = L.data[j];	//将第i个位置后的元素前移
	}
	L.length--;		//线性表长度减1
	return 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.mfbz.cn/a/797198.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

如何在Linux上如何配置虚拟主机

如何在Linux上如何配置虚拟主机

在Linux上配置虚拟主机可以通过使用Apache HTTP服务器来实现。Apache是一个开源的跨平台的Web服务器软件&#xff0c;可以在多种操作系统上运行并支持虚拟主机的配置。 以下是在Linux上配置虚拟主机的步骤&#xff1a; 安装Apache HTTP服务器 在终端中运行以下命令来安装Apache…
阅读更多...
通过vm可以访问那些属性——06

通过vm可以访问那些属性——06

1.通过vue实例都可以访问那些属性&#xff1f;&#xff08;通过vm都可以vm.什么&#xff09; vue实例中的属性很多。有的以$开始&#xff0c;有的以_开始。 所有以$开始的属性&#xff0c;可以看做是公开的属性&#xff0c;这些属性是提供给程序员使用的 所有以_开始的属性&…
阅读更多...
Linux的世界 -- 初次接触和一些常见的基本指令

Linux的世界 -- 初次接触和一些常见的基本指令

一、Linux的介绍和准备 1、简单介绍下Linux的发展史 1991年10月5日&#xff0c;赫尔辛基大学的一名研究生Linus Benedict Torvalds在一个Usenet新闻组(comp.os.minix&#xff09;中宣布他编制出了一种类似UNIX的小操作系统&#xff0c;叫Linux。新的操作系统是受到另一个UNIX的…
阅读更多...
系统架构设计师教程（清华第2版）＜第2章 计算机系统基础知识＞解读

系统架构设计师教程（清华第2版）＜第2章 计算机系统基础知识＞解读

系统架构设计师教程 第二章 计算机系统基础知识-2.1计算机系统概述 2.2 计算机硬件 2.1 计算机系统概述2.2 计算机硬件2.2.1 计算机硬件组成2.2.2 处理器2.2.2.1 控制单元(CU)2.2.2.2 算术逻辑单元(ALU)2.2.2.3 指令集2.2.2.3.1 CISC的特点2.2.2.3.2 RISC的特点2.2.3 存储器2.2…
阅读更多...
Lottery 分布式抽奖（个人向记录总结）

Lottery 分布式抽奖（个人向记录总结）

1.搭建&#xff08;DDDRPC&#xff09;架构 DDD——微服务架构&#xff08;微服务是对系统拆分的方式&#xff09; &#xff08;Domain-Driven Design 领域驱动设计&#xff09; DDD与MVC同属微服务架构 是由Eric Evans最先提出&#xff0c;目的是对软件所涉及到的领域进行建…
阅读更多...
html（抽奖设计）

html（抽奖设计）

<!DOCTYPE html> <html><head><meta charset"UTF-8"><title>抽奖</title><style type"text/css">* {margin: 0;padding: 0;}.container {width: 800px;height: 800px;border: 1px dashed red;position: absolut…
阅读更多...
【学术会议征稿】第三届智能电网与能源系统国际学术会议

【学术会议征稿】第三届智能电网与能源系统国际学术会议

第三届智能电网与能源系统国际学术会议 2024 3rd International Conference on Smart Grid and Energy Systems 第三届智能电网与能源系统国际学术会议&#xff08;SGES 2024&#xff09;将于2024年10月25日-27日在郑州召开。 智能电网可以优化能源布局&#xff0c;让现有能源…
阅读更多...
C++之多态使用小结

C++之多态使用小结

1、多态定义 1.1 多态概念 C多态性&#xff08;Polymorphism&#xff09;是面向对象编程(OOP)的一个重要特性之一&#xff0c;它允许我们使用统一的接口来处理不同类型的对象。多态性使得程序更加灵活、可扩展并且易于维护。 通俗来说&#xff0c;就是多种形态&#xff0…
阅读更多...
Java小白入门到实战应用教程-开发环境搭建-IDEA2024安装激huo详细教程

Java小白入门到实战应用教程-开发环境搭建-IDEA2024安装激huo详细教程

writer:eleven 安装IDEA2024 一、下载IDEA 推荐大家去官网下载 我这里也给大家直接准备了安装包&#xff0c;和激huo教程&#xff0c;大家可以自行下载使用。 注意&#xff1a;激huo教程只用于学习交流&#xff0c;不可商用。 IDEA2024安装包及激huo教程 说明&#xff1a…
阅读更多...
stm32入门-----初识stm32

stm32入门-----初识stm32

目录 前言 ARM stm32 1.stm32家族 2.stm32的外设资源 3.命名规则 4.系统结构 5.引脚定义 6.启动配置 7.STM32F103C8T6芯片 8.STM32F103C8T6芯片原理图与最小系统电路 前言 已经很久没跟新了&#xff0c;上次发文的时候是好几个月之前了&#xff0c;现在我是想去学习st…
阅读更多...
35 解决单条链路故障问题-华三链路聚合

35 解决单条链路故障问题-华三链路聚合

InLoopBack接口是一种虚拟接口。InLoopBack接口由系统自动创建&#xff0c;用户不能进行配置和删除&#xff0c;但是可以显示&#xff0c;其物理层和链路层协议永远处于up状态。InLoopBack接口主要用于配合实现报文的路由和转发&#xff0c;任何送到InLoopBack接口的IP报文都会…
阅读更多...
zigbee开发工具：3、驱动安装与程序下载（更新中...）

zigbee开发工具：3、驱动安装与程序下载（更新中...）

zigbee开发工具前两篇讲解了IAR开发工具的安装与注册&#xff0c;还介绍了新建一个cc2530开发工程的建立与配置。在进行zigbee开发&#xff0c;代码编写编译好后还需要下载到zigbee节点设备上进行调试与验证&#xff0c;那么就需要安装SmartRF Flash Programmer软件 和仿真器等…
阅读更多...
Vim使用教程

Vim使用教程

目录 引言1. Vim的基本概念1.1 模式1.2 启动和退出 2. 基础操作2.1 导航2.2 插入文本2.3 删除和复制2.4 查找和替换 3. 高级功能3.1 多文件编辑3.2 宏录制和执行3.3 使用插件3.4 自定义快捷键 4. Vim脚本和自定义配置4.1 基本配置4.2 编写Vim脚本 5. 实用技巧5.1 快速移动5.2 批…
阅读更多...
基于复旦微JFMQL100TAI的全国产化FPGA+AI人工智能异构计算平台，兼容XC7Z045-2FFG900I

基于复旦微JFMQL100TAI的全国产化FPGA+AI人工智能异构计算平台，兼容XC7Z045-2FFG900I

基于上海复旦微电子FMQL45T900的全国产化ARM核心板。该核心板将复旦微的FMQL45T900&#xff08;与XILINX的XC7Z045-2FFG900I兼容&#xff09;的最小系统集成在了一个87*117mm的核心板上&#xff0c;可以作为一个核心模块&#xff0c;进行功能性扩展&#xff0c;能够快速的搭建起…
阅读更多...
Golang | Leetcode Golang题解之第233题数字1的个数

Golang | Leetcode Golang题解之第233题数字1的个数

题目&#xff1a; 题解&#xff1a; func countDigitOne(n int) (ans int) {// mulk 表示 10^k// 在下面的代码中&#xff0c;可以发现 k 并没有被直接使用到&#xff08;都是使用 10^k&#xff09;// 但为了让代码看起来更加直观&#xff0c;这里保留了 kfor k, mulk : 0, 1;…
阅读更多...
Dify中的weaviate向量数据库操作

Dify中的weaviate向量数据库操作

一.安装weaviate客户端 1.Dify 0.6.9中weaviate信息 在Dify 0.6.9版本中weaviate容器信息如下： # The Weaviate vector store. weaviate:image: semitechnologies/weaviate:1.19.0restart: alwaysvolumes:# Mount the Weaviate data directory to the container.- ./volume…
阅读更多...
数据结构（空间复杂度介绍）超详细！！！

数据结构（空间复杂度介绍）超详细！！！

1. 数据结构前言 1.1 数据结构 数据结构是计算机存储、组织数据的形式&#xff0c;指相互之间存在一种或多种特定关系的数据元素的集合 1.2 算法 算法&#xff1a;良好的计算过程&#xff0c;它取一个或一组的值为输入&#xff0c;并产生出一个或一组的值作为输出。即算法经…
阅读更多...
初学SpringMVC之 Ajax 篇

初学SpringMVC之 Ajax 篇

Ajax&#xff08;Asynchronous JavaScript and XML&#xff09;是一种在无需重新加载整个网页&#xff0c;能够更新部分网页的技术 Ajax 不是编程语言&#xff0c;而是一种用于创建更好更快以及交互性更强的 Web 应用程序技术 使用 Ajax 技术的网页&#xff0c;通过在后台服务…
阅读更多...
课程设计——Python+OpenCV数字图像处理[车牌识别]

课程设计——Python+OpenCV数字图像处理[车牌识别]

Python opencv 车牌识别 数字图像处理课程设计作业Python3OpenCV使用tkinter搭建界面tmp/文件夹是数字图像处理过程chepai/文件夹是车牌图片pic/文件夹是程序界面图PPT文件是验收时要讲的程序是从网上学习的并自己弄的&#xff0c;不完善&#xff0c;识别率不高 开发环境配置…
阅读更多...
jenkins系列-09.jpom构建java docker harbor

jenkins系列-09.jpom构建java docker harbor

本地先启动jpom server agent: /Users/jelex/Documents/work/jpom-2.10.40/server-2.10.40-release/bin jelexjelexxudeMacBook-Pro bin % sh Server.sh start/Users/jelex/Documents/work/jpom-2.10.40/agent-2.10.40-release/bin jelexjelexxudeMacBook-Pro bin % ./Agent.…
阅读更多...
最新文章

Copyright @ 2022~2023