Ferry's blog

Introduction栈的实现需要先了解几个背景：内存管理，接口继承，对象游离。 tip：引用：相当于存储对象的变量 Detail内存管理java使得引用不可修改，而相对于其它语言来说增加了一条特性：自动内存管理 当引用a被覆盖时，那么引用a原来指向的对象就成了孤儿，就会被回收。 当对象离开作用域后也会被回收。 例如： 动态数组1234567private void resize(int max){ Item[] temp = (Item[]) new Object[max]; for(int i = 0; i < N; i++) temp[i] = a[i]; a = temp; //让a指向了新数组，原来的a指向数组就成了孤儿。temp引用也会被回收。} 对象游离实现栈，主要的情景是：栈是占用使用数组的空间的。当我们应用pop()的实现中，弹出的元素仍然在数组中。而java的自动内存管理是针对那些再也无法被引用的对象的内存，所有回收不到这些pop出去的元素。所以，就要采取一种方法：将元素的引用...

二分查找法123456789101112131415161718192021222324252627282930313233343536373839import java.util.Arrays;public class BinarySearch { //Find the number by changing the hight limit and lower limmit of the array. public static int rank(int key, int[] a, Counter n) { int lo = 0; int hi = a.length - 1; while(lo <= hi) { int mid = lo + (hi - lo) / 2; n.increment(); if(key < a[mid]) hi = mid - 1; else if(key > a[mid]) lo = mid + 1; else return...

IntroductionFirstly，需要有对象的知识才能运用抽象数据的实现来实现代码。对象有三大性质：状态（实例变量），标识（构造函数），行为（实例方法）。 抽象数据类型的实现.md Detail实例变量即该数据类型的值，就像int who = 0; final这个关键字是指该值初始话后不会再改变。 因为根据java的定义，要用private来修饰它，如果用public那么这种数据类型将不会被看成是抽象的。 12private final String name;private int count; 构造函数它的作用是初始化实例变量，没有返回指定的返回值类型，但它返回对象的引用（就是拿来创建对象，所以它的名字和类名相同） 这里的构造函数只定义了name(一个实例变量）没有定义count（另外的实例变量）。那么这些值将会变成是默认的。默认的：原始数据类型为0，布尔类型为false，引用类型变量为null 1234public Counter(String id)//构造函数{ name = id;} 如果连构造函数都没有呢?...

Minimum Spanning　Tree 若图中有v个顶点，那么将生成v-1条边 这棵树包含了全部的顶点 不能有回路，且向树添加一条边就有回路 图连通<=>最小生成树存在 不唯一

Depth_First_Search过程 从某个顶点v1出发，然后找到并访问与v1的邻接点（且从未访问过）v2，再从v2出发访问与v2相邻的顶点。–>这就是递归思想 直到所有的顶点被访问到。 因为要记录该点是否被访问过，所以需要一个数组bool visited[MAXVEX]; 邻接矩阵遍历12345678910111213141516171819202122void DFS(MGraph G, int i){ int j; visited[i] = true; printf("%c ", G.vexs[i]); for(j = 0; j < G.numVertexs; j++) { //有边(i--j)，且 j 顶点没被访问 if(G.arc[i][j] == 1 && visited[j] == false) DFS(G, j); }}void DFSTraverse(MGraph...

前言由于图的多方向性，不能用顺序存储结构来实现。如果我用多重链表的话，那么结构中的多个指针就会造成空间资源的浪费（因为图的顶点上的度是不确定的）。因此图的存储结构，不应该使用物理存储去实现。图的实现被提供了5种存储结构。1. 邻接矩阵 2.邻链表 3.十字链表 4. 邻接多重链表 5. 边集数组。 邻接矩阵由顶点数组（一维）和边或弧数组（二维）组成 无向图 例如a[i][j]的0，1值表示，从i–j这个edge是否存在，1存在，0不存在。所以类似于a[i][i]这样的顶点到顶点的值都为0 无向图的边数组是一个对称矩阵，即满足a[i][j] ==...

前言二叉查找树的插入，删除等操作上都运用了递归来实现。首先，需要了解递归在执行递归调用之后的语句要以之前保存的变量反方向执行。 Insert这里的if-else看成一块，而return看成另一块。 每次插入会比较节点的大小，大的return右孩子，小的return左孩子，直到找的到孩子为NULL就创建节点T->Left = Insert(X, T->Left);T->Right = Insert(X, T->Right); 如果，我们传入根节点，那么递归调用之前的语句被执行后，均按被调函数相反的顺序执行。所以，最后会传回根节点。 123456789101112131415161718192021SearchTree Insert(ElementType X, SearchTree T){ if(T == NULL) { /* Create and return a one-node tree */ T = malloc(sizeof(TreeNode)); if(T ==...

不要使用没初始化的指针即只能使用指向已经分配空间的指针。否则可能会擦拭掉数据或代码。 可以，因为第二行就让指针指向字符串ferry12char *str;str = "ferry" 不可以，scanf（）是把信息拷贝到指定的地址上12char *str;scanf("%s", str); 不可以，跟上面情况一样，不要解引用未初始化的指针12int *a;a = 2; 时刻记得指针指向的地址（位置）当我们用指针遍历数组的时候，遍历完以后就已经不再指向数组首元素地址了 123int *i;int arr[10];i = arr;

DefinitionRecursion the process of repeating a function, each time applying it to the result of the previous stage. ​ 经过树形结构，和嵌套结构后的思想：可像数学函数一样，一个个嵌套，完美解决递归 演示递归 debug1234567891011121314151617/* recur.c -- recursion illustration */#include <stdio.h>void up_and_down(int);int main(void){ up_and_down(1); return 0;}void up_and_down(int n){ printf("Level %d: n location %p\n", n, &n); // 1 if (n < 4) up_and_down(n+1); ...

概念二叉树的遍历是从根节点出发，按照某几种不同的顺序遍历每个节点，使得每个节点被遍历仅一遍。这些遍历方法分为：1. 前序遍历2. 中序遍历3. 后序遍历4. 层序遍历规则：若树为空(T == NULL)，则空操作返回(return)，否则执行访问（递归） 说明如何看待遍历顺序？![(https://i.loli.net/2020/05/19/1W6rsVNP9hJubB8.png) 这张图已经完美说明了。首先，把这颗树加上空节点看成是完全二叉树，然后就它们的孩子嵌套并于括号括起来。 前序遍历 打印顺序：父母。左子孙。右子孙。 12345678void PreOrderTraverse(Tree T){ if(T == NULL) return; printf("%c", T->e); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild);} 中顺遍历 打印顺序：左子孙。父母。右子孙。 12345678void...