2022年《数据结构》知识点.docx

《2022年《数据结构》知识点.docx》由会员分享，可在线阅读，更多相关《2022年《数据结构》知识点.docx（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -第 1 章 绪论 1.1 数据是表示客观事物的符号,是对客观事物的抽象,是信息的载体；对运算机科学而言,经抽象 数字化 后,能被运算机识别、储备和加工处理的客观事物均称作数据； 1.2 具有某种共同属性的数据集合称作数据对象；数据集中的元素称作数据元素,简称元素,又称结点、顶点、记录等；数据对象 =数据元素,数据元素, ,数据元素 1.3 就数据的自身结构而言,分为原子型和结构型,前者是不行分解或无须分解的数据,后者可分解为如干个数据项； 1.4 通常,数据项是无须分解或不行分解的所谓最小数据单位,数据元素是

2、作为整体对待的基本数据单位； 1.5 数据集和其上定义的一组操作合称数据类型,即,数据类型 =数据集 +一组操作 = 数据集,一组操作 明白 狭义地说,数据类型侧重于数据的值,不区分值相同的数据,忽视数据的自身结构；例. 复数类 =复数集,运算集 模和幅角； ,复数集以复数为基本元素,复数由两个数据项组成：实部和虚部或 1.6 数据集和其元素间的一组关系合称数据结构,即, 简 1.7 数据结构 =数据对象 +数据关系 = 数据对象,数据关系 数据结构的抽象描述称作规律结构；规律结构分为：集合结构；线性结构；树形结构称树结构 ；图形结构 简称图结构 ； 1.8 树结构和图结构统称非线性结构； 1

3、.9 数据结构在运算机上的详细实现称作储备结构或物理结构；储备结构分为：次序储备；链式储备；索引储备；散列储备； 1.10 数据结构和其上定义的一组操作的抽象描述合称抽象数据类型,即,抽象数据类型 =数据结构 +基本操作 =数据对象 +数据关系 +基本操作 1.11 求解问题的步骤称作算法,是合法指令的有限序列,具有以下主要特性：有穷性；确定性；可行性； 1.12 算法所用的总时间称作时间复杂度,通常用算法中执行次数最多 频度最高 的操作的执行次数 频度 或数量级表示；时间复杂度又称时间效率,但两者的高低是相反的； 1.13 算法所用最大储备量称作空间复杂度；空间复杂度又称空间效率,但两者的高

4、低是相反的； 1.14 从数量级上说,算法的时间复杂度和空间复杂度与规模 n 的某个函数同级；常见数量级由低到高排列如下：1、logan、n k、a n、n. 、n n k0,a1 对同一个详细问题,数据本身所用储备量与算法无关,通常,空间复杂度只考虑附加储备空间复杂度； 1.15 算法的性能分析主要包括时间复杂度和空间复杂度； 1.16 数据元素间的关系分为有序关系和无序关系；有序关系简称弧 或有向弧、有向边 ,无序关系简称边 或无向弧、无向边 ,分别表为 : 、 元素,元素 或 前驱后继、元素元素 1.17 k 阶斐波那契序列的定义及其化简式；f0=f1= =fk-2 =0,fk-1 =1

5、,nk 时,fn=fn-1+fn-2+ +fn-k 1.18 一元多项式的高效运算式；Pnx=p0+p1x+p2x 2+ +pnx n=p0+xp 1+x Pn-1+xpn 递推算法为： forP=pn,i=n-1;i=0;i-P*=x+=pi; 第 2 章 线性表 2.1 同类型元素的有限序列称作线性表；简记为a 1,a 2, ,a n 或 a 1,a 2, ,a n 或 第 1 页,共 9 页 - - - - - - - - - ai |i=1,2, ,n,|i=1,2, ,n-1 2.2 线性表中元素的个数称作表长,表长为0 的线性表称作空表； 2.3 在线性表中,第一个元素称作首元,它

6、没有前驱,其它元素均有唯独前驱；最终一个元素称作尾元,它没有后继,其它元素均有唯独后继；线性表的这种关系称作一对一关系,记作1:1 ；例. 既有首元又有尾元的线性表的表长1,某元素既有前驱又有后继的线性表的表长3； 2.5 用连续的一片储备空间依次次序存放线性表的元素,称作线性表的次序储备,简称次序表；细心整理归纳 精选学习资料 - - - - - - - - - - - - - - -名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -次序表中规律相邻者的储备位置也相邻；次序表有三个要素：基址；表长 或尾元下标 ；预留表长 或最大下标 ；假如次序表的预留表长

