数据结构-图总结

数据结构树知识点总结图一、树的定义树是一种抽象的数据结构，它是由n（n≥0）个节点组成的有限集合，其中一个节点被指定为根节点，其他节点被划分为m（m≥0）个互不相交的子集T1、T2、...、Tm，每个子集本身又是一棵树。

树的定义可以用递归方式来描述，即树是由一个根节点和若干颗子树组成的。

其中，根节点没有父节点，每个子树的根节点都是父节点的孩子节点。

二、树的特点1. 树是一种层次结构：树中的节点可以分层次地组织，也就是包含父子关系。

根节点是树的第一层，它的子节点是树的第二层，以此类推。

2. 树是一种非线性结构：树中的节点之间的关系是非线性的，每个节点可以有多个子节点，但只有一个父节点。

3. 树是一种递归结构：树的定义中包含了对子树的定义，因此树是一种递归结构，通过递归的方式可以方便地对树进行操作。

4. 树是一种有序结构：树中的节点之间存在明确定义的顺序关系，因此可以用来表示有序集合。

三、树的基本操作1. 树的创建：创建一棵树需要先创建根节点，然后在根节点上添加子节点，逐层递归地创建子树。

2. 树的遍历：树的遍历是指按照一定顺序访问树中的每个节点，常见的遍历方式包括前序遍历、中序遍历、后序遍历和层序遍历。

3. 树的查找：树的查找是指在树中查找指定的节点，包括广度优先搜索（BFS）和深度优先搜索（DFS）两种方式。

4. 树的插入：树的插入是指将新节点插入到树中的指定位置，可以在根节点或指定节点的子节点上进行插入操作。

5. 树的删除：树的删除是指将指定节点从树中删除，可以删除叶子节点、中间节点或整棵子树。

6. 树的修改：树的修改是指对树中的节点进行数值或结构的改变，包括修改节点的值、替换子树等操作。

四、常见类型的树1. 二叉树（Binary Tree）：每个节点最多含有两个子节点的树，包括普通二叉树、满二叉树和完全二叉树等。

2. 平衡二叉树（Balanced Binary Tree）：每个节点的左子树和右子树的高度差不超过1的二叉树。

考研数据结构图的必背算法及知识点Prepared on 22 November 20201.最小生成树：无向连通图的所有生成树中有一棵边的权值总和最小的生成树问题背景：假设要在n个城市之间建立通信联络网，则连通n个城市只需要n—1条线路。

这时，自然会考虑这样一个问题，如何在最节省经费的前提下建立这个通信网。

在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。

n个城市之间，最多可能设置n(n-1)/2条线路，那么，如何在这些可能的线路中选择n-1条，以使总的耗费最少呢分析问题（建立模型）：可以用连通网来表示n个城市以及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示两城市之间的线路，赋于边的权值表示相应的代价。

对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。

即无向连通图的生成树不是唯一的。

连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不同的生成树。

图G5无向连通图的生成树为(a)、(b)和(c)图所示：G5G5的三棵生成树：可以证明，对于有n个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅有n－1条边。

最小生成树的定义：如果无向连通图是一个网，那么，它的所有生成树中必有一棵边的权值总和最小的生成树，我们称这棵生成树为最小生成树，简称为最小生成树。

最小生成树的性质：假设N=(V,{E})是个连通网，U是顶点集合V的一个非空子集，若（u,v）是个一条具有最小权值(代价)的边，其中，则必存在一棵包含边（u,v）的最小生成树。

解决方案：两种常用的构造最小生成树的算法：普里姆（Prim）和克鲁斯卡尔（Kruskal）。

他们都利用了最小生成树的性质1.普里姆（Prim）算法：有线到点，适合边稠密。

时间复杂度O(N^2)假设G＝（V，E）为连通图，其中V为网图中所有顶点的集合，E为网图中所有带权边的集合。

数据结构实验报告总结反思引言在本学期的数据结构实验课程中，我们学习了各种常用的数据结构和算法，并进行了相应的实验操作。

通过实验，我们巩固了理论知识，并锻炼了自己的编程能力和问题解决能力。

