数据结构、算法及程序设计

栈的定义：栈是在表的同一端进行插入和删除运算的线性表。将允许进行插入和 删除运算的一端称为栈顶，另一端称为栈底。通常，将插入元素的运算称为入栈，将删除元素的运算称为出栈。栈遵循先进后出，后进先出的原则。

顺序存储结构：结点之间的逻辑关系由存储单元的相邻关系体现出来。

算法是解决问题的具体方法和步骤的描述，是一组有限的运算序列算法是定义在逻辑结构上的操作，独立于计算机，但必须在计算机上执行，因此，算法的实现依赖于数据存储结构

定义

算法的定义

算法复杂度：算法复杂度是对算法效率的度量，是评价算法优劣的重要依据 计算机资源分为时间资源和空间资源， 因此算法复杂度有时间复杂度（执行算法所需要的时间）和空间复杂度（执行算法过程中所占用的附加空间数量）之分

线性表结构

图形结构：数据元素之间存在多对多关系

B

C

H

D

循环队列

数据结构的基本概念

优点：充分利用空间存储单元缺点：需要保护每个结点的指针，占用较多存储单元

索引散列

满二叉树 ：如果一个深度为2的k次方减一个结点，则称其为满二叉树，在满二叉树上，每一层上的结点数都达到最大值

集合 ：一种松散的结构

树及二叉树

I

顺序查找法：一种最简单的查找算法，适用于线性表（要了解如何查找）二分查找法：又称折半查找，要求被查找的表采用顺序存储结构呢且数据元素升序或降序排列，即二分查找法只适用于有序表

一个深度为K的二叉树，第一到第k-1层为满二叉树，第K层的结点都满放在该层的最左边，则称此二叉树为完全二叉树完全二叉树的叶子结点只能出现在最下层和次下层，并且最下层的叶子结点是从左向右满放的。如果某个结点没有左子树，则他一定没有右子树。满二叉树是完全二叉树，但完全二叉树不一定是满二叉树性质4：具有n个结点的完全二叉树深度为（log2n ）+1完全二叉树中结点之间的逻辑关系可以通过节点编号准确的找出来

队列

1.线性表链式存储用一组存储单元存储线性表中的数据元素，为了反映数据之间的逻辑v 关系，每个数据元素由两部分组成，一部分用于存放数据元素，称为数据域或值域，另 一部分用于存放直接前件或直接后件的存储地址，称为指针域2.在链表中，结点之间的逻辑关系由指针域来确定3.每个结点只有一个指针域的链表称为单链表

G

了解并掌握栈的基本运算

算法的描述方法：通常描述算法的工具有：自然语言、伪代码、流程图和N-S等工具

K

数据查找算法及程序设计

数据结构示例

非线性结构（可以有多个开始结点和终结点，每个结点可有多个前件和后件）

分类

完全二叉树的性质

线性表的单链表存储

优点：每个结点占用存储空间最少缺点：不能很好的利用空间存储单元，容易产生碎片

二叉树中每个结点最多只有两个后件非空二叉树有且只有一个根结点每个结点有且只有一个子树，且有左右之分在二叉树中，结点最大的度为2二叉树有五种基本形态

数据逻辑结构：

队列是一种允许在一端进行插入运算，而在另一端进行删除运算的线性表。允许删除的一端称为队头，允许插入的一端称为队尾。队列也称为先进先出的线性表，或称为后进后出的线性表

数据物理结构

链式存储结构：结点由两部分组成，一部分用于存放数据元素，称为数据域；另一部分用于存放前件或后件的存储地址。链式存储结构通过指针反应数据元素之间的逻辑关系

性质1：在二叉树的第i层上，最多有2的i-1次个结点性质2：深度为k的二叉树最多有2的k次方-1个结点（k≥1）性质3:对于任意一棵二叉树，度为0的结点（叶子结点）总比度为2的结点多一个

栈

二叉树及其特点

F

算法的评价

树是一种常用的非线性结构，树结构中结点之间既有分支关系又有层次关系

优点：可以很方便的随机读取表中任意元素缺点：插入和删除元素需要移动大量元素

A

数据逻辑结构从逻辑上描述数据元素之间的关系，独立于计算机数据在计算机存储器中的存储方式称为数据存储结构（数据物理结构）数据结构中数据元素之间在计算机中的位置关系与逻辑关系不一定相同在数据存储结构中，不仅要存放各个数据元素，还要存放数据元素之间前后件关系的信息数据存储结构是逻辑结构是计算机在存储器中的表示

线性表是一组特征相同数据的有限序列在非空线性表中，每个数据元素都有一个确定的位置，其位置取决于它的序号非空线性表的特征是除首元素和末尾元素只有一个前件或后件，其他数据元素只有一个前件和后件线性表通常采用顺序存储结构或链式存储结构，顺序存储的线性表也称顺序表，链式存储的线性表也称为链表

E

树形结构：数据元素之间存在一对多关系

J

数据结构、算法及程序设计

线性结构：数据元素之间存在一对一关系：线性结构（至多有一个开始结点和终结点，每个结点只多一个前件和后件）

L

数值计算方法及程序设计：迭代算法、递归算法数据排序算法及程序设计：交换排序法、选择排序法、插入排序法

树

1.在用图形表示树时，通常表示成一棵倒挂树。2.逻辑上相邻的两个结点用直线连接起来，上端结点是前件，下端结点是后件3.在树结构中，有且只有一个根结点，根结点没有前件，其他结点只有一个前件4.在树结构中，每个结点可以有多个后件，将节点的后件称为该结点的子节点，将没有后件的结点称为叶子结点5.一个结点所拥有的后件的个数称为该结点的度6.叶结点的度均为0，树中所有结点的最大度称为树的度7.树中结点的最大层次称为树的深度或高度

数据结构定义：指具有相同特征、相互关联的数据集合，数据也称为数据元素或结点

在循环队列中进行入队运算时，如果存储空间的最后一个位置被占用，而第一个位置空闲，便将元素放到第一个位置上，即存储空间的第一个位置作为队尾

二叉树的存储二叉树的遍历

计算机程序主要对数据进行加工和处理

线性表

二叉树基本性质

算法的基本概念

数据元素存储方式

定义：将数据结构中数据元素之间所固有的关系描述成前后件关系。 数据元素之间的前后件关系是他们之间的逻辑关系，将这种关系称为数据逻辑结构

线性表的循环链表存储：循环链表的特点是从表中任何一个结点出发，均可以找到其他所有结点

二叉树的特点及性质