数据结构知识点总结

1、数据结构知识点总结绪论时间复杂度t（n）=o（f（n）通常用：常量阶o(1)线性阶o(n)平方阶o(n2)对数阶o(logn)指数阶o(2n)计算的复杂性：算法的计算量的大小算法的时间复杂度取决于问题的规模和待处理数据的初态。算法：是对特定问题求解步骤的一种描述，它是指令的有限序列。（1）有穷性（2）确定性（3）可行性（4）输入（5）输出从逻辑上可以把数据结构分为线性结构和非线性结构栈与数据的存储结构无关串是线性结构有序表属于逻辑结构连续存储设计时，存储单元的地址一定连续一、数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。它是计算机程序加工的

2、“原料”。二、数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。三、数据对象：是性质相同的数据元素的集合，是数据的一个子集。四、数据机构：是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构。根据数据元素之间关系的不同特性，通常有下列4类基本结构：（1）集合-数据元素仅有同属一个关系的关系（2）线性结构-结构中数据元素之间存在一个对一个的关系（3）树形结构-结构中的数据元素之间存在一个对多个的关系（4）

3、图状结构或网状结构-结构中的数据元素之间存在多个对多个的关系五、元素在存贮结构（1）物理结构（存储结构）：它包括数据元素的表示和关系。（2）逻辑结构六、位bit：在计算机中表示信息的最小单位是二进制的一位七、元素element/节点node：位串八、数据域：当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串九、数据元素之间的关系在计算机中有两种不同的表示方法，顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构（借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系）和链式存储结构（借助指示元素存储地址的指针表示数据元素之间的逻辑关系）。算法：是对特定问题求解步骤的一种

4、描述，它是指令的有限序列。（1）有穷性（2）确定性（3）可行性（4）输入（5）输出算法设计要求：（1）正确性（2）可读性（3）健壮性（4）效率与低存储量需求-线性表：采用顺序存储，便于进行插入和删除的操作顺序表的优点：结构紧凑，存储空间利用率高，操作简单。（存储密度大） 缺点：它需要一块连续的存贮空间。当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用顺序存储结构。若某线性表最常用的操作是存取任一指定序号的元素和最后进行插入和删除运算，则利用顺序表的存储方式最节省时间；若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除一个元素，则采用

5、仅有尾指针的单循环链表的存储方式最节省时间。设一个链表最常用的操作是在末尾插入结点或删除尾结点，则利用带头结点的双循环链表的存储方式最节省时间。若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则利用带头结点的双循环链表的存储方式最节省时间。链表的优点：在空间的合理利用上和插入、删除时不需要移动，是线性表的首选存储结构。（不必事先估计存储空间、所需空间与线性长度成正比）缺点：求线性表的长度时不如顺序存储结构（不可随机访问任一元素）线性表在顺序存储时，查找第i个元素的时间同i的值无关；线性表在链式存储时，查找第i个元素的时间同i的值成正比。对于顺序存储的线性表，访问结点的时间

6、复杂度为o（1），插入和删除结点的时间复杂度为o（n）。对于链式存储的线性表，访问第i个元素的时间复杂度为o（n）。对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为o(1)，在给定值为x的结点后插入一个新结点的时间复杂度为o(n)根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分为单链表和多重链表；根据指针的连接方式，链表又可分为动态链表和静态链表。链表的头结点的作用：1.标识作用2.使操作统一3.其数据域可写入链表长度，或作监视哨。静态链表中指针表示的是下一个元素地址静态链表能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。静态链表与动态链表

7、在元素的插入、删除上类似，不需做元素的移动。线性表是线性结构的基本形式线性表的逻辑结构线性表的定义 线性结构的特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。 线性表是具有相同数据类型的n(n=0)个数据元素的有限序列，记为：(a1，a2， ai-1，ai，ai+1，an)； 其中：n为表长， n0 时称为空表。 表中相邻元素之间存在顺序关系： ai-1 称为ai的直接前趋，ai+1称为ai的直接后继。 a1， an-1有且仅有一个直接后继；（非空线性表） a2， an有且仅有一个直接前趋。（非空线性表） 线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元

