顺序存储结构线性表的最大问题 插入和删除需要移动大量的元素！ 链式存储的定义 为了表示每个元素与其直接后继元素之间的逻辑关系；数据元素除了存储本身的信息外，还要存储其直接后继的信息。 ai 和 ai+1 是线性表中的两个相邻数据元素；在物理内存中无相邻关系。 联系存储逻辑结构 基于链式存储结构的线性表中，每个结...

课程目标 完成 DynamicArray 类的具体实现 DynamicArray 设计要点 类模板 动态确定内部数组空间大小 实现函数返回数组长度 拷贝构造和赋值操作 DynamicArray 类的声明 {代码...} 编程实验：动态数组的实现 {代码...} 文件：main.cpp {代码...} 输出： {代码...} 问题: DynamicArray 类中的函数实现存在重复的逻辑，如何...

课程目标 完成 Array 类的具体实现 完成 StaticArray 类的具体实现 需求分析 创建数组类代替原生数组的使用 数组类包含长度信息 数组类能够主动发现越界访问 Array 要点设计 抽象类模板，存储空间的位置和大小由子类完成 重载数组操作符，判断访问下标是否合法 提供数组长度的抽象访问函数 提供数组对象间的复制操作 Arr...

SqlList中，最耗时的是插入和删除操作，因为要进行移位，尤其当数据元素是自定义类类型，并且类非常庞大时耗时尤为明显。因此，分析一段代码的效率，不能够只看时间复杂度（大O表示法），大O表示法仅为参考指标，而非绝对指标。还需要具体情况具体分析，当前算法是否真的满足需求。由此也证明顺序存储表不适合类类型的元...

课程目标 完成 StaticList 类的具体实现 完成 DynamicList 类的具体实现 StaticList 设计要点 类模板 使用原生数组作为顺序存储空间 使用模板参数决定数组大小 {代码...} 编程实验：StaticList 的实现 文件：StaticList.h {代码...} 文件：main.cpp {代码...} 输出： {代码...} DynamicList 设计要点 类模板 申请连续堆...

课程目标 完成顺序存储结构线性表的抽线实现 SqlList 设计要点 抽象类模板，存储空间的位置和大小由子类完成 实现顺序存储结构线性表的关键操作（增，删，查，等） 提供数组操作符，方便快速获取元素 {代码...} 编程实验：顺序存储线性表 SqlList.h {代码...} To be continued 思考：StaticList 和 DynamicList 如何实现...

顺序存储的定义 线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表中的数据元素。 实际思路 可以用一维数组来实现顺序存储结构 存储空间：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() 结束函数会被自动调用 默...