aCannedFish's Home

1.基本概念 无向图 路径：在无向图G=(V,{E})中由顶点vi至vj 的顶点序列。 回路或环：第一个顶点和最后一个顶点相同的路径。 简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。 连通：顶点vi至vj之间有路径存在。 连通图：无向图图 G 的任意两点之间都是连通的，则称 G 是连通图。 连通分量：极大连通子图。 完全图：有 n(n-1)/2 条边的无向图。其中 n 是结点个数。 生成树：极小连通子图。包含图的所有 n 个结点，但只含图的 n-1 条边。在生成树中添加一条边之后，必定会形成回路或环。 有向图 路径：在有向图G=(V,{E})中由顶点vi经有向边至vj的顶点序列。 回路或环：第一个顶点和最后一个顶点相同的路径。 简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。 连通：顶点vi至vj之间有路径存在 强连通图：有向图图 G 的任意两点之间都是连通的，则称 G 是强连通图。 弱连通：有向图的基图（将有向边变成无向边后形成的图）是连通的。 强连通分量：极大连通子图 有向完全图：有 n(n-1) 条边的有向图。...

1.B树 基本性质 多路（m叉）平衡查找树，一般作为索引。文件系统，数据库系统，外部存储，自底向上生成并维持平衡。 B树或者为空，或者满足： 根结点要么是叶子，要么至少有两个儿子，至多有m个儿子； 除根结点和叶子结点外，每个结点至少有⌈m/2⌉个儿子，至多有m个儿子； 有s个儿子的结点有n = s - 1个关键字，这些结点的数据信息为： 关键字按非降序排列，且每个关键字都大于其左边的关键字，小于其右边的关键字； (n, A0, (K1, R1), A1, (K2, R2), ..., An-1, (Kn, Rn), An)，其中Ki为关键字，Ri为数据在硬盘中的地址，A0为小于K1结点的地址,Ai为指向数据记录的指针。 所有的叶子（外部/查找失败）结点都出现在同一层上，即它们的深度相同，并且不带信息。 插入 插入操作从根结点开始，沿着关键字的顺序向下查找，直到找到合适的叶子结点。 如果叶子结点有空间，则直接插入关键字和数据地址。 如果叶子结点已满，则需要分裂： 将叶子结点分裂成两个结点，并将中间的关键字上升到父结点。 如果父结点也满，则继续向上分裂，直到...

1.直接插入排序 代码实现 123456789101112template <class KEY, class OTHER>void simpleInsertSort(SER<KEY, OTHER> a[], int size) { int k; SET<KEY, OTHER> tmp; for (int j = 1; j < size; ++j) { tmp = a[j]; for (k = j - 1; k >= 0 && tmp.key < a[k].key; --k) { a[k + 1] = a[k]; } a[k + 1] = tmp; }} 效率分析 最好情况：O(n)，当数据已经有序时。 最坏情况：O(n^2)，当数据完全逆序时。 平均情况：O(n^2)，稳定的排序算法，因为每次插入都需要遍历已排序部分。 使用情况：排序元素较少，且几...