8、素，用这种存储形式存储的线性表称其为顺序表。存储的特点：物理上的相邻实现了逻辑相邻的表示。顺序存储能随机访问第i个元素： 设 a的存储地址为loc(a)，每个数据元素占d个存储地址，则第i个数据元素的地址为： loc(ai)=loc(a)+(i-1)*d 1in 顺序表插入运算时间主要消耗：数据的移动。 一般情况下，在第i（1=i=n）个元素之前插入一个元素时，需将第n至第i（共n-i+1）个元素向后移动一个位置。 （在第i个位置上插入 x ，从 ai 到 an 都要向下移动一个位置，共需要移动 ni1个元素。）一般情况下，删除第i（1=i=n）个元素时，需从第i+1至第n（共n-i）个元素向

9、前移动一个位置 i 的取值范围为 ：1 i n+1（即有 n1个位置可以插入）。 设在第i个位置上作插入的概率为pi：在等概率情况下：pi=1/ (n+1) ，则平均移动数据元素的次数则为： 这说明：在顺序表上做插入操作需移动表中一半的数据元素。 显然顺序表上插入时间复杂度为(n)。int seqlistinsert(a,n,i，x)if(in) /检查插入位置的正确性printf(“参数非法”);return 0; /插入位置参数错，返回错误代码0elsefor(k=n;k=i;k-)ak-1=ak; /结点移动ai=x; /新元素插入n=n+1; / n指向新的最后元素return n;

10、/插入成功，返回成功代码线性表的删除运算是指将表中第 i 个元素从线性表中去掉。seqlistdelete(a,n,i)if(in) /检查空表及删除位置的合法性printf(“参数非法”);return 0; /不存在第i个元素，返回错误代码0elsefor(k=i+1;kn;k+)ak-1=ak; /数据元素向前移动nnext=p-next;p-next=s;注意：两个指针的操作顺序不能交换。在某结点前面插入新结点： 设指向链表中某结点，指向待插入的值为x的新结点，将*s插入到*p的前面。与后插不同的是：首先要找到*p的前驱*q，然后再完成在*q之后插入*s。 设单链表头指针为l，操作如下

11、：q=l;while (q-next!=p) q=q-next; /找*p的直接前驱s-next=q-next; q-next=s;删除结点：设p指向单链表中某结点，删除*p。作业1：线性表中元素为整型，以50为界，小于50在左，大于50在右。作业讲解：x=x and ij) j=j-1; if(ajx) ai=aj; i=i+1;while(aix and xj)i=x)aj=ai;jdate=a1;指针p指向对象date=a1，该对象是一个结构体，指向结构体里a1那部分 删除a1并把存储空间解放：free（p）；二、链表的构造q=1;i-)pdatenext=null;把指针设为空指针，替

12、换为qq=p;考虑链表的头指针当ai未插入时：算法：creatlinklist(n) 构造链表，n为节点q=1;i-)pdatenext=q;q=p;return(p);注：此时p、q一样已被赋值给对方作业4：倒过来。从前节点到后节点。头指针head p=head;从头指针出发，依次输出节点。可用for循环或while循环（不确定循环次数时用）pdata);pnext;三、链表的插入算法：假定：在表中值为x的节点前面插入一个值为y的节点。分析：1.空链2.表中第1个节点的值为x3.表中有一个值为x的节点4.表中没有值为x的节点5.表中有多个值为x的节点。node*insertlinklist(

13、head,x,y)qdatanext=null;if(head=null)headdate=x)q-next=head;head=q; elser=head;pnext;while(p-data=/x and p=null)pnext;if(p=null)q-nextnextnext=q;return(head); 假定：删除表中值为x的节点分析：1.空表； 2.第1个节点的值为x； 3.在表中有值为x的节点； 4.在表中没有值为x的节点node *=deletelinklist(head,x,t) （返回指针）a.值参 call by value b.变参call by addresssda

14、ta=x)s=head;headnext;elseq=head; （返回内容不同）pnext;while(p-data=x and p-next=null)q=p;pnext;if(p-data=x)snextnext;elseprintf(表中没有值为x的节点)；if(s=null)tdata;free(s);return(head); （返回值）四、链式存贮结构的栈五、链式存贮结构的队列六、循环链表循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到表中其他结点。双向链表在双向链表的结点中有两个指针域，其一指

