July

CPP:STL库 C++泛型编程和STL技术 1.模版 学习模版并不是为了写模版，而是在STL中能够运用系统提供的模版 1.1 函数模版 模版就是建立通用的模具，大大提高复用性 C++中另一种编程思想称为泛型编程，主要利用的技术就是模版 C++中提供两种模版机制：函数模版和类模版 1.1.1 函数模版语法 建立一个通用函数，其函数的返回值类型和形参类型可以不具体指定，用一个虚拟的类型来代表 语法：template关键字声明一个通用数据类型T 1 2 template<typename T> 函数声明或定义 template声明创建模版 typename表明其后面的符号是一种数据类型，可以用class代替 T：通用的数据类型，名称可以替换 1 2 3 4 5 6 template <typename T> void swap(T &a, T &b) { T temp = a; a = b; b = temp; } 自动类型推导：我们在模版中使用通用类型T，当传入具体的数据类型时，根据该数据类型推导出T的类型 ...

CPP面向对象 1. 内存分区模型 代码区：二进制代码 全局区：全局变量和静态变量以及常量 栈区：编译器自动分配释放，存放局部变量 堆区：程序员分配和释放 1.1 程序运行前 ​ 程序编译后，生成了exe可执行程序，未执行该程序前分为两个区域 代码区 存放CPU执行的机器指令 代码区是共享的 代码区是只读的 全局区 全局变量、静态变量(static) 常量区：字符串常量和const修饰的全局变量 该区域的数据在程序结束后由操作系统回收 1.2 程序运行后 栈区：由编译器自动分配释放，存放函数的参数值和局部变量 不要返回局部变量的地址 1 2 3 4 int * func() { int a = 10; // 函数中的局部变量，存放在栈区，栈区的数据在函数执行完后自动释放 return &a; } 局部变量：在函数中定义；全局变量：在函数外定义 在函数中定义的局部变量存放在内存中的栈区，在函数运行结束后编译器自动释放 回想MIPS函数调用规范中的分配栈 堆区：由程序员分配释放 在c++中由new关键字在堆区中申请内存 1 int * p = new int(10); 该局部变量不会随函数结束被回收，即堆区的变量与栈区的变量有不同的生命周期 1.3 new操作符 用new操作符在堆区开辟数据 基本语法：new 数据类型 (初始值)|[元素个数]，返回该数据类型的指针 1 2 3 4 int *p = new int(10); // 创建int型变量 int *arr = new int[10]; // 创建一个数组 [] delete p; delete[] arr; 用delete操作释放内存，释放数组加[] ...

利用malloc分配二维数组 先利用malloc分配出连续的行，再分别对每行分配内存 1 2 3 4 5 int row,col;//二维数组的行数和列数 int** a=(int**)malloc(sizeof(int)*row);//分配出连续的行头 for(int i=0;i<row;i++){ a[i]=(int* )malloc(sizeof(int)*col);//分配每一行的内存 } 注：每一行的内存是连续的，相邻两行的内存不一定连续

用hash解决leetcode01两数之和 题意分析：在一个数组中找到和为target的两个元素，并返回下标数组 1. 做法一：双层暴力循环 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 int *twoSum(int *nums,int numsSize,int target,int *returnSize) { static int ret[10]={0}; for(int i=0;i<numsSize;i++){ for(int j=i+1;j<numsSize;j++){ if(nums[i]+nums[j]==target){ //int* ret=(int *)malloc(sizeof(int)*10); ret[0]=i,ret[1]=j; *returnSize=2; return ret; } } } *returnSize=0; return NULL; } 2. 做法二：hash ​ **利用hash的做法即为涉及到查找，我们设置一个集合，初始状态为空，在遍历原数组的过程中，就在这个集合中查找target-a[i],如果有则停止查找，如果没有则将该元素加入集合** ```c //leetcode支持ut_hash函数库 typedef struct { int key; int value; UT_hash_handle hh;//make this structure hashable }map; map* hashMAP=NULL; void hashMapAdd(int key,int value) { map*s; HASH_FIND_INT(hashMap,&key,s); if(s==NULL){ s=(map*)malloc(sizeof(map)); s->key=key; HASH_ADD_INT(hashMap,key,s); } s->value=value; } map* hashMapFind(int key) { map*s; HASH_FIND_INT(hashMap,&key,s); return s; } void hashMapCleanup() { map*cur,*tmp; HASH_ITER(hh,hashMap,cur,tmp){ HASH_DEL(hashMap,cur); free(cur); } } void hashPrint(){ map*s; for(s=hashMap;s!=NULL;s=(map*)(s->hh.next)) { print("key %d ,value %d\n",s->key,s->value); } } int *twoSum(int *nums,int numsSize,int target,int *returnSize) { int i,*ans; map* hashMapRes; hashMap=NULL; ans=(int*)malloc(sizeof(int)*2); for(i=0;i<numsSize;i++){ hashMapAdd(nums[i],i); } hashPrint();//经典打印检查 for(i=0;i<numsSize;i++){ hashMapRes=hashMapFind(target-nums[i]); if(hashMapRes&&hashMapRes->value!=i){ ans[0]=i; ans[1]=hashMapRes->value; *returnSize=2; return ans; } } hashMapCleanup(); *returnSize=0; return NULL; } ``` ​ 此种做法中涉及到很多使用头文件函数库uthash.h中的用法，当然我们也可以将这些封装好的函数进行手搓，关于函数库uthash.h会在下一篇中介绍 **手搓hash** ```c //每个元素的关键是值和下标 struct node{ int key; int value; struct node*link; }; struct node *hash[10000]={NULL}; //这里的整数值都比较小，可以考虑直接取余法(质数)，但是会处理一些冲突 int HASH(int key) { return key%13; } int *twoSum(int *nums,int numsSize,int target,int *returnSize) { int*a=(int*)malloc(sizeof(int)*2); for(int i=0;i<numsSize;i++){ //以下代码为target>nums[i] if(hash[HASH(target-nums[i])]==NULL){ struct node *p=(struct node*)malloc(sizeof(struct node)); p->key=nums[i];p->value=i;p->link=NULL; hash[HASH(nums[i])]=p; }else{ struct node *q=hash[HASH(target-nums[i])]; while(q!=NULL){ if(q->value!=i)//不同下标 { a[0]=q->value,a[1]=i; *returnSize=2; return a; } q=q->link; } } } *returnSize=0; return NULL; } ``` ​ **但是测试用例中会出现target<nums[i]的情况，即可能出现hash数组下标为负数的情况，以上版本不能通过**

C语言内存分区 5大分区 栈区 向下生长 编译器自动分配释放 存储：局部变量 形参 返回值 堆区 向上生长 程序员调用和分配 malloc free 全局（静态）区 全局变量 静态变量 常量区 字符串 数字 代码区 程序代码 下面来看一段代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 int *twoSum(int *nums,int numsSize,int target,int *returnSize) { int ret[10]={0}; for(int i=0;i<numsSize;i++){ for(int j=i+1;j<numsSize;j++){ if(nums[i]+nums[j]==target){ ret[0]=i,ret[1]=j; *returnSize=2; return ret; } } } *returnSize=0; return NULL; } ​ 这是leetcode第一题 ，函数要求返回存储原数组下标的新数组，出现过错误在于在函数中去建立临时变量数组，再返回数组地址， ...