C/C++基础

基础"/>

C/C++基础

C

二进制

问题：二进制怎么表示整数、小数、正数、负数，如何存储？加减乘除怎么运算（见文章《计算机加减乘除本质》）？

变量

c定义一个变量的时候，需要事先定义变量大小和变量类型。

//有符号整数
char 一个字节
short 两个字节
int 四个字节
long long 八个字节
__int64 八个字节
//无符号整数
unsigned char 一个字节
unsigned short 两个字节
unsigned int 四个字节
unsigned long long 八个字节
unsigned __int64 八个字节
//小数
float 四个字节
double 八个字节

sizeof(变量名)可以计算变量占用的字节数
可以定义一个数组存放同一种类型的变量，它存放的内存空间是连续的，大小是变量数*变量长度，如果是二维数组，则是先排第一行，再排第二行，以此类推

全局变量

当一个变量直接定义在函数外部，它是一个全局变量，程序开始时就常驻内存，直到程序退出。如果用static修饰，那么只能在文件内部使用，不能在其他文件访问。
如果static修饰的是局部变量，也会变成全局变量，但只能在函数内部使用，也就是说，这一块内存不会在使用中被分配和释放。

强制转换

当扩大了精度的时候，比如short转int，可以直接转没有精度损失，但是缩小精度比如int转short会丢失高位的数据，数据含义也有可能发生变化

c语言运行原理

进程是运行application的载体，客户端，服务器都是application，每个application会创建一个进程，在创建进程的时候，系统会在内存创建代码段，数据段，堆，栈。和其他三个不同，栈是每个线程独享的，其他三个是公共的。

代码段：编译器把c语言代码编译成二进制的指令代码运行时直接加载到代码段，代码段拥有一个指针，指向当前执行的指令，指令执行完，指针移动到下一个位置

数据段：负责全局变量，单例中的静态变量等的存放。

堆：用来做动态内存分配，例如创建对象的时候就是在堆创建出来，系统会从堆上分配一个满足要求大小的内存。如果不用了需要主动调用系统的free API来释放内存，但很多编程语言都内置垃圾回收器（GC），判断这个数据对象是垃圾，所以会主动回收，但是这会消耗系统性能，所以我们才需要尽可能减少GC。

栈：每个线程有独立的栈，存放代码执行中函数的参数等局部变量，并为函数跳转，返回提供服务，原理是栈临时存储了函数中的变量或引用，并在这个函数的顶部入栈了一个函数的形参，返回地址，前一个栈底地址（%ebp），以便函数调用完成后恢复原来的地址，并设置栈底(%esp)为当前栈顶值，调用完成后返回值压入EAX（如果返回值超过EAX宽度，高位放在EDX中）中并恢复现场。栈的大小有限制（默认几十k，可修改），超出会导致栈溢出，导致系统杀掉进程。

函数调用

参考：


当函数调用时：

1. 函数的参数会从右到左推入栈中，注意：在X64中如果函数参数超过6个，前6个通过寄存器进行传递，其余参数则通过栈来进行参数传递，当少于等于6个或没有参数时，这个时候该栈帧部分可以忽略。
2. 把本来要执行的下一个指令地址存到栈中，也称返回地址
3. 把原来的基准地址（%ebp）推入栈中，并把栈顶地址(%esp)赋给基准地址（%ebp），注意：(%esp)提取分配好了空间，并不是加入一个数据入栈往下移动一格
4. 把指令指针拨动到调用的函数的指令地址中
5. 函数运行中把局部变量推入栈中
6. 把返回值保存起来，如EAX寄存器中
7. 函数返回的时候，栈顶地址(%esp)先移动回基准地址（%ebp）。现在栈顶刚好存储之前的基准地址（%ebp），出栈并把基准地址赋回给（%ebp）。现在栈顶刚好又存放了返回地址，出栈并赋给指令指针。
8. 如果下一条指令是把返回值赋给变量，那么从EAX寄存器中取

指针

在c语言中，cpu读取内存中的数据是可以直接通过地址读取的，这个地址叫做指针。应用程序使用的是虚拟地址，32位系统中这个地址是32位，64位系统中是64位，操作系统会把这个虚拟地址映射到真实地址。
注意不要随意访问不确定或被系统保护的地址，否则将被系统杀掉进程。

int a = 10;
// 取地址（指针）
printf("0x%x\n",&a);
// 通过地址访问数据仅仅通过起始地址无法访问，还要加上变量类型，这样就能知道数据大小
int* p;// p是int类型的变量地址，相当于定义了一个指针
p = &a;// 取a的地址赋给p
int* *p2;
p2 = &p; // 指针的指针，也称二阶指针
printf("%lf\n",*p); // 取星号访问对应地址的数据void* v_ptr = &a // 这种地址只有起始数据没有字节大小，所以只能存地址无法访问数据

数组是一段连续的内存，分配在栈上

int b[3];
b //数组名字相当于首地址，相当于b[0]的地址
&b[2] // 直接访问对应元素的地址
b+2 // 地址和上面一样，在b的基础上往上偏移2个元素的地址
b-1 // 往前偏移一个元素的地址，不要越界
d = &b
d[2]  // 这种方式也可以访问在b的基础上往上偏移2个位置的内存数据int c[3][3]; // 其实是连续存了九个元素（一行行存），原理和一维相同
c[1] //相当于第一行的起始地址
&b[2][1] // 取特定元素的地址  

