23数据结构与算法实验.docxVIP

?数据结构与算法?课程教学大纲 一、课程根本情况 开课学院：信息科学与工程学院 英文名称：Data Structures and Algorithms 适用专业：计算机科学与技术专业 课程类别：专业教育平台必修课 课程修读条件：高级语言程序设计C、离散数学 网络课程地址: 课程负责人：赵杰煜 所属基层学术组织：移动计算与人机交互研究所 二、课程简介 “数据结构与算法〞是计算机程序设计的重要理论技术根底，是计算机学科的核心课程。本课程是一门专业必修课。课程通过讨论数据的各种逻辑结构、物理结构以及相关算法，使学生能根据实际问题的需要选择适宜的数据结构、设计合理高效的算法，为进一步学习后继专业课程打下根底。 本课程重点介绍如何组织各种数据在计算机中的存储、传递和转换等技术，通过对线性结构、树型结构和图形结构进行全面介绍，分析数据对象的特性，选择适当的数据结构，设计高效率的数据处理算法。 三、教学目标 本课程的教学目标：学会分析研究计算机加工的数据结构的特性，掌握各类数据结构的灵活应用，为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并掌握算法的时间复杂度和空间复杂度的简要分析技术。 通过本课程的学习，重点掌握以下内容：复杂度分析、链表、栈和队列、递归、二叉树、B-树、图、最大流与最小割、堆与优先级队列、排序、Hashing、数据压缩等。使学生深透地理解数据结构的根本概念以及有关算法，进行复杂程序设计的训练，提高抽象设计能力。培养良好的程序设计技能，编写的程序正确高效、结构清晰易读，通过编程提高解决实际问题的能力。 四、教学内容及学时分配 课程针对重点难点问题，均配有综合性设计训练，使学生深入透彻地了解课堂教学内容，如递归应用、二叉树应用、最短路径和关键路径、网络最大流最小割、各种高效率排序算法等,均单独设置综合工程设计Case Study，深入浅出地介绍难点内容。在理论课时之外, 安排一定的自主学习与交流，并配备专门指导教师。 章节 根本内容 学时分配 教学方法 综合工程设计任务 Chapter 1 Object-Oriented Programming Using C++ 1．Data Structure Notation 2．Abstract Data Types 3．Encapsulation 4．Inheritance 5．Pointers 6．The Standard Template Library 2 课堂讲授 Chapter 2 Complexity Analysis 1．Computational and Asymptotic Complexity 2．Big-O Notation, Ω and Θ Notation 3．Properties of Big-O Notation 4．The Best, Average and Worst Cases 3 课堂讲授 Chapter 3 Linked Lists 1．Singly Linked Lists 2．Doubly Linked Lists 3．Circular Lists 4．Skip Lists 5．Self-Organizing Lists 6．Sparse Tables 3 课堂讲授 Case Study: Person List Chapter 4 Stacks and Queues 1．? Stacks 2．? Queues 3．? Priority Queues 4．? Stacks and Queues in the Standard Template library 4 课堂讲授 Case Study: Calculator Chapter 5 Recursion 1．? Recursive Definitions 2．? Function Calls and Recursion Implementation 3．? Anatomy of a Recursive Call 4．? Tail Recursion 5．? Nontail Recursion 6．? Indirect Recursion 7．? Nested Recursion 7 课堂讲授 Case Study: Backtracking Chapter 6 Binary Trees 1．? Trees, Binary trees, and Binary search trees 2．? Implementing Binary trees 3．? Searching a Binary Search Tree 4．? Tree Traversal 5．? Insertion and Deletion 6． ?AVL Trees 7．