数据结构ppt3.ppt

《数据结构ppt3.ppt》由会员分享，可在线阅读，更多相关《数据结构ppt3.ppt（66页珍藏版）》请在课桌文档上搜索。

1、第3章 栈、队列和数组,31 栈,32 队列,33 数组,34 栈的应用栈和递归,3.1 栈,3.1.1 栈的定义和运算,栈的定义：栈是只能在一端进行插入和删除的线性表(运算受限)。由此，栈具有后进先出（LIFO）的特性。,3.1 栈,3.1.1 栈的定义和运算,栈的基本运算：,(1)初始化栈init_stack(S)：设置栈S为空。,(2)判断栈是否为空stack_empty(S)：若栈S为空返回1(TRUE)；否则返回0(FLASE)。,(3)判断栈是否为满stack_full(S)：若栈S为满返回1(TRUE)；否则返回0(FLASE)。,(4)取栈顶元素值stack_top(S，x)：

2、若栈S不空，将栈顶元素的值送x中；否则返回出错信息。,3.1 栈,3.1.1 栈的定义和运算,栈的基本运算：,(5)入栈push_stack(S，x)：若栈S满，返回出错信息；否则将值为x的元素插入到栈中。,(6)出栈pop_stack(S)：若栈S空，返回出错信息；否则删除栈顶元素。,3.1 栈,3.1.2 顺序栈,1、存储结构,以顺序存储方式存储的栈称为顺序栈。可用数组datamaxsize来存放栈的元素值，并设置一个量top来标识栈顶位置。,类型定义如下：#define maxsize 50typedef struct elementtype datamaxsize;int top;se

3、qstack;/定义了一个栈类型seqstackseqstack s1,*s;/定义了栈变量s1和指向栈类型的指针s,3.1 栈,3.1.2 顺序栈,1、存储结构,存储结构示意图如下：,3.1 栈,3.1.2 顺序栈,2、基本运算的实现,（1）初始化栈 void init_stack(seqstack*S)/S是指针 s-top=-1;/设置栈空,（2）判断栈是否为空 int stack_empty(seqstack S)/S是变量 if(S.top=-1)return 1;else return 0;,3.1 栈,3.1.2 顺序栈,2、基本运算的实现,（3）判断栈是否为满 int stac

