数据结构章概论学时

1数据结构

DataStructure曾致远助教：曾道涛手机：2014年2月2学时数：40（28＋12）学分：2.5教材：严蔚敏等，数据结构（C语言版），清华大学出版社，1997年4月（配题集）

参考书：[1]殷人昆等，数据结构（用面向对象方法与C++描述），清华大学出版社，1999年7月。￥26[2]殷人昆等，数据结构习题解析，清华大学出版社，2002年4月。￥26[3]李春保，数据结构习题与解析（C语言篇），清华大学出版社，2001年1月。￥28[4]

丁宝康等，数据结构自学考试指导，清华大学出版社，2001年5月。￥233内容安排(28+12)章内容学时章内容学时1序论27图62线性表68动态存储管理略3栈和队列49查找略4串略10内部排序45数组和广义表略11外部排序略6树和二叉树612文件略4本课程考核方式（百分制）考试（60%)考勤(10%)作业（15%）课程设计（15%）5对本课程同学要求按时上课，打考勤完成作业认真听讲，积极思考多动手，多上机6课前的话——计算机系列课程之间的联系

7数据结构课程的地位是介于数学、计算机硬件和计算机软件三者之间的一门核心课程关系对象关系操作数学软件硬件对象关系操作8第1章序论1.1计算机基本概念（复习）1.2数据结构基本概念1.3抽象数据类型概念1.4算法效率的度量作业9第一章绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分

1.4.1算法

1.4.2算法设计的要求

1.4.3算法效率的度量

1.4.4算法的存储空间的需求10

