《数据结构》理论课教学大纲.doc

PAGE 1 PAGE 1 “数据结构”课程教学大纲 课程编号课程名称：数据结构 / Data Structures 学时：48 学分：3 适用专业：计算机相关专业 开课学期：3 开课部门：数学与计算机科学学院 先修课程：C/C++语言程序设计 考核要求：考试 使用教材及主要参考书： 王红梅 编，《数据结构（C++版）（第2版）》，清华大学出版社，2011年 王红梅 编，《数据结构（C++版）学习辅导与实验指导（第2版）》，清华大学出版社，2011年 管致锦、徐慧编，《数据结构》，清华大学出版社，2010年 陈德裕 主编，《数据结构学习指导与习题集》, 清华大学出版社,2010年 徐慧 主编，《数据结构实践教程》, 清华大学出版社,2010年 一、课程的性质和任务 《数据结构》是计算机科学与技术专业本科生的一门必修课程。本课程主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。内容包括：线性表和链表、栈和队列、多维数组、广义表、树和二叉树、图、堆与优先级队列、集合、有哪些信誉好的足球投注网站结构、排序、索引与散列结构等。课程采用面向对象的观点讨论数据结构技术，并以兼有面向过程和面向对象双重特色的C++语言作为算法的描述工具，强化数据结构基本知识和面向对象程序设计基本能力的双重训练。通过本课程的学习，使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为后续计算机专业课程的学习打下坚实的基础。 二、教学目的与要求 1、掌握重要数据结构的概念、使用方法及实现技术； 2、学会做简单的算法分析，包括算法的时间代价和空间代价。 三、学时分配 章节 课程内容 学时 1 绪论 4 2 线性表 6 3 栈和队列 6 4 字符串和多维数组 4 5 树和二叉树 8 6 图 8 7 查找技术 4 8 排序技术 4 9 索引技术 4 四、教学中应注意的问题 本课程是计算机专业基础课，内容多且带有一定的抽象性，学习起来有一定难度。尽可能利用多种媒体进行教学，使学生能够很快掌握课程的主要知识和解决问题的方法。 本课程教学过程中，面授辅导和答疑是必不可少的教学环节。以习题课、专题讨论或答疑的方式，对课程中的重要概念和典型问题的解决方法进行总结和深入讨论，巩固和加深课堂内学到的知识。 　　自学是获取知识的重要手段。教师讲课只是起到抛砖引玉的作用，关键还在于学生的自学。为达到自学的效果，除读懂教科书中所讲内容外，还需大量做题。其目的是要通过做题弄懂、加深对概念的理解，提高程序设计，解决问题的能力。　 除学校提供的时间外，要求课外学生利用自己可能拥有的计算机条件，完成更多的练习，不通过大量的实践，能力和知识水平得不到有效得提高。 五、教学内容 第一章：绪论 1．基本内容 什么是数据结构？抽象数据类型及面向对象概念：数据类型；数据抽象与抽象数据类型；面向对象的概念；描述数据结构的语言数据结构的抽象层次；算法定义；性能分析与度量：算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法；渐进的空间复杂度 2．教学基本要求 了解：什么是数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、逻辑结构与物理结构间的关系 了解：什么是数据类型、抽象数据类型、数据抽象和信息隐蔽原则。了解什么是面向对象 了解：算法的定义、算法的特性、算法的时间代价、算法的空间代价 掌握：用C++语言描述算法的方法，能够使用C++语言编写程序 3．教学重点难点 用C++语言描述算法的方法 4．教学建议 注意使用案例教学法 第二章：线性表 1．基本内容 顺序表：顺序表的定义和特点；顺序表的类定义；顺序表的查找、插入和删除；使用顺序表的事例 单链表：单链表的结构；单链表的类定义；单链表中的插入与删除；带表头结点的单链表；用模板定义的单链表类；静态链表、循环链表：循环链表的类定义；用循环链表解约瑟夫问题； 多项式及其相加：多项式的类定义；多项式的加法 2．教学基本要求 了解：线性表的逻辑结构特性，以及线性表的两种存储实现方式 熟练掌握：顺序表的定义与实现，包括有哪些信誉好的足球投注网站、插入、删除算法的实现及其平均比较次数的计算，掌握应用顺序表作为集合的简单操作 了解：链表与数组一样，是一种实现级结构。有动态链表和静态链表之分 了解：链表有单链表、循环单链表、双向链表之分 了解：单链表的结构、特点 掌握：单链表的类定义、构造函数、单链表的插入与删除算法 了解：带表头结点的单链表的优点和类定义及相应操作的实现 熟练掌握：用模板定义的单链表类 了解：循环链表的特点，循环链表的类定义，以及用循环链表