第二章+线性表.ppt

1、第二章 线性表, 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 线性表的应用,2.1 线性表的类型定义,线性结构的基本特征: 集合中必存在唯一的一个“第一元素”； 集合中必存在唯一的一个“最后元素”； 除最后元素之外，均有唯一的后继； 除第一元素之外，均有唯一的前驱。,从逻辑上：数据之间的关系可以分4类 ：,线性结构, 树型结构, 图状结构, 集合,线性表最简单的一种线性结构 一个线性表是n个数据元素的有限序列 比如 A BZ 英文字母表 比如,线性表中每个数据元素的具体含义，各不相同，数据元素是基本单位，一个数据元素由若干个数据项组成,2.

2、1 线性表的类型定义,线性表记为（a1, ,ai-1,ai, ai+1,an） ai-1 在ai 之前 称 ai-1是 ai 的 前驱 ai 在 ai-1之后 称 ai 是 ai-1的 后继 序列中数据元素的个数 n 定义为线性表的表长 称 i 为ai在线性表中的位序 i=2，,n 线性表的元素个数称为的表长，n0时称为空表,2.1 线性表的类型定义,线性表的抽象数据类型(ADT)定义如下：,ADT List 数据对象：D= ai | ai ElemSet, i=1,2,.,n, n0 数据关系：R1= |ai-1 ,aiD, i=2,.,n /表示为相邻元素的有序对 基本操作：InitLis

