AVL树简介及实现

2017年02月05日 53 阅读

AVL树简介及实现2013-05-24二叉搜索树的深度与搜索效率我们在树, 二叉树, 二叉搜索树中提到，一个有n个节点的二叉树，它的最小深度为log（n），最大深度为n。比如下面两个二叉树:深度为n的二叉树...

数据结构的C++实现之字符串的基本操作

2017年02月05日 54 阅读

数据结构的C++实现之字符串的基本操作2013-08-13 csdn jnu_simba字符串（string）是由0个或多个字符组成的有限序列。一般使用顺序存储结构，末尾以""表示结束，但不计入字符串的长度。示例程序：（改编自《大话数据结构》）#include<iostream>using namespace std;#define MAXSIZE 20typedef char String[MAXSIZE + 1]; //以""结尾/* 生成一个串...

数据结构的C++实现之程序加图示分析单链表的插入和删除操作

2017年02月05日 56 阅读

数据结构的C++实现之程序加图示分析单链表的插入和删除操作2013-08-13 csdn Simba888888下图展示了单链表的基本结构：head指针是链表的头指针，指向第一个节点，每个节点的next指针域指向下一个节点，最后一个节点的next指针域为NULL，在图中用0表示。下面先来看程序（栈的链式存储实现，另外一个实现点这里）和对应的输出（注意输出前进行了链表反转（见《单链表反转》，否则程序后面的while循环输出的顺序是250，200，100），接...

数据结构的C++实现之队列的链式存储结构

2017年02月05日 62 阅读

数据结构的C++实现之队列的链式存储结构2013-08-13 csdn Simba888888队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。为了操作上的方便，我们将队头指针指向链队列的头节点，而队尾指针指向终端节点。空队列时，front和rear都指向头节点。示例程序：（改变自《大话数据结构》）#include<iostream>using namespace std;typedef int ElemTy...

数据结构的C++实现之队列的顺序存储结构（循环队列）

2017年02月05日 60 阅读

数据结构的C++实现之队列的顺序存储结构（循环队列）2013-08-13 csdn Simba888888队列（Queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。是一种先进先出的线性表（FIFO）。允许插入的一端称为队尾，允许删除的一端称为队头。我们在《栈的顺序存储结构》中发现，栈操作的top指针在Push时增大而在Pop时减小，栈空间是可以重复利用的，而队列的front、rear指针都在一直增大，虽然前面的元素已经出队了，但它所占的...

数据结构的C++实现之二叉树的遍历和存储结构

2017年02月05日 61 阅读

数据结构的C++实现之二叉树的遍历和存储结构2013-08-14 csdn Simba888888在《二叉树的定义和性质》中我们已经认识了二叉树这种数据结构。我们知道链表的每个节点可以有一个后继，而二叉树（Binary Tree）的每个节点可以有两个后继。比如这样定义二叉树的节点：typedef struct node *link;struct node {unsigned char item;link l, r;};这样的节点可以组织成下图所示的形态。二...

数据结构的C++实现之二叉树的定义和性质以及特殊二叉树

2017年02月05日 58 阅读

数据结构的C++实现之二叉树的定义和性质以及特殊二叉树2013-08-14 csdn Simba888888一、二叉树（Binary Tree）是n（n>=0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。如图1就是一棵二叉树图1二叉树的特点：（1）每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。（2）左子树和右子树是由顺序的，次序不能颠倒。（3）即使树中某结点只...

数据结构的C++实现之静态链表

2017年02月05日 73 阅读

数据结构的C++实现之静态链表2013-08-14 Simba888888 首先我们让数组的元素都是由两个数据域组成，data和cur。也就是说，数组的每一个下标都对应一个data和一个cur。数据域data用来存放数据元素，也就是通常我们要处理的数据；而游标cur相当于单链表中的next指针，存放该元素的后继在数组中的下标。我们把这种用数组描述的链表叫做静态链表。数组的第一个元素，即下标为0的元素的cur就存放备用链表的第一个结点的下标；而数组的最后一个...

数据结构的C++实现之两栈共享存储空间

2017年02月05日 56 阅读

数据结构的C++实现之两栈共享存储空间2013-08-14 csdn Simba888888数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈为栈的末端，即下标为数组长度n-1处。这样，如果两个栈增加元素，就是两端点向中间延伸。当top1 + 1 == top2 的时候为栈满。示例代码：（改编自《大话数据结构》）#include <iostream>using namespace std;#defineMAXSIZE...

数据结构的C++实现之树的定义和基本概念

2017年02月05日 66 阅读

数据结构的C++实现之树的定义和基本概念2013-08-14 csdn Simba888888一、树（Tree）是n（n>=0）个结点的有限集。n=0时称为空树。在任意一棵非空树中：（1）有且仅有一个特定的称为根（root）的结点。（2）当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1,T2,....,Tm, 其中每一个集合本身又是一棵树，并且称为根的子树（SubTree），如图1所示：图1树的定义之中还用到了树的概念，即递归定义。如图2中的子...

数据结构的C++实现之双向链表实现队列与循环链表

