华师本科生数据结构课件 第2章 线性表.ppt

《华师本科生数据结构课件 第2章 线性表.ppt》由会员分享，可在线阅读，更多相关《华师本科生数据结构课件 第2章 线性表.ppt（89页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第二章 线性表,线性表是最简单、也是最基本的一种线性数据结构。其存储表示法主要有两种：顺序存储结构和链式存储结构。这一部分内容和方法掌握了，有助于理解和掌握后续章节的内容，如栈队列串是特殊的线性表，数组和广义表是线性表的扩展；有助于理解和掌握树和图等复杂的数据结构 存储结构和图等复杂结构的操作算法，因为树和图的存储结构大多或是这两种存储结构的扩充，或是它们的组合，因此这一章的内容非常重要，同学们要很好地学习理解和掌握。,学习的意义：,2.1 线性表的类型定义 2.4 有序表 2.1.1 线性表的定义 2.5 顺序表和链表的综合比较 2.1.2 线性表的基本操作 2.2 线性表的顺序表示和实现

2、2.2.1 顺序表线性表的顺序存储表示 2.2.2 顺序表中基本操作的实现 2.2.3 顺序表其他算法举例 2.3 线性表的链式表示和实现 2.3.1 单链表和指针 2.3.2 单链表的基本操作 2.3.3 单链表的其他基本操作 2.3.4 循环链表 2.3.5 双向链表,主要内容：,线性表是n 个类型相同数据元素的有限序列，表中相邻的数据元素之间存在“序偶”关系。通常记作（a1, a2, a3, , an ）。,姓名 电话号码 蔡颖 63214444 陈红 63217777 刘建平 63216666 王小林 63218888 张力 63215555 .,2. 1 线性表的类型定义,例1、数学

3、中的数列（11，13，15，17，19，21）例2、英文字母表（A, B, C, D, E Z ）。例3、某单位的电话号码簿。,2.1.1 线性表的定义,2.1.1 线性表的定义,特性：设 A=（a1, a2, . , ai -1, ai , ai+1, , an ）是一线性表 线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是同一 类型的； 在表中 ai-1 领先于ai ，ai 领先于ai+1 ，称ai-1 是ai 的直接前驱，ai+1 是ai 的直 接后继； 在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有 一个直接前驱，有且仅有一个直接后继，具有这种结构特征的数据