需要保证指针访问的内存是合法的，否则将会导致程序崩溃等不可预料的结果

动态内存分配

堆：用来做动态内存分配，例如创建对象的时候就是在堆创建出来，系统会从堆上分配一个满足要求大小的内存。如果不用了需要主动调用系统的free API来释放内存，但很多编程语言都内置垃圾回收器（GC），判断这个数据对象是垃圾，所以会主动回收，但是这会消耗系统性能，所以我们才需要尽可能减少GC。

malloc:操作系统调用，帮你从堆上分配指定大小的内存，返回一个起始地址。
free: 操作系统调用，帮你释放分配的内存，free中的参数必须是malloc返回的地址
realloc：扩容函数，分配新的内存把原来的数据拷贝过来，释放新的内存

void* alloc_block(int size){void* addr = malloc(size);return addr;
}void test_func(){// 分配内存int* p = alloc_block(100*sizeof(int));// 使用内存for(int i = 0; i < 100; i++){p[i] = i + 1;}// 释放内存free(p);
}void test2(){int* p = alloc_block(100*sizeof(int));for(int i = 0; i < 100; i++){p[i] = i + 1;}// 转移数据并释放原来的内存int* p2 = realloc(p, 200*sizeof(int));
}

注意，在c语言中， 堆上的内容除非调用free，否则会一直能够使用，不会自动清理

内存泄漏

如果没有一个可使用的变量保管系统分配出来的内存起始地址，将会导致内存不可使用，同时也不会释放，这就是内存泄漏。

内存泄漏导致可用内存越来越少，内存是有限的，内存不足会导致系统变慢，最后死机。进程被系统杀掉，资源全部回收。

内存操作

menset(dst,byte_value,内存大小字节数) // 把内存全部设为一个值
mencpy(dst,src,内存大小字节数) // 复制内存，速度快
memmove(dst,src,内存大小字节数) // 和copy功能差不多，但更加安全，能处理内存相交

char* p = malloc(100);
memset(ptr,0xff,100); // 所有字节都设定为0xff，注意最后的参数不能大于合法范围char* p2 = malloc(100);
memcpy(p2,p,100); // 把从p开始的100个字节的数据拷贝到p2开始的地方，注意两个范围都不能超过

宏与条件编译

编译器会将c代码转换成二进制的机器代码，C语言提供了标准能够编写一些命令指导编译器在编译程序过程中的一些逻辑，例如包含哪些头文件

宏定义：#define，定义编译过程中的一个符号

#define TEST_DEFINE // 只定义符号
#define WIDTH 640 // 定义符号为一个值
#define MAX(a,b) ((a > b) ? a : b) // 代替表达式的逻辑

有一段代码，我们想只有在达成条件的情况下才编译

#if 条件printf("aaa")#endif// 编译器定义了对应符号才会编译，做跨平台常用
#ifdef WIN32#endif

模块与头文件

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

在完成项目的时候，需要有组织给代码划分模块，

mymath.c

#include "mymath.h" # 方便检查接口和文件的实现保持一致
int g_a = 0
int math_abs(int value){return (value > 0) ? value : -value;
}

同名头文件mymath.h，这是公开给外部调用的接口，实现细节不要放到头文件，它应当是说明书，它会去同目录下搜索具体实现。注意不要在头文件定义全局变量，否则有可能重复定义，用extern替代

// 宏格式： __文件名_H__ ，字母全部大写
#ifndef __MY_MATH_H__  // 防止重复包含#define __MY_MATH_H__extern int g_a ; //  声明外部模块定义了这个变量
int math_abs(int value);#endif

使用的时候：

#include "mymath.h"

当include后面的文件是双引号“”，那么就会在工程项目中搜索文件，即当前编译的.c文件所在文件夹。文件名前面加上“…/”可以在上一层文件夹中搜索。也可以在下一层文件夹搜索例如"test/test.h"，如果查找不到，会到编译器自带的头文件目录搜索。同时也会到自定义的头文件路径查找，这个路径可以在编译器定义

当include后面的文件是尖括号<>，只会到编译器自带的头文件和自定义的头文件目录搜索。
使用的时候，我们要遵循自己的项目文件用双引号，第三方模块和自带模块用尖括号，方便维护并且加快编译速度。

字符和字符串

字符是二进制数据通过计算机图形学绘制出来的，用二进制数据对应表示的字符叫做编码，例如ASSIC码，utf8编码，unicode16编码。内存中存的是整数，通过编码才显示出字符。

char ch = "c"  // 英文可以用ASCII编码，用一个字节表示

字符串是一串字符，存放在连续的内存中，c语言中字符串以字符\0结尾，也就是二进制0结尾。

// 常量字符串只读，保存在数据段上
char* p = "Hello";  // 存放了字符串的起始地址
print("%s\n",p); // 输出整个字符串，直到遇到结尾符号
print("%s\n",p+2); // 输出除了前两个字符的字符串
char* p2 = "Hello";  // 因为是常量，和p指向同一个地址，节省空间

// 非常量字符串
char str_data[] = "Hello";
// 也可以分配堆的内存

