数据结构知识点总结.docx

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

1、精品名师归纳总结数据结构学问点总结绪论时间复杂度 T（n）=O （ f（n）通常用：常量阶 O1 线性阶 On 平方阶 On2对数阶 Ologn 指数阶 O2n运算的复杂性：算法的运算量的大小算法的时间复杂度取决于问题的规模和待处理数据的初态。算法：是对特定 问题求解 步骤的一种描述,它是指令的有限 序列。（1） ）有穷性（ 2 ）确定性（ 3 ）可行性 （ 4）输入（ 5）输出从规律上可以把数据结构分为 线性结构 和非线性结构栈与数据的储备结构无关串是线性结构有序表属于规律结构连续储备设计时,储备单元的的址肯定连续一、数据： 是对客观事物的符号表示, 在运算机科学中是指全部能输入到运算机中并

2、被运算机程序处理的符号的总称。它是运算机程序加工的“原料”。二、数据元素： 是数据的基本单位 ,在运算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由如干个数据项组成。数据项是数据的不行分割的最小单位。三、数据对象：是性质相同的数据元素的集合,是数据的一个子集。四、数据机构： 是相互之间存在一种或多种特定关系的数据元素的集合。 在任何问题中, 数据元素都不是孤立存在的, 而是在它们之间存在着某种关系, 这种数据元素相互之间的关系称为结构。 依据数据元素之间关系的不同特性, 通常有下可编辑资料 - - - 欢迎下载精品名师归纳总结列 4 类基本结构：（ 1 ）集合-数据元素仅有同属一个关

3、系的关系（ 2 ） 线性结构 -结构中数据元素之间存在一个对一个的关系（3 ）树形结构-结构中的数据元素之间存在一个对多个的关系（4）图状结构或网状结构-结构中的数据元素之间存在多个对多个的关系五、元素在存贮结构 （1 ）物理结构（储备结构）：它包括数据元素的表示和关系。（2） ）规律结构六、位 bit ：在运算机中表示信息的最小单位是二进制的一位七、元素 element/节点 node ：位串八、数据域： 当数据元素由如干数据项组成时, 位串中对应于各个数据项的子位串九、数据元素之间的关系在运算机中有两种不同的表示方法, 次序映像和非次序映像,并由此得到两种不同的储备结构： 次序储备结构 （

4、借助元素在储备器中的相对位置来表示数据元素之间的规律关系） 和链式储备结构 （借助指示元素储备的址的指针表示数据元素之间的规律关系） 。算法：是对特定问题求解步骤的一种描述,它是指令的有限序列。（ 1）有穷性（ 2 ）确定性（ 3）可行性（ 4）输入（ 5）输出算法设计要求：（1 ）正确性（ 2）可读性（ 3）健壮性（ 4）效率与低储备量需求线性表：采纳次序储备,便于进行插入和删除的操作次序表的优点：结构紧凑,储备空间利用率高,操作简洁。（储备密度大 ） 缺点：它需要一块连续的存贮空间。可编辑资料 - - - 欢迎下载精品名师归纳总结当线性表的元素总数基本稳固, 且很少进行插入和删除操作, 但

5、要求以最快的速度存取线性表中的元素时,应采纳次序储备结构。如某线性表最常用的操作是 存取任一指定序号的元素和最终进行插入和删除运算,就利用 次序表的储备方式最节约时间。 如某线性表最常用的操作是 在最终一个元素之后插入一个元素和删除一个元素,就采纳 仅有尾指针的单循环链表 的储备方式最节约时间。设一个链表最常用的操作是在末尾插入结点或删除尾结点 , 就利用带头结点的双循环链表 的储备方式最节约时间。 如某表最常用的操作是 在最终一个结点之后插入一个结点或删除最终一个结点,就利用 带头结点的双循环链表的储备方式最节约时间。链表的优点： 在空间的合理利用 上和插入、删除时不需要移动 ,是线性表的首

6、选储备结构。（ 不必事先估量储备空间、所需空间与线性长度成正比）缺点：求线性表的长度时不如次序储备结构（不行随机拜访任一元素 ） 线性表在 次序储备 时,查找第 i 个元素的时间同 i 的值无关。线性表在 链式储备时,查找第 i 个元素的时间同 i 的值成正比。对于次序储备 的线性表, 拜访结点的时间复杂度为O（1 ）,插入和删除结点的时间复杂度为 O （n ）。对于链式储备 的线性表, 拜访第 i 个元素的时间复杂度为O（n ）。对于一个具有 n 个结点的单链表,在已知的结点*p 后插入一个新结点的时间复杂度为 O1 ,在给定值为 x 的结点后插入一个新结点的时间复杂度为On依据线性表的链式

