数据结构ppt第一章绪论

数据结构》主讲教师陈明

教材

数据结构教程

李春葆等

清华大学出版社

参考教材数据结构（C++语言版）

刘清王琼电子工业出版社数据结构（C语言版）

严蔚敏吴伟民清华大学出版社数据结构与程序设计—C++语言描述（影印版）RobertL.Kruse，AlexanderJ.Ryba高等教育出版社教学内容

第一章绪论

第二章线性表

第三章栈和队列

第四章串（最后选讲）

第五章数组和广义表（简单介绍）

第六章树

第七章图

第八章查找

第九章排序课程特点及教学方法难度大综合性强必须下苦功学习关于教学的几个新观念教学过程以学生为主体,教师为主导学生由知识技能的被动接受者向知识技能的主动探求者转变,教师由传授者向教学活动的设计者、组织者、指导者转变教学目标为使学生在知识、能力、素质方面协调发展能力包括自学能力、知识运用能力、动手能力、创新能力、发现问题能力、分析问题和解决问题能力以及可持续发展能力第一章绪论

第一章绪论

1.1

本课程的研究对象；

1.2数据结构的有关基本概念；

1.3数据结构的分类及表示；

1.4算法及算法分析（算法评价）

1.1本课程研究的问题

计算机的发展

软件硬件应用领域

数据处理的种类和能力

数据数值数据

非数值数据

数(整数,实数)字符字符串文字图形图象声音数据：客观对象的符号表示数学中的整数、实数，

课程名，地名、书名程序原始数据结果数据

数值问题与非数值问题1）数值问题例1已知：游泳池的长len和宽wide，求面积area◆设计求解问题的方法◆

编程1.1本课程研究的问题◆建模型：

问题涉及的对象：游泳池的长len

宽wide，面积area；

对象之间的关系：area=len

wide

学号姓名性别出生日期籍贯入学成绩所在班级 00201

杨润生男82/06/01广州56100计算机2

00102石磊男83/12/21汕头51200计算机1

00202李梅女83/02/23阳江53200计算机200301马耀先男82/07/12广州50900计算机32）非数值问题例2已知某级学生情况,要求分班按入学成绩排列顺序。1.1本课程研究的问题在这类文档管理的数学模型中,计算机处理的对象之间通常存在着一种最简单的线性关系,这类数学模型称为线性模型。1.1本课程研究的问题例3迷宫问题。在迷宫中，每走到一处，接下来可走的通路有三条。计算机处理的这类对象之间通常不存在线性关系。若把从迷宫入口处到出口的过程中所有可能的通路都画出，则可得一棵“树”

入口

出口城市间交通网问题1.1本课程研究的问题数据结构的研究问题：非数值数据之间的结构关系，及如何表示，如何存储，如何处理。本课程讨论的问题：应用中常用的几种数据间的结构关系，及如何表示,如何存储，如何处理。

1.数据（Data）数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。换句话说，数据是对客观事物采用计算机能够识别、存储和处理的形式所进行的描述。简而言之，数据就是计算机化的信息。

1.2数据结构的有关概念例如对C源程序，数据概念不仅是源程序所处理的数据，相对于编译程序来说，C编译程序相对于源程序是一个处理程序，它加工的数据是字符流的源程序（.c），输出的结果是目标程序(.obj)；对于链接程序来说，它加工的数据是目标程序(.obj)，输出的结果是可执行程序(.exe)，如图1.1所示。图1.1编译程序示意图源程序目标程度可执行程序C编译程序C链接程序

2.数据元素（DataElement）数据元素是组成数据的基本单位,是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。表1-1学籍表学号姓名性别籍贯出生年月住址101赵红玲女河北1983.11北京………………数据项记录

3.数据对象（DataObject）

数据对象是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={′A′，′B′，…，′Z′}，表1-1所示的学籍表也可看作一个数据对象。由此可看出，不论数据元素集合是无限集（如整数集）、有限集（如字符集），还是由多个数据项组成的复合数据元素（如学籍表），只要性质相同，都是同一个数据对象。综上1~3所述，再分析数据概念：

4.数据结构（DataStructure）

数据结构是指相互之间存在一种或多种特定关系的数据元素集合，图1.2学校组织层次结构图图1.3交通流量图

5.数据类型(DataType)

数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。数据类型中定义了两个集合，即该类型的取值范围，以及该类型中可允许使用的一组运算。例如高级语言中的数据类型就是已经实现的数据结构的实例。从这个意义上讲，数据类型是高级语言中允许的变量种类，是程序语言中已经实现的数据结构（即程序中允许出现的数据形式）。在高级语言中，整型类型可能的取值范围是-32768~+32767，可用的运算符集合为加、减、乘、除、乘方、取模（如C语言中+，-，*，/，%）。6.数据抽象与抽象数据类型１）数据的抽象计算机中使用的是二进制数，汇编语言中则可给出各种数据的十进制表示，如98.65、9.6E3等,它们是二进制数据的抽象;使用者在编程时可以直接使用,不必考虑实现细节。在高级语言中，则给出更高一级的数据抽象，出现了数据类型，如整型、实型、字符型等。到抽象数据类型出现，可以进一步定义更高级的数据抽象，如各种表、队、栈、树、图、窗口、管理器等，这种数据抽象的层次为设计者提供了更有利的手段，使得设计者可以从抽象的概念出发，从整体考虑，然后自顶向下、逐步展开，最后得到所需结果。可以这样看，高级语言中提供整型、实型、字符、记录、文件、指针等多种数据类型，可以利用这些类型构造出像栈、队列、树、图等复杂的抽象数据类型。２）抽象数据类型(AbstractDataType)