第一章绪论计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的表示信息的处理而信息的表示和组又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。11计算机基本概念(复习）计算机系统＝硬件系统＋软件系统Q1硬件系统由哪几部分组成？Q2微型计算机与其他计算机的区别？Q3内存与外存的不同之处是？Q4计算机内常用到哪些数制？Q5

计算机主要技术指标有哪些?硬件概念复习软件概念复习Q1软件系统包含哪些软件？Q2什么是系统软件和应用软件？Q3机器语言、汇编语言、高级语言的区别？12Q1：计算机硬件系统由哪几部分组成？答：计算机硬件系统由部分组成：也可浓缩为3部分：存储器CPUI/O接口及设备人脑：感受→判断→计算→记忆→反应电脑：输入→控制→运算→存储→输出控制器

输入运算器

存储器

输出主机513Q2：微型计算机与一般意义上的计算机有什么区别？

其本质特征是答：运算器和控制器集成在一块IC芯片上这种CPU简称MPU14Q3：内存与外存是一回事吗？能被CPU直接控制（BUS直连）的存储器称为内存通过I/O接口才能被CPU控制的存储器称为外存答：不是一回事。它们的区别是：

输入运算器

存储器控制器

输出BUS外存储器CPU15Q4：计算机内常用到哪些数制？A.（11011001）B B.（75）D

C.（37）O D.（2A）H答案：

C

2进制(B)8进制(O)10进制(D)16进制(H)例3：下列四种不同进制的无符号数中，最小的数是∶例2：下列数据中，有可能是八进制数的是∶

A.238 B.764 C.396 D.789例1：10(B)＝

D10(O)＝

D10(H)＝

D

281616Q5：

计算机主要技术指标有哪些？——CPU一次能处理的二进制位数，它与数据总线的根数有关，如8位机，16位机、32位机等等——运算器做一次“加”动作的最小可靠时间，如奔4机器主频达1.6G（Hz）——CPU每秒能执行加法指令的次数（MIPS）——bit，Byte，KB，MB，GB，TB练：微机中1K字节表示的二进制位数是：1B=8bit1KB=210B1MB=210KB1GB=210MBA.1000B.8×1000C.1024D.8×1024答案：D字长主频运算速度主存容量17Q1：

软件系统包含哪些软件？裸机系统软件操作系统支援软件应用软件答：包含系统软件和应用软件两大类18Q2：什么是系统软件？什么是应用软件？答：系统软件——管理计算机系统各部分，使之高效工作，同时为上层提供服务。应用软件——处于系统软件的上层，帮助计算机用户完成特定领域的工作。系统软件中最重要的是操作系统（OperatingSystem），它是一个大型的、优秀的程序，管理着计算机的全部软、硬件资源，并提供人机交互的界面。19Q3：机器语言、汇编语言、高级语言的区别？——用二进制代码直接表示的语言，是计算机唯一能识别、执行的语言——符号化了的机器语言（即用助记符来写程序，靠汇编程序翻译成机器码才能执行）——接近自然英语和数学公式的语言（要通过编译或解释程序翻译成机器码）答：低级语言面向机器，执行速度快，效率高；高级语言面向问题，易理解，易移植。机器语言汇编语言高级语言20

1.1什么是数据结构

众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。那么，什么是数据结构呢？先看以下几个例子。

21例1、电话号码查询系统设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：

(a1，b1)(a2，b2)…(an，bn)

其中ai，bi(i=1，2…n)分别表示某人的名字和对应的电话号码

要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。22方法1：顺序存储，顺序查找姓名电话号码王2李2……张1刘……王1李1……23方法2：有序顺序存储，二分查找（线形结构）姓名电话号码李1李2……张1张2……王1王2……24方法3：部分有序，建立索引表姓名电话号码李1李2……张1张2……王1王2……姓地址李张……25

算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。数据的结构，直接影响算法的选择和效率。上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量。假定名字和其电话号码逻辑上已安排成N元向量的形式，它的每个元素是一个数对(ai，bi)，1≤i≤n

数据结构还要提供每种结构类型所定义的各种运算的算法。26“学生”表格27“课程”表格28

“选课单”包含如下信息

学号课程编号成绩时间

学生选课系统中实体构成的网状关系学生(学号,姓名,性别,籍贯)课程(课程号,课程名,学分)选课(学号,课程号,成绩)非线性结构中各数据成员之间的没有线性关系:前驱和后继可能多于一个29UNIX文件系统的系统结构图/(root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp30例2、图书馆的书目检索系统自动化问题例3、人机对弈问题例4、多叉路口交通灯的管理问题

P3

通过以上几例可以直接地认为：数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。311.2基本概念和术语数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(DataElement):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。32数据对象(DataObject)：是性质相同的数据元素的集合。是数据的一个子集。如字母字符数据对象是集合

C={‘A’,’B’,…,’Z’}数据结构(DataStructure)：是相互之间存在一种或多种特定关系的数据元素的集合。33数据结构主要指逻辑结构和物理结构数据之间的相互关系称为逻辑结构。通常分为四类基本结构：一、集合结构中的数据元素除了同属于一种类型外，别无其它关系。二、线性结构结构中的数据元素之间存在一对一的关系。三、树型结构结构中的数据元素之间存在一对多的关系。四、图状结构或网状结构结构中的数据元素之间存在多对多的关系。

34数据结构的形式定义为：数据结构是一个二元组：

Data-Structure=(D，S)其中：D是数据元素的有限集，S是D上关系的有限集。例复数的数据结构定义如下：

Complex=(C，R)

其中：C是含两个实数的集合﹛C1，C2﹜，分别表示复数的实部和虚部。R={P}，P是定义在集合上的一种关系{〈C1，C2〉}。35数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。

数据对象可以是有限的，也可以是无限的。

数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。36抽象数据类型：一个数学模型以及定义在该模型上的一组操作。抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。用三元组描述如下：（Ｄ，Ｓ，Ｐ）

D:数据对象

S:D上的关系集

P:对D的基本操作集37数据结构在计算机中有两种不同的表示方法：顺序表示和非顺序表示由此得出两种不同的存储结构：顺序存储结构和链式存储结构顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。链式存储结构：在每一个数据元素中增加一个存放地址的指针（），用此指针来表示数据元素之间的逻辑关系。38数据类型：在一种程序设计语言中，变量所具有的数据种类。例1、在FORTRAN语言中，变量的数据类型有整型、实型、和复数型例2、在C语言中数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定义39数据对象：某种数据类型元素的集合。例3、整数的数据对象是{…-3，-2，-1，0，1，2，3，…}英文字符类型的数据对象是{A，B，C，D，E，F，…}401.2数据结构基本概念小结Q1什么是数据结构？Q2学习数据结构有什么用？

Q3数据结构涵盖的主要内容？

讨论：41Q1：什么是数据结构？答:(见教材P5)

是相互之间存在一种或多种特定关系的数据元素的集合，表示为：（数值或非数值）Data_Structure=（D,S）元素有限集关系有限集42数据结构描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中的表示和实现43术语：数据、数据元素和数据项（见教材P4定义）：数据(data)——所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息）。数据元素(dataelement)——是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。数据项(Dataitem)——构成数据元素的项目。是具有独立含义的最小标识单位（又称字段、域、属性等）。三者之间的关系：数据>数据元素>数据项例：班级通讯录>个人记录>姓名、年龄……44Q2：学习数据结构有什么用？答：计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。

这是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。程序设计实质＝好算法＋好结构同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。45Q3：数据结构涵盖的内容？46解释1：什么叫数据的逻辑结构？答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。逻辑结构可细分为4类：集合结构：仅同属一个集合线性结构:

一对一（1:1)

树结构:

一对多（1:n)

