线性表1-顺序表及单链表

数据结构与算法2009年秋季授课教师：张剑波方芳授课班级：111081-4班115081-2班Chapter3线性表本章教学内容3.2线性表ADT3.3线性表的公式化描述（数组表示）3.4线性表的链表描述3.5线性表的应用3.2线性表（Linear_List）1、线性表（Linear_List）的示例例如：1、（0，1，2，3，4，5，6，7，8，9）；学号姓名性别年龄成绩高数英语物理体育98011张娟女208086819098012赵立军男1982728986……………………

2、一本书可以看成是一个线性表；

3、学生成绩档案表：线性表是n(n≥0)个相同类型数据元素构成的有限序列，其中n为线性表的长度。

n=0的线性表称为空表；

n>0时，非空表，通常记为（e1,e2,…,ei-1,ei,ei+1,…en-1,en）

ei(1≤i≤n)是线性表中第i个元素

e1：第一个元素（无前驱）

en：最后一个元素（无后继）

ei优先于ei+1（ei是ei+1的前驱，ei+1是ei的后继）线性表的定义线性表的ADT（ADT3-1）本书：线性表的描述公式化描述使用数组，借助数学公式指明每个元素存储位置。链表描述每个元素中包含指向下一个元素的指针。间接寻址建立一张单独的元素地址表，存放指向元素的指针。模拟指针类似链表描述，用整数代替C++指针。1、顺序表的定义2、顺序表的特点用一组地址连续的存储单元依次存放线性表中的各数据元素。逻辑结构上相邻的元素其物理结构也相邻。3、用一维数组描述顺序表中数据元素的存储区域。3.3线性表的公式化描述（顺序表）使用一维数组element[]，按照数学公式将每个元素映射到数组中的特定位置。第i个元素放置在element[i-1]：location(i)=i-1变量

length

