c++程序设计梳理（谭浩强）5-6章

 今天看到了TIOBE编程语言社区排行榜9月的数据，从第一到第四分别是：c、java、objective-c、c++。其中java和c++同比都下降了几个百分点！objective-c似乎乘着swift的高风，一路狂飙！在前十的名单中swift也疯狂的杀了进来，势头之猛，不可小觑！自我感觉还是那个观点：基础不好，上层一切都是浮云！java的JVM是c++开发的；objective-c底层是c；swift又是objective-c构建出来的……一切的本源其实都离不开c与c++，甚至是汇编！加速、扎实的补好基础，才是王道！
 今天来总结梳理，在面向过程当中最为重要的两章：数组与指针。可以这么说吧，这两个东西在c与c++的语言中，是灵魂没有之一！难度与重要性不言而喻。java的最初开发者就是一名c++程序员，因为被c++的繁琐的指针与类与类多重继承二义性等一系列的东西所烦恼，故一怒之下开发了java（大牛啊！）。在速度与激情的当今，效率、内存、算法等等一系列的计算机关键词环绕于我们身边，在此种情况下，我们更要加强在加强对指针的掌握，才能在技术领域处于不败之地。
Chapter5~chapter6
->数组
1、数组定义的过程中，例如：a[n]，其中[]中的变量n必须是常变量，例如：const int n=5，否则非法。或者我们可以动态的申请数组空间，但是动态申请是在堆上申请，例如：int *a = new int[n]，在此种情况下，n可以为变量。

#include<iostream>
using namespace std;
int main(){
	int n;
	cin >> n;
	int *a = new int[n];
	for (int *p = a, i = 0; i < n; i++){
		*(p + i) = i;
	}
	for (int *p = a, i = 0; i < n; i++){
		cout << *(p + i) << endl;
	}
	return 0;
}

2、这种情况：int a[3]={1,2}，将前两个数组位赋值成1和2，后面一个位置，默认初始化，值为0；char类型的数组，默认初始化为'\0'。
3、经典的冒泡排序！（必须手到擒来，信手拈来。否则还学什么计算机！！） 

/*
冒泡排序
*/
#include<iostream>
using namespace std;
void bubble(int a[],int n){
	if (n == 0)
		return;
	else{
		for (int i = 0; i < n; i++){
			for (int j = 0; j < n -1 - i; j++){//自己感觉在这边界的问题上有点小纠结下！
				if (a[j]>a[j + 1]){
					int t = a[j + 1];
					a[j + 1] = a[j];
					a[j] = t;
				}
			}
		}
	}
}

int main(){
	int a[] = { 4, 2, 5, 1, 6, 2, 6 };
	bubble(a, sizeof(a) / sizeof(int));
	for (int i = 0; i < sizeof(a) / sizeof(int); i++){
		cout << a[i] << " ";
	}
	cout << endl;
	return 0;
}

