数据结构课件：第2章 线性表0顺序

1、第2章 线性表第3章 栈和队列第4章 串引言线性结构线性结构的特点在元素的非空有限集中(1)存在唯一的一个被称作“第一个”的数据元素(2)存在唯一的一个被称作“最后一个”的数据元素(3)除第一个之外，每个元素均只有一个前驱(4)除最后一个之外，每个元素均只有一个后继引言线性结构的特点线性结构表达式：(a1, a2, , an) 线性结构反映了结点间一对一的逻辑关系线性结构包括：线性表、堆栈、队列、字符串等。其中，最典型、最常用的是线性表。引言一元多项式的表示及相加第2章 线性表线性表的类型定义线性表的顺序表示和实现线性表的链式表示和实现2.1 线性表的类型定义线性表的定义由n (n0)个数据元

2、素组成的有限序列。其中数据元素的个数n定义为表的长度，当 n=0 时称为空表。一般将非空的线性表(n0) 记作： (a1, a2, ai-1, ai, ai+1, an) (1in) 2.1 线性表的类型定义线性表的定义例1：26个英文字母组成的字母表 (A，B，C, , Z)例2：某校从1978年到1983年各种型号的计算机拥有量的变化情况 (6，17，28，50，92，188)数据元素都是字母; 元素间关系是线性数据元素都是数值; 元素间关系是线性2.1 线性表的类型定义线性表的定义例3：学生健康情况登记表姓名学号性别年龄健康情况王小林790631男18健康陈 红790632女20一般刘建

3、平790633男21健康张立立790634男17 神经衰弱 数据元素都是记录; 元素间关系是线性2.1 线性表的类型定义线性表的逻辑特征(a1 , a2 , ai-1 , ai , ai1 , , an)n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长空表线性终点2.1 线性表的类型定义线性表的抽象数据类型期望：可以读写线性表的数据元素。期望：可以添加和删除线性表数据元素，线性表长度可以根据需要增长和缩短。(a1 , a2 , ai-1 , ai , ai1 , , an)2.1 线性表的类型定义线性表的抽象数据类型ADT

4、List 数据对象：D=ai|aiElemSet,i=1,2,.,n) 数据关系: R=|ai-1,aiD,i=2,.,n) 基本操作： InitList(&L) 构造一个空的线性表L。 DestroyList(&L) 销毁线性表L。 ClearList(&L) 将L重置为空表。 PriorElem(L, cur_e, &pre_e) 若cur_e是L的元素，则用pre_e 返回它的前驱， NextElem(L, cur_e, &next_e) 若cur_e是L的元素，则用next_e返回它的后继， GetElem(L, i, &e) 用e返回L中第i个元素的值。 PutElem(&L, i,

5、 e) L中第i个元素赋值同e的值。 ListInsert(&L, i, e) 在L的第i个元素之前插入新的元素e，L的长度增1。 ADT List2.1 线性表的类型定义线性表的基本操作InitList( &L )操作结果：结构初始化，构造一个空的线性表LDestroyList( &L )初始条件：线性表L已存在。操作结果：销毁线性表L。2.1 线性表的类型定义线性表的基本操作GetElem( L,i, &e )初始条件：线性表L已存在，且1i表长操作结果：用 e 返回L中第i个元素的值LocateElem( L, e, compare( ) )初始条件：L已存在，compare()是元素判

6、定函数操作结果：返回L中第1个与e满足关系compare()的元素的位序，若这样的元素不存在，则返回值为0。2.1 线性表的类型定义线性表的基本操作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无定义2.1 线性表的类型定义线性表的基本操作ListInsert

