Microsoft PowerPoint - 第+2+章+线性表[check].ppt [兼容模式]

Size: px

Start display at page:

Download "Microsoft PowerPoint - 第+2+章+线性表[check].ppt [兼容模式]"

地刑
5 years ago
Views:

2 教学内容 1 线性表的定义和性质及基本运算 2 线性表的顺序存储结构 3 线性表的链式存储结构 4 多项式的代数运算

3 线性结构的特点 : 数据元素的非空有限集存在唯一的一个被称作第一个的数据元素 ; 存在唯一的一个被称作最后一个的数据元素 ; 除第一个之外的数据元素均只有一个前驱 ; 除最后一个之外的数据元素均只有一个后继例 : 法学系第一个数据元素国贸系工商系直接前驱计算机系会计系直接后继统计系外语系最后一个数据元素

4 数据结构第二章线性表 2.1 线性表的类型定义线性表 (Linear_List) : 由 n (n 0) 个数据元素 a 1, a 2,, a n 组成的有限并且有序有序的序列指线性表中的每一个元素都有自己的位置 (position) 其中数据元素的个数 n 定义为表的长度当 n=0 时称为空表非空的线性表 (n>0) 常记作 : i 为数据元素 a i 的位序 (a 1, a 2,, a i -1, a i, a i +1,, a n ) 这里的数据元素 a i (1 i n) 只是一个抽象的符号, 其具体含义在不同的情况下可以不同数据元素为字符例 1:26 个英文字母组成的字母表 :(A, B, C,, Z) 例 2: 某校从 1978 年到 1983 年各种型号的计算机拥有量的变化情况 : (6, 17, 28, 50, 92, 188) 数据元素为数字

5 例 3: 学生健康情况登记表 : 姓名学号性别年龄健康情况王小林男 18 健康陈红女 20 一般刘建平男 21 健康张立立男 17 神经衰弱文件 (file) 数据元素 ( 结点记录 ) 由 5 个数据项 ( 字段域 ) 组成线性表中的数据元素可以是各种各样的, 但同一线性表中的元素必定具有相同特性 ( 属于同一数据对象 ) 线性表中的数据元素之间存在着序偶关系 <a i 1, a i >

6 从以上例子可看出线性表 ( 非空 ) 的逻辑特征是 : 1 有且仅有一个开始结点 a 1, 它没有直接前趋, 而仅有一个直接后继 a 2, a 1 叫表头元素 ; 2 有且仅有一个终端结点 a n, 它没有直接后继, 而仅有一个直接前趋 a n -1, a n 叫表尾元素 ; 3 其余的内部结点 a i (2 i n -1) 都有且仅有一个直接前趋 a i 1 和一个直接后继 a i +1

7 抽象数据类型线性表的定义 : 参看 P19 ADT List { 数据对象 :D={ a i a i ElemSet, i = 1, 2,..., n, n 0 } 数据关系 :R1={ <a i-1, a i > a i-1, a i D, i = 2,..., n } 基本操作 :( 线性表的基本操作很多, 为讨论方便起见, 在此将它归为四类 ) { 结构初始化 } 任何数据结构在被使用之前都必须进行初始化, 它类似于编程中使用的变量都必须先有定义 InitList ( &L ) 操作结果 : 构造一个空的线性表 L

8 { 销毁结构 } 任何数据结构不再使用时都必须进行结构销毁, 其实质为释放它所占有的存储空间 DestroyList( &L ) 初始条件 : 线性表 L 已存在操作结果 : 销毁线性表 L { 引用型操作 } ListEmpty( L ) 初始条件 : 线性表 L 已存在操作的结果不改变线性表中的数据元素, 也不改变数据元素之间的关系操作结果 : 若 L 为空表, 则返回 TRUE, 否则返回 FALSE

9 ListLength( L ) 初始条件 : 线性表 L 已存在操作结果 : 返回 L 中元素个数 PriorElem( L, cur_e, &pre_e ) 若 cur_e 是线性表 L 中第一个数据元素, 则它的前驱 pre_e 为空元素初始条件 : 线性表 L 已存在操作结果 : 若 cur_e 是 L 中的数据元素若 cur_e, 则用是线性表 pre_e e 返回 L 中最后一个数据元素, 则它的前驱, 否则操作失败它的后继,pre_e next_e 无定义为空 NextElem( L, cur_e, &next_e ) 元素初始条件 : 线性表 L 已存在操作结果 : 若 cur_e 是 L 中的数据元素, 则用 next_e 返回它的后继, 否则操作失败,next_e 无定义

10 GetElem( L, i, &e ) 初始条件 : 线性表 L 已存在,1 i LengthList(L) 操作结果 : 用 e 返回 L 中第 i 个元素的值 LocateElem( L, e, compare( ) ) 初始条件 : 线性表 L 已存在,compare( ) 是元素判定函数操作结果 : 返回 L 中第 1 个与 e 满足关系 compare( ) 的元素的位序若这样的元素不存在, 则返回 0 此操作通常称为定位函数, 这是一种广义的定位函数写法, 以 compare() 作为判定的条件, 参数 e 和线性表中数据元素具有相同类型较多场合是以相等作为判定条件, 此时可省略函数参数, 且操作结果为 : 若线性表中存在与 e 值相同的数据元素, 则返回第一个这样的元素在表中的位序, 否则返回函数值为 0

11 ListTraverse(L, visit( )) 初始条件 : 线性表 L 已存在,visit( ) 为元素的访问函数操作结果 : 依次对 L 的每个元素调用函数 visit( ) 一旦 visit( ) 失败, 则操作失败 visit() 亦为函数参数, 常见的情况是依次输出表中元素的值, 同样在这种情况下, 通常的写法也是省略省略函数参数 { 加工型操作 } 操作的结果或修改表中的数据元素, 或修改元素之间的关系 ClearList( &L ) 初始条件 : 线性表 L 已存在操作结果 : 将 L 重置为空表在对线性表 L 进行 ClearList(L) 操作之后, 仅是删除表中所有元素, 在以后的程序中仍可对它进行某些合法操作, 如判空插入等但在进行了 DestroyList(L) 操作之后, 线性表 L 不再存在, 即不能在以后的程序中再引用它

12 PutElem( &L, i, e ) 初始条件 : 线性表 L 已存在,1 i LengthList(L) 操作结果 :L 中第 i 个元素赋值为 e 的值 ListInsert( &L, i, e ) 初始条件 : 线性表 L 已存在,1 i LengthList(L)+1 操作结果 : 在 L 的第 i 个元素之前插入新的元素 e, L 的长度增 1 ListDelete( &L, i, &e ) 初始条件 : 线性表 L 已存在且非空,1 i LengthList(L) 操作结果 : 删除 L 的第 i 个元素, 并用 e 返回其值, L 的长度减 1 } ADT List

