【1】Chapte1 课程简介及C++重点知识回顾[1].ppt

1、1,2020/12/10,数据结构与算法,2011年秋季,授课教师：张剑波 授课班级：111101-2班,2,2020/12/10,Chapter1 课程简介,3,课程总体介绍,课程教学内容 课程重要性 前导知识和技能 教材 参考资料 课程实习安排 成绩评定 学习要求,4,一、课程教学内容,Programs ：为计算机处理问题编制一组指令集；,Algorithms ：处理问题的策略；,Data Structures ：问题的数学模型。（数据+关系）,Niklaus Wirth提出： AlgorithmsData StructuresPrograms,5,用计算机解决一个具体问题时，大致需要以下

2、步骤：,从具体问题抽象出一个适当的数学模型； 设计一个解决此数学模型的算法； 编写出程序，进行测试、调整直至得到最终解答。,数值计算的程序设计问题,“鸡兔同笼”问题,全球天气预报, 二元一次方程组, 环流模式方程,今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何？,课程教学内容（一）数据结构,6,例1.1 学生学籍登记表。,非数值计算的程序设计问题,（线性表结构）,特点？,7,例1.2 酒店管理系统中的客房分配问题,例1.3 铺设煤气管道,(a) 居民区示意图,(b) 铺设煤气管道设计图,（队列结构）,（图结构及图的最小生成树）,8,例1.4 计算机和人对弈的问题,（树结构）,【数据结构

3、】研究非数值计算的程序设计问题中计算机的操作对象以及它们之间关系和操作等的学科。,9,课程教学内容（二）常用算法设计方法,10,常用算法求解问题示例-百钱百鸡,【问题描述】公鸡3元每只，母鸡5元每只，小鸡1元3只，一百元钱买一百只鸡。请求出公鸡，母鸡和小鸡的数目。,【解】假设公鸡数为x，母鸡数为y，小鸡数是z，则： 3*x+5*y+z/3=100 且 x+y+z=100 x：020 y：033,穷举法,11,常用算法求解问题示例-迷宫问题,【思考】怎样走出迷宫？,12,计算机怎样求解迷宫？,计算机解迷宫时，通常用的是“穷举求解”的方法： 从入口出发，顺某一方向向前探索，若能走通，则继续往前走；

4、 否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。 如果所有可能的通路都试探过，还是不能走到终点，那就说明该迷宫不存在从起点到终点的通道。,回溯法,13,解答：需找零：100-17=83元， 找零：1张50元，1张20元，1张10元，1张2元，1张1元,在找零钱时，为使找回的零钱的张数最少， 从最大面值的币种开始，按递减的顺序考虑各币种， 先尽量用大面值的币种， 当不足大面值币种的金额时才去考虑下一种较小面值的币种。,【问题描述】在超市购物时，用100元购买了17元的物品，怎样找零？（以人民币1元，2元，5元，10元，20元，50元，100元为例）,贪婪算法,常用算法求解

5、问题示例-找零问题,14,常用算法求解问题示例-背包问题,【问题描述】有一个贼在偷窃一家商店时发现有N件物品；第i件物品值pi元，重wi磅（1iN），且都是整数。他希望带走的东西越值钱越好，但他的背包中最多能装下M磅的东西（整数）。,贪婪算法,动态规划法,15,二、课程重要性,综合性专业基础课 涉及数学、软件和硬件 专业化编程的基础：程序设计的实质是对确定的问题选择一种好的数据结构，设计一种好的算法 后续大量专业课的基础：操作系统、数据库、编译原理、计算机图形学 计算机科学与工程的基础 相关考试的核心课程 计算机软件资格水平考试 计算机考研统考课程之一（占45分）,16,三、前导知识和技能,面

