计算机二级数据结构及算法课件.ppt

1、计算机教研室nDxxtxpnA)()()()(max)(xtnWnDxX出现的概率算法在输入x时所执行的基本运算次数规模为n时，算法执行时所有可输入的集合 学生基本情况学 号姓 名性 别出生年月.99070101李 军男8012.99070102王颜霞女812.99070103孙 涛男809.99070104单晓宏男813. 数据结构是一门研究数据结构是一门研究数据数据组织组织、存储存储和和运算运算的一般方法的学科。的一般方法的学科。1.2.2 基本概念和术语数据结构主要研究和讨论以下三个方面的问题：1.数据集合中各数据元素之间所固有的逻辑关系， 即数据的逻辑结构。2.在对数据进行处理时，各数

2、据元素在计算机中的存储关系， 即数据的存储结构。3.对各种数据结构进行的运算。位置：位置：P6，重要。，重要。能输入到计算机中能输入到计算机中并能被计算机程序处理的并能被计算机程序处理的符号的集合。符号的集合。整数整数(1,2)(1,2)、实数、实数(1.1,1.2)(1.1,1.2)字符串字符串(Beijing)(Beijing)、图形、声音。图形、声音。 数据结构是一门研究数据结构是一门研究数据数据组织组织、存储存储和和运算运算的一般方法的学科。的一般方法的学科。计算机管理图书问题计算机管理图书问题 在图书馆里有各种卡片：有按书名编排的、在图书馆里有各种卡片：有按书名编排的、有按作者编排的

3、、有按分类编排有按作者编排的、有按分类编排如何将查询图书的这些信息存入计算机中如何将查询图书的这些信息存入计算机中既要考虑查询时间短，又要考虑节省空间既要考虑查询时间短，又要考虑节省空间 数据结构是一门研究数据结构是一门研究数据数据组织组织、存储存储和和运算运算的一般方法的学科。的一般方法的学科。最简单的办法之一是建立一张表，最简单的办法之一是建立一张表，每一本书的信息在表中占一行，如每一本书的信息在表中占一行，如 数据结构是一门研究数据结构是一门研究数据数据组织组织、存储存储和和运算运算的一般方法的学科。的一般方法的学科。将各种逻辑结构的数据存放在将各种逻辑结构的数据存放在计算机存储空间中。

4、计算机存储空间中。 目的不同，最佳的存储方方法就不同。目的不同，最佳的存储方方法就不同。 数据元素在数据元素在计算机中的表示计算机中的表示 数据结构是一门研究数据结构是一门研究数据数据组织组织、存储存储和和运算运算的一般方法的学科。的一般方法的学科。对数据结构中的节点进行对数据结构中的节点进行操作处理操作处理(插入、删除、修改、查找、排序插入、删除、修改、查找、排序) 数据结构是一门研究数据结构是一门研究数据数据组织组织、存储存储和和运算运算的一般方法的学科。的一般方法的学科。数据元素数据元素(Data Element)(Data Element) 现实世界中客观存在得一切个体或个体相关现实世

5、界中客观存在得一切个体或个体相关的操作都可以抽象为数据元素。的操作都可以抽象为数据元素。 如：四季的名称：春、夏、秋、冬由季节抽如：四季的名称：春、夏、秋、冬由季节抽象而来，可以作为季节的数据元素。象而来，可以作为季节的数据元素。 同理，父亲、儿子、女儿可以作为家庭成员同理，父亲、儿子、女儿可以作为家庭成员的数据元素。的数据元素。 简单的说，数据结构是指相互有关联的数据简单的说，数据结构是指相互有关联的数据元素的集合。元素的集合。数据元素数据元素(Data Element)(Data Element) 甚至客观存在的事件，如演出、借书、比赛等也可甚至客观存在的事件，如演出、借书、比赛等也可以抽

6、象为数据元素。以抽象为数据元素。 在具有在具有相同特征相同特征的数据元素集合中，各个数据元素的数据元素集合中，各个数据元素之间存在某种关系，这种关系反映了该集合中的数据元之间存在某种关系，这种关系反映了该集合中的数据元素所固有的一种结构。在数据处理领域中，通常把数据素所固有的一种结构。在数据处理领域中，通常把数据元素之间的这种固有的关系简单地用前后件关系来描述。元素之间的这种固有的关系简单地用前后件关系来描述。数据逻辑结构可表示为：数据逻辑结构可表示为：B=（D，R）B B表示数据结构表示数据结构D D表示数据元素的集合表示数据元素的集合R R表示数据元素间前后件关系表示数据元素间前后件关系为

7、反映前后件关系，通常用二元组为反映前后件关系，通常用二元组(a,b)来来表示，它表示表示，它表示a是是b的前件。的前件。B=(D,R)D=父亲，儿子，女儿R=(父亲，儿子)，(父亲，女儿)B=(D,R)D=春，夏，秋，冬R=(春，夏)，(夏，秋)，(秋，冬)春夏秋冬一年四季数据结构的图形表示ABCD字节线性结构线性结构 A , B , C , ，X ,Y , Z学 生 成 绩 表86胡孝臣986110395刘忠赏9861107100张卓9861109成绩姓名学号线性表线性表结点间是以线性关系联结结点间是以线性关系联结ABC非线性结构非线性结构 如果数据结构不满足线性结构的条件，如果数据结构不满

8、足线性结构的条件，则称之为非则称之为非线性结构。线性结构。此外，在线线结构中插入或删除一个此外，在线线结构中插入或删除一个 结点，结点，还应是线线结构，否则此结构非线线还应是线线结构，否则此结构非线线ABCD树形结构树形结构全校学生档案管理的组织方式全校学生档案管理的组织方式计算机程序管理系统也是典型的树形结构计算机程序管理系统也是典型的树形结构树形结构 结点间具有分层次的连接关系HBCDEFGA在计算机中存放线性表，采用顺序存储是一种简单方便的方法。 元素元素a an n.元素元素a ai i.元素元素a a2 2元素元素a a1 1bADR(a1) +k存储地址存储地址内存状态内存状态顺序

9、存储结构示意图顺序存储结构示意图(顺序表顺序表)：首地址首地址ADR(aADR(a1 1) )每个元素所占用每个元素所占用的存储单元个数的存储单元个数ADR(a1) + (i-1)* kADR(a1) + (n-1)* kADR(ai) =ADR(a1) + (i-1)* kn-1线性表的插入和删除运算示意图线性表的插入和删除运算示意图ai-1.a2a1an ai+1ai x ai-1. a2 a1 ai ai+1 alength an ai+1 ai x删删除除运运算算插插入入运运算算ajaj 1=j=i-1b j=iaj-1 i+1=j=n+1长度增加为：n+1ajaj 1=j=i-1aj

10、 +1 i=j=n-1长度减少为：n-11.4.1.11.4.1.1栈的定义栈的定义栈栈：限定只能在表的一端进行插入和删除的特殊的线性表限定只能在表的一端进行插入和删除的特殊的线性表, ,此种结此种结构称为构称为先进后出先进后出(FILO)(FILO)或或后进先出后进先出(LIFO)(LIFO)设栈设栈s=s=（a a1 1，a a2 2，. . . ,a. . . ,ai i，. . . . . . ，a an n），其中其中a a1 1是栈底元素，是栈底元素， a an n是栈顶元素。是栈顶元素。栈顶（栈顶（top)top)：允许插入和删除的一端；：允许插入和删除的一端；栈底（栈底（bot

