还没学 的
167页的wordcnt程序
199页的checking程序（太长了，不想看）
113页的第八章编程练习5（不想看）
125页的复习题9(有问题，有时间再来验证)
119页重定向和文件(nnd，有更强大的文件通信方法我干嘛学这个，装X吗)
307页的字符串排序和命令行参数还有字符串转换什么玩意，等学c++再说，我就是这么懒
11章及以后的编程练习都没做，不是懒，是想学c++(是的，没错)
334页随机数函数和掷骰子(不做赌徒)学C++肯定也有，不学！
360页文件压缩程序(这个倒可以试试，不过我懒，不想写)
369页的文件程序示例什么的(反正我不用C写文件，不看)
366页其他标准函数
398页伸缩型数组成员
402页保存结构程序(有空可以写来试试)
415页func_ptr程序
433页位字段(啊?)
458页及以后剩余的16章内容
514页用队列模拟
代码规范
-
定义常量或限定变量时，名应大写，以此区分变量与常量。
-
使用
a+=、a-=、a*=、a/=、a%=、a<<=、a>>=来提升逼格专业性。 -
代码应两份，一份写注释，一份不写注释。提升
逼格不可替代性。 -
合理应用圆括号和逗号运算符组合子表达式。
-
合理使用空格与缩进提升美感。
c语言概述
无论main()在程序文件中处于什么位置，
所有的c程序都由main()开始执行。
main()函数圆括号内是参数，无参数应写void- 函数必须在花括号内
- 在定义函数时，返回类型为
void表示无返回值
返回类型 函数名(参数)
传递给函数的信息被称为参数
表达式 && 语句
表达式(expression)由运算符和运算对象组成。
语句(statement)是C程序基本构建块，每条语句都可以看作一条完整的计算机指令，大部分语句由分号结尾。
根据C标准，声明不算语句，这与C++不同。
副作用(side effect)指对数据对象或文件的修改
states=5;
副作用是将变量值设置为5；
a++;
副作用是将a+1；
使用它们的主要目的就是使用其副作用。
** 序列点 **
序列点(sequence point)是程序执行的点，在该点上，所有的副作用都在进入下一步之前发生。
在C语言中，语句的分号就标记了一个序列点。
完整表达式：指这个表达式不是另一个更大表达式的子表达式。
完整表达式的结束也是一个序列点。
while(guests++ < 10)
printf("%d\n",guests);
在该例中，guests++不是先在printf()中先使用，再递增它的意思，因为guests++ < 10是一个完整的表达式，因为它是while循环的测试条件，所以该表达式的结束就是一个序列点
因此，C保证了在程序执行printf()之前发生副作用(递增guests++)。同时，使用后缀形式使guests在完成与10的比较后才递增。
复合语句(compound statement)是用花括号括起来的一条或多条语句
，复合语句也称为块(block)。
数据类型
scanf()：获取程序输入
printf()：获取程序输出
short int&&long int&&long long int字面意思
在类型前添加unsigned关键字，只允许非负值，表示范围更大，可理解为将负数范围变为正数范围。添加signed关键字，可强调使用有符号类型的意图。
如果是常量, 编译器会根据值大小进行类型改变。
注意：当变量溢出时，编译器不会提示。
char类型实际存储的是整数而不是字符，计算机使用数字编码来处理字符，即用特定整数表示特定字符
转义序列和空格也可以赋给char
- 整数类型可使用%c打印对应的ASCLL码
_Bool类型用于表示布尔值，即true && false
C99中提供了 <stdbool.h> 头文件，该头文件让 bool 成为 _Bool 的别名,并把 true 和 false 分别定义为1和0的符号常量。
_Bool 类型只能取 true 和 false 两个值， bool类型可取 true 、 false 和 0 三个值。
-
使用浮点型时注意上溢(overflow)和下溢(underflow)
下溢是数值太小无法表示，上溢是数值太大超出类型范围。 -
浮点型可写成小数点形式和指数形式，分别使用%f和%e
sizeof()会以字节为单位给出指定类型的大小
字符串
字符使用 ''
字符串使用 ""因为这样系统会自动在末尾添加空字符，而''不会
注意对应的格式转换符 %c && %s
字符串常量一定以\0(null character)结束；
字符函数
<ctype.h>头文件中的一些函数
字符映射函数
| 函数名 | 行为 |
|---|---|
| tolower() | if参数是大写字符，则返回小写；else返回原始参数 |
| toupper() | if参数是小写字符，则返回大写；else返回原始参数 |
字符映射函数不修改原始参数，而是返回已修改的值。
字符测试函数
| 函数名 | if是下列参数，返回值为ture |
|---|---|
| isalnum() | 字母或数字 |
| isalpha() | 字母 |
| isdigit() | 数字 |
| islower() | 小写字母 |
| isupper() | 大写字母 |
| isblank() | 标准的空白字符(空格、水平制表符、换行符)与本地化指定为空白的字符 |
| isspace() | 空白字符与本地化指定为空白的字符 |
| ispunct() | 标点符号（除空格、数字、字母以外的任何可打印字符） |
字符串与数组和指针
在指定数组大小时，要确保数组的元素个数至少比字符串长度多1，为了存储空字符，未被使用的元素自动初始化为\0不是数字0
可以使用sizeof()计算字符串长度来确定数组大小
char pies[sizeof(long double)+1];
字符数组名与其他数组名一样，都是该数组首元素的地址
也同样可以使用指针表示法创建字符串
const char * ptr = "Something is pointing at me"
//也可以用数组表示法 ptr[]
数组形式：
每个元素被初始化为字符串字面量对应的字符。通常，字符串都作为可执行文件的一部分存储在数据段中。当把程序载入内存时，也载入了程序中的字符串。
字符串存储在静态存储区中，当程序运行时才会对该数组分配内存。此时才将字符串拷贝到数组中
指针形式：
将字符串地址存储在指针变量中
数组名是数组第一个元素的地址，所以字符串指针指向字符串的第一个字符。
在数组形式中，数组名是地址常量，更改它是改变数组的地址
- 初始化数组是把静态存储区中的字符串拷贝到数组中，而初始化指针是把字符串的地址拷贝给指针
- 要注意，数组元素是变量(除非const)，但数组名不是变量
char * p1 = "Apple";
p1='B';
printf("%ss\n","Apple");
编译器可以使用内存中的一个副本来表示所有完全相同的字符串字面量，如果使用这种单次副本表示法，修改的值将影响所有使用该字符串的代码，将输出"Bpple"
其行为未定义，也会导致程序中断等异常
因此在把指针初始化为字符串字面量时，应使用const限定符
在把非const数组初始化为字符串字面量时，将不会导致类似的问题，因为数组获得的是原始字符串的副本
-
指针和字符类型占用字节不同，相同的多维数组，一定是指针占用内存少的多
-
指针指向初始化时使用的字符串字面量的位置，这些字符串字面量存储在静态内存
-
数组存储字符串字符量的副本，所以每个字符串都被存储了两次
-
为字符串数组分配内存的使用率低，因为每个元素大小必须相同，且必须是能存储最长字符串的大小，而指针数组可以不规则
因此，如果需要修改字符串，就不要用指针指向字符串字面量
如果要用数组表示一系列待显示字符，应使用指针数组
字符串输入
fgets()函数
- 函数原型：
char * fgets(char * str, int n, FILE * stream)
-
fgets()函数的第二个参数指明读入字符的最大长度，为n-1，因为字符串以\0结尾，或者遇到第一个换行符为止 -
如果
fgets()函数读到一个换行符，会把它存储在字符串中,而gets()函数不会 -
fgets()函数的第三个参数是文件指针，如果为NULL，则从标准输入stdin读取 -
puts()函数会在待输出字符串末尾添加一个换行符，fputs()函数不会
fgets()函数返回指向char的指针。该函数返回地址与传入的第一个参数相同，但如果函数读到文件末尾，它将返回一个空指针，用数字0或宏NULL代替(如果读入数据出现某些错误，该函数也返回NULL)
char * word_get(char * word, int n)
{
char * result;
int i = 0;
result = fgets(word, n, stdin);
if (result)//result1 != NULL
{
while (word[i] != '\n' && word[i] != '\0')
i++;//遍历字符串
if
(word[i] == '\n')
word[i] == '\0';
//如果遇到换行符，则将换行符替换为空字符
else
while (getchar() != '\n')
continue;
//如果遇到空字符，则丢弃输入行剩余字符
}
return result;
}
空字符是用于标记C字符串结尾的字符，对应字符编码是0
空指针有一个值，该值不会与任何数据的有效地址对应，通常，函数使用它返回一个有效地址表示某些特殊情况发生，例如遇到文件末尾或未能按预期执行。
空字符是整数类型，而空指针是指针类型，空字符是一个字符，占1字节，而空指针是一个地址，通常占4字节，容易混淆的地方是它们都能用数字0来表示
scanf()函数
scanf()函数从第一个非空字符作为字符串的开始，到指定宽度或读到第一个空白字符停止(空格、空行、制表符或换行符)作为结束
下一次调用时从上一次调用结束的地方继续读取数据
scanf()函数的格式字符串中，%s表示读入一个字符串，%c表示读入一个字符
scanf()函数返回一个整数值，该值等于scanf()成功读取的项数或EOF
fgets()读取从键盘输入的数据更合适，因为scanf()遇到空白字符便会停止读取
scanf()典型用法是读取并转换混合数据类型为某种标准形式
字符串输出
fputs()函数
- 函数原型：
int fputs(const char * str, FILE * stream)
fputs()是puts()针对文件的版本
fputs()函数第二个参数为文件指针，如果为NULL，则从标准输出stdout输出- 与
puts()函数不同，fputs()函数不会在待输出字符串末尾添加换行符
如果要处理字符串，实际参数可以是数组名、双引号字符串或声明为char*类型的变量
字符串函数
C提供多个处理字符串的函数，在string.h头文件中
strlen()函数
用于统计字符串的长度，即字符数
-
strlen()给出字符串中的字符实际占用长度，\0不计算 -
printf()返回打印字符的个数，包括空格和转义序列 -
不能在
""括起来的字符串中间用enter断行,可用\n表示
sizeof()数组大小计算:类型大小*数组
-
使用
strlen()||sizeof()时应使用%zd格式转换符 -
sizeof()返回 size_t 类型，这是一个无符号整数类型
strcat()函数
- 函数原型：
size_t strlen(const char *str)
接受两个字符串参数，将第二个字符串的备份连接到第一个字符串的末尾，拼接后的新字符串作为第一个字符串，第二个字符串不变，返回第一个字符串的地址，strcat()函数是char *类型
strncat()函数
- 函数原型：
char *strncat(char *dest, const char *src, size_t n)
strcat()函数无法检查第一个数组能否容纳第二个字符串
而strncat()函数的第三个参数可以指定最大添加字符数
strcmp()函数
- 函数原型：
int strcmp(const char *str1, const char *str2)
strcmp()函数通过比较运算符比较两个字符串的内容，如果两个字符串相同，则返回0，否则返回非0值
strcmp()函数比较的是字符串，而不是整个数组，因此可以比较不同大小数组中的字符串
strcmp()函数返回的是字符串的差值，即第一个字符小于第二个字符时，返回相应的负数，第一个字符串大于第二个字符时，返回相应的正数，字符串的返回值便是累加
strncmp()函数
- 函数原型
strncmp(const char *str1, const char *str2, size_t n)
strncmp()函数的第三个参数指定比较的最大字符数，如果两个字符串的前n个字符相同，则返回0，否则返回非0值
strcpy()函数
- 函数原型：
char *strcpy(char *dest, const char *src)
dest：目标字符串指针，拷贝地址
src：源字符串指针，被拷贝的字符串
可以理解为字符串赋值运算符
如果dest指针没有初始化，会被拷贝到任意地方！
src指针可以是指针、数组名、字符串常量，而dest指针应指向一个数据对象，且该对象有足够的空间存储源字符串的副本
strcpy()函数返回类型是char *
声明数组分配存储数据的空间，而声明指针只分配一个地址的空间
strncpy()函数
- 函数原型：
char *strncpy(char *dest, const char *src, size_t n)
它的第三个参数指定拷贝的最大字符数，如果源字符串的长度大于n，则只拷贝前n个字符，这个时候没有拷贝完整个源字符串，就不会拷贝空字符，所以拷贝的副本不一定有空字符
应该将第三个参数设置为比目标数组大小少1，然后把数组最后一个元素设置为空字符
strncpy(word[i],temp,TARGET-1);
word[i][TARGET-1] = '\0';
这样做确保存储的是一个字符串，如果目标空间能容纳源字符串副本，那么从源字符串拷贝的空字符便是该副本的末尾，如果目标空间装不下副本，则把副本最后一个元素设置为空字符
sprintf()函数
- 函数原型：
int sprintf(char *str, const char *format, [argument]...)
buffer：这是一个指向目标字符串的指针，即要将格式化的数据写入的字符串地址
format：这是一个指向格式字符串的指针，该字符串中的字符将用于控制输出的格式
[argument]…：这是可选参数，表示要写入到字符串中的实际数据，这些数据可以是任何类型
该函数声明在stdio.h中，它与printf()类似，但它是把数据写入字符串，而不是打印在显示器上，该函数可以把多个元素组合成一个字符串，并写入到buffer所指向的内存中
sprintf(target,"%s phone:%d",name,phone)
常量
常量定义方法：
使用c预处理器：#define 明示常量 符号常量值
注意边缘效应
例:
#define N 2+3
double a;
a = ( float ) N / ( float ) 2；
上述例子中，编译器会将a=N/2处理成a=2+3/2,应写成#define N (2+3)。
常量命名时可用大写，以此来区分常量与变量
2.const关键字:const 数据类型 符号常量 = 符号常量值
用于限定变量为只读，本质还是变量。
明示常量
c头文件limits.h&&float.h分别提供整数类型和浮点类型大小限制相关的详细信息，定义了一系列供实现使用的明示常量。
| 明示常量 | 含义 |
|---|---|
| CHAR_BIT | char类型的位数 |
| CHAR_MAX | char类型的最大数 |
| CHAR_MIN | char类型的最小数 |
| SCHAR_MAX | signed char类型的最大数 |
| SCHAR_MIN | signed char类型的最小数 |
| USHRT_MAX | unsigned char类型的最大 |
| INT_MAX | int类型的最大数 |
| INT_MIN | int类型的最小数 |
| UINT_MAX | unsigned int类型的最大数 |
| LONG_MAX | long int类型的最大数 |
| ULONG_MAX | unsigned long int类型的最大数 |
| LLONG_MAX | long long int类型的最大数 |
| LLONG_MIN | long long int类型的最小数 |
| ULLONG_MAX | unsigned long long int类型的最大数 |
我也不知道我为什么花那么多时间去建这张sb表
I/O
printf()&&scanf()都可以用*修饰符来修改转换说明的含义，不过用法不同。
int a=8,b=2
float c=222.378;
printf("%0*.*f",a,b,c);
-
上例说明输出一个8位字符宽度，小数点后显示2位的浮点数，不足8位时用0补齐
-
%nf:不足n位时右对齐至n位
-
%-nf:不足n位时左对齐至n位
scanf("%*d %d",a,a);
-
将
*放在%和转换字符之间，会跳过相应输入值
在程序需要读取文件中特定列的内容时，这项跳过功能很有用。 -
对于字符数组，
scanf()不需要使用& -
scanf()读取时，遇到空格便会暂停
单字符I/O函数
getchar() 函数不带任何参数，它从输入队列中返回下一个字符
ch = getchar:读取下一个字符，将字符赋给变量ch
putchar()函数打印它的参数
putchar(ch):打印变量ch的字符
这两个函数定义在<stdio.h>中（它们通常是预处理宏，而不是函数）
scanf() ： 根据返回状态值判断是否结束循环
getchar()：根据输入值来判断是否结束循环
缓冲区
输入字符后后不是立即执行，而是将输入的字符逐个送入缓冲区(buffer)
缓冲分为完全缓冲I/O和行缓冲I/O
- 完全缓冲I/O：当缓冲区被填满时才刷新缓冲区，通常出现在文件输入中。缓冲区大小取决于系统，常见大小是512字节和4096字节。
- 行缓冲I/O：当出现换行符时刷新缓冲区
无缓冲I/O
getche()：带回显getch()：不带回显
文件、流
C把输入和输出设备视为存储设备上的普通文件，尤其是把键盘和显示设备视为每个C程序自动打开的文件。
stdin流表示键盘输入，stdout流表示屏幕输出
从概念上看，C程序处理的是流，而不是直接处理文件。流是一个实际输入或输出映射的理想化数据流。也就是说不同属性和不同种类的输入，由属性更统一的流来表示。打开文件的过程就是把流和文件相关联，并且读写都由流来完成。
在C语言中，getchar()和scanf()函数读取文件结尾时返回EOF(end of file)值，这个值是-1, （因为标准字符集是0~127） EOF标志检测到文件末尾。
UNIX模拟文件结尾是 ctrl+D windows是 ctril+z
创建友好？的用户界面
- 使用缓冲输入
int a = 1;
char m;
while ((m = getchar()) != 'y')
{
printf("%c %d\n",m, a++);
while (getchar() != '\n')
continue;
}
上例中，第二个while循环舍弃了除第一个字符外的所有字符，当等于换行符时跳过循环，若无该循环，计数时换行符也会被计入，将会打印两次a++。
在编写交互式程序时，应预料用户的输入错误，并设计相应的程序处理
- 混合数值和字符输入
void display(char ch,int LINES,int ROWS);
int main(void)
{
int ch;
int rows,lines;
printf("Enter a character:\n");
while ((ch = getchar()) != '\n')
{
printf("Enter two integers:");
if (scanf_s("%d %d",&lines,&rows)!=2)
break;
display(ch,lines,rows);
while(getchar()!='\n')
continue;
color(6); printf("Enter to quit\n"); color(20);
printf("Enter a character\n:");
}
printf("Bye!");
return 0;
}
void display(char ch, int LINES, int ROWS)
{
int i,j;
for (i = 1; i <= LINES; i++)
{
for(j=1;j<=ROWS;j++)
//printf("%c",ch);
putchar(ch);
printf("\n");
}
}
上例中，也是使用了一个同上上例中一样的while循环来判断当输入错误时，使用continue跳过循环，继续等待输入。
可以使用新函数来替换getchar()函数，仅读取一行的第一个字符
char get_first(void)
{
int ch;
do
{
ch = getchar();
}
while (getchar() != '\n');
putchar(ch);
return ch;
}
可以改为：
char get_first(void)
{
int ch;
ch = getchar();
while (getchar() != '\n')
continue;
putchar(ch);
return ch;
}
输入混合数值和字符过程需要注意scanf()函数能否自动消除换行符和空格，getchar()函数会读取每一个字符，两者混用时需要注意缓冲区内数据的清理。
常用方法是使用while循环，调用getchar()函数判断并清空缓冲区数据
可以这样写putchar(putchar(getchar()));
别管可读性，复杂才是王道
一些小技巧
- 使用取反控制循环
int a = 0, b = 0;
while (~scanf("%d%d", &a, &b))
{
printf("%d\n", a + b);
}
关于~的作用解析：
- 在Windows下，用户按下CTRL+Z（会看到一个^Z字符），会停止输入流，scanf会返回-1。
- -1的补码为11111111 11111111 11111111 11111111 一共4个字节。
- 是C语言中的按位取反，因此（-1）结果为00000000 00000000 00000000 00000000刚好为整数0的补码。
- 因此当输入Ctrl+Z时，scanf会返回-1，while(~-1)==while(0)，0为假，退出while循环
- 可以使用数组来输出界面
char s1[]="请输入第一个数字：";
printf("%-20s",s1);
- %g 格式化字符串会自动选择合适的精度，以使得输出结果更加简洁
- %f 输出浮点数时，默认输出6位小数
- %e 输出浮点数时，默认输出指数形式，e为底数
写一个满意的界面并不容易，但开发一种可行方案后，大多数情况可以复用
运算符
几个 装逼 术语
- 赋值运算符
左侧是可修改的左值，也叫对象定位值(object locator value)
右侧是能赋给对象定位值的量
赋值表达式语句的目的是把值存储到内存位置上，用于存储值的数据存储区域统称为数据对象(data object)
/ && %
/一个运算对象为负，则为负，两个及以上对象为负，则为正%仅当第一个对象为负数时，结果为负，否则为正
a++ && ++a
-
a++：后缀递增
先使用a值，然后递增 -
++b：前缀递增
先递增，然后使用b值
明智的选择是：
++i;//此处改为i++也可以，因为没有赋值和循环
b=i;
比较运算符
比较运算符的结果是布尔值
- n在比较浮点数时，尽量只使用
<和>因为浮点数的舍入误差会导致两个浮点数看起来相等，但实际不等，例如:31/3的结果是1.0，但如果把1/3表示为小数点后面6位小数，那么31/3的结果就是.999999，不等于1.0,(不过实测等于1)，但还是应尽量避免。
使用fabs()函数(声明在<math.h>头文件中)，该函数可以将一个浮点数转换为绝对值。
逗号运算符
const int FIRST_PAY = 46;
const int NEXT_PAY = 20;
int kg, cost;
printf("Enter weight in kilograms:");
scanf_s("%d", &kg);
for (kg = 1, cost = FIRST_PAY; kg <= 10 ; kg++, cost += NEXT_PAY)
{
printf("%2dkg is $%3d\n", kg, cost);
}
逗号运算符不局限于for循环，也可以用于while循环和if语句
逗号也是一个序列点，逗号左侧项的所有副作用都在程序执行逗号右侧项前发生
逻辑运算符
&&：逻辑与||：逻辑或!：逻辑非(变真为假，变假为真)只需要一个运算对象
&&和||也都是序列点
&&和&是等价的，||和|是等价的
如果使用布尔类型的变量，通常习惯把变量自身作为测试条件
if (!inword) & if(inword == false)是相同的
包含
<iso646.h>头文件后可用andornot代替&&||!
- 注：逻辑表达式从左到右执行，一旦结果为真，则不再执行右侧表达式
条件运算符
expression1 ? expression2 : expression3
if expression1 is true, then the value of expression2 is returned, otherwise the value of expression3 is returned
可用于替代简单的 if else 语句
#define COVERAGE 350//每罐油漆可刷面积(平方英尺)
int area, cans;
char can = "can";
printf("Enter number of square feet to be painted:\n");
while (scanf_s("%d", &area) == 1)
{
cans = area / COVERAGE;
cans += (area % COVERAGE == 0) ? 0 : 1;
printf("You need %d %s of paint.\n", cans, cans == 1 ? "can" : "cans");
printf("Enter next value (q to quit):\n");
}
类型转换
-
涉及两种类型的运算，两个值会分别转换成两种类型的更高级别。
升级(promotion) -
在赋值表达式语句中，计算的最终结果会被转换成被赋值变量的类型。这个过程可能导致类型升级或降级(demotion)
-
当作为函数参数传递时，char && short 被转换为 int，float 被转换为 double
-
浮点型降级为整型时，浮点值将被截断(truncation)
-
将超出其类型范围数赋给char时，待赋值是原始值%256
强制类型转换语法:
(目标类型)表达式
将右表达式值强行转换为目标类型
强制类型转换应注意可能会丢失数据或损失精度的操作，也可强调转换类型的意图
mice1 = 1.6 + 1.7
mice2 = (int) 1.6 + (int) 1.7
结果：
mice1=3.3
mice2=2
注意：
虽然C允许编写混合类型的表达式，但算数运算要求运算对象都是相同类型。因此，C会进行自动类型转换。
但不能依赖自动类型转换，应该使用合适的类型或使用强制类型转换，这样就不会担心出现不必要的类型转换。
函数
函数是完成特定任务的独立程序代码单元，函数调用时，函数体代码被临时复制到内存中，函数调用结束后，内存中的函数体代码被销毁。
1. 函数可以作为组成大型程序的构建块
- 每个函数都应该有一个单独且定义好的功能。
- 将大型程序组织成若干函数非常有用
void values(int n)；//函数原型声明 声明要有分号，声明可以省略变量名，这里的变量名是假名，不必与函数定义的形参名一致
//函数类型 函数名 (函数参数)
int main(void)//圆括号里的void类型表明函数没有参数
{
int a=5;
char b='!';
float f=12.77
values(a);//函数调用
values(b);
values(f+1);
return 0
}
void values(int n)//函数定义,每个变量前都要声明其类型
//圆括号外的void表明函数没有返回值
//函数类型是返回值的类型，不是函数参数的类型
{
while(n-- > 0)
{
printf("#");
}
printf("\n");
}
- 函数原型告诉编译器函数的类型和参数的类型。
- 函数调用表明在此处执行函数
- 函数定义明确函数要做什么
函数声明告知编译器函数的类型，函数定义则提供实际的代码
-
形参是局部变量，实参是函数调用提供的值，实参赋给相应的形参
形式参数是被调函数中的变量，实际参数是主调函数赋给被调函数的具体值
形参是函数定义的函数头中声明的变量，实参是函数调用圆括号中的表达式
在上述程序中，a是values()的形参，n是values()的实参 -
实参可以是变量、常量或是复杂的表达式
-
实参的值将被拷贝给被调函数相应的形参，因为是拷贝，所以无论被调函数对拷贝的实参进行怎样的操作，都不会影响到实参的值
变量名是函数私有的，在一个函数中定义的变量名不会和其他地方的相同变量名发生冲突
先声明，再调用；把声明函数放在调用函数之前
函数原型的目的是为了让编译器在第一次执行到该函数之前就知道如何使用它
原型(prototype)是函数的声明，描述了函数的返回值和参数。
values()函数的原型说明了两点：
- 该函数没有返回值(因为有void关键字)
- 该函数有一个int类型的形参
上述程序中，如果将values(int n)改为values()
第一次调用与第二次调用都没有问题，因为函数调用时 char 和 short 自动升级为 int 类型。但第三次调用时， float 会自动升级为 double 类型，在visualstudio2022上运行时，不显示结果，也没有报错。
因为将较大类型转换为较小类型时，可能会丢失数据。
return
函数的返回值可以把信息从被调函数传回主调函数
- 返回值不仅可以赋给变量，也可以被用作表达式的一部分
answer=2*sum(a)+25;
printf("%d",sum(a));
- 也可以是任意表达式的值
return (a<b)?a:b;
- return的另一个作用是终止函数的执行并把控制返回给主调函数的下一条语句
if(a>b)
return a；
else
return ；
printf("%d is a big number",b);
递归
C允许函数调用它自己，这种调用过程称为递归(recursion)
void up(int n)
{
printf("level %d:n location %p\n",n,&n);
if(n<4)
up(n+1);
printf("LEVEL %d:n LOCATION %p\n",n,&n);
}
int main(void)
{
up(1);
return 0;
}
```CPP
1. 每级函数调用都有自己的变量，第一级的n和第二级的n是两个不同的变量，从内存位置也能看出它们在内存中的位置不同
2. 每次函数调用都会返回一次，当函数执行完毕后，就会返回上一级，并继续执行上一级的后续操作，程序必须按顺序逐级返回递归(被调函数结束会返回至主调函数)
3. 递归函数位于递归调用之前的语句，均按照被调函数顺序执行，而位于递归调用之后的语句，则均按照被调函数相反顺序执行
4. 虽然每级递归都有自己的变量，但是没有拷贝函数的代码。程序按顺序执行函数中的代码，而递归调用相当于又从头开始执行函数的代码。除了为每次递归调用创建变量外，递归调用非常类似于一个循环语句
5. 递归函数必须包含能让递归停止的语句
>一般还是选择循环，因为每次递归调用都会在内存中创建一组变量，而且每次递归调用都会把创建的一组新变量放在栈中，递归调用的数量受限于内存空间。在程序中使用递归一定要特别注意，尤其是效率优先的程序。
## 函数和多维数组
函数声明指向多维数组的指针：
```CPP
void function(int(*pt)[4]);
void function(int pt[][4]);
//空的方括号表明pt是一个指针
void function(int ar[][], int n);
//error 编译器会把数组表示法转换成指针表示法，但必须知道ar所指向对象的大小
void function(int ar[][4],int n);
//ar指向一个有4个int类型元素的数组
void function(int ar[3][4],int n);
//有效声明，3会被忽略
void function(int ar[][3][4],int n);
//ar指向一个nx3x4的三维数组
复合字面量
compound literal
字面量是除符号常量外的常量，如：5，6.6，Y，Apple
复合字面量类似于数组初始化列表，前面是用括号括起来的类型名
(int [2]) {10,20};//复合字面量
(int []) {10,20,30};//初始化时可以省略大小
//因为复合字面量是匿名的，所以必须在创建的同时使用它，使用指针记录地址就是一种用法
int * pt;
pt = (int []) {10,20,30};
//也可以把复合字面量作为实际参数传递给带有匹配形式参数的函数
int sum(const int ar[],int n);
...
int total;
total = sum((int []) {10,20,30},3);
//第一个实参是内含3个int元素的数组，这同时也是该数组首元素的地址
//这种用法的好处是把信息传入函数前不用先创建数组，这也是典型用法
复合字面量是提供只需要临时需要的值的一种手段，复合字面量具有块作用域，一旦离开定义复合字面量的块，程序将无法保证该字面量是否存在，也就是说，复合字面量定义在最内层的花括号中
循环
while循环
根据输入判断条件时，可以这样写：
double x;
while(scanf("%lf",x)==1)
也可以
再定义一个变量，将scanf的结果赋值给该变量
double x,i=1;
while(i=scanf("%lf",&x)==1)
可以使用空语句来测试循环条件，而不需要测试循环体
double x, i;
i = scanf_s("%lf", &x);
;
while(i==1)
{
i = scanf_s("%lf", &x);
printf("1\n");
}
也可以使用do-while循环，在循环体执行前测试循环条件
for循环
for ( initialize; test; update)
- 可以省略一个或多个表达式(但不能省略分号)
- update可以使用任意合法表达式
- initialize不一定是赋值语句，也可以是其他语句，在执行循环体的其他部分之前，initialize只执行一次
- 循环体中的行为可以改变循环头中的表达式
逗号运算符至高用法：
int k;
for( k=1,printf("%d:hi!\n",k); printf("k = %d\n",k),k*k<26; k+=2,printf("now k is %d \n",k))
;
这种语句写法容易让人迷惑，没有可读性，提升不可替代性，让别人看不懂你的代码，代码是程序员的内裤 所以一般不建议使用
嵌套循环
do while循环
出口条件循环(exit-condition loop)：在循环的每次迭代之后检查test条件，保证至少执行循环体中的内容一次。
控制语句
if选择是否执行一个行为，if else选择两个行为之一，else if选择多个行为之一
else if 实际是 if else 的变式
if
else if
else if
if
else
if
else
if
两种形式完全等价，但是else if形式更简洁
C99标准要求编译器至少支持127层嵌套（我滴个乖乖）
在没有花括号限制时，else与最近的if配对
循环控制语句
continue 跳过循环体中剩余的语句，直接进入下一次循环
break 跳出循环体，如果是循环嵌套，则是跳出最近的内层循环
如果使用这两个语句反而更复杂，
那可太好了就不要使用
switch语句
switch (整型表达式)
{
case 常量表达式1:
语句1;
break;
case 常量表达式2:
语句2;
break;
default:
语句
}
也可以在switch语句中使用多重标签
switch (整型表达式)
{
case 常量表达式1:
case 常量表达式2:
语句1;
break;
case 常量表达式3:
case 常量表达式4:
语句2;
break;
default:
语句
}
goto语句
goto 标签名;
...
...
...
标签名:
使程序跳转至相应标签语句
不要使用goto语句，除非你非常确定它比其他方法更有效率
数组
数组(array)是相同类型数据元素的有序集合
数组从0开始编号
-
每一个数据被称为数组元素，它们在内存中是连续存储的。每个数组元素都有一个序号，这个序号被称为下标或索引。
-
数组名是一个指针，指向数组第一个元素的地址
-
数组名是常量，不能改变
初始化数组
未初始化数组时，存储的都是垃圾值，部分初始化后，剩余元素将被初始化为0
const int datys[]={31,28,31,30,31,30,31,31,30,31,30,31};
for(int index=0;index<sizeof days/sizeof days[0];index++)
printf("Month %2d has %d days.\n",index+1,days[index]);
-
初始化数组省略大小时，编译器会根据初始化列表中的项数确定数组大小
-
可以使用sizeof来计算大小，sizeof days是整个数组的大小，sizeof days[0]是数组第一个元素的大小 (以字节为单位)
int array1[10]={10};//每个元素都初始化为10
int array2[]={[5]=10};//把array2[5]初始化为10
int array3[]={1,2,[5]=10,6,[5]=20,[1]=2};
//最终array[1]=2,array[5]=20,数组大小为7
可以利用数组下标(索引给数组元素赋值)
#define SIZE 10
int a=20,count,even[a];//变量不能用作数组大小，可以定义符号常量来表示数组大小
//C99标准允许变量声明
for(count=0;count<a;count++)
even[count]=count*2;
- C编译器不会检查数组下标的有效性，要确保下标是有效的值
- 数组下标不能为负数
- 数组下标不能超过数组大小
数组大小是0~n-1，a[20],那么它的数组下标是 0~ 19
变长数组(VLA)
variable-length array 是C99引入的特性，允许用变量声明一个数组
变长数组必须是自动存储类别，这意味着无论是作为函数形参还是函数中声明，都不能使用static || extern存储类别说明符，而且不能在声明中初始化
int sum(int n, int ar[*][*]);
可以省略函数原型中的形参名，但在变长数组中，必须用*代替省略的维度
变长数组允许动态内存分配，可以在程序运行时指定数组的大小
在函数定义的形参列表中声明的变长数组并未实际创建数组，变长数组名实际上是一个指针，这说明带变长数组形参的函数实际上是在原始数组中处理数组，因此可以修改传入的数组
多维数组
float rain[5] [12];//5行12列的数组，包含60个元素
rain [0] [0] rain [0] [1] rain [0] [2] rain [0] [3] ...
rain [1] [0] rain [1] [1] rain [1] [2] rain [1] [3] ...
rain [2] [0] rain [2] [1] rain [2] [2] rain [2] [3] ...
rain [3] [0] rain [3] [1] rain [3] [2] rain [3] [3] ...
rain [4] [0] rain [4] [1] rain [4] [2] rain [4] [3] ...
......
多维数组初始化
const float rain[YEARS] [MONTHS]=
{
{1,2,3,4,5}//rain[0]
//一个列表用花括号括起来，也可以省略内部花括号，适用于较小的二维数组
{6,7,8,9}//rain[1]
{10,11,12,13}//rain[2]
{[4][0]=14,15}//rain[3]
}
多维数组处理
处理二维数组要使用2重嵌套循环，处理三维数组要使用3重嵌套循环，以此类推
for (year = 0, total = 0; year < YEARS; year++)
{
//处理一年的数据
for(month=0,subtot=0;month<MONTHS;month++)
//处理每个月的数据
} //处理n年的数据
- 每执行一次外层循环，就完整遍历一次内层循环
数组和指针
指针提供一种以符号形式使用地址的方法，因为计算机的硬件指令非常依赖地址，指针在某种程度上把程序员想要传达的指令以更接近机器的方式表达。
因此，使用指针的程序更有效率，尤其是，指针能有效地处理数组。
array==&array[0];//数组名等于该数组首元素的地址
两者都是常量，在程序运行过程中不会改变。但可以把它们赋值给指针变量，然后修改指针变量的值
在C中，指针加1指的是增加一个存储单元，对数组而言，这意味着加1后的地址是下一个元素的地址，而不是下一个字节的地址。
这就是为什么必须声明指针指向对象类型的原因之一。只知道地址不够，还需要知道存储对象需要多少个字节。
data + 2 == &data[2];//相同的地址
* (data + 2) == data[2];//相同的值
不要与*data+2;混淆，*的优先级高于+，它的意思是将data的第一个元素的值加2
由上例可看出，数组与指针的关系十分密切
- 指针加1，指针的值递增它所指向类型的大小(以字节为单位)
- 在指针前面使用
*运算符可以得到该指针所指对象的值
同一个对象有两种表示法，C语言在描述数组表示法时借助了指针。也就是说，定义ar[n]的意思是*(ar+n)，可以理解为 ： 到内存的ar位置，然后移动n个单元，检索存储在那里的值 。
for(index=0;index<MONTHS;index++)
printf("MONTH% 2d has %d days.\n",index+1,days[index]);
//days[index]可以用指针表示法写为*(days+index);
//ar[i]和*(ar+i)是等价的
/* int *ar和int ar[]都表示ar是一个指向int的指针，因为数组名本质上是该数组首元素的地址
但只有在函数定义头或函数原型中才可以用int ar[]代替int *ar */
函数处理数组必须知道何时开始、何时结束
int sum(int ar[], int n)
{
int i, total = 0;
for (i = 0; i < n; i++)
total += ar[i];
return total;
}
int sum(int* start, int* end)
{
int total = 0;
while (start < end)
{
total += *start;//加上数组元素的值
start++;//让指针指向下一个元素
//也可简写为total += *(start++)，*与++优先级相同，结合律是从右到左
}
return total;
}
保护数组中的数据
如果函数的意图是修改数组中的数据，那么必须通过指针参数来传递数组。
但如果不想修改数组中的数据，则应使用const限定符来限定指针，这样就可以防止函数意外地修改数组。
在声明函数原型和定义函数时使用const并不是要求原数组是常量，而是要求该函数在处理数组时将其视为常量
void show_array(const double* ar, int );
void alter_array(double* ar,int , double);
int main(void)
{
double ar[SIZE] = { 20.05,10.21,4.17,8.1,6.6};
show_array(ar, SIZE);
alter_array(ar, SIZE, 2);
putchar('\n');
show_array(ar, SIZE);
return 0;
}
void show_array(const double ar[], int n)
{
for (int i = 0; i < n; i++)
printf("%.2f ", ar[i]);
putchar('\n');
}
void alter_array(double ar[], int n,double f)
{
for (int i = 0; i < n; i++)
ar[i] *= f;
}
const也可以有其他用法：
const ar[]={1,2,3,4,5};
ar[1]=6;//不能修改数组元素，因为ar有const关键字
int rate;
const int * pr = rate;//pr指向数组首元素
*pr=12;//error
*pr[2]=14;//error
pr++；//让pr指向下一个元素是可以的
//const限定后，指针表示法和数组表示法都不允许修改它所指向的值，但指针可以修改它所指向的地址
rate[2]=14;//rate并未被声明为const，所以rate可以修改
关于指针赋值和const需要注意一些规则：
- 把const数据或非const数据的地址初始化为指向const的指针或为其赋值是合法的
const指针可以指向const或非const地址
非const指针只能指向非const地址
int rate[5]={1,2,3,4,5};
const int locked[5]={1,2,3,4,5};
const int * ptr = rate;//correct
ptr=locked; //const指针可以指向const数据，仅initialize，之后不可修改
ptr=&rate[3]; //const的指针也可以指向非const数据
//const指针可以指向const或非const地址
int * ptc = rate; //effective
ptc=locked; //error
ptc=&rate[3]; //effective
//只能把非const的地址赋给非const的指针
show_array(rate,5);
show_array(locked,5);
//两者都是有效的，这两种参数都可以用来初始化const指针
alter_array(rate,5,2);
alter_array(locked,5,2);//error
//C标准规定，使用非const标识符修改const数据导致的结果是未定义的
- 创建指针时可以使用const两次，这样后该指针既不能更改它所指向地址上的值，也不能更改它所指向的地址
int end[5]={1,2,3,4,5};
const int * const pte = end;
pte=&rates[2];//ineffective
*pte=12; //ineffective
指针
指针(pointer)是一个值为内存地址的变量(或数据对象)，它存储了另一个变量的地址
查找地址
- & 运算符是获取变量的地址，地址是变量在内存中的位置，在赋值数组时可以省略，表示数组首元素的地址
- %p是输出地址的转换说明(pc地址通常使用十六进制表示)可以用%u或%lu代替
- %td转换说明打印地址的差值，可以用%d或%ld代替
间接运算符：*
也叫解引用运算符
给出存储在指针指向地址上的值
int *ptr number，val；
number=21；
ptr=&number;//指向number的指针
val=*ptr;//把ptr指向地址上的值赋给val
指针操作
int ar[] = { 1,2,3,4,5 };
int* pr1,* pr2,* pr3;
pr1 = ar;
printf("pr1==%p *pr1==%d &pr1==%p &ar==%p\n", pr1, *pr1, &pr1, &ar);
//赋值：可以将数组名、带地址运算符的变量名、另一个指针进行赋值
//地址应与指针类型兼容，至少避免不明智的类型转换，C99/C11已强制不允许这样做，指针地址和指针指向地址是不同的概念
pr2 = &ar[2];
printf("pr2==%p *pr2==%d\n",pr2,*pr2);
pr3 = &ar[3];
printf("pr3+1==%p pr3+1=%p (pr3+1)==%d\n",pr3+1,*pr3+1,*(pr3+1));
//pr3+1表示将变量pr3的地址加1，即指向pr3的下一个内存单元
//*pr3+1是访问pr3指向的内存单元地址上的值，然后将该值加1
//*(pr3+1)是将pr3+1的值作为地址，然后通过解引用运算符访问其指向的内存单元的值
printf(" pr2==%p pr1==%p pr2-pr1==%td\n",pr2,pr1, pr3 - pr2);
//计算指针间的差值，求出两元素之间的距离，差值单位与数组类型单位相同
//pr3-pr2表示pr3指向的地址与pr2指向的地址之间的内存单位距离，因为是int类型，所以单位是int，不是字节
printf("pr3==%p pr1==%p\n pr3-3==%p", pr3, pr1, pr3 - 3);
//将pr3指向的内存地址减去3个内存单元，即指向pr3-3的内存地址
- 使用关系运算符可以比较两个指针的值，前提是两个指针指向相同类型的对象
当使用关系运算符比较两个指针时，实际上是比较它们所指向的内存地址是否相同。如果两个指针指向相同的内存地址，则它们的值相等；否则，它们的值不相等。
需要注意的是，在使用关系运算符比较指针时，需要确保两个指针都已经被正确初始化并指向了有效的内存地址。另外，由于指针变量本身没有固定的大小，因此在不同的平台上，指针变量可能占用不同的字节数。因此，在进行指针比较时，还需要考虑平台和编译器的差异。
- 递增或递减指针时，编译器不会检查指针是否仍指向数组元素
指针使用递增或递减运算符（++和--）可以用来将指针指向数组中的下一个元素或上一个元素
- 不要解引用未初始化的指针
int * pr;
*pr=5;
//*pr uninitialized 时，其值是一个随机值，所以不知道将5存储在何处
//创建一个指针时，系统只分配了存储指针本身的内存，并未分配存储数据的内存，因此在使用指针之前，必须先用已分配的地址对其进行初始化
指针和多维数组
int view[4][2] = { {1,2},{3,4},{5,6},{7,8} };
printf("view==%p view+1==%p\n",
view,view+1);
//view+1表示将变量view的地址加1，即指向view的下一个内存单元
//view是一个二维数组，是一个内含2个int类型值的数组的地址，因此view+1，它所指向的地址加8字节
printf("view[0]==%p view[0]+1==%p\n",
view[0],view[0]+1);
//view[0]+1表示将view[0]的地址加1，即指向view[0]的下一个内存单元
printf("*view==%p *view+1==%p\n",
*view,*view+1);
//结果与数组表示法相同，说明数组表示法和指针表示法相同
//指针表示法(尤其是和递增运算符结合使用时)更接近机器语言
//因此一些编译器在编译时能生成效率更高的代码
printf("view[0][0]==%d *view[0]==%d **view==%d\n",
view[0][0],*view[0],**view);
//*view 表示对view的第一个元素进行解引用，即view[0]
//**view 表示对 view 数组的第一个元素的第一个元素进行解引用，即view[0][0]
//view[0]是一个占用一个int大小对象的地址，view是一个占用两个int大小对象的地址
//由于数组都开始于同一个地址，所以它们的值相同
printf("view[2][1]==%d *(*(view)+2)+1==%d\n",
view[2][1], * (*(view+2)+1));
//二维数组的第三个元素的第二个元素的值(三行二列的值)
//两种表示法都能得到相同的结果，当然数组表示法更简单
指针数组
int *p[10];
//p是一个包含10个int *类型元素的数组，每个元素都指向一个int类型变量
int (*p)[10];
//p是一个指向数组的指针，该数组内含10个int类型元素
int a[10];
int *p[10];
指向多维数组的指针
int (*pr)[2];//pr指向一个含两个int类型的数组
int * pz[2];//因为[]优先级比*高，不加()表明pz是一个数组，数组中每个元素都是指向int类型的指针
指针的兼容性
指针之间的赋值比数值类型之间的赋值要严格，不能使用隐式类型转换进行类型转换
更复杂的类型更为严格：
int* pt;
int(*pa)[3];
int ar1[2][3];
int ar2[3][2];
int** pr;//指向指针的指针
//effective 都是指向int的指针
pt = &ar1[0][0];
//effective 都是指向int的指针
pt = ar1[0];
//ineffective pt指向一个int类型值，而ar1指向一个内含3个int类型元素的数组
pt = ar1;
//ineffective ar2指向一个内含2个int类型元素的数组
pa = ar1;
//effective 都是指向3个int类型元素的数组的指针
pa = ar2;
//ineffective
pr = &pt;
//都是指向int的指针
*pr = ar2[0];
//都是指向int的指针
pr = ar2;
//ineffective
将const指针赋给非const指针是不安全的，因为这样可以使用新的指针改变const指针指向的数据
但把非const指针赋给const指针没问题，前提是只进行一级解引用
int x = 20;
const int y = 30;
int* p1 = &x;
const int* p2 = &y;
const int** pp3;
p1 = p2;//不安全--将const指针赋给非const指针
p2 = p1;//有效--将非const指针赋给const指针
pp3 = &p1;//不安全--嵌套指针赋值
printf("p1==%d p2==%d p3==%d", *p1, *p2, **pp3);
在进行两级解引用时，将非const指针赋给const指针不安全
const int** pp1;
int* p2=20;
const int n = 13;
pp1 = &p2;
//pp1是一个指向指针的常量指针，所以它不能直接被解引用
//而p2是一个普通的指针，可以直接被解引用
//因此，这里需要使用取地址运算符&来获取p2的地址
//但如果使用*运算符，那么pp1将被赋值为p2的值，而不是p2的地址
//这可能会导致未定义的行为，因为pp1现在指向了一个整数值，而不是一个指针
//允许这样赋值，但这导致const限定符失效
printf("%p %p\n%d %d", pp1,&p2,*pp1,p2);
*pp1 = &n;
printf("\n%d %d", **pp1, n);
*p2 = 10;
printf("\n%d %d", **pp1, n);
//将p2的地址赋给了pp1，即pp1指向了p2
//通过*pp1将n的地址赋给了pp1所指向的指针，即该指针现在指向了n
//通过解引用p2（即p2），将10赋值给了p2所指向的变量。
通过非const指针可以修改const指针所指向的数据，但结果是未定义的，不同编译器结果不同，不要这样做 Don't do this.
C和C++const的用法类似，但不完全相同
1.C++允许声明数组大小时使用const整数，但C不允许
2.C++不允许把const指针赋给非const指针，而C允许这样做
指针作为函数参数
void change(int* , int* y);//参数名可以省略
int main(void)
{
int x, y;
while (scanf_s("%d %d", &x, &y) == 2)
{
printf("x=%d,y=%d\n", x, y);
change(&x, &y);//传递地址给函数
printf("x=%d,y=%d\n", x, y);
}
return 0;
}
void change(int* x, int* y)
{
int middle;
middle = *x;//将指针指向地址上的值赋给middle
*x = *y;
*y = middle;
}
存储类别、链接和内存管理
存储类别
被存储的值都占用一定的物理内存，C语言把这样一块内存叫做对象(object)
面向对象编程中的对象是类对象，其定义包括数据和允许对数据进行的操作，C是面向过程语言
作用域
作用域描述程序中可访问标识符的区域，一个C变量的作用域可以是块、函数、函数原型、文件作用域
- 块是用一对花括号括起来的代码
在花括号{}内定义的变量，仅在当前块内可见 - 函数是函数定义中的函数体
在函数内部定义的变量，仅在当前函数内可见 - 函数原型是函数声明中的函数体
在函数声明时定义的变量，范围是到原型声明结束，因为编译器处理函数原型形参时只关系类型，不关心形参的名称，只有在变长数组中才有用 - 文件作用域是整个文件(全局变量)
在函数外部定义的变量，在整个文件中的任何函数内都可访问
链接
C变量有3种链接属性：外部链接、内部链接和无链接
具有块、函数或函数原型作用域的变量都是无链接变量，这意味着这些变量属于定义它们的块、函数或函数原型
具有文件作用域的变量可以是外或内部链接
外部链接变量可以在多文件程序使用，内部链接变量只能在一个翻译单元使用
C预处理实际上是用包含的头文件内容替换#include指令，所以会包含多个单独的物理文件，编译器把源代码文件和所有的头文件都看成是一个包含信息的单独文件。这个文件便是翻译单元(ranslation unit)。
描述一个具有文件作用域的变量时，它的实际可见范围是整个翻译单元，包括所有包含它的文件，如果程序由多个源代码文件组成，那么该程序也将由多个翻译单元组成，每个翻译单元均对应一个源代码文件和它所包含的文件。
在定义类型的前面使用static存储类别说明符，便是内部链接的全局变量
存储期
C变量有4种存储期：静态、动态分配、线程、自动
- 对象具有静态存储期，那么它在程序执行期间将一直存在，文件作用域变量具静态存储期
- 线程存储期用于并发程序设计，程序执行可被分为多个线程。具有线程存储期的对象，从被声明时到线程结束一直存在
- 块作用域的变量通常都具有自动存储期，当程序进入块时，为这些变量分配内存，当程序离开块时，释放内存。这种做法相当于把自动变量占用的内存视为一个可重复使用的工作区或暂存区，一个函数调用结束后，其变量占用的内存可用于存储下一个被调用函数的变量
- 块作用域也能具有静态存储期，创建这样的变量，要把变量声明在块中，且在前面加上关键字
static
有静态存储期的变量将从程序被载入到程序结束期间一直存在，但它的作用域仅限于声明它的函数块中，只有执行该函数时，程序才能使用该变量访问它指定的对象（但该函数可以给其他函数提供该存储区的地址以便间接访问该对象，例如通过指针形参或返回值）
寄存器变量
寄存器变量存储在CPU的寄存器中，或者最快的可用内存，但它们只能保存非常小的数据，例如，一个32位寄存器只能存储一个32位整数，处理和访问寄存器变量速度更快，但因为不是在内存中，所以无法获取寄存器变量的地址。和自动变量一样是块作用域、无链接和自动存储期
使用register可以请求为寄存器变量
因为编译器根据寄存器或最快内存的数量衡量你的请求，或者直接忽略你的请求，这样与普通的自动常量几乎相同，因为依旧不能对该变量使用地址运算符
静态变量
静态变量(static variable)或称局部静态变量
指该变量在内存中不动，不是值不变，具有文件作用域的变量自动具有(也必须是)静态存储期
以static存储类别说明符(提供静态存储期)声明
当程序离开它们所在函数后，这些变量不会消失，这种变量具有块作用域、无链接，但具有静态存储期，计算机在多次函数调用之间会记录它们的值
不能在函数形参中使用static
外部链接的静态变量
外部链接的静态变量具有文件作用域、外部链接和静态存储期，属于该类别的变量叫外部变量，把变量的定义性声明放在所有函数外便是外部变量
为了指出该函数使用了外部变量，可以在函数中使用关键字extern再次声明，如果不添加关键字，是创建了一个自动变量
如果一个源代码文件使用的外部变量定义在另一个源代码文件中，则必须使用extern在该文件中声明该变量
如果未初始化具有静态存储期的变量，它会自动初始化为0，这一原则也适用于外部定义的数组元素，只能使用常量表达式初始化文件作用域变量
只要不是变长数组，sizeof表达式可被视为常量表达式
不要用关键字extern创建外部定义，只用它来引用现有的外部定义
外部变量只能初始化一次，且必须在定义该变量时进行
C通过在一个文件中定义式声明，在其他文件中使用引用式声明来实现共享，也就是除定义式声明外，都要使用extern关键字，而且只有定义式声明才能initialize变量
内部链接的静态变量
内部链接的静态变量具有静态存储期、文件作用域和内部链接
使用static存储类别说明符声明
可以使用extern存储类别说明符，不会改变内部链接属性
函数也有存储类别外部(默认)、静态和内联
外部函数可以被其他文件的函数访问
静态函数只能用于其定义所在的文件
保护性程序设计的黄金法则："按需知道"原则
尽量在函数内部解决该函数的任务，只共享需要共享的变量
分配内存
所有程序都必须预留足够的内存来存储程序使用的数据
malloc()函数接受一个参数：所需的内存字节数，它会找到合适的空闲内存块，这样的内存是匿名的，也就是说malloc()分配内存，但不会为其赋名
但它确实返回动态分配的首字节地址，因此可以把该地址赋给一个指针变量，并使用指针访问这块内存
返回类型为指向void的指针。该类型相当于一个通用指针，malloc()函数可用于返回指向数组的指针、指向结构的指针等，该函数的返回值会被强制转换为匹配的类型
如果malloc()分配内存失败，将返回空指针
用malloc()请求内存要注意还需要一个指针记录这块内存的地址
double * ptr；
int n = 30；
ptr = (double *) malloc(n * sizeof(double));
该例为30个double型数据分配内存，并把地址赋给ptr，注意指针被声明为一个指向一个double类型，而不是指向内含30个double类型值的块
现在我们有三种创建数组的方法：
- 声明数组时，用常量表达式表示数组的维度，用数组名访问数组的元素，可以用静态内存或主动内存创建这种数组
- 声明变长数组时，用变量表达式表示数组的维度，用数组名访问数组的元素，只能在自动内存中创建
- 声明一个指针，调用
malloc()，将其返回值赋给指针，用指针访问数组的元素，该指针可以是静态或自动的
第二和第三种方法可以创建动态数组，可以在程序运行时选择数组的大小和分配内存
通常，malloc()要与free()配套使用，free()的参数是之前malloc()返回的地址，该函数释放之前malloc()分配的内存。
因此，动态分配内存的存储期从调用malloc()分配内存到调用free()释放内存为止。
free()函数的参数应该是一个指针，指向malloc()分配的一块内存。
不能使用free()释放其他方式分配的内存。
它们的原型在<stdilb.h>头文件中
如果内存分配失败，可以调用exit()函数结束程序，其原型在<stdilb.h>头文件中，标准提供了两个返回值以保证在所有操作系统中都能正常工作：
EXIT_SUCCESS表示普通的程序结束
EXIT_FAILURE表示程序异常终止，这种情况下，该函数返回空指针，程序结束
if(ptd == NULL)
exit(EXIT_FAILURE);
在C中不一定要使用强制类型转换，但C++必须使用
free()的重要性
静态内存的数量在编译时是固定的，在程序运行期间也不会改变。
自动变量使用的内存数量在程序执行期间自动增加或减少。
而动态内存的内存数量只会增加，除非用free()进行释放
void gobble(double ar[], int n);
int main(void)
{
double glad[2000];
...
for (int i = 0; i < 1000; i++)
gobble(glad, 2000);
...
return 0;
}
void gobble(double ar[], int n)
{
double* temp = (double*)malloc(n * sizeof(double));
.../*free(temp);*/ //假设忘记使用free()
}
第一次调用gobble()时，它创建指针temp，并分配2000个double类型的内存(一个double占8字节，便是16000字节内存)，当函数结束时，作为自动变量的指针temp也会消失，但指向的16000字节内存不会消失，由于temp指针已被销毁，所以无法访问这块内存，它也不能被重复使用，不断调用gobble()函数，便会循环以上的过程
这类问题被称为内存泄露(memory leak)
函数末尾处调用free()函数可避免这类问题发生
calloc()函数
分配内存还可以使用calloc()函数
long * new;
new = (long *)calloc(100, sizeof(long));
calloc()也返回指向void的指针，calloc()函数接受两个无符号整数作为参数(size_t类型)
第一个参数是所需的存储单元数量
第二个参数是每个存储单元的字节大小
它的一个特性是把块中所有位都设置为0
free()也可以释放calloc()`分配的内存
变长数组(VLA)和调用malloc()在功能上有些重合
但不同的是变长数组是自动存储类型，不必使用free()释放内存
malloc()创建的数组不局限于一个函数内访问，free()所用的指针变量可以和malloc()的指针变量不同，但两个指针一定存储相同的地址，不能释放同一块内存两次
malloc()也可以创建多维数组，但语法比较繁琐
double (*pt)[3];
pt = （double (*) [3]）malloc(2 * 3 * sizeof（double）);
//创建了一个2*3的二维数组
ANSI C类型限定符
const限定符
const float* pt;
float const* pt;
//等价于const float* pt;表示指向一个float类型的const值，指向的值不可变，pt本身可变
float* const pt;
//pt是一个指向float类型的指针，pt本身不变，但指向的值可变
const float* const pt;
//pt既不能指向别处，也不能改变它所指向的值
const可以创建变量、数组、结构
在文件间共享const数据要小心，可以采用两种策略:
- 把
const变量放在头文件中，在所有文件中包含这个头文件，这样就可以在所有文件中使用这个变量
但要注意，这种方案必须在头文件中使用关键字static声明全局const变量(以static声明的文件作用域变量具有内部链接属性)，如果没有static，将导致使用该头文件的文件都有一个相同标识符的定义式声明，C标准不允许这样做。
这种方案实际上相当于给每个文件提供一个单独的数据副本，该副本只对该文件可见，它的优点是可以偷懒，但它的缺点是，数据是重复的，如果const数据包含庞大的数组就不要偷懒 - 遵循外部变量的常用规则，即在一个文件中使用定义式声明，在其他文件中使用引用式声明
volatile限定符
volatile告诉计算机，代理可以改变该变量的值，通常用于硬件地址以及在其他程序或同时运行的线程中共享数据
这个以及后面几种限定符涉及编译器的优化，就不看了，我只想学C++
详见347页
文件输入/输出
有时需要程序从文件中读取信息或把信息写入文件，这种程序与文件交互的形式就是文件重定向(第8章讲过，但我没学嘿嘿，看来是正确的)
文件通常是在磁盘或固态硬盘上的一段已命名的存储区
C把文件看作一系列连续的字节，每个字节都能被单独读取，，这与UNIX环境中的文件结构相对应，由于其他环境中可能无法完全对应这个模型
C提供两种文件模型：文本模式和二进制模式
所有文件的内容都以二进制形式存储，如果文件最初使用二进制编码的字符表示文本，该文件就是文本文件，其中包含文本内容。如果文件中的二进制值表示机器语言代码或数值数据、图片、音乐编码，该文件就是二进制文件，其中包含二进制内容。
C提供两种访问文件的途径：文本模式和二进制模式
程序以文本模式读取文件时，把本地环境表示的行末尾或文件结尾映射为C模式。以二进制模式读取文件时，程序可以访问文件的每个字节
C程序会自动打开3个文件：标准输入(stdin为它的文件指针)、标准输出(stdout)、标准错误输出(stderr)
fopen和fclose函数
fopen()函数原型：
FILE *fopen (const char *path, const char *mode)
const char *path是一个字符串，用于指定要打开的文件路径及文件名
const char *mode是一个模式字符串，用于指定文件的访问模式
r：读模式打开文件
w：写模式打开文件，把现有文件的长度截为0，如果文件不存在则创建该文件
a：写模式打开文件，在文件末尾追加内容，如果文件不存在则创建该文件
r+：以更新模式打开文件(即可以读写文件)
w+：以更新模式打开文件(即可以读写文件)，如果文件存在则截断为0，如果文件不存在则创建该文件
a+：以更新模式打开文件(即可以读写文件)，在文件末尾追加内容，如果文件不存在则创建该文件，可以读整个文件，但只能从文件末尾添加内容
以上模式加个b就是以二进制模式打开文件
使用wx或w+x即使fopen()操作失败，原文件的内容也不会被删除，x会以独占模式打开文件
程序成功打开文件后，fopen()将返回文件指针，其他I/O函数可以使用这个指针指定该文件
文件指针的类型是指向FILE的指针，FILE是一个定义在stdio.h中的派生类型。文件指针并不指向实际的文件，它指向一个包含文件信息的数据对象，其中包含操作文件的I/O函数所用的缓冲区信息。
因为标准I/O函数使用缓冲区，所以它们不仅要知道缓冲区，所以它们不仅要知道缓冲区的位置，还要知道缓冲区被填充的程度以及操作哪一个文件。
标准I/O函数根据这些信息在必要时决定再次填充或清空缓冲区。文件指针指向的数据对象包含了这些信息(该数据对象是一个C结构)
fclose()函数原型：
int fclose (FILE *stream)
FILE *stream是一个指向FILE对象的指针，该FILE对象标识了要关闭的流。
对于输出流，fclose函数会在文件关闭前刷新缓冲区，如果执行成功，fclose函数返回零值。当文件不再需要时，使用此函数关闭文件可以释放系统资源，并确保所有缓冲区中的数据都写入文件。
如果调用成功，则函数返回0；否则，函数返回 EOF
getc函数和putc函数
ch = getchar();
//从标准输入获取一个字符
ch = getc(fp);
//从fp指定的文件中获取一个字符读入ch
putc(ch, fp);
//把ch的字符放入FILE指针fp指定的文件中
在put()函数的参数列表中，第一个参数是待写入的字符，第二个参数是FILE指针，表示把字符写入到指针指向的文件中
如果get()函数在读取到一个字符时发现是文件末尾，将返回EOF，C程序只有在读到超过文件末尾时才会发现文件的结尾
int ch;
FILE* fp;
fp = fopen("test.txt", "a");
while ((ch = getc(fp)) != EOF)
{
putchar(ch);
}
fclose(fp);
if (fclose(fp) == EOF)
printf("error");
//fclose(fp)关闭fp指定的文件，必要时刷新缓冲区
//如果成功关闭fclose()返回0，否则返回EOF
文件I/O
文件I/O函数要用指向FILE的指针指定一个文件，或者使用fopen()的返回值
fprintf()和fscanf()函数的工作方式与printf()和scanf()类似，区别在于前者需要用第一个参数指定待处理的文件
fprintf()函数原型：
int fprintf ( FILE *stream, const char *format [, argument] ... )
FILE *stream：这是一个文件流指针，用于指定需要操作的数据流。这个参数指向一个已经打开的文件或者设备，例如一个硬盘上的文本文件或者一个串口设备。
const char *format：这是一个格式化字符串，由格式化占位符和普通字符组成。格式化占位符以%开头，主要用于指明输出参数值的格式化方式。普通字符是原封不动写入到文件中的字符，如逗号、空格、换行符等。
可选的附加参数：这部分参数需要与格式化字符串中的占位符一一对应，它们会被传递给相应的函数进行处理。这些参数可以是任何类型，包括整数、浮点数、字符指针等。
fscanf()函数原型：
int fscanf ( FILE *stream, const char *format [, address, maxsize] )
FILE *stream 是一个文件流指针，用于指定需要操作的数据流
const char *format 是一个格式化字符串，由格式化占位符和普通字符组成
格式化占位符以%开头，主要用于指定输入数据的格式化方式
address 是一个可选参数，表示接收输入数据的目标地址
maxsize 是一个可选参数，表示要读取的最大字符数
rewind()函数接受一个文件指针作为参数，将文件指针重置到文件的开头
-
fgets()函数原型：
char *fgets(char *str, int n, FILE *stream)
第一个参数和gets()函数一样，也是表示存储位置的地址(char*类型)
第二个参数是一个整数，表示待输入字符串的大小
注意：字符串大小是字符串占用空间，字符串长度是字符串的字符个数
第三个参数是文件指针，指定待读取的文件 -
fputs()函数原型：
int fputs(const char *str, FILE *stream)
第一个参数是一个指向要写入的字符串的常量字符指针，也就是字符串的地址
第二个参数是一个文件指针，用于指定需要写入的文件或数据流
和puts()不同，fputs()在打印字符串时不会在其末尾添加换行符
这些在字符串那里讲过的，sb
-
fseek()函数原型：
int fseek(FILE *stream, long offset, int fromwhere)
第一个参数是一个文件指针，指向待查找的文件
第二个参数是偏移量
表示从起始点开始要移动的位置
可以加L后缀表示其值为long类型
正为前移，负为后移
应该是long类型，因为是希望移动的范围更大，能处理的文件更大
第三个参数是模式，该参数确定起始点
C语言中，起始位置有三种选择：
SEEK_SET：从文件开头，对应的常量值为0
SEEK_CUR：从文件的当前位置，对应的常量值为1
SEEK_END：从文件末尾，对应的常量值为2
fseek()正常返回0，出现错误返回值为-1 -
ftell()函数原型：
long ftell (FILE *stream)
它返回的是参数指向文件的当前位置距文件开始处的字节数
通过返回距文件开始处的字节数来确定文件的位置，文件的第1个字节到文件开始处的距离是0，第2个字节到文件开始处的距离是1，依次类推
该定义使用于以二进制模式打开的文件，以文本模式打开的文件情况不同 -
fgetpos()函数原型：
int fgetpos (FILE *stream, fpos_t *pos)
FILE *stream是一个指向FILE对象的指针，该FILE对象标识了流
fpos_t *pos是一个指向fpos_t类型的指针，用于存储文件指针的位置信息
它把fpos_t类型的指针放在pos指向的位置上，该值描述了文件中的当前位置距文件开头的字节数
如果函数调用成功，则返回0；否则返回非0值 -
fsetpos()函数原型：
int fsetpos (FILE *stream, const fpos_t *pos)
FILE *stream是一个指向FILE对象的指针，该FILE对象标识了流
const fpos_t *pos是一个指向fpos_t类型的指针，用于存储文件指针的位置信息
调用时，使用pos指向位置上的fpos_t类型值来设置文件指针指向偏移该值后指定的位置
如果函数调用成功，则返回0；否则返回非0值
它们都使用新类型fpos_t(file position type，文件定位类型)它不是基本类型，它根据其他类型来定义，fpos_t类型的变量或数据类型可以在文件中指定一个位置，它不能是数组类型
结构和其他数据形式
struct book
{
char name[20];
char author[20];
float value;
} /*book1*/ ；//在这里也可以直接定义结构变量
//未创建实际的数据对象，只描述了该对象由什么组成
struct book book1 = {
"C++入门到入土",
"张三",
95.5
}; //定义了一个结构体变量并初始化，各初始化项用逗号分隔
//如果初始化一个静态存储期的结构，初始化列表中的值也必须是常量表达式
printf("书名：%s\n", book1.name);
printf("作者：%s\n", book1.author);
scanf("价格：%f\n", &book1.value);//点优先级比取址符高，所以可以不加括号
//使用结构成员运算符点(.)访问结构中的成员
struct book book2 = {
.author = "张三",
.value = 95.5,
.name = "C++入门到入土"
/*100*/ //对特定成员的最后一次赋值才是它实际获得的值，因为name后面是value成员，所以去掉注释会让value的值为100
}
//可以使用指定初始化器(使用点运算符和成员名)标识特定的元素
结构数组
创建一个内含n个结构变量的数组，由于该数组是自动存储类别的对象，其中的信息存储在栈中，大的数组可能会占用大量的栈空间，会导致一些问题
可以更改编译器选项设置里的栈大小、使用较小的数组、创建为静态或外部数组(这样编译器就不会把数组放在栈中)
栈和内存都是计算机中的存储区域，但它们有不同之处
栈是一块用于存储数据的特殊内存区域，它遵循后进先出（LIFO）的原则，即最后存入的数据会被首先取出。栈内存是为线程留出的临时空间，每个线程都有一个固定大小的栈空间，并且栈空间存储的数据只能由当前线程访问，因此它是线程安全的。栈空间的分配和回收是由系统自动处理的，无需手动控制 。
内存是指计算机中用于存储各种数据和程序的通用存储区域。它包括堆内存和栈内存两部分。堆内存是一块动态分配的内存区域，可以根据程序的需要随时分配和释放，而栈内存则是在程序运行时由编译器自动分配和释放的固定大小的内存区域。堆内存主要用于存储动态生成的数据结构，如数组、对象等，而栈内存则用于存储局部变量、函数调用等短暂存在的数据 。
总结而言，栈是一种特殊的内存区域，用于存储局部变量和函数调用的信息，遵循后进先出原则。而内存是更广泛的概念，包括堆内存和栈内存，用于存储各种数据和程序
struct book library[100];
library //一个book结构的数组
library[2] //数组中的第3个元素，为book结构
library[2].name //一个char数组，library[2]的name成员
library[2].name[3] //library[2]的name成员的第4个元素
/*library[2].name返回的是字符数组的指针
而library[2].name[3]返回的是字符数组中特定位置上的字符值*/
嵌套结构
struct names {
char name[20];
char worknumber[12];
};
struct guy {
struct names ID;
//该声明表明ID是一个struct names类型的变量
char addrss[20];
char job[20];
double salary;
};
struct guy a1 = {
{"迪迦","M870012"},
"the earth",
"练习生",
999999999.98
};
int main(void)
{
printf("name:%s\n", a1.ID.name);
printf("ID:%s\n", a1.ID.worknumber);
//访问嵌套结构的成员，在这里需要使用两次结构成员运算符
//从左到右进行寻找
printf("address:%s\n", a1.addrss);
printf("job:%s\n", a1.job);
printf("salary:%.2lf", a1.salary);
if (a1.salary > 2000)
puts("!");
return 0;
}
指向结构的指针
strct guy *p1;
//关键字 结构标记 指针
p1 = &a1;
//和数组不同，结构变量名不是结构变量的地址，因此要加&
p1->ID.name
//结构体指针运算符，指向ID.name
p1->job
//就是a1.job
/*如果p1 == &a1那么*p1 == a1，因为它们是互逆的
a1.job == (*a1).job
必须使用圆括号，因为点运算符比*运算符的优先级高
a1.job == *(a1).job == p1->job
*/
向函数传递结构的信息
struct funds {
char bank[30];
double bankfund;
char save[30];
double savefund;
};
struct funds cute = {
"谢的银行账户",
9999999.99,
"裴的储蓄账户",
100000000.99
};
double sum(double, double);
int main(void)
{
printf("一共是%.2lf人民币\n", sum(cute.bankfund, cute.savefund));
return 0;
}
double sum(double bank, double save)
{
return (bank + save);
}
//只要结构成员是一个具有单个值的数据类型，便可以把它作为参数传递给接受该特定类型的函数
//函数不关心实参是否是结构成员，只需类型正确即可
//如果需要在被调函数中修改主调函数成员中的值，就要传递成员的地址
double sum(const struct funds *);
//参数是一个指针
int main(void)
{
printf("一共是%.2lf人民币\n",sum(&cute));
return 0;
}
double sum(const struct funds * money)
{
return (money->bankfund + money->savefund);
}
//一定记的使用&运算符来获取结构的地址，和数组名不同，结构变量名不是其地址的别名
//但对于数组类型，无论是结构体数组还是其他类型的数组，其数组名都是一个地址常量，表示数组首元素的地址
double sum( struct funds structure);
//参数是一个结构
int main(void)
{
printf("一共是%.2lf人民币\n",sum(cute));
return 0;
}
double sum( struct funds structure)
{
return (structure.bankfund+structure.savefund);
}
//调用sum函数时，编译器根据funds结构创建了一个名为structure的自动结构变量
//传递指针使用原始结构计算，传递结构使用结构的副本计算
C允许将一个结构赋值或给另一个相同类型的结构
也可以把一个结构初始化为相同类型的另一个结构
指针作为参数执行更快，因为只需传递地址，缺点是无法保护数据，但const限定符可以解决这个问题
复合字面量与结构
if (cute.bankfund > cute.savefund){
structure = (strcut book) {"C++入门到入土",
"张三",
95.5};
}
else{
structure = (strcut book) {"C++不是人学的",
"张三",
100};
}
/*完全可以这样写
因为复合字面量是匿名的，所以必须在创建的同时使用它，这里是使用复合字面量为一个结构变量提供不同的值*/
struct res { double x; double y; };
double res_area(struct res r)
{
return r.x * r.y;
}
int main(void)
{
double area;
area = res_area( (struct res) { 10.5, 20.0 } );
printf("%f", area);
return 0;
}
//可以把复合字面量作为函数的参数，如果函数接受一个结构，就可以把复合字面量作为实际参数传递
struct res { double x; double y; };
double res_area_ptr(struct res *ptr)
{
return ptr->x * ptr->y;
}
int main(void)
{
double area;
area = res_area_ptr( &(struct res) { 10.5, 20.0 } );
printf("%f", area);
return 0;
}
//如果函数接受一个地址，可以传递复合字面量的地址
复合字面量在所有函数的外部，具有静态存储期；如果在块中，则是自动存储期；复合字面量和普通初始化列表的语法规则相同，也就是说，可以在复合字面量中使用指定初始化器(标记化结构初始化语法)
匿名结构
即没有名称的结构
struct person{
struct {
char name[20];
char worknumber[12];//匿名结构
};
int age;
};
sturct person zs = { { "张三", "13K8DS6" }, 20 };
puts(zs.name);//使用匿名便可以在访问时省略简化步骤
联合
它能在同一个内存空间中存储不同的数据类型(不是同时存储)
典型用法是设计一种表以存储无规律的混合类型，使用联合类型的数组，其中的联合大小都相等，每个联合可以存储各种数据类型
union hold {
int digit;
double bigfl;
char letter;
};
//创建联合模板
//可以初始化联合，需要注意联合只能存储一个值，这与结构不同
union hold valA;
valA.letter = 'a';
union hold valB = valA
//用另一个联合来初始化
union hold valC = {88};
//初始化联合的digit成员
union hold valD = {.bigfl = 88.8};
//使用指定初始化器(标记化结构初始化语法)
union hoid fit;
fit.digit = 10;
fit.bigfl = 12.0;
fit.letter = 'a';
//最后fit存储a，因为在联合中，一次只能存储一个值，即使有足够的空间，也不能同时存储不同类型的值
pt = &fit;
x = pt->digit;
//用指针访问联合和结构一样
匿名联合和匿名结构工作原理相同
枚举
可以用枚举类型声明符号名称来表示整形变量。可以创建一个新类型并指定它的可具有的值(enum常量是int类型，只要能使用int类型的值，就能使用枚举类型)。枚举类型的目的是提高程序可读性，它的语法和结构语法相同
enum spectrum {red,orange,yellow,green,blue,violet};
//声明枚举类型，花括号内的标识符枚举了spectrum变量可能有的值，这些符号常量被称为枚举符
enum spectrum color;
//声明color作为该类型的变量，它的值是花括号中的某个值
/*在这里red值为0，orange为1，以此类推
只要是能使用整形常量的地方就可以使用枚举常量
例如，声明数组时可以用枚举常量表示数组大小；switch语句可以把枚举常量作为标签*/
enum levels {low=100,medium=500,high=1000};
//如果只给一个枚举变量赋值，后面的常量会自动赋予后续值
因为枚举类型是整数类型，所以可以在表达式中以使用整型变量的方式使用enum变量，用在case语句中很方便
typedef
- 与#define不同，typedf创建的符号名只受限于类型，不能用于值
- typedef由编译器解释，不是预处理器
- 在其受限范围内，typedef比#define更灵活
typedef unsigned char BYTE;
BYTE x,y[10],* z;
/*定义BYTE为无符号字符类型
x为BYTE类型变量，y为10个BYTE类型元素的数组，z为指向BYTE类型元素的指针*/
//定义的作用域取决于typedef定义所在的位置，typedef使用名称遵循变量的命名规则
为现有类型创建一个名称，看上去多此一举，但有时的确很有用
在示例中，用BYTE代替unsigned char表明你打算用BYTE类型的变量表示数字，而不是字符码，使用typedef还能提高程序的可移植性
typedef char * STRING;
/*有typedef关键字，编译器将把STRING解释为一个类型的标识符，该类型是指向char的指针
没有typedef关键字，编译器将把STRING识别为一个指向char的指针变量*/
typedef struct comple {
float real;
float imag;
}COMPLE;
//定义一个结构体类型，用typedef创建COMPLE类型来代替comple结构
//用typedef来命名一个结构类型时，可以省略该结构的标签
COMPLE C1={1.0,2.0};
COMPLE C2;
//以上代码将被翻译成：
struct {float real;float imag;} C1={1.0,2.0};
struct {float real;float imag;} C2;
C2=C1;
//typedef常用于给复杂的类型命名
typedef char (* PRICE ()) [5];
//把PRICE声明为一个函数类型，该函数返回一个指针，指针指向内含5个char类型元素的数组
//typedef并没有创建任何新类型，它只是为某个已存在的类型增加一个方便使用的标签
//可以使用typedef建立一系列相关类型
typedef int ar5[5];
typedef ar5；
typedef *pt_ar5 arp10[10];
ar5 ar1; //ar1是一个内含5个int类型元素的数组
pt_ar5 ptar;//ptar是一个指向数组的指针，该数组内含5个int类型元素
arp10 arp; //arp是一个内含10个指针的数组，每个指针都指向一个内含5个int类型元素的数组
此处笔记有误
函数和指针
函数指针常用作另一个函数的参数，告诉该函数要使用哪一个函数
指向函数的指针存储函数代码起始处的地址
声明一个数据指针时，必须声明指针所指向的数据类型
声明一个函数指针时，必须声明指针所指向的函数类型
即指明函数的返回类型和形参类型
void (*pf) (char *);
//pf是一个指向函数的指针，该函数有一个char *类型的参数
void *pf(char *);
//省略圆括号表示pf是一个返回字符指针的函数
//声明函数指针后，可以把类型匹配的函数地址赋给它，函数名可用于表示函数地址
void TOupper(char *);
void TOlower(char *);
int aha(double)；
void (*pf)(char *);
pf=TOupper;
pf=TOlower;
pf=aha; //ineffective，类型不匹配
pf=TOlower();//ineffective，因为不是地址
//数据指针访问数据，函数指针也能访问函数
char miss[] = "I miss you!";
pf=TOupper;
(*pf) (miss);
pf=TOlower;
pf(miss);
/*第1种方法显而易见：因为pf是指向TOupper函数，那么*pf就相当于TOupper函数
第2种方法：由于函数名是指针，那么函数名和指针可以互换使用，从赋值表达式便可以看出二者是等价的*/
void show(void (*fp) (char *),char * str);
/*声明了两个形参，fp形参是一个函数指针，str是一个数据指针
fp指向的函数接受char * 类型的参数，返回类型void；str指向一个char类型的值*/
show(TOupper,miss);
//show使用TOupper函数，fp = TOupper
show(pf,miss);
//show使用pf指向的函数：fp = pf
void show(void (*fp) (char *),char * str)
{
(*fp)(str);//把所选函数作用于str
puts(str);
}
位操作
1字节最大能表示数字是2的8次方
程序可以用1字节存储0 ~ 255的数，或-128 ~ +127
二进制(binary number)
二进制补码是最常用的系统，它用1字节中的后7位表示0~127
高阶位为0表示正，高阶位为1表示负
二进制补码能表示-128 ~ 127范围内的数
二进制反码通过反转每一位形成一个负数
二进制反码能表示-127 ~ 127范围内的数
二进制浮点数分两部分存储：二进制小数和二进制指数
.101 = 1/2 + 0/4 + 1/8
//从左往右，使用2的幂作为分母
八进制(octal)
每个八进制位对应3个二进制位
//八进制与二进制等价表
0 = 000
1 = 001
2 = 010
3 = 011
4 = 100
5 = 101
6 = 110
7 = 111
十六进制(hexadecimal)
//十进制、十六进制与二进制等价表
0 = 0 = 0000
1 = 1 = 0001
2 = 2 = 0010
3 = 3 = 0011
4 = 4 = 0100
5 = 5 = 0101
6 = 6 = 0110
7 = 7 = 0111
8 = 8 = 1000
9 = 9 = 1001
10 = A = 1010
11 = B = 1011
12 = C = 1100
13 = D = 1101
14 = E = 1110
15 = F = 1111
C按位运算符
二进制反码(按位取反)
一元运算符 ~ 把1变为0，把0变为1
注意：该运算符不会改变原有值，但确实创建了一个可使用或赋值的新值
按位与
二元运算符 & 通过逐位比较两个运算对象，生成一个新值
相应位都为真则结果为真，否则为假
a &= 0377 == a = a & 0377
按位或
二元运算符 | 通过逐位比较两个运算对象，生成一个新值
相应位其一或两个位都为真则结果为真，否则为假
a |= 0377 == a = a | 0377
按位异或
二元运算符 ^ 通过逐位比较两个运算对象，生成一个新值
相应位其一为真结果为真，都为真则为假
a ^= 0377 == a = a ^ 0377
用法
按位与运算符常用于掩码(mask)
掩码是通过二进制的位操作隐藏或者关闭某些数位上的数据，ASCLL码只使用后7位，最高位保留。因此其掩码只需要使最高位为0，其余位为1(0111 1111)
#define MASK 2
//二进制为00000010
a &= MASK;
/*把a中除1号位以外所有值设置为0，因为 & 任意一位为0则为0
这个过程叫做使用掩码，因为掩码中的零隐藏了a中相应的*/
打开位(设置位)
打开一个值中的特定位，同时保持其他位不变
a |= MASK;
/*1号位为1，其余不变，因为 | 任意一位为1则为1
根据MASK中为1的位，把a中相应位设置为1，其余位不变*/
关闭位(清除位)
关闭一个值中的特定位，同时保持其他位不变
a &= ~MASK;
/*一元运算符 ~ 把1变为0，把0变为1
~00000010 == 11111101
使用 & 都为1则为1*/
切换位
指打开已关闭的位或关闭已打开的位
a ^= MASK;
/*1^1=0 1^0=0
位都为1则为0，其一为1则为1*/
检查位的值
if ((a & MASK) == MASK)
/*只检查a的一号位是否为1
按位与运算符优先级比==低，需要加圆括号
为避免信息漏过边界，掩码至少要与其覆盖的值宽度相同*/
移位运算符
左移
左移运算符 << 把左侧运算对象向左移动右侧运算对象指定的位数
左侧运算对象移出最末端位的值丢失，用0填充空位
10001010 << 2 == 00101000
int a = 1,b;
b = a << 2;//把4赋给b
a <<= 2; //将a的值改为4
右移
右移运算符 >> 把左侧运算对象向右移动右侧运算对象指定的位数
左侧运算对象移出最末端位的值丢失，对于无符号类型用0填充空位；对于有符号类型，结果取决于机器，用符号位(最左边的位)的副本填充
//有符号类型的两种结果
10001010 >> 2 == 00000010
10001010 >> 2 == 11100010
int a = 16,b;
b = a >> 3;//把2赋给b
a >>= 3; //将a的值改为2
移位运算符针对2的幂提供快速有效的乘法和除法
number << n//乘以2的n次幂
number >> n//如果number非负，则除以2的n次幂
C预处理器和C库
C预处理器在程序执行之前查看程序，根据程序中预处理器指令，预处理器把符号缩写替换成其表示的内容
在预处理之前，编译器必须对程序进行翻译处理
- 首先编译器把源代码中出现的字符映射到源字符集，该过程处理多字节字符和三字节字符
- 编译器定位每个反斜杠后面跟着换行符的实例，并删除它们
把下面两个物理行:
printf("Hello,
world!\n");
转换成一个逻辑行:
printf("Hello, world!\n");
预处理器表达式长度必须是一个逻辑行，一个逻辑行可以是多个物理行 - 编译器把文本划分成预处理记号序列、空白序列和注释序列(记号是由空格、制表符或换行符分隔的项)
编译器将用一个空格替代每一条注释
可以用一个空格替换除换行符之外的所有空白字符序列
最后，程序已准备好进入预处理器阶段，预处理器查找一行中以#号开始的预处理器指令
明示常量:#define
指令可以出现在源文件的任何地方，其定义从指令出现的地方到该文件末尾有效
指令的长度仅限于一行，但可以通过反斜杠延续定义
#define NAME value
预处理器指令 宏 替换体
代表值的宏被称为类对象宏
宏的名称不允许有空格，且遵循C变量的命名规则
当预处理器在程序中找到宏后，就会用替换体代替该宏(有例外)
从宏变成最终替换文本的过程称为宏展开
宏可以表示任何字符串,甚至整个C表达式
宏定义可以包含其他宏
宏定义可以包含参数
带有参数的宏和函数很类似
#define SUR(X) x*x
完全可以这样使用:
z=SUR(2);
//宏参数与函数参数不完全相同
SUR(5+2)
/*不是7的平方，而是5+2*5+2，因为预处理器不计算，不求值，只替换字符序列
函数调用在程序运行时把参数值传递给函数
宏调用在编译之前把参数记号传递给程序*/
#define SUR(X) (x)*(x)
现在SUR(5+2)替换为(5+2)*(5+2)
但并未解决所有问题
100/SUR(2)
将变成：
100/2*2
#define SUR(X) (x*x)
现在
100/SUR(2) == 100/(2*2)
要处理前面的两种情况，要这样定义
#define SUR(X) ((x)*(x))
因此，必要时使用足够多的圆括号保证运算和结合的正确顺序
但若使用递增或递减运算符运算符还是会出错
所以不要在宏中使用递增或递减运算符
类函数宏
宏函数与函数相比有其独特的优势
- 宏函数在运行速度上要比函数快，原因是函数调用需要额外的过程，如开辟和释放栈空间、记录返回地址等，而宏函数则不需要这些过程。
- 宏函数没有参数类型约束，适合于任何能用 > 比较的类型，与此相反，函数的参数必须声明为特定的数据类型。
- 宏函数在编译之前就进行了替换，不占用运行时内存，也无需保存现场和跳转等过程。
宏函数的主要作用是提高程序的执行效率
在C语言中，宏代码本身并不是函数，但在使用上却像函数一样。预处理器会通过复制宏代码的方式来替代函数调用，从而避免了参数压栈、生成汇编语言的CALL调用、返回参数以及执行return等过程，以此达到提升速度的目的
宏函数也有其缺点
- 由于预处理器在复制宏代码时可能会产生一些意想不到的边际效应，使用宏函数容易引发错误。
- 宏函数的参数替换是直接替换的，不经过任何计算，这可能导致潜在的问题。
- 由于宏展开可能会导致目标文件变大，从而使得程序的执行效率降低。
/*C允许在字符串中包含宏参数
在类函数宏的替换体中，#号作为一个预处理运算符，可以把记号转换成字符串
如果X是一个形参名，那么#x就是转换为字符串"#"的形参名，这个过程叫字符串化*/
#define PSO(X) printf("The "#X" is %d\n",((X)*(X)))
int main(void)
{
int y = 5;
PSO(y);
PSO(2 + 4);
}
调用宏时将用实参替换#X
ANSI C字符串的串联特性将这些字符串与printf()语句的其他字符串组合，生成最终的字符串
printf("The" "y" "is %d\n",((y)*(y)))
然后字符串串联功能将这3个相邻的字符串组合成一个字符串
##运算符
与#运算符类似，##运算符可用于类函数宏的替换部分。还可以用于对象宏的替换部分
运算符把两个记号组合成一个记号
#define ADD(N) X ## N
#define ADD2(N) printf("X "#N" =%d\n",X ## N)
int main(void)
{
int ADD(1) = 10;
int ADD(2) = 20;
int X1 = 30;
ADD2(1);
ADD2(2);
ADD2(3);
}
ADD宏用##运算符把记号组合为一个新的标识符
ADD2宏用#运算符组合字符串
变参宏
一些函数接受数量可变的参数，stdvar.h头文件让用户自定义带可变参数的函数
通过把宏参数列表中最后的参数写成省略号(三个点)来实现这一功能
预定义宏__VA_ARGS__用在替换部分中，表示省略号代表什么
#define PR(X,...) printf("Message "#X" :" __VA_ARGS__)
int main(void)
{
double x = 48;
double y = 64;
PR(1, "x=%g\n", x);
PR(2, "x=%.2f,y=%.2f\n", x, y);
return 0;
}
省略号只能代替最后的宏参数
宏和函数的选择
使用宏比使用普通函数复杂，稍有不慎便会产生奇怪的副作用
宏和函数的选择实际上是时间和空间的权衡
宏产生内联代码，即在程序中生成语句
调用20次宏就是在程序中插入了20行代码
调用20次函数，程序中只有一份函数语句的副本，所以节省了空间
然而另一方面，程序的控制必须跳转至函数内，再返回主调函数，这比内联代码花费更多时间
C99提供第三种可替换的方法——内联函数
对于简单函数通常使用宏
#define MAX(x,y) ((x)>(y)?(x):(y))
#define ABS(X) ((X)<0?-(X):(X))
注意以下几点：
- 宏名不允许有空格，但替换字符串中可以有空格
- 用圆括号把宏参数和整个替换体括起来，确保宏正确的展开
- 用大写字母表示宏函数名，提醒程序员宏可能产生的副作用
- 如果打算用宏来加快程序运行速度
首先确定使用宏和使用函数是否有较大差异
在程序中只使用一次的宏无法明显减少程序的运行时间，在循环嵌套中使用宏更有助于提高效率
如果开发了一些方便的宏函数，用#include指令来包含它们
文件包含:#include
当预处理器发现#include指令时，会查看后面的文件名并把文件的内容包含到当前文件中，即替换源文件中的#include指令。这相当于把包含文件的全部内容输入到源文件#include指令所在的位置
#include <stdio.h>
//在标准系统目录中查找该文件
#include "hot.h"
#include "/user/big/p.h"
//在当前目录中(或文件名中指定的其他目录)查找该文件，如果未找到再查找标准系统目录
头文件常用形式：
- 明示常量
- 宏函数
- 函数声明，函数声明都是函数原型形式
- 结构模板定义
- 类型定义
还可以使用使用头文件声明外部变量供其他文件共享
-
#undef
undef指令用于取消已定义的#define指令
如果想使用一个名称又不确定之前是否使用过，为安全起见可以用该指令取消该名字的定义
-
#ifdef和#else以及#endef
与
if和else很像，主要区别是：编译器不识别用于标记块的花括号这些指令结构可以嵌套
防卫式声明 #ifdef #define ... #endef -
error
让预处理器发出错误信息
高级数据表示
链表
调用malloc() N次，为N个结构请求分配足够的空间
调用malloc() N次，分别为每个结构请求分配足够的空间
前者分配的是连续的内存块，只需要一个单独指向struct变量的指针，该指针指向已分配块中的第一个结构，简单的数组表示法让指针访问块中的每个结构
后者无法保证每次调用malloc()都能分配到连续的内存块，结构不一定被连续存储，需要存储N个指针，每个指针指向一个单独存储的结构
一种解决方法是创建一个大型指针数组，并在分配新结构时逐个给这些指针赋值，但如果用不完，还是会浪费一些空间
更好的方法是每次使用malloc()为新结构分配内存时，也为新指针分配内存。
但需要另一个指针来跟踪新分配的指针，用于跟踪新指针的指针本身也需要一个指针来跟踪，以此类推
struct film{
char title[20];
int rating;
struct film* next;
}
每个结构中包含指向next结构的指针，当创建新结构时，可以把该结构的地址存储在上一个结构中
虽然结构不能含有与本身类型相同的结构，但可以含有指向相同类型的指针
这种定义是定义链表(linked list)的基础
链表中的每一项都包含者在何处能找到下一项的信息
需要一个单独的头指针存储第1个结构的地址
该指针被称为头指针
struct film {
char title[30];
int rating;
struct film* next;//指向链表中的下一个结构
};
int main(void)
{
struct film* head = NULL;
struct film* prev = NULL, * current = NULL;
char input[30];
puts("Enter first movie title:");
while (gets(input, 29) != NULL && input[0] != '\0') {
current = (struct film*)malloc(sizeof(struct film));
if (head == NULL)
head = current;
/*链表的头指针指向第一个结构
随后每个结构的地址应存储在其前一个结构的指针成员中*/
else
prev->next = current;
current->next = NULL;
/*指针prev指向上一次分配的结构
把指针成员设置为NULL
表明当前结构是链表的最后一个结构*/
strcpy(current->title, input);
puts("Enter your rating<0~10>:");
scanf("%d", ¤t->rating);
while (getchar() != '\n')
continue;
puts("Enter next mobie title(empty line to stop):");
prev = current;
/*最后为下一次输入做准备
设置prev指针指向当前结构
因为在用户输入下一部电影且程序为新结构分配内存后
当前结构将成为新结构的上一个结构*/
}
if (head == NULL)
printf("No data enterd.");
else
puts("Here is the movie list:");
current = head;
while (current != NULL) {
color(9);
printf("Movie:%s Rating:%d\n",
current->title,current->rating);
current = current->next;
}
color(0);
current = head;
while (current != NULL) {
head = current->next;
free(current);
current = head;
/*为每个已分配内存的结构释放内存*/
}
return 0;
}
该程序有许多不足，例如没有检查malloc()是否成功请求到内存，也无法删除链表中的项，但这些问题可以解决
这种用特定方法解决特定问题，并且在需要时才添加相关功能的编程方式通常不是最好的解决方案
很多成功的大型程序都是由成功的小型程序逐步发展而来
如果要修改程序，首先应该强调最初的设计，并简化其他细节
该程序没有遵循这个原则，它把概念模型和代码细节混在一起
该程序的概念模型是在一个链表中添加项，但程序却把一些细节放在最明显的位置，没有突出接口
如果程序能以某种方式强调给链表添加项，并隐藏具体的处理细节会更好
把用户接口和代码细节分开的程序更容易理解和更新
抽象数据类型(ADT)
类型特指两类信息：属性和操作
计算机科学领域已开发一种定义新类型的好方法，用3个步骤完成从抽象到具体的过程：
-
提供类型属性和相关操作的抽象描述
这些描述既不能依赖特定的实现，也不能依赖于特定的编程语言
这种正式的抽象描述被称为抽象数据类型(ADT) -
开发一个实现ADT的编程接口
也就是指明如何存储数据和执行所需操作的函数
例如在C中，可以提供结构定义和操纵该结构的函数原型
这些作用于用户定义类型的函数相当于C基本类型的内置运算符
需要使用该新类型的程序员可以使用这个接口进行编程 -
编写代码实现接口
非正式但抽象的链表定义:链表是一个能存储一系列项且可以对其进行所需操作的数据对象
用一种简化的链表作为抽象数据对象，该类型总结如下：
类型名：简单链表
类型属性：可以存储一系列项
类型操作：初始化链表为空
确定链表为空
确定链表已满
确定链表中的项数
在链表末尾添加项
遍历链表，处理链表中的项
清空链表
下一步是为简单链表ADT开发一个接口
建立接口
这个简单链表的接口有两个部分
第1部分是描述如何表示数据
第2部分是描述实现ADT操作的函数
要设计在链表中添加项的函数和报告链表中项数的函数
接口设计应尽量与ADT的描述保持一致
因此，应该使用某种通用的类型，可以用C的typedef来定义所需的类型:
struct film {
char title[30];
int rating;
};
typedef struct film Item;
这样就可以在定义的其余部分使用Item类型
如果以后需要其他数据形式的链表，可以重新定义Item类型，不必改变其余的接口定义
typedef struct node {
Item item;
struct node * next;
}Node;
typedef Node * List;
List movies;//创建了该链表所需类型的指针movies
//着重理解该声明是创建了一个链表而不是指向节点的指针或一个结构
//movies代表的确切数据应该是接口层次不可见的实现细节
还可以用另一种方法定义List类型：
typedef struct list {
Node * head;//指向链表头节点的指针
int size; //记录链表中的项数
}List;
定义Item之后确定如何存储这种类型的项
在链表的实现中，每一个链节叫作节点(node)
每个节点包含形成链表内容的信息和指向下一个节点的指针
程序启动后应该把头指针初始化为NULL
但不要使用 movies = NULL 这样的语句
用Liat类型的结构会更好
movies.head = NULL;
movies.size = 0;
使用该类型的程序员只需要知道用InitializeList()函数来初始化链表，不必了解List类型变量的实现细节
这是数据隐藏的一个示例，数据隐藏是从编程的更高层次隐藏数据表示细节的艺术
/*操作：初始化一个链表*/
/*前提条件：plist指向一个链表*/
/*后置条件：该链表初始化为空*/
void InitilizeList(List* plist);
前提条件(precondition)是调用该函数前应具备的条件
后置条件(postcondition)是执行该函数后的情况
该函数的参数是一个指向链表的指针，而不是一个链表
InitilizeList(&movies);//使用该函数
由于按值传递参数，所以该函数只能通过指向该变量的指针才能更改主调程序传入的变量
这里由于语言的限制使接口和抽象描述略有区别
C语言把所有类型和函数的信息集合成一个软件包的方法是：
把类型定义和函数原型放在一个头文件中
该文件应该提供程序员使用该类型所需的所有信息
struct film {
char title[30];
int rating;
};
typedef struct film Item;
typedef struct node {
Item item;
struct node* next;
} Node;
typedef Node* List;
/*
还可以用另一种方法定义List类型：
typedef struct list {
Node* head; //指向链表头节点的指针
int size; //记录链表中的项数
}List;
*/
/*函数原型*/
/*操作： 初始化一个链表*/
/*前提条件：plist指向一个链表*/
/*后置条件：链表初始化为空*/
void InitializeList(List* plist);
/*操作： 确定链表是否为空，plist指向一个已初始化的链表*/
/*后置条件：如果链表为空，该函数返回true;否则返回false*/
bool ListIsEmpty(const List* plist);
/*操作： 确定链表是否已满，plist指向一个已初始化的链表*/
/*后置条件：如果链表已满，该函数返回true;否则返回false*/
bool ListIsFull(const List* plist);
/*操作： 确定链表中的项数，plist指向一个已初始化的链表*/
/*后置条件：该函数返回链表中的项数*/
unsigned int ListItemCount(const List* plist);
/*操作： 在链表的末尾添加项*/
/*前提条件：item是一个待添加至链表的项，plist指向一个已初始化的链表*/
/*后置条件：如果可以，该函数在链表末尾添加一个项，且返回true;否则返回false*/
bool AddItem(Item item, List* plist);
/*操作： 把函数作用于链表中的每一项
plist指向一个已初始化的链表
pfun指向一个函数，该函数接受一个Item类型的参数且无返回值*/
/*后置条件：pfun指向的函数作用于链表中的每一项一次*/
void Traverse(const List* plist, void(*pfun)(Item item));
/*可以把函数指针作为参数传递给另一个函数,然后该函数就可以使用这个被指针指向的函数
pfun指向显示链表项的函数,然后Traverse()函数把该函数作用于链表中的每一项，显示链表中的内容*/
/*操作： 释放已分配的内存
plist指向一个已初始化的链表*/
/*后置条件：释放了为链表分配的所有内存，链表设置为空*/
void EmptyTheList(List* plist);
只有 InitializeList()、AddItem()、EmptyTheList()函数
要修改链表，这些函数需要一个指针参数
某些函数不需要修改链表，则不需要指针参数，可以用List类型变量作为参数，也可以如代码所示加以const限定符
使用接口
我们的目标是使用这个接口编写程序，但是不必知道具体的实现细节
#include <stdio.h>
#include <stdlib.h>//提供exit()的原型
#include "list.h"
void showmovies(Item item);
char* s_gets(char* st, int n);
int main(void)
{
List movies;
Item temp;
/*初始化*/
InitializeList(&movies);
if (ListIsFull(&movies)) {
fprintf(stderr, "No memeory available! Bye.\n");
exit(1);
}
/*获取用户输入并存储*/
puts("Enter first movie titile:");
while (s_gets(temp.title, 30) != NUll && temp.title[0] != '\n') {
puts("Enter your rating<0~10>:");
scanf("%d", &temp.rating);
while (getchar() != '\n')
continue;
if (AddItem(temp, &movies) == false) {
fprintf(stderr, "Problem allocating memory\n");
break;
}
if (ListIsFull(&movies)) {
puts("The list is now full.");
break;
}
}
/*显示*/
if (ListIsEmpty(&movies)) {
printf("No data entered.");
}
else {
printf("Here is the movie list.\n");
Traverse(&movies, showmovies);
}
printf("You entered %d movies.\n", ListItemCount(&movies));
/*清理*/
EmptyTheList(&movies);
printf("Bye!\n");
return 0;
}
void showmovies(Item item) {
printf("Movie:%s Rating:%d\n",
item.title, item.rating);
}
char* s_gets(char* st, int n) {
char* ret_val;
char* find;
ret_val = fgets(st, n, stdin);
if (ret_val) {
find = strchr(st, '\n');//查找换行符
if (find)
*find = '\n';//如果地址不是NULL，在此处放置一个空字符
else
while (getchar() != '\n')//处理输入行的剩余内容
continue;
}
return ret_val;
}
实现接口
C方法是把函数定义统一放在list.c文件中
整个程序由
list.h(定义数据结构和提供用户接口的原型)
list.c(提供函数代码实现接口)
film3.c(把链表接口应用于特定编程问题的源代码文件)
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
/*局部函数原型*/
static void CopyToNode(Item item, Node* pnode);
/*接口函数*/
/*把链表设置为空*/
void InitializeList(List* plist) {
plist = NULL;
}
/*如果链表为空，返回true*/
bool ListIsEmpty(const List* plist) {
(*plist == NULL) ? true : false;
}
/*如果链表已满，返回ture*/
bool ListIsFull(const List* plist) {
Node* pt;
pt = (Node*)malloc(sizeof(Node));
int full = (pt == NULL) ? true : false;
free(pt);
return full;
}
/*返回节点的数量*/
unsigned int ListItemCount(const List* plist) {
unsigned int count = 0;
Node* pnode = *plist; //设置链表的开始
while (pnode != NULL) {
++count;
pnode = pnode->next;//设置下一个节点
}
return count;
}
/*创建存储项的节点，并将其添加至由plist指向的链表末尾*/
bool AddItem(Item item, List* plist) {
Node* pnew;
Node* scan = *plist;
pnew = (Node*)malloc(sizeof(Node));
if (pnew == NULL) return false;//失败时退出函数
CopyToNode(item, pnew);
pnew->next = NULL;
if (scan == NULL)//空链表，把pnew放在链表的开头
*plist = pnew;
else {
while (scan->next != NULL)//找到链表末尾，把pnew添加到链表的末尾
scan = scan->next;
scan->next = pnew;
}
return true;
}
/*访问每个节点并执行pfun指向的函数*/
void Traverse(const List* plist, void(*pfun)(Item item)) {
Node* pnode = *plist; //设置链表的开始
while (pnode != NULL) {
(*pfun)(pnode->item);//把函数应用于链表中的项
pnode = pnode->next; //前进到下一项
}
}
/*释放内存*/
/*设置链表指针为NULL*/
void EmptyTheList(List* plist) {
Node* psave;
while (*plist != NULL) {
psave = (*plist)->next; //保存下一个节点的地址
ferr(*plist); //释放当前节点
*plist = psave; //前进至下一个节点
}
}
/*局部函数定义*/
/*把一个项拷贝到节点中*/
static void CopyToNode(Item item, Node* pnode) {
pnode->item = item;//拷贝结构
}
具有内部链接的函数只能在其声明所在的文件夹可见
在实现接口时，有时编写一个辅助函数(不作为正式接口的一部分)很方便
例如：使用CopyToNode()函数把一个Item类型的值拷贝到Item类型的变量中
由于该函数是实现的一部分，但不是接口的一部分
所以我们使用static存储类别说明符把它隐藏在list.c文件中
InitializeList()函数将链表初始化为空，在我们的实现中
这意味着把List类型变量设置为NULL
这要求把指向List类型变量的指针传递给该函数
ListIsEmpty()函数的前提条件是当链表为空时，链表变量被设置为NULL
因此，在首次调用该函数之前初始化链表非常重要
另外如果要扩展接口添加删除项的功能，那么当最后一个项被删除时，应该确保该删除函数重置链表为空
对链表而言，链表的大小取决于可用内存量
ListIsFull()函数尝试为新项分配空间
如果分配失败，说明链表已满
如果分配成功，则必须释放刚才分配的内存供真正的项使用
ListItemCount()函数使用常用的链表算法遍历链表，同时统计链表中的项
AddItem函数首先为新节点分配空间
如果分配成功
该函数使用CopyToNode()把项拷贝到新节点中
然后把该节点的next成员设置为NULL，这表明该节点是链表中的最后一个节点
最后，完成创建节点并为其成员赋正确的值后，该函数把该节点添加到链表的末尾
如果该项是添加到链表的第1个项，需要把头指针设置为指向第1项
头指针地址是传递给AddItem()函数的第2个参数，所以*plist就是头指针的值
否则，代码继续在链表中前进，直到发现被设置为NULL的next成员
此时，该节点就是当前的最后一个节点，所以，函数重置它的next成员指向新节点
Traverse()与ListItemCount()类似，不过它还把一个指针函数作用于链表中的每一项
有const的函数形参防止函数修改movies
在ListItemCount中：
*plist = (*plist)->next;//如果*plist是const，不允许这样做
因为改变*plist就改变了movies，将导致程序无法跟踪数据
然而，*plist和movies都被看作const并不意味着*plist或movies指向的数据是const
例如，可以编写下面的代码：
(*plist)->item.rating = 3;//即使*plist是const也可以这样做
因为上面的代码没有改变*plist，它改变的是*plist指向的数据
由此可见，不要指望const能捕获到意外修改数据的程序错误
队列ADT
在C语言中使用抽象数据类型方法编程包含以下3个步骤
- 以抽象、通用的方式描述一个类型，包括该类型的操作
- 设计一个函数接口表示这个新类型
- 编写具体代码实现这个接口
队列是具有两个特殊属性的链表
- 新项只能添加到链表的末尾
- 只能从链表的开头移除项
可以把队列想象成排队买票的人，从队尾加入队列，从队首离开
队列是一种先进先出(first in，first out，缩写为FIFO)的数据形式
非正式的抽象定义：
类型名：队列
类型属性：可以存储一系列项
类型操作：初始化队列为空
确定队列为空
确定队列已满
确定队列中的项数
在队列末尾添加项
在队列开头删除或恢复项
清空队列
定义接口
#include <stdbool.h>
typedef int Item;//用于use_q.c
//或者这样定义 typedef struct item {int gumption;int charisma;} Item;
/*直接使用int类型可能会引起混淆
因为int是C语言中的基本数据类型之一
所以使用typedef关键字将一个已有的类型重新命名
这样可以避免与基本数据类型的命名冲突
提高代码的可读性和可维护性。*/
#define MAXQ 10
typedef struct node {
Item item;
struct node* next;
}Node;
//定义节点
typedef struct queue {
Node* front;
Node* rear;
int items;
}Queue;
/*对队列而言，要保存首尾项，可以使用指针来完成
还可以用一个计数器来记录队列中的项数
Queue是一个含3个成员的结构
所以用指向队列的指针作为参数比直接用队列作为参数节约时间和空间*/
/*操作： 初始化队列*/
/*前提条件：pq指向一个队列*/
/*后置条件：队列被初始化为空*/
void InitializeQueue(Queue* pq);
/*考虑初始化，涉及改变Queue类型，所以该函数应该以Queue的地址作为参数*/
/*操作： 检查队列是否已满*/
/*前提条件：pq指向之前被初始化的队列*/
/*后置条件：如果队列已满返回true，否则返回false*/
bool QueueIsFull(const Queue* pq);
/*操作： 检查队列是否为空*/
/*前提条件：pq指向之前被初始化的队列*/
/*后置条件：如果队列为空返回true，否则返回false*/
bool QueueIsEmpty(const Queue* pq);
/*如果stdbool不可用，可以使用int类型或自己定义bool类型
由于该函数不更改队列，所以接受Queue类型的参数
但传递Queue的地址更快，更节省内存，这取决于Queue类型的对象大小
为表明这些函数不更改队列，可以且应该使用const限定符*/
/*操作： 确定队列中的项数*/
/*前提条件：pq指向之前被初始化的队列*/
/*后置条件：返回队列中的项数*/
int QueueItemCount(const Queue* pq);
/*操作： 在队列末尾添加项*/
/*前提条件：pq指向之前被初始化的队列
item是要被添加在队列末尾的项*/
/*后置条件：如果队列不为空，item将被添加到队列末尾
该函数返回true，否则队列不改变，返回false*/
bool EnQueue(Item item, Queue* pq);
/*在队列末尾添加项涉及标识项和队列
更改队列有必要使用指针
该函数返回类型可以是void，或者通过返回值来表示是否成功*/
/*操作： 从队列的开头删除项*/
/*前提条件：pq指向之前被初始化的队列*/
/*后置条件：如果队列不为空，队列首端的item将拷贝到*pitem中
并删除，函数返回true;
如果该操作使队列为空，则重置队列为空
如果队列在操作前为空，该函数返回false*/
bool DeQueue(Item* pitem, Queue* pq);
/*如果把项定义为结构或一种基本类型，可以通过函数返回待删除的项
函数的参数可以是Queue类型或指向Queue的指针
从队列中待删除的项存储在pitem指向的地址*/
/*操作： 清空队列*/
/*前提条件：pq指向之前被初始化的队列*/
/*后置条件：队列被清空*/
void EmptyTheQueue(Queue* pq);
/*清空队列只需要队列的地址*/
实现接口
#include <stdio.h>
#include <stdlib.h>
#include "queue.h"
/*局部函数*/
static void CopyToNode(Item item, Node* pn);
static void CopyToItem(Node* pn, Item* pi);
void InitializeQueue(Queue* pq) {
pq->front = pq->rear = NULL;
pq->items = 0;
}
/*初始化队列为NULL，把指向队列首项和尾项的指针设置为NULL
把项数设置为0
这样可以通过检查items的值很方便的了解队列是否已满，是否为空和确定队列的项数*/
bool QueueIsFull(const Queue* pq) {
return pq->items == MAXQ;
}
bool QueueIsEmpty(const Queue* pq) {
return pq->items == 0;
}
int QueueItemCount(const Queue* pq) {
return pq->items;
}
bool EnQueue(Item item, Queue* pq) {
Node* pnew; //定义了一个指向节点（Node）的指针变量pnew，用于创建新的节点
if (QueueIsFull(pq))
return false;
pnew = (Node*)malloc(sizeof(Node));
if (pnew == NULL) {
fprintf(stderr, "Unable to allocate memory!\n");//如果内存分配失败，输出错误信息并退出程序
exit(1);
}
CopyToNode(item, pnew); //将待加入队列的元素复制到新节点中
pnew->next = NULL; //将新节点的next指针设置为NULL，表示它是队列中的最后一个节点
if (QueueIsEmpty(pq))
pq->front = pnew; //判断队列是否为空，如果为空，则将新节点设为队列的头节点
else
pq->rear->next = pnew;//如果队列不为空，则将新节点添加到队列的尾部
pq->rear = pnew; //更新队列的尾指针，使其指向新节点
pq->items++;
return true;
}
bool DeQueue(Item* pitem, Queue* pq) {
Node* pt; //声明一个指向节点的指针变量pt，用于临时存储被移除的元素
if (QueueIsEmpty(pq))
return false;
CopyToItem(pq->front, pitem);//将队头元素复制到pitem指向的位置
pt = pq->front; //将队列的头指针赋给临时指针变量pt
pq->front = pq->front->next; //更新队列的头节点指针，使其指向下一个节点，即原来的队头元素的下一个节点
free(pt);
pq->items--;
if (pq->items == 0) //如果队列中没有剩余元素，那么将队列的尾指针pq->rear设置为NULL
pq->rear = NULL;
return true;
}
void EmptyTheQueue(Queue* pq) {
Item dummy;
while (!QueueIsEmpty(pq))
DeQueue(&dummy, pq);
}
static void CopyToNode(Item item, Node* pn) {
pn->item = item;
}
static void CopyToItem(Node* pn, Item* pi) {
*pi = pn->item;
}
把项添加到队列的步骤：
1. 创建一个新节点
2. 把项拷贝到节点中
3. 设置节点的next指针为NULL
表明该节点为最后一个节点
4. 设置当前尾节点的next指针指向新节点
把新节点链接到队列中
5. rear指针指向新节点
以便找到最后的节点
6. 项数加1
函数还要处理两种特殊情况
- 如果队列为空，应把front指针设置为指向新节点
因为如果队列只有一个节点，那么这个节点既是首节点也是未节点 - 如果函数不能为节点分配所需内存，这里是使用
exit()函数终止程序
从队列首端删除项的步骤：
1. 把项拷贝到给定的变量中
2. 释放空节点使用的内存空间
3. 重置首指针指向队列中的下一个项
4. 如果删除最后一项，把首指针和尾指针都重置为NULL
5. 项数减1
关于指针注意两点：
- 删除最后一项时，代码中并未显式设置front指针为NULL
因为已经设置front指针指向被删除节点的next指针
如果该节点是最后一个节点
那么它的next指针就为NULL - 代码使用临时指针存储待删除节点的位置
因为指向首指针的正式指针被重置为指向下一个节点
所以如果没有临时指针
程序就不知道该释放哪块内存
保持纯正的ADT
定义ADT接口后，应该只使用接口函数处理数据类型
例如 DeQueue() 依赖 ENQueue() 函数来正确设置指针和把rear节点的next指针设置为NULL
如果在一个使用ADT的程序中，直接操纵队列的某些部分
有可能破坏接口包中函数之间的协作关系
测试队列
/*use_q.c--驱动程序测试Queue接口*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include "queue.h"
int main(void) {
Queue line;
Item temp;
char ch;
InitializeQueue(&line);
puts("Testing the Queue interface.Type a to add a value.");
puts("type d to ...");
while ((ch = getchar()) != 'q') {
if (ch != 'a' && ch != 'd')
continue;
if (ch == 'a') {
printf("Integer to add:");
scanf("%d", &temp);
if (!QueueIsFull(&line))
{
printf("Putting %d into queue\n", temp);
EnQueue(temp, &line);
}
else
puts("Queue is full!");
}
else {
if (QueueIsEmpty(&line))
puts("Nothing to delete!");
else
{
DeQueue(&temp, &line);
printf("Removing %d from queue\n", temp);
}
}
printf("%d items in queue\n", QueueItemCount(&line));
puts("Type a to add,d to delete,q to quit:");
}
EmptyTheQueue(&line);
puts("Bye!");
return 0;
}
在重要程序中使用一个新设计之前，应该先测试该设计
测试的一种方法是编写一个小程序
这样的程序被称为驱动程序(driver) 其唯一用途是进行测试
用队列进行模拟
假设一个提供建议的摊位，顾客可以选择1、2、3分钟的建议
摊位最多等待10位顾客
顾客随机出现，花在咨询的时间也是随机
那么平均每小时接待多少位顾客，每位顾客平均花多长时间，排队等待顾客平均多少人
链表和数组
| 数据形式 | advantage | fault |
|---|---|---|
| array | C直接访问 提供随机访问 | 编译时确定大小 插入和删除元素浪费时间 |
| linked list | 运行时确定大小 快速插入和删除元素 | 不能随机访问 用户必须提供编程支持 |
在数组中插入元素，必须移动其他元素腾出空位插入新元素
新插入的元素离数组开头越近，要被移动的元素越多
而在链表中插入节点只需要给两个指针赋值
在数组中删除一个元素也要移动许多相关元素
从链表中删除节点只需重新设置一个指针并释放被删除节点占用的内存即可
数组可以使用数组下标直接访问该数组中的任意元素
这叫随机访问(random access)
链表只能从链表首节点逐个节点移动至要访问的节点
这叫顺序访问(sequential access)
查找链表中的特定项的一种算法是从列表的开头开始按顺序查找
这叫顺序查找，如果项并未按某种顺序排列则只能顺序查找
我们可以先排序列表，以改进顺序查找
对一个排序列表，用二分查找(binary search)比顺序查找好得多
- 首先把待查找项称为目标项，且假设列表中的各项按字母排序
- 然后比较列表的中间项和目标项
如果两者相等则查找结束
如果中间项在目标项前面，则目标项一定在后半部分项中
如果中间项在目标项后面，则目标项一定在前半部分项中 - 继续使用该方法，把需要查找的剩下一半的中间项与中间项比较
以此类推，直到找到目标项或最后发现列表中无目标项
n次比较能处理有2的n次方-1元素的数组
数组实现二分查找很简单，因为可以使用数组下标确定数组中任意部分的中点
只要把数组首元素和尾元素的索引相加的和除2即可
链表只支持顺序访问，不能使用二分查找
如果频繁插入和删除项且不经常查找，应选择链表
如果偶尔插入和删除项且经常查找，应选择数组
二叉查找树
一种即支持频繁插入和删除项又支持频繁查找的数据形式
二叉查找树是一种结合了二分查找策略的链接结构
二叉树的每个节点都包含一个项和两个指向其他节点(子节点)的指针
二叉树中的每个节点都包含两个子节点——左节点和右节点
顺序按照如下规定确定：
左节点的项在父节点的项前面，右节点的项在父节点的后面
这种关系存在于每个有子节点的节点中
也就是所有可以追溯其祖先回到一个父节点的左节点的项，都在该父节点的前面
所有以一个父节点的右节点为祖先的项，都在该父节点项的后面
树的顶部被称为根
二叉查找树的每个节点都是其后代节点的根，该节点与其后代节点构成了一个子树(subtree)
二叉树ADT
类型名：二叉查找树
类型属性：二叉树要么是空节点的集合(空树)，要么是有一个根节点的节点集合
每个节点都有两个子树，左子树和右子树
每个子树本身也是一个二叉树，也可能是空数
二叉查找树是一个有序的二叉树，每个节点包含一个项
左子树的所有项都在根节点项的前面，右子树的所有项都在根节点项的后面
类型操作：初始化数为空
确定树是否为空
确定数是否已满
确定树中的项数
在树中添加一个项
在树中删除一个项
在树中查找一个项
在树中访问一个项
清空树
二叉查找树接口
可以使用多种方法实现二叉查找树，可以通过操纵数组下标用数组来实现
但实现二叉查找数最直接的方法是通过指针动态分配链式节点
typedef SOMETHING Item;
typedef struct trnode {
Item item;
struct trnode* left;
struct trnode* right;
}Tronode;
typedef struct tree {
Trnode* root;
int size;
}Tree;
每个节点包含一个项、一个指向左子节点的指针和一个指向右子节点的指针
可以把Tree定义为指向Trnode的指针类型
因为只需要根节点的位置就可以访问整个树
使用有成员大小的结构能方便地记录树的大小
/*一个维护Nerfville宠物俱乐部的花名册
每一项都包含宠物名和宠物种类*/
#include <stdbool.h>
#define SIZE 20
#define MAXITEMS 10
typedef struct item {
char petname[SIZE];
char petkind[SIZE];
}Item;
typedef struct trnode {
Item item;
struct trnode* left;
struct trnode* right;
}Trnode;
typedef struct tree {
Trnode* root;
int size;
}Tree;
/*函数原型*/
/*操作： 把树初始化为空*/
/*前置条件：ptree指向一个树*/
/*后置条件：树被初始化为空*/
void InitializeTree(Tree* ptree);
/*操作： 确定树是否为空*/
/*前置条件：ptree指向一个树*/
/*后置条件：如果树为空返回true，否则返回false*/
bool TreeIsEmpty(const Tree* ptree);
/*操作： 确定树是否已满*/
/*前置条件：ptree指向一个树*/
/*后置条件：如果数已满返回true，否则返回false*/
bool TreeIsFull(const Tree* ptree);
/*操作： 确定树的项数*/
/*前置条件：ptree指向一个树*/
/*后置条件：返回树的项数*/
int TreeItemCount(const Tree* ptree);
/*操作： 在树中添加一个项*/
/*前置条件：pi是待添加项的地址
ptree指向一个已初始化的树*/
/*后置条件：如果可以添加，该函数在树中添加一个项后返回true，否则返回false*/
bool AddItem(const Item* pi, Tree* ptree);
/*操作： 在树中查找一个项*/
/*前置条件：pi是待添加项的地址
ptree指向一个已初始化的树*/
/*后置条件：如果在树中找到指定项，该函数返回true，否则返回false*/
bool InTree(const Item* pi,const Tree* ptree);
/*操作： 从树中删除一个项*/
/*前置条件：pi是删除项的地址
ptree指向一个已初始化的树*/
/*后置条件：如果从树中成功删除一个项，该函数返回true，否则返回false*/
bool DeleteItem(const Item* pi, Tree* ptree);
/*操作： 把函数应用于树中的每一项*/
/*前置条件：ptree指向一个树
pfun指向一个函数
该函数接受一个Item类型的参数且无返回值*/
/*后置条件：pfun指向的这个函数为树中的每一项执行一次*/
void Traverse(const Tree* ptree, void(*pfun)(Item item));
/*操作： 删除树中的所有内容*/
/*前置条件：ptree指向一个已初始化的树*/
/*后置条件：树为空*/
void DeleteAll(Tree* ptree);
二叉树实现
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include "tree.h"
/*Local data type*/
typedef struct pair {
Trnode* parent;
Trnode* child;
}Pair;
/*DeleteItem()要知道待删除项的父节点
To update the parent's pointer to the child after the child is deleted*/
/*因此我们设计的SeekItem()函数返回结构包含two pointer
one pointer指向包含项的node
one pointer指向parent node*/
/*Local function prototype*/
static Trnode* MakeNode(const Item* pi);
static bool ToLeft(const Item* i1, const Item* i2);
static bool ToRight(const Item* i1, const Item* i2);
static void AddNode(Trnode* new_node, Trnode* root);
static void InOrder(const Trnode* root, void(*pfun)(Item item));
static Pair SeekItem(const Item* pi, const Tree* ptree);
static void DeleteNode(Trnode** ptr);
static void DeleteAllNodes(Trnode* ptr);
/*function definition*/
void InitializeTree(Tree* ptree) {
ptree->root = NULL;
ptree->size = 0;
}
bool TreeIsEmpty(const Tree* ptree) {
if (ptree->root == NULL)
return true;
else
return false;
}
bool TreeIsFull(const Tree* ptree) {
if (ptree->size == MAXITEMS)
return true;
else
return false;
}
int TreeItemCount(const Tree* ptree) {
return ptree->size;
}
bool AddItem(const Item* pi, Tree* ptree) {
Trnode* new_node;
if (TreeIsFull(ptree)) {
fprintf(stderr, "Tree is full\n");
return false;
}
if (SeekItem(pi, ptree).child != NULL) {
fprintf(stderr, "Attempted to add duplicate item\n");
return false;
}
new_node = MakeNode(pi);
if (new_node == NULL) {
/*如果内存分配失败，malloc函数会返回NULL
因此，如果指针分配内存失败，它会变为空指针*/
fprintf(stderr, "Couldn't create node\n");
return false;
}
ptree->size++;
if (ptree->root == NULL) /*树为空*/
ptree->root = new_node;
else
AddNode(new_node, ptree->root); /*树不为空*/
return true;
}
bool InTree(const Item* pi, const Tree* ptree) {
return (SeekItem(pi, ptree).child == NULL) ? false : true;
}
bool DeleteItem(const Item* pi, Tree* ptree) {
Pair look;
look = SeekItem(pi, ptree);
if (look.child == NULL)
return false;
if (look.parent == NULL)
DeleteNode(&ptree->root);
else if (look.parent->left == look.child)
DeleteNode(&look.parent->left);
else
DeleteNode(&look.parent->right);
ptree->size--;
return true;
}
void Traverse(const Tree* ptree, void(*pfun)(Item item)) {
if (ptree != NULL)
InOrder(ptree->root, pfun);
}
void DeleteAll(Tree* ptree) {
if (ptree != NULL)
DeleteAllNodes(ptree->root);
ptree->root = NULL;
ptree->size = 0;
}
/*Local function definition*/
static void InOrder(const Trnode* root, void(*pfun)(Item item)) {
if (root != NULL) {
InOrder(root->left, pfun);
(*pfun)(root->item);
InOrder(root->right, pfun);
}
}
static void DeleteAllNodes(Trnode* root) {
Trnode* pright;
if (root != NULL) {
pright = root->right;
DeleteAllNodes(root->left);
free(root);
DeleteAllNodes(pright);
}
}
static void AddNode(Trnode* new_node, Trnode* root) {
if (ToLeft(&new_node->item, &root->item)) {
if (root->left == NULL)
root->left = new_node;
else
AddNode(new_node, root->left);
}
/*通过比较确定新项的位置，这个过程持续到函数发现一个空子树为止
root是指向当前当前子树的指针
所以每次递归调用它都指向一个新的下一级子树*/
else if (ToRight(&new_node->item, &root->item)) {
if (root->right == NULL)
root->right = new_node;
else
AddNode(new_node, root->right);
}
else {
fprintf(stderr, "location error in AddNode()\n");
exit(1);
}
}
static bool ToLeft(const Item* i1, const Item* i2) {
int comp1;
if ((comp1 = strcmp(i1->petname, i2->petname)) < 0)
return true;
else if (comp1 == 0 && strcmp(i1->petkind, i2->petkind) < 0)
return true;
else
return false;
}
/*左节点的项在父节点的项前面，右节点的项在父节点的后面
数字用比较运算符，字符串用strcmp()，多个字符串则需自定义
strcmp()函数返回的是字符串的差值
即第一个字符小于第二个字符时，返回相应的负数
第一个字符串大于第二个字符时，返回相应的正数
字符串的返回值便是累加*/
static bool ToRight(const Item* i1, const Item* i2) {
int comp1;
if ((comp1 = strcmp(i1->petname, i2->petname)) > 0)
return true;
else if (comp1 == 0 && strcmp(i1->petkind, i2->petkind) > 0)
return true;
else
return false;
}
static Trnode* MakeNode(const Item* pi) {
Trnode* new_node;
/*处理动态内存分配和初始化节点
参数是指向新项的指针，返回值是指向新节点的指针*/
new_node = (Trnode*)malloc(sizeof(Trnode));
if (new_node != NULL) {
new_node->item = *pi;
new_node->left = NULL;
new_node->right = NULL;
}
return new_node;
}
static Pair SeekItem(const Item* pi, const Tree* ptree) {
Pair look;
look.parent = NULL;
look.child = ptree->root;
if (look.child == NULL)
return look;
while (look.child != NULL) {
if (ToLeft(pi, &(look.child->item))) {
look.parent = look.child;
look.child = look.child->right;
}
else if (ToRight(pi, &(look.child->item))) {
look.parent = look.child;
look.child = look.child->right;
}
else
break;/*相等的重复项*/
}
return look;
}
static void DeleteNode(Trnode** ptr) {
//ptr是指向目标节点的父节点指针成员地址
/*父节点的指针成员是指向目标节点的指针
所以需要使用二级指针来修改指针的指向*/
Trnode* temp;
if ((*ptr)->left == NULL) {
temp = *ptr;
*ptr = (*ptr)->right;
free(temp);
}
else if ((*ptr)->right == NULL) {
temp = *ptr;
*ptr = (*ptr)->left;
free(temp);
}
/*无子节点的节点可看作无左子节点的节点的特例
用临时指针存储被删除节点的地址以此来使用free函数*/
else {
for (temp = (*ptr)->left; temp->right != NULL; temp = temp->right)
continue; /*从左子树右半部分向下查找一个空位*/
temp->right = (*ptr)->right;
temp = *ptr;
*ptr = (*ptr)->left;
free(temp);
/*ptr类型是Trnode**，所以*ptr类型是Trnode*，与temp类型相同*/
}
}
/*待删除的node没有child node
只需把parent node中的pointer重置为NULL
并用free()函数释放已删除的节点内存*/
/*删除带有一个子节点的node
需要把被删除节点父节点中存储该节点的地址更新为该节点子树的地址*/
/*删除有两个子树的节点
其中一个子树可以连接在被删除节点之前连接的位置
牢记树的基本设计：
左子树的所有项都在父节点项的前面，右子树的所有项都在父节点项的后面
也就是右子树的所有项都在左子树所有项的后面*/
使用二叉树
/*使用二叉查找树*/
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include "tree.h"
char menu(void);
void addpet(Tree* pt);
void droppet(Tree* pt);
void showpets(const Tree* pt);
void findpet(const Tree* pt);
void printitem(Item item);
void uppercase(char* str);
char* s_gets(char* st, int n);
int main(void) {
Tree pets;
char choice;
InitializeTree(&pets);
while ((choice = menu()) != 'q') {
switch (choice) {
case 'a': addpet(&pets);
break;
case 'l': showpets(&pets);
break;
case 'f': findpet(&pets);
break;
case 'n': printf("%d pets in club\n",
TreeItemCount(&pets));
break;
case 'd': droppet(&pets);
break;
default: puts("Switching error");
}
}
DeleteAll(&pets);
puts("Bye.");
return 0;
}
char menu(void) {
int ch;
puts("Nerfville pet Club Membership Program");
puts("Enter the letter corresponding to your choice:");
puts("a==add a pet l==show list of pets");
puts("n==number of pets f==find pets");
puts("d==delete a pet q=quit");
while ((ch = getchar()) != EOF) {
while (getchar() != '\n')
continue;
ch = tolower(ch);
if (strchr("alrfndq", ch) == NULL)
puts("Please enter an a,l,f,n,d or q:");
else
break;
}
if (ch == EOF)
ch = 'q';
return ch;
}
void addpet(Tree* pt) {
Item temp;
if (TreeIsFull(pt))
puts("No room in the club!");
else {
puts("Please enter name of pet:");
s_gets(temp.petname, SIZE);
puts("Please enter pet kind:");
s_gets(temp.petkind, SIZE);
uppercase(temp.petname);
uppercase(temp.petkind);
AddItem(&temp, pt);
}
}
void showpets(const Tree* pt) {
if (TreeIsEmpty(pt))
puts("No entries!");
else
Traverse(pt, printitem);
}
void printitem(Item item) {
printf("Pet: %-19s kind: %-19s \n", item.petname, item.petkind);
}
void findpet(const Tree* pt) {
Item temp;
if (TreeIsEmpty(pt)) {
puts("No entries!");
return;
}
puts("Please enter name of pet you wish to find:");
s_gets(temp.petname, SIZE);
puts("Please enter pet kind:");
s_gets(temp.petkind, SIZE);
uppercase(temp.petname);
uppercase(temp.petkind);
printf("%s the %s", temp.petname, temp.petkind);
if (InTree(&temp, pt))
printf("is a member.\n");
else
printf("is not a member.\n");
}
void droppet(Tree* pt) {
Item temp;
if (TreeIsEmpty(pt)) {
puts("No entries!");
return;
}
puts("Please enter name of pet you wish to delete:");
s_gets(temp.petname, SIZE);
puts("Please enter pet kind:");
s_gets(temp.petkind, SIZE);
uppercase(temp.petname);
uppercase(temp.petkind);
printf("%s the %s", temp.petname, temp.petkind);
if (DeleteItem(&temp, pt))
printf("is dropped from the club.\n");
else
printf("is not a member.\n");
}
void uppercase(char* str) {
while (*str) {
*str = toupper(*str);
str++;
}
}
char* s_gets(char* st, int n) {
char* ret_val;
char* find;
ret_val = fgets(st, n, stdin);
if (ret_val) {
find = strchr(st, '\n');//使用strchr函数查找字符串st中的换行符
/*函数原型：
char *strchr(const char *str, int c);
str：指向要搜索的字符串的指针
c：要查找的字符
如果找到指定字符，则返回指向该字符的指针。
如果未找到指定字符，则返回NULL*/
if (find)
*find = '\0';//如果地址不是NULL，在此处放置一个空字符
else
while (getchar() != '\n')//处理输入行的剩余内容
continue;
}
return ret_val;
}
二叉查找树只在满员(或平衡)时效率最高
如果用户按字母顺序输入数据，那么都会被添加到右节点，是不平衡的树，这种树不比查找链表快
避免串行树的方法之一是创建树时多注意
如果树或子树的一边太不平衡，就需要重新排列节点使之恢复平衡