7、是常量,可用一般数组储备 称作静态次序表,只有两个要素 ,否就,用动态数组储备 称作动态次序表 ；对于次序表,附加储备空间复杂度为 O1 ,插入、删除、查找操作的时间复杂度为 On ,其它基本操作的时间复杂度均为 O1 ； 2.6 附加“ 链” 将规律相邻数据元素的储备位置链接起来的储备结构称作链式储备；链式储备的线性表称作线性链表,简称链表；附加一个链的线性链表称作单链表；习惯上,链域指向其后继；单链表中第一个结点的地址称作头指针；作为线性链表首元的形式前驱的附加结点称作头结点；对于单链表,附加储备空间复杂度为 On ,初始化操作的时间复杂度为 O1 ,其它基本操作的时间复杂度均为 On ；

8、 2.7 静态次序表的详细实现储备结构 插入操作的核心步骤typedef struct/ 用静态数组储备的次序表 forj=L-last+;j=i-1;j-/ 后移int last;/ 尾元下标 表长 -1 L-dataj+1=L-dataj; DataType dataMAX;/MAX 为最大表长 常量 L-datai-1=x;/ 插入 x SeqList; 留意后移次序：从后向前逐个后移；初始化操作的核心步骤 删除操作的核心步骤SeqList *p=new SeqList; forj=i;jlast;j+/ 前移p-last=-1; L-dataj-1=L-dataj; L-last-;/

9、 修改表长留意前移次序：从前向后逐个前移； 2.8 单链表的详细实现返回数据元素x 地址的核心步骤 第 2 页,共 9 页 结点的储备结构typedef struct node/结点结构whileL&L-data.=xL=L-next; DataType data;/数据域return L; struct node *next;/指针域附加头结点时,改为：Lnode,*LinkList;/结点及结点的地址whileL=L-next&L-data.=x; 附加头结点初始化操作的核心步骤返回数据元素x 序号的核心步骤Lnode *L=new Lnode; int j=1; L-next=0; wh

10、ileL&L-data.=xL=L-next,j+; 求表长操作的核心步骤return L.j:0; forint j=0;L;L=L-nextj+; 附加头结点时,改为：return j; whileL=L-next&L-data.=xj+; 附加头结点时,j的初值改为 -1 或返回值改为清空操作的核心步骤j-1或Lnode *p; int j=0; whileL=L-nextj+; whilep=LL=L-next; delete p; 在结点 p 之后插入元素x 的核心步骤另外,调用后需补上语句：s=new Lnode; L=0; s-data=x; 附加头结点时,改为：s-next=p

11、-next; p-next=s; whilep=L-nextL=p-next; delete p; 删除结点p 后继的核心步骤某些操作的递归算法s=p-next; 求表长p-next=s-next; delete s; return L.1+LenL-next:0; 返回第 i 个元素地址的核心步骤清空forint j=1;jnextj+; ifLClearL-next; return i1|.L.0:L; delete L; 附加头结点时,j 的初值改为0 或int j=1; whilejnextj+; 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - -

12、- - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -第 3 章 栈和队列 3.1 只许一端插入和删除的线性表称作栈,此端称作栈顶,另一端称作栈底； 3.2 栈具有先进后出的特点 FILO ,即,后进先出的特点 LIFO ； 3.3 由入栈序列“ 前 中 后 ” 不行能得到出栈序列“ 后 前 中 ” ； 3.4 只许一端插入、另端删除的线性表称作队列,答应删除的一端称作队首,另端称作队尾； 3.5 队列具有先进先出的特点 FIFO ,即,后进后出的特点 LILO ；出队序列和入队序列相同； 3.6 次序储备的栈简称次序栈；通常

13、,次序栈以表尾作为栈顶；储备结构 栈满的条件：s-top+1=MAX typedef struct/ 静态次序栈 入栈的核心步骤int top;/ 栈顶下标 或栈长 s-data+s-top=x; DataType dataMAX; 出栈的核心步骤SeqStack; return &s-datas-top-; 初始化的核心步骤 或 return s-datas-top-; Stack *s=new SeqStack; 或 x=&s-datas-top-; s-top=-1; 或 x=s-datas-top-; 栈空的条件：s-top=-1; 3.7 链式储备的栈简称链栈；通常,链栈以表头作为栈

14、顶；结点储备结构 p-next=s; s=p; typedef struct node 出栈的核心步骤DataType data; Stack p=s; s=p-next; struct node *next; *x=p-data; delete p; StackNode,*LinkStack; 清空操作栈空的条件：.L 或 L=0 Stack p; 入栈的核心步骤 whilesp=s; s=s-next; delete p; LinkStack p=new StackNodex; 3.8 由“ 入栈序列” 、“ 出栈序列” 、“ 栈操作序列” 中的任意两项可确定另一项；例. 习题 3-2 ；

