文档介绍：肇数据结构复****提纲羆概论莁数据:信息的载体,能被计算机识别,存储,加工。腿数据元素:表示数据的基本单位,常由若干数据项组成。袇数据项:有独立含义的数据最小标识单位。螃数据结构:数据间的组织关系,即数据的组织形式,它含:逻辑结构,存储结构,数据运算(即操作)三方面内容。蚄逻辑结构:从逻辑关系上描述数据,独立于计算机,与存储无关。是问题的抽象数学模型。薈存储结构:逻辑结构在计算机上的存储方式(或数据元素及其关系在计算机存储器内的表示),依赖于计算机。又称物理结构。薇运算:定义在逻辑结构上的对数据的一组操作,它们是抽象的。螅数据类型:一组值的集合及在此上的一组操作的总称。按其值是否可分解分成二种类型:原子类型和结构类型。螂抽象数据类型(ADT):抽象数据的组织和与之相关的操作。肈线性结构:对非空集,有仅且有一个始结点,一个终结点;所有结点最多只有一个直接前趋,一个直接后继。莈非线性结构:一个结点可能有多个直接前趋和后继。袆逻辑结构种类:线性,树,图,集合四种。羀存储结构种类:顺序,链式,索引,散列四种。螁顺序存储:逻辑上相邻结点存于物理上相邻的存储单元的存储形式。常用数组或向量实现。肈链式存储:逻辑上相邻结点可以存于物理上不相邻的存储单元的存储形式。它借助程序语言的指针类型来表示数据元素间的逻辑关系。蚃索引存储:建立附加索引表的顺序存储方式,索引表中有索引项,它对应存储的结点,每一结点对应一个索引项称为稠密索引,多个结点对应一个索引项称为稀疏索引。芃散列存储:按结点关键字值计算其存储地址的存储形式。膁程序:程序=数据结构(逻辑与存储结构)+算法(对数据运算的描述)衿学****数据结构的意义:选择一个好的数据结构和算法。蚅算法评价指标:正确;所需时间与空间;易理解,编码,调试。莁算法时间复杂度T(n):算法所需时间,当n趋向于无穷大时,其数量级称为渐近时间复杂度。其量级有:O(1),O(log2n),O(n),O(nlog2n),O(n2),O(n3),O(nk),O(2n),薀估算算法时间复杂度时考虑的问题规模通常是指算法求解问题的规模N的函数P8芅算法空间复杂度S(n):算法所需的存储空间,是问题的规模n的函数,当n趋向于无穷大时其数量级称为渐近空间复杂度。。螄罿线性表肅线性表:由n>0个元素组成的有限序列,n为表长,n=0时称为空表。其常见运算有:建表,求表长,读表头,查找,插入,删除。薃顺序表:采用顺序存储结构的线性表。袂结点地址计算式:LOC(ai)=loc(a1)+(i-1)*c葿插入算法的评价:螆最好时间复杂度是:O(1),最坏时间复杂度是:O(n),平均移动次数:n/2蚅删除算法时间复杂度:羀最好时间复杂度是:O(1),最坏时间复杂度是:O(n),平均移动次数:(n-1)/2袈查找算法时间复杂度:最好时间复杂度是:O(1),最坏时间复杂度是:O(n),平均查找长度=(n+1)/2薆链表:采用链式存储结构的线性表。蚆单链表:每个结点只有一个指针域的链表。莃单链表插入,删除(查找)算法的时间复杂度是:O(n);芇指针变量:存放空间地址的变量P。芆结点变量:*P表示P所指向的结点存储空间。:将头结点地址放入尾结点的指针域的单链表。:每个结点有二个指针域的(前,后各一个)链表。=数据所占总存储空间量/:对于顺序表:其空间事先难估算,大了浪费,小了不够。会产生溢出。链表与此相反,但占用空间多点。顺序表可随机或顺序存取,随机访问的时间复杂度为O(1),不适于插入,删除多的场合,链表与此反之,只能顺序访问,适于插入,删除多的场合,如果插入和删除主要在首尾进行,则用带尾指针的单循环链表为宜。薅栈和队列袃栈:只能在一端(栈顶)进行插,删运算的线性表,线性表的变种,一种逻辑结构。具有栈顶指针,其常见运算有:建空栈,判栈空,进栈,出栈,读栈顶元素。蒅LIFO:后进先出。袂顺序栈:采用顺序存储结构的栈。莈链栈:采用链式存储结构的栈。肇队列:只能尾进头出的线性表。一种逻辑结构,线性表的又一变种。其常见运算有:建空队,判队空,进队,出队,判队满。有头指针和尾指针。袅FIFO:先进先出。薃直形队列:采用一般向量存储结构的队列,它会产生假溢出现象。葿顺序队列:采用顺序存储结构的队列。膅循环队列:存储在首尾相结的向量中的队列。它不会产生假溢出现象,其队满判据是:(rear+1)/m=front;队空判据是:rear=front。或计数器=0。rear,front和length三者间的关系是:front=(rear-length+m)%m;length=(rear-front+m)%m莄链队:采用链式存储结构的队列。莃串薀串: