不属于企业网站建设基本标准是,友情链接交换统计表,网络营销分析论文,重庆网红打卡景点找往期文章包括但不限于本期文章中不懂的知识点#xff1a; 个人主页#xff1a;我要学编程(ಥ_ಥ)-CSDN博客 所属专栏#xff1a; 学校课程突击 下面均是为了应付学校考试所用#xff0c;如果有涉及部分知识点下面未说明#xff0c;可以去我的数据结构专栏看看或者自行在…找往期文章包括但不限于本期文章中不懂的知识点 个人主页我要学编程(ಥ_ಥ)-CSDN博客 所属专栏 学校课程突击 下面均是为了应付学校考试所用如果有涉及部分知识点下面未说明可以去我的数据结构专栏看看或者自行在网上查阅资料。
以下所有知识均是阅读大话数据结构所得。如果有小伙伴对这本书也感兴趣可以去看看。
通过百度网盘分享的文件大话数据结构-目录版.rar 链接https://pan.baidu.com/s/1ge7HSe00tvj1U1S2zWnA8w?pwd2580 提取码2580
目录
树与二叉树章节相关
树与二叉树的转换
森林与二叉树的转换
树与森林的遍历
赫夫曼树哈夫曼树
图章节相关
查找章节相关
数据结构的相关理解记忆
算法 树与二叉树章节相关
我们前面学习的树都是特殊的二叉树且都是采用孩子双亲表示法而下面要学习的二叉树采用的是 孩子兄弟表示法第一个节点表示孩子第二个节点表示当前节点的兄弟节点。
typedef struct Node {int val; // 节点的值struct Node *child; // 指向第一个子节点的指针struct Node *brother; // 指向下一个兄弟节点的指针
} TreeNode;树与二叉树的转换
一般的树都不是只有两个分叉的而是存在多个分叉但我们要想办法将多个分叉的树转换为二叉树就需要用到下面的方法
1、加线。在同一层的相邻兄弟节点之间加上一根线将其相连。
2、去线。若某个节点存在多个子节点 将除第一个子节点之外的所有子节点之间的线全部去掉。
3、调整层次。 上述就是树转换为二叉树的过程。
二叉树转换为树就是树转换为二叉树的逆过程。
1、加线。若某个节点存在左子节点且该子节点的右子节点不为空则将父节点与该子节点的右子节点相连。
2、去线。将所有与右子节点的相连的线全部去掉。
3、调整层次。 森林与二叉树的转换
森林是由若干棵树组成的所以完全可以理解为森林中的每一棵树都是兄弟可以按照兄弟的处理办法来操作。
1、先将森林中的每棵树都转为二叉树
2、再以第一棵树作为基准将后续的树全部使用。 上图转换为二叉树的过程。
二叉树转换为森林也是逆着来。但首先得判断这二叉树是转换成一棵树还是森林。如果根结点存在右子树那么这棵二叉树就可以转为森林反之则不能转为森林就是直接转为树了。
1、先将森林分裂成多棵二叉树。将根结点与右子树之间的连线断开继续从右子树为起点重复上述步骤直至右子树为空。
2、将分裂出的每棵子树全部使用二叉树转换为树的方法去转换每棵树。 树与森林的遍历
树的遍历方式分为两种一种是先根遍历树即先访问树的根结点然后依次先根遍历根的每棵子树。另一种是后根遍历即先依次后根遍历每棵子树然后再访问根结点。
树的先根遍历就是二叉树的先序遍历而树的后根遍历就是二叉树的后序遍历。 如果直接看不出来的话还有一种方法将树先转为二叉树然后再对二叉树进行相应的遍历即可。 将图中的树转为二叉树之后再去遍历结果还是一样的。
森林的遍历也分为两种方式一种是前序遍历先访问森林中第一棵树的根结点然后再依次先根遍历根的每棵子树再依次用同样方式遍历除去第一棵树的剩余树构成的森林。
后序遍历是先访问森林中第一棵树后根遍历的方式遍历每棵子树然后再访问根结点再依次同样方式遍历除去第一棵树的剩余树构成的森林。
森林的前序遍历就是对每个树都进行先根遍历同理后序遍历就是对每棵树都进行后序遍历。 同样如果直接看不出来的话也可以先将森林转换为二叉树然后再对二叉树进行先序遍历 与 中序遍历。这样得出的结果是一样的。 注意这里森林的后序遍历不是二叉树的后序遍历而是中序遍历了。
注意我们上面所说的树均不是二叉树而是普通的树。只有当说是二叉树时才表明这是二叉树。同样森林也不是由二叉树构成而是由普通的树构成的。
赫夫曼树哈夫曼树
从树中一个结点到另一个结点之间的分支构成两个结点之间的路径路径上的分支数目称做路径长度。树的路径长度就是从树根根结点到每一结点叶子结点的路径长度之和。针对带权路径来说树的带权路径长度为树中所有叶子结点的带权路径长度之和。 假设有n个权值{W1,W2,...,Wn}构造一棵有n个叶子结点的二叉树每个叶子结点带权Wk每个叶子的路径长度为Ik我们通常记作则其中带权路径长度WPL最小的二叉树称做赫夫曼树。也被称为 哈夫曼树 与 最优二叉树。
考试中使用最多的就是去计算一棵树的带权路径长度。
那如何去构造一棵赫夫曼树呢
1、将结点与权值绑定在一起。
2、找到结点权值最小的两个连接在一起构造成一个新的结点权值为两者之和。
3、重复上述步骤直至构造成一个完整的二叉树即可。
如下图所示 注意
1、将两个结点结合成一个新的结点时下次再去找权值最小的两个结点就只能从结合的新结点与原来剩下的结点中去寻找。如果使用队列进行预处理的话就是将队列中的两个权值最小的结点出队然后再将结合的结点入队。
2、为了更好的处理我们一般都会先将需要构造赫夫曼树的结点重新排序。上述图示只是为了更好的展示效果实际的处理过程中我们是使用优先级队列来处理的。
3、由于结点放置的左右顺序没有要求因此最终所形成的赫夫曼树也是有不同的形状的但是带权路径长度一定是最小的。
赫夫曼树构造出来之后就可以求对应的加权路径长度以及每个结点字符对应的赫夫曼编码了。
我们先来看赫夫曼树的加权路径长度WPL。其计算方法是将每个根结点到叶子结点的长度求出然后乘上叶子结点的权值最后将所有的结果相加就得到了WPL。 注意为了做到不重不漏的计算出正确答案我们最好是按照叶子结点从左到右的顺序来计算。
在学习赫夫曼编码之前我们先来了解一下什么是编码以及为什么需要编码
编码是将数据从一种形式转换为另一种形式。例如二进制编码就可以将不属于二进制的数据转换为属于二进制的数据。编码的作用主要是为了更好的传输与存储。这里的哈夫曼编码就是为了更好的传输。
在现实生活中数据的传输都是先转换为二进制数据然后通过光信号或者电信号发生出去最后接收方再通过同样的方式将接受的光信号或者电信号转换为对应的二进制最终在转换为相应的原始数据。 在上述情况下便诞生了赫夫曼编码 与 赫夫曼树。赫夫曼编码既不会产生前缀不唯一的情况也不会出现冗余。 赫夫曼编码是通过赫夫曼树得到的。这里的权值是每次字符出现的次数。我们还是拿最上面的那个赫夫曼树来举例。 其实现在我们再去看赫夫曼树的构造过程使用权值最小的结点开始构造这样最终形成的编码也是最长的但是权值小意味着出现的频率小也就占用的编码长度短因此采用赫夫曼树构造出来的树的带权路径长度一定是最短的。
注意由于赫夫曼树的构造不止一种因此对应字符的赫夫曼编码也是唯一的但是带权路径长度一定是唯一且最短的。
除了上述构造赫夫曼树与对应的赫夫曼编码以及WPL之外还常考的就是计算存储一段正文所需的二进制字节数或者说存储这段正文所需的最小内存是多少。
这种题目的思路是将对应字符出现的次数构造成一棵赫夫曼树然后将对应字符的编码求出来最后将编码长度乘以对应字符出现的次数整体求和就可以得到存储这段正文所需的内存这里得到的是比特位的个数。 图章节相关
深度优先遍历 与 广度优先遍历的区别
深度优先遍历的思想体现在深当遍历到一个新的顶点时不会继续往当前路径去遍历而是直接沿着新顶点的路径去遍历剩下的顶点了。
广度优先遍历的思想体现在广当遍历到一个新的顶点时会将该顶点相邻的所有顶点都尝试去遍历一遍。
普利姆算法 与 克鲁斯卡尔算法的区别
普利姆算法是需要确定一个顶点从该顶点出发寻找局部权值最小的边与已知顶点相连的边直至构成最小生成树。
克鲁斯卡尔算法是在图中所有的边中选取一个权值最小的边因此并不需要确定顶点出发。
顶点的度
在有向图中顶点的度包括了出度与入度而在无向图中顶点的图只需要看出度或者入度即可。
关键路径
概念在项目网络图中关键路径是从项目开始到结束的最长序列边权值和最大。这个路径上的任务总持续时间最长。 求关键路径一般就是求其的序列而求关键路径长度时才会去求具体的边权和。 关键活动是指关键路径上的顶点。 若一个有向无环图的关键路径有几条时当要求加快进度缩短工期时应如何才能做到必须同时提高几条关键路径上的活动。 关键活动速度的提高在什么情况下才有效在不改变关键路径路径的情况下才有效。 注意关键路径只存在于有向无环图中。对于无向图或者有向成环图不存在这样的概念。
拓扑排序
每次选入度为0的点然后删除这个点和它的出边。接着继续在图中选择一个入度为0的点并删除其出边直至图中不存在点。
注意拓扑排序只针对有向无环图才能生效如果图中存在环就不能使用拓扑排序或者说拓扑排序的结果不存在。 对上图进行拓扑排序
1、选择入度为0的点 a
2、删除a 与 其的出边这里也可以认为是全部的边因为其不存在入边
3、从 b 与 c 中选择一个点即可继续重复上述步骤。
最终拓扑排序的结果为其中一种a b c e d。
我们也可以看一下对于存在环的图是啥样的 对上图进行拓扑排序
1、选择入度为0的点 a
2、删除a 与 其的出边这里也可以认为是全部的边因为其不存在入边
3、c d e 都不满足入度为0的点这个要求因此没法继续拓扑排序了。
拓扑排序也常用来判断图中是否存在环。
查找章节相关
二叉搜索树 1、求在等概率情况下的查找成功的平均查找长度
查找成功的情况只能出现在树中有节点存在的情况才行而查找本质上就是遍历整棵树。对于第一层的结点来说查找一次即可对于第二层的结点来说查找两次即可依次类推对于第n层的结点查找成功的次数是n。对于查找成功的平均查找长度就是将这棵树的结点全部查找所需的次数然后除以节点的个数就是最终的结果。
上面这棵树查找成功的平均查找长度ASL (1*1 2*2 3*4 4*2 5*1) / 10 3
2、求在等概率情况下的查找不成功的平均查找长度
查找不成功就是指不是树中存在那怎么知道不在树中存在呢当查找到空节点时就证明查找失败了。查找不成功的平均长度就是空节点的查找次数之和除以空节点的个数。注意的是对于处于第n层的空节点来说查找的次数是 n-1而不是n。ASL (6*3 3*4 2*5) / 11 3.64约为
二分查找 对于有序表12 ,18 , 24 , 35 , 47, 50, 62, 83, 90 ,115,134在等概率的情况下 1请画出折半查找树判定树 2求采用折半查找法时成功和不成功的平均查找长度。 3当用折半查找法查找90时需要进行多少次查找可以确定成功 4查找100时需要进行多少次查找才能确定不成功 1、对于 折半查找树画法是根据二分查找折半查找的顺序来的。将二分查找取的数作为当前子树的根结点。左区间就作为左子树右区间就作为右子树。 2、查找成功与不成功的平均查找长度和前面的二叉搜索树是一样的做法都是计算树中节点的查找的次数之和 除以 节点的个数。
ASL不成功 4*3 8*4/ 12 3.67 ASL成功 1*1 2*2 4*3 4*4/ 11 3
3、4当我们画出折半查找树之后就可以直接对照树来进行判断了。
90 是属于第二层那么查找的次数就是2次。
100 是属于 第四层的空节点查找的次数为3次。
哈希表 设哈希Hash表的地址范围为017哈希函数为HKK MOD 16。K为关键字用线性探测法再散列法处理冲突输入关键字序列1024321731304647406349造出Hash表试回答下列问题 画出哈希表的示意图若查找关键字63需要依次与哪些关键字进行比较若查找关键字60需要依次与哪些关键字比较假定每个关键字的查找概率相等求查找成功时的平均查找长度。 1、画出哈希表根据映射函数 线性探测法将哈希表的图给画出来即可 2、查找63就是先通过哈希映射函数将对应的下标求出来key 15先查找到31不对继续往后找46 47 32 17 63一共找了6次。
3、查找60同样是通过哈希映射函数计算出下标key 12查找到12的位置为空就说明不存在这个元素只需要比较一次。
4、计算平均查找长度就是将所有元素查找成功的次数之和 除以 元素的个数。哈希表中没有冲突的元素只需要查找一次冲突的元素加上线性探测的次数即为最终的查找次数。
ASL 6×123336623336/ 11 23 / 11 ≈ 2.09
数据结构的相关理解记忆 1、简述线性结构与非线性结构的不同点 答线性结构反映结点间的逻辑关系是 一对一的,非线性结构反映结点间的逻辑关系是多对多的。 2、数据结构中讲述的结构主要有哪四种?这四种又分别属于哪二个大类?请分别给出这二类结构中你学了哪些结构 答 1数据结构中的结构主要有以下四种:集合、线性表、树与图。 2这四种又分别属于线性与非线二个大类,其中线性表属于线性结构,树与图属于非线性结构。 3线性结构学了线性表、栈、队列、串、数组 非线性结构学了树、图 3、一般来说,一个问题往往有多种不同的算法,我们如何评价这些算法的好坏并能从中得到较好的算法呢? 答评价一个算法的好坏主要从二个方面进行:一个方面是时间,这个主要用时间复杂度来度量;另一个方面是空间,这个主要用空间复杂度不度量;考虑一个算法的优劣主要是从时间复杂度方面来考虑。 4、数据结构中的存储结构主要有哪二种它们分别通过什么来实现?他们各有什么特点与优缺点? 答 1数据结构中的存储结构主要有静态结构与动态结构 2静态结构主要通过数组来实现,动态结构主要通过链表来实现; 3静态结构的特点逻辑上相邻的元素在存储上一定相邻动态结构的特点逻辑上相邻的元素在存储上不一定相邻 4静态结构的优点:能随机访问,缺点是:插入删除要移动大量的元素;动态结构的优点:插入删除不需要移动元素,缺点是:不能随机访问元素 算法
// 一、使用C语言对链表进行排序
// 1、结构体的定义
typedef struct ListNode {int data;struct ListNode *next;
} ListNode, *List;// 2、排序的主逻辑
void sort(List L) {// 如果链表为空或者只有一个结点则无需排序if (L NULL || L-next NULL) {return;}ListNode *p, *q;// 外层循环for (p L-next; p ! NULL; p p-next) {// 内层循环for (q p-next; q ! NULL; q q-next) {// 如果数据较大交换数据if (p-data q-data) {int tmp p-data;p-data q-data;q-data tmp;}}}
}// 2、将两个集合合并
typedef struct list {ElemType *elem; // 集合元素int length; // 有效元素个数int listsize; // 集合的大小
}sqList// 将 la 和 lb 线性表归并到 la
void mergelist_sq(sqlist la, sqlist lb) {ElemType *pa, *pb, *pc, *pa_last, *pb_last;pa la.elem;pb lb.elem;pa_last la.elem la.length - 1;pb_last lb.elem lb.length - 1;// 合并后的表从 la 的末尾开始插入pc pa_last 1;// 归并 lb 到 lawhile (pb pb_last) {pa la.elem;// 在 la 中查找是否有与 pb 相等的元素while (pa pa_last) {if (*pa *pb) {break;}pa;}// 如果 la 中没有相等的元素则将 pb 插入 laif (pa pa_last) {*pc *pb;la.length;}pb;}
}
注意使用 Hoare法、 挖坑法 对同一组序列进行快速排序时最终排序的结果是一样的但是中间排序的结果可能会不一样。 若一组记录的排序码为(46, 79, 56, 38, 40, 84)则利用快速排序的方法以第一个记录为基准得到的一次划分结果为:() A、 38, 40, 46, 56, 79, 84 B、 40, 38, 46, 79, 56, 84 C、 40, 38 46, 56, 79, 84 D、 40, 38, 46, 84, 56, 79 1、Hoare法版 2、挖坑法版 上图题目的答案是C采取的挖坑法。
好啦本期 数据结构理论篇期末突击 的学习之旅 就到此结束啦我们下一期再一起学习吧
