[计算机软件及应用]【0-1】chapte0 课程简介及c++重点知识回顾

《[计算机软件及应用]【0-1】chapte0 课程简介及c++重点知识回顾》由会员分享，可在线阅读，更多相关《[计算机软件及应用]【0-1】chapte0 课程简介及c++重点知识回顾（68页珍藏版）》请在金锄头文库上搜索。

1、数据结构,2012年秋季,中国地质大学信息工程学院,Chapter1 课程简介,课程总体介绍,课程教学内容 课程重要性 前导知识和技能 教材 参考资料 课程实习安排 成绩评定 学习要求,一、课程教学内容,Programs ：为计算机处理问题编制一组指令集；,Algorithms ：处理问题的策略；,Data Structures ：问题的数学模型。（数据+关系）,Niklaus Wirth提出： AlgorithmsData StructuresPrograms,用计算机解决一个具体问题时，大致需要以下步骤：,从具体问题抽象出一个适当的数学模型； 设计一个解决此数学模型的算法； 编写出程序，进

2、行测试、调整直至得到最终解答。,数值计算的程序设计问题,“鸡兔同笼”问题,全球天气预报, 二元一次方程组, 环流模式方程,今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何？,课程教学内容（一）数据结构,例1.1 学生学籍登记表。,非数值计算的程序设计问题,（线性表结构）,特点？,例1.2 酒店管理系统中的客房分配问题,例1.3 铺设煤气管道,(a) 居民区示意图,(b) 铺设煤气管道设计图,（队列结构）,（图结构及图的最小生成树）,例1.4 计算机和人对弈的问题,（树结构）,【数据结构】研究非数值计算的程序设计问题中计算机的操作对象以及它们之间关系和操作等的学科。,小结：课程教学内容（一

3、）数据结构,线性结构 线性表 数组 栈 队列 非线性结构 树、二叉树 图,课程教学内容（二）常用算法,常用算法 排序（Sort） 简单排序算法：起泡、插入、选择 箱排序、基数排序 堆排序 快速排序 归并排 搜索（Search） 简单搜索 折半搜索 散列 搜索树：BST、AVL、B树、红黑树,二、课程重要性,综合性专业基础课 涉及数学、软件和硬件 专业化编程的基础：程序设计的实质是对确定的问题选择一种好的数据结构，设计一种好的算法 后续大量专业课的基础：操作系统、数据库、编译原理、计算机图形学 计算机科学与工程的基础 与课程相关的相关考试、竞赛 计算机软件资格水平考试 计算机考研统考课程之一（占

4、45分） 计算机等级考试 ACM大赛 就业面试 ,三、前导知识和技能,面向对象编程思想 C+程序设计语言 Visual C+编程环境,四、教 材,数据结构（用面向对象方法与C+描述）（第2版） 殷人昆 主编 清华大学出版社,五、参考资料,数据结构（C语言版） 严蔚敏 吴伟民编著 清华大学出版社,参考资料,数据结构与算法 张铭 等编著 高等教育出版社,参考资料,Data Structures, Algorithms, and Applications in C+ (1st edition) by Sartaj Sahni ， McGraw-Hill Co. 汪诗林，孙晓东 等译 机械工业出版社，

5、 2006 年7月,http:/ to Algorithms （算法导论） Thomas H.Cormen Charles E.Leiserson Ronald L.Rivest， Clifford Stein “五个一”： 一章介绍一个算法； 一种设计技术； 一个应用领域； 一个相关话题。,参考资料,Effective C+ by Scott Meyers, Addison-Wesley “改善程序技术与设计思维的50个有效做法” 中文版：侯捷 译 电子工业出版社,六、实习安排,实习时间安排：4学时4次（共16学时） 实习地点：信息楼203 实习工具：Visual C+6.0/ Visual

6、 Studio2005 实习教材：数据据结构与算法实习指导。,实习内容,【实习一】线性表的应用 【实习二】栈和队列的应用 【实习三】树及二叉树 【实习四】图,七、成绩评定,平时成绩（考勤/作业/提问） 15% 上机实习 25% 期末闭卷笔试 60%,八、学习要求,课前预习，课后复习 认真完成书面作业和上机实习 不拘于课堂讲授，广泛阅读，勤于思考 多实践，多交流 【知识拓展】查阅资料了解经典数据结构及算法在相关领域的应用,九、联系方式及公共邮箱,Cell Phone：13607113691 E-mail：（交作业邮箱） 提交作业的邮件，主题按以下格式： 班号+班内序号-姓名-章号-本章作业次数序

7、号 Public E-mail： Password：datastructure 用于下载课件和参考资料，切勿删除邮件！,课表调整（重要）,注：第2、3周的上机时间更改，另行通知,记住自己的总结与体会,算法思想很重要 设计很重要 交流很重要 编码规范很重要 细心很重要 调试很重要 测试很重要,参考资料电子版,算法导论.pdf 数据结构与算法-面向对象的C+设计模式.pdf,C+Primer（中文第三版）.pdf EffectiveC+.chm More Effective C+.doc C+沉思录.pdf,C+回顾重点,模板类 引用与指针（&，*） 递归函数 内存分配与释放：new和delete