7、( &L, i, e )初始条件：线性表L已存在，1i表长+1操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。 ListLength( L )初始条件：线性表L已存在。操作结果：返回L中元素个数2.1 线性表的类型定义线性表的基本操作ListDelete(&L, i, &e)初始条件：L已存在且非空，1i表长操作结果：删除L的第i个元素，用e返回其值，L的长度减1。ListEmpty( L )初始条件：线性表L已存在操作结果：若L为空表，返回TRUE，否则FALSE2.1 线性表的类型定义线性表的基本操作ListTraverse(L, visit( )初始条件：线性表L已存在。操作

8、结果：依次对L的每个元素调用visit()函数。一旦visit()失败，则操作失败ClearList( &L )初始条件：线性表L已存在。 操作结果：将L重置为空表。2.1 线性表的类型定义利用上述定义的操作完成更复杂的操作例1：假设有两个集合A和B分别用两个线性表LA和LB表示。即线性表中的数据元素即为集合中的成员，现要求一个新集合 AAB2.1 线性表的类型定义利用上述定义的操作完成更复杂的操作思路为： (1) 从线性表LB中依次取得每个数据元素； (2) 依值在线性表LA中进行查访； (3) 若不存在，则插入。2.1 线性表的类型定义利用上述定义的操作完成更复杂的操作void union

9、(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 相同的元素，则插入之 / union2.1 线性表的类型定义利用上述定义的操作完成更复杂的操作例2：已知一个非纯集合B，(即B中包含有相同

10、元素)试构造一个纯集合A，使A中只包含B中所有值各不相同的数据元素。(假设B为有序序列)2.1 线性表的类型定义利用上述定义的操作完成更复杂的操作思路为： (1) 创建一个空的线性表LA; (2) 从线性表LB中依次取得每个数据元素； (3) 依值在线性表LA中进行查访； (4) 若不存在，则插入之。2.1 线性表的类型定义利用上述定义的操作完成更复杂的操作void purge(List &La, List Lb) / 构造La，使其只包含Lb中所有值不相同的元素 InitList(LA); La_len = ListLength(La); Lb_len = ListLength(Lb); f

11、or (i = 1; i = Lb_len; i+) GetElem(Lb, i, e); / 取Lb中第i个元素赋给e if( ! equal (en, e) ) ListInsert(La, +La_len, e); en = e; / La中不存在和e相同的元素，则插入 / purge2.1 线性表的类型定义利用上述定义的操作完成更复杂的操作例3：已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。2.1 线性表的类型定义利用上述定义的操作完成更复杂的操作void mergelist(list la, lis

12、t 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); w

13、hile(j=lb_len) getelem(lb, j+, bj); listinsert(lc, +k, bj); 2.1 线性表的类型定义线性表的抽象数据类型ADT List 数据对象：D=ai|aiElemSet,i=1,2,.,n) 数据关系: R=|ai-1,aiD,i=2,.,n) 基本操作： InitList(&L) 构造一个空的线性表L。 DestroyList(&L) 销毁线性表L。 ClearList(&L) 将L重置为空表。 PriorElem(L, cur_e, &pre_e) 若cur_e是L的元素，则用pre_e 返回它的前驱， NextElem(L, cur_e

14、, &next_e) 若cur_e是L的元素，则用next_e返回它的后继， GetElem(L, i, &e) 用e返回L中第i个元素的值。 PutElem(&L, i, e) L中第i个元素赋值同e的值。 ListInsert(&L, i, e) 在L的第i个元素之前插入新的元素e，L的长度增1。 ADT List2.1 线性表的类型定义线性表的抽象数据类型2.2 线性表的顺序表示及实现线性表的顺序表示线性表的顺序实现顺序表的运算效率分析2.2 线性表的顺序表示及实现线性表的顺序表示线性表的顺序表示又称为顺序存储结构，即把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。顺序存储

15、方法：用一组地址连续的内存单元存储线性表的元素，可用数组V n来实现。逻辑上相邻，物理上也相邻线性表顺序存储特点2.2 线性表的顺序表示及实现a1a2aian 地址 内容 元素在表中的位序1i2n空闲区lLOC(a1) = bb + lb +(i - 1)lb +(n - 1)lb +(maxlen - 1)l2.2 线性表的顺序表示及实现线性表顺序存储特点1)逻辑上相邻的数据元素, 物理上也相邻；2)若已知表中首元素在存储器中的位置, 则其它元素存放位置亦可利用数组下标求出。计算方法是： 设首元素a1的存放首地址为LOC(a1) 设每个元素占用存储空间为l字节，则表中任一数据元素的存放地址为

16、： LOC(ai) = LOC(a1) + (i1)l LOC(ai+1) = LOC(ai) + l a1a2aianLOC(a1) = bb + lb +(i - 1)lb +(n - 1)lb +(maxlen - 1)l2.2 线性表的顺序表示及实现线性表的顺序表示例1：设是一维数组，下标的范围是0到9，每个数组元素用相邻的5个字节存储。存储器按字节编址，设存储数组元素0的第一个字节的地址是98，则3的第一个字节的地址是 113因此：LOC(M3) = 98 + (30)5 =113解：地址计算通式为：LOC(ai) = LOC(a1) + (i1)l2.2 线性表的顺序表示及实现顺序

17、表的实现1.分配连续内存区域存储线性表2.插入数据元素3.删除数据元素4.修改数据元素2.2 线性表的顺序表示及实现分配连续内存区域存储线性表静态分配和动态分配两种不同的方法静态分配数组困扰我们的问题：数组应该有多大？根据用户需求增加或者减少空间，必须重新去修改程序？在大多数情况下会浪费大量的内存空间2.2 线性表的顺序表示及实现分配连续内存区域存储线性表如何动态分配？首先定义一个数据元素指针，通过malloc()得到一个用于存储线性表的空间，并把该空间的首地址赋给这个指针(强制类型转换)。访问动态存储分配的线性表中的元素和访问静态存储分配时的情况完全相同，可采用指针方式或数组下标方式。2.2

18、 线性表的顺序表示及实现线性表的动态分配顺序存储结构# define LIST_INIT_SIZE 100 / 线性表存储空间的初始分配量# define LISTINCREMENT 10 / 线性表存储空间的分配增量Typedef struct /若后面不再用，可省略结构名 ElemType *elem; /表基址 int length; /表长（特指元素个数） int listsize; /表当前存储容量（字节数）SqList;2.2 线性表的顺序表示及实现构造线性表Status InitList_Sq( SqList &L ) /构造一个空的线性表L。 L.elem = (ElemTyp

