七、其他内容

这里包含了一些C语言的其他内容
包含:宏、大程序建立、位和位运算、可变数组、链表
这一部分比较多而杂,建议妥善选取所需

全局变量

定义在函数外面的变量是全局变量

基本介绍

全局变量具有全局的生存期和作用类
它们与任何函数都无关，在任何函数内部都可以使用它们

初始化

没有初始化的全局变量会得到0值，而指针会得到NULL值
只能用在编译时刻，已知的值来初始化全局变量
它们的初始化发生在main函数之前

Tips:
即使是 

1
2
int gAll = 12 ; 
int g2 = gAll ;

也会被认为是“用编译时未知的值初始化”

但是，如果已经保证了该变量不会变化(即是const)，就可以通过编译 

1
2
const int gAll = 12 ; 
int g2 = gAll ;

但是，不建议一个全局变量和另外一个全局变量联系

隐藏全局变量

如果在函数内部存在与全局变量同名的变量，则全局变量会被隐藏
或者说，在“更小的范围内”重新定义了同名的变量，“更大范围中”的变量会被隐藏

允许在更小的地方重新定义一个定义过的变量

静态本地变量

在本地变量定义的时候加上static修饰符即可让它成为静态本地变量

简介

当函数离开的时候，静态本地变量会继续存在并保持其值
静态本地变量的初始化只会在第一次进入这个函数时进行
在之后进入函数会保持上次离开时的值

静态本地变量实际上是特殊的全局变量

它们是位于相同的内存区域的
静态本地变量具有全局本地的生存期，函数内的局部作用域

静态本地变量 = 全局生存期+局部作用域

贴士

返回的本地变量的地址是危险的
返回的全局变量/静态本地变量的地址是安全的

返回在函数内的malloc的内存是安全的，但容易造成问题
最好的做法是返回传入的指针

不要使用全局变量来在函数间传递参数和结果
尽量避免使用全局变量

使用全局变量和静态本地变量的函数是线程不安全的

宏定义

编译预处理指令

以#开头的是编译预处理指令
它们不是C语言的成分，但是C语言程序离不开它们
使用#define来定义一个宏
注意，后面不用接上分号
绝对不能加分号，在替换后及其容易影响到代码

<符号的名字> <符号的值>```，比如
1
2
3
4
5
6
7
8
9
10
11
12
13
```#define PI 3.14159```

```#define```所做的就是最原始的“替换”   
也就是在预处理的时候，把下面代码中的<符号的名字>全部替换为<符号的值>    
> 在C语言的编译器还是编译之前，编译预处理程序(CPP)会把程序中的名字换成值
> 是完全的文本替换
名字必须是一个单词，而值可以是各种东西  

### 使用
如果一个宏的值中有其他宏的名字，也是会被替换的  
如果一个宏的值超过一行，最后一行之前的行末需要加```\```表示下一行仍然是该宏的值  
宏的值后面出现的注释不会被当作宏的值的一部分

#define PI 3.14
#define PI2 2*PT //这里是注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
最终的结果会变成    把PI2变成2*3.14 

#### 没有值的宏
```#define _DEBUG```
这类宏是用于条件编译的，后面有其他的编译预处理指令来检查这个宏是各已经被定义过了    


## 带参数的宏   

