您好,欢迎访问三七文档
当前位置:首页 > 中学教育 > 高中教育 > 数据结构知识点总结(详细无题目)
数据结构知识点总结内容概要:基本概念——线性表——栈与队列——树与二叉树——图——查找算法——排序算法一、基本概念1、数据元素是数据的基本单位。2、数据项是数据不可分割的最小单位。3、数据结构的逻辑结构(抽象的,与实现无关)物理结构(存储结构)顺序映像(顺序存储结构)位置“相邻”非顺序映像(链式存储结构)指针表示关系4、算法特性:算法具有正确性、有穷性,确定性,(可行性)、输入,输出正确性:能按设计要求解决具体问题,并得到正确的结果。有穷性:任何一条指令都只能执行有限次,即算法必须在执行有限步后结束。确定性:算法中每条指令的含义必须明确,不允许由二义性可行性:算法中待执行的操作都十分基本,算法应该在有限时间内执行完毕。输入:一个算法的输入可以包含零个或多个数据。输出:算法有一个或多个输出5、算法设计的要求:(1)正确性:算法应能满足设定的功能和要求。(2)可读性:思路清晰、层次分明、易读易懂。(3)健壮性:输入非法数据时应能作适当的反应和处理。(4)高效性(时间复杂度):解决问题时间越短,算法的效率就越高。(5)低存储量(空间复杂度):完成同一功能,占用存储空间应尽可能少。二、线性表1、线性表List:最常用且最简单的数据结构。含有大量记录的线性表称为文件。2、线性表是n个数据元素的有限序列。线性结构的特点:①“第一个”②“最后一个”③前驱④后继。3、顺序表——线性表的顺序存储结构特点a)逻辑上相邻的元素在物理位置上相邻。b)随机访问。1)typedefstruct{DataTypeelem[MAXSIZE];intlength;}SqList;2)表长为n时,线性表进行插入和删除操作的时间复杂度为O(n)‘插入一个元素时大约移动表中的一半元素。删除一个元素时大约移动表中的(n-1)\24、线性表的链式存储结构1)类型定义简而言之,“数据+指针”。typedefstructLNode{DataTypedata;structLNode*next;}LNode,*LinkList;2)不带头结点的空表判定为L==null带头结点的空表判定为L-next==null循环单链表为空的判定条件为L.next==L线性链表的最后一个结点的指针为NULL头结点的数据域为空,指针域指向第一个元素的指针。5、顺序表和单链表的比较01MAXSIZE-1...L.elem[]L.elem[]L.elem[]L.length==0L.length==MAXSIZE0L.lengthMAXSIZEdatanext顺序表单链表以地址相邻表示关系用指针表示关系随机访问,取元素O(1)顺序访问,取元素O(n)插入、删除需要移动元素O(n)插入、删除不用移动元素O(n)(用于查找位置)6、顺序存储:优点:存储密度大,可随机存储缺点:大小固定;不利于增减节点;存储空间不能充分利用;容量难扩充链式存储:优点:易于插入删除;可动态申请空间;表容量仅受内存空间限制缺点:增加了存储空间的开销;不可以随机存储元素三、栈与队列1、栈栈:限定仅在表尾进行插入或删除操作的线性表。栈顶:表尾端栈底:表头栈是先进后出的线性表。插入栈顶元素称为入栈,删除栈顶元素称为出栈。2、栈分为链栈和顺序栈·链栈用不带头结点的单链表实现。·顺序栈类似于顺序表,插入和删除操作固定于表尾。a1/\anS...an-1进栈:进栈运算是在栈顶位置插入一个新元素x。算法思想:(a)判栈是否为满,若栈满,作溢出处理,并返回0;(b)若栈未满,栈顶指针top加1;(c)将新元素x送入栈顶,并返回1。算法实现:intPush(SeqStack*s,datatypex){if(s-top==MAXLEN–1)return0;//栈满不能入栈,且返回0else{s-top++;s-data[s-top]=x;//栈不满,则压入元素xreturn1;}//进栈成功,返回1}出栈:出栈运算是指取出栈顶元素,赋给某一个指定变量x。算法步骤:(a)判栈是否为空,若栈空,作下溢处理,并返回0;(b)若栈非空,将栈顶元素赋给变量x;(c)指针top减1,并返回1。算法实现:datatypePop(SeqStack*s){datatypex;if(SEmpty(s))return0;//若栈空不能出栈,且返回0else{x=s-data[s-top];//栈不空则栈顶元素存入*xs-top--;returnx;}//出栈成功,返回1}3、队列先进先出的线性表。队尾入队对头出队允许插入的一端叫做队尾允许删除的一端叫做对头4、链队列·typedefstructqueuenode{datatypedata;structqueuenode*next;}queuenode;//链队结点的类型datatypetypedefstruct{queuenode*front,*rear;}linkqueue;//将头指针、尾指针封装在一起的链队frontrearpABJ^…frontrearpAABBJ^J^…图4-6链队列示意图5、循环队列typedefstruct{DataTypeelem[MAXSIZE];intfront,rear;//队头、队尾位置}SqQueue;·循环队列判断队空的条件为front=rear循环队列判断队满的条件为(rear+1)%m=front在一个循环队列中删除元素时,首先需要后移队首指针。6、栈与队列比较:都是线形结构,栈的操作LIFO(后进先出),队列操作FIFO(先进先出)。四、树和二叉树1.树的定义树(Tree):是n(n≥0)个有限数据元素的集合。在任意一棵非空树T中:(1)有且仅有一个特定的称为树根(Root)的结点,根结点无前趋结点;(2)当n1时,除根结点之外的其余结点被分成m(m0)个互不相交的集合T1,T2,…,Tm,其中每一个集合Ti(1≤i≤m)本身又是一棵树,并且称为根的子树。2.基本术语:结点的度数:结点的非空子树(即后缀)个数叫作结点的度数树叶、分支结点:左(右)子树均为空二叉树的结点称作树叶否则称作分支结点。结点的层数:规定根的层数是0,其余结点的层数等于其父结点的层数加1孩子和双亲:树的深度:树的度数:树中度数最大的结点度数叫作树的度数树林:是由零个或多个不相交的树所组成的集合。3.二叉树性质:1)二叉树的第i层上至多有2i-1个结点。2)深度为k的二叉树至多有2k-1个结点。满二叉树:深度为k,有2k-1个结点。完全二叉树:给满二叉树的结点编号,从上至下,从左至右,n个结点的完全二叉树中结点在对应满二叉树中的编号正好是从1到n。3)叶子结点n0,度为2的结点为n2,则n0=n2+1。考虑结点个数:n=n0+n1+n2考虑分支个数:n-1=2n2+n1可得n0=n2+14)n个结点的完全二叉树深度为1logn。5)n个结点的完全二叉树,结点按层次编号有:i的双亲是2/n,如果i=1时为根(无双亲);i的左孩子是2i,如果2in,则无左孩子;i的右孩子是2i+1,如果2i+1n则无右孩子。4.二叉树的存储结构·顺序存储结构用数组、编号i的结点存放在[i-1]处。适合于存储完全二叉树。·链式存储结构二叉链表:typedefstructBTNode{DataTypedata;structBTNode*lchild,*rchild;}BTNode,*BinTree;三叉链表:typedefstructBTNode{DataTypedata;structBTNode*lchild,*rchild,*parent;}BTNode,*BinTree;在链式存储结构中,含有n个结点的二叉链表有n+1个空链域。5.遍历二叉树(先序DLR、中序LDR、后序LRD)方法与C语言描述由二叉树的递归定义可知,一棵二叉树由根结点(D)、根结点的左子树(L)和根结点的右子树(R)三部分组成。因此,只要依次遍历这三部分,就可以遍历整个二叉树。一般有三种方法:先序(前序)遍历DLR(根左右)、中序遍历LDR(左根右)、后序遍历LRD(左右根)。dataparentlchildrchilddatarchildlchild1.先序遍历(DLR)的递归过程voidPreorder(BT*T)//先序遍历二叉树BT{if(T==NULL)return;//递归调用的结束条件{printf(T-data);//输出结点的数据域Preorder(T-lchild);//先序递归遍历左子树Preorder(T-rchild);//先序递归遍历右子树}}2.中序遍历(LDR)的递归过程voidInorder(BT*T)//中序遍历二叉树BT{if(T==NULL)return;//递归调用的结束条件{Inorder(T-lchild);//中序递归遍历左子树printf(T-data);//输出结点的数据域Inorder(T-rchild);//中序递归遍历右子树}}3.后序遍历(LRD)的递归过程voidPostorder(BT*T)//后序遍历二叉树BT{if(T==NULL)return;//递归调用的结束条件{Postorder(T-lchild);//后序递归遍历左子树Postorder(T-rchild);//后序递归遍历右子树printf(T-data);//输出结点的数据域}}6.线索二叉树n个结点的二叉链表中有n+1个空指针,可以利用其指向前驱或后继结点,叫线索,同时需附加一个标志,区分是子树还是线索。lchild有左子树,则指向左子树,标志ltag==0;没有左子树,可作为前驱线索,标志ltag==1。rchild有右子树,则指向右子树,标志rtag==0;没有右子树,可作为后继线索,标志rtag==1。7.树和森林树的存储结构双亲表示法,孩子表示法,孩子兄弟表示法。特点:双亲表示法容易求得双亲,但不容易求得孩子;孩子表示法容易求得孩子,但求双亲麻烦;两者可以结合起来使用。孩子兄弟表示法,容易求得孩子和兄弟,求双亲麻烦,也可以增加指向双亲的指针来解决。lchildltagdatartagrchild0/10/1树与二叉树的转换表错误!文档中没有指定样式的文字。.1树和二叉树的对应关系树对应的二叉树根根第一个孩子左孩子下一个兄弟右孩子树的遍历树的结构:①根,②根的子树。先根遍历:①②。例:ABCDEFGHIJK。后根遍历:②①。例:CEDFBHGJKIA。遍历森林森林的结构:①第一棵树的根,②第一棵树的根的子树森林,③其余树(除第一棵外)组成的森林。先序遍历:①②③。例:ABCDEFGHIJ。中序遍历:②①③。例:BDCEAGFIJH。注:先序遍历森林,相当于依次先根遍历每一棵树;中根遍历森林相当于后根遍历每一棵树。遍历树、森林与遍历二叉树的关系遍历树、森林和二叉树的关系树森林二叉树先根遍历先序遍历先序遍历后根遍历中序遍历中序遍历8.哈夫曼树:叶子结点带有权值的最小带权路径长度的最优二叉树构造赫夫曼树每次取两个最小的树组成二叉树ABICDFHGJKEAHBCEGFIJD①①②②③树的结构划分森林的结构划分赫夫曼编码(前缀码)向左分支为0,向右分支为1,从根到叶子的路径构成叶子的前缀编码。五、图1.完全图:有1\2n(n-1)条变得无向图有向完全图:具有n(n-1)条弧的有向图。权:与图的边或弧相关的数。顶点v的度:和v相关联的边的数目。入度:以顶点v为头的弧的数目出度:以顶点v为尾的弧的数目回路或环:第一个顶点和最后一个顶点相同的路径。简单路径:序列中顶点不重复出现的路径。2.图的存储结构·邻接矩阵:·邻接表:typedefstructArcNode{//弧结点intadjvex;//邻接点structArcNode*nextarc;//下一个邻接点}ArcNode;typedefstructVexNode{//顶点结点VertexTypedata;//顶点信息ArcNode*firstarc;//第一个邻接点}VexNode;constin
本文标题:数据结构知识点总结(详细无题目)
链接地址:https://www.777doc.com/doc-4506491 .html