数据结构：第2章 线性表

第2章线性表

线性表的逻辑结构

线性表的顺序存储及实现

线性表的链接存储及实现

顺序表和链表的比较

线性表的其他存储方法本章的基本内容是：2.1线性表的逻辑结构数据元素之间的关系是什么？2.1线性表的逻辑结构数据元素之间的关系是什么？现实生活中，许多问题抽象出的数据模型是线性表，如何存储这种线性结构并实现插入、删除、查找等基本操作呢？线性表的定义线性表：简称表，是n（n≥0）个具有相同类型的数据元素的有限序列。线性表的长度：线性表中数据元素的个数。空表：长度等于零的线性表，记为：L=()。非空表记为：L＝（a1,a2,…,ai-1,ai,…,an)2.1线性表的逻辑结构其中，ai（1≤i≤n）称为数据元素；下角标i表示该元素在线性表中的位置或序号。a1a3a4ana22.1线性表的逻辑结构线性表的特性1.有限性：线性表中数据元素的个数是有穷的。2.相同性：线性表中数据元素的类型是同一的。3.顺序性：线性表中相邻的数据元素ai-1和ai之间存在序偶关系(ai-1,ai)，即ai-1是ai的前驱，ai是ai-1的后继；a1无前驱，an无后继，其它每个元素有且仅有一个前驱和一个后继。

线性表的抽象数据类型定义ADTListData

线性表中的数据元素具有相同类型，相邻元素具有前驱和后继关系OperationInitList

前置条件：表不存在输入：无

功能：表的初始化输出：无

后置条件：建一个空表2.1线性表的逻辑结构DestroyList

前置条件：表已存在

输入：无

功能：销毁表

输出：无

后置条件：释放表所占用的存储空间Length

前置条件：表已存在

输入：无

功能：求表的长度

输出：表中数据元素的个数

后置条件：表不变2.1线性表的逻辑结构线性表的抽象数据类型定义Get

前置条件：表已存在

输入：元素的序号i

功能：在表中取序号为i的数据元素

输出：若i合法，返回序号为i的元素值，否则抛出异常

后置条件：表不变Locate

前置条件：表已存在

输入：数据元素x

功能：在线性表中查找值等于x的元素

输出：若查找成功，返回x在表中的序号，否则返回0

后置条件：表不变2.1线性表的逻辑结构线性表的抽象数据类型定义线性表的抽象数据类型定义Insert

前置条件：表已存在

输入：插入i；待插x

功能：在表的第i个位置处插入一个新元素x

输出：若插入不成功，抛出异常

后置条件：若插入成功，表中增加一个新元素Delete

前置条件：表已存在

输入：删除位置i

功能：删除表中的第i个元素

输出：若删除成功，返回被删元素，否则抛出异常

后置条件：若删除成功，表中减少一个元素2.1线性表的逻辑结构线性表的抽象数据类型定义Empty

前置条件：表已存在

输入：无

功能：判断表是否为空

输出：若是空表，返回1，否则返回0

后置条件：表不变ADT进一步说明:（1）线性表的基本操作根据实际应用是而定；（2）复杂的操作可以通过基本操作的组合来实现；（3）对不同的应用，操作的接口可能不同。2.1线性表的逻辑结构2.2线性表的顺序存储结构及实现顺序表——线性表的顺序存储结构例：（34,23,67,43）342367434存储要点用一段地址连续的存储单元依次存储线性表中的数据元素2.2线性表的顺序存储结构及实现顺序表——线性表的顺序存储结构例：（34,23,67,43）34236743存储空间的起始位置4用什么属性来描述顺序表？顺序表的容量（最大长度）顺序表的当前长度2.2线性表的顺序存储结构及实现顺序表——线性表的顺序存储结构例：（34,23,67,43）342367434如何实现顺序表的内存分配？顺序表一维数组0…i-2i-1…n-1Max-1a1…ai-1ai…an空闲长度2.2线性表的顺序存储结构及实现顺序表一般情况下，(a1，a2，…,ai-1，ai,…,an)的顺序存储：数组的长度Max线性表的长度Length数组的长度大于等于当前线性表的长度如何求得任意元素的存储地址？0…i-2i-1…n-1Max-1a1…ai-1ai…an空闲长度2.2线性表的顺序存储结构及实现顺序表一般情况下，(a1，a2，…,ai-1，ai,…,an)的顺序存储：cLoc(ai)Loc(a1)0…i-2i-1…n-1Max-1a1…ai-1ai…an空闲长度Loc(ai)=Loc(a1)+(i-1)×c随机存取：在O(1)时间内存取数据元素2.2线性表的顺序存储结构及实现顺序表一般情况下，(a1，a2，…,ai-1，ai,…,an)的顺序存储：cLoc(ai)Loc(a1)2.2线性表的顺序存储结构及实现存储结构是数据及其逻辑结构在计算机中的表示；存取结构是在一个数据结构上对访问操作的时间性能的一种描述。存储结构和存取结构“顺序表是一种随机存取的存储结构”的含义为：在顺序表这种存储结构上进行的访问，其时间性能为O(1)。顺序表类的声明constintMaxSize=100;template<classDataType>//模板类classSeqList{public:SeqList();//构造函数

