萧-十一-CSDN博客

原创 C语言宏定义实现sizeof功能

可以使用如下两个宏定义实现类似sizeof的功能//针对T为一个类型名的情况#define _sizeof_type(T) (size_t)((T*)0 + 1)//针对T为一个变量或者数组名的情况#define _sizeof(T) ((size_t)(&T + 1) - (size_t)(&T))测试代码#include <stdio.h&gt...

2018-07-22 13:26:35 3296 1

原创【lintcode】删除二叉查找树的节点

描述给定一棵具有不同节点值的二叉查找树，删除树中与给定值相同的节点。如果树中没有相同值的节点，就不做任何处理。你应该保证处理之后的树仍是二叉查找树。样例给出如下二叉查找树： 5 / \ 3 6 / \2 4删除节点3之后，你可以返回： 5 / ...

2018-07-15 16:06:48 337

原创【数据结构】红黑树小结

红黑树是一种二叉搜索树。性质一颗红黑树满足以下五个红黑性质：每个结点或者是红色或者是黑色。根结点是黑色的。每个叶结点是黑色的。（这个叶节点是树尾端的黑色节点nil）若一个结点是红色的，它的两个子结点必须是黑色的。对于任意一个结点，从该结点到它的每一个后代叶结点的简单路径上，都包含相同数目的黑色结点。一棵有n个内部结点的红黑树，它的高度至多为2lg(n+1)。也就是说，在一棵...

2018-07-14 16:14:59 299

原创【设计模式】策略模式

定义策略模式定义了一系列的算法，并将每一个算法封装起来，而且使他们可以相互替换，让算法独立于使用它的客户而独立变化UML适用场景针对同一类型问题的多种处理方式，仅仅是具体行为有差别时；需要安全地封装多种同一类型的操作时；出现同一抽象类有多个子类，而又需要使用 if-else 或者 switch-case 来选择具体子类时。代码示例//策略类class oper...

2018-07-12 15:13:55 175

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

定义简单工厂模式(Simple Factory Pattern)：又称为静态工厂方法(Static Factory Method)模式，它属于类创建型模式。在简单工厂模式中，可以根据参数的不同返回不同类的实例。简单工厂模式专门定义一个类来负责创建其他类的实例，被创建的实例通常都具有共同的父类优点工厂类含有必要的判断逻辑，可以决定在什么时候创建哪一个产品类的实例，客户端可以免除直接创建...

2018-07-12 14:58:10 207

原创【算法】字符串大整数相乘

题目描述：给定两个以字符串形式存储的大整数，要求以字符串形式输出相乘后的结果。思路：模拟计算乘法时列竖式的过程，对于两个字符串s1和s2，让s2的每一位和s1整体相乘，求得一组中间值，然后对中间值做移位操作，最后将移位后的所有中间值相加即可求得最终结果。问题的关键在于实现两个函数，用于计算两个字符串相加以及字符串和单个字符相乘的结果。//计算两个字符串相加string mya...

2018-07-09 00:35:27 1563

原创强/弱类型、动/静态类型语言辨析

这是知乎上轮子哥的解释：强类型：偏向于不容忍隐式类型转换。弱类型：偏向于容忍隐式类型转换。譬如说C语言的int可以变成double静态类型：编译的时候就知道每一个变量的类型，因为类型错误而不能做的事情是语法错误。动态类型：编译的时候不知道每一个变量的类型，因为类型错误而不能做的事情是运行时错误再配上这张图 ...

2018-07-07 14:23:58 206

转载【C++】trivial和non-trivial构造函数及POD类型

今天看书看到侯捷的《STL源码剖析》里提到trivial和non-trivial及POD类型，查了些资料理解了一下。trivial意思是无意义，这个trivial和non-trivial是对类的四种函数来说的：构造函数(ctor) 复制构造函数(copy) 赋值函数(assignment) 析构函数(dtor) 如果至少满足下面3条里的一条：显式(explict)定...

2018-07-06 16:37:12 1287

原创【算法】桶排序和基数排序

