网站重新解析,wordpress 背景特效插件,网站后台首页模板,北京到安阳的火车票一、介绍
栈和队列是限定插入和删除只能在表的“端点”进行的线性表#xff0c;是线性表的子集#xff0c;是插入和删除位置受限的线性表。
#xff08;操作受限的线性表#xff09; 二、栈
1#xff09;概念#xff1a;
栈(stack)是一个特殊的线性表#xff0c;是限…一、介绍
栈和队列是限定插入和删除只能在表的“端点”进行的线性表是线性表的子集是插入和删除位置受限的线性表。
操作受限的线性表 二、栈
1概念
栈(stack)是一个特殊的线性表是限仅在一端通常是表尾进行插入和删除操作的线性表。
表尾(即an端)称为栈顶Top;
表头(即a1端)称为栈底Base插入元素到栈顶即表尾的操作称为入栈。
从栈顶即表尾删除最后一个元素的操作称为出栈。
“入” 压入 PUSH(x)“出” 弹出 POP(y)2特点先进后出
3示意图 4常见问题
数制转换 表达式求值
括号匹配的检验 八皇后问题
行编辑程序 函数调用
迷宫求解 递归调用的实现5栈的表示
1、栈的抽象数据类型的类型定义 2、相关操作 6顺序栈的表示和实现
1、存储方式
同一般线性表的顺序存储结构完全相同利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。栈底一般在低地址端。
附设top指针指示栈顶元素在顺序栈中的位置。另设base指针指示栈底元素在顺序栈中的位置。
但是为了方便操作通常top 指示真正的栈顶元素之上的下标地址
另外用stacksize表示栈可使用的最大容量。
2、栈空标志
base top 是栈空标志3、栈满标志
top - base stacksize4、栈满处理方法
报错返回操作系统。分配更大的操作空间作为栈的存储空间将原有的内容移入新栈。
使用数组作为顺序栈存储方式的特点简单方便、但易产生溢出(数组大小固定)
**上溢(overflow)**栈已经满又要压入元素**下溢(underflow)**栈已经空还要弹出元素
注上溢是一种错误使问题的处理无法进行;而下溢一般认为是一种结束条件即问题处理结束。
5、定义顺序栈结构
#include iostream
#include cstdlibusing namespace std;#define OK 1 //成功标识
#define ERROR 0 //失败标识#define MAXSIZE 100 //存储空间的初始分配量typedef int Status; //Status是函数的类型其值是函数结果状态代码如OK等typedef int SElemType; //ElemType的类型根据实际情况而定这里假定为inttypedef struct{SElemType *base; // 栈底指针SElemType *top; // 栈顶指针int stackSize; // 栈可用最大容量
}SqStack;6、顺序栈的初始化 // 顺序栈的初始化
Status InitStack(SqStack* S) { // 构造一个空栈S-base new SElemType[MAXSIZE]; // 或S.base (SElemType*)malloc(MAXSIZE*sizeof(SElemType))if (!S-base) return ERROR; // 内存分配失败S-top S-base; // 栈顶指针等于栈底指针S-stackSize 0; return OK;
}7、顺序栈的清空与销毁
// 清空栈
Status ClearStack(SqStack *S) {if (S-base) { // 如果存在这个栈S-top S-base;S-stackSize 0; // 将栈顶等于栈底就为空 }return OK;
}// 销毁栈
Status DestroyStack(SqStack* S) {if (S-base) {delete[] S-base;S-base nullptr;S-top nullptr;S-stackSize 0;}return OK;
}8、求顺序栈长度和判断是否为空
// 判断顺序栈是否为空
Status StackEmpty(SqStack S) {//若栈为空返回TRUE;否则返回FALSEif (S.top S.base) {return OK;}else {return ERROR;}
}// 求顺序栈长度
int StackLength(SqStack S) {return S.top - S.base;
}9、顺序栈的入栈
// 入栈操作
Status Push(SqStack* S, SElemType e) {if (S-top - S-base MAXSIZE) return ERROR; // 栈满*S-top e;S-top;S-stackSize;return OK;
}10、顺序栈的出栈
// 出栈操作
Status Pop(SqStack* S, SElemType* e) {if (S-top S-base) return ERROR; // 栈空S-top--;*e *S-top;S-stackSize--;return OK;
}11、获取栈顶元素
// 获取栈顶元素
Status GetTop(SqStack S, SElemType* e) {if (S.top S.base) return ERROR; // 栈空*e *(S.top - 1);return OK;
}12、运行测试
// 打印栈内元素
void PrintStack(SqStack S) {if (S.top S.base) {cout 栈为空 std::endl;return;}cout 栈内元素: ;for (SElemType* p S.base; p S.top; p) {cout *p ;}cout endl;
}int main() {SqStack S;SElemType e;// 初始化栈if (InitStack(S) OK) {cout 栈初始化成功 endl;}else {cout 栈初始化失败 endl;return -1;}// 入栈操作if (Push(S, 1) OK Push(S, 2) OK Push(S, 3) OK) {cout 入栈成功 endl;PrintStack(S); // 打印栈内元素}else {cout 入栈失败 endl;}// 获取栈顶元素if (GetTop(S, e) OK) {cout 栈顶元素: e endl;}else {cout 栈为空 endl;}// 出栈操作while (Pop(S, e) OK) {cout 出栈元素: e std;PrintStack(S); // 打印栈内元素}// 判断栈是否为空if (StackEmpty(S) OK) {cout 栈为空 endl;}else {cout 栈非空 endl;}// 获取栈的长度cout 栈的长度: StackLength(S) endl;// 清空栈if (ClearStack(S) OK) {cout 栈已清空 endl;}else {cout 清空栈失败 endl;}// 销毁栈if (DestroyStack(S) OK) {cout 栈已销毁 endl;}else {cout 销毁栈失败 endl;}return 0;
}13、总体代码
#include iostream
#include cstdlibusing namespace std;#define OK 1 //成功标识
#define ERROR 0 //失败标识#define MAXSIZE 100 //存储空间的初始分配量typedef int Status; //Status是函数的类型其值是函数结果状态代码如OK等typedef int SElemType; //ElemType的类型根据实际情况而定这里假定为inttypedef struct{SElemType *base; // 栈底指针SElemType *top; // 栈顶指针int stackSize; // 栈可用最大容量
}SqStack;// 顺序栈的初始化
Status InitStack(SqStack* S) { // 构造一个空栈S-base new SElemType[MAXSIZE]; // 或S.base (SElemType*)malloc(MAXSIZE*sizeof(SElemType))if (!S-base) return ERROR; // 内存分配失败S-top S-base; // 栈顶指针等于栈底指针S-stackSize 0; return OK;
}// 判断顺序栈是否为空
Status StackEmpty(SqStack S) {//若栈为空返回TRUE;否则返回FALSEif (S.top S.base) {return OK;}else {return ERROR;}
}// 求顺序栈长度
int StackLength(SqStack S) {return S.top - S.base;
}// 清空栈
Status ClearStack(SqStack *S) {if (S-base) { // 如果存在这个栈S-top S-base;S-stackSize 0; // 将栈顶等于栈底就为空 }return OK;
}// 销毁栈
Status DestroyStack(SqStack* S) {if (S-base) {delete[] S-base;S-base nullptr;S-top nullptr;S-stackSize 0;}return OK;
}// 入栈操作
Status Push(SqStack* S, SElemType e) {if (S-top - S-base MAXSIZE) return ERROR; // 栈满*S-top e;S-top;S-stackSize;return OK;
}// 出栈操作
Status Pop(SqStack* S, SElemType* e) {if (S-top S-base) return ERROR; // 栈空S-top--;*e *S-top;S-stackSize--;return OK;
}// 获取栈顶元素
Status GetTop(SqStack S, SElemType* e) {if (S.top S.base) return ERROR; // 栈空*e *(S.top - 1);return OK;
}// 打印栈内元素
void PrintStack(SqStack S) {if (S.top S.base) {cout 栈为空 std::endl;return;}cout 栈内元素: ;for (SElemType* p S.base; p S.top; p) {cout *p ;}cout endl;
}int main() {SqStack S;SElemType e;// 初始化栈if (InitStack(S) OK) {cout 栈初始化成功 endl;}else {cout 栈初始化失败 endl;return -1;}// 入栈操作if (Push(S, 1) OK Push(S, 2) OK Push(S, 3) OK) {cout 入栈成功 endl;PrintStack(S); // 打印栈内元素}else {cout 入栈失败 endl;}// 获取栈顶元素if (GetTop(S, e) OK) {cout 栈顶元素: e endl;}else {cout 栈为空 endl;}// 出栈操作while (Pop(S, e) OK) {std::cout 出栈元素: e std::endl;PrintStack(S); // 打印栈内元素}// 判断栈是否为空if (StackEmpty(S) OK) {cout 栈为空 endl;}else {cout 栈非空 endl;}// 获取栈的长度cout 栈的长度: StackLength(S) endl;// 清空栈if (ClearStack(S) OK) {cout 栈已清空 endl;}else {cout 清空栈失败 endl;}// 销毁栈if (DestroyStack(S) OK) {cout 栈已销毁 endl;}else {cout 销毁栈失败 endl;}return 0;
}14、运行结果 7链栈的表示和实现
1、存储方式
链栈是运算受限的单链表只能正在链表头部进行操作 链表的头指针就是栈顶 不需要头结点 基本不存在栈满的情况 空栈相当于头指针指向空 插入和删除仅在栈顶处执行
2、定义链栈结构
#include iostream
using namespace std;// 函数结果状态码
#define OK 1 //成功标识
#define ERROR 0 //失败标识#define MAXSIZE 100 //线性表存储空间的初始分配量typedef int Status; //Status是函数的类型其值是函数结果状态代码如OK等typedef int SElemType; //ElemType的类型根据实际情况而定这里假定为inttypedef struct StackNode {SElemType data;struct StackNode* next;
}StackNode, *LinkStack;3、链栈的初始化
// 初始化链栈
Status InitStack(LinkStack S) {S NULL;return OK;
}4、链栈的清空与销毁
// 销毁链栈
void DestroyStack(LinkStack S) {LinkStack p;while (S ! NULL) {p S;S S-next;delete p;}
}// 清空链栈
void ClearStack(LinkStack S) {DestroyStack(S);InitStack(S);
}5、求链栈长度和判断链栈是否为空
// 获取链栈的长度
int StackLength(LinkStack S) {int length 0;LinkStack p S;while (p ! NULL) {length;p p-next;}return length;
}// 判断链栈是否为空
Status StackEmpty(LinkStack S) {if (S NULL) {return OK;}else {return ERROR;}
}6、链栈的入栈 // 入栈操作
Status Push(LinkStack S, SElemType e) {LinkStack p;p new StackNode; // 生成一个新节点if (p NULL) return ERROR; // 内存分配失败p-data e; // 将新节点数据域置为ep-next S; // 将新节点插入栈顶S p; // 修改栈顶指针return OK;
}7、链栈的出栈 // 出栈操作
Status Pop(LinkStack S, SElemType e) {if (S NULL) return ERROR; // 栈空LinkStack p S;;e p-data;S p-next;delete p;return OK;
}8、获取栈顶元素
// 获取栈顶元素
Status GetTop(LinkStack S, SElemType e) {if (S NULL) return ERROR; // 栈空e S-data;return OK;
}
9、运行测试
// 打印链栈内元素
void PrintStack(LinkStack S) {if (S NULL) {cout 栈为空 endl;return;}cout 栈内元素: ;LinkStack p S;while (p ! NULL) {cout p-data ;p p-next;}cout endl;
}int main() {LinkStack stack;InitStack(stack);int choice, value;bool running true;while (running) {cout 1. 入栈\n2. 出栈\n3. 获取栈顶元素\n4. 判断链栈是否为空\n5. 清空链栈\n6. 获取链栈长度\n7. 打印栈内元素\n8. 退出\n;cout 请输入你的选择: ;cin choice;switch (choice) {case 1:cout 请输入你要入栈的元素: ;cin value;if (Push(stack, value) OK) {cout 入栈成功 endl;}else {cout 入栈失败 endl;}PrintStack(stack);break;case 2:if (Pop(stack, value) OK) {cout 出栈的元素为: value endl;}else {cout 链栈为空 endl;}PrintStack(stack);break;case 3:if (GetTop(stack, value) OK) {cout 栈顶元素为: value endl;}else {cout 链栈为空 endl;}break;case 4:if (StackEmpty(stack) OK) {cout 链栈为空 endl;}else {cout 链栈不为空 endl;}break;case 5:ClearStack(stack);cout 清空链栈 endl;PrintStack(stack);break;case 6:cout 链栈的长度为: StackLength(stack) endl;break;case 7:PrintStack(stack);break;case 8:running false;break;default:cout Invalid choice endl;break;}}DestroyStack(stack);return 0;
}10、总体代码
#include iostream
using namespace std;// 函数结果状态码
#define OK 1 //成功标识
#define ERROR 0 //失败标识#define MAXSIZE 100 //线性表存储空间的初始分配量typedef int Status; //Status是函数的类型其值是函数结果状态代码如OK等typedef int SElemType; //ElemType的类型根据实际情况而定这里假定为inttypedef struct StackNode {SElemType data;struct StackNode* next;
}StackNode, *LinkStack;// 初始化链栈
Status InitStack(LinkStack S) {S NULL;return OK;
}// 销毁链栈
void DestroyStack(LinkStack S) {LinkStack p;while (S ! NULL) {p S;S S-next;delete p;}
}// 入栈操作
Status Push(LinkStack S, SElemType e) {LinkStack p;p new StackNode; // 生成一个新节点if (p NULL) return ERROR; // 内存分配失败p-data e; // 将新节点数据域置为ep-next S; // 将新节点插入栈顶S p; // 修改栈顶指针return OK;
}// 出栈操作
Status Pop(LinkStack S, SElemType e) {if (S NULL) return ERROR; // 栈空LinkStack p S;;e p-data;S p-next;delete p;return OK;
}// 获取栈顶元素
Status GetTop(LinkStack S, SElemType e) {if (S NULL) return ERROR; // 栈空e S-data;return OK;
}// 判断链栈是否为空
Status StackEmpty(LinkStack S) {if (S NULL) {return OK;}else {return ERROR;}
}// 清空链栈
void ClearStack(LinkStack S) {DestroyStack(S);InitStack(S);
}// 获取链栈的长度
int StackLength(LinkStack S) {int length 0;LinkStack p S;while (p ! NULL) {length;p p-next;}return length;
}// 打印链栈内元素
void PrintStack(LinkStack S) {if (S NULL) {cout 栈为空 endl;return;}cout 栈内元素: ;LinkStack p S;while (p ! NULL) {cout p-data ;p p-next;}cout endl;
}int main() {LinkStack stack;InitStack(stack);int choice, value;bool running true;while (running) {cout 1. 入栈\n2. 出栈\n3. 获取栈顶元素\n4. 判断链栈是否为空\n5. 清空链栈\n6. 获取链栈长度\n7. 打印栈内元素\n8. 退出\n;cout 请输入你的选择: ;cin choice;switch (choice) {case 1:cout 请输入你要入栈的元素: ;cin value;if (Push(stack, value) OK) {cout 入栈成功 endl;}else {cout 入栈失败 endl;}PrintStack(stack);break;case 2:if (Pop(stack, value) OK) {cout 出栈的元素为: value endl;}else {cout 链栈为空 endl;}PrintStack(stack);break;case 3:if (GetTop(stack, value) OK) {cout 栈顶元素为: value endl;}else {cout 链栈为空 endl;}break;case 4:if (StackEmpty(stack) OK) {cout 链栈为空 endl;}else {cout 链栈不为空 endl;}break;case 5:ClearStack(stack);cout 清空链栈 endl;PrintStack(stack);break;case 6:cout 链栈的长度为: StackLength(stack) endl;break;case 7:PrintStack(stack);break;case 8:running false;break;default:cout Invalid choice endl;break;}}DestroyStack(stack);return 0;
}11、运行结果 三、栈与递归
1递归的定义
若一个对象部分地包含它自己或用它自己给自己定义则称这个对象是递归的
若一个过程直接地或间接地调用自己则称这个过程是递归的过程。
例如递归求n的阶乘
long(Facty( long n ) {if(n 0) return 1;else return n * Fact(n-1);
}以下三种情况常常用到递归方法
递归定义的数学函数具有递归特性的数据结构可递归求解的问题
2递归问题——用分治法求解
分治法对于一个较为复杂的问题能够分解成几个相对简单的且解法相同或类似的子问题来求解
必备的三个条件
能将一个问题转变成、个新问题而新问题与原问题的解法相同或类同不同的仅是处理的对象且这些处理对象是变化有规律的可以通过上述转化而使问题简化必须有一个明确的递归出口重或称递归的边界
3分治法求递归问题算法的一般形式
void p (参数表) {if (递归结束条件) 可直接求解步骤; ——基本项else p (较小的参数); ——归纳项
}例如:
long Fact ( long n){if(n 0) return 1; // 基本项else return n * Fact(n - 1); // 归纳项
}4函数调用过程
调用前,系统完成:
(1)将实参,返回地址等传递给被调用函数
(2)为被调用函数的局部变量分配存储区(3)将控制转移到被调用函数的入口
调用后,系统完成:
(1)保存被调用函数的计算结果
(2)释放被调用函数的数据区(3)依照被调用函数保存的返回地址将控制转移到调用函数
当多个函数构成嵌套调用
遵循后调用先返回
例如 int main(void){...y fact(3);...
}
double fact(int n) {...Z mypow(3.5, 2);...
}
double mypow(double x, in n) {...
}5递归的优缺点
优点结构清晰程序易读。
缺点每次调用要生成工作记录保存状态信息入栈;返回时要出栈恢复状态信息。时间开销大。
6递归 - 非递归
方法1尾递归、单向递归→循环结构 方法2自用栈模拟系统的运行时栈
递归程序在执行时需要系统提供栈来实现仿照递归算法执行过程中递归工作栈的状态变化可写出相应的非递归程序改写后的非递归算法与原来的递归算法相比结构不够清晰可读性较差有的还需要经过一系列优化
四、队列
1概念
队列(queue)是一种先进先出Frist In Frist Out ----FIFO的线性表。在表一端插入(表尾)在另一端(表头)删除。 2特点先进先出
3示意图 4常见问题
脱机打印输出:按申请的先后顺序依次输出。
多用户系统中多个用户排成队分时地循环使用CPU和主存。
按用户的优先级排成多个队每个优先级一个队列。
实时控制系统中信号按接收的先后顺序依次处理。
网络电文传输按到达的时间先后顺序依次进行。5队列的表示
队列(Queue)是仅在 表尾 进行插入操作在 表头 进行删除操作的线性表。表尾即an端称为队尾表头即a1端称为队头。它是一种先进先出( FIFO )的线性表。
例如队列 Q (a1, a2 a3 .. an-1. an)插入元素称为入队删除元素称为出队队列的存储结构为链队或顺序队(常用循环顺序队) 6循环顺序队的表示与实现
1、真溢出与假溢出 真溢出是数组没有空位再入新的元素了。
假溢出是数组中不按原来顺序依次放入以按其他顺序还有空位可以放入新的元素。 解决假上溢的方法 2、解决假上溢方法——引入循环队列
base[0] 接在base[MAXQSIZE - 1] 之后若rear 1 M则令rear 0实现方法利用模(modC语言中:%)运算。
因为如上图所示
当在 0 位置时0 1% 6 1当在 1 位置时1 1% 6 2…当在 5 位置时数组满时5 1% 6 0 回到 0 位置
所以
插入元素Q.base[Q.rear] x;Q.rear (Q.rear 1) % MAXQSIZE // 达到最大值等于0,回到原点删除元素:x Q.base[s.front];Q.front (Q.front 1) % MAXQSIZE3、解决队空队满如何判定的方法 4、定义循环顺序表队列结构
#include iostream
#include stdexceptusing namespace std;
#define MAXSIZE 100 // 队列的最大容量
#define OK 1 //成功标识
#define ERROR 0 //失败标识typedef int QElemType; // 队列元素的类型这里假定为int
typedef int Status;typedef struct {QElemType data[MAXSIZE]; // 存储队列元素的数组// QElemType *base; // 动态分配存储空间int front; // 头指针int rear; // 尾指针
} SqQueue;
5、循环顺序表队列的初始化
// 初始化队列
Status InitQueue(SqQueue Q) {// Q.base new QElemType[MAXQSIZE] // 分配数组空间// Q.base (QElemType*) malloc (MAXQSIZE *sizeof(QElemType)); // 动态分配空间// if (!Q.base) exit(OVERFLOW); // 存储分配失败Q.front 0; // 头指针Q.rear 0; // 尾指针return OK;
}6、循环顺序表队列的清空与销毁
// 销毁队列
Status DestroyQueue(SqQueue Q) {// 顺序表实现的队列不需要显式释放内存Q.front 0;Q.rear 0;return OK;
}// 清空队列
Status ClearQueue(SqQueue Q) {Q.front 0;Q.rear 0;return OK;
}7、求循环顺序表队列长度和判断循环顺序表队列是否为空
// 获取队列的长度
int QueueLength(SqQueue Q) {return (Q.rear - Q.front MAXSIZE) % MAXSIZE;
}// 判断队列是否为空
bool QueueEmpty(SqQueue Q) {return Q.front Q.rear;
}8、循环顺序表队列的入队
// 入队操作
Status EnQueue(SqQueue Q, QElemType e) {if ((Q.rear 1) % MAXSIZE Q.front) { // 队列满return ERROR;}Q.data[Q.rear] e;Q.rear (Q.rear 1) % MAXSIZE; // 循环队列 队尾 1return OK;
}9、循环顺序表队列的出队
// 出队操作
Status DeQueue(SqQueue Q, QElemType e) {if (Q.front Q.rear) { // 队列空return ERROR;}e Q.data[Q.front];Q.front (Q.front 1) % MAXSIZE; // 循环队列 队头 1return OK;
}10、获取循环顺序表队列顶元素
// 获取队列头部元素
Status GetHead(SqQueue Q, QElemType e) {if (Q.front Q.rear) { // 队列空return ERROR;}e Q.data[Q.front];return OK;
}11、运行测试
// 打印队列内元素
void PrintQueue(SqQueue Q) {if (Q.front Q.rear) {cout 队列为空 endl;return;}cout 队列为: ;int i Q.front;while (i ! Q.rear) {cout Q.data[i] ;i (i 1) % MAXSIZE;}cout endl;
}int main() {SqQueue queue;InitQueue(queue);int choice, value;bool running true;while (running) {cout 1. 入队\n2. 出队\n3. 获得队头元素\n4. 判断队列是否为空\n5. 清空队列\n6. 获得队列长度\n7. 打印队列\n8. 退出\n;cout 请输入你的选择: ;cin choice;switch (choice) {case 1:cout 请输入要入队的元素: ;cin value;if (EnQueue(queue, value) OK) {cout 入队成功 endl;}else {cout 队列已满 endl;}PrintQueue(queue);break;case 2:if (DeQueue(queue, value) OK) {cout 出队的元素: value endl;}else {cout 队列为空 endl;}PrintQueue(queue);break;case 3:if (GetHead(queue, value) OK) {cout 队头元素为: value endl;}else {cout 队列为空 endl;}break;case 4:if (QueueEmpty(queue)) {cout 队列为空 endl;}else {cout 队列不为空 endl;}break;case 5:ClearQueue(queue);cout 队列已清空 endl;PrintQueue(queue);break;case 6:cout 队列长度: QueueLength(queue) endl;break;case 7:PrintQueue(queue);break;case 8:running false;break;default:cout Invalid choice endl;break;}}DestroyQueue(queue);return 0;
}12、总体代码
#include iostream
#include stdexceptusing namespace std;
#define MAXSIZE 100 // 队列的最大容量
#define OK 1 //成功标识
#define ERROR 0 //失败标识typedef int QElemType; // 队列元素的类型这里假定为int
typedef int Status;typedef struct {QElemType data[MAXSIZE]; // 存储队列元素的数组// QElemType *base; // 动态分配存储空间int front; // 头指针int rear; // 尾指针
} SqQueue;// 初始化队列
Status InitQueue(SqQueue Q) {// Q.base new QElemType[MAXQSIZE] // 分配数组空间// Q.base (QElemType*) malloc (MAXQSIZE *sizeof(QElemType)); // 动态分配空间// if (!Q.base) exit(OVERFLOW); // 存储分配失败Q.front 0; // 头指针Q.rear 0; // 尾指针return OK;
}// 销毁队列
Status DestroyQueue(SqQueue Q) {// 顺序表实现的队列不需要显式释放内存Q.front 0;Q.rear 0;return OK;
}// 入队操作
Status EnQueue(SqQueue Q, QElemType e) {if ((Q.rear 1) % MAXSIZE Q.front) { // 队列满return ERROR;}Q.data[Q.rear] e;Q.rear (Q.rear 1) % MAXSIZE; // 循环队列 队尾 1return OK;
}// 出队操作
Status DeQueue(SqQueue Q, QElemType e) {if (Q.front Q.rear) { // 队列空return ERROR;}e Q.data[Q.front];Q.front (Q.front 1) % MAXSIZE; // 循环队列 队头 1return OK;
}// 获取队列头部元素
Status GetHead(SqQueue Q, QElemType e) {if (Q.front Q.rear) { // 队列空return ERROR;}e Q.data[Q.front];return OK;
}// 判断队列是否为空
bool QueueEmpty(SqQueue Q) {return Q.front Q.rear;
}// 清空队列
Status ClearQueue(SqQueue Q) {Q.front 0;Q.rear 0;return OK;
}// 获取队列的长度
int QueueLength(SqQueue Q) {return (Q.rear - Q.front MAXSIZE) % MAXSIZE;
}// 打印队列内元素
void PrintQueue(SqQueue Q) {if (Q.front Q.rear) {cout 队列为空 endl;return;}cout 队列为: ;int i Q.front;while (i ! Q.rear) {cout Q.data[i] ;i (i 1) % MAXSIZE;}cout endl;
}int main() {SqQueue queue;InitQueue(queue);int choice, value;bool running true;while (running) {cout 1. 入队\n2. 出队\n3. 获得队头元素\n4. 判断队列是否为空\n5. 清空队列\n6. 获得队列长度\n7. 打印队列\n8. 退出\n;cout 请输入你的选择: ;cin choice;switch (choice) {case 1:cout 请输入要入队的元素: ;cin value;if (EnQueue(queue, value) OK) {cout 入队成功 endl;}else {cout 队列已满 endl;}PrintQueue(queue);break;case 2:if (DeQueue(queue, value) OK) {cout 出队的元素: value endl;}else {cout 队列为空 endl;}PrintQueue(queue);break;case 3:if (GetHead(queue, value) OK) {cout 队头元素为: value endl;}else {cout 队列为空 endl;}break;case 4:if (QueueEmpty(queue)) {cout 队列为空 endl;}else {cout 队列不为空 endl;}break;case 5:ClearQueue(queue);cout 队列已清空 endl;PrintQueue(queue);break;case 6:cout 队列长度: QueueLength(queue) endl;break;case 7:PrintQueue(queue);break;case 8:running false;break;default:cout Invalid choice endl;break;}}DestroyQueue(queue);return 0;
}13、运行结果 7链队的表示与实现 1、定义链队结构
#include iostream
#include stdexceptusing namespace std;#define OK 1 //成功标识
#define ERROR 0 //失败标识typedef int QElemType; // 队列元素的类型这里假定为int
typedef int Status;typedef struct QueueNode {QElemType data;struct QueueNode* next;
} QueueNode, * QueuePtr;typedef struct {QueuePtr front; // 头指针QueuePtr rear; // 尾指针
} LinkQueue;2、链队的初始化
// 初始化队列
Status InitQueue(LinkQueue Q) {// Q.front Q.rear (QueuePtr)malloc(sizeof(QNode)) // 动态分配内存空间Q.front Q.rear new QueueNode; // 创建头结点if (Q.front NULL) return ERROR; // 内存分配失败Q.front-next NULL;return OK;
}3、链队的清空与销毁
// 销毁队列
Status DestroyQueue(LinkQueue Q) {while (Q.front ! NULL) {QueuePtr p Q.front;Q.front Q.front-next;delete p;}return OK;
}// 清空队列
Status ClearQueue(LinkQueue Q) {DestroyQueue(Q);return InitQueue(Q);
}4、求链队长度和判断链队是否为空
// 获取队列的长度
int QueueLength(LinkQueue Q) {int length 0;QueuePtr p Q.front-next;while (p ! NULL) {length;p p-next;}return length;
}// 判断队列是否为空
bool QueueEmpty(LinkQueue Q) {return Q.front Q.rear;
}5、链队的入队
// 入队操作
Status EnQueue(LinkQueue Q, QElemType e) {QueuePtr s new QueueNode; // 创建新节点if (s NULL) return ERROR; // 内存分配失败s-data e;s-next NULL;Q.rear-next s;Q.rear s;return OK;
}6、链队的出队
// 出队操作
Status DeQueue(LinkQueue Q, QElemType e) {if (Q.front Q.rear) return ERROR; // 队列空QueuePtr p Q.front-next;e p-data;Q.front-next p-next;if (p-next NULL) Q.rear Q.front; // 如果队列变为空更新尾指针delete p;return OK;
}7、获取队顶元素
// 获取队列头部元素
Status GetHead(LinkQueue Q, QElemType e) {if (Q.front Q.rear) return ERROR; // 队列空e Q.front-next-data;return OK;
}8、运行测试
// 打印队列内元素
void PrintQueue(LinkQueue Q) {if (Q.front Q.rear) {cout 队列为空 endl;return;}cout 队列为: ;QueuePtr p Q.front-next;while (p ! NULL) {cout p-data ;p p-next;}cout endl;
}int main() {LinkQueue queue;InitQueue(queue);int choice, value;bool running true;while (running) {cout 1.入队\n2.出队\n3.获得队头元素\n4.判断队列是否为空\n5.清空队列\n6.获得队列长度\n7.打印队列\n8.退出\n;cout 请输入你的选择: ;cin choice;switch (choice) {case 1:cout 请输入要入队的元素: ;cin value;if (EnQueue(queue, value) OK) {cout 入队成功 endl;}else {cout 入队失败 endl;}PrintQueue(queue);break;case 2:if (DeQueue(queue, value) OK) {cout 出队的元素: value endl;}else {cout 队列为空 endl;}PrintQueue(queue);break;case 3:if (GetHead(queue, value) OK) {cout 队头元素为: value endl;}else {cout 队列为空 endl;}break;case 4:if (QueueEmpty(queue)) {cout 队列为空 endl;}else {cout 队列不为空 endl;}break;case 5:ClearQueue(queue);cout 队列已清空 endl;PrintQueue(queue);break;case 6:cout 队列长度为: QueueLength(queue) endl;break;case 7:PrintQueue(queue);break;case 8:running false;break;default:cout Invalid choice endl;break;}}DestroyQueue(queue);return 0;
}9、总体代码
#include iostream
#include stdexceptusing namespace std;#define OK 1 //成功标识
#define ERROR 0 //失败标识typedef int QElemType; // 队列元素的类型这里假定为int
typedef int Status;typedef struct QueueNode {QElemType data;struct QueueNode* next;
} QueueNode, * QueuePtr;typedef struct {QueuePtr front; // 头指针QueuePtr rear; // 尾指针
} LinkQueue;// 初始化队列
Status InitQueue(LinkQueue Q) {// Q.front Q.rear (QueuePtr)malloc(sizeof(QNode)) // 动态分配内存空间Q.front Q.rear new QueueNode; // 创建头结点if (Q.front NULL) return ERROR; // 内存分配失败Q.front-next NULL;return OK;
}// 销毁队列
Status DestroyQueue(LinkQueue Q) {while (Q.front ! NULL) {QueuePtr p Q.front;Q.front Q.front-next;delete p;}return OK;
}// 入队操作
Status EnQueue(LinkQueue Q, QElemType e) {QueuePtr s new QueueNode; // 创建新节点if (s NULL) return ERROR; // 内存分配失败s-data e;s-next NULL;Q.rear-next s;Q.rear s;return OK;
}// 出队操作
Status DeQueue(LinkQueue Q, QElemType e) {if (Q.front Q.rear) return ERROR; // 队列空QueuePtr p Q.front-next;e p-data;Q.front-next p-next;if (p-next NULL) Q.rear Q.front; // 如果队列变为空更新尾指针delete p;return OK;
}// 获取队列头部元素
Status GetHead(LinkQueue Q, QElemType e) {if (Q.front Q.rear) return ERROR; // 队列空e Q.front-next-data;return OK;
}// 判断队列是否为空
bool QueueEmpty(LinkQueue Q) {return Q.front Q.rear;
}// 清空队列
Status ClearQueue(LinkQueue Q) {DestroyQueue(Q);return InitQueue(Q);
}// 获取队列的长度
int QueueLength(LinkQueue Q) {int length 0;QueuePtr p Q.front-next;while (p ! NULL) {length;p p-next;}return length;
}// 打印队列内元素
void PrintQueue(LinkQueue Q) {if (Q.front Q.rear) {cout 队列为空 endl;return;}cout 队列为: ;QueuePtr p Q.front-next;while (p ! NULL) {cout p-data ;p p-next;}cout endl;
}int main() {LinkQueue queue;InitQueue(queue);int choice, value;bool running true;while (running) {cout 1.入队\n2.出队\n3.获得队头元素\n4.判断队列是否为空\n5.清空队列\n6.获得队列长度\n7.打印队列\n8.退出\n;cout 请输入你的选择: ;cin choice;switch (choice) {case 1:cout 请输入要入队的元素: ;cin value;if (EnQueue(queue, value) OK) {cout 入队成功 endl;}else {cout 入队失败 endl;}PrintQueue(queue);break;case 2:if (DeQueue(queue, value) OK) {cout 出队的元素: value endl;}else {cout 队列为空 endl;}PrintQueue(queue);break;case 3:if (GetHead(queue, value) OK) {cout 队头元素为: value endl;}else {cout 队列为空 endl;}break;case 4:if (QueueEmpty(queue)) {cout 队列为空 endl;}else {cout 队列不为空 endl;}break;case 5:ClearQueue(queue);cout 队列已清空 endl;PrintQueue(queue);break;case 6:cout 队列长度为: QueueLength(queue) endl;break;case 7:PrintQueue(queue);break;case 8:running false;break;default:cout Invalid choice endl;break;}}DestroyQueue(queue);return 0;
}10、运行结果
