数据结构与算法：第二章（线性表）
一、线性表的概念
1、线性表的结构特点是数据之间的逻辑关系是线性关系。
2、线性结构是数据元素间约束力最强的一种数据结构： 在非空线性结构的有限集合中，存在唯一一个被称 为“第一个”的数据元素；存在唯一一个被称为 “最后一个”的数据元素；除“第一个”元素无前 驱外，集合中的每个元素均有且只有一个“直接” 前驱；除“最后一个”元素无后继外，集合中每个 数据元素均有且只有一个“直接”后继。
线性表的概念和术语：
1．线性表（Linear_List）是具有相同数据类型 的 n(n ≥ 0) 个数据元素的有限序列，通常记为： (a 0 ，a 1 ，… ，a i−1 ，a i ，a i+1 ，…，a n−1 ) 表中相邻元素之间存在着顺序关系，a i−1 先于 a i ， a i 先于 a i+1 ，称 a i−1 是 a i 的前驱， a i+1 是 a i 的后继。 就是说：在这个集合中，除了 a 0 和 a n−1 外，每个 元素都有唯一的前趋和后继。而 a 0 是表中第一个 元素，只有后继没有前驱；a n−1 是最后一个元素， 只有前驱没有后继。
2．线性表中元素的个数 n(n ≥ 0) 称为线性表的长 度，当 n = 0 时称为空表。
3．a0称为首结点，an−1称为尾结点。
4．在非空线性表中每个元素有一个确定位置，设
ai(0 ≤ i ≤ n − 1) 是线性表中的元素，则称 i 为数据 元素 a i 在线性表中的位序（位置）。
线性表的抽象数据类型
线性表的储存结构
分类：
线性表的顺序储存：
顺序表用物理上的相邻（内存中的地址空间是线性的）实现数据元素之间的逻辑相邻关系。假定线性表的每个元素 占L个存储单元，若知道第一个元素的地址（基地址）为Loc(a0)，则位序为i的元素的地址为：
Loc ai= Loc a0+i ∗ L 0 ≤ i ≤ n − 1
只要已知顺序表首地址 Loc(a 0 ) 和每个数据元素的大小 L 就可通过上述公式求出位序为i的元素的地址，时间复杂 度为 O(1)，因此顺序表具有按数据元素的序号随机存取 的特点，在C++语言中可用一维数组来实现定长的线性存储结构。
顺序表的类型定义
二、线性表上基本运算的实现
}
}
}
5．求前驱和后继
◼算法思想：求顺序表中位序为i的元素的前驱和后 继，若 i0，则为第一个元素无前驱，否则其 前驱是 data[i-1]；若 icurLength-1，则为 最后一个元素无后继，否则其后继是 data[i+1] 。通过元素的下标可以直接定位其前驱和后继， 算法的时间复杂度为O(1)。
顺序表的插入图示
}
本算法中要注意以下问题：
(1) 检验插入位置的有效性，这里 i 的有效范围是： 0≤i≤curLength，注意：在表尾元素data[curLength-1] 的后面插入元素成为新的表尾是合法的。
(2) 检查表空间是否满了，在表满的情况下不能再做插入， 否则产生溢出错误。此时有两种解决方法：一种是不执行插 入，报错后退出；另一种是扩大数组的容量。本书采用第二 种方法。
(3) 注意数据的移动方向，最先移动的是表尾元素。
插入算法的时间复杂度分析
顺序表的删除图示
}
本算法中要注意以下问题：
(1) 检查删除位置的有效性。i的取值范围为：0 ≤ ???? ≤ ???? − 1。
(2) 顺序表为空时不能做删除，当顺序表为空时 curLength的值为0，代码2.6中的判别条件 ???? < 0||???? > ????????????????????????????????ℎ − 1 隐含了对表为空的检查。
(3) 删除a i 之后，该数据被覆盖，如果需要保留它的 值，则先取出a i ，再做删除。
删除算法的时间复杂度分析
}
10．合并顺序表
◼ 顺序表A与B的结点关键字为整数，A表与B表的元素均非 递减有序，试给出一种高效的算法，将B表中元素合并到 A表中，使新的A表的元素仍保持非递减有序，高效指最 大限度的避免移动元素。
}
顺序表的特点
◼ (1) 顺序表需要预先分配存储空间，很难恰当预留空间， 分配大了造成浪费，分配小了对有些运算会造成溢出。
◼ (2) 由于逻辑次序和物理次序的一致性，顺序表能够按元 素序号（下标）直接存取元素具有随机存取的优点；
◼ (3) 由于要保持逻辑次序和物理次序的一致性，顺序表在 插入删除时需要移动大量的数据，因此顺序表的插入和 删除效率低；
◼ (4) 改变顺序表的大小，需要重新创建一个新的顺序表， 把原表里的数据复制到新表，然后释放原表空间。
◼ (5) 顺序表比较适合静态的、经常做定位访问的线性表。
算法举例一
◆ 已知长度为n的线性表A采用顺序存储结构， 请写一时间复杂度为0(n)、空间复杂度为 0(1)的算法，该算法删除线性表中所有值为 item的数据元素。
◆ O(1)表示算法的辅助空间为常量。
算法举例二
（ 13 分）设将n（n>1）个整数存放到一维数组R中 。试设计一个在时间和空间两方面都尽可能高效的算法，将 R中保存的序列循环左移P（0<P<n）个位置， 即将R中 的数据由（X0,X1,…,Xn-1）变换为（Xp,Xp+1,…,Xn1,X0,X1,…,Xp-1）。要求： （1）给出算法的基本设计思想。
（2）根据设计思想，采用C 或C++或JAVA 语言描述算法 ，关键之处给出注释。
（3）说明你所设计算法的时间复杂度和空间复杂度。
◼ 算法设计思想：
◼ 按照下标0到p-1、p到n-1、0到n-1的顺序，将这三 段分别逆置，最后的结果即为所求。
◼ (3)算法执行了两趟逆置，时间复杂度为O(n);用了一 个辅助变量空间，空间复杂度为O(1)。
◼ 讨论：若采用直接左移p位，空间复杂度仍为O(1)，但 时间复杂度为O(np)。
三、线性表的链接存储结构
（1）单链表：
单链表的几个概念
头结点的意义
◼头结点的出现，使得在表头位置上进行插入和删除 和在其它结点位置上是完全一致的，从而使得插入 和删除算法得到简化。
◼如，在没有头结点的单链表中插入和删除
单链表结点类型定义
}
单链表的定义
}；
说明：在上述单链表类型定义中，tail是单链表的尾指针， 指向表尾结点，如图所示。尾指针的加入使得频繁修改表尾 结点的值或后继时，无需从头遍历链表。
单链表上基本运算的实现
}
}
插入元素示意图
}
单链表带头结点，p是插入位置cur的前驱
删除结点
}
单链表带头结点，pre是删除位置p的前驱
}
总 结
◼链表的特点： (1) 不要求用地址连续的存储空间存储，每个结点在运行时 动态生成。结点的存储空间在物理位置上可以相邻，也可以 不相邻； (2) 插入和删除操作不需要移动元素，只需修改指针，满足 经常插入和删除结点的需求； (3) 链表不具备顺序表随机存取的优点； (4) 链表结点增加了指示元素间关系的指针域，空间开销比 较大。
◼ 单链表上运算的分析 1. 对一个结点操作，必先找到它，即用一个指针指向它 2. 找单链表中任一结点，都必须从第一个点开始： p = head;或 p = head->next; while (没有到达) p = p->next;
◼ 单链表的时间复杂度 ◼ 查找： O(n) ◼ 插入： O(n) + O(1) = O(n) ◼ 删除： O(n) + O(1) = O(n)
（2）双链表
◼如果某链表经常进行查找结点前驱的操作，我们希 望查找前驱的时间复杂度也达到O(1)，这时可以 用空间换时间：即每个结点再增加一个指向前驱的 指针域prior，使链表可以进行双向查找，这种链 表称为双向链表。
◼每个结点附加了两个指针字段，如prior和next
◼prior字段给出直接前驱结点的地址
◼next给出直接后继结点的地址。
双链表的头尾结点
◼为了消除在表头、表尾插入删除的特殊情况，通常 双链表设一头结点，设一尾结点
◼头结点中prior字段为空，它的next字段给出线性 表中的首结点的地址
◼尾结点中next字段为空，它的prior字段给出线性 表中最后一个节点的地址
深刻理解双向链表
Create运算
插入
删除
单循环链表
双循环链表
总 结
- 顺序表的主要优点 (1) 顺序表的实现方法简单，各种高级语言中都有数组 类型，容易实现； (2) 按序号查找可通过下标直接定位，时间代价O(1)； (3) 元素间的逻辑次序和物理存储次序一致，不需要借 助指针，不产生结构性存储开销； (4) 顺序表是存储静态数据的理想选择。
- 顺序表的主要缺点 (1) 需要预先申请固定长度的数组； (2) 插入删除运算需要移动大量的元素，时间代价O(n)
- 链表的主要优点 (1) 插入删除运算不需要移动元素，只需修改指针的指向， 时间代价O(n)；若不考虑查找，则插入删除运算时间代价 O(1)，链表比较适合经常插入删除元素的情况； (2) 动态地按照需要为表中新的元素分配存储空间，无需事 先了解线性表的长度，对线性表的长度难以估计时，采用链 表比较合适； (3) 链表是存储动态变化数据的理想选择。
- 链表的主要缺点 (1) 链表需要在每一个结点上附加指针，用以体现元素间的 逻辑关系，增加了结构性的存储开销。 (2) 按序号查找元素需要遍历链表，时间代价O(n)
总结：线性表实现方法的比较
◼顺序表
◼ 插入、删除运算时间代价O(n)，按位置查找则可常数 时间完成O (1)
◼ 预先申请固定长度的数组
◼ 如果整个数组元素很满，则没有结构性存储开销
◼链表
◼ 不考虑查找，则插入、删除运算时间代价O(1)，但找 第i个元素运算时间代价O(n)
◼ 存储利用指针，动态地按照需要为表中新的元素分配 存储空间
◼ 每个元素都有结构性存储开销