《数据结构软》PPT课件.ppt

《《数据结构软》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数据结构软》PPT课件.ppt（375页珍藏版）》请在三一办公上搜索。

1、1,数 据 结 构,（C语言版）,作者：黎剑兵,2,第 一 章 绪 论,学习内容 常用术语 算法评价 时间复杂度与空间复杂度的分析 重点了解逻辑结构 物理结构和数据的运算三方面相关概念及相互关系难点 时间复杂度的分析方法掌握 用类C语言的表示方法会用类C编写程序,3,第 一 章 绪 论,计算机科技 是 一门研究用计算机进行信息表示和处理的科学。主要涉及两方面的问题：信息的表示和信息的处理 信息的表示和组织直接关系到处理信息的程序 的效率，随着计算机的应用领域的扩大。信息量的增加，信息范围的拓宽，使系统程序和应用程序的规模的日趋增大，结构也日趋增大。因此，为了编写出一个“好”的程序，必须分析 处

2、理的对象的特征及个对象之间的存在的关系。这就是本课程所要研究的问题。,4,第 一 章 绪 论,计算机程序 是 对信息进行加工处理。这些信息之间大多数情况下往往具有重要的结构关系。这就是数据结构的内容。那么，什么是数据结构呢？,5,1.地位,第 一 章 绪 论,6,1.地位,第 一 章 绪 论,数据结构Data Structure,7,数据模型,问题,实现,2.主要内容,第 一 章 绪 论,8,数据模型,问题,实现,2.主要内容,第 一 章 绪 论,(1)要对所加工的对象进行逻辑组织(2)如何把加工对象存储到计算机中去？(3)数据运算,9,3.学科定义,什么是数据结构,数据结构 是一门研究非数值

3、 计算的程序设 计问题中计算机的 操作对象以及它们之间的关系和 操作等等的科。,10,基本概念和术语,数据元素(data element)数据基本单位，也称节或孩子，可由若干个数据项组成。数据项是数据最小单位数据(data)是对客观事物的 表示，指所有能输入到计算机并被计算机程序处理的符号的总称。数据对象(data object)性质相同的数据元素的集合数据结构 数据元素之间的相互关系,11,1)集合,基本概念和术语,数据间的四种典型结构：,2）线形,3）树形,4）图或网络：,12,基本概念和术语,四种典型结构：,1)集合,13,四种典型结构,基本概念和术语,2）线形：,14,四种典型结构：,

4、基本概念和术语,3）树形：,15,四种典型结构：,基本概念和术语,4）图或网络：,16,基本概念和术语,（5）逻辑结构：从具体问题抽象出的数学模型。体现逻辑关系。,（6）物理结构(存储结构)：DE及关于在计算机中的表示。DE存储称为节点关系存储：a.顺序存储 b.链式存储,17,基本概念和术语,（7）DS广义定义：DE 的逻 辑 结 构 DE 的物 理 结 构DE 的 抽 象 运 算（8）基本操作加工型：查找 删除 更新 排序 引用型：查找,18,基本概念和术语,19,算法和算法分析,一、算法定义,算法是对特定问题求解步骤的一种描述，是指令的有限序列。特性：有穷性 确定性 可行性 输入 输出,

