国二复习必备 数据结构

数据元素集合元素间关系集合数据结构（datastructure)—数据元素和数据元素关系的集合Data_Structure={D,R}数据的逻辑结构—抽象反映数据元素的逻辑关系从逻辑关系上描述数据，与数据的存储无关从具体问题抽象出来的数据模型；与数据元素本身的形式、内容无关；与数据元素的相对位置无关。数据结构（datastructure)—数据元素和数据元素关系的集合Data_Structure={D,R}数据的逻辑结构—抽象反映数据元素的逻辑关系数据逻辑结构分为：（集合）——数据元素间除“同属于一个集合”外，无其它关系线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树图状结构——多个对多个，如图数据的存储结构（物理结构）—数据的逻辑结构在计算机存储器中的实现存储结构分为：顺序存储结构—借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构—借助指示元素存储地址的指针表示数据元素间的逻辑关系时间复杂度：同一问题可用不同算法解决，各种算法中，语句执行次数越多，则该算法耗费的时间越长。一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)。T(n)=∑语句执行次数×该语句执行时间≈∑语句执行次数该方法可独立于机器的软件、硬件系统来分析算法在效率方面的优劣例x=0;y=0;for(k=0;k2*n;k++)x++;for(i=0;in;i++)for(j=0;jn;j++)y++;112nn2时间耗费T(n)=4+6n+2n22lim/2nTnn当n充分大时，T(n)与n2在数量级上相同，记T(n)=O(n2)2n+1n+1n*(n+1)执行次数时间复杂度：算法耗用时间相对问题规模n的增长率，一般指基本操作重复执行的次数的阶数大O表示法：T(n)=O(f(n))加法规则与乘法规则1、O(f(n))+O(g(n))=max{O(f(n)),O(g(n))}2、O(f(cn))=O(f(n)),c是正整数3、O(f(n))*O(g(n))=O(f(n)*g(n))T1(n)=O(1)T2(n)=O(n)T3(n)=O(n2)T(n)=T1(n)+T2(n)+T3(n)=O(max(1,2n,n2))=O(n2)例x=0;y=0;for(k=0;k2n;k++)x++;for(i=0;in;i++)for(j=0;jn;j++)y++;频度最大语句重复执行次数的阶数例：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];}33)(nOnTnnf时间复杂度：基本操作重复执行的次数的阶数（算法耗用时间的增长率）（渐近）空间复杂度：S(n)=O(f(n))辅助存储空间增长率或者说是算法所需存储空间的量度常用时间复杂度：O(1)-----常量型O(n)、O(n2)、O(n3)------多项式型O(log2n)、O(nlog2n)-------对数型O(2n)、O(en)------指数型O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(nk)O(2n)……线性结构特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中的每个数据元素均只有一个前驱除最后一个外，集合中的每个数据元素均只有一个后继§2.1线性表的逻辑结构定义：一个线性表是n个数据元素的有限序列12,,......,......inaaaa例英文字母表（A,B,C,…..Z)是一个线性表例学号姓名年龄001张三18002李四19………………数据元素特征：有限、序列、同构元素个数n—表长度，n=0空表1in时ai的直接前驱是ai-1，a1无直接前驱ai的直接后继是ai+1，an无直接后继元素同构，且不能出现缺项§2.2线性表的顺序存储结构顺序表：定义：用一组地址连续的存储单元存放一个线性表叫~元素地址计算方法：an……..ai……..a2a1LLOC(ai)=LOC(a1)+(i-1)*LLOC(ai+1)=LOC(ai)+L其中：L—一个元素占用的存储单元个数LOC(ai)—线性表第i个元素的地址实现：可用一维数组或动态分配顺序存储结构实现已知某元素序号i，可计算出该元素地址LOC(ai)进行操作，无需从表头查找特点：实现逻辑上相邻—物理地址相邻实现随机存取顺序存储结构的优缺点优点逻辑相邻，物理相邻可随机存取任一元素存储空间使用紧凑缺点插入、删除操作需要移动大量的元素§2.3线性表的链式存储结构特点：用一组任意的存储单元存储线性表的数据元素利用指针(链)实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外，还需存储其直接后继的地址结点数据域：元素本身信息指针域：指示直接后继的存储位置数据域指针域结点“指针”或“链”指示表中元素的逻辑关系例线性表(ZHAO,QIAN,SUN,LI)…71319内存31LI…………QIANSUNZHAOZHAOQIANSUNLI13197数据域指针域^例线性表(ZHAO,QIAN,SUN,LI)…71319内存31LI…………QIANSUNZHAOZHAOQIANSUNLI197数据域指针域^例线性表(ZHAO,QIAN,SUN,LI)…71319内存31LI…………QIANSUNZHAOZHAOQIANSUNLI7数据域指针域^例线性表(ZHAO,QIAN,SUN,LI)…71319内存31LI…………QIANSUNZHAOZHAOQIANSUNLI数据域指针域^例线性表(ZHAO,QIAN,SUN,LI)数据域指针域…71319内存31LI…………QIANSUNZHAOZHAOQIANSUNLI^31H头指针单链表特点它是一种动态结构，整个存储空间为多个链表共用不需预先分配空间指针占用额外存储空间不能随机存取，查找速度慢删除，插入等操作方便RailwaySwitchingNetwork栈和队列是两种特殊的线性表是操作受限的线性表，称限定性数据结构限定插入和删除只能在表的“端点”进行的线性表a1a2a3………….an入队出队frontrear队列Q=(a1,a2,……,an)ana1a2……......出栈进栈栈s=(a1,a2,…,an)§3.1栈（stack）栈的定义和特点定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈特点：先进后出（FILO）或后进先出（LIFO）ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)栈的存储结构顺序栈base—栈底指针，始终指向栈底的位置top—栈顶指针,指向实际栈顶后的空位置，初始指向栈底，即top=basetop123450入栈Atop出栈栈满BCDEF设栈容量为stacksize栈满—top-base=stacksizetoptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空top123450栈空basebasebasetop栈空—top=baseABCDE操作序列：出栈序列：①元素A入栈AA②元素B入栈BB③元素C入栈CC能否由入栈序列A、B、C、D、E,得到出栈序列CBDAE？DE操作序列：出栈序列：①元素A入栈A②元素B入栈B③元素C入栈④元素C出栈CC⑤元素B出栈B能否由入栈序列A、B、C、D、E,得到出栈序列CBDAE？DE操作序列：出栈序列：①元素A入栈A②元素B入栈③元素C入栈④元素C出栈C⑤元素B出栈B⑥元素D入栈DD⑦元素D出栈D⑧元素A出栈A能否由入栈序列A、B、C、D、E,得到出栈序列CBDAE？E操作序列：出栈序列：①元素A入栈②元素B入栈③元素C入栈④元素C出栈C⑤元素B出栈B⑥元素D入栈⑦元素D出栈D⑧元素A出栈A⑨元素E入栈EE⑩元素E出栈E能否由入栈序列A、B、C、D、E,得到出栈序列CBDAE？可以得到按1,2,3,4顺序进栈，有几种出栈序列？链栈栈顶^…...topdatalink栈底typedefstructSnode{SElemTypedata;//数据域structSnode*link;//指针域}LinkStack;链栈的操作是线性表的特例，比较易于实现链栈结点结构datalink队列的定义及特点定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表a1a2a3…………………….an入队出队frontrear队列Q=(a1,a2,……,an)队列的逻辑结构队尾(rear)——允许插入的一端队头(front)——允许删除的一端队列特点：先进先出(FIFO)…a1a2an^ai…a1a2…ai…an队头front队尾rear出队入队front队头队尾设队首、队尾指针front和rear,front指向头结点，rear指向队尾rear链队列——队列的链式存储结构^frontrearQ.rear123450Q.front入队J1溢出J2J3J4J5J6Q.rearQ.rearQ.rearQ.rearQ.rearQ.rear真队列的顺序存储结构SqQueueQ;#defineMAXQSIZE100//最大队列长度typedefstruct{QElemType*base;//存储空间基址intfront;//头指针，指向队头元素intrear;//尾指针，指向队尾元素的下一个位置}SqQueue;顺序队列存储结构初值：Q.front=Q.rear=0;队空：Q.front==Q.rear;入队：真溢出条件：Q.base[Q.rear++]=e;Q.front==0;Q.rear==MAXQSIZE;SqQueueQ;#defineMAXQSIZE100//最大队列长度typedefstruct{QElemType*base;//存储空间基址intfront;//头指针，指向队头元素intrear;//尾指针，指向队尾元素的下一个位置}SqQueue;顺序队列存储结构出队：假溢出条件：e=Q.base[Q.front++];123450Q.front出队J1J2J3J4J5J6Q.rearQ.frontQ.frontQ.front溢出假队列的顺序存储结构Q.front0;Q.rear==MAXQSIZE;方案一：队首固定，每次出队，剩余元素下移123450Q.frontJ1出队J1J2J3J4Q.rear真溢出条件：Q.front==0;Q.rear==MAXQSIZE;假溢出条件：Q.front0;Q.rear==MAXQSIZE;队列的顺序存储结构假溢出问题解决方案Q.rear123450Q.frontJ2出队J2J3J4Q.rearQ.rear缺点：浪费时间方案一：队首固定，每次出队，剩余元素下移队列的顺序存储结构假溢出问题解决方案真溢出条件：Q.front==0;Q.rear==MAXQSIZE;假溢出条件：Q.front0;Q.rear==MAXQSIZE;J4J5J6123450Q.frontQ.rear方案二：循环队列，把队列设想成环形，首尾相接,若Q.rear==MAXSIZE，则令Q.rear=0J4J5J6450123Q.rearQ.front实现：利用模运算队列的顺序存储结构假溢出问题解决方案真溢出条件：Q.front==0;Q.rear==MAXQSIZE;假溢出条件：Q.front0;Q.rear==MAXQSIZE;J4J5J6123450Q.frontQ.rear方案二：循环队列，把队列设想成环形，首尾相接，若Q.rear==MAXSIZE，则令Q.rear=0J4J5J6450