第1页共17页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第1页共17页数据结构研究什么数据处理中数据之间的逻辑关系、数据在计算机中的存储方式和在这种“结构”上能进行的操作(运算)。如何表示数据，如何存储数据，如何对数据进行处理3种逻辑结构线性结构树形结构(图结构线性结构的性质和概念性质：全序性：线性结构的全部结点两两都可以比较前后关系。单索性：除头结点外，每个结点有唯一的直接前驱结点；除尾结点外，每个结点有唯一的直接后继结点。概念：直接前驱、直接后继结点：前后相邻的结点；前驱、后继结点：前面、后面的结点。在不混淆的前提下，直接前驱和直接后继可简称为前驱和后继。树结构的性质和概念性质和概念：根结点：“树的根”，一棵树只有唯一的一个根结点。叶子结点：“树的叶子”，一棵树有很多叶子。除根结点外，每个结点有唯一的父结点；除叶子结点外，每个结点允许有多个子结点。父亲结点，子女结点，兄弟结点，祖先结点，子孙结点。树结构是一棵“倒立的树”。4种存储结构顺序结构的优缺点第2页共17页第1页共17页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第2页共17页用一块连续的、无间隙的存储空间按顺序存储各结点。各结点地址计算方法(问题1)：结点i的地址=起始地址+i×每个结点所占存储空间大小各结点之间逻辑关系表示(问题2)：地址相邻关系就表达了结点之间的逻辑关系。顺序存储结构是在内存中开辟一个连续的空间用来存储数据,因此对于内存的需求和苛刻,必须是连续的空间.在数据查找(特别是不按照规律排列的数据),时间复杂度教少.效率高.链式结构的优缺点链式存储结构是采取连表指针来指示数据的存储位置,这就可以是在内存中随意的存储,没有必须连续储存空间的要求,对于内存的要求相对教容易.但是要是是从小到大顺序排列的数据,链式存储结构的时间复杂度教小,效率高.但是要是不规则排布的数据一般时间复杂度较高,效率更低算法渐进复杂度的表示方法算法时间复杂度的渐进分析：在时间复杂度t(n)中，剔除不会从实质上改变函数数量级的项，经过这样处理得到的函数是t(n)的近似效率值，但这个近似值与原函数已经足够接近，当问题规模很大时尤其如此。这种效率的度量就称为算法的渐进复杂度。(在不引起混淆的情况下，也可简称时间复杂度)算法的最好、最坏和平均时间复杂度算法的复杂度往往取决于输入数据，例如一个排序算法的时间复杂度往往取决于输入数据的原始有序程度。因此分析算法复杂度时往往要区分最好情况、最坏情况和平均情况。例如，在一个包含n个元素的数组中查找某个数据(假定该数据是数组元素)：最好情况：该数据就是第0个元素，只需比较1次就可以结束了，其复杂度为O(1)。最坏情况：该数据是数组最后一个元素，则需要比较n次，其复杂度为O(n)。评均情况：假设需要查找的数据是第0个元素、第1个元素、…、最后一个元素的概率相等，则平均需要查找的次数为：1×1/n+2×1/n+…+n×1/n=(n+1)/2。其复杂度为O(n)。基本的算法复杂度类型第3页共17页第2页共17页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第3页共17页线性表、顺序表、链表、栈和队列的基本概念线性表是一类线性（区别于树型结构和图结构）数据结构，它有多种存储结构和应用方法，从而可以细分为顺序表、链表、队列、栈等。“线性表”是从逻辑结构的角度来描述数据结构的，它主要有两种存储结构：顺序存储结构和链式存储结构。顺序表(sequentiallist)又称为向量(vector)，它采用定长的一维数组存储结构。向量的主要特性：元素的类型相同。元素顺序地存储在一块有连续地址的存储空间中，每一个元素按其顺序有唯一的索引值，又称下标值，用它可以方便地访问元素内容。STL提供了3种通用实体：容器、迭代器和算法。链表(linkedlist)的特点是动态申请内存空间，并通过指针来链接结点，按照线性表的前驱/后继关系把一个个结点链接起来。几种用于线性表的链式存储结构：单链表；双链表；循环单链表；循环双链表。链表存储是最常用的存储方式之一，...