7、储备结构中每一个结点包含的指针个数,将线性链表分为单链表和多重链表。依据指针的连接方式,链表又可分为动态链表和静态链表。链表的头结点的作用： 1. 标识作用 2. 使操作统一 3. 其数据域可写入链表长度,可编辑资料 - - - 欢迎下载精品名师归纳总结或作监视哨。静态链表中指针表示的是 下一个元素的址静态链表能容纳的元素个数的最大数在表定义时就确定了,以后不能增加。静态链表与动态链表在元素的插入、删除上类似,不需做元素的移动。线性表是线性结构的基本形式线性表的规律结构线性表的定义线性结构的特点是数据元素之间是一种线性关系,数据元素“一个接一个的排列”。线性表是具有相同数据类型的 nn=0个数

8、据元素 的有限序列,记为：a1,a2, ai-1 , ai ,ai+1 ,an 。其中： n 为表长, n0 时称为空表。表中相邻元素之间存在次序关系：ai-1称为 ai 的直接前趋, ai+1 称为 ai 的直接后继。a1, an-1 有且仅有一个直接后继。 （非空线性表）a2 , an 有且仅有一个直接前趋。（非空线性表）线性表的次序储备是指在内存中用的址连续的一块储备空间次序存放线性表的各元素,用这种储备形式储备的线性表称其为次序表。储备的特点：物理上的相邻实现了规律相邻的表示。次序储备能随机拜访第i 个元素：可编辑资料 - - - 欢迎下载精品名师归纳总结设 a的储备的址为 Loca

9、,每个数据元素占 d 个储备的址,就第 i 个数据元素的的址为：Loca i =Loca +i-1*d1In次序表插入运算时间主要消耗：数据的移动。一般情形下,在第 i（ 1=i=n）个元素之前插入一个元素时,需将第n 至第 i（共 n-i+1 ）个元素向后移动一个位置。（在第 i 个位置上插入 x,从 ai 到an 都要向下移动一个位置,共需要移动n i 1 个元素。）一般情形下,删除第 i（1=i=n）个元素时,需从第 i+1 至第 n（共 n-i ）个元素向前移动一个位置n 1Einpi ni1i 1n1n 1Einp1i ni1 n1 ni1 n2i 1i 1i 的取值范畴为：1 i

10、n+1 （即有 n 1 个位置可以插入）。设在第 i 个位置上作插入的概率为 Pi：在等概率情形下：Pi=1/ n+1,就平均移动数据元素的次数就为：这说明： 在次序表上做插入操作需移动表中一半的数据元素。明显次序表上插入时间复杂度为 n 。int SeqlistInsertA,n,i,xifin/ 检查插入位置的正确性Printf “参数非法” ;return 0;/ 插入位置参数错,返回错误代码0可编辑资料 - - - 欢迎下载精品名师归纳总结elsefork=n;k=i;k-Ak-1=Ak;/ 结点移动Ai=x;/ 新元素插入n=n+1;/ n指向新的最终元素return n;/ 插入胜

11、利,返回胜利代码线性表的删除运算是指将表中第i 个元素从线性表中去掉。SeqlistDeleteA,n,iifin /检查空表及删除位置的合法性Printf “参数非法” ;return 0; /不存在第 i 个元素,返回错误代码0elsefork=i+1;kn;k+Ak-1=Ak; /数据元素向前移动nnext=p-next; p-next=s;留意：两个指针的操作次序不能交换。在某结点前面插入新结点：设指向链表中某结点,指向待插入的值为x 的新结点,将 *s 插入到 *p的前面。与后插不同的是：第一要找到 *p 的前驱 *q ,然后再完成在 *q 之后插入*s。设单链表头指针为 L,操作如

12、下：q=L;while q-next.=pq=q-next;/ 找*p 的直接前驱s-next=q-next;q-next=s;删除结点：设 p 指向单链表中某结点,删除 *p 。作业 1 ：线性表中元素为整型,以 50 为界,小于 50 在左,大于 50 在右。作业讲解： x=x and ij可编辑资料 - - - 欢迎下载精品名师归纳总结j=j-1;ifAjxAi=Aj; i=i+1;whileAix and xj i=xAj=Ai; jdate=a1;指针 p 指向对象 date=a1 ,该对象是一个结构体,指向结构体里 a1 那部分删除 a1 并把储备空间解放： free （p ）。二

