数据类型:一个值的集合以及在这些值上定义的一组操作的总称。
线性表定义:每个数据元素最多只有一个直接前趋,每个数据元素最多只有一个直接后继,只有第一个数据元素没有直接前趋,最后一个数据元素没有直接后继。
线性表的存储分为顺序存储和非顺序存储。
顺序存储也称为向量存储或一维数组存储。特点是逻辑关系上相邻的两个元素在物理位置上也相邻,随机存取元素简单,插入删除会造成大量数据移动。线性表的顺序存储的情况下插入和删除算法的时间复杂度为o(n);求表长以及取第i个元素的时间复杂度为o(1);
线性表的链式存储,不要求逻辑上相邻的数据元素在物理位置上也相邻。由于不要求物理位置上也相邻,那么每个节点对象包含两个元素,一个是当前值,一个是指向下一个节点的地址。如果插入某个值,那么将插入的值的节点指向之前的后继,之前的指向下一个节点指向这个插入的节点即可。
链式存储的查找比较麻烦,要按照顺序一个一个查,求表长也如此。单向链表,头节点至关重要。循环链式存储,是指最后一个元素的next指向头部。这样以来,就可以查找每个元素的前趋。
双向链表是在每个节点的值和next两个元素的基础上,再加一个prior,用来保存指向前趋的指针。当然还有双向循环链表。
栈:先进后出。限制只有栈顶才可以操作。每次pop删除的总是最新元素,每次push压入的元素也总是最新元素。
实现栈的方式:顺序栈和链式栈
顺序栈:入栈是在线性表的头部插入元素,出栈是在线性表的头部删除一个元素。这样效率不高,时间代价为o(n)。如果是在线性表的尾部作为栈顶,插入删除元素,那么时间代价为o(1),效率高。
链式栈:单向链表存储栈。操作一般在头部。
顺序栈和链式栈比较:当需要堆栈共享时,顺序栈可以使用一个数组存储两个栈, 数组的两端作为两个栈各自的栈低,中间部分为共享区域。这样的情况适合两个栈有相反的需求时,此消彼长的情况。链式栈是每个节点多了一个指针域的开销。
队列:先进先出。只需要操作线性表的两端。一端只能进入,另一端只能出。队尾进,队首出。有顺序存储和链式存储两种。队列假溢出是因为队首指针确定导致的,就是被删除的元素空间无法被重复利用。可以让队首和队尾的指针循环起来就可以,就是将元素存储在循环向量中。
顺序队列:必须用一个向量空间来存放元素。设置front和rear分别来指示队首和队尾的位置。
循环队列:就是将元素存储在循环向量中。
矩阵存储分为行优先和列优先两种。
矩阵压缩存储,是针对特殊矩阵队存储,只存储其元素一部分,另一部分通过相应的算法计算出来。这样的矩阵包括对称矩阵,稀疏矩阵和三角矩阵。
(t+1)*3<=m*n
即可
广义表是线性表的扩展。元素包括
如果所有元素都是原子元素则是线性表。如果有可以再分的元素,也就是子表,则是广义表。广义表含有元素的个数称为广义表的长度,广义表中含有括号对数称为广义表的深度,也就是层。
非线性结构。树的递归定义:树是由根节点和若干棵子树构成的。
一个节点的子树个数称为该节点的度。
度为零的节点称为叶子或终端节点。不为零的为分支节点。除根节点之外的称为内部节点。
一棵树中节点度最大的值称为该树的度。
二叉树:或者为空,或者由一个根节点加上两棵左右互不交叉的子树构成。
二叉树的顺序存储:只存储节点的值,不存储节点之间的逻辑关系
二叉树的链接存储:每个节点由数据域和指针域两部分组成。指针域有两个,一个指向父亲,一个指向儿子。
二叉树遍历,包括前中后三序遍历,以及层次遍历。
当我们遍历完二叉树,就形成一个线性序列,于是就有了唯一的前趋和后继节点。
线索二叉树,就是为了解决寻找前趋和后继的。每个链接节点有五个变量,通常树都是链式存储。
将一棵树转为二叉树的方法:
这样的旋转可以证明是唯一的。而且过程是可逆的。
将二叉树还原为普通树的方法:
树的遍历分为先根遍历和后根遍历。
森林的遍历分为前序遍历和中序遍历。
哈夫曼树,也是二叉树。这种二叉树的带权路径长度最小。并且每个权值都是叶子节点。
带权路径长度为根节点到该节点之间的路径长度与该节点的值的乘积。该节点的值,是我们人为指定的。
路径长度是层数减1.根节点为第一层。
图是非线性结构。图中任何两个顶点都可能有关联,顶点间的关系是多对多点关系。图的每个节点有任意多个前趋和后继。图分为有向图和无向图。带权的图称为网。网分为有向网和无向网。
图的邻接矩阵表示法和邻接表表示法。
邻接矩阵,行与列分别表示各个顶点。1表示有边,0表示没有边。比如第一行第二列是1,则表示顶点1到顶点2有边。第三行第四列是1,则表示顶点3到顶点4有边。这是有向图。如果是无向图的话,那么矩阵是对称的,就是说如果第三行第四列是1,那么第四列第三行也是1,因为顶点3和顶点4的边没有方向。
邻接表:是图的一种链式存储结构。先建立一个链表存储每个顶点。每个顶点有两个域,邻接点域和指针域。邻接点域存序号,指针域指向边的表节点。边表是存储顶点与邻接点具有边关系的表,每个节点也有两个域,指针域指向下一个与邻接表节点具有边关系的顶点。比如顶点1与顶点2,3都有边。那么顶点1在邻接表中的指针域指向边表的顶点2的位置。边表中顶点2的指针域指向与顶点1有边的顶点3的位置。
图的深度优先遍历和广度优先遍历
深度优先遍历:递归访问顶点,直到某个顶点没有未被访问的顶点为止,开始访问它的前趋。如果前趋是最开始访问的那个顶点,就结束遍历。
广度优先遍历:从最开始的访问点出发,访问与它邻接的所有点,再从这些邻接点出发访问它们的邻接点。直到所有顶点均被访问为止。
克鲁斯卡尔算法。普里姆算法
最短路径:迪卡斯特拉算法
拓扑排序:从网中旋转一个入度为0的顶点并输出。也就是没有其它顶点指向这个顶点,只有这个顶点指向其它顶点。从网中删除此顶点及其所有出边。如此循环。拓扑排序解决的是各个顶点的依赖关系的有序数列。
排序的稳定性是根据需要排序的元素中的关键字如果有相等的情况,那么这些相等关键字的元素如果排序前后的相对位置不变就是稳定的,如果这些相等关键字的元素相对位置发生了改变,就是不稳定的。
排序过程中是否涉及数据的内外存交换可以将排序分为:
动态内存分区常用算法:
最先适配法(nrst-fit):按分区在内存的先后次序从头查找,找到符合要求的第一个分区进行分配。该算法的分配和释放的时间性能较好,较大的空闲分区可以被保留在内存高端。但随着低端分区不断划分会产生较多小分区,每次分配时查找时间开销便会增大。
下次适配法(循环首次适应算法 next fit):按分区在内存的先后次序,从上次分配的分区起查找(到最后{区时再从头开始},找到符合要求的第一个分区进行分配。该算法的分配和释放的时间性能较好,使空闲分区分布得更均匀,但较大空闲分区不易保留。
最佳适配法(best-fit):按分区在内存的先后次序从头查找,找到其大小与要求相差最小的空闲分区进行分配。从个别来看,外碎片较小;但从整体来看,会形成较多外碎片优点是较大的空闲分区可以被保留。
最坏适配法(worst- fit):按分区在内存的先后次序从头查找,找到最大的空闲分区进行分配。基本不留下小空闲分区,不易形成外碎片。但由于较大的空闲分区不被保留,当对内存需求较大的进程需要运行时,其要求不易被满足。
身份认证 购VIP最低享 7
领优惠券(最高得80元)
构成广义表的合法字符:大写或者小写的字母,空白字符,原括弧和逗号,且设广义表的原子为单个字母。 演示程序使用户了解每一步的操作功能,分步显示每一步的操作结果。 程序执行的命令 1)建立广义表,提示用户输入广义表字符串 2)求广义表的表头、表尾、长度、深度等功能 完成数据输入测试 A.创建广义表 B.取表头 C.取表尾 D.求长度 E.求深度 F.求原子结点个数 G.复制广义表 H.原表插入 I.遍历广义表 J.比较广义表 K.销毁表 Q.退出