数据结构课件01

第一章绪论精英专升本1.1数据结构讨论的范畴1.2基本概念1.4算法和算法分析1.3抽象数据类型1.1

数据结构讨论的范畴NiklausWirth：

Algorithm

+DataStructures=Programs程序设计:算法:数据结构:为计算机处理问题编制一组指令集

处理问题的策略问题的数学模型在现实社会中存在着许多非数值计算问题，其数学模型难以用数学方程描述。例人机对奕问题树……..……..…...…...…...…...概括地说：

数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。（P3）1.2

基本概念和术语一、数据与数据结构二、数据类型三、抽象数据类型一、数据与数据结构所有能被输入到计算机中，且能被计算机处理的符号的集合。数据:是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。是数据（集合）中的一个“个体”数据元素:是数据结构中讨论的基本单位。有时，一个数据元素可由若干个数据项组成。数据对象是性质相同的数据元素的集合，是数据的子集

数据项：是数据结构中讨论的最小单位例如：描述一个运动员的数据元素可以是姓名俱乐部名称出生日期参加日期职务业绩三者之间的关系：数据对象>数据元素>数据项数据元素可以是数据项的集合例，在2行3列的二维数组{a1,a2,a3,a4,a5,a6}中六个元素之间存在两个关系:行的次序关系:列的次序关系:row={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}col={<a1,a4>,<a2,a5>,<a3,a6>}

a1a3a2

a5a4a6a1a2a3a4a5a6

数据结构：带结构的数据元素的集合再例，在一维数组{a1,a2,a3,a4,a5,a6}的数据元素之间存在如下的次序关系:{<ai,ai+1>|i=1,2,3,4,5}

或者说，数据结构是相互之间存在着某种关系的数据元素的集合。可见，不同的“关系”构成不同的“结构”数据结构：有关系的数据元素的集合数据结构的形式定义为:数据结构是一个二元组Data_Structures=(D,S)其中:D是数据元素的有限集，

S是D上关系的有限集。1.数据结构被形式定义为（D，S），其中D是（）的有限集合，S是D上的（）有限集合。A、算法B、数据元素C、数据操作D、逻辑关系E、操作F、映象G、存储H、关系BH历年真题：数据结构包括以下几个方面：数据元素之间的逻辑关系，即逻辑结构数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构施加在该数据上的操作，即数据的运算数据的逻辑结构与存储结构密切相关 算法设计 逻辑结构 算法实现 存储结构 数据的逻辑结构—只抽象反映数据元素的逻辑关系划分方法一（1）线性结构有且仅有一个开始和一个终端结点，并且所有结点都最多只有一个直接前趋和一个后继。例如：线性表、栈、队列、串（2）非线性结构一个结点可能有多个直接前趋和直接后继。例如：树、图线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树集合——数据元素间除“同属于一个集合”外，无其它关系图形结构——多个对多个，如图划分方法二数据的存储结构(物理结构)

——

逻辑结构在存储器中的映象“数据元素”的映象？“关系”的映象？数据元素的映象方法：用二进制位(bit)的位串表示数据元素(321)10=(501)8=(101000001)2关系的映象方法：（表示

x,y

的方法）顺序映象(顺序存储方法)以相对的存储位置表示后继关系链式映象(链式存储方法)

不要求在逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑关系由附加的指针字段表示。【索引存储】【散列存储】元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=L0+（i-1)*m顺序存储结构存储地址存储内容指针

1345元素1

1400

1346元素4∧

…….

……..

…….

1400元素2

1536

…….

……..

…….

1536元素3

1346链式存储结构元素2元素1元素3∧元素41400153613461345hh

数据的逻辑结构

数据的存储结构数据的运算：插入、删除、修改、查找、排序

线性结构

非线性结构

顺序存储

链式存储线性表栈、队列串、数组树形结构图形结构逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构小结：数据结构的三个方面1.下列与数据元素有关的叙述中，哪一个是不正确的（）。A．数据元素是数据的基本单位，即数据集合中的个体B．数据元素是有独立含义的数据最小单位C．数据元素又称结点D．数据元素又称作记录2.下列关于数据的逻辑结构的叙述中，哪一个是正确的（）。A．数据的逻辑结构是数据间关系的描述B．数据的逻辑结构反映了数据在计算机中的存储方式C．数据的逻辑结构分为顺序结构和链式结构D．数据的逻辑结构分为静态结构和动态结构BA3.在数据结构中，从逻辑上可以把数据结构分成（）。A、动态和静态结构B、紧凑接和非紧凑结构C、线性与非线性结构D、内部结构和外部结构C数据的运算：插入、删除、修改、查找、排序数据类型

是一个值的集合和定义在此集合上的一组操作的总称。

不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。二、数据类型例如，C

语言中提供的基本数据类型有:整型int浮点型float字符型char逻辑型bool

（C++语言）双精度型double实型（C++语言）二、数据类型数据结构课程所研究的问题均运用到“结构体”。在C语言中定义结构体的一般格式是：struct

结构体类型名

{ 类型名1变量名1；//数据子域 类型名2变量名2；

…… 类型名n变量名n；}；补充：结构体的定义在使用时必须声明一个具体的结构体类型的变量，声明创建一个结构体变量的方法是：