8、 异常处理：try、catch、throw 预编译指令 友元 操作符重载 程序的测试和调试,请回顾： （1）面向对象程序设计PPT -第0讲PPT； （2）CString类模拟的实习。,Q & A -C+回顾,Q1： 函数的参数传递,void Func1(int x) x = x + 10; int n = 0; Func1(n); cout“n = “nendl;,void Func2(int ,void Func3(int *p) (*p) = (*p) + 10; int n=0; Func3(,（1）值传递：由于Func1函数体内的x是实参n的一份拷贝，x值的改变不会影响n的变化，所以

9、n仍为0。,（2）引用传递：由于Func1函数体内的x是实参n的引用，x值的改变影响n的变化，所以n为10。,（3）指针传递：由于Func1函数体内的p是指向实参n的指针，p指向的内存的值改变影响n的变化，所以n为10。,Q2：引用 vs.指针,指针通过地址间接访问某个变量，引用通过别名直接访问某个变量。 引用必须被初始化为指向一个对象，一旦初始化了它就不能再指向其他对象； 指针可以指向一系列不同的对象，也可以什么都不指向。 如果一个参数可能在函数中指向不同的对象或者这个参数可能不指向任何对象，则必须使用指针参数。,#include using namespace std; int main(

10、 ) int val(5); int ,10 10 10,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& rc2 能否修改第一个参数为： D_RECT rc1 D_RECT& rc1 const D_RECT& rc1,Q4：函数模板 VS. 类模板,模板是C

11、+支持参数化的工具 使一段程序可以用于处理多种不同类型的对象，即实现了参数化多态性。 函数模板（Function Template） 用来创建一个通用功能的函数。 类模板（Class Template） 使用户可以为类声明一种模式，使得类中的某些数据成员、某些成员函数的参数、某些成员函数的返回值，能取任意类型（包括基本类型的和用户自定义类型）。,函数模板示例,函数模板可以用来创建一个通用功能的函数，以支持多种不同形参，进一步简化重载函数的函数体设计。,类模板,类模板，是对一批仅仅成员数据类型不同的类的抽象，程序员只要为这一批类所组成的整个类家族创建一个类模板，给出一套程序代码，就可以用来生成多

12、种具体的类，（这类可以看作是类模板的实例），从而大大提高编程的效率。,定义类模板的一般形式是：,template class 类名 类声明体 ;,template class Smemory public: void mput(T x); ;,template 类模板名 :成员函数名（形参表） 成员函数的函数体 ,在类模板的外部定义类成员函数的一般形式是：,例如： template void Smemory:mput(T x) ,类模板实例化,类模板是一个类家族的抽象，它只是对类的描述，编译程序不为类模板（包括成员函数定义）创建程序代码，但是通过对类模板的实例化可以生成一个具体的类以及该具体类

13、的对象。 与函数模板不同的是：函数模板的实例化是由编译程序在处理函数调用时自动完成的，而类模板的实例化必须由程序员在程序中显式地指定。,其实例化的一般形式是： 类名 对象名 例如，Smemory mol；,Q5：异常处理,异常的识别和发出 try划定异常识别的代码段 throw抛出异常 异常的处理 catch处理指定类别的异常,float *x=NULL; /set_new_handler(NULL); try x = new float 100000000; catch (std:bad_alloc) / 仅当new 失败时才会进入 cout “Out of Memory“ endl; re

14、turn 1; if(x) memset(x,0, 100000000); /看看是否是有效的内存 delete x; ,C+标准库的异常类,C+标准库中的异常层次的根类被称为exception，定义在库的头文件中。,C+标准库提供的逻辑异常： invalid_argument异常，接收到一个无效的实参，抛出该异常。 out_of_range异常，收到一个不在预期范围中的实参，则抛出。 length_error异常，报告企图产生“长度值超出最大允许值”的对象。 domain_error异常，用以报告域错误（domain error）。,C+标准库提供的运行时异常： range_error异常，

15、报告内部计算中的范围错误。 overflow_error异常，报告算术溢出错误。 underflow_error异常，报告算术下溢错误。 bad_alloc异常。当new( )操作符不能分配所要求的存储区时，会抛出该异常。它是由基类exception派生的。,Q6：静态存储分配VS.动态存储分配,静态存储分配 通常定义变量（或对象），编译器在编译时都可以根据该变量（或对象）的类型知道所需内存空间的大小，从而系统在适当的时候为它们分配确定的存储空间。 动态存储分配 有些操作对象只有在程序运行时才能确定，编译器在编译时就无法为它们预定存储空间，只能在程序运行时，系统根据运行时的要求进行内存分配，称为动态存储分配。,C+内存空间分布,动态分配在自由存储区中进行,全局变量、static变量,局部变量、函数参数等,Q7：new和delete操作符,int *pi = new int; int *pi = new int(1024); int *pia = new int10; string *ps = new string; string *psa = new string10;,delete pi; delete pia; delete ps;