6、向对象编程思想 C+程序设计语言 Visual C+编程环境,17,四、教 材,Data Structures, Algorithms, and Applications in C+ (1st edition) by Sartaj Sahni ， McGraw-Hill Co.,教学资源：,18,教材中译本,汪诗林，孙晓东 等译 机械工业出版社， 2006 年7月,19,教材组织,三个部分 I 1-2章, 背景知识 II 3-12章, Data Structures III 13-17章, 算法设计方法 每章包含： 概念 + 应用,20,五、参考资料,数据结构（C语言版） 严蔚敏 吴伟民编著

7、清华大学出版社,21,参考资料,数据结构（用面向对象方法与C+描述） 殷人昆 等编著 清华大学出版社,22,参考资料,数据结构与算法 张铭 等编著 高等教育出版社,23,参考资料,Introduction to Algorithms （算法导论） Thomas H.Cormen Charles E.Leiserson Ronald L.Rivest， Clifford Stein “五个一”： 一章介绍一个算法； 一种设计技术； 一个应用领域； 一个相关话题。,24,参考资料,Effective C+ by Scott Meyers, Addison-Wesley “改善程序技术与设计思维的5

8、0个有效做法” 中文版：侯捷 译 电子工业出版社,25,六、实习安排,实习时间：4学时6次， 周3：周五晚上 周5-7-9-11-13，周四下午 实习地点：信息楼302 实习工具：Visual Studio2005 OR 2010 实习教材：数据结构与算法实习指导。,26,实习内容,【实习一】 线性表的应用 法雷序列；大数阶乘 【实习二】栈和队列的应用 表达式求值：简单计算器 【实习三】 树及二叉树 二叉树的创建及遍历 【实习四】 搜索树 BST树；优先队列 【实习五】图 图的遍历 【实习六】算法设计方法应用 校园导游图,27,七、成绩评定,平时成绩（考勤+作业） 10% 上机实习 30% 期

9、末闭卷笔试 60%,28,八、学习要求,课前预习，课后复习 准备一个练习本，认真完成书面作业 认真完成上机实习 不拘于课堂讲授，广泛阅读，勤于思考 多实践，多交流 【知识拓展】查阅资料了解经典数据结构及算法在相关领域的应用,29,九、课件及作业的公共邮箱,课件 E-mail： Password：software2011 其他文件夹：数据结构与算法课件,研究生助教邮箱： 周斯波：zhou_ 张帅：zhangshuai_,30,记住自己的总结与体会,算法思想很重要 设计很重要 交流很重要 编码规范很重要 细心很重要 调试很重要 测试很重要,31,8、如果不是天才的话，想学编程就不要想玩游戏你以为你

10、做到了，其实你的C+水平并没有和你通关的能力一起变高其实可以时刻记住：学C+是为了编游戏的。,18、学习编程最好的方法之一就是阅读源代码。,21、看得懂的书，请仔细看；看不懂的书，请硬着头皮看。,学习C+和编程的50条忠告（节选）,32,22、别指望看第一遍书就能记住和掌握什么请看第二遍、第三遍。 31、学习编程的秘诀是：编程，编程，再编程。 37、经常回顾自己以前写过的程序，并尝试重写，把自己学到的新知识运用进去。 44、决不要因为程序“很小”就不遵循某些你不熟练的规则好习惯是培养出来的，而不是一次记住的。 46、记录下在和别人交流时发现的自己忽视或不理解的知识点。 48、保存好你写过的所有

11、的程序那是你最好的积累之一。,学习C+和编程的50条忠告（节选）,33,参考资料电子版,算法导论.pdf 数据结构与算法-面向对象的C+设计模式.pdf,C+Primer（中文第三版）.pdf EffectiveC+.chm More Effective C+.doc C+沉思录.pdf,34,【课后编程作业】string类模拟,模拟C+标准库中的string容器，实现自定义的String类，支持下列程序： int main( ) String s1,s2,s3,s4(“abcdef”); cins1s2; s3=s1+s2; couts2) couts1is more lager than

