《数据结构及其算法》PPT课件

1、数据结构及其算法http:/ 东信息学院6系中国科学技术大学Data Structure and Algorithm第1章 预备知识1.1 程序设计概述1.2 指针与结构体1.3 文件操作1.4 函数与模块化程序设计2021-12-1数据结构及其算法 第1章 预备知识21.1 程序设计概述Hello, World!2021-12-1数据结构及其算法 第1章 预备知识3#include #include using namespace std; int main() printf(Hello,); cout World ! endl;用两种方法求圆周率2021-12-1数据结构及其算法 第1章

2、预备知识4#include #include #include using namespace std; double Gregory() double pi = 0.0; int s = 1, n = 1; while (true) double t = double(s) / n; if (fabs(t) 1e-6) break; pi += t; s = -s; n += 2; return pi * 4;double MonteCarlo() int count = 0, N = 1000000; for (int i = 0; i N; +i) double x = double(r

3、and() / RAND_MAX; double y = double(rand() / RAND_MAX; if (x * x + y * y = 1.0) +count; return double(count) / N * 4;int main() cout Gregory : Gregory() endl; cout Monte Carlo 0: MonteCarlo() endl; cout Monte Carlo 1: MonteCarlo() endl;Gregory : 3.14159Monte Carlo 0: 3.14164Monte Carlo 1: 3.139091.2

4、 指针与结构体指针是什么2021-12-1数据结构及其算法 第1章 预备知识5#define _USE_MATH_DEFINES#include #include 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 %gn, c, i, d); printf(Pointed variables: %c %d %gn, *cp, *ip, *dp); printf(Po

5、inters : %d %d %dn, cp, ip, dp); printf(Added pointers : %d %d %dn, cp + 1, ip + 1, dp + 1);Variables : a 8 3.14159Pointed variables: a 8 3.14159Pointers : 4456167 4456152 4456136Added pointers : 4456168 4456156 4456144Variables : a 8 3.14159Pointed variables: a 8 3.14159Pointers : 5634279 5634264 5

6、634248Added pointers : 5634280 5634268 5634256指针和数组的关系2021-12-1数据结构及其算法 第1章 预备知识6#include #include using namespace std; int max_element(int a10) int m = a0; for (int i = 1; i m) m = ai; return m;int max_element(int *a, int len) int m = a0; for (int i = 1; i m) m = ai; return m;int main() int a10 = 1

7、, 2, 3, 4, 5, 0, 0, 0, 0, 0; int N = 5; int *pa = (int*)malloc(N * sizeof(int); for (int i = 0; i N; +i) pai = i + 1; cout max_element(a) max_element(a, 10) max_element(pa) max_element(pa, N) endl; free(pa);5 5 678710410 5动态内存管理动态内存管理C语言 malloc, free, realloc 只分配或释放内存C+语言 new, delete分配内存并调用构造函数、调用析构

8、函数并释放内存绝不能混用！2021-12-1数据结构及其算法 第1章 预备知识7int *pa = (int*)malloc(N * sizeof(int);for (int i = 0; i N; +i) pai = i + 1;free(pa);int *pa = new intN;for (int i = 0; i a b; cout a b;慎用scanf！ 必须提供正确的指针，且保证存储空间慎用字符串输入！2021-12-1数据结构及其算法 第1章 预备知识91.4 函数与模块化程序设计局部变量与全局变量2021-12-1数据结构及其算法 第1章 预备知识10#include int

9、 count;void func1() int count; for (count = 0; count 10; +count) putchar(.);void func2() int temp = count; func1(); printf(The count is %dn, temp);int main() count = 100; func2();.The count is 100引用参数 C+等语言提供的功能，C语言不支持 引用参数传递的是“地址”而不是“值”，因此引用参数使得对参数“值”的修改可以回传 C语言的“传指针”可实现类似功能，但代码繁琐2021-12-1数据结构及其算法

10、第1章 预备知识11#include 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(%dn, a); chPointer(&a); printf(%dn, a); chRef(a); printf(%dn, a);传值：修改无法回传传指针（特殊的值）传引用：修改可以回传引用参数的用法 实现“多输出” 避免大型数据结构的复制2021-12-1数据结构及其算法 第1章 预备知识

11、12void MaxMin(int *p, int len, int &maxValue, int &minValue) / 输入数组p，其长度为len / 以引用参数返回数组中的最大值和最小值const int N = 10000;struct BigStruct double arrayN;double MaxValue(BigStruct &a) double m = a.array0; for (int i = 1; i m) m = a.arrayi; return m;指针的引用参数2021-12-1数据结构及其算法 第1章 预备知识13#include v

12、oid InitArray(int *&p, int len) if (p) delete p; p = new intlen;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) pi = i; int sum = 0; for (int i = 0; i N; +i) sum += pi; DestoryArray(p); printf(P