13 注上述各个操作目前还无法在程序设计中加以引用但如果已经实现了上述定义的线性表类型, 那么在应用问题的求解中就可以用这些操作实现应用问题的算法设计例 2-1: 已知集合 A 和 B, 求这两个集合的并集, 使 A=A B, 且 B 不再单独存在要在计算机中求解, 首先要确定如何表示集合用线性表表示集合以线性表 LA 和 LB 分别表示集合 A 和 B, 两个线性表的数据元素分别为集合 A 和 B 中的成员由此, 上述集合求并的问题便可演绎为 : 扩大线性表 LA, 将存在于线性表 LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去

14 思路 : 1. 从 LB 中取出取出一个数据元素 ; 2. 依值在 LA 中进行查询 ; GetElem ( LB, i, &e ) ListDelete (&LB, i, &e ) LocateElem ( LA, e, equal()) 3. 若不存在, 则插入插入之 ListInsert t ( &LA, n +1 1, e ) 重复上述三步直至 LB 中的数据元素取完为止其中的每一步能否利用线性表类型中定义的基本操作来完成呢?

$算法 2.1 void union(list &La, List Lb) { La_len = ListLength(La); Lb_len =ListLength(Lb); // 求线性表的长度 for (i = 1; i <= Lb_len; i ++) 假设执行时间与表长无关 { GetElem ListDelete (Lb, (&LB, i,&e); &e ) // 取 Lb 中第$

15 算法 2.1 void union(list &La, List Lb) { La_len = ListLength(La); Lb_len =ListLength(Lb); // 求线性表的长度 for (i = 1; i <= Lb_len; i ++) 假设执行时间与表长无关 { GetElem ListDelete (Lb, (&LB, i,&e); &e ) // 取 Lb 中第 i 个数据元素赋给 e if(!locateelem (La, e, equal())) ListInsert (&La, ++La_len, e); // La 中不存在和 e 相同的数据元素, 则插入之 } 执行时间与表长成正比 DestroyList (LB); // 销毁线性表 LB } // union 时间复杂度 :O(ListLength (La) ListLength (Lb))

16 例 2-2: 归并两个其数据元素按值非递减有序排列的线性表 La 和 Lb, 求得线性表 Lc 也具有同样特性设 La = (3, 5, 8, 11) Lb = (2, 6, 8, 9, 11, 15, 20) 则 Lc = ( ) (2, 3, 5, 6, 8, 8, 9, 11, 11, 15, 20) 思路 : 1. 分别从 La 和 Lb 中取得当前元素 a i 和 b j ; 2. 若 a i b j, 则将 a i 插入到 Lc 中, 否则将 b j 插入到 Lc 中

17 算法 2.2 void MergeList(List La, List Lb, List &Lc) { InitList(&Lc); 假设执行时间与表长无关 i = j = 1; k = 0; La_len = ListLength(La); Lb_len = ListLength(Lb); while ((i La_len) && ( j Lb_len)) { // La 和 Lb 均未取完 GetElem(La, i, a i ); GetElem(Lb, j, b j ); if (a i b j ) {ListInsert(Lc, ++k, a i ); ++i; } else { ListInsert(Lc, ++k, b j ); ++j; } } while (i La_len) {GetElem(La, i++, a i ); ListInsert(Lc, ++k, a i );} while (j Lb_len) {GetElem(Lb, j++, b j ); ListInsert(Lc, ++k, b j );} } 时间复杂度 :O(ListLength(La) + ListLength(Lb))

18 在实际的程序设计中要引用线性表的基本操作, 必须先实现先实现线性表类型确定存储结构实现基本操作

19 2.2 线性表的顺序表示和实现在计算机中用一组地址连续地址连续的存储单元依次存储依次存储线性表的各个数据元素, 称作线性表的顺序存储结构或顺序映象用这种方法存储的线性表称作顺序表

20 例如 : 线性表 (1, 2, 3, 4, 5, 6) 的存储结构 : 依次存储, 地址连续中间没有空出存储单元是一个典型的线形表顺序存储结构线形表顺序存储结构存储结构 : 地址不连续中间存在空的存储单元不是一个线形表顺序存储结构线形表顺序存储结构

21 顺序表中元素存储位置的计算 : 线性表的第 1 个数据元素 a 1 的存储位置, 称作线性表的起始位置或基地址 a 1 a 2 a i-1 a i a i+1 a n 基地址假设线性表的每个元素需占 l 个存储单元, 则第 i +1 个数据元素的存储位置和第 i 个数据元素的存储位置之间满足关系 : LOC(a i +1 ) = LOC(a i ) + l 由此, 所有数据元素的存储位置均可由第一个数据元素的存储位置得到 : LOC(a i ) = LOC(a 1 ) + (i -1) l 基地址

22 线性表顺序存储结构的图示 : 存储地址 LOC(a 1 ) LOC(a 1 )+l LOC(a 1 )+(i -1) l LOC(a 1 )+(n -1) l LOC(a 1 )+n l LOC(a 1 )+(maxlen-1) l 内存状态 a 1 a 2 a i a n 数据元素在线性表中的位序空闲 1 2 i 顺序表的特点 : 以物理位置相邻表示逻辑关系任一元素均可随机存取 ( 优点 ) n 顺序表在机器内存中的物理状态本课程在高级语言层次讨论数据结构的实现方法需用高级语言已经实现的数据类型描述存储结构

23 地址连续一维数组的定义方式 : 依次存放类型说明符数组名 [ 常量表达式用一维数组 ] 顺序表 ( 元素 ) 数组 ( 元素 ) 随机存取说明 : 常量表达式中可以包含常量和表示顺序表类型相同符号常量, 不能包含变量即 C 不允许对数组的大小作动态定义线性表长可变 ( 删除 ) 用一变量表示顺序表的长度属性数组长度不可动态定义 #define LIST_INIT_SIZE 100 // 线性表存储空间的初始分配量 typedef struct { ElemType elem[list_init_size]; int length; // 当前长度 } SqList;

24 考虑到线性表因插入元素而使存储空间不足的问题, 应允许数组容量进行动态扩充 #define LIST_INIT_SIZE 100 // 线性表存储空间的初始分配量 #define LISTINCREMENT 10 // 线性表存储空间的分配增量 typedef struct { ElemType *elem; // 数组指针, 指示线性表的基地址 int length; // 当前长度 int listsize; // 当前分配的存储容量 ( 以 sizeof(elemtype) 为单位 ) } SqList; 注意 C 语言中的数组下标从 0 开始, 因此若 L 是 Sqlist 类型的顺序表, 则表中第 i 个元素是 L.elem[i -1]

25 数据结构第二章线性表顺序表基本操作的实现初始化操作 : 为顺序表分配一预定义大小的数组空间, 并将线性表的当前长度设为 0 函数的类型 Status InitList_Sq (Sqlist &L) { // 构造一个空的顺序表 L L.elem = (ElemType *)malloc(list_init_size*sizeof(elemtype)); INIT SIZE*si if (! L.elem) exit(overflow); // 存储分配失败 L.lengh = 0; // 空表长度为 0 L.listsize = LIST_INIT_SIZE; // 初始存储容量 return OK; }//InitList_Sq

26 插入操作 : 线性表的插入运算是指在表的第 i (1 i n +1) 个位置上, 插入一个新结点 b, 使长度为 n 的线性表 (a 1,, a i 1, a i,, a n ) 变成长度为 n + 1 的线性表 (a 1,, a i 1, b, a i,, a n ) 算法思想 : 1) 检查 i 值是否超出所允许的范围 (1 i n + 1), 若超出, 则进行超出范围错误处理 ; 2) 将线性表的第 i 个元素和它后面的所有元素均后移一个位置 ; 3) 将新元素写入到空出的第 i 个位置上 ; 4) 使线性表的长度增

27 算法 2.4 Status ListInsert_Sq(SqList &L, int i, ElemType e) { if (i < 1 i > L.length+1) return ERROR; // 插入位置不合法 if (L.length >= L.listsize) { // 当前存储空间已满, 增加分配 newbase = (ElemType *) realloc(l.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType)); if (!newbase) exit(overflow); // 存储分配失败 L.elem = newbase; // 新基址 L.listsize i += LISTINCREMENT; // 增加存储容量 } q = &(L.elem[i -1]); // q 指示插入位置 for (p = &(L.elem[L.length-1]); p >= q; --p) *(p+1) = *p; // 插入位置及之后的元素右移 *q = e; // 插入 e ++L.length; // 表长增 1 return OK; }//ListInsert_sq

28 插入算法的时间复杂度分析 : 问题规模是表的长度, 设它的值为 n 算法的时间主要花费在向后移动元素的 for 循环语句上该语句的循环次数为 (n i + 1) 由此可看出, 所需移动结点的次数不仅依赖于表的长度 n, 而且还与插入位置 i 有关当插入位置在表尾 (i = n+1) 时, 不需要移动任何元素 ; 这是最好情况, 其时间复杂度 O(1) 当插入位置在表头 (i = 1) 时, 所有元素都要向后移动, 循环语句执行 n 次, 这是最坏情况, 其时间复杂度 O(n)

29 算法的平均时间复杂度 : 设 p i 为在第 i 个元素之前插入一个元素的概率, 则在长度为 n 的线性表中插入一个元素时所需移动元素次数的期望值为 E is n 1 i 1 p i ( n i 1) 假设在表中任何位置 (1 i n+1) 上插入结点的机会是均等的, 则 1 p i n 1 E is n 1 1 i 1 n 1 n ( n i 1) 2 由此可见, 在顺序表上做插入运算, 平均要移动表上一半元素当表长 n 较大时, 算法的效率相当低算法的平均时间复杂度为 O(n)

30 数据结构第二章线性表删除操作线性表的删除运算是指将表的第 i (1 i n) 个结点删除, 使长度为 n 的线性表 (a 1,, a i 1, a i,, a n ) 变成长度为 n -1 的线性表 (a 1,, a i 1, a i +1,, a n ) 算法思想 : 1) 检查 i 值是否超出所允许的范围 (1 i n), 若超出, 则进行超出范围错误处理 ; 2) 将线性表的第 i 个元素后面的所有元素均前移一个位置 ; 3) 使线性表的长度减