strlen(字符串首地址) // 返回字符串长度
strcpy(目标地址，原地址，地址长度) // 复制字符串
strcmp(左边字符串对象，右边字符串对象)  // 是否相等
strncpy // 拷贝指定的字符个数
strncmp // 比较前n个字符串
strdump // 复制一个字符串到堆，不用了要用free释放，否则会内存泄漏

结构体

把多个数据打包起来，形成一个新的数据类型，方便管理

struct student{char name[16];int age;int sex;int grade;int class;
}struct student xm;
struct student xh;
sizeof(struct student) // 返回结构体大小xm.age = 10;
xm.sex = 1;  // 采用变量.成员名访问数据struct student xiaotian = {   // 从第一个成员开始直接初始化，可以不用初始化完"xiaotian",10,1,1,1
};struct student stuset[80]; // 定义结构体数组struct student* p = &xm;  // 结构体指针
p->age = 11; // 指针通过->访问数据成员
p->sex = 1;
(*p).class = 1;  // *p直接获取对象，一般不这么写// 动态内存分配
struct student* ptr = malloc(sizeof(struct student));
memset(ptr,0,sizeof(*ptr)); //初始化
ptr->age = 33;
free(ptr);ptr2 = malloc(100 * sizeof(struct student));
memset(ptr2, 0, 100 * sizeof(struct student));
for(int i = 0; i < 100; i++){ptr2.age = 10;
}
free(ptr2);

结构体变量定义在哪里，内存就分配在哪里，定义为局部变量在栈上，全局变量在数据段上。内存是从第一个成员开始依次排布。
当结构体作为函数参数进行传递的时候，传指针比直接传本身性能要好，传递数据少。

联合体和枚举

当可能是集合中的一种情况，使用结构体会造成浪费

union shape{  // 这里联合了三个结构体struct rect r;struct circle c;struct trangle t;
};union shape s;
s.c.xpos = 0;
s.c.ypos = 0;// 会把上面的数据冲掉
s.r.xpos = 0;
s.r.ypos = 0;

联合体只同时存放联合内容的其中一个，其中的内容起始地址都一样，因为被联合的项不并存，所以不冲突。内存大小根据最大的项决定。

枚举：当用一组有意义的名字代表数字的时候使用

enum AUDIO_TYPE{WAV = 1,   // 如果不赋值，默认为0MP3 = 2,OGG = 3,AMR = 4, // 如果不赋值，会默认为上一个+1
};

综合应用结构体和联合体

用一种结构体可以同时描述三种结构体

enum Type{RECT,TRANGLE,CIRCLE,
}struct object{int type;union{struct rect r;struct trangle t;struct circle c;};};

文件读写

对文件读写来说，c语言是可以跨平台的。

// 打开文件，返回struct FILE*的结构对象，r是只读，r+是可读写，w是打开只写文件（一打开文件清空），
//w+是打开可读写文件（一打开文件清空，但是文件不存在也会创建文件），
//a是以追加的方式打开只写文件（文件原来的内容保留），
//a+也是以追加的方式打开只写文件（文件不存在也会建立文件），
//b是二进制读写
f = fopen("bin/readme.txt","rb");
if(f == NULL){printf("文件打开失败");
}// 参考点：SEEK_BEGIN，当前位置 SEEK_CUR 1，文件结尾 SEEK_END 2
fseek(f,0,SEEK_SET);  // 移动到开头
fseek(f,5,SEEK_SET);  // 从开头移动5个位置
fseek(f,-2,SEEK_END); // 从结尾往回移动两个位置
fseek(f,2,SEEK_CUR); // 从现在的位置往后移动两个位置// 计算文件大小
fseek(f,0,SEEK_END);
int file_size = ftell(f);  // 返回文件起始位置到当前位置的字节数，相当于文件字节数char* file_data = malloc(file_size + 1); // 包含结尾符号
int read =  fread(file_data,1,file_size,f);  // 读取文件，返回读取的字节数free(file_data)
if(f){fclose(f); // 关闭文件
}

写文件：

f = fopen("write.txt","wb");// 原有的内容会删除
if(f==NULL){return;
}
char* write_data = "hello world fro";
fwrite(write_data, 1, strlen(write_data),f);fflush(f); // 强制同步到磁盘，一般不用
fclose(f);// stdout是输出文件，printf就是把数据写入这个文件中，这个文件每次程序运行都会创建
// 同理stdin是输入文件
fprintf(stdout,"Helloworld");  // 写入文件中，和打印同理

文件缓存：操作系统有文件缓存区，写文件的时候并不是立刻刷写进磁盘，而是进入缓存区，操作系统达到某些条件或者用户强制才会同步数据到磁盘，可以提高硬盘使用寿命

关键字

static

修饰的变量、函数会变成全局变量，但是只能在当前区域（模块）使用，使得模块内部设计更优雅，减小维护压力。

const

表示修饰的变量或指针指向的数据不会改变，在编译的层面上会检查，如果改变会报错。如果说函数传递进来的参数确定不会被修改，加上const可以减小维护负担。

struct student* const s = &xm;  // 指针不能修改
const struct student* ptr = &xm;  // 指针指向的结构体数据不能修改

typedef

可以用typedef创建新的类型，使用的时候与原来的写法等同，但是要慎用，制造一个新的概念就会增加学习成本。

