chapter21-22顺序表

1、 第2章 线性表 2.1 线性表的概念线性表的概念 2.2 顺序表顺序表 2.3 链表链表 第2章 线性表 唯一头元素唯一头元素 唯一尾元素唯一尾元素 除头元素外，均有一个直接前驱除头元素外，均有一个直接前驱 除尾元素外，均有一个直接后继除尾元素外，均有一个直接后继 线性结构特点线性结构特点: OOOOO线性线性 头头尾尾 1 2 3 4 5 线性表 第2章 线性表 具有反对称性和传递性具有反对称性和传递性 1. 线性表的语言定义线性表的语言定义 线性表是线性表是n个数据元素的有限序列。个数据元素的有限序列。 例，例，英文字母表英文字母表 (A，B，C，Z) 线性表中的数据元素可以由若干个数据

2、项组成。线性表中的数据元素可以由若干个数据项组成。 例，例，包含大量记录的登记表包含大量记录的登记表 线性表的定义 第2章 线性表 2. 线性表的形式定义线性表的形式定义 其中其中a1 1是头元素，是头元素， an是尾元素，是尾元素， ai是第是第i个元素。个元素。 ai-1 -1是 是ai的直接前驱，的直接前驱， ai是是ai-1 -1的直接后继。 的直接后继。 当当2in时，时， ai有且只有一个直接前驱。有且只有一个直接前驱。 当当1 1in-1-1时，时， ai有且只有一个直接后继。有且只有一个直接后继。 线性表可以表示为线性表可以表示为 n 个数据元素的有限序列个数据元素的有限序列:

