第2章 线性表线性表的逻辑结构线性表的顺序表示和实现线性表的链式表示和实现顺序表和链表的比较线性表的应用2.1 线性表的逻辑结构2线性表是由性表是由类型相同型相同的数据元素的数据元素组成的成的有限序列有限序列。线性表的数据元素可以是数字、字符或更复杂的信息。英语字母表：(a,b,c,d,x,y,z)一个人的一年的月收入：(5000,5200,4890,4890,5300)学生成绩表：2.1 线性表的逻辑结构3n 线性表的定义n 二元组表示n 逻辑关系图2.1 线性表的逻辑结构4n 线性表的抽象数据类型定义GetElem(i,&e)初始条件：线性表已存在，1ilength。操作结果：用e返回第i个元素的值。SetElem(i,e)初始条件：线性表已存在，1ilength。操作结果：将线性表的第i个位置的元素赋值为e。Search(e)初始条件：线性表已存在。操作结果：在线性表中查找值为e的元素，若查找成功，返回其所在的位置，否则返回0。Insert(i,e)初始条件：线性表已存在，1iength+1。操作结果：在线性表的第i个元素前插入元素e，线性表长度加1。Delete(i,&e)初始条件：线性表已存在，1ilength。操作结果：删除线性表的第i个元素，并用e返回其值，线性表长度减1。2.2 线性表的顺序表示和实现1.线性表的顺序存储结构顺序表52.2 线性表的顺序表示和实现2.顺序表的实现6template class SqListprivate:int maxsize;/顺序表可能达到的最大长度int length;/顺序表的长度T*elem;/存储空间的基地址public:SqList(int size=DEFAULT_SIZE);/构造函数，DEFAULT_SIZE为符号常量SqList(T a,int n);/构造函数SqList(SqList&sl);/复制构造函数SqList();/析构函数int Length();/求顺序表长度bool Empty();/判断表是否为空void Clear();/清空顺序表void PrintList();/输出表中的各个元素bool GetElem(int i,T&e);/获取指定位置的元素值bool SetElem(int i,T e);/设置指定位置的元素值int Search(T e);/查找元素bool Insert(int i,T e);/插入元素bool Delete(int i,T&e);/删除元素;2.2 线性表的顺序表示和实现2.顺序表的实现7/求顺序表的长度template int SqList:Length()return length;/判断顺序表是否为空template bool SqList:Empty()if(length=0)return true;else return false;/清空顺序表template void SqList:Clear()length=0;/读取元素的值template bool SqList:GetElem(int i,T&e)if(ilength)return false;e=elemi-1;return true;/设置元素的值template bool SqList:SetElem(int i,T e)if(ilength)return false;elemi-1=e;return true;/查找操作template int SqList:Search(T e)int i;for(i=0;ilength;i+)if(e=elemi)return i+1;return 0;2.2 线性表的顺序表示和实现2.顺序表的实现8template bool SqList:Insert(int i,T e)if(length=maxsize)return false;if(ilength+1)return false;for(int j=length;j=i;j-)elemj=elemj-1;elemi-1=e;length+;return true;算法分析算法分析假设在线性表的任意位置上插入元素的概率相等，即：则：插入算法的时间复杂度为：O(n)2.2 线性表的顺序表示和实现2.顺序表的实现9template bool SqList:Delete(int i,T&e)if(ilength)return false;e=elemi-1;for(int j=i;jdata：该结点的数据元素p-next：指向该结点的后继 data nextp单链表表结构示意构示意图：a1 a2 an head头结点：没有存储任何数据增加头结点：算法实现更简单，效率更高头指针指向单链表的头结点空空链表示意表示意图：head结点定点定义template struct Node T data;/数据域Node*next;/指针域;2.3 线性表的链式表示和实现3.单链表的实现1212/求单链表的长度template int LinkList:Length()int len=0;Node*p=head-next;while(p!=NULL)len+;p=p-next;return len;/判断表是否为空template bool LinkList:Empty()return head-next=NULL;/读取元素的值template bool LinkList:GetElem(int i,T&e)if(iLength()return false;Node*p;p=GetPtr(i);e=p-data;return true;/清空单链表template void LinkList:Clear()Node *p=head-next;while(p!=NULL)head-next=p-next;delete p;p=head-next;/设置元素的值template bool LinkList:SetElem(int i,T e)if(iLength()return false;Node*p;p=GetPtr(i);p-data=e;return true;/查找template int LinkList:Search(T e)Node*p=head-next;int i=1;while(p!=NULL&p-data!=e)p=p-next;i+;if(p=NULL)return 0;elsereturn i;2.3 线性表的链式表示和实现3.单链表的实现1313template bool LinkList:Insert(int i,T e)if(iLength()+1)return false;Node*q,*p;p=GetPtr(i-1);q=new Node;q-data=e;q-next=p-next;p-next=q;return true;2.3 线性表的链式表示和实现3.单链表的实现1414template bool LinkList:Delete(int i,T&e)if(iLength()return false;Node *p,*q;p=GetPtr(i-1);q=p-next;e=q-data;p-next=q-next;delete q;return true;2.3 线性表的链式表示和实现4.双链表1515双向链表（双链表）的结点中有两个指针，分别指向前驱和后继。从双链表的任一结点开始，都可以方便地访问它的前驱结点和后继结点。双双链表表结点点结构：构：双向链表通常采用带头结点的循环链表形式，称为双向链表通常采用带头结点的循环链表形式，称为循环双链表循环双链表p-back：指向该结点的前驱p-data：该结点的数据元素p-next：指向该结点的后继Back data nextp循循环双双链表表结构：构：template struct DbNodeT data;DbNode*prior;DbNode*next;结点定点定义：2.3 线性表的链式表示和实现4.双链表1616template bool DbLinkList:Insert(int i,T&e)if(iLength()+1)return false;DbNode*p,*q;p=GetPtr(i-1);/p指向第i-1个结点q=new DbNode;/q指向新建结点q-data=e;/为新结点的数据域赋值q-prior=p;/新结点的前驱指向pq-next=p-next;/新结点的后继指向p的后继if(p-next!=NULL)/若p存在后继结点，修改其前驱指针p-next-prior=q;p-next=q;/修改p的后继指针return true;2.3 线性表的链式表示和实现4.双链表1717template bool DbLinkList:Delete(int i,T&e)if(iLength()return false;DbNode *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存储要删除的元素值delete q;/释放被删除结点所占的空间return true;2.3 线性表的链式表示和实现5.循环链表1818循循环单链表：表：将终端结点的next域由指向头结点，结点结构与单链表的结点结构相同。示意示意图：空循环链表的条件：head-next=head循循环双双链表：表：将终端结点的next域指向头结点，将头结点的prior域指向终端结点，结点结构与双链表的结点结构相同。示意示意图：循环双链表中可以通过head-prior快速找到终端结点2.3 线性表的链式表示和实现5.循环链表1919p循环链表的基本操作实现算法与对应非循环链表的算法基本相同，主要差别是对于空表或到达终端结点的判定条件不同。p在单链表中，判断空表的条件是head-next=NULL，判断指针p指向终端结点的条件是p-next=NULL。p在循环链表中，判断空表的条件是head-next=head，判断指针p指向终端结点的条件是p-next=head。2.4 顺序表和链表的比较201.空间性能的比较n存储空间的分配n存储密度的大小2.时间性能的比较由于顺序表需要分配一定长度的连续的存储空间，因此，当线性表的长度变化较大，难以预估规模时，宜采用链式存储结构。顺序表的存储密度为1，链表的存储密度小于1。因此，当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。n存取元素的效率n插入和删除操作的效率顺序表是由数组实现的，它是一种随机存取结构，指定任意一个位置序号i，都可以在O(1)时间内直接存取该位置上的元素，即取值操作的效率高；而链表是一种顺序存取结构，按位置访问链表中第i个元素时，只能从表头开始依次向后遍历链表，直到找到第i个位置上的元素，时间复杂度为O(n)。因此，若线性表需频繁查找却很少进行插入删除操作，或者操作和元素在线性表中的位置紧密相关时，宜采用顺序表作为存储结构。对于链表，在确定插入或删除的位置后，插入或删除操作无需移动数据，只需要修改指针，时间复杂度为O(1)。而对于顺序表，进行插入或删除操作时，平均要移动表中近一半的元素，时间复杂度为O(n)。因此，对于频繁进行插入或删除操作的线性表，宜采用链表作为存储结构。本章小结(1)线性表是由n（n0）个类型相同的数据元素组成的有限序列，相邻数据元素之间存在着序偶关系。对于非空的线性表，除第一个元素以外，每一个元素有且仅有一个前驱，除最后一个元素外，每一个元素有且仅有一个后继。(2)线性表有两种存储结构：顺序存储（顺序表）和链式存储（链表）。对于顺序表，元素存储的相邻位置反映出其逻辑上的线性关系，可借助数组来实现。给出数组的下标，便可以存取相应的元素，因此顺序表是一种随