11、tom):bottom):不允许插入和删除的一端。不允许插入和删除的一端。约定用指针约定用指针top始终指向栈顶的位置，始终指向栈顶的位置，用指针用指针bottom指向栈底。指向栈底。 a1 a2 . ai进栈进栈出栈出栈topbottomn11.4.2 栈的顺序存储结构及其基本运算栈的顺序存储结构及其基本运算 a1 a2 top 用顺序存储结构表示的栈用顺序存储结构表示的栈。 顺序栈用一组连续的存储单元存放自栈底到栈顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素，一般用一维数组表示，设置一个顶的数据元素，一般用一维数组表示，设置一个简单变量简单变量top指示栈顶位置，称为指示栈顶位置，

12、称为栈顶指针栈顶指针，它它始终指向待插入元素的位置。始终指向待插入元素的位置。基本运算：压（进）栈：PUSH出栈：POP读栈顶元素进栈示例进栈示例 栈满：栈顶指针指向存储空间的最后一个位置退栈示例退栈示例1.4.1.2 队列队列的定义的定义定义：定义：一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表 。 a1 , a2 , a3 , a4 , an-1 , an 队 列 示 意 图队头队尾队列只允许在队尾插入，在对头删除。队列只允许在队尾插入，在对头删除。队头指针：队头指针：front：指向排头元素的前一个位置：指向排头元素的前一个位置队尾指针：队尾指针：rear：

