[研究生入学考试]数据结构第一讲.ppt

数据结构,第一讲,绪论,线形表,栈和队列,串,第1章 绪论,1 数据（Data）：所有能输入到计算机中并被计算机程序处理的描述客观事物的符号的集合。 （数字、字符、声音、图形、图像等） 分类: 数值性数据 非数值性数据,1.1 数据结构的基本概念,2 数据元素(Data element)：数据的基本单位。（又称为结点、顶点、记录）。 数据元素也可以由若干数据项(最小单位)构成。,例如：,描述一个学生的数据元素,称之为组合项,原子项,1.1 数据结构的基本概念,3 数据类型(Data type)：具有相同性质的计算机数据的集合及在这个集合上的一组操作。,如：C语言中的整型变量int,值的范围是： - 32768 32767 操作是：+，-，*，/，%,原子数据类型:不可分解,由计算机语言提供. 如：C语言：int、float、char 结构数据类型:可分解,借用计算机语言提供的一种描述数据元素之间的逻辑关系的机制,由用户自己定义. 如：C语言：数组、结构体、共用体,1.1 数据结构的基本概念,4 数据结构（data structure）:数据之间的相互关系，即数据的组织形式。 一般包括三方面内容： 数据的逻辑结构数据元素之间的的逻辑关系。 数据的存储（物理）结构数据的逻辑结构在计算机存储器中的表示。 数据的运算对数据施加的操作。,（数据运算）,（算法实现）,1.1 数据结构的基本概念,逻辑结构直接前趋和直接后继最多只有一个。 存储结构顺序or链式依具体实际而定。 数据运算插入、删除、检索等。,分析：,1.1 数据结构的基本概念,根据数据元素间关系的不同特性，有四种基本结构： 集合 同属关系 线性结构一对一，如线性表、栈、队列 树形结构一对多，如树 图状结构多对多，如图 （网状结构）,线性,非线性,1）数据逻辑结构分类：,1.1 数据结构的基本概念,2）数据存储结构分类：,1.2 算法描述和算法分析,算法（Algorithm）对特定问题求解步骤的一种描述，是若干条指令组成的有穷序列。 算法五个重要特性 输入 有0个或多个输入。 输出 有一个或多个输出(处理结果)。 有穷性 算法应在执行有穷步后结束。 确定性 每步定义都是确切、无歧义的。 可行性 算法中描述的操作可以通过对基本运算执行有限次来实现。,注：算法 程序,有穷性,课堂练习： (1)顺序存储结构中数据元素之间的逻辑关系是由( )表示的，链式存储结构中的数据元素之间的逻辑关系是由( )表示的。 线性结构 非线性结构 存储位置 指针 答案：、 (2)( )不是算法所必须具备的特性。 有穷性 确切性 可运行性 可行性 答案： (3)在数据结构中,数据的运算是定义在数据的( ). 逻辑结构 物理结构 物理和存储位置 存储结构 答案：A,2.1 线性表的概念及运算,（a1, a2, ai-1，ai, ai1 ，, an）,1. 线性表的定义：n(n0)个相同类型数据元素的有限序列。,n=0时称为,数据元素,开始结点,ai的直接前趋,ai的直接后继,下标，是元素的序号，表示元素在表中的位置,n为元素总个数，即表长,空表,终端结点,2.1 线性表的概念及运算,线性结构的逻辑特征: 对于一个非空的线性表: 1) 有且仅有一个开始结点a1,它无直接前趋,仅有一个直接后继a2； 2) 有且仅有一个终端结点an,它无直接后继,仅有一个直接前趋an-1； 3) 其余的内部结点ai (1in),都有且仅有一个直接前趋ai-1和一个直接后继ai+1 .,2.2 线性表的顺序存储,一 顺序表,用一组地址连续的存储单元依次存储线性表的元素，可通过静态数组Vn或动态数组来实现。,把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。,线性表的顺序表示又称为顺序存储结构或顺序映像。,顺序存储定义：,顺序存储方法：,简言之，逻辑上相邻，物理上也相邻,2.2 线性表的顺序存储,线性表顺序存储特点：,1. 逻辑上相邻的数据元素，其物理上也相邻； 2. 若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出。计算方法是： 设首元素a1的存放地址为LOC(a1)（称为基地址）， 设每个元素占用存储空间（地址长度）为C字节， 则表中任一数据元素的存储地址为： LOC(ai+1) = LOC(ai)+C LOC(ai) = LOC(a1) +（i-1） * C (1in),注意：C语言中数组的下标从0开始， 即：Ln的有效范围是L0Ln-1,2.2 线性表的顺序存储,线性表的顺序存储结构示意图,地址 内容 元素在表中的位序,1,i,2,n,空闲区,i+1,C,b=LOC(a1),b + C,b +(i-1)*C,b +(n-1)*C,b +(max-1)*C,顺序表是一种随机存取的存储结构,2.2 线性表的顺序存储,一个一维数组，下标的范围是到，每个数组元素用相邻的4个字节存储。存储器按字节编址，设存储数组元素的第一个字节的地址是，则的第一个字节的地址是,例1,因此：LOC( M3 ) = 98 + 4 (3-0) =110,解：地址计算通式为：,LOC(ai) = LOC(a1) + L *（i-0）,2.2 线性表的顺序存储,二 基本运算,1 插入 Insert(L,x,i) /在线性表L的第i个位置插入值为x的结点 插入前：(a1, , ai-1, ai, , an) 插入后：(a1, , ai-1, x , ai, , an),ai-1和ai之间的逻辑关系发生了变化,顺序存储要求存储位置反映逻辑关系,存储位置要反映这个变化,2.2 线性表的顺序存储,例：（35，12，24，42），在i=2的位置上插入33。,表满：last+1=MaxSize 合理的插入位置：1in+1（i指的是元素的序号）,4,35,12,24,42,a1,a2,a3,a4,0 1 2 3 4 表长,42,24,12,33,什么时候不能插入？,共移动（n-i+1）个元素！,2.2 线性表的顺序存储,时间复杂度分析：,讨论：若在长度为 n 的线性表的第 i 位 插入一个元素，则向后移动元素的次数f(n)为: f(n) =,最好情况（ i =n+1）：移动元素次数0次，时间复杂度为O(1)。 最坏情况（ i =1）：移动元素次数n次，时间复杂度为O(n)。 平均情况（1in+1）：时间复杂度为O(n)。,n i + 1,2.2 线性表的顺序存储,ai-1和ai之间的逻辑关系发生了变化,顺序存储要求存储位置反映逻辑关系,存储位置要反映这个变化,2 删除 Delete(L,i) /删除线性表L的第i个位置结点 删除前：(a1, , ai-1, ai, , an) 删除后：(a1, , ai-1, ai+1, , an),2.2 线性表的顺序存储,例：（35, 33, 12, 24, 42），删除i=2的数据元素。,5,35,a1,a2,a3,a4,0 1 2 3 4,42,24,12,33,a5,12,24,42,合理的删除位置：1in（i指的是元素的序号）,什么时候不能删除？,共移动（n-i）个元素！,2.2 线性表的顺序存储,2.2 线性表的顺序存储,时间复杂度分析：,讨论：若在长度为n的线性表上删除第i位元素，向前移动元素的次数f(n)为： f(n) =,n i,最好情况（ i =n）：移动元素次数0次，时间复杂度为O(1)。 最坏情况（ i =1）：移动元素次数n-1次，时间复杂度为O(n)。 平均情况（1in）：时间复杂度为O(n)。,课堂练习,向一个长度为n的顺序表的第i个元素(1in+1)之前插入一个元素时，需向后移动( )个元素;删除第i个元素(1in)时，需向前移动( ) 个元素。 若线形表采用顺序存储结构,在等概率情况下,在长度为n的线形表中删除一个元素平均需要移动( )个 数据元素,插入一个数据元素平均需要移动( )个数据元素. 假设顺序存储的线性表,每个结点占4个存储单元,设LOC(a1)=1000,则LOC(a8)=( );若共100个结点,则最后一个结点LOC(100)=( );若删除第40个结点,则需要移动( )个结点,在第50个结点之前插入一个结点,则需要 移动( )个结点.,2.3 线性表的链式存储,存储特点： 逻辑次序和物理次序 不一定相同。 2.元素之间的逻辑关系 用指针表示。,例：(a1, a2 ,a3, a4)的存储示意图,a1 0200,a2 0325,a3 0300,a4 ,2.3.1 单链表,单链表是由若干结点构成的；每个结点结构有两个部分组成：,data：数据域，存储数据元素 next：指针域（链域），存储指向后继结点的地址,开始结点,头指针,2.3.2 单链表上的基本运算,1 单链表的查找运算 按序号查找:查找第i个结点 0in,核心操作（关键操作）：p指针后移。从头结点出发，通过p指针的反复后移而将整个单链表“审视”一遍的方法称为扫描（或遍历）。 需要设置一个计数器,随p的后移一起记数.,head,a1,a2,an,ai,顺藤摸瓜,时间复杂度为O(n)。,2.3.2 单链表上的基本运算,2 单链表的插入运算 假设p指向某一结点, s指向待插入的值为x的新结点, 将s插入在p之后.,插入步骤（即核心语句）：,思考：步骤1和2能互换么？,不能互换！,1,2,平均时间复杂度为O(1),s=malloc(sizeof(linklist); s-data=x; Step1:s-next=p-next; Step2:p-next=s;,2.3.2 单链表上的基本运算,3 单链表的删除运算,分析:删除*p的后继简单,设r指向被删结点,则:,删除步骤（即核心语句）： r=p-next; p-next=r-next; free(r);,2.3.3 循环链表,特点： 1、尾结点的指针域指向头结点。 2、从任一结点出发均可找到表中其他结点。 3、操作时仅循环条件与单链表不同：（判表空） 单链表 用 p = NULL (不带头结点) 或 p -next =NULL(带头结点) 循环链表用 p= =head(不带头结点) 或 p-next = head(带头结点),head,a1,ai-1,an,ai,2.3.4 双链表,常用双向循环链表，如空的双向循环链表为：,ai-1,ai,ai+1,特点： 1.从任一结点出发均可找到表中其他结点。 2. p-prior-next=p=p-next-prior;,2.3.4 双链表,双向链表的操作插入实现(后插),a,注意指针修改的相对顺序,核心语句： s=malloc(sizeof(dlinklist); s-data=x; s-prior=p; s-next=p-next; p-next-prior=s; p-next=s;,b,c,d,2.3.4 双链表,双向链表的操作删除实现(删p本身),ai-1,ai,ai+1,核心语句： p-prior-next=p-next; p-next-prior=p-prior; free(p);,课堂练习,不带头结点的单链表H为空表的条件是( )。带头结点的单链表H为空表的条件是( )。 带头结点的单循环链表H为空表的条件是( )。 单链表中，在指针p所指结点之后插入s结点的操作为（ ）。 A.snext=pnext; pnext=s; B.pnext=s; snext=pnext; C,pnext=snext; snext=p; D.snext=p; pnext=snext;,3.1.1 栈的概念和运算,1、栈的基本概念,空栈：不含任何数据元素的栈。,栈：限定仅在一端进行插入和删除操作的线性表。,允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)。 数据元素之间的逻辑关系：一对一 。,（a1, a2, , an）,3.1.1 栈的概念和运算,注： 栈的运算规则 只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。 入栈：插入元素到栈顶（即表尾）的操作。 出栈：从栈顶（即表尾）删除最后一个元素的操作。 入栈操作演示 出栈操作演示,3.1.1 栈的概念和运算,a1,a2,a3,入栈,插入：入栈、进栈、压栈,入栈的操作示图：,3.1.1 栈的概念和运算,a1,a2,a3,删除：出栈、弹栈,出栈的操作示图：,栈的操作特性：后进先出,出栈,3.1.1 栈的概念和运算,思考题：一个栈的输入序列为123，若在入栈的过程中允许出栈，且每个元素只允许进一次栈，则可能得到的出栈序列有哪些？,答：,可以通过穷举所有可能性来求解： 1入1出， 2入2出，3入3出， 即123； 1入1出， 2、3入3、2出， 即132； 1、2入，2出， 3入3出， 即231； 1、2入，2、1出，3入3出， 即213； 1、2、3入，3、2、1出， 即321； 合计有5种可能性。,3.1.1 栈的概念和运算,思考题：,设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是： ）a，b，c，d ）c，d，a，b ）b，c，d，a ）a，c，d，b,A、D可以（ B、C不行）。,答：,3.1.2 顺序栈,顺序栈栈的顺序存储结构,如何改造数组实现栈的顺序存储？,a1,确定用数组的哪一端表示栈底。,附设指针top指示栈顶元素在数组中的位置。,S,3.1.2 顺序栈,进栈核心语句： s-top+; s-datas-top=a1;,栈空：s-top = -1,a1,a2,进栈的操作步骤如何？,3.1.2 顺序栈,出栈核心语句： s-top-;,边界条件 栈空：s-top= = -1;,a1,a2,出栈的操作步骤如何？,课堂练习,栈是一种特殊的线性表，允许插入和删除运算的一端称为 ;不允许插入和删除运算的一端称为 。 若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为（ ）,若p1=1，则pi为（ ）,。 i n=i n-i+1 不确定,3.2 队列,1 逻辑结构,空队：不含任何数据元素的队列。,（a1, a2, , an）,队列：只允许在一端进行插入操作，而在另一端进行删除操作的线性表。 。,允许插入的一端称为队尾，另一端允许删除的称为队头。 数据元素之间的逻辑关系：一对一 。,3.2.1 队列的概念和运算,注： 队列的运算规则 只能在队尾进行插入运算，在队头进行删除运算;且访问结点时依照先进先出（FIFO）或后进后出（LILO）的原则。 入队：插入元素到队列的队尾的操作。 出队：从队头删除一个元素的操作。 问：队列与一般线性表有什么不同？ 一般线性表 队列 逻辑结构：一对一 逻辑结构：一对一 存储结构：顺序表、链表 存储结构：顺序队、链队 运算规则：随机存取 运算规则：先进先出 (FIFO),3.3.2 顺序队列,如何改造数组实现队列的顺序存储？,a1,确定用数组的如何表示队头、队尾。,附设指示器rear指示队尾元素（在数组中最后一个元素的位置），指示器front指示队头（队头元素所在位置的前一位置）。,S,3.3.2 顺序队列,实例1：a1a2a3a4依次入队,a1,a2,a3,a4,入队核心语句： sq-rear+;,3.3.2 顺序队列,实例2：a1a2依次出队,a1,a2,a3,a4,队列的移动有什么特点？,出队核心语句： sq-front+;,3.3.2 顺序队列,假溢出：当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，尽管此时数组的低端还有空闲空间，这种现象叫做假溢出。,继续入队会出现什么情况？,a3,a4,a5,3.3.2 顺序队列,循环队列：将存储队列的数组头尾相接。,如何解决假溢出？,0 1 2 3 4,入队,出队,a3,a4,a5,a6,a3,a2,a1,0,1,2,3,N-1,rear,front,循环队列,顺序队列,a3,a2,a1,front,rear,0 1 2 3 . . N-1,新问题：在循环队列中，空队特征是front=rear；队满时也会有front=rear；判决条件将出现二义性！ 解决方案： 浪费一个单元，令队满特征为front=(rear+1)%N；,3.3.2 顺序队列,队空条件 : front = rear (初始化时：front = rear ) 队满条件： front = (rear+1) % N (N=maxsize) 队列长度：L=（Nrearfront）% N,J2 J3,J1 J4,J5,front,rear,问2： 在具有n个单元的循环队列中，队满时共有多少个元素？,n-1个,5,问1：左图中队列长度L=？,3.3.2 顺序队列,例： 一循环队列如下图所示，若先删除4个元素，接着再插入4个元素，请问队头和队尾指针分别指向哪个位置?,解：由图可知，初始状态,队头和队尾指针的初态分别为front=0和rear=5。,删除4个元素后(front+4)%6=4； 再插入4个元素后，r=(rear+4)%6=(5+4)%6=3,J1,J2,J5,J6,J7,J8,J9,J3,J4,课堂练习,设栈S和队列Q初始状态为空，元素a、b、c、d、e和f依次通过栈S，一个元素出栈后即进入队列，若6个元素出队的序列是bdcfea，则栈S的容量至少应该存多少个元素，请画出进出栈状态。 若用一个大小为7的数组实现循环队列，且当前front=4,rear=0，则当从队列中删除2个元素，再加入3个元素后，front= , rear= ,当前队列长度为 。,4.1 串及其运算,记为： s =“a1 a2 an “ (n0 ),串(String)即字符串，是由(n0)零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。,ai(1in):字母、数字或其他字符。 i称为字符ai在串中的位置; 思考：“w” 与 w两概念相同吗？ 答：不同，前者是字符串，后者是字符。,4.1.1 串的基本概念,若干术语： 串长：串中字符个数（n0）. 空串：（null string）零个字符的串，长度为0。 空白串：由一个或多个空格符组成的串。 子串：串s中任意个连续的字符序列叫s的子串; s叫主串。 子串位置：子串在主串中的位置，即子串的第一个字符在主串中的位置。 字符位置：字符在串中的序号。 串相等：串长相等，且对应位置上字符相等。,4.1.1 串的基本概念,练习1：串是由 字符组成的序列，一般记 。,练习2：现有以下4个字符串： a =“BEI“ b =“JING“ c = “BEIJING“ d =“BEI JING“,问： 他们各自的长度？ b是哪个串的子串？在主串中的位置是多少？,a =3，b =4，c = 7，d=8,a是c和d的子串，在c中的位置是4,在 d中的位置是5.,练习3：空串和空白串有无区别？ 答：有区别。空串(Null String)是指长度为零的串；而空白串(Blank String),是指包含一个或多个空格字符的字符串。,0个或多个,s=“a1a2an“,4.1. 串的基本运算,）赋值 eg: S1=“shanghai”; S2=“dianli”; S3=S1; S4=“”;,2）串联接 strcat(S1,S2) 即：把两个串连接形成一个长度为两个串长度之和的新串。 eg: strcat(S1,S2); 则：S1=“shanghaidianli”,3）求串长 strlen(S) eg: strlen(S2)=6; strlen(S4)=0;,4.1. 串的基本运算,4）求子串 substr(S,i,j) 即：从串S中的第i个字符开始连续抽出j个字符构成一个新串。 eg: substr(S1,6,3) substr(S2,5,5) =“hai” =“li” 一般：1 i strlen(S); 0 j即可,）串比较 strcmp(S,T) 即：比较两个串的ASCII码值的大小。 eg: result=strcmp(“abcdef”,”ababa”); /reault0 result=strcmp(“abcd”,”abcd”); /reault=0 result=strcmp(“abcde”,”abfeg”); /reault0,4.1. 串的基本运算,6）串插入 insert(S1,i,S2) 即：把串S2插入到串S1的第i个字符之后。( 1i strlen(S1) eg: S1=“shangdianli” S2=“hai” insert(S1,5,S2)=“shanghaidianli”,7）串删除