struct

结构体类型名结构体变量名；例如：

struct

ElemType /*定义结构体*/{intnum;charname[10];};struct

ElemTypex； /*声明结构体变量x*/

另外有一种方法是使用typedef

语句定义结构体，在声明结构体变量时可以不写struct，使得书写更加简便。例如：

typedef

struct{intnum;charname[10];}ElemType；

ElemType就是一个新的类型名，并且是结构体类型名。声明变量x的语句是：

ElemTypex;(1)通过“结构体变量名.数据子域”可以访问数据子域。例typedef

struct /*定义结构体Student*/{longnum; /*学号*/

intx; /*成绩*/charname[10]; /*姓名*/}Student;

补充：结构体的使用Students1;s1.num=1001;/*为s1的数据子域提供数据*/s1.x=83;补充：结构体的使用(2)通过“结构体指针->数据子域”访问数据域。在实际问题中还会使用到指向结构体的指针，通过以下语句段可以说明结构体指针的一般用法。Student*p; /*声明指针变量p*/p=(Student*)malloc(sizeof(Student));/*分配存储单元，首地址赋给p指针*/p->num=101;p->x=83;strcpy(p->name,"李明");numxnamep10183李明三、抽象数据类型

(AbstractDataType

简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作。抽象数据类型可以用以下的三元组来表示：

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

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

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

基本操作：<基本操作的定义>}ADT抽象数据类型名ADT常用定义格式例如，抽象数据类型复数的定义：

数据对象：

D＝{e1,e2｜e1,e2∈RealSet}

数据关系：

R1＝{<e1,e2>|e1是复数的实数部分

|e2

是复数的虚数部分}

ADTComplex{基本操作：

AssignComplex(&Z,v1,v2)操作结果：构造复数Z,其实部和虚部分别被赋以参数v1和v2的值。

DestroyComplex(&Z)操作结果：复数Z被销毁。

GetReal(Z,&realPart)初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。

GetImag(Z,&ImagPart)初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。

Add(z1,z2,&sum)初始条件：z1,z2是复数。操作结果：用sum返回两个复数z1,z2的和值。}ADTComplex1.4算法和算法分析一、算法//二、算法设计的原则//三、算法效率的衡量方法和准则四、算法的存储空间需求算法（algorithm）—解决某一特定问题的具体步骤的描述，是指令的有限序列。算法特性——有穷性一个算法必须在执行有限步骤之后结束确定性算法的每一步必须是确切定义的，不能产生二义性可行性算法是能行的输入一个算法有零个或多个输入输出一个算法有一个或多个输出算法的描述—采用类C语言算法的评价—衡量算法优劣的标准正确性(correctness)可读性(readability)健壮性(robustness)效率与低存储量三、算法效率的衡量方法和准则一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。

假如，随着问题规模n的增长，算法执行时间的增长率和f(n)

的增长率相同，则可记作：T(n)=

O(f(n))称T(n)为算法的(渐近)时间复杂度。10n2+4n+2=O(n2)它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。渐进符号（O）的定义：当且仅当存在一个正的常数C和n0

，使得对所有的

nn0

，有

T(n)

Cf(n)，则

T(n)=O(f(n))3n+2=O(n)/*3n+24nforn2*/3n+3=O(n)/*3n+34nforn3*/100n+6=O(n)

/*100n+6101nforn10*/10n2+4n+2=O(n2)/*10n2+4n+211n2forn5*/6*2n+n2=O(2n)

/*6*2n+n27*2nforn4*/如何估算算法的时间复杂度？

从算法中选取一种对于所研究的问题来说是基本操作

的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。n*n阶矩阵加法：for(i=0;i<n;i++) for(j=0;j<n;j++)

c[i][j]=a[i][j]+b[i][j];

语句的频度（FrequencyCount):重复执行的次数：n*n;T(n)=O(n2)即：矩阵加法的运算量和问题的规模n的平方是同一个量级变量计数x=0;y=0;for(intk=0;k<n;k++)x++;for(inti=0;i<n;i++)for(intj=0;j<n;j++)y++;T1(n)=O(1)T2(n)=O(n)T3(n)=O(n2)T(n)=T1(n)+T2(n)+T3(n)=O(max(1,n,n2))=O(n2)例2：for(i=1;i<=n;i++) for(j=1;j<=i;j++)for(k=1;k<=j;k++)

x=x+1;语句频度

=例3：分析以下程序段的时间复杂度i=1;①while(i<=n) i=i*2;②即f(n)≤log2n，取最大值f(n)=log2n所以该程序段的时间复杂度T(n)=O(log2n)例4：顺序查找，在数组a[i]中查找第一个值等于e的元素，返回其所在下标。

for(i=0;i<n;i++)if(a[i]==e)returni;return0;有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同

最好情况：1次

最坏情况：n

平均时间复杂度为：O(n)复杂度高复杂度低时间复杂度T(n)按数量级递增顺序为：1、指数时间的关系为：O(2n)<O(n!)<O(nn)

3、几个比较重要的时间复杂度排序：

2、四、算法的存储空间需求算法的空间复杂度定义为:

表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。S(n)=O(g(n))算法的存储量包括:1．输入数据所占空间2．程序本