数据结构复习数据结构：带有结构和操作的数据元素集合结构：数据元素之间的关系；操作：对数据的加工处理；数据结构研究的问题：非数值数据之间的结构关系，及如何表示，如何存储，如何处理。（字符字符串文字图形图象声音）对每种数据结构，主要讨论如下三方面的问题：数据的逻辑结构；逻辑结构它属于用户的视图，是面向问题的数据结构从逻辑上分为四类：⑴集合：“属于同一个集合”；⑵线性结构：一对一的线性关系；⑶树结构：一对多的层次关系；⑷图结构：多对多的任意关系。数据的存储结构；数据的存储结构是逻辑结构的物理存储方式，属于具体实现的视图，是面向计算机的通常有两种存储结构：1.顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。2.链接存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。一种数据的逻辑结构可以用多种存储结构来存储数据结构的抽象层次线性结构?直接存取类数组,文件?顺序存取类表,栈,队列,优先队列?广义索引类线性索引,搜索树非线性结构?层次结构类树，二叉树，堆?群结构类集合，图3）数据的运算，即对数据施加的操作算法分析:时间复杂度算法的概念:算法是求解问题的操作序列（或操作步骤）。时间复杂度T（n）:以求解问题的基本操作（原操作）的执行次数作为算法时间的度量for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;单条语句O（1）一条循环O（n）两条循环O(n^2)...一、线性表１线性表的逻辑结构：在线性表中，除第一个元素和最后一个元素外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继。２顺序表存储特点：1）元素存储在一组连续的内存单元中2）通过元素的存储顺序反映线性表中数据元素之的逻辑顺序；３顺序表操作特点：1）可随机存取顺序表的元素；2）顺序表的插入删除操作要通过移动元素实现４线性链表存储特点1）用任意一组的存储单元存储线性表中的数据元素；2）通过保存直接后继元素的存储位置来表示数据元素之间的逻辑关系；５线性链表操作特点1）不能随机存取元素；2）插入、删除操作通过修改结点的指针实现；６顺序表的插入平均要移动表的一半元素n/2、删除操作平均要移动(n-1)/2７顺序表能随机存取元素的原因是：顺序表能通过L.elem[i-1]或L.elem+(i-1)直接定位元素的存储地址。８线性链表不能随机存取元素的原因是：需从线性链表的头指针开始，顺着链指针定位元素的存储地址９对于经常要存取元素的应用，线性表应采用顺序存储结构10对于经常要插入删除元素的应用，线性表应采用链式存储结构二、栈和队列栈：１栈是限定仅能在表尾一端进行插入、删除操作的线性表；后进先出2表尾称为栈顶，表头称为栈底；3栈的满空判断4栈顶元素的位置由一个栈顶指针指示；5进栈、出栈操作要修改栈顶指针；6一个栈的输入序列为a,b,c，则所有可能的出栈序列为：abc,acb,bac,bca,cba7栈的顺序存储结构1）用一组连续的内存单元依次存放自栈底到栈顶的数据元素；2）栈顶元素的位置由栈顶指针指示；8栈的链式存储和实现栈的链式存储与线性表的链式存储类似，可用带头结点的线性链表存储。注意：栈顶指针就是带头结点的线性链表的头指针队列：１队列是限定仅能在表尾一端插入，表头一端删除操作的线性表；先进先出2表尾称为队头，表头称为队尾3队头、队尾元素的位置分别由队头指针和队尾指针指示；4队列的满空判断5入队操作要修改队尾指针，出队操作要修改队头指针；6循环队列——队列的顺序存贮结构三、数和二叉树1树的逻辑结构树：是一种一对多的结构关系或称为分枝结构关系，除了根之外，每个元素只有一个直接前趋；，但每个元素可以有零个或多个直接后继；2树的基本术语：树的结点孩子结点双亲结点兄弟结点结点层（根为1）树的高度（层数）结点的度（结点子树的个数）树的度（树中最大的结点度）叶子结点（度为0的结点）分枝结点（度不为0的结点）森林（互不相交的树集合）3二叉树的定义：或为空树，或由根及两颗不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。4二叉树的五种基本形态5二叉树性质性质1在二叉树的第i层上最多有2^(i-1)个结点性质2深度为k的二叉树最多有2^k-1个结点，最少有k个结点性质3设二叉树叶子结点数为n0，度为2的结点数为n2，则n0=n2+1