在本次实验报告中，我将对我所学到的内容进行总结和反思，并讨论未来的学习计划和改进方法。

总结学习内容在实验课程中，我学习了以下数据结构和算法：1. 线性表：包括顺序表和链表，学会了它们的插入、删除和查找操作。

2. 栈和队列：熟悉了它们的特性和基本操作，并应用到实际问题中。

3. 二叉树：了解了树的定义和遍历方法，熟悉了二叉搜索树的操作。

4. 图：学习了图的基本概念和表示方法，实现了图的遍历和最短路径算法。

5. 排序算法：掌握了冒泡排序、选择排序、插入排序、快速排序等排序算法的原理和实现。

实验操作在每次实验中，我都认真阅读了实验指导书，并按照指导书上的要求进行了实验操作。

通过自己的努力，我成功地实现了实验要求，并得到了正确的结果。

实验操作中，我尽量养成了规范的编程习惯，包括良好的命名、合理的代码结构和注释等。

这有助于提高代码的可读性和可维护性。

实验收获通过实验，我对数据结构和算法有了更深入的理解，巩固了相关知识。

在实验过程中，我遇到了一些问题，并学会了解决它们。

同时，实验也锻炼了我的编程能力和解决问题的能力。

通过不断地思考和实践，我提高了自己的代码质量和效率，并学会了如何写出更优雅的代码。

反思遇到的问题在实验过程中，我遇到了一些问题，其中包括以下几点：1. 对于一些复杂的数据结构和算法，理解起来较为困难。

我需要花费更多的时间来学习和掌握这些内容。

2. 在某些情况下，实验指导书的说明不够清晰。

我需要仔细阅读并进行补充学习，以理解实验的要求和实现思路。

3. 在编写代码时，我有时会犯一些低级错误，比如数组越界、指针错误等。

我需要更加细心和谨慎地编写代码，以避免这些错误的发生。

改进方法为了提升自己的学习效果和编程能力，我计划采取以下改进方法：1. 增加学习时间。

摘要：本学期我完成的主要实验任务有:实验一对比算法的时空效率之裴波那契序列、实验二线性表及其应用之约瑟夫环、实验三栈和队列之算术表达式求值、实验四树和二叉树之层序遍历二叉树以及实验五排序之学生成绩统计程序，文档内容为对本学期的五次实验进行概要介绍、综合分析以及自我评价。

并且对本学期所写程序提供相关数据结构理论和对本课程的相关建议。

关键字：Data Structure数据结构stack栈tree 树binary tree二叉树queue 队列linear list线性表sort排序algorithm算法正文：实验开发环境及工具：1.软件环境：Microsoft Windows 7 旗舰英文版Microsoft Visual C++6.0编译器2.硬件环境：Genuine Intel(R) CPU U2700 @ 1.30GHz1.30GHz,1.86 GB 的内存320G硬盘（含隐藏分区）物理地址扩展郑重声明:本电脑无光驱，携带相当便捷重量：1.6kg(含电池)型号：Lenovo U350实验一实验名称:实验一对比算法的时空效率之裴波那契序列实验目的及要求：1.熟悉开发工具的编程环境。

2.体会算法和程序的不同。

3.学习用不同算法实现同一程序功能，并能熟练编程实现。

4.学习分析算法。

对比不同算法实现的效率有何不同，所占空间有何不同。

对比不同算法的优点和缺点。

实验主要内容：选题题目：试编写求k阶（k>=2）裴波那契序列的第m项值的不同算法，并编程实现。

k和m均以值调用的形式在函数参数中表现。

要求：至少用两种不同的算法（如，递推、递归等等）。

当k=2时，裴波那契序列的初始两项为0、1，此后序列的每个值都是前两项之和。

当k=3时，裴波那契序列的初始三项为0、0、1，此后序列的每个值都是前三项之和，以此类推。