记录当前元素数目。length=5数组下标索引位置1234567abcde0123456数据元素公式化描述的线性表类（程序3-1）template<classT>classLinearList{public:

LinearList(intMaxListSize=10);

~LinearList(){delete[]element;}boolIsEmpty()const{returnlength==0;}/*判断是否为空*/intLength()const{returnlength;}/*返回长度*/boolFind(intk,T&x)const;/*寻找第k个元素，保持在x中，else，返回false*/intSearch(constT&x)const;/*返回元素x在表中的位置，如果不在则返回0*/

LinearList<T>&Delete(intk,T&x);/*删除表中第k个元素，保存于x中，函数返回修改后的链表*/LinearList<T>&Insert(intk,constT&x);/*在第K个元素之后插入x，函数返回修改后的链表*/LinearList<T>&Reverse();voidOutput(ostream&out)const;private:intlength;intMaxSize;T*element;//动态一维数组};补充：替换new的异常处理#include<new.h>1、定义自己的异常处理类classNoMem{public:NoMem(){}};2、定义VC要求的异常函数intmy_new_handler(size_tx){throwNoMem();return0;};3、环境设置与恢复_PNHold_Handler=_set_new_handler(my_new_handler);使用：int*p=newint[1000];_set_new_handler(old_Handler);-操作1-创建空表（程序3-3）template<classT>LinearList<T>::LinearList(intMaxListSize){MaxSize=MaxListSize;element=newT[MaxSize];length=0;}-操作2-取元素（程序3-3）template<classT>boolLinearList<T>::Find(intk,T&x)const{//将第k个元素取至x中if(k<1||k>length)returnfalse;

x=element[k-1];

returntrue;}时间复杂度：Θ(1)-操作3-查找（程序3-3）template<classT>intLinearList<T>::Search(constT&x)const{//返回值为x的元素下标。【注意】此处有效下标为[1,n]for(inti=0;i<length;i++)

if(element[i]==x)

return++i;

return0;}时间复杂度：Θ(n)（a1,…,ak-1,ak,ak+1…,an）（a1,…,ak-1,ak+1,…,an）1a12a2……kakk+1ak+1……lengthan……MaxSize1a12a2……kak+1k+1ak+2……length-1an……MaxSize删除前删除后-操作4：删除删除算法（程序3-4）template<classT>LinearList<T>&LinearList<T>::Delete(intk,T&x){if(Find(k,x)){

for(inti=k;i<length;i++)element[i-1]=element[i];

//元素前移

length--;

return*this;}else{throwOutOfBounds();//越界异常return*this;}}时间复杂度：O(length-k)-删除算法分析删除算法的时间代价主要耗费在移动数据元素上，移动数据元素的个数取决于删除元素的位置。

最好情形：删除表尾元素，不需要移动其它元素（移动个数为0）；

最坏情形：删除序号为1的元素，需要将表中其他的元素全部向前移（移动个数为n-1）；删除时，数据平均移动次数AMN：可供删除的位置有n个；假设删除第i个元素的概率为Pi，删除第i个元素，数据移动的次数为（n-i）个；不失一般性，等概率Pi=1/n（a1,…,ak,ak+1,…,an）（a1,…,ak,x,ak+1,…,an）1a12a2……kakk+1ak+1……lengthan……MaxSize1a12a2……kakk+1xk+2ak+1……lengthan-1length+1an…MaxSize插入x插入前插入后-操作5：插入插入算法（程序3-5）template<classT>LinearList<T>&LinearList<T>::Insert(intk,constT&x){if(k<0||k>length)throwOutOfBounds();//越界异常if(length==MaxSize)throwNoMem();//空间异常

for(inti=length-1;i>=k;i--)element[i+1]=element[i];

//元素后移

element[k]=x;

length++;

return*this;}时间复杂度：O(length-k)-插入算法分析插入算法的时间代价主要耗费在移动数据元素上，移动数据元素的个数取决于插入元素的位置。

最好情形：在表尾追加一个新元素，不需要移动其它元素（移动个数为0）；

最坏情形：在序号为1的元素之前插入一个元素，需要将表中所有的元素全部向后移（移动个数为n）；插入时，数据平均移动次数AMN：可供插入的位置有n+1个；假设在第i个元素之前插入一个元素的概率为Pi，在第i个元素之前插入，数据移动的次数为（n-i+1）个；不失一般性，等概率Pi=1/（n+1）-操作6-输出（程序3-6）template<classT>voidLinearList<T>::Output(ostream&out)const{//Putthelistintothestreamout.for(inti=0;i<length;i++)out<<element[i]<<"";}template<classT>//输出流操作符<<重载ostream&operator<<(ostream&out,constLinearList<T>&x){x.Output(out);returnout;}外部调用：cout<<L;时间复杂度：Θ(length)-操作7：顺序表的原地逆置template<classT>LinearList<T>&LinearList<T>::Reverse(){

空间要求：只能使用一个临时变量T}for(inti=0;i<length/2;i++)Swap(element[i],element[length-1-i]);return*this;公式化描述方法（顺序表）分析【特点】逻辑结构上相邻的元素其物理结构也相邻。查找、删除、插入算法：与表的大小呈线性的关系。【缺点】空间的低效利用。问题2：插入、删除算法涉及频繁元素移动，如何改进？问题1：如何做到根据元素增长，动态分配T*element？【优点】存取操作速度快。多个线性表公用一个数组空间first[1]last[1]first[2]first[3]last[2]last[3]一种解决空间低效利用的方法！1234……789使用线性表（程序3-7）程序运行结果：课后作业编码实现：Page85【练习7】【练习8】有序表的合并、拆分函数原型声明（参考形式）template<classT>LinearList<T>&LinearList<T>::Merge(LinearList<T>&LA,LinearList<T>&LB);10月7日前发至：fangfangcug@126.com

邮件名称：11108X-XX-顺序表合并、拆分本章教学内容3.2线性表ADT3.3线性表的公式化描述（数组表示）3.4线性表的链表描述3.5线性表的应用3.4链表描述1、定义用一组任意的存储单元存储线性表的数据元素（这些存储单元可以是连续的，也可以是不连续的）。一种物理存储单元上非连续、非顺序的存储结构。数据元素的逻辑顺序通过链表中指针链接次序实现的。为了表示每个元素ai与其直接后继ai+1之间的逻辑关系存储数据元素本身的信息；存储指示其直接后继的信息（即直接后继的存储位置）。链式存储结构中每个数据元素占用一个节点（Node），一个节点由两个域组成：

数据域（设域名为data）：存储数据元素信息的域；

指针域（设域名为link）：存储直接后继存储位置的域，指针域中存储的信息称作指针或链。datalink链表节点结构adatalink例：设有线性表（A,B,C,D,E,F），该线性表的链表形式如下：ABCDEF∧firstlast链表逻辑结构示意图（1）数据域：存放数据元素A、B、C、D、E、F的域；（2）指针域：存放指针的域；（3）节点：包含数据域值和指针域值；（4）第一个节点（首元节点）：节点A；尾节点：节点F;（5）A节点称为B节点的直接前驱，B节点称为A节点的直接后继；（6）first称为表头指针；last称为链尾指针；（7）最后一个节点的指针不指向任何节点，称为空指针（NULL）。链表中常用的几个概念链表中每个节点可以包含若干个数据域和指针域。根据指针的数量和性质的不同，可以将链表分为以下类型:按指针数量分类按指针性质分类单链表——只有一个指针域多链表——有多个指针域（多为双向链表）普通链表（非循环链表）循环链表链表的分类1、定义：若链表中的每个节点只有一个指针域。2、单链表的逻辑状态和物理状态数据元素之间的相对关系是由链表中的指针域所指示的；单链表中的节点之间由链建立起来的逻辑顺序必须和线性表中相应的数据元素的顺序相一致；数据元素在内存中以任意次序存放。单链表中必须指出第一个节点的存储地址，所以需要设立一个特殊的指针，称为头指针。整个链表的存取都是从头指针开始进行的。单链表（线性链表）例：设有线性表（a1，a2，a3，a4，a5，a6），采用单链表进行存储，其物理状态如下图所示:存储地址数据域指针域21a58234a24545a3665058a13466a42182a6NULL8758first单链表存储状态示例单链表的逻辑结构示意图链接（指针）域数据域abcdeNULLfirst链表中每个节点代表一个元素；每个节点包含一个指针，指向下一个节点；

最后一个节点的指针域是NULL。单链表类定义-节点类ChianNode（程序3-8）template<classT>classChainNode{friendChain<T>;private:Tdata;ChainNode<T>*link;};linkdata单链表类定义-单链表类Chian（程序3-8）template<classT>classChain{public:

Chain(){first=0;}

~Chain();boolIsEmpty()const{returnfirst==0;}intLength()const;boolFind(intk,T&x)const;intSearch(constT&x)const;Chain<T>&Delete(intk,T&x);Chain<T>&Insert(intk,constT&x);voidOutput(ostream&out)const;private:ChainNode<T>*first;//指向第一个节点的指针};线性表的链表描述不需要指定表的最大长度。补充：指针的基本操作实例操作内容执行操作的语句执行前后指针指向节点指针指向后继指针移动指针改接指针改接后继p=qp=q->linkp=p->linkp->link=qp->link=q->linkBCDpqEFq-操作1：删除表中所有节点（程序3-9）template<classT>Chain<T>::~Chain(){

ChainNode<T>*next;

while(first)

{

next=first->link;

deletefirst;

first=next;}}时间复杂度：Θ(n)-操作2：确定链表长度（程序3-10）template<classT>intChain<T>::Length()const{//Returnthenumberofelementsinthechain.ChainNode<T>*current=first;intlen=0;

while(current){len++;current=current->link;}returnlen;}时间复杂度：Θ(n)-操作3：在链表中查找第k个元素（程序3-11）template<classT>boolChain<T>::Find(intk,T&x)const{//Setxtothek'thelementinthechain.//Returnfalseifnok'th;returntrueotherwise.if(k<1)returnfalse;ChainNode<T>*current=first;intindex=1;//indexofcurrent

while(index<k&¤t){current=current->link;index++;}if(current){x=current->data;returntrue;}returnfalse;//nok'thelement}时间复杂度：Θ(n)-操作4：在链表中搜素（程序3-12）template<classT>intChain<T>::Search(constT&x)const{//Locatex.Returnpositionofxiffound.//Return0ifxnotinthechain.ChainNode<T>*current=first;intindex=1;//indexofcurrent

while(current&¤t->data!=x){current=current->link;index++;}if(current)returnindex;return0;}时间复杂度：Θ(n)-操作5：输出链表（程序3-13）template<classT>voidChain<T>::Output(ostream&out)const{

//Insertthechainelementsintothestreamout.

ChainNode<T>*current;

for(current=first;current;current=current->link)

out<<current->data<<"";}//overload<<template<classT>ostream&operator<<(ostream&out,constChain<T>&x){

x.Output(out);

returnout;}时间复杂度：Θ(n)-操作6：删除节点：Delete(1,x)abcdeNULLfirstp=first;first=first->link;deletep;p删除表头节点删除节点：Delete(3,x)abdeNULLfirstc第1步，到达要删除节点的前一个节点

。ccbq删除非表头节点删除节点：Delete(3,x)第2步，保存指向待删节点的指针。p=q->link;qabcdeNULLfirstp删除节点：Delete(3,x)第3步，改变前节点的指针域，使其指向待删节点的后一节点。q->link=p->link;deletep;qabcdeNULLfirstp-删除算法（程序3-14）template<classT>Chain<T>&Chain<T>::Delete(intk,T&x){

//Setxtothek'thelementanddeleteit.

//ThrowOutOfBoundsexceptionifnok'thelement.

if(k<1||!first)throwOutOfBounds();//nok'th

//pwilleventuallypointtok'thnode

ChainNode<T>*p=first;

//moveptok'th&removefromchainif(k==1)

//palreadyatk'thfirst=first->link;//remove

-删除算法（续）（程序3-14）else{

//useqtogettok-1'stChainNode<T>*q=first;for(intindex=1;index<k-1&&q;index++)

q=q->link;if(!q||!q->link)throwOutOfBounds(

);

//nok'thp=q->link;

//k'thq->link=p->link;}

//removefromchain

//savek'thelementandfreenodep

x=p->data;

deletep;

retu