- 博客(18)
- 收藏
- 关注
RSS订阅原创 顺序表的类型定义与基本操作
顺序表的类型定义与基本操作顺序表主要指数组，顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中逻辑相邻的元素也物理相邻，采用顺序存储结构的线性表通常称为顺序表。1. 顺序表的类型定义typedef struct{ ElemType *elem; // 存储空间的基地址 int length; // 当前长度}SqList; // 顺序表的结构类型为 SqList2. 顺序表的基本操作顺序表的操作不多，但可以通
2021-01-16 13:26:17
8197
原创 详解二叉排序树及其基本操作
详解二叉排序树及其基本操作二叉排序树又称二叉查找树，它是一种对排序和查找都很有用的特殊二叉树。1. 二叉排序树的定义二叉排序树或者是一颗空树，或者是具有下列性质的二叉树：(1) 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；(2) 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；(3) 它的左、右子树也分别为二叉排序树。由定义可得到二叉排序树的一个重要性质：中序遍历一颗二叉排序树时可以得到一个结点值递增的有序序列。在下面讨论二叉排序树的操作中，使用二叉链表作为存
2020-11-22 15:39:05
2866
原创 数据结构：图
数据结构：图1. 图的定义和基本术语1.1 图的定义图 G 由两个集合 V 和 E 组成，记作 G = (V，E)，其中 V 是顶点的有穷非空集合，E 是 V 中边 ( 顶点偶对 ) 的有穷集合。E(G) 可以为空，则图 G 只有顶点而没有边。有向图中，顶点对 <x，y> 是有序的。x 为弧尾，y 为弧头，称为有向边或弧。<x，y> 与 <y，x> 是不同的两条边，无向边的表示方法：(x，y)。1.2 图的基本术语用 n 表示图中顶点数目，e 表示边的数目，下
2020-11-15 21:30:19
623
原创 二叉树的类型定义与基本操作
二叉树的类型定义与基本操作树结构是一类重要的非线性数据结构，在客观世界中广泛存在。树在计算机领域中也得到了广泛的应用，尤以二叉树最为常用。本文重点讨论二叉树的基本操作。1. 二叉树的类型定义二叉树通常由三个域组成：数据域、左孩子指针域和右孩子指针域。其类型定义为：typedef struct BiNode{ char data; // 数据域 struct BiNode* lchild, * rchild; // 左右孩子指针域}Bi
2020-10-29 20:25:45
4521
原创 详解 KMP 算法与 next 数组的计算
详解 KMP 算法与 next 数组的计算1. KMP 算法KMP 算法为 BF 算法的优化，当模式串与主串之间存在许多 “部分匹配” 的情况下比 BF 算法快很多。其核心是利用匹配失败后的信息，具体通过一个 next 数组实现，数组本身包含了模式串的局部匹配信息。下面给出 KMP 与 BF 的代码实现：...
2020-10-28 12:24:36
649
原创 数据结构：树和二叉树
数据结构：树和二叉树引言：树结构是一类重要的非线性数据结构。树是以分支关系定义的层次结构，在计算机领域广泛应用，尤以二叉树最为常用。在操作系统中，用树来表示文件目录的组织结构，在编译系统中，用树来表示源程序的语法结构，在数据库系统中，树结构也是信息的重要组织形式。本章重点讨论二叉树的存储结构及其各种操作，并研究树和森林与二叉树的转换关系，最后介绍树的应用。1. 树和二叉树的定义1.1 树的定义树是 n 个结点的有限集，它或为空树；或为非空树，对于非空树 T：(1) 有且仅有一个称之为根的结点；
2020-10-25 11:39:20
686
原创 数据结构：串和广义表
数据结构：串、数组和广义表1. 串的定义串（ string ）（或字符串）是由零个或多个字符组成的有限序列，一般记为sss = " a1a2...ana_1 a_2 ... a_na1a2...an " ( n≥0n \geq 0n≥0 )其中，
2020-10-08 17:14:48
763
原创 数据结构：栈和队列
数据结构：栈和队列1. 栈和队列的定义和特点栈的定义和特点：栈是限定仅在表尾进行插入或删除操作的线性表。这里的表尾称为栈顶，相应的，表头称为栈底。不含元素的空表称为空栈。栈的特点是后进先出。队列的定义和特点：队列限定在表的一端进行插入，而在另一端删除元素。允许插入的一端称为队尾，允许删除的一端称为队头。队列的特点是先进先出。2. 栈的表示和操作的实现2.1 栈的类型定义...
2020-09-21 09:16:00
340
原创 数据结构：线性表
数据结构：线性表1. 线性表的定义和特点线性表的定义：由 n ( n≥0n \geq 0n≥0 )个数据特性相通的元素构成的有限序列。线性表的特点：(1) 存在唯一的一个被称作 “ 第一个 ” 的数据元素；(2) 存在唯一的一个被称作 “ 最后一个 ” 的数据元素；(3) 除第一个之外，结构中的每个数据元素均只有一个前驱；(4) 除最后一个之外，结构中的每个数据元素均只有一个后继；2. 线性表的类型定义ADT List {数据对象：D = { aia_iai | ai∈ElemSet，
2020-09-09 20:34:11
608
1
原创 数据结构：绪论
数据结构：绪论1. 基本概念与术语1.1 数据、数据元素、数据项和数据对象数据：是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称。例如：学生。数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。例如：学生信息。数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如：学生信息中的学号。数据对象： 是性质相同的数据元素的集合。例如：学生信息表。1.2 数据结构逻辑结构：也称为狭义的数据结构，含有两个要素：数据元素、关系。有四种类型：集合结构、
2020-09-03 19:39:56
136
原创 堆排序法的使用
堆排序法的使用相关背景：堆排序法被誉为十大经典排序算法中最难掌握的一种算法，这是因为这种算法基于堆这种数据结构。在学习这种算法之前，我们需要先复习一下堆这个数据结构。堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结...
2020-04-12 13:23:58
295
原创 希尔排序法的使用
希尔排序法的使用希尔排序法的背景：希尔排序按其设计者希尔（Donald Shell）的名字命名，该算法由希尔1959年公布。一些老版本教科书和参考手册把该算法命名为Shell-Metzner，即包含Marlene Metzner Norton的名字，但是根据Metzner本人的说法，“我没有为这种算法做任何事，我的名字不应该出现在算法的名字中。”其设计者还真是风趣十足！实际上，希尔的话确...
2020-04-05 22:03:48
333
原创 快速排序法的使用 ( 超详细图解 )
快速排序法的使用快速排序法作为一种广受好评的排序方法，不仅仅因为它的排序效率很高，更因为它体现了分治的思想。因此许多广为人知的软件公司（BAT）的笔试面试都喜欢考，甚至在一些大大小小的考试如软考、考研中也能见到它的身影。因此熟练默写快速排序法的代码并掌握其核心思想对我们来说尤为重要。快速排序法的背景：快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排...
2020-04-01 23:07:31
1066
原创 广度优先搜索的概念及应用
基于队列的搜索算法 —— 广度优先搜索（BFS）对于一些实际问题，如：求迷宫最小步数、最小曼哈顿距离时，我们会使用到BFS搜索算法来得到所求的答案。搜索算法的概念：搜索算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种方法。现阶段一般有枚举算法、深度优先搜索、广度优先搜索、A*算法、回溯算法、蒙特卡洛树搜索、散列函数等算法。搜索算法的运行...
2020-03-30 19:09:36
897
原创 线段树的概念及构造
线段树的概念及构造在介绍线段树之前，让我们先来看一道面试题：给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。update(i, val) 函数可以通过将下标为 i 的数值更新为 val，从而对数列进行修改。...
2020-03-26 18:47:32
293
原创 弗洛伊德的乌龟和兔子
使用弗洛伊德的乌龟和兔子来检测循环在介绍这个概念之前，首先让我们看一道经典的面试题：给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。示例1：输入: [1,3,4,2,2]输出: 2示例2：输入: [3,1,3,4,2]输出: 3说明：1.不能更改原数...
2020-03-24 11:07:57
324
原创 快慢指针在链表中的使用
快慢指针在链表中的使用链表毫无疑问是数据结构中最重要的知识点之一，因此许多面试官都很喜欢在链表上做文章。链表主要有这几种形式：单向链表，双向链表，循环链表。以链表为考点的面试题更是千变万化，令人眼花缭乱。下面让我们来看一道十分简单的题目：给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。示例1：输入：[1,2,3,4,5]输出：...
2020-03-23 22:38:31
274
原创 从两数之和到散列函数（Hash）
从两数之和到散列函数（Hush） 相信刚接触力扣（Leetcode）的小白们都遇到过这么一道经典的题目： 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。 示例：...
2020-03-23 12:21:30
274
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人