顺序存储的定义 线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表中的数据元素。 实际思路 可以用一维数组来实现顺序存储结构 存储空间：T *m_array; 当前长度： int m_length; {代码...} 顺序存储结构的元素获取操作 判断目标是否合法 将目标位置作为数组下标获取元素 {代码...} 顺序存储结构的元...

生活中的智慧 幼儿园老师总会让小朋友以同样的排队秩序出行。 线性表（List）的表现形式 零个或多个数据元素组成的集合 数据元素在位置上是有序排列的 数据元素的个数是有限的 数据元素的类型必须相同 线性表（List）的抽象定义 线性表是具体有相同类型的 n(>=0)个数据元素的有限序列 (a0, a1, ..., an-1) ai 是表项...

Exception 类继承自 Object 堆空间中创建异常对象失败时，返回NULL指针 新增 InvalidOperationException 异常类 成员函数调用时，如果状态不正确则抛出异常 SmartPointer 类继承自 Object 类 堆空间中创建智能指针对象失败时，返回NULL指针

当代软件架构实践中的经验 尽量使用单重继承的方式进行系统设计 尽量保持系统中只存在单一的继承树 尽量使用组合关系代替继承关系 不幸的事实 C++ 语言的灵活性使得代码可以存在多个继承树 C++ 编译器的差异使得同样的代码可能表现不同的行为 new 操作如果失败会发生什么？ 老版编译器：返回空 新版编译器：抛出异常 创...

异常的类型可以是自定义类类型 对于类类型异常的匹配依旧是至上而下严格匹配 赋值兼容性原则在异常匹配中依然适用 一般而言 匹配子类异常的 catch 放在上部 匹配父类异常的 catch 放下下部 现代C++库必然包含充要的异常类 异常类是数据结构类所依赖的”基础设施“！ 异常类功能定义 异常类 功能定义 ArithmeticException ...

C++ 内置了异常处理的语法元素 try...catch... try 语句处理正常代码逻辑 catch 语句处理异常代码逻辑 try 语句中的异常由对应的 catch 语句处理

内存泄漏（臭名昭著的Bug） 动态内存申请堆空间，用完后不归还 C++ 语言中没有垃圾回收的机制 指针无法控制所指堆空间的生命周期 当代C++软件平台中的智能指针 指针生命周期结束时主动释放堆空间 一片堆空间最多只能由一个指针标识 杜绝指针运算和指针比较 智能指针的设计方案 通过类模板描述指针的行为 能够定义不同类...

数据结构课程的特点 专注数据元素之间的关系 专注于特定结构之上的算法 数据结构课程并不关注数据元素的具体类型。 问题：如何为数据结构的学习选择合适的语言 经验分享：支持泛型编程的语言最适合数据结构课程的学习 泛型编程的概念 不考虑具体数据类型的编程方式 对于Swap函数可以考虑下面的泛型写法 {代码...} Swap ...

先从概念上形象的理解数据元素之间的关系 思考这种关系能够解决什么问题 考虑基于这种关系能够产生哪些算法 理解和熟悉最终的算法 选择一种熟悉的语言，编码实战

常见的时间复杂度 常见时间复杂度的比较 当算法的时间复杂度为 O(2n)(n为指数)，O(n!),或O(nn)(n为指数)时，即使n的值很小，实际的程序运行时间也是不可接收的。 算法的最好与最坏情况 意义：当算法在最坏情况下仍然能满足需求时，可以推断，算法的最好情况和平均情况都能满足需求。 算法分析示例 {代码...} 注意：数据...

结论：判断一个算法的效率时，操作数量中的常数项和其他次要项常常可以忽，只需要关注最高阶次项就能得出结论。 问题：如何用符号定性的判断算法的效率? 算法的复杂度（定性描述） 时间复杂度 算法运行后对时间需求量的定性描述 空间复杂度 算法运行后对空间需求量的定性描述 注意：数据结构课程重点关注的是算法的效率...

比较不同算法对同一组输入数据的运行处理时间 缺陷 为了获得不同算法的运行时间必须编写相应程序 运行时间严重依赖硬件及运行时的环境因素 算法的测试数据选取相当困难

学员间的对话 木暮：我发现三井真是牛，只用一行就实现了strlen 宫城：那么强！他是怎么做的呢？ 木暮：不知道，我看了一下，没看懂。。。 宫城：牛人就是牛人啊！ 问题：程序是否越短越好？是否别人看不懂就证明自己很厉害？ 数据结构与算法 数据结构静态的描述了数据元素之间的关系 高效的程序设计需要在数据结构的基...

程序设计的挑战 利用计算机解决现实生活中的问题 生活中的不同个体之间存在联系 用计算机程序描述生活中个体间的联系 问题：如何描述生活中的个体？ 数据的概念 程序的操作对象，用于描述客观事物 数据的特点 可以输入到计算机 可以被计算机处理 数据中的新概念 数据元素 组成数据的基本单位 数据项 一个数据元素由若干...

理解程序的本质 问题：为什么会有各种各样的程序存在？程序的本质是什么？ 程序是为了解决实际问题而存在的，从本质而言，程序是解决问题的步骤描述。 一小步的进阶：理解实际问题 确认问题类型 如：数值计算，求最小值个数 确认求解步骤 如：打开文件，读取文件，关闭文件，计算和 问题：如何判断问题求解步骤的好坏？ ...

