数据结构第02讲线性表类型定义与顺序表.ppt

《数据结构第02讲线性表类型定义与顺序表.ppt》由会员分享，可在线阅读，更多相关《数据结构第02讲线性表类型定义与顺序表.ppt（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第2 2章章 线性表线性表2.1 2.1 线性表的类型定义线性表的类型定义2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现 2.3.1 2.3.1 线性链表线性链表 2.3.2 2.3.2 循环链表循环链表 2.3.3 2.3.3 双向链表双向链表 2.4 2.4 一元多项式的表示及相加一元多项式的表示及相加 2.1 2.1 线性表的类型定义线性表的类型定义1.1.线性表的定义线性表的定义 由由 n(nn(n0)0)个数据元素组成的有限序列。其个数据元素组成的有限序列。其中数据元素的个数中数据元素的个数 n n 定义为定

2、义为表的长度表的长度，当，当 n=0n=0 时称为时称为空表空表。一般将非空的线性表（一般将非空的线性表（n0n0）记作：）记作：(a(a1 1,a,a2 2,a,ai i,a,ai+1i+1,a,an n)(1in)(1in)例例1 1：2626个英文字母组成的字母表个英文字母组成的字母表 （A A，B B，C,C,Z,Z）例例2 2：某校从：某校从19781978年到年到19831983年各种型号的计算年各种型号的计算 机拥有量的变化情况。机拥有量的变化情况。（6 6，1717，2828，5050，9292，188188）例例3 3：学生健康情况登记表如下：学生健康情况登记表如下：姓名姓名

3、学号学号性别性别年龄年龄健康情况健康情况王小林王小林790631790631男男1818健康健康陈陈 红红790632790632女女2020一般一般刘建平刘建平790633790633男男2121健康健康张立立张立立790634790634男男1717 神经衰弱神经衰弱 2.2.线性表的逻辑特征线性表的逻辑特征1.1.非空的线性表中，有且仅有一个开始结点非空的线性表中，有且仅有一个开始结点 a a1 1无直接前趋，并且仅有一个直接后继无直接前趋，并且仅有一个直接后继 a a2 2；2.2.有且仅有一个终端结点有且仅有一个终端结点 a an n 无直接后继，并且无直接后继，并且仅有一个直接前趋

4、仅有一个直接前趋 a an-1n-1；3.3.其余的内部结点其余的内部结点 a ai i(2in-1)(2in-1)都有且仅有一都有且仅有一个直接前趋个直接前趋 a ai-1 i-1 和一个直接后继和一个直接后继 a ai+1i+1。3.3.抽象数据类型线性表的定义抽象数据类型线性表的定义ADT List ADT List 数据对象：数据对象：D D a ai i|a|ai iElemSet,i=1,2,ElemSet,i=1,2,n,n0,n,n0 数据关系：数据关系：R R a|a|ai-1i-1,a,ai iD,i=2,D,i=2,n,n 设线性表为设线性表为 (a(a1 1，a a2

5、2，a ai i ，a an n),),称称 i i 为为 a ai i 在线性表中的位置。在线性表中的位置。基本操作：基本操作：ADT List ADT List线性表的基本操作线性表的基本操作1 1）InitList(&L)InitList(&L)操作结果：结构初始化，构造一个空的线性表操作结果：结构初始化，构造一个空的线性表L L2 2）DestroyList(&L)DestroyList(&L)初始条件：线性表初始条件：线性表L L已存在。已存在。操作结果：销毁线性表操作结果：销毁线性表L L。3 3）ListEmpty(L)ListEmpty(L)初始条件：线性表初始条件：线性表L

6、L已存在已存在 操作结果：若操作结果：若L L为空表，返回为空表，返回TRUETRUE，否则，否则FALSEFALSE4 4）ListLength(L)ListLength(L)初始条件：线性表初始条件：线性表L L已存在。已存在。操作结果：返回操作结果：返回L L中元素个数中元素个数5 5）GetElem(L,GetElem(L,i i,&e),&e)初始条件：线性表初始条件：线性表L L已存在，且已存在，且1i1i表长表长 操作结果：用操作结果：用 e e 返回返回L L中第中第i i个元素的值个元素的值6 6）LocateElem(L,e,compare()LocateElem(L,e,

7、compare()初始条件：初始条件：L L已存在，已存在，compare()compare()是元素判定函数是元素判定函数 操作结果：返回操作结果：返回L L中第中第1 1个与个与e e满足关系满足关系compare()compare()的元的元 素的位序；若这样的元素不存在，则返回值为素的位序；若这样的元素不存在，则返回值为0 0。7 7）PriorElem(L,cur_e,&pre_e)PriorElem(L,cur_e,&pre_e)初始条件：线性表初始条件：线性表L L已存在。已存在。操作结果：若操作结果：若cur_ecur_e是是L L的元素，但不是第一个，则的元素，但不是第一个，

8、则用用 pre_epre_e返回它的前驱，否则操作失败，返回它的前驱，否则操作失败，pre_epre_e无定义无定义8 8）NextElem(L,cur_e,&next_e)NextElem(L,cur_e,&next_e)初始条件：线性表初始条件：线性表L L已存在。已存在。操作结果：若操作结果：若cur_ecur_e是是L L的元素，但不是最后一个，则的元素，但不是最后一个，则 用用next_enext_e返回它的后继，否则操作失败，返回它的后继，否则操作失败，next_enext_e无定义无定义9 9）ListTraverse(L,visit()ListTraverse(L,visit(

9、)初始条件：线性表初始条件：线性表L L已存在。已存在。操作结果：依次对操作结果：依次对L L的每个元素调用的每个元素调用visit()visit()函数。函数。一旦一旦visit()visit()失败，则操作失败失败，则操作失败1010）ListInsert(&L,i,e)ListInsert(&L,i,e)初始条件：线性表初始条件：线性表L L已存在，已存在，1i1i表长表长+1+1 操作结果：在操作结果：在L L的第的第i i个元素之前插入新的元个元素之前插入新的元 素素e e，L L的长度增的长度增1 1。1111）ListDelete(&L,i,&e)ListDelete(&L,i,

10、&e)初始条件：初始条件：L L已存在且非空，已存在且非空，1i1i表长表长 操作结果：删除操作结果：删除L L的第的第i i个元素，用个元素，用e e返回其返回其 值，值，L L的长度减的长度减1 1。1212）ClearList(&L)ClearList(&L)初始条件：线性表初始条件：线性表L L已存在。已存在。操作结果：将操作结果：将L L重置为空表。重置为空表。4.4.利用上述定义的操作完成更复杂的操作利用上述定义的操作完成更复杂的操作例例1 1：假设有两个集合假设有两个集合A A和和B B分别用两个线性表分别用两个线性表LALA和和LBLB表示。（即：线性表中的数据元素即为集合中表

11、示。（即：线性表中的数据元素即为集合中的成员），现要求一个新集合的成员），现要求一个新集合 A AABAB问题可演绎为，要求对线性表作如下操作：问题可演绎为，要求对线性表作如下操作：扩大线性表扩大线性表LALA，将存在于线性表，将存在于线性表LBLB中而不存于线中而不存于线性表性表LALA中的数据元素插入到线性表中的数据元素插入到线性表LALA中。中。则思路即为：则思路即为：1)1)从线性表从线性表LBLB中依次取得每个数据元素；中依次取得每个数据元素；2)2)依值在线性表依值在线性表LALA中进行查访；中进行查访；3)3)若不存在，则插入之。若不存在，则插入之。void union(List

12、&La,List Lb)void union(List&La,List Lb)/将所有在线性表将所有在线性表LbLb中但不在中但不在LaLa中的元素插入到中的元素插入到LaLa La_len=ListLength(La);La_len=ListLength(La);Lb_len=ListLength(Lb);Lb_len=ListLength(Lb);for(i=1;i=Lb_len;i+)for(i=1;i=Lb_len;i+)GetElem(Lb,i,e);GetElem(Lb,i,e);/取取LbLb中第中第i i个元素赋给个元素赋给e e if(!LocateElem(La,e,equ

13、al()if(!LocateElem(La,e,equal()ListInsert(La,+La_len,e);ListInsert(La,+La_len,e);/La/La中不存在和中不存在和 e e 相同的元素，则插入之相同的元素，则插入之 /union/union例例2 2：假已知一个非纯集合假已知一个非纯集合B B，(即即B B中包含有相同元中包含有相同元素）试构造一个纯集合素）试构造一个纯集合A A，使，使A A中只包含中只包含B B中所有值中所有值各不相同的数据元素。各不相同的数据元素。（假设（假设B B为有序序列）为有序序列）则思路即为：则思路即为：1)1)创建一个空的线性表创建

14、一个空的线性表LA;LA;2)2)从线性表从线性表LBLB中依次取得每个数据元素；中依次取得每个数据元素；3)3)依值在线性表依值在线性表LALA中进行查访；中进行查访；4)4)若不存在，则插入之。若不存在，则插入之。void purge(List&La,List Lb)void purge(List&La,List Lb)/构造构造LaLa，使其只包含，使其只包含LbLb中所有值不相同的元素中所有值不相同的元素 InitList(LA);InitList(LA);La_len=ListLength(La);La_len=ListLength(La);Lb_len=ListLength(Lb)

