数据结构教学大纲要点.docVIP

北京师范大学《数据结构》课程教学大纲 一、课程基本信息 中文名称： 数据结构 英文名称：Data Structure 课程类别（公共任选课、学科基础课、专业方向课）：学科基础课 学分： 4 学时： 48+32 建议开设学期：2 开课单位建议：信息科学与技术学院 主讲教师： （姓名） （性别） （职称） （学科方向） 沈复兴 男 教授 计算机软件 郑新 女 副教授 计算机应用 肖永康 男 讲师 计算机应用 二、课程目标： 本课程的主要目标是使学生深入了解数据结构的思想和数据结构的实现方法，特别是 数据结构在实际工作中的应用和技术。本课程追求理论联系实际，实践教学与相应的教学内 容相呼应。在形式上，灵活多样地采取了实践、拓展性学习、报告会等多种形式，目的在于 加深学生对所学内容的理解，发展学生从事发展算法与程序设计研究和实践的能力，努力做 到学以致用，同时激发学生的学习兴趣和主动参与精神，更好地掌握和运用所学习的知识。 三、课程内容与主要学习材料（含教材及参考书目） 课程内容： 第一章 绪论 教学内容: ? 数据结构的一些基本概念：数据、数据元素、数据的逻辑结构、物理结构、算 法等。 ? 抽象数据类型。 ? 描述算法的程序语言（C++）。 ? 算法时间复杂度和空间复杂度的分析。 教学目的及要求 ? 掌握数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、逻 辑结构与物理结构间的关系等数据结构的基本概念； ? 了解数据类型、抽象数据类型、数据抽象和信息隐蔽原则以及面向对象这种数 据抽象实现方法 ? 了解算法的定义、算法的特性、算法的时间代价、算法的空间代价 ? 掌握用 C++语言描述算法的方法，能够使用 C++语言编写程序 教学重点 数据结构的概念；算法分析；C++语言。 学时分配 本章共教授 4 学时. 第二章 数组 教学内容 ? 线性表的基本概念 ? 顺序表：顺序表的定义和特点；顺序表的类定义；顺序表的查找、插入和删除； 使用顺序表的事例；顺序表复杂度分析 ? 特殊矩阵的压缩存储：特殊矩阵定义、稀疏矩阵类定义、矩阵转置与快速转置、 矩阵乘法与输出 ? 字符串：字符串类型定义；字符串操作的实现；字符串的模式匹配 教学目的及要求 ? 了解线性表的逻辑结构特性，以及线性表的两种存储实现方式 ? 熟练掌握顺序表的定义与实现，包括有哪些信誉好的足球投注网站、插入、删除算法的实现及其平均比 较次数的计算，掌握应用顺序表作为集合的简单操作 ? 了解稀疏矩阵的定义及其数组实现 ? 掌握字符串的定义及实现 教学重点 线性表的基本概念、顺序表的实现及应用 教学难点 矩阵的快速转置及模式匹配改进 教学时间分配 本章共教授 4 学时. 第三章 链表 1． 教学内容 ? 单链表：单链表的结构；单链表的类定义；单链表中的查找、插入与删除；带 表头结点的单链表；单链表的游标类及静态链表 ? 循环链表：循环链表的类定义及操作；用循环链表解约瑟夫问题； ? 多项式及其相加：多项式的链表表示类定义；多项式的加法 ? 双向链表：双向链表的类定义及操作 ? 稀疏矩阵：稀疏矩阵的正交链表表示法及建立和删除操作 2． 教学目的及要求 ? 了解链表与数组一样，是一种实现级结构。有动态链表和静态链表之分 ? 了解链表有单链表、循环单链表、双向链表之分 ? 了解单链表的结构、特点 ? 熟练掌握单链表的类定义、构造函数、单链表的查找、插入与删除算法 ? 掌握带表头结点的单链表的优点和类定义及相应操作的实现 ? 了解游标类的定义与实现 ? 掌握循环链表的特点，循环链表的类定义，以及用循环链表解决问题的方法 ? 掌握双向链表的特点，双向链表的类定义及相关操作的实现，用双向链表解决 问题的方法。 ? 了解稀疏矩阵正交链表表示方法 教学重点 单链表、循环链表以及双向链表的类定义、实现及应用 教学难点 实现链表删除与插入操作时指针的变化以及特殊情况处理；稀疏矩阵正交 链表表示方法 5． 教学时间分配 本章共教授 4 学时. 第四章 栈与队列 １． 教学内容 ? 栈：栈的类型定义及特点；栈的顺序存储表示；栈的链接存储表示 ? 栈的应用：回文验证、数制转换及表达式求值（后缀表达式求值；中缀表达式 求值） ? 队列 ：队列数据类型定义及特点；队列的顺序存储表示；队列的链接存储表 示；队列的应用举例 ? 优先级队列：优先级队列的定义；优先级队列的存储表示 ２． 教学目的及要求 ? 熟练掌握栈的定义和特性，栈的顺序表示、链表表示以及相应操作的实现；特 别注意在不同表示方式下栈空和栈满的条件 ? 了解栈的不同应用，掌握后缀与中缀表达式计算方法和算法思路 ? 熟练掌握队列