15、向直接后继，另一指向直接前驱。二叉链表的特征：n个结点，则链指针所指的为n-1二叉链表总链域个数2n，头指针指向根结点，其余n-1个结点在有n个结点的k叉树链表中，值为非空的链域个数为n-1； 空的链域个数为kn-（n-1）=kn-n+1对于任意给定的一个线性表：l=(a1,a2,an),写出构造一个链表的算法。节点类型及其算法头部约定如下：struct node elemtype data； struct node *next； ； typedef struct node node；node *createlinklist(int n)算法如下：node *createlinklist(in

16、t n) q (node *)malloc(sizeof(node);scanf( an );q - data an;q - next null;for (i=n-1; i1; i-) p (node *)malloc(sizeof(node);scanf( ai );p - data ai;p - next q; q p;return ( p ); 有一个单链表（不同结点的数据域值可能相同），其头指针为head，编写一个函数计算数据域为x的结点个数。链表节点结构定义如下：datanext解：遍历该链表的每个结点，每遇到一个结点，判断其值是否为x，是的话就计数。结点个数存储在变量n中。算法如下

17、：int counter(head, x) int n = 0; p data = x )n = n + 1; p next; return ( n ); -栈和队列栈：限定仅在表尾进行插入或删除栈：是限定仅在表尾进行插入或删除操作的线性表表尾（栈顶） 表头（栈底）假设栈s=（a1，a2，an），则称a1为栈底元素，an为栈顶元素。栈中元素按a1，a2，an的次序进栈，退栈的第一元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈又称为后进后出的线性表。压栈算法：int pushstack(s,top,x)if(top=smax)printf(overlow);return

18、0;elsestop=x;top=top+;出栈算法：elemtype popstack(s,top,bottom)if(top=bottom)printf(overlow);return 0;elsetop=top-1;y尾指针+1；删除队列头元素-头指针+1头指针始终指向队列头元素尾指针始终指向队列尾指针的下一个位置在栈满的情况下，不能作进栈运算，否则产生“上溢”。队列：1.什么是队列？也是一种特殊的线性表（插入在表的一端，删除在表的另一端）队列：先进先出区别于线性表：插入、删除在同一端。2.队列的操作：1.插入。判别队列空间“空”或“满” a.另设一个标志位以区别队列“空”或“满”b.少

19、用一个元素空间，约定以“队列头指针在队列尾指针的下一个位置（指环状的下一位置）”上作为队列呈“满”状态的标志总结：若rearfront，元素个数为rear-front；若rear=qmax)printf(overlow);return 0;elserear=rear+1;qrear=x;return 1;2.删除：elemtype queue delete(q,front,rear)if(rear=front)printf(overlow);return 0;elsefront=front+1;以上为错误算法,rearqmax才能插入，空队列：rear=front指针重叠“假满”删除/插入一次

20、无事，n次则无用了。插入满了只能删除，rear、front均在尾，插入为满，删除为空成为了无用队列。正确的队列插入与删除算法如下：int queue insert(q,front,rear,x)if(rear+1)mod qmax=front)printf(overlow);return 0;elsemod qmaxqrear=x;return 1;elemtype queue delete(q,front,rear)if(rear=front)printf(overlow);return 0;elsemod qmax3.队列的应用keyboard buffer 32byte如何解决“假满”？

21、-还有空的地方却不能再插入。答：接为环状（上弯下弯不同）总结：优点：1.不要求连续的、大块的内存，充分地利用内存空间 2.动态的存储结构不足：1.空间复杂度增加 2.操作（算法）复杂些双端队列：限定插入和删除操作在表的两端进行的线性表。这两端分别是端点1和端点2。在实际使用中，还可以有输出受限的双端队列（即一个端点允许插入和删除，另一个端点只允许插入的双端队列）和输入受限的双端队列（即一个端点允许插入和删除，另一个端点只允许删除的双端队列）。而如果限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变成两个栈底相邻接的栈了。链队列：用链表表示的队列。-数组和广义表从一给定的数组a

