数据结构 线性表 第二章 线性表 主讲：张昱 重点：顺序表和链表上各种基本算 yuzhang@ustc.edu 法的实现及相关的时间性能分析 0551-3603804 难点：线性表应用的算法设计 13 273 第二章线性表 2.1线性表的类型定义 21线性表的类型定义 ·定义 2.2线性表的顺序表示和实现 n(>0)个戴摄元素的有限序列，记作(a,….n4,a) 2.3线性表的链式表示和实现 其中，4是表中数据元意，n是表长度(a-0时称为空表) 2.3.1线性链表 2.3.2循还链表 ■逻辑特征 2.3.3能态链表 n>0时 2.3.4动杰链表与静杰链袁 ·有且仅有一个“第一个"”戴排元素 2.3.5双向能意2.3.6其他袁示 。有且仅有一个“最后一个”数据元素 2.4基王链凌的算法设计 ,除第一个数据元素外，其它元素有且仅有一个直接前驱 2.5一元多项式的表示及相加 。除最后一个数据元素外，其它元素有且仅有一个直接后继 33 73 2.1线性表的类型定义-ADT List LocateElem(L,e.compare)) ,ADT Listy定义 PriorElem(L,cur_e &pre_e) 作 作结果，构地一十空的线性表虹 Des Listinsert(&L,i,e ClearList(&L) 代整壁为空味 : 装数装RuE,香F处3死 L帐 初己存在 去装无快 作铺果做衣对L的每外数描元求调用面敏vs训，一且v修出)失败，则量作失败 )ADT List 图 67 画
1/73 数据结构——线性表 主讲：张昱 yuzhang@ustc.edu 0551-3603804 2/73 重点：顺序表和链表上各种基本算 法的实现及相关的时间性能分析 难点：线性表应用的算法设计 第二章 线性表 3/73 第二章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 静态链表 2.3.4 动态链表与静态链表 2.3.5 双向链表 2.3.6 其他表示 2.4 基于链表的算法设计 2.5 一元多项式的表示及相加 4/73 2.1 线性表的类型定义 定义 n(≥0)个数据元素的有限序列,记作(a1, …ai-1, ai , ai+1,…, an) 其中，ai是表中数据元素，n 是表长度(n=0时称为空表) 逻辑特征 n>0时 有且仅有一个“第一个”数据元素 有且仅有一个“最后一个”数据元素 除第一个数据元素外，其它元素有且仅有一个直接前驱 除最后一个数据元素外，其它元素有且仅有一个直接后继 5/73 2.1 线性表的类型定义-ADT List ADT List定义 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中数据元素的个数 6/73 2.1 线性表的类型定义 ADT List定义 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中第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线性表的类型定义-ADT List 2.1线性表的类型定义-例2-1 ,ADT List定义 ,基于ADT List的算法设计 ·P19 ·例2-1复设利用两个战性表La利b分别表示两个集合A和B 基本操作 (即：戴性表中的敏据元素即为果合中的成黄】，观要求一 个新的集金A一AUB。 。初始化、筛毁 ,查询：个体、整体 物入：线性表La、线性表b 。动志变化：播入、时除 输出：变化了的La 争union(&La,Lb) 处理方法：扩大线性表La,将存在于线性表Lb中而不存在于 ·重点掌提以下三个基本操作 线性表La中的敏搭元素辑入到铁性表La中去。 。GetElem(L,i,&e) 8 步骤： ListInsert(&L,i,e) ~1,从线性表b中依次取得每个数据元素 ListDelete(&L,i,&e) LocateElem 2,依值在线性表La中进行查访 注意：接口的形式可以略有变化，如e=GetElem(L,) 不存在，则插入之 7 回 1的 73 回 2.1线性表的类型定义-例2-1 21线性表的类型定义削2.2 void union(List &La,List Lb){ ,基于ADT List的算法设计 /∥将所有在城性表b中不在La中的数元素入到a中 La_len ListLength(La); 。例2-2巴加旋性兼La布Lb中的数据元素妆值摔递减有序掉 e是变◆ Lb_Jen=ListLength(b:/求，性囊的长度 列，要求将La不Lb归并成一个新的战性表L,且Lc中的数据 调用时不 元素仍：值非递减有序神列。 加&符号 =i<=地e;it+) GetElem(b,同：/取Lb中第i个数W元肃减皓e 输入：线性表La、线性表b(均按值丰道减有序排列) if(LocateElem(La.e.eoual)) 输出：Lc(拨值非道减有序排列merge(La,Lb,&Lc) /La中不存在和e相同的元豪，则插入之 处理方法：：La和Lb均按值非通减有序排列 ListInsert(La,++La_len,e); ∴设置两个位置指示器和j,分别指肉L和Lb中的某个元 )/union 素，初始均指向第1个。LC初始化为空表。 比较和所指肉的元景a和bj,进取值小的插入到Lc的尾部， T(na,nb)=O(b*na),na、nb表示La表和Lb表的长度 并使相应的位置指示卷向后移。 算法：算法2.2P21 9/73 图 10y73 图 2.1线性表的类型定义-例2-2 2,1线性表的类型定义-例2-2 void MergeList(List La,List Lb,List &Lc){ a和Lb中的元素教值非 /归La和Lb得到断的，性表Lc,Lc的元素拔值非递减排列。 ListInsert(Lc,++k,ai); InitList(Lc); i=j=1;k=0: while (j<=Lb_len){ La_len ListLength(La); GetElem(Lb,j++,bj); Lb len ListLength(Lb): ListInsert(Lc,++k,bj); while ((i<=La_len)&&(j<=Lb_len)){ a和b均非空 }//MergeList GetElem(La,i,ai);GetElem(Lb,j,bj); if (ai<=bj){ ListInsert(Lc,++k,ai);++i; T(na,nb)=O(na+nb) ListInsert(Lc,++k,bj);++j; 1/ 图 12万 图
7/73 2.1 线性表的类型定义-ADT List ADT List定义 P19 基本操作 初始化、销毁 查询：个体、整体 动态变化：插入、删除 重点掌握以下三个基本操作 GetElem(L, i ,&e) ListInsert(&L, i, e) ListDelete(&L, i, &e) 注意: 接口的形式可以略有变化,如 e = GetElem(L, i) 8/73 2.1 线性表的类型定义-例2-1 基于ADT List的算法设计 例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 P20 ListLength GetElem LocateElem ListInsert 9/73 2.1 线性表的类型定义-例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)) // La中不存在和e相同的元素，则插入之 ListInsert(La, ++La_len, e); } } // union T(na, nb) =O(nb*na), na、nb表示La表和Lb表的长度 e是变参, 调用时不 加&符号 10/73 2.1 线性表的类型定义-例2-2 基于ADT List的算法设计 例2-2 已知线性表La和Lb中的数据元素按值非递减有序排 列，要求将La和Lb归并成一个新的线性表Lc，且Lc中的数据 元素仍按值非递减有序排列。 输入：线性表La、线性表Lb(均按值非递减有序排列) 输出：Lc(按值非递减有序排列) Îmerge(La, Lb, &Lc) 处理方法：∵La和Lb均按值非递减有序排列 ∴设置两个位置指示器i和j，分别指向La和Lb中的某个元 素，初始均指向第1个。Lc初始化为空表。 比较i和j所指向的元素ai和bj，选取值小的插入到Lc的尾部， 并使相应的位置指示器向后移。 算法：算法2.2 P21 11/73 2.1 线性表的类型定义-例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; } } 12/73 2.1 线性表的类型定义-例2-2 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 T(na, nb) =O(na+nb)
2.1线性表的类型定义-结论 2.2线性表的顺序表示和实现 。结论 ▣定义：用一组地址连线的存储单元依火存储线 ·使用不同的算法策略，可以得到不同时间复 性表中的数据元素 杂度的算法 ■特点：逻枰上相邻，物理上也相邻。随机存取 ,输入线性表的特征会形响算法的策略 （是否有序？…) 逻料序号12345 6 陈述问 。输出线性表的特征会形响算法的策略 688970674078 题时用 (是否有序？…) C数组下标012345 13n 回 1W万 图 2.2-顺序表的存储 2.2-顺序表类型定义（方案一） 假设每个元素占用个存储单元，则元素的存 顺序表定义 储位置： ·方案一 #define LIST_SIZE 100 LOC(a)=LOC(a)+ typedef struct{ LOC(a)=LOC(aj)+(i-1)*I ElemType elem[LIST_SIZE]; 严存情空何1 int length; 胪当前长度 12 …i )SqList_static; an 评价： ↑ 1LSTS1ZE进小，则会号顺序表上道： a+(n-1)*I idle 2)LIST SIZE过大，则女导数空间的利用率不高 15/73 图 13 图 2.2-顺序表类型定义（方案二） 2.2C中的动态分配与释放函数 方案二 C中的动态分配与释放函数 void *malloc(unsigned int size) 大小为心的韩底空间，将请空间的起地 typedef struct( ElemType 'elem; ”存储空间的基址 地址赋给p: int length: 产当前长度 free(void *p) int listsize: :当前分配的存储客量1 回收p所指向的结点空间： )SqList; .void *realloc(void *p,unsigned int size) 将D所描向的已分配内存区的大小改为size,sizc 该方案解决方案一中的上滥"问圆和“空间利用率不高问 愿，但是有时间和空间代价的。 分配成助示组 可以比原分配的空间大或小。 )必须记藏当前做性表的实际分配的空间大小： 当 引当或不再使用时，应放其所占的空间： 3)要夹现的语言能展供空间的动本分配与放理， 177万 图
13/73 2.1 线性表的类型定义-结论 结论 使用不同的算法策略，可以得到不同时间复 杂度的算法 输入线性表的特征会影响算法的策略 （是否有序？…） 输出线性表的特征会影响算法的策略 （是否有序？…） 14/73 2.2 线性表的顺序表示和实现 定义：用一组地址连续的存储单元依次存储线 性表中的数据元素 特点：逻辑上相邻，物理上也相邻。随机存取 68 89 70 67 40 78 逻辑序号 1 2 3 4 5 6 C数组下标 0 1 2 3 4 5 陈述问 题时用 15/73 2.2 -顺序表的存储 假设每个元素占用l个存储单元，则元素的存 储位置： LOC(a i+1) = LOC( a i )+l LOC(a i ) = LOC(a1)+(i-1)*l a1 a2 … a i …… … an 1 2 … i ……… n a a+l … a+(i-1)*l … … … a+(n-1)*l idle 16/73 2.2 –顺序表类型定义(方案一) 顺序表定义 方案一 #define LIST_SIZE 100 typedef struct{ ElemType elem[LIST_SIZE]; /* 存储空间*/ int length; /* 当前长度*/ }SqList_static; 评价： 1)LIST_SIZE过小，则会导致顺序表上溢； 2) LIST_SIZE过大，则会导致空间的利用率不高 17/73 2.2 –顺序表类型定义(方案二) 方案二 #define LIST_INIT_SIZE 100 /* 存储空间的初始分配量*/ #define LISTINCREMENT 10 /* 存储空间的分配增量 */ typedef struct{ ElemType *elem; /* 存储空间的基址 */ int length; /* 当前长度 */ int listsize; /* 当前分配的存储容量 */ }SqList; 该方案解决方案一中的“上溢”问题和“空间利用率不高”问 题 ，但是有时间和空间代价的 。 1) 必须记载当前线性表的实际分配的空间大小； 2) 当线性表不再使用时，应释放其所占的空间； 3) 要求实现级的语言能提供空间的动态分配与释放管理。 18/73 2.2 –C中的动态分配与释放函数 C中的动态分配与释放函数 void *malloc(unsigned int size) 生成一大小为size的结点空间，将该空间的起始 地址赋给p； free(void *p) 回收p所指向的结点空间; void *realloc(void *p, unsigned int size) 将p所指向的已分配内存区的大小改为size，size 可以比原分配的空间大或小。 old p new size 起址 返回 回收 分配成功示例
2.2-C中的动态分配与释放函数 2.2一基本操作的实现（宏与Status) C中的动态分配与释放函数 ■基本操作的实现 void *malloc(unsigned int size) P10 生成一大小为s立的站点空间，将被空间的起地 地址赋给p: /体函数结果状春代码 #define TRUE 1 free(void *p) 回收p所指询的结点空间： #define FALSE #define OK 1 void *realloc(void *p,unsigned int size) #define ERROR 0 特p所指向的已分配内存区的大小改为size,size #define INFEASIBLE -1 分配失败示 可以比原分乖的空间大或小。 #define OVERFLOW -2 条温 /体函数结果状态类型，其值为上述的状本代码 typedef int Status; 172 囵 20y3 图 2.2-基本操作的实现(InitList_Sq) 主2.2-基本操作实现(LocateElem-.s)刘 ■基本操作的实现 ■基本操作的实现 ,°化Status InitList_Sq(SqList&L) ,求表长L.length Status InitList_Sq(SqList &L){ ∥构造一个空的线性表L ,取第i个元素L.elem[i-1](0<i<L..length-+1) Lelem=(ElemType") 。按值查找 malloc(LIST_INIT_SIZE'sizeof(ElemType)); int LocateElem_Sq(SqList L,ElemType e, if (L.elem =NULL) exit(OVERFLOW); Ⅱ存储分配失败 Status("compare)(ElemType,ElemType)) L.length=0; Ⅱ空表长度为0 for(i=0;i<Llength &&!(compare)(L.elem[i],e);i++); Llistsize=LIST_INIT_SIZE; ∥初始存偏容量 if (i<L.length)returni+1; return OK; else return 0; }HIni混ist Sq 21/73 图 22/73 图 2.2-插入操作的实现 2.2-插入操作的实现（分析设计） 。基本操作的实现 ,插入操作—算法设计（算法2.4） ■插入操作 ·最：顺序表&L、领入位量、指入元廉： Status ListInsert Sq(SqList &L,int i,ElemType e) 播入分析： 12345678 15234616571064.. 后移的序是从录后一个元震开地，毫个住后移 for(j=Llength;j>=子-L.e4em0]=L.elem-1j/∥盾w 入e L.eemt-1】=ei/算个元常存放在L.elem[i-1]中，胞地下标为0 L.length Llength+1; 48y 123456789 ,法的位置：i1L.length+1 。上滥及处理： 1523464816571064 。上提搜生的条并：LlengthL.lists位e, 22/7万 图
19/73 2.2 –C中的动态分配与释放函数 C中的动态分配与释放函数 void *malloc(unsigned int size) 生成一大小为size的结点空间，将该空间的起始 地址赋给p； free(void *p) 回收p所指向的结点空间; void *realloc(void *p, unsigned int size) 将p所指向的已分配内存区的大小改为size，size 可以比原分配的空间大或小。 old p 返回 空间不够, NULL 分配失败! 分配失败示例 20/73 2.2 –基本操作的实现(宏与Status) 基本操作的实现 P10 /* 函数结果状态代码 */ #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 /* 函数结果状态类型，其值为上述的状态代码 */ typedef int Status; 21/73 2.2 –基本操作的实现(InitList_Sq) 基本操作的实现 初始化 Status InitList_Sq(SqList &L) 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 22/73 2.2 –基本操作实现(LocateElem_Sq) 基本操作的实现 求表长 L.length 取第i个元素 L.elem[i-1] (0<i<L.length+1) 按值查找 int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType)) { for(i=0; i<L.length && !(*compare)(L.elem[i],e); i++); if (i<L.length) return i+1; else return 0; } 23/73 2.2 –插入操作的实现 基本操作的实现 插入操作 Status ListInsert_Sq(SqList &L, int i, ElemType e) 15 23 46 16 57 10 64 …… 1 2 3 4 5 6 7 8 48 插入 e 0 1 2 3 4 5 6 7 i 15 23 46 16 57 10 64 …… 1 2 3 4 5 6 7 8 9 48 24/73 2.2 –插入操作的实现(分析设计) 插入操作——算法设计(算法2.4) 参数：顺序表&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，再进行插入工作；否则报错退出
2.2-插入操作的实现（算法） 2.2-插入操作的实现（算法分析） 77时u nepe 时闯复杂度 if (i<1 l i>Llength +1) return ERROR; 。频次最高的操作：移动元豪 /上避时增加空间的分配 ,上漫时，空间的再分配与复制(reoc操作分摊到每次领入操作中 if(Llength >Llistsize){ 。若能性表的长度为■，则： ,量好品推入位置为+1，此时无须暮助元素，T)-01) 为什么量引 (ElemType)al(Lele (Llistsize+LIST INCREMENT 是经品描入位量为1，此时须移动▣个元素，T(@)一0时 入newbase? (ElemType)); if newbase==NULL exit(OVERFLOW); ,平垃品假设为在第个元素之前捕入一个元素的振率， elem newbase; 空间分配失败 Llistsize+=LISTINCREMENT; 箱入时带动次最的明道值：E。=艺P,口-1+) 时，蓬免将原 川地止失 //麵入元康 等振率时，可 】+ for (j=L.length;j>=i;j--)L.elem[j]=Lelem[j-1]; Lelem[i-1]=e Llength++; p,+1 T时-0 return OK; ,空间复杂度S)-01) 25/73 回 273 图 22-刷除操作的实现 2.2-删除操作的实现（分析设计） 基本操作的实现 ·测除操作一算法设计（算法2.5） ■副除操作 。数：顺序表&L、副除位量 Status ListDelete_Sq(SqList &L int i,ElemType &e) ·除分折： 。去辣幕i个元章，则原来第+1-L.kg山个敏据元囊必须前 12345678 移，以服整第个位置 15234616571064. 。前移的顺序是从靠行+1元豪开增，是个住前修 for (j-i:j<L.length ;jt)Lelemlj-l1-L.elemlil: 剂除e i L.length-1_length-1; ,合法的位量：i1.L.length 1234567 。下及处通： 152346571064.. ,下溢没生的条件：L.length毛0 。处理：雕含在的条件中 27173 图 28/73 图 2.2-删除操作的实现（算法） 2.2-删除操作的实现（算法分析） ,则峰操作—算法设计（算法2.5） ,时间复杂度 Status ListDelete_Sq(SqList &L,int i){ 。侧次最高的操作：移助元套 若战性的长皮为，则： /位置合法性的判断 ,量好品副膝位量为，此时无须移勒元素，T(一O片 if (i<1 i>L.length return ERROR; 连品副除位量为1，此时须黄移1个元素， /剔除 T(n)-O(n): ,亚均况：假设为测膝靠个元豪的振率，则： for (j=i;j<L.length ;j++) 汇除时移动次数的厕望值： L.elem[j-1]L.elem[j]; E-2a-0 L.length--; return OK; T-0) ,空间复杂度S(a)-0山 297万 图 307万 图
25/73 2.2 –插入操作的实现(算法) 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 == 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; } 为什么要引 入newbase? 空间分配失败 时，避免将原 空间地址丢失! 26/73 2.2 –插入操作的实现(算法分析) 时间复杂度 频次最高的操作：移动元素 上溢时，空间的再分配与复制(realloc操作)分摊到每次插入操作中 若线性表的长度为n，则： 最好情况：插入位置i为n+1，此时无须移动元素，T(n)=O(1); 最坏情况：插入位置i为1，此时须移动n个元素， T(n)=O(n); 平均情况：假设pi为在第i个元素之前插入一个元素的概率， 则： 插入时移动次数的期望值： 等概率时，即 ， ∴ T(n) = O(n) 空间复杂度 S(n) = O(1) ∑ + = = − + 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 − + = + = ∑ + = 27/73 2.2 –删除操作的实现 基本操作的实现 删除操作 Status ListDelete_Sq(SqList &L, int i, ElemType &e) 15 23 46 16 57 10 64 …… 1 2 3 4 5 6 7 8 16 删除 e 0 1 2 3 4 5 6 7 i 15 23 46 57 10 64 …… 1 2 3 4 5 6 7 28/73 2.2 –删除操作的实现(分析设计) 删除操作——算法设计(算法2.5) 参数：顺序表&L、删除位置i 删除分析： 去掉第i 个元素，则原来第i+1~L.length个数据元素必须前 移，以覆盖第i个位置; 前移的顺序是从第i+1元素开始，逐个往前移 for ( j = i; j < L.length ; j++) L.elem[j-1] = L.elem[j]; L.length = L.length-1; 合法的位置：i:1..L.length 下溢及处理： 下溢发生的条件：L.length≤0 处理：隐含在i的条件中 29/73 2.2 –删除操作的实现(算法) 删除操作——算法设计(算法2.5) Status ListDelete_Sq( SqList &L, int i) { // 位置合法性的判断 if ( i<1 || i>L.length ) return ERROR; // 删除 for ( j = i; j < L.length ; j++) L.elem[j-1] = L.elem[j]; L.length--; return OK; } 30/73 2.2 –删除操作的实现(算法分析) 时间复杂度 频次最高的操作：移动元素 若线性表的长度为n，则： 最好情况：删除位置i为n，此时无须移动元素，T(n)=O(1); 最坏情况：删除位置i为1，此时须前移n-1个元素， T(n)=O(n); 平均情况：假设qi为删除第i个元素的概率，则： 删除时移动次数的期望值： 等概率时，即 ， ∴ T(n) = O(n) 空间复杂度 S(n) = O(1) ∑= = − n i de i E q n i 1 ( ) n qi 1 = 2 1 ( ) 1 1 − = ∑ − = = n n i n E n i de