数据结构第3问：什么是线性表？

线性表

线性表由具有相同数据类型的n个元素构成，这些元素之间存在一一对应的线性关系。其中n为表长，当n=0的时候线性表是一个空表。简单来说，线性表中的元素排列成一条线，每个元素最多有一个直接的前驱和后继（除第一个和最后一个元素外）。线性表的第一个数据元素称为表头元素，最后一个数据元素称为表尾元素。

线性表的特点

  1. 表中元素的个数有限。
  2. 表中元素具有逻辑上的顺序，有先后次序。
  3. 表中元素都是数据元素，每个元素都是单独的基本单位。
  4. 表中元素的数据类型相同，占用相同大小的存储空间。
  5. 表中元素具有抽象性，表示逻辑上的数据对象。
  6. 表中每个元素除首末元素外，有且仅有一个直接前驱和一个直接后继，保证线性关系。
  7. 线性表可用顺序存储（如数组）或链式存储（如链表）两种方式实现。
  8. 支持按位置访问元素，比如通过索引或指针遍历。
  9. 线性表的逻辑结构独立于物理存储，实现方式多样。

线性表的基本操作

InitList(&L);			// 初始化线性表
Length(L);				// 求表长。返回表L的长度，即L中数据元素的个数
LocateElem(L, e);		// 按值查找操作，即查找表中具有给定e的元素
GetElem(L, i);			// 按位查找操作，获取表L中第i个位置的元素的值
ListInsert(&L, i, e);	// 将元素e插入表L的第i个位置
ListDelete(&L, i, &e);	// 删除表L第i个位置的元素，并用e返回删除元素的值
PrintList(L);			// 按先后顺序打印出表L的所有元素值
Empty(L);				// 判断表L是否为空，为空返回true，否则返回false
DestyoyList(&L);		// 销毁线性表

线性表的顺序表示：顺序表

线性表的顺序存储也称顺序表。

顺序表是一种线性表的存储结构，也叫做“顺序存储结构”或“顺序结构”。它将线性表中的元素按顺序存放在一块连续的存储空间中（通常是数组），每个元素占用相同大小的存储单元。通过元素的下标，可以快速访问和定位元素。简单来说，顺序表就是利用数组实现的线性表。

由于每个数据元素的存储位置都和顺序表的起始位置相差一个和该数据元素的位序乘正比的常数，因此顺序表的任意数据元素都支持随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。

随机存取：只要一种数据结构能够在常数时间 O(1) 内直接找到任意元素的地址，就可以称之为支持随机存取。支持随机存取的数据结构具有以下特征：

  1. 直接访问：能够直接访问任何元素而不需要依赖于顺序遍历。例如，通过索引或其他唯一标识符（如键）可以直接获取到数据。

  2. 时间复杂度：支持随机存取的关键是，在访问任何元素时，不论元素在数据结构中的位置，都能保持常数时间的访问复杂度 O(1)。这意味着，无论数据的大小如何，访问时间始终是固定的。

静态分配内存空间的顺序表实例

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>#define MaxSize 100
// 描述一个顺序表的存储结构
typedef struct
{unsigned char data[MaxSize];unsigned int length;
} SqList;// 顺序表初始化
void InitList(SqList *L)
{L->length = 0;
}// 求表长
int Length(SqList L)
{return L.length;
}// 按值查找操作，即查找表中具有给定值e的元素
int LocateElem(SqList L, unsigned char e)
{for (int i = 0; i < L.length; i++){if (L.data[i] == e)return i + 1;}return 0;
}// 按位查找操作，获取表L中第i个位置的元素的值
int GetElem(SqList L, unsigned int i)
{if (i < 1 || i > L.length)return 0;elsereturn (L.data[i - 1]);
}// 将元素e插入表L的第i个位置
bool ListInsert(SqList *L, unsigned int i, unsigned char e)
{if (i < 1 || i > L->length + 1)return false;if (L->length >= MaxSize)return false;// 搬运元素的时候注意要从后往前开始搬运，从前往后会导致前面的数据元素把后面的元素覆盖掉for (int j = L->length; j >= i; j--)L->data[j] = L->data[j - 1];L->data[i - 1] = e;L->length++;return true;
}// 删除表L第i个位置的元素，并用e返回删除元素的值
bool ListDeleteSqList(SqList *L, unsigned int i, unsigned char *e)
{if (i < 1 || i > L->length + 1)return false;if (L->length >= MaxSize)return false;*e = L->data[i-1];for (int j = i; j < L->length; j++)L->data[j-1] = L->data[j];L->length--;return true;
}// 按先后顺序打印出表L的所有元素值
void PrintList(SqList *L)
{for (int i = 0; i < L->length; i++){printf("Array index:%d, data:%d\r\n", i, L->data[i]);}
}// 判断表L是否为空，为空返回true，否则返回false
bool Empty(SqList L)
{if (L.length == 0)return true;elsereturn false;
}// 销毁顺序表
void DestyoyList(SqList *L)
{L->length = 0;L = NULL;
}