概要设计和存储结构：k阶（k>=2）裴波那契序列的第m项值假设为temp[m]则temp[m]=temp[m-1]+temp[m-2]+……+temp[m-k]=temp[m-1]+temp[m-2]+……+temp[m-k]+temp[m-k-1]-temp[m-k-1]=temp[m-1]+{temp[m-2]+……+temp[m-k]+temp[m-k-1]}-temp[m-k-1]}=2*temp[m-1]- temp[m-k-1]采用线性表顺序结构——数组主要算法：通过temp[m]=2*temp[m-1]- temp[m-k-1]此公式采用了循环递推以及递推的方法得出结果。

数据结构图知识点总结高中一、线性结构1. 线性表线性表是数据结构中最基本的一种结构，它是由零个或多个数据元素构成的有限序列。

其中每个数据元素都只有一个前驱元素和一个后继元素，除了第一个和最后一个元素外，其他元素都有且仅有一个前驱和一个后继。

线性表有两种基本的存储结构，分别是顺序存储结构和链式存储结构。

顺序存储结构是利用一组地址连续的存储单元来存放线性表的数据元素，而链式存储结构是通过指针来表示数据元素之间的逻辑关系。

2. 栈栈是一种特殊的线性表，它只能在表的一端进行插入和删除操作。

栈有一个被称为栈顶的元素，只能在栈顶进行插入和删除操作。

栈有两种经典的存储结构，分别是顺序栈和链式栈。

顺序栈是利用数组来实现栈的存储和操作，而链式栈则是利用链表来实现栈的存储和操作。

3. 队列队列也是一种特殊的线性表，它只能在表的两端进行插入和删除操作。

队列有一个被称为队头和队尾的元素，只能在队头进行删除操作，只能在队尾进行插入操作。

队列也有两种经典的存储结构，分别是顺序队列和链式队列。

顺序队列是利用数组来实现队列的存储和操作，而链式队列则是利用链表来实现队列的存储和操作。

4. 串串是线性表的一种特殊形式，它是由零个或多个字符构成的有限序列。

串的存储结构有两种常见的形式，分别是顺序存储结构和链式存储结构。

顺序存储结构是利用数组来存储串的字符序列，而链式存储结构是利用链表来存储串的字符序列。

二、非线性结构1. 树树是一种非线性结构，它是由n (n ≥ 1) 个节点组成的有限集合，这些节点之间存在着明确的层次关系。

树的存储结构通常有两种形式，分别是双亲表示法和孩子表示法。

双亲表示法通过数组来存储树的节点和节点之间的关系，而孩子表示法则通过链表来存储树的节点和节点之间的关系。

树有许多种特殊形式，如二叉树、平衡二叉树、多路查找树等。

其中，二叉树是一种特殊的树，它的每个节点最多有两个子节点，这两个子节点被称为左子树和右子树。

2. 图图是一种非线性结构，它是由一组顶点和一组边组成的数据结构。

优先队列、图等总结及习题一、优先队列1、定义优先队列（priority queue）是0个或多个元素的集合，每个元素都有一个优先权或值。

与FIFO结构的队列不同，优先队列中元素出队列的顺序由元素的优先级决定。

从优先队列中删除元素是根据优先权高或低的次序，而不是元素进入队列的次序.对优先队列执行的操作有:1)查找一个元素2)插入一个新元素3)删除一个元素2、描述线性表、堆、左高树（1）线性表⏹采用无序线性表描述最大优先队列公式化描述（利用公式Location(i)=i-1)◆插入：表的右端末尾执行，时间: Θ(1) ;◆删除:查找优先权最大的元素，时间:Θ(n) ;使用链表，◆插入：在链头执行，时间: Θ(1) ;◆删除: Θ(n) ;⏹采用有序线性表描述最大优先队列公式化描述（利用公式Location(i)=i-1，元素按递增次序排列)◆插入: O(n) ;删除: O(1) ;使用链表（按递减次序排列）插入: O(n) ;删除: O(1)（2）堆◆最大/最小树◆最大/最小堆初始化、插入、删除。

（3）左高树定义（重量优先、高度优先）；操作：创建、插入、删除。

3、应用（1）堆排序（2）哈夫曼编码（3）归并排序二、图1、定义⏹图(graph)是一个用线或边连接在一起的顶点或节点的集合。

