http://staff.ustc.edu. cn/~dongeliu/dsa.html 刘 东 信息学院6系 中国科学技术大学 Data Structure and Algorithm 《数据结构及其算法》 http://staff.ustc.edu. cn/~dongeliu/dsa.html 刘 东 信息学院6系 中国科学技术大学

第1章 预备知识 1.1 程序设计概述 1.2 指针与结构体 1.3 文件操作 1.4 函数与模块化程序设计 2018/11/202018/11/20 数据结构及其算法 第1章 预备知识

1.1 程序设计概述 Hello, World! #include <stdio.h> #include <iostream> using namespace std;   int main() { printf("Hello"); cout << ' ' << "World" << "!" << endl; } 2018/11/202018/11/20 数据结构及其算法 第1章 预备知识

用两种方法求π #include <math.h> double x = double(rand()) / RAND_MAX; #include <stdlib.h> #include <iostream> double y = double(rand()) / RAND_MAX; using namespace std;   if (x * x + y * y <= 1.0) ++count; double Gregory() { double pi = 0.0; int s = 1, n = 1; return double(count) / N * 4; while (true) { double t = double(s) / n; int main() { if (fabs(t) < 1e-6) break; cout << "Gregory : " << Gregory() << endl; pi += t; s = -s; n += 2; srand(0); } cout << "Monte Carlo 0: " << MonteCarlo() << endl; return pi * 4; srand(1); double MonteCarlo() { cout << "Monte Carlo 1: " << MonteCarlo() << endl; int count = 0, N = 1000000; for (int i = 0; i < N; ++i) { Gregory’s series原理是用arctan x做泰勒展开 Gregory : 3.14159 Monte Carlo 0: 3.14164 Monte Carlo 1: 3.13909 2018/11/202018/11/20 数据结构及其算法 第1章 预备知识

1.2 指针与结构体 指针是什么 #define _USE_MATH_DEFINES #include <math.h> #include <stdio.h>   int main() { char c = 'a'; int i = int(8.1); double d(M_PI); char *cp = &c; int *ip = &i; double *dp(&d); printf("Variables : %c %d %g\n", c, i, d); printf("Pointed variables: %c %d %g\n", *cp, *ip, *dp); printf("Pointers : %d %d %d\n", cp, ip, dp); printf("Added pointers : %d %d %d\n", cp + 1, ip + 1, dp + 1); } Variables : a 8 3.14159 Pointed variables: a 8 3.14159 Pointers : 4456167 4456152 4456136 Added pointers : 4456168 4456156 4456144 Variables : a 8 3.14159 Pointed variables: a 8 3.14159 Pointers : 5634279 5634264 5634248 Added pointers : 5634280 5634268 5634256 2018/11/202018/11/20 数据结构及其算法 第1章 预备知识

指针和数组的关系 5 5 678710410 5 #include <stdlib.h> int main() { #include <iostream> int a[10] = {1, 2, 3, 4, 5, 0, 0, 0, 0, 0}; using namespace std;   int N = 5; int max_element(int a[10]) { int *pa = (int*)malloc(N * sizeof(int)); int m = a[0]; for (int i = 1; i < 10; ++i) for (int i = 0; i < N; ++i) pa[i] = i + 1; if (a[i] > m) m = a[i]; return m; cout << max_element(a) << ' ' << max_element(a, 10) << ' ' << max_element(pa) << ' ' << max_element(pa, N) << endl; } int max_element(int *a, int len) { for (int i = 1; i < len; ++i) free(pa); 2018/11/202018/11/20 数据结构及其算法 第1章 预备知识

动态内存管理 C语言 C++语言 绝不能混用！ malloc, free, realloc 只分配或释放内存 new, delete 分配内存并调用构造函数、调用析构函数并释放内存 绝不能混用！ int *pa = (int*)malloc(N * sizeof(int)); for (int i = 0; i < N; ++i) pa[i] = i + 1; free(pa); int *pa = new int[N]; for (int i = 0; i < N; ++i) pa[i] = i + 1; delete []pa; 2018/11/202018/11/20 数据结构及其算法 第1章 预备知识

指向指针的指针 #include <stdlib.h> >pointpointer.exe #include <iostream> using namespace std;   void ErrorMsg(const char* msg) { cerr << msg << endl; exit(EXIT_FAILURE); } int main(int argc, char **argv) { if (argc < 4) ErrorMsg("Argument error!"); int rows = atoi(argv[1]); int cols = atoi(argv[2]); int **a = new int*[rows]; for (int r = 0; r < rows; ++r) a[r] = new int[cols]; for (int r = 0; r < rows; ++r) for (int c = 0; c < cols; ++c) a[r][c] = r + c; cout << a[r][c] << (c == cols - 1 ? '\n' : ' '); cout << argv[3] << endl; for (int r = 0; r < rows; ++r) delete []a[r]; delete []a; >pointpointer.exe Argument error! >pointpointer.exe 5 3 done 0 1 2 1 2 3 2 3 4 3 4 5 4 5 6 done 2018/11/202018/11/20 数据结构及其算法 第1章 预备知识