22、中删除元素值在x到 y（xy）之间的所有元素（假定数组中有n个元素）。算法头部约定如下：void delete( a, n, x, y )本题的算法思想是：先将a中所有元素值在xy之间的元素置成一个特殊的值（如0），并不立即删除它们，然后从最后向前依次扫描，对于该特殊值的元素便移动其后面的元素将其删除，这种算法比每删除一个元素后立即移动其后元素效率要高一些。实现本题功能的过程如下：void delete( a, n, x, y ) for ( i1; i n; i+ ) if ( ai x & ai y ) ai 0; for ( in; i 1; i- ) if ( ai = 0 ) for

23、 ( kj; k (n-1); k+ ) ak ak+1; n n - 1; -树和二叉树设一棵huffman树中度为2的节点数为n2，则该树的总节点数为2n2+1度的概念：结点的度指结点的孩子结点个数，例如度为2 就是有2个孩子结点的结点；叶子结点就是度为0的结点，没有孩子结点的结点.按照这个概念，度为2的结点树为n2,即为非叶子结点，huffman树中叶子结点个数是非结点个数+1，所以总结点个数：n2+n2+1有一棵非空的二叉树（第0层为根结点），其第i层上至多有2i个结点。对于n个节点的满二叉树，设叶节点数为m，分枝节点数为k，则n=k+m满二叉树中，除了叶子结点，就是分支结点。将一棵树