1.二叉查找树 二叉查找树或者为空，或者满足以下性质： 每个结点的左子树中所有结点的值都小于该结点的值。 每个结点的右子树中所有结点的值都大于该结点的值。 每个结点的左、右子树也是二叉查找树。 类定义 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980template <class KEY, class OTHER>class BinarySearchTree: public dynamicSearchTable<KEY, OTHER>{private: struct BinaryNode { SET<KEY, OTHER> data; BinaryNode *left; BinaryNode *right; ...

静态搜索表：集合中的结点总数是固定的或者很少发生变化。 动态搜索表：集合中的结点总数是经常在发生变化。 在内存中进行的搜索：重点减少比较、或查找的次数。评价标准：平均搜索长度。 在外存中进行的搜索：重点在于减少访问外存的次数。评价标准：读盘次数。 1.顺序查找 1234567template <class KEY, class OTHER>int seqSearch(SET<KEY, OTHER> data[], int size, const KEY &x){ data[0].key = x; for (int i = size ; x != data[i].key; --i); return i;} 时间复杂度为O(n)，其中n为数据元素的个数。 推导过程注意分为成功和不成功两部分，两种情况概率相等，同时每个结点搜索成功的概率也相等。 2.折半查找（二分查找） 123456789101112template <class KEY, class OTHER>int binarySearch...

1.基本概念 优先级队列是一种特殊的队列，其中每个元素都有一个优先级。出队时，优先级高的元素会先被处理。优先级队列可以用来实现任务调度、事件处理等。 优先级队列的简单实现： 方式一：入队时，按照优先级数值在队列（线性表）中寻找合适的位置，将新入队的元素插入在此位置。出队操作的实现保持不变。 方式二：入队时将新入队的元素直接放在队尾。但出队时，在整个队列中查找优先级最高的元素，让它出队。 时间复杂度分析： 方式一：入队操作的时间复杂度为O(n)，出队操作的时间复杂度为O(1)。 方式二：入队操作的时间复杂度为O(1)，出队操作的时间复杂度为O(n)。 2.二叉堆 二叉堆是一种特殊的完全二叉树，分为最大化堆(大顶堆)和最小化堆(小顶堆)满足堆的性质：对于每个节点，其值都大于或等于（或小于或等于）其子节点的值。 123例如:序列 { 2,3,4,5,7,10,23,29,60 } 是最小化堆 序列 { 12,7,8,4,6,5,3,1} 是最大化堆 教材默认最小化堆 优先级队列的堆实现 使用二叉堆来实现优先级队列，入队和...

1.树的抽象类 1234567891011template<class T>class tree {public: virtual void clear() = 0; virtual bool isEmpty() const = 0; virtual T root(T flag) const = 0; //非空，返回根节点；空树，返回flag virtual T parent(T x, T flag) const = 0; virtual T child（T x, int i, T flag) const = 0; virtual void remove(T x, int i) = 0; virtual void traverse() const = 0;}; 2.二叉树 基本定义 二叉树（Binary Tree）是结点的有限集合，它或者为空，或者由一个根结点及两棵互不相交的左、右子树构成，而其左、右子树又都是二叉树。 注意：二叉树必须严格区分左右子树。即使只有一棵子树，也要说明它是左子树还是右子树。交换...

1.队列的抽象类 12345678910template <class elemType>class queue{public: virtual bool isEmpty() const = 0; virtual void enQueue(const elemType &x) = 0; virtual elemType deQueue() = 0; virtual elemType getHead() const = 0; virtual ~queue() {}}; 2.顺序存储实现 实现分类 使用数组存储队列中的元素。 节点个数用MaxSize维护。 下标范围为0到MaxSize-1。 分三种组织方式： 队头位置固定：出队会引起大量的数据移动。 队头位置不固定：操作为O(1)，但需要记录队头和队尾的位置,同时会浪费数组空间。 循环队列：队头和队尾位置可以循环使用，避免了空间浪费，同时避免大量的数据移动。 3.循环队列 front指向队头前方的位置。 rear指向队尾位置。 操...

1.栈的抽象类 12345678910template <class elemType>class stack{public: virtual bool isEmpty() const = 0; virtual void push(const elemType &x) = 0; virtual elemType pop() = 0; virtual elemType top() const = 0; virtual ~stack() {}}; 2.顺序栈 代码实现 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162//类定义template <class elemType>class seqStack: public stack<elemType>{private: elem...

1.概念与定义 空或者只有一个结点。或者 1、存在唯一的一个被称之为“第一个”的结点。 2、存在唯一的一个被称之为“最后一个”的结点。 3、除第一个结点之外，每个结点均只有一个前驱结点。 4、除最后一个结点之外，每个结点均只有一个后继结点。 2.抽象类 12345678910111213template <class elemType>class list{ public: virtual void clear() = 0; //纯虚函数 virtual int length() const = 0; virtual void insert(int i, const elemType &x) = 0; virtual void remove(int i) = 0; virtual int search(const elemType &x) const = 0 ; virtual elemType visit(int i) const = 0; virtual void traverse() ...