3、t( / 存储空间基址 int length; / 当前长度 int listsize; / 当前分配的存储容量 SqList; / 俗称 顺序表 sequence list,2.2 线性表的顺序表示和实现,typedef ? ElemType; /根据实际需要定义,InitList_Sq (SqList / ListLength_Sq,顺序表操作,顺序表是否为空,Status IsEmpty_Sq (SqList L) if (L.length=0) return TRUE; else return FALSE; / IsEmpty_Sq,顺序表操作,顺序表的数据获取,Status GetE

4、lem_Sq(SqLIST L,int pos,EntryType / GetElem_Sq,顺序表操作,Status LocateElem_Sq(SqList L, ElemType e) /* 在顺序线性表L中查找第1个值与e相等的元素的位序。若找到，则返回其在L中的位序，否则返回0。*/ p = L.elem; / 指针p从顺序表基地址开始 while (p-L.elem)L.length / LocateElem_Sq,顺序表的定位(按值查找)V1.0(指针法),顺序表的定位(按值查找)V2.0 (下标法),Status LocateElem_Sq (SqList L , ElemTy

5、pe x ) int i=0； for(; i L.length; i+) if( L.elemi=x ) return i+1; if ( i= L.length) return 0; ,注意：数组元素的两种标识方法：指针法和下标法 例： p = L.elem； *p 和L.elem0指同一个元素 p = p+1; *p 和L.elem1指同一个元素,顺序表操作,Status LocateElem_Sq(SqList L, ElemType e ,Status compare (ElemType, ElemType) int i=0； for(; i L.length; i+) if(com

6、pare (L.elemi , x ) return i+1; if ( i= L.length) return 0; / LocateElem_Sq,顺序表的定位(按值查找)V3.0,Status lag(ElemType a, ElemType b) return ab; /*/ Status LocateElem_Sq(SqList L, ElemType e ,Status compare (ElemType, ElemType) for(; i L.length; i+) if(compare (L.elemi , x ) return i+1; /*/ void main( ) L

7、ocateElem_Sq(L, e, lag); ,形参1,使用形参1,实参1,实参2,形参2,使用形参2,顺序表操作,顺序表的清除,void ClearList_Sq(Sq_LIST /将线性表的长度置为0 / ClearList_Sq,顺序表操作,顺序表的插入,线性表的插入运算是指在表的i(1in+1个位置上，插入一个新结点x，使长度为n的线性表 (a1，a i-1，ai，an) 变成长度为n+1的线性表 (a1，a i-1，x，ai，an),返回,顺序表插入操作V1.0(下标法) 插入元素时，注意线性表的逻辑结构发生什么变化？ (a1, , ai-1, ai, , an) 改变为 (a1

8、, , ai-1, e, ai, , an),pos的合法值为1posL.length+1, if (pos L.length+1) return ERROR; /位置是否合法 if (L.length = L.Listsize) exit(OVERFLOW); /空间是否够用 for ( j=L.length-1; j=pos-1; j-) /插入位置后的元素右移 L.elemj+1=L.elemj; L.elempos-1 = e; / 插入e L.length +; / 表长增1 return OK; / ListInsert_Sq,Status ListInsert_Sq (SqLis

9、t ,if (L.length= L.listsize) newbase=(ElemType*)realloc (L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType); /*分配一个大小为(L.listsize+LISTINCREMENT)*sizeof (ElemType)的存储空间，将原表元素填充到新空间中，把首地址赋值给newbase*/ if (!newbase) exit(OVERFLOW); / 存储分配失败 L.elem = newbase; / 新基址 L.listsize += LISTINCREMENT; / 增加存储容量 ,

10、插入时检测到空间不够时可以用realloc申请增加空间,现在分析算法的复杂度。 这里的问题规模是表的长度，设它的值为n。该算法的时间主要花费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）不仅依赖于表的长度，而且还与插入位置有关。 当i=n+1时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度O（1）； 当i=1时，结点后移语句将循环执行n次，需移动表中所有结点，这是最坏情况，其时间复杂度为O（n）。 由于插入可能在表中任何位置上进行，因此需分析算法的平均复杂度,动画,在长度为n的线性表中第i个位置上插入一个结点，令Eis(n)表示移动结点的期望值（即

11、移动的平均次数），则在第i个位置上插入一个结点的移动次数为n-i+1。故 Eis(n)= pi(n-i+1) 不失一般性，假设在表中任何位置(1in+1)上插入结点的机会是均等的，则 p1=p2=p3=p n+1=1/(n+1) 因此，在等概率插入的情况下， Eis(n)= (n-i+1)/(n+1)=n/2 也就是说，在顺序表上做插入运算，平均要移动表上一半结点。当表长n较大时，算法的效率相当低。虽然Eis(n)中n的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为O(n)。,顺序表操作,顺序表的删除,线性表的删除运算是指将表的第i(1in)结点删除，使长度为n的线性表

12、： (a1，a i-1，ai，a i+1，an) 变成长度为n-1的线性表 (a1，a i-1，a i+1，an),返回,顺序表删除操作V1.0(指针法)：删除元素时，注意线性表的逻辑结构发生什么变化？(a1, ai-1, ai, ai+1, , an) 变为 (a1, , ai-1, ai+1, , an),Status ListDelete_Sq(SqList / ListDelete_Sq,pos的合法值为1posL.length,顺序表删除操作V2.0(下标法),Status ListDelete_Sq(SqList / ListDelete_Sq,该算法的时间分析与插入算法相似，结点

13、的移动次数也是由表长n和位置i决定。 若i=n，则由于循环变量的初值大于终值，前移语句将不执行，无需移动结点； 若i=1，则前移语句将循环执行n-1次，需移动表中除开始结点外的所有结点。这两种情况下算法的时间复杂度分别为O(1)和O(n)。,动画,删除算法的平均性能分析与插入算法相似。在长度为n的线性表中删除一个结点，令Ede(n)表示所需移动结点的平均次数，删除表中第i个结点的移动次数为n-i，故 Ede(n) = pi(n-i) 式中，pi表示删除表中第i个结点的概率。在等 概率的假设下， p1=p2=p3=pn=1/n 由此可得： Ede(n)= (n-i)/n=(n-1)/2 即在顺序

14、表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是O(n)。,顺序表回顾： 特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻； 优点：可以随机存取表中任一元素；存储空间使用紧凑 缺点：1.在插入，删除某一元素时，需要移动大量元素; 2.预先分配空间需按最大空间分配，利用不充分; 3.插入数据元素需要考虑溢出情况,讨论： 在线性表中插入和删除数据元素时可不可以不移动元素？,答：可以！引入线性表的另一种物理映象链表,2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 线性表的应用,2.3 线性表类型链式存储, 2.3.1 链表的基本概念

15、 2.3.2 单链表 2.3.3 单循环链表 2.3.4 双向循环链表 2.3.5 改进的链表及基本操作 2.3.6 链表的应用,2.3.1 链表的基本概念, 什么是链表 链表的存储结构,什么是链表？,链表 链式存储的线性表 用一组地址任意的存储单元存放线性表中的数据元素（这组存储地址可以连续或者非连续） 可以以线性表中第一个数据元素a1的存储地址作为线性表的地址，为线性表的头指针,2.3.1 链表的基本概念,2.3.1 链表的基本概念,什么是链表 链表的存储结构,2.3.1 链表的基本概念,链表的存储结构,链表中的每个数据元素称为结点 每个结点包括： 数据域存放数据元素ai的值； 指针域存放

16、ai的直接后继ai1的地址 链表正是通过每个结点的指针域将表中n个数据元素按其逻辑顺序链接在一起的 链表中数据元素的逻辑顺序与其物理存储顺序不一定相同；,head是头指针，它指向单链表中的第一个结点，这是单链表操作的入口点 由于最后一个结点没有直接后继结点，所以，它的指针域放入一个特殊的值NULL。NULL值在图示中常用（）符号表示,【例】设有一组线性排列的数据元素（zhao, qian, sun, li, zhou, wu, zheng, wang），其链接存储形式下页图所示：,讨论：在该存储方式下，如何找到表中任一元素？,答：在链接存储方式下（链表中），每一个数据元素的存储地址是存放在其直

17、接前驱结点的next域中，只要知道第一个数据元素（结点）zhao的存储地址，就可以“顺藤摸瓜”找到其后续的所有结点。,头指针H,170,通常情况下，我们用箭头来表示指针域中的指针，忽略每一个结点的实际存储位置，而重点突出链表中结点间的逻辑顺序，将链表直观地画成用箭头链接起来的结点序列。,2.3.1 链表的基本概念 2.3.2 单链表 2.3.3 单循环链表 2.3.4 双向循环链表 2.3.5 改进的链表及基本操作 2.3.6 链表的应用,2.3 线性表类型链式存储,2.3.2 单链表,一、 定义 链表的每个结点只有一个指针域单链表,可以有多个数据域,二、单链表结点的C语言描述,typedef

18、 struct LNode ElemType data; / 数据域 LNode *next; / 指针域 LNode, *LinkList;,设p为动态变量，它是通过标准函数生成的，即 p=(LNode*)malloc(sizeof(LNode); 函数malloc分配了一个类型为LNode的结点变量的空间，并将其首地址放入指针变量p中。一旦p所指的结点变量不再需要了，又可通过标准函数 free(p) 释放所指的结点变量空间。,称h为该单链表的头指针。 若已知单链表的头指针，则可以搜索到表中任一结点；也就是说，单链表由头指针唯一确定。 因此，单链表可以用头指针的名字来命名。 上图所示的单链表

19、可称为单链表h。,若有：,在单链表的第一个结点之前设一个头结点 头结点的数据域不存储数据 头结点的指针域存储第一个结点的地址 空链表 L-next = NULL,三、带头结点的单链表,为什么要设头结点？可不可以不设头结点,答：头结点即在链表的首元素结点之前附设的一个结点，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元素结点进行统一处理，免去对链表第一个结点的特殊处理，编程更方便。当然，根据需要有时候也可以不设头节点。,讨论. 在链表中设置头结点有什么好处？ 可不可以不设头结点？,Status InitList_L(LinkList int len; for(p=L, len=

20、0;p-next!=NULL; p=p-next,len+); return(len); /ListLength_L,链表操作,4. 判链表L空否,Status IsEmpty(LINKLIST L) if (L-next=NULL) return TRUE; else return FALSE; /IsEmpty,链表操作,思路：要取第i个数据元素，关键是要先找到该结点的指针p, 然后输出p地址存储的数据元素的值p-data。,难点：单链表中想取得第i个元素，必须从头指针出发寻找（顺藤摸瓜），不能随机存取 。,5.取第i个元素GetElem_L（L,i, for (p=L-next; p;

21、p=p-next) if(compare(e, p-data) return p; ; /寻找满足条件的结点 return NULL; ,链表操作,7.返回链表L中结点e的直接前驱结点,LNode*PriorElem_L(LINKLIST L,ElemType e) LNODE *p; for (p=L; p-next ,链表操作,8. 返回链表L中结点e的直接后继结点,LNode* NextElem_L(LINKLIST L,ElemType e) ElemType *p; for(p=L-next; p ,链表操作,9. 清空链表L,void ClearList(LINKLIST /释放p

22、结点占据的存储空间 ,链表操作,10. 单链表L中节点的插入,Status ListInsert_L ( LinkList / LinstInsert_L,pos=3 e=x,链表操作,11. 单链表 L中删除节点,Status ListDelete_L(LinkList L, int pos, ElemType / ListDelete_L,pos=3,p-next=p-next-next;,L,2,5,7,5,链表操作,时间复杂度分析,链表在插入和删除的时候，无须移动结点，仅需修改指针。但需要寻找插入或删除的位置，算法的时间主要耗费在查找操作上，这需要的平均时间复杂度为O(n) 。总的时间

23、复杂度同顺序表一样。,12. 创建单链表,这里有两种创建方法 1、头插法建表 该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。 2、尾插法建表 头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针q，使其始终指向当前链表的尾结点。,头插法,尾插法,void CreateList_L ( LinkList /插入到表头 /CreateList_L,改为尾插法,void CreateList

24、_L ( LinkList /插入到表尾 /CreateList_L,creat之尾插：,链表操作,思考,1如果不设头指针，请考虑链表的插入、删除和创建算法。 注意： 需要考虑在插入或删除的节点位置是表头的情况，这个时候需要改变头指针。 2比较链表和顺序表的特点和各自的优缺点。,在链表的开始结点之前附加一个结点，并称它为头结点，那么会带来以下两个优点： a、由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致，无需进行特殊处理； b、无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了

25、。,顺序表和链表比较（1）,顺序表和链表比较（2）,2.3.1 链表的基本概念 2.3.2 单链表 2.3.3 单循环链表 2.3.4 双向循环链表 2.3.5 改进的链表及基本操作 2.3.6 链表的应用,2.3 线性表类型链式存储,单循环链表,最后一个结点的指针域的指针又指回第一个结点的链表,怎么样判断链表为空？,if ( head-next = head ),循环链表的操作和单链表基本一致，差别仅在于算法中的循环条件不是p或者p-next是否为空，而是p或者p-next是否等于头指针,Q：单循环链表中如何找到p所指向结点的前驱,带尾指针的单循环链表：,空表：,这时：R-next = R,

26、这时头指针为(一般只设尾指针不再设头指针)： Rnext,(A),步骤: (1) u = Anext (2) Anext = Bnextnext (3) free (Bnext) (4) Bnext = u (5) A = B,连接操作,2.3.1 链表的基本概念 2.3.2 单链表 2.3.3 单循环链表 2.3.4 双向循环链表 2.3.5 改进的链表及基本操作 2.3.6 链表的应用,2.3 线性表类型链式存储,问：链表只能查找结点的直接后继，能不能找到直接前驱？,答：能，只要给每个结点多开一个指针域,typedef struct DuLNode ElemType data; / 数据域

27、 DuLNode *prior; / 指向前驱的指针域 DuLNode *next; / 指向后继的指针域 DuLNode, *DuLinkList;,prior data next,和单循环链表类似，双向链表也可以有循环链表,双向循环链表,p-next-prior = p-prior-next = p,一个空的双向循环链表：,L-next = L,L-prior = L,双向循环链表的操作,status ListInsert_Dul(DuLinkList ,p-next -prior = p-prior;,free (p);,status ListDelete_Dul (DuLinkList struct LNode *next; *Link, *Position; typedef struct /链表类型 Link head, tail; /指向头结点和最后一个结点 int len; /指示链表长度 LinkList;,Status InsAfter ( LinkList / InsAfter,Status MakeNode ( LinkList / MakeNode,Status InsBefore( LinkList / InsBe