数据结构知识点

1、复习要点：第一章1.相关基本概念：数据、数据元素（基本单位）、数据项（最小单位）、算法及其特征等；数据：所有能输入到计算机中并被计算机程序处理的符号总称。数据元素：基本单位。数据项：最小单位。算法特征（5点）：有穷性；确定性；可行性；输入；输出。2.逻辑结构、存储结构（物理结构）及其类型；逻辑结构有四种基本类型：集合、线性结构、树形结构和网状结构。数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。注：期中考题目数据结构分为两大类，即为逻辑结构和存储结构。其中逻辑结构又分为 线性结构和非线性结构 ，存储结构一共有四种（顺序、链

2、接、索引、散列）。3.算法分析：语句频度（执行次数）计算、时间和空间复杂度分析。表示方法语句频度：直接写次数。时间复杂度：O(执行次数),如：O(n)。空间复杂度：O(所需空间)第二章 1.顺序表（数组）插入、删除、有序表合并算法及其移动次数计算；1213212428304277 数据元素 序号 1 2 3 4 5 6 7 8表示 L.elem0 1 2 3 4 5 6 7顺序表插入 算法思想：如果要在序号5前插入元素e，需要将序号58向后移动一个位置。 移动次数为4次，公式n-i+1 顺序表删除 算法思想：如果要删除序号5元素，需要将68依次向前移动一位移动次数为3次，公式n-i 有序表合并

3、 LA = (3,5,8,11) LB = (2,6,8,9,11,15,20) 则LC = (2,3,5,6,8,8,9,11,11,15,20) 算法思想（以非递减为例）：La和Lb非递减排列，La与Lb中元素逐个比较，较小的先插入Lc中。 注：非递减是指递增排序，但元素有可能相等，与之相对的有非递增排序。 移动次数为（La.length + Lb.length） 2.链表（有无头节点、单双、循环）插入(前、后)、删除（前、本身、后）的指针挂接、建立（不带头节点）算法。单链表 每个节点有数据域和指针域 data next 头 a1 a2 a3 a4 a5 a6带头节点L P a1 a2 a

4、3 a4 a5 a6 不带头节点L P单循环链表 在P（a3）节点前插入S节点 (1)Q = P; /先让Q指向a3(2)P = L; /P指向第一个节点（带头结点指向头结点，不带头结点指向a1）(3)while(P->next != Q) P = P->next; /找到a3的前驱a2，P指向a2(4)S->next = P->next; /P->next为a3，让S->next等于a3(5)P->next = S; /a2指针域指向节点S在P（a3）节点后插入S节点(1)S-next = P->next;(2)P->next = S;删

5、除P（a3）前一个节点 (1)Q = P; (2)P = L; (3)while(P->next->next != Q) P = P->next; /找到a1 (4)P->next = P->next->next; /让a1指针域指向a3，从而删除a2删除P（a3）节点 (1)Q = P; (2)P = L; (3)while(P->next != Q) P = P->next; /找到a2 (4)P->next = P->next->next; /让a2指针域指向a4，从而删除a3删除P（a3）后一个节点 (1)P->n

6、ext = P->next->next; /让a3指针域指向a5，从而删除a4双链表 每个节点有前驱指针、数据域、后继指针 prior data next 双循环链表 头 a1 a2 a3 a4 在P（a2）节点前插入S节点 技巧：先让S->prior 和S->next与链表建立关系 注：步骤(4)必须在步骤(3)后面 (1)S->next = P; /先让S->next指向a2 (2)S->prior = P->prior; /S->prior指向a1 (3)P->prior->next = S; /再把a1->next

7、指向S (4)P->prior = S; / a2->prior指向S在P（a2）节点后插入S节点 注：步骤(4)必须在步骤(3)后面 (1)S->prior = P; (2)S->next = P->next; (3)P->next->prior = S; /a3->prior指向S (4)P->next = S;删除P（a2）前一个节点a1 (1)Q = P->prior; /Q指向要被删除的a1; (2)P->prior = P->prior->prior; /P->priro指向头 (3)P->p

