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

数据机构记录顺序表-笔记1

一、线性表的基本概念

数据元素:线性表中的基本单位,每个元素都是线性表的一部分。
数据项:数据元素的具体值。
存储位置:线性表中的元素在内存中的具体存储位置。
线性表按存储结构可以分为顺序表和链表两大类:

1.1顺序表:

顺序表是用一段连续的存储单元依次存储线性表中的元素。
**优点:**可以快速访问任意位置的元素(时间复杂度为 O(1))。
**缺点:**插入和删除操作效率较低(时间复杂度为 O(n)),需要移动大量元素;在存储空间不足或溢出时需要进行空间扩展或缩减。

1.2链表:

链表是由一系列结点组成的,每个结点包含数据元素和指向下一个结点的指针。### 链表分类
可以分为单链表、双向链表和循环链表等
单链表:每个结点只包含一个指向后继结点的指针。
双向链表:每个结点包含两个指针,分别指向前驱结点和后继结点。
循环链表:尾结点的指针指向头结点,形成一个环。
优点:插入和删除操作效率较高(时间复杂度为 O(1)),不需要移动大量元素。
缺点:无法快速访问任意位置的元素(时间复杂度为 O(n)),需要遍历链表。

1.3线性表的基本操作

初始化:创建一个空的线性表。
销毁:销毁线性表,释放存储空间。
插入:在指定位置插入一个新元素。
删除:删除指定位置的元素。
查找:查找指定值的元素,返回其位置。
更新:更新指定位置的元素值。
遍历:依次访问线性表中的每个元素。

1.4线性表的应用

线性表广泛应用于各种场景,例如:

1.5数据的存储和管理。

实现其他数据结构和算法,如栈、队列、哈希表等。
操作系统中的进程调度、内存管理等。
数据库系统中的表操作。

二、线性表的基本操作

2.1 初始化

初始化是创建一个空的线性表。根据存储方式的不同,初始化的方式也不同。

顺序表的初始化

顺序表用数组来表示,因此初始化时需要分配一段连续的存储空间。

# 顺序表的初始化
def init_sequence_list():sequence_list = []  # 创建一个空列表return sequence_list# 使用示例
sequence_list = init_sequence_list()
print(sequence_list)  # 输出: []

链表的初始化

链表用结点来表示,因此初始化时需要创建一个头结点。

# 定义链表的结点
class Node:def __init__(self, data=None):self.data = data  # 结点的数据self.next = None  # 指向下一个结点的指针# 链表的初始化
def init_linked_list():head = Node()  # 创建一个空的头结点return head# 使用示例
linked_list = init_linked_list()
print(linked_list.data)  # 输出: None
print(linked_list.next)  # 输出: None

2.2 插入操作

插入操作是在线性表的指定位置插入一个新元素。

顺序表的插入

在顺序表中插入元素时,需要将插入位置后的所有元素向后移动一位,以腾出插入位置。

# 顺序表的插入操作
def insert_sequence_list(sequence_list, index, element):if index < 0 or index > len(sequence_list):print("插入位置不合法")return Falsesequence_list.insert(index, element)return True# 使用示例
sequence_list = [1, 2, 3, 4]
insert_sequence_list(sequence_list, 2, 99)
print(sequence_list)  # 输出: [1, 2, 99, 3, 4]

链表的插入

在链表中插入元素时,需要找到插入位置的前一个结点,然后修改指针。

# 链表的插入操作
def insert_linked_list(head, index, element):if index < 0:print("插入位置不合法")return Falsenew_node = Node(element)  # 创建新结点current = headfor _ in range(index):if current.next is None:print("插入位置不合法")return Falsecurrent = current.nextnew_node.next = current.nextcurrent.next = new_nodereturn True# 使用示例
linked_list = init_linked_list()
insert_linked_list(linked_list, 0, 1)
insert_linked_list(linked_list, 1, 2)
insert_linked_list(linked_list, 1, 99)
current = linked_list.next
while current:print(current.data, end=" ")  # 输出: 1 99 2current = current.next

2.3 删除操作

删除操作是删除线性表的指定位置的元素。

顺序表的删除

在顺序表中删除元素时,需要将删除位置后的所有元素向前移动一位。

# 顺序表的删除操作
def delete_sequence_list(sequence_list, index):if index < 0 or index >= len(sequence_list):print("删除位置不合法")return Falsedel sequence_list[index]return True# 使用示例
sequence_list = [1, 2, 99, 3, 4]
delete_sequence_list(sequence_list, 2)
print(sequence_list)  # 输出: [1, 2, 3, 4]

链表的删除

在链表中删除元素时,需要找到删除位置的前一个结点,然后修改指针。

