数据结构与算法第2节线性表.ppt

第2章 数据结构与算法,Section 2 Linear List（线性表）,一、基本概念二、顺序表三、链表,学习内容和目标,1、学习和掌握线性表的定义（逻辑结构）及其特点；2、学习和理解线性表的顺序存储结构（顺序表）的C+类定义和类模板定义方法；掌握顺序表的基本操作的实现原理和方法；3、学习和理解线性表的链式存储结构（链表）的C+类定义和类模板定义方法；掌握单链表、双向链表和循环链表的结构特点以及基本操作的实现原理和方法。,Subsection 1Basic Concept,Definition of List A list of elements(数据元素)of type T is a finite sequence(有限序列)of elements of T together with the following operations(操作):,1.Construct(构造)the list,leaving it empty.2.Determine(确定)whether the list is empty or not.3.Determine whether the list is full or not.4.Find the size of the list.5.Clear the list to make it empty.,6.Insert(插入)an entry(数据元素)at a specified position of the list.7.Remove(删除)an entry from a specified position in the list.8.Retrieve(检索)the entry from a specified position in the list.9.Replace(替换)the entry at a specified position in the list.10.Traverse(遍历)the list,performing(执行)a given operation on each entry.遍历:逐项访问数据元素(每个元素只访问一次),线性表(Linear List),线性表的定义和特点 定义 n（0）个数据元素的有限序列，记作（a1,a2,an）或（a0,a1,an-1）ai 是表中数据元素，n 是表长度。数据类型的任意性和一致性直接前驱元素和直接后继元素,线性表的特点,除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。相邻数据元素之间存在序偶关系。“序偶”包含两层含义：顺序、配对,a1,a2,a3,a4,a5,a6,抽象数据类型线性表的定义如下：,ADT List,数据对象：,D ai|ai ElemSet,i=1,2,.,n,n0 称 n 为线性表的表长;称 n=0 时的线性表为空表。,数据关系：,R1|ai-1,aiD,i=2,.,n,设线性表为(a1，a2,.，ai，.，an),称 i 为 ai 在线性表中的位序。,基本操作：,结构初始化操作,结构销毁操作,引用型操作,加工型操作,ADT List,初始化操作InitList(&L)操作结果：构造一个空线性表L,结构销毁操作DestroyList(&L)初始条件：线性表 L 已存在。操作结果：销毁线性表 L。,引用型操作:Empty(L)Length(L)Prior(L,x,&pre)Next(L,x,&next)Get(L,i)Locate(L,x),加工型操作：Clear(&L)PutElem(&L,i,x)Insert(&L,i,x)Delete(&L,i,&x),线性表的基本操作,Empty(L)（判断线性表是否为空）初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则FALSE。,Length(L)（求线性表的长度）初始条件：线性表L已存在。操作结果：返回L中元素个数。,引用型操作,Prior(L,x,&pre)（求数据元素的前驱）初始条件：线性表L已存在。操作结果：若x是L的元素，但不是第一个，则用pre 返回它的前驱，否则操作失败，pre无定义。,Next(L,x,&next)（求数据元素的后继）初始条件：线性表L已存在。操作结果：若x是L的元素，但不是最后一个，则用next返回它的后继，否则操作失败，next无定义。,Get(L,i)（获取线性表中某个数据元素）初始条件：线性表L已存在，且1iLength(L)。操作结果：返回L中第 i 个元素的值。,Locate(L,x)（确定元素在表中位置）初始条件：线性表L已存在，x为给定值 操作结果：返回L中第1个与x相等的元素的位序。若这样的元素不存在，则返回值为0。,Clear(&L)（线性表置空）初始条件：线性表L已存在。操作结果：将L重置为空表。,PutElem(&L,i,x)（改变数据元素的值）初始条件：线性表L已存在，且 1iLength(L)。操作结果：L中第i个元素赋值为x的值。,加工型操作,Insert(&L,i,x)（插入数据元素）初始条件：线性表L已存在，且1iLength(L)+1 操作结果：在L的第i个元素之前插入新的元素x，L的长度增1。,Delete(&L,i)（删除数据元素）初始条件：线性表L已存在且非空，1iLength(L)。操作结果：删除L的第i个元素，L的长度减1。,线性表的存储结构,线性表常用的两种存储结构顺序存储结构（顺序表）链式存储结构（链表）,注意：任意一种存储结构，都不仅要存储数据本身，还需要存储（保留）数据与数据之间的逻辑关系，并且在数据操作过程中不破坏这种逻辑关系。,逻辑上定义的线性表，在计算机中实现时需要考虑其物理存储结构以及相关操作的实现。,Subsection 2Sequential List（顺序表）线性表的顺序存储结构,顺序表(Sequential List),顺序表的定义和特点线性表的顺序存储结构：将线性表中的元素相继存放在一个连续的存储空间中。特点：元素存储位置体现逻辑关系,如何用程序设计语言实现顺序表？,一维数组,一维数组实现顺序表,数组下标：0 1 2 3 4 5 6 7 8 9,25 34 57 16 48 09,需要预先定义数组大小（即线性表的最大长度）；,需要跟踪线性表的长度，以便掌握线性表的相关信息以及进行相应的算法操作。,或通过记录尾元素的下标来跟踪线性表长度,顺序表(SeqList)的定义（C语言实现）,#define MaxSize 表中最大元素个数Type SeqListMaxSize;/定义数组int last;/表中最后一个元素的下标,#define 为宏定义;如:define MaxSize 10数据类型Type可以是原子类型，也可以是已实现的结构类型，但在定义顺序表时必须已经显式定义该数据类型。,数组下标有效取值范围?线性表中元素有效下标范围？顺序表长度与Last的关系？空表和满表的判断？,0 MaxSize1,表长度=last+1,0last,顺序表(SeqList)类的定义(C+类实现),class SeqList protected:/SeqList类的数据成员 Type*data;/定义数组 int MaxSize;/顺序表允许长度 int last;/顺序表最后一个元素下标public:/SeqList类的函数成员 SeqList(int MaxSize);/构造函数 SeqList()delete data;/析构函数 int Length()const return last+1;,int Locate(Type x)const;/定位 int Insert(int i,Type x);/插入 int Delete(int i);/删除 int Next(Type x,Type,（续上页）,顺序表(SeqList)类的定义(C+类模板实现),template class SeqList protected:/SeqList类的数据成员 Type*data;/顺序表存储数组(指针方式定义)int MaxSize;/最大允许长度(元素个数)int last;/最后一个元素的下标public:/SeqList类的函数成员 SeqList(int ListSize);/构造函数 SeqList()delete data;/析构函数 int Length()const return last+1;,int Locate(Type x)const;/定位 int Insert(int i,Type x);/插入 int Delete(int i);/删除 int Next(Type x,Type,（续上页）,类模板和模板类,类模板是对结构相同但数据类型不同的类的抽象描述；利用类模板创建的实例被称为模板类，是具体的类。利用已定义的类模板可以创建实例，如：SeqList A;上述语句将创建一个线性表实例A（模板类），它具有类模板SeqList所有的特性，同时其数据成员“data数组”的数据类型为整型。使用类模板可以减少重复定义，提高重用性。,顺序表部分公共操作的实现SeqList类模板的若干函数成员的实现,构造函数：线性表的初始化查找函数：根据元素值或序号查找元素插入函数：在指定位置插入一个新元素删除函数：删除指定数值（或位置）的元素,注意：在数据操作过程中不能破坏线性表的逻辑关系。,template SeqList:SeqList(int ListSize)/创建一个最大长度为ListSize的空线性表 if(ListSize 0)MaxSize=ListSize;last=-1;/申请分配内存空间 data=new TypeMaxSize;/空间申请失败处理 if(data=NULL)MaxSize=0;,构造函数（初始化）,查找过程示例（查找值为16的元素）,25 34 57 16 48 09,0 1 2 3 4 5,data,查找 16,i,25 34 57 16 48 09,i,25 34 57 16 48 09,i,25 34 57 16 48 09,i,查找成功，返回3,查找函数（定位函数）的实现,25 34 57 16 48,0 1 2 3 4,data,查找 50,i,25 34 57 16 48,i,25 34 57 16 48,i,25 34 57 16 48,i,25 34 57 16 48,i,查找失败，返回1,查找过程示例（查找值为50的元素）,template int SeqList:Locate(Type,查找函数（定位函数）,注意：只需搜索有效元素区域，而不是整个数组。,表项（数据元素）的插入操作,25 34 57 16 48 09 63,0 1 2 3 4 5 6,data,50,插入 x,25 34 57 50 16 48 09 63,0 1 2 3 4 5 6 7,data,50,i3,在进行数据插入操作时，需要注意：插入位置 i 的有效取值范围：此处为0last+1 线性表为满表(last=Maxsize-1)时，不允许插入操作,last,Last,在表中第 i 个元素前插入一个新元素x,template int SeqList:Insert(int i,Type x)/判断删除位置i是否合理以及表是否已满 if(i last+1|last=MaxSize-1)return 0;/插入操作不成功 else last+;for(int j=last;j i;j-)dataj=dataj-1;/元素后移 datai=x;return 1;/操作成功,插入函数,表项的删除操作,25 34 57 50 16 48 09 63,0 1 2 3 4 5 6 7,data,16,删除位置i,25 34 57 50 48 09 63 63,0 1 2 3 4 5 6 7,data,Last,Last,在进行删除操作时，需要注意：删除位置 i 的有效取值范围：0Last 线性表为空（Last1）时，不允许删除操作,删除表中的第 i 个元素,template int SeqList:Delete(int i)/判断插入位置i是否合理,表是否为空表 if(i last|last0)return 0;/数据元素前移 for(int j=i+1;j=last;j+)dataj-1=dataj;/元素前移(覆盖)last-;return 1;/成功删除,删除函数,顺序表的特点,顺序表是随机存取结构，数据元素寻址时间确定；元素最大个数需预先设定，若估计不当会造成空间浪费或空间溢出；插入或删除操作需要耗费较多时间移动数据元素，其时间复杂度为O(n)，n为线性表长度。,顺序表的应用：集合的“并”运算,已知两集合A、B，求两集合的并集，结果存放于Avoid Union(SeqList,已知两集合A、B，求两集合的交集，结果存放于A void Intersection(SeqList/未找到，在A中删除它,顺序表的应用：集合的“交”运算,Subsection 3Linked List（链表）线性表的链式存储结构,链表特点：用一组地址任意的存储单元存放线性表中的数据元素，用指针反映数据元素之间的线性关系，以“结点的序列”来表示线性表。即：,元素(数据元素值的映象)+指针(指示后继元素存储位置)=结点(表示数据元素),根据结点和链表结构的不同，有单链表、循环链表和双向链表、循环双向链表等实现方式。,单链表(Singly Linked List),结构特点：每个数据元素用结点(Node)表示，每个结点由一个数据域 data 和一个指针域 link 组成。数据元素之间通过指针来保持线性结构：前一结点的指针域指向后一结点（即：指针值为后一结点的起始存储地址）。,单链表(Singly Linked List),以链表中第一个结点（首结点）的存储地址作为链表的地址，称作链表的头指针（常用first或head表示）；有时还用一个指针指向链表的最后一个结点（尾结点），称为尾指针（常用last表示）。链表中最后一个结点的指针域为空(NULL)，示意图中常用表示。,单链表结构示意图,首结点,尾结点,单链表的存储映像,Typedef struct LNode Type data;/数据域 struct LNode*next;/指针域,结点和单链表的 C 语言描述,LNode*head；/单链表的头指针,完整的单链表定义包含两层定义：对结点结构的定义以及对链表的定义。,结点和单链表的C+类定义,多个类表达一个概念(单链表)。链表结点(ListNode)类 链表(List)类定义方式 复合方式 嵌套方式,class List;/链表类定义一(复合方式）class ListNode/链表结点类 friend class List;/定义链表类为其友元类 private:/定义数据成员 int data;/结点数据（整型）ListNode*link;/结点指针;class List/链表类 private:ListNode*first;/头指针 public:/链表公共操作（函数成员）定义;,class List/链表类定义二(嵌套方式)private:class ListNode/嵌套链表结点类定义 public:int data;ListNode*link;ListNode*first;/头指针public:/链表公共操作（函数成员）定义;,单链表部分函数成员的实现,查找函数：根据元素值或序号查找元素插入函数：在指定位置插入一个新元素删除函数：删除指定数值（或位置）的元素,根据单链表的结构特点，要查找第 i 个数据元素，必须先找到第 i1 个数据元素。,单链表的元素查找操作查找第i 个位置上的元素,可以采用一个计数器 j 来记录指针p当前指向的元素的序号。,查找元素a3（i3）,查找第 i 个数据元素的基本操作为：令指针 p 初始指向链表首结点（计数变量j0），然后沿着链表不断移动指针 p指向下一结点（j 同步增加），直到 j i 1或者p指向链表尾部（pNULL）。,单链表元素查找操作要点查找第i 个位置上的元素,i 值不合理的情形：i 太小(i 0)或 i 太大(i n,n为单链表最后一个数据元素的序号），如何判断？,int List:GetElem(int i,Type&e)/在单链表中查找第i个元素，并以 e 返回第 i 个元素值,ListNode*p=first;j=0;/p初始指向首结点，j为计数器,/顺着指针方向向后查找，直到p指向第i-1个元素或p为空while(p!=NULL,if(p=NULL|p-link=NULL|ilink-data;/取得第 i 个元素的数据return 1;,单链表元素查找操作的实现,单链表的插入操作,第一种情况：在首结点前（表头）插入,（插入前）（插入后）,newnodelink=first;first=newnode；,(插入前)(插入后),第二种情况：在链表中间（表中）插入,newnodelink=plink;plink=newnode；,第三种情况：在链表末尾（表尾）插入,(插入前)(插入后),newnodelink=plink;plink=last=newnode；,因此，在单链表中第 i 个结点之前进行插入的基本操作为:找到线性表中第i1个结点，然后修改相关指针（先修改被插入结点的指针，再修改第i1个结点的指针）。,在链表中插入结点只需要修改指针：被插入结点的指针以及原链表中相关结点的指针。注意，若要在第 i 个结点之前插入元素，修改的是第 i1 个结点的指针。,单链表插入操作要点总结：,i 的有效 取值范围,链表若为非空表:0in+1(n为表长)链表若为空表:i 0,int List:Insert(const int x,const int i)/在链表第i 个结点前插入新元素x ListNode*p=first;int j=0;while(p!=NULL,单链表插入操作实现,/创建新结点,其数据为x,指针为NULL ListNode*newnode=new ListNode(x,NULL);if(first=NULL|i=0)/插在表前 newnodelink=first;first=newnode;else/插在表中或末尾 newnodelink=plink;plink=newnode;return 1;,（续上页）,第一种情况:删除表中首结点first=firstlink,单链表的删除操作,第 59 页,第二种情况:删除表中或表尾结点plink=qlink,单链表的删除操作（续）,注意第i1个结点存在但第 i 个结点不存在的特殊情形（即i 1=n 时）；,在单链表中删除第 i 个结点的基本操作为：找到线性表中第i1个结点和第i个结点，然后修改第i1个结点的指针。,在链表中删除结点时只需要修改指针。注意，若要删除第 i 个结点，修改的是第 i1 个结点的指针。,单链表删除操作要点总结：,i 值有效取值范围：0 i n(n为尾元素序号),int List:Remove(int i)/在链表中删除第 i 个结点 ListNode*p=first,*q;int k=0;while(p!=NULL,单链表删除操作实现,if(i=0)/删除首结点 q=first;/q保存被删结点地址 p=first=firstlink;/修改first else/删除表中或表尾结点 q=plink;plink=qlink;/重新链接/记录数据并删除q k=qdata;delete q;return k;,（续上页）,带表头结点的单链表,为了操作方便，通常在链表首结点之前增加一个“表头结点”（或称头结点）；并以指向表头结点的指针作为链表的头指针 first。,(b)空表,(a)非空表,表头结点的特点及作用,表头结点与其它结点在结构上完全相同。表头结点位于表的最前端，数据域通常不带数据，仅标志表头；表头结点指针域指向链表的首元素（首结点）。设置表头结点的目的是简化链表操作，例如在进行结点插入和删除操作时无需额外判断是否在表头位置进行，可将不同情形下的处理统一起来。,带表头结点单链表的插入操作（表头位置）,newnodelink=plink;if(plink=NULL)last=newnode;plink=newnode;,q=plink;plink=qlink;delete q;if(plink=NULL)last=p;,带表头结点单链表的删除操作（表头位置）,单链表的类模板实现,模板类将类的数据成员和成员函数设计得更完整、更灵活。类模板更易于重用。在单链表的类模板定义中，考虑了表头结点、last指针。,template class List;链表结点类的定义：template class ListNode friend class List;Type data;ListNode*link;public:ListNode();ListNode(const Type,用类模板定义的单链表类,/返回当前结点的指针 ListNode*NextNode()return link;/在当前结点后插入结点p void InsertAfter(ListNode*p);/创建数据为item，指针为next的新结点 ListNode*GetNode(const Type,（续上页）,template class List ListNode*first,*last;public:/定义成员函数 List()/构造函数 List();/析构函数 void MakeEmpty();/链表置空 int Length()const;/求链表长度 ListNode*Find(Type value);ListNode*Find(int i);/查找结点 int Insert(Type value,int i);/插入结点 Type*Remove(int i);/删除结点 Type*Get(int i);/获取结点值;,链表类的定义：,构造函数析构函数置空函数求取链表长度函数查找函数取值函数结点插入函数结点删除函数,链表类的部分公共操作（函数）的实现,/析构函数template List:List()/链表置空，再删去表头结点 MakeEmpty();delete first;/首指针和尾指针置空值 first=last=NULL;,/构造函数template List:List()last=first=new ListNode;,/链表置空函数template void List:MakeEmpty()/删去链表中除表头结点外的所有其他结点 ListNode*q;while(firstlink!=NULL)/将表头结点后第一个结点从链中删除 q=firstlink;firstlink=qlink;delete q;/释放被删除结点 last=first;/修改尾指针,/取链表长度函数template int List:Length()const/求单链表的长度 ListNode*p=firstlink;/指针p初始指向首结点 int count=0;while(p!=NULL)/逐个结点计数 p=plink;count+;return count;,/元素查找（定位）函数（根据值查找）template ListNode*List:Find(Type value)/在链表中从头搜索数据值为value的结点 ListNode*p=firstlink;/指针p初始指向首结点 while(p!=NULL/p 在搜索成功时返回找到的结点地址/p 在搜索不成功时返回空值,/元素搜索（定位）函数（根据序号查找）template ListNode*List:Find(int i)/在链表中从头搜索第i个结点，表头结点编号为0，首结点编号为1，if(i*p=first;int j=0;while(p!=NULL,/结点插入函数template int List:Insert(Type value,int i)/令p指向第i1个结点 ListNode*p=Find(i-1);if(p=NULL)return 0;/第i个结点不存在 ListNode*newnode=new ListNode(value);/申请结点 newnode link=plink；/修改指针 if(plink=NULL)last=newnode;plink=newnode;return 1;,/结点删除函数template Type*List:Remove(int i)/从链表中删去第 i 个结点/令p指向第i1个结点 ListNode*p=Find(i-1),*q;if(p=NULL|plink=NULL)return NULL;/第i个结点不存在 q=plink;/令q指向待删除结点 plink=qlink;/修改指针 Type value=qdata;/保存被删数据 if(q=last)last=p;delete q;return,/取值函数template Type*List:Get(int i)/获取第 i 个结点的数据 ListNode*p=Find(i);/p 指向链表第 i 个结点 if(p=NULL|p=first)return NULL;else return,链表的特点,数据元素（结点）由数据域和指针域共同构成；链表属于顺序存取结构，数据元素的搜索需按指针方向逐个结点顺序进行，寻址时间取决于被搜寻结点在表中的位置；在主存允许的情况下，链表可以按需扩充，不存在空间浪费或空间溢出问题；插入或删除操作只需修改相关结点的指针，操作简单。,循环链表(Circular List),循环链表由单链表衍生而来（链表的结点结构相同，链表结构不同）：循环链表最后一个结点的link指针不为空指针(NULL)，而是指向了表的前端（表头结点或首结点）。为简化操作，通常在循环链表中加入表头结点。,关于循环链表的说明,循环链表结构示意图,带表头结点的循环链表(非空表与空表),不带表头结点的循环链表,循环链表特点：只要知道表中某一结点的地址，就可以找到所有其它结点。,template class CircList;/循环链表结点的类模板定义template class CircListNode friend class CircList;private:Type data;CircListNode*link;public:CircListNode(Type d=0,CircListNode*next=NULL)data=d;link=next;/构造函数,循环链表类的定义,/循环链表的类模板定义template class CircList private:/数据成员 CircListNode*first,*current,*last;public:/成员函数 CircList(Type value);/构造函数 CircList();/析构函数 int Length()const;Boolean IsEmpty()return firstlink=first;,Type GetData()const;Boolean First();Boolean Next();Boolean Prior();Boolean Find(const Type,（续上页）,双向链表(Doubly Linked List),双向链表(Doubly Linked List),双向链表是指在前驱和后继方向都有指针指向的线性链表。双向链表中每个结点的结构：前驱方向 后继方向双向链表有时也采用带表头结点的循环链表形式。,双向链表和双向循环链表,双向链表中结点的指针指向关系p=plLinkrLink=prLinklLink,非空表 空表,带表头结点的双向循环链表,template class DblList;/双向循环链表结点的类模板定义template class DblNode friend class DblList;private:Type data;/数据 DblNode*lLink,*rLink;/指针 DblNode(Type value,DblNode*left,DblNode*right)data=value;lLink=left;rLink=right;DblNode(Type value=NULL)data=value;lLink=NULL;rLink=NULL;,双向循环链表的类模板定义,/双向循环链表的类模板定义template class DblList private:DblNode*first,*current;public:DblLIst();DblList();int Length()const;int IsEmpty()return firstrlink=first;int Find(const Type,搜索成功,搜索不成功,双向循环链表的搜索算法,关键：沿某方向搜索时应注意在何种条件下结束搜索,template int DblList:Find(const Type,双向循环链表的搜索算法实现,(1)prLink=current;/修改被插入结点的右指针(2)plLink=currentlLink;/修改被插入结点的左指针(3)currentlLink rLink=p;/修改前驱结点的右指针(4)currentlLink=p;/修改后继结点的左指针(5)current=p;/修改current指针,双向循环链表的插入操作（非空表）,第 96 页,(1)prLink=first;/修改被插入结点的右指针(2)plLink=first;/修改被插入结点的左指针(3)firstlLink=p;/修改前驱结点的右指针(4)firtlLink=p;/修改后继结点的左指针(5)current=p;/修改current指针,双向循环链表的插入操作（空表）,template void DblList:Insert(const Type,双向循环链表插入操作实现,currentrLinklLink=currentlLink;currentlLinkrLink=currentrLink;,双向循环链表的删除操作,注：删除操作通常令current指针指向被删结点的下一结点，但需要根据具体情况进行可能的附加处理。,template void DblList:Remove()if(current!=NULL)DblNode*temp=current;current=currentrLink;/修改current指针 currentlLink=templLink;templLinkrLink=current;delete temp;/current指向表头结点：被删除的是原尾结点 if(current=first)/链表当前为空表时，修改current为NULL if(IsEmpty()current=NULL;/非空表，修改current指向首结点 else current=currentrLink;,双向循环链表删除操作实现,第 100 页,循环链表和双向链表总结,除了具有单链表的基本特性外，循环链表可由任意一个结点出发访问其它结点；双向链表可以快速访问任意结点的直接前驱结点；,