《算法与数据结构》导学大纲.docxVIP

《算法与数据结构》教学大纲 一、使用说明 （一）课程性质 《数据结构》是一门专业基础课，在计算机软件的各个领域中均会使用到数据结构的有关知识。本课程的先修课程为C程序设计或C++程序设计。 （二）教学目的 学会从问题入手，分析研究计算机加工的数据结构的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作算法，并初步掌握时间和空间分析技术。另一方面，本课程的学习过程也是进行复杂程序设计的训练过程，要求学生会书写符合软件工程规范的文件，编写的程序代码应结构清晰、正确易读，能上机调试并排除错误。 （三）教学时数 课堂讲授每周4学时，18周，共72学时。 （四）教学方法 本课程将采用课堂讲授及课堂讨论相结合的交互式教学法，同时辅以必要的上机操作实践。 （五）面向专业 计算机科学与技术专业。 二、教学内容 第一章 绪论 （一）教学目的要求 介绍数据结构的一些基本概念，算法的时间复杂度和空间复杂度的分析方法，抽象数据类型的定义和使用以及算法的描述方法。掌握数据结构的一些基本概念，掌握算法的时间复杂度和空间复杂度的分析方法，了解抽象数据类型的定义和使用，了解算法的描述方法。 （二）教学内容 主要内容：数据结构的一些基本概念：数据、数据元素、数据逻辑结构、数据存储结构、数据类型、算法等。抽象数据类型。算法时间复杂度和空间复杂度的分析。 教学重点：有关数据结构的各个名词和术语的含义，以及语句频度和时间复杂度、空间复杂度的估算。 教学难点：算法时间复杂度和空间复杂度的分析。 什么是数据结构 一、非数值计算 二、数据结构课程内容的历史演变 三、数据结构研究范围 基本概念和术语 一、数据 二、数据结构 三、数据类型 四、抽象数据类型 五、多型数据类型 抽象数据类型的表示与实现 一、固有数据类型 二、数据抽象 三、抽象数据类型的描述语言 算法和算法分析 一、算法 二、算法设计的要求 三、算法效率的度量 四、算法的存储空间需求 （三）教学方法与形式 课堂讲授、多媒体课件。 （四）教学时数 4学时。 第二章 线性表 （一）教学目的与要求 介绍线性表的基本概念和类型定义，对顺序表和单链表的常用操作方法及其程序实现，循环链表和双向链表的定义和它的插入、删除等操作方法。掌握线性表的基本概念和类型定义；熟练掌握对顺序表和单链表的常用操作方法及其程序实现；掌握循环链表和双向链表的定义和它的插入、删除等操作方法。 （二）教学内容 主要内容：线性表的基本概念和类型定义， 线性表的顺序存储结构， 线性表的链接存储结构：（1）单链表的查找、插入和删除；（2）循环链表；（3）双向链表。 教学重点：在顺序表和链表上各种基本算法的实现及相关的时间性能分析。 教学难点：用所学的基本知识设计有效算法解决与线性表相关的应用问题。链表要分清链表中指针p和结点*p之间的对应关系，区分链表中的头结点、头指针以及循环链表、双向链表的特点等。 线性表的类型定义 一、线性表的定义 二、线性表的基本操作 线性表的顺序存储表示和实现 一、顺序表 二、顺序表上基本运算的实现 三、顺序表应用举例 线性表的链式存储表示和实现 一、线性链表 二、循环链表 三、双向链表 四、静态链表 一元多项式的表示及相加 一、一元多项式的数学表示 二、一元多项式的计算机表示 三、抽象数据类型：一元多项式的定义 四、抽象数据类型：一元多项式的存储结构 五、抽象数据类型：一元多项式的基本操作算法实现 （三）教学方法与形式 课堂讲授、多媒体课件。 （四）教学时数 8学时。 第三章 栈和队列 （一）教学目的与要求 介绍栈和队列的定义，顺序和链接存储的栈和队列的各种运算的方法及其程序实现。掌握栈和队列的定义，熟练掌握顺序和链接存储的栈和队列的各种运算的方法及其程序实现。 （二）教学内容 主要内容：栈的类型定义，栈的顺序存储和链接存储的表示，在栈的顺序存储和链接存储上进行各种栈操作的算法，栈的应用举例，队列的类型定义，队列的顺序存储(循环队)和链接存储表示及各种操作的实现算法。 教学重点：栈和队列在两种存储结构上实现的基本运算。 教学难点：递归的实现、循环队列中对边界条件的处理。 栈 一、抽象数据类型栈的定义 二、栈的表示和实现 栈的应用举例 一、数制转换 二、括号匹配的检验 三、表达式求值 栈与递归的实现 一、函数调用与栈 二、递归调用栈的变化 队列 一、抽象数据类型队列的定义 二、链队列--队列的链式表示和实现 三、循环队列--队列的顺序表示和实现 优先级队列 一、优先级队列的概念 二、优先级队列的存储表示和实现 （三）教学方法与形式 课堂讲授、多媒体课件。 （四）教学时数 4学时。 第四章 串 （一）教学目的与要求 介绍串的基本概念和操作，串的存储结构以及基本操作的算法实现。掌握串的基本概念