数据结构导论第三章ppt课件.ppt

数据结构导论第三章,第三章 栈、队列和数组,3.1栈3.2队列3.3数组3.4应用举例,3.1 栈,3.1.1 栈的基本概念1、定义 栈限制在表的一端进行插入和删除运算的线 性表 栈顶（Top）：允许插入和删除的一段 栈底（Bottom）：栈的另一端 空栈：不含任何数据元素的栈 栈顶元素：处于栈顶位置的数据元素 例：叠盘子、盒装薯片,出栈：在栈顶插入元素入栈：在栈顶删除元素,栈顶,栈底,出栈(pop),进栈(push),栈的特点后进先出 栈中元素按a1，a2，a3，an的次序进栈，出栈的第一个元素为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出线性表（LIFO）。,练习,一个栈的入栈序列是a,b,c,d,e,则出栈的可能的顺序是()A cdabeB cabdeC dabecD decba,2、栈的基本运算,（1）初始化InitStack(S)：构造一个空栈S（2）判栈空EmptyStack(S):若栈S为空栈，则结 果为1，否则结果为0（3）进栈Push(S,x)：将元素x插入栈S中，使x成 为栈S的栈顶元素（4）出栈Pop(S)：删除栈顶元素（5）取栈顶GetTop(S)：返回栈顶元素,3.1.2 栈的顺序实现,1、顺序栈及常用名词 顺序栈 即栈的顺序实现； 栈容量栈中可存放的最大元素个数；, 栈顶指针top指示当前栈顶元素在栈中的位置； 栈空栈中无元素时，表示栈空； 栈满数组空间已被占满时，称栈满； 下溢当栈空时，再要求作出栈运算，则称“下溢”； 上溢当栈满时，再要求作进栈运算，则称“上溢”；,# define maxsize 5typedef struct seqstack DataType datamaxsize; int top; SeqStk;,SeqStk *s ; /*定义一顺序栈s*/ 约定栈的第1个元素存在data1中,则： s-top=0 代表顺序栈s为空； s-top=maxsize -1 代表顺序栈s为满 ；,top,210,2、顺序栈的运算1）初始化 int Initstack(SeqStk *stk) stk-top=0; return 1; 2) 判栈空 int EmptyStack(SeqStk *stk) if(stk-top=0) return 1; else return 0; 栈空时返回值为1，否则返回值为0。,2 1 0,top,3) 进栈,int Push(SeqStk *stk, DataType x) /*数据元素x进顺序栈stk*/ if（stk-top=maxsize -1) /*判是否上溢*/ error(“栈满”);return 0; /*上溢*/ else stk-top+；/*修改栈顶指针，指向新栈顶*/ stk-datastk-top=x; /*元素x插入新栈顶中*/ return 1; ,int Pop(SeqStk *stk) /*顺序栈stk的栈顶元素退栈*/ if（stk-top=0） /*判是否下溢*/ error(“栈空”);return 0; /*下溢*/ else stk-top- ； /*修改栈顶指针，指向新栈顶*/ return 1; ,4)出栈,5) 取栈顶元素DataType GetTop(SeqStk *stk) if(EmptyStack(stk) return NULLData; /栈空，返回NULLData else return stk-datastk-top;/返回栈顶数据元素 ,1、链式栈的定义 栈的链式存储结构称为链栈，它是运算受限的单链表，插入和删除操作仅限制在表头位置上进行。栈顶指针LS-next。,链式栈的类型说明如下： typedef struct node DataType data; struct node *next LkStk;,头指针LS,栈顶,栈底,下溢条件：LS-next=NULL,上溢：可不考虑栈满现象,3.1.3 栈的链式实现链栈,1)初始化void InitStack(LkStk *LS) LS=(LkStk *)malloc(sizeof(LkStk); LS-next=NULL;2）判栈空int EmptyStack(LkStk *LS) if(LS-next=NULL) return 1; else return 0;,2、链栈的基本运算,2、链栈的基本运算,3）进栈在栈顶插入一元素x, 生成新结点（链栈不会有上溢情况发生）, 将新结点插入链栈中并使之成为新的栈顶结点,void Push (LkStk *LS, DataType x) LkStk *temp; temp= (LkStk *) malloc (sizeof (LkStk); temp-data=x; temp-next=LS-next; LS-next=temp; ,4）出栈在栈顶删除一元素，并返回, 考虑下溢问题, 不下溢，则取出栈顶元素，从链栈中 删除栈顶结点并将结点回归系统。,int Pop (LkStk *LS) LkStk *temp; if (!EmptyStack (LS) temp=LS-next; LS-next=temp-next; free(temp); return 1; else return 0; ,练习,设一个链栈的输入序列为A、B、C，试写出所得到的所有可能的输出序列，即输出出栈操作得到的数据元素排列。,5）取栈顶元素 DataType GetTop(LkStk *LS) if (!EmptyStack(LS) return LS-next-data; else return NULLData; ,3.1.3 栈的应用举例,1、栈的基本应用实例： 设栈的输入序列依次为1,2,3,4，则所得的输出序列不可能是_ 。 a 1,2,3,4 b 4,2,3,1 c 1,3,2,4 d 3,4,2,1,例1,b,例2,阅读程序片段，写出运行结果。（见P66）,例3,写一个算法，借助栈将下图所示的带头结点的单链表逆置。(见P67),a1,an ,head,头结点,2、递归与递归的阅读： (1)递归的定义： 如果一个函数在完成之前又调用自身，则称之为递归函数。,程序实现：int f(int n) if(n=0) return(1); else return(n*f(n-1);,队列(Queue)也是一种运算受限的线性表。队列是只允许在表的一端进行插入，而在另一 端进行删除的线性表。 其中：允许删除的一端称为队头(front)， 允许插入的另一端称为队尾(rear)。 队列 Q=(a1，a2，a3，an) 示意图：,出队,入队,队头,队尾,a1，a2，an,（在队头删一元素）,（在队尾插一元素）,3.2 队 列,3.2.1 队列的基本概念,例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,an ，也就是说队列的修改是依先进先出的原则进行的。,队列特点：先进先出（FIFO）,队列的用途常用于暂时保存有待处理的数据。,队列初始化 InitQueue(Q): 设置一个空队列Q；判队列空 EmptyQueue(Q): 若队列Q为空，则返回值为1，否则返回值为0；入队列 EnQueue(Q,x): 将数据元素x从队尾一端插入队列，使其成为队列的新尾元素；出队列 OutQueue(Q): 删除队列首元素；取队列首元素GetHead(Q): 返回队列首元素的值。,队列的基本操作,3.2.2 队列的顺序实现循环队列,用一维数组作为队列的存储结构,maxsize-1 1 0,队列容量队列中可存放的最大元素个数,约定：,初始： front=rear=0进队： rear增1，元素插入尾指针所指位置出队： front增1，取头指针所指位置元素,队头指针front队尾指针 rear,始终指向实际队头元素的前一位置始终指向实际队尾元素,#define maxsize 20typedef struct seqqueue DataType datamaxsize; int front, rear ; SeqQue;SeqQue sq;,入队列操作：sq.rear=sq.rear+1; sq.datasq.rear=x;出队列操作：sq.front=sq.front+1;,543210,543210,543210,543210,543210,sq,sq.rear,sq.front,sq.rear,sq.front,sq.rear,sq.front,sq.rear,sq.front,sq.rear,sq.front,a),e),c),d),b),图a为空队列，sq.rear=0,sq.front=0。图b为20入队列后，sq.rear=1,sq.front=0。图c为30,40,50依次入队列后，sq.rear=4,sq.front=0。图d为20,30,40,50依次出队列后，sq.rear=4,sq.front=4。图e为60入队列后，sq.rear=5,sq.front=4。,1、顺序队列 只能从数组的一头插入、另一头删除。 SeqQue sq ； 上溢条件：sq.rear = maxsize-1 ( 队满 ) 下溢条件：sq.rear = sq.front (队列空),假溢出：sq.rear = maxsize-1，但队列中实际容量并 未 达到最大容量的现象。,极端现象：队列中的项不多于1, 也导致“上溢”,浪费空间,为克服“假溢出”引入了,循环队列,2、循环队列：,定义为队列分配一块存储空间(数组表示)，并将 这一块存储空间看成头尾相连接的。,示意图：,43210,想象成,0,1,2,3,4,循环队列,front,rear,头指针front顺时针方向落后于实际队头元素一个位置尾指针rear 指向实际队尾元素,循环队列循环的实现,sq.rear=(sq.rear+1)%maxsize,对插入即入队：队尾指针增1,sq.front=(sq.front+1)%maxsize,对删除即出队：队头指针增1,循环队列类型定义： typedef struct Cycqueue DataType datamaxsize; int front,reat; CycQue; CycQue CQ;,初始 front=rear=0,J1,J2,J3,队空,J4,J5,J7,队满,上溢,J2,J3,J1,例：,J6,J8,当队列为空或者为满时，均有front=rear，因此规定如下规定：循环队列CQ下溢条件即队列空： CQ.front=CQ.rear上溢条件即队列满： 尾指针从后面追上头指针 即：(CQ.rear+1)%maxsize=CQ.front （尾赶头） （队满时实际队容量=maxsize-1）,（2）循环队列运算,入队在队尾插入一新元素x, 判上溢否？是，则上溢返回；, 否则修改队尾指针（增1），新元素x插入队尾。,出队删除队头元素，并返回, 判下溢否？是，则下溢返回；, 不下溢，则修改队头指针，取队头元素。,1.队列的初始化2.判队列空3.入队列,循环队列的基本运算：,void InitQueue(CycQue CQ)CQ.front=0; CQ.rear=0;,int EmptyQueue(CycQue CQ) if (CQ.rear=CQ.front) return 1; else return 0;,int EnQueue(CycQue CQ,DataType x) if (CQ.rear+1)%maxsize=CQ.front) error(“队列满”);return 0;/入队列失败 else CQ.rear=(CQ.rear+1)%maxsize; CQ.dataCQ.rear=x; return 1; /入队列成功 ,4.出队列5.取队列首元素,int OutQueue(CycQue CQ) if (EmptyQueue(CQ) error(“队列空”)；return 0； else CQ.front=(CQ.front+1)%maxsize; return 1； ,DataType GetHead(CycQue CQ) if (EmptyQueue(CQ) return NULLData； else return CQ.data(CQ.front+1)%maxsize; ,1、链式队列的定义 链式队列用链表表示的队列，即它是限制仅 在表头删除和表尾插入的单链表。,头指针 front,队头,队尾,尾指针rear,显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。,附设两指针： 头指针front指向表头结点；队头元素结点为front-next 尾指针 rear指向链表的最后一个结点（即队尾结点）,3.2.3 队列的链式实现链式队,将链队列的类型定义为一个结构类型：,链队列类型说明：,typedef struct LinkQueueNode DataType data; struct LinkQueueNode *next; LkQueNode；,typedef struct LkQueue LkQueue *front ,*rear; LkQue;LkQue LQ ; /链式队列,LQ.front链式队的队头指针LQ.rear 链式队的队尾指针,链式队的上溢：可不考虑；（因动态申请空间）,链式队的下溢：即链式队为空时，还要求出队；,LQ. front,此时链表中无实在结点：,LQ.front-next=NULL,规定：链队列空时，令rear指针也指向表头结点。,链队列下溢条件： LQ.front-next=NULL 或 LQ.front= LQ.rear；,LQ. rear,LQ.front= LQ.rear,队列的初始化判队列空,2、链队列的基本运算,void initQueue(LkQue *LQ) LkQueNode *temp; temp=(LkQueueNode *)malloc(sizeof(LkQueNode); LQ-front=temp; LQ-rear=temp; (LQ-front)-next=NULL;,int EmptyQueue(LkQue LQ) if (LQ.rear=LQ.front) return 1; else return 0; ,入队列,Void EnQueue(LkQue *LQ;DataType x) LkQueNode *temp; temp=(LkQueNode *)malloc(sizeof(LkQueNode); temp-data=x; temp-next=NULL; (LQ-rear)-next=temp; LQ-rear=temp;,Q.front,入队在队尾即链表尾部插入一元素x, 生成新结点p（其数据域置x，链域置NULL）, 将新结点p插入到表尾，并变成新的队尾结点,Q.rear,出队列,OutQueue(LkQue *LQ) LkQueNode *temp; if (EmptyQueue(LQ) error(“对列空”)；return 0； else temp=(LQ-front)-next; (LQ-front)-next=temp-next; if (temp-next=NULL) LQ-rear=LQ-front; free(temp); return 1;,Q.front,Q.rear,出队在链式队中删除队头元素, 考虑下溢否, 不下溢，则取队头结点的直接后继结点；将temp指向该结点；从链式队中删除该结点；若链式队中原只有一个元素，则删除后队列为空，应修改队尾指针；结点temp回归系统。,取队列首元素,DataType GetHead (LkQue LQ) LkQueNode *temp; if (EmptyQueue(LQ) return NULLData; else temp=LQ.front-next; return temp-data; ,数组可看成是一种特殊的线性表，其特殊在于，表中的数组元素本身也是一种线性表。,Amn=,3.3 数 组,3.3.1 数组的逻辑结构和运算,数组是线性表的推广，其每个元素由一个值和一 组下标组成，其中下标个数称为数组的维数。 数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是线性表的推广。例如，二维数组：,二维数组Amn可以看成是由m个行向量组成的线性表，也可以看成是n个列向量组成的线性表。 数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组通常只有两种基本运算： 读给定一组下标，读取相应的数据元素； 写给定一组下标，修改相应的数据元素；,Amn=,1.存储结构顺序存储结构 由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。 又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。,3.3.2 数组的存储结构,2.存储方式：（通常有两种顺序存储方式）行优先顺序（以行为主存放）将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为： a00，a01,a02,a0 n-1, a1 0，a1 1,a1 2,a1 n-1, ,am-1 0, am-1 1, am-1 2 ， ,am-1 n-1 在PASCAL、C语言中，数组就是按行优先顺序顺序存储的。列优先顺序（以列为主存放）将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，A的m*n个元素按列优先顺序存储的线性序列为： a0 0,a1 0,am-1 0,a0 1,a1 1,am-1 1,a0 n-1,a1 n-1, , am-1 n-1,以上规则可以推广到多维数组的情况：行优先顺序（以行为主存放）以下标最右边变化最快，最左边变化最慢的规则存放。列优先顺序（以列为主存放）以下标最左边变化最快，最右边变化最慢的规则存放。 按上述两种方式顺序存储的数组，只要知道开始元素的存放地址（即基地址）、维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数。因此，数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。,3.寻址公式（以行为主存放） 例如，二维数组Amn按“行优先顺序”存储在内存中，假设每个元素占用k个存储单元。 元素aij的存储地址应是数组的基地址加上排在aij前面的元素所占用的单元数。因为aij位于第i行、第j列，前面i行一共有in个元素，第i行上aij前面又有j个元素，故它前面一共有in+j个元素，因此，aij的地址计算函数为： LOC(aij)=LOC(a00)+(i*n+j)*k,练习,设有二维数组int M1020,每个元素（整数）占2个存储单元，数组的起始地址为2000，元素M510的存储位置为，M819的存储位置为。,在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，简单而又自然的方法，就是将一个矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为1。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为1，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间， 我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。,3.3.3 矩阵的压缩存储,1、对称矩阵 1.定义：在一个n阶方阵A中，若元素满足下述性质： aij=aji 0i,jn-1 则称A为对称矩阵。如下图便是一个5阶对称矩阵。,特殊矩阵即指非零元素或零元素的分布有一定规律的矩阵。下面我们讨论几种特殊矩阵的压缩存储。,一、特殊矩阵,在这个下三角矩阵中，第i行恰有i个元素，元素总数为： (i)=n(n+1)/2 因此，我们可以按图中箭头所指的次序将这些元素存放在一个一维数组S1.n(n+1)/2中。为了便于访问对称矩阵A中的元素，我们必须在aij和Sk之间找一个对应关系。,2.物理存储： 对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按“行优先顺序”存储主对角线（包括对角线）以下的元素，其存储形式如图所示：,a0 0a1 0 a 1 1a2 0 a2 1 a2 2 .an-1 0 a n-1 1 a n-1 2 a n-1 n -1,(1) 若ij，则ai j在下三角形中。ai j之前的i行（从第0行到第i-1行）一共有1+2+i=i(i+1)/2个元素，在第i行上， ai j之前恰有j个元素（即ai 0,ai 1,ai 2,ai 3,ai j-1）， 因此有：,若ij，则aij是在上三角矩阵中。因为aij=aji，所以只 要交换上述对应关系式中的i和j即可得到： k=j*(j+1)/2+i 0kn(n+1)/2 -1,下标变换公式：（以下三角表示）,即： ai j,Si*(i+1)/2+j ,k=i*(i+1)/2+j 0k n(n+1)/2-1,令 I=max(i,j)， J=min(i,j)，则k和 i, j的对应关系 可统一为： k=I*(I-1)/2+J 0kn(n+1)/2 -1,有了上述的下标交换关系，对于任意给定一组下标(i，j)，均可在Sk中找到矩阵元素aij，反之，对所有的k=0,1,2,3,n(n+1)/2-1，都能确定Sk中的元素在矩阵中的位置(i,j)。由此，称Sn(n+1)/2为对称矩阵A的压缩存储，见下图：,k=0 1 2 3 n(n+1)/2-1 例如a31和a13均存储在 sa4中，这是因为： k=I*(I-1)/2+J=3*(3-1)/2+1=4,三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量s0.n(n+1)/2中，其中c存放在向量的最后一个分量中。 上三角矩阵中，主对角线之上的第p行(0pj,下三角矩阵的存储和对称矩阵类似，sk和aij对应关系是： i(i+1)/2+j ij j(j+1)/2+i ij,什么是稀疏矩阵？简单说，设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数，则称A为稀疏矩阵。,稀疏矩阵的压缩存储即只存储稀疏矩阵中的非零元素。有两种存储方法。,精确点，设在的矩阵A中，有s个非零元素。令 e=s/(m*n)，称e为矩阵的稀疏因子。通常认为e0.05时称之为稀疏矩阵。在存储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储方法。,由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置（i,j)。反之，一个三元组(i,j,aij)唯一确定了矩阵A的一个非零元。因此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。,二、稀疏矩阵的压缩存储,例如，下列三元组表 ( (0,1,12)，(0,2,9)，(2,0,- 3)，(2,5,14)，(3,2,24), (4,1,18)，(5,0,15)，(5,3,-7) ) 加上(5,6)这一对行、列值便可作为下列矩阵M的另一种描述。而由上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法。,1、三元组顺序表 稀疏矩阵的三元组顺序表表示法将矩阵中的非零元素化成三元组形式并按行的不减次序（同行按列的递增次序）存放在内存中。1).三元组表结构： 假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法三元组顺序表。 #define maxnum 10 typedef struct node int i, j; /*非零元的行下标和列下标*/ DataType v; /*非零元素的值*/ NODE;三元组,typedef struct spmatrix NODE datamaxnum; /*非零元三元组表*/ int mu,nu,tu; /*矩阵的行数、列数和非零元个数*/ SpMatx;稀疏矩阵三元组表存储类型 设:SpMatrx M ; 则下图中所示的稀疏矩阵的三元组的表示如右：,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,i j v 0 0 1 12 1 0 2 9 2 2 0 -3 3 2 5 14 4 3 2 24 5 4 1 18 6 5 0 15 7 5 3 -7,三元组表,M.datap.iM.datap.jM.datap.v,掌握栈和队列的特点，并能在相应的应用问题中 正确选用它们；掌握栈的顺序存储结构的描述方法，栈空、栈满 条件及入栈、出栈算法 ；掌握循环队列和链式队列两种存储结构的描述方 法、上下溢条件以及出队、入队算法。 重点：栈、队列的操作原则与基本操作算法。,二维数组以行为主存储时的寻址公式； 特殊矩阵、稀疏矩阵的定义；对称矩阵压缩存储时的下标变换公式；稀疏矩阵的三元组顺序表的表示,第三章 栈、队列和数组小结,