要求循环队列不损失一个空间全部都能得到利用，...

发表于 更新于 分类于 Waline：

题目1：要求循环队列不损失一个空间全部都能得到利用，设置一个标志量tag，以tag为0或1来区分头尾指针相同时的队列状态，请编写与此结构相应的入队与出队算法，循环队列的类型声明与函数原型如下所示： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct SeqQueue
{
    QueueElementType element[MAXSIZE];/*队列的元素空间*/
    int front;/*头指针指示器*/
    int rear;/*尾指针指示器*/
    int tag;/*结合front和rear表示当前栈空或满*/
    /*front==rear && tag==1表示满，front==rear && tag==0表示空*/
}SeqQueue;

/*入队操作*/
int EnterQueue(SeqQueue *Q,QueueElementType x)
    
/*出队操作*/
int DeleteQueue(SeqQueue *Q,QueueElementType *x)

完整程序如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define MAXSIZE 20
typedef int QueueElementType;
typedef struct SeqQueue //定义循环队列
{
    QueueElementType element[MAXSIZE];
    int front;
    int rear;
    int tag;
}SeqQueue;

void InitQueue(SeqQueue *Q) //初始化循环队列
{
    Q->front=Q->rear=0;
    Q->tag=0;
}

int EnterQueue(SeqQueue *Q,QueueElementType x)  //入队
{
    if(((Q->rear)%MAXSIZE)==(Q->front) && Q->tag==1)//判断队列是否已满
        return ERROR;
    else
    {
        Q->element[Q->rear]=x;
        Q->rear=(Q->rear+1)%MAXSIZE;
        if((Q->rear)==(Q->front))//判断队列是否已满
            Q->tag=1;
        return OK;
    }
}

int DeleteQueue(SeqQueue *Q,QueueElementType *x) //出队
{
    if(((Q->rear)%MAXSIZE)==(Q->front) && Q->tag==0)//判断队列是否为空
        return ERROR;
    else 
    {
        (*x)=Q->element[Q->front];
        Q->front=(Q->front+1)%MAXSIZE;
        if((Q->front)==(Q->rear))//判断队列是否已空
            Q->tag=0;
        return OK;
    }
}
/*
void printQueue(SeqQueue Q)
{
    int i;
    for(i=Q.front;i<Q.rear;i++)
        printf("%d ",Q.element[i]);
    putchar('\n');
}
*/
int main()
{
    SeqQueue s;
    InitQueue(&s);
    printf("Please input int xing numbers: \n");
    QueueElementType x;
    do {
        scanf("%d",&x);
    } while(EnterQueue(&s,x));
    while(DeleteQueue(&s,&x))
     printf("%d ",x);
    putchar('\n');
    system("pause");
    return 0;
}

运行结果如图：

正确答案如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
typedef struct SeqQueue
{
	QueueElementType  element[MAXSIZE];  /* 队列的元素空间*/
	int front;  /*头指针指示器*/
	int rear;  /*尾指针指示器*/
	int tag;/*结合front和rear表示当前栈空或满*/
	/*front==rear &&tag==1表示满，front==rear &&tag==0表示空*/
}SeqQueue;

/*初始化操作*/
int InitQueue(SeqQueue *Q)
{
	if(!Q)return ERROR;
	/* 将*Q初始化为一个空的循环队列 */
	Q->front=Q->rear=0;
	Q->tag=0;
	return OK;
}

/*入队操作*/
int EnterQueue(SeqQueue *Q, QueueElementType x)
{  /*将元素x入队*/
	if(!Q)return ERROR;
	if(Q->rear==Q->front && Q->tag)  /*队列已经满了*/
    {
		printf("OVERFLOW\n");
		return(FALSE);
	}
	Q->element[Q->rear]=x;/* 注意入栈与修改队尾指针的次序 */
	Q->rear=(Q->rear+1)%MAXSIZE;  /* 重新设置队尾指针 */
	if(Q->rear==Q->front)
    	Q->tag=1;
	return(TRUE);  /*操作成功*/
}

