计算机二级数据结构与算法

1、第一页，共67页幻灯片第二页，共67页幻灯片第三页，共67页幻灯片第四页，共67页幻灯片第五页，共67页幻灯片第六页，共67页幻灯片第七页，共67页幻灯片第八页，共67页幻灯片nDxxtxpnA)()()()(max)(xtnWnDxX出现的概率算法在输入x时所执行的基本运算次数规模为n时，算法执行时所有可输入的集合第九页，共67页幻灯片第十页，共67页幻灯片第十一页，共67页幻灯片第十二页，共67页幻灯片第十三页，共67页幻灯片 学生基本情况学 号姓 名性 别出生年月.99070101李 军男8012.99070102王颜霞女812.99070103孙 涛男809.99070104单晓宏男8

2、13.第十四页，共67页幻灯片第十五页，共67页幻灯片 数据结构是一门研究数据结构是一门研究数据数据组织组织、存存储储和和运算运算的一般方法的学科。的一般方法的学科。1.2.2 基本概念和术语数据结构主要研究和讨论以下三个方面的问题：1.数据集合中各数据元素之间所固有的逻辑关系， 即数据的逻辑结构。2.在对数据进行处理时，各数据元素在计算机中的存储关系， 即数据的存储结构。3.对各种数据结构进行的运算。位置：位置：P6，重要。，重要。第十六页，共67页幻灯片能输入到计算机中能输入到计算机中并能被计算机程序处理的并能被计算机程序处理的符号的集合。符号的集合。整数整数(1,2)(1,2)、实数、实

3、数(1.1,1.2)(1.1,1.2)字符串字符串(Beijing)(Beijing)、图形、声音。图形、声音。 数据结构是一门研究数据结构是一门研究数据数据组织组织、存储存储和和运算运算的一般方法的学科。的一般方法的学科。第十七页，共67页幻灯片计算机管理图书问题计算机管理图书问题 在图书馆里有各种卡片：有按书名编排的、在图书馆里有各种卡片：有按书名编排的、有按作者编排的、有按分类编排有按作者编排的、有按分类编排如何将查询图书的这些信息存入计算机中如何将查询图书的这些信息存入计算机中既要考虑查询时间短，又要考虑节省空间既要考虑查询时间短，又要考虑节省空间 数据结构是一门研究数据结构是一门研究

4、数据数据组织组织、存储存储和和运算运算的一般方法的学科。的一般方法的学科。第十八页，共67页幻灯片最简单的办法之一是建立一张表，最简单的办法之一是建立一张表，每一本书的信息在表中占一行，如每一本书的信息在表中占一行，如 数据结构是一门研究数据结构是一门研究数据数据组织组织、存储存储和和运算运算的一般方法的学科。的一般方法的学科。第十九页，共67页幻灯片将各种逻辑结构的数据存放在将各种逻辑结构的数据存放在计算机存储空间中。计算机存储空间中。 目的不同，最佳的存储方方法就不同。目的不同，最佳的存储方方法就不同。 数据元素在数据元素在计算机中的表示计算机中的表示 数据结构是一门研究数据结构是一门研究

5、数据数据组织组织、存储存储和和运算运算的一般方法的学科。的一般方法的学科。第二十页，共67页幻灯片对数据结构中的节点进行对数据结构中的节点进行操作处理操作处理(插入、删除、修改、查找、排序插入、删除、修改、查找、排序) 数据结构是一门研究数据结构是一门研究数据数据组织组织、存储存储和和运算运算的一般方法的学科。的一般方法的学科。第二十一页，共67页幻灯片数据元素数据元素(Data Element)(Data Element) 现实世界中客观存在得一切个体或个体相关的操作现实世界中客观存在得一切个体或个体相关的操作都可以抽象为数据元素。都可以抽象为数据元素。 如：四季的名称：春、夏、秋、冬由季节

6、抽象而如：四季的名称：春、夏、秋、冬由季节抽象而来，可以作为季节的数据元素。来，可以作为季节的数据元素。 同理，父亲、儿子、女儿可以作为家庭成员的同理，父亲、儿子、女儿可以作为家庭成员的数据元素。数据元素。 简单的说，数据结构是指相互有关联的数据元简单的说，数据结构是指相互有关联的数据元素的集合。素的集合。第二十二页，共67页幻灯片数据元素数据元素(Data Element)(Data Element) 甚至客观存在的事件，如演出、借书、比赛等也可以抽甚至客观存在的事件，如演出、借书、比赛等也可以抽象为数据元素。象为数据元素。 在具有在具有相同特征相同特征的数据元素集合中，各个数据元素之间的数

7、据元素集合中，各个数据元素之间存在某种关系，这种关系反映了该集合中的数据元素所固存在某种关系，这种关系反映了该集合中的数据元素所固有的一种结构。在数据处理领域中，通常把数据元素之间有的一种结构。在数据处理领域中，通常把数据元素之间的这种固有的关系简单地用前后件关系来描述。的这种固有的关系简单地用前后件关系来描述。第二十三页，共67页幻灯片第二十四页，共67页幻灯片数据逻辑结构可表示为：数据逻辑结构可表示为：B=（D，R）B B表示数据结构表示数据结构D D表示数据元素的集合表示数据元素的集合R R表示数据元素间前后件关系表示数据元素间前后件关系为反映前后件关系，通常用二元组为反映前后件关系，通

8、常用二元组(a,b)来表示来表示，它表示，它表示a是是b的前件。的前件。第二十五页，共67页幻灯片B=(D,R)D=父亲，儿子，女儿R=(父亲，儿子)，(父亲，女儿)B=(D,R)D=春，夏，秋，冬R=(春，夏)，(夏，秋)，(秋，冬)第二十六页，共67页幻灯片春夏秋冬一年四季数据结构的图形表示ABCD第二十七页，共67页幻灯片第二十八页，共67页幻灯片字节第二十九页，共67页幻灯片第三十页，共67页幻灯片第三十一页，共67页幻灯片线性结构线性结构 A , B , C , ，X ,Y , Z学 生 成 绩 表86胡孝臣986110395刘忠赏9861107100张卓9861109成绩姓名学号线

9、性表线性表结点间是以线性关系联结结点间是以线性关系联结ABC第三十二页，共67页幻灯片非线性结构非线性结构 如果数据结构不满足线性结构的条件，则称如果数据结构不满足线性结构的条件，则称之为非之为非线性结构。线性结构。此外，在线线结构中插入或删除一个此外，在线线结构中插入或删除一个 结点，还结点，还应是线线结构，否则此结构非线线应是线线结构，否则此结构非线线ABCD第三十三页，共67页幻灯片树形结构树形结构全校学生档案管理的组织方式全校学生档案管理的组织方式计算机程序管理系统也是典型的树形结构计算机程序管理系统也是典型的树形结构第三十四页，共67页幻灯片树形结构 结点间具有分层次的连接关系HBC

10、DEFGA第三十五页，共67页幻灯片第三十六页，共67页幻灯片第三十七页，共67页幻灯片在计算机中存放线性表，采用顺序存储是一种简单方便的方法。 第三十八页，共67页幻灯片元素元素a an n.元素元素a ai i.元素元素a a2 2元素元素a a1 1bADR(a1) +k存储地址存储地址内存状态内存状态顺序存储结构示意图顺序存储结构示意图(顺序表顺序表)：首地址首地址ADR(aADR(a1 1) )每个元素所占用每个元素所占用的存储单元个数的存储单元个数ADR(a1) + (i-1)* kADR(a1) + (n-1)* kADR(ai) =ADR(a1) + (i-1)* k第三十九页

11、，共67页幻灯片n-1线性表的插入和删除运算示意图线性表的插入和删除运算示意图ai-1.a2a1an ai+1ai x ai-1. a2 a1 ai ai+1 alength an ai+1 ai x删除删除运算运算插入插入运算运算第四十页，共67页幻灯片ajaj 1=j=i-1b j=iaj-1 i+1=j=n+1长度增加为：n+1ajaj 1=j=i-1aj +1 i=j=n-1长度减少为：n-1第四十一页，共67页幻灯片第四十二页，共67页幻灯片1.4.1.11.4.1.1栈的定义栈的定义栈栈：限定只能在表的一端进行插入和删除的特殊的线性表限定只能在表的一端进行插入和删除的特殊的线性表,

12、 ,此种结构称为此种结构称为先进后出先进后出(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)：允许插入和删除的一端；：允许插入和删除的一端；栈底（栈底（bottom):bottom):不允许插入和删除的一端。不允许插入和删除的一端。约定用指针约定用指针top始终指向栈顶的位置，始终指向栈顶的位置，用指针用指针bottom指向栈底。指向栈底。

