《数据结构（一）》课程教学大纲

1、4/4数据结构课程教学大纲英文名称Data Structure课程代码EDUE2012课程性质必修课授课对象教育技术学学 分3.5学 时72（54+18）课程简介在学习了一门程序设计课程之后，要想深入学习编程，数据结构是必要的通关课程。该课程从比较抽象的视角分析数据的逻辑结构、存储结构及相关算法的实现。课程性质与目的作为计算机相关专业的一门核心基础课，数据结构的研究对象主要是数据的逻辑结构、数据的物理存储结构及对数据的操作（算法）等三个方面。通过该课程的学习，要求学习者能够掌握常用的线性结构和非线性结构的基本概念、存储表示和基于不同存储基础上的基本操作的实现方法，学会分析各种算法在时间和空间上

2、的效率等。在此过程中，培养更加严谨的逻辑推理能力，为编写出高质量程序打下良好基础。教学内容与学时分配C语言复习（3+2学时）教学内容以一个实验题为切入点，带领学生复习相关知识点：基本输入输出语句的使用、结构体的定义、结构体类型的声明、结构体变量的定义、结构体数组、常用算法、函数的调用等。教学要求复习C语言相关知识点，为数据结构的学习做好准备。重点结构体的相关内容难点无数据结构概述（3学时）教学内容数据结构的起源、基本概念和术语、抽象数据类型、算法与算法分析、学习提示教学要求让学生初步建立对数据结构的认识：研究什么、为什么学习、怎么学习。重点什么是数据结构难点无线性表（6+4学时）教学内容线性表

3、的基本概念、顺序存储及操作的实现、链式存储及操作的实现教学要求让学生了解线性表的逻辑结构、存储结构，并尝试在不同存储结构上实现线性表的基本操作：建表、查找、插入和删除元素。重点基本操作的实现难点链式存储上的建表操作栈与队列（3+2学时）教学内容栈基本概念、顺序栈和链栈上操作的实现、栈的应用队列基本概念、顺序队列（循环队列）上操作的实现、链队列教学要求让学生了解操作受限的两个线性表：栈和队列，并掌握栈的基本操作及应用。重点栈的应用难点无串（3+2学时）教学内容串的基本概念、串的顺序存储及基本操作、串的链式存储、串的模式匹配算法教学要求让学生了解另一种特殊的线性表串（所有数据元素均为字符），掌握串

4、的基本操作及串的模式匹配算法。重点串的模式匹配算法难点无数组和广义表（3+2学时）教学内容数组的定义、数组的顺序存储、矩阵的压缩存储、广义表教学要求让学生了解两种线性结构向非线性结构的过渡形式：数组和广义表，掌握两种特殊矩阵（对称矩阵和稀疏矩阵）的压缩存储。重点矩阵的压缩存储难点无树和二叉树（9+2学时）教学内容树的基本概念、树的存储结构、二叉树的概念与性质、二叉树的存储结构、遍历二叉树、线索二叉树、树和森林与二叉树的互换、赫夫曼树（最优二叉树）教学要求让学生了解树型结构的逻辑特征，掌握二叉树的相关知识点并能够在计算机上实现二叉树的基本操作。重点二叉树的性质、存储、遍历难点线索化二叉树图（6+

5、2学时）教学内容图的基本概念、图的存储结构、图的遍历、连通网的最小生成树教学要求让学生了解图的逻辑特征，掌握图的邻接矩阵存储和邻接表存储两种方法，并在此基础上实现图的建立和遍历算法，初步了解最小生成树。重点图的两种存储方式及相应操作的实现难点邻接表存储图的实现查找（9学时）教学内容查找的基本概念、静态查找表、动态查找表、哈希表教学要求让学生全面了解各种不同的查找算法：理解算法原理、掌握算法实现。重点顺序表上的查找、有序表上的折半查找、二叉排序树上的查找难点二叉排序上上的删除操作排序（9+2学时）教学内容排序的基本概念、插入排序、交换排序、选择排序、归并排序教学要求让学生全面了解各种不同的内排序（插入、交换、选择、归并等）算法的算法思想和算法实现。重点插入和交换排序难点希尔排序和快速排序的实现过程推荐教材及教学参考书严蔚敏、吴伟民编著，数据结构（C语言），清华大学出版社，2011年7月。程杰著，大话数据结构，清华大学出版社，2011年6月第1版。授课形式