doubleyong
管理员
管理员
  • 最后登录2022-01-18
  • 发帖数1052
  • 最爱沙发
  • 喜欢达人
  • 原创写手
  • 社区居民
  • 忠实会员
阅读:146回复:0

数据结构总结

楼主#
更多 发布于:2021-12-29 11:46
1. 关于算法

(1) 什么是算法?
算法:顾名思义,一种计算的方法,在程序设计上,就表现为一组指令序列。

(2)算法与程序有什么区别和联系?
程序是指用某种计算机语言对一个算法的具体实现,即具体要怎么做,
算法偏重于对解决问题的方法的描述,即要做什么。

(3)如何评价算法的优劣?
时间复杂度与空间复杂度

一个算法应该具有以下五个重要的特征:
有穷性(Finiteness)
算法的有穷性是指算法必须能在执行有限个步骤之后终止;

确切性(Definiteness)
算法的每一步骤必须有确切的定义;

输入项(Input)
一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法本身定出了初始条件;

输出项(Output)
一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的;

可行性(Effectiveness)

2. 栈的特性是什么

栈的特点是先进后出表。栈是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据。


3. 稀疏矩阵
0 0 3 0 0 0
1 0 0 0 0 6
0 0 4 0 0 0
0 2 0 0 5 0
0 0 0 0 0 0
(1) 写出该稀疏矩阵的三元组顺序表(行优先)存储表示。
(2) 简要叙述将稀疏矩阵进行转置的算法思想,并给出转置结果。

行优先的表现形式: (行,列,数值)
((1,3,3),(2,1,1),(2,6,6),(3,3,4),(4,2,2),(4,5,5))

进行行转置的方法有:
方法1(简单,但是无序):直接将行和列的值互换
方法2(最后有序,还是按照行优先显示):
1. 遍历三元组顺序表,找列为1的值,执行行列互换 ;
2. 依次重复1的操作,直到所有列都互换




4. 哈夫曼树、哈夫曼编码
假定电文字符集为{A,B,C,D,E,F,G,H),它们在电文中出现的次数分别为{20,7,13,6,39,4,14,5},请为这8个字符设计哈夫曼编码。画出哈夫曼树并给出编码。要求在构造哈夫曼树的过程中,其中权值较小结点放在左侧,编码时左分支生成代码0,右分支生成代码1
(术语: 路径 、 路径长度、权重 、wpl : 【路径长度 * 权重】 的总和 )

(画图方法:将最小的两个数进行连接,连接的和又放入比较的数中;  注: 左小右大)


哈夫曼编码:根据画的图写出编码;(左0右1)

wpl : 路径长度*权重  相加之和
如: wpl = (20+39) *2 + (13+14)*3 + (4+5+6+7) * 4

5. 哈希函数

对关键字集合{1,19,10,23,11, 84,14,27,20},哈希地址空间为HT[O0 ..14],若采用除留余数法构造哈希函数和线性探测再散列方法处理冲突,试画出最后得到的哈希表,并计算在等概率情况下查找成功时的平均查找长度ASL。

(1)写出用除留余数法构造的哈希函数。
( 函数 : H(key)=key  MOD  p , p<=m   (最简单,最常用)p的选取很重要
一般情况,p可以选取为小于或等于空间长度的最大质数))
H(key) = key  mod 13

(2)采用线性探测再散列处理冲突,试画出最后得到的哈希表。
1 mod 13 = 1       23 mod 13 = 10     14 mod 13 = 1
19 mod 13 = 6     11 mod 13 = 11     27 mod 13 = 1
10 mod 13 = 10    84 mod 13 = 6    20 mod 13 = 7

 下标  0  1  2  ...
 数值  
 1  14  
 查找长度  
 1  2  


(3)计算在等概率情况下该哈希表在查找成功时的平均查找长度ASL。ASL =  (1+2+3+1+2+2+1+2+2) / 9

6.二叉排序树
依次读入给定的整数序列{6,15,5,7,19,8,5,17,4},完成下列操作:

(1)构造该二叉排序树; (以第一个数为根,比根结点小的放在左边,比根结点大的放在右边)