2017年02月05日 61 阅读

数据结构的C++实现之双向链表实现队列与循环链表2013-08-15 csdn Simba888888一、双向链表（double linked list）如图26.5，是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。双向链表的基本操作与单链表基本一样，除了插入和删除的时候需要更改两个指针变量，需要注意的是修改的顺序很重要，插入如图3-14-5，删除如图3-14-6。...

数据结构的C++实现之图的存储结构之邻接表

2017年02月05日 69 阅读

数据结构的C++实现之图的存储结构之邻接表2013-08-15 csdn Simba888888对于图来说，邻接矩阵是不错的一种图存储结构，但是我们也发现，对于边数相对顶点较少的图，这种结构是存在对存储空间的极大浪费的。因此我们考虑另外一种存储结构方式：邻接表（Adjacency List），即数组与链表相结合的存储方法。邻接表的处理方法是这样的。1、图中顶点用一个一维数组存储，另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找...

数据结构的C++实现之图的存储结构之邻接矩阵

2017年02月05日 56 阅读

数据结构的C++实现之图的存储结构之邻接矩阵2013-08-15 csdn Simba888888图的邻接矩阵（Adjacency Matrix）存储方式是用两个数组来表示图。一个一维的数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。设图G有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：我们来看一个实例，图7-4-2的左图就是一个无向图。我们再来看一个有向图样例，如图7-4-3所示的左图。在图的术语中，我们提到了网的概念，也就是...

数据结构的C++实现之图的定义和术语总结

2017年02月05日 70 阅读

数据结构的C++实现之图的定义和术语总结2013-08-15 Simba888888 一、图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V，E），其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。在图中的数据元素，我们称之为顶点（Vertex），顶点集合有穷非空。在图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。二、图按照有无方向分为无向图和有向图。无向图由顶点和边组成，有向图由...

数据结构的C++实现之线索二叉树

2017年02月05日 57 阅读

数据结构的C++实现之线索二叉树2013-08-16 csdn Simba888888我们知道满二叉树只是一种特殊的二叉树，大部分二叉树的结点都是不完全存在左右孩子的，即很多指针域没有被充分地利用。另一方面我们在对一棵二叉树做某种次序遍历的时候，得到一串字符序列，遍历过后，我们可以知道结点之间的前驱后继关系，也就是说，我们可以很清楚地知道任意一个结点，它的前驱和后继是哪一个。可是这是建立在已经遍历过的基础之上的。在二叉链表上，我们只能知道每个结点指向其左右...

数据结构的C++实现之线性表之链式存储结构以及单链表反转

2017年02月05日 64 阅读

数据结构的C++实现之线性表之链式存储结构以及单链表反转2013-08-16 csdn Simba888888为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系，对数据ai，除了存储其自身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。这两部分信息组成数据元素ai的存储映像，称为结点（Node）。N个结点链结成一个链表，即为线性表（a1,a2,...,an）的链式存储结构，因为此链表的每个节点中只包含一个指针域，所以叫做单...

数据结构的C++实现之线性表之顺序存储结构

2017年02月05日 54 阅读

数据结构的C++实现之线性表之顺序存储结构2013-08-17 csdn Simba888888线性表的数据对象集合为 {a1,a2,....an}，每个元素的类型均为Datatype。其中，除第一个元素a1外，每一个元素有且 只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的 关系。线性表的顺序存储结构的优缺点：优点：无须为表示表中元素之间的逻辑关系而增加额外的存储空间；可以快速地存取表中任一位...

数据结构的C++实现之栈的链式存储结构

2017年02月05日 63 阅读

数据结构的C++实现之栈的链式存储结构2013-08-17 Simba888888 当单链表限定只能在头部进行插入和删除操作的时候，即为链栈，一般我们会将单链表的头指针和栈的栈顶指针top合二 为一，通常对链栈来说，是不需要头节点的，因为我们维护了栈顶指针。对于链栈来说，基本不存在栈满的情况，除非内存 已经没有可以使用的空间，对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是top = = NULL的时候。示例代码：（改编自《大话数据结构》）#i...

数据结构的C++实现之栈的顺序存储结构

2017年02月05日 56 阅读

数据结构的C++实现之栈的顺序存储结构2013-08-17栈（stack）是限定在表尾进行插入和删除操作的线性表。我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构。示例程序：（改编自《大话数据结构》）#include <iostream>using namespace std;#defineMAXSIZE 20typedef int E...

从赌钱游戏看PageRank算法

2017年02月05日 62 阅读

从赌钱游戏看PageRank算法2013-08-17 infoq 千峰谈到并行计算应用，会有人想到PageRank算法，我们有成千上万的网页分析链接关系确定排名先后，借助并行计算完成 是一个很好的场景。长期以来，Google的创始发明PageRank算法吸引了很多人学习研究，据说当年Google创始者兴奋的找到 Yahoo！公司，说他们找到一种更好的搜索引擎算法，但是被Yahoo！公司技术人员泼了冷水，说他们关心的不是更好的技术， 而是搜索的盈利。后来Go...