线性表的链式表示：链表

顺序表虽然具有随机存取的优点，但是进行删除和插入的操作时需要移动大量的元素，并且需要一段连续的内存空间进行存储。而链式存储的线性表，不需要使用连续的一段内存空间来存储整个线性表，它是利用 “链” 建立元素之间的逻辑关系，因此插入和删除操作不需要移动元素，只需要修改指针，但这样也就失去了顺序表随机存取的优点。

链表是一种线性表的链式存储结构。每个节点包含数据部分和指针部分，指针指向下一个节点的位置，这样节点按逻辑顺序连接起来，形成一个线性结构。通过指针的连接，可以方便地进行插入和删除操作，不需要像顺序表那样移动大量元素。

  1. 单链表：
    • 除尾节点外，每个节点只有一个指针，指向下一个节点。
    • 尾节点的指针指向 NULL，表示链表结束。
  2. 双链表：
    • 除头尾节点外，每个节点有两个指针，分别指向上一个节点和下一个节点。
    • 头节点的前驱指针指向 NULL，后继指针指向下一个节点。
    • 尾节点的后继指针指向 NULL，前驱指针指向上一个节点。
  3. 循环单链表：
    • 每个节点都有一个指针指向下一个节点。
    • 尾节点指针不指向 NULL，而是指向头节点，形成环状结构。
  4. 循环双链表：
    • 每个节点有两个指针，分别指向上一个节点和下一个节点。
    • 头节点的前驱指针指向尾节点，尾节点的后继指针指向头节点，形成双向环状结构。

