CSDN_564174144-CSDN博客

原创编程之美——递归思想的归纳

递归的基本思想递归并不是简单的自己调用自己，也不是简单的交互调用。递归在于把问题分解成规模更小、具有与原来问题相同解法的问题，如二分查找以及求集合的子集问题。这些都是不断的把问题规模变小，新问题与原问题有着相同的解法。但是并不是所有所有可以分解的子问题都能使用递归来求解。一般来说使用递归求解问题需要满足以下的条件：可以把要解决的问题转化为一个子问题，而这个子问题的解决方法仍与原来的解决方法相同，

2017-09-09 09:58:18 512

转载数据结构之数组、单链表和双链表的介绍

线性表是一种线性结构，它是具有相同类型的n(n≥0)个数据元素组成的有限序列。本章先介绍线性表的几个基本组成部分：数组、单向链表、双向链表；数组数组有上界和下界，数组的元素在上下界内是连续的。数组的特点是：数据是连续的；随机访问速度快。数组中的难点是多维数组和动态数组。多维数组本质上也是通过一维数组实现的。至于动态数组，是指数组的容量能动态增长的数组；对于C语言而言，若要提供动态数组，需要手

2017-09-08 17:05:43 707

set集合容器：背景：C++ STL 之所以得到广泛的赞誉，也被很多人使用，不只是提供了像vector, string, list等方便的容器，**更重要的是STL封装了许多复杂的数据结构算法和大量常用数据结构操作。**vector封装数组，list封装了链表，map和set封装了二叉树等，在封装这些数据结构的时候，STL按照程序员的使用习惯，以成员函数方式提供的常用操作，如：插入、排序、删除、查找

2017-09-07 15:12:10 681

原创 C++知识点之string，结合华为编程题：简单错误记录分析（附加容器pair知识点）

C++中string类的详解string是C++标准库的一个重要的部分，主要用于字符串处理。可以使用输入输出流方式直接进行操作，也可以通过文件等手段进行操作。string类的声明头文件：#include< string > 命名域的声明：using namespace std；string类的函数原型string类的构造函数： string(const char *s); //用c字符串s

2017-08-17 20:50:57 833

原创 C++中STL的介绍和vector容器的介绍

1 STL（Standard Template Library）1. 1什么是STL？STL（Standard Template Library），即标准模板库,是一种高效的C++程序库，它被容纳于C++标准程序库（C++ Standard Library）中。1.2 STL的特点STL的一个重要特点是数据结构和算法的分离。例如，由于STL的sort()函数是完全通用的，你可以用它来操作几乎任何数据

2017-08-16 20:26:16 537

转载 static的用法详解--C语言和C++分别介绍

先上一道题目：下面程序的输出是（）？ #include < stdio.h> int fun3(int x) { static int a=2; a+=x; return(a); } void main() { int k=2,m=1,n; n=fun3(k); n+=fun3(m); printf(“%d\n”,n); } 本题分析：本题考查关

2017-08-15 20:28:26 755

原创数据结构和算法分析之排序篇--归并排序（Merge Sort）和常用排序算法时间复杂度比较（附赠记忆方法）

归并排序的基本思想归并排序法是将两个或以上的有序表合并成一个新的有序表，即把待排序序列分成若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。归并排序实例：合并方法：设r[i……n]由两个有序子表r[i….m]和r[m+1……n]组成，两个子表长度分别为m-i+1、n-m。 1. J=m+1 ;k=i ; I=i ; 置两个子表的起始下标及辅助数组的起始下标

2017-08-13 21:29:53 12011

转载数据结构和算法分析之排序算法--选择排序（堆排序）

选择排序–堆排序堆排序是一种树形选择的排序，是对直接选择排序的有效改进。（直接选择排序：第一次选择最小值，与第一位数交换，再从后面选择最小的，和第二位数交换……直至排序结束，共n-1次）基本思想：堆的定义如下：具有n个元素的序列（k1,k2,…,kn），当且仅当满足：时称之为堆。由堆的定义可以看出，堆顶元素（第一个元素）必须为最小项（或最大项）。若一一维数组存储一个堆，则堆对应一

2017-08-12 14:46:22 491

原创数据结构和算法分析之排序算法--交换排序篇（冒泡排序和快速排序）

1. 交换排序–冒泡排序基本思想：在要排序的一组数中，对当前未排序好的范围全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的数往上冒，俗称冒泡。总结：每当两相邻的数比较后发现他们的排序与排序要求相反时，就将他们互换。嵌套排序完成整个冒泡过程冒泡排序的示例：算法的实现： 1、每次排序把最大的数排在最后一个; 2、然后下次排序可以少计算一次，因此是j-i;

2017-08-07 11:28:59 706

原创数据结构和算法分析之排序算法--插入排序篇（直接插入排序和希尔排序）

排序算法的概述排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。本系列介绍的都是内部排序。其中：当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的

2017-08-04 23:22:33 720

原创数据结构与算法分析之哈希表（HashTable，又称散列表）--代码篇

