数据结构复习提纲

数据结构复习提纲数据结构复习提纲数据结构定义——是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。数据结构中基本概念和术语 ●数据(data)—所有能输入到计算机中去的描述客观事物的符号 ●数据元素(data element)—数据的基本单位,也称节点(node)或记录(record) ●数据项(data item)—有独立含义的数据最小单位,也称域(field) ●数据结构(data structure)—数据元素和数据元素关系的集合数据结构研究的三个方面:数据的逻辑结构...

数据结构复习提纲数据结构定义——是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。数据结构中基本概念和术语 ●数据(data)—所有能输入到计算机中去的描述客观事物的符号 ●数据元素(data element)—数据的基本单位,也称节点(node)或记录(record) ●数据项(data item)—有独立含义的数据最小单位,也称域(field) ●数据结构(data structure)—数据元素和数据元素关系的集合数据结构研究的三个方面:数据的逻辑结构(线性结构及非线性结构)、数据的存储结构(顺序存储及链式存储)、数据的运算(检索、排序、插入、删除、修改等) 算法的概念(Algorithm)—解决某一特定问题的具体步骤的一种描述,是指令的有限序列。算法的五个重要特性:有穷性、确定性、可行性、输入、输出算法效率的度量:时间复杂度与空间复杂度线性表 ●线性表的类型定义:一个线性表是n个数据元素的有限序列 ●线性表的顺序表示 ★采用顺序存储结构存储的线性表称为顺序表 ★优点逻辑相邻,物理相邻可随机存取任一元素存储空间使用紧凑 ★缺点插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配,利用不充分表容量难以扩充 ●线性表的链式表示 ★线性链表(单链表) ★它是一种动态结构,整个存储空间为多个链表共用 ★不需预先分配空间 ★指针占用额外存储空间 ★不能随机存取,查找速度慢;插入、删除操作方便栈和队列 ●栈和队列是两种特殊的线性表,是操作受限的线性表,称限定性DS。 ●栈的定义和特点定义:限定仅在表尾进行插入或删除操作的线性表,表尾—栈顶,表头—栈底,不含元素的空表称空栈。特点:先进后出(FILO)或后进先出(LIFO)的线性表采用顺序存储结构存储的栈称为顺序栈采用链式存储结构存储的栈称为链栈栈的应用:表达式求值、函数的调用 ●队列的定义及特点定义:队列是限定只能在表的一端进行插入,而在表的另一端进行删除的线性表?队尾(rear)——允许插入的一端 ?队头(front)——允许删除的一端队列特点:先进先出(FIFO) 的线性表 ●循环队列——队列的顺序表示和实现实现:利用“模”运算 ?入队:Q.base[Q.rear] =x; Q.rear =(Q.rear+1)%M; ?出队:x =Q.base[Q.front]; Q.front =(Q.front+1)%M; 队满、队空判定条件 ?队空:Q.front = = Q.rear ?队满:(Q.rear+1)%M = = Q.front ●链队列——队列的链式表示和实现数组数组的定义数组的顺序表示:以行序为主序及其以列序为主序的表示矩阵的压缩存储:针对特殊矩阵(如对称矩阵、对角矩阵)的存储稀疏矩阵的存储:三元组表示法广义表广义表的定义、求广义表的长度n、求广义表的深度k 求广义表的表头操作:GetHead(广义表)、求广义表的表尾操作:GetTail(广义表) 一个广义表的表头总是一个广义表。(错误) 一个广义表的表尾总是一个广义表。(正确) 树的定义和基本术语二叉树二叉树的定义二叉树5个性质的应用几种特殊形式的二叉树:满二叉树、完全二叉树二叉树的存储结构:顺序存储结构及二叉链表存储结构二叉树的遍历:前序遍历、中序遍历、后序遍历、层次遍历树、森林与二叉树之间的相互转换树的遍历:先根次序遍历、后根次序遍历、按层次遍历森林的遍历:先序遍历、中序遍历赫夫曼树(也称赫夫曼树或最优二叉树)的定义、特点及其应用图图的定义和术语图的存储表示:邻接矩阵(无向图与有向图)、邻接表(无向图与有向图)、逆邻接表(有向图) 图的遍历方法:深度优先遍历(DFS)和广度优先遍历(BFS);深度优先生成树与广度优先生成树最小生成树(无向图的应用)的构造方法:普里姆算法和克鲁斯卡尔算法拓扑排序(有向图AOV网的应用):一个AOV网的拓扑序列不是唯一的最短路径(有向图AOE网的应用):迪杰斯特拉算法(求某个源点到其余各顶点的最短路径)及弗洛伊德算法(求每一对顶点之间的最短路径) 查找静态查找表:顺序表的查找(顺序查找)及有序表的查找(折半查找)、索引顺序表的查找(分块查找) 动态查找表:二叉排序树及平衡二叉树哈希查找:哈希函数的常用构造方法及哈希冲突的常用解决方法,ASL的计算排序按待排序记录所在位置进行分类内部排序:待排序记录存放在内存中进行的排序过程外部排序:排序过程中尚需对外存进行访问的排序过程按排序依据的不同原则对内部排序进行分类插入排序:直接插入排序(稳定)、折半插入排序(稳定)、希尔排序(缩小增量排序,不稳定) 交换排序:冒泡排序(稳定)、快速排序(霍尔排序,不稳定) 选择排序:简单选择排序(不稳定)、堆排序(不稳定) 归并排序:2-路归并排序(不稳定) 基数排序:

                    本文档为【数据结构复习提纲】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

数据结构复习提纲

你可能还喜欢