数据结构ppt3.ppt
第第3章章 栈、队列和数组栈、队列和数组n31 栈n32 队列n33 数组n34 栈的应用栈和递归 3.1 栈栈3.1.1 栈的定义和运算栈的定义： 栈是只能在一端进行插入和删除的线性表(运算受限)。由此，栈具有后进先出（LIFO）的特性。a1a2an入栈(插入)出栈(删除)栈顶：插入、删除的一端栈底：栈顶的另一端栈顶元素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)： 若栈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; seqstack; /定义了一个栈类型seqstackseqstack s1,*s; /定义了栈变量s1和指向栈类型的指针s3.1 栈栈3.1.2 顺序栈1、存储结构a1a2an 下标： 0 1 n maxsize -1datatopn-1S存储结构示意图如下：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 stack_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; （6）出栈 void pop_stack(seqstack *S，elementtype *x) if(stack_empty(*S) error(“栈空，无元素”)； *x = s-datas-top; s-top - - ; 3.1 栈栈3.1.3 链栈 采用链表存储的栈为链栈。 可使用不带头结点的单链表结构，链表头指针为栈顶，链表尾为栈底，则对链栈的操作与对单链表的操作相同，只是入栈和出栈操作在表头位置进行。an-1 a2 a1top 显然在链表的头部做栈顶是最方便的，而且没有必要象单链表那样为了运算方便附加一个头结点。 3.1 栈栈3.1.4 栈的应用实例例3.1 读入一个有限大小的整数n，并读入n个整数，然后按输入次序的相反次序输出各元素的值。 分析： 因最后输入的数据要最先输出，所以采用栈结构，可使用顺序栈或链栈。 先逐一输入数据压人堆栈中，再从堆栈中逐一将数据弹出即可。3.1 栈栈3.1.4 栈的应用实例例3.1void read_write() stack S; int n, x; printf(”Please input num int n”); scanf(“%n”, &n); /输入元素个数 init_stack(S); /初始化栈 for (i=1; inext; / u-next=P; / P=u; / L=P; /原表头指针指示新的表头指针算法如下：3.1 栈栈3.1.4 栈的应用实例例3.3 实现对任意输入的表达式的计算。分析： 表达式以字符串(用#将表达式括起来)的形式输入，需要用两个栈分别存储表达式中的操作数和运算符。 求解时，依次扫描表达式中的各基本符号(运算符、操作数)，并根据扫描的内容分别处理。 具体处理如下：3.1 栈栈3.1.4 栈的应用实例例3.3定义运算符栈S和操作数栈O扫描表达式中的基本符号操作数？操作数入栈栈顶运算符0时，重复(1)，(2)：（1）若 N0，则将N % r 压入栈s中 ，执行2;若N=0，将栈s的内容依次出栈，算法结束。（2）用N / r 代替 N3.1 栈栈3.1.4 栈的应用实例例3.4typedef int elementtype; void conversion(int N，int r) seqstack s; elementtype x; init_stack(&s); while ( N ) pushstack ( &s ，N % r ); N=N / r ; while(stack_empty (& s ) ) popsstack (&s ，&x ) ; printf ( “ %d ”，x ) ; 算法如下：3.2 队列队列3.2.1 队列的定义和运算队列的定义： 队列是只能在一端插入、另一端删除的线性表(运算受限)。由此，队列具有先进先出（FIFO）的特性。a1a2 an出队(删除)入队(插入)队头：删除端队尾：插入端队头元素队尾元素3.2 队列队列3.2.1 队列的定义和运算队列的基本运算： (1) 初始化队列init_queue(Q)： 设置队列Q为空。(2) 判断队列是否为空queue _empty(Q)： 若队列Q为空，返回1(TRUE)；否则返回0(FLASE)。(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、存储结构 以顺序存储方式储存的队列为顺序队列。可用数组datamaxsize存放元素，并设两个量front、rear指向队头元素的前一个位置和队尾元素的位置，则类型定义如下：#define maxsize 50typedef struct elementtype datamaxsize; int front，rear； /队头、队尾位置标示 seqqueue; /顺序队列类型seqqueueseqqueue Q1，*Q；/顺序队列的变量Q1和指向顺序队列的指针Q3.2 队列队列3.2.2 顺序队列与循环队列1、存储结构 存储结构示意图：a1a2 an 下标： 0 i j maxsize-1datafrontreari-1jQ3.2 队列队列3.2.2 顺序队列与循环队列1、存储结构 出队时头指针Q-front后移，入队时尾指针Q-rear后移，如此可能出现数组前面部分有闲置元素空间而尾指针Q-rear已指到数组最后一个元素(即Q-rear= =maxsize-1成立)的情况(假溢出假溢出)。 为此，可采用循环结构来解决，即将Q-data0做为Q-datamaxsize-1的下一个存储位置循环队列。 3.2 队列队列3.2.2 顺序队列与循环队列1、存储结构 Q-frontQ-rear01maxsize-1Q-data:3.2 队列队列3.2.2 顺序队列与循环队列1、存储结构 判定队空、队满状态： 方法一：方法一：设置一个出队或入队标志。 若最后一个操作是入队标志而导致Q-front= =Q-rear成立，则此时是队满； 若最后一个操作是出队标志而导致Q-front= =Qrear成立，则此时是队空。 方法二：方法二：少用一个元素空间(即将仅剩一个空位置时的状态作为队满)。 若要入队先判断(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 *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-rear = (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)，链表尾作为队尾(rear) ，可以将头、尾指针合在一起构成一个结构类型。 由于入队操作虽是在表尾插入结点，但该位置也可能在链表的第一个位置，所以最好采用带头结点的链表形式，以使操作简便。3.2 队列队列3.2.3 链队列1、存储结构 存储结构类型定义如下： typedef struct node *front, *rear ; linkqueue; linkqueue *Q; /指向链队列的指针Qa1 an frontrearQ3.2 队列队列3.2.3 链队列2、链队列各基本运算的实现(1) 初始化队列 void init_queue(linkqueue *Q) Q-front = (node *)malloc(sizeof(node); /产生头结点 Q-rear = Q-front; /头、尾
