公共基础知识
数据结构和算法
算法
算法是指解决方案准确而完备的描述
算法的基本特征：可行性、确定性、有穷性（算法程序的运行时间是有限的）、拥有足够的情报
算法的基本要素：算法对数据的基本运算和操作、算法的控制结构（顺序结构、选择结构、循环结构）
算法的复杂度（较易考）
时间复杂度
是指执行算法所需的计算工作量（而不是时间）
换言之，算法的时间复杂度是指执行该算法所需要的基本运算次数
空间复杂度
是指执行这个算法所需的内存空间
算法的时间复杂度与空间复杂度没有直接关系
数据结构的基本概念
什么是数据结构
事物的存在有两种形式：实体、关系
数据结构研究和讨论问题：
数据集合中各数据之间所固有的逻辑关系，即数据的逻辑结构
在对数据处理时，各数据在计算机中的存储结构，即数据的存储结构
对各种数据结构进行的运算
数据结构是指相互有关联数据元素集合的表示。更通俗地讲，数据结构是带有结构地数据元素的集合。
一个数据结构应该包含以下两方面内容：
表示数据元素信息即数据元素的集合，通常记为D
表示各数据元素之间的前后件关系，通常记为R。即一个数据结构可以表示为B=（D,R）。
例如：B=（D,R）  D={ 春、夏、秋、冬}
R={ （ 春，夏 ），（ 夏，秋 ），（ 秋，冬 ）}
数据结构的图形表示
父亲
一个数据结构除了用二元关系表示外，还可以直观地用图形表示，在数据结构的图形表示中，对于数据集合D中的每一个元素用中间标有元素值的方框表示，一般称之为数据节点，并简称为节点；为了进一步表示各数据之间的前后件关系，对于关系R中的每一个二元组，
用一天有向线段从前件节点指向后件节点。
数据结构的图形表示
二叉树的基本性质
线性结构和非线性结构（重点）
如果一个非空的数据结构满足下列两个条件：
1)有且只有一个根节点
2)每一个节点最多有一个前件，也最多有一个后件。
则，称该数据结构为线性结构。线性结构又称线性表。一个数据结构不是线性结构，则称为非线性结构。
线性表的基本概念
线性表由一组数据元素组成。比如一年中的（春、夏、秋、冬）。其中矩阵也是线性表。
非空线性表有如下结构特征：
1)有且只有一个根节点，它无前件；
2)有且只有一个终端节点（叶子节点），它无后件；
3)除根节点与终端节点外，其他所有节点有且只有一个前件，也有且只有一个后件。线性表中节点个数n称为线性表的长度。当n=0时，称为空表。
线性表的顺序存储结构
线性表的顺序存储结构具有以下两个基本特点：
1.线性表中所有元素所占的存储空间是连续的；
2.线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
练习：
1.下列叙述中正确的是（A）
A.具有两个根节点的数据结构一定是非线性结构
B.存储空间连续的数据结构一定是线性结构                        二叉树
C.没有根节点的非空数据结构一定是线性结构
D.存储空间不连续的数据结构一定是非线性结构              链表不连续，是线性结构
2.在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数相同，元素的存储顺序与逻辑顺序一致。
栈和队列
栈及其基本运算
●栈是限定在一端插入与删除的线性表。
●允许插入与删除的一端称为栈顶（Top），而不允许插入与删除的另一端称为栈底（Bottom）。
●栈是按照“先出后进”或“先进后出”的原则组织数据。
●在栈的顺序存储空间S（1：m）中，S（bottom）通常为栈底元素（在非空情况下），S（top）为栈顶元素。top=0表示栈空；top=m表示栈满。
●入栈运算是栈顶插入一个元素，top=top+1.如果栈空间已满，不能再入栈。这种情况称为“上溢”错误。
●退栈运算是栈顶取出一个元素，top=top-1.如果栈空，不能再退栈，这种情况称为“下溢”错误。
●一般来说，top=0，栈的开口向上，元素的个数是top；top=bottom+1，栈的开口向下，元素的个数是bottom-top+1
队列及其基本运算
●队列：队头删除元素、队尾插入元素的线性表
●允许插入元素的一端称为队尾（Rear），允许删除元素的另一端称为队头（Front）。
●队列又称为“先进先出”或“后进后出”的线性表，它体现了‘先来先服务”的原则。在计算机方面应用广泛。
●队列的顺序存储结构一般采用循环队列的形式。循环队列是线性的。
●在循环队列顺序存储空间Q（1：m），元素的个数为：Rear-Front,如果此值为负数，则为：（Rear-Front）+m。如果Rear-Front=0，则元素个数为0或m。
●入队运算是队尾加入元素即Rear=Rear+1，并当Rear=m+1，Rear置于1.如果队列已满，不能进行入队运算，这种情况称为“上溢”错误。
●退队运算时队头删除元素即Front=Front+1，不能进行退队运算，这种情况称为“下溢”错误。
练习
正确观点如下：
●栈与队列都是线性结构
●在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化
●在循环队列中，元素的个数是由队头指针和队尾指针共同决定的
●循环队列中，队头指针可以大于队尾指针，也可以小于队尾指针
在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况
在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况
●循环队列的存储空间为Q（1：60），初始状态为空。经过一系列正常的入队与退队操作后，front=24，rear=25.循环队列中的元素个数为1
●某循环队列的存储空间为Q（1：m），初始状态为front=rear=m。现经过一系列的入队操作和退队操作后，front=m，rear=m-1，则该循环队列中的元素个数为m-1
●设循环队列存储空间为Q（1：50），初始状态为front=rear=50.经过一系列入队和退队操作后，front=rear=25，则该循环队列中元素个数为0或50
●设循环队列的存储空间为Q（1：50），初始状态为front=rear=50，现经过一系列入队与退队操作后，front=rear=1，此后又正常地插入了两个元素，最后该队列中的元素个数为2
●循环队列的存储空间为Q（1：50），初始状态为人、front=rear=50.经过一系列正常的入队与退队操作后，front=rear=25，此后又插入了一个元素，则循环队列中的元素个数为1 或 50且产生上溢错误
●设栈的顺序存储空间为S（1：50），初始状态为top=0.现经过一系列入栈与退栈运算后，top=20.则当前栈中元素个数为20
●设栈的顺序存储空间为S（0:49）,栈底指针bottom=49，栈顶指针top=30（指向栈顶元素）。则栈中的元素个数为20
●设栈的顺序存储空间为S（1：m），初始状态为top=m+1，现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为m-19
栈的开口向上还是向下由初始状态决定，初始状态若为最大值的地方，栈的开口向下
●设栈与队列初始状态为空，将元素A,B,C,D,E,F,G,H依次轮流入队和入栈，然后依次轮流退队和出栈，则输出序列为A,H,C,F,E,D,G,B
线性链表的基本概念
线性表的顺序存储结构具有简单、运算方便等优点，特别是对于小线性表或长度固定的线性表，采取顺序存储结构的优越性更为突出。但是，对于大的线性表，特别是元素变动频繁的大线性表，不宜采取顺序存储结构，而是采用链式存储结构。……
双向链表具有两个或两个以上指针域
                                  带链的栈
以上3种均为线性结构
练习
✓只有一个根节点且只有一个叶子节点的数据结构也可能是非线性结构
✓顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的
✓循环队列是线性结构
✓有序线性表既可以采用顺序存储结构，也可以采用链式存储结构
✓线性链表各数据节点的存储空间可以不连续，存储顺序与逻辑顺序也没有必然联系
✓顺序存储结构的存储空间是连续的
✓在双向链表、二叉链表和循环链表中，可以从任何一个节点开始直接遍历到所有节点。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。