《数据结构》教学大纲.pdf

《数据结构》教学大纲

DataStructure

课程编号：J6110G0003
课程性质：学科基础课程
适用专业：计算机科学与技术、网络工程、数字媒体技术
先行课：计算机科学导论、离散数学、高级语言程序设计；
后续课：无。
学分数：5
主讲教师：任燕、王命延、冯豫华、周石林、王玮立等

一、课程的目的与任务
数据结构是信息与计算科学专业中一门重要的专业基础课程。当用计算机
来解决实际问题时，就要涉及到数据的表示及数据的处理，而数据表示及数据处
理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续软件方
面的课程打下了厚实的知识基础，同时也提供了必要的技能训练。因此，数据结
构课程在计算机应用专业中具有举足轻重的作用。
本课程的目的是使学生掌握数据组织、存储和处理的常用方法，为以后进
行软件开发和学习后续专业课程打下基础。主要任务是讨论现实世界中数据的各
种逻辑结构，在计算机中的存储结构以及进行各种非数值运算的算法。
本课程达到《认证通用标准》规定中关于“毕业要求”的第三款项（具有运
用工程基础知识和本专业基本理论知识解决问题的能力，具有系统的工程实践学
习经历；了解本专业的前沿发展现状和趋势）、第四款项（具备设计和实施工程
实验的能力，并能够对实验结果进行分析）。

二、课程的基本要求
通过本课程的学习，要求学生了解数据结构及其分类、数据结构与算法的
密切关系；熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数
据结构；掌握设计算法的步骤和算法分析方法；掌握数据结构在排序、查找和
路由选择等常用算法中的应用。
最后学生应达到知识技能两方面的目标：在基础方面，要求学生掌握常用
数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不
同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。

三、课程教学内容
第一章绪论
基本要求:
掌握数据结构的基本概念，抽象数据类型在软件设计中的意义，算法的概念和算法的时
间复杂度分析，了解算法的描述和评价。
基本知识点:
数据结构的基本概念；
算法特性、描述；
算法分析：时间复杂度和空间复杂度；
教学重点:
数据结构的基本概念；
算法分析：时间复杂度和空间复杂度；
实验:
实验1:对某一组数据排序,采用不同的算法定义与实现，并进行算法分析。
习题课安排:
安排一次课下习题,并进行一次课堂讲解.
第二章线性表
教学要求:
理解线性表的定义和线性表基本操作的功能；掌握线性表的顺序和链式存储结构；掌握
顺序表的设计及应用；掌握单链表的设计及应用。掌握两种存储结构的实现及优缺点。
基本知识点:
线性表的类型定义：概念、长度、抽象数据类型定义，基本操作的应用；
线性表的顺序存储结构、构造一个空的线性表、线性表的插入操作、线性表的删除
操作、线性表的查找、线性表的合并，插入、删除算法的算法分析；
线性表的链式实现、返回线性表第i个数据元素的值、在线性表第i个位置之前插
入元素e、在带头结点的线性表L中删除第i个元素、链表的合并；
静态链表、循环链表、双向链表；
教学重点:
线性表的定义和抽象数据类型；顺序和链式存储结构；顺序表的设计；单链表的设计，
算法分析。

实验:
实验2：顺序表的基本操作
实验3：单链表的基本操作
实验4：双向链表或循环链表的基本操作
习题课安排:
安排两次次课下习题,并进行一到两次课堂讲解.

第三章栈和队列
教学要求:
理解堆栈的概念，掌握顺序堆栈和链式堆栈的设计方法；理解队列的概念，掌握顺序循
环队列和链式队列的设计方法；了解堆栈和队列的应用方法，掌握堆栈和队列的基本应用。
基本知识点:
堆栈的基本概念、堆栈的抽象数据类型定义、
堆栈的顺序表示和实现、堆栈的链式表示和实现；
堆栈应用（数制转换问题、括号匹配问题等、表达式求值、栈与递归的实现等）；
队列的基本概念、队列的抽象数据类型定义、
顺序队列、顺序循环队列、链式队列、队列应用。
教学重点:
顺序堆栈和链式堆栈的设计方法；顺序循环队列和链式队列的设计方法。
实验:
实验5：栈的基本操作
实验6：队列的基本操作
习题课安排:
安排一次课下习题,并进行一次课堂讲解.

第四章串
教学要求:
掌握串及其基本概念；理解串的存储结构及串基本操作的实现；了解串的模式匹配算法;
基本知识点:
串的定义和基本运算；
串的存储表示及基本运算的实现；
教学重点:
串的存储结构；
实验:
实验7：串的基本操作
第五章数组
教学要求:
掌握数组的定义及其实现机制；了解数组的抽象数据类型；掌握特殊矩阵的压缩存储和
稀疏矩阵的压缩存储；了解广义表的概念和表示。
基本知识点:
数组的定义及其实现机制；
特殊矩阵（包括n阶对称矩阵、n阶三角矩阵）的压缩存