桶排序假设我们要对n个整数排序，而且这n个数的大小在区间[0,m]之内。那么我们可以设置m+1个”桶”来表示区间内的m+1个数，用数组bucket[m+1]表示。然后遍历n个待排数据，将每个数字放入到它对应的”桶”中。最后我们按照”桶号”递增的顺序将n个数字一次从”桶”中取出，那么取出的数字序列就是排序后的序列了。桶排序使用了hash的思想，将n个数散列在了m个”桶”中，然后利用桶固有的顺...

2018-07-06 13:37:26 389

原创【C++】如何使用基类指针遍历派生类对象数组

今天在一个群里看到一位老哥提出了这样一个问题。1. 基类指针自增起初我认为这是不可能实现的，确实，通过自增基类指针的方式是不能遍历派生类数组的。因为在编译时编译器不知道基类指针所指的对象是基类对象还是派生类对象，所以基类指针自增的移动距离只能是基类对象的长度，但是基类对象和派生类对象的长度往往是不同的，那么如果使用基类指针自增的方式遍历派生类数组就会产生未定义的行为。2.使用虚函数...

2018-07-04 17:06:13 4119

原创 C++中const限定符小结

const限定符const限定符用于定义一个常量const对象在定义时必须被初始化默认情况下，const对象仅在文件内有效。如果在不同的文件下出现了同名的const变量，则视作在文件中单独定义的独立变量。如果想在不同的文件中使用同一个从上图变量，则需要在声明和定义前都添加extern关键字。 //file1.cpp中定义一个const变量 extern const int A = 3...

2018-06-06 14:26:58 243

原创【lintcode】子集问题

