《数据结构》课件1第2章 线性表

第2章线性表线性表的逻辑结构线性表的顺序表示和实现线性表的链式表示和实现顺序表和链表的比较线性表的应用2.1线性表的逻辑结构2线性表是由类型相同的数据元素组成的有限序列。线性表的数据元素可以是数字、字符或更复杂的信息。英语字母表：(’a’,’b’,’c’,’d’,……,’x’,’y’,’z’)一个人的一年的月收入：(5000,5200,4890,4890,……,5300)学生成绩表：2.1线性表的逻辑结构3

线性表的定义二元组表示

逻辑关系图2.1线性表的逻辑结构4

线性表的抽象数据类型定义GetElem(i,&e)初始条件：线性表已存在，1≤i≤length。操作结果：用e返回第i个元素的值。SetElem(i,e)初始条件：线性表已存在，1≤i≤length。操作结果：将线性表的第i个位置的元素赋值为e。Search(e)初始条件：线性表已存在。操作结果：在线性表中查找值为e的元素，若查找成功，返回其所在的位置，否则返回0。Insert(i,e)初始条件：线性表已存在，1≤i≤ength+1。操作结果：在线性表的第i个元素前插入元素e，线性表长度加1。Delete(i,&e)初始条件：线性表已存在，1≤i≤length。操作结果：删除线性表的第i个元素，并用e返回其值，线性表长度减1。}2.2线性表的顺序表示和实现1.线性表的顺序存储结构——顺序表5

2.2线性表的顺序表示和实现2.顺序表的实现6template<typenameT>classSqList{private: intmaxsize; //顺序表可能达到的最大长度

intlength; //顺序表的长度

T*elem; //存储空间的基地址public: SqList(intsize=DEFAULT_SIZE); //构造函数，DEFAULT_SIZE为符号常量

SqList(Ta[],intn); //构造函数 SqList(SqList<T>&sl); //复制构造函数

~SqList(); //析构函数

intLength(); //求顺序表长度

boolEmpty(); //判断表是否为空

voidClear(); //清空顺序表

voidPrintList(); //输出表中的各个元素

boolGetElem(inti,T&e); //获取指定位置的元素值

boolSetElem(inti,Te); //设置指定位置的元素值

intSearch(Te); //查找元素

boolInsert(inti,Te); //插入元素

boolDelete(inti,T&e); //删除元素};类模板定义2.2线性表的顺序表示和实现2.顺序表的实现7基本操作//求顺序表的长度template<typenameT>intSqList<T>::Length(){ returnlength;}//判断顺序表是否为空template<typenameT>boolSqList<T>::Empty(){ if(length==0) returntrue; else returnfalse;}//清空顺序表template<typenameT>voidSqList<T>::Clear(){ length=0;}//读取元素的值template<typenameT>boolSqList<T>::GetElem(inti,T&e){ if(i<1||i>length) returnfalse; e=elem[i-1]; returntrue;}//设置元素的值template<typenameT>boolSqList<T>::SetElem(inti,Te){ if(i<1||i>length) returnfalse; elem[i-1]=e; returntrue;}//查找操作template<typenameT>intSqList<T>::Search(Te){ inti; for(i=0;i<length;i++) if(e==elem[i]) returni+1; return0;}2.2线性表的顺序表示和实现2.顺序表的实现8插入操作template<typenameT>boolSqList<T>::Insert(inti,Te){ if(length==maxsize)

returnfalse; if(i<1||i>length+1) returnfalse; for(intj=length;j>=i;j--) elem[j]=elem[j-1]; elem[i-1]=e; length++; returntrue;}算法分析

假设在线性表的任意位置上插入元素的概率相等，即：则：

插入算法的时间复杂度为：O(n)

2.2线性表的顺序表示和实现2.顺序表的实现9删除操作template<classT>boolSqList<T>::Delete(inti,T&e){ if(i<1||i>length) returnfalse; e=elem[i-1]; for(intj=i;j<length;j++) elem[j-1]=elem[j]; length--; returntrue;}

删除算法的时间复杂度为：O(n)算法分析2.3线性表的链式表示和实现线性表的链式存储结构称为链表。链表是用一组地址任意的存储单元存放线性表中的数据元素，这些存储单元可以连续也可以不连续，甚至可以零散分布在内存中的任意位置。链表中，每个数据元素用一个结点来存储，结点不仅包含元素本身的信息（称为数据域），而且包含表示元素之间逻辑关系的信息（在C++语言中用指针来实现，称为指针域）。由于线性表中的每个元素最多只有一个前驱元素和一个后继元素，因此采用链式存储时，一种最简单、最常用的方法是在每个结点中除包含数据域之外只设置一个指针域，用于指向其后继结点，这样的链表称为单链表；另一种方法是在每个结点中除包含数据域之外设置两个指针域，分别用于指向其前驱结点和后继结点，这样的链表称为双链表。1.线性表的链式存储结构——链表102.3线性表的链式表示和实现单链表是一种最简单的线性表的链式存储结构，用它来存储线性表时，为了能正确表示元素之间的逻辑关系，每个结点在存储数据元素的同时，还必须存储其后继元素所在的地址信息。2.单链表的定义和表示11结点示意图：p->data：该结点的数据元素p->next：指向该结点的后继datanextp单链表结构示意图：a1a2an