13、、链表的构造q=1;i-可编辑资料 - - - 欢迎下载精品名师归纳总结pdatenext=NULL;把指针设为空指针,替换为 q q=p;考虑链表的头指针当 ai 未插入时： 算法：CreatLinkListn构造链表, n 为节点 q=1;i-pdatenext=q; q=p;returnp;注：此时 p 、q 一样已被赋值给对方可编辑资料 - - - 欢迎下载精品名师归纳总结作业 4 ：倒过来。 从前节点到后节点 。头指针 headp=head;从头指针动身,依次输出节点。可用 for 循环或 while 循环（不确定循环次数时用）pdata; pnext;三、链表的插入算法：假定：在表

14、中值为 x 的节点前面插入一个值为 y 的节点。分析： 1.空链2. 表中第 1 个节点的值为 x3. 表中有一个值为 x 的节点4. 表中没有值为 x 的节点5. 表中有多个值为 x 的节点。可编辑资料 - - - 欢迎下载精品名师归纳总结NODE*InsertLinkListhead,x,yqdatanext=NULL;ifhead=NULL headdate=xq-next=head; head=q;elser=head; pnext;whilep-data=/x and p=NULLpnext;可编辑资料 - - - 欢迎下载精品名师归纳总结ifp=NULLq-nextnextnext

15、=q;returnhead;假定：删除表中值为 x 的节点分析： 1.空表。2. 第 1 个节点的值为 x。3. 在表中有值为 x 的节点。4. 在表中没有值为 x 的节点NODE*=DeleteLinkListhead,x,t（返回指针） a.值参call by valueb. 变参 call可编辑资料 - - - 欢迎下载精品名师归纳总结by addresssdata=xs=head; headnext;elseq=head;（返回内容不同）pnext;whilep-data=x and p-next=NULLq=p;pnext;ifp-data=xsnextnext;可编辑资料 - -

16、- 欢迎下载精品名师归纳总结elseprintf表中没有值为 x 的节点 。ifs=NULLtdata; frees;returnhead;（返回值）四、链式存贮结构的栈 五、链式存贮结构的队列六、循环链表循环链表是另一种形式的链式储备结构。它的特点是表中最终一个结点的指针域指向头结点,整个链表形成一个环。由此,从表中任一结点动身均可找到表中其他结点。双向链表在双向链表的结点中有两个指针域,其一指向直接后继,另一指向直接前驱。二叉链表的特点： n 个结点,就链指针所指的为 n-1二叉链表总链域个数 2n ,头指针指向根结点,其余 n-1 个结点在有n 个结点的 K 叉树链表中,值为非空的链域个

17、数为n-1 。可编辑资料 - - - 欢迎下载精品名师归纳总结空的链域个数为 kn- （ n-1 ）=kn-n+1 对于任意给定的一个线性表： L=a 1 ,a2 , n ,a写出构造一个链表的算法。节点类型及其算法头部商定如下：struct nodeElemTypedata 。struct node*next 。typedef struct nodeNODE 。NODE*CreateLinkListintn算法如下：NODE*CreateLinkListintnqNODE *mallocsizeofNODE; scanf a n ;q - dataan;q - nextNULL; for i

18、=n-1; i -1-; ipNODE *mallocsizeofNODE; scanf a i ;p - dataai;可编辑资料 - - - 欢迎下载精品名师归纳总结p - nextq; qp;return p ;有一个单链表（不同结点的数据域值可能相同） ,其头指针为 head ,编写一个函数运算数据域为 x 的结点个数。链表节点结构定义如下：datanext解：遍历该链表的每个结点,每遇到一个结点,判定其值是否为x,是的话就计数。结点个数储备在变量 n 中。算法如下：intCounterhead,xintn = 0;p data = x n = n + 1;p next;return

19、n ;可编辑资料 - - - 欢迎下载精品名师归纳总结栈和队列栈：限定仅在表尾进行插入或删除栈：是限定仅在表尾进行插入或删除操作的线性表表尾（栈顶）表头（栈底）假设栈 S= （ a1,a2 ,an ）,就称 a1 为栈底元素, an 为栈顶元素。栈中元素按 a1 ,a2,an 的次序进栈,退栈的第一元素应为栈顶元素。 换句话说, 栈的修改是按后进先出的原就进行的 。因此,栈又称为后进后出的线性表。压栈算法： int PushStacks,top,xiftop=SMAXprintfoverlow; return 0;可编辑资料 - - - 欢迎下载精品名师归纳总结elseStop=x;top=t