19、e*)malloc( LIST_INIT_SIZE * sizeof( ElemType) ); If ( ! L.elem ) exit ( OVERFLOW ) ; / 存储分配失败 L.length = 0; / 空表长度为0 L.listsize = LIST_INIT_SIZE; / 初始存储容量 return OK; / InitList_Sq存储分配，返回void型的指针强制类型转换，转换为指向ElemType类型的指针向线性表中第i个位置插入一个元素a1a2ai-1aian2.2 线性表的顺序表示及实现a1a2ai-1aiana1a2ai-1aianea1a2ai-1aiana

20、1a2ai-1aiana1a2ai-1eaian表的长度增加12.2 线性表的顺序表示及实现向线性表中第i个位置插入一个元素分析：线性表的逻辑结构发生什么变化？ （a1, , ai-1, ai, , an） 改变为,（a1, , ai-1, e, ai, , an）2.2 线性表的顺序表示及实现向线性表中第i个位置插入一个元素1.检查i的合法性2.检查线性表是否为满，若是则动态分配存储3.从第i个插入位置起，将该位置元素以及其后所有位置上的元素均后移一个位置4.把新元素写入到空出的位置上5.线性表的长度加12.2 线性表的顺序表示及实现向线性表中第i个位置插入一个元素status listin

21、sert ( &L,i,e) if (iL.len+1) return ERROR; / i值不合法 if (L.len = = L.lsize) / 当前存储空间已满，增加分配 newbase = (Elemtype * ) realloc(L.elem, (L.lsize + LISTINCREMENT) * (sizeof(ElemType); if (!newbase) exit(overflow); / 存储分配失败 L.elem = newbase; / 新基址 lsize += LISTINCREMENT; / 增加存储容量 q = &(L.elemi-1); / q为插入位置

22、for (p = &(L.elemL.len-1);p=q;-p) *(p+1) = * p; / 元素后移 *q = e; +L.len; / 插入e，表长增1 return OK; /listinsert注意：C语言中数组的下标从“0”开始，因此，若L是SqList类型的顺序表，则表中第i个数据元素是L.elemi-1。 例：ListInsert_Sq(L, 5, 66) 2.2 线性表的顺序表示及实现21 18 30 75 42 56 8721 18 30 75L.len-10pppq87564266q = &(L.elemi-1); for (p = &(L.elemL.len-1);

23、 p = q; -p) *(p+1) = *p;*q = e;pfor (j=L.len-1; j=i-1; j) L.elemj+1=L.elemj;L.elemi-1=e向线性表中第i个位置删除一个元素a1a2ai-1aiai+1an2.2 线性表的顺序表示及实现a1a2ai-1aiai+1ana1a2ai-1ai+1ai+1andeletea1a2ai-1ai+1ana1a2ai-1ai+1anan表的长度减少12.2 线性表的顺序表示及实现向线性表中第i个位置删除一个元素分析：线性表的逻辑结构发生什么变化？ （a1, , ai-1, ai, ai+1, , an） 改变为,（a1, ,

24、 ai-1, ai+1, , an）2.2 线性表的顺序表示及实现向线性表中第i个位置删除一个元素1.检查i的合法性；2.删除第i个位置的元素，即使后面第i至第n个元素(共 ni个)依次前移一个位置；3.使线性表的长度减12.2 线性表的顺序表示及实现向线性表中第i个位置删除一个元素status ListDelete ( &L,i,&e) if (iL.len ) return ERROR; / 删除位置不合法 p = &(L.elemi-1); / p 为被删除元素的位置 e = *p; / 被删除元素的值赋给 e q = L.elem + L.len 1; / 表尾元素的位置 for (+

25、p; pq; +p) *(P - 1) = * P; / 被删除元素之后的元素左移 - L.len; / 表长减1 return OK; / ListDelete例：ListDelete_Sq(L, 5, e) 2.2 线性表的顺序表示及实现21 18 30 75 42 56 8721 18 30 75L.len-10pppq8756p = &(L.elemi-1);q = L.elem+L.len-1;for (+p; p = q; +p) *(p-1) = *p; p*e=L.elemi-1;for (j=i; j=L.len-1; j+) L.elemj-1=L.elemj;2.2 线性表的顺序表示及实现顺序表的运算效率分析时间效率分析:算法时间主要耗费在移动元素的操作上，因此，计算时间复杂度的基本操作T (n) = O(移动元素次数)移动元素的个数取决于插入或删除元素的位置2.2 线性表的顺序表示及实现顺序表的运算效率分析讨论：若在长度为n的线性表的第i位前插入一元素，则向后移动元素的次数f (n)为:思考若插入在尾结点之后，则根本无需移动(特别快)；若插入在首结点之前，则表中元素全部要后移(特别慢)若要考虑在各种位置插入(共n+1种可能)的平均移动次数，该如何计算？f (n) = n i