typedef unsigned char uint8;
typedef struct student student;
typedef struct student *student_ptr;student s; 
uint8 a = 10;
student_ptr s_ptr = &s;// 可以在定义结构体的时候同时typedef创建新的类型
typedef struct _ITEM{int a;int b;int c;}ITEM,*ITEM_PTR;ITEM it;
ITEM_PTR it_p = ⁢

goto

强制跳转到特定的代码位置，强行改变指令指针的位置，不要滥用。

  int sum = 0;int i = 1;
again:sum += i;i++;if(i <= 10)goto again;return sum;

但可以使用让代码更优雅的goto：

// 初始化函数，同时打开四个文件，都成功了才算初始化成功
// 原写法
int test(){FILE* A = fopen("A","rb");if(a == NULL)return -1;FILE* B = fopen("B","rb");if(B == NULL){fclose(A);return -1;}FILE* C = fopen("C","rb");if(C == NULL){fclose(A);fclose(B);return -1;FILE* D = fopen("D","rb");if(D == NULL){fclose(A);fclose(B);fclose(C);return -1;}return 0;
}// 优雅写法
int test2(){FILE *A = NULL，*B = NULL , *C = NULL , *D = NULL;A = fopen("A","rb");if(A == NULL){goto failed;}B = fopen("B","rb");if(B == NULL){goto failed;}C = fopen("C","rb");if(C == NULL){goto failed;}D = fopen("D","rb");if(D == NULL){goto failed;}
failed:if(A){fclose(A);}if(A){fclose(B);}if(A){fclose(C);}if(A){fclose(D);}
｝

动态数组

数组的大小不可改变，为了使得存储更灵活，需要编写动态的数组，动态数组的内存放在堆上，不用在意栈溢出的问题。

vector_array.h

#ifndef __VECTOR_ARRAY_H__
#define __VECTOR_ARRAY_H__// 动态数组的对象结构
struct vector_array {unsigned char* mem_data; // 存放我们数组元素的内存地址,内存是分配在堆上的;int max_elem; // 当前这块内存最大的容量;int elem_count; // 当前这块内存存放的元素个数;int sizeof_elem; // 每个元素所占的内存大小;
};// 定义配置这个动态数组存放哪种类型的元素
void vector_define(struct vector_array* v, int sizeof_elem);
// 清楚掉我们动态数组在堆上为元素分配的内存,动态数组将不会存放任何数据;
void vector_clear(struct vector_array* v);
// 往动态数组最后存放我们的元素
void vector_push_back(struct vector_array* v, const void* elem_ptr);
// 获取第i个元素的内存地址
void* vector_at(struct vector_array* v, int i);
// 获取数组存放的内存的首地址
void* vector_begin(struct vector_array* v);
// 获取数组当前的元素个数
#define vector_size(v) ((v)->elem_count)
// 清理到这个数组里面的所有元素，但是我们还要继续存放(内存还要使用)
void vector_popall(struct vector_array* v);
// 删除我们的数组里面的元素start,开始删除多少个
void vector_erase(struct vector_array* v, int start, int count);
// 弹出数组最后一个元素，
// 并把最后一个元素的值写到我们用户准备好的内存里面
void vector_popback(struct vector_array* v, void* out_of_elem);
#endif

vector_array.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "vector_array.h"
#define my_malloc malloc
#define my_free free
#define my_realloc realloc#define ELEM_STEP 64void vector_define(struct vector_array* v, int sizeof_elem) {memset(v, 0, sizeof(struct vector_array)); // 初始化一下我们动态数组的内存;v->sizeof_elem = sizeof_elem;
}void vector_clear(struct vector_array* v) {if (v->mem_data) {my_free(v->mem_data);v->mem_data = NULL;}v->elem_count = 0;v->max_elem = 0;
}void vector_push_back(struct vector_array* v, const void* elem_ptr) {if (v->elem_count >= v->max_elem) { // 表示这个当前的动态内存里再也不能存放元素了,扩容v->max_elem += ELEM_STEP;v->mem_data = my_realloc(v->mem_data, v->max_elem * v->sizeof_elem);}// 存放元素memcpy(v->mem_data + v->elem_count * v->sizeof_elem, elem_ptr, v->sizeof_elem);v->elem_count ++;
}void* vector_at(struct vector_array* v, int i) {if (i < 0 || i >= v->elem_count) {return NULL;}return (void*)(v->mem_data + i * v->sizeof_elem);
}void* vector_begin(struct vector_array* v) {return v->mem_data;
}void vector_popall(struct vector_array* v) {v->elem_count = 0; // 数组里面的所有的元素清楚了，但是内存还保留
}void vector_erase(struct vector_array* v, int start, int count) {// 判断删除的个数索引要合法if (start < 0 || start >= v->elem_count) {return;}// count合法性的处理if (start + count > v->elem_count) {count -= ((start + count) - v->elem_count);}//if ((v->elem_count - (start + count) > 0)) {memmove(v->mem_data + start * v->sizeof_elem, // 目的地v->mem_data + (start + count) * v->sizeof_elem,(v->elem_count - (start + count)) * v->sizeof_elem); // 开始地址}v->elem_count -= count;
}void vector_popback(struct vector_array* v, void* out_of_elem) {if (v->elem_count <= 0) {return;}v->elem_count --; // 元素的个数 --;if (out_of_elem) {memcpy(out_of_elem, v->mem_data + v->elem_count * v->sizeof_elem, v->sizeof_elem);}
}

使用：

int main(int argc, char** argv) {int b = 4;struct vector_array array; // 定义了这个动态数组;vector_define(&array, sizeof(int)); // 定义这个动态数组，让它存放哪种类型的数据;vector_push_back(&array, &b); // 保存4b = 8;vector_push_back(&array, &b); // 8b = 16;vector_push_back(&array, &b); // 16;// 访问第0个元素int* ptr = NULL;ptr = (int*)vector_at(&array, 0);printf("%d\n", *ptr); // 第0个元素ptr = (int*)vector_at(&array, 1);printf("%d\n", *ptr); // 第0个元素ptr = (int*)vector_at(&array, 2);printf("%d\n", *ptr); // 第0个元素vector_erase(&array, 0, 2);int last;vector_popback(&array, &last);printf("last = %d\n", last);// 遍历数组printf("===================\n");ptr = vector_begin(&array);for (int i = 0; i < vector_size(&array); i++) {printf("%d\n", ptr[i]);}printf("==================\n");// end vector_popall(&array); // 弹出所有的元素，但是不释放内存; vector_clear(&array); // 不再用了以后就全部清除system("pause");return 0;
}

通用链表设计

link_list.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>#include "link_list.h"void list_insert_head(list_head* header, struct link_node* node) {struct link_node** walk = header;node->next = *walk;*walk = node;
}void list_insert_tail(list_head* header, struct link_node* node) {struct link_node** walk = header;while (*walk) {walk = &((*walk)->next);}node->next = NULL;*walk = node;
}void list_remove(list_head* header, struct link_node* node) {struct link_node** walk = header;while (*walk) {if (*walk == node) { // 找到了这个节点*walk = node->next;node->next = NULL;return;}walk = &((*walk)->next);}
}

link_list.h

#ifndef __LINK_LIST_H__
#define __LINK_LIST_H__ // 防止头文件重复包含struct link_node {struct link_node* next; // 指向下一个的指针;
};typedef struct link_node *list_head;// 插入链表头
void list_insert_head(list_head* header, struct link_node* node);// 插入链表尾巴
void list_insert_tail(list_head* header, struct link_node* node);// 遍历链表里面所有的元素
// 基地址 + offset = &((基地址)->成员)
// 当基地址为--> 0, offset = &((NULL)->成员)
#define LINK_TO_ELEM(link_ptr, elem_type, mem_name) \((elem_type*)(((unsigned char*)link_ptr) - (int)(&(((elem_type*)NULL)->mem_name))))// 从链表里面移除一个节点
void list_remove(list_head* header, struct link_node* node);#endif

main.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>#include "link_list.h"#define my_malloc malloc
#define my_free freestruct rect {int x;int y;int w;int h;
};struct circle {int x;int y;int r;
};// 定义一个形状
struct shape {int type;int order;union {struct rect r;struct circle c;};struct link_node link;
};
// end static struct shape* alloc_shape() {struct shape* s = my_malloc(sizeof(struct shape));memset(s, 0, sizeof(struct shape));return s;
}static void free_shape(struct shape* s) {my_free(s);
}int main(int argc, char** argv) {list_head head = NULL; // 他是一个指针struct shape* s = alloc_shape();s->order = 1;list_insert_head(&head, &s->link);s = alloc_shape();s->order = 2;list_insert_head(&head, &s->link);s = alloc_shape();s->order = 3;list_insert_tail(&head, &s->link);list_remove(&head, &s->link);// header 指向了第一个链表头节点的位置;struct link_node* walk = head;while (walk) { // 有节点// 访问这个节点struct shape* elem = LINK_TO_ELEM(walk, struct shape, link);// struct shape* elem = (struct shape*)(((unsigned char*)walk) - (&(((struct shape*)NULL)->link)));printf("elem->order = %d\n", elem->order);// end walk = walk->next;}system("pause");return 0;
}