/*出队操作*/ 
int DeleteQueue(SeqQueue *Q, QueueElementType *x)
{ /*删除队列的队头元素，用x返回其值*/
	if(!Q)return ERROR;
	if(Q->front==Q->rear && !(Q->tag))  /*队列为空*/
    {
		printf("UNDERFLOW\n");
		return(FALSE);
	}
	*x=Q->element[Q->front]; /* 注意出队与修改队首指针的次序 */
	Q->front=(Q->front+1)%MAXSIZE;  /*重新设置队头指针*/
	if(Q->rear==Q->front)
        Q->tag=0;
	return(TRUE);  /*操作成功*/
}

题目2：回文判断。称正读与反读都相同的字符序列为“回文”序列。试写一算法，判断依次读入的一个以@为结束符的字符序列，是否为形如“序列1&序列2”模式的字符序列。其中序列1和序列2中都不包含字符”&”，且序列2是序列1的逆序列。例如”a+b&b+a”是属于该模式的字符序列，而”1+3&3-1”则不是。函数原型如下所示：

/*序列从终端读入*/

int IsReverse()

完整程序如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h>
#include <stdlib.h>
#include "ds.h"
int isReverse(char *c)
{
    int i=0,j,k,count=0;
    printf("Please input characters and input @ means endinput: \n");
    do {
        scanf("%c",&c[i]);
        i++;
    } while(c[i-1]!='@');
    i--;
    for(j=0;j<i;j++)
    {
        if(c[j]=='&')
            count++;
    }
    if(count)
    {
         for(j=0;c[j]!='&';j++)
        {
            k=i-1-j;
            if(c[k]==c[j])
                continue;
            else
            {
                return ERROR;
            }
        }
        return OK;
    }
    else
        return ERROR;
}

int main()
{
    char c[Stack_Size];
    if(isReverse(c))
        printf("Yes! \n");
    else
        printf("NO! \n");
    system("pause");
    return 0;
}

其中，ds.h文件如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/*定义常量*/
#define		TRUE	1
#define		FALSE	0
#define		OK		1
#define		ERROR	0
#define		Stack_Size 20/*顺序栈空间大小*/

/*定义ElemType类型和使用到的物理数据类型*/
typedef char StackElementType;
/*定义使用顺序栈*/
typedef struct SeqStack
{
	StackElementType elem[Stack_Size]; /*用来存放栈中元素的一维数组*/
	int top;          		/*用来存放栈顶元素的下标，top为-1表示空栈*/
}SeqStack;

/*声明物理数据类型的操作（函数）和使用到的其他功能函数*/
/*初始化*/
void InitStack(SeqStack *S);
/*判栈空*/
int IsEmpty(SeqStack *S); /*判断栈S为空栈时返回值为真，反之为假*/
/*判栈满*/
int IsFull(SeqStack *S);	/*判断栈S为满栈时返回值为真，反之为假*/
void Push(SeqStack *S,StackElementType x);
void Pop(SeqStack *S,StackElementType *x);

/*定义物理数据类型的操作（函数）和使用到的其他功能函数*/
/*初始化*/
void InitStack(SeqStack *S)
{
	S->top=-1;
}

/*判栈空*/
int IsEmpty(SeqStack *S) /*判断栈S为空栈时返回值为真，反之为假*/
{
	if((S->top)==-1)
		return TRUE;
	else
		return FALSE;
}

/*判栈满*/
int IsFull(SeqStack *S)	/*判断栈S为满栈时返回值为真，反之为假*/
{
    if((S->top)==(Stack_Size-1))
        return TRUE;
    else
        return FALSE;
}

void Push(SeqStack *S,StackElementType x) //进栈
{
    S->top++;
    S->elem[S->top]=x;
}

void Pop(SeqStack *S,StackElementType *x) //出栈
{
    (*x)=S->elem[S->top];
    S->top--;
}

运行结果如图：