8、rior->next = P; /头->next指向P (4)free(Q); /释放a1的存储空间删除P（a2）节点 (1)P->next->prior = p->prior; (2)P->prior->next = p->next; (3)free(P);删除P（a2）后一个节点a3 (1)Q = P->next; (2)P->next = P->next->next; /a2->next指向a4 (3)P->next->prior = P; /a4->prior = P (4)free(Q);

9、 /释放a3存储空间建立（不带头节点）单链表读程序：设n为2（i取0，1）i = 0时， pLqi = 1时， Lq p Lq p L qp第三章 1.栈的进出序列、栈、队列、循环队列的满/空条件; 由于栈的插入、删除操作是限制在栈顶进行的，因而后进栈的元素必然是先出栈，0.所以栈是“后进先出”表。由于队列的输入、输出操作分别在队的两端进行，因此先入队的元素必然先输出，故队列又称为“先进先出”表 栈的进出序列 例题：进栈序列为123，可能得到的出栈序列是什么？ 答：共五种123/132/213/231/321 进出栈情况（以132序列为例）：1进栈1出栈，输出12进栈3进栈3出栈2出栈 输出3

10、2栈、队列、循环队列的满/空条件 栈空条件：s.top = s.base;栈满条件：s.top - s.base = stacksize; 队空条件：Q.front=Q.rear; 队满条件：q->rear - q->front = MAXSIZE循环队列空条件：Q.front=Q.rear循环队列满条件：为避免在队满是队头指针和队尾指针也是重合的情况，规定队列中还有一个空的存储单元时为队满，即为Q.front=(Q.rear+1)MOD maxsize(MOD为取余运算符）。因而，这种循环队列不适合用动态数组作为存储结构。 2. 栈、队列的存储结构、基本操作算法（双向栈）; 栈存

11、储结构顺序栈 typedef structSElemType *base;SElemType *top;int stacksize; SqStack;链式栈队列存储结构 顺序存储结构 链式存储结构 双向栈存储结构：typedef   struct         Elemtype   *base2;         Elemtype   *top2; BDStacktype;   /双向栈类型初始化：Status Init_Stack(BDStacktype &tws

12、, int m)/初始化一个大小为m的双向栈tws         tws.base0 = (Elemtype*)malloc(sizeof(Elemtype)*m);         tws.base1 = tws.base0 + m;         tws.top0 = tws.base0;         tws.top1 = tws.base1;         return OK; /

13、Init_Stack入栈：Status push(BDStacktype &tws, int i, Elemtype x)/x入栈,i=0表示低端栈,i=1表示高端栈 if(tws.top0 > tws.top1) return OVERFLOW; /注意此时的栈满条件 if (i = 0) *tws.top0+ = x; else if (i = 1) *tws.top1- = x; else return ERROR;return OK; /push出栈：Status pop(BDStacktype &tws, int i, Elemtype &x) /x出栈

14、,i=0表示低端栈,i=1表示高端栈 if (i = 0) if (tws.top0 = tws.base0) return OVERFLOW; x = *-tws.top0; else if(i = 1) if(tws.top1 = tws.base1) return OVERFLOW; x = *+tws.top1; else return ERROR; return OK; /pop第四章 1.字符串模式匹配的简单算法；int Index(SString S, SString T, int pos) / 算法4.5 / 返回子串T在主串S中第pos个字符之后的位置。 / 若不存在，则函数

15、值为0。 / 其中，T非空，1posStrLength(S)。 int i = pos; int j = 1; while (i <= S0 && j <= T0) if (Si = Tj) / 继续比较后继字符 +i; +j; else / 指针后退重新开始匹配 i = i-j+2; /此时i为上次开始比较位置的下一位 j = 1; if (j > T0) return i-T0; else return 0; / Index 2.计算NEXT。 j ：1 2 3 4 5 6 7串 ：a b c a b a anextj：0 1 1 1 2 3 2技巧：第一

16、二个肯定是0，1！如果要计算next4，找的字符串必须是以第3个字符c为结尾，第1个字符a为开头的。以第6个为例，a前一个字母是b，以第5个字符b为结尾的ab刚好和以第1个字符为开头的ab匹配，所以next6 = 2+1 = 3。第五章 1.二维数组的地址（下标）换算；习题5.1假设有二维数组A6*8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，计算：（1）数组A的体积（即存储量）6*8*6 = 288字节（3）按行存储是，元素a14的第一个字节的地址 1000+(8*1+4)*6 = 1072 基址+(每行的元素个数*行数+当前列序)*每个元素所

17、占存储单元（4）按列存储时，元素a47的第一个字节的地址 1000+(6*7+4)*6 = 6276 基址+(每列的元素个数*列数+当前行序)*每个元素所占存储单元习题5.2假设按低下标优先存储整数组A9*3*5*8时，第一个元素的字节地址是100，每个整数占四个字节。问下列元素的存储地址是什么？（2）a1111 地址：100+(3*5*8*1+5*8*1+8*1+1)*4 = 776（3）a3125 地址：100+(3*5*8*3+5*8*1+8*2+5)*4 = 1784（4）a8247 地址：100+(3*5*8*8+5*8*2+8*4+7)*4 = 4416 2.特殊矩阵（三角、其他有

18、规律）压缩为一维的下标计算；下三角矩阵压缩为一维数组（记忆公式） 技巧：推荐把公式(2)背下来（i,j,R范围都是从0开始），其他根据范围变化公式 (1)若1<=i,j<=n, 0<=k<=n(n+1)/2-1 当i>=j时，k = i(i-1)/2+j-1; 当i<j时，k = j(j-1)/2+i-1.(2)若0<=i,j<=n-1, 0<=k<=n(n+1)/2-1 /注意i,j是0到n-1，下面的公式相当于把(1)中i变成i+1,j变成j+1 当i>=j时，k = (i+1)i/2+j; 当j<j时，k = (j+

19、1)j/2+i.(3)若1<=i,j<=n, 1<=k<=n(n+1)/2 /注意R是1到n(n+1)/2，下面公式相当于把(1)中k变成k-1 当i>=j时，k = i(i-1)/2+j; 当i<j时，k = j(j-1)/2+i;(4)若0<=i,j<=n-1, 1<=k <=n(n+1)/2 当i>=j时，k = (i+1)i/2+j+1; 当i<j时，k = (j+1)j/2+i+1;3.稀疏矩阵的三元组表示。 4.稀疏矩阵应用的算法。（略）第六章 1.二叉树的性质；性质1：。性质2：深度为k的二叉树至多有个结点(

20、k³1)。性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。性质4：。性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1£i£n)，有： (1)如果i=1，则结点i是二叉树的根，无双亲； 如果i>1，则其双亲是ëi/2û。 (2)如果2i>n，则结点i无左孩子； 如果2i£n，则其左孩子是2i。 (3)如果2i+1>n，则结点i无右孩子； 如果2i+1£n，则其右孩子是2i+1。 2.二叉树的先序、中序、后序、层次遍历过程；算法（如：求二叉

