《数据结构》实验教学大纲

《数据结构》实验教学大纲

课程名称：数据结构

英文名称：Data Structures

课程编号：2215990506

课程性质：课程类型：专业基础课 是否为独立设课的实验课：否

适用专业：计算机与软件学院

学时与学分：总学时：72 总学分：3.5 实验学时：18 实验学分：0.5

执 笔 人：张小健/蔡茂国

制定时间：2010年8月

一、实验课的任务、性质与目的

本实验课程与《数据结构》课堂教学有机结合，相辅相成。在课堂教学中，比较全面、概括性地讲述数据结构学科中一些基础性知识、重要概念及各种算法，而在本实验课程中，将这些基础性知识、重要概念及各种算法，在计算机上编程实现，使学生能够达到以下教学目标：

⑴、掌握计算机处理数据的基本方法

⑵、了解算法需用的时间及空间分析方法

⑶、能够为实际应用所涉及的数据选择适当的逻辑结构、存储结构及相应的算法

⑷、通过在计算机上编程实现课程中介绍的各种算法，在程序设计能力方面得到提升。

二、主要仪器设备及环境

1． 计算机

2． Windows软件环境

3． TurboC/VC编程环境

三、实验项目的设置与实验内容

序号 实验项目名称 实验内容 实验

要求 实验

时数 每组

人数 实验

类型

1 多项式相加 对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”的一项；对于两个一元多项式中所有指数不相同的项，则分别复抄到“和多项式”中去 必做 2 1 验证

2 表达式计算 先将中缀表达式（就是我们通常所见的）转换为后缀表达式，比如 a+b*c+d 要变成 abc*+d+；转换的方法用栈来实现，涉及到运算符的优先级；然后用另一个栈来对表达式计算结果 选做 2 1 验证

3 Kmp算法 求出子串（模式串）的next，利用kmp算法实验模式与主串的匹配算法 选做 2 1 验证

4 Huffman 编码 根据给定一串字符（或一个文本文件），自动生成n必做 2 1 验证 个权值(w1, w2,„,wn)构成n棵二叉树的集合F={T1, T2,„,Tn}，其中每棵二叉树Ti中只有一个带树为Ti的根结点；在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置其根结点的权值为其左右子树权值之和；在F中删除这两棵树，同时将新得到的二叉树加入F中；4.重复2, 3，直到F只含一棵树为止；然后求出每个字符对应的Huffman编码，继而求出整个字符串（或文本文件）的Huffman码流

《数据结构》教学大纲

课程编号：071213A

课程类型：□通识教育必修课 □通识教育选修课

□专业必修课 □专业选修课

■学科基础课

总学时：48 讲课学时：32 实验（上机）学时：16

学 分：3

适用对象：计算机科学与技术专业

先修课程：

程序设计基础与应用、计算机基础

一、教学目标

本课程是计算机科学与技术专业的必修课。本课程是计算机科学与技术专业的核心课程，既重视学生相关理论的系统学习，又强调培养学生发现问题、分析问题和解决问题的实践能力。《数据结构》在计算机科学中是一门综合性的专业主干课，它是介于数学、计算机硬件、计算机软件三者之间的一门核心课程，而且是操作系统、数据库系统及其它系统程序的大型应用程序设计的基础，同时又直接为从事各类计算机应用的技术人员提供了必要的基本知识和解决实际问题的多种方法。

用计算机解决任何问题都需要进行数据表示和数据处理，而数据表示和数据处理正是《数据结构》要研究的内容。《数据结构》主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。该课程逻辑上以线性结构、层次结构、网状结构为主线，物理上分顺序存储、链式存储，分别介绍基本数据结构的特点和算法。并重点介绍有关各种检索、排序和文件组织的常用算法。通过上述知识的学习和能力的提高，为后续学习和实际工作打下良好的知识基础和能力基础。

目标1： 通过对数据结构基本知识进行讲解，让学生理解并掌握数据的逻辑结构和物理结构，并掌握算法设计的基本思想。

目标2：培养学生分析算法复杂度的初步能力，锻炼学生逻辑思维能力和想象能力，并使之了解数据结构的各种应用场景。

