逻辑结构

特点：

只是描述数据结构中数据元素之间的联系规律
是从具体问题中抽象出来的数学模型，是独立于计算机存储器的(与机器无关)

逻辑结构分类

线性结构

集合中必存在唯一的一个 "第一个元素"
集合中必存在唯一的一个 "最后的元素"
除最后元素之外，其他数据元素均有唯一的 "后继"
除第一元素之外，其他数据元素均有唯一的 "前驱"

树形结构(层次结构)

树形结构指的是数据元素之间存在着"一对多"的树形关系的数据结构，是一类重要的非线性数据结构。在树形结构中，树根结点没有前驱结点，其余每个结点有且只有一个前驱结点。叶子结点没有后续结点，其余每个结点的后续节点数可以是一个也可以是多个。

图状结构（网状结构)

图是一种比较复杂的数据结构。在图结构中任意两个元素之间都可能有关系，也就是说这是一种多对多的关系。

其他结构

除了以上几种常见的逻辑结构外，数据结构中还包含其他的结构，比如集合等。有时根据实际情况抽象的模型不止是简单的某一种，也可能拥有更多的特征。

存储结构

特点:

是数据的逻辑结构在计算机存储器中的映象（或表示)
存储结构是通过计算机程序来实现的，因而是依赖于具体的计算机语言的。

存储结构分类

顺序存储

顺序存储( Sequential Storage ):将数据结构中各元素按照其逻辑顺序存放于存储器一片连续的存储空间中。

链式存储

链式存储(Linked Storage )∶将数据结构中各元素分布到存储器的不同点，用记录下一个结点位置的方式建立它们之间的联系，由此得到的存储结构为链式存储结构。

索引存储

索引存储（ lndexed Storage ):在存储数据的同时，建立一个附加的索引表，即索引存储结构=数据文件+索引表。

线性表的链式存储

只能操作头部节点指向下一个

定义

将线性表L=(a0,a1.......an-1)中各元素分布在存储器的不同存储块，称为结点，每个结点（尾节点除外）中都持有一个指向下一个节 点的引用，这样所得到的存储结构为链表结构。

特点

逻辑上相邻的元素ai, ai+1，其存储位置也不一定相邻;
存储稀疏，不必开辟整块存储空间。
对表的插入和删除等运算的效率较高。
逻辑结构复杂，不利于遍历。

栈

先进后出 --> 水桶

定义

栈是限制在一端进行插入操作和删除操作的线性表（俗称堆栈），允许进行操作的一端称为"栈顶”，另一固定端称为"栈底”，当栈中没有元素时称为空栈"。

特点

栈只能在一端进行数据操作
栈模型具有先进后出或者叫做后进先出的规律

队列

先进先出 --> 排队

定义

队列是限制在两端进行插入操作和删除操作的线性表，允许进行存入操作的一端称为队尾”，允许进行删除操作的一健称为“队就-b

特点:

队列只能在队头和队尾进行数据操作
队列模型具有先进先出或者叫做后进后出的规律

树形结构

定义

树( Tree )是n ( n≥0 )个节点的有限集合T，它满足两个条件∶有且仅有一个特定的称为根(Root )的节点;其余的节点可以分为m ( m≥0 )个互不相交的有限集合T1、T2、......、Tm，其中每一个集合又是一棵树，并称为其根的子树( Subtree ) 。
基本概念
一个节点的子树的个数称为该节点的度数，一棵树的度数是指该树中节点的最大度数。
度数为零的节点称为树叶或终端节点，度数不为零的节点称为分支节点，除根节点外的分支节点称为内部节点。
一个节点的子树之根节点称为该节点的子节点，该节点称为它们的父节点，同一节点的各个子节点之间称为兄弟节点。一棵树的根节点没有父节点，叶节点没有子节点。
一个节点系列k1,k2，......,ki,ki+1,......,kj,并满足ki是ki+1的父节点，就称为一条从k1到kj的路径，路径的长度为j-1,即路径中的边数。路径中前面的节点是后面节点的祖先，后面节点是前面节点的子孙。
节点的层数等于父节点的层数加一，根节点的层数定义为树中节点层数的最大值称为该树的高度或深度。
m ( m≥0 ）棵互不相交的树的集合称为森林。树去掉根节点就成为森林，森林加上一个新的根节点就成为树。

二叉树

定义

二叉树( Binary Tree )是n ( n≥0 )个节点的有限集合，它或者是空集( n=0 ），或者是由一个根节点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。二叉树与普通有序树不同，二叉树严格区分左孩子和右孩子，即使只有一个子节点也要区分左右。

二叉树的特征

工叉树第i ( i≥1)层上的节点最多为2i-1个。
深度为k ( k≥1)的二叉树最多有2k一1个节点。
在任意一棵二叉树中，树叶的数目比度数为2的节点的数目多一。
满二叉树︰深度为k ( k≥1)时有2k一1个节点的二叉树。
完全二叉树∶只有最下面两层有度数小于2的节点，且最下面一层的叶节点集中在最左边的若干位置上。

二叉树的遍历

沿某条搜索路径周游二叉树，对树中的每一个节点访问一次且仅访问一次。
先序遍历︰先访问树根，再访问左子树，最后访问右子树; --> 根左右
中序遍历︰先访问左子树，再访问树根，最后访问右子树; --> 左根右
后序遍历︰先访问左子树，再访问右子树，最后访问树根﹔ --> 左右根
层次遍历:从根节点开始，逐层从左向右进行遍历。

递归思想

什么是递归?

所谓递归函数是指一个函数的函数体中直接调用或间接调用了该函数自身的函数。这里的直接调用是指一个函数的函数体中含有调用自身的语句，间接调用是指一个函数在函数体里有调用了其它函数，而其它函数又反过来调用了该函数的情况。
　　

递归函数调用的执行过程分为两个阶段

递推阶段︰从原问题出发，按递归公式递推从未知到已知,最终达到递归终止条件。
回归阶段:按递归终止条件求出结果，逆向逐步代入递归公式，回归到原问题求解。
　　

优点与缺点

优点︰递归可以把问题简单化，让思路更为清晰,代码更简洁
缺点︰递归因系统环境影响大，当递归深度太大时，可能会得到不可预知的结果

算法基础

基础概念特征

定义

算法( Algorithm )是一个有穷规则（或语句、指令)的有序集合。它确定了解决某一问题的一个运算序列。对于问题的初始输入，通过算法有限步的运行，产生一个或多个输出。

数据的逻辑结构与存储结构密切相关

算法设计:取决于选定的逻辑结构
算法实现:依赖于采用的存储结构

算法的特性

有穷性—～算法执行的步骤（或规则)是有限的;
确定性——每个计算步骤无二义性;
可行性——每个计算步骤能够在有限的时间内完成;
输入，输出——存在数据的输入和出输出

评价算法好坏的方法

正确性︰运行正确是一个算法的前提。
可读性︰容易理解、容易编程和调试、容易维护。
健壮性:考虑情况全面，不容以出现运行错误。
时间效率高︰算法消耗的时间少。
储存量低︰占用较少的存储空间。

排序和查找

排序

排序(Sort)是将无序的记录序列(或称文件）调整成有序的序列。

常见排序方法∶

冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

选择排序
工作原理为，首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