通用树设计

tree.c:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>#include "tree.h"void
link_parent(struct tree_link* link, struct tree_link* parent) {link->parent = parent;if (parent == NULL) {return;}struct tree_link** walk = &parent->children;while (*walk) {walk = &(*walk)->brother;}*walk = link;
}void
remove_frome_parent(struct tree_link* link) {if (link->parent == NULL) {return;}// 从父亲里面，把这个孩子从孩子列表里面删除struct tree_link** walk = &link->parent->children;while (*walk) {if (*walk == link) {*walk = link->brother;link->brother = NULL;break;}walk = &(*walk)->brother;}// end link->parent = NULL;return;
}

tree.h:

#ifndef __TREE_H__
#define __TREE_H__struct tree_link {struct tree_link* parent; // 指向他的父亲// 用链表的方式来表示孩子struct tree_link* children; // 指向他的孩子列表struct tree_link* brother; // 指向他的下一个兄弟// end // 用动态数组的方式// end 
};// 建立复制管理
void 
link_parent(struct tree_link* link, struct tree_link* parent);#define TLINK_TO_ELEM(link_ptr, elem_type, mem_name) \
((elem_type*)(((unsigned char*)link_ptr) - (int)(&(((elem_type*)NULL)->mem_name))))void
remove_frome_parent(struct tree_link* link);#endif