15、 3.9 对于双目运算,运算符在两个操作数之前的表达式称作波兰式或前缀表达式；同理,可定义逆波兰式 或后缀表达式 ；例. 运算 4 3 + 2 1 * -和- + 4 3 * 2 1；第 4 章 串 4.1 字符串简称串；串中一段连续字符称为该串的子串；串是其子串的主串；0； 4.2 子串的第一个字符在主串中的序号称作子串在主串中的位置,并商定,非子串的位置是 4.3 查找一个串在另一串的位置简称串定位,或模式匹配,被查找的串又称模式串； 4.4 附加终止标志的定长次序储备结构为：typedef char StringMAX+1; 通常,终止标志为空字符0；j=1 时 其它情形 4.4 内嵌串

16、长的定长次序储备结构为：typedef char StringMAX+1;/s0的值为串长 4.5 KMP算法中 next 函数的运算公式为：0 nextj= maxk|1kj且t1 t k-1=tn t j-1 1 明显, next1=0,next2=1； 4.6 next函数的算法为：void NextString t,int next int i=1,j=0; next1=0; whilei0 的深度 h=log 2n+1 ；推论： n 个结点二叉树深度为 log 2n+1 n；性质 5：对于具有 n 个结点的完全二叉树,假如按层次遍历从 1 开头编号,就对编号为 i 的结点有：假如 i

17、1 ,其双亲编号为 i/2；假如 2i n,其左孩子编号为 2i ；假如 2i+1 n,其右孩子编号为 2i+1 ；假如从 0 开头编号,就对编号为 i 的结点有：双亲编号为 i-1/2、左孩子编号为 2i+1 、右孩子编号为 2i+2 ； 6.10 空树和 1 个结点的二叉树只有1 种形状, 2 个结点的二叉树有2 种形状, 3 个结点的二叉树有5细心整理归纳 精选学习资料 第 4 页,共 9 页 - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -种形状；明白：

18、 n 个结点二叉树有 C2n,n/n+1 种形状 6.11 先序遍历二叉树 根左右 ：拜访根结点；先序遍历左子树；先序遍历右子树；先序遍历又称前序遍历； 6.12 中序遍历二叉树 左根右 ：中序遍历左子树；拜访根结点；中序遍历右子树； 6.13 后序遍历二叉树 左右根 ：后序遍历左子树；后序遍历右子树；拜访根结点； 6.14 由中序和先序 或后序、层序 可唯独确定二叉树； 6.15 由中序和先序确定二叉树的步骤为：由先序确定根；结合中序得左、右子树的中序和先序；对非空左、右子树重复和 递归 ；同理可得,由中序和后序 或层序 确定二叉树的步骤；例如,习题 6.8-6.10； 6.16 二叉树的次

19、序储备是指,用数组储备二叉树的结点,并使父子关系表达在储备位置中； 6.17 二叉树的二叉链表储备附加两个指针,分别指向左、右孩子；结点的储备结构 先序遍历的算法typedef struct Node void PreOrderBiTree t/ 先序输出结点的值DataType d;/ 数据 if.treturn;/ 空树struct Node *left,*right;/ 指向左、右孩子 coutd;/ 输出结点的值Node,*BiTree; PreOrdert-left;/ 先序遍历左子树求树深的算法 PreOrdert-right;/ 先序遍历右子树int DepthBiTree t/

20、 求树深 int i,j; 中序遍历的算法if.treturn 0;/ 空树 void InOrderBiTree t/ 中序输出结点的值i=Deptht-left;/ 左子树深度 if.treturn;/ 空树j=Deptht-right;/ 右子树深度 InOrdert-left;/ 中序遍历左子树returnij . i:j+1; coutd;/ 输出结点的值 InOrdert-right;/ 中序遍历右子树求结点数的算法 int NodeBiTree t/ 求结点数 后序遍历的算法if.treturn 0;/ 空树 void PostOrderBiTree t/ 后序输出结点的值ret

21、urn 1+Nodet-left+Nodet-right; if.treturn;/ 空树 PostOrdert-left;/ 后序遍历左子树求叶子数的算法 PostOrdert-right;/ 后序遍历右子树int LeafBiTree t/ 求叶子数 coutd;/ 输出结点的值if.treturn 0;/ 空树 if.t-left&.t-right/ 仅有根结点 清空的算法return 1; void ClearBiTree t/ 清空return Leaft-left+Leaft-right; if.treturn;/ 空树 Cleart-left;/ 清空左子树Cleart-righ

