线性表（从数据结构的三要素出发）

文章目录

  • 逻辑结构
  • 存储结构
    • 顺序存储
    • 链式存储
      • 单链表
      • 双链表
      • 循环单链表
      • 循环双链表
      • 静态链表
  • 数据的操作
    • 顺序结构
    • 链式结构
      • 单链表
      • 双链表

逻辑结构

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

L = ( a 1 , a 2 , ⋯   , a i , a i + 1 , ⋯   , a n ) L=\left(a_1, a_2, \cdots, a_i, a_{i+1}, \cdots, a_n\right) L=(a1​,a2​,⋯,ai​,ai+1​,⋯,an​)

式中， a 1 a_1 a1​是唯一的“第一个”数据元素，又称表头元素； a n a_n an​是唯一的“最后一个”数据元素，又称表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。

线性表有以下特性：

  • 表中元素的个数有限。
  • 表中元素具有逻辑上的顺序性，表中元素有其先后次序。
  • 表中元素都是数据元素，每个元素都是单个元素。
  • 表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间。
  • 表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。

存储结构

顺序存储

它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。第1个元素存储在顺序表的起始位置，第i个元素的存储位置后面紧接着存储的是第 i + 1 i+1 i+1个元素，称 i i i为元素 a i a_i ai​在顺序表中的位序。因此，顺序表的特点是表中元素的逻辑顺序与其存储的物理顺序相同。

假设顺序表L存储的起始位置为LOC(A),sizeof(ElemType)是每个数据元素所占用存储空间的大小。

在这里插入图片描述

typedef struct {
	ElemType data[Maxsize];
	int length;
} SqList;

存在的问题：

  • 需要大量连续的存储空间
  • 插入删除时，时间复杂度高
  • 顺序表一旦确定大小，后续将不可扩充

链式存储

链式存储线性表时，不需要使用地址连续的存储单元，即不要求逻辑上相邻的元素在物理位置上也相邻，它通过“链”建立元素之间的逻辑关系，因此插入和删除操作不需要移动元素，而只需修改指针，但也会失去顺序表可随机存取的优点。

单链表

在这里插入图片描述

typedef struct LNode {
	ElemType data;
	struct LNode *next;
} LNode, *LinkList;

存在的问题：

  • 失去了顺序存储中随机存取的特性
  • 求表长的时间复杂度高
  • 访问前驱结点的时间复杂度高

双链表

在单链表中要访问某个结点的前驱(插入、删除操作时),只能从头开始遍历，访问前驱的时间复杂度为 O ( n ) O(n) O(n)。为了克服单链表的这个缺点，引入了双链表，双链表结点中有两个指针prior和next,分别指向其直接前驱和直接后继。表头结点的 prior域和尾结点的 next 域都是 NULL。

在这里插入图片描述

typedef struct DNode {
	ElemType data;
	struct DNode *next, prior;
} DNode, *DLinkList;

循环单链表

循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL,而改为指向头结点，从而整个链表形成一个环。

在这里插入图片描述

循环双链表

由循环单链表的定义不难推出循环双链表。不同的是，在循环双链表中，头结点的prior指针还要指向表尾结点。

在这里插入图片描述

静态链表

静态链表是用数组来描述线性表的链式存储结构，结点也有数据域data 和指针域 next,与前面所讲的链表中的指针不同的是，这里的指针是结点在数组中的相对地址(数组下标),又称游标。

在这里插入图片描述

typedef struct {
	ElemType data;
	int next;
} SLinkList[Maxsize];

数据的操作

顺序结构

初始化

void InitList(SqList &L)
{
	L.length = 0;
}

判满

bool isFull(SqList L)
{
	if (L.length == Maxsize) return true;
	return false;
}

判空

bool isEmpty(SqList L)
{
	if (L.length == 0) return true;
	return false;
}

插入操作

bool ListInsert(SqList &L, int i, ElemType e)
{
	if (i < 1 || i > L.length + 1)				// 无效的插入位置
		return false;

	if (isFull(L)) 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;
}

删除操作

bool ListDelete(SqList &L, int i, ElemType e)
{
	if (i < 1 || i > L.length + 1)				// 无效的删除位置
		return false;
	if (isEmpty(L)) 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;
}

按值查找

int LocateElem(SqList L, ElemType e)
{
	for (int i = 0; i < L.length; i ++ )
		if (L.data[i] == e)
			return i + 1;
	return -1;
}