# 链表的删除操作
def delete_linked_list(head, index):if index < 0:print("删除位置不合法")return Falsecurrent = headfor _ in range(index):if current.next is None:print("删除位置不合法")return Falsecurrent = current.nextif current.next is None:print("删除位置不合法")return Falsecurrent.next = current.next.nextreturn True# 使用示例
linked_list = init_linked_list()
insert_linked_list(linked_list, 0, 1)
insert_linked_list(linked_list, 1, 99)
insert_linked_list(linked_list, 2, 2)
delete_linked_list(linked_list, 1)
current = linked_list.next
while current:print(current.data, end=" ")  # 输出: 1 2current = current.next

2.4 查找操作

查找操作是查找线性表中指定值的元素,返回其位置。

顺序表的查找
# 顺序表的查找操作
def find_sequence_list(sequence_list, element):try:index = sequence_list.index(element)return indexexcept ValueError:return -1# 使用示例
sequence_list = [1, 2, 3, 4]
index = find_sequence_list(sequence_list, 3)
print(index)  # 输出: 2

链表的查找

# 链表的查找操作
def find_linked_list(head, element):current = head.next  # 跳过头结点index = 0while current:if current.data == element:return indexcurrent = current.nextindex += 1return -1# 使用示例
linked_list = init_linked_list()
insert_linked_list(linked_list, 0, 1)
insert_linked_list(linked_list, 1, 2)
insert_linked_list(linked_list, 2, 3)
index = find_linked_list(linked_list, 3)
print(index)  # 输出: 2

相关文章:

数据机构记录顺序表-笔记1

一、线性表的基本概念 数据元素&#xff1a;线性表中的基本单位&#xff0c;每个元素都是线性表的一部分。 数据项&#xff1a;数据元素的具体值。 存储位置&#xff1a;线性表中的元素在内存中的具体存储位置。 线性表按存储结构可以分为顺序表和链表两大类&#xff1a; 1.1…...

考研必备~总结严蔚敏教授《数据结构》课程的重要知识点及考点

作者主页&#xff1a;知孤云出岫 目录 1. 基本概念1.1 数据结构的定义1.2 抽象数据类型 (ADT) 2. 线性表2.1 顺序表2.2 链表 3. 栈和队列3.1 栈3.2 队列 4. 树和二叉树4.1 树的基本概念4.2 二叉树 5. 图5.1 图的基本概念5.2 图的遍历 6. 查找和排序6.1 查找6.2 排序 7. 重点考…...

【数据分享】国家级旅游休闲街区数据(Excel/Shp格式/免费获取)

之前我们分享过从我国文化和旅游部官网整理的2018-2023年我国50个重点旅游城市星级饭店季度经营状况数据&#xff08;可查看之前的文章获悉详情&#xff09;&#xff01;文化和旅游部官网上也分享有很多与旅游相关的常用数据&#xff0c;我们基于官网发布的名单文件整理得到全国…...

Linux开发:进程间通过Unix Domain Socket传递数据

进程间传递数据的方式有很多种,Linux还提供一种特殊的Socket用于在多进程间传递数据,就是Unix Domain Socket(UDS)。 虽然通过普通的Socket也能做到在多进程间传递数据,不过这样需要通过协议栈层的打包与拆包,未免有些浪费效率,通过UDS,数据仅仅通过一个特殊的sock文件…...

Redis基础教程(九):redis有序集合

&#x1f49d;&#x1f49d;&#x1f49d;首先&#xff0c;欢迎各位来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里不仅可以有所收获&#xff0c;同时也能感受到一份轻松欢乐的氛围&#xff0c;祝你生活愉快&#xff01; &#x1f49d;&#x1f49…...

Servlet与Servlet容器

什么是Servlet? Servlet是Java EE&#xff08;现称Jakarta EE&#xff09;中的一个组件&#xff0c;通常用于创建动态Web内容。Servlet是运行在Web服务器上的Java程序&#xff0c;它处理客户端的请求并生成响应。Servlet的核心功能是处理HTTP请求和响应。下面是一个servlet例…...

腾讯centos mysql安装

腾讯centos mysql安装 腾讯云提供了一系列的云计算服务&#xff0c;包括操作系统、数据库、服务器等。在腾讯云上安装CentOS操作系统和MySQL数据库可以按照以下步骤进行&#xff1a; 登录腾讯云控制台&#xff08;登录 - 腾讯云&#xff09;。在控制台页面上方的搜索框中输入…...

c_各个unsigned int 和 int的取值范围

bool, uint8_t, uint16_t, uint32_t, uint64_t, int8_t, int16_t, int32_t, int64_t 取值范围分别是什么&#xff1f; 定义形式&#xff1a; typedef unsigned char uint8_t; typedef unsigned short uint16_t; typedef unsigned int uint32_t; typedef unsigned long uint64_…...

C#/WPF 自制截图工具

