中国科学技术大学：《数据结构及其算法》课程教学资源（教案讲义）第2章线性表.doc

程序设计——数据结构第二章线性表基本概念、线性表的应用第 0 页第 0 页文档编号完成人张昱完成时间完成时间修改时间修改时间 2003-9-10 目录 2.1 线性表的类型定义....................................................................................................1 2.1.1 抽象数据类型线性表的定义.............................................................................1 2.1.2 基于ADT List的算法设计.................................................................................2 2.2 线性表的顺序表示和实现..........................................................................................4 2.2.1 顺序表定义.....................................................................................................4 2.2.2 基本操作实现..................................................................................................4 2.3 线性表的链式表示和实现..........................................................................................6 2.3.1 线性链表.........................................................................................................6 2.3.2 静态链表....................................................................................................... 11 2.3.3 循环链表.......................................................................................................12 2.3.4 双向链表.......................................................................................................12 2.3.5 其它..............................................................................................................13 2.4 线性表的应用.........................................................................................................14 2.4.1 链表的合并和分解.........................................................................................14 2.4.2 线性表的合并(例2-1).....................................................................................15 2.4.3 有序表的合并(例2-2).....................................................................................17 2.4.4 简单的单表分解释放.....................................................................................18 2.4.5 双向循环链表的自身变换..............................................................................18

