- 博客(58)
- 收藏
- 关注
RSS订阅原创 AVL树概念及简单实现
为什么会有AVL树？极端情况下的二叉搜索树效率是O(n),如果调整二叉树搜索树的高度，那么树的搜索效率会达到O(log n).（ 这里简单介绍一下二叉搜索树：当前结点大于它的左子树结点，小于右子树的结点，中序遍历是按照升序进行排列的。并且树中没有相同的结点: 二叉搜索树的实现.）AVL树即平衡树，在二叉搜索树的前提下增加了平衡因子，使得每个结点的左右高度差不超过1.平衡因子=右子树的高度-左子树的高度AVL树的插入：AVL的插入和二叉搜索树一样的方法，只不过需要更新平衡因子。1.如果在左
2021-01-31 00:38:33
197
原创 单链表的快排
面试有被问到快排单链表，啊，，这，普通的快排是双指针，一个找比基准值小的，另一个从另一边找比基准值大的，然而单链表只能正向遍历，所以就只采取快排的思想，即分治的思想。通过查阅资料发现了一种适合单链表的快排。先以数组为列int i=0;int j=i+1;int key=0;//基准值int temp=i;while(j<n){if(arr[j]>=key)++j;else{++i;swap(arr[i],arr[j]);++j;}}然后再 swap(arr[i],
2020-12-22 20:17:12
213
原创 共享内存
共享内存其实是不同进程之间通过访问同一块内存进行通信。之前博客有写道共享内存的一些接口，今天用代码实践了一下，证实了一个概念，，，共享内存的生命周期跟随操作系统（破涕为笑）写端进程代码#include<stdio.h>#include <unistd.h>#include <sys/shm.h>int main(){ //创建共享内存 int shmid=shmget(IPC_CREAT,1024,IPC_CREAT|0664);
2020-12-03 20:45:13
206
1
原创 分页式、分段式、段页式
分页式：页号+页内偏移，通过页号找到块号，通过块号，算出块的起始地址，最后块的起始地址+页内偏移分段式：段号+段内偏移 通过段号找到段的起始地址，然后段的起始地址+段内偏移段页式：段号+页号+页内偏移 先通过段号找到页的起始地址，通过页表当中的页号找到对应的块号，再通过块号计算出起始地址，块的起始地址+页内偏移...
2020-08-16 15:51:14
4076
原创 动态规划
动态规划具备了以下三个特点把原来的问题分解成了几个相似的子问题。所有的子问题都只需要解决一次。储存子问题的解。动态规划的本质，是对问题状态的定义和状态转移方程的定义(状态以及状态之间的递推关系)常见的动规题字符串分割二级目录三级目录字符串分割：link题目描述：给定一个字符串s和一组单词dict，判断s是否可以用空格分割成一个单词序列，使得单词序列中所有的单词都是dict中的单词（序列可以包含一个或多个单词）。例如:给定s=“leetcode”；dict=[“leet”, “cod
2020-08-14 01:01:31
113
原创 TCP可靠传输
这里写目录标题确认应答机制超时重传机制拥塞控制机制慢启动拥塞避免快重传快恢复滑动窗口机制捎带应答机制延时应答机制流量控制保活计时器确认应答机制当发送方发送一个报文的时候，需要带上报文序号，而接收方收到该报文之后，会给发送方发送确认报文，确认报文里面有确认序号即期望收到的下一个序号是多少。超时重传机制当发送方发送一条消息之后，就会开启一个重传计时器，当发出去消息的时间大于RTO，就会重传该条数据（无论是接收方没有收到消息还是发送方没有收到确认，都是没有收到确认报文，RTO时间之后会重传）RTO:超时
2020-08-12 21:24:57
129
原创 二叉搜索树
二叉搜索树（排序二叉树）的概念若左子树不为空，则左子树所有结点的值都小于根结点的值若右子树不为空，则右子树所有结点的值都小于根节点的值左右子树也分别是二叉搜索树二叉搜索树的最优情况：log 以2为底的N (log2N)二叉树的最坏情况：N/2;二叉树的模拟实现template<class T>//二叉搜索树的结构struct BSTNode{ T _val; BSTNode<T>* left; BSTNode <T>* right; BSTN
2020-08-08 00:03:33
150
原创 多态及其原理
这里写目录标题什么是多态构成多态的条件重载、重写、重定义虚函数C++11 override 和 final抽象类多态的实现原理什么是多态多态就是多种形态，完成某个行为，不同的对象调用会产生不同的形态。构成多态的条件1.必须通过对象的指针或者引用调用虚函数2.被调用的函数必须是虚函数，子类的虚函数必须重写父类的虚函数重载、重写、重定义重载：相同作用域下，函数名相同，参数列表不同（参数的个数，顺序，类型）重写（覆盖）：派生类有和基类相同的虚函数，（函数名相同，参数列表相同，返回值相同）（协变例外）
2020-08-07 12:46:59
1493
原创 string的现代简单写法
只需要拷贝和赋值#include <iostream>using namespace std;namespace lhy{ class string { public: string (const char*str=""):_str(new char[strlen(str)+1]) { strcpy(_str,str); } ~string() { delete[]_str; _str=nullptr; } /* 传统写法 /
2020-08-04 17:52:16
200
原创 C复习总结（二）
这里写目录标题字符串函数sizeof与strlen有以下区别：atoi()函数itoa()函数内存对齐为什么存在内存对齐?malloc、calloc和realloc内存分配的几个区域柔性数组C复习总结（一）字符串函数size_t strlen ( const char * str );返回字符串中’\0’前面出现的字符个数char* strcpy(char * destination, const char * source );把含有’\0’结束符的字符串复制到另一个地址空间ch
2020-08-03 23:56:32
129
原创 C++复习（二）
这里写目录标题C++中struct和class的区别this指针构造函数析构函数拷贝构造赋值运算符主要有四点：const成员函数初始化列表static成员链接：C++复习（一）.C++中struct和class的区别C++需要兼容C语言，所以C++中struct可以当成结构体去使用。另外C++中struct还可以用来定义类。和class是定义类是一样的，区别是struct的成员默认访问方式是public，class是struct的成员默认访问方式是private。一个类的大小就是成员变量占用空间之和
2020-08-03 19:11:21
171
原创 C++复习（一）
这里写目录标题缺省参数命名空间C++为什么支持函数重载extern "C"引用指针和引用的区别inline宏的优缺点？inline与宏比较autoauto不能推导的场景缺省参数缺省参数是声明或定义函数时为函数的参数指定一个默认值。在调用该函数时，如果没有指定实参则采用该默认值，否则使用指定的实参。分为全缺省和半缺省规则：半缺省参数必须从右往左依次来给出，不能间隔着给缺省参数不能在函数声明和定义中同时出现（如果生命与定义位置同时出现，恰巧两个位置提供的值不同，那编译器就无法确定到底该用那个缺省值
2020-08-03 18:57:34
159
原创 C复习总结(一）
这里写目录标题整形提升数组与指针大小端概念：大小端产生的原因如何判断大小端整形提升整形提升的规则1.若是有符号数，则前面8*3位补符号位。2.若是无符号数，则前面面8*3位补0。整形提升的意义表达式的整型运算要在CPU的相应运算器件内执行，CPU内整型运算器(ALU)的操作数的字节长度一般就是int的字节长度，同时也是CPU的通用寄存器的长度。因此，即使两个char类型的相加，在CPU执行时实际上也要先转换为CPU内整型操作数的标准长度。通用CPU（general-purpose CPU）是难以
2020-08-02 11:38:58
133
原创 求栈的最小元素或者队列的最大元素
链接: https://www.nowcoder.com/practice/4c776177d2c04c2494f2555c9fcc1e49?tpId=13&tqId=11173&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking.
2020-08-01 14:40:35
282
原创 表的约束
表的约束有 null/not null,default,comment,zerofill,primary key,auto_increment,unique key).这里写目录标题空属性默认值（default)列描述（comment)zerofill主键（primary key)自增长（auto_incremet)唯一键（unique)外键空属性null(默认值)和not null数据库的默认字段基本都是null，但是要尽可能保证字段不为空，因为数据为空无法参与运算。如果没有指定不能为空的字段相
2020-07-13 21:30:11
165
原创 mysql---基础操作(二)
1.创建表create table table_name(field1 datatype,field2 datatype,filed3 datatype) character set 字符集 collate 校验规则 engine 存储引擎field 表示列名datatype 表示列的类型character set 字符集，如果没有指定字符集，则以所在数据库的字符集为准collate 校验规则，如果没有指定的校验规则，则以所在数据库的校验规则为准2.查看表结构desc 表明；
2020-07-08 19:02:24
64
原创 mysql---基础操作(一）
1.运行mysql服务端2.客户端连接mysql服务器3.查看数据库4.创建数据库5.使用数据库6.创建数据库表7.给数据库表中插入数据8.查询数据库表中的数据9.查看数据库表10.查看数据库的版本11.查看系统默认的字符集12.查看系统支持的数据集只截了一部分字符集：ASCII字符集：采用的是一个字节的低七位表示字符，高位始终为0；LATIN1字符集：相对于ASCII字符集做了一个扩展，启用了最高位；GBK字符集：支持中文，字符可以使用一个字节，也
2020-07-06 23:53:29
114
原创 UDP套接字实现
UDP套接字的相关接口及具体含义的链接.#pragma once#include <unistd.h>#include <cstdio>#include <cstring>#include <iostream>#include <sys/socket.h>#include <netinet/in.h>#include <arpa/inet.h>#include <sys/types.h>usi
2020-06-18 15:21:27
379
原创 网络编程套接字（一）
这里写目录标题网络基础概念网络协议初识OSI七层模型：TCP/IP五层模型IP地址和端口TCP和UDP网络字节序socket编程接口创建套接字(TCP/UDP,客户端+服务器）绑定地址信息（TCP/UDP，服务器）发送数据接收数据关闭套接字网络基础概念网络协议初识OSI七层模型：物理层，数据链路层，网络层，传输层，会话层，表示层，应用层TCP/IP五层模型应用层：负责应用程序之间的数据传输，程序员就是工作在这一层面典型的协议：HTTP协议，FTP协议，DNS协议，SMTP协议传输层：负责端
2020-06-18 15:08:38
293
原创 C++继承
这里写目录标题继承的概念和定义概念继承关系和访问限定符基类和派生类对象复制转换继承中的作用域派生类的默认成员函数菱形继承和菱形虚拟继承继承和组合继承的概念和定义概念继承机制是面向对象程序设计使代码可用复用的最重要手段，它允许程序员在保持原有类特性的基础上进行扩展，增加功能，产生新的派生类。继承呈现了面向对象程序设计的层次结构，体现了由简单到复杂的认知过程。继承是类设计层次的复用继承关系和访问限定符继承的方式有：public继承，protected继承，private继承访问限定符：public访
2020-06-02 22:50:32
210
原创 多线程（二）
这里写目录标题线程安全与重入1. 概念2.常见的线程不安全情况3.常见的线程安全情况4.常见的不可重入情况5.常见可重入的情况6.可重入与线程安全的联系7.可重入与线程安全的区别互斥锁1.定义互斥锁2.初始化互斥锁3.加锁4.解锁5.销毁互斥锁6.互斥锁加锁解锁的底层实现原理死锁什么是死锁死锁的四个必要条件避免死锁的方法线程安全与重入1. 概念线程安全：多个线程并发同一段代码时，不会出现不同的结果。对全局变量或者静态变量进行操作，并且在没有锁保护的情况下，会出现线程安全的问题重入：同一个函数被不同
2020-05-29 16:45:15
392
原创 多线程（一）
多线程线程的概念线程优缺点线程的独有和共享多线程和多进程的区别创建线程线程终止线程等待线程分离线程的概念在程序里一个执行路线叫做线程，线程是“一个进程内部的控制序列”一切进程至少都有一个执行线程线程在进程内部运行，本质时在进程地址空间运行在Linux系统中，在CPU眼中，看到的PCB都要比传统的进程更加轻量化透过进程虚拟地址空间，可以看到进程的大部分资源，将进程资源合理分配给每个执行流，就形成了线程执行流对于linux内核而言，没有线程的说法，内核对于创建线程而言就是创建一个轻量级进程（L
2020-05-24 21:46:57
209
原创 vector的深度剖析及模拟实现
vectorvector的介绍reserve和resizevector的模拟实现vector的介绍vector在C++标准模板库中的部分内容，它是一个多功能的，能够操作多种数据结构和算法的模板类和函数库。vector是表示可以改变大小的序列容器可以像数组一样使用。采用连续的存储空间存储元素，支持元素的随机访问，但是又不像数组，可以动态自动扩容。（vs下1.5倍增容，g++下2倍增容）vector使用动态分配数组存储它的元素，当新插入一个元素时，如果空间不够，则会分配一个新的数组，将全部元素移动到
2020-05-21 22:34:13
196
原创 进程间通信（二）
目录命名管道system v共享内存消息队列命名管道1 .命名管道是具有标识符的管道，内存当中开辟的内存是由标识的，不同的 进程可以通过名字访问命名管道2.创建命名管道使用命令进行创建mkfifo [命名管道的文件名称] 文件类型是p，p代表是管道文件使用函数创建命名管道mkfifi（char* pathname,mode_t mode)mode:指定创建出来的命名管道的读写权...
2020-05-06 17:50:00
146
原创 化栈为队及化队为栈
文章目录队列的实现两个栈实现队列两个队列实现栈队列的实现思路：用链表实现队列，先定义一个结构体QNode，里面存放数据域和指针域，因为队列只在队头和队尾进行操作，可以让两个指针分别指向队头和队尾，所以再定义一个结构体Queue里面存放两个QNode结构体的指针——front和_rear，让这两个结构体一个指向链表的头一个指向尾。然后通过Queue这个结构体里面的两个指针来对队列进行各种操作。...
2020-04-24 23:06:40
224
原创 Linux --进程间通信(一)
进程间通信：管道（数据传输） 共享内存（数据共享） 消息队列（数据传输） 信号量（进程控制）进程间通信产生的目的：每一个进程都拥有自己的独立的虚拟地址空间和页表结构，促使了进程独立，导致了进程与进程之间相互协作的问题为了解决这个问题产生了进程间通信进程间通信的种类：1.数据传输2.数据共享3.进程控制管道：匿名管道和命名管道匿名管道：什么是管道：管道就...
2020-04-21 16:29:52
269
原创 基础IO
C文件的接口FILE * fopen(const char * path,const char* mode)打开文件出错则返回空FILE： 返回值是文件流指针path: 需要打开哪一个文件，可以带路径，如果不带路径，则在当前的目录下寻找mode:r:以读方式打开，如果当前打开的文件不存在则报错r+:以读写方式打开，如果当前打开的文件不存在，则报错w:以写方式打开，如果文件不存在...
2020-04-08 17:00:17
157
原创 再识从预处理到链接
预处理阶段test.c----->test.igcc -E test.c -o test.i展开头文件进行宏替换去注释条件编译编译阶段进行语法语义检测，将文本文件test.i翻译成test.s的汇编程序gcc -S test.c -o test.s汇编阶段（生成机器可执行的代码）汇编器将test.s翻译成机器语言指令，把这些指令打包成一种叫做可重定位目标程序的格式，...
2020-03-25 22:58:33
136
原创 进程概念（二）
1.fork初始fork函数将运行着的程序分成2个（几乎）完全一样的进程，每个进程都启动一个从代码的同一位置开始执行的线程。这两个进程中的线程继续执行，就像是两个用户同时启动了该应用程序的两个副本。fork系统调用用于创建一个新进程，称为子进程，它与进程（称为系统调用fork的进程）同时运行，此进程称为父进程。创建新的子进程后，两个进程将执行fork（）系统调用之后的下一条指令。子进程使用相同...
2020-03-17 17:47:21
181
原创 进程描述（一）
操作系统是什么操作系统是管理计算机硬件与软件资源的计算机程序，同时也是计算机系统的内核与基石。操作系统需要处理如管理与配置内存、决定系统资源供需的优先次序、控制输入设备与输出设备、操作网络与管理文件系统等基本事务。操作系统也提供一个让用户与系统交互的操作界面。设计OS的目的与硬件交互，管理所有的软硬件资源为用户程序（应用程序）提供一个良好的执行环境如何理解管理管理=描述+组织...
2020-03-06 22:57:13
255
1
原创 C++命名空间
什么是命名空间命名空间是ANSIC++引入的可以由用户命名的作用域。使用命名空间的目的是对标识符的名称进行本地化，以避免命名冲突或名字污染。它可作为附加信息来区分不同库中相同名称的函数、类、变量等。使用了命名空间即定义了上下文。本质上，命名空间就是定义了一个范围。有了命名空间的概念，标识符就被限制在特定的范围呢，不会引起命名冲突。最典型的例子就是std命名空间，C++标准库中所有标识符都包含在...
2020-03-06 00:13:08
338
原创 Linux 编辑器和调试器的使用
编译器gcc/g++的使用格式： gcc 选项 要编译的文件 选项 目标文件1.预处理（进行宏替换）预处理功能主要包括 宏定义，文件包含，条件编译，去注释等。预处理指令是以#号开头的代码行。eg： gcc -E hello.c -o hello.i选项“-E”，作用是让gcc在预处理结束后停止编译过程。选项“-o”是指目标文件，“i”文件为已经过预处理的C原始程序。2....
2020-03-04 16:36:47
205
原创 Linux基础指令篇（一）
1.ls指令功能：ls对于目录，该命令列出该目录下的所有子目录与文件。对于文件，将列出文件名以及其他信息。-a 列出目录下的所有文件，包括以.开头的隐含文件-d 将目录像文件一样显示，而不是显示其下的文件。如：ls -d 指定目录-i 输出文件i节点的索引信息。如：ls -ai 指定文件-k 以k字节的形式表示文件的大小。例如ls -alk 指定文件-l 列出文件的详细信息...
2020-03-03 19:56:54
257
原创 八皇后的两种思路
题目描述：n皇后是指在一个n行n列的棋盘上，将n个皇后摆放在不同的位置，不能出现在同一行，同一列，同一斜线，问有多少种解法。思路一：建立一个二维数组，初始化都为0，（皇后的位置置1）从第一行开始放皇后，列有八种情况，从第一种情况开始，如果这个位置的上面的列，左上正对角线，以及右上正对角线没有皇后，则是安全的，这个位置可以放置皇后，继续递归下一行，否则继续探索这一行的其他列，如果这一行的所有列都...
2020-02-16 22:05:05
414
原创 经典排序算法
1.插入排序思想：从第二个数开始将待排序的数插入到前面已经排好序的相应位置直到最后一个数插入完毕2.希尔排序思想 ： 又称缩小增量排序，将待排序的数分为间距为gap(gap=size/2)的若干组，并将相同间距上的数进行插入排序，然后将gap缩小，直到gap=1时结束3.选择排序思想：每次在待排序的序列中找到最小的元素放在序列的起始位置，直到待排序的序列已经全部排好序4.堆排序...
2020-02-14 21:48:51
168
原创 堆的基本实现以及堆排序
Heap.h#pragma once#include<stdio.h>#include<stdlib.h>#include<string.h>#include<assert.h>#include<malloc.h>#include<assert.h>typedef int HPDataType;typedef...
2019-12-25 21:41:51
100
原创 有效括号
利用栈的结构，当如果遇到左括号就存入栈中，如果遇到右括号，就将栈顶的元素进行匹配，然后出栈，直到栈为空力扣：20题 有效的括号栈的实现typedef char STDataType;// 支持动态增长的栈typedef struct Stack{ STDataType* myarr; int _top; // 栈顶 int _capacity; // 容量...
2019-12-20 14:00:24
147
原创 带头双向循环链表的实现
List.h#pragma once#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<malloc.h>typedef int Datetype;typedef struct ListNode{ Datetype date; struct ListNode ...
2019-12-19 10:36:45
78
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人