一、排序 1.桶排序 int main() { int a[11],i,j,t; //初始化数组 for(i=0;i<=10;i++) { a[i]=0; } //读入五个数用于排序 for(i=1;i<=5;i++) { scanf("%d",&t); a[t]++;//a[t]记录分数t的出现次数 } for(i=0;i<=10;i++)//依次判断a[0]-a[10] { for(j=1;j<=a[i];j++)//分数i出现的次数a[i] { printf("%d",i);//打印分数i } } return 0; } 时间复杂度O（M+N） 2.冒泡排序 核心在于双层嵌套循环 分数排序： int i,j,t,n; int a[100]; printf("输入需要排序的个数："); scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&a[i]); } for(i=1; i<=n-1; i++)//n个数需要排n-1趟 { for(j=1; j<=n-i; j++)//每一趟需要比较n-i次大小 { if(a[j]<a[j+1])//交换位置，从小到大 { t=a[j]; a[j]=a[j+1]; a[j+1]=t; } } } for(i=1;i<=n;i++)//打印排好序的数字 { printf("%d\n",a[i]); } return 0; 根据分数打印人名： struct student{ char name[21]; char score; };//创建一个结构体存放姓名和分数 int main(){ int i,j,n; struct student a[100],t;//创建一个数组用来存放姓名和分数 printf("输入一个n："); scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%s %d",&a[i].name,&a[i].score);//分别存入姓名和分数 } //排序 for(i=1;i<=n-1;i++) { for(j=1;j<=n-i;j++) { if(a[j].score<a[j+1].score)//数组中的分数进行比较 { t=a[j];//交换保存着姓名和分数的数组 a[j]=a[j+1]; a[j+1]=t; } } } for(i=1;i<=n;i++) { printf("%s %d\n",a[i].name,a[i].score);//打印排好序的姓名和分数 } return 0; } 时间复杂度为O（n^2） 3.快速排序 二、栈 队列 链表 1.队列 允许在队列的首部进行删除操作（head++），在队列的尾部进行插入操作（tail++）；haed用来记录队列的队首（即第一位），tail用来记录队列的队尾的下一个位置。规定：队首和队尾重合时，队列为空。 问题：现有一串数字，删除第一个数字，第二个数字移到队尾；删除第三个数字，将第四个数字移到队尾...... 队列是广度优先搜索以及队列优先的Bellman-Ford最短路算法的核心数据结构。 一般代码实现： int main() { int q[102]={0,6,3,1,7,5,8,9,2,4},head,tail;//初始化队列 int i; head=1; tail=10; while(head<tail) { printf("%d",q[head]);//打印队首 head++;//加1，指向新的队首 q[tail]=q[head];//将新的队首移到队尾 tail++; head++; //再将队首出队，进入下次循环 } return 0; } 结构体实现： struct queue { int data[100]; int head; int tail; }; //结构体包含整型数组data、整形head和整形tail，访问其内容，可用`.成员` int main() { struct queue q; q.head=1; q.tail=1; int i; for(i=1;i<=9;i++) { scanf("%d",&q.data[q.tail]);//初始化队列 q.tail++; } while(q.head<q.tail) { printf("%d",q.data[q.head]); q.head++; q.data[q.tail]=q.data[q.head]; q.tail++; q.head++; } return 0; } 2.栈 栈：后进后出，只能在一端进行插入和删除操作。 回文：正读反读均相同的字符序列，如aha，ahha

一、 1.n的阶乘 int i=0; int n; int sum=1; printf("输入n的值："); scanf("%d",&n); //获取n的值 for(i=1;i<=n;i++) { sum=i*sum;//实现阶乘 } printf("%d\n",sum); return 0; 2.n的阶乘之和 //法一：嵌套循环 int i=0; int j=0; int sum_1=1; int sum_2=0; int n=10; for(i=1;i<=3;i++) { sum_1=1; for(j=1;j<=i;j++) { sum_1=j*sum_1;//阶乘 } sum_2=sum_1+sum_2;//阶乘之和 } printf("%d",sum_2); return 0; //法二： int i=0; int sum=1; int sum_1=0; for(i=1;i<=3;i++) { sum*=i; sum_1+=sum; } printf("%d",sum_1); return 0; 3.冒泡排序 核心在于双层嵌套循环 排分数： int i,j,t,n; int a[100]; printf("输入需要排序的个数："); scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&a[i]); } for(i=1; i<=n-1; i++)//n个数需要排n-1趟 { for(j=1; j<=n-i; j++)//每一趟需要比较n-i次大小 { if(a[j]<a[j+1])//交换位置，从小到大 { t=a[j]; a[j]=a[j+1]; a[j+1]=t; } } } for(i=1;i<=n;i++)//打印排好序的数字 { printf("%d\n",a[i]); } return 0; 根据分数打印人名： struct student{ char name[21]; char score; };//创建一个结构体存放姓名和分数 int main(){ int i,j,n; struct student a[100],t;//创建一个数组用来存放姓名和分数 printf("输入一个n："); scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%s %d",&a[i].name,&a[i].score);//分别存入姓名和分数 } //排序 for(i=1;i<=n-1;i++) { for(j=1;j<=n-i;j++) { if(a[j].score<a[j+1].score)//数组中的分数进行比较 { t=a[j];//交换保存着姓名和分数的数组 a[j]=a[j+1]; a[j+1]=t; } } } for(i=1;i<=n;i++) { printf("%s %d\n",a[i].name,a[i].score);//打印排好序的姓名和分数 } return 0; } 时间复杂度为O（n^2） 4. 快速排序

一、输入输出 1. scanf与printf ####（1）scanf scanf函数称为格式输入函数，即按用户指定的格式从键盘上把数据输入到指定的变量之中。scanf函数是一个标准库函数，它的函数原型在头文件“stdio.h”中。故在程序前面要先声明#include <stdio.h>. scanf的一般形式： scanf(“格式控制字符串”, 地址表列); 如scanf("%d",&a)； 其中，格式化字符串： 格式字符串的一般形式为： %[*][输入数据宽度][长度]类型 各部分含义： ①类型 格式 字符意义 d 输入十进制整数 o 输入八进制整数 x 输入十六进制整数 u 输入无符号十进制整数 f或e 输入实型数(用小数形式或指数形式) f或e 输入实型数(用小数形式或指数形式) c 输入单个字符 s 输入字符串 ②“*”符 用以表示该输入项，读入后不赋予相应的变量，即跳过该输入值。如： scanf("%d %*d %d",&a,&b); 当输入为：1 2 3时，把1赋予a，2被跳过，3赋予b ③ 数据宽度 用十进制整数指定输入的宽度（即字符数）。例如： scanf("%5d",&a); 输入12345678只把12345赋予变量a，其余部分被截去。又如： scanf("%4d%4d",&a,&b); 输入12345678将把1234赋予a，而把5678赋予b。 ④长度 长度格式符为l和h，l表示输入长整型数据（如%ld）和双精度浮点数（如%lf）。h表示输入短整型数据。 地址列表： &是一个取地址运算符，&a是一个表达式，其功能是求变量的地址。系统先为其变量a分配内存空间，这样变量a就有了内存地址,用&取出a的地址,把输入的数根据所取出的地址，存入内存空间。 scanf实现原理： 用户输入 -> 输入缓冲区 ->scanf scanf只要输入缓存区有内容,就不会要求用户输入数据。 由于scanf函数本身不能显示提示串，故先用printf语句在屏幕上输出提示，如： printf("input a,b,c:"); scanf("%d%d%d",&a,&b,&c); (2) printf 功能是将程序运行的结果输出到屏幕上. 一般格式： ①printf("字符串\n"); ②printf("字符串\n"); ③printf("输出控制符1 输出控制符2…", 输出参数1, 输出参数2, …); 如: printf("%d %d\n", i, j);//%d就是输出控制符。 输出控制符：计算机中所有的数据都是二进制 0、1 代码，所以输出的时候要用“输出控制符”告诉计算机以什么形式将二进制数据显示出来。 2. getchar与putchar （1）getchar 从标准输入流只读取一个字符(包括空格、回车、tab)，读到回车符('\n')时退出，键盘输入的字符都存到缓冲区内,一旦键入回车,getchar就进入缓冲区读取字符,一次只返回第一个字符作为getchar函数的值,如果有循环或足够多的getchar语句,就会依次读出缓冲区内的所有字符直到'\n'. 如：while((ch=getchar())!='0') // putchar(ch); ####（2）putchar 函数putchar()用于将给定的字符输出到控制台，其原型如下： int putchar (int ch); 二、控制结构 1.分支语句 1.1 分支分类 if if-else if-else if-else switch(多分支适用) 注意： if-else 就近原则配对 2.循环语句 while for do while 注意： ①不可以在for循环体内修改循环变量，防止for循环失去控制（死循环）。 ②建议循环控制变量的取值采用“前闭后开”写法。for(i=0; i <10; i++) ③for循环的初始化、调整、判断都可以被省略，但是如果判断部分省略掉，判断条件就恒为真，陷入死循环。

毛不易 《给你给我》 给你我平平淡淡的等待和守候 给你我轰轰烈烈的渴望和温柔 给你我百转千回的喜乐和哀愁 给你我微不足道 所有的所有 给我你带着微笑的嘴角和眼眸 给我你灿烂无比的初春和深秋 给我你未经雕琢的天真和自由 给我你最最珍贵 所有的所有 给你我义无反顾的长长和久久 给我你多年以后仍握紧的手 给你成熟 你给我迁就 会不会就这样白了头 给你我义无反顾的长长和久久 给我你多年以后仍握紧的手 给你成熟 你给我迁就 会不会就这样白了头 给我你带着微笑的嘴角和眼眸 给你我轰轰烈烈的渴望和温柔 给我你未经雕琢的天真和自由 给你我微不足道 所有的所有 给你我微不足道 所有的所有 《一程山路》 青石板留着谁的梦啊 一场秋雨 又落一地花 旅人匆匆的赶路啊 走四季 访人家 如同昨夜天光乍破了远山的轮廓 想起很久之前我们都忘了说 一夜曲折过后 又一道坎坷 走不出 看不破 山谷的薄雾吻着烟霞 枯叶之下 藏多少情话 划破天空的归鸟啊 它不问 你不答 如同昨夜天光乍破了远山的轮廓 想起很久之前我们都忘了说 一夜曲折过后 又一道坎坷 走不出 看不破 潺潺流水终于穿过了群山一座座 好像多年之后你依然执着 白云是否也听过你的诉说 笑着你 笑着我 白云是否也听了你的诉说 笑着你 笑着我

一、数据存储 1. 数据类型 类型的意义： 使用这个类型开辟内存空间（大小决定了适用范围） 决定了如何看待内存空间的视角 1.1 内置类型 （1）整形家族 char 有符号数，范围是[-128，127] short int long （2）浮点型家族 float：4字节 double：8字节 （3）指针类型 *p （4）空类型 void表示空类型，通常用于函数的返回类型、函数的参数、指针类型 1.2 自定义类型（构造类型） 数组类型 结构体类型 struct 枚举类型 enum 联合类型 union 此处见二、自定义数据类型 2.整形在内存中的存储 （1）原码反码补码 计算机中的有符号数有三种表示方法，即原码、反码和补码。对于整形，数据存放内存中存放的是补码 8位二进制, 使用原码或反码表示的范围为[-127, +127], 即2^7-1，而有符号数使用补码表示的范围为[-128, 127]，-128就是10000000，无符号数范围是[0，255]；因为机器使用补码, 所以对于编程中常用到的32位int类型, 可以表示范围是: [-2^31, 2^31-1] 因为第一位表示的是符号位.而使用补码表示时又可以多保存一个最小值。 原码： 直接将二进制数按照正负数形式翻译成二进制就可以； 反码： 正数的反码是其本身 将原码的符号位不变，其它依次按位取反； 补码： 正数的反码是其本身 反码+1就是补码。 栗子： [+1] = [00000001]原 = [00000001]反 = [00000001]补 [-1] = [10000001]原 = [11111110]反 = [11111111]补 正码、反码和补码详解 真值： 现实世界中的数字 原码：在真值的基础上解决了正负号在机器中的表示问题 补码：在原码的基础上解决了如何将减法变成加法的问题 移码：在补码的基础上解决了数字的直观大小比较问题 （2）大小端 大端模式（大端字节序存储模式）：数据的低位保存在内存的高地址中，而数据的高位保存在内存的低地址中 小端模式（小端字节序存储模式）：数据的低位保存在内存的低地址中，而数据的高位保存在内存的高地址中 栗子： 判断当前机器的字节序： //思路：将存储的地址存放在一个字符指针变量中，判断首元素和待比较的低位相等。 将其封装成一个函数： 指针部分可以简化成：return *(char* )&a; （3）整型提升 表达式中的字符和短整型操作数在使用之前被转换为普通整型，这种转换称为整型提升。 表达式中各种长度可能小于int长度的整型值，都必须先转换为int或unsigned int，然后才能送入CPU去执行运算。 负数的整型提升 char c1 = -1; 变量c1的二进制位(补码)中只有8个比特位： 1111111 因为 char 为有符号的 char 所以整形提升的时候，高位补充符号位即1， 提升之后的结果是： 11111111111111111111111111111111 正数的整型提升 char c2 = 1; 变量c2的二进制位(补码)中只有8个比特位： 00000001 因为 char 为有符号的 char 所以整形提升的时候，高位补充符号位即0， 提升之后的结果是： 00000000000000000000000000000001 无符号整形提升，高位补0 （4）举个栗子 题一： （即使两个char类型8位的相加，在CPU执行时实际上也要先转换为CPU内整型32位操作数的标准长度。） 题二： 计算方法：因为整形存储的是补码，所以先计算出32位补码，后取8位char类型，遇到整型提升（%d），补充0/1至32位（此时还是补码），提升后输出将此时的补码转化成原码再转化成十进制即可。 原码——>补码（取后八位...）——>整型提升成补码——>原码输出 负数：补充1 正数：补充0 无符号unsigned：补充0 题三： 题四： //这里的数是int类型，在计算时不需要取后8位整型提升；%d是输出有符号数，将相加后的补码，按照符号位不变的原则，算出对应原码即可。 题五： //因为i是无符号数始终>=0，此循环执行结果为：9，8，7，6，5，4，3，2，1，死循环。 无符号数取值范围：[0,255]；有符号数（char）取值范围：[-128,127] 题六： //此题注意有符号类型（char）的范围和钟表法 2.浮点型在内存中的存储 1.1 浮点数的表示方法 （1）表示方式： S：符号位 M：1<=M<2，M可以写成1.~~~~~~形式，在计算机保存Mde时候，默认第一位总为1，故存储时只存小数点后的数，小数部分补齐0至32/64位，读取时再加上第一位的1。好处就是可以多存一位有效数字。 E：是无符号整数，若E为8位，它的范围是[0，255]；若E为11位，它的范围是[0,2047]。 因为科学计数法中E可能是负数，如十进制小数0.5它转换成二进制为0.1，写成科学计数法为（-1）0`*`1.0`*`2(-1),所以IEEE 754规定，保存E时加上中间值，对于8位，加上127；对于11位，加上1023,这样保证了存入的E为正。 补充：关于二进制与十进制的转换 其中，E从内存中取出有以下三种情况： ①E不全为1或不全为0 举个栗子：0.5 （-1）0`*`1.0`*`2(-1)：s=0,M=1.0,E=-1，E存入的位-1+127=126；对于32位来说，存储如下： ②E全为0 当E为0时，那么真实值为-127，那么V趋于0. 所以直接规定，当指数E存储值为0时，它的真实值为1-127，有效数字M不再加上1，直接写成+-0.几几几。 这样的好处就是可以表示+-0，以及接近于0的很小的数字。如： 0/1 00000000 01100000000000000000000——>+/- 0.011*2^(-126) ③E为全1 当E=11111111即255时，E的真实值为128，表示的数是正负无穷大的数字。 举个栗子： //n=9是整形，存入的形式是：符号位（1）+数值（31位） 即00000000 00000000 00000000 00001001 若要以%f输出，则将00000000 00000000 00000000 00001001看成是0 00000000 0000000 0000000000001001即S（1位）+E（8位）+M（23位）表示的数就是（-1）^0*0000000 0000000000001001*2^(-126) ，趋于0 。 9.0是float类型，二进制为1001.0，E存储值为127+3=130，存放形式是0 10000010 00000000000000000000000 若以整形形式输出，将其看成0（符号位） 1000001000000000000000000000000即可。 二、自定义数据类型 1.结构体 1.1 结构体类型的声明 结构是一些值的集合，这些值成为成员变量。结构体的每个成员可以是不同类型。 （1）结构的声明 声明格式： struct tag { member-list; }variable-liast; //tag 是结构体标签。 member-list 是标准的变量定义，比如 int i; 或者 float f，或者其他有效的变量定义。 variable-list 结构变量，定义在结构的末尾，最后一个分号之前，您可以指定一个或多个结构变量。 在声明结构体时，tag、member-list、variable-list 这 3 部分至少要出现 2个： ①声明了结构变量，未声明结构体标签——又叫匿名结构体类型，必须要声明结构变量。 struct { int a; char b; double c; } s1; ②未声明结构变量，声明了结构体标签 struct Su { int a; char b; double c; } ; ③声明了结构变量，也声明了结构体标签 struct Su { int a; char b; double c; } s1; 1.2 结构体的自引用 struct Node { int data; struct Node* next; }; 可以使用 typedef 来为用户自定义的数据类型取一个新的名字。 typedef struct Node// 重命名时不建议省略结构体标签，若省略，则Node无声明。 { int data; struct Node next; } Node; 1.3 结构体变量的定义和初始化 （1）定义 struct Su { int a; char b; double c; } s1;//定义方式1：声明类型变量的同时定义变量s1 struct Su s2；//定义方式2：定义结构体变量s2 (2)初始化 s.c='c',s.a=100赋值也可以。 在结构体里包含结构体： 访问weight，用s.st.weight即可。 1.4 结构体内存对齐 （1）对齐原因 平台原因（移植原因） 并非所有平台能任意访问任意地址的任意数据，某些硬件只能在某些地址处取某些特定类型的数据。 性能原因 数据结构（尤其是栈）应该尽可能在自然边界对齐，因为若是未对齐的地址，处理器需要两次内存访问，而对齐的地址只需要访问一次。 （2）对齐规则 第一个成员在与结构体变量偏移量为0的地址处。 其他成员变量要对齐到对齐数的整数倍的地址处。这里的地址是相对于初始地址0而言，也就是偏移量。 对齐数=编译器默认的一个对齐数 与 该成员大小（最基本的数据类型的大小）的较小值。 char arr[5]//对齐数为1 结构体总大小为最大对齐数（每个成员变量都有一个对齐数）的整数倍。（不够就补齐空间） 如果嵌套了结构体，嵌套的结构体对齐自己的最大对齐数的整数倍的地址处，结构体的整体大小就是所有最大对齐数（含嵌套结构体的对齐数）的整数倍。 对规则的解释： 题1： 注：其中vs默认对齐数是8，gcc编辑器没有默认的对齐数，对齐数就是成员大小。 题2： //由上可知，尽量让占用小的成员集中在一起。 题3：（结构体嵌套） 计算步骤： （3）修改默认对齐数 #pragma pack(6)//设置默认对齐数为4，一般设置成2，4，8，16这样的数 #pragma pack（ )//取消设置的默认对齐数 补充： 引入头文件：#include <stddef.h> offsetof()函数用来计算偏移量。 具体的之后更新。 ........ 1.5 结构体传参 结构体传参的时候，要传结构体的地址 1.6 位段 (1) 位段的声明： 位段的成员必须是int，unsigned int，signed int。 位段的成员名后有一个冒号和一个数字，数字代表着二进制位。 struct S { int a : 2; int b : 5; int c : 10; int d : 30; }; //struct S s; //sizeof(s)=8字节 (2)内存分配规则 位段成员可以是 int，unsigned int，signed int或是 char（整形家族）； 位段的空间上是按照需要以4个字节（int）或者是1个字节（char）的方式来开辟的； 位段：不跨平台，注重可移植的程序应该避免使用位段。 （3）应用 数据传输时的数据包 2.枚举 1.2 枚举类型的定义 enum Sex { //枚举的可能取值-常量 male，//male默认的值为0 female，//默认值为1 secret//默认为2，依次加1 }; 除了默认值赋值外，也可以自己赋给常量一个初始值。 1.3 枚举的优点 （1）增加代码的可读性和可维护性 （2）与#define比较，枚举有类型检查，更严谨 （3）防止了命名污染（封装） （4）便于调试，一次可以定义多个常量 3.联合(共用体) 1.1 定义 联合是一种特殊的自定义类型，定义的变量包含了一系列成员，特征是这些成员共用同一块空间。 union Un { char c; int i; }; union Un u; sizeof(u)//4，大小至少是最大成员的大小;（满足4是最大对齐数4的整数倍） //&u,&u.c,&u.i三者的地址一样，共用同一块空间 补充：用联合体判断大小端： 1.2 联合大小的计算 联合的大小至少是最大成员的大小 当最大成员的大小不是最大对齐数的整数倍的时候，就要对齐到最大对齐数的整数倍。 三、动态内存分配 1. 基本介绍 （1）内存的使用方式 创建一个变量 栈区：存放局部变量、函数的形式参数 堆区：动态内存分配 静态区：存放全局变量、静态变量 创建一个数组 2.基本函数 1.1 malloc 1.2 1.3.常见的动态内存错误 1.4.举个栗子 1.5.柔性数组

一、数组 1. 定义 数组是一组相同类型元素的集合，它在内存中是连续存放的。创建方式为： type_t arr_name [const_n] ,如： int arr[5] char arr[3] double arr[10] 2.初始化： 不完全初始化：int arr[5]={1,2,3} 剩下的元素默认为0； 未指定数组长度：int arr[]={1,2,3,4} 字符串形式初始化：char arr[]='abcd' 补充：sizeof和strlen sizeof：“sizeof()”运算符求的是字符数组的长度，而不是字符串长度。只跟你给该字符串数组定义了多大空间有关，而跟字符串是否结束无关.如果遇到字符串，编译时会自动在末尾增加一个 null 字符，即char arr1[]='abc\0'。 strlen：用来计算以’\0’结尾的字符串长度的函数。它并不是计算内存大小，仅计算字符串从开端到’\0’结尾字符的个数(不包含’\0’)。 char arr1[]='abc';//字符串 char arr2[]={'a','b','c'}//字符数组 sizeof(arr1)=4//41=4， char arr[]={'a','b','c','\0'} sizeof(arr2)=3//31=3 strlen(arr1)=3 strlen(arr2)=随机数 其中，arr1[]是字符串,arr2[]是字符数组 总结：以字符串形式出现的，编译器都会为该字符串自动添加一个0作为结束符，如在代码中写 "abc",那么编译器帮你存储的是"abc/0"，char arr[]="abc"实际上存储的是 char arr[]={'a','b','c','\0'} 3.二维数组 3.1 创建方式 数据类型 数组名称[行][列]，如：int arr[3][2]代表三行两列的数组 3.2 初始化 不完全初始化：int arr[3][2]={1,2,3} 剩下的元素默认为0； 1 2 3 0 0 0 指定行列：int arr[3][4]=={{1,2,3},{4,5}} 1 2 3 0 4 5 0 0 0 0 0 0 3.3 使用 访问元素： for(int i=0;i<3;i++){  for(int j=0;j<4;j++){   print("%d",arr[i][j]); }   print("\n") } 数组作为函数参数: void bubble_sort(int arr[],int sz){ { ... } int main(){ int arr[]={1,2,3,4,5}; bubble_sort(arr,sz);//我们对arr进行传参，实际上传递过去的是数组的首元素的地址即&arr[0]; int sz=sizeof(arr)/sizeof(arr[0]); ... return 0; } 补充1：关于sizeof（arr）/sizeof(arr[0]) sizeof(arr)计算的是数组arr所占的总字节数，即空间大小； sizeof(arr[0])是单个元素的大小； sizeof（arr）/sizeof(arr[0])就是数组的长度； 如：int arr[]={1,2,3,4,5} 数组长度：sizeof（arr）/sizeof(arr[0]) 其中，整数 int占4个字节，总字节数/4就是数组长度； char arr[]={'a','b','c'} 数组长度：sizeof（arr）/sizeof(arr[0]) 其字母占1个字节，故可简写成：sizeof（arr）。 补充2：&数组名、&数组名【】 &数组名：取出的是整个数组的地址（打印出首元素地址作为整个地址地代表）->p=&arr,*p=arr(p是整个数组的地址，*p是数组首元素的地址) &数组名[0]：取出的是数组的首元素地址 数组名：取出的是数组的首元素地址 ☀️☀️注意： ①数组名arr是首元素地址，但是以下两种 情况除外： sizeof(arr) 数组名表示整个数组，求得数组的大小，单位是字节。sizeof（arr）/sizeof(arr[0])；arr表示整个数组，sizeof（arr）表示整个数组的大小。 &arr表示整个数组的地址。 ②int arr[10]={0} 二、指针 1.1 定义 指针是编程语言中的一个对象，利用地址，它的值直接指向存在电脑存储器中的另一个地方的值，地址指向变量单元，存放地址的变量就是指针变量，换句话说，指针就是一个变量，里面存放着地址，指针就是地址。 如： int a=10 int *p=&a//p是一个指针变量 prunt(*p)// *是解引用，取指针p指向的地址里的内容，*p=10 指针的大小在32位平台是四个字节，在64位平台是八个字节。 1.2 指针和指针类型 （1）指针类型的意义 ①指针类型决定了指针进行解引用操作的时候，能够访问空间的大小。 int*p： *p能够访问4个字节 char *p：*p能够访问1个字节 double* p：*p能够访问8个字节 ②指针类型决定了指针走一步走多远（指针的步长） int*p： p+1-->往后4字节 char *p：p+1-->往后1字节 double* p：p+1-->往后8字节 （2）野指针 指针执行的位置是不可知的 导致野指针的原因： 未初始化，局部变量不初始化，默认是随机值 指针越界访问 指针指向的空间释放 怎么避免野指针： 指针初始化 小心指针越界 指针指向空间释放的话，使之置为NULL 指针使用之前检查有效性 补充： ① i++与++i 区别一：i++是右值，++i是左值，左值是可以放到赋值符号左边的变量，即具有对应的可以由用户访问的存储单元，并且能够由用户去改变其值的量，而右值i++不可以。比如说： int i=0； ++i=1;//正确 i++=1;//错误 左值与右值的根本区别在于是否允许取地址&运算符获得对应的内存地址，左值允许，右值不允许。如 &（++i）//正确 & (i++) //错误 为什么++i允许，而i++不允许呢？ C/C++语言中可以放在赋值符号左边的变量，即具有对应的可以由用户访问的存储单元，并且能够由用户去改变其值的量。左值表示存储在计算机内存的对象，而不是常量或计算的结果。或者说左值是代表一个内存地址值，并且通过这个内存地址，就可以对内存进行读并且写（主要是能写）操作；这也就是为什么左值可以被赋值的原因了。相对应的还有右值：当一个符号或者常量放在操作符右边的时候，计算机就读取他们的“右值”，也就是其代表的真实值。简单来说就是，左值相当于地址值，右值相当于数据值. 区别二：i++是先运算后自加；++i是先自加后运算。比如说： i=3 n=i++,此时，n=3，i=4（先赋值运算，后加1） n=++i，此时，n=4，i=4（先加1，后赋值运算） ②指针+-整数 float arr[5]; float *vp；//定义一个指针变量 for (vp=&arr[0]; vp<arr[5]; ){ . *vp++ = 0； } 指针vp指向数组arr的首元素地址，vp++=0先赋值给vp为0，在vp+1指向第二个元素，第二个元素=0；直至第五个元素也为0. ③指针-指针（地址-地址） 必须是同类型指针 int arr[5]={1，2，3，4，5} &arr[5]-&arr[0]=5//结果是两指针中间的元素个数 ④指针比较大小 法一： for(vp = &arr[5];vp>&arr[0]; ){ *--vp = 0; } 法二： for(vp = &arr[5-1];vp>=&arr[0];vp-- ){ *vp = 0; } 但是更推荐第一种方法，标准规定：允许指向数组元素的指针与指向数组最后一个元素后面的那个内存位置的指针比较即法一，不允许与指向第一个元素之前的那个内存位置的指针进行比较。 1.4 二级指针 1.4.1 定义 int a=10; int * p1 = &a;//一级指针，int*分开，int表示p1指向的对象类型是int整形，*表示p1是指针 int* * p2=&p1//二级指针，int*表示p2指向的对象类型是int*指针即p1，右边的*表示p2是一个指针; 1.4.2 用法 解引用： *p1=**p2=a=10 *p2=p1 1.4.3 指针与数组 #####（1）指针数组 指针数组就是存放指针的数组。 int a = 10; int b = 20; int c = 30; int* pa=&a; int* pb=&b; int* pc=&c; 为了方便，我们可以将pa,pb,pc指针存放在一个数组中。 int* arr[3]={&a,&b,&c} 或int* arr[3]={pa，pb，pc} 遍历访问元素： int i=0; for(i=0;i<3,i++){ . *(arr[i]) } (2)数组指针 存放数组的指针。见进阶 三、指针进阶 1.1 字符指针 1.1.1 定义 法一： char ch = 'abc; char* pc = &ch; 法二： char* p = "abc"//把常量字符串“abc”的首元素a的地址放进了p中，而不是内容abc 这个严格来说应该这么写：const char* p="abc",理由后面介绍。 补充：字符数组和字符指针 （1）字符数组： char arr1[4]="abcd" char arr2[4]="abcd" 定义的是一个字符数组，所以就相当于定义了一些空间来存放"abcd"，而又因为字符数组就是把字符一个一个地存放的，所以编译器把这个语句解析为 char arr[5] = {'a','b','c','d','\0'}; 回顾之前到讲到的，sizeof(arr[5])=5; 扩展一下，如果char arr[] = "abcd"是在函数内部写的话，那么这里 的"abcd/0"因为不是常量，所以应该被放在栈上。 另外，arr1！=arr2，因为arr1，arr2分别定义了各自的空间来存储内容，这里恰巧两个的字符数组的内容一样而已。故，两者不一样。 （2）字符指针： char* p1="abcd" char* p2="abcd" 定义的是一个普通指针，并没有定义空间来存放"abcd"，所以编译器得帮我们找地方来放"abcd"，显然，把这里的"abcd"当成常量并把它放到程序 的常量区是编译器最合适的选择。拓展一下， 字符指针指向的字符串保存在内存的静态存储区中。 因为是常量字符串，如下操作： char* p1="abcd" p1=“h” 错误，常量字符串不可修改。 另外，p1==p2,因为p1，p2都是常量，内容都是“abcd”，都指向同一个内存空间。 此处，为避免错误，还是写成const char p="abcd"为好。 总结一下就是： 首先在内存的中位置不同，字符数组保存的字符串存放在内存的栈中，而字符指针指向的字符串保存在内存的静态存储区中。 其次字符数组保存的字符串属于字符串变量，可以被修改，而字符指针指向的字符串是属于字符串常量，不能被修改。 1.2 指针数组 1.2.1定义 指针数组是一个数组，用来存放指针。 int* p[10]={0}//存放整形指针的数组-指针数组 char* p[10]={0}//存放字符指针的数组-指针数组 1.2.2 使用 指针数组访问每个元素： 1.3 数组指针 数组指针是一个指针,(*p)，用来指向数组的指针。 int* p=NULL //p是整形指针-指向整型的指针-存放整形的地址 char* pc=NULL //pc是字符指针-指向字符的指针-存放字符的指针 int (*p )[10]=&arr //数组指针-指向数组的指针-存放数组的地址 关于数组的地址，前面有讲过，即&arr。 书写方法： char* arr[5]; char* (*p)[5]=&arr; int arr2[10]={0]; int (*p2)[10]=&arr2; 补充：关于*星号 ①在定义变量时，代表着该变量是一个指针 int a=10; int* p=&a; ②在取值操作时，叫解引用，即得到指针指向的地址的内容 *p=a=10 ③ &放在一起，抵消掉，如： int a,b; a=100; b=100; int *p,*q; p=&a; q=&b; *p=*q; 代入：&a=&b 抵消：a=b ④有，&符号出现，就说明此处用到了指针，指针（或者说数组/数组元素地址）的大小在32位平台是4，64位平台是8。原因：在32位cpu上，指针能够存储这2^32次个地址就需要4个字节。（1字节=8位）. 遍历方法： int arr[10]={1,2,3,4,5,6,7,8,9,10}; int* p=arr; int i=0; for(i=0;i<10;i++){ . printf("%d", *(p+i)) . printf("%d", *(arr+i))//用指针的方法打印 . printf("%d", arr[i])//普通的数组打印方式 . printf("%d",p[i]) 四种打方式结果一样 } 关于二维数组： 二维数组的数组名是首元素的地址，这里的首元素不是第一行第一列的元素，而是第一行所有的元素。（这里把二维数组理解成特殊的一维数组） 遍历二维数组的元素： 法一： 参数是数组的形式 法二（用数组指针）： 参数是指针的形式 难点：解释下为什么是*（*（p+i）+j）: 补充： *（*（p+i）+j）的等效写法： ①（*（p+i）[j]）//备注：*（p+i）=p[i],。*（p+i）=p[i], 比如说，p是二维数组arr的首元素地址p=arr=&arr1，*p=p[0]是一维数组arr1的首元素地址。 ②*（p[i]+j） ③p[i][j] ④二维数组的数组名是地址的地址a=&a[0]=&&a[0][0],一次解引用：*a=&a[0][0],二次解引用：**a=a[0][0] a[0]讲解： 二维数组指针表示，C语言指针引用二维数组详解 1.4关于以上几种类型的总结 ①int arr[5]//arr是一个5 个元素的整型数组 ②int* parr1[10]//parr1是一个数组，数组有10个元素，每个元素的类型是int*, parr1是指针数组 ③int(* parr2)[10]//parr2是一个指针，该指针指向了一个数组，该数组有10个元素，每个元素的类型是int， parr2是数组指针 ④int (* parr3[10]）[5])//parr3是一个数组，该数组有10个元素，每个元素是一个数组指针，该数组指针指向的数组有5个元素，每个元素的类型是int。 1.5 数组参数 1.5.1 一维数组 （1）数组在传参的时候可以将参数写成数组，也可以写成指针。如 void test(int arr[]) { } void test(int arr[10]) { } void test(int *arr); { } int main(){ int arr[10]={0}; test(arr); } 这三种传参都是正确的。 （2）指针数组在传参的时候可以将参数写成数组，也可以写成指针。如 void test(int* arr[])//数组类型是int* { } void test(int* arr[10]) { } void test(int** arr); { } int main(){ int* arr[10]={0}; test(arr); return 0; } 这三种传参也是正确的。 1.5.2 二维数组 (1)数组名写法 void test (int arr[3][5]) // 写成int arr[][5],不可以写成int arr[3][],行可以省略，列不可以省略 { } int main(){ int arr[3][5]={0}; test(arr); return 0; } （2）指针写法 ①void test (int* arr)//写法错误，整形指针只存放整形，不能存放数组，而arr是二维数组的首元素地址，也就是第一行数组的地址 { } ②void test (int** arr)//写法错误，二级指针是用来存放一级指针的地址，而arr是一个数组的地址 { } ③void test (int* arr[5]）//写法错误，arr是一个数组，每个元素类型是int* { } ④void test (int（* arr)[5]）//写法正确，arr是一个指针，指向第一行数组的五个元素，类型是int { } int main(){ int arr[3][5]={0}; test(arr); return 0; } 1.6 指针传参 1.6.1 一级指针传参 void test1(int* p)//传过来的是地址（整形指针），所以这里要用一个指针来接收 {} int main() { int a=10; 'test1(&a);//传过去的是地址 int* p=&a; test1(p);//传过去的是a的地址，将a的地址存在指针变量p里面 } 1.6.2 二级指针传参 void test1(int** ptr)//传过来的是一级指针的地址，所以这里要用一个二级指针来接收 {} int main() { int a=10; int* p=&a; int** pp=&p//pp是二级指针; test1(pp);//传过去的是一级指针p的地址，将p的地址存在二级指针变量pp里面 test1(&p); int* arr[10];//定义一个指针数组，里面存放着一级指针 test1(arr)//arr是数组首元素地址，也就是一级指针的地址 } 故，当函数的参数为二级指针得时候，参数可以是： 一级指针变量的地址 二级指针变量本身 存放一级指针的指针数组的数组名 1.7 函数指针 数组指针-指向数组的指针-存放数组的地址- int （* p）[10] 函数指针-指向函数的指针-存放函数的地址- int (* p)(in tx, int y)//函数指针类型int（* ）(int x,int y),p是一个函数声明。 使用方法： int ADD(int x,int y) { ...} int main() { int(* p)(int x,int y); p(2,3); ADD(2,3); (*p)(2,3) (*ADD)(2,3) //以上四种调用函数ADD的方法都正确 //调用的时候，的数量没有用，*没有意义 } 补充： ①&函数名和函数名都是函数的地址 ②( *( void ( * )( ) ) 0 )( ) 把0强制类型转换成：void（）（）函数指针类型，0就是一个函数的地址。（*（...）0）（）调用0地址处的该函数。 ③void (*signal(int , void(\*)(int) ) )( int ) signal是一个函数声明，signal的函数有2个参数，一个是int，一个是void（*）（int）函数指针，该函数指针指向的函数的参数类型是int，返回类型是void。 signal返回类型也是一个函数指针，该函数指针指向的函数的参数类型是int，返回类型是void。 该代码可以简化成： typedef void(*pfun_t)(int); pfun_t signal(int,pfun_t); 1.8 函数指针数组 指针数组-int* arr[5] 函数指针-int(* p)(int int)=ADD//函数指针的返回类型是int 函数指针数组-存放多个函数的地址即函数指针的地址-int (* parr[4])(int ,int)={ADD，SUB，MUL，DIV} : parr是一个数组，有四个元素，每个元素的类型是函数指针。 使用方法： 函数指针数组的用途--转移表： 计算器案列： int main(){ } //pfArr是一个函数指针数组，又叫转移表 1.9 指向函数指针数组的指针 1.9.1 定义 数组指针-指向数组的指针-存放数组的地址 指向函数指针的数组的指针--存放着函数指针数组的地址 int (* pf)(int , int)//函数指针 int(* pfArr[4])(int , int)//函数指针数组，pfArr是一个数组，函数指针数组 int(* (* ppfArr[4] )(int , int))//指向函数指针数组的指针，ppfArr是一个数组指针，指针指向的数组有4个元素，每个元素的类型是一个函数指针int( * )(int ， int) 1.9.2 回调函数 回调函数就是一个通过函数指针调用的函数。 解释一下就是，如果你把函数的指针（地址）作为参数传递给另一个函数，当这个指针被用来调用其所指向的函数时，我们就说这是回调函数。 1.9.3 qsort函数 ... 三、指针和数组笔试题 1.1 一维数组 1.1.1 sizeof（）问题 （1）整形数组 （2）字符数组 （3）初始化为字符串的数组 总结： 一个指针（或者说数组/数组元素地址）的大小在32位平台是4，64位平台是8。原因：在32位cpu上，指针能够存储这2^32次个地址就需要4个字节。（1字节=8位），64位同理； 求地址的大小（数首元素地址，下一个元素地址，整个数组地址，下一个数组地址...）都是4/8字节。 求元素的大小，就看是整形还是字符，整形4个字节，字符型1个字节。 不分char，int等类型，只要是求地址大小，都是4/8. 1.1.2 strlen（）问题 （1）字符数组 （2）初始化为字符串的数组 总结： C 库函数 size_t strlen(const char *str) 接收的类型是地址char *，函数返回值是无符号的。从给定地址往后寻找，从给定直到空结束字符（不包括空结束字符），然后返回字符串 str 的长度。 如果传给strlen（）的参数是未可知范围的地址，strlen会一直走下去，直到遇到"\0"为止，‘\0’出现位置是未知的，结果就是随机值（如char arr[]={'a','b','c'},strlen(arr) 随机）； 如果传给strlen（）的地址后面会出现'\0',那么就返回字符串的长度（char arr[]=“abc”,strlen(arr) =6）； 如果传给strlen的参数是一个具体的元素而不是一个地址，这样会把字符a的ascii码值97传给strlen函数，而此函数是访问不到这个地址的，因此会程序中断。（char arr[]={'a','b','c'},strlen(*arr) 报错）。 1.2 二维数组 总结 ①a[0]： a[0]是二维数组的第一行，是二维数组的首元素地址，a[0]是第一行的数组名，也就是一维数组的首元素地址，即a[0]=&a[0][0] 二维数组指针表示，C语言指针引用二维数组详解 ②a： a是二维数组的数组名，没有sizeof（数组名），也没有&（数组名），所以a是二维数组的首元素地址，将二维数组看成一维数组，a就是第一行的地址即a=&a[0]，又因为a[0]是a[0][0]的地址，有a == &(&a[0][0]) 即二维数组名 a 是地址的地址。 ③数组名的意义 数组名有：一维数组arr，二维数组a，二维数组的第i行a[i] sizeof（数组名），这里的数组名表示整个数组，计算的是整个数组的大小，单位是字节，元素个数x单个字节 &数组名，表示是整个数组的地址 除此之外所有的数组名表示首元素地址 1.3 指针 题一： *（ptr-1）= ptr[-1]-->*(*(p+4)+2)=p[4][2] 题二： 题三： 题四： 补充： 逗号表达式： a=（表达式1, 表达式2），先求解表达式 1，再求解表达式 2。整个逗号表达式的值是表达式 2 的值。 如：a=（1，2），a就是2；b=(count=19, incr=10, count+1)，b就是20。 题五： 题六：

原因 今天我想更新一篇文章，在设置封面图的时候，选择了外链的方式打开，结果...Gridea的数据全没了，后来查明是因为在软件内填写封面图地址时，填入地址不合法，导致生成的md文件中“feature” 不合法。会导致软件无法读取数据。地址应该是url，而我用地址转换网站转换成markdown格式传上去了，就导致了后续的错误。 解决办法 找到Gridea的存储路径，我的是C:\Users\hp\Documents\Gridea，里面找到/post文件夹，然后找到你最近一次修改过的文章，,点进去将feature删除，保存后再次打开Gridea客户端即可。

“程序=数据结构+算法” ——Pascal语言之父-Nicklaus Wirth 一、绪论 1.1 研究内容 具体问题抽象为数学模型->分析问题、提取操作对象、找出操作对象间的关系、用数学语言描述。其中，操作对象和对象间的关系也就是数据结构。如何根据关系状态来解决问题用的方法就是算法。📐📏 1.2 基本概念于术语 （1）数据 数据是能输入计算机且能被计算机处理的各种符号的集合。包括数值型数据：int、float等；非数值型数据：文字、图像、声音等。 （2）数据元素与数据项 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理；数据项是数据元素不可分割的最小单位。比如，学生李华的姓名、学号、年龄等是一个数据元素，其中的姓名就是一个数据项。 （3）数据对象 数据对象是性质相同的****数据元素的集合，是数据集合的子集。比如整数集合，字母集合。 我画了如下一张图来表示他们之间的关系👇📣： （4）数据结构 数据结构是带结构的数据元素的集合；结构是指数据元素之间的关系。 数据结构的分类： 逻辑结构：数据元素之间的逻辑关系 物理（存储）结构：数据元素及其关系在计算机内存中的表示（又称映像） 运算和实现：对数据元素的操作 逻辑结构和存储结构的关系： 存储结构是逻辑关系的映像与元素本身之间的映像 逻辑结构是数据结构的抽象，存储结构是数据结构的实现 两者建立了数据元素之间的结构关系 逻辑结构的种类： 线性结构：最多只有一个直接前驱和直接后继 非线性结构：可能有多个直接前驱和直接后继 存储结构的分类： 顺序存储：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置决定的。C语言中用数组表示 链式存储：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。 索引存储：在存储信息的同时，还建立了附加的索引表。 散列存储：根据结点的关键字直接计算出该结点的存储地址。 （5）数据类型 数据类型 包括int、float等基本数据类型，数字、结构、共用体等构造数据类型，指针。 数据类型是一组性质相同的值的集合和定义于这个值集合上的一组操作的总称。 抽象数据类型（ADT） 形式定义：（D、S、P）三元组表示， D:数据对象； S：对象的关系集合； P：对D的基本操作集合 定义格式： ADT 抽象数据类型名{ 数据对象：定义 数据关系：定义 基本操作：定义 } ADT 抽象数据类型名 其中基本操作的定义内容为： 参数表：赋值参数，为操作提供输入值；引用参数：用连字符&表示，返回操作结果、 初始条件和操作结果。 概念小结： 1.3 算法与算法分析 1.3.1 算法特性： 有穷性 确定性 可行性 输入 输出 1.3.2 设计要求 正确性 可读性 健壮性 高效性 1.3.3 算法效率 算法的复杂度分析是事前估计，考虑其最坏情况，用大写O（f（n））表示。 (1)时间复杂度 算法运行时间= （语句频度）每条语句的执行次数执行时间之和 —>单次执行时间由机器决定，所以算法运行时间只讨论语句频度 如何计算时间复杂度： 计算规则：忽略常数、忽略系数、只取最高次项。 计算流程：算法中基本语句重复执行的次数是问题规模n的某个函数f（n），算法的时间量度记作：T(n)=O(f(n)),O(f(n))称为算法的渐进时间复杂度（O是数量级的符号），简称为时间复杂度。 首先，找到基本语句（即执行次数最多的语句）， 还有关于问题规模n的函数f（n）： 排序：n为记录数 矩阵：n为矩阵的阶数 多项式：n为项数 集合：n为元素个数 树：n为树的结点个数 图：n为图的顶点数或边数 最后用O表示 计算方法： 定理一:找最高次项 例子： for循环：嵌套几个for循环，时间复杂度就是n的多少次方 关于log2n的问题 ... 常见时间复杂度： 执行常数次操作：O(1) 二分查找：O（logN） 线性查找：O（N） 归并排序、快速排序：O（NlogN） 选择排序、插入排序：O（N^2） 搜索算法：O（2^N） 二、线性表 逻辑结构分为线性结构和非线性结构，其中线性结构有线性表、栈、队列、字符串、数组、广义表等。 线性表有两种基本存储结构：顺序存储和链式存储。 1.1 线性表的定义及特点 （1）定义 线性表是具有相同特性的数据元素的有限序列,记作（a1,a2,a3, a4, a5, a6......an），其中a1为线性起点，an为线性终点，a3的直接前驱是a2，直接后继是a4；数据元素的个数n叫表长，n=0是叫空表。 (2)特点 开始节点：有且只有一个，没有直接前驱，有且只有一个直接后继 终端节点：有且只有一个，没有直接后继，有且只有一个直接前驱 中间节点：有且只有一个直接前驱，有且只有一个直接后继 （3）案例 稀疏多项式：没有包含所有x的幂的多项式 如A=7+3x+9x8+5x17 B=8x+22x7-9x8 用线性表表示：p=（系数，指数） A=((7,0),(3,1),(9,8),(5,17)) B=((8,1),(22,7),(-9,8) 线性表运算： 先创建一个新数组C，分别遍历比较A、B里面的项： 指数相同，系数相加，其和不为零，则加到C中 指数不同，将指数较小的复制到C中 按照此方法：C=((7,0),(11,1),（22，7），(5,17)) 那么，新数组的大小应该定义成多大呢？显然并不好操作。我们可以用更合适的链式存储结构来存储A+B： 还是分别遍历A，B： 1.2 线性表的类型定义 （1）基本操作 InitList（&L）：初始化，构造一个空的线性表L DesyroyList（&L）：销毁已存在的线性表L ClearList：清空重置已存在的线性表L ListEmpty（L）：判断线性表是否为空，返回True或False ListLength（L）：计算线性表的元素个数 GetElem（L，i，&e）：若1<=i<=ListLength(L),用e返回第i个元素 LocateElem（L，e，compare（））：compare（）为数据元素判定函数，返回第一个与e满足compare（）的数据元素 PriorElem（L，cur_e,&pre_e）:c当ur_e不是第一个元素时，用pre_e返回cur_e的前驱。 NextElem（L，cur_e,&next_e）:c当ur_e不是最后一个元素时，用next_e返回cur_e的后继。 GetElem（&L，i，e）：若1<=i<=ListLength(L)+1（最后一个元素的后面）,在第i个位置插入新的元素e，L的长度加1。 ListDelete（&L，i,&e）:若1<=i<=ListLength(L),删除第i个元素，并用e返回其值，L长度减1. ListTraverse（&L，visited（））：遍历 1.3 线性表的顺序表示和实现 顺序表示又叫顺序存储（顺序映像）； 特点：地址连续、依次存放、随机存取、类型相同。 优点：存储密度大，随机存取任意元素 缺点：插入删除操作时，需要移动大量元素；浪费存储空间；静态存储，元素个数不可自有扩充。 定义：把逻辑上相邻的数据元素存储在物理上也相邻的存储单元中的存储结构，它占用了一片连续的储存空间。 故，可以计算出某个元素的位置。 公式：LOC（a_n）=LOC（a_m)+(n-m)*i 其中，已知第m个元素的位置和每个元素占用i个存储单元，求第n个元素的位置（n>m）。 若已知第一个元素，就变成了：LOC（a_n）=LOC（a1)+(n-1)*i 根据顺序表特点可用一维数组来表示： 线性表长可变-->用一变量表示顺序表的长度属性 注意：线性表顺序存储时的逻辑结构下标是从1开始，存储结构是从0开始的（因为存储在数组），因此，逻辑位序比物理位序多1。 1.4 顺序表基本操作的实现 （1）初始化 (2) 销毁与清空线性表 （3）线性表长度 （4）判断是否为空 （5）顺序表取位置为i的值 （6）按值查找 在线性表中查找与指定值e相同的是数据元素的位置，从表的一端与表中数据逐个比较，找到返回位置序号，未找到返回0。 平均查找长度（ASL）： 为确定记录在表中的位置，需要与给定值进行比较的关键字的个数的期望值叫做查找算法的平均查找长度。 简单来说，就是所有情况下的查找次数之和除以元素个数就是ASL。 ASL=∑PiCi (i=1,2,3,…,n),可以简单以数学上的期望来这么理解。其中：Pi 为查找表中第i个数据元素的概率，Ci为找到第i个数据元素时已经比较过的次数。 （7）插入算法 算法思想： 判断插入位置i是否合法（1~n+1） 判断存储空间是否已满（i<l.length） 将第n个位置至第i位的元素依次往后移动一个位置，空出第i个位置。 将要插入的新元素e放入第i个位置 表厂+1 插入情况： ①插入位置在最后 ②插入位置在中间 ③插入位置在最前面 算法实现： 算法分析：ASL=(n+...+1+0)/n+1=n/2 时间复杂度位O(n) (8) 删除操作 删除情况： 删除位置在最后 删除位置在中间 删除位置在最前 算法思想： ①判断删除位置是否合法（1~n） ②将欲删除的元素保留在e中（可选） ③将第i个元素至第n位的元素依次向前移动一个位置 ④表长-1，删除成功返回ok 算法实现： 算法分析： ASL： （n-1+n-2+n-3+...+0）/n=(n-1)/2 时间复杂度： O（n） 1.5 线性表的链式表示和实现 1.5.1 表示 （1）概念 ①结点 数据元素的存储映象。由数据域和指针域两部分组成。 数据域 指针域 数据域是存储元素数值数据；指针域是存储直接后继结点的存储位置（地址） ②链表 n个结点由指针链组成一个链表。 Head ->| 数据a | 指针p1 | ->| 数据b | 指针p2 | ->| 数据c | NULL | ③头指针 链表中第一个结点（即第一个数据元素的存储映像）的存储位置。当存在头结点时头指针指向头结点的数据域，当不存在头结点时，头指针指向首结点。 头指针具有标识作用，故常用头指针冠以链表的名字。 无论链表是否为空，头指针均不为空。头指针是链表的必要元素。 (2) 链表分类 ①单链表（或线性链表） 结点只有一个指针域的链表 单链表是由表头唯一确定的，故单链表可以用头指针的名字来命名，若头指针名是L，则叫做链表L。 ②双链表 每个结点有两个指针域的链表 ③循环链表 首尾相接的链表 补充： 怎么表示空链表？ 无头结点时，头指针为空表示空表 有头结点时，当头结点的指针域为空表示空表 设置头结点有什么好处？ 便于首元节点的处理 首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其他位置一致，无需进行特殊处理。 便于空表和非空表的统一处理 无论链表是否为空，头指针都是指向头结点得非空指针，因此空表和非空表的处理也就统一了。 头节点的数据域存放着什么？ 头结点的数据域可以为空，也可以存放线性表长度、监哨所等附加信息，但此结点不能计入链表长度值。 （3）链表特点 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。 只能通过头指针访问链表，并通过每个结点的指针域依次向后顺序扫描其余结点。 顺序表 -> 随机存取 eg:访问第i个元素，a[i-1]； 链表 -> 顺序存取 eg:访问第i个元素，要从1，2，3，...i依次访问到i。 （4）单链表 定义： 链表有单链表、双链表以及循环链表。其中，重点介绍单链表。 单链表是由表头唯一确定的，故单链表可以用头指针的名字来命名，若头指针名是L，则叫做链表L。 存储结构： 数据域 指针域 data next 定义链表L：LinkList L； 定义结点指针p: LNode *P; 栗子 typedef struct student{ char num[8]; char name[8]; int score;//前三都是数据域 struct student *next;//指针域，next指针指向下一个节点，指针类型是包含四个成员的struct student }Lnode,*LinList; LinkList L; 或者 typedef struct{ char num[8]; char num[8]; int score; }ElemType; typedef struct Lnode { ElemType data;//数据域 struct Lnode *next;//指针域 1.5.2 基本操作的实现 （1）单链表的初始化（带头结点的单链表） ^ 步骤： 生成一个新节点作为头结点，用头指针L指向头节点 将头结点的指针域置空 描述： Status InitList_L(LinkList &L){ L= new LNode;或 L=(LinkList)molloc(sizeof(LNode));//创建一个头结点 L->next=NULL;//将头结点的指针域置空 return 0; } 补充： 判断链表是否为空 空表：链表中无元素，但头指针和头结点还在 思路：判断头结点的指针域是否为空 算法描述： int ListEmpty(LinkList){ if(L->next)//若链表为空，返回0；不为空返回1 return 0; else return 1; } 单链表的销毁 链表销毁后不存在（头结点也会消失） 思路：从头指点开始，依次释放所有结点； 算法描述： Status DestoryList_L(LinkList &L){ LinkList p;//Lnode *p; while(L){ p=L;//p指针指向头结点 L=L->next; delete p; } } 清空单链表 链表仍存在，但链表无元素，成为空链表。（头结点仍存在,，其他节点删除） Status DestoryList_L(LinkList &L){ Lnode *p;*q;//或LinkList p,q; p=L->next;//p存放要删除的结点 while(L){ q=p->next;//q存放下一个节点 delete p; p=q; } L->next=NULL; return OK; } 单链表的表长 从首元结点开始，每访问一个节点，表长i就+1（头结点不算入表长） Status DestoryList_L(LinkList L){ Lnode *p; int i=0; p=L->next;//p指向首元结点 while(p){ i++;//p不为空，表长就加1 p=p->next; } return i; } (2) 取值-取单链表中第i个元素的内容 从第一个结点出发，顺着链域next逐个结点往下搜索，直至搜索到第i个节点为止。因此，链表不是随机存取结构。 算法描述: Status GetElem L(LinkList L,inti,Elemtype &e){ p=L->next;i=1; while(p&&j<i){ p=0->next; ++j; } if(!p||j>i) return ERROR; e=p->data; return OK; }//GetElem_L

写在前面： 爬虫基础 python基础 爬虫案例

我的python 之旅 记录与心得 - 流年的文章 - 知乎