本篇文章是继上一篇对于哈希表理论的介绍，进行一个代码上的书写工整，可以加深对哈希表的理解，本段代码主要分为以下几个部分： 1、哈希表的结构 2、哈希表的建立 3、哈希函数 4、哈希表插入元素 5、哈希表的查找元素代码如下：//头文件，后面申请空间需要用到的#include "stdafx.h"#include <stdlib.h>//宏定义，不能有分号#define HASHSIZE

2017-08-03 17:49:33 655

转载数据结构与算法分析之哈希表（HashTable，又称散列表）--理论篇

哈希表的定义哈希表就是一个集合A到另一个集合B的映射。 A->B；人->身份证；上面的映射关系，在哈希表中，上述对应过程就称为hashing。A中元素a对应B中元素b，a称之为键值（key）, b被称之为a的hash值（hash value）。哈希函数映射在数学上相当于一个函数f(x)：A->B；哈希表的核心就是哈希函数，这个函数规定了集合A中的元素如何对应到集合B中的元素。Hash

2017-08-03 15:33:30 953

原创剑指offer算法题之栈和队列--面试题7：用两个栈实现队列（补充知识点：类模板）

关于栈和队列的介绍，在上一篇文章里已经介绍过了，话不多说直接上题目了。题目如下：队列的声明如下：template <typename T> class CQueue{public: CQueue(void); ~CQueue(void);private: stack<T> stack1; stack<T> stack2;};在上述队列的声明可以看出，一个队列

2017-08-02 12:22:40 452

转载数据结构--堆和队列&&C语言的内存分配--堆和栈

1 数据结构–栈和队列1. 栈1.1 栈的定义栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下图所示： 1.2 栈的特点：后进先出的特点（Last in first out）; 1.3 栈的声明： stack< int > stk;1.4 栈的操作 s.empty() 如果栈为空返回true，否则返回fal

2017-08-01 11:56:24 1399

原创剑指Offer算法题之已知两种遍历方式重建二叉树--面试题6：重建二叉树

直接上题目本题所构建的二叉树如下图 -本文已知二叉树的前序遍历和中序遍历，在二叉树的前序遍历序列中，第一个数字总是树的根结点的值。但在中序遍历序列中，根结点的值再序列的中间，所以左子树的结点的值位于根结点的值得左边，而右子树的结点的值位于根结点的值得右边。因此可知，我们需要扫描一遍中序遍历，找到根结点。如下图可知，前序遍历序列的第一个数字1就是根结点，进过扫描中序遍历后找到根结点1所在位置。因此

2017-07-31 22:10:32 586

原创剑指offer算法题之单链表的删除结点操作--面试题13：在O（1）时间删除链表结点

题目如下： - 常见删除链表结点的顺序遍历法单链表最常见的删除结点操作：就是从链表的头结点开始，顺序遍历查找要删除的结点，找到该结点后删除即可。如下图（a）所示链表中，我们想删除链表结点i，可以从链表的头结点a开始顺序遍历，发现h结点的m_pNext指针指向的结点就是i结点，于是我们可以安全的删除结点i，把指针指向下一个结点j。指针调整之后我们就可以安全的删除结点i,并保证链表没有断开，

2017-07-30 22:17:10 445

原创剑指offer算法题之单链表的反转--面试题16：反转链表

题目如下：本题分析第一步: 反转结点指针一般解决与链表相关问题总是涉及到大量的指针操作，这时候代码中很容易出错。为了正确地反转一个链表，需要调整链表中指针的方向。因此我们借助图形来直观的分析本题指针的变化过程。如下图所示，（a )图中的h, i , j 是三个相邻的结点。假设进过之前的反转操作，h结点之前的指针调整完毕，可见，前面的所有结点的m_pNext指针都指向前面一个结点。接下来要做分

2017-07-28 23:35:46 701

原创 C++之迭代器（Iterator）篇

迭代器（Iterator）的介绍背景：指针可以用来遍历存储空间连续的数据结构，但是对于存储空间费连续的，就需要寻找一个行为类似指针的类，来对非数组的数据结构进行遍历。定义：迭代器提供对一个容器中的对象的访问方法，并且定义了容器中对象的范围。迭代器（Iterator）是指针（pointer）的泛化，它允许程序员用相同的方式处理不同的数据结构（容器）。（1）迭代器类似于C语言里面的指针类

2017-07-28 10:52:21 39056 10

原创剑指offer算法题之循环链表--约瑟夫问题，面试题45：圆圈中最后剩下的数字（补充：define和typedef）

题目如下：分析本题思路：本题的原型就是约瑟夫环问题，有两种解决方法：第一种方法是用环形链表模拟圆圈的经典解法，第二种方法是分析每次被删除的数字的规律并直接计算出1圆圈中最后剩下的数字。本篇文章主要分析第一种解题方法。经典的解法：用环形链表模拟圆圈既然题目中有一个数字圆圈，很自然的想法就是用环形链表来模拟这个圆圈。我们可以创建一个共有n个结点的环形链表，然后每次在这个链表中删除第m个结点。