### 例子
```#define cube(x) ((x)*(x)*(x))```
举个例子，此时我们写:
```c
#define cube(x) ((x)*(x)*(x)) 
int main(){
    printf("%d \n" , cube(5)) ; 
    
    return 0 ;
}

此时对于cube(5)，在过程中有以下变化
cube(5)->((5)*(5)*(5))->75

即最后打印出来的结果是75

在书写这类宏的时候，要非常注意书写的值，小括号的使用
要考虑代码中其替换后的结果
要避免失误的情况,一般要参照”带参数的宏的原则”来书写

带参数的宏的原则

一切都要括号
整个值最终使用一个括号
参数出现的每个地方都有括号

补充

带参数的宏也可以带多个参数
也可以组合/嵌套来使用其他宏

小结

带参数的宏在大型程序的代码中使用普遍，可以以空间换取效率
宏是没有任何类型检查的
部分宏会被inline函数来替代

大程序

一个main()太长了时候分为多个函数
一个源代码文件太长了时候分成几个文件

项目:多个源文件合一

我们可以通过新建项目的方式，来组合多个源代码来使用

新建项目与添加

我们分别写下两个源文件

text01.c

1
2
3
4
5
6
7
8
9
int max(int a , int b) ; 

int main(void){
    int a = 5 ; 
    int b = 6 ; 
    printf("%d \n" , max(a,b));

    return 0 ;
}

theMax.c

1
2
3
int max(int a, int b){
    return a>b?a:b ; 
}

然后新建-项目，如下建立项目

新建后会自动生成一个main.c视情况使用

然后在项目中添加.c文件(即上文两个文件)

然后对项目进行编译-运行，即可正常使用

对于项目，Dev C++的编译会把一共项目中的所有源代码都编译之后，连接起来

有的IDE有分开的编译和构建两个按钮，前者是对单个源代码文件的编译，后者是对整个项目的编译

有一个.c文件是一个编译单元，编译器每次编译只处理一个编译单元

头文件

把函数原型放到一个头文件(.h结尾)中，在外面需要调用这个函数的源代码文件(.c文件)的时候
外面使用#include <头文件>，如此一来就能让编译器在编译的时候知道函数的原型

使用

新建一个新的源文件，写入
int max(int a , int b) ;
随后命名为theMax.h,此时的test01即可修改为 

1
2
3
4
5
6
7
8
9
10
#include <stdio.h>
#include "theMax.h"

int main(void){
    int a = 5 ; 
    int b = 6 ; 
    printf("%d \n" , max(a,b));

    return 0 ;
}

编译成功

#include

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
它的作用是，**把对应文件的全部文本内容原封不动地插入到它在的地方**  
所以，也不一定要在```.c```文件的最开头写下```#include <>```   

##### 使用形式
使用``` "" ```或者 ```<>``` 来指出要插入的文件  
``` "" ``` 要求编译器首先在当前目录寻找这个文件，若没有，再去编译器指定的目录寻找   
```<>```  让编译器只在指定的目录寻找

> 编译器知道自己的标准库的头文件在哪里
> 环境变量和编页码命令行参数也能指定寻找头文件的目录    

\#include并非是引入库的，它只做插入 
现在的C语言编译器默认会引入所有标准库   
例如```#include <stdio.h>```是为了让编译器知道```printf```函数的原型，来保证你调用时给出的参数值是正确的类型    

在使用和定义某个函数的地方都应该\#include这个头文件 
> 一般的做法就是任何.c都有对应的同名.h文件，把所有对外公开的函数的原型和全局变量的声明都放进去  

> 全局变量，也是可以在多个.c中共享的

#### static 
在函数前面加上```static```就使得它成为只能在所在编译单元中被使用的函数  
在全局变量前面加上```static```参数就可以使得它成为只能在所在的编译单元中被使用的全局变量    

## 声明
需要有一个**声明**来表示项目的某处有某个变量    

### 声明全局变量    
使用```extern```关键字来表示“在某个位置，会有这么一个全局变量”  
比如如下修改刚才的三个文件: 

test01:
```c
#include <stdio.h>
#include "theMax.h"

int main(void){
    int a = 5 ; 
    int b = 6 ; 
    printf("%d \n" , max(a,gALL)); //将b改成了gALL这个全局变量

    return 0 ;
}

theMax.c

1
2
3
4
5
6
7
#include "theMax.h"

int gALL = 12 ;//这里加入了一个全局变量gALL

int max(int a, int b){
    return a>b?a:b ; 
}

theMax.h

1
2
int max(int a , int b) ; 
extern int gAll ; //使用extern关键字

定义与声明

在C语言中，定义与声明是两个不同的东西

i ; ```是变量的定义
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
```extern int i  ; ```是变量的声明  

定义是产生代码的东西    
> 函数，全局变量    

声明是不产生代码的东西  
> 比如 函数原型，变量声明，结果声明，宏声明，枚举声明，类型声明，inline函数 

只有声明可以被放到头文件中  
> 是一个默认的规则，在头文件中进行定义容易出错  

在头文件中定义很容易造成一个项目中多个编译单元里有重名的实体    

> 某些编译器允许几个编译单元中存在同名的函数，或者用weak修饰符来强调这些存在    

同一个编译单元，同名的结构不能被重复声明    
利用标准头文件，可以防止这种情况发生    

#### 标准头文件

