中国科学技术大学：《数据结构及其算法》课程教学资源（教案讲义）第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∈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：排序，删除

程序设计——数据结构第二章线性表基本概念、线性表的应用第 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);

敦察第二章线性表程序设计—数据结构基本概念、线性表的应用 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

程序设计——数据结构第二章线性表基本概念、线性表的应用第 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

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

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