《本章主要内容1栈的概念存储结构及其基本操作及其应用;2计算机存储_计算机-数据结构与算法.pdf》由会员分享，可在线阅读，更多相关《本章主要内容1栈的概念存储结构及其基本操作及其应用;2计算机存储_计算机-数据结构与算法.pdf（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、本章主要内容：1、栈的概念、存储结构及其基本操作及其应用；2、队列的概念、存储结构及其基本操作 及其应用 课时分配：1、2 各占 2 学时，上机 2学时 重点、难点：栈的存储结构及其基本操作、队列存储结构及其基本操作 3.1 栈 3.1.1 栈的定义 栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所 示：结论：后进先出(Last In First Out)，简称为 LIFO 线性表。例 3 1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最 先拿走最上面的那只碗，而最后拿出最下面的那只碗。例 3 2：在建筑工地上
2、，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。下面我们先给出栈结构的 基本操作：(1)初始化栈 InitStack(S)(2)入栈 Push(S,elem)(3)出栈 Pop(S,elem)(4)获取栈顶元素内容 GetTop(S,elem)(5)判断栈是否为空 StackEmpty(S)3.1.2 栈的顺序存储结构及其基本运算的实现 栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个数据元素，并用起始端作为栈底。类型定 义如下所示：#define MAXSIZE 100#define ERROR-1 typedef struct /*栈类定义*/int ele
3、mentsMAXSIZE;int top;Stack;基本操作算法：(1)初始化栈 void InitStack(Stack*S)/*初始化栈，将栈置空*/S-top=0;(2)入栈 void Push(Stack*S,int x)/*将元素 x 压入到栈 S 中*/if(!IsFull(*S)/*如果尚未达到栈满，则将 x 压入栈 S 中，并使栈顶指针增 1*/S-elementsS-top=x;S-top+;else printf(栈上溢！n);(3)出栈 int Pop(Stack*S)/*将栈 S 中的栈顶元素出栈*/if(!IsEmpty(*S)/*如果栈非空，则返回栈顶元素，并使栈
4、顶指针减 1*/S-top-;return S-elementsS-top;else printf(栈下溢！n);return ERROR;(4)获取栈顶元素内容 int GetTop(Stack S)/*获取栈顶元素，但不改变栈顶指针*/if(!IsEmpty(S)return S.elementsS.top-1;else printf(栈空！n);return ERROR;(5)判断栈 S 是否为空 bool IsEmpty(Stack S)/*判断栈是否为空。如果栈空，返回 true，否则返回 false*/学时上机学时重点难点栈的存储结构及其基本操作队列存储结构及其基本操作栈栈的定义栈
5、是一种特殊的线性表其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行如下所示结论后进先出简称为线性表例家里吃饭最下面的那只碗例在建筑工地上使用的砖块从底往上一层一层地码放在使用时将从最上面一层一层地拿取下面我们先给出栈结构的基本操作初始化栈入栈出栈获取栈顶元素内容判断栈是否为栈的顺序存储结构及其基本运算的实现栈类定义基本操作算法初始化栈初始化栈将栈置入栈将元素压入到栈中如果尚未达到栈满则将压入栈中并使栈顶指针增栈上溢出栈将栈中的栈顶元素出栈如果栈非空则返回栈顶元素并使栈顶指针减栈下溢获取栈顶元素内容获取栈顶元if(S.top=0)return true;else return fa
6、lse;结论：由于栈的插入和删除操作具有它的特殊性，所以用顺序存储结构表示的栈并不存在插入删除数据元 素时需要移动的问题，但栈容量难以扩充的弱点仍就没有摆脱。3.1.3 栈的链式存储及其基本运算的实现 若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。链式存储结构表示的栈称作 链栈 。链栈通常用一个无头结点的单链表表示。如图示：bottom 结点类型定义：t ypedef struct node /*栈类定义*/int data;struct node*next;LinkStack;(1)初始化 void InitLinkStack(LinkStack*top)/
7、*初始化栈，将栈置空*/*top=NULL;2)判断是否为空 bool IsEmpty(LinkStack*top)/*判断栈是否为空。如果栈空，返回 true，否则返回 false*/if(top=NULL)return true;else return false;3)进栈 void Push(LinkStack*top,int x)/*将元素 x 压入到栈 S 中，先申请结点再将其入栈*/LinkStack*S;S=(LinkStack*)malloc(sizeof(LinkStack);S-data=x;S-next=*top;*top=S;4)出栈 int Pop(LinkStack
8、*top)/*将栈 S 中的栈顶元素出栈*/LinkStack*S;int data;if(!IsEmpty(*top)/*如果栈非空，则返回栈顶元素，并使栈顶指针减 1*/S=*top;*top=(*top)-next;人们将用 学时上机学时重点难点栈的存储结构及其基本操作队列存储结构及其基本操作栈栈的定义栈是一种特殊的线性表其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行如下所示结论后进先出简称为线性表例家里吃饭最下面的那只碗例在建筑工地上使用的砖块从底往上一层一层地码放在使用时将从最上面一层一层地拿取下面我们先给出栈结构的基本操作初始化栈入栈出栈获取栈顶元素内容判断栈是否为
9、栈的顺序存储结构及其基本运算的实现栈类定义基本操作算法初始化栈初始化栈将栈置入栈将元素压入到栈中如果尚未达到栈满则将压入栈中并使栈顶指针增栈上溢出栈将栈中的栈顶元素出栈如果栈非空则返回栈顶元素并使栈顶指针减栈下溢获取栈顶元素内容获取栈顶元data=S-data;free(S);return data;else printf(栈下溢！n);return ERROR;(5)取栈顶元素 int GetTop(LinkStack*top)/*获取栈顶元素，但不改变栈顶指针*/if(!IsEmpty(top)return top-data;else printf(栈空！n);return ERROR;(
10、6)清空 void EmptyLinkStack(LinkStack*top)/*清空堆栈 S，使其栈顶指针为 0*/LinkStack*S;while(*top!=NULL)S=(*top)-next;free(*top);*top=S;3.1.4 栈的应用举例 例 3-3:将从键盘输入的字符序列逆置输出 比如，从键盘上输入：tset a si sihT；算法将输出：This is a test 下面我们给出解决这个问题的完整算法。typedef char Elemtype;void ReverseRead()Stack S;/定义一个栈结构 S char ch;InitStack(&S);
11、/初始化栈 while(ch=getchar()!=n)/从键盘输入字符，直到输入换行符为止 学时上机学时重点难点栈的存储结构及其基本操作队列存储结构及其基本操作栈栈的定义栈是一种特殊的线性表其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行如下所示结论后进先出简称为线性表例家里吃饭最下面的那只碗例在建筑工地上使用的砖块从底往上一层一层地码放在使用时将从最上面一层一层地拿取下面我们先给出栈结构的基本操作初始化栈入栈出栈获取栈顶元素内容判断栈是否为栈的顺序存储结构及其基本运算的实现栈类定义基本操作算法初始化栈初始化栈将栈置入栈将元素压入到栈中如果尚未达到栈满则将压入栈中并使栈顶指针增
12、栈上溢出栈将栈中的栈顶元素出栈如果栈非空则返回栈顶元素并使栈顶指针减栈下溢获取栈顶元素内容获取栈顶元Push(&S,ch);/将输入的每个字符入栈 while(!StackEmpty(S)/依次退栈并输出退出的字符 Pop(&S,&ch);putchar(ch);putchar(n);例 3 4：十进制数值转换成二进制 使用展转相除法将一个十进制数值转换成二进制数值。即用该十进制数值除以 2，并保留 其余数；重复此操作，直到该十进制数值为 0 为止。最后将所有的余数反向输出就是所对应的二进制数值。比如：(692)10=(1010110100)2，其展转相除的过程如图所示：下面给出解决这个问题的
13、完整算法。void Decimal _ Binary()STACK S;/定义栈结构 S InitStack(&S);/初始化栈 S scanf(%d,data);/输入十进制正整数 while(data)Push(&S,data%2);/余数入栈 data/=2;/被除数 data 整除以 2，得到新的被除数 while(!StackEmpty(S)/依次从栈中弹出每一个余数，并输出之 Pop(&S,&data);printf(%d,data);例 3 5：检验表达式中的括号匹配情况 假设在一个算术表达式中，可以包含三种括号：圆括号 (和)，方括号 和 和花括号 和 ，并且这三种括号可以按任
14、意的次序嵌套使用。比如，.(.).。现在需要设计一个算法，用来检验在输入的算术表达式中所使用括号的合法性。算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以 嵌套，但不能出现交叉情况。我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中 弹出左括号，检验匹配情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。(1)当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；(2)从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；(3)算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于
15、右括号。下面是解决这个问题的完整算法。typedef char Elemtype;int Check()学时上机学时重点难点栈的存储结构及其基本操作队列存储结构及其基本操作栈栈的定义栈是一种特殊的线性表其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行如下所示结论后进先出简称为线性表例家里吃饭最下面的那只碗例在建筑工地上使用的砖块从底往上一层一层地码放在使用时将从最上面一层一层地拿取下面我们先给出栈结构的基本操作初始化栈入栈出栈获取栈顶元素内容判断栈是否为栈的顺序存储结构及其基本运算的实现栈类定义基本操作算法初始化栈初始化栈将栈置入栈将元素压入到栈中如果尚未达到栈满则将压入栈中并使
16、栈顶指针增栈上溢出栈将栈中的栈顶元素出栈如果栈非空则返回栈顶元素并使栈顶指针减栈下溢获取栈顶元素内容获取栈顶元STACK S;/定义栈结构 S char ch;InitStack(&S);/初始化栈 S while(ch=getchar()!=n)/以字符序列的形式输入表达式 switch(ch)case(ch=(|ch=|ch=):Push(&S,ch);break;/遇左括号入栈/在遇到右括号时，分别检测匹配情况 case(ch=):if(StackEmpty(S)retrun FALSE;else Pop(&S,&ch);if(ch!=()return FALSE;break;case(
17、ch=):if(StackEmpty(S)retrun FALSE;else Pop(&S,&ch);if(ch!=)return FALSE;break;case(ch=):if(StackEmpty(S)retrun FALSE;else Pop(&S,&ch);if(ch!=)return FALSE;break;default:break;if(StackEmpty(S)return TRUE;else return FALSE;3.2 队列 3.2.1 队列的定义 插入端和删除端都是浮动的。通常我们将插入端称为队尾，用一个 队尾指针 指示；而删除端被称为队头，学时上机学时重点难点栈的
18、存储结构及其基本操作队列存储结构及其基本操作栈栈的定义栈是一种特殊的线性表其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行如下所示结论后进先出简称为线性表例家里吃饭最下面的那只碗例在建筑工地上使用的砖块从底往上一层一层地码放在使用时将从最上面一层一层地拿取下面我们先给出栈结构的基本操作初始化栈入栈出栈获取栈顶元素内容判断栈是否为栈的顺序存储结构及其基本运算的实现栈类定义基本操作算法初始化栈初始化栈将栈置入栈将元素压入到栈中如果尚未达到栈满则将压入栈中并使栈顶指针增栈上溢出栈将栈中的栈顶元素出栈如果栈非空则返回栈顶元素并使栈顶指针减栈下溢获取栈顶元素内容获取栈顶元用一个队头指针 指
19、示。结论：先进先出(First In First Out)，简称为 FIFO 线性表。例 3-6：到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。例 3-7：乘坐公共汽车，应该在车站排队，车来后，按顺序上车。例 3-8：在 Windows这类多任务的操作系统环境中，每个应用程序响应一系列的 消息，像用户点击鼠标；拖动窗口这些操作都会导致向应用程序发送消息。为此，系统将为每个应用程序创建一个队列，用来存放 发送给该应用程序的所有消息，应用程序的处理过程就是不断地从队列中读取消息，并依次给予响应。下面我们给出队列结构的基本操作：(1)初始化队列 InitQueue(Q)(2)入队 EnQu
20、eue(Q,elem)(3)出队 DeQueue(Q,elem)(4)获取队头元素内容 GetFront(Q,elem)(5)判断队列是否为空 QueueEmpty(Q)3.2.2 队列的顺序存储结构及其基本运算的实现 队列的顺序存储结构如下图所示：0 1 2 n-2 n-1 a1 a2 a3 an-1 an 问题 1：当队列空时，对头和队尾指针都为 1，队列将变成下图所示状态：0 1 2 n-2 n-1 问题 2：假溢出，即，在添加数据时，可能出现没有剩余空间而实际队列又不满的状况。如：0 1 2 3 4 5 6 7 a5 a6 a7 a8 front rear 解决办法：将存储队列元素的一
21、维数组首尾相接形成一个环状，即循环队列，如下图：front学时上机学时重点难点栈的存储结构及其基本操作队列存储结构及其基本操作栈栈的定义栈是一种特殊的线性表其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行如下所示结论后进先出简称为线性表例家里吃饭最下面的那只碗例在建筑工地上使用的砖块从底往上一层一层地码放在使用时将从最上面一层一层地拿取下面我们先给出栈结构的基本操作初始化栈入栈出栈获取栈顶元素内容判断栈是否为栈的顺序存储结构及其基本运算的实现栈类定义基本操作算法初始化栈初始化栈将栈置入栈将元素压入到栈中如果尚未达到栈满则将压入栈中并使栈顶指针增栈上溢出栈将栈中的栈顶元素出栈如果栈
22、非空则返回栈顶元素并使栈顶指针减栈下溢获取栈顶元素内容获取栈顶元假设为队列开辟的数组单元数目为 MAX_QUEU，E在 C语言中，它的下标在 0MAX_QUEUE-之1 间，若增加队 头或队尾指针，可以利用取模运算(一个整数数值整除以另一个整数数值的余数)实现。如下所示：front=(front+1)%MAX_QUEUE；rear=(rear+1)%MAX_QUEUE；当 front 或 rear 为 MAXQUEUE-时1，上述两个公式计算的结果就为 0。这样，就使得指针自动由后面转到 前面，形成循环的效果。队空和队满的标志问题：队列变为空，队头和队尾指针相等。QUEUE;各项基本操作算法。
23、(1)初始化队列 Q void InitQueue(QUEUE*Q)Q-front=-1;Q-rear=-1;(2)入队 void EnQueue(QUEUE*Q,Elemtype elem)if(Q-rear+1)%MAX_QUEUE=Q-front)exit(OVERFLOW);else Q-rear=(Q-reasr+1)%MAX_QUEUE;解决方法：一是为队列另设一个标志，用来区分队列是 为队满，此时，队尾指针只差一步追上队头指针，即：类型定义：#define MAX_QUEUE 10/队列的最大数据元素数目 typedef struct queue/空 还是满；二是当数组只剩下一个
24、单元时就认(rear+1)%MAX_QUEUE=front。Elemtype elemMAX_QUEUE;/int front,rear;/队头指针、队尾指针 假设当数组只剩下一个单元时认为队满 存放队列中数据元素的存储单学时上机学时重点难点栈的存储结构及其基本操作队列存储结构及其基本操作栈栈的定义栈是一种特殊的线性表其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行如下所示结论后进先出简称为线性表例家里吃饭最下面的那只碗例在建筑工地上使用的砖块从底往上一层一层地码放在使用时将从最上面一层一层地拿取下面我们先给出栈结构的基本操作初始化栈入栈出栈获取栈顶元素内容判断栈是否为栈的顺序存
25、储结构及其基本运算的实现栈类定义基本操作算法初始化栈初始化栈将栈置入栈将元素压入到栈中如果尚未达到栈满则将压入栈中并使栈顶指针增栈上溢出栈将栈中的栈顶元素出栈如果栈非空则返回栈顶元素并使栈顶指针减栈下溢获取栈顶元素内容获取栈顶元Q-elemQ-rear=elem;(3)出队 void DeQueue(QUEUE*Q,Elemtype*elem)if(QueueEmpty(*Q)exit(Queue is empty.);else Q-front=(Q-front+1)%MAX_QUEUE;*elem=Q-elemQ-front;(4)获取队头元素内容 void GetFront(QUEUE Q
26、,Elemtype*elem)if(QueueEmpty(Q)exit(Queue is empty.);else*elem=Q.elem(Q.front+1)%MAX_QUEUE;(5)判断队列 Q是否为空 int QueueEmpty(Queue Q)if(Q.front=Q.rear)return TRUE;else return FALSE;3.2.3 队列的链式存储结构及其基本运算的实现 在用链式结构存储队列时，需要设置队头指针和队尾指针，以便指示队头结点和队尾结点 Queue;基本运算：链式存储的队列的一般形式 结点结构定义如下：typedef struct node /*队列结点
27、类型定义*/int data;struct node*next;LinkQueue;typedef struct /*队列头结点类型定义*/LinkQueue*front;/*队列的队首指针*/LinkQueue*rear;/*队列的队尾指针*/学时上机学时重点难点栈的存储结构及其基本操作队列存储结构及其基本操作栈栈的定义栈是一种特殊的线性表其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行如下所示结论后进先出简称为线性表例家里吃饭最下面的那只碗例在建筑工地上使用的砖块从底往上一层一层地码放在使用时将从最上面一层一层地拿取下面我们先给出栈结构的基本操作初始化栈入栈出栈获取栈顶元素内
28、容判断栈是否为栈的顺序存储结构及其基本运算的实现栈类定义基本操作算法初始化栈初始化栈将栈置入栈将元素压入到栈中如果尚未达到栈满则将压入栈中并使栈顶指针增栈上溢出栈将栈中的栈顶元素出栈如果栈非空则返回栈顶元素并使栈顶指针减栈下溢获取栈顶元素内容获取栈顶元(1)初始化 void InitQueue(Queue*Q)/*初始化队列，生成一个带哨兵的空队列*/Q-front=(LinkQueue*)malloc(sizeof(LinkQueue);Q-front-next=NULL;Q-rear=Q-front;(2)判空 bool IsEmpty(Queue Q)/*判断队列是否为空。如果队列为空，
29、返回 true，否则返回 false*/if(Q.front=Q.rear)return true;else return false;(3)进队 void EnQueue(Queue*Q,int x)/*将元素 x 压入到队列 Q 中，先申请结点再将其入队*/Q-rear-next=(LinkQueue*)malloc(sizeof(LinkQueue);Q-rear=Q-rear-next;Q-rear-data=x;Q-rear-next=NULL;(4)出队 int DeQueue(Queue*Q)/*将队列 Q 中的队首元素出队*/LinkQueue*p;int data;if(!I
30、sEmpty(*Q)/*如果队列非空，则返回队首元素*/p=Q-front-next;Q-front-next=p-next;/*当将队列中的一个元素删除后，指针 rear 就悬浮起来了，需要将其调整到正确的状态，即必须使其等于 front*/if(p-next=NULL)Q-rear=Q-front;data=p-data;free(p);return data;3.2.4 队列的应用举例 例 3-9：汽车加油站。随着城市里汽车数量的急速增长，汽车加油站也渐渐多了起来。通常汽车加油站的结构基本上是：入口和 出口为单行道，加油车道可能有若干条。每辆车加油都要经过三段路程，第一段是在入口处排队等
31、候进入 加油学时上机学时重点难点栈的存储结构及其基本操作队列存储结构及其基本操作栈栈的定义栈是一种特殊的线性表其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行如下所示结论后进先出简称为线性表例家里吃饭最下面的那只碗例在建筑工地上使用的砖块从底往上一层一层地码放在使用时将从最上面一层一层地拿取下面我们先给出栈结构的基本操作初始化栈入栈出栈获取栈顶元素内容判断栈是否为栈的顺序存储结构及其基本运算的实现栈类定义基本操作算法初始化栈初始化栈将栈置入栈将元素压入到栈中如果尚未达到栈满则将压入栈中并使栈顶指针增栈上溢出栈将栈中的栈顶元素出栈如果栈非空则返回栈顶元素并使栈顶指针减栈下溢获取栈顶
32、元素内容获取栈顶元车道；第二段是在加油车道排队等候加油；第三段是进入出口处排队等候离开。实际上，这三段都是 队列结构。若用算法模拟这个过程，就需要设置加油车道数加 2 个队列。例 3-10：模拟打印机缓冲区。在主机将数据输出到打印机时，会出现主机速度与打印机的打印速度不匹配的问题。这时主机就要停下来 等待打印机。显然，这样会降低主机的使用效率。为此人们设想了一种办法：为打印机设置一个打印数据 缓冲区，当主机需要打印数据时，先将数据依次写入这个缓冲区，写满后主机转去做其他的事情，而打印 机就从缓冲区中按照先进先出的原则依次读取数据并打印，这样做即保证了打印数据的正确性，又提高了 主机的使用效率。
33、由此可见，打印机缓冲区实际上就是一个队列结构。例 3-11：CPU 分时系统 在一个带有多个终端的计算机系统中，同时有多个用户需要使用 CPU 运行各自的应用程序，它们分别通过 各自的终端向操作系统提出使用 CPU 的请求，操作系统通常按照每个请求在时间上的先后顺序，将它们排 成一个队列，每次把 CPU 分配给当前队首的请求用户，即将该用户的应用程序投入运行，当该程序运行完 毕或用完规定的时间片后，操作系统再将 CPU 分配给新的队首请求用户，这样即可以满足每个用户的请求，又可以使 CPU 正常工作。学时上机学时重点难点栈的存储结构及其基本操作队列存储结构及其基本操作栈栈的定义栈是一种特殊的线性表其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行如下所示结论后进先出简称为线性表例家里吃饭最下面的那只碗例在建筑工地上使用的砖块从底往上一层一层地码放在使用时将从最上面一层一层地拿取下面我们先给出栈结构的基本操作初始化栈入栈出栈获取栈顶元素内容判断栈是否为栈的顺序存储结构及其基本运算的实现栈类定义基本操作算法初始化栈初始化栈将栈置入栈将元素压入到栈中如果尚未达到栈满则将压入栈中并使栈顶指针增栈上溢出栈将栈中的栈顶元素出栈如果栈非空则返回栈顶元素并使栈顶指针减栈下溢获取栈顶元素内容获取栈顶元