抽象数据类型（简称ADT）是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。抽象数据类型的定义取决于客观存在的一组逻辑特性，而与其在计算机内如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。从某种意义上讲，抽象数据类型和数据类型实质上是一个概念。整数类型就是一个简单的抽象数据类型实例。“抽象”的意义在于教学特性的抽象。一个ADT定义了一个数据对象，数据对象中各元素间的结构关系，以及一组处理数据的操作。ADT通常是指由用户定义且用以表示应用问题的数据模型，通常由基本的数据类型组成，并包括一组相关服务操作。抽象数据类型是近年来计算机科学中提出的最重要的概念之一，它集中体现了程序设计中一些最基本的原则：分解、抽象和信息隐藏。一个抽象数据类型确定了一个模型，但将模型的实现细节隐藏起来；它定义了一组运算，但将运算的实现过程隐藏起来。数学模型→抽象数据类型→数据结构，恰好反应了信息结构转换的三个重要阶段，而在这个转换过程中，数据结构是基础，抽象数据类型是中枢。

一个线性表的抽象数据类型的描述如下：

ADTLinear-list

数据元素所有ai属于同一数据对象，i=1，2，…，n,n≥0；逻辑结构所有数据元素ai（i=1，2，…，n-1）存在次序关系<ai，ai+1>，ai无前趋，an无后继；操作 设L为Linear-list: Initial(L):初始化空线性表; Length(L):求线性表的表长; Get(L,i):取线性表的第i个元素；

Insert(L,i,b):在线性表的第i个位置插入元素b；

Delete(L,i):删除线性表的第i个元素。３）抽象数据类型实现第一种情况：传统的面向过程的程序设计。第二种情况：“包”、“模型”的设计方法。第三种情况：面向对象的程序设计（ObjectOriented Programming，简称OOP）。４）ADT的表示与实现

ADT的定义

ADT的定义格式不唯一,我们采用下述格式定义一个ADT:

ADT<ADT名>

{数据对象:<数据对象的定义>

结构关系:<结构关系的定义>

基本操作:<基本操作的定义>}ADT<ADT名>其中数据对象和结构关系的定义采用数学符号和自然语言描述,而基本操作的定义格式为:<操作名称>(参数表)

操作前提:<操作前提描述>

操作结果:<操作结果描述>关于参数传递

参数表中的参数有两种：第一种参数只为操作提供待处理数据,又称值参；第二种参数既能为操作提供待处理数据,又能返回操作结果，也称变量参数。操作前提描述了操作执行之前数据结构和参数应满足的条件,操作结果描述操作执行之后,数据结构的变化状况和应返回结果。ADT可用现有计算机语言中已有的数据类型,即固有数据类型来表示和实现。不同语言的表示和实现方法不尽相同，如ADT中“返回结果的参数”，PASCAL语言用“变参”实现,C++语言通过“引用型参数”实现,而C语言用“指针参数”实现。用标准C++语言表示和实现ADT描述时，主要包括以下两个方面:(1)通过结构体将int、float等固有类型组合到一起,构成一个结构类型,再用typedef为该类型或该类型指针重新起一个名字。

(2)用C++语言函数实现各操作。基本操作主要有以下几种：

(1)插入：在数据结构中的指定位置上增添新的数据元素；

(2)删除：删去数据结构中某个指定数据元素；

(3)更新：改变数据结构中某个元素的值，在概念上等价于删除和插入操作的组合；

(4)查找：在数据结构中寻找满足某个特定要求的数据元素（的位置和值)；

(5)排序：（在线性结构中）重新安排数据元素之间的逻辑顺序关系，使数据元素按值由小到大或由大到小的次序排列。对每种数据结构，主要讨论如下两方面的问题：

1）数据的逻辑结构，数据结构的基本操作；

2）数据的存储结构，数据结构基本操作的实现；数据的逻辑结构：

数据之间的结构关系，是具体关系的抽象。数据结构的基本操作：指对数据结构的加工处理数据的存储结构(物理结构)：

数据结构在计算机内存中的表示数据结构基本操作的实现：基本操作在计算机上的实现（方法)1.3数据结构的分类及表示

某班学生基本情况登记表，记录了每个学生的学号姓名专业政治面貌，表中的记录是按学生的学号顺序排列的。

学号姓名 专业 政治面藐

001 王洪 计算机党员