main.c:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>#include "tree.h"struct item_node {int num;char name[16];struct tree_link link;
};struct item_node*
alloc_item_node(const char* name) {struct item_node* node = malloc(sizeof(struct item_node));memset(node, 0, sizeof(struct item_node));strcpy(node->name, name);return node;
}// 先遍历父亲再遍历孩子,先序遍历
// 先遍历孩子再遍历父亲,后序遍历
void trans_tree(struct tree_link* root) {// 先遍历根节点，然后再遍它的子树// struct item_node* node = TLINK_TO_ELEM(root, struct item_node, link);// printf("%s\n", node->name);// end // 遍历所有孩子的子树struct tree_link* walk = root->children;while (walk) {trans_tree(walk);walk = walk->brother;}// end struct item_node* node = TLINK_TO_ELEM(root, struct item_node, link);printf("%s\n", node->name);}int main(int argc, char** argv) {struct tree_link* tree_root = NULL;struct item_node* root = alloc_item_node("A");tree_root = &root->link;struct item_node* node;struct item_node* B_node;node = alloc_item_node("B");B_node = node;link_parent(&node->link, tree_root);node = alloc_item_node("C");link_parent(&node->link, tree_root);node = alloc_item_node("D");link_parent(&node->link, tree_root);node = alloc_item_node("E");link_parent(&node->link, &B_node->link);node = alloc_item_node("F");link_parent(&node->link, &B_node->link);remove_frome_parent(&node->link);// 遍历这可树trans_tree(tree_root);// end system("pause");return 0;
}

哈希表设计