22、t;/ 清空右子树delete t; t=0;/ 释放根 6.18 在加权叶子相同的二叉树中,根到全部叶子的加权路径长度之和 WPL最小的二叉树称作最优二叉树,又称赫夫曼 Huffman 树； 6.21 哈夫曼编码的构造步骤为：以字符的使用概率为权,构造哈夫曼树；在哈夫曼树中每对边上分别标记 0 和 1；以根到叶子路经上的标记序列作为相应字符的编码； 6.22 哈夫曼编码的性质有：平均编码长度最短；属前缀编码任一字符编码都不会是其它字符编码的前缀； 6.23 在二叉链式储备的非空二叉树中,空指针域比结点多一个；把这些空指针改造为指向所需遍历的前驱和后继,称作线索化,改造的指针称作线索,改造后的

23、二叉树称作线索二叉树；细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 5 页,共 9 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -第 7 章 树和森林 7.1 空表称作空树；假如 T1,T 2, ,T n 是不相交树、 R是单元素,就称 R,T 1,T 2, ,T n也是树； 7.2 对于非空树 R,T1,T2, ,Tn ,称 R是根结点或根元素,简称根,称 T1,T2, ,Tn为子树； 7.3 在树中,根无前驱,其它结点均有唯独前驱；树的这一特性称作一对多关系,简记为

24、 1:n ； 7.4 区分父子方向的树称有向树,否就称无向树；区分子树次序的树称有序树,否就称无序树； 7.5 有限棵不相交树的集合称作森林； 7.6 二叉树的相关概念：结点的度、树的度、叶子、支点、孩子、双亲、兄弟、结点的层、树的深度、祖先、子孙； 7.7 孩子兄弟表示法附加两个链域,分别指向长子和下一个兄弟；孩子兄弟表示法的结点与二叉链表相像,但链域的含义不同；结点结构求树深的算法求树深typedef struct Node int DepthCSTree T/DataType d;/数据int i,j=0; 空树struct Node *c,*s;/指向长子和下一兄弟if.Treturn

25、 0;/Node,*CSTree; i=1+DepthT-c;/本树深度求叶子数的算法j=DepthT-s;/其它兄弟树深度int LeafCSTree T/求叶子数returnij.i:j; if.Treturn 0;/空树 if.T-creturn 1+LeafT-s;/本身是叶子return LeafT-c+LeafT-s;/本身是支点 7.8 树与二叉树的转换 孩子兄弟表示法 ；树所对应的二叉树没有右子树； 7.9 森林与二叉树的转换步骤为：将森林中的每棵树转换成相应的二叉树；后一棵二叉树作为前一棵二叉树的右子树； 7.10 树的层次遍历：由上至下、从左至右； 7.11 树的先根遍历：

26、拜访根；从左至右先根遍历各子树； 7.12 树的后根遍历：从左至右后根遍历各子树；拜访根； 7.13 树的先根遍历与对应二叉树的先序遍历相同,后根遍历与对应二叉树的中序遍历相同； 7.14 森林的前序遍历：从左至右先根遍历每棵树； 7.15 森林的中序遍历：从左至右后根遍历每棵树； 7.16 森林的前序遍历与对应二叉树的前序相同,中序遍历与对应二叉树的中序相同；第 8 章 图 8.1 图由顶点集 V数据集 和边集 E关系集 两个要素组成,简记为 V,E ；对于简洁图,关系集 E是V V=|x,yV的子集； 8.2 图的相关概念：无向图、有向图、完全有向图、完全无向图、入度、出度、度、路径、路径

27、长度、网、加权路径长度、连通图； 8.3 n 个顶点的无向完全图有nn-1/2条边； n 个顶点的有向完全图有nn-1 条弧；有向图中全部结点的入度之和、出度之和均等于边数；图中全部结点的度之和均等于边数的两倍； 8.4 图、网的邻接矩阵；wij E 顶点 j 的入度aij =1 E aij =0 E E 8.5 图的邻接矩阵次序储备；ifG.aijk+; 储备结构typedef struct return k; int n,e;/当前顶点数和边数 VertexType vMax;/顶点数组求结点入度的算法bool aMaxMax;/邻接矩阵int IDegreeMGraph G,int j/

28、MGraph; ifj=G.nreturn -1; 第 6 页,共 9 页 求结点出度的算法forint k=0,i=0;iG.n;i+ int IDegreeMGraph G,int i/顶点 i 的入度ifG.aijk+; ifi=G.nreturn -1; return k; forint k=0,j=0;jG.n;j+ 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -增加顶点的算法forint i=0;in&G-vi.=v;i

