发布时间 : 星期一 文章数据结构-朱二周更新完毕开始阅读12798ad2c9d376eeaeaad1f34693daef5ef7132a
《数据结构》教学大纲
课程编号：ZJ36007
课程名称：数据结构 英文名称：Data Structure 学分/学时： 68 课程性质：必修 适用专业： 计算机类各专业
先修课程： C语言程序设计、离散数学 开课单位： 计算机科学与技术学院
一、课程的教学目标与任务
《数据结构》是计算机专业本科学生的专业技术基础课。也是计算机程序设计的重要理论技术基础。它不仅是计算机学科的核心课程，而且已成为其他理工专业的热门选修课程。设置本课程的目的是要培养学生的数据抽象能力，学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及实现应用的相应算法，并初步掌握分析算法的时间和空间复杂度的技术。学习本课程的要求是：通过本课程的学习，使学生了解和掌握数据结构和算法的基本思想和常见算法，学习分析、设计和实现解决问题的策略；使学生了解和基本掌握典型的数据结构类型及其应用；结合实际问题分析，加深对所学知识的理解，并为后续课程和未来的工程实践打下良好的基础。
《数据结构》是计算机类各专业的一门必修的核心课程，从课程的地位来说，它在专业基础课和专业课之间起着承上启下的作用，应此一般安排在《离散数学》和《C语言程序设计》课程之后，后续课程还包括《面向对象程序设计》 、《软件工程》等。通过本课程的学习，使学生能够系统地掌握数据结构的基本概念、各种数据结构的基本原理、适用场景和实现技术；具有使用数据结构解决实际应用的能力，为以后在学习其他课程以及实际工作打下坚实的理论基础。
二、课程具体内容及基本要求
第1章 绪论 ( 2学时) （一）基本内容： （1）什么是数据结构
程序＝数据结构＋算法 线性结构 ：1：1关系 树线结构 ：1：N层次组织关系 图状结构 ：N：N关系
数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。 （2）基本概念和术语
数据：所有能输入到计算机中并能被计算机程序处理的符号的总称。如数值、
字符、图像、声音等。
数据元素：用于描述数据的基本单位。它可由数据项组成。数据项是数据表
示中不可分割的最小标识单位。
数据对象：具有相同性质的数据元素所组成的集合。数据对象中包含的数据
元素之间具有一定的组织形式和结构关系。
数据结构：是对数据元素及其相互关系的描述。包含两方面的内容：一方面
是对数据元素的有限集合即数据对象的描述，另一方面是对数据对象中数据元素的关系的描述。
数据结构的基本类型：集合、线性结构、树形结构、图状结构。
数据的存储结构：与逻辑结构相对应。它指的是数据元素及其逻辑关系在计
算机存储器中的存储形式，也称数据的物理结构。分为两类：顺序存储结构与非顺序存储结构（链式存储结构）。
（3）抽象数据类型的表示与实现
抽象数据类型通过固有数据类型来表示和实现，即利用处理器中已存在的数据类型来说明新的结构，用以实现的操作来组合新的操作。
描述语言：类C语言。 （4）算法和算法分析
算法及其特性：算法是对特定问题的求解描述，它是指令的有限序列。 算法通常有五个特性：有穷性、确定性、可行性、输入、输出。 算法设计的要求：正确性、可读性、健壮性、效率与低存储量需求。 算法效率的度量：时间复杂度和空间复杂度。 （二）基本要求
（1）熟悉数据、数据元素、数据对象、数据结构等名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系；
（2）了解抽象数据类型的定义、表示和实现方法；
（3）熟悉类C语言的书写规范，特别要注意值调用和引用调用的区别，输入、
输出的方式以及错误处理方式； （4）理解算法五个要素的确切含义；
（5）掌握计算语句频度和估算算法时间复杂度的方法。 （三）重点、难点
（1）数据的逻辑结构与存储结构的关系；
（2）如何分清哪些是逻辑结构的性质，哪些是存储结构的性质； （3）算法的时间和空间复杂度分析。 （四）作业及课外学习要求：
（1）思考什么是数据、数据元素以、数据对象、数据结构、存储结构、数据类
型和抽象数据类型？
（2）试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。
本知识点的讲授和学习，可以支撑“毕业要求2问题分析”中的“指标点2.1能够将数学与自然科学的基本概念运用到工程问题的适当表述之中”，使学生掌握工程基础知识和本专业的基本理论知识。 第2章 线性表 ( 6学时) （一）基本内容： （1）线性表的类型定义
线性表是由n个数据元素所构成的一个有限序列，表中的每个数据元素都具有相同的数据类型，其中表中的每个数据元素也称为结点，结点与结点之间具有一定的前后次序关系，也即除了第一个结点以外，每一个结点都有一个前驱，除了最后一个结点以外，每个结点都有一个后继。
线性表中数据元素的个数n称为线性表的长度，当n=0时，线性表就是一张空表。对于表中的每一个数据元素，它都有确定的位置，也就是该数据元素在表中的序号。
线性表中的数据元素可由多个数据项构成，也可只包含一个数据项。每一个数据项也就相应地称为结点中的数据域。
对于线性表而言，通常有以下基本操作：初始化、销毁、求长度、定位、插入元素、删除元素、取元素、求前驱、求后继、遍历等。
这些操作都是定义在线性表的逻辑结构上的基本操作，在尚未对线性表的存储结构作出规定之前，这些操作的具体实现尚无法得到。 （2）线性表的顺序表示和实现
线性表的顺序存储结构指的是表中的结点依次存储在一组地址连续的存储
单元中，使得结点的逻辑顺序与它在存储器中的物理顺序一致，这种结构的线性表也称为顺序表。
假设线性表中的每个结点具有固定长度，占用m个存储单元，并且线性表中第一个结点的存储地址为Loc(a1)，则表中第i个结点的存储地址为：
Loc(ai)=Loc(a1)+(i-1)*m
线性表顺序存储结构的类型定义：
在C语言中，实现线性表的顺序存储结构的类型定义
#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量 #define LISTINCREMENT 10//线性表存储空间的分配增量 typedef struct {
ElemType *elem; //指向存放线性表中数据元素的基地址 int length; //线性表的当前长度
int listsize;//当前分配的存储容量 (以sizeof(ElemType)为单位） }SqList；
线性表顺序存储结构下基本操作的实现算法：初始化操作、插入操作、删除
操作。
插入操作算法时间复杂度分析：平均移动元素次数为n/2，时间复杂度O(n)。 删除操作算法：平均移动元素次数为(n-1)/2，时间复杂度O(n)。 线性表的顺序存储结构的优点：简单、直观，易于实现随机存取。
线性表的顺序存储结构的缺点：需要占据较大的连续存储空间，不利于零碎内存空间的利用，且在数据元素的插入和删除时，为了保证逻辑关系与物理位置的对应，必须要移动大量的数据元素。 （3）线性表的链式表示和实现
为了克服线性表顺序存储结构存在的缺点，在线性表的链式存储结构中，逻辑上相邻的数据元素不必在物理上也占据相邻的存储单元。这意味着可用物理上任意位置的存储单元来存储线性表中的数据元素。此时，数据元素的逻辑关系是通过指针来表示的。 （a）线性链表
由于在链式存储结构中，数据元素的逻辑关系是通过指针来表示的，因此，线性表中的基本单位除了要有存储数据元素的数据域外，还要有存储指示其与其他元素的逻辑关系的指针，这样的基本单位称为结点。线性链表中结点的结构为：
data next
其中，data域为存储数据元素信息的数据域，而next则为指示其直接后继存储位置的指针域。如此，一个包含了n个结点的线性表(a1,a2,??an)就是一个线性链表，其结构如下图所示：
┅┅ a2 An ^ a1
其中，线性链表中的最后一个结点无直接后继，其指针域为空（NULL）。由于在这样的线性表结点中，只有一个指示相邻元素的指针域，因此又称为单链表。
链表中结点之间的逻辑次序是通过指针来指示的，而结点在存储器中的存储位置可以是任意的，并不要求逻辑上相邻的数据元素在物理位置上也相邻。所以