图结构:

多对多(m:n)非线性线性47例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。（1）

S=(D,R)D={a,b,c,d,e,f}R={(a,e),(b,c),(c,a),(e,f),(f,d)}解：上述表达式可用图形表示为：bcaefd此结构为线性的。48（2）

S=(D,R)

D={di|1≤i≤5}

R={(di,dj),i<j}

d1d5d2d4d3该结构是非线性的。解：上述表达式可用图形表示为：49解释2：什么叫数据的物理结构？答：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。存储结构可分为4大类：例：（见教材P6）复数3.0－2.3i的两种存储方式：顺序、链式、索引、散列－2.303023.00300041503023.003000415－2.3法1：地址内容法2：地址内容2字节50解释3：什么是数据的运算？答：在数据的逻辑结构上定义的操作算法。它在数据的存储结构上实现。最常用的数据运算有5种：插入、删除、修改、查找、排序511.3抽象数据类型概念Q1数据类型与抽象数据类型的区别？Q2抽象数据类型如何定义？Q3抽象数据类型如何表示和实现？

讨论：提示：教材中例1-6和例1-7分别给出了抽象数据类型“三元组”的定义、表示和实现，请试阅读。52Q1数据类型与抽象数据类型的区别？数据类型：是一个值的集合和定义在该值上的一组操作的总称。抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。53Q2抽象数据类型如何定义？抽象数据类型可以用以下的三元组来表示：

ADT=（D，S，P）数据对象D上的关系集D上的操作集ADT抽象数据类型名{

数据对象：<数据对象的定义>

数据关系：<数据关系的定义>

基本操作：<基本操作的定义>}ADT抽象数据类型名ADT常用定义格式§2DataAbstraction〖Example5〗ADTNatural_Numberstructure

Natural_Number

isobjects:anorderedsubrangeoftheintegersstartingatzeroandendingatthemaximuminteger(INT_MAX)onthecomputerfunctions:

forallx,yNatural_Number;TRUE,FALSE

Booleanandwhere,,,andaretheusualintegeroperationsNatural_NumberZero()::=0BooleanIs_Zero(x)::=if(x)returnFALSE

elsereturnTRUENatural_NumberAdd(x,y)::=if((x+y)<=INT_MAX)returnx+y

elsereturnFALSE

BooleanEqual(x,y)::=if(x==y)returnTRUEelsereturnFALSE

Natural_NumberSuccessor(x)::=if(x==INT_MAX)returnxelsereturnx+1

Natural_NumberSubtract(x,y)::=if(x<y)return0elsereturnxyend

Natural_Numbershort?long?unsigned?Thedescriptionsmustbe

implementation-independentFunctionClassificationCreator/Constructor:Createanewinstance.Transformer:Createanewinstancebyusingoneormoreotherinstances.Observer/Reporter:Provideinformationaboutaninstancewithoutchangingtheinstance.55例：给出自然数(Natural

Number

)的抽象数据类型定义。ADT

Natural_Number

isobjects:

一个整数的有序子集合，它开始于0，结束于机器能表示的最大整数(MAXINT)functions:

