【数据结构专题】2.1 【逻辑】线性表定义与基本操作

线性表的定义

提示：

补充一个数学概念：

序偶，也叫有序对，是指由两个元素组成的序列，且这两个元素的顺序非常重要。

通常写作：(a, b)

• a 称为第一分量（First component）。
• b 称为第二分量（Second component）。

二元组的表示方法：

线性表是一个逻辑上的定义，后面讲的顺序表+链表是对其逻辑上的物理实现

“逻辑定义”存在的意义：它屏蔽了底层的实现细节，让程序员可以更专注于业务逻辑。

概念：

a_i 是线性表中第i个元素在线性表中的逻辑位序

a_1是表头元素，a_n是表尾元素

线性表元素n=0时候定义为空表

a_(i-1)为a_i的直接前驱元素，a_(i+1)是a_i的直接后继元素

除第一个元素外，每个元素有且仅有一个直接前驱； 除最后一个元素外， 每个元素有且仅有一个直接后继

一个数据元素可以由若干个数据项组成，在这种复杂线性表的情况下，常把数据元素称作为记录。含有大量记录的线性表称作为文件。

（下面内容按数据元素算）

相同数据类型 也可以用结构体自定义一个；

对于定义的Tips:

1. 每个数据元素占的空间一样大
2. 有次序
3. 必须是有限的数据元素

线性表的基本操作

传入参数为何要用引用型：对参数的修改结果需要带回来

我们想要把值带回来通常有两种 一种是指针 一种是引用

指针在内存中单独分出来一块空间存放着对应你要调用空间的地址。

引用是一个别名 实际上用的就是你要修改的那个元素的空间

那同样都可以把值传递到main函数为什么在线性表中我们要更多的使用引用而不是指针？

1. 指针安全风险很高，直接请求的是地址，而引用使用的是名字进行访问（自动进行映射）

2. 引用写法更像正常变量的操作 可以减少对逻辑的干扰
3. 因为顺序表是一整块连续的内存。我们操作它时，通常是想改表里的数据或长度。用引用 (SqList &L)：直接用名字 L.length 修改，代码读起来就像在读课本上的伪代码，非常顺滑。 相比之下链表就必须使用指针，因为链式结构数据是散落分布的，所以我们要指向新的地址就不得不使用指针。

对于函数传参什么时候要引用：

• 传值（不用引用）：函数得到了一个新名字，对应一块新地址（副本）。你改这个新地址，原地址不动。
• 传引用（用名字）：函数得到了一个新名字，但对应的是旧地址（原件）。你改这个新名字，原地址里的东西就真变了。

建议：

如果这个函数运行完了，我希望 main 函数里的那个表发生变化吗？

• 希望变 必须加引用 &。
• 不希望变（或者无所谓）可以不加，但为了跑得快，通常还是加个 const &。

const & 常量引用：

提示：

概念辨析：

线性表的存储空间长度：数组长度

线性表长度是线性表中数据元素的个数。

任何时刻，线性表长度要小于等于数组长度。