- 博客(109)
- 收藏
- 关注
RSS订阅原创 new详解
new int和new int()——内置类型对于int内置类型，new仅仅只是分配内存，除非后面显示加()，相当于调用它的构造函数。int *p=new int[10];//10个未初始化的intint *p2=new int[10]();//10个值初始化为0的intnew 自定义类型对于自定义类型，只要一调用new，那么编译器不仅仅给他分配内存，还调用它的默认构造函数初始...
2020-02-23 00:45:34
469
原创 散列表处理冲突的方法
一、开放地址法所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。1.1 线性探测法fi ( key ) = ( f ( key ) + di ) MOD m (di=1,2,3,4,…,m-1)会出现不是同义词却需要争夺一个地址的情况，我们称这种情况为堆积。1.2 二次探测法关键字集合『12，67，56，16，25...
2020-02-23 00:35:38
3383
原创 散列表查找及其函数
一、散列表查找存储位置 = f (关键字)不需要通过关键字比较就可以获得记录的存储位置。散列技术就是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)。散列是主要面向查找的存储结构。不适合散列的情况：一个关键字对应多条记录：比如以一个班的性别男女查找男同学女同学。不适合范围查找：查找一个班级的18～20岁的同学。冲突：...
2020-02-19 00:06:14
549
原创 数据结构——图的存储结构
图的存储结构1、邻接矩阵typedef char VertexType;typedef int EdgeType;#define MAXVEX 100#define INFINITY 65535typedef struct{ VertexType vexs[MAXVEX]; //顶点表 EdgeType arc[MAXVEX][MAXVEX];//邻接矩阵 int num...
2020-02-07 21:50:32
286
原创 线索二叉树
一、为什么需要线索二叉树？大部分二叉树，可以发现指针域并不是都充分利用，存在着很多空指针域，我们应该想办法利用起来。例如下图，很多“^”，浪费了内存空间。在中序遍历的时候我们得到一个序列 HDIBJEAFCG 这个字符序列。在进行中序遍历之后，我们就可以知道，结点I的前驱是D，后继是C。也就是说我们可以清楚的知道任意一个结点，它的前驱和后驱结点是哪一个。综合那些空指针，我们可以用来存放前...
2020-02-06 23:36:06
158
原创 数据结构——树
一、树的存储结构1、双亲表示法假设有一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点到链表的位置。也就是说，每个结点除了知道自己是谁以外，还知道它的双亲在哪里。#define MAX_TREE_SIZE 100typedef int TElemType;typedef struct PTNode{ TElemType data;//结点数据 int pare...
2020-02-06 17:40:32
167
原创 KMP模式匹配算法
一、KMP模式匹配算法符号说明i主串当前位置的下标（不回溯）j模式串T当前位置的下标目的：原本的匹配时 i 和 j 不停的回溯，KMP模式匹配让 i 不用回溯。j 值的变化与主串无关，取决于模式串T的结构中是否有重复（即当前字符之前的串的前后缀的相似度）。我们把模式串T各个位置的 j 值的变化定义为一个数组 Next，那么Next的长度就是模式串T的长度。...
2020-02-03 23:27:54
643
原创 （四）索引与数据完整性
一、索引1、索引的作用快速存取数据既可以改善数据库性能，又可以保证列值的唯一性实现表与表之间的参照完整性在使用ORDER BY，GROUP BY子句进行数据检索时，利用索引可以减少排序和分组的时间2、索引的分类索引按照存储方法分类，可以分为两类：(1)B树索引的存储结构类似图书的索引结构：有分支和叶两种类型的存储数据块，分支相当于图书的大目录，叶子相当于索引到的具体书页。Or...
2019-12-29 11:42:02
1424
1
原创 （二）数据库的创建和操作
以oracle为例一、创建表CREATE TABLE [<用户方案名>.] <表名>( <列名1> <数据类型> [DEFAULT <默认值>] [<列约束>] <列名2> <数据类型> [DEFAULT <默认值>] [<列约束>] [,…n] &l...
2019-12-23 16:19:50
539
原创 （一）数据库的基本概念
概念数据模型、逻辑数据模型、物理数据模型（区别）一、数据模型层次模型（一对一、一对多、只有一个父节点）网状模型（一对一、一对多、多对多，可以有多个父节点）关系模型（最重要，二维表格的形式组织数据，关系之间通过公共属性产生联系）逻辑数据模型之层次数据模型、网状数据模型和关系数据模型二、概念结构设计一对一的联系（1：1）一对多的联系（1：n）多对多的联系（m：n）...
2019-12-23 15:05:35
140
原创 输入输出及返回值、格式符
一、返回值1、scanf, fscanf, sscanf, scanf_s, fscanf_s, sscanf_s1-3) 成功赋值的接收参数的数量（可以为零，在首个接收用参数赋值前匹配失败的情况下），或者若输入在首个接收用参数赋值前发生失败，则为EOF。4-6) 同 (1-3) ，除了若有运行时制约违规，亦返回 EOF 。2、printf, fprintf, sprintf, snpri...
2019-11-27 11:06:57
740
原创 浮点数与绝对值
fabsMath.abs假设浮点变量的名字为x，应当将 if (x == 0.0) 转化为 if ((x>=-EPSINON) && (x<=EPSINON))或者 if ( fabs(x) <=EPSINON) // fabs(x)取x的绝对值其中EPSINON是允许的误差（即精度）。%schar str[21] cin>>str...
2019-11-26 17:09:30
1749
原创 常量指针和指针常量
（1）const在*前：表示const修饰的为所声明的类型——常量指针。（2）const在*后：表示const修饰的为指针——指针常量。（3）前后均有*：指向常量的指针常量。1、常量指针只能读取内存中的数据，不能修改内存数据，称为指向常量的指针//声明char const *p;const char *p;const 修饰的是char，所以说p所指向的内存地址所对应的值，是...
2019-11-19 17:20:49
122
原创 字符串（一）
strlen()函数计算空间中的字符数，以‘\0’为结束符（该字符不算入内）size_t strlen(const char *str);在C++中,char_traits::length实现相同的行为sizeof()计算分配空间的字节数例一#include<stdio.h>#include<stdlib.h>#include<string.h&...
2019-11-19 17:06:23
164
转载 Redis的数据类型详解
stringhashlistsetsorted set***string（字符串）它是二进制安全的。string可以包含任何数据，比如jpg图片或者序列化对象。最大能存储512MB。hash（哈希）是一个键值对的集合。是一个string类型的field和value的映射表，hash特别适合用于存储对象。list（列表）是简单的字符串列表，按照插入顺序排序。可以添加到一...
2019-11-13 21:29:29
143
原创 查询大数据
如何判断在40亿个无符号整型数据是否存在某个数（不需要排序）？方案1申请512M的内存（232/8=512M），一个bit位代表一个unsigned int值。读入40亿个数，设置相应的bit位，读入要查询的数，查看相应的bit位是否为1，为1表示存在，为0表示不存在。方案2因为232为40亿多，所以给定一个数可能在，可能不在，这里把40亿个数中的每一个用32位的二进制来表示。假设这40...
2019-11-13 21:03:45
959
原创 哈希表
一、哈希表结构特点：快常用结构：顺序表+链表主结构：顺序表每个顺序表的节点在单独引出一个链表二、添加数据计算哈希码计算在哈希表中的存储位置存入哈希表情况1：一次添加成功情况2：多次添加成功（出现了冲突，调用equals()和对应链表的元素进行比较，比较到最后，结果都是false的话，创建新节点，存储数据，并加入链表末尾）情况3：不添加（出现了冲突，调用eauqls()...
2019-11-13 20:19:49
160
原创 交换两个整型变量,不需要额外空间
一、加减法例子:int a,b;a=10;b=8;a=b-a;//-2b=b-a;//即是b-(b-a)=b-b+a=a=10 a=a+b;//a=(b-a)+a=b=8int a,b;a=10;b=8;a=a+b;//18b=a-b;//即是b=a+b-b=a=10a=a-b;//a=a+b-b=a+b-a=8二、位运算例子 int a=10,b=12; //a=...
2019-11-13 17:56:17
229
转载 2019年vivo秋招笔试（第三题）
leetcode 546.移除盒子给出一些不同颜色的盒子，盒子的颜色由数字表示，即不同的数字表示不同的颜色。你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1），这样一轮之后你将得到 k*k 个积分。当你将所有盒子都去掉之后，求你能获得的最大积分和。示例 1：输入:[1, 3, 2, 2, 2, 3, 4, 3, ...
2019-09-12 21:29:44
867
原创 动态链接和静态链接
静态链接的问题当静态库更新时那么整个程序都要重新链接；对于printf这种标准函数库，如果每个程序都要代码，这将会极大的浪费资源。动态链接在给定的文件系统中一个库只有一个文件，所有引用该库的可执行目标文件都共享这个文件，它不会被复制到引用它的可执行文件中；在内存中，一个共享库的 .text 节（已编译程序的机器代码）的一个副本可以被不同的正在运行的进程共享。区别静态链接方式...
2019-08-11 11:08:55
114
原创 内存管理
虚拟内存虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。为了更好的管理内存，操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块成为一页。这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。当程序引用到不再物理内存的页时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失败的指...
2019-08-11 10:53:38
161
原创 进程管理
一、进程与线程1、进程进程是资源分配的基本单位。进程是一段程序执行的过程。进程是一个实体。每个进程都有它自己的地址空间。进程是一个“执行中的程序”。程序：程序是指令和数据的有序集合。本身没有运行的含义，是一个静态的概念。2、线程线程是独立调度的基本单位一个进程中可以有很多个线程，它们共享进程资源。QQ和浏览器是两个进程，浏览器进程有很多线程，例如HTTP请求线程，事件响应线程...
2019-08-10 11:22:38
111
原创 死锁
死锁的必要条件互斥条件：资源是独占且排他使用，进程互斥使用资源，及任意时刻一个资源只能给一个进程使用。不可剥夺条件：进程所获得的资源在未使用完毕之前，不被其他进程强行剥夺，而只能由获得该资源的进程资源释放。请求和保持条件：进程每次申请它所需要的一部分资源，在申请新的资源的同时，继续占用已分配到的资源。循环等待条件：在发生死锁时必然存在一个进程等待队列{P1,P2,…,Pn}，其中P1等待...
2019-08-10 10:06:54
130
原创 五、应用层
DNS协议DNS协议结构16位标识：用于标记一对DNS查询和应答，以此区分一个DNS应答是哪个DNS查询的回应16位标志：用于协商局的通信方式和反馈通信状态接下来的四个字段指出最后四个字段的资源记录数据。对于查询报文而言，他一般包含一个查询问题，而应答资源记录数、授权资源记录数和额外资源记录数都为0。应答报文的应答资源记录数至少为1，而授权资源数和额外信息记录数可为0或非0。DN...
2019-08-09 09:19:37
288
原创 四、传输层
传输层传输层主要是为运行在不同主机上的应用进程提供直接的通信服务（端到端的通信）。通信单元为：报文段端口为应用层的各个应用进程的数据通过这个“门”向下传递给传输层。服务端使用的端口号：（1）熟知端口号：0~1023。分配给TCP/IP最重要的一些应用进程。（2）登记端口号：1024~49151。给没有熟知端口号的应用程序使用应用进程FTPTELNETSMTPDNS...
2019-08-06 20:51:54
635
原创 12.C++ STL之queue、stack
queuestack同queuequeue和stack关于其iterator和底层结构stack或者queue都不允许遍历，因此也不提供iterator，因此也不能在任意一个地方插入元素（1）stack和queue都可以选择list或者deque作为底层结构但是deque更快（2）queue不可选择vector作为底层结构，stack可以选择vector作为底层结构queue&...
2019-08-05 20:17:51
187
原创 11.C++ STL之deque
一、容器deque结构是双向开口的空间。而vector是单向的，已知vector的内存扩充是二倍成长。那么deque怎么扩充呢？双向扩充！deque的方式是使用分段，然后将各段串接在一起。map是个vector,其中每个元素是指针，指向每个分段，以将每个分段串接在一起。如果队列末尾满了，需要再分配一个buffer，并且在map后面中存入指向他的指针。deque的迭代器iterato...
2019-08-05 19:57:18
246
原创 三、网络层
IP协议IP协议格式版本：若为IPV4则为4，若为IPV6则为6。首部长度：单位为4个字节。最小为5，最大为15。所以首部最小长度为20个字节，最大长度为60个字节。服务类型：Qos用，目前不怎么用。总长度：字节为单位，最多可以传送65535字节的IP数据包。若超过该长度，需要分片。标识：唯一记录了一个IP包的ID，具有同一个ID的IP分片将会重新组装标志：后两位才有用，最低位表...
2019-08-05 16:34:39
1799
原创 2.树之搜索/完全二叉树和平衡二叉树
二叉搜索树又称二叉排序树、二叉查找树查找操作：递归或者循环，循环更好Position FindMin(BinTree BST)//遍历左子树知道某个结点左子树为空Position FindMax(BinTree BST)//遍历右子树知道某个结点右子树为空插入操作：BinTree Insert(ElementType X,BinTee BST){ if(!BST)//原...
2019-08-04 21:09:27
487
原创 二、数据链路层
数据链路层提供的服务链路层协议交换的数据单元称为帧，每个链路层帧通常封装一个网络层的数据报。当发送和接受帧时，链路层所采取的动作包括差错检测、重传、流量控制和随机接入。协议例子包括：以太网、WiFi、令牌环和PPP链路层协议的任务是将网络层的数据报通过路径中的单段链路节点到节点地传送，而网络层地任务是将运输层报文段从源主机端到端地传送到主机。数据报在路径上可能由不同地链路层协议所承载。例...
2019-08-04 20:46:21
388
原创 一、TCP/IP协议体系的认知
TCP/IP协议体系的定义TCP/IP协议体系是一系列网络协议的总和。它采用4层结构,分别是应用层、传输层、网络层和链路层每一层都调用它的下一层所提供的协议来完成自己的需求。各层结构的简述数据链路层、网络层（IP）、链路层（tcp、udp）处于内核态应用层（DNS、ftp、https协议）处于用户区参考：https://www.cnblogs.com/onepixel/p/...
2019-08-03 17:20:05
1129
原创 插入排序及其时间复杂度、代码(c++实现)、改进和应用场景
插入排序插入排序的思想：检查第i个数字，如果在它的左边的数字比它大，进行交换，这个动作一直继续下去，直到这个数字的左边数字比它还要小，就可以停止了。插入排序法主要的回圈有两个变数：i和j，每一次执行这个回圈，就会将第i个数字放到左边恰当的位置去。插入排序是稳定的非线性排序算法。从第一个元素开始，该元素可以认为已经被排序，该序列称为Done取出下一个元素，在已经排序的元素序列Done中从后...
2019-07-28 20:37:23
549
原创 计数排序及其时间复杂度、代码(c++实现)、应用场景
计数排序计数排序是一种非基于比较的排序算法。基本思想是：用空间换时间，本质上是建立了基于元素的Hash表。1、时间复杂度时间与空间复杂度均为O(n)。基于比较的排序算法时间复杂度最小是O(nlogn)的。计数排序、桶排序与基数排序都是线性排序。...
2019-07-28 20:09:17
856
原创 归并排序及其时间复杂度、代码(c++实现)、改进和应用场景
一、归并排序基本思想：将数组A[0 … n-1]中的元素分成两个子数组A1[0 … n/2]和A2[n/2+1 … n-1]。分别对这两个子数组单独排序，然后将一排序的两个子数组归并成一个含有n个元素的有序数组。归并排序包含不相邻元素的比较，但并不会直接交换。在合并两个已排序的数组时，如果遇到了相同的元素，只要保证前半部分数组优先于后半部分数组，相同元素的顺序就不会颠倒，所以归并排序属于稳定的...
2019-07-27 20:14:23
3090
原创 11.算法之快速排序
数组中的第K个最大元素在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。示例 1:输入: [3,2,1,5,6,4] 和 k = 2输出: 5示例 2:输入: [3,2,3,1,2,4,5,5,6] 和 k = 4输出: 4int target=0;class Solution {public: ...
2019-07-26 09:57:03
106
原创 B树（B-树）、B+树
B树、B+树、B*树的引入二叉查找树（Binary Search Tree），平衡二叉查找树（Balanced Binary Search Tree），红黑树(Red-Black Tree )，B-tree/B±tree/ B*-tree (B~Tree)。前三者是典型的二叉查找树结构，其查找的时间复杂度O(log2N)与树的深度相关，那么降低树的深度自然会提高查找效率。在大规模的数据存储中，...
2019-07-25 11:45:56
255
原创 红黑树
红黑树的优势二叉查找树：左子树的所有节点的值均小于或等于它根节点的值右子树的所有节点的值均大于或等于它根节点的值左、右子树也分别为二叉排序树二叉查找树蕴含着二分查找的思想，查找所需的次数等同于二查找树的高度。但是二叉查找树存在着一定的缺陷。二叉查找树会因为插入的数值不均衡导致树的高度随着插入的节点个数的增多而线性增长。例如：插入7，6，5，4，3，二叉树就退化成不平衡的链表结构...
2019-07-24 21:59:40
252
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人