数据结构基础
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
状态：完结
dexcoder
1年前
共 21 篇
DFS ? ? 从图中某个顶点V0?出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到(使用堆栈). ? //使用邻接矩阵存储的无向图的深度优先遍历
template <typename Type>
void Graph<Type>::D
1年前发布
图的结构定义 ? ? 图是由一个顶点集?V?和一个弧集?E构成的数据结构。 ? ? ?Graph?=?(V?,?E?) ? ?其中，E?＝?{<v,w>|?v,w∈V?且?P(v,w)}?<v,w>表示从?v?到?w?的一条弧，并称?v?为弧尾，w?为弧头。谓词?P(v,w)?定义了弧?<v,w>的意义或信息。 ? ?由顶点集和边
1年前发布
完全二叉树 首先让我们回顾一下完全二叉树的两个性质: ? 性质1:具有n个结点的完全二叉树的深度为[logn](向下取整)+1。 ? 性质2:若对含?n?个结点的完全二叉树从上到下且从左至右进行?1?至?n?的编号，则对完全二叉树中任意一个编号为?i?的结点： ? ? (1)?若?i=1，则该结点是二叉
1年前发布
哈希表 ? ? 根据设定的哈希函数?H(key)和所选中的处理冲突的方法，将一组关键字映射到一个有限的、地址连续的地址集?(区间)?上，并以关键字在地址集中的“映像”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。 构造哈希函数的方法 1.?直接定址法(数组
1年前发布
二叉排序树的特征 二叉排序树或者是一棵空树,或者是具有如下特性的二叉树： ? ? 1.每一元素都有一个键值,?而且不允许重复; ? ? 2.若它的左子树不空，则左子树上所有结点的值均小于根结点的值； ? ? 3.若它的右子树不空，则右子树上所有结点的值均大于根结点的值； ? ? 4.它的
1年前发布
树的基本术语 1.结点:{数据元素+若干指向子树的分支} 2.结点的度:分支的个数（子树的个数） 3.树的度:树中所有结点的度的最大值 4.叶子结点:度为零的结点 5.分支结点:度大于零的结点(包含根和中间结点) 6.(从根到结点的)路径：由从根到该结点所经分支和结点构成; 7.结点的层次
1年前发布
? ? 基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。 实现多关键字排序通常有两种作法: ? ?最低位优先法(LSD) ? ? 先对K[0]{基数的最低位}进行排序，并按?K(0)?的不同值将记录序列分成若干子序列之后，分别对?K[1]?进行排序,...,?K[d-1]依次
1年前发布
? ? 链式队列是基于单链表的一种存储表示,?其形状如下图所示: ? ? ? (队列的队头指针指向单链表的第一个结点,?队尾指针指向单链表的最后一个结点,?注意没有无用的空[头/尾]节点) ? ? 用单链表表示的链式队列特别适合于数据元素变动比较大的情况,?而且不存在队列满而产生溢出的
1年前发布
? ? 采用链式存储的栈成为链式栈(或简称链栈),?链栈的优点是便于多个栈共享存储空间和提高其效率,?且不存在栈满上溢的情况(因为链栈是靠指针链接到一起,只要内存够大,?则链栈理论上可以存储的元素是没有上限的); ? ? 与顺序栈相比,?由于顺序栈是采用的数组实现,?因此一旦数组
1年前发布
双向链表的操作特点： ? ? (1)?“查询”?和单链表相同; ? ? (2)“插入”?和“删除”时需要同时修改两个方向上的指针。 ? ?但是对于双向循环链表则在表尾插入非常的迅速,?只需O(1)的时间,因为有指向前面的指针,?因此双向循环链表会很容易的找到位于表尾的元素,因此双向循环链表
1年前发布
循环链表:最后一个结点的指针域的指针又指回第一个结点的链表; ? ? 循环单链表与单链表的区别在于:表中最有一个节点的指针不再是NULL,?而改为指向头结点(因此要对我们原来的MyList稍作修改),?从而整个链表形成一个环. ? ? 因此,?循环单链表的判空条件不再是头结点的指针是否为
1年前发布
为了向?STL 致敬(O(∩_∩)O~), 我们模仿STL中的list的迭代器,?我们也自己实现一个MyList的迭代器,?以供遍历整个链表的所有元素: 首先:Node节点需要做如下修改(注意后缀有+的代码) //链表节点
template <typename Type>
class Node
{
friend class MyList<Typ
1年前发布
链表的链接: ? ? 将第二条链表的所有内容链接到第一条链表之后,?其完整实现代码与解析如下: //链表的链接
template <typename Type>
void MyList<Type>::concatenate(const MyList<Type> &list)
{
if (isEmpty())//如果自己的链表为空
{
1年前发布
链表简介 数组的缺点: ? ? ?1.元素插入:除了在数组的末尾插入元素之外,在数组的其他任何位置插入元素都需要进行数组元素的频繁移动(插入位置之后的元素都需往后移动),?时间复杂度约为O(N); ? ? ?2.数组的删除:除了在数组的末尾删除元素之外,在数组的其他任何位置删除元素都需
1年前发布
队列 ? ? 队列简称队,?也是一种操作受限的线性表,?只允许在表的一端进行插入,?而在表的另一端进行删除.其特点为”先进先出(FIFO)”,故又称为先进先出的线性表,简单队列如图所示: 循环队列 ? ? 顺序队列有一个先天不足,?那就是空间利用率不高,?会产生”假溢出”现象,即:其实队
1年前发布
栈是一种只允许在一端进行插入或删除操作的线性表.其特点为:先进后出(FILO)/后进先出(LIFO); 栈?VS.?队列 ? ? 栈和队列都是动态集合,?但在栈中,?可以去掉的是最近插入的那一个,:栈实现了一种后进先出(last-in,?first-out)的策略;类似的,?在队列中,?可以去掉的元素总是在集合中
1年前发布
归并排序的基本思想： ? ? 将两个或两个以上的有序子序列”归并”为一个有序序列:假定待排序表含有n个记录,?则可以看成是n个有序的子表,?每个子表长度为1,?然后两两归并,?得到[n/2]个长度为2或1的有序表,;?再量量归并,?....,?如此重复,?直到合并成为一个长度为n的有序表为止,?
1年前发布
? ? 快速排序是最流行的,也是速度最快的排序算法(C++?STL?的sort函数就是实现的快速排序);?快速排序（Quicksort）是对冒泡排序的一种改进。由C.?A.?R.?Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分
1年前发布
Permutation(排列组合) 排列问题: 设R?=?{r1,?r2,?...?,?rn}是要进行排列的n个元素,?Ri?=?R-{ri};?集合X中元素的全排列记为Permutation(X),?(ri)Permutation(X)表示在全排列Permutation(X)的每一个排列前加上前缀ri得到的排列. R的全排列可归纳定义如下: 当n=1时，Permutation
1年前发布
顺序查找 适用范围: 没有进行排序的数据序列 缺点: 速度非常慢,?效率为O(N) //实现
template <typename Type>
Type *sequenceSearch(Type *begin, Type *end, const Type &searchValue)
throw(std::range_error)
{
if ((begin == end) || (begin == NULL)
1年前发布
Swap的简单实现 //C语言方式(by-pointer):
template <typename Type>
bool swapByPointer(Type *pointer1, Type *pointer2)
{
//确保两个指针不会指向同一个对象
if (pointer1 == NULL || pointer2 == NULL)
{
return false;
}
if
1年前发布
最新动态
MO
8月前
MO
8月前
SD
1年前
TJ
1年前
YE
1年前
GO
1年前
JO
HA
17
1年前