导图社区 C语言和数据结构
- 26
- 0
- 0
- 举报
C语言和数据结构
对c语言和数据结构相关的基础知识进行了整理，以及语法进行了补充说明和实例解释便于理解，既可以当作查找语法的工具书，也可以用来学习和理解这两部分
编辑于2023-08-16 21:39:05 陕西- 材料书
- 相似推荐
- 大纲
C语言和数据结构
C语言零碎整理
常见转义字符
图片
system("cls")和system("pause")【清屏函数和暂停函数】
运算符顺序
指针
指针相关概念
指针变量：c语言规定只能使用一种特殊的【变量】存放地址（内存中字节的编号），这种类型称为指针类型。
指针：对于内存单元而言，内存单元的地址就是指针。
注：由于通过地址就能找到所需的变量，因此，C语言将地址形象地称为指针。
个人对指针变量的叙述：指针变量是一种特殊的变量，里面【只能】存放【同类型变量】的【地址】或者存放0，通过地址对变量的值进行【间接访问】，【访问内存地址是为了更方便的操作内存单元中的地址】
使用方式：将变量的首地址和其他数据结构的首地址赋予【指针变量】
指针变量的定义和初始化
指针变量的定义：应包括【数据类型名】和【指针变量名】
格式：数据类型名 *指针变量名1，*指针变量名2 或者单独定义一个然后多次定义来完成。
注意：存放指针变量中的数据，必须是【同类型变量】的【地址】，这也是定义时，需要有数据类型名的原因【它可以指明指针和变量数据类型是否相同】，如果我们定义的变量其类型和指针类型相同，则该变量存放数据的首地址才可以赋值给指针。
指针变量的初始化：先定义再初始化或者定义的同时进行初始化，其他情况是错误的。
格式：数据类型名 *指针变量名=初始值；
注意：初始值是地址，所以，如果将变量地址赋予指针变量时，需要使用取址运算符。
总结：在定义和初始化时，书上陈述了许多需要注意的问题，但这些问题，都围绕定义和概念展开，只要牢记【你自己总结的叙述】，这些问题都可以通过概念解决。
指针变量的引用
方式：在C语言中，对指针变量的引用，可通过【*取值运算符】和【&取址运算符】来完成，前者可以取出地址中的变量，后者则是可以取出变量所在的地址。
注：需要注意的是优先级，运算顺序，以及明白定义时*取址运算的特殊【定义时不作为取值的作用】
重点：在二维以及多维数组应用中，会有一些特殊性，具体可在【指针和多维数组的表示】中了解。
总结：在一个指针变量正确定义和初始化后，如果该指针变量为p，则“p”此时使用时，是一个存放地址的变量（比如打印p的值，显示为地址），而通过取值【*】运算符可以获得【该地址指向变量】的值
注意：指针变量定义完成后，如果操作不涉及指向变量的数据而仅仅对指针变量中的地址时，请不要加*号，反之不同。（具体请联系【指针的运算】节理解
举例：
指针的运算【特殊性】
方式：指针变量的运算一般分为加法和减法，指针可以加上或减去整数，但指针这种运算和通常意义的运算是不同的。
总结：由于内存单元和指针的关系，这种运算不仅仅是地址的加减，而是【数字】和【相应数据类型字节大小】“乘积的加减”，与此同时，由于变量的地址实质是内存单元的起始地址，所以，通过指针运算，产生的地址加减结果是由相应数据类型字节大小决定的，而不是直接地址的值加上或减去整数。
举例：【可以看出，指针中变量的值改变了16，该值为减去的4和基本整型字节数4的积】
指针和数组
须知
指针和数组的联系：数组名既不是指针常量也不是常量指针，在某些时候，它可以退化成指向数组第一个元素的指针，也就是说，数组名可以隐式的被转化为指针类型。
举例：将数组名传递给一个接受指针类型参数的函数时，数组名会对应转化为对应的指针类型。
优势：由于数组下标在编译时需要转化为指针，所以，直接使用指针能减少系统编译的时间。
注意：数组在使用的时候需要考虑是否越界的因素，而使用指针时也需要考虑。
数组元素的引用
下标法：通过数组下标表示，具体请在数组节找寻。
指针法：通过对指针的运算，来表示数组的所有元素，需要注意指针运算的特殊，在指针运算中有过总结。
补充：可以看出，对于基本整型而言，每个变量占用4字节，使用指针运算指向数组变量时，可以直接加减整数而不必加上字节数。
重点：下标法和指针法在后面的学习中，有很大联系，特别是在指针和多维数组的联系中，有着很大的作用。指针法的表示在【指针和多维数组的表示】有着详细举例
指针和多维数组的表示
多维数组的属性：在所有的数组中，我们使用下标表示数组，不同维数的数组，我们会表示相应的下标，当下标小于维数时，它表示此维数的地址而不是此维数的值。在多维数组指针运算时，数组名加减时，表示加值的首地址，且使用取值运算符需要使用两次。
举例：
指针和一维数组
格式：指针变量名=数组名
总结：一维数组和指针关系是很密切的，通过数组名赋予给定义的指针变量，以此通过指针运算来表示数组元素。
指针和二维数组
总结：二维数组有两种表示方式，第一种以前半部分下标作为地址，通过地址运算，来表示这个数组里的其他元素，只有补全后面的下标，才可以表示特定的数组元素。第二种是以数组名和取值运算符来表示，再第一次使用*时，表示的依旧是地址，不使用时依旧是地址，只有同时二次使用*时，才能表示这个地址所指向的变量。
注：在上述解释中，使用数组名加上指针方式表示数组元素，以及使用指针变量表示时，是完全不同的，错误的使用会导致程序错误。【后面有专门的指针变量来表示数组】
指向二维数组的指针变量
原因：对于二维数组来讲，不能和一维数组一样，直接将数组名赋予给定义的指针变量，因此，专门指向二维数组的指针变量由此诞生。
定义形式：数据类型名 (*指针变量名)[元素个数]
形式解释：[元素个数]表示目标变量是一维数组，并指明了一维数组元素的个数，括号是由于必须严格规定运算优先级，否则导致定义的非指向二维数组的指针变量。
特性：此变量赋值后，相当于二维数组中，通过数组名和取值运算符，表示数组元素。【其后的元素个数表示数组列数】。相当于把带前半部分下标的数组也就是数组每维数组首元素地址赋予这个变量。【最后一句话的详细解释在指针和二维数组节有】
[元素个数]的解释：个数表示的是，相当于数组的列数
指针数组
须知：数组元素都为指针类型的元素，也就是说，指针数组中每个元素都将存放一个指针变量。
声明格式
一般声明格式：<存储类型><数据类型>*<数组名>[<数组长度>]；
完整声明格式：<存储类型><数据类型>*<数组名>[<数组长度>]={初值列表}；
注意：定义和赋值应该是可以分开的，这里不进行详细展开。
重点：指针数组中的元素既是数组元素，又是指针。因此，当引用他们时，既要注意他们的数组元素特征，也要注意它们指针特征。【既可以使用下标引用数组元素，也可以使用数组名引用相应位置的地址，若数组元素本身就是指针，注意使用取值运算符访问该指针指向的变量】
字符指针数组与二维数组的比较
区别：后者存储时，占用连续的内存空间。前者则是分散的内存空间。
二维字符数组的特点：二维数组表示字符串时，需要占用一片来连续的储存空间，但中间很多存储空间可能是空白的。因此，在定义时，需要指定列数为最长字符串加一。
指针与字符串
指向字符串的指针
优势：当把地址赋给指针时，指针的指向随之发生改变。因此，当我们使用字符型指针变量时，处理字符串会更便捷。
引用方式：定义一个字符指针，用它指向字符串的起始地址，就可以进行字符串的引用了，此时，不用使用取址运算符。
定义格式
char *指针变量名；
char *指针变量名=字符串常量；
须知：可以先定义后初始化，也可以同时进行。
输出方式：通过%s和字符指针变量名输出该字符串。如果想要输出字符串中特定的字符，可以使用指针运算，将该字符指针指向的地址变为，输出特定字符的地址。
字符指针和字符数组的区别
第一：字符指针变量名可以多次赋值，而字符数组名是地址常量，不能赋值，其次，数组的大小是固定的，需要预先分配空间。
第二：类型和占用存储单元不同，前者是字符串首地址，后者是已分配的空间
第三：数组中的元素可重新赋值，但我们不能通过字符指针来间接修改字符常量的值，否则后果无法预料。
总结：字符指针是变量，可多次直接赋值，指向的是字符串首地址。字符数组大小固定，数组中的元素多次赋值，直接赋值时，必须在初始化时赋值。也可以使用输入函数进行赋值，不可以使用赋值语句。
指针和函数
将指针变量作为函数参数
目的：用指针做函数的参数，保证传递给形参是地址。由于被调函数对参数作的修改不会传递给主函数，所以，有时为保存这种修改，将使用指针变量作为函数参数。
特点是：共享内存，双向传递
对该方式的解释：这种方式的实行，是需要保证传递给形参是指针，其次，使用形参，参与函数。需要知道，在函数里实行语句时，并不是给形参的地址参与函数，而是形参，由于指针的特殊性，此时形参的变换，实则是内存地址中，变量的变换。为了保证准确性，我进行了验证并在下面给出了例图
例图：
指向函数的指针（函数指针）
原因：函数名和数组名有相似的特性，函数名代表了函数的起始地址，编译器通过函数名来索引函数的入口地址。
函数指针的定义
定义：为了操作类型属性相同的函数，c语言引入了函数指针（function pointer），将函数首地址赋予指针变量，则该变量就指向函数，我们可以通过指针变量找到并调用对应的函数。
定义形式：数据类型名 （*函数指针名)( );
解释：数据类型定义了函数的返回值类型，（*函数指针名）确定了指向了函数的指针变量，（）表明指向对象是函数。
函数指针的初始化和使用
函数指针没有独立的函数代码，必须初始化。初始化有两种形式，一是直接赋值函数名，二是通过取址运算符赋值函数名。当然也可以在定义的同时初始化，然后采取两种初始化方式。
初始化方式
函数指针名=函数名 或者 函数指针名=&函数名
数据类型名 （*函数指针名)( )=函数名
使用函数指针变量调用函数的一般形式
(*函数指针名)(实参表)；
返回指针值的函数
函数类型是由返回值决定的，这种返回值是指针的函数称为指针型函数
定义形式：数据类型 *函数名(参数表)；
注：返回值必须是外部或静态存储类别的变量指针和数组指针。
指向指针的指针
定义：如果一个指针变量中存放的是另一个指针变量的地址，就称这个指针变量为指向指针的指针变量。
定义形式：数据类型名 **p
解释：*号数量决定是几级指针变量，同类型的同级的指针变量才可以相互赋值。与此同时，高阶指针必须由相邻的低价指针赋予。
理解：对于给定的一个变量，将它一级一级的赋予不同级别的指针变量，他们都指向最初的那个变量，使用方式和一阶指针变量相似。
例图：
指针和动态内存分配
因为动态内存管理函数的原型定义在标准头文件<stdlib.h>,所以使用时需要加上。
malloc函数
作用：malloc是从内存的动态存储区分配长度为size的连续空间，malloc函数的参数是一个无符整型，返回值是一个指针，用以指向分配的动态存储区的起始地址。需要注意的是，当未能成功分配空间时，malloc函数会分配一个空指针，所以，当我们使用它时，我们必须检测返回值是否为空指针并执行相应操作。比如，下图里，需要执行的操作可以是，显示分配错误。
原型：void *malloc（unsigned int size）
解释：void * 作为返回值的类型，unsigned int 处写无符整型 ，size处用以计算大小，比如size(int)，结果为4.
例图：
calloc函数
重点：和malloc函数的区别，在于，calloc函数会将分配的内存空间先初始化为零，其他的基本相同。
原型：void *calloc（num，size）
解释：用法和malloc函数相同，当num和size一个或者多个为零，则会出现分配错误，所以，你知道的。
用法以及例图：
free函数
原因：由于内存不能无限的分配下去，因此我们必须节约资源，所以，在使用动态内存管理函数后，必须释放分配的空间，以便其他变量的使用。
原型：void free（void *ptr）
注意事项
如果free没有指向先前分配的空间，则会产生未定义行为
free是释放分配的空间，但不会改变ptr原本的值，也就是说ptr依旧指向原来的地址，但该地址已经无效
如果ptr是空指针，则该函数不会进行任何操作
free过后，ptr还必须置空，ptr=NULL，不然，在后续再次使用变量ptr访问时，会有错误。
free不能重复释放，不然会有错误
用法以及例图
free：在保证正确的前提下，只会对malloc和calloc分配返回的非空指针释放一次，释放后必须置空，且不会改变原本指针的指向。
上面三种函数，仅作参考，所以，不足之处可网上搜寻。
malloc函数和free函数共同作用的例图
指向结构体变量的指针
解释：结构体变量在声明后，会在内存中分配存储空间，而这片空间的起始地址就是结构体变量的地址（指针）。因此，我们可以通过赋值给指针，来通过指针来访问，此时注意指针变量的定义，“只能存放【同类型】”，所以，面对我们自定义的结构体，是不可以直接赋予的。我们需要先通过这种结构体定义同类型的指针，然后再把结构体变量的地址赋于指针。
一般形式：struct 结构体名 *指针变量名 或者 （typedef后的名字）*指针变量名
解释：本质是指针的定义，所以跟使用基本类型定义是一致的，所以，typedef后的名字也具有相同作用
注：赋值时，请找准结构体变量的地址，赋值过程属于指针变量的初始化，所以，不必麻烦。
重点：可以通过指针的运算，通过指向结构体数组首地址，然后间接访问数组中的变量。如数组a——a[1]=*(a+1)，a[1][1]=*(*(a+1)+1)。【如果使用指针变量，其方式和数组名方式一致，只需要单纯的替换】
发现：可以在结构体里直接使用结构体名定义指向结构体变量。【存疑】
形式：结构体名 *指针变量名；【此时不带struct】
指针，数组，函数，结构体综合图
指针常量【指针类型的变种，用来限制修改所指向的地址】
定义：本质是一个常量，而用指针修饰它。指针常量的值是指针，这个值因为是常量，所以不能被赋值。
代码形式：int* const p;
效果：它是一个常量，该指针只能指向规定好的地址，而且不能改变，但是地址中的值可以改变【类似数组名，但不同】
常量指针【指针类型的变种，用来限制修改所指向的值】
定义：又叫常指针，可以理解为常量的指针，也即这个是指针，但指向的是个常量，这个常量是指针的值（地址），而不是地址指向的值。
代码形式：int const* p; const int* p；
效果：可以接受包括变量在内的地址，可以任意指向某个地址，但是不能通过指针修改变量值的方式去改变，可以通过变量原本的方式去改变。
常用输入输出函数
关于输入输出函数的概念
所谓输入输出，是以计算机主机为主的，通过输入设备和输出设备完成的。
C语言中本身没有输入输出函数语句，但它提供了丰富的输入输出函数库函数，标准输入输出标准库函数，是在头文件stdio.h定义的，（英文缩写，不进行深入）。在使用这些库函数时，需要使用宏命令#include，将头文件包含到源文件里。
#include使用方式
#include <stdio.h>
解释：在include目录下找指定文件。
#include "stdio.h"
解释：先在源文件所在目录下找，再按标准方式搜索。
字符输入输出
字符输入函数
限制：只能作用于【单个字符】的输入
三者使用方式：把输入的字符赋值给字符型变量或者整型变量，既可以充当赋值语句，也可以作为一部分参与到运算里。
理解：字符输入函数在stdio.h中定义的，都没有参数。
getchar（可用来清除缓冲区，即充当暂停键）
限制：只接收第一个字符，如果输入数字，也会按照字符处理。必须按回车才能成功输入，会显示在屏幕上。
格式：getchar（）；或者 变量名=getchar（）；
getche
解释：基本和getchar类似，区别在于，不用回车，也会回显在屏幕上
getch
解释：基本类似，和getche区别在于，不会回显在屏幕上。
例图
字符输出函数
putchar
使用格式：putchar（形参）；
解释：向屏幕输出单个字符，其中，形参的可以是字符常量，字符型变量以及表达式。如果形参是控制字符，则执行控制功能，因为控制字符不可见，因此只能目测光标位置变化和声音。
字符串处理函数【定义在<string.h>头文件中】
字符串输出函数puts
格式：puts（字符数组名/字符串）
功能：向计算机屏幕输出字符串，并在输出完毕后换行。
说明：字符数组必须以‘\0'结尾。
字符串输入函数gets
格式：gets（字符数组）
功能：从键盘输入一个以回车为结尾的字符串，并放入字符数组中，然后在结尾自动添加'\0'，得到一个函数值，这个函数值就是字符数组的起始地址。
说明：输入的字符串应小于字符数组的长度。
字符串连接函数strcat
格式：strcat(字符数组1，字符数组2)
功能：把字符数组2中的字符串连接到字符数组1中，去除字符数组1中字符串结尾的'\0'，保留字符串2结尾的'\0'。
说明：字符数组1必须足够大，这个函数的返回值是字符数组1的首地址。
字符串复制函数strcpy
格式：strcpy(字符数组1，字符数组2)
功能：把字符数组2的字符串赋值给字符数组1中，包括结尾的'\0'。字符数组2也可以是字符串常量，此时相当于把字符串赋值给字符数组。
说明：字符数组1必须足够大，不能使用赋值语句对字符数组进行赋值。
字符串比较函数strcmp
格式：strcmp（字符数组1，字符数组2）
功能：对两个字符串从左到右进行比较【比较的是字符ASCLL】，直到遇见不同或者'\0'为止。
前者等于后者，返回值为0
前者大于后者，返回值为正整数
前者小于后者，返回值为负整数
说明：比较字符串时，只能使用strcmp。它可用于字符串常量之间，甚至字符数组和字符串常量之间。
字符串长度测量函数strlen
格式：strlen（字符数组）
功能：测量字符串的实际长度【不含'\0'】，并作为返回值。
其他字符串处理函数
格式：strupr（字符数组），功能：将所有字符转化为大写
格式：strlwr（字符数组），功能：将所有字符转化为小写
格式：strset（字符数组，字符），功能：将所有字符转化为特定字符
格式控制输入输出函数
格式控制输出函数
定义：printf函数称为格式控制输出函数
定义位置：<stdio.h>
基本格式：printf("格式控制字符串",参数1，参数2，……);
延伸：格式控制字符串中，包括两部分，一部分是普通字符序列或转义字符序列。另一部分是格式声明字符串。前者是原样打印，后者是根据功能生效。
参数：可以是常量和变量，表达式或者函数调用
两者必须是一一对应的，如果错误，会输出错误的值或者无法输出【因为编译器只检查调用形式，不分析格式控制字符串】。与此同时，输出数据时，一切数据类型均按照格式字符控制串优先。
printf函数格式的声明
完整格式：%[标志][输出最小宽度].[精度][长度]类型
%：是起始符号，必不可少
标志：可填选项+，-，0，#，空格【主要对输出有辅助作用】
输出最小宽度：这里指域宽，也就是显示的字符的个数，小于它时，默认右对齐，左补空格。大于它时，按照原样输出。
精度：显示的有效小数，超出则是四舍五入。
长度：为ll或h，l对于整型是long，对于实型是double，h用于将整型修改为short型
类型：指定输出数据的类型。【建议牢记常见的】
printf的求值顺序：不同编译系统顺序不同，VC中是从右向左【很重要，要明确】
格式控制输入函数
定义：scanf函数称为格式控制输出函数
定义位置：<stdio.h>
基本格式：scanf("格式控制字符串",地址1，地址2，……)；
延伸：格式控制字符串里包括一个或多个以%开头格式控制字符，%后面跟一个或多个格式控制字符，用来占位，以便于对应后面的地址，在相应的位置使用格式控制字符确定数据的输入格式
scanf函数的声明
完整格式声明：%[*][输入宽度][长度]类型
%：格式声明的起始字符，不可缺少。
[*]：读入但不赋值，在赋值时跳过它
输入宽度：输入的·有效字符个数
长度：为l或h，整型时，前者为长整型，后者为短整型。实型时，为double型。
类型：类似printf
有关scanf函数的说明
格式很重要，请务必按照完整格式使用，否则会产生错误
格式控制字符和地址两者必须对应，否则程序将会面目全非。如果格式控制字符之间有字符，则地址之间也必须添加字符。
数据类型（一个值集合和定义在这个集合上所有操作的总称）
原因：在数学里，数据是不进行分类的。但在计算机中，由于存储空间受限于物理硬件，所以，存储空间不可能存放无限大或者无限位数的小数。因此，对数据分类很有必要。
基本类型
整型
整型数据相关知识
定义：通过int定义的变量
表示方法：在c语言中，可以通过十进制，八进制，十六进制表示。
存储方式：在计算机中，以二进制的方式存放，正数以原码，负数以补码形式存放。
分类方式
范围
短整型（short）
占用字节：2字节
【有符】表示范围：-2的15次方~2的15次方-1
【无符】表示范围：0~2的16次方
基本整型（int）
占用字节：4字节
【有符】表示范围：-2的31次方~2的31次方-1
【无符】表示范围：0~2的32次方
长整型（long）
占用字节：4字节
【有符】表示范围：-2的31次方~2的31次方-1
【无符】表示范围：0~2的32次方
双长整型（long long）
占用字节：8字节
【有符】表示范围：-2的63次方~2的63次方-1
【无符】表示范围：0~2的64次方
符号
有符整型（signed int）：存储单元的最高位是符号位，0为正，1为负，其他为数值位。
无符整型（unsigned int ）：全部二进制位都用来存放数值而没有符号位。
两者区别：一是正负的区别，其次是，定义的两种变量，所能表示的数的范围不同，会在基本整型中的范围详细解释。
实型
实型数据（浮点数据）的相关知识
表示方式（实型常量）：在计算机中，实型常量是可以用小数和指数形式表示
存储方式：在计算机中，实型数据是以指数形式存放的，将实型数据分为小数部分和指数部分存放的。C语言并没有规定多少位是小数，多少位是指数，这由编译系统决定，一般来说，大多数编译系统，是以24位小数和8位指数。前者表示精度，后者表示范围。
指数形式的使用要求
一，格式为 aEn ，例如，123，表示则为，1.23E2
二，字母E或e，前面必须有数字，e后必须是整数
三，规范化（不强制），即，e前小数点左边有且只有一个非0的数，后面必须为整数
实型数据的精度
原因：受限于物理硬件，计算机内存并不是无限的，所以，不能保存无限位小数，因此，计算机中的实型数据都是近似值。【也正是如此，实型数据比较大小，一般是是否接近，而不是认为是否相等】
注意事项
使用实型数据时，需要根据需求，选择单精度实型或者双精度实型。
不要使用实型数据表示【较大的整数】，因为，实型数据在计算机中的【存放形式】导致了，如果超出该实型的范围，该数据会丢失部分位数，以至于数值发生改变。
尽量避免用大数减去一个过小的数，可能会导致小数丢失。
计算机对实型常量的处理：计算机会将实型常量作为双精度实型数据处理，缺点是降低运算。在实型常量的后面添加字母f或者F，计算机会将它当作单精度实型数据处理。添加l或者L，会当作长双精度实型数据处理。
分类
精度
单精度实型变量（float）
占用字节：4字节
有效位数：6
范围：-3.4e的38次方~3.4e的38次方
双精度实型变量（double）
占用字节：8字节
有效位数：15
范围：-1.7e的308次方~1.7e的308次方
长双精度实型变量（long double）
占用字节：8字节或者16字节
有效位数：15或者19
范围：-1.7e的308次方~1.7e的308次方或者-3.4e的4932次方~3.4e的4932次方【编译器的不同所导致】
字符型数据
字符型变量
字符型变量是使用关键字char定义的，定义的同时赋初值。
格式：char 变量名；
字符型常量
解释：有两种形式的字符型常量，一种是普通字符型常量，另外一种转义字符型常量
普通字符型常量：使用【' '单引号】括起来的【单个】【字符】，在内存中存放对应的编码（ASCII），它既可以当作字符处理，也可以当作数字处理。
转义字符型常量：以【反斜杠\】开头的字符序列。【建议了解常用的转义字符】
字符型数据的运算
当把字符放到字符变量时，字符型变量存放的是对应的ASCII编码，它既可以当字符处理，又可以当数据处理（此时参与运算的是ASCII），所以，它可以作为整型变量来处理。与此同时，可以通过输出语句，输出两种形式的数据。
字符串常量
定义：以【双引号】括起来，以及由【\0结尾】（C语言规定）的【字符序列】
不能把字符串常量赋值给字符型变量
没有字符型变量，不过可以使用字符型数组和字符指针
结尾的\0也需要占用一字节空间，单是两个双引号，也叫字符串常量，也叫空串，大小一个字节。
注：字符型数据在内存中只占用一字节。
抽象数据类型
可以通过固有的数据类型来表示和实现，它有些类似c语言中的结构
算法（仅有定义）和程序控制结构
算法
产生原因：计算机始终是解决实际问题的工具，不可避免遇见具体问题，算法为解决这些问题而产生的步骤和方法。
定义：是一组定义完好且排列有序的指令集合。
问题规模：不在于输入数据的大小，而是问题大小的本质表现。
算法的特征
有穷性：算法在它包含的每种情况下，必须能够在人忍受范围之内，通过有限步骤完成这个算法。
可行性：可以通过已经确定的基本运算和有限步骤完成算法。
确定性：每个语句都必须拥有确定性，不能有二义，保证了程序在相同输入条件下，产生相同的结果。
I/O性：算法必须有零个或多个输入，以及一个或多个输出。
有效性：算法的每一步必须能够有效执行
除此之外，算法好坏的判定，也需要考虑，正确性，可读性，健壮性，时间复杂度和空间复杂度（高效性）。
算法的表示
自然语言：人们日常使用的语言，但人对于它的理解容易出现不同，降低程序的确定性
流程图：条例较为清晰，但过多的流程线容易造成混乱，修改不方便，画起来费时费力
N-S图：真正的结构化方式，但依旧有着修改复杂，画起来复杂的因素
伪代码：优点很多，修改方便，使用计算机语言和自然语言，理解方便。
使用的一般步骤：自顶向下，解决问题不能要求一下子处理到细节，要能够把大问题划分成小问题。
算法的执行时间
解释：算法的执行时间等于所有语句执行时间之和，而所有语句执行时间等于执行一次的时间和执行的次数
语句频度：一个语句重复的次数。
（渐进）时间复杂度
定义：算法执行时间的数量级称为时间复杂度，T（n）=Q（f（x））
排序（时间复杂度）：常量阶<对数阶<线性阶<线性对数阶<平方阶<立方阶<k次方阶<指数阶
说明：它随着问题规模增大而增大。
（渐进）空间复杂度
包括：【程序执行时，指令，常数，变量和输入数据】和【对数据操作需要的辅助空间】
说明：如果程序执行时，需要的辅助空间相对于输入数据是个常数，就称这个算法在原地工作。
注意：定义在上面两句话里
时间和空间复杂度的说明：算法分析的两个方面主要在于时间复杂度和空间复杂度，【一般情况下，运算空间充足时，分析时间复杂度作为判断算法优劣主要目标】，此外，过度追求其中一个，另一个可能会使性能变差。
C语句的分类
表达式语句：表达式加上分号，执行该语句就是计算表达式的值
函数调用语句：函数名加上参数表，再加上分号
控制语句：C语言有九种控制语句，共分为三类，条件判断语句，循环执行语句，跳转语句，后续有详细解释。
复合语句：多个语句通过花括号括起来形成的语句，在语法上视为一条语句，花括号中每个语句都要加上分号，但花括号后不能再添加。
空语句：什么操作也不执行，仅有分号组成的语句。
顺序结构
顺序结构程序：顺序程序中，程序的运行按照自上而下运行，执行完当前语句后，不需要任何判断，就执行下一个语句。【通常由表达式和函数调用语句构成】因为控制语句的执行，并不是完全按照顺序执行，每种执行方式不同。
选择结构
if语句【在顺序使用的时候，可用于流程中每步的判断】
单分支if语句
一般形式：if（表达式）语句；
解释：如果表达式为真，则执行其后的语句，反之不执行。
if……else双分支if语句
一般形式：if（表达式）语句；else 语句；
解释：表达式为真，则执行其后的语句，反之，执行else后的语句。
if嵌套语句
字面意思，if单分支和双分支嵌套，不进行详细说明
注意：在有多个if和else时，如果要找寻相应组合，可从else找寻，即距离else最近的if就是对应组合。
if多分支语句
一般形式：if（表达式）语句；else if（表达式）语句；……else 语句；
解释：哪个表达式为真，则执行其后的语句并跳出这个多分支语句。如果都为假，则执行最后的语句并结束这个多分支。
switch语句（也可用来调用函数）
一般形式：switch（表达式）{case 常量表达式：语句；break；……default ：语句；break；}
注意
一，switch中表达式必须是整型和字符型。
二，switch执行顺序：通过计算括号里的表达式的值与常量表达式进行值判断，进而执行case后的语句，如果有break，则跳出switch语句，如果没有，则向下执行，如果没有break则执行之后所有的语句。
三，case后可以有多个语句，不必使用花括号。
四。最好有停止运行的跳转语句。
条件运算符和条件表达式
注：优先级不同，if最高，switch其次。
循环结构
while语句
一般形式：while（表达式）语句；
解释：如果表达式一直为真，则执行一直相应语句，如果表达式始终无法为真，则无限循环。所以，该循环的表达式必须能够为假，或者相应语句后有break语句。
注意：表达式的位置一般是关系表达式和逻辑表达式，但也可以是其他类型的表达式。比如，自加，关系，1和0.
do-while语句（搭配if语句，可特定条件退出）
一般形式：do{语句；}while（表达式）；
解释：和whlie很相似，但形式上有部分区别，执行方式也不同，while循环是先判断后执行，而这种语句是先执行一次再进行判断。也正是这种执行方式导致它的适用性不如while语句。
for语句
注：上面三种循环可以相互嵌套，其中，三种循环语句范围不同，for最大，while其次，do-while最后
说明：上面只是提供部分整理和整体思路，循环语句其灵活性繁多，建议在使用过程中逐步掌握。
跳转语句
break语句：常用于循环体和switch中，不能用于if语句的中断
continue语句：只能用于循环体中，且常和if语句连用
goto语句
一般形式：goto 语句标识；
解释：执行符号标识后的语句，一般和if语句连用
return语句
注意：如果已经返回，会直接跳出循环。
说明：跳转语句的使用，把选择结构和循环结构变得更灵活。选择结构和循环结构由选择语句和循环语句组成，再加之跳转语句，三者称为控制语句。
结构体及其延伸
结构体的定义
定义形式
struct 结构体名 {数据类型 变量名；……}；
typedef使用方式【帮助结构体变量的定义和使用】
定义结构体时：typedef struct 结构体名 {数据类型 变量名；……} 新的数据类型名；
说明：上面在使用过程中，结构体名省略，不影响结果，只是在结构体变量定义时，不能够使用结构体名，因为，你省略了。
定义后使用：typedef 数据类型或数据类型名【如int和struct 结构体名】 新数据类型名
说明【结构体定义的注意事项】
一，结构体成员可以是任何基本数据类型，除此以外，还可以是数组和指针类型。
二，结构体的大小和数量必须是一定的，不能够定义动态的结构体【C语言中不支持】
三，结构体可以多个嵌套定义，但不可以递归定义【在结构体里使用结构体名定义结构体成员】
四，结构体成员名字不能相通
五，结构体里可以使用结构体名定义指针变量，该指针变量可以指向结构体变量。
结构体变量
定义：我们自己定义了结构体类型，当我们将它用来定义变量时，我们称它为结构体变量，类似基本数据类型的定义方式。
特点：通过定义我们可以知道，定义的结构体是不占用存储空间的，但是我们用它定义结构体变量时，这时系统才会分配存储空间。
定义形式
一，先定义结构体【可以选择在此使用typedef】，再通过struct加变量名定义结构体变量。因为是分开定义，所以可以使用ty后的新名字定义。这两种方式归属于【先后类】
二，定义结构体的同时，定义结构体变量【直接在花括号后面写变量名，多个变量时使用逗号分开】，此时，可以省略结构体变量名，但是由限制，请参考结构体定义相关概念。这两种方式属于【同时类】
初始化【未初始化，结构体变量自动为0】
一般形式：诸多形式，也就是定义的结构体——【结构体类型】结构体变量名={初值表}；
具体：先定义结构体，在定义【结构体变量】的同时初始化【结构体变量】。或者，定义结构体的同时并进行结构体变量定义和初始化。前者的定义和初始化过程，如果没有使用typedef建立别名，则不能省略结构体类型而直接选择变量名进行定义
解释：所谓诸多形式，是对定义和初始化过程大致分为两类，【先后】和【同时】，都有各自的特点，【先后】可配合typedef，【同时】可选择省略结构体名。
注意：初始化和变量的定义是紧密联系的，通过【赋值运算初始化】时，定义和初始化不可分割，【而基本类型都可以，这也是区别之处】除此之外，【初值表里的顺序必须和结构体里成员的顺序一致，不可有错】
引用形式
成员运算符：结构体变量名.成员名
指针加取值运算符：（*指针变量名).成员名
指针加成员选择指针：指针变量名->成员名
说明：不可以整体引用，只能通过上面三种方式进行部分变量的引用来参与使用。具备普通变量的作用，且引用时，只能先整体再部分。
指向结构体变量的指针【该部分经过考虑，选择放在指针节】
结构体数组
特点：既具备数组的特点，也具备结构体变量的特点
定义：定义方式和结构体变量的定义一致，先后或同时
一般形式：struct 结构体名 结构体数组名【大小】
struct 结构体变量名 { } 结构体数组名【大小】
初始化：依旧和结构体变量的定义要求类似，和结构体的数组定义紧密结合，不能分开【就是不能先定义再通过赋值运算进行初始化，可以通过scanf】。形式可参考结构体变量的初始化以及多维数组赋值方式。
引用：通过数组下标和成员运算符，来对数组中具体的变量进行引用，对于数组中的每个部分可以整体赋值，如，a[0]=a[1]。也可以对成员进行部分赋值，但他们类型必须是相同的，如，a[0].name=a[1].name。
验证上面问题的例图
解释定义和初始化的几张例图
结构体中所有初始化，除定义时外，还可以通过格式控制输入函数scanf进行初始化
定义和初始化通过赋值运算初始化时，两者不可分割，通过scanf则可以，例图在上
共用体
定义形式：union <共用体名>{<成员列表>}
特点：以成员列表最大的变量给每个成员变量开辟相同的空间，初始化后，成员列表里存放一个值的不同形式。
补充：其他方式完全和结构体一样
变量存储相关概念
变量的作用域
定义：变量的有效范围称为变量的作用域，在函数的调用时，形参只用在函数的调用时才会被分配空间，所以，变量并不是一直存在，不同变量作用后结果也不同。
重点：变量范围的规定，自然产生了可以同名的问题，同名的变量在【不同的定义范围】是没有联系的。
局部变量
定义：在函数内或者复合语句中定义的变量称为局部变量
有效范围：局部变量仅在定义他们的函数内或复合语句中有效，两者并无优先级，若函数内有一复合语句，根据定义的范围，只在其一生效。
全局变量（外部变量）
定义：全局变量是定义在所有函数之外的变量，可由同一程序中的所有函数共享，当它改变时，仅有函数里复合语句中同名的全局变量不受改变。
有效范围：从定义的位置开始到程序结束处。
注意：全局变量的使用会降低程序的可读性，所以，尽量不要定义全局。
变量的存储类别及生命周期
原因：根据变量的生命周期，可分为静态存储变量和动态存储变量。静态存储变量是在程序运行时，固定分配存储空间的变量。动态存储变量是在运行时根据需要分配存储空间的变量，明确定义，更好理解。
静态存储变量
范围：全局变量，静态的局部变量
生命周期：在程序执行时，开始分配空间，在整个程序的运行完毕后才会释放。
动态存储变量
范围：自动变量，形参变量，中断的现场数据
生命周期：在函数调用时到结束时，贯函数的整个执行过程。
自动变量解释：指的是未使用static声明的局部变量
形参变量解释：指的是函数形式的参数
中断的现场数据解释：函数调用的现场保护和返回值
变量的存储类别
解释：变量在定义时，我们通常使用数据类型定义，但变量还有存储类别。在c语言中，变量有两个属性，数据类型和数据存储类型。
变量的完整定义形式：存储类别 数据类型标识符 变量名；
自动变量（auto）
定义：在定义局部变量时，如果使用了auto或者未指定存储类别，系统就会默认它为自动变量，会为它分配空间，放置动态存储区。
作用范围：从定义位置开始，到定义函数范围或者复合语句结束。
寄存器变量（register）
原因：由于一些变量的使用频率较高，为了运行效率，系统会把变量的值保存CPU里的寄存器里。
定义：一种特殊的自动变量。
限制
只能是char，int，指针类别的变量
只有函数中定义的变量和参数才可以定义为寄存器变量
目前的编译系统已经能够自动识别这些变量，从而放入寄存器变量中。
静态变量（static）
定义：使用关键字static定义的变量
静态局部变量
定义：使用关键字static在函数内或者复合语句中定义的变量
作用域：作用范围不变，生命周期变为整个程序的执行过程中。
静态全局变量
定义：使用static声明的变量，但是，在声明后，这个全局变量只能在这个源文件里使用，失去了作为外部变量的一部分作用。
外部变量（extern）
定义：在所有函数之外定义的变量
作用范围：从定义位置开始到整体程序结束，从定义位置之前如果想要使用外部变量，可以在引用位置，使用extern声明外部变量，这样就扩大的作用范围
注意：在其他源文件里，声明这个外部变量里，可以在其他源文件里使用。
文件操作
文件概述
文件：既是以文件名标识的一组相关数据的有序集合，也是操作系统管理数据的一种单位
文件的分类【文件一般存储在外部介质上，直到使用时才会调用内存，角度不同，对文件的分类也不同】
【1】从用户的角度看，文件可分为设备文件和普通文件
【2】从逻辑结构上看，文件可分为记录文件和流式文件
【3】从编码方式看，文件可分为文本文件和二进制文件
文件指针
说明：在C语言中，对文件的访问是通过文件指针来实现的
文件类型的指针：C语言中的FILE类型是用来存放有关文件信息的结构体类型，其定义在<stdio.h>
文件结构体指针：C语言中，将所有的外部设备都作为文件对待，称为设备文件。
文件的打开和关闭
说明：C语言程序在执行文件操作时，必须遵循“打开”—>“读写”—>“关闭”这样的操作流程。不打开文件就不能对文件进行读写操作，不关闭就会耗尽系统资源。
文件的打开【操作失败返回NULL】
函数：fopen
形式：文件指针名=fopen（文件名，文件打开模式）
【文件指针名】必须是声明为FILE类型的指针变量
【文件名】可以是字符串常量或字符数组。
【打开文件模式】是指文件类型和操作要求，具体如下
举例
文件的关闭
说明：文件使用完后，就应该使用fclose函数将其关闭，以免文件丢失或者文件再次被误用。
形式：fclose（文件指针）
【1】【文件的关闭操作将会使文件指针不再指向文件对应FILE结构，从而断开与文件的关联】
【2】【在向文件写数据时，会把数据先放到缓冲区，等到缓冲区满后，才会将缓冲区内容发送给磁盘，未满则不行，而文件关闭会强制发送缓冲区内容】
【3】【文件操作正操返回0，否则返回EOF】
文件的读写
【说明】：C语言提供了很多文件读写的函数，它们的区别在于读写单位不同，它们都定义在头文件stdio.h中
字符读写函数：fgetc和fputc
字符串读写函数：fgets和fputs
数据块读写函数：freed和fwrite
格式化输入输出函数：fscanf和fprinf
字输入输出函数：getw和putw
文件的定位【不包括具体的操作函数】
文件的检错
数据结构
定义：相互之间存在一种或多种特定关系的数据元素的集合，也可以认为是带结构的数据元素的集合。
数据结构的两个层次
逻辑结构：从实际问题抽象出的数据模型
划分1
线性结构：栈，队列，线性表，数组
非线性结构：树，图，集合
划分2
集合：数据元素除了处于同一集合，没有其他关系。
线性结构： 数据元素之间存在一对一的关系。
树形结构——结构中的数据元素之间存在一对多的层次关系
图形结构——结构中的数据元素之间存在多对多的关系
存储结构（物理结构）：数据元素及其关系在存储器中的存储方式
顺序存储：【要求所有元素依次存放在连续的存储空间】，借助元素在存储器中的位置来表示元素之间的逻辑关系。通常借助数组表示。
链式存储：【不要求数据元素存放在连续的存储空间，但每一个数据元素中的数据项是存放在连续的空间里】，需要给每个结点附加指针字段。用以存放后继元素的地址。
抽象数据类型
定义：是指由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总和。
包括：数据对象，数据关系上的关系的集合，对数据对象的基本操作的集合。
线性表
顺序表
定义：由n个数据特性相同的数据元素构成的有限序列称为线性表。当n等于0时，称为空表。
特点
存在唯一一个被称为“第一个”和“最后一个”的数据元素。
除第一个以外，每个元素只有一个直接前驱。
除最后一个以外，每个元素只有一个直接后驱。
线性表的顺序存储表示【顺序表】
定义：用一组【地址连续的存储单元】依次存储线性表的数据元素，也称线性表的顺序存储结构或者顺序映像
特点：逻辑上相邻的数据元素，物理次序也相邻
说明：由于顺序表是连续的，所以只要确认存储线性表的首地址，就可以对任一数据元素进行存取。，所以线性表的顺序存储结构是一种【随机存取】得存储结构。
补充：由于高级程序设计语言也有随机存取的特性，因此，通常用数组描述数据结构中的顺序存储结构。在此，由于线性表的长度可能随问题的不同而不同，所以，在C语言中可用动态分配的一维数组表示线性表。
顺序表中的基本操作的实现【下面的操作注意设置判断是否合法条件，不合法需返回错误】
初始化：顺序表的初始化就是构造一个空的顺序表，通过判断length是否为0，来判断线性表是否为空表
取值：是通过给定的位置序号i，来获取线性表第i个元素的值。也就是数组下标i-1个元素。
插入：将表中第i个位置插入新的元素，使长度为n的线性表变为长度为n+1的线性表。【还需要判断线性表是否已满】
删除：将表中第i个元素删去，将线性表的长度减一。
缺陷：
链式表
数据及其相关概念
1.1数据结构的研究内容
非数值，特点，操作
是使计算机能够更高效地进行非数值处理，
1.2基本概念和术语
1.数据（data）
定义：所有能输入到计算机中去的【描述客观事物】的【符号】
分类
数值性的数据
非数值性的数据
2.数据元素（element）：数据中的基本单位，也称节点（node）
3.数据项（data item）：数据中组成数据元素的，有独立含义，不可分割，的最小单位
范围：数据>数据对象>数据元素>数据项（范围包含）
数据对象（data object）：具备相同性质的数据元素，是数据的子集。
图
定义：包括点的有穷非空集合和边的有穷集合组成，若边集是有向边，则该图称为有向图，若边集是无向边，则该图称为无向图。
基本术语
子图：在给定的图中，选择部分存在的点和边，遵循给定图中的连接方式，组成的图。
无向完全图和有向完全图
1#对于无向图，若具有n(n-1)/2个边，则该图称为无向完全图
2#对于有向图，若具有n(n-1)个弧，则该图称为有向完全图。
稀疏图和稠密图：有很少边或弧的图称为稀疏图，反之称为稠密图【主观较强，判断标准由人决定】
权和网
权：图在实际应用中，在边上标注数值，这些数值表示从一点到另一点的代价或花费，称为权。
网：带权的图称为网
邻接点：两点通过一个公共边相邻接，也可以说该边与这两点相关联。
度，入度，出度
度：连接该点的边的数量，有向图中，度等于出度和入度之和
出度：有向图中，从该点出去的边
入读：有向图中，从该点进入的边。
路径和路径长度
路径：从起始点到末尾点，所有的顶点序列，若图是有向图，则路径也是有向的。
路径长度：一条路径上，经过的所有边或弧的数目。
回路或环：第一个顶点和最后一个顶点相同的路径称为回路或环。
简单路径，简单回路(简单环)
简单路径：序列中顶点不重复的路径称为简单路径
简单回路或简单环：除第一个和最后一个顶点以外，其他顶点不重复的回路称为简单回路或简单环。
连通相关概念
连通：在【无向图】中，若顶点v到顶点v1之间存在【路径】，则称之为连通【顶点自身也可认为连通】。
连通图：若任意两个顶点都连通，则称该图为连通图
连通分量：无向图中的极大连通子图。
强连通图：在【有向图】中，若任意两个顶点【此两个点不可相等】存在路径，则称该图为强连通图
强连通分量：有向图中，极大连通子图
连通图的生成树：首先它是连通子图，再然后，它含有图中的全部顶点，但是边只有n-1条
有向树：有一个顶点的入度为0，其余顶点的入度均为1的有向图
生成森林：若干颗有向树组成。
图的存储结构
邻接矩阵：是表示顶点之间相邻关系的矩阵
规则：若相邻顶点v(i)和v(j)存在路径，该路径在图的边的有穷集合中，i和j决定的位置处，使用1表示，反之则使用0
优点
可以清楚知道相邻顶点是否存在边
便于计算各个顶点的度，无向图里，第i行元素之和就是度。无向图里，第i行元素之和就是出度，j列元素之和就是入度。
缺点
不便于增加和删除顶点
不便于统计边的数目，需要扫描所有的元素，时间复杂度为Q(n^2)
空间复杂度高【对于稀疏图尤为浪费时间】
若表示的为网，则每个连通的位置上，使用权值表示，反之，使用无穷符号表示。
邻接表：是图的一种链式存储结构
规则
优点
便于增加和删除顶点
便于统计顶点边的数目，时间复杂度为Q(n+e)
空间效率高【适合稀疏图】
缺点
不便于判断顶点是否有边
不便于计算有向图的各个边
图的遍历
深度优先搜索【规则】
从图的某个节点开始，访问该节点
从刚访问的节点开始，找寻未被访问的邻接点，然后访问它，重复此步骤，直到访问的节点没有邻接点
如果此时该点没有未被访问的邻接点，则返回上一个被访问的节点，如果该节点有未被访问的节点，则访问它，然后继续返回。反之。直接返回，直到所有节点被访问
广度优先搜索【规则】
从图的某个顶点开始
访问该点的邻接点，若有多个邻接点，则横向访问
然后，以先被访问节点大于后被访问节点的优先级为原则，访问后面的节点，直到图的所有节点访问完毕
图的应用
最小生成树
普里姆算法【加点法】
对于存在的连通网，我们先规定一个边的集合【构建完最小生成树后，它就是边的集合】，再规定只有【第一个顶点】的集合。
取出连通图中所有顶点，并按照相应的位置摆放
从第一个顶点开始，在给出的连通图里，找出相邻的权值最小的边【并且该边到达的点必须未被加入点集中】按照原来的方式连接它【该边加入边集里】，然后从该边到达的顶点【该点加入点集中】开始，重复此步骤。
若选择边的时候，存在多个权值相同的边，此时选择任意一个边即可
克鲁斯卡尔算法【加边法】
对于存在的连通网，将其中的权值按从小到大的顺序排序
取出连通图中所有顶点，并按照相应的位置摆放
取出权值最小的边，在自己的图上，按照原来的位置连接，若新加入的边会产生回路，则舍弃该边，选择下一条权值较小的边
最短路径【在带权有向图中，习惯上将第一个顶点称为源点，最后一个顶点称为终点。
从某一源点到其他源点的最短路径【迪杰斯特拉算法】
对于存在的网，将顶点分为两组
一组是只包含源点的集合，命名为S
一组是不包含源点的所有点
算法是按照源点到其他顶点的最短路径长度递增的次序,若该点到源点的最短路径长度排第三，则该点是第三个加入到集合S中的点。
AOV-网【使用顶点表示活动，弧表示活动优先级关系的有向图】
一个无环有向图称为有向无环图，有向无环图是描述一项工程或系统进行过程的有效工具
【引言】在AOV-网中，不应出现有向环，检测方法是对给定网进行拓扑排序，若所有的顶点都在拓扑排序的有向序列中，则该AOV-网中必定不存在环。
从顶点v(i)到v(j)，若存在的是有向路径，则称v(i)是v(j)的前驱，若存在的是网中的一条弧，则称直接前驱。
拓扑排序【将AOV-网中所有顶点排成一个线性序列，该序列满足：若在AOV-网中，顶点v(i)到顶点v(j)之间存在路径，则v(i)必定在v(j)之前】
在有向图中，选择一个无直接前驱的点输出它
并删除在有向图中，该点和以该点为尾的弧
重复上面步骤，直到不存在无前驱的顶点
若此时输出的点数目小于有向图中的顶点数，则说明有向图中存在环，反之，即为一个拓扑排序有向序列。
AOE-网【带权有向无环图，使用边表示活动，顶点表示事件，权表示活动持续的时间，每个事件表示在它之前活动已经完成，在它之后的活动可以开始了】
通常用来表示工程，整个工程只有一个完成点和一个结束点，故在正常情况下，网中只有一个入度为0的点，称为源点。也只有一个出度为零的点，称为汇点。
带权路径长度：在AOE-网中，一条路径上各弧上权值之和
关键路径：从源点到汇点，带权路径长度最长的路径
关键活动：关键路径上的边。
关键路径求解过程
拓扑排序求出活动最早发生的时间
逆拓扑排序求出活动最晚发生的时间
若这两个时间相同，则它为关键活动
由关键活动形成的由源点到汇点的每一条路径就是关键路径，关键路径有可能不止一条
树和二叉树
树【是有n个结点的有限集，n大于等于0】
说明：当n等于0时，它被称为空树，否则为非空树
非空树的定义
有且只有一个被称为根的结点
除根结点以外的结点，可分为m个互不相交的有限集，每个集合本身就是一颗树，并且称为树的子树。
理解：树的结构定义是一个递归的定义，即在树的定义用到树的定义。树还可以有其他表示形式，【嵌套集合形式】，【广义表的形式】，【凹入表示法】
树的基本术语
结点：树的一个独立单元，包含一个数据元素以及【若干指向其子树分支】（？——如链式存储中，指向左右孩子的指针，以及存储数据的变量）
结点的度：结点拥有的子树的数目称为结点的度【结点拥有的孩子数】
树的度：各结点度的最大值，即所有结点度进行比较，取最大值
叶子【或终端结点】：度为0的结点
非终端结点：度不为0的结点称为非终端结点或分支结点。除根结点以外，分支结点也称为内部结点
双亲和孩子：一个结点，它的子树的根，称为该结点的孩子，相应的，该结点称为孩子的双亲
祖先：从根到该结点所经分支上的所有结点
子孙：以某结点为根的子树中的任意结点称为子孙。
层次：从树的定义开始，根为第一层，根的孩子为第二层。树中任意结点的的层次等于其双亲结点的层次加一
堂兄弟：双亲在同一层次的结点，称为堂兄弟
树的深度：树中结点的最大层次称为树的深度或高度
有序树和无序树：如果将结点各子树看成从左到右是有次序的，则称有序树，反之无序树【大概就是，如果规定位置不能变，那么这树中各结点位置不能变】。有序树中，最左边子树的根称为第一个孩子，最右边的孩子称为最后一个孩子。
森林：是m颗互不相交的树的集合，m大于等于0。对于树中每个结点而言，其子树的集合称为森林。
重点：树的所有结点的度之和，等于总结点数减1【除根结点以外，每个结点都会参与度数目的计算】
树的存储结构
双亲表示法
说明：以一组连续存储单元存储树的特点，便于找到结点的双亲，但是求结点的孩子需要遍历整个结构
每个结点包含，数据域和parent域，后者存储双亲结点的下标，如图
孩子表示法
二叉树【由n个结点组成集合，n大于等于0】
和树的区别：二叉树每个结点最多有两个子树，其子树有左右之分，其次序不能倒换
定义【树的术语基本都适用于二叉树】
有且只有一个根结点
除根节点以外，其他结点分为两个互不相交的子集，分别称为左子树和右子树，它们也是二叉树。
二叉树的性质
性质1：在二叉树的第【i】层最多有2^i-1个结点（i大于等于1）【相当于以1为首项，2为公比的等比数列】
性质2：深度为k的二叉树，最多有(2^k)-1个结点（k大于等于1）【相当于以1为首项，2为公比的等比数列，这是前n项和】
性质3：对于任何一个二叉树，其终端结点的数目等于度为2的结点之和加1
满二叉树：深度为k，且结点数目为2^k减1的二叉树【相当于除根结点，最高层次的2^i-1个终端结点以外，其他结点的度都为2】
完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n个结点一一对应。【与满二叉树的区别，在于结点数目不同】
性质1：具有n个结点的完全二叉树，其深度为以2为底的n的对数，再加一
性质2：
二叉树的存储结构
顺序存储结构【仅适用于完全二叉树，一般二叉树也可以，但是很浪费存储单元】
解释：顺序存储结构使用一段连续的存储单元存储元素，为了反应结点之间的逻辑关系，必须将结点按照一定的规律存储
存储方式：对于完全二叉树，从根节点按照层序，依次从上到下，从左到右存储。而一般二叉树的存储方式是，对照完全二叉树，相应位置没有结点的位置，存储时使用0表示。
链式存储结构
每个结点包含数据域和指向左右孩子的指针域1child和rchild，这种链表称为二叉链表
有时为了便于找到孩子结点的双亲，可以增添一个指向双亲的指针域【parent】，这种链表称为三叉链表
链表的头指针指向根结点
二叉树的遍历
先序遍历二叉树
先访问根结点
再先序遍历左子树
最后先序遍历右子树
中序遍历二叉树
中序遍历左子树
访问根结点
中序遍历右子树
后序遍历二叉树
后序遍历左子树
后序遍历右子树
访问根节点
线性表
定义：由n(n>0)个具有【相同数据特性】的【元素】的【有限】序列称为线性表。
说明：线性表中元素个数n【n>0】定义为线性表的长度，n等于0时，为空表
特点【总结：头尾的唯一性，以及头无前驱，尾无后驱。】
存在唯一一个称为【第一个】的数据元素
存在唯一一个称为【最后一个】的数据元素
除第一个元素以外，结构中的每一个数据元素均只有一个前驱
除最后一个元素以外，结构中的每个数据元素均只有一个后驱
线性表的类型定义
线性表的顺序表示和实现（【顺序存储结构】【顺序映像】）
定义：指的是用一组连续的存储单元依次存储线性表的数据元素
特点：逻辑上相邻的元素，结构上也相邻，即逻辑和物理结构对应，它是一种随机存储结构
操作【在初始化的同时，其连续的存储空间已经开辟，每个位置我们可以通过直接表示数组表示（如，L.elem[i]=e），因其结构体中的指针变量指向空间首地址，相当于数组名。】
初始化：动态开辟一组连续存储空间，判断是否开辟成功，然后将线性表的长度置为0，返回相应的判断值
插入：先判断插入位置的合理性，移动相应位置的元素，再在相应位置插入数据元素，然后表长加1，返回对应的判断值。
取值：判断取值合理性，直接取相应位置的值即可。
删除：先判断删除位置的合理性，然后直接删除对应位置的值，并返回删除值，移动两边的值，再把线性表的长度减一，返回对应的判断值。
清空和销毁：前者是将线性表的长度置为0，后者是将开辟的空间释放
理解图
线性表的链式表示和实现（【非顺序映像】【链式映像】）【逻辑上相邻的，物理位置上不要求相等】
链式存储结构的定义：一组任意存储单元存储线性表的数据元素，这组存储单元既可以是连续的，也可以是不连续的
特点：由于存储结构的原因，对元素处理必须从头指针开始，所以，也称为顺序存储的存取结构。
原因：正是因为这种存储结构，为了表示相邻数据元素的逻辑关系，我们通过直接前驱中存放直接后继的存储地址，来表示两者的关系，所以，在C语言中，通过定义数据域和指针域来共同组成这个元素，称它为结点。指针域存储的信息称为指针或链，n个结点组成了线性表。【由于结点中只有一个指针域，这种方式组成线性表称为线性链表或单链表。】
说明，区分，注意
说明
链表结点的定义
#！ElemType是通用类型标识符，根据需要可通过define进行替换
#！为了程序的可读性，定义了LNode和*LinkList两个结构体变量，通常使用前者定义结点，后者定义链表的头指针。
#！但单链表是由表头指针唯一确定的，因此单链表可以使用头指针来命名，若头指针是L，则链表也为L
区分
结点变量：每个结点的名字
指针变量：指向结点的指针
头结点：为了方便处理，在单链表的首元节点前附加一个结点，称为头结点，数据域可选择性存放，指针域指向首元结点。
头指针：指向链表中第一个结点的指针，根据是否有头节点，产生不同的指向对象
首元节点：是指链表中存储第一个数据元素的结点。
注意：说明里第二步，关于两种结构体的不同名却等价，很重要
创建单链表
前插法：将新结点插入到头结点之后，每次申请新结点之后，将其插入到头结点之后，注意元素值的存储。
算法步骤
#！先创建一个只有头结点的链表
#！根据链表包含的个数n，循环n次
#生成一个新节点*p
#输入元素值并存放在数据域中
#将新结点插入到头结点之后
示意图
后插法：先有一个尾指针指向链表尾节点，然后每次申请新结点并插入到尾结点之后，然后移动尾指针指向新结点的位置
算法描述
#！先创建只有头结点的链表，然后初始化尾指针指向头结点
根据链表个数n，进行n次循环
#申请一个新结点*p
#将输入的元素值赋予存储结构
#将新结点插入到尾指针后
#移动尾指针指向新的尾指针
操作
初始化
【1】生成一个新结点，作为一个头结点，并使头指针指向头结点
【2】头结点的数据域置于空
【示意图】