第二章线性表 线性表的定义 线性表的顺序表示 线性表的链式表示 一元多项式的运算 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 ∈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 是顺序表的类型名
存储地址 内存状态 元素序号 数据结构 线性表 空闲 线性表的顺序存储结构示意图 >重新分配动态存储空间的函数 数据结构 realloc(原动态区首址,字节数 其功能为: >申请新的动态存储空间(成功或失败); >将原动态区的数据拷贝到新动态区; >释放原动态存储区 返回新存储区首地址(无类型) >用途:当原动态区不够用时,追加动态 存储区;
6 数 据 结 构 之 线 性 表 11 存储地址 内存状态 元素序号 空闲 a a a a 1 2 i n : : : : : : : b b+L b+(i-1)L b+(n-1)L B+(maxlen-1)L 1 2 i n 线性表的顺序存储结构示意图 数 据 结 构 之 线 性 表 12 ¾ 重新分配动态存储空间的函数 realloc(原动态区首址，字节数) ¾其功能为： ¾申请新的动态存储空间(成功或失败); ¾将原动态区的数据拷贝到新动态区; ¾释放原动态存储区; ¾返回新存储区首地址（无类型）。 ¾用途：当原动态区不够用时，追加动态 存储区；
顺序表的操作 >构造一个空的线性表L ws #define List Init Size 100 A #define ListIncrement 10 2 Status InitList Sq( SqList &L) L elem=(ET)malloc (List Init Size sizeof(ET)) if(L. elem--NULL) 性 exi( OVERFLOW);/存储分配失败* 表 Llength=0: /空表的长度* L listsize= List init size;初始存储容量 return OK: 插入操作:在顺序表L中第个位置上插 入一个新的元素e。 据 >形式参数为:&L,i,e 算法步骤如下 构 对输入参数的安全性检查:插入位置i应落在 表长+1范围内,即:1≤i≤L. length+1 存储空间的处理:若原表的存储空间已满,应追 加存储空间的分配 数据块的搬移:将表中从i到L. length位置上的 所有元素往后移动一个位置; >在第i个位置上存储新的元素e,表长增1 注意:逻辑位置(序号)i对应的存储下 标是i-1
7 数 据 结 构 之 线 性 表 13 ¾ 顺序表的操作 ¾ 构造一个空的线性表 L #define List_Init_Size 100 #define ListIncrement 10 Status InitList_Sq( SqList &L){ L.elem=(ET*)malloc(List_Init_Size*sizeof(ET)); if(L.elem==NULL) exit(OVERFLOW); /*存储分配失败*/ L.length=0; /* 空表的长度 */ L.listsize=List_Init_Size; /* 初始存储容量 */ return OK; } 数 据 结 构 之 线 性 表 14 ¾ 插入操作：在顺序表L中第i个位置上插 入一个新的元素e。 ¾形式参数为：&L ,i , e ； ¾算法步骤如下： ¾对输入参数的安全性检查: 插入位置 i 应落在 表长＋１范围内，即： 1≤ i ≤ L.length+1 ¾存储空间的处理：若原表的存储空间已满，应追 加存储空间的分配； ¾数据块的搬移：将表中从i到L.length位置上的 所有元素往后移动一个位置； ¾在第i个位置上存储新的元素e,表长增１; ¾注意：逻辑位置（序号）i 对应的存储下 标是i-1
顺序表--插入操作算法描述之 s Status ListInsert_Sq(SqList &L, int i, ET e) if (iLlength+1)return ERROR; I*s if(L length >=L listsize) P=(ET )realloc (L elem, (L listsize+10)*sizeof(ET)) if(p-NULL) exit(OVERFLOW); L elem=p; Llistsize+=ListIncrement; 线性表 for(j=Llength; j>i; -j) Lelem j=L elem j-1; Lelemie; ++.length; return OK: 顺序表-插入操作算法描述之二 Status ListInsert Sq(sqlist &L, int i, ET e)t if (i= L listsize) 构 P=(ET"realloc(Lelem, L. listsize-+10)* sizeof(ET); if(p-NULL) exit(OVERFLOW); L elem=p; L listsize+=ListIncrement; q=&( L elemi1);*q= L elem+(i1)插入位置 for (p=&(L elem[.length-l D;>=g:--p) (p+1)=p ge: ++Llength return OK;
8 数 据 结 构 之 线 性 表 15 ¾顺序表----插入操作算法描述之一 Status ListInsert_Sq(SqList &L , int i , ET e){ if ( iL.length+1) return ERROR; if(L.length >= L.listsize){ p=(ET*)realloc(L.elem,(L.listsize+10)*sizeof(ET)); if (p==NULL) exit(OVERFLOW); L.elem=p; L.listsize+=ListIncrement; } for( j=L.length ; j>=i ; --j ) L.elem[j]=L.elem[j-1]; L.elem[j]=e ; ++L.length ; return OK; } 数 据 结 构 之 线 性 表 16 ¾顺序表----插入操作算法描述之二 Status ListInsert_Sq(SqList &L , int i , ET e){ if ( iL.length+1) return ERROR; if (L.length >= L.listsize){ p=(ET*)realloc(L.elem,(L.listsize+10)*sizeof(ET)); if (p==NULL) exit(OVERFLOW); L.elem=p; L.listsize+=ListIncrement; } q=&(L.elem[i-1]); /* q=L.elem+(i-1) 插入位置 */ for (p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p; *q=e ; ++L.length ; return OK; }
插入操作的算法性能分析 据结构 >空间复杂度是O(1) >时间复杂度:O(m),其中n= Llength 步骤(1)、(2)、(4)的时 间复杂度都是常数,即:O(1); 步骤(3)的基本操作是数据移动 线性表 最坏的情况下(在第一个位置上插入元素), 需要移动n个元素; 平均情况下(等概率),需移动表中n/2 个元素,最好的情况是不移动元素 因此,插入操作算法的时间复杂度是Om) 删除操作:长为n的线性表L(a1,a2,… 数据结构 an),删除a1,并把它送入某单元e n-1 n-1 18 顺序存储结构的删除操作
9 数 据 结 构 之 线 性 表 17 ¾插入操作的算法性能分析 ¾空间复杂度是 O( 1 ) ¾时间复杂度： O(n) , 其中n= L.length ¾步骤（１）、（２）、（４）的时 间复杂度都是常数，即：O ( 1 ); ¾步骤（３）的基本操作是数据移动， 最坏的情况下(在第一个位置上插入元素)， 需要移动n个元素； 平均情况下（等概率），需移动表中 n/2 个元素，最好的情况是不移动元素。 因此，插入操作算法的时间复杂度是O(n); 数 据 结 构 之 线 性 表 18 ¾ 删除操作：长为n的线性表L(a1,a2, … , an ), 删除ai ，并把它送入某单元e e ai a1 a2 a3 ai-1 ai an : : 1 2 3 i-1 i n-1 i+1 n : : a1 a2 a3 ai-1 an : : 1 2 3 i-1 i n-1 i+1 n : : ai+1 顺序存储结构的删除操作
据结构 形式参数为:&L,i,&e; 算法步骤如下: 对输入参数的安全性检查:删除位置i 应落在表长范围内,即:1≤i≤ Llength 取出元素值赋给e 线性表 数据块的搬移:将表中从计1到 Llength 位置上的所有元素往前移动一个位置; 表长减1:- Llength; 算法 st Status ListDelete Sq(sqlist &L, int i, ET&e)i a if(iL length) return ERROR; 构 e=L.elemi-1: for(j=i; j<Llength;j++ L.elemj-1=Lelemi; L.length--; 表 算法分析:基本操作是什么?时间复杂度 是多少 20
10 数 据 结 构 之 线 性 表 19 ¾形式参数为：&L ,i , &e ； ¾算法步骤如下： ¾对输入参数的安全性检查: 删除位置 i 应落在表长范围内，即：1≤ i ≤ L.length ¾取出元素值赋给e： ¾数据块的搬移：将表中从i+1到L.length 位置上的所有元素往前移动一个位置； ¾表长减１：--L.length; 数 据 结 构 之 线 性 表 20 ¾算法 Status ListDelete_Sq(SqList &L , int i , ET &e){ if(iL.length) return ERROR; e=L.elem[i-1]; for( j=i ; j<L.length;j++) L.elem[j-1]=L.elem[j]; L.length--; } 算法分析：基本操作是什么？时间复杂度 是多少？