数据结构知识点整理

数据结构知识点整理

ID:20953919

大小:89.00 KB

页数:6页

时间:2018-10-18

数据结构知识点整理_第1页
数据结构知识点整理_第2页
数据结构知识点整理_第3页
数据结构知识点整理_第4页
数据结构知识点整理_第5页
资源描述:

《数据结构知识点整理》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、数据是信息的载体,是描述客观事物的数、字符、以及所有能输入到计算机中,被计算机程序识别和处理的符号(数值、字符等)的集合。数据元素(数据成员)是数据的基本单位。在不同的条件下,数据元素又可称为元素、结点、顶点、记录等数据对象具有相同性质的数据元素(数据成员)的集合数据结构由某一数据对象及该对象中所有数据成员之间的关系组成。记为Data_Structure={D,R}其中,D是某一数据对象,R是该对象中所有数据成员之间的关系的有限集合。数据类型是指一种类型,以及定义在这个值集合上的一组操作的总称。判断一个算法的优劣主要标准:正确性、可

2、使用性、可读性、效率、健壮性、简单性。算法效率的衡量方法:后期测试,事前估计算法分析是算法的渐进分析简称数据结构包括“逻辑结构”和“物理结构”两个方面(层次):逻辑结构是对数据成员之间的逻辑关系的描述,它可以用一个数据成员的集合和定义在此集合上的若干关系来表示物理结构是逻辑结构在计算机中的表示和实现,故又称“存储结构”线性表的定义:n(³0)个表项的有限序列L=(a1,a2,…,an)ai是表项,n是表长度。第一个表项是表头,最后一个是表尾。线性表的特点:表中元素的数据类型相同;线性表中,结点和结点间的关系是一对一的,有序表和无序表

3、线性表的存储方式。一,顺序存储方式,二,链表存储方式。顺序表的存储表示有2种方式:静态方式和动态方式。顺序表的定义是:把线性表中的所有表项按照其逻辑顺序依次存储到从计算机存储中指定存储位置开始的一块连续的存储空间中。顺序表的特点:用地址连续的一块存储空间顺序存放各表项,各表项的逻辑顺序与物理顺序一致,对各个表项可以顺序访问,也可以随机访问。单链表是一种最简单的链表表示,也叫线性链表,用她来表示线性表时,用指针表示结点间的逻辑关系。特点:是长度可以很方便地进行扩充。连续存储方式(顺序表)特点:存储利用率高,存取速度快缺点:插入、删除等

4、操作时需要移动大量数据:链式存储方式(链表)特点:适应表的动态增长和删除。缺点:需要额外的指针存储空间单链表的类定义:多个类表达一个概念(单链表)。分为:链表结点(ListNode)类,链表(List)类。循环链表的概念:是另一种形式的表示线性表的链表,它的结点结构与单链表相同,与单链表不同的是链表中表尾结点的LINK域中不是NULL,而是存放了一个指向链表开始结点的指针,这样,只要知道表中任何一个结点的地址,就能遍历表中其他任何一结点。双向链表的概念:在双向链表的没饿结点中应有两个链接指针作为它的数据成员:1LINK指示它的前驱结

5、点,RLINK指示它的后继结点,因此,双向链表的每个结点至少有3个域:1LINK(前驱指针)DADA(数据)RLINK(后继指针)。栈:定义为只允许在表的末端进行插入和删除的线性表。特点是:后进先出。递归的定义:若一个对象部分地包含它自己,或用它自己给自己定义,则称这个对象是递归的;若一个过程直接地或间接地调用自己,则称这个过程是递归的过程。以下三种情况常常用到递归方法一。定义是递归的二。数据结构是递归的三问题的解法是递归的。队列:队列是只允许在一端删除,在另一端插入的顺序表允许删除的一端叫做队头,允许插入的一端叫做队尾。特性:先进

6、先出。优先级队列:是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。多维数组是一维数组的推广。多维数组是一维数组的推广。多维数组的特点是每一个数据元素可以有多个直接前驱和多个直接后继。数组元素的下标一般具有固定的下界和上界,因此它比其他复杂的非线性结构简单。字符串是n(³0)个字符的有限序列,记作S:“c1c2c3…cn”其中,S是串名字c1c2c3…cn”是串值ci是串中字符n是串的长度,n=0称为空串。广义表是n(≥0)个表元素组成的有限序列,记作LS(a1,a2,a3,…,an),LS是表名,ai是表

7、元素,可以是表(称为子表),可以是数据元素(称为原子)。n为表的长度。n=0的广义表为空表。n>0时,表的第一个表元素称为广义表的表头(head),除此之外,其它表元素组成的表称为广义表的表尾(tail有根树:一棵有根树T,简称为树,它是n(n≥0)个结点的有限集合。当n=0时,T称为空树;否则,T是非空树,记作T={空集n=0{r,T1,T2….Tn},n>0r是一个特定的称为根(root)的结点,它只有直接后继,但没有直接前驱;根以外的其他结点划分为m(m³0)个互不相交的有限集合T1,T2,…,Tm,每个集合又是一棵树,并且称

8、之为根的子树。每棵子树的根结点有且仅有一个直接前驱,但可以有0个或多个直接后继二叉树的定义:一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。完全二叉树:─若设二

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。