#ifndef XXX
#define XXX
…
…

#endif

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

```#ifndef XXX```:如果没有定义过XXX

> 运用条件编译和宏，保证这个头文件在一个编译单元中只会被#include一次    
> #program once 也能起到相同的作用，但并非所有编译器都支持  

## 格式化输入输出
我们之前在```printf```和```scanf```中曾经设法规定其输入输出形式，实际上即   

***printf** 
```%[flags][width][.prec][hlL]type```   

**scanf**   
```%[flag]type```   

### printf
```%[flags][width][.prec][hlL]type```   
使用```[flags]```，有以下可填:    
```-```:左对齐。不加就是右对齐  
```+```:在前面放+或-，强制输出加号      
```(space)```:整数留空  
```0```:0填充   


使用```[width]以及[.prec]```，可填: 
```<数字>```:最小字符数，整个输出占据的位置 
``` * ```:下一个参数是字符数    
```.<数字>```:小数点之后的位数  
``` .* ```:下一个参数是小数点后的位数   
比如
9.2f:一共占据九个位置，其中小数点后占据两个位置 
```printf("%*d \n",6,123) ; ``` 一共有**6**位字符，值为**123**也就是说第一位参数规定了这个地方的输入数目      

使用```[hlL]```来进行修饰，可填:    
```hh```:单个字节   
```h```: short  
```l```:long    
```ll```:long long  
```L```:long double 

#### type类型(printf)   
这部分比较多，因此单独列出  
i/d :用于int    
u : unsigned int 
o:八进制    
x:十六进制  
X：字母大写的十六进制   
f/F:float,6 
e/E:指数    
g/G:float   
a/A:十六进制浮点数  
c:char  
s:字符串    
p:指针  
n:读入/写入的个数   

### scanf   
使用```[flags]```，有以下可填:    
``` * ```:跳过  
``` <数字> ```：最大字符数  
``` hh ```: char    
``` h ``` : short   
``` l ``` : long/double 
``` ll ```：long long   
``` L ``` :long double  

#### type类型(scanf)    
d : int 
i ：整数，可能为十六进制，可能为八进制 
u : unsigned int    
o ：八进制  
x ：十六进制    
a,e,f,g: float  
c : char    
s : 字符串(单词)   
p : 指针 
[...] :所允许的字符 

### printf和scanf的返回值   
printf:读入的项目处 
scanf:输出的字符数  

> 在要求严格的程序中，应该判断每次调用scanf或printf的返回值，从而了解程序运行中是否存在问题 

## 文件输入输出 

### 重定向: 输入<  ,  输出>    
在终端，可以利用```>``` 和 ```<``` 作重定向输入输出 
不过一般情况还是使用```FILE```来进行重定向  

### FILE    
```FILE* fopen(const char* restrict path , const char* restrict mode);```   
```int fclose(FILE *stream);```
```fscanf(FILE* , ...)``` 
```fprintf(FILE*,...)```  

