数据结构：第二章 线性表

1、二、线性表2.1 线性表的逻辑结构2.1.1 线性表的定义二、线性表线性结构的基本特征为: 集合中必存在唯一的一个“第一元素” 集合中必存在唯一的一个 “最后元素” 除最后元素之外，均有 唯一的后继 除第一元素之外，均有 唯一的前驱n个数据元素的有限序列ABECFGD典型的线性表的应用二、线性表二、线性表2.2 线性表的顺序表示和实现2.2.1 顺序存储结构的定义二、线性表 0 i-2 i-1 n-1 a1 ai-1 ai an kLoc(ai)Loc(a1)元素位置线性表的顺序存储的表示二、线性表2.2.2 线性表的顺序存储上的基本操作实现1.顺序线性表的数据插入操作二、线性表从最末尾元素开

2、始依次将前一个元素的值存于后一个空间注意边界条件时间复杂度：O(n)二、线性表2.顺序线性表的数据删除操作依次将后一个元素的值存于前一个空间二、线性表时间复杂度：O(n)二、线性表3.顺序线性表的定位操作时间复杂度：O(n)二、线性表5.顺序线性表的取元素操作时间复杂度：O(1)二、线性表6.顺序线性表的输出操作时间复杂度：O(n)二、线性表线性表的顺序存储上的基本运算的测试二、线性表7. 两线性表的归并操作(算法2.2)二、线性表7. 两线性表的归并操作(算法2.2)二、线性表时间复杂度：O(n+m)二、线性表LA中剩余的元素放入LC中LB中剩余的元素放入LC中二、线性表算法2.1 编写函数

3、实现求两线性表的并集 void Union(SeqList &La, SeqList &Lb);二、线性表2.2.3 线性表顺序存储的特点二、线性表练习：1.编写函数实现求两线性表的交集 SeqList InterSection(SeqList &La, SeqList &Lb);二、线性表2.3 线性表的链式表示和实现2.3.1 单链表用任意的存储单元存储数据元素，每个元素由结点(Node)构成。data存储节点值（数据域），next存储元素的后继节点的地址（指针域）结点可以连续，可以不连续存储链表可扩充链表的头指针head指向链表的第一个节点（可能是头结点）data nexta0a1a2a

4、3a4head二、线性表free(a) 可利用存储空间a0a2a1a3freehead(b) 经过一段运行后的单链表结构单链表的存储映像:借助指针域，可以使得逻辑上相邻的元素在物理位置上不用相连。二、线性表带头节点的单链表头结点数据域不存储任何信息，也可以存储表长等信息，头节点的指针域指向第一个元素节点。二、线性表带头结点的单链表的存储结构二、线性表单链表上的基本运算带头节点的空单链表的构造函数头指针二、线性表4.建立单链表(1)头插法建表二、线性表二、线性表注意(1)语句必须在(2)语句之前，因为若调换了两者的位置，(2)语句改后的head-next已经不是之前的指向值了。二、线性表(2) 尾插法建表二、线性表表收尾二、线性表1.取元素二、线性表2.插入元素二、线性表二、线性表3.删除元素二、线性表二、线性表练习：1.实现单链表求表长的成员函数；2.实现单链表清空的成员函数；headqheadheadqqheada0a1a1a2a2a2二、线性表练习：3.实现两个非递增的单链表的合并，合并后的单链表是个递增链表。LinkList Merge(LinkList &L1,LinkList &L2);4.实现某带头节点的单链表的逆序操作。二、线性表2.3.2 双向链表双向链表是一种对称结构，显然有:p-next-prior=p-pr