SeqList(DataTypea[],intn);~SeqList();//析构函数intLength();DataTypeGet(inti);intLocate(DataTypex);voidInsert(inti,DataTypex);DataTypeDelete(inti);private:DataTypedata[MaxSize];intlength;};2.2线性表的顺序存储结构及实现顺序表的实现——无参构造函数操作接口：SeqList()

算法描述：SeqList<DataType>

::SeqList(){length=0;}2.2线性表的顺序存储结构及实现

datalength0顺序表的实现——有参构造函数操作接口：SeqList(DataTypea[],intn)2.2线性表的顺序存储结构及实现顺序表

数组a351224334253512243342顺序表的实现——有参构造函数template<classDataType>SeqList<DataType>

::SeqList(DataTypea[],intn){if(n>MaxSize)throw"参数非法";

for(i=0;i<n;i++)

data[i]=a[i];length=n;}2.2线性表的顺序存储结构及实现算法描述：顺序表的实现——插入操作接口：voidInsert(inti,DataTypex)插入前：(a1,…,ai-1,ai,…,an)插入后：(a1,…,ai-1,x

,ai,…,an)2.2线性表的顺序存储结构及实现ai-1和ai之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化33顺序表的实现——插入例：（35，12，24，42），在i=2的位置上插入33。表满：length>=MaxSize合理的插入位置：1≤i≤length+1（i指的是元素的序号）2.2线性表的顺序存储结构及实现435122442a1a2a3a401234422412335什么时候不能插入？注意边界条件算法描述——伪代码1.如果表满了，则抛出上溢异常;2.如果元素的插入位置不合理，则抛出位置异常;3.将最后一个元素至第i个元素分别向后移动一个位置；4.将元素x填入位置i处；5.表长加1；2.2线性表的顺序存储结构及实现顺序表的实现——插入顺序表的实现——插入template<classDataType>voidSeqList<DataType>::Insert(inti,DataTypex){if(length>=MaxSize)throw"上溢";

if(i<1||i>length+1)throw"位置";for(j=length;j>=i;j--)data[j]=data[j-1];data[i-1]=x;length++;}算法描述——C++描述2.2线性表的顺序存储结构及实现基本语句？顺序表的实现——插入最好情况（i=n+1）：基本语句执行0次，时间复杂度为O(1)。最坏情况（i=1）：基本语句执行n+1次，时间复杂度为O(n)。平均情况（1≤i≤n+1）：时间复杂度为O(n)。时间性能分析2.2线性表的顺序存储结构及实现å+-+=11)=1(niiinpå+-++=11)=1(11niinn2n=O(n)操作接口：DataTypeDelete(inti)删除前：(a1,…,ai-1,ai,ai+1,…,an)删除后：(a1,…,ai-1,ai+1,…,an)

顺序表的实现——删除2.2线性表的顺序存储结构及实现ai-1和ai之间的逻辑关系发生了变化顺序存储要求存储位置反映逻辑关系存储位置要反映这个变化例：（35,33,12,24,42），删除i=2的数据元素。仿照顺序表的插入操作，完成：1.分析边界条件；2.分别给出伪代码和C++描述的算法；3.分析时间复杂度。2.2线性表的顺序存储结构及实现顺序表的实现——删除535a1a2a3a401234422412334a5122442顺序表的实现——按位查找操作接口：DataTypeGet(inti)

2.2线性表的顺序存储结构及实现0…i-2i-1…n-1Max-1a1…ai-1ai…an空闲

n算法描述：template<classDataType>DataTypeSeqList<DataType>

::Get(inti){

if(i>=1&&i<=length)returndata[i-1];}时间复杂度？顺序表的实现——按值查找操作接口：intLocate(DataTypex)

2.2线性表的顺序存储结构及实现535a1a2a3a40123442241233a5例：在（35,33,12,24,42）

中查找值为12的元素，返回在表中的序号。iii注意序号和下标之间的关系template<classDataType>intSeqList<DataType>

::Locate(DataTypex){for(i=0;i<length;i++)if(data[i]==x)returni+1;return0;}2.2线性表的顺序存储结构及实现顺序表的实现——按值查找算法描述：时间复杂度？顺序表类的声明constintMaxSize=100;template<classDataType>//模板类classSeqList{public:SeqList(intmaxlen=MaxSize);//构造函数

SeqList(DataTypea[],intn);~SeqList();//析构函数intLength();DataTypeGet(inti);intLocate(DataTypex);voidInsert(inti,DataTypex);DataTypeDelete(inti);private:

DataType*data;intlength;intmaxsize;

booladdSpace(intsize=10);};2.2线性表的顺序存储结构及实现(动态数组)顺序表的实现——构造函数操作接口：SeqList(int

maxlen=MaxSize)

