资源描述：
《NOIP-初赛复习(数据结构)课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构数据结构基本结构:2.线性结构:数据之间存在一对一的关系;3.树:数据元素间存在一对多的关系;4.图:数据元素间存在多对多的关系;定义:相互之间存在一种或多种特定关系的数据元素的集合.1.集合:数据元素之间“同属于一个集合”;集合例题.设全集I={a,b,c,d,e,f,g,h}，集合A={a,b,c,d,e,f}，B={c,d,e}，C={a,d}，那么集合AnBn~C为（）。A.{c,e}B.{d,e}C.{e}D.{c,d,e}E.{d,f}n:交集,与的关系u:并集,或的关系~:非的关系=not~>n>u~
2、C={b,c,e,f,g,h}AnB={c,d,e}AnBn~C={c,e}A线性结构特点:由n（n≥0）个数据元素（结点）a1，a2，…，an组成的有限序列,(1).在这个序列中,存在唯一称做“第一个”的数据元素;(2).存在唯一的一个被称做“最后一个”的数据元素;(3).除第一个之外,集合中的每个数据元素均只有一个前驱;(4).除最后一个元素外,集合中的每个元素均只有一个后继.应用:线性表:栈和队列:数组:线性结构线性表线性表的顺序存储结构(1)方法:把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。a
3、1a2a3a4序列:a1,a2,a3,a4内存状态地址bb+lb+(2-1)*lb+(3-1)*lL:表示每个元素所占字节数目地址:元素所占的第一个单元的存储地址(2).特点:逻辑上相邻的结点其物理位置亦相邻结点ai的存储地址不失一般性，设线性表中所有结点的类型相同，则每个结点所占用存储空间大小亦相同。假设表中每个结点占用c个存储单元，其中第一个单元的存储地址则是该结点的存储地址，并设表中开始结点a1的存储地址（简称为基地址）是LOC（a1），那么结点ai的存储地址LOC（ai）可通过下式计算：LOC（ai）=LOC（a1
4、）+（i-1）*c 1≤i≤n练习:一个向量第一个元素的存储地址是100,每个元素的长度是2,则第5个元素的地址是()A)110B)108C)100D)109B线性表线性表的链式存储结构(1)方法:①用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）②链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）(2)结点结构datenextdata--存放结点
5、值的数据域next--存放结点的直接后继的地址（位置）的指针域（链域）序列:zhao,qian,sun,li,zhouzhaoqianzhou^sunli存储地址数据(date)指针(next)线性表1li序列:zhao,qian,sun,li,zhou,wu,zheng,wang437qian1313sun119wangnull25wu3731zhao737zheng1943zhou25头指针31内存中的存储方式线性表的链式存储结构循环链表（1）单循环链表——在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结
6、点即可。小结:(1)线性表的顺序存储与链式存储比较顺序:优–查找结点方便缺–进行插入和删除时,需要花费大量的时间来移动数据存储规模过大时难于预先估计空间,过大造成空间浪费,过小又会使数据溢出.链式:优–进行数据的删除和插入时只需要修改指针即可,非常方便.当存储规模较大时,动态分配不连续的内存空间,不会造成浪费.缺–查找某个结点需要从头指针起顺着链扫描才能取到.(2).链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。线性结构栈和队列1、栈的定义栈（Stack）是限制仅在表的一端进行
7、插入和删除运算的线性表。(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。(2)当表中没有元素时称为空栈。(3)栈为后进先出（LastInFirstOut）的线性表，简称为LIFO表。栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中"最新"的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。设栈S的初始状态为空，元素a,b,c,d,e,f,g依次入栈，以下出栈序列不可能出现的是 （）。 A.a,b,c,e,d,f,gB.b,c,a,f,e,g,dC.
8、a,e,d,c,b,f,g D.d,c,f,e,b,a,gE.g,e,f,d,c,b,a递归E栈和队列2、队列的定义队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表（1）允许删除的一端称为队头（Front）。（2）允许插入的一端称为队尾（Rear）。（3）当队列中没有元素时