敦案第二章线性表程序设计—数据结构基本概念、线性表的应用第2章线性表 2.1线性表的类型定义 2.1.1抽象数据类型线性表的定义抽象数据类型指一个数学模型和定义在该模型上的一组操作的接口和语义说明。 ◆不研究具体的实现，反映其逻辑特征，而其在计算机的内部表示和实现对用户是透明的。 ◆包含各种处理器（包括计算机硬件系统、操作系统、高级语言、数据库等）中己定义并实现的数据类型（固有数据类型）和用户自定义的数据类型。分类：原子类型、固定聚合类型、可变聚合类型、多形数据类型抽象数据类型定义：(D,S,P)D-数据对象，S-数据关系，P基本操作线性表的抽象数据类型定义： ADT List{ 数据对象：D={ala∈ElemSet,.i=l,2,…,n,n≥0} 数据关系：R={R1},R1={<a-1,a>a-1,a∈D,=2,3,…,n} 基本操作： InitList(&L) 操作结果：构造一个空的线性表L DestroyList(&L) 初始条件：线性表L已存在操作结果：销毁线性表L ClearList(&L) 初始条件：线性表L己存在操作结果：将线性表L重置为空表 ListEmpty(L) 初始条件：线性表L己存在操作结果：若L为空表，则返回TRUE,否则返回FALSE ListLength(L) 初始条件：线性表L己存在操作结果：返回线性表L中数据元素的个数 GetElem(L,i,&e) 初始条件：线性表L己存在，l≤i≤ListLength(L) 操作结果：用e返回L中第ⅰ个数据元素的值 LocateElem(L,e,compare()) 初始条件：线性表L己存在，compare()是数据元素的判定函数操作结果：返回L中第1个与e满足关系compare(()的数据元素的位序。若这样的元素不存在，则返回值为0 PriorElem(L,cur_e,&pre_e) 初始条件：线性表L已存在操作结果：若cure是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pree无定义 NextElem(L,cur e,&next_e) 初始条件：线性表L己存在操作结果：若cure是L的数据元素，且不是最后一个，则用next e返文档编号完成时间完成人张昱修改时间2003-9-10 第1页

程序设计——数据结构第二章线性表基本概念、线性表的应用第 1 页第 1 页文档编号完成人张昱完成时间完成时间修改时间修改时间 2003-9-10 第2章线性表 2.1 线性表的类型定义 2.1.1 抽象数据类型线性表的定义抽象数据类型指一个数学模型和定义在该模型上的一组操作的接口和语义说明。 ◆ 不研究具体的实现，反映其逻辑特征，而其在计算机的内部表示和实现对用户是透明的。 ◆ 包含各种处理器（包括计算机硬件系统、操作系统、高级语言、数据库等）中已定义并实现的数据类型（固有数据类型）和用户自定义的数据类型。分类：原子类型、固定聚合类型、可变聚合类型、多形数据类型抽象数据类型定义：(D,S,P) D-数据对象，S-数据关系，P-基本操作线性表的抽象数据类型定义： ADT List{ 数据对象：D={ai | ai∈ElemSet, i=1,2,…,n, n≥0} 数据关系：R={R1},R1={<ai-1,ai>|ai-1,ai∈D, i=2,3,…,n } 基本操作： InitList(&L) 操作结果：构造一个空的线性表 L DestroyList(&L) 初始条件：线性表 L 已存在操作结果：销毁线性表 L ClearList(&L) 初始条件：线性表 L 已存在操作结果：将线性表 L 重置为空表 ListEmpty(L) 初始条件：线性表 L 已存在操作结果：若 L 为空表，则返回 TRUE，否则返回 FALSE ListLength(L) 初始条件：线性表 L 已存在操作结果：返回线性表 L 中数据元素的个数 GetElem(L, i ,&e) 初始条件：线性表 L 已存在，1≤i≤ListLength(L) 操作结果：用 e 返回 L 中第 i 个数据元素的值 LocateElem(L, e, compare( )) 初始条件：线性表 L 已存在，compare( )是数据元素的判定函数操作结果：返回 L 中第 1 个与 e 满足关系 compare( )的数据元素的位序。若这样的元素不存在，则返回值为 0 PriorElem(L, cur_e ,&pre_e) 初始条件：线性表 L 已存在操作结果：若 cur_e 是 L 的数据元素，且不是第一个，则用 pre_e 返回它的前驱，否则操作失败，pre_e 无定义 NextElem(L, cur_e ,&next_e) 初始条件：线性表 L 已存在操作结果：若 cur_e 是 L 的数据元素，且不是最后一个，则用 next_e 返

教案第二章线性表程序设计—数据结构基本概念、线性表的应用回它的后继，否则操作失败，next e无定义 ListInsert(&L,i,e) 初始条件：线性表L已存在，1≤i≤ListLength(L)+1 操作结果：在L中第ⅰ个位置之前插入新的数据元素e,L的长度加1 ListDelete(&L.i.&e) 初始条件：线性表L己存在，I≤i≤ListLength(L) 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 ListTraverse(L.visit()) 初始条件：线性表L己存在操作结果：依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败 ADT List 2.1.2基于ADT List的算法设计 1、例2-1 假设利用两个线性表La和Lb分别表示两个集合A和B(即：线性表中的数据元素即为集合中的成员)，现要求一个新的集合A=AUB。【设计思路】输入：线性表La、线性表Lb 输出：变化了的La →union(&LaLb) 处理方法：上述问题相当于：扩大线性表L,将存在于线性表b中而不存在于线性表La 中的数据元素插入到线性表La中去。步骤： 1.从线性表LB中依次取得每个数据元素； 2.依值在线性表LA中进行查访： 3.若不存在，则插入之。【算法2.1】 void union(List &La,List Lb){ ∥将所有在线性表Lb中但不在La中的数据元素插入到La中 La len=ListLength(La); Lb len ListLength(Lb); ∥求线性表的长度 for(i=1;i<=Lb len;i+){ GetElem(Lb,i,e); ∥取b中第i个数据元素赋给e if(!LocateElem(La,e,equal)) ListInsert(La,+La len,e;∥La中不存在和e相同的数据元素，则插入之 }/∥union 【性能分析】时间复杂度：O(ListLength(La)×ListLength(Lb)(视GetElem和在表尾的插入操作为单位时间) 【思考】 1、算法设计：已知集合B,试构造集合A,要求集合A中只包含B中所有值不相同的数据元素。方法1：InitList(&La,union(&La,Lb): 时间复杂度：O2(ListLength(Lb) 方法2：排序，删除文档编号完成时间完成人张昱修改时间2003-9-10 第2页

程序设计——数据结构第二章线性表基本概念、线性表的应用第 2 页第 2 页文档编号完成人张昱完成时间完成时间修改时间修改时间 2003-9-10 回它的后继，否则操作失败，next_e 无定义 ListInsert(&L, i, e) 初始条件：线性表 L 已存在，1≤i≤ListLength(L)+1 操作结果：在 L 中第 i 个位置之前插入新的数据元素 e，L 的长度加 1 ListDelete(&L, i, &e) 初始条件：线性表 L 已存在，1≤i≤ListLength(L) 操作结果：删除 L 的第 i 个数据元素，并用 e 返回其值，L 的长度减 1 ListTraverse(L, visit( )) 初始条件：线性表 L 已存在操作结果：依次对 L 的每个数据元素调用函数 visit( )。一旦 visit( )失败，则操作失败 }ADT List 2.1.2 基于 ADT List 的算法设计 1、例 2-1 假设利用两个线性表 La 和 Lb 分别表示两个集合 A 和 B（即：线性表中的数据元素即为集合中的成员），现要求一个新的集合 A＝A∪B。【设计思路】输入：线性表 La、线性表 Lb 输出：变化了的 La ➔union(&La, Lb) 处理方法：上述问题相当于：扩大线性表 La，将存在于线性表 Lb 中而不存在于线性表 La 中的数据元素插入到线性表 La 中去。步骤： 1．从线性表 LB 中依次取得每个数据元素; 2．依值在线性表 LA 中进行查访; 3．若不存在，则插入之。【算法 2.1】 void union(List &La, List Lb) { // 将所有在线性表 Lb 中但不在 La 中的数据元素插入到 La 中 La_len = ListLength(La); Lb_len = ListLength(Lb); // 求线性表的长度 for (i = 1; i <= Lb_len; i++) { GetElem(Lb, i, e); // 取 Lb 中第 i 个数据元素赋给 e if(!LocateElem(La, e, equal)) ListInsert(La, ++La_len, e); // La 中不存在和 e 相同的数据元素，则插入之 } } // union 【性能分析】时间复杂度：O(ListLength(La)×ListLength(Lb)) (视 GetElem 和在表尾的插入操作为单位时间) 【思考】 1、算法设计：已知集合 B，试构造集合 A，要求集合 A 中只包含 B 中所有值不相同的数据元素。方法 1：InitList(&La); union(&La, Lb); 时间复杂度：O2 (ListLength(Lb) 方法 2：排序，删除

程序设计——数据结构第二章线性表基本概念、线性表的应用第 3 页第 3 页文档编号完成人张昱完成时间完成时间修改时间修改时间 2003-9-10 void purge(List &La, List Lb) { // 已知线性表 Lb 中的数据元素依值非递减有序排列，现构造线性表 La， // 使 La 中只包含 Lb 中所有值不相同的数据元素 InitList（La）； // 初始化 La 为空表 La_len = ListLength(La); Lb_len = ListLength(Lb); // 求线性表的长度 for (i = 1; i <= Lb_len; i++) { GetElem(Lb, i, e); // 取 Lb 中第 i 个数据元素赋给 e if( ListEmpty(La) || !equal(en，e) ) { ListInsert(La, ++La_len, e); // La 中不存在和 e 相同的数据元素，则插入之 en = e; } } // for } // purge 时间复杂度：O(ListLength(Lb)) (前提 Lb 为有序表) (视 GetElem 和在表尾的插入操作为单位时间) 2、算法设计：已知集合 B，要求删除 B 中值相同的多余数据元素。 2、例 2-2 已知线性表 La 和 Lb 中的数据元素按值非递减有序排列，要求将 La 和 Lb 归并成一个新的线性表 Lc，且 Lc 中的数据元素仍按值非递减有序排列。【设计思路】输入：线性表 La、线性表 Lb(均按值非递减有序排列) 输出：Lc(按值非递减有序排列) ➔merge(La, Lb, &Lc) 处理方法：∵La 和 Lb 均按值非递减有序排列 ∴设置两个位置指示器 i 和 j，分别指向 La 和 Lb 中的某个元素，初始均指向第 1 个。比较 i 和 j 所指向的元素 ai 和 bj，选取值小的插入到 Lc 的尾部，并使相应的位置指示器向后移。【算法 2.2】 void MergeList(List La, List Lb, List &Lc) { // 已知线性表 La 和 Lb 中的元素按值非递减排列。归并 La 和 Lb 得到新的线性表 // Lc，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, ai); GetElem(Lb, j, bj); if (ai <= bj) { ListInsert(Lc, ++k, ai); ++i; }else { ListInsert(Lc, ++k, bj); ++j; } } while (i <= La_len) { GetElem(La, i++, ai); ListInsert(Lc, ++k, ai); }

教黎第二章线性表程序设计—数据结构基本概念、线性表的应用 while(j<=Lb_len){ GetElem(Lb,j++,bj); ListInsert(Lc,++k,bj); }/MergeList 【性能分析】时间复杂度：O(ListLength(LA)+ListLength(LB)(视GetElem和在表尾的插入操作为单位时间) 【思考】 1、上述算法中元素插入到Lc中的位置是Lc中最后一个元素的后面。试修改算法，使得元素每次插入到Lc中的位置是Lc中的第一个元素之前。 2、若要求Lc为无序表或按值非递增有序排列，则算法应如何设计。 2.2线性表的顺序表示和实现 2.2.1顺序表定义 1、方案一 #define LIST SIZE 100 typedef struct ElemType elem[LIST_SIZE]; /体存储空间 */ int length; /体当前长度 * SqList static; 1)LIST SIZE过小，则会导致顺序表上溢： 2)LIST SIZE过大，则会导致空间的利用率不高。 2、方案二 #define LIST INIT SIZE 100 /体存储空间的初始分配量*/ #define LISTINCREMENT 10 /体存储空间的分配增量*/ typedef struct ElemType *elem: /体存储空间的基址 *制 int length: /体当前长度 */ int listsize; /体当前分配的存储容量 */ )SqList; 这种方法可以解决方案一中的“上溢”问题和“空间利用率不高”问题。但是这一方案是有时间和空间代价的：当因插入元素而空间不足时，需要重新分配比原先的顺序表多存储 LISTINCREMENT个数据元素的连续空间，并且需要将原空间的数据元素复制到新分配的空间中。 1)必须记载当前线性表的实际分配的空间大小： 2)当线性表不再使用时，应释放其所占的空间： 3)这种方法要求实现级的语言能提供空间的动态分配与释放管理。 void *malloc(unsigned int size) 生成一大小为siz心的结点空间，将该空间的起始地址赋给pP: free(void *p) 回收p所指向的结点空间； void *realloc(void *p,unsigned int size) 将p所指向的已分配内存区的大小改为siz心，siz可以比原分配的空间大或小。 2.2.2基本操作实现文档编号完成时间完成人张昱修改时间2003-9-10 第4页

程序设计——数据结构第二章线性表基本概念、线性表的应用第 4 页第 4 页文档编号完成人张昱完成时间完成时间修改时间修改时间 2003-9-10 while (j <= Lb_len) { GetElem(Lb, j++, bj); ListInsert(Lc, ++k, bj); } } // MergeList 【性能分析】时间复杂度：O(ListLength(LA)+ListLength(LB)) (视 GetElem 和在表尾的插入操作为单位时间) 【思考】 1、上述算法中元素插入到 Lc 中的位置是 Lc 中最后一个元素的后面。试修改算法，使得元素每次插入到 Lc 中的位置是 Lc 中的第一个元素之前。 2、若要求 Lc 为无序表或按值非递增有序排列，则算法应如何设计。 2.2 线性表的顺序表示和实现 2.2.1 顺序表定义 1、方案一 #define LIST_SIZE 100 typedef struct{ ElemType elem[LIST_SIZE]; /* 存储空间 */ int length; /* 当前长度 */ }SqList_static; 1) LIST_SIZE 过小，则会导致顺序表上溢； 2) LIST_SIZE 过大，则会导致空间的利用率不高。 2、方案二 #define LIST_INIT_SIZE 100 /* 存储空间的初始分配量 */ #define LISTINCREMENT 10 /* 存储空间的分配增量 */ typedef struct{ ElemType *elem; /* 存储空间的基址 */ int length; /* 当前长度 */ int listsize; /* 当前分配的存储容量 */ }SqList; 这种方法可以解决方案一中的“上溢”问题和“空间利用率不高”问题。但是这一方案是有时间和空间代价的：当因插入元素而空间不足时，需要重新分配比原先的顺序表多存储 LISTINCREMENT 个数据元素的连续空间，并且需要将原空间的数据元素复制到新分配的空间中。 1) 必须记载当前线性表的实际分配的空间大小； 2) 当线性表不再使用时，应释放其所占的空间； 3) 这种方法要求实现级的语言能提供空间的动态分配与释放管理。 void *malloc(unsigned int size) 生成一大小为 size 的结点空间，将该空间的起始地址赋给 p； free(void *p) 回收 p 所指向的结点空间; void *realloc(void *p, unsigned int size) 将 p 所指向的已分配内存区的大小改为 size，size 可以比原分配的空间大或小。 2.2.2 基本操作实现

中国科学技术大学：《数据结构及其算法》课程教学资源（教案讲义）第2章 线性表

中国科学技术大学：《数据结构及其算法》课程教学资源（教案讲义）第2章线性表