12、s2endl; /输出s4在s3中位置 couts3.find(s4); return 0; ,35,【提示】,1、完成String类的构造函数、拷贝构造函数、析构函数、操作符重载（+、=、） 、length函数、find函数； 2、字符串的大小比较： 例如：abc与bc；abcd与abcde 3、find函数（字符串的模式匹配算法） Brute-Force算法 KMP算法 4、9月7日前发至课件邮箱 邮件名称：11110X-XX姓名-【作业一】String类模拟,36,C+回顾重点,模板类 引用与指针（ int n = 0; Func1(n); coutn = nendl;,void Fun

13、c2(int ,void Func3(int *p) (*p) = (*p) + 10; int n=0; Func3(,（1）值传递：由于Func1函数体内的x是实参n的一份拷贝，x值的改变不会影响n的变化，所以n仍为0。,（2）引用传递：由于Func1函数体内的x是实参n的引用，x值的改变影响n的变化，所以n为10。,（3）指针传递：由于Func1函数体内的p是指向实参n的指针，p指向的内存的值改变影响n的变化，所以n为10。,39,传值参数（value parameter） 实际参数（actual parameter）的值在函数执行之前被复制给形式参数（formal parameter）

14、； 复制过程是由该形式参数所属数据类型的复制构造函数（copy constructor）完成的。 函数结束时，形式参数所属数据类型的析构函数（destructor）负责释放该形式参数。 当函数返回时，形式参数的值不会被复制到对应的实际参数中函数调用不会修改实际参数的值。 传值参数会增加程序的运行开销。,例如：int ABC(int a, int b, int c) 调用：z=ABC(2, 3, 4),40,引用参数（reference parameter） 传送实际参数的地址，避免大块数据的复制。 可以将变化了的值传送到调用环境。 减少函数调用时，复制构造函数的调用。 减少函数返回时，析构函数

15、的调用。,例如：int ABC(int int main( ) int val(5); int ,10 10 10,42,引用在函数中使用需要注意,用做函数的参数或函数的返回值； 函数不能返回对局部对象的引用。,返回引用的函数，只能用全局变量或静态变量作为返回值，而不能用该函数的局部变量，因为局部变量在该函数体外自动消失。,int ,43,ANSI C+对引用的限制,不能对引用变量取地址： 指针变量可定义成二级，即指向指针的指针：char *p; 然而不能对引用取地址，用” /毫无意义,44,常量引用,函数不得修改常量引用参数。 例如：设置/获取当前地图范围： short SetMapRect

16、(const RECT 这是C+推荐的参数定义风格！,45,Q3：实例比较,typedef struct double xmin; double ymin; double xmax; double ymax; D_RECT; #define MIN_DOUBLE_DIST 0.00000001f,评估效果: 将第二个参数改为 D_RECT rc2 const D_RECT rc2 const D_RECT *rc2 const D_RECT,template class Smemory public:void mput(T x);,49,template 类模板名 :成员函数名（形参表） 成员

17、函数的函数体 ,在类模板的外部定义类成员函数的一般形式是：,例如： template void Smemory:mput(T x),50,类模板实例化,类模板是一个类家族的抽象，它只是对类的描述，编译程序不为类模板（包括成员函数定义）创建程序代码，但是通过对类模板的实例化可以生成一个具体的类以及该具体类的对象。 与函数模板不同的是：函数模板的实例化是由编译程序在处理函数调用时自动完成的，而类模板的实例化必须由程序员在程序中显式地指定。,其实例化的一般形式是： 类名 对象名例如，Smemory mol；,51,Q5: 递归函数,递归函数（recursive function）：自己调用自己的函数

18、。 直接递归（direct recursion） 间接递归（indirect recursion）,函数A,调用,函数A,调用,函数B,调用,52,递归是程序设计中一种强有力的工具：,（1）有许多数学函数是递归的,例如：阶乘函数,例如：2阶Fibonacci数列,Fact(n)=,1， 若n=0,nFact(n-1)， 若n0,Fib(n)=,1， 若n=1,Fib(n-1)+Fib(n-2)，其它情形,0， 若n=0,53,（2）有的数据结构，如二叉树、树、广义表等由于本身固有的递归特性，则它们的操作可递归地描述；,（3）有一类问题，虽然问题的本身没有明显的递归结构，但用递归求解比迭代求解更

19、简单，如八皇后、Hanoi塔、迷宫等问题。,递归算法的基本要素：,（1）问题具有某种可借用类同自身的子问题描述的性质； （2）相对于问题来说，子问题将更简化； （3）某一有限步的子问题有直接的解存在（即有递归出口）,54,递归函数示例,求解阶乘函数的递归算法 long Factorial ( long n ) if ( n = 0 ) return 1; 基本部分 else return n * Factorial (n-1); 递归部分 ,阶乘函数,55,递归原理,每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。 每层递归调用需分配的空间形成递归工作记录，按后进先出的栈

20、组织。,局部变量 返回地址 参 数,活动记录框架,递归 工作记录,56,课后练习,看书理解： Page7：例1-3，排列算法 编码完成： Page9：练习5，子集算法,57,Q6：异常处理,异常（exception）是程序可能检测到的，运行时不正常的情况，如存储空间耗尽、数组越界、被0除等等。 当发生运行时错误时，不能简单地结束程序运行，而是退回到任务的起点，指出错误，并由用户决定下一步工作。 面向对象的异常处理（exception handling）机制是C+语言用以解决这个问题的有力工具。,58,异常处理结构,异常的识别和发出 try划定异常识别的代码段 throw抛出异常 异常的处理 c

21、atch处理指定类别的异常,float *x=NULL; /set_new_handler(NULL); try x = new float 100000000; catch (std:bad_alloc) / 仅当new 失败时才会进入 cout Out of Memory endl; return 1; if(x) memset(x,0, 100000000); /看看是否是有效的内存 delete x; ,59,C+标准库的异常类,C+标准库中的异常层次的根类被称为exception，定义在库的头文件中。,C+标准库提供的逻辑异常： invalid_argument异常，接收到一个无效的

22、实参，抛出该异常。 out_of_range异常，收到一个不在预期范围中的实参，则抛出。 length_error异常，报告企图产生“长度值超出最大允许值”的对象。 domain_error异常，用以报告域错误（domain error）。,C+标准库提供的运行时异常： range_error异常，报告内部计算中的范围错误。 overflow_error异常，报告算术溢出错误。 underflow_error异常，报告算术下溢错误。 bad_alloc异常。当new( )操作符不能分配所要求的存储区时，会抛出该异常。它是由基类exception派生的。,60,#include using na

23、mespace std; templateclass Stack T* v; int max_size; int top; public: class stack_error public: virtual void error(void) = 0; ; class Underflow: public stack_error / public: void error(void) cerr stack Underflow endl; ; class Overflow: public stack_error / public: void error(void) cerr stack Overflo

24、w endl; ; Stack(int s): max_size(s), top(0) v = new Tmax_size; / construct function. determine the size Stack() void push(T c) if(top = max_size) throw Overflow(); vtop+ = c; T pop() if(top = 0) throw Underflow(); return v-top; ;,void f() Stack ss(0); try ss.push(Quiz); string s = ss.pop(); ss.pop()

25、; catch(Stack:stack_error ,异常处理示例,61,Q7：静态存储分配VS.动态存储分配,静态存储分配 通常定义变量（或对象），编译器在编译时都可以根据该变量（或对象）的类型知道所需内存空间的大小，从而系统在适当的时候为它们分配确定的存储空间。 动态存储分配 有些操作对象只有在程序运行时才能确定，编译器在编译时就无法为它们预定存储空间，只能在程序运行时，系统根据运行时的要求进行内存分配，称为动态存储分配。,62,C+内存空间分布,动态分配在自由存储区中进行,全局变量、static变量,局部变量、函数参数等,63,new和delete操作符,使用的格式： （1）指针变量名=

26、new 类型名(初始化式)； （2）delete 指针名; new运算符返回的是一个指向所分配类型变量（对象）的指针。 对所创建的变量或对象，都是通过该指针来间接操作的，而动态创建的对象本身没有名字。,64,一维数组的动态分配与释放,1、定义 * = 例如：int *fa=NULL; 2、申请内存空间 = new 表达式; 例如：fa=new int100; 注意不是常量表达式！ if(!fa) return error_flag; 可以运行时确定！,65,3、释放内存空间 delete ; 例如：if(fa!=NULL) delete fa; fa=NULL; 说明： 1）如果缺少 ，会产生

27、回收不彻底的问题（只回收了第一个元素所占空间），因为编译器认为该指针是指向数组第一个元素的指针；加了方括号后就转化为指向数组的指针，回收整个数组。 2）delete 的方括号中不需要填数组元素数，系统自知。 即使写了，编译器也忽略。,66,二维数组,指向一维数组的指针的定义如下： 数据类型 (* 指针变量名)n; 这里数组元素的个数n不可省略。 因是指向指针的指针，称二级指针。,二维数组是数组元素为一维数组的数组，所以等效的指针类型应该是指向一维数组的指针类型。如有： int x2d34=1,2,3,4,5,6,7,8,9,10,11,12; int (*pt)4=x2d; 则指针pt 和x2

28、d 是等效的。,67,二维数组的存储空间分布,例 double Matrix108;,首地址 每行首地址 数据单元,Matrix Matrix0 更为灵活！ 【形式2】 (*标识符) 表达式; 例如：int (*fa)20=NULL; 使用指向一维数组的指针，第二维的容量固定！,69,二维数组：申请内存空间,template bool Make2DArray(T * ,70,二维数组：释放内存空间,template void Delete2DArray(T * ,阻止用户继续访问已被释放的空间,71,课后练习,如何实现三维数组的动态分配与释放？ 编码实现：函数模板 1）Make3DArray(

29、) 2）Delete3DArray(),72,Q8：类几个关注点,头文件的构造 枚举类型 构造函数和析构函数 public, private 和 friend 操作符重载,73,预编译指令的作用,#ifndef Currency_ #define Currency_ #endif,预编译指令：确保Currency的代码仅被程序包含（include）和编译一次。,74,枚举类型：enum,enum sign plus, minus; /表示货币符号 C+对枚举的支持 直接作为数据类型使用，不必带enum 例如：sign a; 使用匿名枚举定义常量 例如：enumADD, SUB, MUL, DI

30、V;,75,类的存取访问限制符,class 类名称 public: 公有成员（外部接口） private: 私有成员（隐藏接口） protected: 保护型成员（用于派生） ;,访问限定符private和protected体现了类具有封装性！,76,友元：friend,友元提供了不同类或对象的成员函数之间、类的成员与一般函数之间进行数据共享的机制。 友元是一种定义在类外部的类或普通函数，但需要在类体内进行说明（前面加friend关键字）。 class Complex friend Complex operator + (double,Complex); ; /opration+说明为类Com

31、plex类的友元函数， 友元函数不是成员函数，但可以访问类中的私有成员和保护成员。,77,友元函数示例：操作符重载,/friend只用于类说明中，定义时不加friend Complex operator + (double d , Complex c) return Complex(d+c.Real , c.Image) ; /友元不是成员函数，但以直接访问私有成员 int main( ) c=d+c1; c.print( ); return 0; 解释：d+c被C+编译器解释为：operator+(d,c),78,Q9：程序测试,程序测试：在目标计算机上利用输入数据（test data）来实际运行该程序，把程序的实际行为与所期望的行为进行比较。 测试集（test set）：用来测试的输入数据空间的子集。 测试的目的不是去建立正确性认证，而是要暴露程序中的错误，所以必须选择能暴露程序中所存在错误的测试数据。,79,设计测试数据黑盒与白盒,黑盒法（black box method）：考虑程序的功能，按照行为分类。 白盒法（white box method）：基于对代码的考察，要求实现对程序语句在某种程度上的覆盖。 语句覆盖（statement coverage） 分支覆盖（decision coverage） 从句覆盖（ c