数据结构总结「考查目标」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