#### 打开文件的标准代码 
```C
FILE* fp = fopen("file" , "r");  //第一个参数是文件名，第二个参数是表明我们打开它是为了读

if(fp) { //判断是否成功打开
    fscanf(fp,...) ; //第一个参数是指向代表文件的指针，后面的参数同scanf    
    fclose(fp) ;  //关闭
}else{
    ....
}

fopen的第二个参数
r:打开，只读
r+:打开读写，从文件头开始
w:打开，只写。若不存在则新建，若存在则清空
w+:打开读写。若不存在则新建，若存在则清空
a:打开追加。若不存在则新建，若存在则从文件尾开始
..x:在上述符号的后面可以加上该符号。只新建，如果文件已存在则不能打开(一般加在w/a后面，可以避免对已有的文件可能的破坏)

二进制文件

所有文件的最终都是二进制文件
二进制文件是需要专门的程序去读写的文件
文本文件的输入输出是格式化，可能经过转码

背景

Unix喜欢使用文本文件夹来做数据存储和程序配置，交互式终端的出现使得人们喜欢用文本和计算机来交互
Unix的shell提供了一些读写文本的小程序

而windows喜欢用二进制文件，PC刚开始的时候能力有限，DOS的能力更有限
二进制更接近底层

文本：
方便人类读写、跨平台
程序的输入输出要经过格式化，开销大

二进制：
人类读写困难，不跨平台(比如int大小不一致)
优点是程序读写快

程序与文件

配置：Unix使用文本，windows使用注册表(一个非常大的二进制文件)
数据：稍微比较有点量的数据均放在数据库中
媒体：只能是二进制的

事实上，程序通过第三方库来读写文件，很少直接读写二进制文件了

二进制读写

二进制读
size_t fread(void *restrict ptr , size_t size, size_t nitems , FILE *restrict stream) ;

二进制写
size_t fwrite(const void *restrict ptr , size_t size,size_t nitems , FILE* restrict stream)

第一个参数是要读写的内存，第二个参数是这块内存的大小，第三个参数是有多少个这样的内存，最后一个参数是文件指针
返回的是成功读写的字节数

对二进制文件的读写一般是通过对一个结构变量的操作来进行的,nitem用来说明这次读写的几个结构变量

在二进制文件中定位

long ftell(FILE *stream) ;
int fseek(FILE *stream , long offest , int whence);

SEEK_SET:从头开始
SEEK_CUR:从当前位置开始
SEEK_END:从尾开始(倒着来)

可移植性

在这种情况下写出的文本不具有可移植性

比如在int为32位的机器上写成的数据文件，就无法在int为64位的机器上正确读出

解决方案之一是放弃int,而是使用typedef具有明确大小的类型
更好的方案是使用文本

换位运算

换位运算符

C语言有这些按位运算符 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
```|```：按位的或   
```~```：按位的取反 
```^```：按位的异或 
```<<```：左移
```>>```：右移  
下文若无特殊表述，均是位运算    

#### 按位与
若```x==1,y==1```,(x&y) = 1 ; 否则(x&y) = 0   
常被用于两种应用:
1.让某一位或某些位为0，如: x & 0xFE  
> FE:1111 1110，它可以使得某一个数的最低位变成0  
2.取某一个数中的一段: x & 0xFF  
> FF:1111 1111,使和FE进行按位与的部分皆被保存     

#### 按位或
若```x==1```,或```y==1```，那么就有(x|y) = 1 , 否则才有(x|y) = 0    
常被用于两种应用:   
1.使得一位或者几个位为1，如：x | 0x01   
2.把两个数相拼接，如: 0X00FF | 0XFF00 ,结果就是0XFFFF   

#### 按位取反    
把1位变成0，0位变成1    
想要得到全部位为1的数，使用```~0``` 

#### 按位异或
在C中，没有表示幂次的运算符，```^```表示按位异或    
若```x==y```,那么有(x^y) = 0  
否则，(x^y) = 1
> 如果两个位相等，结果为0；不相等，结果为1  

> 对同一个变量，连续使用另一个相同的变量连续异或两次，则等于没做    

> 上述那一条可以做一个非常非常弱的加密运算↑

### 逻辑运算与按位运算  
在逻辑运算中，实质上它只看到两个值：0和1    
可以认为逻辑运算相当于把所有非0值都变成1，然后做按位运算    
5&4 ->4
5&&4 -> 1&1 ->1
>实际上，在计算机中，我们只有按位运算，而没有逻辑运算   

## 移位运算 

### 左移    
i << j 
把i中所有的为都向左移动j个位置，而右边填入0     
所有小于int的类型，移位使用int的方式来做，结果也是int   
$x <<= 1$ 等价于 $x *= 2 $  (<<=表示<<1 后的结果，类比x+=2这种形式)    
$x <<= n$ 等价于 $x *= 2^n$ 
对于二进制而言,左移了一位自然是等价于数值的翻倍

### 右移
i >> j 
i中所有的位向右移j位    
所有小于int的类型，移位以int的方式来做，结果是int   
对于```unsigned```类型，左边填入0   
对于```signed```类型，左边填入原来的最高位(保持符号不变)    
> 也就是说，此时有符号和无符号是不一样的    

$x >>= 1$ 等价于 $x /= 2 $      
$x >>= n$ 等价于 $x /= 2^n$ 

另外，移位的位置不要使用负数，这是没有定义的行为    

## 位运算例子和位段   
> 该部分比较简略，若想了解请参考翁恺老师的13.2-3位运算例子和12.2-4位段    
> 或者，直接刷相关的题目，能更好地理解  

例子:输出一个数的二进制 
```C
#include <stido.h>
int main(int argc , char const *argv[]){
    int number ; 
    scanf("%d" , &number) ; 
    unsigned mask = lu<<31 ; 

    for( ; mask ; mask >>=1 ){
        printf("%d" ， number &mask?1:0);
    }
    printf("\n") ; 

    return 0 ;
}

