第二章线性表 线性表的定义 线性表的顺序表示 线性表的链式表示 一元多项式的运算 2.1线性表的类型定义 >线性表 构定义:n个数据元素的有限序列 (A,B,C,…,X,Y,Z) (a,a2,…,ail,ai,ai+1,…,an-1,an) 线线性表的逻辑特性 线性表中的所有数据元素,其数据类型是 致的 >数据元素在表中的位置只取决于它们自己 的序号,数据元素之间的相对位置是线性 的
1 第二章 线性表 线性表的定义 线性表的顺序表示 线性表的链式表示 一元多项式的运算 数 据 结 构 之 线 性 表 2 2.1 线性表的类型定义 ¾ 线性表 ¾ 定义： n 个数据元素的有限序列。 ( A , B , C , ...... , X , Y , Z ) ( a 1 , a 2 , ... , a i -1 , a i , a i + 1, ... , a n - 1 , a n ) ¾ 线性表的逻辑特性： ¾线性表中的所有数据元素，其数据类型是 一致的； ¾数据元素在表中的位置只取决于它们自己 的序号，数据元素之间的相对位置是线性 的
>基本术语 结 >直接前驱:a1针对a >直接后继:a+1 线性表的长度:是指线性表中数据 线性表 元素的个数,n=0时为空表。 >位序:下标i是数据元素a1,在线 性表中的位序 >线性表抽象数据类型的定义 ADT List{数据对象:D={a|a;∈ ElemNet,i 据 构数据关系:R1={ai-1,ai>|ai-1,ai∈D,i=1,2…,n} >基本操作:&符号说明函数参数是引用型 之 Initlist(&L ListLength(L) Destroy List(&L) GetElem(L, i, &e) 线 Clearlist(&L) Locate Elem, e) 表 ListEmpty(&L) PriorElem(L, cur e, &pre e) ListInsert(&L, i, e) ListDelete(&L, i, &e)
2 数 据 结 构 之 线 性 表 3 ¾基本术语 ¾ 直接前驱： a i - 1 针对 a i ¾ 直接后继： a i + 1, ¾ 线性表的长度：是指线性表中数据 元素的个数，n = 0 时为空表。 ¾ 位序：下标i是数据元素ai ，在线 性表中的位序。 数 据 结 构 之 线 性 表 4 ¾ 线性表抽象数据类型的定义 ¾ 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 = 1,2,...,n } ¾ 基本操作：& 符号说明函数参数是引用型 InitList(&L) ListLength(L) DestroyList(&L) GetElem(L , i , &e) ClearList(&L) LocateElem(L , e) ListEmpty(&L) PriorElem(L , cur_e , &pre_e) ListInsert(&L , i , e) ListDelete(&L , i , &e) .......}
求A=A∪B的算法 分析:建立线性表La、Lb,将La中不存在 的b插入La中,因此,本算法的基本操作是 据结构 查找(比较 基于逻辑结构的算法描述 void Union( List &La, List Lb)i La len=ListLength(La); Lb len=Listlength (Lb) for(i-I; i<=Lb len; i++) 线性表 GetElem(Lb,, e); /*0(1)*/ if( Locate Elem (La, e)/O(La len)*/ ListInsert(La, ++La len, e);/*o(1)*/ 算法分析:考虑算法的最费时执行状况,作 为算法的时间复杂度O0La_1en*Lb-1en) 求LC=LA+LB的算法:La和Lb的元素按升序 排列,将La和Lb归并为Lc。 st void Merge List( List La, List Lb, List &Lc)( 据 结 InitList(Lc); k=0; La_len=ListLength(La); Lb_len=-List Length(Lb) While((i<=La len)&&(j<=Lb len))( GetElem (La, i, ai); GetElem(Lb,,bj); if(ai<=bj) ListInsert(Lc, ++k, ai); ++i else ListInsert(Lc, ++k, bj); ++Jl) 表 while (i<=La len)i GetElem ( La, i++, ai); ListInsert(Lc, ++k, ai);) while (i<=lb len)t GetElem(Lb,j++, bj); ListInsert(Lc, ++k, bj);33 算法分析:时间复杂度OLa-1en+Lb-len)
3 数 据 结 构 之 线 性 表 5 ¾ 求 A = A ∪ B 的算法 ¾ 分析：建立线性表 La、Lb，将La中不存在 的 bi插入 La中，因此，本算法的基本操作是 查找(比较) ¾ 基于逻辑结构的算法描述： void Union( List &La ,List Lb){ La_len=ListLength(La);Lb_len=ListLength(Lb); for(i=1;i<=Lb_len;i+ +){ GetElem(Lb,i,e); /* O(1) */ if(!LocateElem(La,e)) /* O(La_len ) */ ListInsert(La,+ +La_len,e); /* O(1 ) */ } } ¾ 算法分析：考虑算法的最费时执行状况，作 为算法的时间复杂度 O(La_len*Lb_len) 数 据 结 构 之 线 性 表 6 ¾求 LC = LA+ LB 的算法:La和Lb的元素按升序 排列，将La和Lb归并为Lc。 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)) { 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); } } 算法分析：时间复杂度 O(La_len+Lb_len)
>线性表的存储结构 顺序存储的线性表,叫 顺序表 >链式存储的线性表,叫 链表 22线性表的顺序表示和实现 据>概念 构 用一组地址连续的存储单元依次存储线性 表的数据元素。 顺序表的特点是:逻辑关系上相邻的两个 元素在物理位置上也相邻 顺序表是随机存取的存储结构 可以随机存取(所需时间相同)表中任 元素,因为它的存储位置可用一个简单、直观 的公式(位序的线性函数)来表示
4 数 据 结 构 之 线 性 表 7 ¾线性表的存储结构 ¾顺序存储的线性表，叫 顺序表 ¾链式存储的线性表，叫 链表 数 据 结 构 之 线 性 表 8 2.2 线性表的顺序表示和实现 ¾ 概念 ¾ 用一组地址连续的存储单元依次存储线性 表的数据元素。 ¾ 顺序表的特点是：逻辑关系上相邻的两个 元素在物理位置上也相邻。 ¾ 顺序表是随机存取的存储结构： 可以随机存取（所需时间相同）表中任一 元素，因为它的存储位置可用一个简单、直观 的公式（位序的线性函数）来表示
数据元素ai的存储位置(内存地址): (不同于位序i) 据结构 Loc( ai)=Loc (ai-1)+L Loc(ai =Loc(a 1)+(i-1)"L Loc(ai)是ai在内存中的第一个字节的 地址。 L是一个元素的字节数。 表例如:整型线性表存储在内存中的地址是 C00,表中的第7个元素的存储地址是 C000+2*6=C00C 顺序存储结构 数据结构 >定义 A typedef int Elem Type typedef Elemtype ET; 尺之 typedef struct ElemType *elem;动态空间基址 length;∥实际元素个数 int istsize;∥当前分配的存储 } Sqlist;/容量(以 Sizeof( ElemType)为单位) Sqlist是顺序表的类型名
5 数 据 结 构 之 线 性 表 9 ¾ 数据元素a i 的存储位置（内存地址）： （不同于位序 i ） Loc ( a i )=Loc ( a i -1 ) + L Loc ( a i )=Loc ( a 1 ) +( i -1 )*L Loc(a i )是a i 在内存中的第一个字节的 地址。 L 是一个元素的字节数。 例如：整型线性表存储在内存中的地址是 C000，表中的第7个元素的存储地址是 C000+2*6=C00C 数 据 结 构 之 线 性 表 10 ¾ 顺序存储结构 ¾ 定义 typedef int ElemType ; typedef Elemtype ET; typedef struct{ ElemType *elem ; //动态空间基址 int length ; //实际元素个数 int listsize ; //当前分配的存储 }SqList ; //容量(以sizeof(ElemType)为单位) SqList 是顺序表的类型名