24、转换为二叉树表示后,该二叉树的根结点没有右子树。已知完全二叉树的第八层有8个结点，则其叶子结点数是68。注意是根结点为第1层，第7层该有26=64个结点，第八层有8个结点用去第7层的4个结点，所以叶子结点总数：64-4+8=68。叶子的带权路径长度=权值*路径长度树的带权路径长度=所有叶子结点的带权路径长度之和已知某二叉树中，有n0个叶节点，n1个度为1的节点，n2个度为2的节点。则： n0= n2+1二叉树采用顺序存储结构（数组形式）和链式存储结构（二叉链表）来存储。高度为k 的二叉树至多有2k-1个节点。二叉树节点数目的算法。counter lsubtree); numbers(tree-

25、rsubtree); 设二叉树的根节点的指针为tree，每个节点的结构为：lsubtreedatarsubtree试写一算法，用于输出该二叉树中最大的节点值。算法如下： max data max) max data; maxnode(tree-lsubtree); maxnode(tree-rsubtree); 或者： max = 0; void maxnode(node *tree) if (tree) x data; y lsubtree); z rsubtree); reyurn (max(x，y，z); else return (-); -图设有向图g有n个顶点，m条弧，则其邻接表中链

26、上的节点个数为m若一无向图是连通的，且其中有n个顶点和e条边，则必满足en-1有向图强连通分量在有向图g中，如果两个顶点vi,vj间（vivj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图g的每两个顶点都强连通，称g是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量(strongly connected components)。记主要特征：强联通分量图中两两都可达，也可见下图实例。按照这个定义，得到图g 中的强联通分量共3个： ,在一个有n（n1）个顶点的有向图中，边数最多为n(n-1)

27、带权有向图g用邻接矩阵a存储，则顶点i的入度等于a中第i列非且非o的元素个数有向图中，结点i的入度就是指向 i结点的弧的条数,而邻接矩阵是行数据中非0非无穷元素个数为i的出度，列才为入度有向图用邻接矩阵表示后，顶点i的出度等于第i行中非0且非的元素个数。图的深度优先和广度优先都要弄清楚。深度优先为相连访问（注意退回到还有连接结点没有访问过的那个结点上，广度优先为层次访问,先访问的结点其子树也先访问（子树访问无次序，仅对下层访问有影响）广度优先和深度优先遍历序列均可能是不唯一的。-查找折半查找算法。int binsearch (sqlist r, int k, int n ) low 1；hig

28、h n；find 0; while ( low high and not find ) mid (low + high) / 2 ; if (k rmid. key ) low mid + 1; else i mid; find 1; if ( not find ) i 0; return ( i ); 折半查找法使用于存储结构为顺序存储且按关键字排好序的线性表。在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表的个数有关，而且与每一块中的元素个数有关。-排序在已知待排序文件已基本有序的前提下，效率最高的排序方法是直接插入排序考排序的效率和特点：一、插入排序(inserti

29、on sort)1. 基本思想：每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。2. 排序过程： 【示例】：初始关键字 49 38 65 97 76 13 27 49j=2(38) 38 49 65 97 76 13 27 49j=3(65) 38 49 65 97 76 13 27 49j=4(97) 38 49 65 97 76 13 27 49j=5(76) 38 49 65 76 97 13 27 49j=6(13) 13 38 49 65 76 97 27 49j=7(27) 13 27 38 49 65 76 9

30、7 49j=8(49) 13 27 38 49 49 65 76 97 二、选择排序1. 基本思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。2. 排序过程：【示例】：初始关键字 49 38 65 97 76 13 27 49第一趟排序后 13 38 65 97 76 49 27 49第二趟排序后 13 27 65 97 76 49 38 49第三趟排序后 13 27 38 97 76 49 65 49第四趟排序后 13 27 38 49 49 97 65 76第五趟排序后 13 27 38 49 49 97 97 76

31、第六趟排序后 13 27 38 49 49 76 76 97第七趟排序后 13 27 38 49 49 76 76 97最后排序结果 13 27 38 49 49 76 76 97三、冒泡排序(bubblesort)1. 基本思想：两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。2. 排序过程：设想被排序的数组r1.n垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组r，凡扫描到违反本原则的轻气泡，就使其向上漂浮，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。【示例】：49 13 13

32、13 13 13 13 13 38 49 27 27 27 27 27 2765 38 49 38 38 38 38 3897 65 38 49 49 49 49 4976 97 65 49 49 49 49 4913 76 97 65 65 65 65 6527 27 76 97 76 76 76 7649 49 49 76 97 97 97 97 四、快速排序（quick sort）1. 基本思想：在当前无序区r1.h中任取一个数据元素作为比较的基准(不妨记为x)，用此基准将当前无序区划分为左右两个较小的无序区：r1.i-1和ri+1.h，且左边的无序子区中数据元素均小于等于基准元素，右边

33、的无序子区中数据元素均大于等于基准元素，而基准x则位于最终排序的位置上，即r1.i-1x.keyri+1.h(1ih)，当r1.i-1和ri+1.h均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。2. 排序过程：【示例】：初始关键字 49 38 65 97 76 13 27 49第一次交换后 27 38 65 97 76 13 49 49 第二次交换后 27 38 49 97 76 13 65 49 j向左扫描，位置不变，第三次交换后 27 38 13 97 76 49 65 49 i向右扫描，位置不变，第四次交换后 27 38 13 49 76 97 65

34、49j向左扫描 27 38 13 49 76 97 65 49（一次划分过程） 初始关键字 49 38 65 97 76 13 27 49一趟排序之后 27 38 13 49 76 97 65 49 二趟排序之后 13 27 38 49 49 6576 97三趟排序之后 13 27 38 49 49 6576 97最后的排序结果 13 27 38 49 49 65 76 97 各趟排序之后的状态五、堆排序(heap sort)1. 基本思想：堆排序是一树形选择排序，在排序过程中，将r1.n看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。2.

35、 堆的定义: n个元素的序列k1,k2,k3,.,kn.称为堆，当且仅当该序列满足特性：kik2i ki k2i+1(1 i n/2)堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。例如序列10,15,56,25,30,70就是一个堆，它对应的完全二叉树如上图所示。这种堆中根结点（称为堆顶）的关键字最小，我们把它称为小根堆。反之，若完全二叉树中任一非叶子结点的关键字均大于等于其孩子的关键字，则称之为大根堆。3. 排序过程：堆排序正是利用小根堆（或大根堆）来选取当前无序区中关键字小（或最大）的记录实现排序的。我们不妨利用大根堆来排序。每一趟排序的基本操作是：将当前无序区调整为一个大根堆，选取关键字最大的堆顶记录，将它和无序区中的最后一个记录交换。这样，正好和直接选择排序相反，有序区是在原记录区的尾部形成并逐步向前扩大到整个记录区。【示例】：对关键字序列42，13，91，23