算法描述：SeqList<DataType>

::SeqList(int

maxlen):length(0),maxsize(maxlen){if(maxlen<=0)throw“参数非法”; data=new

DataType[maxlen];}2.2线性表的顺序存储结构及实现(动态数组)

datalength0顺序表的实现——分配空间操作接口：booladdSpace(int

size=10)

算法描述：boolSeqList<DataType>

::addSpace(int

size){if(size<=0)returnfalse;tmpdata=data;maxlen+=size;data=new

DataType[maxlen];for(i=0;i<length;i++)data[i]=tmpdata[i];delete[]tmpdata;returntrue;}2.2线性表的顺序存储结构及实现(动态数组)顺序表的优缺点顺序表的优点：⑴无需为表示表中元素之间的逻辑关系而增加额外的存储空间；⑵随机存取：可以快速地存取表中任一位置的元素。

顺序表的缺点：⑴插入和删除操作需要移动大量元素；⑵表的容量难以确定，表的容量难以扩充；⑶造成存储空间的碎片。

2.2线性表的顺序存储结构及实现单链表：线性表的链接存储结构。存储思想：用一组任意的存储单元存放线性表的元素。2.3线性表的链接存储结构及实现单链表静态存储分配顺序表事先确定容量链表动态存储分配运行时分配空间连续不连续零散分布0200020803000325…………存储特点：逻辑次序和物理次序不一定相同。

2.元素之间的逻辑关系用指针表示。2.3线性表的链接存储结构及实现例：(a1,a2

,a3,a4)的存储示意图单链表a10200a20325a30300a4∧2.3线性表的链接存储结构及实现单链表0200020803000325…………a10200a20325a30300a4∧结点数据域指针域单链表是由若干结点构成的；单链表的结点只有一个指针域。data：存储数据元素next：存储指向后继结点的地址datanext单链表的结点结构：数据域指针域template<classDataType>structNode{DataTypedata;Node<DataType>*next;};

2.3线性表的链接存储结构及实现单链表datanext单链表的结点结构：如何申请一个结点？s=newNode<int>;template<classDataType>structNode{DataTypedata;Node<DataType>*next;};

2.3线性表的链接存储结构及实现单链表datanext单链表的结点结构：……sNodes=newNode<int>;2.3线性表的链接存储结构及实现单链表datanext……sNode如何引用数据元素？s->data;*s.data;data如何引用指针域？nexts->next;2.3线性表的链接存储结构及实现单链表0200020803000325…………a10200a20325a30300a4∧firsta1a2an∧非空表first=NULL空表重点在数据元素之间的逻辑关系的表示，所以，将实际存储地址抽象。什么是存储结构？2.3线性表的链接存储结构及实现单链表0200020803000325…………a10200a20325a30300a4∧firsta1a2an∧非空表first=NULL空表头指针：指向第一个结点的地址。尾标志：终端结点的指针域为空。2.3线性表的链接存储结构及实现单链表0200020803000325…………a10200a20325a30300a4∧firsta1a2an∧非空表first=NULL空表空表和非空表不统一，缺点？如何将空表与非空表统一？对第一个结点的操作与对其他结点的操作，使用语句可一致？头结点：在单链表的第以一个元素结点之前附设一个类型相同的结点，以便空表和非空表处理统一，并且可统一对任意位置的结点的操作实现。