31 算法 2.5 Status ListDelete_Sq(SqList &L, int i, ElemType &e) { if ((i <1) (i > L.length)) return ERROR; // 删除位置不合法 p = &(L.elem[i -1]); // p 为被删除元素的位置 e = *p; // 被删除元素的值赋给 e q = L.elem+L.length-1; length // 表尾元素的位置 for (++p; p <= q; ; ++p) *(p-1) = *p; // 被删除元素之后的元素左移 --L.length; // 表长减 1 return OK; }//ListInsert_sq

32 删除算法的复杂度分析 : 问题规模是表的长度, 设它的值为 n 算法的时间主要花费在向前移动元素的 for 循环语句上该语句的循环次数为 (n i) 由此可看出, 所需移动结点的次数不仅依赖于表的长度 n, 而且还与删除位置 i 有关当删除位置在表尾 (i = n) 时, 不需要移动任何元素 ; 这是最好情况, 其时间复杂度 O(1) 当删除位置在表头 (i = 1) 时, 有 n -1 个元素要向前移动, 循环语句执行 n -1 次, 这是最坏情况, 其时间复杂度 O(n)

33 算法的平均时间复杂度 : 设 q i 为删除第 i 个元素的概率, 则在长度为 n 的线性表中删除一个元素时所需移动元素次数的期望值为 E dl n i 1 q i ( n i) 假设在表中任何位置 (1 i n) 删除结点的机会是均等的, 则 1 q i n n 1 n 1 E dl ( n i) n 2 i 1 由此可见, 在顺序表上做删除运算, 平均约要移动表上一半元素当表长 n 较大时, 算法的效率相当低算法的平均时间复杂度为 O(n)

34 算法 2.1 void union(list union(sqlist &La, &La, List SqList Lb) Lb) { for La_len (i i = 1; = 0; ListLength(La); i i <= < Lb.length; Lb_len; i ++) i ++) Lb_len =ListLength(Lb); { // e 求线性表的长度 = Lb.elem[i]; // 取 Lb 中第 i 个数据元素赋给 e for (i sign = 1; = i 1; <= Lb_len; i ++) { for j = 0; j < La.length; j ++) GetElem if (La.elem[j] (Lb, i,&e); = e) {sign// = 取 0; Lb break;} 中第 i 个数据元素赋给 e if(!locateelem (sign) {La.elem[La.length] (La, e, equal())) = e; ListInsert La.length++; (&La, ++La_len, } e); // La 中不存在和 e 相同的数据元素, 则插入之 } DestroyList (LB); // 销毁线性表 LB } // union

35 作业选择题部分 1 一个线性表第一个元素的存储地址是 100, 每个元素的长度为 2, 则第 5 个元素的地址是 ( ) (A)110 (B)108(C)100 (D)120 2 向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变, 平均要移动 ( ) 个元素 (A)64(B)63 (C)63.5 (D)7

36 2.3 线性表的链式表示和实现顺序表的特点 : 以物理位置相邻表示逻辑关系顺序表的优点 : 任一元素均可随机存取顺序表的缺点 : 进行插入和删除操作时, 需移动大量的元素为避免元素的移动, 我们介绍线性表的另一种存储方式, 链式存储结构, 简称为链表 (Linked List)

37 2.3.1 线性链表链表的存储方式用一组物理位置任意的存储单元来存放线性表的数据元素这组存储单元既可以是连续的, 也可以是不连续的, 甚至是零散分布在内存中的任意位置上的因此, 链表中元素的逻辑次序和物理次序不一定相同

38 例 : 线性表 : ( 赵, 钱, 孙, 李, 周, 吴, 郑, 王 ) 顺序表链表结点存储地址存储状态存储地址存储状态数据域指针域 0031 赵 0001 李钱 0007 钱 0013 链单 0035 孙 0013 孙 0001 表链 0037 李 0019 王 NULL H 0039 周 0041 吴 0043 郑 0045 王头指针 H 0031 赵钱孙李周吴郑王 ^ 0025 吴 0031 赵 0037 郑 0043 周链表指针单链表是由头指针唯一确定, 因此单链表可以用头指针的名字来命名

39 单链表的表示单链表在 C 语言中可用结构指针来描述 : typedef struct Lnode{ // 声明结点的类型和指向结点的指针类型 ElemType data; // 数据元素的类型 struct Lnode *next; // 指示结点地址的指针 }Lnode, *LinkList;

40 例 : L Struct student { char num[8]; // 数据域 char name[8]; // 数据域 num name score next 0201 丁一丁二丁三 66 int score; // 数据域 struct student *next; //next 既是 struct student 类型中的一个成 // 员, 又指向 struct student 类型的数据 }Stu_1, Stu_2, Stu_3, *LinkList; LinkList L;

41 头结点 : 在单链表的第一个结点之前人为地附设的一个结点头结点数据域指针域不存放任何数据存放附加信息 ( 链表的结点个数等 ) 存放第一个结点的地址 ( 若线性表为空表, 则空, 用 ^ 表示 ) 头指针存放头结点的地址 L a 1 a 2 a n ^ L ^ 头指针头结点

42 讨论 1. 在链表中设置头结点有什么好处? 头结点即在链表的首元结点之前附设的一个结点, 该结点的数据域中不存储线性表的数据元素, 其作用是为了对链表进行操作时, 可以对空表非空表的情况以及对首元结点进行统一处理, 编程更方便

43 单链表的基本操作 1 查找运算按序号查找 (GetElem(L, i, &e) 在链表中的实现 ) 在单链表中, 即使知道被访问结点的序号 i, 也不能象顺序表中那样直接按序号 i 访问结点, 而只能从头指针出发, 顺链域 next 逐个结点往下搜索, 直到搜索到第 i 个结点为止因此, 单链表是非随机存取的存储结构

44 设单链表的长度为 n, 要查找表中第 i 个结点, 仅当 1 i n 时,i 的值是合法的其算法如下 : 算法 2.8 Status GetElem_L(LinkList L, int i, ElemType &e) { p = L next; j = 1; // 初始化,p 指向第一个结点,j 为计数器 while ( p && j < i ) { p = p next; ++j; } if (!p j > i ) return ERROR; // 第 i 个元素不存在 e = p data; // 取第 i 个元素 return OK; } // GetElem_L 算法的时间复杂度为 :O(n)

45 按值查找按值查找是在单链表中查找结点值等于给定值 key 的结点, 若有的话, 则返回首次找到的其值为 key 的结点的存储位置 ; 否则返回 NULL 其算法如下: Status GetElem_L1(LinkList L1, ElemType key) { p = L1 next; while ( p && p data!=key) p = p next; return p; } // GetElem_L1 该算法的执行时间与 key 有关, 时间复杂度为 :O(n)

46 2 插入运算 (ListInsert(&L, i, e) 在链表中的实现 ) 步骤 : 1 首先找到 a i -1 的存储位置 p 2 生成一个数据域为 x 的新结点 3 插入新结点:1 结点 a i 1 的指针域指向新结点 2 新结点的指针域指向结点 a i p a i 1 s x s next = p next; p next = s; a i

47 算法 2.9 Status ListInsert_L(LinkList L, int i, ElemType e) { p = L; j = 0; while ( p && j < i -1) { p = p next; ++j; } // 寻找第 i 1 个结点 if (!p j > i -1) return ERROR; // i 小于 1 或者大于表长 s = (LinkList) malloc ( sizeof (LNode)); // 生成新结点 s data = e; s next = p next; // 插入 L 中 p next = s; return OK; } // LinstInsert_L 时间复杂度 :O(n)

48 3 删除运算 (ListDelete(&L, i, &e) 在链表中的实现 ) 步骤 : 1 首先找到 a i 1 的存储位置 p 2 令 p next 指向 a i+1 3 释放结点 a i 的空间 p a i 1 a i a i+1 p next = p next next;

49 Status ListDelete_L(LinkList L, int i, ElemType &e) { p = L; j = 0; 算法 2.10 while ( p next && j < i 1) { p = p next; ++j; } if (!(p next) j > i 1) return ERROR; // 删除位置不合理 q=p next; p next = q next; // 删除并释放结点 e = q data; free(q); return OK; } // ListDelete_L 时间复杂度为 :O(n) 在链表上实现插入和删除运算, 无须移动结点, 仅需修改指针

50 4 建立单链表因为每个新生成的结点的插入位置在表尾 ( 头插法建表逆序建表 ), 则算法如果是顺序创建单链表, 那么算法该如何写呢? 中必须维持一个始终指向已建立的链表表尾的指针从一个空表开始, 逐个将新结点插入到当前链表的表头上算法 2.11 void CreateList_L(LinkList &L, int n) { // 逆位序输入 n 个元素的值, 建立带表头结点的单链线性表 L L = (LinkList) malloc (sizeof (LNode)); L next = NULL; // 先建立一个带头结点的单链表初始化 for (i = n; i > 0; --i) { p = (LinkList) malloc (sizeof (LNode)); // 生成新结点 scanf(&p data); // 输入元素值 p next = L next; L next = p; // 插入到表头 } } // CreateList_L 算法的时间复杂度为 :O(n)

51 数据结构第二章线性表 5 销毁单链表 void DestroyList(LinkList &L) { // 销毁以 L 为头指针的单链表, 释放链表中所有结点空间 while (L) { 为什么要加上 L=NULL 的语句? p = L; 虽然头结点占有的空间已经 L = L next; 释放, 但指针变量 L 中的值没有 free(p); 变, 为安全起见, 置 L 为空, } // while 以防止对系统空间的访问 L = NULL; } // DestroyList 算法的时间复杂度为 O(n)

52 例 : 以链表作存储结构, 将线性表 (a 1, a 2,, a m, b 1, b 2,, b n ) 改变成 (b 1, b 2,, b n, a 1, a 2,, a m ) 解 : 分析 : 因为对链表来说, 插入和删除仅需修改指针即可完成, 并且由于前 m 个元素之间和后 n 个元素之间的链接关系分别都不需要改变, 则算法的实际操作为 : (1) 将 (b 1, b 2,, b n ) 链接到头结点之后 ; (2) 将 (a 1, a 2,, a m ) 链接到 b n 之后 L a 1 a 2 a m ^ b 1 b 2 b n ^

53 void exchange_l( SLink &L,int m ) { if ( m && L next ) { // 链表不空且 m!= 0 p = L next; k = 1; while( k < m && p ) { // 查找结点 a m p = p next; ++k; } // while if (p next) { // p n!=!= NULL 0 时才需要修改指针的判断? ha = L next; // 以指针 ha 记结点 a 1 的位置 L next = p next; // 将结点 b 1 链接在头结点之后 p next = NULL; // 设 a m 的后继为空 q = L next; 出问题 // 令 q? 指向结点 b 1 while (q next) q = q next; // 查找结点 b n 循环的条件中为什么要有因为单链表的长度是个隐含值, 如果这里不加在此无法如顺序表那样事先 p->next 是否为空的判别条件判别参数 m 是否合法, 下面哪一个语句会, 如果参数不合适, 则在没有找到第 m 个结点时算法执行到,p = NULL, q->next while 时会出问循环中题的语句就会出问题 //, 将结点因为当 a 1 p->next=null 链接到结点 b n 之后时, q=null,q->next 就不成立了这是初学链表的人最容易出问题的 P ha 时间复杂度为 P O(n) P q q 地方, 千万要注意避免 L a 1 a 2 a m ^ b 1 b 2 b n ^ q next = ha; } // if(p) } // if(m) } // exchange_l

54 作业 : 线性表采用链式存储结构时, 其地址 ( ) (A) 必须是连续的 (B) 部分地址必须是连续的 (C) 一定是不连续的 (D) 连续与否均可以 2 在一个单链表中, 若 p 所指结点不是最后结点, 在 p 之后插入 s 所指结点, 则执行 () (A)s->next=p;p->next=s; (B) s->next=p->next;p->next=s; (C)s->next=p->next;p=s; (D)p->next=s;s->next=p; 3 在一个单链表中, 若删除 p 所指结点的后续结点, 则执行 ( ) (A)p->next=p->next->next; (B)p=p->next; p->next=p->next->next; (C)p->next=p->next; (D)p =p->next->next;

55 数据结构第二章线性表循环链表循环链表 : 是一种头尾相接的链表 ( 即 : 表中最后一个结点的指针域指向头结点, 整个链表形成一个环 ) H a 1 a n H 非空表单链表空表优点 : 从表中任一结点出发均可找到表中其他结点由于循环链表中没有 NULL 指针, 故涉及遍历操作时, 其终止条件就不再像非循环链表那样判断 p 或 p next 是否为空, 而是判断它们是否等于头指针判断它们是否等于头指针

56 H a 1 非空表 a n H 空表头指针表示单循环链表找 a 1 的时间复杂度 :O(1) 找 a n 的时间复杂度 :O(n) 不方便注意 : 表的操作常常是在表的首尾位置上进行尾指针表示单循环链表 a 1 的存储位置是 :R next next a n 的存储位置是 :R 时间复杂度 :O(1) a 1 a n R

57 例 : 将两个线性表合并成一个线性表仅需将一个表的表尾和另一个表的表头相接 A a 1 a n A B b 1 b m B C = A next B next = C a 1 a n A b 1 b m B A next = B next next A=B 当线性表以上图的循环链表作存储结构时, 此操作仅需改变两个指针即可时间复杂度是 O(1)

58 2.3.3 双向链表为什么要讨论双向链表 : 单链表的结点有指示后继的指针域找后继结点方便 ; 即 : 查找某结点的后继结点的执行时间为 O(1) 无指示前驱的指针域找前驱结点难 : 从表头出发查找即 : 查找某结点的前驱结点的执行时间为 O(n) 可用双向链表来克服单链表的这种缺点双向链表 : 在单链表的每个结点里再增加一个指向其直接前驱的指针域 prior, 这样链表中就形成了有两个方向不同的链, 故称为双向链表

59 双向链表的结构可定义如下 : typedef struct DuLNode{ Elemtype data; struct DuLNode *prior, *next; } DuLNode, *DuLinkList; prior element next 结点结构和单链的循环表类似, 双向链表也可以有循环表, 让头结点的前驱指针指向链表的最后一个结点, 让最后一个结点的后继指针指向头结点 H 空表 H 非空表

60 双向链表结构的对称性 ( 设指针 p 指向某一结点 ): p prior next = p = p next prior 在双向链表中有些操作 ( 如 :ListLength GetElem 等 ), 因仅涉及一个方向的指针, 故它们的算法与线性链表的相同但在插入删除时, 则需同时修改两个方向上的指针, 两者的操作的时间复杂度均为 O(n) p a b c 删除结点 a x 插入结点 p b

61 void ListInsert_DuL(DuLinkList &L, Int i, ElemType e) { // 在带头结点的双向循环链表 L 中第 i 个位置之前插入元素 e s ->date = e; s ->prior = p ->prior; p ->prior ->next = s; p s ->next = p; p ->prior = s; return OK; }// ListInsert_DuL a s e 插入结点 b

62 void ListDelete_DuL(DuLink &L, Int i, ElemType &e) { // 删除带头结点的双向循环链表 L 的第 i 个元素, // 并用 e 返回 e = p -> data; p -> >prior -> >next=p -> >next; p -> next -> prior = p -> prior; free(p); return OK; } // ListDelete_DuL p a b c 删除结点

63 链式存储结构的优点 : 结点空间可以动态申请和释放 ; 数据元素的逻辑次序靠结点的指针来指示, 插入和删除时不需要移动数据元素链式存储结构的缺点 : 每个结点的指针域需额外占用存储空间指针域需额外占用存储空间当每个结点的数据域所占字节不多时, 指针域所占存储空间的比重显得很大链式存储结构是非随机存取非随机存取结构对任一结点的操作都要从头指针依指针链查找到该结点, 这增加了算法的复杂度不便于在表尾插入元素 : 需遍历整个表才能找到插入位置

64 有序表的定义若线性表中的数据元素相互之间可以比较, 并且数据元素在线性表中依值非递减或非递增有序排列, 即 a i a i-1 或 a i a i-1 (i = 2, 3,, n), 则称该线性表为有序表有序表的有序特性可以给某些操作带来很大方便, 在某些应用问题中, 如果用有序表而不是线性表将使算法的时间复杂度下降严格地说, 有序表是另一种数据类型在有序表类型的定义中需限定数据对象中数据元素所属集合为有序集, 即集合中任意两个元素之间都可以进行比较, 并在数据关系中加上 a i-1 a i 的条件

65 2.4 一元多项式的表示及相加符号多项式的表示及其操作是线性表处理的典型用例一个一元多项式 P n (x) 可以表示为 : P n (x)=p 0 +p 1 x+p 2 x 2 + +p n x n ( 最多有 n+1 项 ) 它由 n+1 个系数唯一确定因此可用一个线性表 P 来表示 :P = ( p 0, p 1, p 2,, p n ) 每一项的指数 i 隐含在其系数 p i 的序号里假设 Q m (x) 是一元 m 次多项式, 同样可用线性表 Q 表示 : Q = (q 0, q 1, q 2,, q m ) 若 m < n, 则两个多项式相加的结果 R n (x)= P n (x)+ Q m (x) 可用线性表 R 来表示 : R = (p 0 + q 0, p 1 + q 1, p 2 +q 2,, p m + q m, p m+1,, p n )

66 上述只存储系数的方案对存在大量零系数的多项式并不适用例如 : S(x) = 1 + 3x x 要用一个长度为的线性表来表示, 表中仅有 3 个非零系数, 会浪费大量存储空间若只存储非零系数项, 则必须同时存储相应的指数一般情况下, 一元 n 次多项式 ( 只表示非零系数项 ) 可写成 : P n ( x) p x e p x e 其中 p i 0 (i =1, 2,, m),n = e m > e m-1 > > e p m x e m 若采用一个长度为 m 且每个数据元素有两个数据项 ( 系数项和指数项 ) 的线性表 (( p 1, e 1 ), ( p 2, e 2 ),, ( p m, e m )) 便可唯一确定多项式 P n (x) 对于 S(x) 类的多项式将大大节省空间

67 对于一元多项式既可以采用顺序存储结构, 也可以采用链式存储结构表示究竟采用拿一种, 要根据运算而定 : 若进行不改变系数和指数的运算, 可采用顺序存储结构 ; 否则采用链式存储结构例 : 假设多项式 A 17 (x)=7+3x+9x 8 +5x 17 与 B 8 (x)=8x+22x 7-9x 8 已经用单链表表示, 其头指针分别为 A 与 B, 如下图所示 A B ^ ^ 将两个多项式相加为 C 17 (x)=7+11x+22x 7 +5x 17 C ^ 22 7

68 本章小结问 : 线性表的逻辑结构特点是什么? 其顺序存储结构和链式存储结构的特点是什么? 答 : 线性表逻辑结构特点 : 只有一个首结点和尾结点 ; 除首尾结点外其他结点只有一个直接前驱和一个直接后继简言之, 线性结构的逻辑关系是一对一 (1:1) 的顺序存储时, 相邻数据元素的存放地址也相邻 ( 逻辑与物理统一 ); 要求内存中可用存储单元的地址必须连续链式存储时, 数据元素可随意存放, 但所占存储空间分两部分, 一部分存放结点值, 另一部分存放表示结点间关系的指针

69 问 : 顺序存储和链式存储各有哪些优缺点? 答 : 顺序存储 : 优点 : 存储密度大, 存储空间利用率高, 可随机存取缺点 : 插入或删除元素时不方便不方便链式存储 : 优点 : 插入或删除元素时很方便, 使用灵活结点空间可以动态申请和释放 ; 缺点 : 存储密度小, 存储空间利用率低, 非随机存取事实上, 链表插入删除运算的快捷是以空间代价来换取时间

70 问 : 在什么情况下用顺序表比链表好? 答 : 顺序表适宜于做查找查找这样的静态操作 ; 链表宜于做插入删除插入删除这样的动态操作若线性表的长度变化不大, 且其主要操作是查找, 则采用顺序表 ; 若线性表的长度变化较大, 且其主要操作是插入删除操作, 则采用链表

71 教学要求 1 了解线性表的逻辑结构特性以及两种存储实现方式; 2 熟练掌握两种存储结构的描述方法链表是本章的重难点 3 熟练掌握顺序表的定义与实现, 包括查找插入删除算法的实现 ; 4 熟练掌握在各种链表结构中实现线性表操作的基本方法, 能在实际应用中选用适当的链表结构 ; 5 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合

Microsoft Word - 专升本练习2：线性表.doc

Microsoft Word - 专升本练习2：线性表.doc 第二章线性表一选择题 1. 线性表是 ( ) A. 一个有限序列, 可以为空 B. 一个有限序列, 不能为空 C. 一个有限序列, 可以为空 D. 一个无序序列, 不能为空 2. 对顺序存储的线性表, 设其长度为 n, 在任何位置上插入或删除操作都是等概率插入一个元素时大约要移动表中的 ( ) 个元素, 删除一个元素时大约要移动表中的 ( ) 个元素 A. n/2 B. (n+1)/2 C.