[研究生入学考试]数据结构第一讲PPT课件

数据结构,第一讲,绪论,线形表,栈和队列,串,第1章绪论,1数据（Data）：所有能输入到计算机中并被计算机程序处理的描述客观事物的符号的集合。（数字、字符、声音、图形、图像等）分类:数值性数据非数值性数据,1.1数据结构的基本概念,2数据元素(Dataelement)：数据的基本单位。（又称为结点、顶点、记录）。数据元素也可以由若干数据项(最小单位)构成。,例如：,描述一个学生的数据元素,称之为组合项,原子项,1.1数据结构的基本概念,3数据类型(Datatype)：具有相同性质的计算机数据的集合及在这个集合上的一组操作。,如：C语言中的整型变量int,值的范围是：-3276832767操作是：+，-，*，/，%,原子数据类型:不可分解,由计算机语言提供.如：C语言：int、float、char结构数据类型:可分解,借用计算机语言提供的一种描述数据元素之间的逻辑关系的机制,由用户自己定义.如：C语言：数组、结构体、共用体,1.1数据结构的基本概念,4数据结构（datastructure）:数据之间的相互关系，即数据的组织形式。一般包括三方面内容：数据的逻辑结构数据元素之间的的逻辑关系。数据的存储（物理）结构数据的逻辑结构在计算机存储器中的表示。数据的运算对数据施加的操作。,（数据运算）,（算法实现）,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(1data=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为（）,。in=in-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顺序队列,循环队列：将存储队列的数组头尾相接。,如何解决假溢出？,01234,入队,出队,a3,a4,a5,a6,a3,a2,a1,0,1,2,3,N-1,rear,front,循环队列,顺序队列,a3,a2,a1,front,rear,0123.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,J2J3,J1J4,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=a1a2.an(n0),串(String)即字符串，是由(n0)零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。,ai(1in):字母、数字或其他字符。i称为字符ai在串中的位置;思考：“w”与w两概念相同吗？答：不同，前者是字符串，后者是字符。,4.1.1串的基本概念,若干术语：串长：串中字符个数（n0）.空串：（nullstring）零个字符的串，长度为0。空白串：由一个或多个空格符组成的串。子串：串s中任意个连续的字符序列叫s的子串;s叫主串。子串位置：子串在主串中的位置，即子串的第一个字符在主串中的位置。字符位置：字符在串中的序号。串相等：串长相等，且对应位置上字符相等。,4.1.1串的基本概念,练习1：串是由字符组成的序列，一般记。,练习2：现有以下4个字符串：a=BEIb=JINGc=BEIJINGd=BEIJING,问：他们各自的长度？b是哪个串的子串？在主串中的位置是多少？,a=3，b=4，c=7，d=8,a是c和d的子串，在c中的位置是4,在d中的位置是5.,练习3：空串和空白串有无区别？答：有区别。空串(NullString)是指长度为零的串；而空白串(BlankString),是指包含一个或多个空格字符的字符串。,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”一般：1istrlen(S);0j即可,）串比较strcmp(S,T)即：比较两个串的ASCII码值的大小。eg:result=strcmp(“abcdef”,”ababa”);/reault0result=strcmp(“abcd”,”abcd”);/reault=0result=strcmp(“abcde”,”abfeg”);/reault0,4.1.串的基本运算,6）串插入insert(S1,i,S2)即：把串S2插入到串S1的第i个字符之后。(1istrlen(S1)eg:S1=“shangdianli”S2=“hai”insert(S1,5,S2)=“shanghaidianli”,7）串删除delete(S,i,j)即：从串S中删除第i个字开始的连续j个字符。(1istrlen(S)eg:S=“shangdianhai”delete(S,6,4)=“shanghai”delete(S,10,5)=“shangdian”,4.1.串的基本运算,8）子串定位index(S1,S2)即：求子串S2在主串S1中的位置。若有:则返回S2在S1中首次出现的位置;若无:则返回0.eg:index(“abcdbce”