济宁网站建设专业定制,全网媒体整合推广平台,营销宣传方案,保驾护航装修网目录 1.实现方式说明2.代码实现2.12.1.1 代码12.1.2 代码22.1.3 代码3 2.22.2.1 代码42.2.5 代码52.2.6 代码6 总结 1.实现方式说明
多在选择题中考察
队尾指针#xff08;rear#xff09;有两种指向方式#xff1a;
队尾指针指向队尾元素的位置#xff0c;队尾指针指向… 目录 1.实现方式说明2.代码实现2.12.1.1 代码12.1.2 代码22.1.3 代码3 2.22.2.1 代码42.2.5 代码52.2.6 代码6 总结 1.实现方式说明
多在选择题中考察
队尾指针rear有两种指向方式
队尾指针指向队尾元素的位置队尾指针指向队尾元素的下一个位置。
区分队空与队满
牺牲一个存储空间利用队头元素和队尾元素的相对位置来区分队空与队满。增加一个变量size记录队列元素个数增加一个变量tag记录操作是删除tag为0还是插入tag为1插入后rear队尾front是队满删除后rearfront是队空。
所以队列的实现一共有六种情况 书写代码注意操作实现的前提条件也就是逻辑问题
查、删的前提是队列非空要进行判断插入的前提是队列不满要进行判断。
静态数组实现的队列是循环队列为了循环利用空间rear的下一个元素为(rear1)%MaxSize.
2.代码实现
2.1
2.1.1 代码1
C静态数组实现rear队尾指针指向队尾元素的下一个元素且牺牲一个存储空间来区分队满和队空的判断。 这种情况下队列的长度为(rearMaxSize-front)%MaxSize.
#include stdio.h
#include assert.h
#define MaxSize 10
typedef int ElemType;
typedef struct {ElemType data[MaxSize];int front, rear;
}SqQueue;
void InitQueue(SqQueue Q)
{Q.rear Q.front 0;
}
bool QueueEmpty(SqQueue Q)
{if (Q.rear Q.front)return true;elsereturn false;
}
bool EnQueue(SqQueue Q,ElemType x) {if ((Q.rear 1) % MaxSize Q.front)return false;Q.data[Q.rear] x;Q.rear (Q.rear 1) % MaxSize;return true;
}
bool DeQueue(SqQueue Q, ElemType x)
{if (QueueEmpty(Q))return false;x Q.data[Q.front];Q.front (Q.front 1) % MaxSize;return true;
}
bool GetHead(SqQueue Q, ElemType x)
{//assert(!QueueEmpty(Q));if (QueueEmpty(Q))return false;x Q.data[Q.front];return true;
}
void testQueue()
{SqQueue Q;InitQueue(Q);//printf(%d\n,QueueEmpty(Q));EnQueue(Q, 5);int x 0;DeQueue(Q, x);GetHead(Q, x);printf(%d\n,x);
}
int main() {testQueue();return 0;
}后续代码与代码1相同的部分省略
2.1.2 代码2
C静态数组实现rear队尾指针指向队尾元素的下一个元素且增加一个变量size记录队列长度来区分队满和队空的判断。
//队尾指针指向队尾元素
//引入size变量来记录队列元素个数
typedef struct {ElemType data[MaxSize];int front, rear;int size;
}SqQueue;
void InitQueue(SqQueue Q)
{Q.rear Q.front 0;Q.size 0;
}
bool QueueEmpty(SqQueue Q)
{if (Q.size0)return true;elsereturn false;
}
bool EnQueue(SqQueue Q, ElemType x) {if (Q.sizeMaxSize)//队满的判断return false;Q.data[Q.rear] x;Q.rear (Q.rear 1) % MaxSize;Q.size;return true;
}
bool DeQueue(SqQueue Q, ElemType x)
{if (QueueEmpty(Q))return false;x Q.data[Q.front];Q.front (Q.front 1) % MaxSize;Q.size--;return true;
}2.1.3 代码3
C静态数组实现rear队尾指针指向队尾元素的下一个元素且增加一个变量tag来记录判断前队列的上一步操作是入队还是出队来区分队满和队空的判断。
//队尾指针指向队尾元素
//引入tag变量来记录队列元素个数元素入队tag为1出队tag为1
typedef struct {ElemType data[MaxSize];int front, rear;int tag;
}SqQueue;
void InitQueue(SqQueue Q)
{Q.rear Q.front 0;Q.tag 0;
}
bool QueueEmpty(SqQueue Q)
{if (Q.rear Q.frontQ.tag0)return true;elsereturn false;
}
bool EnQueue(SqQueue Q, ElemType x) {if (Q.rear Q.front Q.tag 1)return false;Q.data[Q.rear] x;Q.rear (Q.rear 1) % MaxSize;Q.tag 1;return true;
}
bool DeQueue(SqQueue Q, ElemType x)
{if (QueueEmpty(Q))return false;x Q.data[Q.front];Q.front (Q.front 1) % MaxSize;Q.tag 0;return true;
}其实我们遇到的问题是Q.rearQ.front可以表示队空和队满两种状态那么我们考虑怎么将二者分开呢1.牺牲一个存储单元将队满对队空的判断条件区别开2.增加size变量3.增加tag变量只有入队之后才有可能队满出队之后才有可能队空。 三种情况的对比图如下
2.2
2.2.1 代码4
C静态数组实现rear队尾指针指向队尾元素且牺牲一个存储空间来区分队满和队空的判断。
//队尾指针指向队尾元素下一个元素
//牺牲一个存储空间
void InitQueue(SqQueue Q)
{Q.rear -1;Q.front 0;
}
bool QueueEmpty(SqQueue Q)
{if ((Q.rear 1) % MaxSize Q.front)return true;elsereturn false;
}
bool EnQueue(SqQueue Q, ElemType x) {if ((Q.rear 2) % MaxSize Q.front)return false;Q.rear (Q.rear 1) % MaxSize;Q.data[Q.rear] x;return true;
}
bool DeQueue(SqQueue Q, ElemType x)
{if (QueueEmpty(Q))return false;x Q.data[Q.front];Q.front (Q.front 1) % MaxSize;return true;
}2.2.5 代码5
C静态数组实现rear队尾指针指向队尾元素且增加一个变量size记录队列长度来区分队满和队空的判断。
typedef struct {ElemType data[MaxSize];int front, rear;int size;
}SqQueue;
void InitQueue(SqQueue Q)
{Q.rear -1;Q.front 0;Q.size0;
}
bool QueueEmpty(SqQueue Q)
{if (Q.size0)return true;elsereturn false;
}
bool EnQueue(SqQueue Q, ElemType x) {if (Q.sizeMaxSize)return false;Q.rear (Q.rear 1) % MaxSize;Q.data[Q.rear] x;Q.size;return true;
}
bool DeQueue(SqQueue Q, ElemType x)
{if (QueueEmpty(Q))return false;x Q.data[Q.front];Q.front (Q.front 1) % MaxSize;Q.size--;return true;
}2.2.6 代码6
C静态数组实现rear队尾指针指向队尾元素的下一个元素且增加一个变量tag来记录判断前队列的上一步操作是入队还是出队来区分队满和队空的判断。
typedef struct {ElemType data[MaxSize];int front, rear;int tag;
}SqQueue;
void InitQueue(SqQueue Q)
{Q.rear -1;Q.front 0;Q.tag0;
}
bool QueueEmpty(SqQueue Q)
{if (Q.tag0)return true;elsereturn false;
}
bool EnQueue(SqQueue Q, ElemType x) {if ((Q.rear 1) % MaxSize Q.front Q.tag0)return false;Q.rear (Q.rear 1) % MaxSize;Q.data[Q.rear] x;Q.tag1;return true;
}
bool DeQueue(SqQueue Q, ElemType x)
{if (QueueEmpty(Q))return false;x Q.data[Q.front];Q.front (Q.front 1) % MaxSize;Q.tag0;return true;
}总结
以上部分为王道课件代码部分为自写代码有问题欢迎交流。 注王道本身图画得很形象此处不再做图有兴趣的伙伴可以去看一下王道该章节的内容。