正确答案如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int IsReverse()
{
	LinkStack s;
	char c,e;
	InitLStack(&s);
	while((e=getchar())!='&')
	{
		if(e=='@')  //不允许在'&'之前出现'@'
		return ERROR;
		Push(s,e); 
	}
	/*有些同学此处用了do…while循环，最好使用while循环*/
	while( (e=getchar())!='@')
	{
		if(StackEmpty(s))//栈空
			return ERROR;
		Pop(s,&c);
		if(e!=c)
			return ERROR;
	}
	if(!StackEmpty(s)) //栈非空
		return ERROR;
	return OK;
}//IsReverse

题目3：一般性回文判断。称正读与反读都相同的字符序列为”回文“序列。试写一算法，判断依次读入的一个字符序列，是否为形如”序列1序列2”模式的字符序列。其中序列2是序列1的逆序列。例如”a+bb+a”是属于该模式的字符序列，而”1+33-1”则不是。(提示：同时使用栈和队列实现)函数原型如下所示：

/*序列从终端读入*/

int Palindrome_Test()

完整程序如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <stdio.h>
#include <stdlib.h>
#define Stack_Size 50
#define TRUE 1
#define FALSE 0
typedef char StackElementType;
typedef char QueueElementType;

typedef struct //声明顺序栈
{
    StackElementType elem[Stack_Size];
    int top;
}SeqStack;

void InitStack(SeqStack *S) //初始化顺序栈
{
    S->top=-1;
}

int Push(SeqStack *S,StackElementType x) //进栈
{
    if(S->top==(Stack_Size-1))
        return FALSE;
    S->top++;
    S->elem[S->top]=x;
    return TRUE;
}

int Pop(SeqStack *S,StackElementType *x) //出栈
{
    if(S->top==-1)
        return FALSE;
    else
    {
        (*x)=S->elem[S->top];
        S->top--;
        return TRUE;
    }
}

typedef struct //声明循环队列
{
    QueueElementType element[Stack_Size];
    int front;
    int rear;
}SeqQueue;

void InitQueue(SeqQueue *Q) //循环队列初始化
{
    Q->front=Q->rear=0;
}

int EnterQueue(SeqQueue *Q,QueueElementType x) //循环队列进队
{
    if(((Q->rear+1)%Stack_Size)==Q->front)
        return FALSE;
    Q->element[Q->rear]=x;
    Q->rear=(Q->rear+1)%Stack_Size;
    return TRUE;
}

int DleteQueue(SeqQueue *Q,QueueElementType *x) //循环队列出队
{
    if(Q->front==Q->rear)
        return FALSE;
    (*x)=Q->element[Q->front];
    Q->front=(Q->front+1)%Stack_Size;
    return TRUE;
}

int Palindrome_Test(SeqStack *S,SeqQueue *Q)
{
    printf("Please input characters and input @ means endinput: \n");
    StackElementType c,d;
    int count=0,i;
    scanf("%c",&c);
    while(c!='@')
    {
        count++;
        Push(S,c);
        EnterQueue(Q,c);
        scanf("%c",&c);
    }
    for(i=0;i<count/2;i++)
    {
        if(Pop(S,&c));
        if(DleteQueue(Q,&d));
        if(c==d)
            continue;
        else
            return FALSE;  
    }
    return TRUE;
}

int main()
{
    SeqStack s;
    SeqQueue q;
    InitStack(&s);
    InitQueue(&q);
    if(Palindrome_Test(&s,&q))
        puts("Yes! ");
    else 
        puts("No! ");
    system("pause");
    return 0;
}

运行结果如图：

正确答案如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int Palindrome_Test()
{
	SeqStack s;
	SeqQueue q;
	char c,e;
	InitStack(&s);
	InitQueue(&q);
	while((c=getchar())!='\n')/*终端输入结束是通过’\n’表示，不是’\0’表示（字符串结束）*/
	{
		Push(&s,c);EnterQueue(&q,c); //同时使用栈和队列两种结构
	}
	/*不需要判断栈和队列是否同时为空，因为二者的长度相同，也可以在前面增加计数器保证只判断一半的字符串即可*/
	while(!IsEmpty(&s))
	{
		Pop(&s,&c);DeleteQueue(&q,&e);
		if(c!=e) return FALSE;
	}
	return TRUE;
}

完！