4、二维数组表达的几种方式，其中包含了默认值的问题：
（1）int a[2][3]={{2,3,4},{5,6,7}};
（2）int a[][3]={3,4,5,6,4,43,3}（第二维度数值不能省略）
（3）int a[2][3]={{},{34,45}}
5、数组作为函数的参数的时候，例如：void function(int a[])，其中传进来的实参，是一种值传递，但是只是将数组元素的首元素的地址传递给了形参而已。所以在函数内部接收到的数组并不能运用于一些STL中对数组操作的函数，例如bigin()与end()等（这个似乎是c++11新添加进来的函数）。
6、二维数组用成函数参数的时候，一维的数值可以省略，二维的数值必须要给出，而且要和实参的一样！
7、字符串数组的一个自己测试的问题：
char a[5] = { '1', '2', '3', '4','\0' };
这种情况下，如果最后的'\0'字符换成其他的字符，不空缺，那样我用cout<<a来输出，编译器会将a当成字符串来处理，而没有结束符，会多输出一些随机的字符在后面，所以在实际的使用过程当中，我们会人为的将这种形式的字符数组，在最后加上一个'\0'。
8、原c语言中，对于字符数组的几种操作函数：（包含在#include<cstring>中）
strcat(char[],const char[])：字符串连接函数
strcpy(char[],const char[])：字符串复制函数，第一个数组空间必须要大于第二个字符串的大小+1，否则报错
strcmp(const char[],const char[])：字符串比较函数
strlen(const char[])：求字符串的长度函数
9、c++中关键的字符串处理类型：（string类）
任何语言，对于字符串处理都是非常关键的。以前的c用的是字符数组来处理，并不是那么的方便与安全。在c++的领域，我们看到了string类型的诞生，是非常让人欣慰的！（装逼了~哈哈！）总结了下，有如下的几种改进。
（1）定义字符串变量可以直接用等于号，例如：string str = "jicheng"；
（2）字符串常量是以'\0'结尾的，编译器会自动加上。当把字符串常量赋给string类型的变量的时候，并不包括最后的那个'\0'。
（3）string类型的变量，可以直接使用复制运算，例如：string str = "jicheng"，也可以直接使用各种关系运算符，例如：==、>、>=、<、<=、!=等，这些都在string类里面进行了运算符的重载！比操作字符数组要方便多了。
10、习题1：
用筛选法求n以内的素数。（这个筛选法我在网上查了下，看到了几种优化的算法实现。在以前的那种求素数的算法中是看原数能不能被2到sqrt(n)之间的数整除，如果能就不是素数，时间复杂度为O(n*sqrt(n))，相对来说数量级是比较大的。筛选法就是为了处理较大的n而出现的）

/*
筛选法的素数求法。我在网上查了下，发现如下的一种高效算法，主要思想就是：我只判断奇数是不是素数，因为偶数肯定不是素数（2除外），所以我们申请一个布尔数组来对应相应的奇数，例如布尔数组下标为0，对应奇数是3，下标为1，对应奇数是5，对应公式为：num=i*2+3，在如下的应对关系下，将每个布尔数组都赋值为true。从第一个开始，如果后面的值是true的就是素数，筛选掉的基本方法就是，每个下标对应的数的倍数，例如3是第一个数组下标1对应的数，3+3=6就不是素数，要筛选掉，可是6本身是偶数不在我们所考虑的对应关系内，故继续查找；不难看出，3+3+3=9也要筛选掉，并且它是奇数，使我们要考虑的对应关系，所以通过9来求得具体的布尔下标（(num-3)/2），将此下标对应的布尔值设为false。就是这样。最后输出时，遍历布尔数组，如果是true的，输出i*2+3,即可！
*/
#include<iostream>
#include<cmath>
using namespace std;

int main(){
	int n;
	cout << "请输入您要筛选的n!" << endl;
	cin >> n;
	int size = (n % 2 == 0) ? (n / 2) : (n / 2 + 1);//此处的作用是获得我要申请与之对应的布尔数组的大小，因为要对应的是奇数，所以当输入是偶数是直接就是原数的一半，如果是奇数的话，还要加一
	bool *bl = new bool[size - 1];//我们要将1去除，直接从3开始，所以申请的对应布尔数组要size-1
	for (int i = 0; i < size - 1; i++){
		bl[i] = true;
	}
	for (int i = 0; (i*2+3)<=sqrt(n); i++){
		if (!bl[i]) continue;
		int j = i*(2 * i + 6) + 3;//网上的高效算法核心，就是当筛选到一个数的时候，我们可以得到第一个之前没有筛选掉的那个数，就用这个公式求得这个数的下标，我还是不是很能理解这个公式的推算过程。
		while (j < size - 1){
			bl[j] = false;
			int num=j*2+3+i*2+3;//此处是获得下一个数
			while (num % 2 == 0) {//当下一个数是偶数的时候，因为我们假设的bl对应的是从3开始的奇数，所以当碰到偶数的时候我们要跳过
				num = num + i * 2 + 3;//再加一次开始的那个素数，直到获得的是奇数才结束。
			}
			j = (num - 3) / 2;//此时求得下一个要筛选的下标
		}
	}
	cout << 2 << endl;
	for (int i = 0; i < size - 1; i++){
		if (bl[i]){
			cout << (i*2+3) << endl;
		}
	}
	return 0;
}

11、习题6：
打印杨辉三角前十行。

