数据结构总结VIP免费

数据结构总结「考查目标」1.理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。2.掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。3.能够选择合适的数据结构和方法进行问题求解。第一章绪论（一）基本概念1数据结构(DataStructure)：是相互之间存在一种或多种特定关系的数据元素的集合。2数据结构的三个方面的含义：1）数据的逻辑结构，只抽象反映数据元素的逻辑关系，与数据存储无关，独立于计算机；2）数据的存储结构，数据的逻辑结构在计算机存储器中的实现，是逻辑结构用计算机语言的实现，它依赖于计算机语言。分为顺序存储结构和链式存储结构。3）数据的运算，定义在逻辑结构上，每种逻辑结构都有一个运算集合。常用的运算：检索/插入/删除/更新/排序。3根据数据元素间关系的基本特性，有四种基本数据结构：集合——数据元素间除“同属于一个集合”外，无其它关系线性结构：一个对一个，如线性表、栈、队列树形结构：一个对多个，如树图状结构：多个对多个，如图4数据类型：一个值的集合及在值上定义的一组操作的总称。分为：原子类型和结构类型。5抽象数据类型：抽象数据的组织和与之相关的操作。优点：将数据和操作封装在一起实现了信息隐藏。6抽象数据类型ADT：是在概念层上描述问题；类：是在实现层上描述问题；在应用层上操作对象（类的实例）解决问题。（二）算法的概念所谓算法（Algorithm)是描述计算机解决给定问题的操作过程（解题方法），即为解决某一特定问题而由若干条指令组成的有穷序列。一个算法必须满足以下五个准则：（1）有穷性---执行了有限条指令后一定要终止。（2）确定性（无二义）---算法的每一步操作都必须有确切定义，不得有任何歧义性。（3）可行性---算法的每一步操作都必须是可行的，即每步操作均能在有限时间内完成。（4）输入数据---一个算法有n（n>=0)个初始数据的输入。（5）输出数据---一个算法有一个或多个与输入有某种关系的有效信息的输出。（三）对算法进行简单分析的评价准则算法的评价准则首先，算法必须是“正确”的，其次：（1）执行算法所耗费的时间（效率要高）。（2）执行算法所耗费的存储空间（主要考虑辅存空间；低存储要求）。（3）算法的可读性、易维护性要好（易于理解，易于编码，易于调试）。（四）什么是问题的规模？时间复杂度？渐近时间复杂度？（1）问题的规模（size)---算法求解问题的输入量（或初始数据量）。不考虑机器软硬件环境时算法的时间耗费：设：执行每条语句所需时间为单位时间，则：一个算法耗费的时间=所有语句的频度之和。（2）时间复杂度T(n)---时间耗费，它是算法求解问题n的函数。（3）渐近时间复杂度---即当问题的规模n→∞时的时间复杂度T(n)的数量级（阶），记作：T(n)=O(f(n))****评价一个算法的时间性能，主要标准是算法的渐近时间复杂度第二章线性表（一）线性表的定义和基本操作P18-P19线性表:是由n(n>=0)个数据元素（结点）a1,a2,a3,⋯⋯an组成的有限序列。基本操作:（1）存取;（2）插入;（3）删除;（4）查找;（5）合并;（6）分解（7）排序;（8）求线性表的长度（二）线性表的实现1.顺序存储结构顺序表的描述：Fig2-1//⋯线性表的动态分配顺序存储结构⋯//#defineList_INIT_SIZE100//线性表存储空间的初始分配量。#defineLISTINCREMENT10//线性表存储空间的分配增量typedefstruct{ElemType*elem;//分配空间基址intLenth;//当前长度intListsize;//当前分配的存储容量（以sizeof(ElemType)为单位）}Sqlist;1）在顺序表中实现插入算法的思想、算法和求T(n)的方法。算法思想：Fig2-2若i=n+1,则将x插入到表尾；若表长度n<0或插入位置不适当，则输出错误信息，并返回-1；当1<=I<=n时，则从表尾开始到I个依次向后移动一个位置（共需移动n-I+1个数据元素)。最后将x存入v[I]中，表长n增1插入成功，函数返回值为0。算法和求T(n)的方法：P242）在顺序表中实现删除算法的思想、算法和求T(n)的方法。算法思想：若i=n,只需删除终端结点，不用移动结点；若表长度n<=0或删除位置不适当，则输出错误信息，并返回-1；当1<=I