数据结构复习资料.docx
- 文档编号:18508770
- 上传时间:2023-08-19
- 格式:DOCX
- 页数:16
- 大小:404.90KB
数据结构复习资料.docx
《数据结构复习资料.docx》由会员分享,可在线阅读,更多相关《数据结构复习资料.docx(16页珍藏版)》请在冰点文库上搜索。
数据结构复习资料
数据(Data):
信息的载体,它能够被计算机识别、存储和加工处理。
数据元素是数据基本单位。
数据一般包括三个方面的内容:
数据的逻辑结构、存储结构和数据的运算。
数据元素之间的逻辑关系简称为数据结构,存储结构是数据元素及其关系在计算机存储器内的表示,称为数据的存储结构它分为线性结构和非线性结构。
栈、队列、串等都是线性结构,非线性结构:
数据逻辑结构中的另一大类,它的逻辑特征是一个结点可能有多个直接前趋和直接后继。
数组、广义表、树和图等数据结构都是非线性结构。
,
数据存储方法有:
1.顺序存储方法2.链接存储方法3.索引存储方法4.散列存储方法
算法的时间复杂度不仅与问题的规模相关,还与输入实例中的初始状态有关。
但在最坏的情况下,其时间复杂度就是只与求解问题的规模相关的。
我们在讨论时间复杂度时,一般就是以最坏情况下的时间复杂度为准的
时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定。
把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里用这种方法存储的线性表这顺序表。
把与树对应的广义表称为纯表.
它限制了表中成分的共享和递归;把允许结点共享的表称为再入表
把允许递归的表称为递归表
数据项(DataItem):
具有独立意义的最小数据单位,是对数据元素属性的描述。
数据项也称域或字段。
10.数据结构(DataStructure):
指的是数据之间的相互关系,即数据的组织形式。
11.数据元素之间的逻辑关系,也称为数据的逻辑结构(LogicalStructrue);
12.数据元素及其关系在计算机存储器内的表示,称为数据的存储结构(StorageStructure);
13.算法的空间复杂度(SpaceComplexity):
当问题的规模以某种单位由1增至n时,解决该问题的算法实现所占用的空间也以某种单位由1增至f(n),则称该算法的空间复杂度是f(n)。
14.语句频度(FrequencyCount):
指的是该语句重复执行的次数。
15.线性表(LinearList):
是由n(n>0)个性质相同的数据元素组成的有限序列
16.顺序表:
即用一组连续的存储单元依次存放线性表的数据元素
17.链表(LinkedList):
用链接存储方式存储的线性表
28.若链表中每个结点只包含一个指针域,则称此链表为单链表(SingleLinked)。
19.存储数据元素信息的域称为数据域
20.存储直接后继存储位置的域称为指针域
21.循环链表(CircularLinkedList):
就是将单向链表中的最后一个结点的指针指向链表中第一个结点,使整个链表构成一个环形。
22.双(向)链表(DoubleLinkedList):
有两种不同方向链的链表称为双向循环链表。
23.栈(Stack):
是限制仅在表的一端进行插入和删除运算的线性表,通常称插入、删除的这一端为栈顶(Top),另一端称为栈底(Bottom)。
24.串是零个或多个字符组成的有限序列。
25.长度为零的串称为空串。
26.数据结构由数据的逻辑结构、存储结构和数据的运算三部分组成
27.串中任意个连续字符组成的子序列称为串的子串(模式),包含子串的串相应地称为主串(目标).
28.空串是任意串的子串,任意串是其自身的子串。
29.串的顺序存储结构简称为顺序串
30.用单链表方式来存储串值,串的这种链式存储结构简称为链串。
31.森林是m(m>=0)棵互不相交的树的集合
32.高度(深度)是树中结点的最大层数
33.二叉树是n(n>=0)个结点的有限集合。
34.文件是性质相同的记录集合,文件上的操作方要有两类:
检索和维护。
35.文件基本的组织方式有四种:
顺序组织,索引组识,散列组织和链组织。
36.在有向图中,把顶点v为终点的边的数目,称为v的入度
37.在有向图中,把顶点v为始点的边的数目,称为v的出度
38.对图进行深度优先遍历时,按访问顶点的先后次序得到的顶点序列称为深度优先遍历(DFS序列)
39.对图进行用树的按层次遍历时,按访问顶点的先后次序得到的顶点序列称为广度优先遍历(BFS序列)
40.经过排序后这些具相同关键字的记录之间的相对次序保持不变,称这种排序方法是稳定
41.经过排序后这些具相同关键字的记录之间的相对次序发生变化,称这种排序方法是不稳定
42.稳定的排序方法有直接插入排序,冒泡排序,归并排序,基数排序
43.不稳定的排序方法有希尔排序,快速排序,直接选择排序,堆排序
44.插入排序方法:
直接插入排序和希尔排序
45.交换排序方法:
冒泡排序和快速排序
46.选择排序方法:
直接选择排序和堆排序
47.平方阶0(n2)排序,一般称为间单,例如直接插入,直接排序和冒泡排序
48.线性对数阶(0(nlgn))排序,如快速,堆,归并排序。
49.线性阶(0(n))排序,如桶,箱和基数排序
50.0(n1+@)阶排序,@是介于0和1之间的常数,0<@<1,如希尔排序
51.每条边都是有向方的称有向图
52.ISAM(索引顺序存取方法),它一种专为磁盘存取
53.顺序文件中记录存放物理顺序和逻辑顺序一致
54.在单链表中,除了第1个元素结点外,任一结点的存储位置均由前驱结点的链指针指示
栈的修改是按后进先出的原则进行。
字符串中任意个连续的字符组成的子序列称为该串的子串。
假设一个10阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中,若矩阵中的第一个元素a11在B中的存储位置k=0,则元素a55在B中的存储位置k=34。
在一棵具有n个结点的严格二叉树中,度为1的结点个数为0。
对于稀疏图,采用邻接表表示法较为节省存储空间。
在排序过程中,如果需要在内,外存之间交换数据,则称其为外部排序。
若一个算法中的语句频度之和为T(n)=3n3-200nlog2n+50n,则该算法的渐近时间复杂度为
.
散列文件是一种随机存取的文件。
对有序表进行二分查找成功时,元素比较的次数仅与表的长度和被查元素的位置有关。
在带权图的最短路径问题中,路径长度是指路径上各边的权值之和。
数据库文件是由大量带有结构的记录组成的集合。
估算算法时间复杂度时考虑的问题规模通常是指算法求解问题的输入量
链串的结点大小定义为结点的数据域中存放的字符个数
VSAM文件的实现依赖于操作系统的分页存取方法的功能。
排序方法
最好时间
平均时间
最坏时间
辅助时间
稳定性
直接插入排序
0(n)
0(n2)
0(n2)
0
(1)
稳定
冒泡排序
0(n)
0(n2)
0(n2)
0
(1)
稳定
归并排序
0(nlgn)
0(nlgn)
0(nlgn)
0(n)
稳定
基数排序
0(d*n+d*rd)
0(d*n+d*rd)
0(d*n+d*rd)
0(n+rd)
稳定
希尔排序
0(n1.25)
0
(1)
不稳定
快速排序
0(nlgn)
0(nlgn)
0(n2)
0(lgn)
不稳定
直接选择排序
0(n2)
0(n2)
0(n2)
0(n2)
不稳定
堆排序
0(nlgn)
0(nlgn)
0(nlgn)
0
(1)
不稳定
直接插入排序
直接插入排序算法的空间复杂度为O
(1)。
因此,直接插入排序算法是一种稳定的排序算法。
voidinsert_sort(inta[],intn){
inti,j,temp;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 复习资料