G = (V,E)V 是顶点集. E是边集.顶点也叫作节点( nodes)和点(points).E中的每一条边连接V中两个不同的顶点。

边也叫作弧(arcs)或连线(lines) 。

可以用(i,j)来表示一条边，其中i和j是E所连接的两个顶点。

不带方向的边叫无向边(undirected edge)。

对无向边来说，(i,j)和(j,i)是一样的。

带方向的边叫有向边(directed edge)，而对有向边来说，(i,j)和(j,i)是不同的。

有向图、无向图、带权有向图、带权无向图2、描述邻接矩阵、邻接压缩表、邻接链表（1）邻接矩阵（2）邻接压缩表（3）邻接链表3、基本操作及应用（1）基本操作求是否存在边、顶点度数…,DFS、BFS（2）应用求路径、求连通分支、判别连通性…三、贪心算法1、单源最短路径2、拓扑排序3、最小耗费生成树四、分而治之1、快速排序2、归并排序习题：1、归并排序-优先队列练习232、已知图G 的邻接矩阵如下所示：由邻接矩阵画出相应的图G ；图中所有顶点是否都在它的拓扑有序序列中？⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡01000001010010103、分别用深度优先搜索和宽度优先搜索遍历下图所示的无向图，给出以1为起点的顶点访问序列（同一个顶点的多个邻接点，按数字顺序访问），给出一棵深度优先生成树和宽度优先生成树。

第1章绪论内容提要：◆数据结构研究的内容。

针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作。

数据结构涵盖的内容：◆基本概念：数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型。

数据——所有能被计算机识别、存储和处理的符号的集合。

数据元素——是数据的基本单位，具有完整确定的实际意义。

数据对象——具有相同性质的数据元素的集合，是数据的一个子集。

数据结构——是相互之间存在一种或多种特定关系的数据元素的集合，表示为：Data_Structure=（D, R）数据类型——是一个值的集合和定义在该值上的一组操作的总称。

抽象数据类型——由用户定义的一个数学模型与定义在该模型上的一组操作，它由基本的数据类型构成。

◆算法的定义及五个特征。

算法——是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。

算法的基本特性：输入、输出、有穷性、确定性、可行性◆算法设计要求。

①正确性、②可读性、③健壮性、④效率与低存储量需求◆算法分析。

时间复杂度、空间复杂度、稳定性学习重点：◆数据结构的“三要素”：逻辑结构、物理（存储）结构及在这种结构上所定义的操作（运算）。

◆用计算语句频度来估算算法的时间复杂度。

第二章线性表内容提要：◆线性表的逻辑结构定义，对线性表定义的操作。

线性表的定义：用数据元素的有限序列表示◆线性表的存储结构：顺序存储结构和链式存储结构。

顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。

链式存储结构: 其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。

通过指针来实现！◆线性表的操作在两种存储结构中的实现。

数据结构的基本运算：修改、插入、删除、查找、排序1)修改——通过数组的下标便可访问某个特定元素并修改之。

核心语句:V[i]=x;顺序表修改操作的时间效率是O(1)2) 插入——在线性表的第i个位置前插入一个元素实现步骤：①将第n至第i 位的元素向后移动一个位置；②将要插入的元素写到第i个位置；③表长加1。

（原创）数据结构之⼗字链表总结7-1 稀疏矩阵（30 分)如果⼀个矩阵中，0元素占据了矩阵的⼤部分，那么这个矩阵称为“稀疏矩阵”。

对于稀疏矩阵，传统的⼆维数组存储⽅式，会使⽤⼤量的内存来存储0，从⽽浪费⼤量内存。

为此，可以⽤三元组的⽅式来存放⼀个稀疏矩阵。

对于⼀个给定的稀疏矩阵，设第r⾏、第c列值为v，且v不等于0，则这个值可以表⽰为 <r,v,c>。

这个表⽰⽅法就称为三元组。

那么，对于⼀个包含N个⾮零元素的稀疏矩阵，就可以⽤⼀个由N个三元组组成的表来存储了。