002孙文计算机团员

003 谢军 计算机团员

004 李辉 计算机团员

005 沈祥福计算机党员

006 余斌 计算机团员

007 巩力 计算机团员

008 孔令辉计算机团员学生基本情况登记表的图示

001003002004006005008007学生间学号顺序关系是一种线性结构关系例一常用的数据结构

1）集合

2）线性结构

3）树结构

4）图结构

5）其它复杂结构

家族的族谱

假设某家族有10个成员A，B，C，D，E，F，G，H，I，J，他们之间的血缘关系可以用如下图表示。JIACBDHGFE1．3数据结构的分类及表示例1.逻辑结构图1.5四类基本数据结构示意

(1)集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。

(2)线性结构：结构中的数据元素之间存在着一对一的线性关系。

(3)树形结构：结构中的数据元素之间存在着一对多的层次关系。

(4)图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。逻辑结构线性结构——线性表、栈、队、字符串、数组、广义表非线性结构——树、图

2.存储结构存储结构（又称物理结构）是逻辑结构在计算机中的存储映象，是逻辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。形式化描述：D要存入机器中，建立一从D的数据元素到存储空间M单元的映象S，D→M，即对于每一个d，d∈D,都有唯一的z∈M，使S（D）=Z,同时这个映象必须明显或隐含地体现关系R。逻辑结构与存储结构的关系为：存储结构是逻辑关系的映象与元素本身的映象。逻辑结构是数据结构的抽象，存储结构是数据结构的实现，两者综合起来建立了数据元素之间的结构关系。■顺序映象（顺序存储结构）

■非顺序映象（非顺序存储结构）数据结构的内容可归纳为三个部分：逻辑结构、存储结构和运算集合。按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合，就叫做数据结构。数据结构的表示

图示表示

图示表示是由顶点和边构成的图，其中顶点表示数据，边表示数据之间的结构关系；

001003002004006005008007学生基本情况表的图示表示JIACBDHGFE家族树的图示表示1．3数据结构的分类及表示学生基本情况表的二元组表示（D，S）

二元组表示

二元组表示是用一个二元组（D，S）表示数据结构，其中D是数据元素集合，S是D上关系的集合。D={001，002，003，004，005，006，007，008}S={R}R={<001,002>,<002,003>,<003,004>,<004,005>,<005,006>,<006,007>,<007,008>}

家族树的二元组表示（D，S）D={A，B，C，D，E，F，G，H，I，J}

S={R}

R={〈A,B>,<A,C>,<A,D>,<B,E>,<B,F>,<C,G>,<D,H>,<D,I>,<D,J>}1．3数据结构的分类及表示JIACBDHGFE

0010030020040060050080071．4算法与算法分析1.4算法与算法分析一算法的概念

算法是求解问题的操作序列

算法的基本特征：

1）输入：0个或多个输入；

2）输出：1个或多个输出；

3）有穷性：算法必须在有限步内结束；

4）确定性：组成算法的操作必须清晰无二义性。

5）可行性：组成算法的操作必须能够在计算机上实现。

求两个正整数m，n中的最大数MAX的算法（1）若m>n则max=m

（2）若m<=n则max=n例描述算法的书写规则所有算法均以函数形式给出,算法的输入数据来自参数表参数表的参数在算法之前均进行类型说明有关结点结构的类型定义,以及全局变量的说明等均在算法之前进行说明评价算法标准

算法的正确性，可读性，可维护性，健壮性等，1算法时间复杂度T（n）

本课程采用以求解问题的基本操作（原操作）的执行次数作为算法时间的度量。

1．4算法与算法分析O（n3）

称为矩阵相乘算法时间复杂度；O（n3）表示矩阵相乘算法执行时间与n3成正比,即O（n3）与n3同一数量级；n阶矩阵相乘的算法For(i=1;i<=n;i++)

For(j=1;j<=n;j++){c[i][j]=0;

For(k=1;k<=n;k++)

c[i][j]+=a[i][k]*b[k][j]}

乘法加法执行次数均为n3

例

矩阵相乘的基本运算：乘法加法；

有些算法，基本操作执行次数与问题的输入数据有关，这时可考虑

（1）算法平均时间复杂度

（2）算法在最坏情况下的时间复杂度算法的时间复杂度

一般来说，设算法中基本操作的执行次数是问题规模n的某个函数f(n)，算法的时间复杂度记作：

T(n)=O(f(n))

它表示随问题规模n的增大，算法执行时间的增长率与f(n)的增长率相同。

1．4算法与算法分析算法的时间复杂度为O(N3)

1．4算法与算法分析

100元买100支笔,其中钢笔3元/支,圆珠笔2元/支,铅笔0.5元/支.写算法输出各种组合方案解法1#defineN100voidscheme(){inti,j,k,count,money;for(i=0;i<=N;i++)

for(j=0;j<=N;j++)for(k=0;k<=N;k++){count=i+j+k;money=3*i+2*j+0.5*k;

if(count==N&&money==N)

printf