4、k_full(seqstack S)if(S.top=maxsize-1)return 1;else return 0;,（4）取栈顶元素值 void stack_top(seqstack*S，elementtype*x)if(stack_empty(*S)error(“栈空无元素”)；*x=s-datas-top;/栈顶元素由参数带回,3.1 栈,3.1.2 顺序栈,2、基本运算的实现,（5）入栈 void push_stack(seqstack*S，elementtype x)if(stack_full(*S)error(“栈满，入栈会溢出”)；s-top+;s-datas-top=x;,

5、（6）出栈 void pop_stack(seqstack*S，elementtype*x)if(stack_empty(*S)error(“栈空，无元素”)；*x=s-datas-top;s-top-;,3.1 栈,3.1.3 链栈,采用链表存储的栈为链栈。,可使用不带头结点的单链表结构，链表头指针为栈顶，链表尾为栈底，则对链栈的操作与对单链表的操作相同，只是入栈和出栈操作在表头位置进行。,显然在链表的头部做栈顶是最方便的，而且没有必要象单链表那样为了运算方便附加一个头结点。,3.1 栈,3.1.4 栈的应用实例,例3.1 读入一个有限大小的整数n，并读入n个整数，然后按输入次序的相反次序输

6、出各元素的值。,分析：因最后输入的数据要最先输出，所以采用栈结构，可使用顺序栈或链栈。先逐一输入数据压人堆栈中，再从堆栈中逐一将数据弹出即可。,3.1 栈,3.1.4 栈的应用实例,例3.1,void read_write()stack S;int n,x;printf(”Please input num int n”);scanf(“%n”,/退栈并输出栈顶元素,算法如下：,3.1 栈,3.1.4 栈的应用实例,例3.2 将单链表L就地逆置，即将链表中的各元素结点的后继指针倒置为指向其前驱结点，a1结点变成最后一个结点，an结点变成第一个结点。,分析：将链表看成链栈，则依次将原栈中的元素出栈

7、，并插入到初值为空的另一链栈中，当原栈为空时，另一栈即为原栈元素的逆序。,3.1 栈,3.1.4 栈的应用实例,例3.2,void reverse(node*L)node*P=NULL;while(L!=NULL)node*u=L;/L=L-next;/u-next=P;/P=u;/L=P;/原表头指针指示新的表头指针,算法如下：,3.1 栈,3.1.4 栈的应用实例,例3.3 实现对任意输入的表达式的计算。,分析：表达式以字符串(用#将表达式括起来)的形式输入，需要用两个栈分别存储表达式中的操作数和运算符。求解时，依次扫描表达式中的各基本符号(运算符、操作数)，并根据扫描的内容分别处理。,具

8、体处理如下：,3.1 栈,3.1.4 栈的应用实例,例3.3,3.1 栈,3.1.4 栈的应用实例,例3.4 数制转换问题：将十进制数N转换为r进制的数。,转换方法：利用辗转相除法。以N=3456，r=8为例,转换方法如下：N N/8(整数)N%8(余数)3467 433 3 433 54 1 54 6 6 6 0 6,所以：（3456）10=（6613）8,3.1 栈,3.1.4 栈的应用实例,例3.4,算法设计：当N0时，重复(1)，(2)：（1）若 N0，则将N%r 压入栈s中，执行2;若N=0，将栈s的内容依次出栈，算法结束。（2）用N/r 代替 N,3.1 栈,3.1.4 栈的应用实

9、例,例3.4,typedef int elementtype;void conversion(int N，int r)seqstack s;elementtype x;init_stack(,算法如下：,3.2 队列,3.2.1 队列的定义和运算,队列的定义：队列是只能在一端插入、另一端删除的线性表(运算受限)。由此，队列具有先进先出（FIFO）的特性。,3.2 队列,3.2.1 队列的定义和运算,队列的基本运算：,(1)初始化队列init_queue(Q)：设置队列Q为空。,(2)判断队列是否为空queue _empty(Q)：若队列Q为空，返回1(TRUE)；否则返回0(FLASE)。,(

10、3)判断队列是否为满queue _full(Q)：若队列Q为满，返回1(TRUE)；否则返回0(FLASE)。,(4)取队头元素值queue_front(Q，x)：若队列Q不空，将队头元素值送x中；否则返回出错信息。,3.2 队列,3.2.1 队列的定义和运算,队列的基本运算：,(5)入队enqueue(Q，x)：若队列Q满，返回出错信息；否则将值为x的元素插入到队列中。,(6)出队outqueue(Q，x)：若队列Q空，返回出错信息；否则删除队头元素，并将该元素的值置x中。,3.2 队列,3.2.2 顺序队列与循环队列,1、存储结构,以顺序存储方式储存的队列为顺序队列。可用数组datamax

11、size存放元素，并设两个量front、rear指向队头元素的前一个位置和队尾元素的位置，则类型定义如下：,#define maxsize 50typedef struct elementtype datamaxsize;int front，rear；/队头、队尾位置标示 seqqueue;/顺序队列类型seqqueueseqqueue Q1，*Q；/顺序队列的变量Q1和指向顺序队列的指针Q,3.2 队列,3.2.2 顺序队列与循环队列,1、存储结构,存储结构示意图：,3.2 队列,3.2.2 顺序队列与循环队列,1、存储结构,出队时头指针Q-front后移，入队时尾指针Q-rear后移，如此

12、可能出现数组前面部分有闲置元素空间而尾指针Q-rear已指到数组最后一个元素(即Q-rear=maxsize-1成立)的情况(假溢出)。为此，可采用循环结构来解决，即将Q-data0做为Q-datamaxsize-1的下一个存储位置循环队列。,3.2 队列,3.2.2 顺序队列与循环队列,1、存储结构,3.2 队列,3.2.2 顺序队列与循环队列,1、存储结构,判定队空、队满状态：,方法一：设置一个出队或入队标志。若最后一个操作是入队标志而导致Q-front=Q-rear成立，则此时是队满；若最后一个操作是出队标志而导致Q-front=Qrear成立，则此时是队空。,方法二：少用一个元素空间(

13、即将仅剩一个空位置时的状态作为队满)。若要入队先判断(Q-rear+1)%maxsize=Q-front是否成立，若成立则表示队满，不能入队。,3.2 队列,3.2.2 顺序队列与循环队列,2、循环队列各基本运算的实现（基于方法二）,(1)初始化队列 void init_queue(seqqueue*Q)Q-front=0;Q-rear=0;/队头、队尾位置相同,(2)判断队列是否为空 int queue_empty(seqqueue*Q)if(q-front=Q-rear)return 1;else return 0;,(3)判断队列是否为满 int queue_full(seqqueue*

14、Q)if(q-rear+1)%maxsize=Q-front)return 1;else return 0;,3.2 队列,3.2.2 顺序队列与循环队列,2、循环队列各基本运算的实现（基于方法二）,(4)取队头元素 void queue_front(seqqueue*Q,elementtype*x)if(queue_empty(Q)error(“队空”)else*x=Q-data(Q-front+1)%maxsize;/取队头元素,(5)入队 void en_queue(seqqueue*Q,elementtype x)if(queue_full(Q)error(“队满”)elseQ-rea

15、r=(Q-rear+1)%maxsize;/队尾位置后移 Q-dataQ-rear=x;/元素入队,3.2 队列,3.2.2 顺序队列与循环队列,2、循环队列各基本运算的实现（基于方法二）,(6)出队 void out_queue(seqqueue*Q,elementtype*x)if(queue_empty(Q)error(“队空”)else Q-front=(Q-front+1)%maxsize;/队头位置后移*x=QdataQfront;/当前队头位置的元素为原队头元素,3.2 队列,3.2.3 链队列,1、存储结构,队列采用链式存储方式时为链队列。将链表头作为队头(front)，链表尾

16、作为队尾(rear)，可以将头、尾指针合在一起构成一个结构类型。由于入队操作虽是在表尾插入结点，但该位置也可能在链表的第一个位置，所以最好采用带头结点的链表形式，以使操作简便。,3.2 队列,3.2.3 链队列,1、存储结构,存储结构类型定义如下：typedef struct node*front,*rear;linkqueue;linkqueue*Q;/指向链队列的指针Q,3.2 队列,3.2.3 链队列,2、链队列各基本运算的实现,(1)初始化队列 void init_queue(linkqueue*Q)Q-front=(node*)malloc(sizeof(node);/产生头结点 Q

17、-rear=Q-front;/头、尾指针指向头结点 Q-front-next=NULL;/头结点的后继指针为空,(2)判断队列是否为空 int queue_empty(linkqueue*Q)return Q-front=Q-rear;,3.2 队列,3.2.3 链队列,2、链队列各基本运算的实现,(3)取队头元素 void queue_front(linkqueue*Q,elementtype*x)if(queue_empty(*Q)error(“队空”)；else*x=Q-front-next-data;,(4)入队 void en_queue(linkqueue*Q,elementtyp

18、e x)node*p=(node*)malloc(sizeof(node);p-data=x;p-next=NULL;/设置新结点值 Q-rear-next=p;Q-rear=p;/新结点入队,3.2 队列,3.2.3 链队列,2、链队列各基本运算的实现,(5)出队 void out_queue(linkqueue*Q,elementtype*x)node*u;if(queue_empty(*Q)error(“队空”)else*x=Q-front-next-data;u=Q-front-next;/u指向待删除结点 Q-front-next=u-next;free(u);/出队 if(Q-fr

19、ont-next=NULL)Q-rear=Q-front;/若删除最后一个结点则队空,3.2 队列,3.2.4 队列的应用,例3.5设计算法，用队列计算并打印杨辉三角的前8行的内容，即输出结果如下：1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1,3.2 队列,3.2.4 队列的应用,例3.5,算法设计：可利用上一行的数来求出下一行对应位置的数，为便于求解，在每一行的第一个位置添加一个0作辅助，新行的最后一个数直接确定为1。用队列保存上一行的内容，每当由上一行的两个数求出下一行的一个

20、数时，删除前一个数，新求出的数入队。,3.2 队列,3.2.4 队列的应用,void Out_Number(int n)int i,j,k,s1,s2;seqqueue Q;Init_Queue(/最后元素入队,3.3 数组,3.3.1 数组的定义和运算,一维数组：有限个具有相同类型的变量组成的序列。二维数组：一维数组中每个变量本身是一维数组。n维数组：一维数组中每个变量本身是n-1维数组。,（a1,a2,an）一维数组,一维数组中的每个元素ai最多有一个直接前驱ai-1和一个直接后继ai+1,二维数组中每个元素aij分别属于行、列向量，所以最多有两个直接前驱a(i-1)j、ai(j-1)和两

21、个直接后继a(i+1)j、ai(j+1)。,3.3 数组,3.3.1 数组的定义和运算,一维数组：有限个具有相同类型的变量组成的序列。二维数组：一维数组中每个变量本身是一维数组。n维数组：一维数组中每个变量本身是n-1维数组。,对数组的运算，通常是对数组中的元素进行存、取、修改等操作。如此必须要计算出给定元素的实际存储地址。,3.3 数组,3.3.2 数组的顺序存储,数组中的元素按一定次序顺序存储在一个连续区域。如此，只要知道连续区域的起始地址、每个元素的长度、给定元素的存储序号，则可求出该元素的实际存储地址。,给定元素的地址=起始地址+存储序号*元素长度,一维数组A0.n-1：元素ai 的存

22、储序号为i+1。一维数组A1.n：元素ai 的存储序号为i。,3.3 数组,3.3.2 数组的顺序存储,二维数组(n行m列)中元素的存储有两种方式：,对二维数组A0.n-1,0.m-1：元素aij的存储序号为 i*m+(j+1)对二维数组A1.n,1.m：元素aij的存储序号为(i-1)*m+j,列号变化得比行号快,（1）行优先：逐行地顺序存储各元素。,3.3 数组,3.3.2 数组的顺序存储,（2）列优先：逐列地顺序存储各元素。,对二维数组A0.n-1,0.m-1：元素aij的存储序号为 j*n+(i+1)对二维数组A1.n,1.m：元素aij的存储序号为(j-1)*n+i,行号变化得比列号

23、快,二维数组(n行m列)中元素的存储有两种方式：,3.3 数组,3.3.3 矩阵的压缩存储,特殊矩阵：矩阵的元素值的分布有一定规律。稀疏矩阵：矩阵中有较多元素的值为0。为节约存储空间，可采用压缩方式来存储，即在不影响完整性的前提下，用更少的存储空间存储矩阵元素。,1、特殊矩阵（1）对称矩阵和三角矩阵 若矩阵Anxn满足ai j=aj i(1i,jn)，即关于对角线对称(上三角元素值与下三角相同)，则A为对称矩阵。若矩阵Anxn的对角线以上或对角线以下的元素值全为0(或同一值)，则A为三角矩阵。,3.3 数组,3.3.3 矩阵的压缩存储,为了节约存储空间，可以只存储上三角元素值或下三角元素值。如

24、此nxn个元素只需n(n-1)/2个(或n(n-1)/2+1个)存储空间。,设以行优先存储下三角时，则元素aij的存储序号为：i=j：为下三角的元素，序号=1+2+(i-1)+j=i(i-1)/2+j ij：为上三角的元素(即为下三角的元素aj i)，序号=j(j-1)/2+i,3.3 数组,3.3.3 矩阵的压缩存储,（2）对角矩阵 除了主对角线和紧靠主对角线的上、下若干条对角线外，其余元素全为0。,如三对角矩阵：,以行优先存储时，元素ai j(|i-j|=1)的存储序号：序号=3(i-1)-1+j-i+2=2i+j-2,3.3 数组,3.3.3 矩阵的压缩存储,2、稀疏矩阵 只需存储非零元

25、素，由于非零元素位置的不规则性，须用行号、列号及非零元素值来描述。由此一个非零元素可用一个三元组结构表示：typedef struct int i,j;/非零元素的行号、列号 elementtype v;/非零元素值 tuple;/三元组类型,3.3 数组,3.3.3 矩阵的压缩存储,2、稀疏矩阵,对应于一个稀疏矩阵，还需要有行数、列数及非零元素个数，所以其类型定义为：#define maxnum 20 typedef struct int mu,nu,tu;/矩阵行、列数、非零元素个数 tuple datamaxnum;/存放非零元素 spmatrix;spmatrix*M；,3.3 数组,

26、3.3.3 矩阵的压缩存储,2、稀疏矩阵,示例：,3.4 栈的应用栈和递归,3.4.1 递归的定义及其一般形式,直接或间接地调用自身的算法为递归算法。用函数自身给出定义的函数为递归函数。每个递归函数都必须有非递归定义的初始值。,例如：求整数n的阶乘，可递归定义如下：,3.4 栈的应用栈和递归,3.4.1 递归的定义及其一般形式,求整数n阶乘的递归算法：int fact(int n)if(n=0)return(1);else return(n*fact(n-1);,递归程序的一般形式：void Pname(参数表)if（数据为递归出口）简单操作；else 简单操作；Pname(实参表)；简单操作

27、；Pname(实参表)；简单操作；/多次调用时,3.4 栈的应用栈和递归,3.4.2 递归调用的内部实现原理,一般函数的内部实现：,调用时：1）保存返回地址，为被调函数的形参和局部变量分配空间2）实参值送形参3）转入被调函数执行,返回时：1）若有返回值，将返回值送一变量(回传变量)保存2）取出返回地址3）按返回地址返回4）返回后，若有返回值，则从回传变量中取出送相应位置,3.4 栈的应用栈和递归,3.4.2 递归调用的内部实现原理,递归调用的特殊处是：调用的是自身函数，可看成是调用自身的复制件，各复制件各自拥有自己的形参和局部变量。,调用时：（a）栈顶开辟存储空间，保存返回地址、被调层函数的形

28、参和局部变量；（b）计算实参的值并赋给对应的形参(在栈顶元素中)；（c）转入被调函数执行。,返回时：（a）若被调函数有返回值，将其值保存到回传变量中；（b）从栈顶取出返回地址并退栈(同时撤销被调层函数的局部变量及形参)；（c）按返回地址返回；（d）若被调函数有返回值，主调函数从回传变量中取出保存的值并传送到相应的变量或位置上。,3.4 栈的应用栈和递归,3.4.3 递归程序的阅读图示运行轨迹,(1)按次序写出程序当前调用层上实际执行的各语句，并用有向弧表示语句的执行次序。,(2)对程序中的每个调用语句或函数引用，写出其实际调用形式(带实参)，然后在其右边或下边写出本次调用的子程序实际的执行语句

29、，以区分调用主次和层次。并作如下操作：,在被调层的前面标明各形参的值。从调用操作处画一有向弧指向被调子程序的入口，以表示调用路线。从被调子程序的末尾处画一有向弧指向调用操作的下面，表示返回路线。,(3)若为函数,在返回路线上标出所得的函数值；若有要返回修改值的参数，在返回路线上增加标注：实参=形参的值,3.4 栈的应用栈和递归,3.4.3 递归程序的阅读图示运行轨迹,示例：,求整数n阶乘的递归算法：int fact(int n)int f;if(n=0)f=1;else f=n*fact(n-1);return f;,3.4 栈的应用栈和递归,3.4.3 递归程序的阅读图示运行轨迹,示例：,3

30、.4 栈的应用栈和递归,3.4.4 递归程序的编写,确定函数功能和变量含义，确定递归出口和描述,写出递归出口的操作,写出递归体的操作,构成递归函数,1、假设数据接近功能出口时函数功能正常(即假设出合理的较小问题)；2、在此基础上确定本层函数的事项(即给出本层函数与下面层函数之间的关系)。,3.4 栈的应用栈和递归,3.4.4 递归程序的编写,例3.13 fibnacci序列为：1，1，2，3，5，8，13，。编写求解第n个元素值的递归函数。,分析：该序列呈现的规律是：除了第一个及第二个元素为1外，从第三个元素开始，每个元素是前两个元素之和，则fibnacci序列表示如下：,设函数名为F,参数n

31、，则：(1)递归出口为：n2时，F(n)=1。(2)递归体即为：n2时,假设在nK时函数功能正确,则在n=k时,F(n)=F(n-1)+F(n-2)。,3.4 栈的应用栈和递归,3.4.4 递归程序的编写,例3.13 fibnacci序列为：1，1，2，3，5，8，13，。编写求解第n个元素值的递归函数。,递归程序如下：int F(int n)if(n=2)return 1;else return F(n-1)+F(n-2);,3.4 栈的应用栈和递归,3.4.5 递归的模拟,递归程序,非递归程序,存在一些问题：1、程序设计语言对递归的支持方面的限制。2、程序运行的时间性能方面不如非递归程序。

32、,转换,有两种方法：（1）直接转换法：使用中间变量保存中间结果，不需要回溯；（2）间接转换法：需要回溯，用栈保存中间结果。,3.4 栈的应用栈和递归,3.4.5 递归的模拟,间接转换法的转换规则：,1、设置一个栈，初始置为空。,2、在转入子程序的入口处设置一个标号(如：L0)。,3、对程序中的每一个递归调用，用以下操作来替换：将返回地址(标号)、形参和局部变量的植入栈；计算实参的值赋给对应的形参；转入子程序(goto L0)；返回处设一标号，并根据需要可从回传变量中取值送相应位置。,4、对返回语句，用以下操作来替换：若有返回值，将其保存到回传变量中；将返回地址(标号)出栈(可保存到变量X中)，

33、各变量和形参的值出栈；按返回地址返回(goto X)。,5、对其中非递归调用和返回操作可照搬。,3.4 栈的应用栈和递归,3.4.5 递归的模拟,简化规则1：如果递归程序中只有一处递归调用，则转换时返回地址不必入栈。（则返回处不设标号，goto X改为goto L0）,简化规则2：在模拟尾递归调用时，不必执行入栈操作。（尾递归：程序中的递归调用处于子程序中的最后位置，即其后没其他操作，返回后不做其他操作。如函数返回后要执行相应赋值操作，不是尾递归。）,根据转换后的程序绘制流程图，进行调整后得一结构较好的程序。,3.4 栈的应用栈和递归,3.4.5 递归的模拟,例3.14 将下面递归程序转换为等

34、价的非递归程序。,void P(int w)if(w0)P(w-1);printf(“%d”,w);,void P1(int w)init_stack(S);/规则1 L0:/规则2 if(w0)/规则5 push_stack(S,w);/规则3.a、简化1 w=w-1;/规则3.b goto L0;/规则3.c L1:/规则3.d printf(“%d”,w);/规则5 if(!stack_empty(S)/规则4 pop_stack(S,/规则4.b,4.c,3.4 栈的应用栈和递归,3.4.5 递归的模拟,根据转换后的程序绘制流程图：,例3.14,3.4 栈的应用栈和递归,3.4.5 递归的模拟,根据流程图编写程序：,例3.14,void P1(int w)init_stack(S);while(w0)push_stack(S,w);w=w-1;while(!stack_empty(S)pop_stack(S,第四章,