《数据结构》课程教学大纲.docx

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

课程总学时/学分：64/3.5（其中理论52学时，实验12学时）

课程类别：专业限选课

一、教学目的和任务

数据结构主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计

算法以及对算法的分析和评价。通过本课程的学习，使学生深入地理解数据结构的

逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，

编制高效可靠的程序，为学习操作系统、编译原理和数据库等课程奠定基础。

二、教学基本要求

通过本课程的学习和实践，要求学生达到以下要求：了解数据结构及其分类、

数据结构与算法的密切关系；理解各种基本数据结构及其操作，学会根据实际问题

要求来选择数据结构；掌握设计算法的步骤和算法分析方法；掌握数据结构在排序

和查找等常用算法中的应用；能有效合理的利用所学数据结构、程序设计技术和相

关算法解决简单实际应用问题；初步掌握文件组织方法和索引技术。

本课程在“算法语言与程序设计”之后开设，课程以C语言作为数据结构和算法

的描述工具，在教学方法上应采用理论与实践相结合的方式，用理论指导实践，以

讲授理论为主，用多媒体手段展示教学内容，通过实验加深学生对本课程相关知识

的理解，强化数据结构基本知识和程序设计基本能力的双基训练。

三、教学内容及学时分配

第一章绪论（4学时）

教学要求：

1．理解各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结

构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。

2．了解抽象数据类型的定义、表示及实现方法。

3．掌握类C语言的书写规范，特别要注意值调用和引用调用的区别，输入、输

出的方式及错误处理方式。

4．理解算法五个要素的确切含义：动态有穷性（能执行结束）、确定性（对于

相同的输入执行相同的路径）、有输入、有输出、可行性（用以描述算法的操作都

市足够基本的）。

5．掌握计算语句频度和估算算法时间复杂度的方法。

教学重点：

数据结构的定义；算法的描述方法。

教学难点：

数据结构的定义；算法与程序的区别；时间复杂度及其计算。

第二章线性表（10学时）

教学要求：

1．了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表

示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。

2．掌握这两种存储结构的描述方法，如链表中的头结点、头指针和首元素结点

的区别及循环链表、双向链表的特点等，链表是本章的重点和难点。扎实的指针操

作和内存动态分配的编程技术是学好本章的基本要求。

3．掌握线性表在顺序存储结构上实现基本操作：查找、插入和删除的算法。

4．掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适

当的链表结构。了解静态链表，能够加深对链表本质的理解。

5．能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及

其使用场合。

教学重点：

线性表的概念；线性表的顺序存储结构、链式存储结构及其常用算法。

教学难点：

链式存储结构及其常用算法；双向循环链表。

[实验名称]

链表的建立、插入和删除

[实验要求]

创建一个以正序排列的链表，链表节点为一个整形数据，插入一个元素，删除

一个元素，均保持链表的正序。在执行完每个操作后将其输出。通过对链表的实际

操作，巩固链表的基本知识，关键是掌握指针的操作。

[实验学时]

4学时

第三章栈和队列（6学时）

教学要求：

1．掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选

用它们。

2．熟练掌握栈类型的两种实现方法，即两种存储结构表示时的基本操作实现算

法，特别应注意栈满和栈空的条件以及它们的描述方法。

3．熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的条

件以及它们的描述方法。

4．理解递归算法执行过程中栈的状态变化过程。

教学重点：

堆栈和队列的概念；递归的定义；循环队列和链队列的基本运算。

教学难点：

递归的编程实现；循环队列和链队列的基本运算。

[实验名称]

栈的应用

[实验要求]

编写一个能判别表达式中括号是否匹配的程序，当任意输入一个表达式时，程

序能判别表达式中开闭括号是否匹配。

[实验学时]

2学时

第四章串（4学时）

教学要求：

1．熟悉串的七种基本操作的定义，并能利用这些基本操作实现串的其它各种操

作的方法。

2．熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。

3．掌握串的碓存储结构以及在其上实现串操作的基本方法。

4．掌握串匹配的KMP算法，熟悉next函数的定义，学会手工计算给定模式串

的next函数值和改进的next函数值。

教学重点：

串定义和存储方法；串的操作。

教学难点：

串操作实现方法。

第五章数组和广义表（4学时）

教学要求：

1．了解数组的两种存