数据：能够被计算机输入、存储、处理、输出的一切信息,数据元素：是一个数据整体中相对独立的单位（记录 文件，字符 字符串，下标变量 数组）,数据记录：由一个或若干个数据项组成,一、几个概念：,关键数据项：能唯一标识一个记录的数据项。,关键字：关键项中的每一个值。,数据结构的基本知识,数据的逻辑结构（数据以及数据之间的联系，如哪个元素是第一个元素、哪个元素是第二个元素、哪些元素在给定的元素之前或之后）,数据的物理结构（数据在计算机中的存储方式，数据的存放方式有顺序、链接、索引、散列等 ）,数据的处理（查找、插入、删除、合并、排序、统计、简单计算、输入、输出等）,二、数据结构的研究内容,(1)一般用二元组描述：B=(K，R)B代表一种数据结构K代表数据元素的集合R代表K上的二元关系的集合,1、数据的逻辑结构,(2)常用的三种结构,线性结构,K=1,2,3,4,5,6,7,8,9,10 R=r 表示只包含一种关系 r=,举例：10个学生按学号排列 示意图： ,特点：每个数据只有一个前驱、一个后继（第一个元素无前驱，最后一个元素无后继） 是1：1的关系。,树型结构,举例：一个领导与被领导的关系(14人，单向) 示意图：,K=1,2,3,4,5,6,7,8,9,10,11,12,13,14 R=r r=,，, ,特点：除第一个结点外，都有一个前驱，可有多个后继 ；最下一层只有前驱无后继 ，是1：N的关系。,图型结构,举例：人与人之间互相认识的关系(双向的) 示意图：,K=1,2,3,4,5,6,7,8,9,10 R=r r=,6,7 双向,特点：每个结点都可有多个前驱和多个后继 ，M：N的关系。, 顺序存储 把逻辑上相邻的结点存储在物理上相邻的存储单元,链接存储 给结点加上指针域。每个结点的存储单元由数据域和指针域两部分组成。,2、数据的存储结构,索引存储 用结点的索引号来确定结点的存储地址,散列存储 根据结点的值来确定结点的存储地址,查找、插入、删除、合并、排序、统计、简单计算、输入、输出等。,算法实质上是针对所处理问题的需要，在数据的逻辑结构和存储结构的基础上所施加的一种运算。 如何设计数据的逻辑结构 如何选择数据的物理结构 如何优化设计思想和技巧,学习数据结构的目的 优化算法,3、数据的处理,(1)算法的描述 采用“类Pascal语言”，一般以过程和函数的形式书写,(2)算法的特点确定性有穷性可行性有0个或多个输入有输出,(3)算法的评价 时间复杂性：T(n)依赖于问题的规模 空间复杂性：S(n)所占用的存储空间,一般采取事前分析估算法来评价算法。,算法常见的数量级有： O(1) 问题规模的变化对复杂性影响小，这类算法是十分优秀的。 O(n) 算法复杂性是问题规模的线性函数，这类算法是很好的。 O(nlog2n) 虽比O(n)差，但仍属不错 O(nk) 尽可能改进，使k值愈小愈好。 O(2n) n较大时，复杂性会变得很大。,例： 求Y=anxn+an-1xn-1+an-2xn-2+a1x+a0 分析：次数n是问题的规模,算法： y:=a0； for k:=1 to n dobegint:=ak；for i:=1 to k do t:=t*x； 计算akxky:=y+tend； writeln(y=，y)；,内循环计算akxk用了k次乘法，计算y共用乘法的次数为123n，即n(n+1)/2，时间复杂度为n2，空间复杂度为n,算法： b0:=1； for k:=1 to n dobk:=bk-1*x； y:=a0； for k:=1 to n doy:=y+ak*bk； writeln(y=，y)；,增加数组b0至bn，用于存放x0，x1，x2，xn，则该算法的时间复杂度和空间复杂度均为2n,算法：将y的计算公式改写为 y=(an*x+an-1)*x+an-2)+a1)*x+a0 如y =7x5+4x4-8x3+6x+2 ，可改写为 y=(7x+4)x-8)x+6)x+2，其中 a5=7，a4=4，a3=-8，a2=0，a1=6，a0=2,y:=an； for i:=n-1 to 0 doy:=y*x+ai； writeln(y=，y)；,算法的时间复杂度为n，空间复杂度也为n，是三个算法中效果最好的。,三个算法的复杂性比较如下：,当n=100时，三种算法的复杂性：,1.请估计下面算法的时间复杂性(以乘法作为估计时间的基础) beginfor i:=1 to n dofor j:=1 to n dobeginci,j:=0;for k:=1 to n doci,j:=ci,j+ai,k*bk,jend; end 2.请估计下面算法的时间复杂性(以加法作为估计时间的基础) beginx:=0;y:=1;for i:=1 to n dofor j:=1 to i dofor k:=1 to j dox:=x+y end,时间复杂性和空间复杂性在一定条件下是可以相互转化的，由于目前计算机硬件发展很快，内存空间比较充分，因此在算法设计时，常会采用用空间换时间的作法，以优化程序的设计。,线性表（linear-list）是最常用、最简单的一种数据结构。,一、顺序存储 1.定义constlmaxlen=最大长度；typeelemtype =元素的数据类型；list=recorddata：array1lmaxlen of elemtype ；last：0lmaxlenend；,线性表,初始化initial(a)：设置一个空的线性表a 求长度length(a)：求数据元素的个数 获取元素getlist（a，i，x)：取第i个元素 定位loclist(a，x)：搜索第一个值为x的数据元素的序号，若不存在，则返回0。 插入inslist(a，i，x)：把给定元素x插入到线性表的第i个位置。 删除dellist（a，i)：删除第i个数据元素。 判断线性表是否满fulllist(a) 判断线性表是否空emplist(a),2、基本操作,1.单链表定义typeelemtype =单链表中结点的数据类型link=node；node=recorddata： elemtype ； next：linkend；,二、链接存储,2、单链表基本操作,初始化intlkst(head)：为单链表建立头元素 建立单链表crtlkst(head) 求单链表的长度lenlkst(head)：求出元素个数 求单链表中第i个元素的位置getlkst(head，i)：取第i个元素的指针，函数值为link类型。 插入元素inslkst(head，i，x)：在第i个元素之前 删除第i个元素dllkst(head，i) 查找元素loclkst(head，x)：返回该元素在链表中第一次出现的结点指针，否则返回空指针。 判断链表是否为空(emplkst(head),3、双向链表基本操作,在单链表中，从某个结点出发只能顺指针往后查找结点。若要寻找某个结点的前驱，只有从表头指针出发。 双向链表：在每个结点中设置两个指针域，分别用以指向其前驱结点和后继结点。,第一个结点无前驱，最后一个结点无后继。,3、循环链表基本操作,附加表头结点：在第一个结点之前增加一个结点，并让头指针指向这个结点。,带附加表头结点的单链表和双向链表,带附加表头结点的循环单链表和循环双向链表,栈（stack）：限定只能在表尾进行插入、 删除数据元素的线性表。(后进先出表LIFO) 栈顶(top)：允许插入和删除数据元素的一端。 栈底（bottom ）：固定的一端。 空栈：不含任何元素。 进栈(压栈)：插入元素。 出栈(退栈)：删除元素。,一、栈的概念,栈,二、顺序存储 1.定义 用一组连续的存储单元依此存放自栈底到栈顶的数据元素，同时设立指针top（称为栈顶指针）以指示栈顶元素的当前位置。,1.设栈S的初始状态为空，现有序列1,2,3,4,5，对该序列在栈S上依次进行如下操作（从序列中的1开始）：进栈、进栈、进栈、出栈、进栈、出栈、进栈。问出栈的元素序列是：,3,4,2.若进栈的序列是1、2、3、4、5，问能否得到出栈序列4、3、5、1、2 ？,1,2,3,出栈的元素,3,3,4,4,4,5,出栈的元素,1,2,3,4,4,4,3,3,5,5,5,此时能出栈的只能是2,不能,const smaxsize=栈的最大长度； type elemtype=栈中元素的数据类型；stack=recorddata：array1smaxsize of elemtype；top：0 . . smaxsizeend； vars:stack;,2、基本操作,栈的初始化setnull(s)：将s设为空栈 procedure setnull(var s：stack)； beginstop:=0 end；,判断栈空sempty(s)：true或false。 function sempty(s：stack)：boolean； beginsempty:=(s.top=0)； end；,入栈push(s，x)：若栈S不满，把元素x插入到栈顶；否则返回信息overflow(上溢)。 procedure push(var s:stack；x:elemtype)； beginif s.top=smaxsize then writeln(overflow)else begins.top:=s.top+1； s.datas.top:=xend end；,出栈pop(s,x)：若栈s不空，把栈顶元素赋给x，栈顶指针下移；否则返回信息underflow（下溢）。 procedure pop(var s：stack;var x: elemtype)； beginif s.top=0 then writeln(underflow)else beginx:=s.datas.top;s.top:=s.top -1；end end；,出栈也可用函数来实现： function pop(var s：stack): elemtype ； beginif s.top =0 then writeln(underflow)else beginpop:=s.datas.top;s.top:=s.top -1；end end；,出栈操作之后，原栈顶元素依然存在，只是栈顶指针下移，不再指向它。,取栈顶元素readtop(s)：若栈s不空,，返回栈顶元素的值；否则返回信息underflow。 function gettop(s:stack)：elemtype ； begin if s.top=0 then writeln(underflow)else readtop:=s.datas.top end；,提醒,这个算法中栈顶指针保持不变,注意与pop(s)的区别 。,当应用中需设立两个栈时(元素类型一致)，可以使它们共享一维数组空间s1max，两个栈的栈底分别设在数组两端，让两个栈彼此迎面“增长”。仅当两个栈的栈顶指针在中间相遇时才发生“上溢” 。,栈1,栈2,3、双栈操作,const t=可用空间大小 typeelemtype =栈中元素的数据类型bothstack=recorddata：array1t of elemtype ；top1，top2：0t+1end； varbs:stack;k:12; k=1表示栈1，k=2表示栈2,栈满、上溢、下溢条件各是什么？ 置空栈算法 插入算法 删除算法,