文档介绍：------------------------------------------------------------------------------------------------ ——————————————————————————————————————数据结构知识点( 含算法) 概念总结第一章概论 1. 数据结构描述的是按照一定逻辑关系组织起来的待处理数据元素的表示及相关操作,涉及数据的逻辑结构、存储结构和运算 2. 数据的逻辑结构是从具体问题抽象出来的数学模型, 反映了事物的组成结构及事物之间的逻辑关系可以用一组数据(结点集合 K )以及这些数据之间的一组二元关系(关系集合 R )来表示: (K, R) 结点集 K 是由有限个结点组成的集合, 每一个结点代表一个数据或一组有明确结构的数据关系集 R 是定义在集合 K 上的一组关系, 其中每个关系 r(r∈R )都是 K×K 上的二元关系 3. 数据类型 a. 基本数据类型整数类型(integer) 、实数类型(real) 、布尔类型(boolean) 、字符类型( char ) 、指针类型( pointer ) b. 复合数据类型复合类型是由基本数据类型组合而成的数据类型; 复合数据类型本身,又可参与定义结构更为复杂的结点类型 4. 数据结构的分类:线性结构(一对一) 、树型结构(一对多)、图结构(多对多) 5. 四种基本存储映射方法:顺序、链接、索引、散列------------------------------------------------------------------------------------------------ —————————————————————————————————————— 6. 算法的特性:通用性、有效性、确定性、有穷性 7. 算法分析: 目的是从解决同一个问题的不同算法中选择比较适合的一种,或者对原始算法进行改造、加工、使其优化 8. 渐进算法分析 a .大Ο分析法:上限,表明最坏情况 :下限,表明最好情况 :当上限和下限相同时,表明平均情况第二章线性表 1. 线性结构的基本特征 a. 集合中必存在唯一的一个“第一元素” b. 集合中必存在唯一的一个“最后元素” c. 除最后元素之外,均有唯一的后继 d. 除第一元素之外,均有唯一的前驱 2. 线性结构的基本特点: 均匀性、有序性 3. 顺序表 a. 主要特性: 元素的类型相同; 元素顺序地存储在连续存储空间中,每一个元素唯一的索引值;使用常数作为向量长度 b. 线性表中任意元素的存储位置: Loc(ki) = Loc(k0) +i*L (设每个元素需占用 L 个存储单元) c. 线性表的优缺点: 优点: 逻辑结构与存储结构一致; 属于随机存取方式, 即查找每个元素所花时间基本一样缺点:空间难以扩充------------------------------------------------------------------------------------------------ —————————————————————————————————————— d. 检索: ASL= 【Ο(1)】 e. 插入: 插入前检查是否满了, 插入时插入处后的表需要复制【Ο(n)】 f. 删除: 删除前检查是否是空的, 删除时直接覆盖就行了【Ο(n)】 4. 链表 单链表 a. 特点: 逻辑顺序与物理顺序有可能不一致; 属于顺序存取的存储结构,即存取每个数据元素所花费的时间不相等 b. 带头结点的怎么判定空表: head 和 tail 指向单链表的头结点 c. 链表的插入( q->next=p->next; p->next=q; )【Ο(n)】 d. 链表的删除( q=p->next;p->next = q->next;delete q;)【Ο(n)】 e. 不足: next 仅指向后继,不能有效找到前驱 双链表 a. 增加前驱指针,弥补单链表的不足 b. 带头结点的怎么判定空表:head 和 tail 指向单链表的头结点 c. 插入:( q->next = p->next; q->prev = p; p->next = q; q->next->prev = q;) d. 删除:( p->prev->next = p->next;p->next->prev = p->prev; p->prev = p->next = NULL; delete p;) 顺序表和链表的比较 主要优点---