我们可以把一个int的若干位都合成一个结构 

1
2
3
4
5
6
struct {
    unsigned int leading : 3 ; 
    unsigned int FLAG1: 1 ;
    unsigned int FLAG2: 2 ;
    int trailing: 11 ;
};

每一个成员的后面，有一个:,其后面的数字表示一个成员占几个比特

定义位段之后，可以用位段的成员名称来访问
比移位、与、或还方便
编译器会安排其中位的排列，不具有可移植性
当所需的位超过一个int时候会采用多个int

制作可变数组

Interface

我们先如下考虑，我们需要这些函数来实现我们的要求：

array_create(int init_size);``` 创建这个数组
1
2
3
4
5
6
7
8
9
10
11
12
13
```void array_free(Array *a);``` 回收数组空间    
```int array_size(const Array *a);```得到数组大小   
```int* array_at(Array *a , int index);```获得某个单元、可读可写  
```void array_inflate(Array *a , int more_size);```让数组扩大 

### 基础    
首先定义一个结构表示该数组  
创建```array.h```:  
```c
typedef struct {
    int *array ; 
    int size ;
} Array;

按照要求定义整体头文件如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#ifndef _ARRAY_H_
#define _ARRAY_H_

typedef struct {
    int *array ; 
    int size ;
} Array;

Array array_create(int init_size);
void array_free(Array *a);
int array_size(const Array *a);
int* array_at(Array *a , int index); 
void array_inflate(Array *a , int more_size);

#endif