2.3线性表的链接存储结构及实现单链表非空表firsta1a2an∧空表first∧template<classDataType>classLinkList{public:LinkList()；LinkList(DataTypea[],intn);~LinkList();intLength();DataTypeGet(inti);intLocate(DataTypex);voidInsert(inti,DataTypex);DataTypeDelete(inti);voidPrintList();private:Node<DataType>*first;};单链表类的声明2.3线性表的链接存储结构及实现单链表的实现——遍历操作操作接口：

voidPrintList();核心操作（关键操作）：工作指针后移。从头结点（或开始结点）出发，通过工作指针的反复后移而将整个单链表“审视”一遍的方法称为扫描（或遍历）。2.3线性表的链接存储结构及实现firsta1pa2pan∧aippp单链表的实现——遍历操作操作接口：

voidPrintList();2.3线性表的链接存储结构及实现template<classDataType>voidLinkList<DataType>::PrintList(){p=first->next;while(p!=NULL){cout<<p->data;p=p->next;}}p++能否完成指针后移？a1a2pp++p->next单链表的实现——按位查找操作接口：

DataTypeGet(inti);2.3线性表的链接存储结构及实现firsta1a2an∧aipp查找失败1.工作指针p初始化;累加器count初始化;2.重复执行下述操作，直到p为空：

