数据结构讲稿第一次课DS绪论

发布时间：2020-03-03 21:35:41 来源：范文大全收藏本文下载本文手机版

《数据结构》教案

课程性质和任务

本课程是计算机专业的主要专业基础课程之一。本课程的参考教学时数为54学时，实际讲课学时为35，实验学时为16。其主要内容包括顺序表、链表、栈、队、串、树和图的结构，以及查找和排序技术。通过本课程的教学，使学生理解计算机软件系统所必须的数据结构及算法的内部逻辑，掌握在软件工程中大量存在的查找和排序技术，并通过大量的上机实习，实现各种数据结构的算法，以便为后续课程的学习提供专业基础知识，同时增强学生编制程序的能力。

课程教学目标

通过本课程的学习，应达到以下目标：

 深刻理解数据结构中线性表、栈、队和链的概念、算法及其基本应用。

 理解树的基本概念，学会建立二叉树，并在二叉树上进行查找、插入和删除等各种运算。

 理解图的基本结构和算法，了解图的路径问题。

 熟练掌握几种重要的内部排序和查找技术，了解外部排序的一般过程。

 能熟练地运用C语言，准确、清晰地编制与本课程有关的算法，并能上机调试通过。

新疆农业大学数据结构课程教案

第一讲绪论 (对应教材p1—p17)

一、教学目的和要求

要求掌握数据结构中基本概念的定义，理解数据结构研究的主要内容，了解抽象数据类型的表示和实现，理解算法评价的两个指标。

二、授课主要内容

1.数据结构研究的主要内容 2.数据结构中涉及的基本概念

3.算法的概念、描述方法以及评价标准

三、教学重点难点

数据结构中的基本概念、算法的概念、描述方法以及评价标准

四、授课内容和方法

【口述】当今计算机应用的特点：所处理的数据量大且具有一定的关系；对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。

一、什么是数据结构

我们大家知道许多非数值计算问题的数学模型常常是数学方程，如线性方程组、微分方程。所以这类非数值计算问题的解决就归结于对数学模型设计算法、编写程序。然而在现实社会中存在着许多非数值计算问题，其数学模型难以用数学方程描述。

1、举例说明

 图书馆的书目检索自动化问题----计算机处理的对象之间存在着线性关系，称为线性的数据结构。

 人机对奕问题----计算机处理的对象是一个个格局。所有可能出现的格局是一棵倒置的树。

 多岔路口交通灯的管理问题----数学模型是图的数学结构。

【由以上举例引出下列结论：】

非数值计算问题的数学模型是表、树和图之类的数据结构。【总结出定义】数据结构：是一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间关系和操作的一门学科。（三个要素：对象、关系及操作（运算））

2、《数据结构》课程的介绍

1968年美国克努特教授开创了数据结构的最初体系：数据的逻辑结构和存储结构及其操作。

数据结构是一门综合性的专业课程，是一门介于数学、计算机硬件、计算机软件之间的一门核心课程。是设计和实现编译系统、操作系统、数据库系统及其他系统程序和大型应用程序的基础。

二、基本概念和术语

1、数据数据：是指所有能输入到计算机中并被计算机程序处理的符号的总称。是计算机

加工的“原料”。

数据元素:是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据项:有时，一个数据元素可由多个数据项组成。数据项是数据的不可分割的最小单位。

2、数据对象、数据结构

数据对象：是性质相同的数据元素的集合，是数据的一个子集。数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。四类基本结构：集合、线性结构、树形结构、图形结构或网状结构。数据结构的形式定义：数据结构是一个二元组

Data_Structure=(D,S) 其中，D 是数据元素的有限集， S 是D上关系的有限集。

例：复数 Complex=(C,R) 例：课题小组 Group=(P,R) P={T,G1,„,Gn,S11,„,Snm}1≤n≤3，1≤m≤2， R={R1,R2} R1={ |1≤i≤n, 1≤n≤3,} R2={ |1≤i≤n, 1≤j≤m,1≤m≤2,} 数据结构一般包括三方面的内容：

① 逻辑结构：数据元素之间的逻辑关系。

② 存储结构(物理结构)：数据元素及其关系在计算机存储器的表示。用于表示数据元素的位串称之为元素或结点。用于表示数据项的位串称之为数据域。