链式结构

单链表

初始化

void InitList(LinkList &L)
{
	L = (LNode *) malloc (sizeof(LNode));
	L->next = NULL;
}

求表长

int Length(LinkList L)
{
	LNode *p = L->next;
	int cnt = 0;			// 记录长度
	while (p)
	{
		cnt ++ ;
		p = p->next;
	}
	return cnt;
}

按序号查找结点

LNode * GetElem(LinkList L, int i)
{
	LNode *p = L->next;
	int cnt = 0;						// 记录当前遍历到第几个结点了
	while (p)
	{
		cnt ++ ;
		if (cnt == i)
			return p;
		p = p->next;
	}
	return NULL;
}

按值查找

LNode * LocateElem(LinkList L, ElemType e)
{
	LNode *p = L->next;
	while (p)
	{
		if (p->data == e)
			return p;
		p = p->next;
	}
	return NULL;
}

插入结点

在这里插入图片描述

bool ListInsert(LinkList &L, int i, ElemType e)
{
	LNode *p = L;
	int j = 0;
	while (p && j < i - 1)
	{
		p = p->next;
		j ++ ;
	}
	if (p == NULL) return false;		// 位置不合法

	LNode *s = (LNode *) malloc (sizeof(LNode));
	/*插入结点*/
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

删除结点
在这里插入图片描述

bool ListDelete(LinkList &L, int i, ElemType e)
{
	LNode *p = L;
	int j = 0;
	while (p && j < i - 1)
	{
		p = p->next;
		j ++ ;
	}
	if (p == NULL || p->next == NULL) return false;		// 位置不合法

	LNode *q = p->next;
	/*删除结点q*/
	e = q->data;
	p->next = q->next;
	free(q);
	return true;
}

采用头插法建立链表

在这里插入图片描述

LinkList List_HeadInsert(LinkList &L)
{
	LNode *s;
	int x;
	L = (LNode *) malloc (sizeof(LNode));
	L->next = NULL;
	scanf("%d", &x);
	while (x != 9999)		// 输入9999停止
	{
		s = (LNode *) malloc (sizeof(LNode));
		s -> data = x;
		s->next = L->next;
		L->next = s;
		scanf("%d", &x);
	}
	return L;
}

采用尾插法建立链表

在这里插入图片描述

LinkList List_TailInsert(LinkList &L)
{
	int x;
	L = (LNode *) malloc (sizeof(LNode));
	LNode *s, *r = L;		// r是表尾指针
	scanf("%d", &x);
	while (x != 9999)		// 输入9999停止
	{
		s = (LNode *) malloc (sizeof(LNode));
		s -> data = x;
		r->next = s;
		r = s;
		scanf("%d", &x);
	}
	r->next = NULL;
	return L;
}

双链表

初始化

void InitList(DLinkList &L)
{
	L = (DNode *) malloc (sizeof(DNode));
	L->next = L->prior = NULL;
}

插入结点

在这里插入图片描述

bool ListInsert(DLinkList &L, int i, ElemType e)
{
	DNode *p = L;
	int j = 0;
	while (p && j < i - 1)
	{
		p = p->next;
		j ++ ;
	}
	if (p == NULL) return false;		// 位置不合法

	DNode *s = (DNode *) malloc (sizeof(DNode));
	/*插入结点*/
	s->data = e;
	s->next = p->next;
	p->next->prior = s;
	s->prior = p;
	p->next = s;
	return true;
}

删除结点

bool ListDelete(DinkList &L, int i, ElemType e)
{
	DNode *p = L;
	int j = 0;
	while (p && j < i - 1)
	{
		p = p->next;
		j ++ ;
	}
	if (p == NULL || p->next == NULL) return false;		// 位置不合法

	DNode *q = p->next;
	/*删除结点q*/
	e = q->data;
	p->next = q->next;
	q->next->prior = p;
	free(q);
	return true;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/642553.html

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

相关文章

KMP算法【C++】

KMP算法【C++】

KMP算法测试 KMP 算法详解 根据解释写出对应的C代码进行测试&#xff0c;也可以再整理成一个函数 #include <iostream> #include <vector>class KMP { private:std::string m_pat;//被匹配的字符串std::vector<std::vector<int>> m_dp;//状态二维数组…
阅读更多...
WXSS模板样式-全局样式和局部样式

WXSS模板样式-全局样式和局部样式

一、WXSS 1.WXSS WXSS(WeiXin Style Sheets)是一套样式语言&#xff0c;用于美化WXML的组件样式&#xff0c;类似于网页开发中的CSS 2.WXSS和CSS的关系 WXSS具有CSS大部分特性&#xff0c;同时&#xff0c;WXSS还对CSS进行了扩充以及修改&#xff0c;以适应微信小程序的开发…
阅读更多...
NetSuite Intercompany COGS科目设置问题

NetSuite Intercompany COGS科目设置问题

在22年底的NetSuite多公司功能串讲中&#xff0c;有一个题目是Intercompany COGS科目的设置问题。近期在项目上这个问题被密集讨论。为了方便分享&#xff0c;所以在此摘出来独立成文。有兴趣的同学也可以翻看之前的视频。 NetSuite知识会 第8谈 多公司功能串讲 NetSuite Inter…
阅读更多...
Spring6基础笔记

Spring6基础笔记

Spring6 Log4j2 1、概述 1.1、Spring是什么&#xff1f; Spring 是一款主流的 Java EE 轻量级开源框架 &#xff0c;Spring 由“Spring 之父”Rod Johnson 提出并创立&#xff0c;其目的是用于简化 Java 企业级应用的开发难度和开发周期。Spring的用途不仅限于服务器端的开发…
阅读更多...
MPLS LDP原理与配置

MPLS LDP原理与配置

1.LDP基本概念 &#xff08;1&#xff09;LDP协议概述 &#xff08;2&#xff09;LDP会话、LDP邻接体、LDP对等体 &#xff08;3&#xff09;LSR ID 与LDP ID &#xff08;4&#xff09;LDP消息 ⦁ 按照消息的功能&#xff0c;LDP消息一共可以分为四大类型&#xff1a;发现…
阅读更多...
【C++STL详解(四)------vector的模拟实现】

【C++STL详解(四)------vector的模拟实现】

文章目录 vector各函数接口总览vector当中的成员变量介绍默认成员函数构造函数1构造函数2构造函数3拷贝构造函数赋值运算符重载函数析构函数 迭代器相关函数begin和end 容量和大小相关函数size和capacityreserveresizeempty 修改容器内容相关函数push_backpop_backinserterases…
阅读更多...
OpenStack平台Keystone组件的使用

OpenStack平台Keystone组件的使用

1. 规划节点 安装基础服务的服务器规划 IP地址 主机名 节点 192.168.100.10 controller Openstack控制节点 2. 基础准备 使用机电云共享的单节点的openstack系统&#xff0c;自行修改虚拟网络编辑器、网络适配器&#xff0c;系统用户名&#xff1a;root&#xff0c;密…
阅读更多...
【数据分析面试】53.推送消息的分布情况（SQL）

【数据分析面试】53.推送消息的分布情况（SQL）

题目 我们有两个表&#xff0c;一个是 notification_deliveries 表&#xff0c;另一个是包含 created 和购买 conversion dates 的 users 表。如果用户没有购买&#xff0c;那么 conversion_date 列为 NULL。 编写一个查询&#xff0c;以获取用户转换前的推送通知总数的分布情…
阅读更多...
51 单片机[4]：数码管显示

51 单片机[4]：数码管显示

目标&#xff1a; 一次显示一个数字&#xff1a;在数码管第三位显示6.同时显示多个不同数字&#xff1a;在数码管前三位分别显示1, 2, 3. 一、认识数码管 LED数码管&#xff1a;数码管是一种简单、廉价的显示器&#xff0c;是由多个发光二极管封装在一起组成“8”字型的器件…
阅读更多...
零拷贝(Zero-Copy)

零拷贝(Zero-Copy)

1.背景 现在有这样一个场景&#xff0c;我们需要在本地选择一个文件后&#xff0c;然后上传到网络上。 我们再看看文件的内容数据的具体搬运过程&#xff1a; 你会发现&#xff0c;在整个文件搬运的过程中&#xff0c;发生了多次的数据拷贝和上下文转换。 4次数据拷贝&#…
阅读更多...
amis 联动效果触发的几种方式

amis 联动效果触发的几种方式

联动效果实现主要俩种方式: 1.表达式实现联动,基于组件内或数据链的变量变化的联动 比如&#xff1a; "source": "/amis/api/mock2/options/level2?name${name} " (必须是这种字符串拼接形式,在data数据映射中表达式不会触发联动) 所有初始化接口链…
阅读更多...
【Linux】中的常见的重要指令（中）

【Linux】中的常见的重要指令（中）

目录 一、man指令 二、cp指令 三、cat指令 四、mv指令 五、more指令 六、less指令 七、head指令 八、tail指令 一、man指令 Linux的命令有很多参数&#xff0c;我们不可能全记住&#xff0c;我们可以通过查看联机手册获取帮助。访问Linux手册页的命令是 man 语法: m…
阅读更多...
【Spring Boot】深度复盘在开发搜索引擎项目中重难点的整理，以及遇到的困难和总结

【Spring Boot】深度复盘在开发搜索引擎项目中重难点的整理，以及遇到的困难和总结

&#x1f493; 博客主页&#xff1a;从零开始的-CodeNinja之路 ⏩ 收录文章&#xff1a;【Spring Boot】深度复盘在开发搜索引擎项目中重难点的整理&#xff0c;以及遇到的困难和总结 &#x1f389;欢迎大家点赞&#x1f44d;评论&#x1f4dd;收藏⭐文章 目录 什么是搜索引…
阅读更多...
基于SpringBoot+Vue的人事管理系统

基于SpringBoot+Vue的人事管理系统

引言 目前,人事管理的系统大都是CS架构的大型系统,很少有面向机关,事业单位内部的基于BS架构的微型人事系统,因此.开发一个基于BS架构的人事信息管理系统是非常必要的.但是基于BS架构的人事系统对于安全是一个大的考验点.在人事信息系统中,功能需简单清晰,可操作性强,其次安全…
阅读更多...
站在ESG“20+”新起点上，看中国ESG先锋探索力量

站在ESG“20+”新起点上，看中国ESG先锋探索力量

全链减碳、建设绿色工厂、打造零碳产品、守护生物多样性、向受灾群众捐助……不知你是否察觉&#xff0c;自“双碳”目标提出以来&#xff0c;一股“可持续发展热潮”正覆盖各行各业&#xff0c;并且渗透到我们衣食住行的方方面面。在资本市场&#xff0c;ESG投资热潮更是席卷全…
阅读更多...
外汇天眼：风险预警！以下平台监管牌照被撤销！

外汇天眼：风险预警！以下平台监管牌照被撤销！

监管信息早知道&#xff01;外汇天眼将每周定期公布监管牌照状态发生变化的交易商&#xff0c;以供投资者参考&#xff0c;规避投资风险。如果平台天眼评分过高&#xff0c;建议投资者谨慎选择&#xff0c;因为在外汇天眼评分高不代表平台没问题&#xff01; 以下是监管牌照发生…
阅读更多...
Leetcode | 5-21| 每日一题

Leetcode | 5-21| 每日一题

2769. 找出最大的可达成数字 考点: 暴力 数学式子计算 思维 题解 通过式子推导: 第一想法是二分确定区间在区间内进行查找是否符合条件的, 本题最关键的便是 条件确定 , 第二种方法: 一般是通过数学公式推导的,这种题目我称为数学式编程题 代码 条件判断式 class Solution { …
阅读更多...
ViT：1 从DETR说起

ViT：1 从DETR说起

大模型技术论文不断&#xff0c;每个月总会新增上千篇。本专栏精选论文重点解读&#xff0c;主题还是围绕着行业实践和工程量产。若在某个环节出现卡点&#xff0c;可以回到大模型必备腔调重新阅读。而最新科技&#xff08;Mamba,xLSTM,KAN&#xff09;则提供了大模型领域最新技…
阅读更多...
探索微软Edge开发者工具：优化前端开发的艺术与科学

探索微软Edge开发者工具：优化前端开发的艺术与科学

探索微软Edge开发者工具&#xff1a;优化前端开发的艺术与科学 引言&#xff1a;Edge开发者工具概览一、基础操作&#xff1a;步入DevTools的大门1.1 启动与界面布局1.2 快速导航与定制 二、元素审查与样式调整2.1 精准元素选取2.2 实时CSS编辑2.3 自动完成与内联文档 三、Java…
阅读更多...
Spring Web MVC(2)

Spring Web MVC(2)

响应 Http响应的结果可以是数据也可以是静态页面可以针对响应设置状态码 Header信息 返回静态页面注解RestController和Controller 我们创建一个前端页面 package com.example.demo.demos.web.controller;import org.springframework.web.bind.annotation.RequestMapping; i…
阅读更多...
最新文章

Copyright @ 2022~2023