问题：为什么要学士数据结构这门课程？ 学员的常见问题 语言学习结束之后是否有能力进行项目开发？ 当面对一个问题的时候如何思考解决方案？ 如何评价代码效率的高低好坏？ 怎样才能提高自己的编程能力？ 。。。 数据结构的意义 培养专业的程序设计思维 训练使用程序语言描述解决方案的能力 计算机专业的基础课 算法分析...

在一个二维数组中，每一行都按照从左到右的顺序排序，每一列都按照从上到下的顺序排序。请实现一个函数用于判断数组中是否包含指定的数。 {代码...} {代码...} 写一个函数，打印二叉树中某层的所有节点 {代码...} {代码...} {代码...} 编写一个函数用于删除二叉树中的度数为 1 的所有节点 {代码...} {代码...} 输入一个...

下面代码是否有错误？如果有错，错在哪里？ {代码...} 答案： {代码...} 下面的代码输出什么？为什么？ {代码...} 输出： {代码...} 说明： {代码...} 参考：初始化列表的使用 下面的代码输出什么？为什么？ {代码...} 输出： {代码...} Which virtual fucntion re-declaration of the Derived class are correct ? {代...

下面的代码输出什么?为什么? {代码...} 输出： {代码...} 说明： {代码...} 参考：关于 new malloc free delete 的疑问 下面的程序输出什么?为什么? {代码...} 输出： {代码...} 说明： {代码...} 参考：父子间的冲突 下面的描述正确的是？ {代码...} 答案： 【B】说明： {代码...} 下面的代码输出什么？为什么？ {代码....

考虑函数原型 void hello(int a, int b=7, char pszC=""), 下面的函数调用中属于不合法调用的是？ {代码...} 答案：【C】说明：C++ 函数参数的扩展 一个有 800 个节点的完全二叉树，问有多少个叶子节点？ {代码...} 答案：【C】说明： {代码...} 二叉树的深层特性 性质 1 性质 2 性质 3 性质 4 性质 5 若 6 元素为 A.B.C...

32位机上根据下面的代码，问哪些说法是正确的？ {代码...} {代码...} 答案： 【C】输出： {代码...} 说明：有符号与无符号 下面哪些选项可以编译通过？ {代码...} {代码...} 答案：【A】说明： {代码...} int a[10]; 问下面哪些地址不可以表示a[1]的地址? {代码...} 答案：【A】说明： {代码...} 下面的数据存放在哪些存...

动态内存的结果 问题： 动态内存申请一定成功吗？ 常见的动态内存分配代码 C 代码： {代码...} C++ 代码: {代码...} 必须知道的事实 malloc 函数申请失败时返回 NULL 值 new 关键字申请失败时（根据编译器不同） 返回 NULL 值 （古代） 抛出 std::bad_alloc 异常 （现代） 问题： new 语句中的异常是怎么抛出来的呢？ ne...

函数的异常规格说明 问题： 如何判断一个函数是否会抛出异常，以及抛出哪些异常？ C++ 提供语法用于声明函数所抛出的异常 异常声明作为函数声明的修饰符，写在参数列表后面 {代码...} 异常规格说明的意义 提示函数调用者必须做好异常处理的准备 提示函数维护者不要抛出其它异常 异常规格说明是函数接口的一部分 问题： ...

main 函数中抛出异常 问题： 如果在main函数中抛出异常会发生什么？ 如果异常不处理，最后会传到哪里？ 编程实验： 异常的最终处理 下面的代码会输出什么呢？ {代码...} {代码...} 思考：不同的编译器为什么有不同的行为，g++ 中的提示信息是在哪里打印的呢？ 如果异常无法被处理， terminate() 结束函数会被自动调用 默...

本课程学习的是 "经典" C++ 语言 ”经典“ 指的是什么？ C++ 98/03 标准在实际工程中的常用特性 大多数企业的产品开发中需要使用的 C++ 技能

mutable 是为了突破 const 函数的限制而设计的 mutable 成员变量将永远处于可改变的状态 mutable 在实际的项目开发中被严谨滥用

历史上的原因 。。。 早期的 C++ 直接复用 class 关键字来定义模板 但是泛型编程针对的不只是类类型 class 关键字的复用使得代码出现二义性

面试问题 一 编写程序判断一个变量是不是指针 指针的判别 拾遗 C++ 中仍然支持 C 语言中的可变函数参数 C++ 编译器的匹配调用优先级 重载函数 函数模板 变参函数 思路 将变量分为两类： 指针 VS 非指针 编写函数： 指针变量调用时返回 true 非指针变量调用时返回 false 函数模板与变参函数的化学反应 {代码...} 编程实验...

类型识别 在面向对象中可能出现下面的情况 基类指针指向子类对象（赋值兼容性） 基类引用成为子类对象的别名（赋值兼容性） 静态类型 - 变量（对象）自身的类型【编译期可确定】 动态类型 - 指针（引用）所指向对象的实际类型【运行时才可确定】 {代码...} 基类指针是否可以强制类型转换为子类指针取决于动态类型！ 问题...

C++ 中的异常处理 catch 语句块中可以抛出异常 编程实验： catch 中抛出异常 {代码...} {代码...} 问题：为什么要在 catch 中重新抛出异常？ catch 中捕获得异常可以被重新解释后抛出 工程开发中使用这样得方式统一异常类型 编程实验： 异常的重新解释 {代码...} {代码...} 异常的类型可以是自定义类型 对于类类型异常的...