③ 数据的运算：对数据施加的操作。

算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于采用的存储结构。

3、数据的两种存储结构：顺序存储结构：把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。通常顺序存储结构是借助于语言的数组来描述的。

链式存储结构：不要求逻辑上相邻的结点物理上也相邻，结点间的逻辑关系是由附加的指针字段表示的，通常要借助于语言的指针类型来描述。

4、数据类型、抽象数据类型

数据类型:是一个值的集合和定义在这个值集上的所有的操作。例如，整数类型。数据类型可分为：非结构的原子类型和结构类型。

原子类型的值是不可分解的，结构类型的值是由若干成分按某种结构组成的。

抽象数据类型:是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型和数据类型实质上是一个概念，它仅取决于数据类型的逻辑性，而与其在计算机内部如何表示和实现是无关的。

抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。抽象数据类型按其值的不同特性，分为三种类型： ① 原子类型:变量的值是不可分解的。

② 固定聚合类型:变量的值由确定数目的成分按某种结构组成。 ③ 可变聚合类型:其值的成分数目不确定。

抽象数据类型的形式定义：我们用一个三元组来表示一个抽象数据类型。

（D，S，P）

D是数据对象， S是D上的关系集， P是对D的基本操作。

格式：

ADT 抽象数据类型名{ 数据对象：〈数据对象的定义〉数据关系：〈数据关系的定义〉基本操作：〈基本操作的定义〉 }ADT 抽象数据类型名。

数据对象和数据关系的定义用伪码描述。数据基本操作的定义格式：

基本操作名（参数表）

初始条件：〈初始条件描述〉

操作结果：〈操作结果描述〉例：

ADT Triplet{ 数据对象：D={e1，e2,e3 |e1,e2,e3∈Elemset(定义了关系运算的某个集合)} 数据关系：R1={〈e1,e2>,〉基本操作：

InitTriplet(&T,v1,v2,v3) DestroyTriplet（&T） Get（T,i,&e） Put(&T,i,e) IsAscending(T) IsDescending(T) Max(T,&e)

Min(T,&e)

}ADT Triplet 多形数据类型:是其值的成分不确定的数据类型。

三、抽象数据类型的表示与实现

抽象数据类型可通过固有数据类型来表示和实现，即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。

1、类C语言

精选了C 的一个子集，扩充修改，增强了语言的描述功能。  预定义常量和类型

 数据结构的表示：存储结构用类型（typedef）定义来描述。

数据元素类型约定为ElemType. 基本操作的算法用函数描述：

函数类型函数名（函数参数表）{ //算法说明

语句序列

}//函数名

增加了引用调用的参数传递方式。

 赋值语句、选择语句、循环语句、结束语句、输入输出语句、注释语句  基本函数  逻辑运算约定

例：Triplet的表示和实现

//采用动态分配的顺序存储结构

Typedef ElemType * Triplet://由InitTriplet分配三个元素存储空间 //基本操作的函数原型说明

Status InitTriplet(Triplet &T,ElemType v1, ElemType v2, ElemType v3) Status DestroyTriplet（&T） Status Get（T,i,&e） Status Put(&T,i,e) Status IsAscending(T) Status IsDescending(T) Status Max(T,&e) Status Min(T,&e) //基本操作的实现

Status InitTriplet(Triplet &T, ElemType v1, ElemType v2, ElemType v3){ //构造三元组T，依次置T 的三个元素的处值为v1,v2和v3。

T=(ElemType ) malloc(3*sizeof(ElemType));//分配三个元素的存储空间

If(!T)exit(OVERFLOW);//分配存储空间失败 T[0]=v1;T[1]=v2;T[2]=v3; return OK; }//InitTriplet Status DestroyTriplet（Triplet &T）{ //销毁三元组T。 ······

}//Min

四、算法和算法分析

1、算法（Algorithm）

是对特定问题求解步骤的一种描述，它是指令的有限序列。算法具有五个重要特性：有穷性、确定性、可行性、输入、输出

2、算法设计的要求

正确性、可读性、健壮性和效率与低存储量要求

3、算法效率的度量

算法时间是由控制结构和原操作的决定的。做法：选取一种是基本操作的原操作，以该基本操作重复的次数作为算法的时间量度。

时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数f（n），