21、树的高度或结点个数）树的先序、后序、层次遍历过程；二叉树遍历过程：先（根）序遍历：根左子树右子树中（根）序遍历：左子树根右子树后（根）序遍历：左子树右子树根层次遍历：从上到下，从左往右，逐个遍历树的遍历过程：先根（次序）遍历：先访问根结点，然后依次先根遍历根的每棵子树(根子树)后跟（次序）遍历：先依次后根遍历每棵子树，然后访问根结点（子树根）层次遍历：从上到下，从左往右，逐个遍历注：树与二叉树相互转化后树的先根遍历相当于二叉树的先序遍历树的后根遍历相当于二叉树的中序遍历 3.给出两个遍历序列，画出树（二叉树、树）习题6.23画出和下列已知序列对应的树T：(1)树的先根次序访问序列为GFKDAI

22、EBCHJ;(2)树的后根次序访问序列为DIAEKFCJHBG。注：树的后根遍历相当于二叉树的中序遍历G 由(1)知G为根； G为根，联系(2)知G无右子树； 观察(1)，F为G左子树；F 根据，观察(2)知DIAEK在F左边， CJHB在F右边；BK 观察(1)，K为F左子树； 根据，观察(2)知K无右子树； 观察(1)，D为K左子树；CD 根据，观察(2)知D无左子树； 观察(1)，A为D右子树； 观察(2)，IE分别为A左右子树；AH F的右子树自行观察判断。JEI 4.二叉树与树相互转换；树转化成二叉树： 规则：树的最左孩子变成二叉树左子树，该左孩子的兄弟变成二叉树左子树的右子树 注：

