数据结构和算法算法算法：是指解决方案的准确而完整的描述，程序属于算法的一种描述，算法优于程序。基本特征：可行性，确定性，又穷性，足够的情报（输入和输出）两个基本要素：对象的运算和操作以及算法的控制结构运算和操作：算数运算、逻辑运算、关系运算、数据传输（输入，输出，赋值）控制结构：算法中各种运算和操作的执行顺序的控制结构，包括：顺序、选择和循环，描述控制结构的工具：传统流程图（PFD），N-S结构化流程图，算法描述语言（PDL）算法设计基本方法：列举法，归纳法，递推法（），递归法（分层），减半递推法（分而治之），回溯法（试）算法复杂度：算法的时间复杂度和空间复杂度时间复杂度：执行算法所需要的计算工作量用基本计算次数来度量，是问题规模的函数。算法的工作量=F(n)空间复杂度：执行算法所需要的内存空间算法程序所占的空间，输入的初始数据所占的空间和程序执行过程中所需要的额外空间。2.数据结构2.1数据结构作为计算机的一门学科，主要讨论一下3个问题：数据的逻辑结构（前后件关系），存储结构，及数据结构的运算。目的：提高数据的运算速度，降低数据的存储空间数据结构-相互有关联的数据元素的集合，数据元素是世界中客观存在的一切个体，是数据结构的基本单位，一个数据结构包括两方面信息：表示数据的信息和表示各数据之间的前后间关系及逻辑关系。B=（D,R）（二元关系表示），还可用图形表示，方框+有向线段。每一个数据元素称为节点，没有前节点的叫做根节点，没有后节点的称为叶子节点。存储结构-数据的逻辑借个和数据信息在存储空间中的存放形式称为存储结构，一种逻辑结构根据需要可以表示成多种存储结构，采取不同的存储结构，数据处理的效率是不同的2.2线性结构：有且只有一个根节点，每一个节点最多有一个前件，也最多有一个后件。且在一个线性结构中插入或者删除一个节点后还应该是线性结构。一个空的数据结构属于先行结构还是非线性结构还要根据具体情况而定。线性表：一种线性结构，数据元素在线性表中的位置只取决于自己的序号线性表的顺序存储：存储空间连续，按逻辑顺序依次存放表中元素随机存取：知道序号既可知道地址，插入和删除时表中元素的运动。栈-实现递归调用的存储结构，其插入和删除只能在表的一端进行。允许插入和删除的一端称为栈顶，另一端称为栈底，栈顶元素最后被插入，最先被删除：“后进先出”。用top指针指栈顶的位置，bottom指针指栈底的位置。入栈：top+1，出栈top-1，读栈顶元素：为其赋值。队列-允许一端插入，一端删除的线性表，先进先出，允许插入的一端称为队尾，用尾指针（rear）指向最后被插入的元素，允许删除的一端称为队头，用头指针（front）只想派头元素的前一个位置，向队尾加一个元素涉及rear，队头删除只涉及front。队列的存储结构一般用循环队列来表示，在循环队列中，队满和队空都是rear=front，rear和front的纸大小不定，入队rear+1，出队ftont+1，队中元素为(rear-front+maxsize)modmaxsize线性链表-每个节点由两个部分组成，一部分用于存储数据元素值，一部分用于存储指针域，用于指向前件或后件：有一个head指针只想一个节点的指针域，最后一个节点的指针域为null。为顺序存取，存储空间大，密度小；循环链表-最后一个节点的指针域只想表头节点。2.非线性结构树-根节点，叶节点，度-每一个节点的后件个数，最大的度成为树的度。树的最大层次成为深度，子树-以某一节点的子节点作为根的树为该节点的子树二叉树-非空二叉树只有一个根节点，每一个节点最多有两棵子树，左子树和右子树。二叉树的基本性质-在k层的节点最多有2^（k-1）个，深度为m的二叉树最多有2^m-1,n0=n2+1.满二叉树-所有的节点数都达最大值完全二叉树-出最后一层外，每一层上的节点数均达到最大值，在最后一层只缺少右边的若干节点。左节点（2k）和右节点（2k+1）的父节点k，在完全二叉树中最多只有一个度为1的节点。注意相关习题。二叉树的存储结构一般为链式。二叉树的遍历-不重复的访问二叉树的所有节点。前序遍历（DLR），中序遍历(LDR)，后序遍历(LRD).3.数据中的查找和排序3.1查找技术顺序查找：平均查找次数（n+1）/2,函数O（n）。一个个的找条件：所有的无序表，和有序表的链式存储结构二分法查找二分法查找：有序表（递增）的顺序存储，最坏情况需要log2n3.1排序技术（非递减顺序排）交换类排序法：借助元素间相互交换进行排序。冒泡排序法：n(n-1)/2快速排序法：不断分割交换排序，插入类排序法：简单插入：各元素一次插入n(n-1)/2希尔排序法：整个无序序列分成