动态分配内存空间的单链表实例

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include <stdlib.h>typedef struct Node
{int data;struct Node *next;
} Node, *Linklist;/*** 方法1：初始化链表头指针（通过入口参数传入指针的地址）* @param L 指向链表头指针的指针（二级指针）* @return true 分配成功，false 分配失败** 说明：* - 函数接收一个指向头指针变量的指针（Linklist *L），*   可以在函数内部修改调用者的头指针变量，使其指向新节点。* - malloc 分配一块内存空间存储一个 Node 结构体。* - 如果分配失败，返回 false。* - 分配成功后，设置头节点的数据成员和指针域。* - 这种写法充分利用了 C 语言的值传递特性，通过传入指针的地址，*   修改指针本身，实现头指针的初始化。*/
bool init_Linklist(Linklist *L)
{*L = malloc(sizeof(Node));if (*L == NULL){return false;}(*L)->data = 1;(*L)->next = NULL;return true;
}/*** 方法2：初始化链表头指针（通过函数返回新分配的节点指针）* @return 返回指向链表头节点的指针，分配失败返回 NULL** 说明：* - 函数内部通过 malloc 分配一个 Node 节点。* - 给新节点赋予初始数据和指针值。* - 函数直接返回新分配节点的指针。* - 调用者通过接收返回值获得链表头指针。* - 这种写法简洁，调用方便，适用于不需要返回其它状态码，*   只需要通过 NULL 判断失败的情况。*/
Linklist INIT2_Linklist(void)
{Linklist L = malloc(sizeof(Node));L->data = 1;L->next = NULL;return L;
}// 在头节点后面插入新的节点
bool insert_below_head(Linklist *head, int new_data)
{Node *new_node = malloc(sizeof(Node));if (new_node == NULL)return false;new_node->data = new_data;new_node->next = (*head)->next;(*head)->next = new_node;return true;
}// 在头节点前面插入新的节点
bool insert_front_head(Linklist *head, int new_data)
{// 创建新节点Node *new_node = malloc(sizeof(Node));if (new_node == NULL)return false;new_node->data = new_data;// 插入新节点new_node->next = (*head);// 更新头指针为新的节点*head = new_node;return true;
}// 在尾节点后面插入新的节点
bool insert_tail(Linklist *head, int new_data)
{Node *new_node = malloc(sizeof(Node));if(new_node == NULL)return false;new_node->data = new_data;new_node->next = NULL;  // 尾节点的next为NULLNode *node = *head;// 遍历找到最后一个节点，循环退出时node为尾节点while(node->next != NULL){node = node->next;}node->next = new_node;return true;
}// 在尾节点前面插入新的节点
bool insert_front_tail(Linklist *head, int new_data, int length)
{Node *new_node = malloc(sizeof(Node));if(new_node == NULL)return false;new_node->data = new_data;new_node->next = NULL;  // 尾节点的next为NULLNode *node = *head;while (node->next->next != NULL){node = node->next;}new_node->next = node->next;node->next = new_node;return true;
}// 打印链表所有节点
void print_node(Linklist *head)
{Node *new_node = *head;if (*head == NULL){printf("链表为空\n");return;}// 遍历打印出所有节点，循环退出时new_node为NULLwhile (new_node != NULL){printf("node:%p,DATA:%d\r\n", new_node, new_node->data);new_node = new_node->next;}
}// 删除链表
void delete_list(Linklist *head)
{while((*head) != NULL){Node *node = *head;*head = (*head)->next;free(node);}
}// 求链表长度
int getlistlength(Linklist *head)
{if (*head == NULL){printf("链表长度为:0\n");return 0;}Node *node = *head;int i = 0;while(node->next != NULL){i++;node = node->next;}printf("链表长度为:%d (不包含头节点)\n",i);return i;
}// 按值查找某个节点，返回该节点的位号
int seek_node_by_value(Linklist *head, int value)
{Node *current = *head;int i = 0;while (current != NULL && current->data != value){current = current->next;i++;}printf("[check by value] index:%d,DATA:%d\r\n",i,current->data);return i;
}// 按位置查找某个节点，返回该节点的值,eg：查找第3个节点的值
int seek_node_by_index(Linklist *head, int index)
{Node *current = *head;int i = 0;while (current != NULL && i < index - 1){current = current->next;i++;}printf("[check by index] index:%d,DATA:%d\r\n",i,current->data);return current->data;
}// 将某个节点插入第i个位置（不考虑头尾需要的额外处理）
bool insert_node_by_index(Linklist *head, int index, int data)
{Node *new_node = malloc(sizeof(Node));if(new_node == NULL)return false; new_node->data = data;Node *current_node = *head;    int i = 0;// while (i < index - 1) 这个条件正是为了让循环结束时 current_node 指向插入位置的前驱节点，方便在这个位置插入新节点。while(current_node != NULL && i < index - 1){current_node = current_node->next;i++;}new_node->next = current_node->next;current_node->next = new_node;return true;
}// 删除表中第i个节点
bool delete_node_by_index(Linklist *head, int index)
{Node *current = *head;int i = 0;while(current != NULL && i < index - 1){current = current->next;i++;}// 先保存待删除的节点指针Node *node_to_delete = current->next;// 修改指针来断开链表中的该节点current->next = current->next->next;// 最后释放内存free(node_to_delete);return true;
}

顺序表和链表的比较

  1. 存取方式

    1. 顺序表：采用顺序存取，通过数组的下标可以直接访问任意位置的元素，访问速度快（时间复杂度为O(1)）。
    2. 链表：采用链式存取，访问元素时需从表头开始沿指针逐个访问，访问特定位置元素时间复杂度为O(n)。

  2. 逻辑结构和物理结构

    1. 顺序表

      逻辑结构是线性表，元素按顺序排列。物理结构是连续的内存空间（数组）。

    2. 链表

      逻辑结构也是线性表，元素按顺序连接。物理结构是分散的节点，节点通过指针连接，内存地址不必连续。

  3. 查找、插入和删除操作

操作顺序表链表
查找支持随机访问，时间O(1)需顺序遍历，时间O(n)
插入插入位置后元素需移动，时间O(n)插入位置通过指针调整，时间O(1)（已找到插入点）
删除删除后元素需移动，时间O(n)通过指针调整删除，时间O(1)（已找到删除点）

  1. 空间分配

    • 顺序表：需要预先分配一块连续的固定大小的内存空间，可能造成浪费或空间不够。

    • 链表：动态分配内存，根据需要申请和释放节点空间，节省空间但需要额外指针的存储开销。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.pswp.cn/news/916949.shtml
繁体地址，请注明出处：http://hk.pswp.cn/news/916949.shtml

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

常见CMS 靶场复现

常见CMS 靶场复现

一、wordpass1.修改模版文件getshell搭建网站登录网站后台更改网站模版的相关文件写入一句话木马凭借路径访问/wp-content/themes/twentyfifteen/404.php/?aphpinfo();2.上传夹带木马的主题getshell外观-->主题-->添加-->上传-->浏览-->安装-->访问木马文件…
阅读更多...
Elasticsearch - 倒排索引原理和简易实现

