freertos 源码详解 目录简单的任务函数void ATaskFunction( void *pvParameters ) { int iVariableExample = 0; /* 任务通常实现在一个死循环中。 */ for( ;; ) { /* 完成任务功能的代码将放在这里。 */ } /* 如果任务的具体实现会跳出上面的死循环，则此任务必须在函数运行完之前删除。传入NULL参数表示删除的是当前任务 */ vTaskDelete( NULL ); }创建任务函数/* 函数原型 */ portBASE_TYPE xTaskCreate( pdTASK_CODE pvTaskCode, const signed portCHAR * const pcName, unsigned portSHORT usStackDepth, void *pvParameters, unsigned portBASE_TYPE uxPriority, xTaskHandle *pxCreatedTask ); /* 函数示例 */ static TaskHandle_t myTaskHandler = NULL; xTaskCreate(ATaskFunction, "myTask", 512, NULL, configMAX_PRIORITIES - 4, &myTaskHandler);删除任务函数/* 函数原型 */ void vTaskDelete( xTaskHandle pxTaskToDelete );任务优先级低优先级号表示任务的优先级低，优先级号0表示最低优先级。有效的优先级号范围从0到(configMAX_PRIORITES – 1)。函数说明vTaskPrioritySet()可以动态的更改任务优先级uxTaskPriorityGet()获取任务优先级uxTaskPriorityGetFromISR()在ISR函数中获取任务优先级延时函数void vTaskDelay( portTickType xTicksToDelay );xTicksToDelay 表示延时多少个tick \该函数会把task切出到阻塞态精确延时函数void vTaskDelayUntil( portTickType * pxPreviousWakeTime, portTickType xTimeIncrement );调用此函数的任务解除阻塞的时间是绝对时刻，比起vTaskDelay()延时时间更精确使用方法：void vTaskFunction( void *pvParameters ) { char *pcTaskName; portTickType xLastWakeTime; pcTaskName = ( char * ) pvParameters; /* 变量xLastWakeTime需要被初始化为当前心跳计数值。说明一下，这是该变量唯一一次被显式赋值。之后， xLastWakeTime将在函数vTaskDelayUntil()中自动更新。 */ xLastWakeTime = xTaskGetTickCount(); for( ;; ) { vPrintString( pcTaskName ); /* 本任务将精确的以250毫秒为周期执行。同vTaskDelay()函数一样，时间值是以心跳周期为单位的， 可以使用常量portTICK_RATE_MS将毫秒转换为心跳周期。变量xLastWakeTime会在 vTaskDelayUntil()中自动更新，因此不需要应用程序进行显示更新。 */ vTaskDelayUntil( &xLastWakeTime, ( 250 / portTICK_RATE_MS ) ); } }空闲任务调用vTaskStartScheduler()时，调度器会自动创建一个空闲任务 \空闲任务拥有最低优先级(优先级0) \空闲任务是一个非常短小的循环具体代码在vTaskStartScheduler()中可以看到：void vTaskStartScheduler( void ) { BaseType_t xReturn; /* Add the idle task at the lowest priority. */ #if ( INCLUDE_xTaskGetIdleTaskHandle == 1 ) { /* Create the idle task, storing its handle in xIdleTaskHandle so it can be returned by the xTaskGetIdleTaskHandle() function. */ xReturn = xTaskCreate( prvIdleTask, "IDLE", tskIDLE_STACK_SIZE, ( void * ) NULL, ( tskIDLE_PRIORITY | portPRIVILEGE_BIT ), &xIdleTaskHandle ); /*lint !e961 MISRA exception, justified as it is not a redundant explicit cast to all supported compilers. */ } #else { /* Create the idle task without storing its handle. */ xReturn = xTaskCreate( prvIdleTask, "IDLE", tskIDLE_STACK_SIZE, ( void * ) NULL, ( tskIDLE_PRIORITY | portPRIVILEGE_BIT ), NULL ); /*lint !e961 MISRA exception, justified as it is not a redundant explicit cast to all supported compilers. */ } #endif /* INCLUDE_xTaskGetIdleTaskHandle */ ... }队列创建队列xQueueHandle xQueueCreate( unsigned portBASE_TYPE uxQueueLength,unsigned portBASE_TYPE uxItemSize );写入到队列首portBASE_TYPE xQueueSendToFront( xQueueHandle xQueue, const void * pvItemToQueue, portTickType xTicksToWait );写入到队列尾portBASE_TYPE xQueueSendToBack( xQueueHandle xQueue, const void * pvItemToQueue, portTickType xTicksToWait );发送队列协程--croutine.c系统运行过程协程--croutine.c4个链表：readyList pendingList delayList（2个）链表设计--List.c系统调度任务管理内存管理优先级反转有优先级为A、B和C三个任务，优先级A>B>C，任务A，B处于挂起状态，等待某一事件发生，任务C正在运行，此时任务C开始使用某一共享资源S。在使用中，任务A等待事件到来，任务A转为就绪态，因为它比任务C优先级高，所以立即执行。当任务A要使用共享资源S时，由于其正在被任务C使用，因此任务A被挂起，任务C开始运行。如果此时任务B等待事件到来，则任务B转为就绪态。由于任务B优先级比任务C高，因此任务B开始运行，直到其运行完毕，任务C才开始运行。直到任务C释放共享资源S后，任务A才得以执行。在这种情况下，优先级发生了翻转，任务B先于任务A运行。优先级继承freertos 使用优先级继承来解决优先级反转问题当任务A 申请共享资源S 时， 如果S正在被任务C 使用，通过比较任务C 与自身的优先级，如发现任务C 的优先级小于自身的优先级， 则将任务C的优先级提升到自身的优先级， 任务C 释放资源S 后，再恢复任务C 的原优先级。freertos HOOK函数vApplicationIdleHook() idle的hook函数vApplicationTickHook() 系统tick的hook函数vApplicationMallocFailedHook() malloc失败的hook函数vApplicationStackOverflowHook() 栈溢出的hook函数vApplicationDaemonTaskStartupHook() vTaskStartScheduler()函数第一次执行的时候调用。freertos栈溢出检测的2种方法第一种 每次调度都检查一下任务的当前栈有没有超过任务的栈区域。第二种 每个任务栈最下面会有16个字节是特定的内容，每次调度的时候如果发现这16个字节不正常了，就说明有谁踩到了这个栈。

linux知识点 目录关键命令说明系统关机命令linux查看文本的指令mountdmesggrepfindlsusblsoflinux软件开发知识点linux进程间通讯方式内存申请函数gcc编译过程文件系统硬链接和软连接linux内核子系统进程几种状态文件系统组成linux文件类型linux常用的系统调用函数fork函数僵尸进程常见文件说明/proc目录说明fopen参数说明linux驱动开发知识点makefileshell关键命令说明系统关机命令linux查看文本的指令mountdmesggrepfindlsusblsof系统关机命令指令说明shutdown命令安全地将系统关机。halt就是调用shutdown -h。reboot工作过程差不多跟halt一样﹐不过它是引发主机重启poweroff就是halt的软链接而已init所有进程的祖先﹐它的进程号始终为1﹐init 0为关机﹐init1为重启。linux查看文本的指令 cat tac sed head tail more less nl tac： cat的反向指令，从最后一行倒序显示全部内容head： 只显示头几行tail： 只显示最后几行 tail -f 可以实时显示log文件的更新nl： 类似于cat -n，显示时输出行号mount命令格式：mount [-t vfstype] [-o options] device dir挂载nfsmount -t nfs 192.168.0.1:/tmp /mnt/nfs dmesgcat /var/log/messagesgrep选项-c：只输出匹配行的计数。 -C：匹配的上下文分别显示[number]行。 -I：不区分大小写(只适用于单字符)。 -i：不区分大小写。 -h：查询多文件时不显示文件名。 -l：查询多文件时只输出包含匹配字符的文件名。 -L：列出不匹配的文件名。 -n：显示匹配行及 行号。 -s：不显示不存在或无匹配文本的错误信息。 -v：显示不包含匹配文本的所有行。 -w：只匹配整个单词。 -E：扩展的正则表达式 -R：递归搜寻 --exclude=FILE：跳过FILE正则表达式主要参数：\：忽略正则表达式中特殊字符的原有含义。 ^：匹配正则表达式的开始行。 $：匹配正则表达式的结束行。 \<：从匹配正则表达式的行开始。 \>：到匹配正则表达式的行结束。 []：单个字符，如[A]即A符合要求 。 [-]：范围，如[A-Z]，即A、B、C一直到Z都符合要求 。 .：所有的单个字符。 *：有字符，长度可以为0。 经典使用方法#所有以d开头的文件，包含test的匹配行 grep "test" d* #包含test或者zephyr 不区分大小写 显示行号 扩展正则表达式 grep -inE "test|zephyr" d* #包含test和zephyr 不区分大小写 显示行号 扩展正则表达式 grep -in "test" d* | grep 'zephyr'主要参数：－c：只输出匹配行的计数。 －I：不区分大小写(只适用于单字符)。 －h：查询多文件时不显示文件名。 －l：查询多文件时只输出包含匹配字符的文件名。 －L：列出不匹配的文件名 －n：显示匹配行及行号。 －s：不显示不存在或无匹配文本的错误信息。 －v：显示不包含匹配文本的所有行。 －R：递归搜寻 －d skip：不递归搜寻 －w：匹配整个单词正则表达式主要参数：\：忽略正则表达式中特殊字符的原有含义。 ^：匹配正则表达式的开始行。 $：匹配正则表达式的结束行。 \<：从匹配正则表达式的行开始。 \>：到匹配正则表达式的行结束。 []：单个字符，如[A]即A符合要求 。 [-]：范围，如[A-Z]，即A、B、C一直到Z都符合要求 。 .：所有的单个字符。 *：有字符，长度可以为0。 grep 'test' d* 显示以d开头的文件中包含的test行grep 'test' aa bb cc 查找文件aa bb cc 中匹配的test行grep 'test'|'hello' files 匹配test或者hellogrep '\<man' files 匹配manic 和man 不匹配batmangrep '\<man\>' 只匹配man 不匹配batman和manicgrep '^man' files 匹配的字符行首grep '$man' files 匹配的字符串仔行尾find用法find [-path ..] [expression]选项-name 按照文件名 -iname 按照文件名 忽略大小写 -perm 按照文件权限 -user 按照文件拥有者 -group 按照文件所属的组 -mtime -n +n 按照文件的更改时间来查找文件， -n：n天以内，+n：n天以前 -type 查找某一类型：文件类型有：普通文件(f)，目录(d)，字符设备文件(c)，块设备文件(b)，符号链接文件(l)，套接字文件(s)，管道文件(p) -size n 查找文件长度为n块（一块等于512字节）的文件，带有c时表示文件长度以字节计。 -mount 不跨越文件系统 -follow 遇到符号链接文件，就跟踪至链接所指向的文件 -path 匹配文件路径或者文件 -exec 执行后续命令操作 -a and 与操作 -o or 或操作 -not not 非操作经典使用方法#查找/run中所有的socket文件 find /run -type s #搜索/dev中所有包含tty的文件 find /dev -name "*tty*" #搜索/dev中大小大于10字节，名称包含bus的文件 find /dev -size +10c -name "*bus*" #或操作，搜索debug开头的文件或者.rst的文件 find -name 'debug*' -o -name '*.rst' #与操作，搜索debug开头的文件同时是.rst的文件 find -name 'debug*' -a -name '*.rst' #找出文件大小大于10000块的文件，并复制到当前目录 find -size +100000 -exec cp {} . \;高级使用方法查询所有mk文件中的date文本find ./build/ -name "*.mk" -print -exec grep -rwn "date" --color=auto {} \;lsusb显示系统中以及连接到系统的USB总线信息的工具。$ lsusb Bus 001 Device 001: ID 1d6b:0002 Linux Foundation 2.0 root hub Bus 002 Device 001: ID 1d6b:0002 Linux Foundation 2.0 root hub Bus 003 Device 001: ID 1d6b:0001 Linux Foundation 1.1 root hub Bus 004 Device 001: ID 1d6b:0001 Linux Foundation 1.1 root hub Bus 005 Device 001: ID 1d6b:0001 Linux Foundation 1.1 root hub Bus 006 Device 001: ID 1d6b:0001 Linux Foundation 1.1 root hub Bus 007 Device 001: ID 1d6b:0001 Linux Foundation 1.1 root hub Bus 008 Device 001: ID 1d6b:0001 Linux Foundation 1.1 root hub Bus 002 Device 003: ID 17ef:4811 Lenovo Integrated Webcam [R5U877] Bus 008 Device 002: ID 0a5c:217f Broadcom Corp. Bluetooth ControllerBus 008 : 指明设备连接到哪（哪条总线）Device 002 : 表明这是连接到总线上的第二台设备ID : 设备的IDBroadcom Corp. Bluetooth Controller :生产商名字和设备名列出USB详细信息$ lsusb -v列出有多少USB设备$ find /dev/bus打印特定设备的详细信息$ lsusb -D /dev/bus/usb/008/002lsof列出当前系统打开文件的工具$ sudo lsof COMMAND PID USER FD TYPE DEVICE SIZE NODE NAME init 1 root cwd DIR 3,3 1024 2 / init 1 root rtd DIR 3,3 1024 2 / init 1 root txt REG 3,3 38432 1763452 /sbin/init init 1 root mem REG 3,3 106114 1091620 /lib/libdl-2.6.so init 1 root mem REG 3,3 7560696 1091614 /lib/libc-2.6.so init 1 root mem REG 3,3 79460 1091669 /lib/libselinux.so.1 init 1 root mem REG 3,3 223280 1091668 /lib/libsepol.so.1 init 1 root mem REG 3,3 564136 1091607 /lib/ld-2.6.so init 1 root 10u FIFO 0,15 1309 /dev/initctl COMMAND 进程的名称 PID 进程标识符 USER 进程所有者 FD 文件描述符 应用程序通过文件描述符识别该文件。如cwd、txt、mem等 TYPE 文件类型 REG(文件) DIR(目录) CHR(字符) BLK(块设备) FIFO(管道) UNIX(UNIX 域套接字) IPv4(IP套接字) DEVICE 指定磁盘的名称 SIZE 文件大小 NODE 文件inode 每个文件都有一个唯一的inode NAME 文件名称 参数列表lsof filename 显示打开指定文件的所有进程 lsof -a 表示两个参数都必须满足时才显示结果 lsof -c string 显示COMMAND列中包含指定字符的进程所有打开的文件 lsof -u username 显示所属user进程打开的文件 lsof -g gid 显示归属gid的进程情况 lsof +d /DIR/ 显示目录下被进程打开的文件 lsof +D /DIR/ 同上，但是会搜索目录下的所有目录，时间相对较长 lsof -d FD 显示指定文件描述符的进程 lsof -n 不将IP转换为hostname，缺省是不加上-n参数 lsof -i 用以显示符合条件的进程情况 lsof -i[46] [protocol][@hostname|hostaddr][:service|port] 46 --> IPv4 or IPv6 protocol --> TCP or UDP hostname --> Internet host name hostaddr --> IPv4地址 service --> /etc/service中的 service name (可以不只一个) port --> 端口号 (可以不只一个)查找应用程序打开的文件的名称和数目#显示打开指定文件的所有进程 $ lsof filename #例如:打开所有使用/dev/urandom的进程 $ lsof /dev/urandom #查看22端口现在运行的情况 $ lsof -i :22 #查看所属xiaxiaowen用户进程所打开的文件类型为txt的文件 $ lsof -a -u xiaxiaowen -d txt #查找谁在使用文件系统 $ lsof /media/xiaxiaowen/机械硬盘 COMMAND PID USER FD TYPE DEVICE SIZE/OFF NODE NAME zsh 8465 xiaxiaowen cwd DIR 8,17 8192 5 /media/xiaxiaowen/机械硬盘linux软件开发知识点linux进程间通讯方式内存申请函数linux内存分配说明gcc编译过程文件系统硬链接和软连接linux内核子系统进程几种状态文件系统组成linux文件类型linux常用的系统调用函数fork函数僵尸进程常见文件说明proc目录说明fopen参数说明linux进程间通讯方式管道（Pipe）及有名管道（named pipe）信号（Signal）报文（Message）队列（消息队列）：共享内存信号量（semaphore）套接口（Socket）内存申请函数callocmallocrealloclinux内存分配说明内存存放数据说明静态存储区静态数据、全局数据、常量在程序编译的时候就已经分配好栈区局部变量、函数参数栈内存分配运算内置于处理器的指令集中，效率很高，但是分配的内存容量有限堆区malloc申请的内存动态内存分配,需要手动释放代码区代码存放函数体的二进制代码文字常量区常量字符串程序结束后由系统释放gcc编译过程 过程 生成文件 预编译 *.i 编译 *.s 汇编 *.o 链接 可执行文件 文件系统 fat fat32 ntfs ext2 ext3 ext4 nfs 硬链接和软连接硬链接硬链接直接指向文件的i节点硬链接和原文件的i节点是一样的硬链接文件显示的大小是跟原文件是一样的硬链接不能链接目录文件。ln file2 /home/xiaxiaowen/file2hard软链接(符号链接)软链接则是建立了一个新文件这个文件指向链接的文件，i节点不一样可以链接目录ln -s file2 /home/xiaxiaowen/file2softlinux内核子系统进程管理内存管理I/O管理文件系统管理进程几种状态运行态就绪态阻塞态文件系统组成超级块：存放文件系统本身的信息，比如记录了每个区域的大小，或未被使用的磁盘块的信息。（不同版本稍有差别）i-节点表：每个文件都有其属性，大小，最近修改时间等等，这些被存储在ino_t 的结构体中，所有的i-节点都有一样的大小，i-节点表就是这样一些节点的列表。（表中的每个i-节点都通过位置来标志，例如标志为2的i-节点位于文件系统i-节点表中的第3个位置 ）数据块：存放文件内容，因为块的大小一定，所以有时一个文件会分布在多个磁盘上。i 节点i 节点是一个64字节长的表,表中包含了文件的相关信息,其中有文件的大小、文件所有者、文件的存取许可方式以及文件的类型等重要信息.linux文件类型 文件类型 普通文件 目录 字符设备文件 块设备文件 符号链接文件 套接字文件 管道文件 属性 - d c b l s p linux常用的系统调用函数进程控制函数文件操作函数文件系统操作函数系统控制函数内存管理函数网络管理函数socket函数用户管理函数进程间通信函数信号相关函数消息相关函数管道相关函数信号量相关函数共享内存相关函数进程控制函数 fork 创建一个新进程 clone 按指定条件创建子进程 execve 运行可执行文件 exit 中止进程 _exit 立即中止当前进程 getdtablesize 进程所能打开的最大文件数 getpgid 获取指定进程组标识号 setpgid 设置指定进程组标志号 getpgrp 获取当前进程组标识号 setpgrp 设置当前进程组标志号 getpid 获取进程标识号 getppid 获取父进程标识号 getpriority 获取调度优先级 setpriority 设置调度优先级 modify_ldt 读写进程的本地描述表 nanosleep 使进程睡眠指定的时间 nice 改变分时进程的优先级 pause 挂起进程，等待信号 personality 设置进程运行域 prctl 对进程进行特定操作 ptrace 进程跟踪 sched_get_priority_max 取得静态优先级的上限 sched_get_priority_min 取得静态优先级的下限 sched_getparam 取得进程的调度参数 sched_getscheduler 取得指定进程的调度策略 sched_rr_get_interval 取得按RR算法调度的实时进程的时间片长度 sched_setparam 设置进程的调度参数 sched_setscheduler 设置指定进程的调度策略和参数 sched_yield 进程主动让出处理器,并将自己等候调度队列队尾 vfork 创建一个子进程，以供执行新程序，常与execve等同时使用 wait 等待子进程终止 wait3 参见wait waitpid 等待指定子进程终止 wait4 参见waitpid capget 获取进程权限 capset 设置进程权限 getsid 获取会晤标识号 setsid 设置会晤标识号 文件操作函数 fcntl 文件控制 open 打开文件 creat 创建新文件 close 关闭文件描述字 read 读文件 write 写文件 readv 从文件读入数据到缓冲数组中 writev 将缓冲数组里的数据写入文件 pread 对文件随机读 pwrite 对文件随机写 lseek 移动文件指针 _llseek 在64位地址空间里移动文件指针 dup 复制已打开的文件描述字 dup2 按指定条件复制文件描述字 flock 文件加/解锁 poll I/O多路转换 truncate 截断文件 ftruncate 参见truncate umask 设置文件权限掩码 fsync 把文件在内存中的部分写回磁盘 文件系统操作函数 access 确定文件的可存取性 chdir 改变当前工作目录 fchdir 参见chdir chmod 改变文件方式 fchmod 参见chmod chown 改变文件的属主或用户组 fchown 参见chown lchown 参见chown chroot 改变根目录 stat 取文件状态信息 lstat 参见stat fstat 参见stat statfs 取文件系统信息 fstatfs 参见statfs readdir 读取目录项 getdents 读取目录项 mkdir 创建目录 mknod 创建索引节点 rmdir 删除目录 rename 文件改名 link 创建链接 symlink 创建符号链接 unlink 删除链接 readlink 读符号链接的值 mount 安装文件系统 umount 卸下文件系统 ustat 取文件系统信息 utime 改变文件的访问修改时间 utimes 参见utime quotactl 控制磁盘配额 系统控制函数 ioctl I/O总控制函数 _sysctl 读/写系统参数 acct 启用或禁止进程记账 getrlimit 获取系统资源上限 setrlimit 设置系统资源上限 getrusage 获取系统资源使用情况 uselib 选择要使用的二进制函数库 ioperm 设置端口I/O权限 iopl 改变进程I/O权限级别 outb 低级端口操作 reboot 重新启动 swapon 打开交换文件和设备 swapoff 关闭交换文件和设备 bdflush 控制bdflush守护进程 sysfs 取核心支持的文件系统类型 sysinfo 取得系统信息 adjtimex 调整系统时钟 alarm 设置进程的闹钟 getitimer 获取计时器值 setitimer 设置计时器值 gettimeofday 取时间和时区 settimeofday 设置时间和时区 stime 设置系统日期和时间 time 取得系统时间 times 取进程运行时间 uname 获取当前UNIX系统的名称、版本和主机等信息 vhangup 挂起当前终端 nfsservctl 对NFS守护进程进行控制 vm86 进入模拟8086模式 create_module 创建可装载的模块项 delete_module 删除可装载的模块项 init_module 初始化模块 query_module 查询模块信息 *get_kernel_syms 取得核心符号,已被query_module代替 内存管理函数 brk 改变数据段空间的分配 sbrk 参见brk mlock 内存页面加锁 munlock 内存页面解锁 mlockall 调用进程所有内存页面加锁 munlockall 调用进程所有内存页面解锁 mmap 映射虚拟内存页 munmap 去除内存页映射 mremap 重新映射虚拟内存地址 msync 将映射内存中的数据写回磁盘 mprotect 设置内存映像保护 getpagesize 获取页面大小 sync 将内存缓冲区数据写回硬盘 cacheflush dddd将指定缓冲区中的内容写回磁盘dd 网络管理函数 getdomainname 取域名 setdomainname 设置域名 gethostid 获取主机标识号 sethostid 设置主机标识号 gethostname 获取本主机名称 sethostname 设置主机名称 socket函数 socketcall socket系统调用 socket 建立socket bind 绑定socket到端口 connect 连接远程主机 accept 响应socket连接请求 send 通过socket发送信息 sendto 发送UDP信息 sendmsg 参见send recv 通过socket接收信息 recvfrom 接收UDP信息 recvmsg 参见recv listen 监听socket端口 select 对多路同步I/O进行轮询 close 关闭socket上的连接 getsockname 取得本地socket名字 getpeername 获取通信对方的socket名字 getsockopt 取端口设置 setsockopt 设置端口参数 sendfile 在文件或端口间传输数据 socketpair 创建一对已联接的无名socket 用户管理函数 getuid 获取用户标识号 setuid 设置用户标志号 getgid 获取组标识号 setgid 设置组标志号 getegid 获取有效组标识号 setegid 设置有效组标识号 geteuid 获取有效用户标识号 seteuid 设置有效用户标识号 setregid 分别设置真实和有效的的组标识号 setreuid 分别设置真实和有效的用户标识号 getresgid 分别获取真实的,有效的和保存过的组标识号 setresgid 分别设置真实的,有效的和保存过的组标识号 getresuid 分别获取真实的,有效的和保存过的用户标识号 setresuid 分别设置真实的,有效的和保存过的用户标识号 setfsgid 设置文件系统检查时使用的组标识号 setfsuid 设置文件系统检查时使用的用户标识号 getgroups 获取后补组标志清单 setgroups 设置后补组标志清单 进程间通信函数 ipc 进程间通信总控制调用 信号相关函数 sigaction 设置对指定信号的处理方法 sigprocmask 根据参数对信号集中的信号执行阻塞/解除阻塞等操作 sigpending 为指定的被阻塞信号设置队列 sigsuspend 挂起进程等待特定信号 signal 参见signal kill 向进程或进程组发信号 *sigblock 向被阻塞信号掩码中添加信号,已被sigprocmask代替 *siggetmask 取得现有阻塞信号掩码,已被sigprocmask代替 *sigsetmask 用给定信号掩码替换现有阻塞信号掩码,已被sigprocmask代替 *sigmask 将给定的信号转化为掩码,已被sigprocmask代替 *sigpause 作用同sigsuspend,已被sigsuspend代替 sigvec 为兼容BSD而设的信号处理函数,作用类似sigaction ssetmask ANSI C的信号处理函数,作用类似sigaction 消息相关函数 msgctl 消息控制操作 msgget 获取消息队列 msgsnd 发消息 msgrcv 取消息 管道相关函数 pipe 创建管道 信号量相关函数 semctl 信号量控制 semget 获取一组信号量 semop 信号量操作 共享内存相关函数 shmctl 控制共享内存 shmget 获取共享内存 shmat 连接共享内存 shmdt 拆卸共享内存 fork函数fork是用来创建子进程的，这个函数的特别之处在于一次调用，两次返回，一次返回到父进程中，一次返回到子进程中，我们可以通过返回值来判断其返回点：pid_t child = fork(); if( child < 0 ) { //fork error. perror("fork process fail.\n"); } else if( child ==0 ) { // in child process printf(" fork succ, this run in child process\n "); } else { // in parent process printf(" this run in parent process\n "); }僵尸进程僵尸进程产生原因僵尸进程解决办法ps指令查看僵尸进程僵尸进程产生原因一个进程使用fork创建子进程，如果子进程退出，而父进程并没有调用wait或waitpid获取子进程的状态信息，那么子进程的进程描述符仍然保存在系统中。僵尸进程解决办法通过信号机制 子进程退出时向父进程发送SIGCHILD信号，父进程处理SIGCHILD信号。在信号处理函数中调用wait进行处理僵尸进程。fork两次 父进程创建子进程A，子进程A再创建子进程B，然后子进程A退出，z这样子进程B就交给init进程处理了。init进程可以处理僵尸进程.ps指令查看僵尸进程ps -A -ostat,pid,cmd |grep -iE '^z'-A 显示所有任务 -o 按照指定格式输出 grep -iE 显示z开头的行，不区分大小写常见文件说明/var/log/boot.log 系统引导日志/var/log/dmesg 系统核心启动日志/var/log/messages 核心系统日志/var/log/maillog 邮件系统日志/var/log/xferlog FTP系统日志/var/log/syslog 系统出问题的日志/var/log/secure 安全信息和系统登录与网络连接的信息/var/log/wtmp 登录记录/var/spool/clientmqueue/proc/interrupts/etc/fstab Linux内核引导时,从文件/etc/fstab 中读取要加载的文件系统.proc目录说明proc文件系统是一个伪文件系统，它只存在内存当中。 /proc/buddyinfo 每个内存区中的每个order有多少块可用，和内存碎片问题有关 /proc/cmdline 启动时传递给kernel的参数信息 /proc/cpuinfo cpu的信息 /proc/crypto 内核使用的所有已安装的加密密码及细节 /proc/devices 已经加载的设备并分类 /proc/dma 已注册使用的ISA DMA频道列表 /proc/execdomains Linux内核当前支持的execution domains /proc/fb 帧缓冲设备列表，包括数量和控制它的驱动 /proc/filesystems 内核当前支持的文件系统类型 /proc/interrupts x86架构中的每个IRQ中断数 /proc/iomem 每个物理设备当前在系统内存中的映射 /proc/ioports 一个设备的输入输出所使用的注册端口范围 /proc/kcore 代表系统的物理内存，存储为核心文件格式，里边显示的是字节数，等于RAM大小加上4kb /proc/kmsg 记录内核生成的信息，可以通过/sbin/klogd或/bin/dmesg来处理 /proc/loadavg 根据过去一段时间内CPU和IO的状态得出的负载状态，与uptime命令有关 /proc/locks 内核锁住的文件列表 /proc/mdstat 多硬盘，RAID配置信息(md=multiple disks) /proc/meminfo RAM使用的相关信息 /proc/misc 其他的主要设备(设备号为10)上注册的驱动 /proc/modules 所有加载到内核的模块列表 /proc/mounts 系统中使用的所有挂载 /proc/mtrr 系统使用的Memory Type Range Registers (MTRRs) /proc/partitions 分区中的块分配信息 /proc/pci 系统中的PCI设备列表 /proc/slabinfo 系统中所有活动的 slab 缓存信息 /proc/stat 所有的CPU活动信息 /proc/sysrq-trigger 使用echo命令来写这个文件的时候，远程root用户可以执行大多数的系统请求关键命令，就好像在本地终端执行一样。要写入这个文件，需要把/proc/sys/kernel/sysrq不能设置为0。这个文件对root也是不可读的 /proc/uptime 系统已经运行了多久 /proc/swaps 交换空间的使用情况 /proc/version Linux内核版本和gcc版本 /proc/bus 系统总线(Bus)信息，例如pci/usb等 /proc/driver 驱动信息 /proc/fs 文件系统信息 /proc/ide ide设备信息 /proc/irq 中断请求设备信息 /proc/net 网卡设备信息 /proc/scsi scsi设备信息 /proc/tty tty设备信息 /proc/net/dev 显示网络适配器及统计信息 /proc/vmstat 虚拟内存统计信息 /proc/vmcore 内核panic时的内存映像 /proc/diskstats 取得磁盘信息 /proc/schedstat kernel调度器的统计信息 /proc/zoneinfo 显示内存空间的统计信息，对分析虚拟内存行为很有用 #### 以下是/proc目录中进程N的信息 /proc/N pid为N的进程信息 /proc/N/cmdline 进程启动命令 /proc/N/cwd 链接到进程当前工作目录 /proc/N/environ 进程环境变量列表 /proc/N/exe 链接到进程的执行命令文件 /proc/N/fd 包含进程相关的所有的文件描述符 /proc/N/maps 与进程相关的内存映射信息 /proc/N/mem 指代进程持有的内存，不可读 /proc/N/root 链接到进程的根目录 /proc/N/stat 进程的状态 /proc/N/statm 进程使用的内存的状态 /proc/N/status 进程状态信息，比stat/statm更具可读性 /proc/self 链接到当前正在运行的进程fopen参数说明参数说明r以只读方式打开文件，该文件必须存在。r+以可读写方式打开文件，该文件必须存在。rb+读写打开一个二进制文件，允许读写数据，文件必须存在。w打开只写文件，若文件存在则文件长度清为0，即该文件内容会消失。若文件不存在则建立该文件。w+打开可读写文件，若文件存在则文件长度清为零，即该文件内容会消失。若文件不存在则建立该文件。a以附加的方式打开只写文件。若文件不存在，则会建立该文件，如果文件存在，写入的数据会被加到文件尾，即文件原先的内容会被保留。（EOF符保留）a+以附加方式打开可读写的文件。若文件不存在，则会建立该文件，如果文件存在，写入的数据会被加到文件尾后，即文件原先的内容会被保留。 （原来的EOF符不保留）wb只写打开或新建一个二进制文件；只允许写数据。wb+读写打开或建立一个二进制文件，允许读和写。ab+读写打开一个二进制文件，允许读或在文件末追加数据。wx创建文本文件,只允许写入数据.[C11]wbx创建一个二进制文件,只允许写入数据.[C11]w+x创建一个文本文件,允许读写.[C11]wb+x创建一个二进制文件,允许读写.[C11]w+bx和"wb+x"相同[C11]以x结尾的模式为独占模式,文件已存在或者无法创建(一般是路径不正确)都会导致fopen失败.文件以操作系统支持的独占模式打开.[C11]linux驱动开发知识点insmod rmmod 加载 卸载模块i.max6UL系统框图linux启动过程系统上电--->bootrom--->uboot--->kernel加载--->init--->应用程序makefilemakefile的规则target xxx : prerequisites aaa [command] ... ...prerequisites中如果有一个以上的文件比target文件要新的话，command所定义的命令就会被执行gcc工具链命令描述Binutils由汇编器（as）产生的目标代码（*.o）是不能直接在computer上运行的，它必须经过链接器（ld）的处理才能生成可执行代码。add2line将地址转换成文件名或行号对，以便调试程序ar从文件中创建、修改、扩展文件gasp汇编宏处理器nm从目标文件列举所有变量objcopy使用GNU BSD库把目标文件的内容从一种文件格式复制到另一种格式的目标文件中。objdump显示目标文件信息可发编译二进制文件，也可以对对象文件进行反汇编，并查看机器代码。readelf显示elf文件信息ranlib生成索引以加快对归档文件的访问，并将其保存到这个归档文件中。size列出目标模块或文件的代码尺寸。strings打印可打印的目标代码符号（至少4个字符）strip放弃所有符号连接，一般应用程序最终都要strip处理C++filt链接器ld通过该命令可过滤C++符号和JAVA符号，防止重载函数冲突。gprof显示程序调用段的各种数据nm命令显示二进制目标文件的符号表-A：每个符号前显示文件名； -D：显示动态符号； -g：仅显示外部符号； -r：反序显示符号表。ldd命令用于打印程序或者库文件所依赖的共享库列表。-v：详细信息模式，打印所有相关信息； -u：打印未使用的直接依赖； -d：执行重定位和报告任何丢失的对象； -r：执行数据对象和函数的重定位，并且报告任何丢失的对象和函数；交叉编译工具链说明gcc 交叉编译器将写好的C程序代码编译为ARM架构下的可执行文件.gcc hello.c -o hellold 交叉链接器将多个编译后产生的过程文件连接为一个最终的可执行文件。ld [options] 链接器脚本 -o 文件名.elfreadelf 交叉ELF文件查看器用来查看一个可执行文件的相关信息可以查看elf文件的运行架构，大小端等信息:readelf -a 文件名.elf显示程序需要的动态链接库:readelf -d 文件名.elfobjdump 交叉反汇编器将一个可执行文件转换为汇编下的程序-objdump -D -S elf文件名 >目标文件objcopy 交叉转换器将elf格式文件转换成其他的格式objcopy -O 目标文件格式 原ELF文件 目标文件例子:objcopy -O binary a.elf a.bin

C基础 目录c基础数据类型说明volatile指针函数指针函数指针数组指针数组数组指针指针的指针main函数的返回值const浮点数存储方式c题目printf返回值enum枚举类型可变参数函数链表排序算法选择排序插入排序希尔排序冒泡排序快速排序hash算法hash构造方法hash冲突及解决常用的hash函数c基础数据类型说明volatile指针constmain函数的返回值浮点数存储方式数据类型说明数据类型16位平台32位平台64位平台char1 字节1 字节1 字节pointer2 字节4 字节8 字节short2 字节2 字节2 字节int2 字节4 字节4 字节float4 字节4 字节4 字节double8 字节8 字节8 字节long4 字节4 字节8 字节long long8 字节8 字节8 字节volatilevolatile 指出变量是随时可能发生变化的，每次使用它的时候必须从变量的地址中读取，因而编译器生成的汇编代码会重新从变量的地址读取数据。并行设备的硬件寄存器，一个中断服务子程序中会访问到的非自动变量（Non-automatic variables),可以使用关键区保护多线程应用中被几个任务共享的变量，可以关闭系统调度指针函数指针int (*fun)(int *a);函数指针数组int (*fun[10])(int *data, int size);使用方法：int (*sort_fun[5])(int *data, int size) = { quick_sort, /* 快速排序 */ insert_sort, /* 插入排序 */ bubble_sort, /* 冒泡排序 */ heap_sort, /* 堆排序 */ selection_sort /* 选择排序 */ }; // 或者 sort_fun[0] = quick_sort; sort_fun[1] = insert_sort;指针数组int *a[10];数组指针/* a为指向含10个元素的一维数组的指针变量， * ()优先级高，说明a是一个指针，指向一个整型的一维数组. * a+1时，a要跨过10个整型数据的长度 */ int (*a)[10];指针的指针int **a;main函数的返回值0 表示程序正常退出负数表示程序异常退出constconst T定义一个常量，声明的同时必须进行初始化。一旦声明，这个值将不能被改变。const int constInt = 10; //正确 constInt = 20; //错误，常量值不可被改变 const int constInt3; //错误，未被初始化const T*指向常量的指针，不能用于改变其所指向的对象的值。const int i = 5; const int i2 = 10; const int* pInt = &i; //正确，指向一个const int对象，即i的地址 //*pInt = 10; //错误，不能改变其所指缶的对象 pInt = &i2; //正确，可以改变pInt指针本身的值,此时pInt指向的是i2的地址 const int* p2 = new int(8); //正确，指向一个new出来的对象的地址 delete p2; //正确 //int* pInt = &i; //错误，i是const int类型，类型不匹配，不能将const int * 初始化为int * int nValue = 15; const int * pConstInt = &nValue; //正确，可以把int *赋给const int *，但是pConstInt不能改变其所指向对象的值，即nValue *pConstInt = 40; //错误，不能改变其所指向对象的值const int 与int const的区别指针本身就是一种对象，把指针定义为常量就是常量指针，也就是int const的类型，也可以写成int const，声明时必须初始化。int nValue = 10; int* const p = &nValue; int *const p2 = &nValue; //const int* 指针指向的对象不可以改变，但指针本身的值可以改变；int* const 指针本身的值不可改变，但其指向的对象可以改变。 int nValue1 = 10; int nValue2 = 20; int* const constPoint = &nValue1; //constPoint = & nValue2; //错误，不能改变constPoint本身的值 *constPoint = 40; //正确，可以改变constPoint所指向的对象，此时nValue1 = 40 const int nConstValue1 = 5; const int nConstValue2 = 15; const int* pPoint = &nConstValue1; //*pPoint = 55; //错误，不能改变pPoint所指向对象的值 pPoint = &nConstValue2; //正确，可以改变pPoint指针本身的值，此时pPoint邦定的是nConstValue2对象，即pPoint为nConstValue2的地址const int* const 是一个指向常量对象的常量指针，即不可以改变指针本身的值，也不可以改变指针指向的对象。const int nConstValue1 = 5; const int nConstValue2 = 15; const int* const pPoint = &nConstValue1; //*pPoint = 55; //错误，不能改变pPoint所指向对象的值 //pPoint = &nConstValue2; //错误，不能改变pPoint本身的值const助记方法把一个声明从右向左读。( * 读成 pointer to )char * const cp; // cp is a const pointer to char const char * p; // p is a pointer to const char; char const * p; // 同上,因为C++里面没有const*的运算符，所以const只能属于前面的类型。C++标准规定，const关键字放在类型或变量名之前等价的。结论：char * const cp // 定义一个指向字符的指针常数，即const指针 const char* p // 定义一个指向字符常数的指针 char const* p // 等同于const char* p const char ** // 是一个指向指针的指针，那个指针又指向一个字符串常量。 char ** // 也是一个指向指针的指针，那个指针又指向一个字符串变量。浮点数存储方式float 占用4个字节，32bits 符号位 指数位 尾数部分 1 bits 8 bits 23 bits double 占用8字节，64bits 符号位 指数位 尾数部分 1 bits 11 bits 52 bits c题目printf返回值enum枚举类型可变参数函数printf返回值#include <stdio.h> int main() { int i = 43; printf("%d\n", printf("%d", printf("%d", i))); return 0; }输出：4321printf返回值是输出字符的个数（不包括字符串结尾\x00）enum枚举类型#include <stdio.h> int main() { enum color{ RED, BLUE, GREEN = -2, YELLOW, PINK }; printf("%d %d\n", BLUE, PINK); return 0; }输出：1 0enum默认是从0开始的，所以RED = 0， BLUE = 1， GREEN = -2， YELLOW = -1， PINK = 0；可变参数函数#include "stdarg.h" char buf[512] = {0}; int func(const char *fmt, ...) { va_list args; va_start(args, fmt); vsprintf(buf, fmt, args); va_end(args); }大小端区分union data { int a; char b; }; struct def { union data mine; }; struct def endian; int main(int argc, char **argv) { endian.mine.a = 0x12345678; printf("%02X\n", endian.mine.b); return 0; } /*打印 78 说明是小端， 12 说明是大端 */链表//////////////////////////////////////////// //单链表的初始化，建立，插入，查找，删除。// //Author:Wang Yong // //Date: 2010.8.19 // //////////////////////////////////////////// #include <stdio.h> #include <stdlib.h> typedef int ElemType; //////////////////////////////////////////// //定义结点类型 typedef struct Node { ElemType data; //单链表中的数据域 struct Node *next; //单链表的指针域 }Node,*LinkedList; //////////////////////////////////////////// //单链表的初始化 LinkedList LinkedListInit() { Node *L; L = (Node *)malloc(sizeof(Node)); //申请结点空间 if(L == NULL) //判断是否有足够的内存空间 printf("申请内存空间失败/n"); L->next = NULL; //将next设置为NULL,初始长度为0的单链表 } //////////////////////////////////////////// //单链表的建立1，头插法建立单链表 LinkedList LinkedListCreatH() { Node *L; L = (Node *)malloc(sizeof(Node)); //申请头结点空间 L->next = NULL; //初始化一个空链表 ElemType x; //x为链表数据域中的数据 while(scanf("%d",&x) != EOF) { Node *p; p = (Node *)malloc(sizeof(Node)); //申请新的结点 p->data = x; //结点数据域赋值 p->next = L->next; //将结点插入到表头L-->|2|-->|1|-->NULL L->next = p; } return L; } //////////////////////////////////////////// //单链表的建立2，尾插法建立单链表 LinkedList LinkedListCreatT() { Node *L; L = (Node *)malloc(sizeof(Node)); //申请头结点空间 L->next = NULL; //初始化一个空链表 Node *r; r = L; //r始终指向终端结点，开始时指向头结点 ElemType x; //x为链表数据域中的数据 while(scanf("%d",&x) != EOF) { Node *p; p = (Node *)malloc(sizeof(Node)); //申请新的结点 p->data = x; //结点数据域赋值 r->next = p; //将结点插入到表头L-->|1|-->|2|-->NULL r = p; } r->next = NULL; return L; } //////////////////////////////////////////// //单链表的插入，在链表的第i个位置插入x的元素 LinkedList LinkedListInsert(LinkedList L,int i,ElemType x) { Node *pre; //pre为前驱结点 pre = L; int tempi = 0; for (tempi = 1; tempi < i; tempi++) pre = pre->next; //查找第i个位置的前驱结点 Node *p; //插入的结点为p p = (Node *)malloc(sizeof(Node)); p->data = x; p->next = pre->next; pre->next = p; return L; } //////////////////////////////////////////// //单链表的删除，在链表中删除值为x的元素 LinkedList LinkedListDelete(LinkedList L,ElemType x) { Node *p,*pre; //pre为前驱结点，p为查找的结点。 p = L->next; while(p->data != x) //查找值为x的元素 { pre = p; p = p->next; } pre->next = p->next; //删除操作，将其前驱next指向其后继。 free(p); return L; } ///////////////////////////////////////////// int main() { LinkedList list,start; /* printf("请输入单链表的数据："); list = LinkedListCreatH(); for(start = list->next; start != NULL; start = start->next) printf("%d ",start->data); printf("/n"); */ printf("请输入单链表的数据："); list = LinkedListCreatT(); for(start = list->next; start != NULL; start = start->next) printf("%d ",start->data); printf("/n"); int i; ElemType x; printf("请输入插入数据的位置："); scanf("%d",&i); printf("请输入插入数据的值："); scanf("%d",&x); LinkedListInsert(list,i,x); for(start = list->next; start != NULL; start = start->next) printf("%d ",start->data); printf("/n"); printf("请输入要删除的元素的值："); scanf("%d",&x); LinkedListDelete(list,x); for(start = list->next; start != NULL; start = start->next) printf("%d ",start->data); printf("/n"); return 0; }排序算法选择排序插入排序希尔排序冒泡排序快速排序排序算法有： 选择排序 快速排序 希尔排序 冒泡排序 插入排序 堆排序 归并排序 排序算法比较：选择排序选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。时间复杂度平均: O(n2) 最好: O(n2) 最坏:O(n2)空间复杂度O(1)算法步骤首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。重复第二步，直到所有元素均排序完毕。动图演示/* 直接选择排序 */ void selection_sort(int n) { for (int i = 0; i < n - 1; i++) { int min = i; for (int j = i + 1; j < n; j++) { if (x[j] < x[min]) { min = j; } } if (min != i) { swap(x,i,min); } } }插入排序插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。时间复杂度平均：O(n2) 最好：O(n) 最坏：O(n2)空间复杂度O(1)算法步骤将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）动图演示/* 直接插入排序 */ void insertion_sort(int n) { for(int i = 1; i < n; i++) { int t = x[i]; int j; for (j = i; j > 0 && x[j-1] > t ; j--) { x[j] = x[j - 1]; } x[j] = t; } }希尔排序希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。希尔排序是基于插入排序的以下两点性质而提出改进方法的：插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。时间复杂度平均：O(n1.5) 最好：O(n) 最坏O(n2)空间复杂度O(1) 算法步骤选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；按增量序列个数 k，对序列进行 k 趟排序；每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。/* 希尔排序 */ void shell_sort(int n) { for (int inc = n/3; inc >= 1; inc /= 3 ) { for (int i = inc; i < n; i++) { int t = x[i]; int j; for (j = i; j >= inc && x[j - inc] > t ; j -= inc) { x[j] = x[j - inc]; } x[j] = t; } } }冒泡排序时间复杂度平均: O(n2) 最好: O(n) 最坏：O(n2)空间复杂度O(1)算法步骤比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。动图演示/* 冒泡排序 */ void bubble_sort(int n) { bool change = true; for (int i = n-1; i >= 1 && change; i--) { change = false; for (int j = 0; j < i; j++) { if(x[j] > x[j + 1]) { swap(x, j, j + 1); change = true; } } } }快速排序快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好，可是这是为什么呢，我也不知道。好在我的强迫症又犯了，查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。时间复杂度平均: O(nlogn) 最好: O(nlogn) 最坏:O(n2)空间复杂度O(nlogn) 用于方法栈算法步骤从数列中挑出一个元素，称为 “基准”（pivot）;重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。动图演示/* 快速排序 */ void quick_sort(int l, int u) { if (l >= u) return; int m = l; for (int i = l+1; i<= u; i++) { if(x[i] < x[l]) swap(x, ++m, i); } swap(x, l, m); quick_sort(l, m-1); quick_sort(m+1, u); }hash算法hash构造方法直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a?key + b，其中a和b为常数（这种散列函数叫做自身函数）数字分析法：分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。平方取中法：取关键字平方后的中间几位作为散列地址。折叠法：将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。随机数法：选择一随机函数，取关键字的随机值作为散列地址，通常用于关键字长度不同的场合。除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p, p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。hash冲突及解决冲突原因：与散列函数有关，一个好的散列函数的值应尽可能平均分布。与解决冲突的哈希冲突函数有关。与负载因子的大小。太大不一定就好，而且浪费空间严重，负载因子和散列函数是联动的。解决冲突的办法开放定址法：线性探查法、平方探查法、伪随机序列法、双哈希函数法。拉链法：把所有同义词，即hash值相同的记录，用单链表连接起来。常用的hash函数unsigned int RSHash(char* str, unsigned int len) { unsigned int b = 378551; unsigned int a = 63689; unsigned int hash = 0; unsigned int i = 0; for(i = 0; i < len; str++, i++) { hash = hash * a + (*str); a = a * b; } return hash; } /* End Of RS Hash Function */ unsigned int JSHash(char* str, unsigned int len) { unsigned int hash = 1315423911; unsigned int i = 0; for(i = 0; i < len; str++, i++) { hash ^= ((hash << 5) + (*str) + (hash >> 2)); } return hash; } /* End Of JS Hash Function */ unsigned int ELFHash(char* str, unsigned int len) { unsigned int hash = 0; unsigned int x = 0; unsigned int i = 0; for(i = 0; i < len; str++, i++) { hash = (hash << 4) + (*str); if((x = hash & 0xF0000000L) != 0) { hash ^= (x >> 24); } hash &= ~x; } return hash; } /* End Of ELF Hash Function */ unsigned int DJBHash(char* str, unsigned int len) { unsigned int hash = 5381; unsigned int i = 0; for(i = 0; i < len; str++, i++) { hash = ((hash << 5) + hash) + (*str); } return hash; } /* End Of DJB Hash Function */javascript数据类型字符串 数字 布尔 对象 数组 undefined nulljs只有一种数字类型undefined：当声明的变量没有初始化的话，那这个变量的值就是undefinednull表示尚未存在的对象。