红黑树

昨天下班在地铁上居然听到有人在讨论红黑树,这块虽然一直在用,但早已忘了具体的实现细节,利用周天上午的时间,学习红黑树的知识。

以下红黑树的基本概念来自维基百科红黑树,详细介绍请阅读该文章。

另一篇非常不错的文章:红黑树的变色与旋转

可以拿来直接工程中使用的代码:libtree-github

红黑树(英语:Red–black tree)是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。

红黑树是每个节点都带有颜色属性的二叉查找树,颜色为红色或黑色。在二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求:

性质

1.......

TLPI-Chapter 29线程:介绍

一个进程可以包含多个线程,多个线程共享同一份全局内存区域,包括初始化数据段(initialized data)、未初始化数据段(uninitialized data)以及堆内存段(heap segment).

对于某些应用而言,线程要优于进程:

1.进程间信息难以共享,必须使用进程间通信IPC方式,在进程间进行消息通信。

2.使用fork创建进程带价较高。

线程解决了上面两个问题:

1.线程之间能够方便、快速共享信息,需要使用线程同步技术(互斥锁 条件变量)

2.创建线程比创建进程快(实现线程是通过clone()系统调用)

文件IO相关的几个面试题

如下代码输出什么?

#include <stdio.h>

#include <stdlib.h>

#include <unistd.h>

int main()

{

fprintf(stderr, "Hello ");

fprintf(stdout, "It's a small ");

fprintf(stderr, "World\n");

fprintf(stdout, "place\n");

return 0;

}

运行结果:

[root systemProgramming]#./printf

Hello World

It's a s......

[LeetCode C++实现]62. Unique Paths

看到题目知道需要用到DFS,自己写了一版存在重复计算的bug,代码如下:

class Solution {

public:

int uniquePaths(int m, int n) {

int res = 0;

help(0,0,m,n,res);

return res;

}

void help(int start_m,int start_n,int m,int n,int &res)

{

if(start_m >= m-1 && start_n >= n-1)

return;

if(start_m < m -1)

{

res++;

hel......

TLPI-Chapter 32 线程:线程取消

在通常情况下,程序中的多个线程并发执行,每个线程各司其职,直至其决意退出,随即会调用函数pthread_exit()或者从线程启动函数中返回。

有时候,需要将一个线程取消,亦即向线程发送一个请求,要求其立即退出。比如一组线程正在执行一个运算,一旦某个线程检测到错误发生,需要其他线程退出,取消线程的功能这时就能派上用场。

另一种情况,一个图形用户界面(GUI)驱动的应用程序可能会提供一个“取消”按钮,以便用户可以终止后台某一线程正在执行的任务。这种情况下,主线程(控制图形用户界面)需要请求后台线程退出。

本文记录学习TLPI一书第32章线程:线程取消内容,讨论POSIX线程的取消机制。

......

日常开发笔记总结(一)

记录日常开发中的一些常用技巧,有的可能比较小,不适合专门写一篇文章,那么可以写在笔记总结系列里面。

scp命令用法发送目录到服务器

比如我想把一个目录下的所有文件发送到服务器中,以C-Thead-Pool为例:

bogon:github coder52$ scp -r C-Thread-Pool/ root@10.211.55.49:~

root@10.211.55.49's password:

LICENSE 100% 1090 592.0KB/s 00:00

thpool.h ......

strace命令使用实例

strace命令

strace是Linux上的一个很好用的工具,它可以用来输出程序在运行过程中发生的系统调用以及收到的信号的相关信息,因此在调试和诊断问题时有很大的帮助,特别是在程序没有源码,或是在前期做一些粗略的分析时。strace命令格式如下:

strace [options] command [args]

查看帮助

strace -h

查看版本信息

strace -V

基本使用

举个例子:

[root cprogs2]#strace sleep 300

execve("/bin/sleep", ["sleep", "300"], 0x7ffc2a8576d8......

线程池-C语言实现

最近可能会用到C实现的线程池,在github fork了一个项目,学习其代码,修改发现的问题,本文记录学习中遇到的问题和解决方法。

我的github仓库地址C-Thread-Poll

原作者仓库地址C-Thread-Poll

查看进程创建的线程

thpool.c文件函数thread_do函数使用了函数:

prctl(PR_SET_NAME, thread_name);

设置线程的名字,thread-pool-%d,如何查看某个进程所创建的线程呢?

[root pthread_detach]#ps -T -p $(pidof /root/C-Thread-Pool/exam......

Linux C写中文配置

需要在linux C/C++程序中生成一个文件,文件中包含中文字符,可是上库到代码中编译运行,发现生成的文件乱码,相同的代码,自己编写的demo生成的文件显示却正常。

为什么会出现相同代码,运行结果不同的问题呢?

原因是由于项目文件中使用的是ISO 8859-1编码,而我自己编写的demo使用的是utf-8编码,而ISO 8859-1编码无法识别中文字符,因此导致写入到文件乱码。

我们使用如下代码验证:

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <......

Linux进程间资源共享

周末整理笔记,发现已经有接近一年的笔记等待整理,主要是Linux进程间资源共享,包括变量、锁、函数,很多笔记中没有记录引用链接,这是个不好的习惯。

Linux内核中是不存在线程的概念的,一切可执行单元都是进程。所谓多线程,其实是一组可以共享内存的进程,即“轻量级进程”。所以应该只要实现内存共享,就能让进程之间互相访问。同一个进程的多个线程天然具有上面的特性。

变量共享

master.c

#include <time.h>

#include <stdio.h>

#include <stdlib.h>

#include <assert.......