数据结构_第一章绪论_第二章_第三章栈与队列

第一章 绪论,主讲教师:董金新 dongjinxinlcu.edu.cn,1.1 什么是数据结构 例11 图书馆中图书管理,考虑在图书馆中查找一本书的过程 查阅图书卡片，记下所要书的书号等信息； 将图书信息交给管理员； 管理员要库中查找此书； 找到，则办理借书手续 否则，报错：“此书不在库中”。其中图书在计算机中如何存储和管理？,图书馆中图书管理,例12 “人机对弈”问题,例13 多叉路口交通灯管理问题,多叉路口需设置多种颜色的交通灯才能使车辆之间不碰撞，又能达到最大流量。,B,A,C,D,E,数据结构： 一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间的关系和操作的学科。 它是计算机专业的专业基础课程 它是介于数学、硬件课程、软件课程之间的一门核心课程。,数据：数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。 数值性数据 非数值性数据 数据元素：数据的基本单位,用于完整地描述一个对象。 数据项：是数据的不可分割的最小单位。 数据对象：数据的子集。具有相同性质的数据成员（数据元素）的集合。 整数数据对象 N = 0, 1, 2, 学生数据对象:初等项（不可分割）、组合项（可再划分）,1.2 基本概念和术语,理解,数据结构:由相互之间存在一种或多种特定关系的数据元素的集合。程序=算法+数据结构,数据结构的形式化定义:Data_Structure = （D, R）其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。,例：课题小组 Group=(P,R) P=T,G1,Gn,S11,Snm1n3，1m2， R=R1,R2 R1= |1in, 1n3, R2= |1in, 1jm,1m2,数据结构依据视点的不同，分为数据逻辑结构和物理结构：,逻辑结构：从解决问题的需要出发，为实现必要的功能所建立的数据结构，它属于用户的视图，是面向对象的。(从操作对象抽象出来的数学模型)逻辑结构分集合、线性、树形、图形等. 物理结构：指数据该如何在计算机中存放，是数据逻辑结构的物理存储方式，是属于具体实现的视图，是面向计算机的。物理结构分顺序存储结构和链式存储结构 关系：物理结构是逻辑数据的存储映象 如何描述存储结构？,数据类型 定义：一组性质相同的值的集合, 以及定义于这个值集合上的一组操作的总称（操作，范围）。 数据结构的区别。 C语言中的数据类型char int float double void字符型 整型 浮点型 双精度型 无值为原子类型（不可分）。基于基本数据类型的构造类型称结构类型（可分成小的数据项）如数组型、构造型、文件型,抽象数据类型 (ADTs: Abstract Data Types),一个数学模型及定义在其上的一组操作 由用户定义，用以表示应用问题的数据模型 信息隐蔽和数据封装，使用与实现相分离（物理实现封装）,对于一个其数据成员完全相同的数据类型，如果给它赋予不同的语义，即定义具有不同功能的一组，则可形成不同的抽象数据类型。,例如: 相同的顺序表结构，语义不同：栈，先进后出；队列，先进先出。 抽象数据类型按数据的不同特性可分： 原子类型:变量的值是不可分解的。 固定聚合类型:变量的值由确定数目的成分按某种结构组成。 可变聚合类型:其值的成分数目不确定。,抽象数据类型的形式定义：我们用一个三元组来表示一个抽象数据类型。 （D，S，P） D是数据对象， S是D上的关系集， P是对D的基本操作。 格式： ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名 数据对象和数据关系的定义用伪码描述。 数据基本操作的定义格式：基本操作名（参数表）初始条件：初始条件描述操作结果：操作结果描述,ADT Triplet 数据对象：D=e1，e2,e3 |e1,e2,e3Elemset(定义了关系运算的某个集合) 数据关系：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& 除可提供输入值外，还将返回操作结果（P8） 多型数据类型：值的成分不确定的数据类型,1.3 抽象数据类型的表示与实现 Smalltalk C C+ Java类C、类Pascal、自然语言、算法语言等,(1)预定义常量和类型 #define TRUE 1 #define FALSE 0 #define ERROR 0 #define OK 1 #define INFEASIBLE -1 #define OVERFLOW -2 /Status 是函数类型，其值是函数结果状态代码 typedef int Status; (2) 数据结构的表示用类型定义(typedef)表示 (3)基本操作的算法 函数类型 函数名（函数参数表） /算法说明 语句序列 /函数名 (4) 赋值语句,(5) 选择语句 (6)循环语句 (7)结束语句 (8)输入和输出语句 (9)注释 (10)基本函数 (11)逻辑运算符 例7 抽象数据类型Triplet的表示和实现,typedef ElemType * Triplet； Status InitTriplet(Triplet ,1.4 算法和算法分析,定义：是对特定问题求解步骤的一种描述，它是指令的有限序列。 与程序的区别 特性： 输入 有0个或多个输入 输出 有一个或多个输出(处理结果) 确定性 每步定义都是确切、无歧义的 有穷性 算法应在执行有穷步后结束 可行性 每一条运算都能实现,算法设计的要求,正确性：对给定输入能得到预期的结果 可读性：编程人员能阅读和交流 健壮性：输入数据非法时能报错而不是出错。 效率：时间、空间两方面的效率都要高,算法效率的度量,事后统计法：在算法中的某些部位插装时间函数 time ( ) 测定算法完成某一功能所花费的时间 缺点： 1 必须先运行依据算法编制的程序 2 所得时间的统计量依赖于计算机的软硬件,算法的事前估计,不考虑计算机的软硬件，只考虑问题的规模（n） 时间复杂度:单位由1增加到n，g(n) 算法时间是由控制结构和原操作的决定的。 做法：选取一种是基本操作的原操作，以该基本操作重复的次数作为算法的时间量度。,例： +x;s=0; for (i=1;i<=n;+i) +x;s+=x; for (j=1;j<=n;+j)for (k=1;k<=n;k+)+x;s+=x; P15,时间复杂度度量,频度：语句重复执行的次数 程序步 语法上或语义上有意义的一段指令序列 执行时间与实例特性无关 例如： 注释：程序步数为0 声明语句：程序步数为0 表达式：程序步数为1,时间复杂度的渐进表示法,大O表示法:T(n)=f(n)=O(n),渐进度量值 渐进时间复杂度：T(n)=O(f(n) 加法规则 针对并列程序段 T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m) c < log2n < n < nlog2n < n2 < n3 < 2n < 3n < n! （图1.7）,乘法规则 针对嵌套程序段T (n, m) = T1 (n) * T2 (m) = O(f (n)*g (m) 在难以精确计算语句频度的情况下，只需求出关于n的增长率即可 有的时候，频度还和问题的输入数据集有关，这时候考虑最坏的情况 课本p16void bubble(int a ,int n) int i,j,t;for (i=n-1;i>=1;i-)for (j=0;jaj+1)t=aj;aj=aj+1;aj+1=t; ,void bubble(int a ,int n) int i,j,t;for (i=n-1,change=TRUE;i>=1 ,思考： i=1; While (i<=n)i=i*3;,空间复杂度度量,存储空间的固定部分 程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占的空间 可变部分 尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用的空间、通过new和delete命令动态使用的空间 原地工作：额外空间相对于输入数据量是常数,S (n) = O(f (n) S(n)： 渐进空间复杂度,算法与程序,(1).一个程序不一定满足有穷性。例操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。 (2).程序中的指令必须是机器可执行的，而算法中的指令则无此限制。,第二章 线性表,在数据元素的非空的有限集合中： 存在唯一的一个被称为“第一个”的数据元素； 存在唯一的一个被称为“最后一个”的数据元素； 除第一个元素外，集合中每个元素都有且仅有一个前驱； 除最后一个元素外，集合中每个元素都有且仅有一个后继；,第二章 线性表,2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现2.3.1 线性链表2.3.2 循环链表2.3.3 双向链表2.4 一元多项式的表示及相加,一、线性表定义 1. 线性表(Linear List) 2. 线性表(线性结构)的逻辑特征： 3. 线性表的抽象数据类型定义 二、线性表的运算 例2-1 例2-2,2.1 线性表的类型定义,1. 线性表(Linear List)定义,由n(n0)个数据元素(结点)a1，a2， an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n>0)记作：(a1，a2，an) 这里的数据元素ai(1in)只是一个抽象的符号，其具体含义在不同的情况下可以不同。,例1、26个英文字母组成的字母表（A，B，C、Z） 例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。（6，17，28，50，92，188） 例3、学生健康情况登记表如下：,在非空线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2； 有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1； 其余的内部结点ai(2in-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。 线性表是一种典型的线性结构。,2. 线性表(线性结构)的逻辑特征,ADT List 数据对象：D ai|aiElemSet,i=1,2,n,n>=0 数据关系：R1=|ai-1,aiD,i=2,n InitList(&L) 操作结果：构造一个空的线性表L. DestoryList(&L)初始条件：线性表L已经存在。操作结果：销毁一个线性表L. ClearList(&L ) 初始条件：线性表L已经存在。操作结果：将L重置为空表。,