∧…head头结点：没有存储任何数据增加头结点：算法实现更简单，效率更高头指针指向单链表的头结点空链表示意图：∧head结点定义template<classT>structNode{ Tdata; //数据域

Node<T>*next; //指针域};2.3线性表的链式表示和实现3.单链表的实现1212基本操作//求单链表的长度template<typenameT>intLinkList<T>::Length(){ intlen=0; Node<T>*p=head->next; while(p!=NULL) { len++; p=p->next; } returnlen;}//判断表是否为空template<typenameT>boolLinkList<T>::Empty(){ returnhead->next==NULL;}//读取元素的值template<typenameT>boolLinkList<T>::GetElem(inti,T&e){ if(i<1||i>Length()) returnfalse; Node<T>*p; p=GetPtr(i);

e=p->data;

returntrue;}//清空单链表template<typenameT>voidLinkList<T>::Clear(){ Node<T>*p=head->next; while(p!=NULL) { head->next=p->next;

deletep;

p=head->next;

}}//设置元素的值template<typenameT>boolLinkList<T>::SetElem(inti,Te){ if(i<1||i>Length()) returnfalse; Node<T>*p; p=GetPtr(i); p->data=e; returntrue;}//查找template<typenameT>intLinkList<T>::Search(Te){ Node<T>*p=head->next; inti=1; while(p!=NULL&&p->data!=e) { p=p->next; i++; } if(p==NULL) return0; else returni;}2.3线性表的链式表示和实现3.单链表的实现1313插入操作template<typenameT>boolLinkList<T>::Insert(inti,Te){ if(i<1||i>Length()+1) returnfalse; Node<T>*q,*p; p=GetPtr(i-1); q=newNode<T>;

q->data=e; q->next=p->next; p->next=q; returntrue;}2.3线性表的链式表示和实现3.单链表的实现1414删除操作template<typenameT>boolLinkList<T>::Delete(inti,T&e){ if(i<1||i>Length()) returnfalse; Node<T>*p,*q; p=GetPtr(i-1); q=p->next; e=q->data; p->next=q->next; deleteq; returntrue;}2.3线性表的链式表示和实现4.双链表1515双向链表（双链表）的结点中有两个指针，分别指向前驱和后继。从双链表的任一结点开始，都可以方便地访问它的前驱结点和后继结点。双链表结点结构：双向链表通常采用带头结点的循环链表形式，称为循环双链表p->back：指向该结点的前驱p->data：

该结点的数据元素p->next：

指向该结点的后继Back

data

nextp循环双链表结构：template<typenameT>structDbNode{ Tdata; DbNode<T>*prior; DbNode<T>*next;};结点定义：2.3线性表的链式表示和实现4.双链表1616插入操作template<typenameT>boolDbLinkList<T>::Insert(inti,T&e){ if(i<1||i>Length()+1) returnfalse; DbNode<T>*p,*q; p=GetPtr(i-1); //p指向第i-1个结点

q=newDbNode<T>; //q指向新建结点

q->data=e; //为新结点的数据域赋值

q->prior=p; //新结点的前驱指向p q->next=p->next; //新结点的后继指向p的后继

if(p->next!=NULL) //若p存在后继结点，修改其前驱指针

p->next->prior=q; p->next=q; //修改p的后继指针

returntrue;}2.3线性表的链式表示和实现4.双链表1717删除操作template<typenameT>boolDbLinkList<T>::Delete(inti,T&e){ if(i<1||i>Length()) returnfalse; DbNode<T>*p,*q; p=GetPtr(i-1); //p指向第i-1个结点

q=p->next; //q指向第i个结点

p->next=q->next; //修改p的后继

if(q->next!=NULL) //若q存在后继结点，修改其前驱指针

q->next->prior=p; e=q->data; //用e存储要删除的元素值

deleteq; //释放被删除结点所占的空间

returntrue;}2.3线性表的链式表示和实现5.循环链表1818循环单链表：将终端结点的next域由指向头结点，结点结构与单链表的结点结构相同。示意图：空循环链表的条件：head->next==head循环双链表：将终端结点的next域指向头结点，将头结点的prior域指向终端结点，结点结构与双链表的结点结构相同。示意图：循环双链表中可以通过head->prior快速找到终端结点2.3线性表的链式表示和实现5.循环链表1919循环链表的基本操作实现算法与对应非循环链表的算法基本相同，主要差别是对于空表或到达终端结点的判定条件不同。在单链表中，判断空表的条件是head->next==NULL，判断指针p指向终端结点的条件是p->next==NULL。在循环链表中，判断空表的条件是head->next==head，判断指针p指向终端结点的条件是p->next==head。2.4顺序表和链表的比较201.空间性能的比较存储空间的分配存储密度的大小2.时间性能的比较由于顺序表需要分配一定长度的连续的存储空间，因此，当线性表的长