对于所有的x,yNatural_Number；TRUE,FALSEBoolean；

+,

-,<,==,=等都是可用的服务。Zero()：Natural

Number

返回0IsZero(x)：Booleanif(x==0)返回TRUE

else返回FALSEAdd(x,y)：Natural

Number

if(x+y<=MAXINT)返回x+yelse返回MAXINTSubtract(x,y):Natural

Number

if(x<y)返回0else返回x-yEqual(x,y):Boolean

if(x==y)返回TRUEelse返回FALSESuccessor(x):

Natural

Number

if(x==MAXINT)返回xelse返回x+1end

Natural_Number

56Q3抽象数据类型如何表示和实现？

抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。注1

：它有些类似C语言中的结构（struct)类型，但增加了相关的服务。注2

：教材中用的是类C语言（介于伪码和C语言之间）作为描述工具。其描述语法见P10-11。但上机时要用具体语言实现，如C或C++等57

1.4算法和算法分析算法：是对特定问题求解步骤的一种描述算法是指令的有限序列，其中每一条指令表示一个或多个操作。

58算法具有以下五个特性：（1）有穷性一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。（2）确定性算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。（3）可行性一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。

(4）输入一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。

(5）输出一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。591.4.2算法设计的要求评价一个好的算法有以下几个标准:(1)正确性(Correctness)

算法应满足具体问题的需求。(2)可读性(Readability)

算法应该好读。以有利于阅读者对程序的理解。(3)健壮性(Robustness)

算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。(4)效率与存储量需求效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。601.4.3算法效率的度量

对一个算法要作出全面的分析可分成两个阶段进行，即事先分析和事后测试事先分析求出该算法的一个时间界限函数事后测试收集此算法的执行时间和实际占用空间的统计资料。611.4.3算法效率的度量定义：如果存在两个正常数c和n0，对于所有的n≧n0，有︱f(n)︳≦c｜g(n)︳

则记作f(n)=O(g(n))

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，算法的时间量度记作

T(n)=O(f(n))称作算法的渐近时间复杂度。(时间复杂度)62

算法的时间复杂度（timecomplexity）的含义

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

它表示随问题特征n的增大，算法中关键操作执行时间的增长率和f（n)的增长率相同，所以称f（n）为算法的时间复杂性。

63例如：在下面的三个程序段中

(a){++x;s=0}(b)for(i=1;i<=n;++i){++x;s+=x;}(c)for(j=1;j<=n;++j)for(k=1;k<=n;++k){++x;s+=x;}关键操作++x的语句的频度分别为1，n，n²，则这三个程序段的时间复杂性分别为

O（1）O（n），O（n²）分别称为常数阶，线性阶，平方阶。

64例１、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];}由于是一个三重循环，每个循环从1到n，则总次数为:n×n×n=n3时间复杂度为T(n)=O(n3)65频度：是指该语句重复执行的次数例２{++x;s=0;}

将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1)

如果将s=0也看成是基本操作，则语句频度为２，其时间复杂度仍为Ｏ(1)，即常量阶。例３、for(I=1;I<=n;++I){++x;s+=x;}

语句频度为：2n其时间复杂度为：O(n)

即时间复杂度为线性阶。66例４、for(I=1;I<=n;++I)

for(j=1;j<=n;++j){++x;s+=x;}

语句频度为：2n2其时间复杂度为：O(n2)

即时间复杂度为平方阶。定理：若A(n)=amnm+am-1nm-1+…+a1n+a0是一个m次多项式，则A(n)=O(nm)证略。67例５for(i=2;i<=n;++I)for(j=2;j<=i-1;++j){++x;a[i，j]=x;}语句频度为：

1+2+3+…+n-2=(1+n-2)×(n-2)/2=(n-1)(n-2)/2=n2-3n+2∴时间复杂度为O(n2)

即此算法的时间复杂度为平方阶.68一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为O(n2)的算法则由一个二次多项式来限界。

69以下六种计算算法时间的多项式是最常用的。其关系为：

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)指数时间的关系为：

O(2n)<O(n!)<O(nn)

当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。70有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。例如：Voidbubble-sort(inta[]，intn)for