数据结构知识点总结内容概要：基本概念——线性表——栈与队列——树与二叉树——图——查找算法——排序算法基本概念1、数据元素是数据的基本单位。2、数据项是数据不可分割的最小单位。3、数据结构的逻辑结构（抽象的，与实现无关）物理结构（存储结构）顺序映像（顺序存储结构）位置“相邻”非顺序映像（链式存储结构）指针表示关系4、算法特性：算法具有正确性、有穷性，确定性，（可行性）、输入，输出正确性：能按设计要求解决具体问题，并得到正确的结果。有穷性：任何一条指令都只能执行有限次，即算法必须在执行有限步后结束。确定性：算法中每条指令的含义必须明确，不允许由二义性可行性：算法中待执行的操作都十分基本，算法应该在有限时间内执行完毕。输入：一个算法的输入可以包含零个或多个数据。输出：算法有一个或多个输出5、算法设计的要求：（1）正确性：算法应能满足设定的功能和要求。（2）可读性：思路清晰、层次分明、易读易懂。（3）健壮性：输入非法数据时应能作适当的反应和处理。（4）高效性（时间复杂度）：解决问题时间越短，算法的效率就越高。（5）低存储量（空间复杂度）：完成同一功能，占用存储空间应尽可能少。线性表1、线性表List：最常用且最简单的数据结构。含有大量记录的线性表称为文件。2、线性表是n个数据元素的有限序列。线性结构的特点：①“第一个”②“最后一个”③前驱④后继。3、顺序表——线性表的顺序存储结构特点a)逻辑上相邻的元素在物理位置上相邻。b)随机访问。01MAXSIZE-1...L.elem[]L.elem[]L.elem[]L.length==0L.length==MAXSIZE0<L.length<MAXSIZEtypedefstruct{DataTypeelem[MAXSIZE];intlength;}SqList;表长为n时，线性表进行插入和删除操作的时间复杂度为O（n）‘插入一个元素时大约移动表中的一半元素。删除一个元素时大约移动表中的（n-1）\24、线性表的链式存储结构类型定义简而言之，“数据+指针”。datanexttypedefstructLNode{DataTypedata;structLNode*next;}LNode,*LinkList;不带头结点的空表判定为L==null带头结点的空表判定为L->next==null循环单链表为空的判定条件为L.next==L线性链表的最后一个结点的指针为NULL头结点的数据域为空，指针域指向第一个元素的指针。5、顺序表和单链表的比较顺序表单链表以地址相邻表示关系用指针表示关系随机访问，取元素O(1)顺序访问，取元素O(n)插入、删除需要移动元素O(n)插入、删除不用移动元素O(n)(用于查找位置)6、顺序存储：优点：存储密度大，可随机存储缺点：大小固定；不利于增减节点;存储空间不能充分利用；容量难扩充链式存储：优点：易于插入删除；可动态申请空间；表容量仅受内存空间限制缺点：增加了存储空间的开销；不可以随机存储元素栈与队列1、栈栈：限定仅在表尾进行插入或删除操作的线性表。栈顶：表尾端栈底：表头栈是先进后出的线性表。插入栈顶元素称为入栈，删除栈顶元素称为出栈。2、栈分为链栈和顺序栈·链栈a1/\anS...an-1用不带头结点的单链表实现。·顺序栈类似于顺序表，插入和删除操作固定于表尾。3、队列先进先出的线性表。队尾入队对头出队允许插入的一端叫做队尾允许删除的一端叫做对头4、链队列·5、循环队列typedefstruct{DataTypeelem[MAXSIZE];intfront,rear;//队头、队尾位置}SqQueue;·循环队列判断队空的条件为front=rear循环队列判断队满的条件为（rear+1）%m=front在一个循环队列中删除元素时，首先需要后移队首指针。6、栈与队列比较：都是线形结构，栈的操作LIFO（后进先出），队列操作FIFO（先进先出）。树和二叉树树的定义树（Tree）：是n（n≥0）个有限数据元素的集合。在任意一棵非空树T中：（1）有且仅有一个特定的称为树根（Root）的结点，根结点无前趋结点；（2）当n>1时，除根结点之外的其余结点被分成m(m>0)个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树，并且称为根的子树。基本术语：结点的度数：结点的非空子树（即后缀）个数叫作结点的度数树叶、分支结点：左（右）子树均为空二叉树的