如：{<1, 1, 9>, <2, 3, 5>, <10, 20, 3>}就表⽰这样⼀个矩阵A：A[1,1]=9，A[2,3]=5，A[10,20]=3。

其余元素为0。

要求查找某个⾮零数据是否在稀疏矩阵中，如果存在则输出其所在的⾏列号，不存在则输出ERROR。

输⼊格式:共有N+2⾏输⼊：第⼀⾏是三个整数m, n, N(N<=500)，分别表⽰稀疏矩阵的⾏数、列数和矩阵中⾮零元素的个数，数据之间⽤空格间隔; 随后N⾏，输⼊稀疏矩阵的⾮零元素所在的⾏、列号和⾮零元素的值；最后⼀⾏输⼊要查询的⾮0数据k。

输出格式:如果存在则输出其⾏列号，不存在则输出ERROR。

输⼊样例:在这⾥给出⼀组输⼊。

例如：10 29 32 18 -107 1 988 10 22输出样例:在这⾥给出相应的输出。

例如：8 10解题思路：实际上这道题⽤三元组写轻松解决，但是这⾥想讲的是⼗字链表；⼗字链表的图⼤致如下：那么如何去实现呢；看以下代码：因为下⾯都有注释，这⾥便不赘述了。

1 #include<iostream>2 #include<stdio.h>3using namespace std;45struct OLNod{6int i ; //该⾮零元的⾏下标；7int j ; //该⾮零元的列下标；8int value ; //该⾮零元的数值；9struct OLNod *right ,*down ;//该⾮零元所在的⾏表和列表的后继链域；10 };11struct CrossL{12 OLNod **rhead, **sead;13//⼗字链表的⾏头指针和列头指针；定义为指向指针的指针；14int row; //稀疏矩阵的⾏数；15int col; //稀疏矩阵的列数；16int num; //稀疏矩阵的⾮零个数；17 };1819int InitSMatrix(CrossL *M) //初始化M（CrossL）类型的变量必须初始化；20 {21 (*M).rhead = (*M).sead = NULL;22 (*M).row = (*M).col = (*M).num = 0;23return1;24 }2526int DestroysMatrix(CrossL *M) //销毁稀疏矩阵M；27 {28int i ;29 OLNod *p,*q;30for( i = 1 ; i <= (*M).row;i++)31 {32 p = *((*M).rhead+i); //p指针不断向右移；33while(p!=NULL)34 {35 q = p ;36 p = p ->right;37delete q; //删除q；38 }39 }40delete((*M).rhead); //释放⾏指针空间；41delete((*M).sead); //释放列指针空间；42 (*M).rhead = (*M).sead = NULL; //并将⾏、列头指针置为空；43 (*M).num = (*M).row = (*M).col = 0; //将⾮零元素，⾏数和列数置为0； 44return1;45 }46int CreatSMatrix(CrossL *M)47 {48int i , j , m , n , t;49int value;50 OLNod *p,*q;51if((*M).rhead!=NULL)52 DestroysMatrix(M);53 cin>>m>>n>>t; //输⼊稀疏矩阵的⾏数、列数和⾮零元个数；54 (*M).row = m;55 (*M).col = n ;56 (*M).num = t;57//初始化⾏链表头；58 (*M).rhead = new OLNod*[m+1];//为⾏头指针申请⼀个空间；59if(!(*M).rhead) //如果申请不成功，则退出程序；60 exit(0);61//初始化列链表头；62 (*M).sead = new OLNod*[n+1];//为列表头申请⼀个空间；63if(!(*M).sead) //如果申请不成功，则退出程序；64 exit(0);65for(int k = 1 ; k <= m ; k++)66 {67 (*M).rhead[k] = NULL;//初始化⾏头指针向量；各⾏链表为空链表；68 }69for(int k = 1 ; k <= n ;k++)70 {71 (*M).sead[k] = NULL;//初始化列头指针向量；各列链表为空链表；72 }73for(int k = 0 ; k < t ;k++) //输⼊⾮零元素的信息；74 {75 cin>>i>>j>>value;//输⼊⾮零元的⾏、列、数值；76 p = new OLNod();//为p指针申请⼀个空间；77if(!p) //e如果申请不成功；78 exit(0); //退出程序；79 p->i = i;80 p->j = j;81 p->value = value;82if((*M).rhead[i]==NULL) //如果⾏头指针指向的为空；83 {84//p插在该⾏的第⼀个结点处；85 p->right = (*M).rhead[i];86 (*M).rhead[i] = p;87 }else//如果不指向空88 {89for(q = (*M).rhead[i];q->right; q = q->right);90 p->right = q->right;91 q->right = p;9293 }94if((*M).sead[j]==NULL)//如果列头指针指向的为空；95 {96//p插在该⾏的第⼀个结点处；97 p->down = (*M).sead[j];98 (*M).sead[j] = p;99 }else//如果不指向空100 {101for(q = (*M).sead[j];q->down;q = q->down);102 p->down = q->down;103 q->down = p;104 }105 }106return1;107 }108int PrintSMatrix(CrossL *M)109 {110int flag = 0;111int val ;//要查找的元素的值；112 cin>>val; //输⼊要查找的s值；113 OLNod *p;114for(int i = 1 ; i <= (*M).row ;i++)115 {116for(p = (*M).rhead[i];p;p = p->right) //从⾏头指针开始找，不断向右找117 {118if(p->value==val) //如果能找到119 {120 cout<<p->i<<""<<p->j; //输出⾏下标和列下标121 flag = 1; //标记找到该元素；122 }123 }124 }125126127if(flag==0) //如果找不到128 {129 cout<<"ERROR\n";130 }131132 }133int main()134 {135 CrossL A; //定义⼀个⼗字链表；136 InitSMatrix(&A); //初始化；137 CreatSMatrix(&A); //创建；138 PrintSMatrix(&A); //输出；139 DestroysMatrix(&A); //销毁；140return0;141 }。