hash_table.c:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>#define my_malloc malloc
#define my_free free#include "hash_table.h"struct hash_node {char* key;void* value; // void*来表示value;struct hash_node* next; // 串联同一个集合的节点
};struct hash_table {struct hash_node** hash_set; // 每个集合的链表的头指针;int n; // hash_table里面有多少集合
};// n的扩大 n * 4个字节;
struct hash_table* create_hash_table(int n) {struct hash_table* t = my_malloc(sizeof(struct hash_table));memset(t, 0, sizeof(struct hash_table));// n个结合的内存，存放的是链表的头指针t->hash_set = my_malloc(n * sizeof(struct hash_node*));memset(t->hash_set, 0, sizeof(struct hash_node*) * n);t->n = n;return t;
}void destroy_hash_table(struct hash_table* t) {// 删除所有的元素hash_clear(t);// end if (t->hash_set) {my_free(t->hash_set);t->hash_set = NULL;}my_free(t);
}static unsigned int hash_index(char *str)
{register unsigned int h;register unsigned char *p;for (h = 0, p = (unsigned char *)str; *p; p++)h = 31 * h + *p;return h;
}void hash_insert(struct hash_table* t, char*key, void* value) {struct hash_node* node = my_malloc(sizeof(struct hash_node));memset(node, 0, sizeof(struct hash_node));node->key = strdup(key);node->value = value;// 使用hash来返回key,属于哪个集合int index = (hash_index(key) % t->n); // [0, n-1]struct hash_node* header = t->hash_set[index];node->next = header;t->hash_set[index] = node;
}void hash_set(struct hash_table* t, char*key, void* value) {// 使用hash来返回key,属于哪个集合int index = (hash_index(key) % t->n); // [0, n-1]struct hash_node** walk = &(t->hash_set[index]);while (*walk) {if (strcmp((*walk)->key, key) == 0) {(*walk)->value = value;return;}walk = &((*walk)->next);}// 不存在key, valuestruct hash_node* node = my_malloc(sizeof(struct hash_node));memset(node, 0, sizeof(struct hash_node));node->key = strdup(key);node->value = value;*walk = node;// end 
}void* hash_find(struct hash_table* t, char* key) {int index = (hash_index(key) % t->n); // [0, n-1]struct hash_node* walk = (t->hash_set[index]);while (walk) {if (strcmp((walk)->key, key) == 0) {return walk->value;}walk = walk->next;}return NULL;
}// 删除HASH表中的项
void hash_delete(struct hash_table* t, char* key) {int index = (hash_index(key) % t->n); // [0, n-1]struct hash_node** walk = &(t->hash_set[index]);while (*walk) {if (strcmp((*walk)->key, key) == 0) {struct hash_node* rm_node = *walk;*walk = (*walk)->next;rm_node->next = NULL;// key, hash_nodemy_free(rm_node->key);my_free(rm_node);// end }else {walk = &((*walk)->next);}}
}void hash_clear(struct hash_table* t) {for (int i = 0; i < t->n; i++) {struct hash_node* walk = t->hash_set[i];t->hash_set[i] = NULL;while (walk) {struct hash_node* rm_node = walk;walk = walk->next;rm_node->next = NULL;// key, hash_nodemy_free(rm_node->key);my_free(rm_node);// end }}
}

hash_table.h:

#ifndef __HASH_TABLE_H__
#define __HASH_TABLE_H__struct hash_table;// n: 多少个集合;
struct hash_table* create_hash_table(int n);
void destroy_hash_table(struct hash_table* t);
// end // 在HASH表里面查找我们的值
void* hash_find(struct hash_table* t, char* key);
// end // 删除HASH表中的项
void hash_delete(struct hash_table* t, char* key);// 插入一个key: value,不判断是否有重复
void hash_insert(struct hash_table* t, char*key, void* value);// 插入/更改 key: value,
void hash_set(struct hash_table* t, char*key, void* value);// 清理所有的hash 表的数据
void hash_clear(struct hash_table* t);#endif

main.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>#include "hash_table.h"int main(int argc, char** argv) {struct hash_table* t = create_hash_table(1024);hash_insert(t, "xiaoming", (void*)12);hash_insert(t, "xiaohong", (void*)36);hash_insert(t, "xiaoming_address", (void*)"长沙市xxx区");int ret = (int)hash_find(t, "xiaohong");printf("xiaoming: %d\n", ret);char* address = (char*)hash_find(t, "xiaoming_address");printf("xiaoming address: %s\n", address);void* value = hash_find(t, "tttttt");if (value == NULL) {printf("can not find key %s\n", "tttttt");}hash_delete(t, "xiaoming_address");value = hash_find(t, "xiaoming_address");if (value == NULL) {printf("can not find key %s\n", "xiaoming_address");}destroy_hash_table(t);system("pause");return 0;
}

C++

类

C++是基于C语言的面向对象扩展。

类的本质

类声明在哪里，内存就开辟在哪里。类的内存是所有数据成员的和，不包括成员函数。成员函数是全局唯一的函数逻辑（存在代码段中，但是有作用域），通过操作不同的实例完成逻辑。类的实例调用成员函数的时候，会隐式地传递实例的指针（this，这个地址由ecx寄存器保存）给成员函数，这样成员函数就能操作对应的数据。

static和const

static修饰的成员变量需要在内部定义，还要在外部分配空间（在数据段上），会变成不用实例化就能访问的全局变量。
const: 修饰成员函数，这个函数里面不会修改任何实例对象的数据成员,如果修改编译器马上报错。用于减少代码维护者负担。

class homan {int age;int sex;char name[16];public:static int test_var;
private:static int test_pri; public:void test_func() {homan::test_pri = 11;// 如果你是在类的内部，可以省略test_pri = 12; // 坚决反对这样写;}void test_const_func() const {printf("this->age = %d\n", this->age);}void test_const_func2() const;
public:static void test_static();
};// const函数实现在外部，要加上const
void homan::test_const_func2() const {}
// 如果实现在外面，不用加static
void homan::test_static() {printf("test_static\n");
}int homan::test_var; // 分配这个内存在数据段;
int homan::test_pri; int main(int argc, char** argv) {homan::test_var = 10;homan::test_var = 11;// 静态成员函数，就是普通的函数，写入类看起来自然些homan::test_static();system("pause");return 0;
}

c++调c

一般来说c++兼容c的代码。
但如果c++调用c库的函数，需要把c语言的代码用extern “C”｛｝包裹住。但是C语言编译器不能识别这个指令，因此需要根据编译器决定加不加这个代码。

#ifdef __cplusplus
extern "C"｛
#endif// 这里写具体的c代码#ifdef __cplusplus
}
#endif

命名空间

using namespace A;A::point a;  // 没加命名空间
point a;  // 加了直接用

为了避免各个厂商的代码命名重复，一般给自己的代码加上命名空间，添加对应的命名空间后，代码就不会有歧义了。

初始化列表

对象在分配内存之后，执行构造函数之前，会对成员变量进行初始化，这就叫初始化列表。

多态于构造函数

函数名字相同，参数不同，根据传的参数选择函数。 
构造函数是实例化的时候，负责给实例传递变量，构造函数也有多态。

动态内存分配（重要）

C++不能像C一样malloc分配内存，因为这样无法调用构造函数，而是用new的方法，自动分配堆内存和调用构造函数。当想释放这个实例的时候，调用delete函数，这会调用类的析构函数，并把内存还给操作系统。因此new对象的时候就要考虑什么时候delete它的指针才不会内存泄漏（如果释放的是数组，用delete[]）。

C++结构体

C++的结构体是一个类，默认public。并且也可以加构造函数和成员函数。

引用类型

引用其实是是内存和变量的别名。和变量指向同一个内存。传指针和传引用都可以修改值。
注意：如果直接传对象进函数，会在栈上复制一个对象，传应引用的话是传同一块内存的别名不会产生参数复制，比传指针还要高效。

human m;
human& a = m2;  // 存引用，必须要赋值
a.height = 1.7; // 可以直接使用void set_a(int& a){  // 传引用，可以修改原值a = 6;   
}

继承

继承分为私有继承，公有继承，保护继承，默认为私有继承。子类实例化之后，会先调用父类的构造函数，再调用子类的构造函数。析构的时候先调用子类的析构函数，再调用父类的析构函数。

可以允许多重继承，但是要慎用。

调用成员的时候会先从子类本身查找，找不到就从父类找。也可以用对象名->类名::函数名来显式访问。子类实现了和父类一样的函数（包括函数名的参数），叫做重载。

