C++基础知识学习到深入理解及其部分算法学习
一、基础知识
??现在把 北京大学 程序实际与算法一 视频刷了一遍，记录自己不懂的知识，所以知识点记录很零碎。这里使用的运行环境为Code::blocks，因为之前学习C一直常用这个，现在开始起飞。
1.1 用freopen重定向输入
??测试程序时，每次运行程序都要输入测试数据，很麻烦。可以将测试数据存入文件，然后用freopen将输入由键盘重定向为文件，则运行程序时不在需要输入数据了。
??我的学习文件目录在 D:\GraduateLevelFile\Program\C++\Advance . 在文件中建立一个Freopen.txt文件，打开文件输入，
1 2 8 6 7 8 9 9 5
??然后关闭掉，运行下面程序，
#include <iostream>
using namespace std;
int main(){
bool flag = freopen("D:\\GraduateLevelFile\\Program\\C++\\Advance\\Freopen.txt", "r", stdin);
if(flag)printf("Success!\r\n");
else printf("Failure\r\n");
int NumArr, maxNum = 0;
while(cin >> NumArr){
if(NumArr > maxNum) maxNum = NumArr;
}
printf("%d", maxNum);
return 0;
}
??输出结果如下，
参考C++文档，总结如下，
标准声明：FILE *freopen( const char *path, const char *mode, FILE *stream );
参数说明：
path: 文件名，用于存储输入输出的自定义文件名。
mode: 文件打开的模式。和fopen中的模式（如r-只读, w-写）相同。
stream: 一个文件，通常使用标准流文件。
返回值: 成功，则返回一个path所指定文件的指针；失败，返回NULL。
功能: 使用不同的文件或模式重新打开流重用流来打开文件名指定的文件或更改其访问模式。标准流文件具体是指stdin、stdout和stderr。其中stdin是标准输入流，默认为键盘；stdout是标准输出流，默认为屏幕；stderr是标准错误流，一般把屏幕设为默认。
1.2 用筛法求素数
??筛法求素数: 对于小于N的数找出其中素数，把2到n中所有的数都列出来，然后从2开始，先划掉n内所有2的倍数，然后每次从下一个剩下的数(必然为素数)开始，划掉其n内的所有倍数。最后剩下的数，就都是素数。
??思路: 1. 设置一个标志数组 isPrime，isPreme[i] 的值是 1 就表示 i 是素数。开始数组元素值全部为 1；2. 划掉 k 的倍数，就是把 isPrime[2k], isPrime[3k] … 置为 0 ； 3. 最后检查 isPrime 数组，输出 isPrime[i] 为 1 的那些 i 。
??程序如下，
#include <iostream>
using namespace std;
#define MAX_NUM 10000
char isPrime[MAX_NUM];
int main(){
// 初始化数组，全部置为 1
for(int i = 2; i <= MAX_NUM; i++){
isPrime[i] = 1;
}
// 用筛法求素数
for(int i = 2; i <= MAX_NUM; i++){
if(isPrime[i]){
// 每次剩下的数的下一个必为素数
for(int j = 2*i; j <= MAX_NUM; j += i){
isPrime[j] = 0;
}
}
}
// 输出素数
for(int i = 2; i <= MAX_NUM; i++){
if(isPrime[i]){
cout << i << " ";
}
}
return 0;
}
??结果如下，
1.3 递归学习（初步）
1.3.1 阶乘
??递归就是一个函数自己调用自己。举一个简单的例子，求一个整数的阶乘，程序如下，
#include <iostream>
using namespace std;
int Factorial(int n){
if(n < 2)return 1;
else return n*Factorial(n-1);
}
int main(){
int result, n = 10;
result = Factorial(n);
cout << "Result is " << result << endl;
}
1.3.2 求斐波那契数列
??求斐波那契数列第n项，程序如下，
#include <iostream>
using namespace std;
int Fib(int n){
if(n == 1 || n == 2)return 1;
else return Fib(n-1) + Fib(n-2);
}
int main(){
int result, n = 10;
result = Fib(n);
cout << "Result is " << result << endl;
}
1.4 字符串学习
1.4.1 字符串基础知识
??在C++对字符串操作需要加入头文件 #include <cstring> , 举一个使用例子情况，
#include <iostream>
#include <cstring>
using namespace std;
int main(){
// '\0'标志着字符串的结束.
char title[] = "Prison Break"; // 最后一个元素是 '\0'
char hero[100] = "Michael Scofield";
char prisonName[100];
char response[100];
cout << "What's the name of the prison in " << title << endl;
cin >> prisonName;
if(strcmp(prisonName, "Fox-River") == 0)
cout << "Yeah! Do you love " << hero << endl;
else{
strcpy(response, "It seems you haven't watched it!\n");
cout << response;
title[0] = 't';
title[3] = 0;
cout << title << endl;
}
}
??结果如下，
??用 scanf 也可以将字符串读入字符数组，scanf会自动添加结尾的’\0’，scanf 读入空格为止。为了防止数组越界的问题，有一个读入一行到字符数组，使用cin防止数组越界
cin.getline(char buf[], int bufSize);
??也是读入一行到字符数组，读入一行，自动添加’\0‘，可能导致数组越界！
char s[10];
while(gets(s)){
printf("%s\n", s);
}
1.4.2 字符串库函数
??在C++对字符串操作需要加入头文件 #include <cstring> , 字符串函数都根据’\0’来判断字符串结尾。其中字符串处理函数定义如下
字符串拷贝：
strcpy(char[] dest, char[] src); // 拷贝scr到dest
字符串比较大小：
int strcmp(char[] s1, char[] s2); // 返回0则相等
求字符串长度：
int strlen(char[] s);
字符串拼接：
strcat(char[] s1, char[] s2); // s2拼接到s1后面
字符串转成大写：
strupr(char[]);
字符串转成小写：
strlwr(char[]);
??实际应用例子，
#include <iostream>
#include <cstring>
using namespace std;
int main(){
char s1[30]; char s2[40]; char s3[100];
int result;
strcpy(s1, "Hello");
strcpy(s2, s1);
cout << "1)" << s2 << endl;
strcat(s2, ", world");
cout << "2)" << s1 << endl;
result = strcmp("abc", s2);
cout << "3)" << result << endl;
result = strcmp("abc", "aaa");
cout << "4)" << result << endl;
int n = strlen(s2);
cout << "5) string length is " << n << endl;
strupr(s1);
cout << "6)" << s1 << endl;
strlwr(s1);
cout << "7)" << s1 << endl;
return 0;
}
??输出结果为，
1.5 指针概念和用法
1.5.1 指针
??不同类型的指针，如果不经过强制类型转换，不能直接互相赋值。指针运算示例，
#include <iostream>
#include <cstring>
using namespace std;
int main(){
int *p1, *p2; int n = 4;
char *pc1, *pc2;
p1 = (int*) 100;
p2 = (int*) 200;
// 输出 1) 25,因为(200-100)/sizeof(int) = 100/25 = 4
cout << "1)" << p2 - p1 << endl;
pc1 = (char*) p1;
pc2 = (char*) p2;
// 输出 2) -100,因为(100-200)/sizeof(char) = -100
cout << "2)" << pc1 - pc2 << endl;
// 输出 3) 29,因为(200 + 4*sizeof(int) - 100)/sizeof(int) = 29
cout << "3)" << (p2 + n) - p1 << endl;
int *p3 = p2 + n; // p2 + n 是一个 int 类型指针，然后赋值给 p3
// 输出 4) 29,因为(200 + 4*sizeof(int) - 100)/sizeof(int) = 29
cout << "4)" << p3 - p1 << endl;
// 输出 5) 90,因为(200 - 10*sizeof(char) - 100)/sizeof(char) = 90
cout << "5)" << (pc2 - 10) - pc1 << endl;
return 0;
}
??结果如下，
??地址0不能访问。指向地址0的指针就是空指针，用”NULL“作为关键字对任何类型指针进行赋值，实际上就是整数0。如果指针值为NULL，相当于假，不为NULL相当于真。
1.5.2 指针和一维数组
??数组的名字是一个指针变量指向数组的起始地址，数组作为函数形参时，下面定义方法是等价的，
数组作为函数形参时，T *p 和 T p[] 是等价的。比如
void Func(int *p){cout << sizeof(p);}
<==>
void Func(int p[]){cout << sizeof(p);}
??举一个实际的例子，
#include <iostream>
#include <cstring>
using namespace std;
int main(){
// 初始化数组，指针定义和指向
int a[200]; int *p;
p = a; // p 指针指向数组首部
*p = 10; // 相当于 a[0] = 10
*(p + 1) = 20; // 相当于 a[1] = 20
cout << "1) " << a[0] << " " << p[0] << "," \
<< a[1] << " " << p[1] << endl;
// p[i] 和 *(p + i) 是等效的，使得
// a[0] = 30; a[4] = 40.
p[0] = 30;
p[4] = 40;
cout << "2) " << *p << " " << *(p + 4) << endl;
// 对数组前10个元素进行赋值
for(int i = 0; i < 10; i++){
*(p + i) = i;
}
cout << "3) " << p[0] << endl; // 输出 1
++p; // p指向 a[1]
cout << "4) " << p[0] << endl; // 输出 1
p = a + 6; // 指针重新定向
cout << "5) " << *p << endl; // 输出 6
return 0;
}
1.5.3 指针和二维数组
??定义一个二维数组，
举一个例子，
int array[3][5];
array[i](i是一个整数)是一个一维数组，是一个行向量
array[i]的类型是 int*
sizeof(array[i]]) = sizeof(int) * 5;
array[i]指向的地址：数组a的起始地址 + i*5*sizeof(int)
??举个例子，
1.5.4 指向指针的指针
??定义一个指针的指针，
int **pointer;
// p是指向指针的指针，p 指向的地方应该存放着一个类型为 int* 的指针
// 其中 *pointer 的类型是 int*
??举个例子，
#include <iostream>
#include <cstring>
using namespace std;
int main(){
int **doublePointer; //指向 int* 类型指针
int *pointer; //
int num = 1234;
pointer = # // p 指向 n
doublePointer = &pointer;
// 使用 doublePointer 读取值
cout << doublePointer << " " \
<< *doublePointer << " " \
<< *(*doublePointer) << endl;
// 使用 pointer 读取值
cout << &pointer << " " \
<< pointer << " " \
<< *pointer << endl;
return 0;
}
??结果如下，
1.5.4 指针与字符串
??字符串常量类型是 char*， 字符串数组名也是 char*。举个例子，
#include <iostream>
#include <cstring>
using namespace std;
int main(){
// char *p 相当于 char p[];
char *p = "Please input your name: \n";
cout << p;
char Name[20];
cin >> Name;
cout << "Your name is " << Name << endl;
return 0;
}
??其中char *p 相当于 char p[], 结果如下，
可以看出输出不完全，其实是数组越界了。
1.5.5 字符串操作库函数
??其中库函数cstring中对字符串操作函数如下，
1) char *strchr(const char *str, char c);
寻找字符 c 在字符串 str 第一次出现的位置。如果找到，返回指向该位置的 char* 指针; 如果 str 中不包含字符 c , 则返回 NULL;
2) char *strstr(const char *str, const char *subStr);
寻找子串 subStr 在字符串 str 第一次出现的位置。如果找到，返回指向该位置的 char* 指针; 如果 str 中不包含子串 ，则返回 NULL;
3) int stricmp(const char *s1, const char *s2);
大小写无关的字符串比较。如果s1小于s2返回负数；如果s1等于s2，则返回0；如果s1大于s2，则返回正数。不同编译器可能结果不同。
4) int strncmp(const char *s1, const char *s2, n)
比较 s1 前 n 个字符组成的字串和 s2 前 n 个字符组成的字串大小。若长度不足 n ，则取整个串作为字串。返回值和 strcmp 类似。
5) char *strncpy(char *dest, const char *src, int n);
拷贝src的前 n 个字符到 dest。如果 src 长度大于或者等于 n，该函数不会往 dest 写入 '\0';若 src 长度不足 n ，则拷贝 src 的全部内容以及结尾的 '\0' 到 dest。
6) char *strtok(char *str, const char *delim);
连续调用该函数若干次，可以做到：从 str 中逐个抽取出被字符串 delim 中的字符分隔开的若干字串。
7) int atoi(char *s);
将字符串 s 里的内容转换成一个整型数返回。如果字符串 s 的内容是”1234“，返回值就为 1234；如果字符串不是一个整数，那么返回0.
8) double atof(char *s);
将字符串s中的内容转换为实数返回。
9) char *itoa(int value, char *string, int radix);
将整型值value以radix进制表示法写入string。
??接下来为这些函数调用的示例，
#include <iostream>
#include <cstring>
using namespace std;
int main(){
char s1[20] = "12345";
char s2[20] = "abcdefg";
char s3[20] = "ABCDE";
strncat(s1, s2, 3); // s2 字符串前 3 个拷贝到 s1
cout << "1)" << s1 << endl;
strncpy(s1, s3, 3); // s3 前 3 个字符串拷贝到 s1
cout << "2)" << s1 << endl;
strncpy(s2, s3, 6); // s3 前 6 个字符串拷贝到 s2
cout << "3)" << s2 << endl; // 因为把'\0'也拷贝过来了
// 比较 s1 和 s3 前 3 个字符
cout << "4)" << strncmp(s1, s3, 3) << endl;\
// 在字符串中寻找'B'字符，返回指针
char *p = strchr(s1, 'B'); // s1 = "ABC45abc"
if(p){
cout << "5)" << p - s1 << "," << *p << endl;
}else{
cout << "5) Not Found" << endl;
}
// 在 s1 中查找字符串"45a", s1 = "ABC45abc"
p = strstr(s1, "45a");
if(p){
// 输出为 3, 45abc
cout << "6)" << p - s1 << "," << p << endl;
}else{
cout << "6) Not Found" << endl;
}
// strtok使用方法
cout << "strtok usage demo:" << endl;
char str[] = "- This, a sample string, OK.";
// 下面要从 str 逐个抽取出，被" ,.-"这几个字符分隔
p = strtok(str, " ,.-"); // " ,.-"中第一个字符为空格
while(p != NULL){
cout << p << endl;
// 后续调用，第一个参数必须是NULL
p = strtok(NULL, " ,.-");
}
return 0;
}
??输出结果为，
1.5.6 void指针和内存操作函数
??void *p, 可以用任何类型的指针对 void 指针进行赋值和初始化，那么 *p 是没有定义，那么 ++p，–p，p-n 等也是没有定义的。
??在头文件中cstring声明了memset：
// 将从 dest 开始的 n 个字节，都设置为 ch 。返回值是 dest。
void *memset(void *dest, int ch, int n);
char arr[200] = "";
memset(arr, 'a', 10);
cout << arr << endl; // 输出为 aaaaaaaaaa
int arrInt[200] = "";
memset(a, 0, sizeof(a)); // 那么数组 a 中的每个元素都是 0 .
??在头文件中cstring声明了memcpy(注意拷贝的是字节)：
#include <iostream>
#include <cstring>
using namespace std;
void *memcpy1(void *dest, void *src, int n){
char *pDest = (char *)dest; //指针类型强制转换
char *pSrc = (char *)src;
for(int i = 0; i < n; i++){
*(pDest + i) = *(pSrc + i);
}
return dest;
}
int main(){
return 0;
}
1.6 函数指针和结构体指针
1.6.1 函数指针
??程序运行期间，每个函数都会占用一段连续的内存空间。而函数名就是该函数所占内存区域的起始地址（也称“入口地址”）。我们可以将函数的入口地址赋给一个指针变量，使该指针指向该函数。然后通过指针变量就可以调用这个函数。这样指向函数的指针变量称为“函数指针”。
??举个例子，
int (*pFunc)(int, char);
// 表示 pFunc 是一个函数指针，它指向的函数，返回值为 int 类型，该函数有
// 两个参数，第一个为 int 类型的，第二个为 char 类型的。
// 举一个实际例子
#include <iostream>
#include <cstring>
using namespace std;
void printMin(int num1, int num2){
if(num1 > num2)cout << num2;
else cout << num1;
}
int main(){
void (*pFunc)(int, int);
int num1 = 4, num2 = 5;
pFunc = printMin;
pFunc(num1, num2); // 输出为 4
return 0;
}
??对于函数指针的必要性，举个例子，在 C 语言快速排序库函数如下，
// 输入参数：base 起始地址，nelem 数组元素大小，width 每个元素大小(可以计算出每个元素的地址,以字节为单位)，元素谁在前谁在后的规则(自己编写的比较函数)
void qsort(void *base, int nelem, unsigned int width, \
int(* pfCompare)(const void *, const void *));
// 能够对任意类型数据进行快速排序。
??实例：下面程序功能是调用 qsort 库函数，将一个 unsigned int 数组按照个位数从小到大进行排序。比如 8，23，15 三个数，按照个位数排序应该是 23，15，8。那么程序为，
#include <iostream>
#include <cstring>
using namespace std;
#define NUM 5
int comparaWay(const void *elem1, const void *elem2){
unsigned int *p1, *p2;
p1 = (unsigned int *)elem1;
p2 = (unsigned int *)elem2;
return (*p1 % 10) - (*p2 % 10);
}
int main(){
unsigned int arr[NUM] = {8, 123, 11, 10, 4};
qsort(arr, NUM, sizeof(unsigned int), comparaWay);
for(int i = 0; i < NUM; i++){
cout << arr[i] << endl;
}
return 0;
}
??结果如下，
1.6.2 结构体指针
??比如定义一个结构体
#include <iostream>
#include <cstring>
using namespace std;
typedef struct student{
string name;
char label[10];
int ID;
float Score;
student *position; // 定义一个指向自己的指针
}stu;
int main(){
stu *pStudent;
stu stu1;
pStudent = &stu1;
stu stu2 = *pStudent;
// 访问指针成员变量的方法
pStudent -> ID = 12345;
(*pStudent).name = "Jack";
(*pStudent).ID = 12345;
// 这样访问改变会出错，错误原因
// 相当于定义了一个字符常量数组，不可以更改，除非用指针方式
// error: incompatible types in assignment of `const char[2]' to `char[10]'|
(*pStudent).label = "come on"; // 会出错
return 0;
};
1.7 全局变量和局部变量
1.7.1 定义和使用
??全局变量都是静态变量。局部变量定义时如果前面加了“static”关键字，该变量也成为静态变量。静态变量的存放地址，在整个程序运行期间，都是固定不变的。如果未明确初始化，静态变量会自动初始化成全 0 .
??局部变量地址每次函数调用时都可能不同，在函数的一次执行期间不变，并且局部变量未初始化的只是随机的。
??使用静态变量对库函数 strtok 的实现，
#include <iostream>
#include <cstring>
using namespace std;
// 根据字符对字符串进行分段
#include <iostream>
#include <cstring>
using namespace std;
// 根据分隔符 sep 对字符串 p 进行分段
// 一定注意从 static 角度理解整个程序，分为多段进行分隔
char *strtokl(char *p, char *sep){
static char * start; // 本次查找字串的起点
if(p) start = p;
// 跳过分隔符
// strchr 匹配成功返回指针，不成功返回 NULL
for( ; *start && strchr(sep, *start); ++start);
if(*start == 0)return NULL;
char *q = start;
// 跳过非分隔符，到第一个非分隔符结束
for( ; *start && !strchr(sep, *start); ++start);
// 并且，在后面加一个'/0'。遇到 '/0'，相当于字符串结束
if(*start){
*start = 0;
++ start;
}
return q;
}
int main(){
char str[] = "- This, a sample string, OK.";
// 下面要从 str 逐个抽取出被 " ,.-" 这几个字符分隔的字串
char *p = strtokl(str, " ,.-");
// 最后 p 指向了 NULL
while(p != NULL){
cout << p << endl;
// 因为 static 的原因，所以从 NULL开始
p = strtokl(NULL, " ,.-");
}
return 0;
}
??结果如下，
1.7.2 变量的作用域和生存期
??在单文件的程序中，结构，函数和全局变量的作用域是其定义所在的整个文件。同名标识符的作用域可能被另外一个包含。则在小的作用域里，作用域大的那个标识符被屏蔽，不起作用。
??变量的生存期指的是在此期间变量占有的内存空间，其占有的内存空间只能归它使用，不会被用来存在别的东西。全局变量的生存期，从程序被装入内存开始，到整个程序结束。静态局部变量的生存期，从定义它语句第一次执行开始到函数结束为止。
二、程序算法设计
??现在基本对 C++ 和 C 重叠的部分给看完并进行相应的理解。现在开始学习一些简单的算法。
2.1 简单排序算法
??排序的顺序这里全部以从小到大的排序方式。
2.1.1 选择排序
??选择排序法是一种不稳定的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。在排序过程中，如果找到比起始元素小的会交换两个数据的位置。程序如下，
#include <iostream>
#include <cstring>
using namespace std;
#include <iostream>
#include <cstring>
using namespace std;
void selectSort(int arr[], int lenArr){
for(int i = 0; i < lenArr; i++){
// 找到最小数据的索引
int tempMin = i;
for(int j = i+1; j < lenArr; j++){
if(arr[j] < arr[tempMin]){
tempMin = j;
}
}
int temp = arr[i];
arr[i] = arr[tempMin];
arr[tempMin] = temp;
for(int i = 0; i < 5; i++){
cout << arr[i] << " ";
}
cout << endl;
}
}
int main(){
int arr[5] = {5, 1 ,8 ,9 ,7};
for(int i = 0; i < 5; i++){
cout << arr[i] << " ";
}
cout << endl;
cout << "start--------" << endl;
selectSort(arr, 5);
cout << "----------end" << endl;
for(int i = 0; i < 5; i++){
cout << arr[i] << " ";
}
}
??结果如下，
2.1.2 插入排序
??插入排序：对于少量元素的排序，它是一个有效的算法 。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增 1 的有序表。可以理解做把无序列列表中每个元素插入有序列表中。程序如下，
#include <iostream>
#include <cstring>
using namespace std;
void insertionSort(int arr[], int lenArr){
for(int i = 1; i < lenArr; i++){
// arr[i]是最左的无序元素，每次循环将 a[i] 放到合适位置
for(int j = 0; j < i; j++){
// 把arr[i]放到位置j, 原下标j到j-1的元素都往后移一个位子
if(arr[j] > arr[i]){
int temp = arr[i];
// 从 j+1 依次移到 k位置;
for(int k = i; k > j; k--){
arr[k] = arr[k-1];
}
arr[j] = temp;
break;
}
}
for(int i = 0; i < 5; i++){
cout << arr[i] << " ";
}
cout << endl;
}
}
int main(){
int arr[5] = {5, 1 ,8 ,9 ,7};
for(int i = 0; i < 5; i++){
cout << arr[i] << " ";
}
cout << endl;
cout << "start--------" << endl;
insertionSort(arr, 5);
cout << "----------end" << endl;
for(int i = 0; i < 5; i++){
cout << arr[i] << " ";
}
}
??结果如下，
2.1.3 冒泡排序
??冒泡排序：由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。程序如下，
#include <iostream>
#include <cstring>
using namespace std;
void bubbleSort(int arr[], int lenArr){
for(int i = lenArr - 1; i > 0; i--){
for(int j = 0; j <= i; j++){
// 大的数通过数的交换往上浮
if(arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
for(int i = 0; i < lenArr; i++){
cout << arr[i] << " ";
}
cout << endl;
}
}
int main(){
int arr[8] = {5, 4, 1, 3, 8, 2, 9, 7};
for(int i = 0; i < 8; i++){
cout << arr[i] << " ";
}
cout << endl;
cout << "start-----------" << endl;
bubbleSort(arr, 8);
cout << "-------------end" << endl;
for(int i = 0; i < 8; i++){
cout << arr[i] << " ";
}
}
??得到的结果如下，
2.1.4 简单排序的总结
??插入排序，冒泡排序，选择排序，它们需要做 n 2 n^2 n2的量级比较。好的排序算法如快速排序，归并排序等等，只需要做 n ? l o g 2 n n*log_2n n?log2?n量级比较。
2.2 程序和算法时间复杂度
??一个程序或算法的时间效率，成为时间复杂度，简称复杂度。复杂度常用大写字母 O 和字母 n 来表示，n 表示问题的规模。计算复杂度问题时，只用统计执行次数最多的那种固定操作次数。对快速排序为 n ? l o g ( n ) n*log(n) n?log(n)的复杂度，二分查找为 l o g ( n ) log(n) log(n)。
2.1.1 二分查找
??对于一个有序的数组，找其中存在的一个数是否存在，返回下标，使用二分查找，算法为，
#include <iostream>
#include <cstring>
using namespace std;
int binarySearch(int arr[], int num, int lenArr){
int Left = 0, Right = lenArr - 1;
for( ;Left <= Right; ){
int mid = Left + (Right - Left) / 2; // 防止溢出
if(num > arr[mid])Left = mid + 1;
else if(num < arr[mid]) Right = mid - 1;
else return mid;
}
return -1;
}
int main(){
int arr[10] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int findNum = 11;
int result = binarySearch(arr, findNum, 10); // 结果为 5
if(result == -1)cout << "Find failure!" << endl;
else cout << "Index is " << result << endl;
return 0;
}
??结果为 5。接着用二分法求根，有一个方程 f ( x ) = x 3 ? 5 x 2 + 10 x ? 80 = 0 f(x)=x^3-5x^2+10x-80=0 f(x)=x3?5x2+10x?80=0,若求出根为 a ，要求 ∣ f ( a ) ∣ < = 1 0 ? 6 |f(a)| <= 10^{-6} ∣f(a)∣<=10?6，并且这个函数是单调递增的，划定区间在 [0, 100] 之间求根。程序如下，
#include <iostream>
#include <cstring>
using namespace std;
double EPS = 1e-6;
double f(double x){return x*x*x - 5*x*x + 10*x - 80;}
int main(){
double x1 = 0, x2 = 100;
while(root < EPS){
root = x1 + (x2 - x1)/2;
y = f(root);
if(y > 0)x2 = root;
else x1 = root;
}
printf(".8f\n", root);
return 0;
}
三、总结
??课程一结束，其中 STL 部分暂时用不到吧，用到再学。课程二，三慢慢学习。现在打算改变计划，先扣两个JAVA项目，然后学习一些主要算法，网络，操作系统等知识。