随后使用一个array.c来进行函数的实现 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
```c
#include "array.h"

// typedef struct {
//     int *array ; 
//     int size ;
// } Array;

Array array_create(int init_size){
    Array a ;
    a.size = init_size ; //通过输入的值来确定大小
    a.array = (int*)malloc(sizeof(int)*a.size) ; //根据大小来分配空间
    return a ; //注意，返回的是a本身而非指针
    //事关本地变量、指针的周期等等，若返回指针会导致失效
    //这一部分可以再看看指针那一块
}

void array_free(Array *a){
    //做两件事情，释放对应的空间+保险起见把size改为0
    free(a->array) ;
    a->array = NULL ; 
    a->size = 0;
}

int array_size(const Array *a);
int* array_at(Array *a , int index); 
void array_inflate(Array *a , int more_size);

可变数组的数据与访问

对于得到数组大小这件事，我们实际上由两种做法
一是直接得到，也就是说a.size
第二种就是我们下面要做的，也就是封装，这样可以保护a.size

书接上文:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "array.h"

// typedef struct {
//     int *array ; 
//     int size ;
// } Array;
Array array_create(int init_size);
void array_free(Array *a);

int array_size(const Array *a){
    return a->size ; //通过指针来访问到该数组，随后得到size
}

int* array_at(Array *a , int index){
    //注意，这里拿的返回值是一个指针    
    return &(a->array[index]);
    //为什么返回指针:因为如果返回的是指针，可以方便赋值
}
//当然，类似的，我们还可以写下以下类似的方法:

int array_get(const Array*a , int index){
    return a->array[index];
}

void array_set(Array *a , int index , int value){
    a->array[index] = value ;
}
//用两个分别的get和set，达到了目的  

void array_inflate(Array *a , int more_size);

可变数组自动增长

来到了最重要的部分了
逻辑是：重新申请一块新的空间，该空间大小是旧空间+新空间：
int *p = (int\*)malloc(sizeof(int)(a->size + more_size));
接下来，我们需要利用循环来把旧的内容赋值到新的空间去： 

1
2
3
4
int i ; 
for(i = 0 ; i < (a->size) ; i++){
    p[i] = a->array[i] ; 
}

接下来是最终的处理，释放空间+转移：

1
2
3
free(a->array) ; 
a->array = p ;
a->size += more_size ;

最终的函数如下:

1
2
3
4
5
6
7
8
9
10
11
void array_inflate(Array *a , int more_size){
    int *p = (int\*)malloc(sizeof(int)(a->size + more_size));
    int i ; 
    for(i = 0 ; i < (a->size) ; i++){
        p[i] = a->array[i] ; 
    }

    free(a->array) ; 
    a->array = p ;
    a->size += more_size ;
}

一般是在进行array_at的时候会检测是否越界
那么我们在此处加入判断并中需要的时候加入自动增长 

1
2
3
4
5
6
int* array_at(Array *a , int index){
    if(index >= a->size){
        array_inflate(a,index-(a->size)+1); //这样子是刚刚好会增长一位
        //当然，我们也可以引入block的概念，每次需要的时候增长x位
    }
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <stdio.h>
#include <stdlib.hs>
#include "array.h"

// typedef struct {
//     int *array ; 
//     int size ;
// } Array;

Array array_create(int init_size){
    Array a ;
    a.size = init_size ; //通过输入的值来确定大小
    a.array = (int*)malloc(sizeof(int)*a.size) ; //根据大小来分配空间
    return a ; //注意，返回的是a本身而非指针
    //事关本地变量、指针的周期等等，若返回指针会导致失效
    //这一部分可以再看看指针那一块
}

void array_free(Array *a){
    //做两件事情，释放对应的空间+保险起见把size改为0
    free(a->array) ;
    a->array = NULL ; 
    a->size = 0;
}

int array_size(const Array *a){
    return a->size ; //通过指针来访问到该数组，随后得到size
}

int* array_at(Array *a , int index){
    if(index >= a->size){
        array_inflate(a,index-(a->size)+1); //这样子是刚刚好会增长一位
        //当然，我们也可以引入block的概念，每次需要的时候增长x位
    }
}
//当然，类似的，我们还可以写下以下类似的方法:

int array_get(const Array*a , int index){
    return a->array[index];
}

void array_set(Array *a , int index , int value){
    a->array[index] = value ;
}
//用两个分别的get和set，达到了目的 

void array_inflate(Array *a , int more_size){
    int *p = (int\*)malloc(sizeof(int)(a->size + more_size));
    int i ; 
    for(i = 0 ; i < (a->size) ; i++){
        p[i] = a->array[i] ; 
    }

    free(a->array) ; 
    a->array = p ;
    a->size += more_size ;
}

可变数组的缺陷

有两个比较重要的缺陷：
1.每次在扩增的时候都有一个copy的过程，随着数据的增多，这部分的开销就会越来越大
2.可能在在内存还足够的时候发生申请空间失败的情况
如果将想法改为不拷贝，但是链接各个部分来进行扩增，就可以避免这种情况，那就是链表

实现链表

该部分算比较基础的数据结构了

理论

把一块单元分为两个部分，第一个部分是该数据，第二部分是指针(该指针指向下一位)

一个“这样的单元”被称为“结点”
在最后一个数据，其指针指向“结束”
同时，还需要一个指针指向该链表的头

实现

首先是这样的结构 

1
2
3
4
5
6
7
8
9
10
#ifndef _NODE_H_
#define _NODE_H_

typedef struct _node{
    int value ; s
    struct _node *next ; 
    // 不能在这李写 Node *next ; 因为此时"Node"还没出现 
}Node ;

#endif

最开始的部分，指向我们的第一个数据的指针 ,p,需要手动得出：

1
2
3
Node *p = (Node*) malloc(sizeof(Node)) ; 
p->value = number ; //这里的number是一个传进来的值  
p->next = NULL ; //目前这个链表就一个数据，因此p既是头也是尾,next指向NULL

那么我们想添加一个值该如何处理呢，首先应该先找到当前的最后一个指针 

1
2
3
4
5
6
Node *last = head ; //这里=head一是为了初始化，二是那些只有一个元素的情况

while(last->next){
    //(last->next)的意思是当last->next有东西，即不为NULL的时候，就一直执行
    last = last->next ; //不断更新
}

然后是增加新的数据:

1
2
3
4
5
Node *q = (Node*) malloc(sizeof(Node)) ; 
q->value = number ; //这里的number是一个传进来的值  
q->next = NULL ; 

last->next = p ;

last是NULL的情况

如果last == NULL,则代码的执行会出现问题。所有最终，添加一个元素/新建一个链表的操作如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Node *p = (Node*)malloc(sizeof(Node)) ; 
p->value = number ; 
p->next = NULL ;

//寻找last
Node *last = head ; 

if(last){
    while(last -> next) {
        last = last->next ; 
    }

    //连接
    last->next = p
}else{
    head = p;
    //如果p是第一个元素，此时要让p被加到head指向的地方，而非last指向的地方
}

链表的函数

增加元素

首先把之前的操作变成一个函数

注意一个问题:

子函数访问的是地址，并且修改的地址指向的值(指针指向的值)，而不是修改地址
函数传递传值，是互不影响的，因此在子函数改地址，是影响不到主函数的
但现在的情况就是，我们要改的不是地址的值————我们要改的是地址

我们先抄一下之前的代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void add(Node* head , int number){
    Node *p = (Node*)malloc(sizeof(Node)) ; 
    p->value = number ; 
    p->next = NULL ;

    //寻找last
    Node *last = head ; 

    if(last){
        while(last -> next) {
            last = last->next ; 
        }

        //连接
        last->next = p
    }else{
        head = p;
        //如果p是第一个元素，此时要让p被加到head指向的地方，而非last指向的地方
    }
}

别使用全局变量的方法，那会使链表只能产生一个且是不安全的

其中一个方法是，让函数返回一个Node*，并在增加函数的地方使得head = add(head,numer)

1
2
3
4
5
6
7
8
9
Node* add(Node\* head ,int number){
    ...

    return head ;
}

...

head = add(head,number);

但是有一个缺点:必须仔细地使用，不要忘记了head = add(head,number);否则就会有问题出现

增加List

解决上面出现的问题，不妨再定义一个东西List使得表和结点分开 

1
2
3
typedef struct _list{
    Node* ; 
}List ;

然后在函数中，传入List的指针，然后对List做修改 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void add(List* pLiast , int number)
{
    Node *p = (Node*)malloc(sizeof(Node)) ; 
    p->value = number ; 
    p->next = NULL ;

    //寻找last
    Node *last = pList ->head ; 

    if(last){
        while(last -> next) {
            last = last->next ; 
        }

        //连接
        last->next = p
    }else{
        pList->head = p;
        //如果p是第一个元素，此时要让p被加到head指向的地方，而非last指向的地方
    }
}

此时，我们在主函数的操作也需要做出对应修改 

1
2
3
4
5
6
7
8
9
10
11
12
13
int main(){
    List list ;
    list->head = NULL ;//初始化

    do{
        scanf("%d" , &number) ;
        if(number != -1){
            add(&list,number);
        }
    }while( number != -1) ;

    return 0 ;
}

好处在于，现在使用了自己定义的结构List定义了整个链表

我们还可以以此为基础扩展，比如我们现在想要List包含尾部，这样我们就不用一直遍历了：

1
2
3
4
typedef struct _list{
    Node* head ; 
    Node* tail ; 
} List ;

相关的地方也需要修改，这里就不演示了

链表的操作

搜索

首先，在C语言中，如果我们想要遍历链表，可以使用: 

1
2
3
4
5
6
void printList(List *pList){
    Node *p ; 
    for(p = plist->head ; p; p = p->next) {
        printf("%d \t",p->value);
    }
}

此时，如果想要加入搜索相关的组件，就只需要把搜索值的判断加入进去即可

删除

删除主要做两件事情：
1.把要删除的指针的前一位指针，指向要删除的指针的后一位
2.释放空间

我们利用一个额外的变量Node *q来进行层层推进，知道找到目标
然后进行要做的两步操作： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Node *q ; 
Node *p ; 
for(q =NULL,p=list.head ; p ; q=p,p=p->next){
    //每一步都使得q=p,p=p->next来逐步前推

    if( p->value == number){
        //number是我们要删除的那个数
        if(q){
            q->next = p->next ; 
            //如果存在q,也是就是第一次执行或者改链表仅有一位元素    
            //那么想删除该元素，只需要把q的下一位连p的下一位
        }else{
            list.head = p->next ; 
            //否则就照常进行改动
        }
        free(p) ; //都完成之后把p的空间释放 
        break;
    }
}

链表清除

在必要的时候，我们需要把整个链表清除干净
一步步的把每一个结点的“下一个结点的指针”清除即可:

1
2
3
4
for( p=head ; p ; p=q){
    q = p->next ; 
    free(p);
}

小结

14的这一部分主要还是看看，更多关键的实现和想法，还需要参照算法、数据结构的相关要求