4、结构 称为线性结构。线性表是一种线性数据结构； 线性表中元素的个数n 称为线性表的长度，n=0 时称为空表； ai是线性表的第i 个元素，称i 为数据元素ai 的序号，每一个元素在线性表 中的位置，仅取决于它的序号；,2.1.1 线性表的定义,1、 二元组表示 L = ，其中：D = a1，a2，a3，, .， an S = R R = , , ,线性表的其他表示方式:,2.1.2 线性表的基本操作,1. 初始化线性表L InitList( GetElem(L,i,e) PriorElem(L,x, InitList (,for (k = 1; k = Lb_len, found; k+) G

5、etElem (Lb, k, e); i = LocateElem (Lc, e); if (i = 0) found = FALSE; else ListDelete ( ,算法中构造的线性表Lc是一辅助结构，它的引入是为了在程序执行过程中不破坏原始数据La，因此算法的最后应销毁Lc！,如果不使用辅助结构Lc，那算法又如何设计呢？,2.1.2 线性表的基本操作,【例2-4 】判别两个集合A和B是否相等。,【方法二 】_不使用辅助结构Lc （1）若线性表La和线性表Lb的长度不等，则返回两集合不等； （2）对Lb中的每个数据元素，在La中进行查询； （3）若La中不存在与该数据元素相同的数据元

6、素，则返回两集合不等； （4）重复（2）和（3）步，直到Lb中的数据元素都遍历完为止； （5）返回两集合相等。,2.1.2 线性表的基本操作,【例2-4 】判别两个集合A和B是否相等。,【具体算法 】_方法二 bool isequal (List La, List Lb) if ( ListLength(La) != ListLength(Lb) ) return (FALSE); Lb_len = ListLength (Lb); for (k = 1; k= Lb_len; k+) GetElem (Lb, k, e); i = LocateElem (La, e); if (i = 0)

7、 return (FALSE); return (TRUE); ,该算法的正确性是因为集合中不存在两个相同的元素！,为了存储线性表，至少要保存两类信息：1）线性表中的数据元素；2）线性表中数据元素的顺序关系；,通常线性表有两种存储表示方法：顺序存储表示和链式存储表示。,线性表的顺序存储结构，就是用一组连续的内存单元依次存放线性表的数据元素。,线性表（a1,a2, a3, . an ） 的顺序存储结构,用顺序存储结构存储的线性表称为顺序表,2.2 线性表的顺序表示和实现,2.2.1 顺序表线性表的顺序存储表示,2.2.1 顺序表线性表的顺序存储表示,说明： 在顺序存储结构下，线性表元素之间的逻辑

8、关系，通过元素的存储顺序反映（表示）出来； 假设线性表中每个数据元素占用 t 个存储单元，那么，在顺序存储结构中，线性表的第i个元素的存储位置与第1个元素的存储位置的关系是： Loc(ai ) = Loc( a1 )+ ( i 1) t,2.2.1 顺序表线性表的顺序存储表示,可用C语言中的一维数组来表示,但数组不是线性表,因为线性表的长度可变。数组存放的是线性表,数组的类型由线性表中的数据元素的性质决定.如: #define MAX 100 int vMAX;,2.2.1 顺序表线性表的顺序存储表示,顺序表的类型定义#define LIST_INIT_SIZE 100 / 线性表存储空间的初

9、始分配量#define LISTINCREMENT 10 / 线性表存储空间的分配增量typedef struct ElemType * elem; /线性表存储空间基址(一维数组) int length; /当前线性表长度 int listsize; /当前分配的线性表存储空间大小 int incrementsize; /约定增补空间量(以ElemType为单位) SqList;,SqList ：类型名， SqList类型的变量是结构变量，它的四个域分别是： *elem：存放线性表元素的一维数组基址；其存储空间在初始化操作（建空表）时动态分配； length：存放线性表的表长； listsi

10、ze：用于存放当前分配（存放线性表元素）的存储空间的大小。 incrementsize：约定增补空间量（当线性表空间不够时）,2.2.1 顺序表线性表的顺序存储表示,存放线性表元素 的一维数组,设 A = （a1,a2 , a3 , . an ）是一线性表，L是SqList 类型的结构变量，用于存放线性表A，则L在内存中的状态如图所示：,顺序表通过 元素的存储顺序 反映线性表元素间的逻辑关系,L.elem L.lenght L.Listsize L.incrementsize,n 99,10,功能：构造一个空的顺序表。 方法：首先要按需为其动态分配一个存储区域，然后设其当前长度为。,2.2.2

11、 顺序表中基本操作的实现,、初始化操作,算法: void InitList_Sq (SqList /需要扩容时每次可增加的元素个数 ,等价于：L.elem = (ElemType *) malloc (LIST_INIT_SIZE * sizeof(ElemType),功能：在顺序表L中查找其值与给定值e相等的数据元素的位序，如果未找到，则返回0。 方法：从第一个元素起，依次和e相比较，直到找到一个其值与e相等的数据元素，则返回它在线性表中的“位序”；或者查遍整个顺序表都没有找到其值和e相等的元素后返回0。,2.2.2 顺序表中基本操作的实现,2、查找元素操作,算法: （书本上的写法） int

12、 LocateElem_Sq (SqList L, ElemType e) i = 1; /i初始值为第一个元素的位序 p = L.elem; /p的初值为第一个元素的存储位置 while (i = L.length /该线性表中不存在满足判定的数据元素 ,算法: （另一种写法） int LocateElem_Sq (SqList L, ElemType e) for (i = 0; i L.length; i+) if (L.elemi = e) return (i+1); return (0); ,注意：位序是从1到L.length!,功能：在顺序表L 中的第 i ( 1iL.length

13、+1)个数据元素之前插入一个新元素x。 插入前线性表为： (a1, a2, a3, ai-1 ,ai, an ) 插入后，线性表长度为L.length+1, 线性表为： (a1, a2, a3, ai-1 , x, ai, an ),2.2.2 顺序表中基本操作的实现,、插入元素操作,2.2.2 顺序表中基本操作的实现,插入前,插入后,_插入操作示意图,、插入元素操作,一般情况下，在顺序表中第i个元素之前插入一个新的元素时，首先需将L.elemL.length-1至L.elemi-1依次往后移动一个位置。显然，此时顺序表的长度应该小于数组的最大容量；否则，在移动元素之前，必须先为顺序表“扩大数

14、组容量”。,2.2.2 顺序表中基本操作的实现,、插入元素操作,算法: void ListInsert_Sq (SqList /表长增1 ,void increment (SqList ,可用realloc (L.elem, (L.listsize+L.incrementsize)*sizeof(ElemType);来代替,void ErrorMessage (char *s) cout s endl; /printf (“%sn”, s); exit (1); ,一般情况下，当插入位置i=L.length+1时，for循环的执行次数为0，即不需要移动元素；反之，若i=1，则需将顺序表中全部（

15、n个）元素依次向后移动。然而，当顺序表中数据元素已占满空间时，不论插入位置在何处，为了扩大当前的数组容量，都必须移动全部数据元素，因此，从最坏的情况考虑，顺序表插入算法的时间复杂度为O(n)，其中n为线性表的长度。,删除算法的主要步骤: 1）若i 不合法或表L空，算法结束，并返回 0；否则转2） 2）将第i个元素之后的元素（不包括第i个元素）依次向前移动一个位置; 3）表长 - 1,2.2.2 顺序表中基本操作的实现,功能：在顺序表L 中删除第 i ( 1iL.length)个数据元素。 删除前线性表为： (a1, a2, a3, ai-1 ,ai, ai+1, an ) 删除后，线性表长度为

16、L.length-1, 线性表为： (a1, a2, a3, ai-1 , ai+1, an ),4、删除元素操作,一般情况下，从顺序表中删除第i个元素时，需将L.elemi至L.elemL.length-1的元素依次往前移动一个位置。,2.2.2 顺序表中基本操作的实现,、删除元素操作,算法: void ListDelete_Sq (SqList /表长减1 ,等价于： e = L.elemi-1; memcpy (L.elem+i-1, L.elem+i, (L.length-i)*sizeof(ElemType); 或 memmove (L.elem+i-1, L.elem+i, (L.

17、length-i)*sizeof(ElemType),和插入的情况相类似，当删除的位置i=L.length时，算法中for循环的执行次数为0，即不需要移动元素；反之，若i=1，则需将顺序表中从第2个元素起至最后一个元素（共n个元素）依次向前移动一个位置。因此，顺序表删除元素算法的时间复杂度也为O(n),其中n为线性表的长度。,2.2.2 顺序表中基本操作的实现,5、销毁结构操作,功能：和结构创建相对应，当程序中的数据结构不再需要时，应该及时进行“销毁”，并释放它所占的全部空间，以便使存储空间得到充分的利用。,算法: void DestoryList_Sq (SqList ,2.2.2 顺序表中

18、基本操作的实现,6、其他操作,对于顺序表来说，其他的操作很容易实现。请同学们在课后自己独立完成！,2.2.2 顺序表中基本操作的实现,插入位置 移动元素个数 1 n 2 n-1 i n-i+1 n 1 n+1 0,（1）插入算法时间复杂度分析 算法时间复杂度取决于移动元素的个数，移动元素的个数不仅与表长有关，而且与插入位置有关。,7、插入和删除操作的时间分析,（1）插入算法时间复杂度分析,由此可见:在顺序表中插入一个元素 ，平均要移动表的一半元素。表长为n的顺序表，插入算法的时间复杂度为 O（n）,假设在线性表的任何位置插入元素的概率相同，即 pi= 1/(n+1),pi:在第i个元素之前插入

19、元素的概率，在长度为n的顺序表中插入一个元素，所需移动元素个数数学期望值为：,（2）删除算法时间复杂度分析,由此可见:在顺序表中删除一个元素 ，平均要移动表的一半元素。表长为n的顺序表，删除算法的时间复杂度为 O（n）,假设在线性表的任何位置删除元素的概率相同，即 qi= 1/n,qi：删除第i个元素的概率，在长度为n的顺序表中删除一个元素，所需移动元素个数数学期望值为：,2.2.3 顺序表其他算法举例,【例2-5 】设A=(a1,a2, ,am)和B=(b1,b2, ,bn)均为顺序表，试比较A、B的大小。,【分析 】这是对两个顺序表进行比较的操作，因此在算法中不应该破坏已知表。从题目的要求

20、看，只有在两个表的长度相等，且每个对应元素都相同时才相等；否则两个顺序表的大小主要取决于两表中除去前面相同的元素后的第一个元素。,【具体步骤 】 （1）设一变量j（初值为1）； （2）当j小于A的长度和B的长度时，若ajbj时，则返回1，否则j+; （3）重复第（2）步，直到j大于A或B的长度； （4）如果A的长度等于B的长度，则返回0；如果A的长度小于B的长度，则返回-1；否则返回1。,2.2.3 顺序表其他算法举例,【例2-5 】设A=(a1,a2, ,am)和B=(b1,b2, ,bn)均为顺序表，试比较A、B的大小。,【具体算法 】 int compare (SqList A, SqL

21、ist B) j = 1; while (j B.elemj) return (1); else j+; if (A.length = B.length) return (0); else if (A.length B.length) return (-1); else return (1); ,等价于： If (j A.length) return (1); else if (j B.length) return (-1); else return (0);,此算法中只有一个while循环，它的执行次数依赖于待比较的顺序表的表长。因此算法的时间复杂度为： O(Min(A.length，B.l

22、ength),2.2.3 顺序表其他算法举例,【例2-6 】设计一个算法，用尽可能少的辅助空间将顺序表中的前m个元素和后n个元素进行整体互换。即将线性表 （a1,a2, ,am,b1,b2, ,bn） 改变成 （b1,b2, ,bn,a1,a2, ,am）,【分析 】此题的难点在于要求用尽可能少的辅助空间。如果没有这个限制，可以另设一个和已知顺序表空间大小相同的顺序表，然后进行元素复制即可。,【具体算法 】_借助于辅助空间 void exchang (SqList ,2.2.3 顺序表其他算法举例,【例2-6 】线性表数据互换。,【方法一 】从表中第m+1个元素起依次插入到元素a1之前，则首先

23、需将该元素bk（k=1,2, ,n）暂存在一个辅助变量中，然后将它之前的m个元素（a1,a2, ,am）依次后移一个位置。,w,w,_将bk插入到（a1,a2,am）之前的过程,【具体算法 】_方法一 void exchang (SqList ,算法的复杂度： 由于对每一个bk都需要移动m个元素，因此算法的时间复杂度为O(m*n)。,2.2.3 顺序表其他算法举例,【例2-6 】线性表数据互换。,【方法二】先将线性表“逆置”成（bn,b2,b1,am,a2,a1），然后分别再对前n个元素（bn,b2,b1）和后m个元素（am,a2,a1）进行“逆置”，便可得到所求结果。,_顺序表中部分元素（a

24、i,ai+1,ai+m）逆置前后的状况,【具体算法 】_方法二 void invert (ElemType ,void exchange2 (SqList ,算法的时间复杂度为： O(t-s+1)。,算法的时间复杂度为： O(m+n)、O(n)、O(m)， 按最坏情况估计为：O(m+n)。,2.2.3 顺序表其他算法举例,【例2-7 】已知一个非纯集合B（即集合B中可能有相同元素），试构造一个纯集合A，使A中只包含B中所有值各不相同的成员。（假设以顺序线性表表示集合）。,【方法 】依次取得顺序表B中的元素，在顺序表A中进行查询，若没有值相同的元素出现，则将它插入到A的表尾。B中的第一个元素必定

25、会插入到A中，因此对它不再进行查询，而是直接“复制”到A表中。,【具体算法 】 void purge_Sq (SqList ,算法的复杂度： O(n2)，其中n为B表的长度。,线性表的顺序表示和实现小结：,顺序表是线性表最简单的一种存储结构,2.3 线性表的链式表示和实现,线性表的链式存储结构是用一组任意的存储单元存储线性表的各个数据元素。为了表示线性表中元素的先后关系，每个元素除了需要存储自身的信息外还需保存直接前趋元素或直接后继元素的存储位置。,2.3.1 单链表和指针,用一组任意的存储单元存储线性表中的数据元素，对每个数据元素除了保存自身信息外，还保存了直接后继元素的存储位置。,用线性链

26、表存储线性表时，数据元素之间的关系是通过保存直接后继元素的存储位置来表示的,结点：数据元素及直接后继的存储位置（地址）组成一个数据元素的存储结构，称为一个结点； 结点的数据域 ：结点中用于保存数据元素的部分; 结点的指针域 ：结点中用于保存数据元素直接后继存储地址的部分;,线性链表有关术语,2.3.1 单链表和指针,存储后继结点 存储地址,存储数据元素,头指针：用于存放线性链表中第一个结点的存储地址;空指针：不指向任何结点，线性链表最后一个结点的指针通常是 指空指针，用NULL表示;,线性链表的每个结点中只有一个指针域 故也称为单链表,线性链表有关术语,2.3.1 单链表和指针,空指针,头指针

27、,怎样在计算机上 实现线性链表？,？,2.3.1 单链表和指针,2.3.1 单链表和指针,结点变量图示,typedef struct LNode ElemType data; struct LNode *next; LNode, *LinkList;,LNode：结构类型名； LNode类型结构变量有两个域： data：用于存放线性表的数据元素， next：用于存放元素直接后继结点的地址；该类型结构变量用于表示线性链表中的一个结点；LNode *p： p为指向结点(结构)的指针变量； LinkList H: 头指针为H的单链表；,data next,LNode类型 结构变量,p是LNode类型

28、的指针变量,单链表的结点类型定义及指向结点的指针类型定义,2.3.1 单链表和指针,方法一： LNode *p; p = new LNode; 方法二： p = (LNode *) malloc ( sizeof (LNode ) );,单链表中结点的创建,2.3.1 单链表和指针,调用free ( p ),调用free ( p ) 图示,delete p 或 free ( p ) 功能：将指针变量p所指示的存储空间，回收到系统内存空间中去,使用方法： . LNode *p; p = (LNode *) malloc (sizeof (LNode); / 一旦p所指示的内存空间不再使用， /调

29、用free( ) 回收之 free(p);,2. 3. 2 单链表的基本操作,如何在线性链表 上实现线性表的基本操作？ 如何插入？删除？查找元素？,？,2. 3. 2 单链表的基本操作,【分析】当以单链表表示线性表时，整个链表由一个“头指针”来表示，线性表的长度即为链表中的结点个数，只能通过“遍历”链表来实现。,1、求线性表的长度,【具体算法 】 int ListLength_L (LinkList L) p = L; k = 0; while (p) k+; p = p-next; return (k); ,算法的时间复杂度： O(n)，其中n为表长。,2. 3. 2 单链表的基本操作,2、

30、查找元素操作,【分析】在单链表L中查找和给定值e相等的数据元素的过程和顺序表类似，从第一个结点起，依次和e相比较，直到找到一个其值和e相等的元素，则返回它在链表中的“位置”；或者查遍整个链表都不存在这样的一个元素后，返回“NULL”。,【具体算法 】 LNode * LocateElem_L (LinkList L, ElemType e) p = L; while (p ,注意：返回值为结点值为e的指针,算法的时间复杂度： O(n)，其中n为表长。,2. 3. 2 单链表的基本操作,3、插入结点操作,【分析】由于在单链表中不要求两个互为“前驱”和“后继”的数据元素紧挨存放，则在链表中插入一个

31、新的数据元素时，不需要移动数据元素，而只需要在链表中添加一个新的结点，并修改相应的指针链接。插入操作分为：后插和前插。,后插（在p所指结点后插 入s所指的结点）,（1） S-next = p-next,（2） p-next = s,2. 3. 2 单链表的基本操作,3、插入结点操作,前插（在p所指结点前插入s所指的结点）,（1） q-next = s,（2） s-next = p,前插时，首先要找到插入结点p的前驱结点的指针q，然后才能进行插入操作。要找到前驱结点，这只要从链表的头指针起进行查询即可。令q的初始值等于头指针，查找结束的条件是q-next = p；若否，则指针q后移。还有一点要注

32、意的是，如果p所指结点是链表中的第一个结点，则“前插”操作尚需修改链表的头指针。,2. 3. 2 单链表的基本操作,3、插入结点操作,【具体算法 】 void * ListInsert_L (LinkList ,算法的时间复杂度： 后插 O(1)，前插O(n)，其中n为表长。,2. 3. 2 单链表的基本操作,4、删除结点操作,【分析】和插入类似，在单链表中删除一个结点时，也不需要移动数据元素，仅需修改相应的指针链接。但由于删除结点时，需要修改的是它的“前驱”结点的指针域，因此和“前插”操作一样，首先应当找到它的前驱结点。,（1） q-next = p-next;,（2） free (p);,

33、2. 3. 2 单链表的基本操作,4、删除结点操作,【具体算法 】 void * ListDelete_L (LinkList /返回被删除结点的数据元素，并释放结点空间 ,算法时间复杂度：O(n)，其中n为表长。,2. 3. 3 单链表的其他基本操作举例,【分析】链表是一种动态管理的结构，它和顺序表不同，链表中每个结点占用的存储空间不需预先分配划定，而是在运行时刻由系统根据需求即时生成的。因此，建立链表的过程是一个动态生成的过程。即从“空表”起，依次建立结点，并逐个插入链表。所谓“逆序”创建链表指的是，依和线性表的逻辑顺序相“逆”的次序输入元素，逆序生成链表可以为处理头指针提供方便。,【例2

34、-8 】逆序创建链表。,线性表(a,b,c,d,e)的逆序创建过程：,2. 3. 3 单链表的其他基本操作举例,【例2-8 】逆序创建链表。,【具体算法 】 void CreateList_L (LinkList ,算法的时间复杂度：O(n)，其中n为表长。,2. 3. 3 单链表的其他基本操作举例,【例2-9 】逆置单链表。,【分析】若对顺序表中的元素进行逆置可以借助“交换”前后相应元素来完成。而对单链表进行逆置，则不能如法炮制。因为对于链表中的第i个结点，都需要顺链查找第n-i+1（设链表长度为n）个结点，将使逆置链表操作的时间复杂度达到O(n2)。因此逆置单链表的操作应借助修改链表中的指

35、针来完成。,【方法】设想逆置后的单链表是一个新建的链表，但表中的结点不是新生成的，而是从原（待逆置的）链表中依次“删除”得到。由此，逆置单链表的操作可类似上例逆序创建链表进行：设逆置链表的初态为一空表，“删除”已知链表中的第一个结点，然后将它“插入”到逆置链表的“表头”，即使它成为逆置链表中“新”的第一个结点，如此循环，直到原链表为空表止。,2. 3. 3 单链表的其他基本操作举例,【例2-9 】逆置单链表。,2. 3. 3 单链表的其他基本操作举例,【例2-9 】逆置单链表。,【具体算法 】 void InvertLinkedList (LinkList /将s结点插入到逆置表的表头 ,算法

36、的时间复杂度：O(n)，其中n为表长。,2. 3. 3 单链表的其他基本操作举例,【方法】设线性表A、B分别用头指针为head_a 、 head_b 的两个带头结点的线性链表存储, 归并后的递减有序表头指针为head, 将两表数据较小的结点依次取出插入到新表,【例2-10 】将两个递增有序线性链表归并成一个递减有序表。,2. 3. 3 单链表的其他基本操作举例,7,3,n,9,5,2,n,7,head_a,head_b,7,9,head,3,8,5,【例2-10 】将两个递增有序线性链表归并成一个递减有序表。,【具体算法 】 LNode * merge_link ( LinkList ,2.

37、3. 3 单链表的其他基本操作举例,【例2-10 】将两个递增有序线性链表归并成一个递减有序表。,while (p != NULL) head_a-next = p-next; p-next = head-next; head-next = p; p = head_a-next; while(q!=NULL) head_b-next = q-next; q-next = head-next; head-next = q; q = head_b-next; free (head_a); free (head_b); return (head); ,2. 3. 3 单链表的其他基本操作举例,【例2

38、-10 】将两个递增有序线性链表归并成一个递减有序表。,线性链表小结,线性链表是线性表的一种链式存储结构,线性链表的特点 1 通过保存直接后继元素的存储位置来表示 数据元素之间的逻辑关系； 2 插入删除操作通过修改结点的指针实现； 3 不能随机存取元素；,1 循环链表的概念 循环链表是线性表的另一种链式存储结构，它的特点是将线性链表的最后一个结点的指针指向链表的第一个结点 2 循环链表图示,2. 3. 4 循环链表,(a)非空表 （b）空表,2. 3. 4 循环链表,说明: 在解决某些实际问题时循环链表可能要比线性链表方便些。如将一个链表链在另一个链表的后面； 循环链表与单链表操作的主要差别是

39、算法中循环结束的条件不是p或p-link是否为NULL，而是它们是否等于首指针； 对循环链表，有时不给出头指针，而是给出尾指针,a,a1,an,给出尾指针的循环链表,2. 3. 4 循环链表,b,a,a1,an,b1,bn,q,q,p,p,两循环链表合并： p = a-next; q = b-next; a-next = q-next; b-next = p; free (q);,1 双向链表的概念,2. 3. 5 双向链表,(a)结点图示,存储数据元素,存储后继结点 的地址,存储前趋结点 的地址,双向链表中，每个结点有两个指针域，一个指向直接后继元素结点，另一个指向直接前趋元素结点。,2.3

40、.5 双向链表,2 双向链表图示,head,typedef struct DuLNode ElemType data; struct DuLNode * prior, *next; DuLNode, *DuLinkList;,在双向链表中删除结点时指针变化情况,在双向链表中插入一个结点时指针的变化情况,p,p,2.3.5 双向链表,3、双向链表的基本操作算法,2.3.5 双向链表,p-prior = q;,1）插入操作算法 (在p 所指结点之前插入q 结点的过程 ),q = (DuLNode *) malloc (sizeof (DuLNode); q-data = x;,q-prior =

41、p-prior;,p-prior-next = q;,q-next = p;,ai-1,ai,p,2.3.5 双向链表,free (p);,2）删除操作算法 (删除p所指向的结点),(p-prior)-next = p-next;,(p-next)-prior = p-prior;,链表结构的讨论,通常链表的定义,定义为一个指向链表中第一个结点或头结点的头指针。 好处：定义简单 不足：虽然可以完成线性表的任何操作，但给某些“简单操作”带来不便。例如，求线性表的长度，在表中最后一个元素后面插入或删除最后一个元素等，对顺序表而言，其时间复杂度为o(1)，而对于链表来说，则为o(n)。,链表结构的讨

42、论,通常链表的改进,链表的定义中加上“头指针”、“尾指针”和“链表长度”三个域。,typedef struct LinkList head, tail; /头指针、尾指针 int length; /链表长度 AdvancedLinkList;,2.4 有序表,若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值递减会递增有序排列，即ai ai-1 或 aiai-1（i=2,3,n），则称该线性表为有序表（ordered list）。,有序表的基本操作和线性表大致相同，但由于有序表中的数据元素有序排列，因此在有序表中插入元素的操作应按“有序关系”进行。和线性表相同，有序表也可以有顺序

43、表和链表两种存储表示方法。,假设某有序表以顺序表的形式存储，其数据元素依值递增排列，先要插入一个新的数据元素x，则应该使插入之后的顺序表仍保持有序表的特性。,【具体算法】 void OrdInsert_Sq (SqList /表长增1 ,算法的时间复杂度：O(n)，其中n为表长。,2.4 有序表,【例2-11 】以顺序有序表表示集合，由一个非纯集合B构造一个纯集合A，使A中只包含B中所有值各不相同的成员。,【分析】由于此例中操作的对象是“有序表”，则表中所有值相同的元素必定连续出现。则在La表中进行“查访”的操作变得简单化了，因为不需要在整个La表中进行“查访”，而只要和La表中最后一个元素比

44、较即可。同时，由于La表的表长不会大于Lb表，则可用同一个顺序表表示。换个角度看问题，当前要实现的算法功能是从一个以顺序表表示的有序表中“删除”所有值相同的多余元素，而使所有值不相同的元素均压缩到顺序表的前部空间中。,【具体算法】 void purge_Osq (SqList ,（1）“删除”的操作是隐含的，仅以j+操作代替。（2）逻辑上的两个线性表La和Lb用同一顺序有序表L表示。（3）i指示La表中“当前所含”的最后一个元素，j指示Lb表中“当前被考察”的元素。（4）若该元素和La中最后一个元素不等，则说明它不是“多余”的，应当“插入”到La表中；否则“不予理睬”，继续考察Lb表中下一个元

45、素。,算法的时间复杂度：O(n)，其中n为表长。,2.4 有序表,【例2-12 】分别以两个（带头结点的）循环有序链表表示集合A和B，完成求这两个集合的并集C（C = AB）的操作。集合C仍以循环有序链表表示，并且不另分配新的空间，而是利用集合A和B的结点来构造集合C的链表。操作完成后，集合A和B的链表不再存在。,【分析】根据并集的定义，C的成员应为A的成员和B的成员之“和”，相同的成员只取一个，则可从C为空集起，逐个将集合A和B中不同的成员插入到集合C中。换句话说，C的链表中的结点或“取自”A的链表，或“取自”B的链表。,2.4 有序表,【例2-12 】分别以两个（带头结点的）循环有序链表表

46、示集合A和B，完成求这两个集合的并集C（C = AB）的操作。集合C仍以循环有序链表表示，并且不另分配新的空间，而是利用集合A和B的结点来构造集合C的链表。操作完成后，集合A和B的链表不再存在。,【方法】利用链表中结点元素“有序”的特性，可作如下处理：（1）设置三个指针：pa、pb和rc，其中pa和pb分别指向集合A和B的链表中某个结点，rc指向C链表中最后一个结点；（2）若pa-data data，说明pa所指结点的元素在B表中不可能出现，应将pa结点链接到C链表中（rc-next = pa）；（3）若pa-data pb-data，则说明pb所指结点的元素在A表中不可能出现，应将pb结点链

47、接到C链表中（rc-next = pb）；（4）若pa-data = pb-data，则应将其中任一结点（pa或pb所指）链接到C链表中，并释放另一结点空间。 指针pa和pb的初始状态：若链表不空，则分别指向各自链表中第一个结点；否则指向头结点，指针rc指向C链表的头结点。 重复操作的条件是：A表和B表都“不空”；反之表明至少有一个表已经处理完毕，即该链表中的结点或已链接到C表中，或已释放。此时，只需将“剩余”结点链接到C链表中即可。,2.4 有序表,求“并集”操作示意图,2.4 有序表,求“并集”操作示意图,2.4 有序表,【具体算法】 void union_OL (LinkList /while,if (pb = Lb-next) rc-next = pa; /链接A的剩余段 else rc-next = pb; pb = Lb-next; /pb指向B的头结点 Lb-next = pa; La =