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