(2)计算在等概率情况下该二叉排序树的平均查找长度ASL。
(第一层的一次,第二层的两次,依次累推)ASL =  (1+(2*2) +  (3*3) + (4*2) ) / 9 =


7. 最小生成树

克鲁斯卡尔算法(Kruskal算法):
1. 对边进行排序(升序)
2. 不同连通分量上的顶点进行连接



普界姆Prim算法方法:
1. 选择任何一顶点,做为起始点
2. 找与顶点相连接的最小权的边,注:不形成回路的边
3. 重复1、2步骤,直到所有顶点相连,即边为n-1为止


注意事项:

构成生成树的准则有三条:
<1> 必须只使用该网络中的边来构造最小生成树。
<2>必须使用且仅使用n-1条边来连接网络中的n个顶点
<3>不能使用产生回路的边。

8. 线索二叉树

建立线索的规律如下:
1、若当前访问的结点的左指针域为空,则左指针域指向prior指的结点,同时置lbit为0,否则,置lbit为1;
2、若prior所指结点的右指针域为空,则右指针域指向当前访问的结点,同时置rbit为0,否则,置rbit为1;
3、遍历结束时,将prior->rchild指向头结点,并置prior->rbit为0。


(画线索二叉树时,会告诉你是先序线索二叉树,中序线索二叉树,后序线索二叉树;当结点无左孩子时,将其指向它前面的结点,而结点的顺序是指先序或中序或后序的顺序。无右孩子时,指向序列后面的结点)

9. 平衡二叉树

定义:任意结点的左、右子树高度差的绝对值不超过1,将这样的二叉树称为平衡二叉树,简称平衡树(AVL树)。
  定义结点左子树与右子树的高度差为该结点的平衡因子,则平衡二叉树节点的平衡因子的值只可能是-1,0,1


判断是否为大顶堆的方法(参考:https://www.bilibili.com/video/BV1RL4y1e72q
看前面的数字是否大于后台两个数字,依次进行判断 - 相当于转成对应二叉树,再来比较)


10. Dijkstra 最短路径

列出起点, 终点,path , dist 距离起点:根据题的要求为0
终点为1,2,3,4;path 表示,从那个点到的终点
dist 表示距离起点到终点有路径就写对应的值,没有就写-1,其它在找距离中最小的点,加入到起点集合中,判断此到其它点的路径,如果小于就一次写的路径,就对路径与距离进行替换

11. 判断有向图是否有环

判断方法:
拓扑排序: 还有顶点末输出,但已经不存在没有前驱的顶点了
深搜:从一个顶点出发存在搜回到自己的路径

12. 拓扑序列
1、从AOV网中选择一个没有前驱的顶点并且输出
2、从AOV网中删除去该顶,并且删除所有以该顶点为尾的弧
2、重复所有操作,直到所有顶点全部输出 ,或AOV网中不存在没有前驱的顶点

若此时输出的顶数小于有向图的顶点数,则说明有向图中存在回路
对一个有向图构造拓扑序列的过程,称为拓扑排序


13. 图的深度遍历DFS与广度遍历BFS

DFS:
1、遍历过的节点不重复遍历(根据邻接表)
2、回溯



BFS:进入一个元素,出队,然后,将出队的这个元素后面的节点,添加再队列后面
判断是否为AOV,什么意思,判断的条件是什么注:不要重复,重复的不要入队




14. 森林与二叉树的转换

森林转二叉树的方法
a. 将森林中所有的普通树各自转化为二叉树
b. 森林中第一棵树的树根作为整个森林的树根其他树的根节点看作是第一棵树根节点的兄弟节点,采用孩子兄弟表示法将所有树进行连接
树或森林与二叉树之间有一个自然的一一对应关系。任何一个森林或一棵树可惟一地对应到一棵二叉树;反之,任何一棵二叉树也能惟一地对应到一个森林或一棵树。

将树转换为二叉树:
树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树:
1.在所有兄弟结点之间加一连线
2.对每个结点,除了保留与其长子的连线外去掉该结点与其它孩子的连线
知识需要管理,知识需要分享
游客


返回顶部

公众号

公众号