23、原树中B为A最左孩子，C,D为B兄弟，变成二叉树后C成为B右子树，D成为C右子树。 二叉树转化成树 5.求哈夫曼树和给出编码、带权路径长度计算。习题6.26假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07, 0.19, 0.02, 0.06, 0.32, 0.21, 0.10。试为这8个字母设计哈夫曼编码，并求带权路径长度设这8个结点为A、B、C、D、E、F、G、H，其相应的权为7、19、2、6、32、3、21、10。当前未用权：7、19、2、6、32、3、21、10，选出2、3构造出5。当前未用权：7、19、6、32、21、10、5，选出5、6构造出11。当前未用权：

24、7、19、32、21、10、11，选出7、10构造出17。当前未用权：19、32、21、11、17，选出11、17构造出28。当前未用权：19、32、21、28，选出19、21构造出40。当前未用权：32、28、40，选出32、28构造出60。剩下权：40、60，构造出100 编码：树的左分支为0，右分支为1。得到哈夫曼编码为A:1101 B:01 C:11111 D:1110 E:10 F:11110 G:00 H:1100带权路径长度：(7*4+19*2+2*5+6*4+32*2+3*5+21*2+10*4)/100 = 2.61注：该公式为：A路径长*A权+B路径长*B权+H路径长*H权

25、，因为设的权值是原来的100倍，所以结果除以100。第七章 1.邻接矩阵、邻接表存储结构及其特征；注：以有向图G1为例(有路径用1，否则0)v1 v2 v3 v4v1 0 1 1 0 v2 0 0 0 0v3 0 0 0 1v4 1 0 0 0 注：以有向图G1为例标号 0 1 2 3 0 0 1 1 0 1 0 0 0 0 2 0 0 0 1 3 1 0 0 0第0行值为1的是1、2，所以有V121。第1行值全为0，所以有V2。第2行值为1的是3，所以有V33。第3行值为1的是0，所以有V40。 2.求最小生成树（Prim、Kruskal）；从V1开始，找到最小边(V1,V3)；寻找与V1、

26、V3相关联的最小边，找到(V3,V6)；寻找与V1、V3、V6相关联的最小边，找到(V6，V4)；寻找与V1、V3、V6、V4相关联的最小边，此时有(V4,V1)和(V3,V2)，因为(V4,V1)与原来的边构成圈，所以选择(V3,V2)。（如果(V4,V1)不与原来的边构成圈，则二条边任选一条）；寻找与V1、V3、V6、V4、V2相关联，并且不与原来边构成圈的最小边，找到(V2,V5)； 普里姆（Prim）： 以点为基础克鲁斯卡尔(Kruskal)（避圈法）：以边为基础 方法介绍：依次寻找权最小边，避免生成一个圈，所有点联通时生成最小树。 3.拓扑排序；步骤：（1）在有向图中选一个没有前驱的

27、顶点且输出之。 （2）从图中删除该顶点和所有以它为尾的弧。输出： V6 V1 V4 V3 V5注：拓扑排序不唯一。4.求最短路径过程（Dijkstra、Floyd）。迪杰斯特拉(Dijkstra) 习题7.11试利用Dijkstra算法求题7.11图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步状态。求解过程：K=1时，找a能直接到达的点，有b,c,d，(a,c)权最小，(a,c)为a到c最短路径，将c放如终点集S；K=2时，找a能直接到达的点，或通过(a,c)能到达的点，(a,c,f)权最小，(a,c,f)为a到f的最短路径，将f放入终点集S；K=3时，找a能直接到达的点，或通过

