数据结构知识点总结-有工大老师多年经验编写(课堂PPT).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构与算法,课堂讲义,哈尔滨工业大学 计算机科学与技术学院,计算机系列课程之间的联系,1,数据结构涵盖的内容,2,二,.,基本概念和术语,1,.,数据,数据是用于描述客观事物的数值、字符，以及一切可以输入到计算机中的并由计算机程序加以处理的符号的集合。其范围随着计算机技术的发展而不断发展。,2.,数据元素,数据的基本单位是数据元素，在计算机程序中通常作为一个整体进行考虑和处理。,3.,数据项,是数据的不可分割的最小单位，一个数据元素可由若干个数据项组成。,4.,数据对象,性质相同的元素的集合叫做数据对象。,3,5.,结点,数据元素在机内的位串表示，即数据元素在计算机内的映象。,6.,域,/,字段,当数据元素由若干个数据项组成时，位串中对应于各个数据项的子串称为域,/,字段，是数据元素中数据项在计算机中的映象。,7.,信息表,计算机程序所作用的一组数据通常称为信息表，是数据对象在计算机中的映象。,4,8.,数据结构,数据结构指的是数据元素之间的相互关系，这种关系是抽象的，即并不涉及数据元素的具体内容。是数据元素及其相互间的关系的数学描述。,9.,逻辑结构和存储结构,(1),逻辑结构,数据结构中描述的是数据元素之间的抽象关系,(,逻辑关系,),，称为逻辑结构。,(2),存储结构,/,物理结构,数据结构在计算机中的表示（映象）称为存储结构,/,物理结构。,1.1.1,基本概念和术语,5,(3),数据元素之间的关系（逻辑结构）在计算机中有两种表示方法：顺序映象,(,表示,),和非顺序映象,(,表示,),，从而导致两种不同的存储结构：顺序结构和链式结构。,顺序映象（表示）的特点是借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。,非顺序映象（表示）的特点是借助指示数据元素存储地址的指针来表示数据元素之间的逻辑关系。,1.1.1,基本概念和术语,返回,6,1.1.2,四种基本的数据结构,1.,集合结构,结构中的数据元素之间除了“属于同一个集合”的关系之外，别无其他关系。关系比较松散，可用其他结构来表示。,结构中的数据元素之间存在一个对一个的关系，即线性关系，每个元素至多有一个直接前导和后继。,2.,线性结构,7,3.,树型结构,结构中的数据元素之间存在一个对多个的关系，即层次关系，即每一层上的元素可能与下层的多个元素相关，而至多与上层的一个元素相关。,结构中的数据元素之间存在多个对多个的关系，即任意关系，任何元素之间都可能有关系。,4.,网状,/,图型结构,返回,8,1.1.3,数据结构的研究对象,数据结构的研究对象,(,研究内容,),1.,数据对象的结构形式,各种数据结构的性质,(,逻辑结构,);,2.,数据对象和”关系”在计算机中的表示,(,物理结构,/,存储结构,);,3.,数据结构上定义的基本操作,(,算法,);,4.,算法的效率,;,5.,数据结构的应用,如数据分类,检索,.,返回,9,数据结构的作用图,数据,结构,数据关系,数,据,表,示,数,据,类,型,数学,离散数学 应用数学,硬件,存储设备,总体结构,软件,系统软件,应用软件,算法,设计,数据,运算,编码,理论,数据,组合,系统设计,数据存取,10,2.1,算法及其性能评价准则,算法（,Algorithm,）,：,是对特定问题求解步骤的一种描述，它是指令（规则）的有限序列，其中每一条指令表示一个或多个操作。,算法的特征,：,有穷性、,确定性、,能行性、,输入、,输出,算法描述：,自然语言；,程序设计语言；,类语言,*,；,一、算法、算法的特征和算法描述,常用的算法设计方法,：,递归法（,Recursion,）、分治法,(Divide-and Conquer),、,贪心法,(Greedy),、,动态规划,(Dynamic Programming),、,搜索与遍历、,回溯（,Backtracking,）、,解空间局部搜索,近似算法,(Approximation),、,在线算法（,On-Line,）等,11,2.2,算法时间复杂性分析方法,定理,2.1,若,A,（,n,）,=a,m,n,m,+a,1,n+a,0,是关于,n,的,m,次多项式，则,A,（,n,）,=,（,n,m,）,*此定理说明，时间复杂性仅取决于多项式的最高次幂，而与最高次幂的系数和其他低次项无关,（,1,）表示实践复杂性为常数,常见的时间复杂性及其比较,（,1,）,（,n,）,（,n,）,（,n,）,（,nn,）,（,n,2,）,（,n,3,）,=(y+1)(y+1),y=y+1;,时间复杂性为,O,（,s=0;,f(n)=1;T2(n)=O(f(n)=O(1),常量阶,）,13,for(i=1;i=n;+i),for(j=1;j=n;+j)+x;s+=x;,f(n)=3n,2,+2n+1;T3(n)=O(f(n)=O(n,2,),平方阶,for(i=1;i=n;+i),for(j=1;j=n;+j),cij=0;,for(k=1;k=n;+k),cij+=aik*bkj;,f(n)=2n,3,+3n,2,+2n+1;T4(n)=O(f(n)=O(n,3,),立方阶,for(i=1;i=n;+i)+x;s+=x;,f(n)=3n+1;T1(n)=O(f(n)=O(n),线形阶,14,第三章 线性表（,Liner List,）,15,知识点：,线性表的逻辑结构和各种存储表示方法,定义在逻辑结构上的各种基本运算（操作）,在各种存储结构上如何实现这些基本运算,各种基本运算的时间复杂性,重点：,熟练掌握顺序表和单链表上实现的各种算法及相关的时间复杂性分析,难点：,使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题,16,3.1,抽象数据型线性表,定义,线性表是由,n(n0),个相同类型的元素组成的有序集合。,记为：,(a,1,a,2,a,3,a,i-1,a,i,a,i+1,a,n,),其中：,n,为线性表中元素个数，称为线性表的长度；,当,n=0,时，为空表，记为（）。,a,i,为线性表中的元素，类型定义为,elementtype,a,1,为表中第,1,个元素，无前驱元素；,a,n,为表中最后一个,元素，无后继元素；对于,a,i-1,a,i,a,i+1,(1in),，称,a,i-1,为,a,i,的直接前驱，,a,i+1,为,a,i,的直接后继。,(,位置概念！）,线性表是有限的，也是有序的。,17,3.1,抽象数据型线性表,线性表,LIST=(D,R),D=a,i,|a,i,Elementset,i=1,2,n,n 0,R=H,H=|a,i-1,a,i,D,i=2,n,操作：设,L,的型为,LIST,线性表实例，,x,的型为,elementtype,的元素,实例，,p,为位置变量。所有操作描述为：,Insert(x,p,L),Locate(x,L),Retrieve(p,L),Delete(p,L),Previous(p,L),Next(p,L),MakeNull(L),First(L),End(L),数学模型,18,3.1,抽象数据型线性表,举例：设计函数,Deleval,（,LIST&L,elementtype d),，其功能,为删除,L,中所有值为,d,的元素。,void Deleval(LIST&L,elementtype d),position p;,p=First(L);,while(p !=Ennd(L),if(same(Retrieve(p,L),d),Delete(p,L);,else,p=Next(p,L);,19,3.2,线性表的实现,问题：确定数据结构（存储结构）实现型,LIST,，并在此基础上,实现各个基本操作。,存储结构的三种方式：,连续的存储空间（数组）静态存储,非连续存储空间,指针（链表）动态存储,游标（连续存储空间,+,动态管理思想）静态链表,3.2.1,指针和游标,指针：地址量，其值为另一存储空间的地址；,游标：整型指示量，其值为数组的下标，用以表示指定元素,的“地址”或“位置”（所在的数组下标）,20,3.2.2,线性表的数组实现,第,1,个元素,第,2,个元素,最后,1,个元素,0,1,2,maxlength-1,last,表,空单元,图,3-1,线性表的数组实现,存储池容量,第,i,个元素,1,i,last,顺序表：,把线性表的元素逻辑顺序依次存放在数组的连续单元内，再用一个整型量表示最后一个元素所在单元的下标。,特点：,元素之间的逻辑关系（相继,/,相邻关系）用物理上的相邻关系来表示（用物理上的连续性刻画逻辑上的相继性）；,是一种随机存储结构，也就是可以随机存取表中的任意元素，其存储位置可由一个简单直观的公式来表示。,21,3.2.2,线性表的数组实现,第,1,个元素,第,2,个元素,最后,1,个元素,0,1,2,maxlength-1,last,表,空单元,图,3-1,线性表的数组实现,存储池容量,第,i,个元素,1,i,last,类型定义：,#define maxlength 100,struct LIST ,elementtype elements,maxlength;,int last;,;,位置类型,：,typedef int position;,线性表,L:,LIST L;,表示,：,L.elementsp /L,的第,p,个元素,L.last L,的长度，最后元素的位置,22,3.2.2,线性表的数组实现,操作,：,void Insert(elementtype x,position p,LIST&L),position q;,if(L.last=maxlength 1),error(“,表满”,),；,else if(p L.last+1)|(p=p;q-),L.elements q+1=L.elements q ;,L.last=L.last+1;,L.elements p =x;,/,时间复杂性：,O,(,n,),第,1,个元素,第,2,个元素,最后,1,个元素,0,1,2,maxlength-1,last,表,空单元,图,3-1,线性表的数组实现,存储池容量,第,i,个元素,1,i,last,23,position Locate(elementtype x,LIST L),position q;,for(q=1;q L.last ),error(“,指定元素不存在”,);,else,return(L.elements p );,/,时间复杂性：,O,(,1,),第,1,个元素,第,2,个元素,最后,1,个元素,0,1,2,maxlength-1,last,表,空单元,图,3-1,线性表的数组实现,存储池容量,第,i,个元素,1,i,last,24,void Delete(position p,LIST&L),position q;,if (p L.last)|(p 1),error(“,指定位置不存在”,),；,else,L.last=L.last 1;,for(q=p;q=L.last;q+),L.elements q =L.elements q+1;,/,时间复杂性：,O,(,n,),3.2.2,线性表的数组实现,position Previous(position p,LIST L),if (p L.last),error(“,前驱元素不存在”,);,else,return(p 1);,/,时间复杂性：,O,(,1,),第,1,个元素,第,2,个元素,最后,1,个元素,0,1,2,maxlength-1,last,表,空单元,图,3-1,线性表的数组实现,存储池容量,第,i,个元素,1,i,last,25,position End(LIST L),return(L.last+1);/,O,(,1,),position First(LIST L),return(1);/,复杂性：,O,(,1,),position Next(position p,LIST L),if (p=L.last),error(“,前驱元素不存在”,);,else,return(p+1);,/,时间复杂性：,O,(,1,),position MakeNull(LIST&L),L.last=0;,return(L.last+1);,/,时间复杂性：,O,(,1,),3.2.2,线性表的数组实现,第,1,个元素,第,2,个元素,最后,1,个元素,0,1,2,maxlength-1,last,表,空单元,图,3-1,线性表的数组实现,存储池容量,第,i,个元素,1,i,last,26,3.2.3,线性表的指针实现,结点形式,element,next,结点信息,下一结点地址,celltype,LIST header;,position p,q;,a,1,a,2,a,3,a,n,header,q,p,单链表：,一个线性表由若干个结点组成，每个结点均含有两个域：,存放元素的信息域和存放其后继结点的指针域，这样就形成一个,单向链接式存储结构，简称单向链表或单向线性链表。,结构特点,：,逻辑次序和物理次序不一定相同；,元素之间的逻辑关系用指针表示；,需要额外空间存储元素之间的关,系；,非随机存储结构,27,3.2.3,线性表的指针实现,结点形式,element,next,结点信息,下一结点地址,celltype,类型定义：,struct celltype ,elementtype element;,celltype *next;,;/*,结点型*,/,线性表的型,typedef celltype*LIST;,位置型,typedef celltype *position;,LIST header;,position p,q;,a,1,a,2,a,3,a,n,header,q,p,a,2,:(*p).element;,q:(*p).next;,a,2,:pelement;,q:pnext;,记法,:,28,操作讨论,：,3.2.3,线性表的指针实现,插入元素,:,p,a,1,x,header,q,a,i-1,a,i,x,p,q,a,n,x,q,p,(a),表头插入元素,(b),中间插入元素,(c),表尾插入元素,q=new celltype;,qelement=x;,qnext=pnext;,pnext=q;,或,:,temp=pnext;,pnext=new celltype;,pnextelement=x;,pnextnext=temp;,讨论表头结点的作用,29,操作讨论,：,3.2.3,线性表的指针实现,删除元素,:,q=pnext;,pnext=qnext;,delete q;,或：,q=pnext;,pnext=pnextnext;,delete q;,讨论结点,a,i,的位置,p,a,1,header,(a),删除第一个元素,a,2,q,p,a,i-1,a,i,p,q,(b),删除中间元素,a,i+1,a,n,a,n-1,q,p,(c),删除表尾元素,30,操作,：,3.2.3,线性表的指针实现,position End(LIST L),position q;,q=L;,while(qnext!=NULL)q=qnext;,return(q);,/,时间复杂性：,O,(n),void Insert(elementtype x,position p),position q;,q=new celltype;,q element=x;,q next=p next;,p next=q;,/,时间复杂性：,O,(1),L,q,a,1,a,2,a,3,a,n,31,操作,：,3.2.3,线性表的指针实现,position Locate(elementtype x,LIST L),position p;,p=L;,while(pnext!=NULL),if (pnextelement=x),return p;,else,p=pnext;,return p;,/,时间复杂性：,O,(n),elementtype Retrieve(position p),return(p next element);,/,时间复杂性：,O,(1),L,q,a,1,a,2,a,3,a,n,32,操作,：,3.2.3,线性表的指针实现,void Delete(position p),position q;,if (pnext!=NULL),q=p next;,p next=q next;,delete q;,/,时间复杂性：,O,(1),position Previous(position p),position q;,if (p=Lnext),error(“,不存在前驱元素”,),；,else,q=L;,while(qnext!=p)q=qnext;,return q;,/,时间复杂性：,O,(n),L,q,a,1,a,2,a,3,a,n,33,操作,：,3.2.3,线性表的指针实现,position Next(position p),position q;,if (pnext=NULL),error(“,不存在后继元素”,),；,else,q=pnext;,return q;,/,时间复杂性：,O,(1),position MakeNull(LIST&L),L=new celltype;,Lnext=NULL;,return L;,/,时间复杂性：,O,(1),34,操作,：,3.2.3,线性表的指针实现,position First(LIST L),return L;,/,时间复杂性：,O,(1),静态链表 与 动态链表的 比较,比较参数,表的容量,存取操作,时间,空间,链式存储,灵活，易扩充,顺序存取,访问元素费时间,实际长度，节省空间,顺序存储,固定，不易扩充,随机存取,插入删除费时间,估算表长度，浪费空间,举例：遍历线性链表，按照线性表中,元素的顺序，依次访问表中的,每一个元素，每个元素只能被,访问一次。,void Travel(LIST L),position p;,p=Lnext;,while(p!=NULL),cout next-next;,q=p-next;,L-next-next=NULL;,while(p!=null),p-next=L-next;,L-next=p;,p=q;,q=q-next;,方法二,:,线性表由,q,来,表示,p=null;,w=q;,while(w!=null),w=w-next;,q-next=p;,p=q;,q=w;,36,3.2.5,双向链表,dcelltype,结点形式,element,next,结点信息,后继结点指针,previous,前驱结点指针,a,i-1,a,i,a,i+1,p,header,a,n,tail,双向连表：在单向链表中，对每个结点增加一个域，用一指向该结点的前驱结点。线性表的这种存储结构称为,双向链表。,/*,结点类型*,/,struct dcelltype ,elementtype element;,dcelltype *next,*previous;,;,/*,表和位置的类型*,/,typedef dcelltype *DLIST;,typedef dcelltype *position;,优点：,实现双向查找（单链表不易做到）,表中的位置,i,可以用指示含有第,i,个结点的指针表示。,缺点：空间开销大。,37,3.2.5,双向链表,操作,：,删除位置,p,的元素：,void Delete(position p,DLIST&L),if(p-previous!=NULL),ppreviousnext=pnext;,if(pnext!=NULL),pnext previous=pprevious;,delete p;,void Insert(elementtype x,position p,DLIST&L),position q;,q=new dcelltype;,qelement=x;,ppreviousnext=q;,qprevious=pprevious;,qnext=p;,pprevious=q;,a,i-1,a,i,a,i,+,1,p,38,3.2.6,环形链表,单向线性链表,双向线性链表,单向循环链表,双向循环链表,对线性链表的改进，解决“单向操作”的问题；改进后的链表，能够从任意位置元素开始，访问表中的每一个元素。,单向环形链表,：,在,(,不带表头结点,),的单向链表中，使末尾结点的指,针域指向头结点，得到一个环形结构；用指向末尾结点的指针标识,这个表。,存储结构,:,与单向链表相同,(,略）,a,1,a,2,a,3,a,n,R,左端结点,右端结点,R,空表,39,操作,：在表左端插入结点,Insert(x,FIRST(R),R);,LInsert,(x,R),void LInsert(elementtype x,LIST&R),celltype *p;,p=new celltype;,pelement=x;,if(R=NULL),pnext=p;R=p;,else,pnext=Rnext;Rnext=p;,3.2.6,环形链表,在表右端插入结点,Insert(x,END(R),R);,RInsert,(x,R),void RInsert(elementtype x,LIST R),LInsert(x,R);R=Rnext;,a,1,a,2,x,a,n,R,p,x,p,R,40,操作,：从表左端删除结点,Delete(First(R),R);LDelete(R),void LDelete(LIST&R),celltype *p;,if(R=NULL),error(“,空表”,);,else,p=Rnext;,Rnext=pnext;,if(p=R),R=NULL;,delete p;,3.2.6,环形链表,x,p,R,p,a,1,a,2,a,n,R,41,3.2.6,环形链表,双向环形链表：,a,1,a,i,a,n,R,双向环形链表的结构与双向连表结构相同，只是将表头元素,的空,previous,域指向表尾，同时将表尾的空,next,域指向表头结点，,从而形成向前和向后的两个环形链表，对链表的操作变得更加灵,活。,举例：设计算法，将一个单向环形链表反向。头元素变成尾,元素，尾元素变成新的头元素，依次类推。,42,3.2.6,环形链表,a,1,a,2,a,3,a,n,R,a,n,a,n-1,a,n-2,a,1,R,void Reverse(LIST&R),position p,q;,q=R;,p=Rnext;,while(p!=R),s=q;,q=p;,p=pnext;,qnext=s;,算法如下：,存储结构定义略,43,3.3,栈（,Stack,）,栈是线性表的一种特殊形式，是一种限定性数据结构，也就是在对线性表的操作加以限制后，形成的一种新的数据结构。,定义：是限定只在表尾进行,插入和删除操作的线性表。,栈又称为后进先出,(Last In First Out),的线性表。,简称,LIFO,结构。,栈举例,a,1,a,2,a,n-1,a,n,Insert,Delete,top,bottom,栈底,栈顶,栈示意图,44,3.3,栈,栈的基本,MakeNull(S),操作,Top(S),Pop(S),Push(x,S),Empty(S),举例：利用栈实现行编辑处理。,设定符号,“,#,”,为擦讫符，用以删,除,“,#,”,前的字符；符号,“,”,为删,行符，用以删除当前编辑行。,原理：,一般字符进栈；,读字符 擦讫符退栈；,删行符则清栈,算法：,void LineEdit(),STACK,；,char c;,MakeNull(S);,c=getchar();,while(c!=n),if(c=#),Pop(S);,else if(c=),MakeNull(S);,else,Push(c,S);,c=getchar();,逆序输出栈中所有元素；,45,3.3.1,栈的实现,3.3,栈,1,、顺序存储,顺序栈示意图,a,n,a,i,a,3,a,2,a,1,-,maxlength-1,3,2,1,0,top,类型定义：,enum BoolenTRUE,FALSE,typedef struct,elementtype elementsmaxlength;,int top;,STACK;,STACK S;,栈的容量：,maxlength 1;,栈空：,S.top=0;,栈满：,S.top=maxlength 1;,栈顶元素：,S.elements S.top ;,46,3.3.1,栈的实现,1,、顺序存储,操作：,void MakeNull(STACK&S),S.top=0;,Boolean Empty(STACK S),if(S.top next=NULL;,void Push(Elementtype x,STACK&S),STACK stk;,stk=new node;,stk-val=elm;,stk-next=S-next;,S-next=stk;,50,void Pop(STACK&S),STACK stk;,if(S-next),stk=S-next;,S-next=stk-next;,delete stk;,Elementtype Top(STACK S),if(S-next),return(S-next-val);,else,return NULL;,51,boolean Empty(STACK S),if(S-next),return FALSE;,else,return TRUE;,多个栈共用一个存储空间的讨论,STACK maxlength,bot1,top1,bot2,top2,bot3,top3,top2,botn,topn,0,Maxlength-1,botn+1,boti,topi,52,3.4,排队或队列（,Queue,）,队列是对线性表的插入和删除操作加以限定的另一种限,定性数据结构。,定义,将线性表的插入和删除操作分别限制在表的两端进行，,和栈相反，队列是一种先进先出（,First In First Out,，简称,FIFO,结构）的线性表。,a,1,，,a,2,，,a,3,，,，,，,a,n-1,，,a,n,出队列,入队列，,插入，排队,删除，出队,队头,队尾,队列示意图,front,rear,操作：,MakeNull(Q),、,Front(Q),、,EnQueue(x,Q),、,DeQueue(Q),、,Empty(Q),53,3.4,队列（,Queue,）,3.4.1,队列的指针实现,元素的“型”：,struct celltype ,elementtype element,；,celltype *next,；,；,队列的“型”：,struct QUEUE,celltype *front,；,celltype *rear,；,;,a,1,a,2,a,n,Q.front,Q.rear,队列的指针实现示意图,54,3.4.1,队列的指针实现,操作：,void MakeNull(QUEUE&Q),Q.front=new celltype;,Q.frontnext=NULL;,Q.rear=Q.front;,Boolean Empty(Q),QUEUE ,if (Q.front=Q.rear),return TRUE;,else,return FALSE;,elementtype Front(Q),QUEUE Q;,return Q.frontnextelement;,55,3.4.1,队列的指针实现,void EnQueue (elementtype x,QUEUE&Q),Q.rearnext=new celltype;,Q.rear=Q.rearnext;,Q.rearelement=x;,Q.rearnext=NULL;,void Delete (QUEUE&Q ),celltype *temp;,if (Empty(Q),error(“,空队列”,);,else temp=Q.frontnext;,Q.frontnext=tempnext;,delete temp;,if (Q.frontnext=NULL),Q.rear=Q.front;,56,3.4.2,队列的数组实现,队列的“型”：,struct QUEUE,elementtype element maxlength ;,int front,；,int rear,；,;,a,1,a,2,a,3,a,4,a,n,Q,front,rear,maxlength,右图：队列,Q,状态,1,随着不断有元素出队和进队,（插入和删除），队列的状,态由,1,变成,2,；此时,a,n,占据队,列的最后一个位置；第,n+1,个元素无法进队,但实际上，,前面部分位置空闲。,“,假溢出“,maxlength,a,1,a,2,a,3,a,4,a,5,a,6,a,n,Q,front,rear,下图：队列,Q,状态,2,57,3.4.2,队列的数组实现,解决假溢出的方法有多种；一是通过不断移动元素位置，,每当有元素出队列时，后面的元素前移一个位置，使队头元,素始终占据队列的第一个位置。,第二种方法是采用循环队列。,Q.rear,Q.front,0,1,maxlength-1,队列,Q,插入元素：,Q.rear=(Q.rear+1,）,%maxlength,删除元素：,Q.front=(Q.front+1,）,%maxlength,队空：,(Q.rear+1,）,%maxlength=Q.front,队满：,(Q.rear+1)%maxlength=Q.front,?,58,3.4.2,队列的数组实现,问题：如何解决循环队列中队空与队满状态相同？,方法一：约定队列头指针在队列尾指针的下一位置上；,方法二：另设一个标志位用以区别队空与队满两种状态；,结论：两种方法的代价是相同的。,操作：,int addone(int i),return(i+1,）,%maxlength);,void MakeNull(QUEUE&Q),Q.front=0;,Q.rear=maxlength 1;,boolean Empty(Q),QUEUE Q;,if(addone(Q.rear)=,Q.front ),return TRUE;,else,return FALSE;,59,3.4.2,队列的数组实现,操作：,elementtype Front(QUEUE Q),if (Empty(Q),return NULL;,else,return (Q.elements Q.front );,void EnQueue(elementtype x,QUEUE Q),if(addone(addone(Q.rear)=Q.front),error (“,队列满”,);,else ,Q.rear=addone(Q.rear);,Q.elements Q.rear =x;,60,3.4.2,队列的数组实现,void DeQueue(QUEUE Q );,if(Empty(Q),error (“,空队列”,);,else,Q.front=addone(Q.front);,;,61,3.6,串,(String),串是线性表的一种特殊形式，表中每个元素的类型为字符型，是一个有限的字符序列。,串的基本形式可表示成：,S=,a,1,a,2,a,3,a,n,；,其中：,char a,i,；,0 i n,；,n 0,；当,n=0,时，为空串。,n,为串的长度；,C,语言中串有两种实现方法：,1,、字符数组，如：,char str110,；,2,、字符指针，如：,char *str2,；,3.6.1,抽象数据型串,62,3.6.2,串的实现,1,、串的顺序存储,采用连续的存储空间（数组），自第一个元素开始，依次,存储字符串中的每一个字符。,char str 10 =,“,China,”,；,C,h,i,n,a,0,0 1 2 3 4 5 6 7 8 9,str,串的顺序存储,操作：,NULL,，,ISNULL,，,IN,，,LEN,，,CONCAT,，,SUBSTR,，,INDEX,2,、串的链式存储,构造线性链表，,element,类型为,char,，自第一个元素开始，依,次存储字符串中的每一个字符。,63,3.7,数组,(ARRAY),3.7.1,抽象数据型数组,数组是由下标（,index,）和值（,value,）组成的序对,（,index,，,value,）的集合。,也可以定义为是由相同类型的数据元素组成有限序列。,数组在内存中是采用一组连续的地址空间存储的，正是,由于此种原因，才可以实现下标运算。,所有数组都是一个一维向量。,数组,1,：,(,a,1,a,2,a,3,a,i,a,n,);,数组,2,：,(,a,11,a,1n,a,21,a,2n,a,ij,a,m1,a,mn,);,1,i,m,1,j,n;,数组,3,:,(,a,111,a,11n,a,121,a,12n,a,ijk,a,mn1,a,mnp,);,1,i,m,1,j,n,1,k,p;,64,3.7.2,数组的实现,1,、数组的顺序存储,数组的顺序表示，指的是在计算机中，用一组连续的存,储单元来实现数组的存储。目前的高级程序设计语言都是这,样实现的。,两种存储方式：,一是按行存储（,C,语言、,PASCAL,等）,二是按列存储（,FORTRAN,等）,A00 A01 A02,A10 A11 A12,A=,A00,A01,A02,A10,A11,A12,A00,A10,A01,A11,A02,A12,第一行,第二行,第一列,第二列,第三列,elementtype A23,；,65,1,、数组的顺序存储,对二维数组有：,LOC,（,Aij,）,=LOC,（,A00,）,+n i+j,，,0 i m-1,，,0 j n-1,对三维数组有：,LOC,（,Ai,1,i,2,i,3,）,=LOC,（,A000,）,+d,2,d,3,i,1,+d,3,i,2,+i,3,，,0 i,1,d,1,-1,，,0 i,2,d,2,-1,，,0 i,3,d,3,-1,66,2,、数组的压缩存储,特殊矩阵,若,n,阶矩阵,A,中的元素满足下述性质,a,ij,=a,ji,1 i,j n,则称,n,阶对称阵。,对于对称矩阵,为实现节约存储空间,我们可以为每一对对称,元素分配一个存储空间,这样,原来需要的,n,2,个元素压缩存,储到,n(n+1)/2,个元素空间。,对称关系：,设,sa 0.n(n+1)/2,做为,n,阶对称阵,A,的存储结构,则,Sa k,和,a,ij,的一一对应关系为,:,i(i+1)/2+j,当,i j,k=,j(j+1)/2+i,当,i j,67,（,2,）稀疏矩阵,稀疏矩阵中，零元素的个数远远多于非零元素的个数。为,实现压缩存储，仍考虑只存储非零元素。,0 12 9 0 0 0 0,0 0 0 0 0 0 0,-3 0 0 0 0 14 0,0 0 24 0 0 0 0,0 18 0 0 0 0 0,15 0 0 -7 0 0 0,M=,i j v,1 2 12,1 3 9,1 -3,6 14,3 24,5 2 18,1 15,6 4 -7,68,定义及相关术语,逻辑结构及其特征,基本操作（算法）,存储结构（描 述）,存储结构特点,操作（算法）实现,存储结构的定义,算法的性能分析,定义,实现,ADT,应用,第,4,章 树,69,先根顺序,中根顺序,后根顺序,层序遍历,双亲表示法,(,数组,),孩子表示法,(,邻接表,),左右链表示,(,二元树,),树的,ADT,逻辑结构,存储结构,树的存储结构,递归,非递归,树的应用,集合表示,哈夫曼树,表达式求值,二元树,逻辑结构,存储结构,基本性质,遍历二元树,线索二元树,顺序存储,二叉链表,优化判定过程