c++循环队列：机器翻译

机器翻译

写这道题真的恶心到我了，从答案错误18->91->45->91就是没个正确的，后来是问学长才知道错误所在，又为这个题讨论了半天，我也要研究他的代码了，如果研究透了，可能会重新补充，不过这是后话了。。。

题目描述

小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。
这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如
果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续
的查找和翻译。
假设内存中有M个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的单词数不超过M?1，软件会将新单词存入一个未使用的内存单元；若内存中已存入M个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。
假设一篇英语文章的长度为N个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。

输入

输入文件共2行。每行中两个数之间用一个空格隔开。 第一行为两个正整数M和N，代表内存容量和文章的长度。
第二行为N个非负整数，按照文章的顺序，每个数（大小不超过1000）代表一个英文单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。

【输入输出样例1说明】 整个查字典过程如下：每行表示一个单词的翻译，冒号前为本次翻译后的内存状况： 空：内存初始状态为空。
1．1：查找单词1并调入内存。
2．1 2：查找单词2并调入内存。
3．1 2：在内存中找到单词1。
4．1 2 5：查找单词5并调入内存。
5．2 5 4：查找单词4并调入内存替代单词1。
6．2 5 4：在内存中找到单词4。
7．5 4 1：查找单词1并调入内存替代单词2。
共计查了5次词典。 【数据范围】 对于10%的数据有M=1，N≤5。 对于100%的数据有0<M≤100，0<=N≤1000。

输出

输出共1行，包含一个整数，为软件需要查词典的次数。

样例输入 Copy

3 7
1 2 1 5 4 4 1

样例输出 Copy

5

提示

此题要求使用队列来做，但是可能要略微改动ADT.

先是我91总是过不了的代码：

#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int QElemType;
typedef int Status;typedef struct
{
    QElemType *base;int front;int rear;
} SqQueue;void InitQueue(SqQueue &Q,int m)    //创建循环队列
{
    Q.base = new QElemType[m];Q.front = Q.rear = 0;
}void DestroyQueue(SqQueue &Q)  //销毁循环队列
{
    if(Q.base)delete []Q.base;Q.base = NULL;Q.front = Q.rear = 0;
}void EnQueue(SqQueue &Q,QElemType e,int m)  //循环队列的入队
{
    int i;if((Q.rear +1)%m== Q.front)  //这里由于取模运算用的不是很好，下面会有改动{
    for(i = 0; i<m-2; i++)  //这里因为是当成了有限的数组，其实m的值很不好控制，下面有改动{
    Q.base[i] = Q.base[i+1];}Q.base[i] = e;}else{
    Q.base[Q.rear] = e;Q.rear = (Q.rear + 1)%m; //仍然取模运算运用不太到位，会有改动}
}Status SearchQueue(SqQueue &Q,QElemType e,int m) //循环队列的查找
{
    int i ;for(i=0; i<m; i++) //这里i的范围条件会有改动{
    if(Q.base[i]==e)return 1;}if(i==m)return 0;
}int main()
{
    int m,n;int i, j;int num=0;SqQueue Q;cin>>m>>n;int* a = new int[n];InitQueue( Q, m);for(i=0; i<n; i++)cin >> a[i];for(j=0; j<n; j++){
    if(SearchQueue( Q, a[j],m)==0){
    EnQueue(Q,a[j],m+1);num++;}}cout<<num<<endl;DestroyQueue(Q);return 0;
}

这个有个错误提示：

样例是可以过的，但是由于边界条件控制的不好，所以后面的结果就不对了。最开始思路是循环队列满了，可以直接覆盖队首，但其实并没有，因为队满和队空实际上都是front和rear指向队首，所以当队满了以后，整个队列数据就被清空了，可以自己测试一下。写一个打印输出的函数。其实就是m传值不如rear和front好使，因为这道题本身就是一个循环队列的问题。或者可以把队列多开一个，然后用取模判断，是否队满，然后再移动front指针，再覆盖队首。

打印输出的函数（测试用）：

void PrintQueue(SqQueue q,int m)
{
    cout <<"Queue is:";for(int i = q.front; i!=q.rear; i=(i+1)%m){
    cout << q.base[i] <<' ';}cout <<endl;
}

然后是oj过了的代码：

#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int QElemType;
typedef int Status;typedef struct
{
    QElemType *base;int front;int rear;
} SqQueue;void InitQueue(SqQueue &Q,int m)    //创建循环队列
{
    Q.base = new QElemType[m];Q.front = Q.rear = 0;
}void DestroyQueue(SqQueue &Q)  //销毁循环队列
{
    if(Q.base)delete []Q.base;Q.base = NULL;Q.front = Q.rear = 0;
}void EnQueue(SqQueue &Q,QElemType e,int m)  //循环队列的入队
{
    int i;if(Q.rear == m){
    for(i = 0; i<Q.rear-1; i++){
    Q.base[i] = Q.base[i+1];}Q.base[i] = e;}else{
    Q.base[Q.rear] = e;Q.rear++;}}Status SearchQueue(SqQueue &Q,QElemType e,int m) //循环队列的查找
{
    int i ;for(i=0; i<Q.rear; i++){
    if(Q.base[i]==e)return 1;}return 0;
}
int main()
{
    int m,n;int i, j;int num=0;SqQueue Q;cin>>m>>n;int* a = new int[n];InitQueue( Q, m);for(i=0; i<n; i++)cin >> a[i];for(j=0; j<n; j++){
    if(SearchQueue( Q, a[j],m)==0){
    EnQueue(Q,a[j],m);num++;}}cout<<num<<endl;DestroyQueue(Q);return 0;
}

具体哪里改了在第一个错误代码有写，由于我的c++数据结构这里实在不行，代码真的仅供参考，如果有什么错误请及时告知我。