doctor_xiong-CSDN博客

原创【C++】TopK问题！

问题描述：在无序的数组中查找最大（最小）的前K个元素？例如：arr[] = {9,1,6,2,3,8,3,4,7,0}最大的四个元素是6，7，8，9思路：使用小堆，先将数组中的K个元素插入到堆中，然后再从第K个开始遍历数组，如果数组中的元素大于，堆顶元素，就将对顶元素pop，然后再将数组中的元素push进堆里面去实现代码：#include<iostream>u...

2018-07-17 16:35:49 1599

原创【网络】CGI入门！！

概念： CGI：通用网关接口（Common Gateway Interface）是一个Web服务器主机提供信息服务的标准接口。通过CGI接口，Web服务器就能够获取客户端提交的信息，转交给服务器端的CGI程序进行处理，最后返回结果给客户端。组成CGI通信系统的是两部分：一部分是html页面，就是在用户端浏览器上显示的页面。另一部分则是运行在服务器上的Cgi程序。...

2018-06-24 15:37:21 710 1

原创【MySQL】索引和事务！！

索引索引的目的：提高数据库的性能，提高海量数据的查询速度。索引的分类 1. 主键索引 2. 唯一索引 3. 普通索引 4. 全文索引创建索引的方式主键索引 1. 在创建表的同时直接在字段名后面加上primary keycreate table stu ( id int not null primary key, name varchar(20),);...

2018-06-09 22:30:33 971

原创【网络】epoll简单概念！！

相关APIepoll_createepoll_create(int size);//创建epoll模型注：在linux2.68之后，size被忽略使用epoll_create创建模型的时候，内核会创建红黑树和就绪队列以及回调机制用来维护所关心的文件描述符。红黑树的节点用来保存用户所关心的文件描述符就绪队列用来保存已经响应的文件描述符epoll_ctlepoll_ct...

2018-06-03 23:20:24 299

原创【网络】IP协议和ARP协议！！

IP协议和ARP协议IP协议IP协议属于网络层的协议，是一个无连接、不可靠的协议。主要的作用是在复杂的网络中寻找合适的传输路径。 IP协议的报头结构： - 版本：IP协议的版本（IPv4、IPv6） - 首部长度：IP协议的首部长度，四个字节最大为15，所以IP报头的最大长度为15*4 = 64字节 - 区分服务： - 总长度：IP报文的总长度 - 标识：当IP报文经过...

2018-06-01 10:35:30 5497 1

原创【网络】select模型基本概念！！

select模型select机制当使用read等系统调用在缓冲区里面读取数据的时候，如果和缓冲区里面没有数据，那么函数会被系统直接挂起等待，这种函数称之为阻塞式接口。如果缓冲区内一直没有数据那么该系统调用会一直阻塞，知道缓冲区内有可读数据。使用select函数的时候，select可以注册多个需要执行IO的socket，并不断的调用select读取被激活的socket，即在一个线程上面可以同...

2018-05-28 22:57:36 1819 3

原创【网络】当在浏览器里面输入url会发生什么？

当在浏览器里面输入url会发生什么？应用层当在浏览器里面输入url的时候，浏览器会现在本机查找url对应的IP地址，如果没有，那么就会向上一级发出DNS请求，知道找到对应的IP地址或者找到根DNS服务器。当找到对应的IP地址的时候，浏览器发出http请求，这时http请求里面包含http报头和一些相关的信息。传输层在传输层，主要的目的是使用TCP建立可靠的连接和将应用层的数据进行分...

2018-05-25 22:31:24 665

原创【网络】TCP的可靠机制！！

TCP的可靠机制确认应答ACK TCP将每一个要发送的数据进行编号，每一份发送的数据接收方就会应答确认序号。回应的序号用于告诉接收者已经接收到的数据。超时重传如果在发送数据的时候发生丢包现象，那么发送方就不会收到接收方的ACK应答，那么在TCP里面就会在隔一定的时间就会重新发送数据。存在的问题一担发生发送方无法接收到ACK应答的时候，在接收方就会出现很多重复的数据，TCP需要...

2018-05-21 22:29:00 462