第5章图●图的定义①图由顶点集V和边集E组成，记为G=（V，E），V(G)是图G中顶点的有穷非空集合，E(G)是图G中顶点之间变得关系集合，|V|表示顶点个数，也称图的阶，|E|表示边数（线性表和树都可以是空的，但图可以只有一个顶点没有边）②有向图：弧是顶点的有序对，记为<v,w>，v,w是顶点,v是弧尾，w是弧头，从顶点v到顶点w的弧。

无向图：边是顶点的无序对，记为(v,w)③简单图：一个图满足：不存在重复边；不存在顶点到自身的边。

多重图相对于简单图定义④完全图：无向图中，任意两顶点之间存在边，称为完全无向图。

N个顶点的无向完全图有n(n-1)/2条边。

在有向图中，任意两顶点之间存在方向相反的两条弧，称为有向完全图，N 个顶点的有向完全图有n(n-1)条边。

⑤连通图：在无向图中任意两顶点都是连通的。

无向图中的极大连通子图称为连通分量。

极大要求连通子图包含其所有的边和顶点，极小连通子图既要保持图连通，又要保持边数最少⑥在有向图中任意两顶点v,w，存在从顶点v到顶点w和从顶点w到顶点v两条路径，这种图称为强连通图。

有向图的极大强连通子图称为有向图的强连通分量。

⑦生成树：①包含图中所有顶点n，②生成树有n-1条边, ③任意两点连通。

对生成树而言，砍去一条边变成非连通图，加上一条边形成一个回路。

在非连通图中，连通分量的生成树构成了非连通图的生成森林。

⑧顶点的度：以该顶点为端点的边的数目。

无向图的全部顶点的度之和等于边数的两倍。

有向图的度等于出度和入度之和，入度是以该顶点为终点的有向边的数目，出度是以该顶点为起点的有向边的数目。

有向图的全部顶点的入度之和和出度之和相等且等于边数。

⑨图中每条边可以标上具有某种含义的数值，该数值称为边的权值。

带有权值的图称为网。

○10对于无向图G=(V, {E})，如果边(v，v’)∈E，则称顶点v，v’互为邻接点，即v，v’相邻接。

边(v，v’)依附于顶点v 和v’，或者说边(v, v’)与顶点v 和v’相关联。