国二复习必备数据结构市公开课一等奖省赛课微课金奖课件.pptx

数据元素集合;数据结构（datastructure)—数据元素和数据元素关系集合Data_Structure={D,R};数据存放结构（物理结构）—数据逻辑结构在计算机存放器中实现;时间复杂度：

同一问题可用不一样算法处理，各种算法中，语句执行次数越多，则该算法花费时间越长。

一个算法中语句执行次数称为语句频度或时间频度，记为T(n)。

T(n)=∑语句执行次数×该语句执行时间

≈∑语句执行次数

该方法可独立于机器软件、硬件系统来分析算法在效率方面优劣;;时间复杂度：算法耗用时间相对问题规模n增加率，普通指基本操作重复执行次数阶数

大O表示法：T(n)=O(f(n));T1(n)=O(1);例：n×n矩阵相乘

for(i=1;i=n;i++)

for(j=1;j=n;j++)

{c[i][j]=0;

for(k=1;k=n;k++)

c[i][j]=c[i][j]+a[i][k]*b[k][j];

} ;时间复杂度：基本操作重复执行次数阶数（算法耗用时间增加率）

;线性结构特点：在数据元素非空有限集中

存在唯一一个被称作“第一个”数据元素

存在唯一一个被称作“最终一个”数据元素

除第一个外，集合中每个数据元素均只有一个前驱

除最终一个外，集合中每个数据元素均只有一个后继;2.1线性表逻辑结构

定义：一个线性表是n个数据元素有限序列;2.2线性表次序存放结构

次序表：

定义：用一组地址连续存放单元存放一个线性表叫~

元素地址计算方法：;次序存放结构优缺点

优点

逻辑相邻，物理相邻

可随机存取任一元素

存放空间使用紧凑

缺点

插入、删除操作需要移动大量元素;2.3线性表链式存放结构

特点：

用一组任意存放单元存放线性表数据元素

利用指针(链)实现了用不相邻存放单元存放逻辑上相邻元素

每个数据元素ai，除存放本身信息外，还需存放其直接后继地址

结点

数据域：元素本身信息

指针域：指示直接后继存放位置;例线性表(ZHAO,QIAN,SUN,LI);例线性表(ZHAO,QIAN,SUN,LI);例线性表(ZHAO,QIAN,SUN,LI);例线性表(ZHAO,QIAN,SUN,LI);例线性表(ZHAO,QIAN,SUN,LI);单链表特点

它是一个动态结构，整个存放空间为多个链表共用

不需预先分配空间

指针占用额外存放空间

不能随机存取，查找速度慢

删除，插入等操作方便;;栈和队列是两种特殊线性表

是操作受限线性表，称限定性数据结构

限定插入和删除只能在表“端点”进行线性表;

3.1栈（stack）

栈定义和特点

定义：限定仅在表尾进行插入或删除操作线性表，表尾—栈顶，表头—栈底，不含元素空表称空栈

特点：先进后出（FILO）或后进先出（LIFO）;栈存放结构

次序栈;ABCDE;DE;DE;E;链栈;队列定义及特点

定义：队列是限定只能在表一端进行插入，在表另一端进行删除线性表;…;Q.rear;SqQueueQ;;方案一：

队首固定，每次出队，剩下元素下移;;J4;J4;利用模运算实现循环队列;利用模运算实现循环队列;利用模运算实现循环队列;利用模运算实现循环队列;五子棋游戏;树是一类主要非线性数据结构，是以分支关系定义层次结构;A;结点(node)——表示树中元素，包含数据项及若干指向其子树分支

结点度(degree)——结点拥有子树数

叶子(leaf)——度为0结点

孩子(child)——结点子树根称为该结点孩子

双亲(parents)——孩子结点上层结点叫该结点~

弟兄(sibling)——同一双亲孩子

树度——一棵树中最大结点度数

结点层次(level)——从根结点算起，根为第一层，它孩子为第二层……

深度(depth)——树中结点最大层次数

森林(forest)——m(m?0)棵互不相交树集合;结点A度：

结点B度：

结点M度：;定义：二叉树是n(n?0)个结点有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树互不相交二叉树组成

特点

每个结点至多有二棵子树(即不存在度大于2结点)

二叉树子树有左、右之分，且其次序不能任意颠倒

基本形态;二叉树性质;证实：由性质1，可得深度为k二叉树最大结点数是;性质3：对任何一棵二叉树T，假如其叶子结点数为n0，度为2结点数为n2，则n0=n2+1;

满二叉树

定义：;

完全二叉树

定义：深度为k，有n个结点二叉树当且仅当其每一个结点都与深度为k满二叉树中编号从1至n结点一一对应时，称为~;