Elasticsearch - 倒排索引原理和简易实现

倒排索引的功能设计倒排索引&#xff08;Inverted Index&#xff09;是一种高效的数据结构&#xff0c;常用于全文搜索和信息检索系统。它的核心思想是将文档中每个关键字&#xff08;term&#xff09;与包含该关键字的文档列表进行映射。以下是实现倒排索引功能的设计步骤和代…
阅读更多...
C#开发的Panel里控件拖放例子 - 开源研究系列文章

C#开发的Panel里控件拖放例子 - 开源研究系列文章

上次写了Panel的分页滚动控件( C#开发的Panel滚动分页控件&#xff08;滑动版&#xff09; - 开源研究系列文章 - Lzhdims Fashion - 博客园 )&#xff0c;但是主要是想写一个Panel里控件拖放的效果&#xff0c;然后分页控件用于Panel里控件的分页。此文这次写的是控件拖放效果…
阅读更多...
Thinkph6中常用的验证方式实例

Thinkph6中常用的验证方式实例

我们在使用thinkphp6中的数据验证时&#xff0c;如果使用不多的话&#xff0c;会经常遇到校验不对&#xff0c;在这个小问题上折腾很多&#xff0c;索引就不用了。我还不如直接写if条件来的迅捷&#xff01;&#xff01;下面把常见的校验方法进行一下整理&#xff1a;protected…
阅读更多...
分享一个FPGA寄存器接口自动化工具

分享一个FPGA寄存器接口自动化工具

FPGA模块越写越多&#xff0c;规范性和可移植性却堪忧。要是有一个工具可以根据模块接口描述文件生成verilog和c头文件就好了。苦苦搜寻找到了几款免费的工具&#xff0c;SystemRDL、cheby和rggen。笔者学习了下cheby和reksio&#xff0c;reksio是gui版的cheby&#xff0c;这是…
阅读更多...
小程序中事件对象的属性与方法

小程序中事件对象的属性与方法

在小程序中&#xff0c;事件处理函数的参数为事件对象&#xff08;通常命名为 e&#xff09;&#xff0c;包含了事件相关的详细信息&#xff08;如事件类型、触发元素、传递的数据等&#xff09;。事件对象的属性和方法因事件类型&#xff08;如点击、输入、触摸等&#xff09;…
阅读更多...
使用宝塔“PostgreSQL管理器”安装的PostgreSQL，如何设置远程连接？

使用宝塔“PostgreSQL管理器”安装的PostgreSQL，如何设置远程连接？

安装 PostgreSQL 使用宝塔“PostgreSQL管理器”安装PostgreSQL&#xff0c;版本可以根据自己的需求来选择&#xff0c;我这里使用的是16.1 创建数据库 根据下图所示步骤创建数据库&#xff0c;其中 “访问权限”一定要选择“所有人”启用远程连接设置允许所有 IP 连接 listen_a…
阅读更多...
论文：M矩阵

论文：M矩阵

M矩阵是线性代数中的一个概念&#xff0c;它是一种特殊类型的矩阵&#xff0c;具有以下性质&#xff1a;非负的非对角线元素&#xff1a;矩阵的所有非对角线元素都是非负的&#xff0c;即对于矩阵MMM中的任意元素mijm_{ij}mij​&#xff0c;当i≠ji\neq jij时&#xff0c;有m…
阅读更多...
跳跃表可视化深度解析：动态演示数据结构核心原理

跳跃表可视化深度解析：动态演示数据结构核心原理

跳跃表可视化深度解析&#xff1a;动态演示数据结构核心原理 一、跳跃表基础概念与核心优势 跳跃表&#xff08;SkipList&#xff09;是一种基于多层索引链表的数据结构&#xff0c;通过概率平衡实现高效的插入、删除和查找操作。其核心优势体现在&#xff1a; ​时间复杂度优…
阅读更多...
《Sentinel服务保护实战：控制台部署与SpringCloud集成指南》

《Sentinel服务保护实战：控制台部署与SpringCloud集成指南》

sentinel 介绍 Sentinel是阿里巴巴开源的一款服务保护框架&#xff0c;目前已经加入SpringCloudAlibaba中。官方网站&#xff1a; home | Sentinel Sentinel 的使用可以分为两个部分: 核心库&#xff08;Jar包&#xff09;&#xff1a;不依赖任何框架/库&#xff0c;能够运行…
阅读更多...
IBM Watsonx BI：AI赋能的下一代商业智能平台

IBM Watsonx BI：AI赋能的下一代商业智能平台

产品概览 IBM Watsonx BI 是基于 watsonx 企业级 AI 与数据平台 构建的智能分析解决方案&#xff0c;专为现代化企业打造。它深度融合人工智能技术&#xff0c;突破传统 BI 工具的限制&#xff0c;通过自动化数据洞察、自然语言交互和预测分析&#xff0c;帮助企业在复杂数据环…
阅读更多...
Python实现GO鹅优化算法优化GBRT渐进梯度回归树回归模型项目实战

Python实现GO鹅优化算法优化GBRT渐进梯度回归树回归模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取 或者私信获取。 1.项目背景 随着大数据和人工智能技术的快速发展&#xff0c;回归预测在金融、气象、能源等多个领域中扮演着至关…
阅读更多...
深度学习计算（深度学习-李沐-学习笔记）

深度学习计算（深度学习-李沐-学习笔记）

层和块 单一输出的线性模型&#xff1a;单个神经网络 &#xff08;1&#xff09;接受一些输入&#xff1b; &#xff08;2&#xff09;生成相应的标量输出&#xff1b; &#xff08;3&#xff09;具有一组相关 参数&#xff08;parameters&#xff09;&#xff0c;更新这些参数…
阅读更多...
leetcode热题——搜索二维矩阵Ⅱ

leetcode热题——搜索二维矩阵Ⅱ

目录 搜索二维矩阵Ⅱ 题目描述 题解 解法一&#xff1a;暴力搜索 C 代码实现 复杂度分析 解法二&#xff1a;二分查找 C 代码实现 复杂度分析 解法三&#xff1a;Z字形查找 算法核心思想 算法步骤详解 C 代码实现 复杂度分析 搜索二维矩阵Ⅱ 题目描述 编写一个…
阅读更多...
牛客 - 数组中的逆序对

牛客 - 数组中的逆序对

描述 在数组中的两个数字&#xff0c;如果前面一个数字大于后面的数字&#xff0c;则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007 数据范围&#xff1a; 对于 50% 的数据, size≤104 s…
阅读更多...
Linux 日志管理与时钟同步详解

Linux 日志管理与时钟同步详解

Linux 日志管理与时钟同步详解 一、日志管理 1. 日志服务概述 Linux 系统中主要有两种日志服务&#xff0c;分别负责临时和永久日志的管理&#xff1a; systemd-journald&#xff1a;存储临时日志&#xff0c;服务器重启后日志会丢失&#xff0c;无需手动配置rsyslog&#xff1…
阅读更多...
个人如何做股指期货？

个人如何做股指期货？

本文主要介绍个人如何做股指期货&#xff1f;个人参与股指期货交易需要遵循一定的流程和规则&#xff0c;同时需充分了解其高风险、高杠杆的特点&#xff0c;并做好风险管理。个人如何做股指期货&#xff1f;一、了解股指期货基础股指期货是以股票价格指数为标的物的金融期货合…
阅读更多...
设计模式-单例模式 Java

设计模式-单例模式 Java

模式概述 单例模式&#xff08;Singleton Pattern&#xff09;是设计模式中最基础但应用最广泛的创建型模式之一&#xff0c;确保一个类仅有一个实例&#xff0c;并提供一个全局访问点。这种模式在需要全局唯一对象的场景中至关重要&#xff0c;如配置管理、线程池、数据库连接…
阅读更多...
RFID 系统行业前沿洞察：技术跃迁与生态重构

RFID 系统行业前沿洞察：技术跃迁与生态重构

在物联网与人工智能深度融合的时代&#xff0c;RFID&#xff08;射频识别&#xff09;系统正经历从 “单品识别工具” 到 “智能决策中枢” 的范式转变。这一技术凭借其非接触式数据采集、环境适应性强、全生命周期追溯等特性&#xff0c;在医疗、制造、农业、环保等领域引发连…
阅读更多...
实现implements InitializingBean, DisposableBean 有什么用

实现implements InitializingBean, DisposableBean 有什么用

在 Spring 框架中&#xff0c;实现 InitializingBean 和 DisposableBean 接口用于管理 Bean 的生命周期回调&#xff0c;分别控制 Bean 的初始化后和销毁前行为。具体作用如下&#xff1a;1. InitializingBean 接口public interface InitializingBean {void afterPropertiesSet…
阅读更多...
最新文章

Copyright @ 2022~2023