搜索
1《数据结构》课程教学大纲课程编号：806302024课程名称：数据结构英文名称：DataStructure课程类型：专业基础课总学时：72讲课学时：56实验学时：16学时：72学分：4.5适用对象：计算机科学与技术专业本科生先修课程：C/C++语言程序设计、Java语言程序设计、离散数学一、课程性质、目的和任务数据结构课程是计算机科学与技术专业本科学生必修的一门专业基础课程。数据结构是软件设计的重要理论和实践基础，数据结构设计和算法设计是软件系统设计的核心。数据结构课程的任务是，讨论数据的各种逻辑结构、在计算机中的存储结构以及各种操作的算法设计。数据结构课程的主要目的是，培养学生掌握处理数据和编写高效率软件的基本方法，为学习后续专业课程以及进行软件开发打下坚实基础。二、教学基本要求数据结构是理论与实践并重的课程，既要掌握数据结构的基础理论知识，掌握算法设计和分析方法，熟练运用一种程序设计语言编制具有中等难度的应用程序；也要掌握运行和调试程序的基本技能，在实践中培养独立分析问题和解决问题的作风和能力。本课程采用Java语言及面向对象程序设计方法描述数据结构和算法。本课程教学的基本要求说明如下。1．理解线性表、串、栈、队列、数组、广义表、树、二叉树、图、散列表等数据结构的基本概念，掌握它们的存储结构及各种操作的实现方法。2．理解各种数据结构的查找操作要求，掌握在线性表、二叉树中采用的查找算法及查找效率分析方法。掌握插入、交换、选择、归并等排序算法，掌握排序算法效率分析方法。3．熟练运用Java语言及面向对象程序设计方法描述各种抽象数据类型，表达它们的存储结构，实现在各存储结构上的各种操作。掌握递归算法设计方法。4．掌握在MyEclipse集成开发环境中编辑、编译、运行和调试程序的方法，具备运行和调试程序的基本技能，能够发现程序错误、及时找到错误所在并改正错误，重点和难点是运用单步运行、设置断点、查看变量运行时值等程序调试技术，发现并改正程序逻辑错误。2三、教学内容及要求1．绪论①了解数据结构的基本概念，了解数据的逻辑结构、数据的存储结构和数据操作，了解抽象数据类型与数据结构的关系。②了解算法、算法描述、算法设计目标和算法分析方法，掌握算法的时间复杂度和空间复杂度的分析方法。2．线性表①理解线性表的逻辑结构和基本操作，掌握线性表抽象数据类型的描述方法。②掌握线性表的顺序存储结构和实现方法。③掌握线性表的链式存储结构及其特点，掌握实现单链表、循环单链表、双链表、循环双链表基本操作的设计方法。比较两种存储结构的特点和性能。3．串①理解串的概念和串的基本操作，熟悉串的顺序存储结构和链式存储结构。②掌握串的定义和基本操作的实现方法。③掌握两种串的模式匹配算法：Brute-Force算法和KMP算法。4．栈和队列①理解栈的概念和作用，掌握顺序栈和链式栈的设计方法，熟悉使用栈的算法设计方法。②理解队列的概念和作用，掌握顺序循环队列和链式队列的设计方法，熟悉使用队列的算法设计方法。熟悉优先队列的概念、设计和使用方法。③理解递归定义，掌握递归算法设计方法。5．数组和广义表①理解数组的概念，理解一维数组和二维数组的存储结构。②熟悉三角矩阵等特殊矩阵的压缩存储方法；熟悉稀疏矩阵的各种压缩存储方法，包括稀疏矩阵三元组顺序表、单链表、行/列的单链表和十字链表存储结构。③理解广义表的概念，熟悉广义表双链表示的存储结构和操作实现。6．树和二叉树①理解树的定义、术语、表示方法、遍历规则和多种存储结构，掌握采用树的孩子兄弟链表存储树并实现树的遍历、插入、删除等操作。②理解二叉树的定义、性质、遍历规则和存储结构，掌握采用二叉链表或三叉链表存储结构存储二叉树的特点，掌握二叉树的遍历、构造、插入、删除等操作算法，比较二叉树遍历的递归算法与非递归算法的特点。③理解线索二叉树概念，熟悉其存储结构，掌握中序线索二叉树的遍历、线索化、求后继结点、插入等基本操作算法。④理解Huffman编码在数据压缩中的作用，理解Huffman树的概念，掌握Huffman算3法实现构造Huffman树。7．图①理解图的基本概念和术语。②掌握图的邻接矩阵和邻接表存储结构。③实现图的深度优先遍历和广度优先遍历算法。④理解最小生成树的概念，掌握两种构造图的最小生成树算法：Prim和Kruskal算法。⑤理解最短路径问题的概念，熟悉求单源最短路径的Dijkstra算法和求所有最短路径的Floyd算法。8．查找①理解查找的基本概念和查找算法效率的分析方法。②掌握线性表的顺序查找、有序顺序表的折半查找、索引顺序表的分块查找算法。③理解散列表的概念，熟悉散列函数的构造方法，熟悉解决冲突的多种方法，掌握链地址法散列表的构造、插入、删除、查找等操作算法。④理解二叉排序树的概念和作用，掌握二叉排序树的查找、插入和删除等操作算法；了解平衡二叉树的基本概念和保持平衡性的调整规则。9．排序①理解排序的基本概念和排序算法效率的分析方法。②掌握直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序算法；比较各排序算法的特点、算法设计思想和适用的存储结构，分析各排序算法的时间效率和空间效率。四、教学方法与手段数据结构课程是一门理论和实践相结合的课程，既要注重理解基本知识，也要注重培养软件设计的基本技能。本课程讲授基本的数据结构和经典算法，比较各种数据结构的特点，分析算法的设计思想及算法性能。课堂上除了讲授基本概念和算法以外，需要适时地穿插进行课堂练习，及时指出并分析学生所写程序的错误性质及改正方法。课后还需要让学生进行大量的程序设计训练。本课程的课堂教学采用板书与多媒体相结合的方式进行，其中，MyEclipse环境的使用和程序运行需要采用多媒体的方式进行演示。五、课外习题及课程讨论本课程通过课堂讲授例题、课堂练习、课后习题、上机实验以及课程设计等各个实践环节，对学生进行系统的程序设计训练。所有例题、课堂练习题、课后习题、上机实验题都是精心挑选的，由浅入深，环环相扣，步步推进，调动学生的主动性和自觉性并培养学生写程4序的兴趣。除了课内安排的习题课、课堂讨论、期中测验、复习课以外，每次课后都要求学生做至少2个完整的程序，并定期检查学生做作业的情况，作业的数量和质量占平时成绩的一部分。六、各教学环节学时分配本课程学时为72，其中讲课56学时，实验16学时。学时分配见下表。章节（或内容）讲课实验合计绪论33线性表8210串426栈和队列66数组和广义表426树和二叉树10414图8210查找628排序527复习22合计561672七、实践环节实践环节是巩固所学理论知识、使理论与实际相结合、提高程序设计能力和计算机操作能力的重要环节。上机实验和课程设计等都是加强程序设计训练所必需的。本课程安排的上机实验学时为16学时，课内开设的8个实验见下表。项目内容实验时数实验1线性表的基本操作（设计型）2实验2串的基本操作及模式匹配算法（设计型）2实验3栈和队列及其应用；数组和广义表2实验4二叉树的基本操作（设计型）2实验5线索二叉树、Huffman树和树2实验6图的表示和操作2实验7查找算法设计及分析（设计型）2实验8排序算法设计及分析2要求学生每次实验前预习并写出程序草稿；程序运行通过并修改完善；对于设计型实验，写出实验报告。八、考核方式本课程为考试课程，期末考试为闭卷笔试。学生的课程总评成绩由平时成绩（占30%）和期末考试成绩两部分构成，平时成绩中实验成绩占20%，出勤、作业、课堂测验、学习主动性等占10%。实验成绩根据实验程序运行情况和实验报告质量评定，作业成绩根据习5题的数量和质量评定。九、推荐教材和教学参考书教材：《数据结构（Java版）（第3版）》，叶核亚编著，电子工业出版社，2011年，“普通高等教育“十一五”国家级规划教材”。参考书：《数据结构（C语言版）》，严蔚敏等编著，清华大学出版社，1997年。《数据结构（用面向对象方法与C++描述）（第2版）》，殷人昆等编著，清华大学出版社，2007年。十、说明本课程另设一周课程设计。大纲制订人：叶核亚大纲审定人：制订日期：2011年8月21日6《数据结构》课程实验教学大纲课程编号：806302024课程名称：数据结构英文名称：DataStructure课程类型：专业基础课课程属性：课内实验总学时：72讲课学时：56实验学时：16开设学期：第4学期适用专业：计算机科学与技术专业本科一、实验教学目标与基本要求数据结构课程是计算机科学与技术专业本科学生必修的一门专业基础课。数据结构课程是一门理论和实践相结合的课程，既要注重理解基本知识，也要注重培养软件设计的基本技能。上机实验、课程设计等实践环节是巩固所学理论知识、使理论与实际相结合、提高程序设计能力和计算机操作能力所必需的重要环节。上机实验的基本要求是，熟练运用数据结构的基础理论和算法设计的基本原则，采用Java语言独立设计针对各章节基础知识的应用程序，运行程序并获得正确结果，积累程序设计经验。掌握在MyEclipse集成开发环境中编辑、编译、运行和调试程序的方法。二、本实验课程的基本理论与实验技术知识1．数据结构的基础理论，分析数据所具有的逻辑结构，采用合适的存储结构存储数据，设计对数据进行各种操作的算法。2．算法设计的基本原则，算法必须达到正确性、健壮性、高时间效率、高空间效率及可读性等基本目标。3．MyEclipse集成开发环境提供编辑、编译、运行和调试程序的工具。三、实验方法、特点与基本要求1．验证教材中的已有算法，给出多种运行结果并分析比较，深入理解并巩固数据结构的基础理论和算法设计的基本原则。2．熟练运用数据结构的基础理论和算法设计的基本原则，采用Java语言独立设计针对各章节基础知识的应用程序，运行程序并获得正确结果；分析运行结果，分析算法效率及性能，给出提高算法效率的解决方法，积累程序设计经验。73．掌握在MyEclipse集成开发环境中编辑、编译、运行和调试程序的方法，具备运行和调试程序的基本技能，能够发现程序错误、及时找到错误所在并改正错误，重点和难点是运用单步运行、设置断点、查看变量运行时值等程序调试技术，发现并改正程序逻辑错误。四、实验主要仪器设备计算机。五、实验项目的设置与内容提要本实验课程学时为16，开设的8个实验说明如下，实验要求是每组1人、必做。序号实验项目内容提要实验学时实验类型1线性表的基本操作实现线性表的顺序存储结构和链式存储结构下的基本操作，重点是单链表的插入、删除、复制等基本操作。2设计2串的基本操作及模式匹配算法实现顺序存储的串的基本操作，熟悉Brute-Force和KMP模式匹配算法。2设计3栈和队列及其应用；数组和广义表掌握顺序栈和链式栈的设计及使用方法；掌握顺序循环队列和链式队列的设计及使用方法；使用数组存储矩阵；实现广义表双链表示的基本操作。2验证4二叉树的基本操作以二叉链表存储二叉树，掌握基于遍历的多种操作算法，掌握构造二叉树的多种算法。2设计5线索二叉树、Huffman树和树建立中序线索二叉树；验证Huffman算法；以孩子兄弟链表存储树，熟悉树的遍历、插入等算法。2验证6图的表示和操作以邻接矩阵或邻接表存储带权图，实现图的构造、深优先遍历和广度优先遍历等算法，构造最小代价生成树，求最短路径。2验证7查找算法设计及分析顺序查找，折半查找，分块查找；构造散列表并查找；构造二叉排序树并查找。2设计8排序算法设计及分析实现直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序算法，比较排序算法特点并给出性能评价。2验证六、实验报告要求实验报告内容包括：实验目的和要求、题目、题目说明、题意分析、功能说明、实现技术和手段、流程描述、源程序清单、程序运行结果及结果分析、程序存在问题和改进意见等。七、考核方式与成绩评定标准实验成绩：程序运行结果及分析50%、实验报告50%。8八、教材及主要参考资料教材：《数据结构（Java版）（第3版）》，叶核亚编著，电子工业出版社，2011年，“普通高等教育“十一五”国家级规划教材”。参考书：