算法与数据结构-线性表

本文主要是介绍算法与数据结构-线性表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

#线性表的定义

由n（n≥0）个数据元素（节点） $a_1,a_2,...a_n$ 组成的有限序列。该序列中的所有节点具有相同的数据类型。其中数据元素的个数n称为线性表的长度。
当n=0时，称为空表。
当n>0时，将非空的线性表记作： $a_1,a_2,...,a_n）,a_1$ 称为线性表的第一个（首）节点， $a_n$ 称为线性表的最后一个（尾）节点。
$ a_1,a_2,…a_{i-1} $都是$ a_i（2≤i≤n） $的 ‘ 前驱 ‘ ，其中$ a_{i-1} $是$ a_i $的 ‘ 直接前驱 ‘ ；$ a_{i+1}，a_{i+2}，…a_n $都是$ a_i（1≤i≤n-1） $的 ‘ 后继 ‘ ，其中$ a_{i+1} $是$ a_i $KaTeX parse error: Expected 'EOF', got '#' at position 10: 的`直接后继`。 #̲线性表的抽象数据类型 ADT \dots$ D={a_i|a_i∈ElemSet,i=1,…,n,n≥0}$
数据关系： $R=\{<a_{i-1},a_i>|a_{i-1},a_i∈D,i=2,3,...n\}$
基本操作：
InitList（&L）
操作结果：构造一个空的线性表L；
ListLength（L）
初始条件：线性表L已存在；
操作结果：若L为空表，则返回TRUE，否则返回FALSE；
…
GetEleme（L,i,&e）
初始条件：线性表L已存在，1≤i≤ListLength（L）;
操作结果：用e返回L中第i个数据元素的值；
ListInsert(L,i,&e)
初始条件：线性表L已存在，1≤i≤ListLength（L）;
操作结果：在线性表L中的第i个位置插入元素e;
…
}ADT List
#线性表的顺序存储

存储结构

顺序存储：把线性表的节点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。
顺序存储 的线性表的特点：
1）线性表的逻辑顺序与物理顺序一致；
2）数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。

基本操作
初始化
插入

在线性表 $L=(a_1,...,a_{i-1},a_i,a_{i+1},...,a_n)$ 中的第i(1≤i≤n)个位置上插入一个新节点e,使其成为线性表：
$L=(a_1,...,a_{i-1},e,a_i,a_{i+1},...,a_n)$
实现步骤：
（1）将线性表L中的第i个至第n个节点后移一个位置
（2）将节点e插入到节点 $a_{i-1}$ 之后
（3）线性表长度加1

删除

在线性表 $L=(a_1,...,a_{i-1},a_i,a_{i+1},...,a_n)$ 中删除节点 $a_i$ (1≤i≤n),使其成为线性表： $L=(a_1,...,a_{i-1},a_{i+1},...,a_n)$
实现步骤：
（1）将线性表L中的第i+1个至第n个节点依次向前移动一个位置
（2）线性表长度减1

#线性表的链式存储

存储结构

用一组任意的存储单元存储线性表中的数据元素。用这种方法存储的线性表简称线性链表。
存储链表中节点的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。
链表中节点的逻辑顺序和物理顺序不一定相同。
链表是通过每个节点的指针域将线性表的n个节点按其逻辑次序链接在一起的。