29、+ void InsertVexMGraph *G,VertexType v ifi=G-nthrow;/无此顶点ifG-n=Maxthrow;/顶点数组已满forint j=0;jn&G-vj.=w;j+ forint i=0;in;i+ ifj=G-n|i=jthrow;/无此顶点或无效边ifG-vi=vreturn;/顶点已存在G-aij=1; G-e+; G-vG-n+=v; 为“删除边的算法增加边的算法把增加边中的“G-aij=1; G-e+;”改void InsertArcMGraph *G, G-aij=0; G-e-; ” ；VertexType v,VertexType w

30、8.6 邻接表每个顶点附加一个链表,将其全部后继的位置 下标或地址 链接起来； 8.7 逆邻接表每个顶点附加一个链表,将其全部前驱的位置 下标或地址 链接起来； 8.8 图的深度优先搜寻 遍历 步骤为：拜访指定或任意起始顶点；以各出端为新的起始顶点做深度优先遍历；假如尚有未遍历的其它连通重量,就从指定或任意起始顶点动身重复和； 8.9 图的广度优先搜寻 遍历 步骤为：拜访指定或任意起始顶点 第一层 ；拜访前一层各顶点的全部出端；假如尚有未遍历的其它连通重量,就从指定或任意起始顶点动身重复和； 8.10 通常,图的遍历操作需附加一个数据用于标识结点是否已被拜访过；深度优先搜寻需借助栈或采纳递归算

31、法；广度优先搜寻需借助队列； 8.11 含图中全部顶点的微小连通子图称作生成树； 8.12 有生成树的图是连通图；对于 n 个顶点的图,其生成树均有 n 个结点和 n-1 条边； 8.13 在连通网中,生成树上权之总和称作该生成树的权,权最小的生成树称作最小生成树； 8.14 构造连通网 V,E 的最小生成树 TV,TE 的 Prim 算法为：置 TE为空, TV取 V 中任一顶点；当 V-TV 不空时,重复执行：在 TV和 V-TV 之间找权最小的边 v,u,把 u 和v,u 加入 TV,TE ； 8.15 构造连通网 V,E 的最小生成树 TV,TE 的 Kruskal 算法为：置 TE为

32、空, TV=V；重复执行 n-1 次：在与 TV,TE 不构成回路的边中找一条权最小的边 v,u ,将其加入 TE； 8.16 从一个源点求其到它各点最短路径的迪杰斯特拉 Dijkstra 算法：从指定的源点动身,逐个找出当前所能到达的最近点； 8.17 求最短路径的弗洛伊德Floyd算法的原理：除了已找到的最短路径外,其它路径中最短者也是最短路径； 8.18 最短路径中的部分路径也是相应的最短路径；两条首尾相连最短路径未必合成最短路径； 8.19 对于有向无环图,不违返序关系的遍历均称作拓朴排序；第 9 章 查找 9.1 数据元素中用于标识该元素的某个数据项或某些数据项的组合称为关键码或关键

33、字,能唯独标识数据元素的关键码称为主关键码,不能唯独标识数据元素的关键码称为次关键码； 9.2 在查找胜利的前提下,按主关键码查找的结果唯独,按次关键码查找的结果可能不唯独； 9.3 查找操作的范畴称作查找表,查找表中的数据元素又称记录； 9.4 整体结构不变的查找表称作静态查找表,否就称作动态查找表；静态查找表答应修改数据； 9.5 在查找中,关键码的平均比较次数称作平均查找长度,简记为 ASL； 9.6 次序查找针对线性表,又称线性查找；从线性表的一端到另一端逐个比较给定值与关键码； 9.7 使用哨兵的次序查找算法为：int SearchST T,KeyType k T.d0.key=k;

34、/0 单元存哨兵forint i=T.n; T.di.key.=k; i-; return i;/ 返回序号 失败为 0 9.8 对于次序查找,失败时,关键码比较n+1 次；胜利且等概率查找时,ASL=n+1/2=On ； 第 7 页,共 9 页 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - - 9.9 二分查找要求查找表中的元素按关键字有序排列 有序表 ； 9.10 折半查找算法为：int SearchST T,KeyType k int mid,low=0;high=T.n-1;/ 初始区间whilelow=high mid=low+high/2;/ 中点ifk=T.dmid.keyreturn mid+1;/ 胜利ifkT.dmid.keyhigh=mid-1;/ 排除右侧else low=mid+1;/ 排除左侧 return 0;/ 失败