13、 a1 a2 . ai进栈进栈出栈出栈topbottomn1第四十三页，共67页幻灯片1.4.2 栈的顺序存储结构及其基本运算栈的顺序存储结构及其基本运算 a1 a2 top 用顺序存储结构表示的栈用顺序存储结构表示的栈。 顺序栈用一组连续的存储单元存放自栈底到栈顶的顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素，一般用一维数组表示，设置一个简单变量数据元素，一般用一维数组表示，设置一个简单变量top指示栈顶位置，称为指示栈顶位置，称为栈顶指针栈顶指针，它始终指向待插入它始终指向待插入元素的位置。元素的位置。基本运算：压（进）栈：PUSH出栈：POP读栈顶元素第四十四页，共67页幻灯片进

14、栈示例进栈示例 栈满：栈顶指针指向存储空间的最后一个位置第四十五页，共67页幻灯片退栈示例退栈示例第四十六页，共67页幻灯片1.4.1.2 队列队列的定义的定义定义：定义：一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表 。 a1 , a2 , a3 , a4 , an-1 , an 队 列 示 意 图队头队尾队列只允许在队尾插入，在对头删除。队列只允许在队尾插入，在对头删除。队头指针：队头指针：front：指向排头元素的前一个位置：指向排头元素的前一个位置队尾指针：队尾指针：rear：指向队尾元素：指向队尾元素此种结构称为先进先出（先进先出（FIFO）或后进后出）