15、;Lb_len=ListLength(Lb);for(i=1;i=Lb_len;i+)for(i=1;i=Lb_len;i+)GetElem(Lb,i,e);GetElem(Lb,i,e);/取取LbLb中第中第i i个元素赋给个元素赋给e e if(if(!equal(en,e)!equal(en,e)ListInsert(La,+La_len,e);en=e;ListInsert(La,+La_len,e);en=e;/La/La中不存在和中不存在和e e相同的元素，则插入相同的元素，则插入 /purge/purge例例3 3：已知线性表：已知线性表LALA和和LBLB中的数据元素按值非递

16、减中的数据元素按值非递减有序排列，现要求将有序排列，现要求将LALA和和LBLB归并为一个新的线性归并为一个新的线性表表LCLC，且，且LCLC中的元素仍按值非递减有序排列。中的元素仍按值非递减有序排列。a a=ba ab b abvoid mergelist(list la,list lb,list&lc)void mergelist(list la,list lb,list&lc)initlist(lc);initlist(lc);i=j=1;k=0;i=j=1;k=0;la_len=listlength(la);la_len=listlength(la);lb_len=listlengt

17、h(lb);lb_len=listlength(lb);while(i=la_len)&(j=lb_len)while(i=la_len)&(j=lb_len)getelem(la,i,ai);getelem(lb,j,bj);getelem(la,i,ai);getelem(lb,j,bj);if(ai=bj)listinsert(lc,+k,ai);+i;if(ai=bj)listinsert(lc,+k,ai);+i;else listinsert(lc,+k,bj);+j;else listinsert(lc,+k,bj);+j;while(i=la_len)while(i=la_le

18、n)getelem(la,i+,ai);listinsert(lc,+k,ai);getelem(la,i+,ai);listinsert(lc,+k,ai);while(j=lb_len)while(j=lb_len)getelem(lb,j+,bj);listinsert(lc,+k,bj);getelem(lb,j+,bj);listinsert(lc,+k,bj);线性表的基本运算：线性表的基本运算：1.1.在两个确定的元素之间在两个确定的元素之间插入插入一个新的元一个新的元素；素；删除删除线性表中某个元素；线性表中某个元素；2.2.按某种要求按某种要求查找查找线性表中的一个元素，线性

19、表中的一个元素，需要时，还可对找到的元素进行需要时，还可对找到的元素进行“值值”的的更新更新。5.5.线性表线性表的分类的分类顺序表顺序表 用顺序存储结构存储的线性表用顺序存储结构存储的线性表链链 表表 用链式存储结构存储的线性表用链式存储结构存储的线性表第第2 2章章 线性表线性表2.1 2.1 线性表的类型定义线性表的类型定义2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现 2.3.1 2.3.1 线性链表线性链表 2.3.2 2.3.2 循环链表循环链表 2.3.3 2.3.3 双向链表双向链表 2.4 2.4 一元

20、多项式的表示及相加一元多项式的表示及相加 2.2 2.2 线性表的顺序表示及实现线性表的顺序表示及实现1.1.线性表的顺序表示线性表的顺序表示 线性表的顺序表示指的是用线性表的顺序表示指的是用一组地址连续的一组地址连续的存储单元存储单元依次依次存储线性表的数据元素。用这种方存储线性表的数据元素。用这种方法存储的线性表简称法存储的线性表简称顺序表顺序表(sequential list)(sequential list)。元素元素a an n元素元素a ai i元素元素a a2 2元素元素a a1 1b bb+sb+sb+(i-1)sb+(i-1)s b+(maxlen-1)s b+(maxlen

21、-1)s存储地址存储地址内存状态内存状态Loc(aLoc(ai i)=Loc(a)=Loc(a1 1)+)+（i-1)i-1)s s首首 地地 址址起始地址起始地址基基 地地 址址Loc(a1 1)每个元素所占用每个元素所占用的存储单元个数的存储单元个数2.2.线性表的顺序存储空间线性表的顺序存储空间分配方法分配方法 线性表线性表在在高级语言中通常用一维数组来描高级语言中通常用一维数组来描述数据结构中的顺序存储结构，但是，由于线述数据结构中的顺序存储结构，但是，由于线性表的长度可变，且所需性表的长度可变，且所需要的要的最大存储空间随最大存储空间随问题问题的的不同而不同。不同而不同。因此，因此，