3、 (a1 1，ai-1 -1， ，ai，an) 线性表的定义 第2章 线性表 线性表 主要知识点主要知识点 线性表抽象数据类型线性表抽象数据类型 顺序表顺序表 链表链表 栈栈 队列队列 字符串字符串 应用举例应用举例 第2章 线性表 线性表抽象数据类型 数据集合数据集合: a0, a1, , an-1 , ai的数据类型为的数据类型为DataType 操作集合操作集合: (1) Clear() 置空线性表置空线性表 (2) Append(T value) 在表尾添加元素在表尾添加元素 (3) Insert(int p, T value) 插入数据元素插入数据元素 (4) Delete(int

4、p) 删除数据元素删除数据元素 (5) GetValue(int p, T 第2章 线性表 多维数组 数组（数组（ArrayArray）是数量和元素类型固定的有序）是数量和元素类型固定的有序 序列序列 静态数组必须在定义它的时候指定其大小和类型静态数组必须在定义它的时候指定其大小和类型 动态数组可以在程序运行才分配内存空间动态数组可以在程序运行才分配内存空间 第2章 线性表 基本概念（续） 多维数组（多维数组（Multi-arrayMulti-array）是向量的扩充）是向量的扩充 向量的向量就组成了多维数组向量的向量就组成了多维数组 可以表示为：可以表示为： ELEM AcELEM Ac1

5、1.d.d1 1cc2 2.d.d2 2 ccn n.d.dn n c ci i和和d di i是各维下标的下界和上界。所以其元素个数是各维下标的下界和上界。所以其元素个数 为：为： n i ii cd 1 ) 1( 第2章 线性表 数组的空间结构 第2章 线性表 数组的存储 多维数组的逻辑特征：一个元素可能有多个直接前驱多维数组的逻辑特征：一个元素可能有多个直接前驱 和多个直接后继。和多个直接后继。 内存是一维的，所以数组的存储也只能是一维的内存是一维的，所以数组的存储也只能是一维的 数组顺序表数组顺序表 以行为主序（也称为以行为主序（也称为“行优先行优先”） 以列为主序（也称为以列为主序（

6、也称为“列优先列优先”） X= 1 2 3 4 5 6 7 8 9 第2章 线性表 以列序为主序以列序为主序 a00 a10 am-1 -1,0 a01 a11 am-1 -1,1 1 a0,n-1 -1 am-1 -1,n-1-1 a1 1,n-1 -1 0 1 n-1 -1 a00 a01 a02 a0,n-1 -1 a10 a11 a12 a1 1,n-1 -1 am-1 -1,0 am-1-1,1 1 am-1-1,2 am-1-1,n-1-1 . . . . . . . . . . . . . . . . . . . . . Am n 第2章 线性表 以行序为主序以行序为主序 a00

7、 a01 a0,n-1 -1 a10 a11 a1 1,n-1 -1 am-1 -1,0 0 am-1 -1,n-1-1 am-1 -1,1 1 0 1 m-1 -1 a00 a01 a02 a0,n-1 -1 a10 a11 a12 a1 1,n-1 -1 am-1 -1,0 am-1-1,1 1 am-1-1,2 am-1-1,n-1-1 . . . . . . . . . . . . . . . . . . . . . Am n 第2章 线性表 对于数组，一旦规定了维数和维界，如何计算数组元素的存储位置。对于数组，一旦规定了维数和维界，如何计算数组元素的存储位置。 a00 a01 a0,

8、n-1 -1 a10 a11 a1 1,n-1 -1 am-1 -1,0 0 am-1 -1,n-1-1 am-1 -1,1 1 0 1 m-1 -1 设数组以设数组以行序行序为主序。为主序。 设二维数组设二维数组 A(mn) 其数组元素其数组元素 aij 的存储位置为的存储位置为 LOC(i，j) = LOC(0，0) 其中，其中，LOC(0，0)是是a00的存储位置；的存储位置； L是每个数组元素占用的存储单元数；是每个数组元素占用的存储单元数； L 例，例，LOC(1，1) = LOC(0，0) + ( n1 + 1 ) L + ( ni + j ) L 第2章 线性表 线性表的链式存储

9、结构线性表的链式存储结构的特点是：的特点是： u 用一组用一组任意任意的存储单元存储线性表的数据元素。的存储单元存储线性表的数据元素。 u 存储单元可以是连续的，也可以是不连续的。存储单元可以是连续的，也可以是不连续的。 链 表 第2章 线性表 结点结点: 两部分信息组成，存储数据元素信息的两部分信息组成，存储数据元素信息的数据域数据域， 存储直接后继存储位置信息的存储直接后继存储位置信息的指针域指针域。 datanext 数据域数据域，存放数据信息，存放数据信息 指针域指针域，指向下一个数据单元，指向下一个数据单元 单链表 第2章 线性表 head: 头指针头指针，指向链表中第一个结点。，指

10、向链表中第一个结点。tail:尾指针尾指针 0: 空指针空指针，有时也表示为，有时也表示为“NULL”或或“”。 头结点头结点: 记录线性表的某些性质信息记录线性表的某些性质信息(如长度如长度)。 单链表 a1a2 0an head tail a1a2 0an head tail 第2章 线性表 typedef struct LinkNode ELEM data ； ListNode * next ； ； 空表空表: a1a2 0an head tail 0 head tail 第2章 线性表 单链表特点 缺点：缺点： 不可随机存取表中任意数据元素不可随机存取表中任意数据元素 不可直接获取线性

11、表的长度不可直接获取线性表的长度 优点：优点： 插入、删除方便插入、删除方便 第2章 线性表 例，例，取第取第i=3个元素。个元素。 p = L- -next j = 1 p = p- -next j = 2 p = p- -next j = 3 e = p- -data = Sun 时间复杂度时间复杂度:O(n) ZhaoQian0Li L Sun tail 第2章 线性表 优点优点: 数据元素的数据元素的插入、删除插入、删除相对方便相对方便 在在a，b之间插入元素之间插入元素x : ab p xs s- -next = p- -next p- -next= s 第2章 线性表 删除元素删除

12、元素b : ac p b q=p- -next p - -next = p - -next - -next ? p- -next = q- -next q = p- -next 第2章 线性表 单链表操作 将两个有序单链表合并为一个有序单链表将两个有序单链表合并为一个有序单链表 通过比较不断后移指针合并链表。通过比较不断后移指针合并链表。 第2章 线性表 pa = La- -next ； pb = Lb- -next ；/分别指向第一个结点分别指向第一个结点 pc- -next = pa ? pa : pb ；/处理剩余部分处理剩余部分 while ( pa & pb ) if ( pa- -

13、data data ) pc- -next = pa ；pc = pa ；pa = pa- -next； else pc- -next = pb ；pc = pb ；pb = pb- -next ； void MergeList_L (LinkList &La，LinkList &Lb，LinkList &Lc) Lc = pc = La ； delete Lb ； 第2章 线性表 2135 0 Lb 0627 La 6789 Lcpa pb , pcpa pc pb Lc pc pb pa Lc pc pa pb Lc pb pa pc Lc 第2章 线性表 双链表 双链表的结点有双链表的结

14、点有两个指针域两个指针域: 一个指向直接后继，一个指向直接后继， 一个指向直接前驱。一个指向直接前驱。 priordatanext 第2章 线性表 性质性质: 设设d 是指向某个结点的指针，则有是指向某个结点的指针，则有 d d- -next- -prior = d- -prior- -next= d 操作操作: 只涉及单向的操作基本相同，但只涉及单向的操作基本相同，但插入、删除插入、删除操操 作变化很大。作变化很大。 空表空表: head ACheadB tail tail 第2章 线性表 1) 插入插入 AB X s p 1. 找到要在之前插入的结点，找到要在之前插入的结点，p记录。记录。 2. s-prior= p-prior ； 3. p-prior-next-next= s ； 4. s-next = p ； 5. p-prior= s ； 第2章 线性表 2) 删除删除 ACB 1. 找到要删除的结点，找到要删除的结点，p记录。记录。 p 2. p-prior-next-next = p-next-next ； 3. p-next-prior= p-prior ； 4. delete p ； 第2章 线性表 表中最后一个节点的指针域指向头结点，形