20、op+;出栈算法：ElemType Popstacks,top,bottomiftop=bottomprintfoverlow;return 0;elsetop=top-1; y 尾指针+1 。删除队列头元素 - 头指针+1头指针始终指向队列头元素可编辑资料 - - - 欢迎下载精品名师归纳总结尾指针始终指向队列尾指针的下一个位置在栈满的情形下,不能作进栈运算,否就产生“上溢” 。队列： 1.什么是队列？也是一种特别的线性表（插入在表的一端, 删除在表的另一端）队列：先进先出区分于线性表：插入、删除在同一端。可编辑资料 - - - 欢迎下载精品名师归纳总结2.队列的操作：1. 插入。判别队列空

21、间“空”或“满”a. 另设一个标志位以区分队列“空”或“满”b. 少用一个元素空间, 商定以“队列头指针在队列尾指针的下一个位置（指环状的下一位置） ”上作为队列呈“满”状态的标志总结：如 RearFront ,元素个数为 Rear-Front 。如 Rear=QMAXprintfOverlow; return 0;可编辑资料 - - - 欢迎下载精品名师归纳总结elserear=rear+1;Qrear=x; return 1;2. 删除：ElemType Queue DeleteQ,front,rearifrear=frontprintfOverlow; return 0;elsefron

22、t=front+1;以上为错误算法 ,rearQMAX才能插入,空队列： rear=front指可编辑资料 - - - 欢迎下载精品名师归纳总结针重叠“假满”删除 / 插入一次无事, N 次就无用了。插入满了只能删除, rear 、front均在尾,插入为满,删除为空成为了无用队列。正确的队列插入与删除算法如下：int Queue InsertQ,front,rear,xifrear+1mod QMAX=frontprintfOverlow; return 0;elsemod QMAX Qrear=x;可编辑资料 - - - 欢迎下载精品名师归纳总结return 1;ElemType Queu

23、e DeleteQ,front,rearifrear=frontprintfOverlow; return 0;elsemod QMAX3. 队列的应用 keyboard buffer 32byte如何解决“假满”？ -仍有空的的方却不能再插入。答：接为环状（上弯下弯不同）总结：优点： 1.不要求连续的、大块的内存,充分的利用内存空间2.动态的储备结构不足： 1.空间复杂度增加2.操作（算法）复杂些可编辑资料 - - - 欢迎下载精品名师归纳总结双端队列：限定插入和删除操作在表的两端进行的线性表。这两端分别是端点1和端点 2。在实际使用中,仍可以有输出受限的双端队列（即一个端点答应插入和删除,

24、 另一个端点只答应插入的双端队列） 和输入受限的双端队列 （即一个端点答应插入和删除,另一个端点只答应删除的双端队列）。而假如限定双端队列从某个端点插入的元素只能从该端点删除,就该双端队列就蜕变成两个栈底相邻接的栈了。链队列：用链表表示的队列。数组和广义表从一给定的数组 A 中删除元素值在 x 到 y（x y ）之间的全部元素（假定数组中有 n 个元素）。算法头部商定如下：可编辑资料 - - - 欢迎下载精品名师归纳总结voidDelete A,n, x, y 此题的算法思想是： 先将 A 中全部元素值在 xy 之间的元素置成一个特别的值（如 0）,并不立刻删除它们, 然后从最终向前依次扫描,

25、 对于该特别值的元素便移动其后面的元素将其删除, 这种算法比每删除一个元素后立刻移动其后元素效率要高一些。实现此题功能的过程如下：voidDelete A,n, x, y for i1;i n;i+ if Ai x&Ai y Ai0;for in;i 1;i- if Ai = 0 for kj;k n-1;k+ AkAk+1;nn - 1;树和二叉树设一棵 Huffman树中度为 2 的节点数为 n 2 ,就该树的总节点数为2n 2+1可编辑资料 - - - 欢迎下载精品名师归纳总结度的概念：结点的度指结点的孩子结点个数,例如度为2 就是有 2 个孩子结点的结点。叶子结点就是度为 0 的结点,

