《数据结构》教学大纲

课程大纲西北大学《数据结构》-13-国家精品课程西北大学《数据结构》教学大纲2012-2013学年第1学期含课堂教学大纲、实训大纲、实验大纲等，以纲要形式规定课程的教学内容，具体应包括课程的教学目的、教学任务、教学内容的结构、模块或单元教学目标与任务、教学活动以及教学方法上的基本要求等。

目录1课程大纲 -1-1.1课程描述 -1-1.2课程目标 -2-1.3先修课程 -2-1.4后续课程 -2-1.5教学时数 -2-1.6教学方式 -2-1.7教学内容 -3-1.8学时分配表 -9-1.9参考文献 -9-2实验大纲 -10-2.1实验目的 -10-2.2实验要求 -10-2.3实验内容 -11-2.4实验考核方式 -12-

1课程大纲1.1课程描述数据结构及其处理算法是设计与实现系统软件和大型应用软件的重要基础，“数据结构与算法”课程是计算机专业重要的专业技术基础课程。该课程的内容对于培养学生的计算思维、系统分析与设计、算法设计与分析、程序设计与实现等学科基本能力非常重要。本课程系统地介绍了软件开发中常用的数据结构以及相应的存储结构和操作算法，包括常用的查找技术、排序技术、递归技术等。1.2课程目标掌握“数据结构”中的基本概念、合理组织数据的基本方法、高效处理数据的基本算法、常用的经典算法、通用的程序设计技术，以及面对实际问题时选择恰当数据结构并设计高效算法的能力，培养学生用计算思维分析问题的能力，提高学生上机解决较大规模实际问题的能力，为进一步的软件开发打下坚实的基础。1.3先修课程离散数学，计算机导论，高级语言程序设计。1.4后续课程数据结构与算法课程设计。1.5教学时数72小时课堂教学和18小时实验教学；1.6教学方式“数据结构与算法”是理论与实践并重的课程，采用理论教学和上机训练相结合的教学方式。在理论教学方面，以课堂讲授为主，同时借助网络教学平台，拓展课堂讲授的相关知识，便于同学自主学习、巩固课堂所学内容。课堂讲授采用多媒体课件，用FLASH动画形象地展示抽象算法的处理过程。书面作业是消化掌握课堂知识的重要环节，是培养计算思维的重要手段，是上机训练的前提条件。每章应布置一定数量的书面作业，其难度和覆盖面应该恰当。可根据学生作业情况，组织若干次独立的习题课，针对学生作业中出现的典型问题进行综合讲评。另外，还可以不定期地进行课堂小测验（15分钟左右）。在上机训练方面，根据教学目标，设计出规模适当、难度适中，实用性和趣味性兼顾的上机题目。上机题目分为三类：第一类是为了验证当前所学知识点的验证性实验，第二类是为了运用多个相关知识点解决问题的综合性实验，第三类是为了灵活运用所学知识解决实际问题的设计性实验（后续课程：数据结构与算法课程设计）。要求学生完成数据结构和相关算法的设计，并上机调试实现，最后提交规范的实验报告。针对不同基础的学生，教师应该提供不同的上机指导。1.7教学内容绪论本章讨论数据结构的基础知识，包括相关概念、算法基础与问题求解方法。1.1相关概念一级知识点二级知识点掌握程度数据数据元素，数据对象掌握数据结构逻辑结构，存储结构，运算熟练掌握数据类型基本数据类型，抽象数据类型掌握1.2算法基础一级知识点二级知识点掌握程度算法概念与描述方法算法定义，算法设计要求，算法描述方式，算法描述规范要点，用高级语言实现抽象数据类型，算法设计风格，高级语言中参数传递和结果返回的相关技术掌握算法设计基本方法穷举法，分治法，回溯法，贪心法，动态规划法了解算法分析大O表示法，渐进分析，最佳、最差和平均时间复杂度，时间和空间的折衷掌握1.3问题求解方法一级知识点二级知识点掌握程度问题分析与抽象问题抽象，数据结构抽象，算法抽象掌握系统设计数据结构设计，算法设计掌握线性结构本章讨论线性结构的定义、存储结构、基本操作及其应用。2.1线性表一级知识点二级知识点掌握程度线性表顺序表（数组）的存储结构与基本操作熟练掌握单链表的存储结构与基本操作熟练掌握双链表的存储结构与基本操作熟练掌握循环链表的存储结构与基本操作熟练掌握静态链表的存储结构与基本操作了解顺序存储结构和链式存储结构的优缺点比较熟练掌握2.2栈和队列一级知识点二级知识点掌握程度栈顺序栈、链栈栈的应用（表达式求值和转换）熟练掌握栈与递归（递归实现机制、递归到非递归转换）初步掌握队列链队列、循环队列的实现，利用队列进行排队问题求解熟练掌握字符串字符串存储结构与简单匹配操作实现掌握字符串的快速模式匹配算法（KMP算法）初步掌握2.3字符串一级知识点二级知识点掌握程度字符串字符串存储结构与简单匹配操作实现掌握字符串的快速模式匹配算法（KMP算法）初步掌握2.4扩展线性结构一级知识点二级知识点掌握程度多维数组多维数组的顺序存储掌握特殊矩阵（三角矩阵、对称矩阵、对角矩阵、稀疏矩阵）的压缩存储掌握稀疏矩阵的三元组存储和十字链表存储了解广义表广义表的存储结构，广义表的简单操作了解二叉树、树与森林本章讨论树结构的定义、存储结构、基本操作及其应用。3.1二叉树一级知识点二级知识点掌握程度二叉树概念二叉树的递归定义，二叉树的性质，二叉树的有关术语熟练掌握二叉树的存储结构二叉树的顺序存储结构熟练掌握二叉链表熟练掌握三叉链表，静态三叉链表熟练掌握二叉树的遍历方法及其应用前序遍历，中序遍历，后序遍历，层次优先遍历；由遍历序列确定二叉树等熟练掌握递归遍历算法到非递归遍历算法的转换方法，非递归遍历算法掌握线索二叉树线索二叉树的建立与使用了解二叉树应用Huffman树（贪心法构造）利用Huffman树进行编码解码熟练掌握3.2树与森林一级知识点二级知识点掌握程度树的存储结构树的链式存储（孩子兄弟链表，孩子链表，父指针表示法）掌握树、森林与二叉树的关系树与森林的递归定义，森林与二叉树的对应关系及其转换方法掌握树的遍历（先根遍历、后根遍历、广度优先遍历）森林的遍历（前序遍历、中序遍历、后序遍历）掌握K叉树了解图结构本章讨论图结构的定义、存储结构、基本操作及其应用。4.1图的概念一级知识点二级知识点掌握程度图的概念顶点，边，权，入度，出度，有向图，无向图，稀疏图，稠密图，子图，路径，简单路径，简单回路，无环图，有向无环图（DAG），连通图，强连通图，带权图掌握4.2图的存储结构一级知识点二级知识点掌握程度图的存储结构邻接矩阵熟练掌握邻接表熟练掌握逆邻接表，十字链表，邻接多重表了解4.3图的遍历方法一级知识点二级知识点掌握程度图的遍历图的深度优先遍历熟练掌握图的宽度优先遍历熟练掌握图的生成树，生成森林掌握4.4图的经典算法一级知识点二级知识点掌握程度有向无环图拓扑排序掌握关键路径掌握最小生成树Prim算法（贪心法）掌握Kruskal算法（贪心法）掌握最短路径Dijkstra算法（贪心法）掌握Floyd算法(动态规划法)掌握查找技术本章讨论常用的查找技术。5.1查找基本概念与基于线性表的查找一级知识点二级知识点掌握程度查找基本概念查找某个结点的比较次数，平均查找长度掌握顺序表查找采用监视哨的顺序查找熟练掌握折半查找，折半判定树熟练掌握分块查找索引表查找和块内查找的二级查找掌握5.2基于树结构的查找一级知识点二级知识点掌握程度二叉搜索树二叉搜索树的定义与查找过程，二叉搜索树结点的插入与删除；熟练掌握扩展二叉搜索树平衡二叉树（AVL）初步掌握红黑树了解多路查找树m路查找树掌握B树的定义B树的查找、插入、删除操作初步掌握B+树的定义B+树的查找、插入简介字符树了解5.3散列查找一级知识点二级知识点掌握程度散列查找散列函数(除留余数法)冲突处理方法(线性探测法、同义词链表法)散列表的查找、构建算法，平均查找性能分析熟练掌握同义词，碰撞，二次聚集散列函数(平方取中法、折叠法)冲突处理方法(二次探测法、伪随机探测法、双散列函数)掌握内部排序本章讨论常用的排序技术。一级知识点二级知识点掌握程度基本概念数据记录，关键字，正序，逆序，稳定性，待排序表的结构（向量、链表、地址表结构）掌握插入排序法直接插入排序熟练掌握Shell排序掌握交换排序法冒泡排序熟练掌握快速排序（分治法）熟练掌握选择排序法直接选择排序熟练掌握堆排序掌握归并排序二路归并（分治法）掌握分配排序桶排序，基数排序（链式、顺序）初步掌握排序算法分析时间代价：记录的比较和移动次数空间代价：辅助数据空间大小排序问题的下限掌握外部排序一级知识点二级知识点掌握程度概念主存储器，外存储器，缓冲区，顺串了解排序算法置换选择排序多路归并(胜方树、败方树)最佳归并树多路归并的读盘和写盘次数了解文件组织技术一级知识点二级知识点掌握程度索引文件ISAM,VSAM初步掌握散列文件桶，基桶，溢出桶初步掌握倒排表次关键字，倒排索引，基于属性的检索初步掌握1.8学时分配表序号内容授课学时上机学时1概论基础32线性表633栈和队列534字符串225数组和广义表526树形结构及其应用1047图结构及其应用848查找技术639内部排序6310外部排序与文件组织301.9参考文献耿国华等，《数据结构》，西安电子科技大学出版社，2002.2。耿国华等，《数据结构（第2版）》，西安电子科技大学出版社，2008.7。耿国华等，《数据结构-C语言描述》及随附教学光盘，高等教育出版社，2005.7。耿国华等，《数据结构-C语言描述(第2版)》及随附教学光盘，高等教育出版社，2011.6。严蔚敏等，《数据结构（C语言版）》，清华大学出版社，2007.3。RobertL.Kruse，《DataStructuresandProgramDesigninC++》，高等教育出版社（影印版），2001.5。MarkWeiss，《DataStructuresandAlgorithmAnalysisinC(3rdedition)》，AddisonWesley，2005.11。SartaSahni，《DataStructures,Algorithms,andApplicationsinC++》，McGraw-Hill，2003。EllisHorowitz，《FundamentalsofDataStructuresinC》，SiliconPress，2007.8。张铭，王腾蛟，赵海燕，《数据结构与算法》，高等教育出版社，2008.6。北京大学《数据结构与算法》国家精品课程网站，/pkujpk/course/sjjg/殷人昆，数据结构（用面向对象方法与Ｃ＋＋描述），清华大学出版社，2007.6。D.E.Knuth,theartofcomputerprogrammingvolume1/fundamewfalalgorithms,ThirdEdition(Reading,Massachusetts:Addison-Wesley,1997);volume3/sortingandsearching,SecondEdition(Reading,Massachusetts:Addison-Wesley,1998)格里斯，程序设计方法技巧，第三卷。2实验大纲2.1实验目的“数据结构与算法”是计算机专业一门重要的专业技术基础课程，由于本课程的技术性与实践性，课程实验的设置十分必要。上机实习是对学生的一种全面综合训练，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的技术，提高计算思维能力。在掌握基本数据结构和基本算法的基础上，提高学生的分析、设计、编码和调试能力，为进一步的软件开发打下坚实基础。2.2实验要求根据教学目标，设计出规模适当、难度适中，实用性和趣味性兼顾的上机题目。上机题目分为三类：第一类是为了验证当前所学知识点的验证性实验，第二类是为了运用多个相关知识点解决问题的综合性实验，第三类是为了灵活运用所学知识解决实际问题的设计性实验（课程设计）。针对不同基础的学生，教师应该提供不同的上机指导。要求学生在认真分析问题的基础上，完成数据结构和相关算法的概要设计和详细设计，然后编码并上机调试，最后提交规范、统一的实验报告。在实验结束前，教师要注意现场验收学生设计实现的系统，并给出现场评定。评定级别分优秀、良好、合格、不合格，最后结合实验报告给出实验成绩。实验学时为18机时。2.3实验内容要求完成以下六个题目：实习一约瑟夫环问题（2机时）用循环链表实现约瑟夫环问题，熟悉链表结构的使用。实习二停车场管理（4机时） 利用栈和队列模拟停车场管理，学习利用栈和队列解决实际问题。实习三二叉树基本操作（2机时）创建、遍历、插入、删除、显示二叉树，通过二叉树的基本操作，掌握树结构的处理方法。实习四图的基本操作（4机时）分别用邻接矩阵和邻接表实现以下操作：图的创建、遍历、插入、删除、最短路径。熟悉图的常用存储结构和基本操作。实习五哈希表设计（3机时）给定30个人的姓名，用除留余数法构造哈希函数，用线性探测再散列法处理冲突，构造哈希表，掌握哈希表的设计与使用。实习六常用排序算法的对比分析（3机时）分别实现直接插入排序、冒泡排序、简单选择排序、希尔排序、快速排序、堆排序，并随机生成50个数，比较各算法的时、空性能和稳定性。掌握常用排序算法的特点，以便根据实际情况选择使用。2.4实验考核方式实验考核采用上机表现、程序质量、实验报告质量相结合