在日常使用电脑办公时&#xff0c;我们经常遇到需要截图然后保存图片&#xff0c;我们往往需要借助安装截图工具才能实现&#xff0c;现在我们通过C#自制截图工具&#xff0c;也能够轻松进行截图。 我们可以通过C#调用WindousAPI来实现截图&#xff0c;实例代码如下&#xff1a…...

以腾讯为例,手把手教你搭建产品帮助中心

一个精心设计的产品帮助中心对于提高用户满意度和体验至关重要。腾讯&#xff0c;作为全球领先的互联网企业&#xff0c;通过其多样化的产品线&#xff08;包括微信、QQ、腾讯游戏、腾讯视频等&#xff09;吸引了亿万用户。下面将以腾讯为例&#xff0c;向您展示如何搭建一个高…...

计算机网络概述--自我学习用

计算网络体系概述 相关问题 计算机网络为什么要分层&#xff1f;计算机网络是怎么分层的&#xff1f;三种计算机网络模型的关系是什么&#xff1f;每一层分别包含哪些协议&#xff1f;计算机网络中&#xff0c;数据如何在各层中传播&#xff1f;数据在网络各层中的存在形式是…...

超级好用的java http请求工具

kong-http 基于okhttp封装的轻量级http客户端 使用方式 Maven <dependency><groupId>io.github.kongweiguang</groupId><artifactId>kong-http</artifactId><version>0.1</version> </dependency>Gradle implementation …...

在原有的iconfont.css文件中加入新的字体图标

前言&#xff1a;在阿里图标库中&#xff0c;如果你没有这个字体图标的线上项目&#xff0c;那么你怎么在本地项目中的原始图标文件中添加新的图标呢&#xff1f; 背景&#xff1a;现有一个vue项目&#xff0c;下面是这个前端项目的字体图标文件。现在需要新开发功能页&#x…...

使用 ESP32-WROOM + DHT11 做个无屏温湿度计

最近梅雨天&#xff0c;有个房间湿度很大&#xff0c;而我需要远程查看温湿度&#xff0c;所以无所谓有没有显示屏&#xff0c;某宝上的温湿度计都是带屏的&#xff0c;如果连WIFI查看温湿度操作也比较麻烦&#xff0c;还需要换电池&#xff0c;实在不能满足我的需求&#xff0…...

如何使用 SwiftUI 构建 visionOS 应用

文章目录 前言WindowsVolumes沉浸式空间结论 前言 Apple Vision Pro 即将推出&#xff0c;现在是看看 SwiftUI API 的完美时机&#xff0c;这使我们能够将我们的应用程序适应 visionOS 提供的沉浸式世界。苹果表示&#xff0c;构建应用程序的最佳方式是使用 Swift 和 SwiftUI。…...

InspireFace-商用级的跨平台开源人脸分析SDK

InspireFace-商用级的跨平台开源人脸分析SDK InspireFaceSDK是由insightface开发的⼀款⼈脸识别软件开发⼯具包&#xff08;SDK&#xff09;。它提供了⼀系列功能&#xff0c;可以满⾜各种应⽤场景下的⼈脸识别需求&#xff0c;包括但不限于闸机、⼈脸⻔禁、⼈脸验证等。 该S…...

华为HCIP Datacom H12-821 卷24

1.单选题 企业大楼有大量员工通常都在上班时在大厅开始接入到公司的WLAN网络,随着每位员工走到各自的工位过程中,每个人的移动端叶通过漫游的方式漫游到各自的网络覆盖区域。为了尽量保证每个终端的IP地址是固定的,建议的做法是? A、配置VLAN Pool并配置顺序算法 B、…...

TikTok马来西亚直播网络怎么配置?

TikTok是一款全球流行的社交媒体应用&#xff0c;在东南亚地区拥有大量用户。在马来西亚这个多元化的国家&#xff0c;配置高效稳定的直播网络对TikTok的运营至关重要。 配置马来西亚直播网络的必要性 广泛的地理覆盖&#xff1a;马来西亚包括大片陆地和众多岛屿&#xff0c;网…...

基于若依的文件上传、下载

基于若依实现文件上传、下载 文章目录 基于若依实现文件上传、下载1、前端实现-文件上传1.1 通用上传分析1.2 修改实现上传接口 2、后端实现-文件上传3、后端实现-文件下载4、前端实现-文件下载 官网其实也写了&#xff0c;但是我是自己改造封装了一下&#xff0c;再次迈向全栈…...

论文回顾 | CVPR 2021 | How to Calibrate Your Event Camera | 基于图像重建的事件相机校准新方法

论文速览 | CVPR 2021 | How to Calibrate Your Event Camera | 基于图像重建的事件相机校准新方法 1 引言 在计算机视觉和机器人领域,相机校准一直是一个基础而又重要的问题。传统的相机校准方法主要依赖于从已知校准图案中提取角点,然后通过优化算法求解相机的内参和外参。这…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...