原创【网络】TCP协议！！

TCP协议段结构源端口地址和目的地址：表示数据从哪个进程来，哪个进程去 32位序号：每个TCP数据包发送出去，需要序号进行编号，方便接受端正确的识别包的序号 32位确认序号：每个包发送出去需要对端确认，确认序号为了给对端发送确认序号 4位TCP报头长度：用来表示TCP首部有多少个32bit位（4字节），TCP最大长度为15*4=60 6个标志位： URG：表示紧急指针是否有效...

2018-05-13 22:23:41 280

原创【MySQL】表的约束以及增删改操作！！

表的约束空属性 null：如果不设置，默认为nullnot null：设置当前字段不为空，再插入数据的时候当前字段不可以为空create table tt1( id int not null, name varchar(20));默认值（default） create table tt2( id int not null, name varch...

2018-05-12 23:16:29 610

原创【网络】TCP通讯协议里面的三次握手和四次挥手的流程！！

服务器初始化的一般过程：调用socket 函数获取创建的文件描述符使用bind函数对IP和port进行绑定调用listen函数监听socket创建的文件描述符调用accept函数对客户端进行连接客户端和服务器建立连接和断开连接的过程：三次握手过程： - 使用`socket`创建文件描述符 - 调用connect向服务器发起连接请求 - connect向...

2018-05-06 21:40:49 765

原创【MySQL】数据库的基本数据类型！！

tinyint 带符号的范围是-128~127，不带符号的范围是0~255。如果不加unsigned，默认为带符号的。 bit（M）其中M为指定的位数，默认1，范围为1~64；在显示的时候是按照ASCII码的形式展示。当类型是bit(1)的时候，那么存入的值只能够是0或者1。ﬂoat[(m, d)][unsigned] m为指定显示的长度，d位小数占用的长度，占用4个字...

2018-05-05 21:28:39 440

原创【网络】网络套接字基本概念！！

IPIP地址是在IP协议里面标识网络中的不同的主机在IPV4协议里面的IP地址是4个字节，32位通常使用点分十进制来表示IP地址，即192.168.2.120,用点来区分每一位端口号在每一台主机里面运行的进程不是唯一的，所以在进程使用网络资源的时候就需要使用一种标记来标记同一个主机里面的使用网络资源的进程，即端口号。一个进程只能占用多个端口号，但一个端口号可以被一个进程占...

2018-04-27 22:28:13 795 2

原创【MySQL】MySQL的基本操作！！

创建数据库： CREATE DATABASE [IF NOT EXISTS] db_name [create_speciﬁcation [, create_speciﬁcation] ...] 大写字母为关键字； []里面的选项为可选选项；创建库的时候使用校验规则utf8_ general_ bin ：区分大小写 utf8_ general_ ci ：不区分大小写创建表...

2018-04-23 18:19:25 398

原创【数据结构】mgraph！！

概念：图是由定点集合和定点间关系组成的数据结构。有向图：在有向图里面的\A,C和C,A是不同的两个边，即在图里面的边是有方向的。无向图：在无向图里面的A,C和C,A是相同的一条边，即在无向图里面的边是没有方向之分的。定点的度：定点的度是指与定点相关的边的个数。重点邻接矩阵方式存储图邻接链表方式存储图邻接矩阵无向图：有向图：代码实现：template<class V,

2018-04-21 13:34:31 5156

原创【Linux】进程组、作业、回话、守护进程的基本概念！！

进程组每一个进程在创建的时候就有自己的进程ID，同时也有自己的ID（PGID）。一个进程组，可以含有一个或者多个进程，进程组也有自己的ID，通常是进程组里面第一个进程的ID。进程组的特点：每一个进程组有一个组长进程，进程组长的ID等于进程组ID进程组长可以创建进程组、创建进程组里面的进程只要进程组里面含有进程，那么进程组就存在，这与进程组长的存在没有关系进程组里面的最后一个进程...

2018-04-15 21:24:11 329

原创【Linux】malloc和free底层的简单实现！！！

从操作系统角度来看，进程分配内存有两种方式，分别由两个系统调用完成：brk和mmap（当然在这里是不考虑共享内存）brk是将数据段(.data)的最高地址指针_edata往高地址推；mmap是在进程的虚拟地址空间中（堆和栈中间，称为文件映射区域的地方）找一块空闲的虚拟内存。注：在开辟空间的时候只是在进程的虚拟地址空间内开辟指定大小的内存，但是并没有实际在物理内存上面开辟空间，只有当对...

2018-04-15 12:19:12 1153

原创【Linux】读写锁！！

读写锁的三二一模型三：三种关系、读者与读者之间没有关系、写者和读者互斥且同步、写者与写者之间互斥二：两种对象、读者和写者一：一个交易场所读写锁应用的场景：在多线程程序里面，线程对临界资源的访问比较多，而对临界资源的修改较少。在读写者模型里面，由于写操作的次数比较少。那么在该模型里面的写操作的优先级必读操作的优先级高。加入读的优先级比写优先级高，那么就会出现读操作在一直读，...

2018-04-13 21:53:39 252

原创【数据结构】并查集！！

在M个人里面包含有N个朋友关系R，如果朋友的朋友也属于同一个朋友圈，那么设计程序计算共有多少个朋友圈？思路：使用并查集，开始时候将M个元素的数组初始化成-1，当加入元素的时候，如果元素的位置上面的数据不是负数，那么就将该数据作为下标继续寻找下标为负数的位置，如果找到了下标为负数的位置就将需要关联的数据的数据加到寻找到的位置上面。如图，将具有直接朋友关系的看成一棵树，那么并查集里面的负数...

2018-04-12 12:22:59 229

原创【Linux】消费者与生产者模型！！

POSIX信号量信号量的类型：sem_t 初始化信号量函数：int sem_init(sem_t* sem,int pthread,unsigned value); sem:信号量名 pthread：0表示线程间共享，非0表示进程间共享 value：信号量初始值销毁信号量函数：int sem_destrpy(sem_t* sem); 等待信号量：int sem_wait(sem_...

2018-04-07 21:10:12 326

原创【Linux】多进程和多线程的调试！！

在gdb调试多线程好人多进程的程序上面，默认的是调试主程序。但是gdb是支持调试多线程和多进程的。调试多进程在调试多进程的时候需要设置follow-fork-mode（默认parent）和 detach-on-fork（默认on）的值设置方法：set follow-fork-mode [parent|child] set detach-on-fork [on|off]...

2018-04-05 17:06:13 293

原创【Linux】死锁！！！

死锁概念在多线程程序里面多个线程因为竞争资源而产生的僵持现象。产生死锁的四个条件互斥条件：每个资源每次只能被一个进程使用，即在一度那时间内得某资源仅为一个进程所占有。此时若有其他的进程请求该资源，则请求进程只能等待。请求与保持条件：进程已经保持了至少一个资源，但是又提出来新的资源请求，而该资源已经被其他的进程战友，此时请求进程被阻塞，但自己已获得的资源保持不放不可剥夺条件：进程获...

2018-04-04 22:19:34 522

原创【Linux】线程的互斥与同步！！

在系统里面线程的资源不同于进程的资源，进程在系统里面是一个一个的单独个体，但是线程的资源大部分是共享的，所以在线程访问问一个临界资源的时候需要同步与互斥机制，从而保证在多线程的程序里main不会出现问题。模拟实现售票系统：int tacket = 100;void* sell_tacket(void* arg){ while(1){ if(tacket &gt...

2018-04-01 22:45:02 146

原创【Linux】线程控制！！

在Linux里面线程被称为轻量级线程，而线程的退出有以下几种方法：线程调用return函数返回，但是在主线程里面不适用，因为主线程里面调用return函数相当于在主线程里面调用exit函数。线程调用pthread_exit函数退出线程调用pthread_cancel函数终止同一个进程里面的其他线程在系统的角度来看待线程是没有具体的结构的，在系统的眼里只有进程。所以线程和进程一样...

2018-03-31 21:54:26 177

原创【数据结构】hash算法！！！

Hash表是一种可以将查找元素的时间复杂度降为O(1)的高效算法。基本原理：将所有的数据通过hash函数映射到hash表里面，如果需要查找元素的时候再通过hash函数来计算出来元素在hash表里面的位置，从而一次将需要的元素找到。存在的问题如果有两个或者更多的元素通过hash函数映射的hash位置是相同的那么就会出现问题。解决办法线性探测：在产生hash冲突的时候，...

2018-03-30 21:48:03 424

原创【linux】线程的基本概念！！！

在linux里面是没有实际的线程的结构，但是在linux里面为了描述线程，将进程分为很多的轻量级进程，这些轻量级的进程被称之为线程。两个区别：进程是系统分配资源的基本单位线程是系统调度的基本单位由于线程在进程的内部运行，那么在创建一个线程的时候需要资源和操作相对于创建进程要少的多。创建进程的过程：申请空白PCB为新进程分配资源初始化进程控制块将新创建的进程...

2018-03-27 22:32:06 297

原创【linux】信号的捕捉！！

在linux里面产生信号的时候并不是当信号产生的瞬间就将信号进行处理，而是当系统感到合适的时候就会将该信号进行处理。当执行用户自定义的信号处理动作的时候的信号执行过程当执行的是用户的自定义信号处理函数的时候从内核空间返回到用户空间进行用户自定义的信号处理函数调用，当执行完用户自定义的信号处理函数的时候返回内核空间，然后再返回到用户空间继续执行进程的其他代码。int sigactio...

2018-03-24 16:11:38 220

原创【linux】信号！！

在linux里面使用kill -l命令可以显示系统的信号列表这里的1~31是普通信号，34~64是实时信号，这里只研究普通信号内核里面的信号信号的产生用户在键盘上按下某些键的时候，驱动会发送信号给前台进程。硬件产生信号，当硬件检测到异常的时候会通知内核，内核给进程发送适当的信号。进程使用kill函数向进程发送信号软件条件产生信号处理的方式忽略此信号执行该信号...

2018-03-24 15:17:27 152

原创【linux】信号量！！！

基本概念：临界资源：当一块资源只能够被一个进程访问的时候，这块资源就叫临界资源。临界区：进程里面访问临界资源的代码叫做临界区。信号量的本质：计数器，计算描述临界资源的多少。信号量集函数：int semget(key_t key,int nsem,int semflg);key:信号量集的名称nsems：信号量集的个数semflg：模式标志若函数调用成功则返回信号集...

2018-03-23 22:18:45 219

原创【linux】共享内存！！

在system V IPC里面，共享内存是所有进程间通信速度最快的。因为在消息队列里面，在消息传递的时候需要进行两次拷贝（将数据拷贝到队列节点里面，从队列节点里面拷贝到内存）。基本原理：注：进程间通讯的本质就是将不同的进程看到同一块地址空间。但是在页表的映射下，不同的进程所占有的实际地址空间是不同的，所以在不同的进程里面数据是相对独立的。但是要是有一块不同进程都可以访问的空间，那么就可...

2018-03-18 22:43:23 214

原创【linux】页表的简单理解！！！

在使用的计算机内存（4G）上面用户可以使用的内存只有0~3G，3~4G是系统内核使用的区域。但是在物理内存上面，任何的区域和位置都是可读可写操作的，假如进程直接访问的是物理内存，那么系统就会存在很大的不安全性。页表页表的存在很好的协调了物理内存和虚拟内存，从而很好的提高系统的安全性。在一个进程里面使用的内存可能是很少的一部分，但是存在的实际内存确实很大的，所以在使用页表的时候可...

2018-03-12 22:59:10 7302 3

原创【linux】管道！！！

进程间通讯的方式有：管道消息队列共享内存信号量在这里面管道是最古老的进程间通讯方式，管道又分为匿名管道和命名管道。匿名管道局限性：只能够在具有亲缘关系的进程里面使用管道提供流式服务管道的生命周期随进程内核会对管道操作进行互斥和同步管道数据只能单向传递在匿名管道里面使用到的函数是int pipo（int fd[2]）; fd[0]表示的是读端 fd[1]...

2018-03-12 21:42:21 254

原创【数据结构】二叉搜索树！！！

二叉搜索树的结构类似于二分查找的思想，在二叉树结构里面，将数据的大小分为树的左右子树，从而在搜索的时候类似于二叉搜索。如图：当搜索一个二叉搜索树的时候时间复杂度就是O(logN). 构建搜索二叉树：BSTree(int *arr,size_t size) :_root(NULL) { int index = 0; ...

2018-03-08 12:10:37 226

原创【数据结构】实现红黑树！！！

相对于AVL树来说，红黑树去掉了AVL树里面的平衡因子，利用树节点的颜色来调整数的平衡。红黑树的创建原则：每个节点的颜色不是黑色就是红色树的根节点是黑色的如果一个节点的颜色是红色的，那么它的里两个孩子结点颜色是黑色的（即，没有两个连续的红色结点）对于每个节点，在其后面的简单路径上面的黑色结点的个数是相同的每个叶子节点都是黑色的（叶子节点是指空节点）注：当满足上面的颜色限...

2018-02-27 13:33:38 161

原创【Linux】设计模式-----简单工厂模式

概念：简单工厂模式即，只需要输入实例化对象的名称，工厂类就可以实例化出来需要的类。核心：实现工厂模式的核心就是多个派生类public继承基类，同时根据用户的需求在简单工厂类里面实例化基类的对象，从而根据基类里面的虚函数来实现对派生类的函数调用，同时实现多态。如图：利用简单计算器的实例来实现工厂模式：#include<iostream>using namesp...

2018-02-25 14:58:30 420

原创【Linux】设计模式---单例模式

概念：单例模式即在单例类实例化对象的时候只能实例化出来一个对象。单例模式实现的要点：单例类只能实例化出来一个单例对象必须能够自行创建实例对象必须能够向整个系统提供这个实力对象单例模式的优点：单例模式只能够创建一个对象，所以在资源方面可以做到节约内存资源单例模式不需要频繁的销毁和创建，所以在效率方面有所提高单例对象在整个系统里面只有一份，可以做到避免共享资源的重复占用...

2018-02-21 17:17:01 1054

原创【Linux】进程终止方式--exit的调用过程！！！

在linux里面的进程终止的方法有8种。五种正常终止：从main函数返回调用exit函数调用_exit或者_Exit最后一个线程从启动实例返回从最后一个线程调用pthread_exit三种议程终止：调用abort函数接收到一个终止信号最后一个线程对取消请求做出响应exit的调用过程函数原型：void exit(int status); 在调用一个函数...

2018-02-12 21:33:18 2063

原创【其他】字符串的解析！！！

在操作字符串的时候经常会碰到，一类是如何将字符串的部分替换，另一类就是如何将字符串进行重新组合。一、如何将‘aaa@@@@bbbbbb@@@@@cccccccc@@@@@@dddddddddddd’,替换成‘aaa bbbbbb ccccccc dddddddddddd’ 要求：时间复杂度O(1),空间复杂度O(1)方法：定义两个指针开始时候都指向字符开头，当另外一个走到需要去掉的字...

2018-02-08 19:16:44 234

原创【C++】标准文件的输入输出！！！

在C++里面的IO都是以流的形式存在的，所以在对文件进行操作的时候也是以流的形式操作的。主要的流：ifstream、ofstream、fstream，都包含于fstream头文件里面。 ifstream：从内存将文件数据读在硬盘 ofstream：从硬盘将文件数据读到内存 fstream：可以对打开的文件进行读写操作ofstream的继承关系 ifstream的继承关系 ...

2018-02-08 17:43:12 482

原创【数据结构】归并排序！！！

归并排序整体思想：将数据分成很多的部分，每次排序数据的一部分，然后将两部分的数据进行整体排序，这样一步一步将整体数据排序。如图：注：将需要排序的数据进行分块，当每个块的数据足够的少的时候就可以进行效率高的排序方法，当两块数据排序好的时候就可以将两块排序好的数据进行合并。具体实现方法：#ifndef _MERGESORT_H#define _MERGESORT_H#

2018-02-05 21:24:58 225

空空如也

空空如也