2017-07-27 23:56:31 579

原创数据结构与算法分析之单链表的建立，插入和删除操作。

序言单链表：当一个序列中只含有指向它的后继结点的链接时，就称该链表为单链表。具体形式如下图：其中：data称为数据域，next称为指针域。在链表的最开头是头指针head，头指针顾名思义，不含有数据域；尾接点指向NULL的地方。注意，若head==NULL，为空表。具体代码如下： 1、定义一个结构体，里面包含单链表的每个接点的数据域和指针域。 2、要注意指针域的定义方式。因为是指

2017-07-25 22:03:12 1887

原创数据结构与算法分析之顺序存储结构的建立，插入和删除操作

绪论线性表是最简单的一种数据结构，它可以用来描述：n个数据元素的优先序列。记为：L=（a1,a2,…..,an）按照存储结构它又可以分为顺序存储结构和链式存储结构。而其中线性表的顺序存储结构是最简单最常用的数据结构。定义：用一段连续地址依次存储表中的数据元素。性质：顺序存储结构封装需要三个属性： 1.存储空间的起始位置，对于数组data来说，它的位置就是线性表存储空间的存储位置

2017-07-22 22:38:02 2306

转载数据结构与算法分析之平衡二叉树的建立

平衡二叉树的概念：平衡二叉树是二叉查找树的一个进化体，也是第一个引入平衡概念的二叉树。平衡二叉树又称AVL树。平衡二叉树的性质：对于每个结点来说，它的左右子树的高度之差不能超过1，如果插入或者删除一个结点是的高度之差大于1，就要进行结点之间的旋转，将二叉树重新维持在一个平衡状态。下面会一步一步的讲解如何写平衡二叉树，重点是平衡二叉树的核心部分，也就是旋转算法。-第一步：创建节点信息相

2017-07-18 22:41:57 844

原创数据结构与算法分析--二叉排序树（二叉查找树，二叉搜索树）的查找、插入和删除操作

什么是二叉排序树它表示一棵二叉树，并且包含以下性质： 1）可能是一棵空树 2）若不为空，那么其左子树结点的值都是小于根结点的值，右子树结点的值都是大于根结点的值 3）左右子树都是二叉树。对于二叉排序树功能的介绍本文主要介绍的是二叉排序树的几种基本操作，包括查找、插入和删除操作。用到的二叉排序树如下图所示：二叉排序树的建立二叉树结点的创建：typedef struct BiTNo

2017-07-18 11:26:24 4216 1

原创数据结构与算法分析之二叉树的三种遍历方式。--前序遍历，中序遍历和后序遍历

在介绍二叉树的遍历算法之前，我们需要介绍一下二叉树以及遍历方式这些概念。二叉树：是树的一种特殊结构，在二叉树中每个结点最多只能有两个子节点。二叉树中最重要的操作就是遍历，通常二叉树的遍历方式有一下几种：前序遍历：先访问根结点，再访问左结点，最后访问右结点。如图示前序遍历顺序是：10、6、4、8、14、12、16。中序遍历：先访问左结点，再访问根结点，最后访问右结点。如图所示中序遍历顺序是：4 、

2017-07-13 10:03:18 957

原创树的存储结构之双亲孩子表示法

已知给出的树结构如下图：用代码实现方式如下：/*孩子表示法：浪费资源双亲孩子表示法：数组和链表的结合*//*1.双亲孩子表示法定义一个数结构,运用结构体指针的编程方式2.找到每个结构之间的联系，此套系统是倒序构建的*/#define MAX_TREE_SIZE 100//孩子结点typedef struct CTnode{ int child;

2017-07-12 21:41:34 3901

原创剑指Offer算法题之设计模式的单例模式--面试题2：实现Singleton模式

提到单例模式，不得不稍微了解一下设计模式，所以首先介绍几种常见的设计模式。设计模式：它表示了一个特定环境、一类问题和一个解决方案之间的关系。每一个模式都描述了一个不断重复发生的问题，以及该问题解决方案的核心设计。常见设计模式介绍1. 单例模式的介绍（singleton）有些时候，允许自有创建某类的实例是会造成系统性能的下降。如果一个类始终只创建一个实例，则这个类就被称为单例类，这种模式就被称为单例模

2017-07-12 10:09:35 386

原创剑指Offer算法题之字符串替换字符--面试题4：替换空格

替换空格题目：请实现一个函数，把字符串中的每个空格替换成“%20”。例如输入“We are happy.”,则输出“We%20are%20happy.”。题目背景：在网络编程中，如果URL参数中含有特殊字符，如空格，可能导致服务器端无法获得正常的参数值。因此我们需要将这些特殊符号转换成服务器可以识别的字符。一般转换规则是在‘%’后面跟上ASCII码的十六进制的表示。例如空格就被替换成“%20”。题目

2017-07-11 15:08:27 736

CSDN_564174144的博客