数据结构-02线性表.ppt

,数据结构（C语言描述） DATA STRUCTURES,第二章 线性表,2.1 线性表的类型定义 2.1.1 线性表的定义 2.1.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 双向链表 2.4 有序表 2.5 顺序表和链表的综合比较,2.1 线性表的类型定义,线性表(Linear_List)是最简单，也是最基本的一种线性数据结构。它有两种存储表示：顺序表和链表，它主要的操作是插入、删除和查找等。 2.1.1 线性表的定义 1）(3,8,5,7,10)是一个线性表，其中的数据元素是整数,按上述顺序排列，表中共有5个数据元素。 2）(A,B,C,D,X,Y,Z)是一个线性表,其中的数据元素是英文字母,按字母顺序排列，共有26个数据元素。 3）按字母顺序排列的学生姓名表。 4）按字母顺序排列的商品列表。 5）(1分、 2分、 5分、 1角、 2角、 5角),2.1.1 线性表的定义,6）下图的学生学籍档案表，是稍复杂的线性表，表中元素可以由多个数据项组成，在这里每个学生档案是一个线性表，它由学号、姓名、和各项成绩组成。（和绪论中介绍的图书目录表类似）,学生学籍档案表,学号 姓名 入学分 数分 ,0101 赵前进 601 90 ,0102 华罗庚 640 98 ,0103 李龙 580 80 , ,2.1.1 线性表的定义,线性表(Linear_List) 是n (n0)个数据元素的有限序列，表中各个数据元素具有相同的特性，既属于同一数据对象，表中相邻的数据元素之间存在“序偶”关系。通常将线性表记做 (a1, a2, , ai-1, ai, ai+1, , an-1, an,) (2-1) 则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。n是表的长度。 当n=0时，表为空。a1 是第一个数据元素，an 是最后一个数据元素， ai 是第i个数据元素，其中i为数据元素ai 在线性表中的位序。 除了这种优先关系之外，在线性表中不再有其他的结构。,2.1.2 线性表的基本操作,在应用程序中会经常用到线性表，虽然每一个具体应用使用的操作不尽相同，但以下基本操作会经常用到： InitList( &L ) : 构造一个空线性表L DestroyList ( &L ): 在线性表L存在的条件下，摧毁线性表L ClearList ( &L ): 在线性表L存在的条件下，将L重置为空表 ListEmpty ( L ): 若L为空，返回TRUE，否则返回FALSE ListLength( L ): 返回表中元素的个数 GetElem( L, i, &e ): 在1 i ListLength( L )条件下， 用e返回L中第i个元素,more,2.1.2 线性表的基本操作,LocateElem( L, e): 返回L中第一个与e满足相等关系的元素的位序，如不存在，返回0 PriorElem( L, cur_e, &pre_e ): 如果cur_e是L中的元素，并且不是第一个，则用pre_e返回它的前驱。否则失败。 NextElem( L, cur_e, &next_e ): 如果cur_e是L中的元素，并且不是最后一个，则用next_e返回它的后继。否则失败。 ListInsert( &L, i, e ): 在1i ListLength(L) +1条件下，在L中第i个位置之前插入新的数据元素e，L的长度加1。 ListDelete( &L, i, &e ): 在1i ListLength(L)条件下，删除L的第i个数据元素，并用e返回其值，L的长度减1。 ListTraverse( L): 依次输出L中的每个数据元素。,2.1.2 线性表的基本操作,前面各个操作的定义仅对抽象的线性表而言，定义中尚未涉及线性表的存储结构以及实现这些操作所用的编程语言。但利用这些操作可以完成例如研究算法、求解算法及分析算法等重要工作。 在这一层次研究问题可以避开技术细节，面向应用，深入讨论问题。下面我们可以通过例子来看如何设计应用。,例2.1 合并两个线性表：La和Lb是分别表示两个集合A、B，现求一个新的集合A=AB 就这个问题我们可以有两种算法来实现，下面是算法1： Void Union1( List / Union1,2.1.2 线性表的基本操作,Void Union2( List / Union2 前面两个算法使用不同的基本操作来实现A=AB的计算。在实际的应用中可根据情况来选用。,2.1.2 线性表的基本操作,2.1.2 线性表的基本操作,例2.2 已知一非纯集合B，试构造一个纯集A，使得A中只包含B中所有值不相同的成员。 void purge( List / purge,例2.A 已知线性表La和Lb的数据元素按值非递减有序排列，现要求将La和Lb归并成一个新的线性表Lc，且Lc中的数据元素仍按值非递减有序排列。 Void MergeList( List La, List Lb, List ,2.1.2 线性表的基本操作,1,3,3,7,2,3,4,1,2,3,3,3,4,7,2.2.1 顺序表-线性表的顺序存储表示 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。此时线性表也称为顺序表。 假设线性表的每个存储单元需占用L个存储单元，并以所占的第一个单元的存储地址作为数据单元的存储地址，则下列关系成立： LOC(ai+1) = LOC(ai) + L LOC(ai) = LOC(a1) + (i-1)*L 其中LOC(a1) 是线性表的第一个数据元素的存储位置，通常称为线性表的起始位置或基地址。 由前面的公式可知：只要确定存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。,2.2 线性表的顺序表示和实现,由于高级程序设计语言中的数组类型也有随机存取的特性，因此，通常都用数组来描述数据结构中的顺序存储结构。 由于线性表的长度可变，且所需最大存储空间随问题不同而不同，所以在C语言中可用动态分配的一维数组来描述。 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 Typedef struct ElemType * elem; /存储空间基地址 int length; /当前长度 int listsize; /当前分配的存储容量 int incrementsize; /约定的增补空间量 SqList; / listsize和incrementsize以ElemType为单位,2.2.1 顺序表-线性表的顺序存储表示,根据前面的定义，如果SqList L; 则L为顺序表，表中含有L.length个数据元素，依次存储在L.elem0至L.elemL.length-1 中，其中L.elemi-1的值线性表中第i个数据元素。该顺序表最多可容纳L.listsize个数据元素； ElemType为线性表中数据元素所属类型。,2.2.1 顺序表-线性表的顺序存储表示,Typedef struct ElemType * elem; /存储空间基地址 int length; /当前长度 int listsize; /当前分配的存储容量 int incrementsize; /约定的增补空间量 SqList;,a1,a2,ai,an,L.length,L.listsize,根据线性表的上述顺序表表示，我们可以看出，线性表的许多基本操作很容易实现。例如： ListEmpty ( L ): 若L为空，返回TRUE，否则返回FALSE ListLength( L ): 返回表中元素的个数 GetElem( L, i, &e ): 在1 i ListLength( L )条件下， 用e返回L中第i个元素 所以下面我们将详细地讨论其他操作。,2.2.2 顺序表中基本操作的实现,初始化操作： void InitList_Sq (SqList / InitList_Sq 复杂度为O(1) 用(1)表示更为恰当,2.2.2 顺序表中基本操作的实现,查找元素操作： int LocateElem_Sq (SqList L, ElemType e) /返回L中第一个与e满足相等关系的元素的位序，如不存在，返回0 i=1; p=L.elem; while ( i=L.length / LocateElem_Sq 复杂度为O(n),2.2.2 顺序表中基本操作的实现,2.2.2 顺序表中基本操作的实现,下面我们重点讨论一下插入和删除操作。,5,6,9,12,15,20,30,37,40,50,Length=10,1,2,3,4,5,6,7,8,9,10,18,5,6,9,12,15,20,30,37,40,50,18,Length=11,5,6,9,12,15,30,37,40,50,18,Length=10,2.2.2 顺序表中基本操作的实现,void ListInsert_Sq( SqLisst / ListInsert_Sq,假设插入概率相等,平均移动次数为： 1/(n+1)n+1i=1 (n-i+1)=n/2,O(n),void incrememt(SqLisst ,#include #include void ErrorMessage(char * s ) / 出错异常处理 cout s endl; exit(1); ,2.2.2 顺序表中基本操作的实现,void ListDelete_Sq( SqLisst / ListDelete_Sq,假设删除概率相等,平均次数为： (1/n)ni=1 (n-i) = (n-1)/2,O(n),销毁结构操作： void DestroyList_Sq (SqList / DestroyList_Sq 复杂度为O(1),2.2.2 顺序表中基本操作的实现,例2.4 试写一个按字典顺序比较两个西文单词大小的算法。在这里我们用线性表A、B来表示两个单词。 int compare( SqList A, SqList B) / if AB return 1 j=0; while( j B.elemj return (1); else j+; if (A.length=B.length) return (0); else if (A.lengthB.length) return (-1); else return (1); ,2.2.3 顺序表其他算法举例,O(Min(A.length,B.length),例2.5 试设计一个算法，用最少的辅助空间将顺序表的前m个元素和后n个元素进行整体互换。 void exchang1( SqList / end for / exchang1,2.2.3 顺序表其他算法举例,O(mXn),a1,a2,am,b1,b2,bn,b1,a1,a2,am,b1,void exchang2( SqList / exchang2,2.2.3 顺序表其他算法举例,O(m+n),a1,a2,am,b1,b2,bn,void invert( ElemType / end for / exchang1,a1,a2,am,b1,b2,bn,b1,b2,bn,a1,a2,am,例2.2 已知一个非纯集合B（可能有相同的元素），试构造一个纯集合A，使A中只包含B中所有值各不相同的成员。,2.2.3 顺序表其他算法举例,void purge(List /例2.2 purge,void purge_Sq(SqList /例2.6 purge_Sq,O(n2),我们在前面的讨论中发现线性表顺序存储结构（顺序表）的特点是逻辑上相邻的两个元素在物理位置上也相邻，因此可以随机存取表中任意元素，它的存储可以用一个简单直观的公式来表示。这是它的优点。 但这个特点也导致这种存储结构的弱点，在插入和删除操作时，需要移动大量的元素。 在这里我们给出线性表的另一种表示方法-链式存储结构，由于它不需要逻辑上相邻的元素在物理上也相邻，因此没有顺序存储结构所具有的弱点，但同时也失去了顺序表可随机存取的优点。,2.3 线性表的链式表示和实现,2.3.1 单链表和指针,链表（Link List）链表的内容通常是存储在内存中分散的位置。为了表示每个元素ai和它的直接后继ai+1之间的的逻辑关系，对于数据元素ai来说，除了要存储它本身的信息之外，还要存储指示它的直接后继的存储位置的信息。这两部分信息和起来对应着线性表中的一个数据元素，称为结点。 结点中存储数据元素本身的域称为数据域，存储直接后继元素的存储位置的域称为指针域,2.3.1 单链表和指针,链表由许多节点(Node)链接而成，每个节点包含了数据部分和指向下一节点的指针（Pointer)。在插入和删除数据时，只需改便指针的指向即可。链表以NULL表示列表的结尾。,H,2.3.1 单链表和指针,通过前面的例子，我们看到单链表可由头指针唯一确定，在C语言中可以用结构指针来描述。 typedef struct LNode ElemType data; struct LNode *next; LNode,* LinkList; 假设L是LinkList型的变量，则L为单链表的头指针，它指向表中第一个节点。 若L为空(L=NULL)，则所表示的线性表为空表，其长度n为0。有时我们在单链表的第一个节点之前附设一个节点，称为头节点。头节点的指针指向第一个节点，此时如果链表为空，则头节点的指针域为空。,a1,a2,L,L,2.3.1 单链表和指针,下面我们讨论有关“指针”的几种基本操作 假设LNode *p,*q; LinkList H; 如果p非空，则p指向某个节点，p-data 表示该节点的数据域，p-next 表示该节点的指针域；如果非空，则指向其后继节点。 指针只能作同类型的指针赋值和比较。并且，指针类型的“值”除了由同类型的指针变量赋值得到外，都必须用C语言中的动态分配得到。 例如p= new LNode; 表示在运行时刻系统动态生成一个LNode类型的节点，并且p指向该节点。当指针p不在使用时，可用delete p; 释放该节点。,2.3.1 单链表和指针,指针指向节点： p=q 指针指向后继： p=q-next 指针移动： p=p-next 链指针改接： p-next=q 链指针改接后继： p-next=q-next,p,q,p,q,p,p,p,q,p,q,2.3.2 单链表的基本操作,1. 求线性表的长度 在顺序表中，线性表的长度是它的一个属性，因此非常容易得到。在链表中，整个表用一个“头指针”表示，如果求长度需要“遍历”链表。 int ListLength_L( LinkList L) / L为链表的头指针。 p=L; k=0; while( p ) k+; p=p-next; return k; / ListLength_L,O(n),2.3.2 单链表的基本操作,2. 查找元素操作 在链表L中查找和给定值e相等的数据元素的过程和顺序表相似。 LNode * LocateElem_L( LinkList L, ElemType e) / L为链表的头指针, e为指定数据，查找与之相等的元素位置。 p=L; while( p / ListLength_L,O(n),2.3.2 单链表的基本操作,3. 插入节点操作 在链表中不要求两个互为前驱和后继的数据元素连续存放，这样就不需要移动数据元素，只需要在链表中添加一个新的节点，并修改相应的指针链接。按插入的位置可考虑两种情况 “后插”：假设在链表中指针p所指节点之后插入一个指针s所指节点， s-next=p-next; p-next=s; 此时，头尾节点处理无差别。,p,s,2.3.2 单链表的基本操作,“前插”：假设在链表中指针p所指节点之前插入一个指针s所指节点， q-next=s; s-next=p; 前插操作需要找到前驱节点，这需要从链表的头指针起进行查找。需要注意的是，如果p所指节点是链表的第一个节点，则“前插”需要修改链表的头指针。,q,s,p,2.3.2 单链表的基本操作,void ListInsert_L( LinkList / end if / ListInsert_L,O(n),如果后插则为O(1) 但注意这里已假设知道节点p的指针,2.3.2 单链表的基本操作,4. 删除节点操作 和插入类似，在链表中删除一个节点时，也不需要移动数据元素，仅需要修改相应的指针链接。 注意在删除时，需要修改它的前驱节点指针域，这点和前插操作类似。 q-next=p-next; 删除节点p 同样，需考虑头节点的处理。,p,q,2.3.2 单链表的基本操作,void ListDelete_L( LinkList / ListInsert_L,O(n),2.3.3 单链表的其他操作举例,例2.7 逆序创建链表 链表是一种动态存储管理的结构，它和顺序表不同，链表中每个节点占用的存储空间不需预先分派划定，而是在运行时刻由系统根据需求即时生成的。因此，建立链表的过程是一个动态生成的过程。即从空表开始，依次建立节点，并逐个插入到链表。 创建链表的方式和方法有很多种；所谓“逆序”创建链表指的是和逻辑顺序相“逆”的次序输入元素。在很多情况下，它很方便。,c,b,a,2.3.3 单链表的其他操作举例,void CreateList_L( LinkList / end for / CreateList_L,O(n),2.3.3 单链表的其他操作举例,例2.8 逆序单链表 在实际的应用中，有时我们需要将整个链表从尾至头反转过来，让我们看一下什么是反转,L,NULL,L,NULL,但是我们应该注意到：在程序中，由于链表的搜索顺序是从头到尾的次序，所以动作流程和上图有所不同。那么，应如何设计程序哪？,2.3.3 单链表的其他操作举例,逆置的过程可以看成顺序删除原来节点，并“逆序”插入到新的节点。 void InvertLinkedList( LinkList /将s节点插入到逆置表头 / end while / InvertLinkedList,O(n),1,2,3,p,s,L,1,2,3,L,p,1,2,3,p,s,L,例2.9 合并两个线性表：La和Lb是分别表示两个集合A、B，现求一个新的集合A=AB Void Union_L( LinkList /s插入到表尾 / while(Lb) / Union_L,2.3.3 单链表的其他操作举例,循环链表(circular linked list)是线性表的另一种形式的链式表示。它的特点是表中最后一个结点的指针域指向第一个结点，整个链表成为一个由链指针相链接的环。据此，从表中任一节点出发均可找到表中其它结点。 对于循环链表，通常还在表中第一个结点之前附加一个“头结点”，并另头指针指向最后一个结点，以便头尾兼顾。,2.3.4 循环链表,L,循环链表的操作和线性链表基本一致，差别仅在于算法中的循环条件不是P或P-next是否为空，而是它们是否指向头指针。 循环链表会使某些操作简化。例如，将两个链表相接成一个表,2.3.4 循环链表,La,Lb,2.3.5 双向链表,双向链表(Double Linked List) 前面我们所讨论的的链式存储结构的节点中只有一个指向直接后继的指针域，这样，从某个节点出发只能顺指针往后寻查其它节点。如果想寻查节点的直接前驱，则需要从表头指针出发。 这样我们可以看到在单链表中，求后继(NextElem)的执行时间为O(1),而求前驱(PriorElem)的执行时间为O(n)。为了解决单链表的这个问题，我们引入双向链表。 在双向链表(Double Linked List)的节点中有两个指针域，其中一个指向直接后继，另一个指向直接前驱。,2.3.5 双向链表,双向链表结构定义如下： Typedef struct DuLNode ElemType data; struct DuLNode *prior; struct DuLNode *next; DuLNode,* DuLinkList; 如果d是双向链表的内部节点，如下公式成立 d-prior-next= d; d = d-next-prior;,假设d为指向 ai 指针,d,ai,ai-1,d,ai+1,d,d-prior,d-prior,d-prior指向结点ai-1,那么指针d-prior所指向的结点ai-1的next,next,next,next,next,指向结点ai,即: d-prior-next=d,d-next,d-next,d-next指向结点ai+1,那么指针d-next所指向的结点ai+1的prior,prior,prior,prior,指向结点ai,即: d-next-prior=d,2.3.5 双向链表,2.3.5 双向链表,在双向链表中，有些操作如ListLength、GetElem、和LocateElem等仅涉及一个方向的指针，则他们的算法和线性链表的操作相同。 但在插入和删除操作时有很大的不同，因为在双向链表中需要修改两个方向的指针。,2.3.5 双向链表,Status ListInsert_DuL(DuLinkList ,2.3.5 双向链表,Status ListDelete_DuL(DuLinkList ,2.3.5 双向链表,在前面的讨论，我们使用的是常规的做法，定义为一个指向链表中第一个节点或头节点的头指针。 这样定义虽然可以完成链表的全部操作，但有些简单的操作并不方便。例如：求链表长度，在链表尾插入一个元素，复杂度都为O(n)，而在顺序表中都是O(1)。如何改进哪？ typedef struct LinkList head, tail; int length; AdvancedLinkList;,需要维护,2.4 有序表,在定义线性表时，我们没有刻意规定线性表元素值之间的依赖关系。若在某些应用中对元素值之间的依赖关系有所约定，例如规定有序性等，则将简化算法，有助于问题的求解。 若线性表中的数据元素之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，即aiai-1或aiai-1（i=2,3,n），则称该线性表为有序表(