2.1工作指针p后移;2.2count++;3.返回p->data的值；pcount=1pcount=2p查找成功count=itemplate<classDataType>DataTypeLinkList<DataType>::Get(inti){p=first->next;count=1;while(p!=NULL){if(count==i)returnp->data;p=p->next;count++;}throw“参数错误”;Node<DataType>tmp;returntmp.data;}2.3线性表的链接存储结构及实现单链表的实现——按位查找算法描述——C++描述template<classDataType>intLinkList<DataType>::Length(){p=first->next;count=0;while(p!=NULL){p=p->next;count++;}returncount;//注意count的初始化和返回值之间的关系}2.3线性表的链接存储结构及实现单链表的实现——按位查找——计算表长算法描述——C++描述template<classDataType>intLinkList<DataType>::Locate(DataTypex){p=first->next;count=1;

while(p!=NULL){if(p->data==x)returncount;//查找成功，返回序号p=p->next;count++;}return0;//退出循环表明查找失败}2.3线性表的链接存储结构及实现单链表的实现——按值查找算法描述——C++描述单链表的实现———插入操作接口：

voidInsert(inti,DataTypex);

2.3线性表的链接存储结构及实现如何实现结点ai-1、x和ai之间逻辑关系的变化？pxsfirsta1ai-1an∧ai算法描述：s=newNode<DataType>;s->data=x;s->next=p->next;p->next=s;注意分析边界情况——表头、表尾。

单链表的实现———插入2.3线性表的链接存储结构及实现firsta1an∧aipxs算法描述：s=newNode<DataType>;s->data=x;s->next=p->next;p->next=s;pxs∧由于单链表带头结点，表头、表中、表尾三种情况的操作语句一致。

算法描述——伪代码

1.工作指针p初始化；

2.查找第i-1个结点并使工作指针p指向该结点；

3.若查找不成功，则插入位置不合理，抛出插入位置异常；否则，3.1生成一个元素值为x的新结点s；

3.2将新结点s插入到结点p之后；2.3线性表的链接存储结构及实现单链表的实现———插入

template<classDataType>voidLinkList<DataType>::Insert(inti,DataTypex){p=first;count=0;//工作指针p应指向头结点

while(p!=NULL&&count<i-1)//查找第i–1个结点

{p=p->next;

count++;}if(p==NULL)throw"位置";//没有找到第i–1个结点

else{s=newNode;s->data=x;//申请一个结点ss->next=p->next;p->next=s;//结点s插入结点p之后

}}2.3线性表的链接存储结构及实现单链表的实现———插入基本语句？时间复杂度？单链表的实现———无参构造函数操作接口：LinkList()构造空表，即仅构造头结点。算法描述：first=newNode<DataType>;first->next=NULL;2.3线性表的链接存储结构及实现初始化first∧template<classDataType>LinkList<DataType>::LinkList(){ first=newNode<DataType>; first->next=NULL;}单链表的实现———构造函数操作接口：LinkList(DataTypea[],intn)头插法：将待插入结点插在头结点的后面。算法描述：first=newNode<DataType>;first->next=NULL;2.3线性表的链接存储结构及实现数组a3512243342初始化first∧单链表的实现———构造函数操作接口：LinkList(DataTypea[],intn)头插法：将待插入结点插在头结点的后面。2.3线性表的链接存储结构及实现数组a3512243342算法描述：s=newNode<DataType>;s->data=a[0];s->next=first->next;first->next=s;插入第一个元素结点first∧35s∧单链表的实现———构造函数操作接口：LinkList(DataTypea[],intn)头插法：将待插入结点插在头结点的后面。2.3线性表的链接存储结构及实现数组a3512243342算法描述：s=newNode<DataType>;s->data=a[1];s->next=first->next;first->next=s;依次插入每一个结点12sfirst35∧template<classDataType>LinkList<DataType>::LinkList(DataTypea[],intn){first=newNode<DataType>;first->next=NULL;for(i=0;i<n;i++){s=newNode<DataType>;s->data=a[i];

s->next=first->next;first->next=s;}}2.3线性表的链接存储结构及实现单链表的实现———构造函数尾插法：将待插入结点插在终端结点的后面。

2.3线性表的链接存储结构及实现单链表的实现———构造函数操作接口：LinkList(DataTypea[],intn)算法描述：first=newNode<DataType>;rear=first;数组a3512243342初始化firstrear尾插法：将待插入结点插在终端结点的后面。

2.3线性表的链接存储结构及实现单链表的实现———构造函数操作接口：LinkList(DataTypea[],intn)算法描述：s=newNode<DataType>;s->data=a[0];rear->next=s;rear=s;数组a3512243342插入第一个元素结点firstrear35srear尾插法：将待插入结点插在终端结点的后面。

2.3线性表的链接存储结构及实现单链表的实现———构造函数操作接口：LinkList(DataTypea[],intn)算法描述：s=newNode<DataType>;s->data=a[1];rear->next=s;rear=s;数组a3512243342依次插入每一个结点first35rear12srear尾插法：将待插入结点插在终端结点的后面。

2.3线性表的链接存储结构及实现单链表的实现———构造函数操作接口：LinkList(DataTypea[],intn)算法描述：rear->next=NULL;数组a3512243342最后一个结点插入后first3542srear∧template<classDataType>LinkList<DataType>::LinkList(DataTypea[],intn){first=newNode;//生成头结点

r=first;//尾指针初始化for(i=0;i<n;i++){s=newNode;s->data=a[i];

r->next=s;r=s;}r->next=NULL;}2.3线性表的链接存储结构及实现单链表的实现———构造函数算法描述：单链表的实现———删除操作接口：

DataTypeDelete(inti);

2.3线性表的链接存储结构及实现p如何实现结点ai-1和ai之间逻辑关系的变化？firsta1ai-1ai+1ai算法描述：q=p->next;x=q->data;p->next=q->next;deleteq;q单链表的实现———删除2.3线性表的链接存储结构及实现算法描述：q=p->next;x=q->data;p->next=q->next;deleteq;注意分析边界情况——表头、表尾。

pqpq表尾的特殊情况：虽然被删结点不存在，但其前驱结点却存在。p->next=NULLfirsta1ana2∧算法描述——伪代码1.工作指针p初始化；2.查找第i-1个结点并使工作指针p指向该结点；3.若p不存在或p不存在后继结点，则抛出位置异常；否则，3.1暂存被删结点和被删元素值；3.2摘链，将结点p的后继结点从链表上摘下；3.3释放被删结点；3.4返回被删元素值；

2.3线性表的链接存储结构及实现单链表的实现———删除template<classDataType>DataTypeLinkList<DataType>::Delete(inti){p=first;count=0;

while(p!=NULL&&count<i-1)

{p=p->next;count++;}if(p==NULL||p->next==NULL)

throw"位置";else{q=p->next;x=q->data;p->next=q->next;deleteq;returnx;}}2.3线性表的链接存储结构及实现单链表的实现———删除单链表的实现——析构函数析构函数将单链表中所有结点的存储空间释放。

2.3线性表的链接存储结构及实现操作接口：~LinkList();firsta1a2an∧aiq算法描述：q=first;first=first->next;deleteq;first注意：保证链表未处理的部分不断开

单链表的实现——析构函数template<classDataType>LinkList<DataType>::~LinkList(){while(first!=NULL)

{q=first;

first=first->next;

deleteq;}}2.3线性表的链接存储结构及实现算法描述：启示：算法设计的一般过程算法设计的一般步骤：第一步：确定入口（已知条件）、出口（结果）；第二步：根据一个小实例画出示意图；第三步：①正向思维：选定一个思考问题的起点，逐步提出问题、解决问题；②逆向思维：从结论出发分析为达到这个结论应该先有什么；③正逆结合；第四步：写出顶层较抽象算法，分析边界情况；第五步：验证第四步的算法；第六步：写出具体算法；第七步：进一步验证，手工运行。循环链表firsta1ai-1an∧aip从单链表中某结点p出发如何找到其前驱？将单链表的首尾相接，将终端结点的指针域由空指针改为指向头结点，构成单循环链表，简称循环链表。2.3线性表的链接存储结构及实现循环链表空表和非空表的处理一致附设头结点first空循环链表firsta1ai-1anai非空循环链表2.3线性表的链接存储结构及实现firsta1ai-1anai循环链表——插入xspxspxsp算法描述：s=newNode<DataType>;s->data=x;s->next=p->next;p->next=s;2.3线性表的链接存储结构及实现

template<classDataType>voidLinkList<DataType>::Insert(inti,DataTypex){p=first;count=0;

while(p->next!=first&&count<i-1){p=p->next;count++;}if(i<=0||count<i-1)throw"位置";else{s=newNode<DataType>;s->data=x;s->next=p->next;p->next=s;}}

循环链表——插入与单链表的插入操作相比，差别是什么？2.3线性表的链接存储结构及实现循环条件：p!=NULL

p!=firstp->next!=NULL

p->next!=first循环链表循环链表中没有明显的尾端如何避免死循环2.3线性表的链接存储结构及实现如何查找开始结点和终端结点？循环链表firsta1ai-1anai开始结点：first->next终端结点：将单链表扫描一遍，时间为O(n)2.3线性表的链接存储结构及实现reara1ai-1anai开始结点：rear->next->next终端结点：rear循环链表带尾指针的循环链表一个存储结构设计得是否合理，取决于基于该存储结构的运算是否方便，时间性能是否提高。2.3线性表的链接存储结构及实现双链表如何求结点p的直接前驱，时间性能？firsta1ai-1anaip为什么可以快速求得结点p的后继？如何快速求得结点p的前驱？2.3线性表的链接存储结构及实现双链表：在单链表的每个结点中再设置一个指向其前驱结点的指针域。双链表结点结构：priordatanextdata：数据域，存储数据元素；prior：指针域，存储该结点的前趋结点地址；next：指针域，存储该结点的后继结点地址。2.3线性表的链接存储结构及实现template<classDataType>structDulNode{DataTypedata;DulNode<DataType>*prior,*next;};

双链表启示？时空权衡——空间换取时间priordatanext定义结点结构：2.3线性表的链接存储结构及实现双链表的操作——插入s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;ai-1ai操作接口：

voidInsert(DulNode<DataType>*p,DataTypex);

pxs注意指针修改的相对顺序2.3线性表的链接存储结构及实现双链表的操作——删除(p->prior)->next=p->next;

(p->next)->prior=p->prior;

操作接口：

DataTypeDelete(DulNode<DataType>*p);

ai-1aipai结点p的指针是否需要修改？deletep;2.3线性表的链接存储结构及实现存储分配方式比较顺序表采用顺序存储结构，即用一段地址连续的存储单元依次存储线性表的数据元素，数据元素之间的逻辑关系通过存储位置来实现。链表采用链接存储结构，即用一组任意的存储单元存放线性表的元素，用指针来反映数据元素之间的逻辑关系。2.4顺序表和链表的比较2.4顺序表和链表的比较时间性能比较

时间性能是指实现基于某种存储结构的基本操作（即算法）的时间复杂度。

按位查找：顺序表的时间为Ｏ(1)，是随机存取；链表的时间为Ｏ(n)，是顺序存取。插入和删除：顺序表需移动表长一半的元素，时间为Ｏ(n)；链表不需要移动元素，在给出某个合适位置的指针后，插入和删除操作所需的时间仅为Ｏ(1)。2.4顺序表和链表的比较空间性能比较

空间性能是指某种存储结构所占用的存储空间的大小。

定义结点的存储密度：数据域占用的存储量整个结点占用的存储量存储密度＝结点的存储密度：顺序表：结点的存储密度为1（只存储数据元素），没有浪费空间；链表：结点的存储密度<1（包括数据域和指针域），有指针的结构性开销。2.4顺序表和链表的比较空间性能比较

空间性能是指某种存储结构所占用的存储空间的大小。

定义结点的存储密度：数据域占用的存储量整个结点占用的存储量存储密度＝结构的存储密度：顺序表：需要预分配存储空间，如果预分配得过大，造成浪费，若估计得过小，又将发生上溢；链表：不需要预分配空间，只要有内存空间可以分配，单链表中的元素个数就没有限制。结论⑴若线性表需频繁查找却很少进行插入和删除操作，或其操作和元素在表中的位置密切相关时，宜采用顺序表作为存储结构；若线性表需频繁插入和删除时，则宜采用链表做存储结构。⑵当线性表中元素个数变化较大或者未知时，最好使用链表实现；而如果用户事先知道线性表的大致长度，使用顺序表的空间效率会更高。2.4顺序表和链表的比较总之，线性表的顺序实现和链表实现各有其优缺点，不能笼统地说哪种实现更好，只能根据实际问题的具体需要，并对各方面的优缺点加以综合平衡，才能最终选定比较适宜的实现方法。静态链表：用数组来表示单链表，用数组元素的下标来模拟单链表的指针。静态链表2.5线性表的其它存储方法data：存储放数据元素；next：也称游标，存储该元素的后继在数组的下标。数组元素（结点）的构成：datanext数据域指针域例：线性表(张，王，李，赵，吴)的静态链表存储2.5线性表的其它存储方法静态链表张2王3李4赵5吴-101234567878-11datanextfirstavailfirst：静态链表头指针，为了方便插入和删除操作，通常静态链表带头结点；avail：空闲链表头指针，空闲链表由于只在表头操作，所以不带头结点；2.5线性表的其它存储方法静态链表静态链表的存储结构定义如下：constintMaxSize=100;//100只是示例数据template<classDataType>structSNode{DataTypedata;//DataType表示不确定的数据类型

intnext;//指针域（也称游标）}SList[MaxSize];在线性表(张，王，李，赵，吴)中“王”之后插入“孙”2.5线性表的其它存储方法张2王3李4赵5吴-101234567878-11datanext静态链表张2王

6李4赵5吴-1012345678孙

38-11datanext王之后插入孙availavailfirstfirst2.5线性表的其它存储方法静态链表假设结点s插在结点p之后，则修改指针的操作为：

s=avail;//利用空闲链的第一个结点

avail=SList[avail].next;//空闲链的头指针后移

SList[s].data=x;//将x填入下标为s的结点

SList[s].next=SList[p].next;//将下标为s的结点插入到

SList[p].next=s;//下标为p的结点后面在线性表(张，王，李，赵，吴)中删除“赵”2.5线性表的其它存储方法张2王3李4赵5吴-101234567878-11datanext静态链表张2王

3李

5赵5吴-1012345678

78-11datanext删除赵摘链在线性表(张，王，李，赵，吴)中删除“赵”2.5线性表的其它存储方法张2王3李4赵5吴-101234567878-11datanext静态链表张2王

3李

5

6吴-1012345678

78-11datanext删除赵归还空间2.5线性表的其它存储方法静态链表假设删除结点p的后继结点，则修改指针的操作为：

q=SList[p].next;//暂存被删结点的下标

SList[p].next=SList[q].next;//摘链

SList[q].next=avail;//将结点q插在链avail的最前端

avail=q;//空闲链头指针avail指向结点q2.5线性表的其它存储方法静态链表相对于顺序表而言，静态链表有什么优点？

优点：在执行插入和删除操作时，只需修改游标，不需要移动表中的元素，从而改进了在顺序表中插入和删除操作需要移动大量元素的缺点。缺点：没有解决连续存储分配带来的表长难以确定的问题；静态链表还需要维护一个空闲链；静态链表不能随机存取。

间接寻址间接寻址：是将数组和指针结合起来的一种方法，它将数组中存储数据元素的单元改为存储指向该元素的指针。2.5线性表的其它存储方法012i-1n-1Max-1……

空闲

长度a1aiana2插入操作移动的不是元素而是指向元素的指针。当元素占用的空间较多时，比顺序表的插入操作快得多。多项式(Polynomial)n阶多项式Pn(x)有n+1项。

系数a0,a1,a2,…,an

指数0,1,2,…,n。按升幂排列

多项式的顺序存储表示第一种：

private:(静态数

intdegree; 组表示)floatcoef[maxDegree+1];

Pn(x)可以表示为：

pl.degree=n pl.coef[i]=ai,0

i

na0

a1

a2……an………012degreemaxDegree-1coefn第二种：private: (动态数

intdegree;组表示) float*coef; Polynomial::Polynomial(int

sz){ degree=sz;

coef=newfloat[degree+1]; }以上两种存储表示适用于指数连续排列的多项式。但对于绝大多数项的系数为零的多项式（称为稀疏多项式），如

P101(x)=3+5x50-4x101,不经济。第三种：

structterm{//多项式的项定义 floatcoef;//系数

intexp; //指数

};statictermtermArray[maxTerms];//项数组staticintfree,maxTerms;//当前空闲位置指针

a0

a1

a2……ai……ame0

e1

e2……ei

……emcoefexp012i

m初始化：//termPolynomial::termArray[MaxTerms];//intPolynomial::free=0;class

Polynomial{//多项式定义public:……private:intstart,finish;//多项式始末位置}两个多项式存储的例子

A(x)=2.0x1000+1.8

B(x)=1.2+51.3x50+3.7x101

两个多项式存放在termArray中A.startA.finishB.startB.finishfreecoefexp1.82.01.251.33.7……01000050101……maxTerms两个多项式的相加结果多项式另存扫描两个相加多项式，若都未检测完：

若当前被检测项指数相等，系数相加。若未变成0，则将结果加到结果多项式。若当前被检测项指数不等，将指数小者加到结果多项式。若有一个多项式已检测完，将另一个多项式剩余部分复制到结果多项式。PolynomialPolynomial::Add(PolynomialB){

PolynomialC;

int

a=start;

int

b=B.start;

C.start=free;

floatc;

while(a<=finish&&b<=B.finish)

Switch

(compare(termArray[a].exp,termArray[b].exp)){

//比较对应项指数

case‘=’://指数相等

c=termArray[a].coef+termArray[b].coef;if(c)NewTerm(c,termArray[a].exp);

a++;b++;

break;case'>':

NewTerm(termArray[b].coef,

termArray[b].exp);

b++;

break;

case'<':

NewTerm(termArray[a].coef,

termArray[a].exp);

a++;

}for(;a<=finish;a++)//a未检测完时

NewTerm(termArray[a].coef,

termArray[a].exp);for(

;b<=B.finish;b++)//b未检测完时

NewTerm(termArray[b].coef,

termArray[b].exp);

C.finish=free-1;

return

C;}在多项式中加入新的项void

Polynomial::NewTerm(floatc,

inte){

//把一个新的项加到多项式C(x)中

if(free>=maxTerms){cout<<"Toomanytermsinpolynomials”<<

endl;return;

}

termArray[free].coef=c;

termArray[free].exp=e;

free++;}

多项式顺序存储表示的缺点插入和删除时项数可能有较大变化，因此要移动大量数据不利于多个多项式的同时处理采用多项式的链表表示可以克服这类困难：多项式的项数可以动态地增长，不存在存储溢出问题。插入、删除方便，不移动元素。多项式的链表存储表示在多项式的链表表示中，每个结点三个数据成员：通过链接指针，可以将多项式各项按指数递增的顺序链接成一个单链表。在此结构上，新项的加入和废项的删除执行简单的链表插入和删除操作即可解决。多项式的链表结构coefexpnext

Data

Term多项式(polynomial)类的链表定义structTerm{

//多项式结点定义

floatcoef; //系数

intexp; //指数

Term*next; //链接指针

Term(floatc,inte,Term*link=NULL)

{coef=c;exp=e;next=link;} Term*InsertAfter(floatc,inte);

friendostream&operator

<<

(ostream&,

constTerm&);};classPolynomial{

//多项式类的定义public: Polynomal(){first=newTerm(0,-1);} //构造函数

Polynomal(Polynomal&R);//复制构造函数

intmaxOrder(); //计算最大阶数private: Term*first;

friendostream&operator<<(ostream&,constPolynomal&);friendistream&operator>>(istream&,

Polynomal&);friendvoidAdd(Polynomial&A,Polynomial&B,

Polynomial&C);

friendvoidMul(Polynomial&A,Polynomial&B,

Polynomial&C);};Term*Term::InsertAfter(floatc,inte){//在调用此函数的对象后插入一个新项

next=newTerm(c,e,next);

//创建一个新结点，自动链接

returnnext; //插入到this结点后面};

ostream&operator<<(ostream&out,constTerm&x){//Term的友元函数：输出一个项x的内容到输出流对//象out中去。

if(x.coef==0.0)returnout;//零系数项不输出

out<<x.coef; //输出系数

switch(x.exp){ //输出指数

case0:break; //指数为0,不出现‘X’

case1:out<<“X”;break;//在系数后输出‘X’

default: