# 插入排序
## 基本思想
每一步将一个待排序的元素，按其排序码的大小，插入到前面已经排好序的一组元素的合适位置上去，直到元素全部插完为止



## 直接插入排序
![mark](https://img.zouchanglin.cn///20200405/bWjJ61NoQU0x.png)
### 代码实现
```c
//插入排序
void InsertSort(int *arr, int n)
{
    int index = 0;
    assert(arr);
    for(index = 1; index < n; index++)
    {
        //将当前数据往前插入
        int end = index-1;
        int temp = arr[index];
        while(end >= 0 && temp < arr[end])
        {
            arr[end+1] = arr[end];
            --end;
        }
        arr[end+1] = temp;
    }
}
```
下图只是演示到将16排序到前面的过程
![mark](https://img.zouchanglin.cn///20200405/rNj8c5yIU2l8.png)

### 直接插入排序的优化
```c
//插入排序
void InsertSort_OP(int *arr, int n)
{
	int index = 0;
	for (index = 1; index < n; index++)
	{
		int temp = arr[index];
		//通过二分查找 找出待插入元素的位置
		int left = 0;
		int right = index - 1;
		
		while (left <= right)
		{
			int mid = left + ((right - left) >> 1);
			if (temp >= arr[mid])
				left = mid + 1;
			else
				right = mid - 1;
		}
		
		//将当前数据往前插入
		int end = index - 1;
		//搬移元素
		while (end >= left)
		{
			arr[end + 1] = arr[end];
			--end;
		}
		arr[left] = temp;
	}
}
```
由于之前的序列都是有序的，这样的话就不用一个一个进行比较，只要先用二分查找找到插入的位置，这样的话本来需要搬运元素只需要搬运一次就行，很多元素不需要比较一次就搬运一次，这样会提高效率！
### 总结
元素集合越接近有序，直接插入排序算法的时间效率越高！
最优情况下：时间效率为$O(n)$
最差情况下：时间复杂度为$O(n^2)$
空间复杂度：$O(1)$，它是一种稳定的排序算法
## 希尔排序
又称缩小增量排序，是对直接插入排序的优化
![mark](https://img.zouchanglin.cn///20200405/GBkftpJgEQ12.png)
很容易看出，经过这样的分组之后，许多比较大的数字都放在了后面，小数字都放在了前面，只要gap不断减小，分组不断变小，最后直到gap减到1的时候就和直接插入排序没什么区别了！
![mark](https://img.zouchanglin.cn///20200405/wMAkWAIoOk1t.png)

### 代码实现
```c
void ShellSort(int* arr,int len)
{
    int gap = len;
    assert(arr);
    while(gap>1)
    {
        gap = gap/3+1;
        int cur = 0;
        for(cur = gap;cur<len;++cur)
        {
            int end = cur-gap;
            int tmp = arr[cur];
            while(end>=0 && tmp<arr[end])
            {
                arr[end+gap] = arr[end];
                end -= gap;
            }
            arr[end+gap] = tmp;
        }
    }
}
```
### 总结
希尔排序是一种**不稳定**的排序，时间复杂度：$N^{1.25}  到 1.6N^{1.25}$
# 选择排序
## 基本思想
假设要排升序，每一趟选择一个最大的数字与最后的元素交换，这里所说的最后一个元素是会逐步向前调整的！
![mark](https://img.zouchanglin.cn///20200405/A12nvJXpQJe3.png)

## 代码实现
```c
//选择排序
void SelectSort(int *arr, int n)
{
    int index = 0;
    assert(arr);
	for (index = 0; index < n; index++)
	{
		int maxPos = 0;
		int i = 1;
		//找最大元素的位置
		for (i = 1; i < n-index; i++)
		{
			if (arr[i] > arr[maxPos])
				maxPos = i;
		}
		if (maxPos != (n - index - 1))
			Swap(&arr[maxPos], &arr[n-index-1]);
	}
}
```
## 基本选择排序的优化
优化为每趟寻找最大值的同时找到最小值
```c
//选择排序的优化
void SelectSort_OP(int *arr, int n)
{
    int begin = 0;
    int end = n-1;

    assert(arr);
    while(begin < end)
	{
            int minindex = begin;
            int maxindex = begin;
	    //分别找到最大和最小的下标
	    int i = 0;
	    for(i = begin;i <= end; ++i)
		{
			if(arr[i]>arr[maxindex])
			{
				maxindex = i;
			}
			if(arr[i]<arr[minindex])
			{
				minindex = i;
			}
	    }
	    //把最小的放在前面，最大的放在后面
	    Swap(&arr[begin], &arr[minindex]);
	    if(begin == maxindex)//修正
		    maxindex = minindex;
	    Swap(&arr[end], &arr[maxindex]);
	    ++begin;
	    --end;
    }
}
```
只不过这种优化的方式需要注意一点（见下图），如果最小的元素恰好是最大的元素需要插入的位置，此时就需要将minPos设置为原来max的位置，因为最小值已经和maxPos位置的值交换了！
![mark](https://img.zouchanglin.cn///20200405/HXsGp0MwzLfw.png)

### 总结
时间复杂度：$n^2$
空间复杂度：$O(1)$
这是一种不稳定的排序
## 堆排序
堆排序有两个关键点
* 根据数组去建堆
* 交换首尾元素向下调整

![mark](https://img.zouchanglin.cn///20200405/TjIFBElBsjhR.png)
### 代码实现
```c
void HeapAdjust(int *arr,int root,int len)
{
    //child是左孩子的下标
    int child = root*2+1;
    assert(arr);
    while(child<len)
    {
        // 比较左孩子和右孩子,child指向大的孩子
        if(child+1<len && arr[child+1]>arr[child])
        {
            child++;
        }
        // 1.若大的孩子节点大于根节点,则不再需要调整,跳出循环
        // 2.否则,交换孩子节点和根节点,将根节点继续往下调整
		if (arr[child] > arr[root])
		{
			Swap(&arr[child], &arr[root]);
			root = child;
			child = child * 2 + 1;
		}
		else
			return;
    }
}
//堆排序
void HeapSort(int *arr, int len)
{
	int i = (len - 2)>>1;
    assert(arr);
    //建堆
    for( ; i>=0; i--)
        HeapAdjust(arr, i, len);
    //排序
    for(i = len-1;i > 0; i--)
    {
        Swap(&arr[i], &arr[0]);
        HeapAdjust(arr, 0, i);
    }
}
```
### 总结
堆排序的时间复杂度：$N/2 *{log N}$其实就是$logN$
空间复杂度：$O(1)$
稳定性：不稳定
# 交换排序
## 冒泡排序
冒泡排序的思想非常简单，如下图，两两比较，每趟排序总可以把最大的放在最后面或者最小的值放在最后面，只需要进行（假设元素个数为n）n-1趟冒泡，便可以排序完成！

![]( https://img.zouchanglin.cn/20181005191008941.gif)



### 代码实现
```c
// 冒泡排序及其优化
void BubbleSort(int* arr, int len)
{
    int index = 0;
    int end = 0;
    assert(arr);
    for(end = len-1;end>0;end--)
    {
        int flag = 0;
        for(index=0;index<end;index++)
        {
            if(arr[index]>arr[index+1])
            {
                Swap(&arr[index], &arr[index+1]);
                flag = 1;
            }
        }
        if(flag == 0)
            break;
    }
}
```
### 总结
冒泡排序最好情况时间复杂度$O(n)$，冒泡排序最坏情况下时间复杂度 $O(1)$
冒泡排序空间复杂度$O(1)$
冒泡排序是一种稳定的排序算法
## 快速排序
### 基本思想
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
![mark](https://img.zouchanglin.cn///20200405/uxqrliqImFKu.png)
这样的话左边都是比基准值小的，在右边的都是比基准值大的，根据分治的思想，可以再把左边的序列选出一个基准值，在右边的序列也选择一个基准值，左边的排好了，右边的排好了，整个序列也就排好了！

### 代码实现_hoare版本
```c
//快速排序
int PartSort(int *a, int left, int right)
{
	int key = a[right];
	int begin = left;
	int end = right - 1;
	while (begin < end)
	{
		//找比基准值大的
		while ((begin < end) && (a[begin] <= key))
			begin++;
		//找比基准值小的
		while ((begin < end) && (a[end] >= key))
			end--;
		if (begin<end)
			Swap(&a[begin], &a[end]);
	}
	//最后别忘记把基准值和相遇点交换
	if (begin != right - 1)
		Swap(&a[begin], &a[right-1]);
	return begin;
}
void QuickSort(int *a, int left, int right)
{
	assert(a);
	if (left >= right)
		return;
	int div = PartSort(a, left, right);
	QuickSort(a, left, div);
	QuickSort(a, div + 1, right);
}
```
### 前后指针法
![]( https://img.zouchanglin.cn/20181008185808472.gif)
这个方式其实不难理解，就是每次将key值移动到中间，在key左边的值都是比key小的值，key右边的值都是比key大的值，这样做分组的的话通过递归就可以完成排序！

```c
int PartSort3(int *array, int left, int right)
{
	int key = array[right - 1];
	int cur = left;
	int pre = cur - 1;
	while (cur < right)//说明区间的元素还没有遍历完成
	{
		if ((array[cur] < key) && (++pre != cur))
			Swap(&array[cur], &array[pre]);
		++cur;
		
	}
	if (++pre != right)
		Swap(&array[pre], &array[right-1]);
	return pre;
}
void QuickSort3(int *a, int left, int right)
{
	assert(a);
	if (left >= right)
		return;
	int div = PartSort3(a, left, right);
	QuickSort(a, left, div - 1);
	QuickSort(a, div + 1, right);
}
```

常见排序的总结

## 进程创建

### fork&vfork

fork与vfork同样都是创建子进程，但是注意两者的区别：

- fork()：子进程拷贝父进程的**数据段，代码段**，
- vfork ()：子进程与父进程**共享数据段**
- fork()：父子进程的**执行次序不确定**
- vfork()： **保证子进程先运行**，在调用exec 或exit 之前与父进程数据是共享的,在它调用exec或exit 之后父进程才可能被调度运行
- vfork()：保证子进程先运行，在她调用exec 或exit 之后父进程才可能被调度运行。**如果在调用这两个函数之前子进程依赖于父进程的进一步动作，则会导致死锁**





```c
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>

int g_val = 100;

int main(int argc, char *argv[]){
	pid_t pid = vfork();
	if(pid == 0){
		sleep(5);
		g_val = 200;
		printf("%d\n",g_val);
		exit(0);
	}else{
		printf("%d\n",g_val);
	}

	return 0;
}
```

![mark](https://img.zouchanglin.cn///20200201/q6udILFBMLno.png)

可以看出，vfork出来的子进程实际上和父进程共享数据段！

## 进程终止

进程退出的三种状况

- 代码运行完毕、结果正确

- 代码运行完毕、结果不正确

- 从`main`函数返回
- 调用`exit()`
- 调用`_exit()`
- 代码异常终止
- 信号终止：

```
kill -9
```

### _exit()

```c
#include <unistd.h>
void _exit(int status);
参数：status定义了进程的终止状态，父进程通过wait来获取该值
```

### exit()

```c
#include <stdlib.h>
void exit(int status);
```

`exit()`最后也会调用`_exit()`，只不过在调用`_exit()`之前做了些其他的事情：

- 执行用户通过`atexit()`或者`on_exit()`定义的清理函数
- 关闭所有打开的流，所有的缓存数据均被写入
- 调用`_exit()`

### return 退出

`return`退出是一种更常见的退出，执行 等同于，因为调用main函数的函数会把main函数的返回值当做的参数



## 进程等待

- 子进程退出，父进程如果不管不顾，就可能造成**僵尸进程**的问题，进而造成内存泄漏。
- 另外，进程一旦变成僵尸状态，那就刀枪不入，`kill -9` 也无能为力，因为谁也没有办法杀死一个已经死去的进程。
- 最后，父进程派给子进程的任务完成的如何，我们需要知道。子进程运行完成，结果对还是不对，或者是否正常退出。
- 父进程通过进程等待的方式，回收子进程资源，获取子进程退出信息

### wait方法

```c
#include <sys/types.h>
#include <sys/wait.h>
pid_t wait(int *status);
返回值：
	成功返回被等待进程的pid，失败返回-1
参数：
	输出型参数，获取子进程退出状态，不用关心此状态则设置为NULL
```

### waitpid方法

```c
#include <sys/types.h>
#include <sys/wait.h>
pid _ t waitpid ( pid _ t pid , int * status , int options ) ;
返回值：
	当正常返回的时候 waitpid 返回收集到的子进程的进程ID 
	如果设置了选项 wNOHANG ，而调用中 waitpid 发现没有已退出的子进程可收集，则返回0
	如果调用中出错，则返回一 1 ，这时 errno 会被设置成相应的值以指示错误所在；
参数： 
	pid : pid ＝ -1 ，等待任一个子进程，与 wait 等效
	pid ＞0 等待其进程ID与 pid 相等的子进程。
	status: WIFEXITED(status) ：若为正常终止子进程返回的状态，则为真。（查看进程是否是正常退出)
	status: WEXITSTATUS(status) ：若 WIFEXITED非零，提取子进程退出码。（查看进程的退出码）
	options :WNOHANG：若 pid 指定的子进程没有结束，则 waitpid()函数返回0，不予以等待。若正常结束，则返回该子进程的ID
```

 如果子进程已经退出，调用 `wait`和`waitpid` 时， wait/waitpid 会立即返回，并且释放资源，获得子进程退出信息。
如果在任意时刻调用 `wait`和`waitpid` ，子进程存在且正常运行，则进程可能阻塞。如果不存在该子进程，则立即出错返回。 

![mark](https://img.zouchanglin.cn///20200201/ml7eN4UOArTl.png)

### 获取子进程status

`wait` 和 `waitpid` ，都一个 status 参数，该参数是一个输出型参数，由操作系统填充。如果传递 NULL ，表示不关心子进程的退出状态信息。否则，操作系统会根据该参数，将子进程的退出信息反馈给父进程。
**status 不能简单的当作整形来看待，可以当作位图来看待**，具体细节如下图（只研究 status 低 16 比特位） :

![mark](https://img.zouchanglin.cn///20200201/8DimRFO2c3kQ.png)

 先看这样一段代码： 

```c
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>

int main(int argc, char *argv[]){
	pid_t pid = fork();
	if(pid < 0){
		printf("fork error");
		exit(1);
	}else if(pid == 0){
		sleep(20);
		exit(10);
	}else{
		int st = 0;
		int ret = wait(&st);
		
		if(ret>0 && (st & 0X7F)==0){//正常退出
			printf("child exit code: %d\n",(st>>8&0XFF));
		}else if(ret > 0){//异常退出
			printf("sig code: %d\n",st&0X7F);
		}
	}
	return 0;
}
```

#### 进程阻塞式等待方式

```c
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>

int main(int argc, char *argv[]){
	pid_t pid = fork();
	if(pid == 0){
		printf("child is run, pid is %d\n", getpid());
		sleep(5);
		exit(27);
	}else{
		int status = 0;
		pid_t ret = waitpid(-1,&status,0);//阻塞式等待5s
		printf("this is test forwait\n");
		if(WIFEXITED(status) && ret == pid){
			printf("wait child 5s success,child return code is %d\n",WEXITSTATUS(status));
		}else{
			printf("wait child failed,return .\n");
			return 1;
		}
	}
	return 0;
}
```

#### 进程的非阻塞等待

```c
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <sys/wait.h>

int main(){

  pid_t pid;
  pid = fork();
  if(pid < 0){
    printf("%s fork error\n", __FUNCTION__);
    return 1;
  }else if(pid == 0){
    printf("child is run, pid is :%d\n", getpid());
    sleep(5);
    exit(1);
  }else{
    int status = 0;
    pid_t ret = 0;
    do{
      ret = waitpid(-1, &status, WNOHANG);//非阻塞式等待
      if(ret == 0){
        printf("child is running\n");
      }
      sleep(1);
    }while(ret == 0);
    if(WIFEXITED(status) && ret == pid){
      printf("wait child 5s success, child return code is :%d\n", WEXITSTATUS(status));
    }else{
      printf("wait child failed, return \n");
      return 1;
    }
  }
  return 0;
}
```

![mark](https://img.zouchanglin.cn///20200201/FLnGU53brkgo.png)

## 进程程序替换

用fork创建子进程后执行的是和父进程相同的程序(但有可能执行不同的代码分支)，子进程往往要调用一种exec函数以执行另一个程序。当进程调用一种exec函数时，该进程的用户空间代码和数据完全被新程序替换，从新程序的启动例程开始执行。调用exec并不创建新进程，所以调用exec前后该进程的id并未改变。

![mark](https://img.zouchanglin.cn///20200201/1ywmmR4KQODF.png)

### 替换函数

```c
#include <unistd.h>
int execl(const char *path, const char *arg, ...);
int execlp(const char *file, const char *arg, ...);
int execle(const char *path, const char *arg, ..., char * const envp[]);
int execv(const char *path, char *const argv[]);
int execvp(const char *file, char *const argv[]);
int execvpe(const char *file, char *const argv[], char *const envp[]);
```

这些函数如果调用成功则加载新的程序从启动代码开始执行，不再返回。
如果调用出错则返回一1
所以exec函数只有出错的返回值而没有成功的返回值。
这么多函数如何区分？

| 函数名 | 参数格式 | 是否带路径 | 是否使用当前环境变量     |
| ------ | -------- | ---------- | ------------------------ |
| execl  | 列表     | 不是       | 是                       |
| execlp | 列表     | 是         | 是                       |
| execle | 列表     | 不是       | 不是，需自己组装环境变量 |
| execv  | 数组     | 不是       | 是                       |
| execvp | 数组     | 是         | 是                       |
| execve | 数组     | 不是       | 不是，需自己组装环境变量 |

**只有execve才是真正的系统调用，其它五个函数最终都是调用execve**

![mark](https://img.zouchanglin.cn///20200201/m4XWQ6J4VVTm.png)

### 利用前面的知识写一个shell

shell的运行原理其实不难，就是从标准输入读入命令和命令参数然后开启一个子进程去执行这个程序，根据程序替换的原理，我们只要使用execve这个系统接口去把要执行的程序的代码段和数据段进行替换，便把一个磁盘上的程序加载到了内存中，变成了进程！此时，我们自己编写的shell变成了该进程父进程！

![mark](https://img.zouchanglin.cn///20200201/RpurV9196hq7.png)

主要分为以下几个步骤：
1、获取命令行
2、解析命令行
3、建立一个子进程（fork）
4、子进程程序替换（execvp）
5、父进程等待子进程退出（wait）

```c
#include <unistd.h>
#include <sys/wait.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>

char* argv[8];
int argc = 0;

void do_parse(char *buf){
  int i;
  int status = 0;

  for(argc=i=0;buf[i];i++){
    if(!isspace(buf[i]) && status == 0){
      argv[argc++] = buf+i;
      status = 1;
    }else if(isspace(buf[i])){
      status = 0;
      buf[i] = 0;
    }
  }
  argv[argc] = NULL;
}

void do_execute(void){
  pid_t pid = fork();
  switch(pid){
    case -1:
      perror("fork");
      exit(EXIT_FAILURE);
      break;
    case 0:
      execvp(argv[0], argv);
      perror("execvp");
      exit(EXIT_FAILURE);
    default:
      {
        int st;
        while(wait(&st) != pid);
      }
  }
}

int main(void){
  char buf[1024] = {};
  while(1){
    scanf("%[^\n]%*c", buf);
    do_parse(buf);
    do_execute();
  }
  return 0;
}
```

### 函数与进程之间的相似性能

exec/exit就像call/return
一个C程序有很多函数组成。一个函数可以调用另外一个函数，同时传递给它一些参数。被调用的函数执行一定的操作，然后返回一个值。每个函数都有他的局部变量，不同的函数通过call/return系统进行通信。这种通过参数和返回值在拥有私有数据的函数间通信的模式是结构化程序设计的基础。Linux鼓励将这种应用于程序之内的模式扩展到程序之间。如下图:

![](https://img.zouchanglin.cn///20200201/FRRpVmpfKQgL.png)

一个C程序可以fork/exec另一个程序，并传给它一些参数。这个被调用的程序执行一定的操作，然后通过exit(n)来返回值。调用它的进程可以通过wait (&ret)来获取exit的返回值。

### popen/system和fork的区别

#### system函数原型

```c
#include <stdlib.h>
int system(const char *command);
```

`system()`会调用`fork()`产生子进程，由子进程来调用`/bin/sh-c string`来执行参数string字符串所代表的命令，此命令执行完后随即返回原调用的进程。在调用`system()`期间`SIGCHLD`信号会被暂时搁置，`SIGINT`和`SIGQUIT`信号则会被忽略。
调用/bin/sh来执行参数指定的命令，/bin/sh 一般是一个软连接，指向某个具体的shell。

实际上`system()`函数执行了三步操作：

1. `fork`一个子进程；
2. 在子进程中调用`exec`函数去执行`command`；
3. 在父进程中调用`wait`去等待子进程结束。

返回值：

1. 如果`exec`执行成功，即`command`顺利执行，则返回`command` 通过 `exit`或 `return`的返回值。(注意 ：command 顺利执行不代表执行成功，当参数中存在文件时，不论这个文件存不存在，command 都顺利执行)
2. 如果`exec`执行失败，也即`command`没有顺利执行，比如被信号中断，或者`command`命令根本不存在， 返回 127
3. 如果 `command`为 `NULL`， 则 `system` 返回非 0 值.
4. 对于`fork`失败，`system()`函数返回-1。

#### popen()函数

创建一个管道用于进程间通信，并调用shell，因为管道被定义为单向的。所以 type 参数只能定义成只读或者只写, 不能是两者同时, 结果流也相应的是只读或者只写.
函数原型：

```c
#include <stdio.h>
FILE *popen(const char *command, const char *type);
int pclose(FILE *stream);
```

函数功能：popen()会调用fork()产生子进程，然后从子进程中调用/bin/sh-c来执行参数command的指令。这个进程必须由 pclose 关闭。

command参数：
command 参数是一个字符串指针, 指向的是一个以null结束符结尾的字符串, 这个字符串包含一个shell命令. 这个命令被送到 /bin/sh 以 -c 参数 执行, 即由 shell 来执行

type 参数 也是一个指向 以 null 结束符结尾的 字符串的指针
参数type可使用“r”代表读取，“w”代表写入。
依照此type值，popen()会建立管道连到子进程的标准输出设备或标准输入设备，然后返回一个文件指针。 随后进程便可利用此文件指针来读取子进程的输出设备或是写入到子进程的标准输入设备中。

返回值：
若成功则返回文件指针，否则返回NULL，错误原因存于errno中

#### 区别

1.system 在执行期间，调用进程会一直等待 shell 命令执行完成(waitpid)，但是 popen 无需等待 shell 命令执行完成就返回了。可以理解为，system为串行执行，popen 为并行执行。
2.popen 函数执行完毕后必须调用 pclose 来对所创建的子进程进行回收，否则会造成僵尸进程的情况。
3.popen 没有屏蔽 SIGCHLD ，如果我们在调用时屏蔽了 SIGCHLD ，如果在 popen 和 pclose 之间调用进程又创建了其他子进程并调用进程注册了 SIGCHLD 来处理子进程的回收工作，那么这个回收工作会一直阻塞到 pclose 调用。

### 参考：

[《调研popen/system, 理解这两个函数和fork的区别》](https://blog.csdn.net/xiaodu655/article/details/79717623)
[《popen/system, 理解这两个函数和fork的区别》](https://blog.csdn.net/yu876876/article/details/80319075)

进程相关的系统调用

重新认识HashMap

## 变量的定义位置

先上一段看来比较正常的代码：

```c
#include <stdio.h>
#include <stdlib.h>

int main(void){
	printf("Tim\n");
	int a = 10;
	printf("a = %d\n",a);
	system("pause");
	return 0;
}
```

 由于我的环境是VisualStudio2013，所以上述程序可以完美执行，并且是编译0警告通过，但是在VisualStudio2008的环境下这样写是完全错误的，C89规定，在任何执行语句之前，在块的开头声明所有局部变量。但是在C99以及C++中则没有这个限制，即在首次使用之前，可在块的任何位置都可以声明变量。例如下面的写法对于C89标准才是正确的： 



```c
#include<stdio.h>
#include<stdlib.h>

int main(void){
	printf("sssssssss\n"); 
	{
		int a = 10;
		printf("a = %d\n", a);
	}

	system("pause");
	return 0;
}
```

当然为了达到更好兼容性，建议都把局部变量写在代码块的开始位置！！

## define与typedef

1、函数式宏定义的参数没有类型，预处理器只负责做形式上的替换，而不做参数类型检查，所以危险性高；但因为省去了函数的调用，返回，释放，所以效率比自定义函数高；
2、调用真正函数的代码和调用函数式宏定义的代码编译生成的指令不同。
如果MAX是个普通函数，那么它的函数体return a > b ? a : b; 要编译生成指令，代码中出现的每次调用也要编译生成传参指令和call指令。而如果MAX是个函数式宏定义，这个宏定义本身倒不必编译生成指令，但是代码中出现的每次调用编译生成的指令都相当于一个函数体，而不是简单的几条传参指令和call指令。所以，使用函数式宏定义编译生成的目标文件会比较大。
3、在执行复杂功能时，如递归，函数式宏定义往往会导致较低的代码执行效率。
尽管函数式宏定义和普通函数相比有很多缺点，但只要小心使用还是会显著提高代码的执行效率，毕竟省去了分配和释放栈帧、传参、传返回值等一系列工作，因此那些简短并且被频繁调用的函数经常用函数式宏定义来代替实现。

①define定义符号

```c
#define MAX 100
```



②定义比较长的关键字

```c
#define reg register
```



③用更加形象的的符号替代另一种实现

```c
#define do_forever for( ; ; )
```



④在写switch语句的时候自动把break加上

```c
#define CASE break;case
```



⑤打印日志

```c
#define DEBUG_PRINT >printf(“file:%s\tline:%d\tdate:%s\ttime:%s\n”,FILE,_LINE__,DATE,TIME)
```



使用宏时候的提示：所有对于数值表达式求值得宏定义都应该用这种方式加上括号，避免在使用宏的时候由于参数中的操作符之间不可预料的相互作用。

## define 替换

在程序中扩展#define定义符号和宏时，需要涉及几个步骤。
在调用宏时，首先对参数进行检查，看看是否包含任何由#define定义的符号。如果是，它们首先被替换。
替换文本随后被插入到程序中原来文本的位置。对于宏，参数名被他们的值替换。
最后，再次对结果文件进行扫描，看看它是否包含任何由#define定义的符号。如果是，就重复上述处理过程。
注意：
宏参数和#define 定义中可以出现其他#define定义的变量。但是对于宏，不能出现递归。
当预处理器搜索#define定义的符号的时候，字符串常量的内容并不被搜索。



## #与##

使用”#”把宏参数变成对应的字符串

```c
#define PRINT(FORMAT, VALUE)\ printf("the value of "#VALUE" is "FORMAT"\n", VALUE) 
int main(void){
	//这里只有当字符串作为宏参数的时候才可以把字符串放在字符串中 
	PRINT("%d", 5 + 10); 
	system("pause"); 
	return 0; 
}
```

 “##”可以把位于它两边的符号合成一个符号。
它允许宏定义从分离的文本片段创建标识符。
注意：这样的连接必须产生一个合法的标识符。否则其结果就是未定义的。
接下来说说宏与函数
宏通常被应用于执行简单的运算。比如在两个数中找出较大的一个： 

```c
#define GET_MAX(a,b) a>b?a:b
```

用于调用函数和从函数返回的代码可能比实际执行这个小型计算工作所需要的时间更多。所以宏比函数在程序的规模和速度方面更胜一筹。
更为重要的是函数的参数必须声明为特定的类型。所以函数只能在类型合适的表达式上使用。反之这个宏怎可以适用于整形、长整型、浮点型等可以用于来比较的类型。宏是类型无关的

和函数相比宏的缺点
每次使用宏的时候，一份宏定义的代码将插入到程序中。除非宏比较短，否则可能大幅度增加程序的长度。
宏是没法调试的。
宏由于类型无关，也就不够严谨。
宏可能会带来运算符优先级的问题，导致程容易出现错
宏的其他注意事项:宏可以传类型，但是函数不行

```c
#define _CRT_SECURE_NO_WARNINGS 
#include<stdio.h> 
#include<stdlib.h> 
#define MALLOC(num, type)\ (type *)malloc(num * sizeof(type))
int main(void)
{
 	 int* p = MALLOC(3, int);
 	 system("pause"); 
 	 return 0; 
}
```

 带副作用的宏参数 

```c
#define MAX(a,b) ((a)>(b)?(a):(b))
int main(int argc,char** argv)
{
	int a = 5; 
	int b = 8;
 	int z = MAX(a++,b++); 
	printf("a=%d b=%d z=%d\n",a,b,z);
}
```

上例就说明了带副作用的宏参数的危害
有时不把宏写成全部大写，是为了让别人把它当做函数理解

函数和宏的对比 

|     属性     | #defien宏                                                    | 函数                                                         |
| :----------: | :----------------------------------------------------------- | :----------------------------------------------------------- |
|   代码长度   | 每次使用时，宏代码都被插入到程序中，除了非常短的宏之外，程序的长度将大幅度增长 | 函数代码只会出现在同一个地方，每次使用这个函数时都会调用这段代码 |
|   执行速度   | 更快                                                         | 存在函数弹栈、压栈的开销                                     |
| 操作符优先级 | 宏参数的求值实在所有周围表达式的上下文环境里，除非它们加上括号，否侧邻近操作符的优先级可能会产生不可预料的后果 | 函数参数只在函数调用时求值一次，它的结果值将传递给函数，表达式的求值很容易预测 |
|   参数求值   | 参数每次用于宏定义时， 它们都将重新求值，具有副作用的参数可能会产生不可预料的结果 | 参数在函数调用前只求值一次，在函数中多次使用参数并不会带至多种求值过程，参数的副作用并不会造成任何的问题 |
|   参数类型   | 宏与类型无关，只要对参数的操作是合法的，它可以适用于任何参数类型 | 函数参数与类型有关，如果参数的类型不同，就需要使用不同的函数，即使它们的逻辑任务是相同的 |
|     调试     | 宏在预处理阶段就已经替换，所以无法执行调试                   | 函数是可以调试的                                             |
|     其他     | 宏不具备函数的性质，不能递归                                 | 函数可以递归                                                 |

## 浮点数与其他数字的比较

C语言中浮点数同0不能直接用\=\=比较，只能看浮点数与0值的误差，原因如下：float是浮点数，存的是近似值，当用来表示0的时候，有可能计算结果是0，但是由于精度问题，实际上存储的是一个和0很接近的值，而\=\=做判断的话只要不是完全相等就返回假，所以用==判断float有可能出错。

## 数组越界问题

下面一段程序：

```c
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

int main(void){
	long i;
	long arr[10];
	for (i = 0; i <= 12; i++){
		arr[i] = 0;
		printf("hehe\n");
	}
	system("pause");
	return 0;
}
```

看起来只是一个数组越界访问的问题，但是会引起死循环， 

![mark](https://img.zouchanglin.cn///20200201/yrvcxkTGIj5m.png)

## 字符究竟是什么样的整数

我们需要把一个字符值转换为一个较大的整数的时候，这个问题才变得重要起来。而在其他情况下，结果都是已经定义：多余的位将简单的被“丢弃”丢弃编译器在将char类型为int类型的时候，需要做出选择：应该将字符作为有符号整数还是应该是无符号整数处理？如果是前一种情况，编译器在将char类型的数扩展到int类型时，应该同时赋值符号位，如果是后一种情况，编译器只需要在多余的位上用0填充即可。

如果说一个字符的最高位是1，编译器是将该字符当成是有符号数还是当做无符号数呢？这个选择非常重要，它决定着一个8字符的取值范围是从-128到127还是从0到255.而这一点，又会反过来影响到程序员岁哈希表或者转换表的设计方式。

如果编程者最关注的一个高位是1 的字符其数值究竟是正还是负，可将字符声明为无符号字符（unsigned char）。这样无论什么编译器将该字符转换为整数的时候只需要多余的位填充为0即可，而如果声明为一般的字符变量，那么有些编译器上可能会作为有符号处理，而另一些编译器又会作为无符号数处理。
与此相关的一个常见错误认识是：如果c是一个字符变量，使用（unsigned ）c就可以得到与c等价的一个无符号整数，但是这是会失败的，因为将字符c转化为无符号整数时，c将首先被转化为一个int型整数，因此可能会得到一个非预期的结果。

下面说说正确的方式：使用（unsigned char） c ，因为一个unsigned char 类型的字符在转化为无符号整数时无需首先转化为int型整数，而是直接进行转换。
接下来再说说getchar()函数，先看下面一段代码：

```c
#include<stdio.h>

int main(void){
        char c;
    while ((c = getchar()) != EOF){
        putchar(c);
    }
    return 0;
}
```

这个程序表面上是把标准输入复制到标准输出，实则不然，原因是c被声明为char类型，而getchar（）的返回值是int类型，这意味着c可能无法容纳下所有可能的字符，特别是可能无法容纳EOF，但是还好在VS下的EOF是-1

使用char类型的变量去接收返回值为int型的结果，最终会有3种可能：

1、某些合法的字符被截断后使得c的取值与EOF相同，这样的话程序将在赋值文件的过程中就终止；

2、c根本不可能取到EOF这个值，那么程序将陷入死循环；

3、程序会正常工作，但完全是因为巧合，尽管getchar()的返回值赋值给c的时候会发生截断，尽管while语句中比较运算符的操作数不是getchar()的返回值，而是截断后的值c。然而令人惊讶的是许多编译器对上述表达式的实现并不正确。这些编译器确实对getchar()的返回值做了截断处理，并把低端字节部分赋值给了变量c。但是它们在表达式中并不是比较c与EOF的值，而是比较getchar()函数的返回值与EOF，如果编译器采用的是红色字段的方法，那么程序完全可以正常运行！

## 求平均数的正确姿势

当然这个就不单单是c语言的坑了，其他语言中也会出现！比如我们现在要写一个二分查找的代码，好吧，我承认这段代码大家都能写出来，可是….谁会写出没BUG的那种？

```c
int binary(int[] arr, int date, int length){
	int min = 0;
	int max = length - 1;
	int mid = 0;

	while(min <= max){
		mid = (min + max)/2;
		if(arr[mid] > data){
			max = mid - 1;
		}else if(arr[mid < data]){
			min = mid + 1;
		}else{
			return mid;
		}
	}
	return -1;
}
```

很多人可能一上手就写出这种代码了，很明显这是非常容易出现Bug的程序，问题就出在第七行,在min和max很大的时候会出现数据溢出，从而导致程序出错。第一篇二分搜索论文在1946年发表，但是这个错误直到1962年才被发现，中途用了16年的时间才发现并且纠正了错误！

错误很明显，但是怎么改进呢？
方法一：加法变减法

```c
int binary(int[] arr, int date, int length){
	int min = 0;
	int max = length - 1;
	int mid = 0;

	while(min <= max){
		mid = min + (max - min)/2;
		if(arr[mid] > data){
			max = mid - 1;
		}else if(arr[mid < data]){
			min = mid + 1;
		}else{
			return mid;
		}
	}
	return -1;
}
```

 方法二：位运算求平均数 

```c
int binary(int[] arr, int date, int length){
	int min = 0;
	int max = length - 1;
	int mid = 0;

	while(min <= max){
		//此处注意：>> 是右移, >>> 是无符号右移
		mid = min + ((max - min) >>> 1)/2;
		if(arr[mid] > data){
			max = mid - 1;
		}else if(arr[mid < data]){
			min = mid + 1;
		}else{
			return mid;
		}
	}
	return -1;
}
```

插入排序

基本思想

进程创建

fork&vfork

变量的定义位置

现代计算机体系结构

冯·诺依曼结构

存储设备对比