/*
打印杨辉三角（10行）。这个锻炼的是二维数组的基础能力
*/
#include<iostream>
#include<cmath>
using namespace std;

int main(){
	int a[10][10];
	for (int i = 0; i < 10; i++){
		for (int j = 0; j < 10; j++){
			if (j == 0 || i == j)
				a[i][j] = 1;
			else if (j>i)
				a[i][j] = 0;
			else
				a[i][j] = a[i - 1][j] + a[i-1][j - 1];
		}
	}
	for (int i = 0; i < 10; i++){
		for (int j = 0; j < 10; j++){
			if (a[i][j]!=0)
				cout << a[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}

12、习题11：

打印图案（用string方法，这个能用上标准输出格式化的函数！）

/*
标准输出格式化控制
*/
#include<iostream>
#include<iomanip>
#include<string>
using namespace std;
int main(){
	string str = "* * * * * *";
	for (int i = 0; i < 5; i++){
		cout << setw(str.size() + i) << setiosflags(ios::right) << str << endl;
	}
	return 0;
}

->指针
1、指针的自我多年体会：
指针，指了个针，指TM个针，这东西让人又爱又恨啊。恨在他的复杂多变易出错，爱在他的灵活可控变化多。自从研究生入了java的门之后，发现很多时候，还是怀念当初的c与c++的日子。虽然抓耳挠腮，但是，过后的领悟与收获，是远远大过我们去灵活使用一个框架的。指针，其实就是地址，就是原存储数据的地址，当然这个地址也可以存在另外一个区域，所以就有地址的地址的这一表现形式，例如：int *p = 4,其中p就是数据4的地址，*p就是指向了数据4的存储空间；int **p = 4，这个就是地址的地址，其中p是地址，*p指向了*p的地址，**p指向了4的存储空间。编译器将地址设置为一个整型，就是一个地址占4字节的存储空间，例如上面的p。
2、“调用函数时不会改变实参指针变量的值，但可以改变实参指针变量所指向变量的值”，这句话的理解就是那种值传递的问题。因为我传进来的是指针，例如：function(*p)，其中p的值是地址，所以我们在函数内部是进行了一个副本拷贝的，编译器自己默认完成，拷贝的的就是p的地址，在此我们假设为_p，其中*_p和*p一样，都指向了实参原指向的数据空间，所以我们在函数内部去改变指向的数据空间的值，就是改变原实参的指向的数据空间的值；可是我们去改变指针变量的值，例如：p=&a，这样其实是改变的_p这个副本的值，并没有改变原p变量的值，所以有了上面那句话。
3、指针的各种模式：
（1）int *p;//普通的指针变量
（2）int a[n];//数组变量，其中a指向数组第一个元素的地址
（3）int *p[n];//这个是数组指针，数组中大小为n，每个元素都指向了一个整型数据
（4）int (*p)[n];//这个是指向数组的指针，p指向了一个包含有n个整型数据的数组
（5）int f();//普通函数声明
（6）int *p();//返回值是一个指向整型数据的指针的函数
（7）int (*p)();//这个很关键，是指向函数的指针，调用模式可以是：p()
（8）int **p;//指针的指针，这个可以表现为二维数组形式，例如：*(*(p+3)+9)对应于a[3][9]
p.s：这里补充下函数指针：（函数指针用处主要在于一种通用性的方面，例如类似的功能，每个功能的参数和返回类型是一样的，函数名不一样，我们就可以用一个函数指针，分别指向不同的函数进行调用。）

/*
函数指针基础示例
*/
#include<iostream>
using namespace std;
int max(int a, int b){
	return a > b ? a : b;
}
int main(){
	int a, b,re;
	cin >> a >> b;
	int (*p)(int, int);//定义函数指针，模式是：函数类型 (*指针变量名)(函数形参表)
	p = max;//将函数指针初始化，其中函数原函数名就是函数的入口地址
	re = p(a, b);//函数调用可以直接运用函数指针来调用
	cout << re << endl;
	return 0;
}

4、强大的引用的引入（c++很给力的地方之一！）：
例如：int &a = b，引用就是变量的别名，所用的存储空间完全一样，上面的a与b所用的地址完全一样，只不过将b变量再起另外一个名字罢了！引用使用的时候要注意的是，在引用声明的时候必须初始化，作为函数的形参又不一样。这里我多说一句，一用用的是&符号，很容易和取地址操作混淆，取地址也是这个符号，具体是什么操作要根据具体的上下文才能分得清，但是当年单纯的我就是认为引用就是取地址，导致只要看到&就各种在那抠，看看到底是什么地址，熟知从一开始的认知就有错了，后面简直寸步难行！希望引以为戒，在将来的学习中，必定要搞清楚搞准确基础的概念，防止事倍功半！下面我就完整的写出c++中两种函数传递的基础模型代码，这两种传递分别是：值传递与地址传递。

/*
两种地址传递模型：值传递与地址传递；其中其实指针的传递就是值传递，在函数内部要进行拷贝复制，只不过和单纯传递变量不同的是，指针传递，传递的是地址罢了。真正的地址传递要用c++的引用，内部传进来的变量地址和外面实参的变量地址是完全一样的！下面我分别写出这两个函数。*/
#include<iostream>
using namespace std;
void swap(int *a, int *b){//指针的值传递
	cout << "a的地址是："<<&a << endl;
	if (a == NULL || b == NULL)
		return;
	else{
		int p = *a;
		*a = *b;
		*b = p;
	}
}
void swap(int &a, int &b){//引用的地址传递
	cout << "a的地址是：" << &a << endl;
	int p = a;
	a = b;
	b = p;
}
int main(){
	int a = 4, b = 8;
	cout << "交换前：" << a <<","<< b << endl;
	cout << "a的地址是：" << &a << endl;
	swap(a, b);
	cout <<"交换后："<< a <<","<< b << endl;
	return 0;
}

5、习题10：
讲一个5*5的矩阵中的最小的四个数按照左上、右上、左下、右下的顺序存放，中间存放最大的数字。

/*
习题10
*/
#include<iostream>
using namespace std;
void swap(int &a, int &b){
	int t = a;
	a = b;
	b = t;
}
void function(int (*a)[5], int r, int c){
	int (*p)[5] = a;
	for (int i = 0; i < r; i++){
		for (int j = 0; j < c; j++){
			if (p[i][j] < p[0][0]){
				swap(p[i][j], p[0][0]);
			}
			else if (p[i][j] < p[0][c - 1]){
				swap(p[i][j], p[0][c - 1]);
			}
			else if (p[i][j]<p[r-1][0]){
				swap(p[i][j], p[r - 1][0]);
			}
			else if(p[i][j]<p[r-1][c-1]){
				swap(p[i][j], p[r - 1][c - 1]);
			}
			if (p[i][j]>a[2][2]){
				swap(p[i][j], a[2][2]);
			}
		}
	}
}

int main(){
	int a[5][5] = { {3,4,5,5,6}, {3,6,3,1,6}, {0,8,7,5,3}, {3,5,6,7,8}, {1,2,3,4,6} };
	cout << "交换前：" << endl;
	for (int i = 0; i < 5; i++){
		for (int j = 0; j < 5; j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
	function(a, (sizeof(a) / sizeof(a[0])), (sizeof(a[0]) / sizeof(int)));//此处一定要注意传参的问题，因为a[][]这种形式是在栈上申请的空间，所以a代表的是(*a)[5]的地址，和**a所代表的地址并不一样！
	cout << "交换后：" << endl;
	for (int i = 0; i < 5; i++){
		for (int j = 0; j < 5; j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}

6、习题17：
写strcmp代码。

/*
习题17：据说是微软的源码
*/
#include<iostream>
using namespace std;
int strcmp(char *c1, char *c2){
	int ret = 0;
	while (!(ret = *(unsigned char *)c1 - *(unsigned char *)c2) && *c2)//这里是核心，因为在c++中，非零的数值进行逻辑判断的时候都当成的true的布尔值来处理，就是无论当前两个字符相减是正数还是负数，判断结果都是真，故继续循环，直到结果为0的时候。
	{
		++c1;
		++c2;
	}
	if (ret < 0)
		ret = -1;
	else if (ret > 0)
		ret = 1;
	return(ret);
}
int main(){
	cout << strcmp("ji","ji")<< endl;
	return 0;
}