目标3：鼓励学生运用算法知识解决各自学科的实际问题，培养他们的独立科研的能力和理论联系实际的能力。

二、教学内容及其与毕业要求的对应关系

（一）教学内容

1．知识体系

第一部分：数据结构的基本概念，包括数据、数据元素、数据项等基本概念、数据类型、抽象数据类型、算法的定义、算法的特性、算法的时间代价、算法的空间代价；

西北师范大学计算机学院计算机科学与技术专业教学大纲

1 《数据结构》实验教学大纲及实验项目

课程编号：71001410

课程类别：专业基础必修课

实验学时：实验36学时

学 分：1

适用专业：计算机科学与技术

一、实验教学目的和任务

数据结构是信息与计算科学专业中一门重要的专业基础课程。当用计算机来解决实际问题时，就要涉及到数据的表示及数据的处理，而数据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续课程，特别是软件方面的课程打下了厚实的知识基础，同时也提供了必要的技能训练。因此，数据结构课程在计算机应用专业中具有举足轻重的作用。

本课程的任务是：通过实践，学生对常用数据结构的基本概念及其不同的实现方法的理论得到进一步的掌握，并对在不同存储结构上实现不同的运算方式和技巧有所体会。

二、实验教学基本要求

本课程是一门实践性很强的专业课，只有了解这门课程的特点和基本要求，学习时才能做到有的放矢，举一反三，本课程特点主要有以下几个方面：

(1) 内容丰富，理论性强。本课程为以后学习专业基础课和专业课(如：计算机操作系统、数据库原理等)打下良好的基础。

(2) 注重理论联系实际，加强实验环节的训练。只有通过实验，才能透彻理解基本原理。

三、实验教学内容

序号 项目名称 项目类别 项目类型 项目学时

1 线性表的顺序存储实验 基础性 必做 2

2 线性表的链式存储实验 基础性 必做 4

3 顺序栈的实现及表达式的括号匹配 综合性 必做 4

4 队列的顺序与链式实现 综合性 选做 4

5 实现二叉树的建立与遍历 综合性 必做 6

6 实现有向图的拓扑排序 综合性 必做 4

7 实现多种（至少4种）排序算法及它们的时间测试 综合性 必做 4

8 三元组法实现稀疏矩阵的转置 设计性 选做 4

9 静态查找树的构造和查找 设计性 选做 4

实验项目内容及要求

实验要求的设备为计算机，统一在计算机实验室完成。实验项目共9个，项目类别分为基础性、综合性和设计性三种，实验项目类型分为必做和选做。要求学生在36学时必须完成必做项目，在完成的基础上实现选做项目。 西北师范大学计算机学院计算机科学与技术专业教学大纲

数据结构教学大纲

(56学时)

一、课程性质、适用专业及层次

本课程是我院计算机专业的一门综合性的专业基础课。主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。通过本课程的学习，使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、编译原理和数据库等课程奠定基础。

本大纲适用于三年制专科层次。适用专业——计算机应用相关专业。

二、课程教学目标

本课程的教学目标是：使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、编译原理和数据库等课程奠定基础。在教学中注重综合应用能力培养，切实提高学生的综合素质。

(一) 知识教学目标

1、了解数据结构及其分类、数据结构与算法的密切关系。

2、熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构。

3、掌握设计算法的步骤和算法分析方法。

4、掌握数据结构在排序和查找等常用算法中的应用。

5、初步掌握文件组织方法和索引技术。

(二) 能力培养目标

培养基本的、良好的程序设计技能，编制高效可靠的程序。

(三) 思想教育目标

1、注重培养学生独立思考能力，学会科学地分析和解决问题。

2、培养学生的团结协作能力。

3、培养学生求真务实、讲求时效和一丝不苟的学习态度。

4、为学生形成良好的职业道德打下基础。

三、教学内容和要求

理论教学模块

(一) 数据结构基本概念及简单的算法分析

教学内容：

1. 什么是数据结构 2. 抽象数据类型及面向对象概念：数据类型；数据抽象与抽象数据类型；面向对象的概念；用于描述数据结构的语言

3. 数据结构的抽象层次

4. 算法定义

5. 性能分析与度量：算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法；渐进的空间复杂.