高级语言程序设计教学大纲.docVIP

高级语言程序设计教学大纲一、课程基本信息课程代码：110421课程名称：高级语言程序设计英文名称：Advanced Programming 课程类别：专业基础课 学 时：90学分：4.5适用对象：信息与计算科学专业大一本科生考核方式：考试（平时成绩占总成绩的30%）先修课程：数学分析、高等代数二、课程简介中文简介：高级程序设计是必修基础课程。本课程以C+语言为工具，主要介绍面向对象的程序设计方法，C+面向对象程序设计语言和面向对象程序设计工具。使学生掌握面向对象的思想方法，是后续专业课程的基础。英文简介：Advanced Programming is major basic course. Through this course, students should master the method of programming,the Object Oriented Language C+ ，and Object Oriented Design tool. This course is the base of several following speciality courses. 三、课程性质与教学目的高级语言程序设计课程是信息与计算科学专业的专业必修课,要求掌握面向对象程序设计中基本的概念、方法，在理论、实践上为后续软件课程打下坚实基础。具体包括：基本语法成分、数据定义和相关运算、基本控制流程的概念和实现、函数的定义和调用、指针的基本概念、能够应用于数据组织和函数调用。以及面向对象程序设计的核心概念：封装、继承、多态和模板与群体数据组织。四、教学内容及要求 第一章 绪论 (一) 目的与要求1掌握计算机程序设计语言的发展；2掌握在VC6.0集成开发环境下建立和运行+程序的方法；3. 了解面向对象的方法；4. 了解面向对象的软件开发过程；5. 了解信息的表示与存储。(二) 教学内容第一节 计算机程序设计语言的发展1主要内容机器语言与汇编语言，主级语言，面向对象语言。2基本概念和知识点： 面向对象的语言，高级语言的概念。3. 问题与应用（能力要求）：了解程序设计语言的发展史与面向对象的语言。第二节 面向对象的方法1主要内容面向对象方法的由来，面向对象的基本概念。2基本概念和知识点 面向对象的基本概念。3. 问题与应用（能力要求）了解面向对象的由来与基本概念。第三节 面向对象的软件开发1主要内容软件开发的各个阶段及任务。2基本概念和知识点 分析、设计、编程、测试与维护。3. 问题与应用（能力要求）了解软件开发过程中的一般过程及各阶段的任务。*第四节 信息的表示与存储1主要内容计算机的数字系统，几种进行记数制之间的转换信息存储单位，二进制数的编码表示，定点数和浮点数，数的表示范围，非数值信息表示。2基本概念和知识点 数字系统，进位制及其转换，数的表示范围。3. 问题与应用（能力要求）掌握用二进制的编码表示，非数值信息表示。第五节 程序的开发过程1主要内容基本术语。2基本概念和知识点 程序开发的基本术语与开发的一般过程。3. 问题与应用（能力要求）了解程序开发的基本术语和开发的一般过程。(三) 实践环节与课后练习VC环境下运行一个简单的C程序。(四) 教学方法与手段课堂板书结合PowerPoint电子教案讲授。第二章 C+简单程序设计(一) 目的与要求1了解C+语言产生和特点；2掌握基本数据类型和表达式；3. 掌握数据的输入与输出；4. 掌握算法的基本控制结构；5. 掌握自定义数据类型。(二) 教学内容第一节 C+语言概述1主要内容C+语言的产生，C+语言的特点，C+程序实例，字符集，词法记号。2基本概念和知识点 字符集，词法记号。3. 问题与应用（能力要求）掌握字符集，了解C+语言的特点与程序实例。第二节 基本数据类型和表达式1主要内容基本数据类型，常量，变量，运算符，表达式与语句。2基本概念和知识点 基本数据类型，常量，变量，运算符，表达式与语句。3. 问题与应用（能力要求）掌握基本数据类型，常量，变量，运算符，表达式与语句。*第三节 数据的输入与输出（自学）1主要内容I/O流，预定义的插入符和提取符，简单的I/O格式控制。2基本概念和知识点 I/O流，预定义的插入符和提取符， I/O格式控制。3. 问题与应用（能力要求）掌握I/O流，预定义的插入符和提取符。第四节 算法的基本控制结构1主要内容用if语句实现选择结构，多重选择结构，循环结构，循环结构与选择结构的嵌套，其它控制语句。2基本概念和知识点 用if语句实现选择结构，多重选择结构，循环结构。3. 问题与应用（能力要求）掌握用if语句实现选择结构，多重选择结构，循环结构。第五节 自定义数据类型1主要内容typedef声明，枚举类型，结构体，联合体。2基本概念和知识点 typedef声明，枚举类型，结构体，联合体。3. 问题与应用（能力要求）掌握枚举类型，结构体。(三) 实践环节与课后练习编写简单的C程序，使用枚举类型，结构体。(四) 教学方法与手段课堂板书结合PowerPoint电子教案讲授，程序演示。第三章 函数(一) 目的与要求1 正确掌握函数的定义；2 掌握内联函数；3 掌握带默认形参值的函数；4 掌握函数重载。(二) 教学内容第一节 函数的定义与使用1 主要内容函数的定义，函数的调用，函数的参数传递。2 基本概念和知识点函数的定义，函数的调用，函数的参数传递。3 问题与应用（能力要求）掌握函数的定义，函数的调用，函数的参数传递。*第二节 内联函数1 主要内容内联函数的定义与使用。2 基本概念和知识点内联函数的定义，内联函数在使用场合。3 问题与应用（能力要求）掌握内联函数的定义，内联函数在使用场合。第三节 带默认形参值的函数1 主要内容带默认形参值的函数。2 基本概念和知识点带默认形参值的函数及其使用法。3 问题与应用（能力要求）掌握带默认形参值的函数及其使用。第四节 函数重载1 主要内容函数重载的概念与定义。2 基本概念和知识点函数重载的概念与定义和使用。3 问题与应用（能力要求）掌握函数重载的概念与使用。*第五节 使用C+系统函数（自学）1. 主要内容C+系统函数。2. 基本概念和知识点C+系统函数及其查询与使用法。3. 问题与应用（能力要求）掌握简单的C+系统函数。(三) 实践环节与课后练习使用简单的系统函数编写程序。(四) 教学方法与手段课堂板书结合PowerPoint电子教案讲授，程序演示。第四章 类与对象(一) 目的与要求1. 熟练掌握类与对象的概念；2. 熟练掌握构造函数与析构函数；3. 掌握类的组合；4. 掌握UML图形标识。(二) 教学内容第一节 面向对象程序设计的基本特点1 主要内容抽象，封装，继承，多态。2 基本概念和知识点抽象，封装，继承，多态。3 问题与应用（能力要求）理解抽象，封装，继承，多态。第二节 类和对象1 主要内容类的声明，类成员的访问控制，类的成员函数，对象，举例说明。2 基本概念和知识点类的声明，类成员的访问控制，类的成员函数，对象。3 问题与应用（能力要求）掌握类的声明，类成员的访问控制，类的成员函数，对象。第三节 构造函数和析构函数1 主要内容构造函数，拷贝构造函数，析构函数，程序举例。2 基本概念和知识点构造函数，拷贝构造函数，析构函数。3 问题与应用（能力要求）掌握构造函数，拷贝构造函数，析构函数。第四节 类的组合1 主要内容组合，引用声明。2 基本概念和知识点组合，引用声明，程序举例。3 问题与应用（能力要求）掌握组合，引用声明，程序举例。*第五节 UML图形标识（自学）1. 主要内容UML简介，UML类图。2. 基本概念和知识点UML简介，UML类图。3. 问题与应用（能力要求）掌握UML类图。(三) 实践环节编写程序，要求含有类及类构造函数与析构函数和拷贝构造函数。(四) 教学方法与手段采用PowerPoint电子教案相结合的方式的课堂讲授和上机实验结合为主，辅以程序演示。第五章 C+程序的结构(一) 目的与要求1. 熟练掌握作用域与可见性的概念；2. 熟练掌握对象的生存期；3. 掌握类的静态成员；4. *了解类的友元；5. *掌握共享数据的保护；6. *掌握多文件结构处理；7. *理解编译预处理命令。(二) 教学内容第一节 标识符的作用域与可见性1 主要内容作用域与可见性。2 基本概念和知识点标识符的作用域与可见性。3 问题与应用（能力要求）掌握标识符的作用域与可见性。第二节 对象的生存期1 主要内容静态生存期，动态生存期。2 基本概念和知识点静态生存期，动态生存期。3 问题与应用（能力要求）掌握静态生存期，动态生存期。第三节 类的静态成员1 主要内容静态数据成员，静态函数成员。2 基本概念和知识点静态数据成员，静态函数成员。*3.问题与应用（能力要求）掌握静态数据成员，静态函数成员。*第四节 类的友元1 主要内容友元类，友元函数。2 基本概念和知识点友元类，友元函数。3 问题与应用（能力要求）了解友元类，友元函数。*第五节 共享数据的保护（选学）1. 主要内容常引用，常对象。2. 基本概念和知识点常引用，常对象。3. 问题与应用（能力要求）掌握常引用，常对象。*第六节 多文件结构和编译预处理命令（自学）1. 主要内容C+程序的一般组织结构，外部变量与外部函数，标准C+库函数和命名空间，预处理。2. 基本概念和知识点C+程序的一般组织结构，外部变量与外部函数，标准C+库函数和命名空间，预处理。3. 问题与应用（能力要求）掌握一般组织结构，外部变量与外部函数，标准C+库函数和命名空间，预处理。(三) 实践环节编写程序，要求类含有静态成员，常引用常对象，使用多文件组织。(四) 教学方法与手段采用PowerPoint电子教案相结合的方式的课堂讲授和上机实验结合为主。辅以程序演示。第六章 数组、指针与字符串(一) 目的与要求1. 熟练掌握数组；2. 熟练掌握指针；3. 掌握动态内存分配；4. 掌握深拷贝与浅拷贝；5. *掌握字符与string类。(二) 教学内容第一节 数组1 主要内容数据的声明与使用，数组的存储与初始化，数组作为函数参数，对象数组，程序举例。2 基本概念和知识点数据的声明与使用，数组的存储与初始化，数组作为函数参数，对象数组。3 问题与应用（能力要求）掌握数据的声明与使用，数组的存储与初始化，数组作为函数参数，对象数组。*第二节 指针（部分选学）1 主要内容内存空间访问方式，指针变量的声明，与地址运算，指针的赋值，指针运算，用指针处理数组元素，指针数组，用指针作为函数参数，指针型函数，指向函数的指针，对象指针。2 基本概念和知识点内存空间访问方式，指针变量的声明，与地址运算，指针的赋值，指针运算，用指针处理数组元素；其中选学：指针数组，用指针作为函数参数，指针型函数，指向函数的指针，对象指针。3 问题与应用（能力要求）掌握：指针变量的声明，与地址运算，指针的赋值，指针运算，用指针处理数组元素，指针数组，用指针作为函数参数，指针型函数，指向函数的指针，对象指针。第三节 动态内存分配1 主要内容new运算和delete运算，动态内存分配与释放函数。2 基本概念和知识点new运算和delete运算，动态内存分配与释放函数。3 问题与应用（能力要求）掌握new运算和delete运算，动态内存分配与释放函数。第四节 深拷贝与浅拷贝1 主要内容深拷贝与浅拷贝。2 基本概念和知识点深拷贝与浅拷贝。3 问题与应用（能力要求）掌握深拷贝与浅拷贝。*第五节 字符串（自学）1. 主要内容用字符数组存储和处理字符串，string类。2. 基本概念和知识点用字符数组存储和处理字符串，string类。3. 问题与应用（能力要求）掌握处理字符串和string类。(三) 实践环节 编写程序，要求使用数组和指针，动态内存分配，另在拷贝构造函数中使用深拷贝，使用string类。(四) 教学方法与手段采用PowerPoint电子教案相结合的方式的课堂讲授和上机实验结合为主。辅以程序演示。第七章 继承与派生(一) 目的与要求1. 熟练掌握继承与派生；2. 熟练掌握继承时的访问控制；3. 掌握派生类的构造和析构函数；4. 掌握派生类成员的标识与访问。(二) 教学内容第一节 类的继承一派生1 主要内容继承与派生的实例，派生类的定义，派生类的生成过程，程序举例。2 基本概念和知识点派生类的定义，派生类的生成过程。3 问题与应用（能力要求）掌握派生类的定义，派生类的生成过程。第二节 访问控制1 主要内容派生时的公有继承，私有继承，保护继承。2 基本概念和知识点派生时的公有继承，私有继承，保护继承。3 问题与应用（能力要求）掌握：派生时的公有继承，私有继承，保护继承。*第三节 类型兼容规则（选学）1 主要内容各派生类的对象类型兼容规则。2 基本概念和知识点各派生类的对象类型兼容规则。3 问题与应用（能力要求）掌握各派生类的对象类型兼容规则。第四节 派生类的构造和析构函数1 主要内容派生类的构造函数，拷贝构造函数与析构函数。2 基本概念和知识点派生类的构造函数，拷贝构造函数与析构函数。3 问题与应用（能力要求）掌握派生类的构造函数，拷贝构造函数与析构函数。*第五节 派生类成员的标识与访问（自学）1. 主要内容作用域与分辨率，虚基类，虚基类及其派生类的构造函数。2. 基本概念和知识点作用域与分辨率，虚基类，虚基类及其派生类的构造函数。3. 问题与应用（能力要求）作用域与分辨率，虚基类，虚基类及其派生类的构造函数。(三) 实践环节 编写程序，要求使用继承与派生，正确书写派生类的构造函数，拷贝构造函数与析构函数，使用虚基类。(四) 教学方法与手段采用PowerPoint电子教案相结合的方式的课堂讲授和上机实验结合为主。辅以程序演示。第八章 多态性(一) 目的与要求1. 熟练掌握运算符重载；2. 熟练掌握虚函数与抽象类。(二) 教学内容第一节 多态性概述1 主要内容多态的类型，多态实现。2 基本概念和知识点多态的类型，多态实现。3 问题与应用（能力要求）掌握多态的类型，多态实现。*第二节 运算符重载1 主要内容运算符重载的规则，运算符重载为成员函数，运算符重载为友元函数。2 基本概念和知识点运算符重载的规则，运算符重载为成员函数，运算符重载为友元函数。3 问题与应用（能力要求）掌握：运算符重载的规则，运算符重载为成员函数。第三节 虚函数1 主要内容一般虚函数成员，虚析构函数。2 基本概念和知识点一般虚函数成员，虚析构函数。3 问题与应用（能力要求）掌握一般虚函数成员，虚析构函数。*第四节 抽象类1 主要内容纯虚函数，抽象类。2 基本概念和知识点纯虚函数，抽象类。3 问题与应用（能力要求）掌握纯虚函数，抽象类。(三) 实践环节 编写程序，要求使用运算符重载，虚函数与虚基类。(四) 教学方法与手段采用PowerPoint电子教案相结合的方式的课堂讲授和上机实验结合为主。辅以程序演示，分组讨论。*第九章 群体类和群体数据的组织（自学）(一) 目的与要求1. 掌握函数模板与类模板；2. 掌握线性群体的概念；3. 掌握数组模板类与链表模板类；4. 掌握群体数据的常操作。(二) 教学内容第一节 多态性概述1 主要内容函数模板与类模板。2 基本概念和知识点函数模板与类模板。3 问题与应用（能力要求）掌握函数模板与类模板。第二节 线性群体1 主要内容线性群体的概念，直接访问数组群体类模板，顺序访问的链表群体类模板。2 基本概念和知识点线性群体的概念，直接访问数组群体类模板，顺序访问的链表群体类模板。3 问题与应用（能力要求）掌握：直接访问数组群体类模板，顺序访问的链表群体类模板。(三) 实践环节 编写程序，数组类模板与链表类模板，并要求用常用操作。(四) 教学方法与手段采用PowerPoint电子教案相结合的方式的课堂讲授和上机实验结合为主,辅以程序演示. *第十章 泛型程序设计与C+标准模板库（选学）(一) 目的与要求1. 掌握泛型程序设计的概念和术语；2. 掌握会使用简单的标准模板库中的容器与容器适配器。(二) 教学内容第一节 泛型程序设计的概念和术语1 主要内容泛型程序设计，命名空间概念，头文件命名规则，标准模板库术语。2 基本概念和知识点泛型程序设计，命名空间概念，头文件命名规则，标准模板库术语。3 问题与应用（能力要求）了解泛型程序设计，命名空间概念，头文件命名规则，标准模板库术语。第二节 C+标准模板库中的容器1 主要内容顺序容器，容器适配器。迭代器。2 基本概念和知识点顺序容器，容器适配器。迭代器。3 问题与应用（能力要求）了解：顺序容器，容器适配器。迭代器。(三) 实践环节 编写程序，使用顺序容器，及其相应的适配器（要求数组模板或链表模板）。(四) 教学方法与手段采用PowerPoint电子教案相结合的方式的课堂讲授和上机实验结合为主，辅以程序演示。 *第十一章 流类库与输入/输出（自学）(一) 目的与要求1. 了解I/O流的概念及流类库结构；2. 了解输出流与输入流。(二) 教学内容第一节 I/0流的概念及流类库结构1 主要内容基本概念，输出流，输入流。2 基本概念和知识点基本概念，输出流，输入流语。3 问题与应用（能力要求）了解基本概念，输出流，输入流。(三) 实践环节 编写程序，使用输出输入流。(四) 教学方法与手段采用PowerPoint电子教案相结合的方式的课堂讲授和上机实验结合为主，辅以程序演示。*第十二章 异常处理（选学）(一) 目的与要求1. 了解异常处理的基本思想；2. 了解C+异常处理的实现；3. 了解标准程序库异常处理。(二) 教学内容第一节 异常处理1 主要内容异常处理的基本思想，异常处理的实现，标准程序库异常处理。2 基本概念和知识点异常处理的基本思想，异常处理的实现，标准程序库异常处理。3 问题与应用（能力要求）了解异常处理的基本思想，异常处理的实现，标准程序库异常处理。(三) 实践环节 阅读书上例题程序，并上机验证，偿试编写异常处理程序。(四) 教学方法与手段采用PowerPoint电子教案相结合的方式的课堂讲授和上机实验结合为主，辅以程序演示。 五、各教学环节学时分配 教学环节教学时数课程内容讲课习题课讨论课实验其他教学环节小计第一章 绪论22第二章C+简单程序设计33第三章函数33第四章 类与对象33第五章C+程序的结构33第六章 数组、指针与字符串9312第七章 继承与派生8311第八章 多态性8311第九章 群体类和群体类数据的组织99第十章 泛型程序设计与标准模板库90第十一章 流类库与输入输出66第十二章 异常处理33派生继承与多态性（综合设计性实验，学生自主设计完成）99期未复习巩固66合计72001890六、推荐教材和教学参考资源推荐教材：郑莉、董渊，C+语言程序设计（第3版）， 清华大学出版社。教学参考资源：（1）郑莉、董渊，C+程序设计程序设计案例教程，清华大学出版社。（2）郑莉、董渊，C+语言程序设计（第3版）学生用书，清华大学出版社。七、其他说明 大纲中打星号的部分，教师可根据实际情况选择是否讲解。 大纲修订人： 孙红英 修订日期：2007.4.25大纲审定人： 胡小健 审定日期：2007.5.28数据结构课程教学大纲一、课程基本信息课程代码：110051课程名称：数据结构英文名称：Data Structure课程类别：专业基础课学 时：72学分：3.5适用对象:信息与计算科学专业本科生考核方式：考试、平时成绩占总成绩的30先修课程：高级语言程序设计、离散数学二、课程简介数据结构是计算机学科的核心专业基础课程，是程序设计的重要理论和实践基础。课程讨论了软件设计中经常遇到的线性表、堆栈、队列、串、数组、树和二叉树、图等典型数据结构的逻辑结构、存储结构和操作的实现方法，以及递归算法设计方法和各种典型排序和查找算法的设计方法。通过本课程的学习，一方面为后续课程，特别是软件分析和设计方面的课程，打下理论基础；另一方面，也进行了充分的实践动手训练。Data Structure is a core specialty basic course for computer subjects. It is also an important theory and practice base for programming. The course discusses logical and storage structure of typical data structures, such as linear list, stack, queue, string, array, tree, binary tree and graph, as well as its operations implementing. Recursion algorithm and all sorts of typical sort and search algorithms are also included. Through learning this course, students could lay a theory foundation for later courses, especially for software analysis and design relative courses. On the other hand, abundant training is practiced in the process.三、课程性质与教学目的课程性质是一门研究非数值计算的程序设计问题中计算机的操作对象及其之间关系与操作的学科，是介于数学、计算机硬件和计算机软件三者之间的一门核心课程，属于计算机学科中的一门综合性专业基础课程，是一般程序设计的基础，也是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。教学目的一方面学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。另一方面，本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚和正确易读，符合软件工程的规范。如果说高级语言程序设计课程对学生进行了结构化程序设计的初步训练的话，那么数据结构课程就要培养他们的数据抽象能力。四、教学内容及要求 第一章 绪论(一) 目的与要求1. 通过本章的学习，使学生领会数据、数据元素和数据项的概念及其相互间的关系；2. 掌握数据结构的逻辑结构、存储结构的联系与区别；3. 了解算法时间复杂度和空间复杂度的分析。 (二) 教学内容 第一节 什么是数据结构 1. 主要内容由数学方程无法描述的非数值计算问题引出数据结构表、图、树的3种实例，数据结构的概念，数据结构的内涵和特点，数据结构所处的学科地位，数据结构的学科背景、起源、发展和现状。2. 基本概念和知识点数据结构的概念；数据结构的内涵和特点；数据结构所处的学科地位；数据结构的学科背景、起源、发展和现状。3. 问题与应用（能力要求）要求学生掌握数据结构的概念，能辨别数学模型中数学方程和表、图、树等数据结构的区别。 第二节 基本概念和术语1 主要内容本课使用的一些基本概念，包括数据、数据元素、数据项、数据对象、数据结构、集合、结构、线性结构、树形结构、图状结构、网状结构、逻辑结构、物理结构、存储结构、位、元素、结点、数据域、顺序映像、非顺序映像、顺序存储结构、链式存储结构、指针、虚拟存储结构、数据类型、原子类型、结构类型、抽象数据类型、固定聚合类型、可变聚合类型、多形数据类型。2 基本概念和知识点数据、数据元素、数据项、数据对象、数据结构、集合、结构、线性结构、树形结构、图状结构、网状结构等在内的所有基本概念。3 问题与应用（能力要求）掌握包括数据、数据元素、数据项、数据对象、数据结构、集合、结构、线性结构、树形结构、图状结构、网状结构等基本概念。第三节 抽象数据类型的表示与实现1 主要内容抽象数据类型的常用表示方法。2 基本概念和知识点抽象数据类型的常用表示方法，包括预定义常量和类型、数据结构的表示用类型定义（typedef）描述、函数表示法、各种赋值语句、选择语句、结束语句、输入和输出语句、基本函数、逻辑运算约定。3 问题与应用（能力要求）掌握抽象数据类型的类C语言11种表示方法。第四节 算法与算法分析1 主要内容算法的定义，算法的5个重要特征。好算法设计的4个要求。算法效率的2种度量方法，时间复杂度的概念，频度的概念。空间复杂度的概念，空间复杂度的表示法，算法原地工作的概念。2 基本概念和知识点算法的定义，算法的5个重要特征。好算法设计的4个要求。时间复杂度，空间复杂度的概念，空间复杂度。3 问题与应用（能力要求）掌握算法的定义；理解算法的5个重要特征；理解好算法设计的4个要求；掌握空间复杂度的概念。(三) 课后练习配套习题集P7 1.1，P8 1.8 （1）、（6）， P10 1.12。(四) 教学方法与手段采用黑板板书和PowerPoint电子教案相结合的方式。第二章 线性表（一） 目的与要求1 了解线性表的基本概念和类型定义；2 熟练掌握顺序存储的线性表和单链表的算法设计及其程序实现；3 掌握循环链表和双向链表的操作。（二） 教学内容 第一节 线性表的类型定义1 主要内容线性结构的特点，线性表的抽象数据类型定义，数据项、记录、文件的定义，实例说明线性表的插入、删除、归并等操作方式，并对算法做相应的分析。 2 基本概念和知识点线性结构的特点, 线性表的插入、删除、归并等操作。3 问题与应用（能力要求）要求学生掌握线性表的概念和抽象数据类型定义。 第二节 线性表的顺序表示和实现1 主要内容线性表的顺序表示的概念，顺序映像的方式，顺序映像的随机存取特性，实例描述线性表在顺序存储表示时进行插入、删除、合并操作的几种算法。2 基本概念和知识点线性表的顺序表示的概念, 插入、删除、合并操作的几种算法。3 问题与应用（能力要求）掌握线性表的顺序表示的概念和顺序映像的方式；理解线性表在顺序存储结构时的插入、删除、合并等操作方法。第三节 线性表的链式表示和实现1 主要内容线性链表的概念，单链表的插入、删除、合并操作处理算法，静态链表的算法；循环链表的概念，循环链表的操作特点；双向链表的概念和特点，双向链表的抽象数据类型定义，双向链表的几种操作算法。2 基本概念和知识点几种链表的概念,操作特点及处理算法。3 问题与应用（能力要求）掌握线性有序链表的概念；理解单链表的插入、删除、合并操作算法；掌握循环链表的概念；掌握双向链表的概念；了解双向链表的抽象数据类型定义；了解双向链表的操作算法。*第四节 一元多项式的表示及相加（选学）1 主要内容利用线性链表的基本操作来实现一元多项式的定义、相加和相乘运算。2 基本概念和知识点一元多项式的定义、相加和相乘运算。3 问题与应用（能力要求）掌握利用线性链表的基本操作来实现一元多项式的定义、相加和相乘运算。（三） 实践环节建立线性表类，实现相关操作，应用于多项式相加、相乘问题。（四） 教学方法与手段采用黑板板书和PowerPoint电子教案相结合的方式。第三章 栈和队列（一）目的与要求1 掌握栈和队列的定义；2 熟练掌握顺序和链接存储的栈和队列的算法设计及其程序实现；3 了解栈和队的各种应用。（二）教学内容 第一节 栈1 主要内容栈、栈顶、栈底、后进先出等概念，栈的抽象数据定义；栈的2种存储表示法：顺序栈和链栈的定义，顺序栈的模块说明。2 基本概念和知识点栈及栈的相关概念，栈的抽象数据定义；顺序栈的定义。3 问题与应用（能力要求）掌握栈及栈的相关概念；理解栈的抽象数据定义；掌握顺序栈的定义。 第二节 栈的应用举例1 主要内容应用栈结构的后进先出特性，进行十进制N和其它d进制数的转换算法；进行圆括号和方括号书写格式是否正确的检查算法。2 基本概念和知识点十进制N和其它d进制数的转换算法；圆括号和方括号书写格式是否正确的检查算法。3 问题与应用（能力要求）理解应用栈结构的数制转换算法；理解应用栈结构的括号匹配检验算法。第三节 栈与递归的实现1 主要内容递归的概念、递归问题的特性，栈在n阶Hanoi塔问题等典型递归问题中的应用。2 基本概念和知识点递归的概念、递归问题的特性，n阶Hanoi塔问题。3 问题与应用（能力要求）理解栈在n阶Hanoi塔递归算法中的应用。第四节 队列1 主要内容队列、FIFO的概念，队列的特性，队列的抽象数据定义。队列链式表示的基本操作函数。循环队列的概念。 2 基本概念和知识点队列、FIFO的概念，队列的特性，队列的抽象数据定义。队列链式表示的基本操作函数。循环队列的概念。3 问题与应用（能力要求）掌握队列的概念；理解队列的特性，队列的抽象数据定义；理解队列链式表示的基本操作函数。 （三）实践环节建立顺序存储的栈类，应用于十进制向d进制数字转换问题。（四）教学方法与手段采用黑板板书和PowerPoint电子教案相结合的方式。第四章 串（一） 目的与要求1. 掌握串的基本存储结构及基本操作；2. 了解改进的模式匹配算法。（二） 教学内容 第一节 串类型的定义1 主要内容串产生的背景，串的概念，串长度、空串、子串、主串、位置、空格串等概念，串的抽象数据类型定义，串的基本操作集概念。2 基本概念和知识点串的概念，串的抽象数据类型定义，串的基本操作集概念。3 问题与应用（能力要求）掌握串及相关的概念，理解串的抽象数据类型定义。 第二节 串的表示和实现1 主要内容串在机内的定长顺序表示，串的连接操作和子串操作，串的堆分配存储表示，在这种存储结构表示时如何实现串的插入操作。2 基本概念和知识点串在机内的定长顺序表示及相关操作算法；串的堆分配存储表示及相关操作算法。3 问题与应用（能力要求）掌握串的定长顺序存储表示；理解在定长顺序存储结构表示时实现串的连接操作和子串操作的方法；掌握串的堆分配存储表示；了解在堆分配存储结构表示时实现串的插入操作串的块链存储表示；了解串的块链存储表示。*第三节 串的模式匹配算法（选学）1 主要内容串的定位操作、匹配、模式匹配、模式串等概念，求子串位置的定位函数；KMP模式匹配算法。2 基本概念和知识点串的定位操作、匹配、模式匹配、模式串等概念，求子串位置的定位函数；KMP模式匹配算法。3 问题与应用（能力要求）掌握模式匹配的概念，熟悉求子串位置的定位函数，熟悉KMP模式匹配算法。第四节 串操作应用举例1 主要内容在文本编辑中使用串操作；使用串建立词索引表的方法，词索引表插入的实现算法。2 基本概念和知识点在文本编辑中使用串操作；使用串建立词索引表的方法。3 问题与应用（能力要求）理解文本编辑中串的用法，了解建立词索引表中串的用法。（三） 实践环节1. 熟悉串类型的实现方法，了解简单文字处理的设计方法。 2. 熟悉C语言的字符和把字符串处理的原理和方法。（四） 教学方法与手段采用黑板板书和PowerPoint电子教案相结合的方式。第五章 数组和广义表（一） 目的与要求1 掌握数组的顺序存储结构及特殊矩阵的存储方式；2 掌握数组的顺序存储结构及特殊矩阵的存储方式；3 了解稀疏矩阵的压缩存储方式三元组表；4 理解广义表的定义、术语、存储结构、运算。（二） 教学内容 第一节 数组的定义1 主要内容抽象数据类型数组的定义。2 基本概念和知识点抽象数据类型数组。3 问题与应用（能力要求）掌握抽象数据类型数组的定义。 第二节 数组的顺序表示和实现1 主要内容数组的顺序存储结构，以列序为主序的二维数组存储方式，以行序为主序的二维数组存储方式，n维数组的数据元素存储位置的计算。2 基本概念和知识点数组的顺序存储结构，n维数组的数据元素存储位置的计算。3 问题与应用（能力要求）掌握数组的顺序表示法。第三节 矩阵的压缩存储1 主要内容矩阵、压缩存储、特殊矩阵的概念，特殊矩阵的压缩存储算法；稀疏矩阵的概念，稀疏矩阵的压缩存储算法，两个稀疏矩阵相乘的算法。2 基本概念和知识点矩阵、压缩存储、特殊矩阵，特殊矩阵的压缩存储算法；稀疏矩阵的概念，稀疏矩阵的压缩存储算法，两个稀疏矩阵相乘的算法。3 问题与应用（能力要求）掌握压缩存储、特殊矩阵的概念，熟悉特殊矩阵的压缩存储算法。掌握稀疏矩阵的压缩存储算法。第四节 广义表的定义1 主要内容抽象数据类型广义表的定义，列表的3个重要结论。2 基本概念和知识点抽象数据类型广义表，列表的3个重要结论。3 问题与应用（能力要求）掌握抽象数据类型广义表的定义。第五节 广义表的存储结构1 主要内容广义表的链式存储结构，广义表的头尾链表存储表示。2 基本概念和知识点广义表的链式存储结构，广义表的头尾链表存储表示。3 问题与应用（能力要求）熟悉广义表的存储结构。 （三） 实践环节与课后练习利用稀疏矩阵的“三元组表”存储结构，实现两个矩阵的相加。（四） 教学方法与手段采用黑板板书和PowerPoint电子教案相结合的方式。第六章 树与二叉树（一） 目的与要求1 掌握树的定义、性质、存储结构；2 熟练掌握二叉树的遍历算法及其实现；3 哈夫曼树的构造方法和编码方法；4 了解树、森林和二叉树的转换及遍历。（二） 教学内容 第一节 树的定义和基本术语1 主要内容树型结构的背景，树、子树、结点、叶子、终端结点、分支结点、双亲、孩子、深度、有序树、无序树、森林抽象数据类型树的定义,树的4种表示法。2 基本概念和知识点树、子树、结点、叶子、终端结点、分支结点、双亲、孩子、深度、有序树、无序树、森林抽象数据类型树的定义,树的4种表示法。3 问题与应用（能力要求）掌握树的概念，树结构中结点、叶子、深度等术语的概念。 第二节 二叉树1 主要内容抽象数据类型二叉树的定义；二叉树的5个重要性质；二叉树的顺序存储结构，二叉树的链式存储结构。2 基本概念和知识点抽象数据类型二叉树；二叉树的5个重要性质；二叉树的顺序存储结构，二叉树的链式存储结构。3 问题与应用（能力要求）掌握抽象数据类型二叉树的定义；掌握二叉树的5个重要性质，掌握二叉树的顺序存储结构，二叉树的链式存储结构。第三节 遍历树和线索二叉树1 主要内容遍历和遍历二叉树的概念，先序遍历二叉树的操作定义，中序遍历二叉树的操作定义，后序遍历二叉树的操作定义，先序遍历二叉树基本操作的递归算法在二叉链表上的实现；线索链表、线索、线索二叉树、线索化的概念，线索二叉树及其存储结构，后序后继线索二叉树。2 基本概念和知识点遍历和遍历二叉树，先序遍历二叉树的操作，中序遍历二叉树的操作，后序遍历二叉树的操作，先序遍历二叉树基本操作的递归算法在二叉链表上的实现；线索链表、线索、线索二叉树、线索化，线索二叉树及其存储结构，后序后继线索二叉树。3 问题与应用（能力要求）掌握遍历和遍历二叉树的概念；熟悉序遍历二叉树基本操作的递归算法在二叉链表上的实现；掌握线索、线索二叉树的概念；熟悉中序线索二叉树，中序线索链表。第四节 树和森林1 主要内容 树的3种常用的链表存储结构。森林与二叉树的转换，森林转换成二叉树的定义，二叉树转换成森林的定义；森林的2种遍历方法。2 基本概念和知识点树的3种常用的链表存储结构。森林与二叉树的转换，森林转换成二叉树，二叉树转换成森林；森林的2种遍历方法。3 问题与应用（能力要求）掌握树的3种常用的链表存储结构；掌握森林转换成二叉树的定义，二叉树转换成森林的定义；了解森林的2种遍历方法。第五节 赫夫曼树及其应用1 主要内容最优二叉树的概念，构造赫夫曼树的算法；赫夫曼编码的定义，赫夫曼编码的存储表示。2 基本概念和知识点最优二叉树，构造赫夫曼树的算法；赫夫曼编码，赫夫曼编码的存储表示。3 问题与应用（能力要求）掌握最优二叉树的概念，构造赫夫曼树的算法；掌握赫夫曼编码的定义，赫夫曼和赫夫曼编码的存储表示。 （三） 实践环节安排综合性实验，建立二叉树类，要求用先序、中序、后序遍历二叉树。（四） 教学方法与手段采用黑板板书和PowerPoint电子教案相结合的方式。第七章 图（一） 目的与要求1 掌握图的定义和术语；2 熟练掌握图的存储结构及深度和广度搜索算法思想及其实现；3 了解最短路径算法。（二） 教学内容 第一节 图的定义和术语1 主要内容图的概念，抽象数据类型图的定义，顶点、弧、有向图、无向图、完全图、有向完全图、稀疏图、稠密图、权、网、子图、邻接点、入度、出度、路径、回路、简单路径、连通、连通图、连通分量、强连通图、生成树、生成森林等概念。2 基本概念和知识点图，抽象数据类型图的定义。3 问题与应用（能力要求）掌握图以及与图有关名词的定义、掌握抽象数据类型图的定义。 第二节 图的存储结构1 主要内容图的多重链表，图的数组表示法，网及其邻接矩阵；图的链式存储结构邻接表、逆邻接表；无向图的链式存储结构邻接多重表。2 基本概念和知识点图的多重链表，图的数组表示法，网及其邻接矩阵；图的链式存储结构邻接表、逆邻接表；无向图的链式存储结构邻接多重表。3 问题与应用（能力要求）掌握图的多重链表，熟悉图的数组表示法。掌握图的链式存储结构邻接表。有向图的链式存储结构十字链表；掌握有向图的链式存储结构十字链表。掌握无向图的链式存储结构邻接多重表。第三节 图的遍历1 主要内容图的遍历概念，遍历图的路径深度优先搜索；遍历图的路径广度优先搜索。2 基本概念和知识点图的遍历，深度优先搜索；广度优先搜索。3 问题与应用（能力要求）掌握深度优先搜索过程。掌握广度优先搜索过程。第四节 图的连通问题1 主要内容利用遍历图的算法求解连通和非连通无向图的连通性问题，无向图的连通分量和生成树的构成方式；求解有向图的强连通分量的步骤；最小生成树问题的概念，构造最小生成树的普里