文档介绍：该【信息学奥赛数据结构公开课获奖课件赛课一等奖课件 】是由【书犹药也】上传分享，文档一共【29】页，该文档可以免费在线阅读，需要了解更多关于【信息学奥赛数据结构公开课获奖课件赛课一等奖课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数据构造
数据构造是计算机存储、组织数据的方式。
数据构造是指互相之间存在一种或多种特定关系
的数据元素的集合。
通俗解释：数据相称于书. 计算机相称于书架，寄存了诸多书，书架分为
诸多格子，书寄存在不一样格子（内存空间，对应一种地址），中。
为了更快的取到想要的书,要用特定的寄存方式—数据构造
线性表
线性表：n个数据元素的有序集合，“连成线的”是一种常用的数据构造。其中数据元素之间的关系一般是一对一的关系，即除了第一种和最终一种数据元素之外，其他数据元素都是首尾相接的
实际应用中常见的特殊线性表：栈、队列、字符串、一维数组
非线性表
非线性表：各个数据元素不再保持在一种线性序列中，每个数据元素也许与零个或者多种其他数据元素发生联络
重要代表：树、图构造、多维数组
链表
链是一种存储单元上非持续、非次序的存储构造，通过链表中的指针依次访问数据。
链表由一系列结点（链表中每一种元素称为结点）构成，数据元素可根据需要实时添加、动态生成。
由于非持续，链表无法随机读取，需要通过指针依次访问，查找数据时间长。
栈
栈是只能在某一端插入和删除的数据构造。
（想象用桶堆积物品，先堆进来的压在底下，随即一件件往上堆。取走时，只能从上面一件件取。堆和取都在顶部进行，底部一般是不动的。）
栈进行删除和插入的一端称栈顶，另一堆称栈底。插入一般称为进栈（PUSH），删除则称为退栈（POP）。
栈的特征是“后进先出”
栈
一种栈可以用定长为Ｎ的数组Ｓ来表达
用一种栈指针TOP指向栈顶。若TOP＝0，表达栈空，TOP=N时栈满。进栈时TOP加１。退栈时TOP减１。当TOP<0时为下溢。
练习
某个车站呈狭长形，宽度只能容下一辆车，并且只有一种出入口。已知某时刻该车站状态为空，从 这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的 次序为 1，2，3，4，5，6，7 ，则车辆出站的次序为（ C ）。
A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7
C. 1, 4, 3, 7, 6 D. 1, 4, 3, 7, 2
队列
跟栈相反，队列是限定只能在表的一端进行插入，在表的另一端进行删除的数据构造。队列的特征是“先进先出”
（就像排队买东西，排在前面的人买完东西后离开队伍（删除），而后来的人总是排在队伍未尾（插入））
一般把队列的删除和插入分别称为出队和入队。
容许删除的一端——队头(front)
容许插入的一端——队尾(rear)
a1 a2 a3…………………….an
入队
出队
队头front
Rear队尾
队列Q=(a1,a2,……,an)
队列
a1 a2 a3…………………….an
入队
出队
front
rear
队列Q=(a1,a2,……,an)
队列可以用数组Q[m+1]来存储，数组的上界ｍ即是队列所容许的最大容量。在队列的运算中需设两个指针：
head：队头指针，指向实际队头元素的前一种位置
tail：队尾指针，指向实际队尾元素所在的位置
树
一棵树是由n（n>0）个元素构成的有限集合，其中：
（1）每个元素称为结点
（2）有且仅有一种特定的结点，称为根结点或树根
（3）除根结点外，其他结点能提成m（m>=0）个互不相交的有限集合 T0,T1,T2,……Tm-1。其中的每个子集又都是一棵树，这些集合称为这棵树的子树。
2的子节点
5，6的父节点
根节点
2的兄弟