敦案 第二章线性表 程序设计—数据结构 基本概念、线性表的应用 目录 2.1线性表的类型定义 . 2.1.1抽象数据类型线性表的定义 2.1.2基于ADT List的算法设计 2.2线性表的顺序表示和实现 2 2.2.1顺序表定义 2.2.2基本操作实现 2.3线性表的链式表示和实现 6 2.3.1线性链表 6 2.3.2静态链表 11 2.3.3循环链表 .12 2.3.4双向链表 2.3.5其它… .12 .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 文档编号 完成时间 完成人张昱 修改时间2003-9-10 第0页
程序设计——数据结构 第二章 线性表 基本概念、线性表的应用 第 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∈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∈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：排序，删除
教案 第二章线性表 程序设计—数据结构 基本概念、线性表的应用 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; }l∥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 <=bi){ ListInsert(Lc,++k,ai);++i; }else ListInsert(Lc,++k,bj);++j;} while(i<=La len){ GetElem(La,i++,ai); ListInsert(Lc,++k,ai); 文档编号 完成时间 完成人张昱 修改时间2003-9-10 第3页
程序设计——数据结构 第二章 线性表 基本概念、线性表的应用 第 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 基本操作实现
教黎 第二章线性表 程序设计—数据结构 基本概念、线性表的应用 l、初始化操作InitList Sq Status InitList Sq(SqList &L) ∥构造一个空的线性表L L.elem =(ElemType *)malloc(LIST_INIT_SIZE*sizeof(Elem Type)); if(L.elem=NULL)exit(OVERFLOW);∥存储分配失败 L.length=0; ∥空表长度为0 L.listsize LIST INIT SIZE; ∥初始存储容量 return OK: }/∥InitList Sq 2、插入操作ListInsert_Sq 1)算法设计 参数：顺序表&L、插入位置i、插入元素e 插入分析：第i个位置放e,则原来第i~L.length个数据元素必须先后移，以腾出第i 个位置； 注意后移的顺序为：从最后一个元素开始，逐个往后移 for (j=L.length;j>=i;j--)L.elem[i]L.elem[j-1]; ∥后移 L.clem[i-1]=e,/第i个元素存放在L.elem[i-l]中，数组下标的起始为0 L.length L.length+1; 合法的位置：i:l.L.length+1 上溢及处理：上溢发生的条件：L.length≥L.listsize,此时要先申请一个有一定增量的 空间：申请成功则原空间的元素复制到新空间，修改L.listsiz心，再进行插 入工作：否则报错退出。 算法 Status ListInsert_Sq(SqList &L,int i,ElemType e){ ∥位置合法性的判断 if(iL.length+1)return ERROR; ∥上溢时增加空间的分配 if(L.length >=L.listsize) newbase =(ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType)); if(newbase =NULL exit(OVERFLOW); L.elem newbase; L.listsize +LISTINCREMENT; ∥插入元素 for (j=L.length;j>=i;j--)L.elem[j]=L.elem[j-1]; L.elem[i-1]=e; L.length++; return OK; 2)算法分析—一时间 频次最高的操作：移动元素。另外，上溢时的空间的再分配与复制(realloc操作)的时 间复杂度与realloc的算法以及当前的表长相关，至少为On):但它仅在插入元素会引起上 溢时才执行。 若线性表的长度为n,则： 最好情况：插入位置i为+1，此时无须移动元素，时间复杂度为O(1): 最坏情况：插入位置i为1，此时须移动n个元素，时间复杂度为O(n: 文档编号 完成时间 完成人张昱 修改时间2003-9-10 第5页
程序设计——数据结构 第二章 线性表 基本概念、线性表的应用 第 5 页 第 5 页 文档编号 完 成 人 张 昱 完成时间 完成时间 修改时间 修改时间 2003-9-10 1、初始化操作 InitList_Sq Status InitList_Sq( SqList &L) { // 构造一个空的线性表 L L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if ( L.elem == NULL ) exit(OVERFLOW); // 存储分配失败 L.length = 0; // 空表长度为 0 L.listsize = LIST_INIT_SIZE; // 初始存储容量 return OK; } // InitList_Sq 2、插入操作 ListInsert_Sq 1) 算法设计 参数：顺序表&L、插入位置 i、插入元素 e 插入分析：第 i 个位置放 e，则原来第 i~L.length 个数据元素必须先后移，以腾出第 i 个位置; 注意后移的顺序为：从最后一个元素开始，逐个往后移 for ( j = L.length; j >= i; j--) L.elem[j] = L.elem[j-1]; // 后移 L.elem[i -1] = e; //第 i 个元素存放在 L.elem[i-1]中，数组下标的起始为 0 L.length = L.length+1; 合法的位置：i:1..L.length+1 上溢及处理：上溢发生的条件：L.length≥L.listsize，此时要先申请一个有一定增量的 空间：申请成功则原空间的元素复制到新空间，修改 L.listsize，再进行插 入工作；否则报错退出。 算法 Status ListInsert_Sq( SqList &L, int i, ElemType e) { // 位置合法性的判断 if ( iL.length +1 ) return ERROR; // 上溢时增加空间的分配 if( L.length >= L.listsize){ newbase = (ElemType *) realloc(L.elem, (L.listsize+ LISTINCREMENT)*sizeof(ElemType)); if ( newbase == NULL ) exit(OVERFLOW); L.elem = newbase; L.listsize += LISTINCREMENT; } // 插入元素 for ( j = L.length; j >= i; j--) L.elem[j] = L.elem[j-1]; L.elem[i-1] = e; L.length++; return OK; } 2) 算法分析——时间 频次最高的操作：移动元素。另外，上溢时的空间的再分配与复制(realloc 操作)的时 间复杂度与 realloc 的算法以及当前的表长相关，至少为 O(n)；但它仅在插入元素会引起上 溢时才执行。 若线性表的长度为 n，则： ➢ 最好情况：插入位置 i 为 n+1，此时无须移动元素，时间复杂度为 O(1); ➢ 最坏情况：插入位置 i 为 1，此时须移动 n 个元素，时间复杂度为 O(n);
教黎 第二章线性表 程序设计—数据结构 基本概念、线性表的应用 平均情况：假设p:为在第ⅰ个元素之前插入一个元素的概率，则： 入时移动次数的期望值：E。三∑P(n-1+1） 等概率时，即p= n+11 2-+0- ∴.Tn)=On) 3、删除操作ListDelete_Sq 1)算法设计 参数：顺序表&L、删除位置i 删除分析：去掉第i个元素，则原来第i+l~L.length个数据元素须前移，以覆盖第i个 位置； 前移的顺序为for(j=ijL.length)return ERROR; ∥删除 for (j=i;j<L.length;j++)L.elem[j-1]=L.elem[jl]; L.length--; return OK: 2)算法分析——时间 频次最高的操作：移动元素 若线性表的长度为n,则： 最好情况：删除位置i为，此时无须移动元素，时间复杂度为O(1); 最坏情况：删除位置i为1，此时须前移n-1个元素，时间复杂度为O(n少： 平均情况：假设4：为删除第ⅰ个元素的概率，则： 删除时移动次数的期望值：E=29(n-) 等展率时，即=，5之u-)=” n ∴.T(n)=On) 2.3线性表的链式表示和实现 2.3.1线性链表 1、顺序映像的弱点 1)空间利用率不高（预先按最大空间分配）： 2)表的容量不可扩充（针对顺序表的方案一）： 3)即使表的容量可以扩充（针对顺序表的方案二），由于其空间再分配和复制的开销，也 不允许它频繁地使用： 文档编号 完成时间 完成人张昱 修改时间2003-9-10 第6页
程序设计——数据结构 第二章 线性表 基本概念、线性表的应用 第 6 页 第 6 页 文档编号 完 成 人 张 昱 完成时间 完成时间 修改时间 修改时间 2003-9-10 ➢ 平均情况：假设 pi 为在第 i 个元素之前插入一个元素的概率，则： 插入时移动次数的期望值： + = = − + 1 1 ( 1) n i is i E p n i 等概率时，即 1 1 + = n pi ， 2 ( 1) 1 1 1 1 n n i n E n i is − + = + = + = ∴ T(n) = O(n) 3、删除操作 ListDelete_Sq 1) 算法设计 参数：顺序表&L、删除位置 i 删除分析：去掉第 i 个元素，则原来第 i+1~L.length 个数据元素须前移，以覆盖第 i 个 位置; 前移的顺序为 for ( j = i; j L.length ) return ERROR; // 删除 for ( j = i; j < L.length ; j++) L.elem[j-1] = L.elem[j]; L.length--; return OK; } 2) 算法分析——时间 频次最高的操作：移动元素 若线性表的长度为 n，则： ➢ 最好情况：删除位置 i 为 n，此时无须移动元素，时间复杂度为 O(1); ➢ 最坏情况：删除位置 i 为 1，此时须前移 n-1 个元素，时间复杂度为 O(n); ➢ 平均情况：假设 qi 为删除第 i 个元素的概率，则： 删除时移动次数的期望值： = = − n i de i E q n i 1 ( ) 等概率时，即 n qi 1 = ， 2 1 ( ) 1 1 − = − = = n n i n E n i de ∴ T(n) = O(n) 2.3 线性表的链式表示和实现 2.3.1 线性链表 1、顺序映像的弱点 1）空间利用率不高（预先按最大空间分配）； 2）表的容量不可扩充（针对顺序表的方案一）； 3）即使表的容量可以扩充（针对顺序表的方案二），由于其空间再分配和复制的开销，也 不允许它频繁地使用；
敦察 第二章线性表 程序设计—数据结构 基本概念、线性表的应用 4)插入或删除时需移动大量元素。 2、链表定义 特点：逻辑上相邻的元素，物理上未必相邻 几个名词：结点一一数据元素的存储映像，包括数据域和指针域（其信息称为指针或链） 头指针一一链表存取的开始 空(NULL)一一最后一个结点的指针 一一非随机存取的存储结构 3、单链表的类型定义 typedef struct LNode ElemType data; ∥数据域 struct LNode *next; ∥后向指针域 }LNode,*LinkList; Lam□-e□ ·一ana 1)无头结点的单链表 头指针为L,则空表时，L=NULL 上%T-a正 an 由于第一个结点无前驱结点，所以只能通过某指针变量来指向，如L: 其余结点均有前驱结点，故可通过其直接前驱结点的next域来指向，即->next: 表示方法的不同，会造成对结点的操作处理的不同。 2)有头结点的单链表 空表时，L指向一结点（称为头结点），该结点的数据域可以不存储信息，也可存储如表 长等的附加信息，结点的指针域存放NULL,即L->next=NULL。 第一个结点和其余结点均可统一表示为其直接前驱结点的nxt域所指向的结点， 即->next。 4、取第i个元素GetElem_L(LinkList L,inti,ElemType&e) 参数：链表L、位置i、取得的第i个元素&e 分析：（带头结点的单链表） 算法1带头结点的单链表中取第ⅰ个元素 Status GetElem L(LinkList L,int i,ElemType &e) p=L->next;j=1;j表示当前p所指向的元素在线性表中的位序 while (jnext,j+;∥后移指针并计数j if(p=NULL Ilj>i)return ERROR;∥第i个元素不存在 e=p->data; ∥取第i个元素 return OK: 【性能分析】 频度最高的操作：寻找下一个结点，指针后移(next) 执行次数：当1≤i≤表长n时，频度为i-l:否则为n .T(n)=O(n) 5、插入ListInsert L(LinkList&L,inti,Elem'Type e) ai-1 ai 【设计思路】 相关结点：a-1和a 结点的表示：引入指针变量LinkList p; ,链表结点的指针域是指向该结点的直接后继 文档编号 完成时间 完成人张昱 修改时间2003-9-10 第7页
程序设计——数据结构 第二章 线性表 基本概念、线性表的应用 第 7 页 第 7 页 文档编号 完 成 人 张 昱 完成时间 完成时间 修改时间 修改时间 2003-9-10 4）插入或删除时需移动大量元素。 2、链表定义 特点：逻辑上相邻的元素，物理上未必相邻 几个名词：结点——数据元素的存储映像，包括数据域和指针域（其信息称为指针或链） 头指针——链表存取的开始 空（NULL）——最后一个结点的指针 ——非随机存取的存储结构 3、单链表的类型定义 typedef struct LNode{ ElemType data; // 数据域 struct LNode *next; // 后向指针域 }LNode, *LinkList; 1) 无头结点的单链表 头指针为 L，则空表时，L == NULL 由于第一个结点无前驱结点，所以只能通过某指针变量来指向，如 L； 其余结点均有前驱结点，故可通过其直接前驱结点的 next 域来指向，即……->next； 表示方法的不同，会造成对结点的操作处理的不同。 2) 有头结点的单链表 空表时，L 指向一结点(称为头结点)，该结点的数据域可以不存储信息，也可存储如表 长等的附加信息，结点的指针域存放 NULL，即 L->next == NULL。 第一个结点和其余结点均可统一表示为其直接前驱结点的 next 域所指向的结点， 即……->next。 4、取第 i 个元素 GetElem_L(LinkList L, int i, ElemType &e) 参数：链表 L、位置 i、取得的第 i 个元素&e 分析：（带头结点的单链表） 算法 1 带头结点的单链表中取第 i 个元素 Status GetElem_L( LinkList L, int i, ElemType &e) { p = L->next; j = 1; // j 表示当前 p 所指向的元素在线性表中的位序 while ( j next; j++; // 后移指针并计数 j } if ( p == NULL || j > i) return ERROR; // 第 i 个元素不存在 e = p->data; // 取第 i 个元素 return OK; } 【性能分析】 频度最高的操作：寻找下一个结点，指针后移(next) 执行次数：当 1≤i≤表长 n 时，频度为 i-1；否则为 n ∴ T(n) = O(n) 5、插入 ListInsert_L(LinkList &L, int i, ElemType e) 【设计思路】 相关结点：ai-1 和 ai 结点的表示：引入指针变量 LinkList p; ∵链表结点的指针域是指向该结点的直接后继 a1 a2 L an ^ a1 an ^ L ai-1 ai s e p 1 2 3 5 4
教黎 第二章线性表 程序设计—数据结构 基本概念、线性表的应用 ∴.当p指向a-1时，a可用*(p->next)表示 关键步骤：（如右图所示） ①找到a-1的位置，即使p指向a-1结点，可参考GetElem()的处理 p≠NULL,则②s=(LinkList))malloc(sizeof(LNode) ③s>data=e ④s->next=p->next ⑤p->next=s 注意：④和⑤不能交换，否则会导致a的位置无法获取。 【性能分析】 其时间消耗主要在①，其他为O(1)∴.T(n)=On) 【有头结点的算法】 算法见教科书P30页。 算法1有头结点的单链表中的插入算法 Status ListInsert(LinkList &L,int i,ElemType e){ ∥有头结点，无须对ⅰ为1的插入位置作特殊处理 p=L;j=0: ∥对p,初始化，*p为L的第j个结点 while(p !NULL &jnext;j++; ∥寻找第i-1个结点的位置 if(p=NULL Il>rI)return ERROR:∥i小于I或大于表长 s=(LinkList)malloc(sizeof(LNode);∥生成新结点 if(s=NULL)exit(OVERFLOW);∥空间分配不成功，报错返回 s->data=e;s->next=p->next; ∥插入L中 p->next =s: return OK; } 【无头结点的算法】 算法2无头结点的单链表中的插入算法 Status ListInsert(LinkList &L,int i,ElemType e) ∥无头结点，须对i为1的插入位置作特殊处理 if (i==1){ s=(LinkList)malloc(sizeof(LNode);∥生成新结点 if(s=NULL)exit(OVERFLOW);∥空间分配不成功，报错返回 s->data=e:s->next L; ∥插入到链表L中 L=s; ∥修改链头指针L }else{ p=L;j=1; ∥对Pj初始化，*p为链表的第j个结点 while(p !NULL&&jnext;j++; ∥寻找第i-1个结点的位置 ifp=NULL‖lj>iI)return ERROR:∥i小于1或大于表长 s=(LinkList)malloc(sizeof(LNode);∥生成新结点*s if(s=NULL)exit(OVERFLOW):∥空间分配不成功，报错返回 s->data=e;s->next=p->next; ∥插入到链表L中 p->next =s; } return OK: 文档编号 完成时间 完成人张昱 修改时间2003-9-10 第8页
程序设计——数据结构 第二章 线性表 基本概念、线性表的应用 第 8 页 第 8 页 文档编号 完 成 人 张 昱 完成时间 完成时间 修改时间 修改时间 2003-9-10 ∴当 p 指向 ai-1 时，ai 可用*(p->next)表示 关键步骤：（如右图所示） ①找到 ai-1 的位置，即使 p 指向 ai-1 结点，可参考 GetElem_L( )的处理 p≠NULL，则② s = (LinkList)malloc(sizeof(LNode)) ③ s->data = e ④ s->next = p->next ⑤ p->next = s 注意：④和⑤不能交换，否则会导致 ai 的位置无法获取。 【性能分析】 其时间消耗主要在①,其他为 O(1) ∴T(n) = O(n) 【有头结点的算法】 算法见教科书 P30 页。 算法 1 有头结点的单链表中的插入算法 Status ListInsert(LinkList &L, int i, ElemType e){ // 有头结点，无须对 i 为 1 的插入位置作特殊处理 p = L; j = 0; // 对 p,j 初始化; *p 为 L 的第 j 个结点 while( p != NULL && jnext; j++; // 寻找第 i-1 个结点的位置 } if( p == NULL || j>i-1) return ERROR;// i 小于 1 或大于表长 s = (LinkList )malloc(sizeof(LNode)); // 生成新结点 if ( s == NULL ) exit(OVERFLOW);// 空间分配不成功，报错返回 s->data = e; s->next = p->next; // 插入 L 中 p->next = s; return OK; } 【无头结点的算法】 算法 2 无头结点的单链表中的插入算法 Status ListInsert(LinkList &L, int i, ElemType e) { // 无头结点，须对 i 为 1 的插入位置作特殊处理 if ( i==1){ s = (LinkList )malloc(sizeof(LNode)); // 生成新结点 if ( s == NULL ) exit(OVERFLOW); // 空间分配不成功，报错返回 s->data = e; s->next = L; // 插入到链表 L 中 L = s; // 修改链头指针 L }else{ p = L; j = 1; // 对 p,j 初始化; *p 为链表的第 j 个结点 while( p != NULL && jnext; j++; // 寻找第 i-1 个结点的位置 } if( p == NULL || j>i-1) return ERROR;// i 小于 1 或大于表长 s = (LinkList )malloc(sizeof(LNode)); // 生成新结点*s if ( s == NULL ) exit(OVERFLOW); // 空间分配不成功，报错返回 s->data = e; s->next = p->next; // 插入到链表 L 中 p->next = s; } return OK;
教黎 第二章线性表 程序设计—数据结构 基本概念、线性表的应用 【思考】对比无头结点和有头结点在插入算法上的不同，分析其中的原因。 6、删除ListDelete L(LinkList&L,inti,ElemType&e) 【设计思路】 相关结点：a-1、a和a+1 结点的表示：引入指针变量LinkList p; 9、0 链表结点的指针域指向该结点的直接后继 ai-1 ∴.当p指向a-1时，a可用*(p>next)表示，ai+ 可用*(p->next->next)表示 关键步骤：（如右图所示） ①找到a-的位置，即使p指向a-i结点，可参考GetElem L()的处理 p->next≠NULL(有待删除的结点)，则 ②q=p->next(记录待释放结点的位置) 3 p->next =p->next->next ④free(q) 注意：必须在③④前增加②步，否则在执行了③后要释放的结点无法标识。 【性能分析】 其时间消耗主要在①，其它为O1).T(n)=O) 7、创建单链表（带头结点）CreateList L(LinkList&L,intn) 【设计思路】 首先初始化单链表，而后根据结点输入的次序与其在线性表中的逻辑次序是否一致（正序） 或相反（逆序），决定是采用尾插法还是头插法，逐个将各结点依次插入到单链表中。 1)头插法 思想：每次将待插结点*s插入到第一个结点之前；当有头结点时，待插结点也可视 为插入到第0个结点（头结点）之后。 插入步骤：以单链表中有头结点为例，单个结点的构造和插入步骤如下 1s=(LinkList)malloc(sizeof(LNode))2 scanf(&s->data) ③s->next=L->next④L->next=s 算法分析：由上可看出每次插入一个结点所需的时间为O(1) ∴.头插法创建单链表的时间复杂度T(n)=O(n) 算法3带头结点，用头插法创建表 Status CreateList L(LinkList &L) ∥空链表的建立 L=(LinkList )malloc(sizeof(LNode)); ∥生成头结点 if (L==NULL exit(OVERFLOW); L->next NULL; ∥构造空表 ∥若是循环链表，则仅将上一语句政为：L->t=L:其余不变 bCycleFlag=1; ∥控制是否继续循环插入新结点 ∥循环插入新结点到头结点L之后 while(bCycleFlag){ scanf(&e)方 ∥输入待插的元素 文档编号 完成时间 完成人张昱 修改时间2003-9-10 第9页
程序设计——数据结构 第二章 线性表 基本概念、线性表的应用 第 9 页 第 9 页 文档编号 完 成 人 张 昱 完成时间 完成时间 修改时间 修改时间 2003-9-10 } 【思考】对比无头结点和有头结点在插入算法上的不同，分析其中的原因。 6、删除 ListDelete_L(LinkList &L, int i, ElemType &e) 【设计思路】 相关结点：ai-1、ai 和 ai+1 结点的表示：引入指针变量 LinkList p; ∵链表结点的指针域指向该结点的直接后继 ∴当 p 指向 ai-1 时，ai 可用*(p->next)表示，ai+1 可用*(p->next->next)表示 关键步骤：（如右图所示） ①找到 ai-1 的位置，即使 p 指向 ai-1 结点, 可参考 GetElem_L( )的处理 p->next≠NULL（有待删除的结点），则 ② q = p->next (记录待释放结点的位置) ③ p->next = p->next->next ④ free(q) 注意：必须在③④前增加②步，否则在执行了③后要释放的结点无法标识。 【性能分析】 其时间消耗主要在①,其它为 O(1) ∴T(n) = O(n) 7、创建单链表（带头结点）CreateList_L(LinkList &L, int n) 【设计思路】 首先初始化单链表，而后根据结点输入的次序与其在线性表中的逻辑次序是否一致（正序） 或相反（逆序），决定是采用尾插法还是头插法，逐个将各结点依次插入到单链表中。 1) 头插法 思想：每次将待插结点*s 插入到第一个结点之前；当有头结点时，待插结点也可视 为插入到第 0 个结点(头结点)之后。 插入步骤：以单链表中有头结点为例，单个结点的构造和插入步骤如下 ① s = (LinkList)malloc(sizeof(LNode)) ② scanf(&s->data) ③ s->next = L->next ④ L->next = s 算法分析：由上可看出每次插入一个结点所需的时间为 O(1) ∴头插法创建单链表的时间复杂度 T(n) = O(n) 算法 3 带头结点，用头插法创建表 Status CreateList_L( LinkList &L){ // 空链表的建立 L = (LinkList )malloc( sizeof( LNode)); // 生成头结点 if ( L == NULL ) exit(OVERFLOW); L->next = NULL; // 构造空表 // 若是循环链表，则仅将上一语句改为：L->next = L；其余不变 bCycleFlag = 1; // 控制是否继续循环插入新结点 // 循环插入新结点到头结点*L 之后 while(bCycleFlag){ scanf( &e ); // 输入待插的元素 ai-1 ai p 1 ai+1 2 3 4 存储池 q