22、可以采用可以采用静态分配静态分配和和动态分配动态分配两种两种不同的方法。不同的方法。1 1）静态分配）静态分配 是在类型定义中为线性表定义好对应的数组是在类型定义中为线性表定义好对应的数组存储空间，前面讨论的即是顺序存储线性表的静存储空间，前面讨论的即是顺序存储线性表的静态分配。在程序在编译阶段就知道该类型变量的态分配。在程序在编译阶段就知道该类型变量的大小，其大小为：大小，其大小为：axsizesizeofaxsizesizeof（ElemTpyeElemTpye）在在程序开始运行前程序开始运行前就会为它分配好存储空间。就会为它分配好存储空间。2 2）动态分配）动态分配 是在定义线性表的存储

23、类型时，不是定义好是在定义线性表的存储类型时，不是定义好一个数组空间，而是只定义一个指针，待一个数组空间，而是只定义一个指针，待程序运程序运行后行后再通过再通过 malloc()malloc()得到一个用于存储线性表得到一个用于存储线性表的空间，并把该空间的首地址赋给这个指针。的空间，并把该空间的首地址赋给这个指针。访问访问动态动态存储分配的线性表中的元素和访问存储分配的线性表中的元素和访问静态静态存储分配时的情况完全相同，可采用存储分配时的情况完全相同，可采用指针方指针方式式或或数组下标方式数组下标方式。-线性表的静态分配顺序存储结构线性表的静态分配顺序存储结构 -#define LIST_

