weixin_43723259-CSDN博客

原创虚拟机下载完Vmware Tool仍无法对文件进行拖拽

解决方法查阅了好多资料，看来好多解决方法都没用，最后终于找到解决方法了，只需要下面三步1.vmware-uninstall-tools.pl2.apt-get install open-vm-tools-desktop3.重启

2022-02-17 11:02:04 668

二叉树遍历中序遍历所谓中序遍历就是先访问左孩子，再访问根节点，最后访问右孩子。递归：template <typename T, typename VST>void travIn_R (BinNodePosi(T) x, VST& visit){//二叉树中序遍历算法（递归版） if(!x) return; travIn_R(x -> lc, visit); visit(x -> data); travIn_R(x -> rc, visit);}

2021-08-06 12:51:19 189

原创数据结构学习（二叉树：三（先序遍历））

二叉树遍历所谓二叉树遍历就是将二叉树中的每个节点依次进行访问，访问次数有且只有一次。其实这一过程是相当于将二叉树半线性结构转换为线性结构。不过毕竟二叉树结构已不再是线性结构，所以对它的遍历相对复杂一些。二叉树本身不具有天然的全局次序，故为实现遍历，首先需要在各节点于其孩子之间约定某种局部次序，从而间接的定义处全局次序。将各节点及其孩子分别记作V, L, R，局部访问次序有VLR、LVR、LRV三种选择，这三种访问次序也分别被称作先序遍历、中序遍历、后序遍历。先序遍历先序遍历算法分为两种：递归和迭代。

2021-08-04 15:15:23 237

原创数据结构学习（二叉树：二（二叉树的实现））

二叉树的实现作为图的特殊形式，二叉树的基本组成单元是节点和边，作为数据结构，其基本组成实体是节点。而边则对应于节点之间的相互引用。二叉树节点BinNode模板类：#define BinNodePosi(T) BinPosi<T>* //节点位置#define stature(p) (()p) ? (P) -> height : -1) //节点高度（与“空树高度为-1”的约定相统一）template <typename T> struct BinNode{//

2021-08-02 16:54:19 74

原创数据结构学习（二叉树：一（二叉树及其表示））

树通过前面的学习，我们主要学习了几种线性的数据结构，根据其实现方式，我们可以大致将其分为两种：基于数组的实现与基于链表的实现。正如我们看到，就其效率而言，二者各有长短。前者允许我们通过下标或秩，在常数时间内找到目标元素；然而对其修改时（插入或删除）则需要线性时间。后者允许我们借助引用或位置对象，在常数时间内插入或删除对象；但是为了找出特定次序的元素，我们却不得不花费线性的时间。而树这种结构会在同时优化静态以及动态的操作。有根树从图论的角度看，树等价于连通无环图。树由一组顶点以及联接与其间的若干条

2021-08-02 15:24:15 261

原创数据结构学习（栈与队列：五（队的接口与实现））

队队的接口与实现与栈一样队也是一种存放数据对象的一种容器，且也是按线性的逻辑次序排列。队列结构同样支持对象的插入与删除，但这两种操作是被限制在队的两端，若约定对象只能从一段插入，则只能从另一端删除已有的元素。允许取出元素的一端被称为队头。允许插入的一端的元素被称作队尾。一般将元素的插入和删除操作分别称作入队和出队。有以上的约定不难看出，与栈的结构恰好相反，队列中各元素的操作次序遵循所谓的先进先出（first-in-first-out，FIFO）。更早（晚）出队的元素应为更早（晚）入队者。ADT接口

2021-07-29 22:41:43 49

原创数据结构学习（栈与队列：五（延迟缓冲））

延迟缓冲表达式求值下面给出上一届代码中orderBetween（）函数与readNumber（）函数：void readNumber(char*& p, Stack<float>& stk){ //将起始于p的子串解析为数值，并存入操作数栈 stk.push((float) (*p - "0"));//当前数位对应的数值进栈 while (isdigit(*(++p))) //只要后面还有紧邻的数字（即多位整数的情况），则 stk.push(stk.pop*10

2021-07-29 14:45:09 98

原创数据结构学习（栈与队列：四（栈的典型应用（延迟缓冲）））

栈的典型应用延迟缓冲在一些应用问题中，输入可分解为多个单元并通过迭代依次扫描处理，但过程中各步计算往往滞后于扫描的进度，需要等到必要的信息已经完整到一定程度之后，才能做出判断并实施计算的这类场合，而栈则可以扮演数据缓冲区的角色。表达式求值中缀表达式的求取便是一个延迟缓冲的问题。当程序扫描一个表达式并对其进行求取，无法在刚扫描之后就对表达式的部分进行求取，而是要判断一下某个运算符是否在此时可以进行运算，而这个判断完成时往往是滞后于扫描速度的。这时候就可以运用栈工具，比如，现在要求取下面这个表达式：

2021-07-29 14:01:15 212

原创数据结构学习（栈与队列：三（栈的典型应用（递归嵌套）））

栈的典型应用递归嵌套栈还适合解决一类问题，这类问题的特点是：具有自相似的（某一局部往往和整体具有某种共性）问题多可嵌套的递归描述，但因分支位置和嵌套深度并不固定，其递归算法不易控制。栈结构天然的具有递归嵌套性，故可高效地解决这类问题。括号匹配括号匹配就是一种递归嵌套的问题，其任务是，在任一程序块，判断其中的括号是否在嵌套的意义下完全匹配。对于这各任务，我们只需要将push、pop操作分别与左括号和右括号相对应即可：bool paren(const char exp[], int lo, int

2021-07-27 16:52:09 367

原创数据结构学习（栈与队列：二（栈的典型应用（逆序输出）））

栈的典型应用逆序输出栈很适合解决了一类问题，这类问题的特点是：1.虽有明确的算法，但其解答却以线性序列的形式给出。2.无论是递归还是迭代实现，该序列都是以逆序计算输出的。3.输入和输出规模不确定，难以实现确定盛放输出数据的容器大小。进制转换进制转换就是一种逆序输出问题，现在要将十进制数进行其它进制的转换。比如要将十进制转换为二进制，首先将这个十进制的数除以2，然后得到一个商和一个余数，之后再将这个商除以2，得到新的商和一个余数，之后不断进行迭代，直至商为0，之后将得到的一个余数从后往前排列，这个得到

2021-07-26 23:54:27 965

原创数据结构学习（栈与队列：一（创建Stack模板类））

栈栈的模板类栈是一种存放数据的特殊容器，其中元素按线性的逻辑顺序排列。栈也支持元素的插入和删除操作，不同的是，其操作的范围仅限于栈的某一特定端，禁止操作的另一端成为盲端。就像把椅子叠成一摞一样，新的椅子只能放到最顶端；反过来，只有最顶端的椅子才能被移走。就像栈一样，可操作的一段被称之为栈顶，不可操作的一端称之为栈底。由以上栈操作的叙述不难看出，栈中元素接受操作的次序必须遵循所谓的后进先出（Last-in-first-out，LIFO) 的规律。栈可以视作序列的特例，，故可以将栈作为向量类的派生类

2021-07-26 23:12:07 207

原创数据结构学习（列表：五（有序列表的排序算法））

有序列表选择排序选择排序算法将有序列表的分为无序前缀和有序后缀两部分，此外，还要求不大于后缀，如此，只需要从前缀中挑出最大者，并作为最小元素转入后缀中，即可使有序部分的范围不断扩张。这个算法的不变性是：在任何时刻，后缀（r，n）已经有序，且不小于前缀S[0，r]。算法初始时刻，后缀为空，不变性自然满足。于是在前缀中找出最大者，并作为首元素插入后缀，使得后缀的范围扩大，并继续保持有序。如此，该后缀的范围不断扩大，直至最终覆盖整个序列，亦即整体有序。//对起始于位置p的n个元素进行排序template

2021-07-25 23:03:25 680 1

原创数据结构学习（列表：四（有序列表的唯一化、查找算法））

有序列表唯一化处理与有序向量同理，有序列表中重复的元素一定（在逻辑上）紧邻。设置位置指针p和q分别指向相邻的节点，若二者雷同则删除q，否则转向下一对相邻节点如此反复迭代，直至检查所有节点：template <typename T> int List<T>::uniquify(){ if(_size < 2) return 0; //元素数量小于2，自然无重复。 int oldSize = _size; //记录原始规模 Posi(T) p = first();

2021-07-24 22:22:26 234

原创数据结构学习（列表：三（无序列表复制、删除、唯一化操作））

无序列表复制列表的内部结构是动态创建的，故利用默认的构造函数无法真正的完成列表的复制创建，为此，需要编写专门的构造方法，有多种复制方式，这里提供一个底层内部方法copyNodes()：template <typename T> void List<T>::copyNodes(Posi(T) P, int n) //p合法，且至少有n-1个后继节点{ init(); //创建头、尾节并作初始化 while(n--) [ //将自p起的n项依次作为末节点插入 i

2021-07-21 16:35:05 112

原创数据结构学习（列表：二（无序列表查找操作））

无序列表创建列表类模板template <typename T> class List{ private: int _size; Posi(T) header; Posi(T) trailer;//规模、头节点、尾节点 protected: void init();//列表创建时初始化 int clear(); //清除所有节点。。。一系列函数 public: Posi(T) first() const {return header -> succ;} /

2021-07-21 15:23:25 756

原创数据结构学习记录（列表：一（接口与实现））

列表的接口与实现从静态到动态数据结构支持的操作，通常有静态到动态两类。静态指从中获取信息，动态则会修改数据结构的局部甚至整体。向量一般是通过循秩访问根据元素的秩在O（1）的时间内直接确定其物理地址，V[i]的物理地址=V+i×s，s为单个占用空间量。列表则是循位置访问，利用节点间的相互引用，找到特定节点。与向量一样，列表也是由具有线性逻辑次序的一组元素构成的集合： L = {a0，a1, a3, a4…an-1}其中的元素称作节点。首先需要定义节点的模板类：typedef int Rank;

2021-07-21 12:55:42 55

原创数据结构学习记录（向量：五（有序向量的排序算法））

有序向量的排序起泡排序void bubblesort (int A[], int n){ bool sorted = false; //整体排序标志，假设其尚未排序 while (!sorted) //只要全局排序没有完成，就逐趟进行扫描 { sorted = true; //假定已经排序 for(int i = 1; 1 < n, i++) //自左向右逐一检查各相临元素 { if(A[i - 1] < A[i]) //如果逆序 {

2021-07-20 23:48:46 645 4

原创数据结构学习（向量：四（有序向量的查找算法））

数据结构学习（向量：四）有序向量查找二分查找（版本A）//在有序向量[lo, hi)内查找元素e，返回其秩template <typename T> static Rank binSearch(T* A, T const& e, Rank lo, Rank hi){ while(lo < hi) //每次迭代至多多两次比较，有三个分支 { Rank mi = (lo + hi)/2; //以中点为轴点 if(e < A[mi]) hi

2021-07-20 11:14:34 142

原创数据结构学习（向量：三（有序向量的唯一化处理））

数据结构学习（向量：三）有序向量唯一化处理处于效率的考虑，一般而言，有序向量的唯一化处理更加重要，所以一般清除重复向量，先将其转化为有序向量。低效版//低效版template <typename T> int Vector<T>::uniquify(){ int oldsize = _size; //记录原始的向量规模 int i = 1; while (i < _size) //从前向后，逐一比对相邻的元素对 _elem[i -

2021-07-19 11:16:29 155

原创数据结构学习记录（向量：二（无需向量的查找与唯一化算法））

无序向量查找template <typename T> Rank Vector<T>::find(T const& e, Rank lo, Rank lo){ while((lo < hi--) && (e != _elem[hi])) //从后向前，顺序查找 return hi; //若hi < lo, 则查找失败，否则hi为命中元素的秩 } 复杂度：O（n），此类算法属于输入敏感型算法。唯一化处理对数据进行处理，要求向量

2021-07-15 14:41:16 93

原创数据结构学习记录（向量：一（无需向量的插入与删除算法））

无序向量插入template <typename T>Rank Vector<T>::insert (Rank r, T const& e){ expand(); //如有必要，进行扩容。 for (int i = _size; i > r; i--) _elem[i] = _elem[i-1]; //自后向前，后继元素顺次后移一个单元 _elem[r] = e; _size++;.

2021-07-15 13:44:48 69

weixin_43723259的博客