15、或后进后出(LILO)。第四十七页，共67页幻灯片当有新元素入队时，尾指针加当有新元素入队时，尾指针加1，当有元素出队时，头指针加当有元素出队时，头指针加1。故在非空队列中，故在非空队列中，头指针头指针始终指向始终指向队头元素前一个位置队头元素前一个位置，而而尾指针尾指针始终指向始终指向队尾元素的位置队尾元素的位置第四十八页，共67页幻灯片n n 队满：队尾指针指向存储空间的最后一个位置第四十九页，共67页幻灯片第五十页，共67页幻灯片Q(1:m)21mrear front 第五十一页，共67页幻灯片Q(1:6）rear front AECDBF第五十二页，共67页幻灯片s1 表示队列非空0

16、表示队列空P19-20详细说明第五十三页，共67页幻灯片线性链表节点第五十四页，共67页幻灯片1.5.1 线性表的链式存储结构线性表的链式存储结构 将线性表的元素放到一个具有头指针的链表中，链将线性表的元素放到一个具有头指针的链表中，链表中每个结点包含数据域和指针域。表中每个结点包含数据域和指针域。 数据域存放数据，指针域存放数据域存放数据，指针域存放后继结点后继结点的地址，最的地址，最后一个结点的指针域为空。逻辑上相邻的数据元素在内后一个结点的指针域为空。逻辑上相邻的数据元素在内存中的物理存储空间不一定相邻。存中的物理存储空间不一定相邻。第五十五页，共67页幻灯片上图的线性表为上图的线性表为

17、ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG第五十六页，共67页幻灯片线性链表表示法线性链表表示法:0第五十七页，共67页幻灯片双向链表双向链表 在每个结点中设置两个指针，一个指向后继在每个结点中设置两个指针，一个指向后继，一个指向前驱。可直接确定一个结点的前驱和，一个指向前驱。可直接确定一个结点的前驱和后继结点。可提高效率。后继结点。可提高效率。datanextbefore第五十八页，共67页幻灯片链式存储结构的特点链式存储结构的特点 插入、删除灵活方便，不需要移动结点，只要改变结点插入、删除灵活方便，不需要移动结点，只要改变结点中指针域的值即可。中指针域的值即可。

18、 适合于线性表是动态变化的适合于线性表是动态变化的, ,不进行频繁查找操作、但经常不进行频繁查找操作、但经常进行插入删除时使用。进行插入删除时使用。 链表的查找只能从头指针开始顺序查找。链表的查找只能从头指针开始顺序查找。 第五十九页，共67页幻灯片babaxHH线性链表的插入运算线性链表的插入运算S在在H所指向的结点之后插入新的结点所指向的结点之后插入新的结点1.5.2线性链表的运算线性链表的运算第六十页，共67页幻灯片baxHbaH线性链表的删除运算线性链表的删除运算S在在H所指向的结点之后删除新的结点所指向的结点之后删除新的结点1.5.2线性链表的运算线性链表的运算baxHS第六十一页，共67页幻灯片0第六十二页，共67页幻灯片0第六十三页，共67页幻灯片1.5.3 循环链表循环链表: 首尾相接的链表