Nim的辙迹

*资料整理来源：《数据结构（C语言版）》–严蔚敏、吴伟民编著1.ADT描述 抽象数据类型（abstract data type,ADT)是指一个数学模型以及定义在该模型上的一组操作。 ADT 抽象数据类型名{ 数据对象：<数据对象的定义> 数据关系：<数据关系的定义> 基本操作：<基本操作的定义> }ADT 抽象数据类型名其中，数据对象和数据关系的

双向冒泡排序，又名鸡尾酒混合排序，是对冒泡排序的一种改进算法。 每完成一次循环就将最大元素排在队尾，最小值排到队头，时间成本能节约1倍。其算法如下：void DoubleBubbleSort(int r[],int size){ int i,low=0,high=size-1,temp; bool exchange; while(low<high) {

起泡排序的过程很简单。首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换之，然后比较第二个记录和第三个记录的关键字。依次类推，直至第n-1个记录和第n个记录的关键字进行比较为止。上述过程称作第一趟起泡排序，其结果使得关键字最大的记录被安置到最后一个记录的位置上。然后进行第二趟起泡排序，对前n-1个记录进行同样操作，其结果是使关键字次大的记录被安置到第n-1个记录的位置上

单链表、双链表介绍及其C++实现

栈的介绍以及顺序栈、链栈、STL自带的栈的实现

链队列介绍及C++实现方法

循环队列的介绍及C++实现方法

二叉查找树的介绍及其C++实现

AVL树（高度平衡二叉树）的介绍及其C++实现

Prim算法和Kruskal算法的介绍，用来求加权连通图的最小生成树的算法。

最长递增子序列问题的算法最低要求O(nlogn)的时间复杂度

常用八大排序算法的总结

快速排序是对起泡排序的一种改进。 它的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分的记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。如何判别快速排序的结束？ 若待排序列中只有一个记录，显然已有序，否则进行一次划分后，再分别对分割所得的两个子序列进行快速排序（即递归处理）。int Partition(int r[],int fir

什么是拓扑排序？简单地说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。偏序：只有部分可以比较关系 全序：全部都能比较关系AOV网：用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网。 在AOV网中，不应该出现有向环，因为存在环意味着某项活动应以自己为先决条件。对给定的AOV网判定网中是否有环？ 拓扑序列使得AOV网中所有应存在的前驱和后继关系都能得到

直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。一般情况下，第i趟直接插入排序的操作为：在含有i-1个记录的有序子序列r[1..i-1]中插入一个记录r[i]后，变成含有i个记录的有序子序列[1..i]；并且，和顺序查找类似，为了在查找插入位置的过程中避免数组下标出界，在r[0]处设置监视哨。在自i-1起往前搜索的过程中，可

**数据结构–用C++实现string**这两天在写string类，实现方法是定长顺序存储。将串定义成字符数组，利用串名可以直接访问串值。用这种表示方法，串的存储空间在编译时确定，其大小不能改变。代码如下： 文件MyString.h#ifndef MyString_byNim#define MyString_byNim#include<iostream>#include<string.h>u

**数据结构–用C++实现顺序表** Sequence List(Array): 线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素 顺序表为静态存储分配，需要事先确定容量老师课上提供了一个class模板，如下： 那么，我们现在可以根据这个模板开始造轮子了。代码实现思路很简单，按照上面提供的函数用自己的方法一步步完善就可以了。为了使这个顺序表适用于不

图的基本概念： 1）图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G=(V ，E) 其中：G 表示一个图，V 是图G 中顶点的集合，E 是图G中顶点之间边的集合。 2）在图中，顶点个数不能为零，但可以没有边。 3）在图结构中，任意两个顶点之间都可能有关系。 4）在图结构中，顶点之间的关系为邻接 。 5）若代表一条边的顶点序偶是无序的(即该边无方向)，则称此图为无向图。 若

数组的定义： 数组是由一组 类型相同 的数据元素构成的有序集合，每个数据元素称为一个数组元素（简称为元素），每个元素受n(n ≥1)个线性关系的约束， 每个元素在n个线性关系中的序号i1 、i2、… 、in 称为该元素的下标，并称该数组为n维数组。有点难理解，没关系，我们看下面这个二维数组： 例如，这是个二维数组，因此元素a22受两个线性关系的约束，在行上有一个行前驱a21和一个行后继a23

无向图的邻接多重表已经在之前一篇文章里介绍了：传送门下面我进一步地来介绍如何实现无向图的初始化，深度优先搜索DFS，广度优先搜索BFS，深度优先搜索的非递归算法1.无向图的初始化：//建立顶点表 void AddVex(OLGraph *G){ int i; for(i=0;i<G->vexnum;i++) { G->xlist[i].data=i;

这篇我们来解决下上一篇留下的两个问题：深度优先生成树和广度优先生成树如何建立？1.深度优先生成树 首先，我们需要读懂的是邻接表下的深度优先生成树，因为这种结构下的方法比较容易推敲，理解之后进而推广到邻接多重表上。我们先以《数据结构（C语言版）》–严蔚敏、吴伟民编著的教材上算法7.7为例，分析下深度优先生成树是如何建立的：void DFSTree(Graph G,int v,CSTree &T){

树型结构和图型就是其中十分重要的非线性结构，可以用来描述客观 世界中广泛存在的层次结构和网状结构的关系，如家族谱、城市交通 等。二叉树不是树的特例二叉树与无序树不同： 二叉树中，每个结点最多只能有两棵子树，并且有左右之分。二叉 树并非是树的特殊情形，它们是两种不同的数据结构。二叉树与度数为2的有序树不同： 在有序树中，虽然一个结点的孩子之间是有左右次序的，但是若该 结点只有一个孩子，

暴力匹配算法假设现在我们面临这样一个问题：有一个文本串 S，和一个模式串 P，现在要查找 P 在S 中的位置，怎么查找呢？如果用暴力匹配的思路，并假设现在文本串 S 匹配到 i 位置，模式串 P 匹配到 j 位置， 则有： – 如果当前字符匹配成功（即 S[i] == P[j]），则 i++，j++，继续匹配下一个字符； – 如果失配（即 S[i]! = P[j]），令 i = i - (j

二路插入排序是对折半插入排序的改进，其目的是减少排序过程中移动记录的次数，但为此需要n个记录的辅助空间。具体做法是：另设一个和r[]同类型的数组d，首先将r[0]赋值给d[0]，并将d[0]看成是在排好序的序列中处于中间位置的记录，然后从r[]中第2个记录起依次插入到d[0]之前或之后的有序序列中。先将待插记录的关键字和d[0]的关键字进行比较，若r[i] < d[0]，则将r[i]插入到d[0]之

再次复习了一些排序算法，这次使用了Java泛型实现方式。