数据结构复习资料只是分享.ppt

《数据结构复习资料只是分享.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构复习资料1.数据结构的定义数据→数据元素→数据项数据结构是指数据以及相互之间的联系（或关系）。包括：（1）数据的逻辑结构。（2）数据的存储结构（物理结构）。（3）施加在该数据上的运算。概述数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它是依赖于计算机语言的。数据的运算是定义在数据的逻辑结构上的，每种逻辑结构都有一组相应的运算。但运算的实现与数据的存储结构有关。程序＝数据结构＋算法概述（1）线性结构（2）树形结构（3）图形结构概述逻辑结构主要有三大类：存储

2、结构分为如下四种：（1）顺序存储方法（2）链式存储方法（3）索引存储方法（4）散列存储方法概述2.算法算法是对特定问题求解步骤的一种描述，它是指令的有限序列。概述算法的五个重要的特性：（1）有穷性（2）确定性（3）可行性（4）有输入（5）有输出概述算法的时间复杂度：是指其基本运算在算法中重复执行的次数。算法中基本运算次数T(n)是问题规模n的某个函数f(n)，记作：T(n)=O(f(n))记号“O”读作“大O”，它表示随问题规模n的增大算法执行时间的增长率和f(n)的增长率相同。概述例分析以下程序段的时间复杂度。i=1;while(i<=n)i=i

3、*2;解：上述算法中基本操作是语句i=i*2，设其频度为T(n)，则有：2T(n)≤n即T(n)≤log2n=O(log2n)。所以，该程序段的时间复杂度为O(log2n)。算法空间复杂度：是对一个算法在运行过程中临时占用的存储空间大小的量度。对于空间复杂度为O(1)的算法称为原地工作或就地工作算法。概述■递归定义3.算法设计方法：递归在定义一个算法时出现调用本算法的成分，称之为递归。概述■递归模型由递归出口和递归体组成例如，求二叉树所有结点个数：f(b)=0b=NULLf(b)=f(b->lchild)+f(b->rchild)+1b≠NULL概

4、述■递归算法设计①对原问题f(s)进行分析，假设出合理的“较小问题”f(s');②假设f(s')是可解的，在此基础上确定f(s)的解，即给出f(s)与f(s')之间的关系；③确定一个特定情况（如f(1)或f(0)）的解，由此作为递归出口.概述bb->rchildb->lchild①假设出合理的“较小问题”：假设左右子树的结点个数可求②求出f(s)与f(s‘)之间的关系：f(b)=f(b->lchild)+f(b->rchild)+1③确定递归出口：f(NULL)=0概述intf(BTNode*b){if(b==NULL)return(0);else

5、return(f(b->lchild)+f(b->rchild)+1);}求解算法：概述例设计求f(n)=1+2+...+n的递归算法解：f(n)为前n项之和，则f(n-1)=1+2+...+(n-1)假设f(n-1)可求，则f(n)=f(n-1)+n，所以：f(n)=1当n=1f(n)=f(n-1)+n当n>1对应的递归算法如下：intf(intn){if(n==1)return(1);elsereturn(f(n-1)+n));}1.一般线性表线性表：具有相同特性的数据元素的一个有限序列。不是集合。模块1：线性结构逻辑结构（1）顺序表typed

6、efstruct{ElemTypeelem[MaxSize];/*存放顺序表元素*/intlength;/*存放顺序表的长度*/}SqList;存储结构之一模块1：线性结构顺序表基本运算的实现插入数据元素算法：元素移动的次数不仅与表长n有关；插入一个元素时所需移动元素的平均次数n／2。平均时间复杂度为O(n)。模块1：线性结构删除数据元素算法:元素移动的次数也与表长n有关。删除一个元素时所需移动元素的平均次数为(n-1)/2。删除算法的平均时间复杂度为O(n)。模块1：线性结构（2）链表定义单链表结点类型:typedefstructLNode{El

7、emTypedata;structLNode*next;/*指向后继结点*/}LinkList;存储结构之二模块1：线性结构定义双链表结点类型:typedefstructDNode{ElemTypedata;structDNode*prior;/*指向前驱结点*/structDNode*next;/*指向后继结点*/}DLinkList;模块1：线性结构■单链表基本运算的实现重点：（1）头插法建表和尾插法建表算法，它是很多算法设计的基础；（2）查找、插入和删除操作。模块1：线性结构头插法建表该方法从一个空表开始,读取字符数组a中的字符,生成新结点

8、,将读取的数据存放到新结点的数据域中,然后将新结点插入到当前链表的表头上,直到结束为止。采用头插法建表的算法如下:模块1：