26、没有孩子结点的结点 .依据这个概念,度为 2 的结点树为 n2, 即为非叶子结点, Huffman树中叶子结点个数是非结点个数 +1 ,所以总结点个数： n2+n2+1有一棵非空的二叉树（第 0 层为根结点）,其第 i 层上至多有 2 i 个结点。对于 n 个节点的满二叉树,设叶节点数为m ,分枝节点数为 k ,就 n=k+m满二叉树中,除了叶子结点,就是分支结点。可编辑资料 - - - 欢迎下载精品名师归纳总结将一棵树转换为二叉树表示后 ,该二叉树的根结点没有右子树。可编辑资料 - - - 欢迎下载精品名师归纳总结已知完全二叉树的第八层有 8 个结点,就其叶子结点数是 68 。留意是根结点为

27、第 1 层,第 7 层该有 26=64 个结点, 第八层有 8 个结点用去第7 层的 4 个结点,所以叶子结点总数：64-4+8=68。可编辑资料 - - - 欢迎下载精品名师归纳总结叶子的带权路径长度 = 权值* 路径长度树的带权路径长度 = 全部叶子结点的带权路径长度之和可编辑资料 - - - 欢迎下载精品名师归纳总结已知某二叉树中,有 n0 个叶节点, n 1 个度为 1 的节点, n 2 个度为 2 的节点。就：n 0= n 2+1二叉树采纳次序储备结构（数组形式）和链式储备结构（二叉链表）来储备。高度为 k 的二叉树至多有 2k-1个节点。二叉树节点数目的算法。counter Lsu

28、btree; Numberstree-Rsubtree;设二叉树的根节点的指针为 tree ,每个节点的结构为：LsubtreedataRsubtree试写一算法,用于输出该二叉树中最大的节点值。算法如下：max data max max data;MaxNodetree-Lsubtree; MaxNodetree-Rsubtree;可编辑资料 - - - 欢迎下载精品名师归纳总结或者：max = 0;voidMaxNodeNODE*treeif treex data;y Lsubtree; z Rsubtree; reyurn maxx ,y,z;elsereturn - ;图设有向图 G

29、有 n 个顶点, m 条弧,就其邻接表中链上的节点个数为m如一无向图是连通的,且其中有n 个顶点和 e 条边,就必满意 e n-1有向图强连通重量在有向图 G 中,假如两个顶点vi,vj间（ vivj）有一条从可编辑资料 - - - 欢迎下载精品名师归纳总结vi 到 vj 的有向路径,同时仍有一条从vj 到 vi 的有向路径,就称两个顶点强连通strongly connected。假如有向图 G 的每两个顶点都强连通, 称 G 是一个强连通图。非强连通图有向图的极大强连通子图,称为强连通重量strongly connectedcomponents。记主要特点：强联通重量图中两两都可达,也可 见

30、 下图 实 例 。 按 照 这 个 定义 , 得 到 图 G中的 强 联通 重量 共 3个：,在一个有 n （n 1 ）个顶点的有向图中,边数最多为nn-1带权有向图 G 用邻接矩阵 A 储备,就顶点 i 的入度等于 A 中第 i 列非且非 O的元素个数有向图中,结点i 的入度就是指向i 结点的弧的条数 ,而邻接矩阵是行数据中非 0 非无穷元素个数为 i 的出度, 列才为入度有向图用邻接矩阵表示后,顶点i 的出度等于第 i 行中非 0 且非的元素个数。图的深度优先和广度优先都要弄清晰。深度优先为相连拜访 （留意退回到仍有连接结点没有拜访过的那个结点上,广度优先为层次拜访,先拜访的结点其子树也先

31、拜访（子树拜访无次序,仅对下层拜访有影响）可编辑资料 - - - 欢迎下载精品名师归纳总结广度优先和深度优先遍历序列均可能是不唯独的。查找折半查找算法。可编辑资料 - - - 欢迎下载精品名师归纳总结intBinSearch sqlistr,intk,intn low1 。highn 。find0;while low highandnot find midlow + high / 2 ; if k rmid. key lowmid + 1; else imid;find1;if not find i0;return i ;可编辑资料 - - - 欢迎下载精品名师归纳总结折半查找法使用于储备结构为次序储备且按关键字排好序的线性表。在索引次序表上实现分块查找, 在等概率查找情形下, 其平均查找长度不仅与表的个数有关,而且与每一块中的元素个数有关。可编辑资料 - - - 欢迎下载精品名师归纳总结排序一、插入排序 Insertion Sort在已知待排序文件已基本有序的前提下,效率最高的排序方法是直接插入排序考排序的效率和特点：