24、INIT_SIZE 100#define LIST_INIT_SIZE 100typedef struct typedef struct ElemType dataLIST_INIT_SIZE;ElemType dataLIST_INIT_SIZE;int len;int len;SqList;SqList;-线性表的动态分配顺序存储结构线性表的动态分配顺序存储结构 -#define LIST_INIT_SIZE 100 /#define LIST_INIT_SIZE 100 /存储空间初始分配量存储空间初始分配量#define LISTINCREMENT 10 /#define LISTIN

25、CREMENT 10 /存储空间分配增量存储空间分配增量typedef struct typedef struct ElemType*elem;/ElemType*elem;/存储空间基址存储空间基址 int len;/int len;/当前长度当前长度 int lsize;/int lsize;/当前分配的存储容量当前分配的存储容量(以以 /sizeof(ElemType)/sizeof(ElemType)为单位为单位)SqList;/SqList;/顺序表顺序表-线性表的初始化在顺序映像中的实现线性表的初始化在顺序映像中的实现 -Status InitList_Sq(SqList&L)St

26、atus InitList_Sq(SqList&L)/构造空线性表构造空线性表L L L.elem=(ElemType*)malloc(L.elem=(ElemType*)malloc(LIST_INIT_SIZE LIST_INIT_SIZE*sizeof(ElemType);sizeof(ElemType);if(!L.elem)if(!L.elem)exit(OVERFLOW);exit(OVERFLOW);/存储分配失败存储分配失败 L.len=0;L.len=0;/长度为长度为0 0 L.lsize=L.lsize=LIST_INIT_SIZELIST_INIT_SIZE;/初始存储

27、容量初始存储容量 return OK;return OK;/InitList_Sq/InitList_Sq存储分配，返回存储分配，返回void型的指针型的指针强制类型转换，转换为强制类型转换，转换为指向指向ElemType类型的类型的指针指针3.3.顺序存储线性表在抽象类型中的操作顺序存储线性表在抽象类型中的操作例例1 1：向线性表中第向线性表中第i i个位置插入一个元素。个位置插入一个元素。分析：分析：线性表的线性表的逻辑结构逻辑结构发生什么变化？发生什么变化？（a a1 1,a,ai-1i-1,a,ai i,a,an n）改变为改变为a a,（a a1 1,a ai-1i-1,e,a,e,

28、ai i,a,an n）a1 a2 ai-1 ai ana1 a2 ai-1 ai ean表的长度增加表的长度增加1 1插入的过程为：插入的过程为：(1)(1)检查检查i i的合法性；的合法性；(2)(2)检查线性表是否为满，若是则动态分配存储；检查线性表是否为满，若是则动态分配存储；(3)(3)从第从第i i个插入位置起，将该位置元素以及其后所个插入位置起，将该位置元素以及其后所有位置上的元素均后移一个位置；有位置上的元素均后移一个位置；(4)(4)把新元素写入到空出的位置上；把新元素写入到空出的位置上；(5)(5)线性表的长度加线性表的长度加1 1。status listinsert(Sq

29、List&L,int i,ElemtType e)status listinsert(SqList&L,int i,ElemtType e)if(iL.len+1)return ERROR;if(iL.len+1)return ERROR;/i/i值不合法值不合法 if(L.len=L.lsize)if(L.len=L.lsize)/当前存储空间已满，增加分配当前存储空间已满，增加分配 newbase=(Elemtype*)realloc(L.elem,(L.lsize+newbase=(Elemtype*)realloc(L.elem,(L.lsize+LISTINCREMENT)*(siz

30、eof(ElemType);LISTINCREMENT)*(sizeof(ElemType);if(!newbase)exit(overflow);if(!newbase)exit(overflow);/存储分配失败存储分配失败 L.elem=newbase;L.elem=newbase;/新基址新基址 lsize+=LISTINCREMENT;lsize+=LISTINCREMENT;/增加存储容量增加存储容量 q=&(L.elemi-1);q=&(L.elemi-1);/q/q为插入位置为插入位置 for(p=&(L.elemL.len-1);p=q;-p)for(p=&(L.elemL.

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

32、,66)ListInsert_Sq(L,5,66)L.len-10pppq87564266q=&(L.elemi-1);q=&(L.elemi-1);for(p=&(L.elemL.len-1);p=q;-p)for(p=&(L.elemL.len-1);p=q;-p)*(p+1)=*p;*(p+1)=*p;*q=e;*q=e;pfor(j=L.len-1;j=i-1;jfor(j=L.len-1;j=i-1;j)L.elemj+1=L.elemj;L.elemj+1=L.elemj;L.elemi-1=eL.elemi-1=e考虑移动元素的平均情况：考虑移动元素的平均情况：假设在第假设在第i

33、 i个元素之前插入的概率为个元素之前插入的概率为 P Pi i，则，则在长度为在长度为n n 的线性表中的线性表中插入一个元素所需移动元插入一个元素所需移动元素次数的期望值素次数的期望值为：为：若假定在线性表中任何一个位置上进行若假定在线性表中任何一个位置上进行插入插入的概率都是相等的，则移动元素的期望值的概率都是相等的，则移动元素的期望值为：为：+-=+=11)1(niiisinpE+-+=+=11)1(11niisinnE2n=a1 a2 ai-1 ai ai+1 an例例2 2：从线性表中删除第：从线性表中删除第i i个位置的元素。个位置的元素。分析：删除元素时，线性表的逻辑结构发生什么

34、分析：删除元素时，线性表的逻辑结构发生什么变化？变化？（a a1 1,a,ai-1i-1,a,ai i,a,ai+1i+1,a,an n）改变为改变为a,a（a a1 1,a ai-1i-1,a,ai+1i+1,a,an n）ai+1ana1 a2 ai-1 表长度减表长度减1 1删除的过程为：删除的过程为：(1)(1)检查检查i i的合法性；的合法性；(2)(2)删除第删除第i i个位置的元素，即使后面第个位置的元素，即使后面第i i至第至第n n个个元素（共元素（共 n ni i个）依次前移一个位置；个）依次前移一个位置；(3)(3)使线性表的长度减使线性表的长度减1 1；返回删除成功。；

35、返回删除成功。status ListDelete(SqList&L,int i,ElemType&e)status ListDelete(SqList&L,int i,ElemType&e)if(iL.len)return ERROR;if(iL.len)return ERROR;/删除位置不合法删除位置不合法 p=&(L.elemi-1);p=&(L.elemi-1);/p/p 为被删除元素的位置为被删除元素的位置 e=*p;e=*p;/被删除元素的值赋给被删除元素的值赋给 e e q=L.elem+L.len q=L.elem+L.len 1;1;/表尾元素的位置表尾元素的位置 for(+

36、p;pq;+p)*(P-1)=*P;for(+p;pq;+p)*(P-1)=*P;/被删除元素之后的元素左移被删除元素之后的元素左移 -L.len;-L.len;/表长减表长减1 1 return OK;return OK;/ListDelete/ListDelete21 18 30 75 42 56 8721 18 30 75L.len-10pppq8756p=&(L.elemi-1);p=&(L.elemi-1);q=L.elem+L.len-1;q=L.elem+L.len-1;for(+p;p=q;+p)*(p-1)=*p;for(+p;p=q;+p)*(p-1)=*p;例：例：Lis

37、tDelete_Sq(L,5,e)ListDelete_Sq(L,5,e)pe=L.elemi-1;e=L.elemi-1;for(j=i;j=L.len-1;j+)for(j=i;j=L.len-1;j+)L.elemj-1=L.elemj;L.elemj-1=L.elemj;考虑移动元素的平均情况：考虑移动元素的平均情况：假设删除第假设删除第i i个元素的概率为个元素的概率为q qi i ,则在长度则在长度为为n n 的线性表中的线性表中删除一个元素删除一个元素所需所需移动元素次移动元素次数的期望值数的期望值为：为：假定在线性表中任何一个位置上进行删除假定在线性表中任何一个位置上进行删除的的概率相等概率相等，则，则移动元素的期望值移动元素的期望值为：为：-=niidlinqE1)(-=nidlinnE1)(121-=n4.4.顺序表的不足顺序表的不足 在顺序表中插入或删除元素时，每进行一在顺序表中插入或删除元素时，每进行一次插入或删除，都要移动近乎一半的元素次插入或删除，都要移动近乎一半的元素 线性表的长度可变，必须按可能达到的最线性表的长度可变，必须按可能达到的最大长度分配空间。大长度分配空间。