数据结构知识点总结 内容概要： 基本概念——线性表——栈与队列——树与二叉树——图——查找算法——排序算法 一、 基本概念 1、数据元素是数据的基本单位。 2、数据项是数据不可分割的最小单位。 3、数据结构的 逻辑结构（抽象的，与实现无关） 物理结构（存储结构） 顺序映像（顺序存储结构）位置“相邻” 非顺序映像（链式存储结构）指针表示关系 4、算法特性：算法具有正确性、有穷性，确定性，（可行性）、输入，输出 正确性：能按设计要求解决具体问题，并得到正确的结果。 有穷性：任何一条指令都只能执行有限次，即算法必须在执行有限步后结束。 确定性：算法中每条指令的含义必须明确，不允许由二义性 可行性：算法中待执行的操作都十分基本，算法应该在有限时间内执行完毕。 输入：一个算法的输入可以包含零个或多个数据。 输出：算法有一个或多个输出 5、算法设计的要求： （1）正 确 性：算法应能满足设定的功能和要求 。 （2）可 读 性：思路清晰、层次分明、易读易懂 。 （3）健 壮 性：输入非法数据时应能作适当的反应和处理。 （4）高 效 性（时间复杂度）：解决问题时间越短，算法的效率就越高。 （5）低存储量（空间复杂度）：完成同一功能，占用存储空间应尽可能少。 二、 线性表 1、线性表 List：最常用且最简单的数据结构。 含有大量记录的线性表称为文件。 2、线性表是n 个数据元素的有限序列。 线性结构的特点： ①“第一个” ②“最后一个” ③前驱 ④后继。 3、顺序表——线性表的顺序存储结构 特点 a) 逻辑上相邻的元素在物理位置上相邻。 b) 随机访问。 1) typedef struct{ DataType elem[MAXSIZE]; int length; } SqList; 2) 表长为n 时，线性表进行插入和删除操作的时间复杂度为O（n）‘ 插入一个元素时大约移动表中的一半元素。 删除一个元素时大约移动表中的（n-1）\2 4、线性表的链式存储结构 1) 类型定义 简而言之，“数据 + 指针”。 typedef struct LNode { DataType data; struct LNode *next; } LNode, *LinkList; 2) 不带头结点的空表判定为 L= =null 带头结点的空表判定为 L->next= =null 循环单链表为空的判定条件为 L.next= =L 线性链表的最后一个结点的指针为NULL 头结点的数据域为空，指针域指向第一个元素的指针。 5、顺序表和单链表的比较 0 1 MAXSIZE-1 ... L.elem[] L.elem[] L.elem[...