class object {
public:int object_type;
};class cat {
private:int age;
protected:int sex;
public:char name[16];
public:void test_func() {printf("cat::test_func\n");}cat() {printf("cat::cat\n");}~cat() {printf("cat::~cat\n");}
};class bs_cat : public cat, public object{ // 公有继承，如果是私有继承，所有的变量会私有化，只有当前的子类可以访问，子类的子类不可以访问，这里是多重继承int age;
public:void test() {// this->age = 10;// sex--> private: sexthis->sex = 1; this->test_func(); // private}void test_func() {printf("bs_cat::test_func\n");this->cat::test_func(); // 子类重载的方法，调用父类的}bs_cat() {printf("bs_cat\n");}~bs_cat() {printf("~bs_cat\n");}
};

函数指针，虚函数

当函数调用的时候，指令指针会拨动到函数开始的地方，C语言中函数名称就代码这个起始地址。
可以用这个函数的指针直接调用函数。

void test_func() {printf("man test_func\n");
}test_func(3);  // 直接调用
void(*func_ptr) (int a); // func_ptr 存放的是返回值void，参数int的函数指针
func_ptr = test_func;
func_ptr(4);   // 函数指针方式调用// 第二种方便的生命方式（常用）
typedef void(*FUNC_PTR) (int); // 创造了一种名为FUNC_PTR的函数指针类型
FUNC_PRT func_ptr;  // 可以这样声明

虚函数是用virtual修饰的成员函数。每一个类在代码段上有全局唯一的虚函数表，存储虚函数名字和所在地址。由于在内存中是连续的，每一个虚函数在表中会有一个偏移，用偏移可以表示虚函数。
如果类中有虚函数，那么对象会有一个指针指向虚函数表，并且用函数名字就能对应虚函数表的偏移。
虚函数调用是查表的过程，没有普通函数效率高。

子类会把父类的虚函数表拷贝过来，并把自己的虚函数加到后面，如果重载了父类的虚函数，会把原来虚函数表中的地址更新到子类对应的函数地址。

基类指针指向子类实例（重要）

如果用基类指针指向子类实例，只能访问基类拥有的成员和方法，但是如果子类重载了父类的虚函数，由于子类的函数地址覆盖了对应的虚函数表地址，因此调用的是子类的函数。

但是如果父类对应的类不是虚函数，基类指针调用的时候就会直接调用基类函数。
这就是虚函数的作用

纯虚函数

纯虚函数是没有实现的函数，所在的类是抽象类，不能够直接实例化（因为有函数没有实现），用于抽象必须实现的接口

class man{virtual void print_out() = 0;  // 纯虚函数，也叫抽象接口
}

模板

函数模板：代码逻辑一样，数据类型不一样，可以使用模板，也叫做泛型。

模板不能直接编译成机器指令，编译器会根据模板生成指定类型的函数，流程和原来没变，但是代码上大大简化了。

// T是一个模板类,当作普通类型来用
template <class T> // 如果有多个可以<class T1,class T2>
void swap(T* lhs,T* rhs){T temp;temp = *lhs;*lhs = *rhs;*rhs = temp;
}int a = 3;
int b = 4;
swap<int>(&a,&b);
float c = 3.0;
float d = 4.0;
swap<float>(&c,&d);

操作符重载

没有重载操作符的情况下，只能同类型赋值，有重载会走重载函数，要慎用。

class object {
public:int value;// 重载 =函数void operator=(int v) {this->value = v;}// += 重载void operator+=(int v) {this->value += v;}// 比较操作符号bool operator<(object& rhs) {return this->value < rhs.value;}// []int operator[](int i) {return this->value;}// ...
};object obj;
obj = 3; // 重载我们的=来实现;
obj += 3;
printf("value = %d",obj[0]);

std库

STL是C++的标准模板类库（standard template library），标准的C++库函数都在std命名空间中。如果需要使用，那么就加上using namespace std;

string类

string类是一个字符串类，定义在哪里，内存分配到哪里。但是这是一个引用，只存地址，真正的数据在堆上开辟一块内存存储。如果string变量被重新赋值，那么会重新在堆上开辟一块内存存放新额字符串，并把指针指向这个字符串开头。

#include <string>
using namespace std;char* ptr = "helloWorld";
string str = "helloworld!"; // string重载了=str = ptr;   // 可以直接赋值str = str.substr(0,5); // 从零开始取5个字符
int index = str.find("world"); // 返回找到的子串位置，没找到返回-1
str.clear(); // 清理字符串，释放内存
str = "fgh" + "dffg"; // 拼接字符串

动态数组Vector

std::vector<float> v;
v.push_back(3.0f);
v.push_back(4.0f);
v.push_back(5.0f);
v.push_back(6.0f);
v.push_back(5.0f);float a = v.pop_back();
float b = v[1];// 迭代器遍历
std::vector<float>::iterator it; // 元素指针
it = v.end(); // 最后一个元素的下一个元素的位置;
it = v.begin(); // 第一个元素开始的位置;
while (it < v.end()) { // 把所有的vector里面的元素遍历一次printf("%f\n", *it);it ++;
}
for (int i = 0; i < v.size(); i++) {  // 数组方式便利printf("%f\n", v[i]);
}v.eraser(v.begin()+1);  // 删除
v.eraser(v.begin()+1,v.begin()+2);  // 删除一个范围内的元素，不包括结束
v.insert(v.begin()+1, 7.0f);  // 插入v.clear();  // 删除所有

Map

Map是基于红黑树的有序关联容器，和字典不一样，这个是有序的，但查找效率慢一些。

std::map<int, float> mm1;
std::map<std::string, float> mm2;
std::map<int, float>::iterator m_it;mm1[3] = 4.0f; // 加入
mm2["blake"] = 1.68f;
printf("%f, %f\n", mm1[3], mm2["blake"]);mm1.erase(3);
mm2.erase("blake"); // 删除一个keymm1.clear();