结构体及其指针 #include <stdio.h> { "Sun", 20, 1995, 10, 12 },   { "Li", 17, 1998, 1, 5 } }; typedef int Age; for (int i = 0; i < 4; ++i) { typedef Age* pAge; students[i].nextStudent = (i == 0 ? NULL : (i == 1 ? students + 2 : (i == 2 ? students : students + 1))); typedef char Name[20]; typedef struct { int year, month, day; } Date; } typedef struct Student { pStudent ps = &students[3]; Name name; while (ps) { Age age; pAge pa = &(ps->age); Date birthday; printf("%s %d (%d-%d-%d)\n", ps->name, *pa, ps->birthday.year, ps->birthday.month, ps->birthday.day); Student* nextStudent; } *pStudent, StudentArray[4]; int main() { ps = ps->nextStudent; StudentArray students = { { "Zhao", 19, 1996, 5, 23 }, { "Qian", 18, 1997, 7, 19 }, Li 17 (1998-1-5) Qian 18 (1997-7-19) Sun 20 (1995-10-12) Zhao 19 (1996-5-23) 2018/11/202018/11/20 数据结构及其算法 第1章 预备知识

1.3 文件操作 标准输入输出 Input two integers: 3 4 Input operator: Input error! int main() { int a, b, res; char c; printf("Input two integers: "); scanf("%d %d", &a, &b); printf("Input operator: "); c = getchar(); switch (c) { case '+': res = a + b; break; case '-': res = a - b; break; default: ErrorMsg("Input error!"); } printf("Result: %d\n", res); 此处加入 getchar(); 或者 fflush(stdin); Input two integers: 3 4 Input operator: + Result: 7 2018/11/202018/11/20 数据结构及其算法 第1章 预备知识

标准输入输出 C语言 C++语言 慎用scanf！ 慎用字符串输入！ scanf, printf scanf("%d %d", &a, &b); printf("%d %d", a, b); C++语言 cin, cout cin >> a >> b; cout << a << ' ' << b; 慎用scanf！ 必须提供正确的指针，且保证存储空间 慎用字符串输入！ 2018/11/202018/11/20 数据结构及其算法 第1章 预备知识

1.4 函数与模块化程序设计 局部变量与全局变量 #include <stdio.h> int count;   int count; void func1() { for (count = 0; count < 10; ++count) putchar('.'); } void func2() { int temp = count; func1(); printf("The count is %d\n", temp); int main() { count = 100; func2(); ..........The count is 100 2018/11/202018/11/20 数据结构及其算法 第1章 预备知识

引用参数 C++等语言提供的功能，C语言不支持 引用参数传递的是“地址”而不是“值”，因此引用参数使得 对参数“值”的修改可以回传 #include <stdio.h>   void chValue (int i) { i = 3; } void chPointer(int *i) { *i = 5; } void chRef (int &i) { i = 7; } int main() { int a = 1; chValue(a); printf("%d\n", a); chPointer(&a); printf("%d\n", a); chRef(a); printf("%d\n", a); } 传值： 修改无法回传 传引用： 修改可以回传 传指针（特殊的值） 2018/11/202018/11/20 数据结构及其算法 第1章 预备知识

引用参数的用法 实现“多输出” 避免大型结构体的复制 void MaxMin(int *p, int len, int &maxValue, int &minValue) { // 输入数组p，其长度为len // 以引用参数返回数组中的最大值和最小值 } const int N = 10000; struct BigStruct { double array[N]; }; double MaxValue(BigStruct &a) { double m = a.array[0]; for (int i = 1; i < N; ++i) if (a.array[i] > m) m = a.array[i]; return m; } 这个例子如果不用引用参数，运行100000次的时间需要9.073秒；用了以后需要3.262秒 2018/11/202018/11/20 数据结构及其算法 第1章 预备知识

指针的引用参数 #include <stdio.h> void InitArray(int *&p, int len) {   void InitArray(int *&p, int len) { if (p) delete []p; p = new int[len]; } void DestoryArray(int *&p) { delete []p; p = NULL; int main() { int *p = NULL; int N = 100; InitArray(p, N); printf("Pointer: %d ", p); for (int i = 0; i < N; ++i) p[i] = i; int sum = 0; for (int i = 0; i < N; ++i) sum += p[i]; DestoryArray(p); printf("Pointer: %d Sum: %d\n", p, sum); Pointer: 6849840 Pointer: 0 Sum: 4950 2018/11/202018/11/20 数据结构及其算法 第1章 预备知识

模块化编译和链接 module.cpp arith.h #include <stdio.h> #include "arith.h"   int main() { int a = 3, b = 5; printf("%d %d %g\n", add(a, b), minus(a, b), pi); ComplexNumber ca = { 2, 3 }, cb = { 3, -5 }; print(add(ca, cb)); } module.cpp extern const double pi;   struct ComplexNumber { double real, imag; }; int add(int, int); int minus(int, int); ComplexNumber add(ComplexNumber, ComplexNumber); void print(ComplexNumber); arith.h 2018/11/202018/11/20 数据结构及其算法 第1章 预备知识

arith.cpp #include <stdio.h> #include "arith.h"   const double pi = 3.1415926; int add(int a, int b) { return a + b; } int minus(int a, int b) { return a - b; } ComplexNumber add(ComplexNumber a, ComplexNumber b) { ComplexNumber res; res.real = a.real + b.real; res.imag = a.imag + b.imag; return res; } void print(ComplexNumber c) { printf("%g%+gi\n", c.real, c.imag); arith.cpp 2018/11/202018/11/20 数据结构及其算法 第1章 预备知识

本章复习提纲 C/C++语言的主要特性 结构体 指针 引用参数 动态内存管理 输入输出 2018/11/202018/11/20 数据结构及其算法 第1章 预备知识

作业 1.2, 1.4 1.2 程序改错 1.4 数组算法 2018/11/202018/11/20 数据结构及其算法 第1章 预备知识