5、20,算法和算法分析,二、算法的描述与分析描述：类C语言要求正确性：a.语法 b.n个输入 c.一组典型的苛刻的输入 d.所有输入可读性健壮性效率与存贮量,21,算法和算法分析,分析标准 a、时间复杂度：算法中基本操作重复执行的次数(频度)。T(o)=O(f(n)时间复杂度分为平均时间复杂度和最坏时间复杂度复杂度的值取规模函数最高阶,22,分析标准 a、时间复杂度：算法中基本操作重复执行的次数。T(o)=O(f(n)时间复杂度分为平均时间复杂度和最坏时间复杂度复杂度的值取规模函数最高阶,算法和算法分析,b、空间复杂度：算法所需存贮空间S(n)=O(f(n),23,算法和算法分析,例：分析下列语

6、句段的时间复杂度m=0;1for(k=0;kn;k+)n+1for(j=0;jk;j+)n(n+1)/2m+=2;O(n2),24,习题与练习 一,1.简要回答下列问题：a.数据与数据元素有何区别？b.逻辑结构与存储结构是什么？它们是什么关系？c.什么是算法？它有什么特点？,25,习题与练习 一,2.试写一个算法，统计输入的100个整数中奇数和偶数的个数。3.设计下面问题算法，并分析最坏情况时间复杂性:在数组 A1.n中查找值为 K的元素，若找到输出其位置 i(0 i n+1),否则输出0。,26,习题与练习 一,4.设 n 为正整数，写出下列程序段的时间复杂度：（1）for(I=1;In;I

7、+)m=m+I;for(j=0;jn;j+)count+=m+j;,27,习题与练习 一,（2）for(I=0;In;I+)m=m+I;for(j=0;j10;)count+=m+j;j+;,28,习题与练习 一,（3）k=1;s=0;while(s=n-1)k=k+s*6;s+;printf(“%d,%d”,s,k);,29,第 二 章 线 性 表,学习内容 线性表定义 线性表的抽象数据结构 线性表的顺序存储和操作实现 线性表的链接存储 线性表在链表上的操作实现 线性表在双向链表操作实现,30,第二章 线性表,线性结构特点：,在数据元素的非空有限集合中 1）“第一个”唯一 2）“最后一个”唯

8、一 3）除第一个外，每一个有且仅有一个直接前驱 4）除最后一个外，每一个均有且仅有一个直接后继,31,一、线性表的定义,第二章 线性表,表头元素,表尾元素,2.1 线性表的类型定义,32,2.1 线性表的类型定义,一、线性表的定义,一个线性表可以用一个标识符来命名：A=(a1,a2,ai,ai+1,an)ai可以是基本数据类型也可以是struct 类型,33,2.1 线性表的类型定义,二、线性结构特点,在数据元素的非空有限集中元素个数n表长度，n=0空表存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中的每个数据元素均只有一个前趋除最后一个外，

9、集合中的每个数据元素均只有一个后继元素同构，且不能出现缺项,34,2.1 线性表的类型定义,线性表几个具体例子,L1=（a,b,c,4,7,+,-,*,/）L2=（25,35,28,49,51,87,46,32,88）L3=（“BASIC”,“PASCAL”,“JAVA”,“OK”）L4=（a,b,c,d,e,f,g,h,i,j,k,x,y,z）,35,2.1 线性表的类型定义,基本运算,(1)初始化 initList(sq)。其作用是建立一个空表sq(即建立线性表的构架，但不含任何数据元素)。(2)求表长 ListLen(sq)。其作用是返回线性表sq的长度。(3)读表元素 GetElem(

10、sq，i)。若1iListLen(sq)，则其作用是返回线性表sq的第i个数据元素;否则，返回NULL。,36,2.1 线性表的类型定义,基本运算,(4)定位(按值查找)LocateElem(sq，x)。若sq中存在一个或多个值与x相等的元素，则其作用是返回这些元素的序号的最小值；否则，返回0。,37,基本运算,(5)插入ListInsert(sq，x，i)。其作用是在线性表sq的第i个位置上增加一个以x为值的新元素，使sq由(a1，ai-1，ai，an)变为(a1，ai-1，x，ai，an)。参数i的合法取值范围是：1in+1,2.1 线性表的类型定义,38,2.1 线性表的类型定义,基本运

11、算,(6)删除ListDelete(sq，i)。其作用是删除线性表sq的第i个元素ai,使sq由(a1，ai-1，ai，ai+l，an)变为(a1，ai-1，ai+1，an)。参数i的合法取值范围是：1in。,39,2.1 线性表的类型定义,基本运算,(7)求前趋 PriorElem(sq,e)若线性表中存在元素e且不是第一个,其作用是返回e的前趋元素;否则，返回NULL。(8)求后继 NextElem(sq,e)若线性表中存在元素e且不是最后一个,其作用是返回e的后继元素;否则，返回NULL,40,2.1 线性表的类型定义,基本运算,应用基本运算可以实现线性表的其他运算，如求任一给定数据元素

12、的直接后继或直接前趋，将两个线性表合并成一个线性表或将一个线性表拆分成两个线性表等等。另一方面，在实际应用中，可以根据具体需要选择适当的基本运算,41,2.1 线性表的类型定义,解本题的算法思路是：依次检查线性表B中的每个元素，看它是否在线性表A中。若在表A中，则将其从A中删除。,基本运算,例2.1 利用线性表的基本运算，编写在线性表A中删除线性表B中出现的元素的算法。,42,2.1 线性表的类型定义,void delete(sqlist/若在线性表A/中找到则将其删除,43,2.1 线性表的类型定义,解 先始化线性表C，然后依次检查线性表A中的每个元素，看它是否在线性表B中；若在线性表B中，

13、则将其插入到线性表C中.,基本运算,例2.2 利用线性表的基本运算，编写将线性表A和B中公共元素生成线性表C的算法,44,2.1 线性表的类型定义,void celem(sqlist A，sqlist B，sqlist/若在线性表B中/找到，将其插入C,45,2.2 线性表的顺序存储和实现,一、线性表的顺序存储（顺序表）定义：把线性表中所有元素按其逻辑顺序依次存储到指定位置开始的连续空间中。即用一组地址连续的存储单元存放一个线性表特点：实现逻辑上相邻物理地址相邻实现随机存取实现：（一维）数组,46,2.2 线性表的顺序存储和实现,ElemType类型的数组listMaxSize存储线性表A=(

14、a1,a2,ai,ai+1,an)元素地址计算方法第i个元素的存储位置为：list+(i-1)*sizeof(ElemType),线性表的顺序存储结构示意图,47,2.2 线性表的顺序存储和实现,元素地址计算方法：lLOC(ai)=LOC(a1)+(i-1)*L lLOC(ai+1)=LOC(ai)+L其中：uL一个元素占用的存储单元个数 uLOC(ai)线性表第i个元素的地址,48,a2,2.2 线性表的顺序存储和实现,49,2.2 线性表的顺序存储和实现,线性表的顺序存储示例（图书资料）,typedef struct card int num;char name20;char author

15、10;char publisher30;float price;DATATYPE;,50,可以定义为静态数组或变量DATATYPE libraryM;或动态申请和释放内存DATATYPE*pData；pDat=(DATATYPE*)malloc(sizeof(DATATYPE);free(pData)；,2.2 线性表的顺序存储和实现,线性表的顺序存储示例（图书资料）,51,2.2 线性表的顺序存储和实现,插入一个元素定义：线性表的插入是指在第i 个元素之前插入一个新的数据元素x，使长度为n的线性表(a1,a2,ai-1,ai,an)变成长度为n+1的线性表(a1,a2,ai-1,x,ai,a

16、n),52,2.2 线性表的顺序存储和实现,插入一个元素算法,int sxbcr(int i,int x,int v,int*p)int j,n;n=*p;if(in+1)return(0);else for(j=n;j=i;j-)vj=vj-1;vj=x;*p=+n;return(1);,53,2.2 线性表的顺序存储和实现,插入一个元素图示1,54,2.2 线性表的顺序存储和实现,插入一个元素图示2,x,55,2.2 线性表的顺序存储和实现,插入算法时间复杂度T(n)Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：,56,2.

17、2 线性表的顺序存储和实现,向线性表中表头插入一个元素,InsertFront(List,57,2.2 线性表的顺序存储和实现,向线性表中满足条件的位置插入一个元素,void Insert(List,58,2.2 线性表的顺序存储和实现,向线性表中的末尾添加一个元素,void InsertRear(List,59,变成长度为n-1的线性表,需将第i+1至第n共（n-i）个元素前移,2.2 线性表的顺序存储和实现,删 除 一 个 元 素 定义：线性表的删除是指将第i（1i n）个元素删除，使长度为n的线性表,60,2.2 线性表的顺序存储和实现,删 除 一 个 元 素算法,int sxbsc(i

18、nt i,int v,int*p)int j,n;n=*p;if(in)return(0);for(j=i;jn;j+)vj-1=vj;*p=-n;return(1);,61,2.2 线性表的顺序存储和实现,删 除 一 个 元 素图示1,62,2.2 线性表的顺序存储和实现,删 除 一 个 元 素图示2,63,故在顺序表中插入或删除一个元平均移动表的一半元素，当n很大时，效率很低,2.2 线性表的顺序存储和实现,删除算法评价,设 Qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为：,64,2.2 线性表的顺序存储和实现,从线性表中删除等于给定值的元素1

19、,int Delete(List,65,2.2 线性表的顺序存储和实现,从线性表中删除等于给定值的元素2,if(i=L.size)printf(“Deleted element is not exist!”);return 0;for(int j=i+1;jL.size;j+)L.listj-1=L.list;L.size-;return 1;,66,例 已知线性表(ao，a1，an-1)按顺序存储，且每个元素都是均不相等的 整数。设计把所有奇数移到所有的偶数前边的算法(要求时间最少，辅助空间最少)。,2.2 线性表的顺序存储和实现,解 从左向右找到偶数A.datai，从右向左找到奇数A.da

20、taj，将两 者交换；循环这个过程直到i大于j为止,67,2.2 线性表的顺序存储和实现,void move(sqlist A)int i=0,j=A.len-l,k;ElemType temp;while(i=j)while(A.datai%2=0)i+;while(A.dataj%2=l)j-;if(ij)temp=A.datai;A.datai=A.dataj;A.dataj=temp;,68,2.2 线性表的顺序存储和实现,顺序存储结构的优缺,缺点:插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配，利用不充分优点:逻辑相邻，物理相邻可随机存取任一元素存储空间使用紧凑表容量难

21、以扩充,69,2.3 线性表的链式存储结构,单链表(线性链表)特点:用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素 每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息,70,单链表(线性链表)特点:用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素 每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息,2.3 线性表的链式存储结构,结点数据域：元素本身信息指针域：指示直接后继的存储位置,71,头指针,2.3 线性表的链式存储结构,定义：结点中只含一个指针域的链表，也叫单链表 例 线性表(Z

22、HAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG),72,2.3 线性表的链式存储结构,73,实现typedef struct node datatype data;struct node*next;LNode,*LinkList;LNode*h,*p,2.3 线性表的链式存储结构,2.3 线性表的链式存储结构,74,(*p)表示p所指向的结点(*p).data/p-data表示p指向结点的数据域(*p).next/p-next表示p指向结点的指针域生成一个LNode型新结点：p=(LNode*)malloc(sizeof(LNode);系统回收p结点：free(p),2.

23、3 线性表的链式存储结构,75,2.3 线性表的链式存储结构,头结点：在单链表第一个结点前附设的一个结点。头结点指针域为空表示线性表为空,76,2.3 线性表的链式存储结构,在带头节点的单链表中查找第 i 个结点,Status ListSearch_L(LinkList L,int i,ElemType*e)P=L-next;j=1;While(!p return OK；,77,2.3 线性表的链式存储结构,在带头节点的单链表中第 i 个结点处插入新元素 x,78,2.3 线性表的链式存储结构,Status ListInsert_L(LinkList L,ElemType x,const in

24、t i)p=L;j=0;while(p,79,2.3 线性表的链式存储结构,删除元素：,80,2.3 线性表的链式存储结构,Status ListDelete_L(LinkList L,int I,ElemType*e)P=L;j=0;While(p-next/ListDelete_L,删除元素：,81,2.3 线性表的链式存储结构,两个有序单链表合并为一个有序单链表(非递减),MergeList_L(Linklist La,LinkList Lb,LinkList Lc)pa=La-next;pb=Lb-next;Lc=pc=La;While(pa,82,它是一种动态结构，整个存储空间为多个

25、链表共用不需预先分配空间指针占用额外存储空间不能随机存取，查找速度慢,2.3 线性表的链式存储结构,单链表具有单向性的缺点,单链表特点,83,2.3 线性表的链式存储结构,循环链表:表中最后一个结点的指针指向头表p或p-next=H结点，使链表构成环状特点：从表中任一结点出发均可找到表中其他结点，提高查找效率,84,2.3 线性表的链式存储结构,循环链表操作与单链表基本一致,循环条件不同单链表:p或p-next=NULL循环链:p或p-next=H,85,2.3 线性表的链式存储结构,双向链表（double linked list),指向前驱结点,数据,指向后继结点,结点定义typedef s

26、truct node datatype data;struct node*prior,*next;DLNode,*DLinkLIst,86,空双向循环链表：,非空双向循环链表：,L,2.3 线性表的链式存储结构,双向链表图例,87,p-prior-next=p=p-next-proir;,2.3 线性表的链式存储结构,双向链表图例,88,2.3 线性表的链式存储结构,在给定结点p前插入一个新结点,89,在给定结点p前插入一个新结点,S=(DLinklist)malloc(sizeof(DLNode);s-data=x;s-prior=p-prior;s-next=p;p-prior-next=

27、s;p-prior=s;,2.3 线性表的链式存储结构,90,p-prior-next=p-next;,p-next-prior=p-prior;,2.3 线性表的链式存储结构,删除给定结点p,91,p-prior-next=p-next;,p-next-prior=p-prior;,删除给定结点p动画演示,2.3 线性表的链式存储结构,92,p-prior-next=p-next;p-next-prior=p-prior;free(p);,删除给定结点 p 算法,就这么简单！,2.3 线性表的链式存储结构,93,3 存储结构的选用,顺序与链式存储结构的选用应考虑因素：（1）存储空间（2）运算

28、时间（3）程序设计语言,94,习题与练习 二,1.描述以下三个概念的区别：头结点、头指针和开始结点2.从尾指针出发能访问到链表上所有结点的链表有。3.假设有两个按元素值递增的线性表 A、B，编写算法将两表合并为一个按元素值递减的线性表C。（分别以顺序、链式实现）,95,习题与练习 二,4.设线性表存放在向量 AMAXSIZE的前elenum个分量中，且递增有序。试写一算法，将 x 插入线性表适当位置上，以保持线性表的有序性，并且分析算法的时间复杂性。5.以链式存储结构实现上题。,96,习题与练习 二,6.在双向链表上实现线性表的下列基本运算：(1)初始化(2)定位(3)插入(4)删除,97,【

29、学习内容】栈的抽象数据类型、顺序表示、链表表示及相应操作(特别注意栈空和栈满的条件）队列的定义、特性 队列的抽象数据类型、顺序表示、链表表示及相应操作（特别是循环队列中队头与队尾指针的变化情况）栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS。,第三章 栈与队列,98,第 三 章 栈 与 队列,3.1 栈（stack）,3.1.1 定义通常称插入、删除的这一端（如表尾）为栈顶(Top)，另一端（表头）为栈底(Bottom)。当表中没有元素时称为空栈 特点：先进后出（FILO）或后进先出（LIFO）,99,例：假设栈S=(a1，a2，a3，an)则a1称为栈底元素，an为栈顶元素。进

30、栈 top+1;新元素插入elementstop位置出栈 top-1;栈中元素按a1，a2，a3，an的次序进栈，退栈按后进先出的原则进行的,因此按an a3 a2 a1的次序出栈,3.1 栈（stack）,100,3.1 栈（stack）,栈的主要操作：,（1）建立一个空栈 IniStack(&s)（2）判断一个栈是否为空StackEmpty(&s)（3）进栈 Push(&s,x)（4）出栈 Pop(&s,&e)（5）获得栈顶元素值 GetTop(s,&e),101,进栈：top+1;新元素插入elementstop位置出栈：top-1,栈s=(a1,a2,an),3.1 栈（stack）,

31、栈的图示,102,3.1 栈（stack）,栈和线性表类似，也有两种（顺序、链式）实现方法,103,存储结构定义#define MAXSIZE 6typedef struct datatype elementsMAXSIZE;int top;SqStack;,3.1 栈（stack）,一、栈的顺序存储,104,3.1 栈（stack）,栈的顺序存储,栈顶指针top 指示栈顶元素在顺序栈中的top=-1,栈空，此时出栈，则下溢（underflow）top=MAXSIZE-1,栈满，此时入栈，则上溢（overflow）,105,3.1 栈（stack）,顺序栈进、出栈图示,栈顶指针top,指向实际

32、栈顶后的空位置，初值为-1,进栈,A,出栈,栈满,B,C,D,E,F,设数组维数为Mtop=-1,栈空，此时出栈，则下溢（underflow)top=M-1,栈满，此时入栈，则上溢（overflow),栈空,106,Status Push(SqStack*S,datatype e)If(S-top=MAXSIZE-1)/*上溢*/return ERROR;S-top+;S-elementsS-top=e;return OK;,3.1 栈（stack）,进栈算法,107,3.1 栈（stack）,出栈算法,Status Pops(SqStack*S,datatype*e)If(S-top=-1)

33、/*下溢*/return ERROR;S-top-;*e=S-elementsS-top+1;return OK;,108,二、链栈（单链表）,3.1 栈（stack）,typedef struct node int data;struct node*link;LinkList;,结点定义,109,3.1 栈（stack）,链栈的特点,链表的存储结构与链接存储的栈完全相同，只是链头指针就是栈顶指针。初始时为NULL 链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作,110,3.1 栈（stack）,链栈的进栈算法,进栈等同于不带头结点单链表的头插法Statu

34、s Push(LinkList*S,datatype e)p=(LinkList)malloc(sizeof(Linklist);p-data=e;p-next=S-top;S-top=p;return OK;,111,3.1 栈（stack）,链栈的出栈算法,出栈等同于删除第一个结点Status Pop(LinkList*S,datatype*e)If(S-top)return ERROR;/*下溢*/p=S-top;S-top=p-next;*e=p-data;free(p);return OK;,112,3.1 栈（stack）,3.1.3 栈的应用,(1)“回溯”问题求解(2)过程的嵌

35、套和递归调用,113,1嵌套调用,3.1 栈（stack）,3.1.3 栈的应用,114,s,3.1 栈（stack）,嵌套调用过程图示,115,递归：函数直接或间接的调用自身的过程 一个对象部分地包含它自己，或是用它自己给自己定义 一个过程直接地或间接地调用自己 利用前面运算来求得答案的过程实现：建立递归工作栈优点：递归函数结构清晰，程序易读，正确性易证明缺点：速度慢，空间大效率低,3.1 栈（stack）,2递归调用,116,3.1 栈（stack）,void p(参数表)if（递归结束条件）可直接求解步骤；-基本项 else p（较小的参数）；-归纳项,递归算法的一般形式,117,3.1

36、 栈（stack）,例：求n!=,1，n=0n*(n-1)！n0,int Factorial(int n)if(n=0)return 1;return n*Factorial(n-1);,118,例：递归的执行情况分析,3.1 栈（stack）,119,void print(Int w)int i;if(w!=0)print(w-1);for(i=1;i=w;+i)printf(“%3d,”,w);printf(“/n”);,3.1 栈（stack）,运行结果：1，2，2，3，3，3，,例 递归的执行情况分析,120,3.1 栈（stack）,上例图示分析,121,3、括号的匹配检验,3.1

37、栈（stack）,假设表达式中有多种扩号，可以用栈来进行扩号匹配检验，具体做法为：非括号字符跳过不理；碰上左扩号，入栈；碰上右扩号，出栈，并且检查出栈元素是否与当前右扩号相匹配，若匹配继续检查，否则匹配失败。,请同学们下去自己编程序试试。,122,3.2 队列（QUEUE）,一、队列定义 队列是限定只能在表的一端进插入，在表的另一端进行删除的线性表队尾(rear)允许插入的一端队头(front)允许删除的一端队列特点：先进先出(FIFO),123,3.2 队列（QUEUE）,队列定义,假设队列S=(a1，a2，a3，an)，则a1称为队首元素，an为队尾元素。队中元素按a1，a2，a3，an的

38、次序入队，出队按先进先出的原则进行的,因此a1，a2，a3，an的次序出队 front 和rear的初始值地队列初始化时均应置为-1。,124,入队时将rear+1,新元素插入elementsfront位置.出队时，将加front+1,删去元素,3.2 队列（QUEUE）,a1 a2 a3.an,入队,出队,front,rear,队列Q=(a1,a2,an),队列定义,125,3.2 队列（QUEUE）,双端队列,126,3.2 队列（QUEUE）,队列的主要操作,（1）建立一个空队列 InitQueue(&Q)（2）进队 EnQueue(&Q,e)（3）出队 DeQueue(&Q,&e)（4

39、）判断一个队列是否为空 QueueEmpty(Q)（5）获得队头元素值 GetHead(Q,&e),127,3.2 队列（QUEUE）,二、链队列,结点定义typedef struct node int data;struct node*next;Qnode,*QueuePtr;,128,3.2 队列（QUEUE）,链队列图示,129,入队不用考虑队满,但出队要考虑队空 队空条件为 front=NULL,3.2 队列（QUEUE）,链队列图示,130,3.2 队列（QUEUE）,链队列入队算法,p=(QueuePtr)malloc(sizeof(Qnode);p-data=x;p-next=N

40、ULL;Q-rear-next=p;Q-rear=p;,131,3.2 队列（QUEUE）,链队列出队算法,if(Empty(Q)return ERROR;else s=Q-front-next;/*指向被删结点*/if(s-next=NULL)Q-front-Next=Null;Q-rear=Q-front;Else Q-front-next=s-next;*e=s-data;free(s);return OK;,132,3.2 队列（QUEUE）,J1,J2,J3,设两个指针front,rear,约定：rear指示队尾元素；front指示队头元素前一位置初值front=rear=-1,空队

41、列条件：front=rear入队列：sq+rear=x;出队列：x=sq+front;,三、循环队列-队列的顺序表示和实现,133,3.2 队列（QUEUE）,存在问题,设数组维数为M，则：当front=-1,rear=M-1时，再有元素入队发生溢出真溢出当front-1,rear=M-1时，再有元素入队发生溢出假溢出解决方案:队首固定，每次出队剩余元素向下移动 浪费时间循环队列,134,循环队列 基本思想：存储队列的数组被当作首尾相接的表处理；让sq0接在sqM-1之后，若rear+1=M,则令rear=0。,3.2 队列（QUEUE）,实现：利用“模”运算入队：rear=(rear+1)%

42、M;sqrear=x;出队：front=(front+1)%M;x=sqfront;队满、队空判定条件,135,rear,front,maxSize-1,入队:rear=(rear+1)%MaxSize;elementsrear=item出队：front=(front+1)%MaxSize;,队空：rear=front;队满：(rear+1)%maxSize=front;,0,1,2,front,0,1,2,rear,队列初始化：front=rear=0;,存储队列的数组被当作首尾相接的表处理。队头、队尾指针加1时从MaxSize-1直接进到0，可用语言的取模(余数)运算实现。,3.2 队列（

43、QUEUE）,136,3.2 队列（QUEUE）,初始状态,解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间：队空：front=rear 队满：(rear+1)%M=front,循环队列出入队图示,队空：front=rear 队满：front=rear,137,3.2 队列（QUEUE）,少用一个元素空间解决方案,队空 rear=front;队满(rear+1)%maxSize=front;入队 rear=(rear+1)%MaxSize;elementsrear=item；出队 front=(front+1)%MaxSize;,138,void en_cycque(int s

44、q,int front,int rear,int x)if(rear+1)%MAXSIZE)=front)printf(overflow);else rear=(rear+1)%MAXSIZE;sqrear=x;,3.2 队列（QUEUE）,循环队列入队算法,139,循环队列出入队图示,3.2 队列（QUEUE）,int del_cycque(int sq,int front,int rear,int*q)if(front=rear)return(0);else front=(front+1)%MAXSIZE;*q=sqfront;return(1);,140,1.铁路进行列车调度时,常把站台

45、设计成栈式结构的站台，如右图所示。试问：,(1)设有编号为1,2,3,4,5,6的六辆列车,顺序开入栈式结构的站台,则可能的出栈序列有多少种?(2)若进站的六辆列车顺序如上所述,那么是否能够得到435612,325641,154623和135426的出站序列,如果不能,说明为什么不能;如果能,说明如何得到(即写出进栈或出栈的序列)。,第三章 习题与上机实验,141,第三章 习题与上机实验,2.假设以数组Qm存放循环队列中的元素,同时以rear和length分别指示环形队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件,并写出相应的插入(enqueue)和删除(delq

46、ueue)元素的操作。,142,第四章 数 组,数组的顺序表示和实现矩阵的压缩存储:特殊矩阵 稀疏矩阵,【学习内容】,143,4.1 数组的定义及运算,数组的性质,数组元素数目固定元素类型相同下标有界且有序,144,一维数组,数组图示,4.1 数组的定义及运算,eg.a1,a2,（a11,a12,a1n）,(a21,a22,a2n),145,二 维 数 组,4.1 数组的定义及运算,数组图示,三 维 数 组,146,4.1 数组的定义及运算,定义：由值和下标构成的有序对，结构中的每一个元素都与一对下标有关。运算：给定一组下标，存取相应DE 给定一组下标，修改相应DE,147,42 数组的顺序表

47、示,元素数目、关系固定,顺序存储,多维数组以一维方式存储，即数组元素还是数组！,问题：内存是一维的，如何以一维内存存储多维数组,148,42 数组的顺序表示,LOC(i)=LOC(i-1)+l=+i*l,一维数组的存储,149,42 数组的顺序表示,二维数组的存储,150,52 数组的顺序表示,行优先 LOC(i,j)=a+(i 0)*m+(j-0)*l,列优先 LOC(i,j)=a+(j-0)*n+(i 0)*l,例：,151,n维数组,各维元素个数为 m1,m2,m3,mn下标为 i1,i2,i3,in 的数组元素的存储地址：,42 数组的顺序表示,152,43 矩阵的压缩存储,压缩存储,

48、多个值相同的元素只分配一个空间，零元素不分配空间,153,一、特殊矩阵定义：相同元素/零元素分布有一定规律的矩阵。,1.对角矩阵,43 矩阵的压缩存储,154,若将以上两矩阵以一维数组BM压缩存储,aij bk,三对角阵,单对角阵,43 矩阵的压缩存储,155,2.上（下）三角矩阵,0,0,非零元素共n(n+1)/2个，以数组Bn*(n+1)/2存储非零 DE,43 矩阵的压缩存储,156,下三角,2.上（下）三角矩阵,上三角,43 矩阵的压缩存储,157,3.对称矩阵,aij=ajik=I(I+1)/2+J;I=max(i,j),J=min(i,j),43 矩阵的压缩存储,好东西啊！,158

49、,二.稀疏矩阵,Am*n 中非零元素个数远小于零元素个数,43 矩阵的压缩存储,1三元组表组成：所有非零元素（行，列，值）+（行数，列数，非零元素个数）,159,三元组表类型说明：#define SMAX 16typedef int datatype；typedef structint i,j;/*行列号*/datatype v;/*元素值*/node;typedef structint m,n,t;/*行、列数，非零元素个数*/node dataSMAX;/*三元组表*/SpMatrix;,43 矩阵的压缩存储,160,43 矩阵的压缩存储,三元组表示例,行数 列数 元素个数,行 列 值,1

50、61,43 矩阵的压缩存储,例：矩阵转置：Am*n-Bn*m 且 aij=bji,162,(1)一般矩阵：for(row=0;rowm;row+)for(col=0;coln;col+)bcolrow=arowcol;时间复杂度为 O(m*n),43 矩阵的压缩存储,163,43 矩阵的压缩存储,(2)三元组表,164,稀疏矩阵转置算法思想,43 矩阵的压缩存储,设矩阵列数为Cols，对矩阵三元组表扫描Cols次。第k次检测列号为k的项。第k次扫描找寻所有列号为k的项，将其行号变列号、列号变行号，顺次存于转置矩阵三元组表。设矩阵三元组表总共有Terms项，其时间代价为 O(Cols*Terms