13、指向队尾元素：指向队尾元素此种结构称为先进先出（先进先出（FIFO）或后进后出）或后进后出(LILO)。当有新元素入队时，尾指针加当有新元素入队时，尾指针加1，当有元素出队时，头指针加当有元素出队时，头指针加1。故在非空队列中，故在非空队列中，头指针头指针始终指向始终指向队头元素前一个位置队头元素前一个位置，而而尾指针尾指针始终指向始终指向队尾元素的位置队尾元素的位置n n 队满：队尾指针指向存储空间的最后一个位置Q(1:m)21mrear front Q(1:6）rear front AECDBFs1 表示队列非空0 表示队列空P19-20详细说明线性链表节点1.5.1 线性表的链式存储结构

14、线性表的链式存储结构 将线性表的元素放到一个具有头指针的链表中，将线性表的元素放到一个具有头指针的链表中，链表中每个结点包含数据域和指针域。链表中每个结点包含数据域和指针域。 数据域存放数据，指针域存放数据域存放数据，指针域存放后继结点后继结点的地址，的地址，最后一个结点的指针域为空。逻辑上相邻的数据元素最后一个结点的指针域为空。逻辑上相邻的数据元素在内存中的物理存储空间不一定相邻。在内存中的物理存储空间不一定相邻。上图的线性表为上图的线性表为ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG线性链表表示法线性链表表示法:0双向链表双向链表 在每个结点中设置两个指针，一个指

15、向在每个结点中设置两个指针，一个指向后继，一个指向前驱。可直接确定一个结点的后继，一个指向前驱。可直接确定一个结点的前驱和后继结点。可提高效率。前驱和后继结点。可提高效率。datanextbefore链式存储结构的特点链式存储结构的特点 插入、删除灵活方便，不需要移动结点，只要改变结插入、删除灵活方便，不需要移动结点，只要改变结点中指针域的值即可。点中指针域的值即可。 适合于线性表是动态变化的适合于线性表是动态变化的, ,不进行频繁查找操作、不进行频繁查找操作、但经常进行插入删除时使用。但经常进行插入删除时使用。 链表的查找只能从头指针开始顺序查找。链表的查找只能从头指针开始顺序查找。 bab

16、axHH线性链表的插入运算线性链表的插入运算S在在H所指向的结点之后插入新的结点所指向的结点之后插入新的结点1.5.2线性链表的运算线性链表的运算baxHbaH线性链表的删除运算线性链表的删除运算S在在H所指向的结点之后删除新的结点所指向的结点之后删除新的结点1.5.2线性链表的运算线性链表的运算baxHS001.5.3 循环链表循环链表: 首尾相接的链表。首尾相接的链表。 将最后一个结点的空指针改为指向头结点，从任一结点将最后一个结点的空指针改为指向头结点，从任一结点出发均可找到其它结点。出发均可找到其它结点。L.带头结点的线性链表带头结点的线性链表L.循环线性链表循环线性链表元素n.元素i

17、.元素2元素1存储内容缺点：缺点：1.作插入或删除操作时，需移动大量元素。作插入或删除操作时，需移动大量元素。2.长度变化较大时，需按最大空间分配。长度变化较大时，需按最大空间分配。3.表的容量难以扩充。表的容量难以扩充。优点：优点：1.结构简单，节省存储空间。结构简单，节省存储空间。2.可随机定位其中的元素。可随机定位其中的元素。线性表顺序存储线性表顺序存储1536元素21400元素11346元素3 0元素41345h 线性表链式存储 1.缺点：比顺序存储结构的存储密度小缺点：比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成每个节点都由数据域和指针域组成)。 定位时必须按顺序进行定位时必须按顺序进行2.优点：逻辑上相邻的节点物理上不必相邻。优点：逻辑上相邻的节点物理上不必相邻。 插入、删除灵活插入、删除灵活 (不必移动节点，只要改变节点中的指针不必移动节点，只要改变节点中的指针)。链接存储结构特点：链接存储结构特点：