28、(a,c)能到达的点，或通过(a,c,f)能到达的点，(a,c,e)权最小，(a,c,e)为a到e最短路径，将e放入终点集S；K=4时，找a能直接到达的点，或通过(a,c)能到达的点，或通过(a,c,f)能到达的点，或通过(a,c,e)能到达的点，(a,c,f,d)为a到d最短路径，将d放入终点集S；K=5时，找a能直接到达的点，或通过(a,c)能到达的点，或通过(a,c,f)能到达的点，或通过(a,c,e)能到达的点，或通过(a,c,f,d)能到达的点，(a,c,f,d,g)权最小，为a到g最短路径，将g放入终点集S；K=6时，只剩下(a,b)，(a,b)为a到b最短路径，将b放入终点集S。

29、弗洛伊德(Floyd) 注：D(1)ij是从Vi到Vj的中间顶点的序号不大于1的最短路径的长度；D(k) ij是从Vi到Vj的中间顶点的序号不大于k的最短路径的长度；D(n-1) ij就是从Vi到Vj的最短路径的长度。D(-1)栏中，ViVj不允许有转折点。直接填邻接矩阵。D(0)栏中，ViVj只允许通过V0转折，或者不转折。通过V0转折权值小于原权值，就把原权值替换掉。D(1)栏中，ViVj只允许通过V0、V1转折，或者不转折。如果转折后权值小于原权值，替换。D(2)栏中，VjVj允许通过V0、V1、V2转折，或者不转折，如果转折后权值小于原权值，替换。此时p(2)中就是各点间的最短路径。第

30、九章 1.以下所有查找成功平均查找长度2.顺序查找；折半查找；顺序查找：从表中最后一个记录开始，逐个进行比较。平均查找长度 等概率时，平均查找长度ASL = (n+1)/2 不等概率时，ASL = nP1 + (n-1)P2 + + 2Pn-1 + Pn折半查找：指针low和high分别指示待查元素所在范围的下界和上界，mid=(low+high)/2，如果要找的值大于Smid，则让mid = (mid+1 + high)/2，继续比较；如果要找的值小于Smid，则让mid = (low + mid-1)/2，继续比较。平均查找长度 等概率条件下，ASL=(n+1)-1当n>50时，有近

31、似结果ASL=(n+1)-13.二叉排序树的插入（建立）、删除、平衡过程；二叉排序树建立 (1)若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； (2)若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； (3)它的左、右子树也分别为二叉排序树。注：中序遍历二叉 排序树，得到从小到大序列根据字母的先后确定大小插入Jan；F小于J，Feb成为Jan左子树；M大于J，Mar成为Jan右子树；Apr小于Jan，且Apr小于Feb，Apr成为Feb左子树；May大于Jan，且May大于Mar，May成为Mar右子树；June大于Jan，且June小于Mar，June成为Mar左

32、子树。剩下的略。二叉排序树删除（） 3种情况：(1)*p为叶子节点，直接删除。(2) *p只有一个孩子*child只需将*child和*p的双亲直接连接后，即可删去*p。(3)*p有两个孩子用*p的直接前驱或直接后继代替*p，然后删除它的直接前驱或直接后继。平衡二叉树：树上任何节点的左右子树深度差都不超过1 插入节点P后不平衡，找到离P最近的不平衡点，根据二叉排序树的建立进行调整。 序列：Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec(1) 插入Aug时，Feb左右子树深度差超过1不平衡（此处错误 Aug和Apr的位置应该对调）(2) 插入Oct时，最近不平衡点为May。因为Sep>Oct>May，所以Oct作为双亲(3) 插入Nov时，Jan不平衡。把Jan左转，Mar的左子树变成Jan右子树。最终平衡树4.哈希表构造、冲突解决方法；除留余数法、线性探测或链地址法。构造：除留余数法：H(key) = key MOD p, p<=m 冲突解决：线性探测法：Hi = (H(key)+) Mod m i = 1, 2, , k(k <= m-1)链地址法：将所有关键字为同义词的记录存储在同一线性链表中。例题：已知一个线性表（38，25，74，63，52，48），假定采用散