【4】Chapter3 线性表1-顺序表及单链表

1,数据结构与算法,2011年秋季,授课教师：张剑波授课班级：111101-2班,2,第二部分数据结构,第3章-第12章（线性表、数组、栈、队列、树、图等）,3,3.1引言,基本概念和术语数据数据元素数据对象数据结构数据结构研究的内容数据结构的描述：抽象数据类型（ADT）,4,1、基本概念和术语数据,1、数据（Data）,数据是信息的载体，是描述客观事物的数、字符以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据=x|x是计算机操作的对象,数值性数据：如整数、实数、复数、双精度数等。非数值性数据：如字符串、文字、图形、语音等。,数据主要有两类：,5,2、数据元素（DataElement）,数据元素是数据（集合）中的一个个体，是数据结构中讨论的基本单位；,数据元素在计算机程序中通常作为一个整体进行考虑和处理；,例如，一个学生基本情况是一个由（学号、姓名、性别、年龄，成绩）等数据项组成的数据元素。,基本概念和术语数据元素,6,组合项,初等项,数据元素,（记录）,数据元素在不同的数据结构中称呼也有所不同。例如：在文件中，数据的基本单位称为“记录”；在树、图数据结构中，数据的基本单位称为“节点”或“顶点”。,7,3、数据对象（DataObject）,一组实例构成的集合；具有相同性质的数据元素；数据的一个子集。,所有的数构成“数”集合，自然数集合N1，2，是“数”的数据对象；所有的字符是数据，字母集合LETTERA，B，Z，a，b，z是该数据的数据对象。,例如,基本概念和术语数据对象,我们研究：数据对象的描述以及与之相关的函数的具体实现。,8,基本概念和术语数据结构,4、数据结构（DataStructure）,数据对象+实例和元素中的存在的各种关系。,不同的关系构成不同的结构。,数据结构的形式化定义：Data_Structure（D，R）D是数据元素的有限集合（即某一数据对象）；R是D中所有元素之间的关系的有限集合。,9,（1）集合：结构中的数据元素除了“同属于一个集合”的关系外，别无其他关系；,（2）线性结构：结构中的数据元素存在的是一种线性关系，即一对一的关系；,（3）树形结构：结构中的元素存在着一对多的关系；,（4）图形结构或网状结构：结构中的数据元素存在着多对多的关系。,数据结构中元素关系的四种常见类型,10,3、数据结构的研究内容,数据的逻辑结构如：线性表、栈、队列、树、图数据的物理结构（存储结构）如：顺序存储结构、链式存储结构数据的操作实现算法及算法分析如：插入、删除、查找、遍历结构的应用实例,11,逻辑结构VS.物理结构,12,（1）逻辑结构的分类,线性结构线性表、栈、队列、串、数组非线性结构树型结构图（网络结构）,13,（2）存储（物理）结构的分类,数据结构在计算机中的表示数据的存储结构依赖于计算机语言顺序存储表示链式存储表示索引存储表示散列存储表示,14,顺序映象顺序存储结构（公式化描述）,借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。例如：,16,（3）数据操作,操作是定义在数据的逻辑结构上，但具体实现要在存储结构上进行。每种逻辑结构都有一个操作集合，常用的操作有：结构的生成：Create结构的销毁：Destroy在结构中查找（搜索）满足规定条件的数据元素：Search在结构中插入新的数据元素：Insert删除结构中已经存在的数据元素：Delete遍历：Traverse,17,（4）数据结构应用示例,管理信息系统中的查询问题,文件中的记录可按顺序方式组织。,顺序文件,导出的链表,为提高检索效率，可将所有选修“算法分析”课的同学记录串接到一起，这种串接称为“加链”。,18,4、数据结构的描述：ADT,数据类型是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。高级程序设计语言中的数据类型有2类：原子类型：整型、实型、字符型、布尔型、枚举类型、指针类型等。结构类型：数据结构定义在其上的一组操作。,19,抽象数据类型（ADT）,抽象数据类型（AbstractDataTypes，ADT）：一个数学模型以及定义在此数学模型上的一组操作。ADT的两个重要特征：数据抽象：强调的是其本质的特征、所能完成和实现的功能以及它和外部用户的接口。数据封装：将实体的外部特征和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。C+语言使用用户定义的类（Class）来表示ADT。,20,Chapter3线性表,21,本章教学内容,3.2线性表ADT3.3线性表的公式化描述（数组表示）3.4线性表的链表描述3.5线性表的应用,22,3.2线性表（Linear_List）,1、线性表（Linear_List）的示例,例如：1、（0，1，2，3，4，5，6，7，8，9）；,2、一本书可以看成是一个线性表；,3、学生成绩档案表：,23,线性表是n(n0)个相同类型数据元素构成的有限序列，其中n为线性表的长度。n=0的线性表称为空表；n0时，非空表，通常记为（e1,e2,ei-1,ei,ei+1,en-1,en）ei(1in)是线性表中第i个元素e1：第一个元素（无前驱）en：最后一个元素（无后继）ei优先于ei+1（ei是ei+1的前驱，ei+1是ei的后继）,线性表的定义,24,线性表的ADT（ADT3-1）,25,本书：线性表的描述,公式化描述使用数组，借助数学公式指明每个元素存储位置。链表描述每个元素中包含指向下一个元素的指针。间接寻址建立一张单独的元素地址表，存放指向元素的指针。模拟指针类似链表描述，用整数代替C+指针。模拟new和delete操作,26,1、顺序表的定义,2、顺序表的特点,用一组地址连续的存储单元依次存放线性表中的各数据元素。,逻辑结构上相邻的元素其物理结构也相邻。,3、用一维数组描述顺序表中数据元素的存储区域。,3.3线性表的公式化描述（顺序表）,27,使用一维数组element，按照数学公式将每个元素映射到数组中的特定位置。,第i个元素放置在elementi-1：location(i)=i-1变量length记录当前元素数目。,length=5,数组下标,索引位置,数据元素,28,公式化描述的线性表类（程序3-1）,templateclassLinearListpublic:LinearList(intMaxListSize=10);LinearList()deleteelement;boolIsEmpty()constreturnlength=0;intLength()constreturnlength;boolFind(intk,T,29,补充：替换new的异常处理,#include1、定义自己的异常处理类classNoMempublic:NoMem();,2、定义VC要求的异常函数intmy_new_handler(size_tx)throwNoMem();return0;,3、环境设置与恢复_PNHold_Handler=_set_new_handler(my_new_handler);使用：int*p=newint1000;_set_new_handler(old_Handler);,30,-操作1-创建空表（程序3-3）,templateLinearList:LinearList(intMaxListSize)MaxSize=MaxListSize;element=newTMaxSize;length=0;,31,-操作2-取元素（程序3-3）,templateboolLinearList:Find(intk,T,时间复杂度：(1),32,-操作3-查找（程序3-3）,templateintLinearList:Search(constT,时间复杂度：(n),33,（a1,ak-1,ak,ak+1,an）,（a1,ak-1,ak+1,an）,删除前,删除后,-操作4：删除,34,删除算法（程序3-4）,templateLinearList,时间复杂度：O(length-k),35,-删除算法分析,删除算法的时间代价主要耗费在移动数据元素上，移动数据元素的个数取决于删除元素的位置。,最好情形：删除表尾元素，不需要移动其它元素（移动个数为0）；,最坏情形：删除序号为1的元素，需要将表中其他的元素全部向前移（移动个数为n-1）；,删除时，数据平均移动次数AMN：,可供删除的位置有n个；假设删除第i个元素的概率为Pi，删除第i个元素，数据移动的次数为（n-i）个；不失一般性，等概率Pi=1/n,36,（a1,ak,ak+1,an）,（a1,ak,x,ak+1,an）,插入x,插入前,插入后,-操作5：插入,37,插入算法（程序3-5）,templateLinearList,时间复杂度：O(length-k),38,-插入算法分析,插入算法的时间代价主要耗费在移动数据元素上，移动数据元素的个数取决于插入元素的位置。,最好情形：在表尾追加一个新元素，不需要移动其它元素（移动个数为0）；,最坏情形：在序号为1的元素之前插入一个元素，需要将表中所有的元素全部向后移（移动个数为n）；,插入时，数据平均移动次数AMN：,可供插入的位置有n+1个；,假设在第i个元素之前插入一个元素的概率为Pi，在第i个元素之前插入，数据移动的次数为（n-i+1）个；不失一般性，等概率Pi=1/（n+1）,39,-操作6-输出（程序3-6）,templatevoidLinearList:Output(ostream,时间复杂度：(length),40,-操作7：顺序表的原地逆置,templateLinearListilink,p=p-link,p-link=q,p-link=q-link,p,q,q,57,-操作1：删除表中所有节点（程序3-9）,templateChain:Chain()ChainNode*next;while(first)next=first-link;deletefirst;first=next;,时间复杂度：(n),58,-操作2：确定链表长度（程序3-10）,templateintChain:Length()const/Returnthenumberofelementsinthechain.ChainNode*current=first;intlen=0;while(current)len+;current=current-link;returnlen;,时间复杂度：(n),59,-操作3：在链表中查找第k个元素（程序3-11）,templateboolChain:Find(intk,T/nokthelement,时间复杂度：(n),60,-操作4：在链表中搜索（程序3-12）,templateintChain:Search(constT,时间复杂度：(n),61,-操作5：输出链表（程序3-13）,templatevoidChain:Output(ostream,时间复杂度：(n),62,-操作6：删除节点：Delete(1,x),p=first;first=first-link;deletep;,p,删除表头节点,63,删除节点：Delete(3,x),a,b,d,e,NULL,first,c,第1步，到达要删除节点的前一个节点。,c,c,q,删除非表头节点,64,删除节点：Delete(3,x),第2步，保存指向待删节点的指针。,p=q-link;,q,a,b,c,d,e,NULL,first,p,65,删除节点：Delete(3,x),第3步，改变前节点的指针域，使其指向待删节点的后一节点。,q-link=p-link;deletep;,q,a,b,c,d,e,NULL,first,p,?,66,-删除算法（程序3-14）,templateChain/remove,67,-删除算法（续）（程序3-14）,else/useqtogettok-1stChainNode*q=first;for(intindex=1;indexlink;if(!q|!q-link)throwOutOfBounds();/nokthp=q-link;/kthq-link=p-link;/removefromchain/savekthelementandfreenodepx=p-data;deletep;return*this;,时间复杂度：(k),68,-操作4：插入节点：insert(0,x),第1步：产生一个节点，容纳x,y=newChainNode;y-data=x;,在表头节点前插入,69,插入节点：insert(0,x),第2步：修改头指针,y-link=first;first=y;,70,插入节点：insert(3,x),第3步：修改指针,y-link=p-link;p-link=y;,第1步：找到第3个节点,第2步：产生一个节点，容纳x,y=newChainNode;y-data=x;,71,-插入算法（程序3-15）,templateChain/nokth,72,-插入算法（续）（程序3-15）,/insertChainNode*y=newChainNode;y-data=x;if(k)/insertafterpy-link=p-link;p-link=y;else/insertasfirstelementy-link=first;first=y;return*this;,时间复杂度：(k),73,考虑：如何在(1)的时间完成插入,在ChainNode中增加一个私有变量ChainNode*last；用于跟踪链表的最后一