这里的子集问题是指给定一个列表求它的所有不重复子集的问题。这个问题分为两类：一类是所给列表包含重复元素，另一类是所给列表不含重复元素。分别对应lintcode中17和18题。1.列表不含重复元素的子集这里使用深度优先搜索的思想，递归求解。代码class Solution {public: /** * @param nums: A set of numbers...

2018-05-24 10:50:17 363

原创 epoll中监听套接字的触发模式

我们知道epoll有两种触发模式：水平触发(LT)和边缘触发(ET)LT模式若数据可读，epoll返回可读事件若开发者没有把数据完全读完，epoll会不断通知数据可读，直到数据全部被读取。若socket可写，epoll返回可写事件，而且是只要socket发送缓冲区未满，就一直通知可写事件。优点是对于read操作比较简单，只要有read事件就读，读多读少都可以。 E...

2018-05-21 19:26:21 1898

原创 swap的三种实现及区别

我们在实现一个swap函数或者宏定义时，往往会使用以下几种方式：使用辅助变量使用加减法使用位运算我以前使用swap时，从来没有对这三种方法做过区分，认为它们的效果完全一致，即使有区别也只在于使用加减法可能会造成溢出。然而除此之外，它们还是有区别的：那就是当要被交换的两个对象为同一个变量时，后两种方法会产生错误。#define swap1(a,b) {int t = a; a =...

2018-05-02 23:50:25 2158

原创 C语言do...while(0)使用小结

引言在一些C语言程序中我们会看到do...while(0);这样的语句，这样的用法貌似画蛇添足，实际却颇有妙用。单独来看，do…while(0)和顺序执行`...部分的代码的效果并无二致，然而在如下两种情况下的效果却十分巧妙。一.宏定义中实现局部作用域我们知道宏定义只是做一个标识符和字符串的替换，尽管宏定义的形式可以类似于函数，但是它实际并不具备与函数类似的局部作用域。当然了，我们可以...

2018-05-02 16:17:08 11741 2

原创使用有限状态自动机构造HTTP报文解析器

首先看一下HTTP请求报文的格式不同于TCP或者IP报文的首部，由于HTTP的报文首部是文本形式的，我们就无法按字节来提取HTTP首部中的字段。所以要对HTTP请求报文做解析，目的是从文本中提取各字段的值。从上图可以看出，HTTP请求报文由首部和正文两部分组成，他们由一个空行隔开，在这里我们仅对报文首部做解析。首部又有请求行和请求头两部分。从图中可以看出报文的各字段都由一些特殊的字...

2018-04-30 21:42:56 2033

原创 C语言的逻辑右移和算术右移

首先说明一下这两个概念：逻辑右移：右移后左边添加0 算术右移：右移后添加的位与原数的符号位相同在C语言中，对于移位操作执行的是逻辑左移和算术右移，不过对于无符号类型，所有的移位操作都是逻辑的。所以要相对一个有符号数执行逻辑右移，那么可以先将它强制类型转换为无符号类型。如下int mian(){ int n = 0xfffffffe; int m = (u...

2018-03-11 15:08:31 22925 2

转载 Linux--线程池与进程池及线程池的简单实现

转载地址：http://blog.csdn.net/sayhello_world/article/details/72829329池由于服务器的硬件资源“充裕”，那么提高服务器性能的一个很直接的方法就是以空间换时间，即“浪费”服务器的硬件资源，以换取其运行效率。这就是池的概念。池是一组资源的集合，这组资源在服务器启动之初就被创建并初始化，这称为静态资源分配。当服务器进入正式运行阶段...

2018-03-11 10:56:43 289

原创背包问题—01背包、完全背包

01背包问题题目有m件物品和一个容量为V 的背包。放入第i 件物品占用的体积是Vi，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。思路这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。所以对于第i件物品，可以转化成与前i-1个物品相关的两个子问题：如果放入第i个物品，那么当前最大的价值f(i,V)就等于将前i-1个物品放入容量为(V-Vi)的背包中...

2018-03-09 21:28:08 311

原创【Linux】存储映射I/O—mmap

存储映射I/O能将一个磁盘文件映射到存储空间中的一个缓冲区上，于是可以用对缓冲区的读写代替对磁盘文件的读写，这样就可以在不使用read和write的情况下执行I/O。为了实现这种功能，应首先将一个给定的文件映射到一个存储区域中，这由mmap函数实现。注：子进程能够通过fork继承父进程的存储映射区。mmap函数#include <sys/mman.h>void *...

2018-03-09 20:41:13 240

原创【Linux】I/O多路复用—poll

poll类似于select，但是接口有所不同。原型#include <poll.h>int poll(struct pollfd fdarray[], nfds_t nfds, int timeout);返回值：准备就绪的描述符数；若超时，返回0；若出错，返回-1与select不同，poll不是构造三个描述符集，而是使用一个pollfd结构的数组，每个元素指定一个描...

2018-03-09 17:24:50 141

原创【Linux】I/O多路复用—select和pselect

select函数#include <sys/select.h>int select(int maxfdp1, fd_set *restrict readfds, fd_set *restrict writefds, fd_set *restrict exceptfds, struct timeval *restrict tvptr); 返回...

2018-03-09 10:47:09 899

原创【Linux】线程和信号

相比于进程中的信号处理，在线程中更加复杂，线程中的信号处理有如下特点：每个线程都有自己的信号屏蔽字，但是信号的处理是进程中所有线程共享的。这意味着单个线程可以阻止某个信号，但是当某个线程修改了一个信号的处理行为，那么所有线程都会共享这个改变。进程中的信号是递送到单个线程的。如果一个信号和硬件故障相关，那么该信号一般会被发送到引起该事件的线程中去，而其他的信号会被发送到任意的线程中。...

2018-03-07 14:21:46 403

原创【Linux】线程特定数据

概述线程特定数据（线程私有数据）是存储和查询某个特定线程相关数据的一种机制，使用这种机制是因为我们希望每个线程可以访问它自己单独的数据副本，而不需要担心与其他线程的访问同步问题。线程的好处就在于促进了进程中数据和属性的共享，那么设计线程私有数据的用意是什么呢？有如下两点原因：有时候需要维护基于每个线程的数据，而建立一个全局数组并通过线程号作为索引这种方式并不方便，并且对数组的访问无法...

2018-03-06 20:56:20 212

原创【Linux】互斥量属性

1.属性类型：pthread_mutexattr_t该类型是一个结构，其中存放了互斥量的各属性字段。在对互斥量初始化时，可以使用PTHREAD_MUTEX_INITIALIZER常量初始化，或在互斥量的初始化函数中的属性参数传递空指针。这样得到互斥量为默认属性。2.初始化与反始化对于非默认属性，可使用如下的函数对pthread_mutexattr_t结构进行初始化和反初始化。初始化后的...

2018-03-01 19:23:51 586

原创【Linux】线程同步—屏障（实现多线程排序算法）

屏障与互斥量、读写锁等不同，它不是用来保护临界区的，而是与条件变量类似，是一种线程之间的同步机制。屏障允许每个线程等待，直到所有合作线程都到达某一点，然后从该点继续执行。pthread_join就是一种屏障，它允许线程等待直到另一个线程退出。#include <pthread.h>pthread_barrier_t ; //屏障数据类型int pthread_barrie...

2018-02-27 21:47:52 1312

条件变量是pthread提供的另一种线程间同步机制。互斥量用于允许或阻塞对临界区的访问，而条件变量则允许线程由于一些未达到的条件而阻塞。互斥量和条件变量往往是一起使用的。考虑一个生产者—消费者问题，一个线程将数据写入缓冲区，另一个线程将数据从缓冲区取出。如果生产者发现缓冲区中没有空槽可以使用，它将不得不阻塞直到由空槽可用。生产者可以使用互斥量来对缓冲区进行原子性的检查，不用担心受其他线程影响。...

2018-02-26 17:23:09 144

原创【Linux】线程同步—读写锁

读写锁与互斥量类似，不过读写锁允许更高的并行性。互斥量只有锁住和不加锁两种状态，且一次只有一个线程可以对其加锁。而读写锁有三种状态：读模式加锁状态，写模式加锁状态，不加锁状态。读写锁具有如下特点：一次只有一个线程可以占有写模式的读写锁，但多个线程可以同时占有读模式的读写锁。在写加锁状态下，在这个锁被解锁之前，所有试图对这个锁加锁的线程都会被阻塞。在读加锁状态下，所有试图以读模式对它加锁的...

2018-02-24 16:06:06 164

原创【Linux】线程同步—互斥量

在讲互斥量之前，先明确下面两个概念：竞争条件：两个或多个进程（或线程）读写某些共享数据，最终结果取决于进程（或线程）运行的精确时序，被称为竞争条件。临界区：对共享内存进行访问的程序片段。通过适当安排使得两个进程（或线程）不可能同时处于临界区，就能够避免竞争条件。那么如何才能避免竞争条件呢？如何才能使两个线程不能同时访问共享资源呢？关键是要互斥，即当一个线程在使用一个共享资源时，其...

2018-02-23 11:48:44 185

原创 top k 问题的几种解决方法

top k问题是指给定一组数量为n的数，从中找出前k大的数或第k大的数(k <= n)。由于只要能找出前k大的数，即可以得到第k大的数。所以下面先介绍解决前k大数问题的几种思路：1.部分排序由于我们只需要找到数组nums的前k大的数，所以不需要对整个数据进行排序，只需要保持前k大的数有序即可。所以我们可以维护一个大小为k的数组tk：首先将数组nums的前k个元素放入数组tk...

2018-02-22 17:30:53 2976 1

原创【Linux】线程的终止

线程的终止分为两种情况，一是随着它所属进程的终止而终止，二是仅有单个线程自己终止。对于第一种进程终止的情况：如果进程中的任意线程调用了exit、_Exit、或_exit，那么整个进程就会终止，当然属于这个进程的所有线程也会相应终止。如果线程收到一个信号，这个信号的默认动作是终止进程，那么整个进程会被终止。对于第二种单个线程终止的情况，线程可以通过以下三种方式退出，而不会终止整个进...

2018-02-18 18:11:02 232

原创 HTTP概述

1.HTTPHTTP全名超文本传输协议，是一个应用层协议，主要用于万维网中的信息传输。它被广泛地用于在web浏览器和web服务器之间传输文本、图像、视频、音频等。2.web客户端和服务器Web内容都是存储在web服务器上的，web服务器使用HTTP协议，所以web服务器也被称作HTTP服务器。HTTP客服端通过HTTP协议向HTTP服务器发送请求报文，HTTP根据不同的请求返回相应...

2018-02-17 00:23:56 342

原创【Linux】线程的创建

线程ID类似于进程ID，线程ID用于表示线程，使用类型pthread_t来表示。该类型在不同的系统中实现的方式也不相同，Linux中使用无符号长整型，而在其他实现中可能使用结构指针，所以考虑到可移植性，对于该类型尽量不要直接当整型来处理。pthread_self函数原型：pthread_t pthread_self(void);功能：返回调用线程的线程ID线程的创建创...

2018-02-13 23:00:01 160

原创 Linux下C程序的编译和链接

这篇博文是在读了《CSAPP》中的链接部分后做的总结和摘录。linux编译过程命令：gcc -o prog main.c 过程： main.c —>预处理器(cpp)—>main.i —>编译器(ccl) —>main.s —>汇编器(as)—>main.o —>链接器(ld)—>prog main.i — ASCII码中间文件 ...

2018-02-13 16:34:10 897

原创 linux下pthread的编译

今天在linux下写一个多线程程序时，在.c 文件中包含了头文件< pthread.h> ，但是编译时却报错：对‘pthread_create’未定义的引用上网查了下，原来pthread库不是linux默认的库，所以在编译时要手动链接，做法如下： gcc mian.c -lpthread由于我是在CLion下写的代码，所以要想让CLion支持自动链接pthread库，需要...

2018-02-12 18:23:13 6245

原创 C语言static关键字小结

在C语言中，static关键字用于普通变量和函数，它用于定义一个静态的变量或函数。下面对于它们各自的特点进行一下小结：静态全局变量在函数外部定义的变量前加上关键字static，这样定义的变量就是一个静态全局变量，有如下特点：存储于程序的全局数据区，作用范围为整个文件，与全局变量不同的是：静态全局变量只作用于本文件，对于其他文件是不可见的。例如，在一个文件中用如下语句定义一个全...

2018-02-08 15:19:46 260

原创【lintcode】图是否是树

给出 n 个节点，标号分别从 0 到 n - 1 并且给出一个无向边的列表 (给出每条边的两个顶点), 写一个函数去判断这张｀无向｀图是否是一棵树注意事项你可以假设我们不会给出重复的边在边的列表当中. 无向边　[0, 1] 和 [1, 0]　是同一条边，因此他们不会同时出现在我们给你的边的列表当中。样例给出n = 5 并且 edges = [[0, 1], [0, 2], [0,

2018-02-04 21:35:52 461

原创【算法】并查集—带路径压缩的按秩合并法

读了《算法导论》的21章：用于不相交集合的数据结构后在这里对并查集算法做一个小结。对于动态集合的表示有多种方法，例如链表和有根树。不论是哪种表示，我们都用一个代表来标识一个集合，这个代表就是该集合中的某个成员。并查集算法用于对不相交集合的查找与合并，主要是以下三种操作：MAKE_SET(X)：创建一个新的集合，它包含唯一的成员x（因而为代表）。UNION(x,y)：将分别包含x和...

2018-02-04 21:04:41 6125 2

原创一个简单的UDP回射程序—总结UDP程序的基本结构

UDP 是面向数据报的无连接的传输协议，这与面向字节流的TCP协议十分不同。所以使用socket编写的UDP程序与TCP程序也是有着本质上的区别的。下面给出一个典型的UDP客户/服务程序的函数调用过程：服务器： socket() –> bind() –> recvfrom() –> sendto() 客户： socket() –> sendto() –> recvfrom() –> c

2018-02-03 18:34:38 1340

原创 C/C++中指针的引用小结

我们知道C语言中，对于函数参数的传指针操作本质上仍然是一个传值过程，只是将实参指针的值传递给了函数中的一个临时变量，实质上我们传入函数的只是一块内存的地址，而非指针本身。所以如果在函数中改变形参指针所指向的地址，实参指针的指向是不会被改变的。如下图代码所示void func(int *p){ int *n = new int; *n = 3; p = n;}

2018-01-30 12:56:16 155

空空如也

空空如也