数据结构作业
2002 年第三章 栈和队列
3.28 假设带表头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队和出队的算法。
/// a1 a2 an非空情况：
头结点指针,rear->next;
首元素指针,rear->next->next;
rear
///空队情况：
空队条件,rear->next=rear;
rear
用指针 rear
表示队列
（ 1） 定义类型：
typedef struct Node{
ElemType data;
struct Node *next;
} Node,*LinkQue;
LinkQue InitQue(void);
LinkQue EnQueue(LinkQue rear,ElemType e);
LinkQue DeQueue(LinkQue rear,ElemType e);
main()
{LinkQue que1,que2; int elem;
que1=InitQue(); que2=InitQue();
que1= EnQueue(que1,10); que1= DeQueue(que1,&elem);
}
（ 2） 初始化算法：
返回值为 NULL表示初始化失败，非 NULL表示成功。
LinkQue InitQue(void)
{ LinkQue p;
p=malloc(sizeof(Node));
if (!p) { printf(“OVERFLOW”); return NULL;}
p->next=p;
return p;
}
（ 3） 入队列算法：
返回值为 NULL表示入队列失败，非 NULL表示成功。
LinkQue EnQueue(LinkQue rear,ElemType e);
{ LinkQue p;
p=malloc(sizeof(Node));
if (!p) { printf(“OVERFLOW”); return NULL;}
p->data=e;
p->next=rear->next; /*新结点指向表头结点 */
rear->next=p; /*原表尾结点指向新结点 */
rear=p; /*表尾指针指向新结点为新表尾 */
return rear; } /*返回表尾指针 */
（ 3） 出队列算法：
返回值为 NULL表示出队列失败，非 NULL表示成功。
LinkQue DeQueue(LinkQue rear,ElemType *e);
{ LinkQue p;
if (rear->next=rear) { printf(“空队列” ); return NULL;}
p= rear->next->next; /*p指向待出队列的首结点 */
*e=p->data; /*出队列的首结点元素值 */
rear->next->next =p->next; /*出队：删除首结点 */
if (rear==p) /*仅有一个结点 */
rear=rear->next; /*队尾指针志向表头结点 */
return rear; } /*返回表尾指针 */
2.30 假设将循环队列定义为：以域变量 rear和 length分别指向循环队列的队尾元素的位置和元素的个数。试给出此循环队列的队满条件，并写出相应的入队和出队的算法 。
A B C D
0 1 2 3 4 5 6 …,,MAXSIZE-1
rear length=4
首元素序号,rear-length+1=6-4+1=3
C D A B C D A B
0 1 2 3 4 5 6 …,,MAXSIZE-1
rear length=4
首元素序号,rear-length+1+MAXSIZE==1-4+1+MAXSIZE
= MAXSIZE-2
首元素序号,( rear-length+1+MAXSIZE)%MAXSIZE
队满条件,length=MAXSIZE
(1) 类型定义：
typedef struct {
ElemType elem[MAXSIZE];
int rear,length;
} SeQueue;
main()
{SeQueue que1,que2; ElemType e;
que1.length=0; que1.rear=0;
EnQueue(&que1,10);
DeQueue(&que1,&e); }
（ 2） 入队列算法：
int EnQueue(SeQueue *Q,ElemType e);
{
if (Q->length==MAXSIZE)
{ printf(“OVERFLOW”); return 0;}
Q->rear=(Q->rear+1)%MAXSIZE; /*取下一空位置 */
Q->elem[Q->rear]=e;
Q->length++;
return 1;
}
（ 3） 出队列算法：
int DeQueue(SeQueue *Q,ElemType *e);
{
if (Q->length==0)
{ printf(“空队列” ); return 0;}
*e=Q->elem[( rear-length+1+MAXSIZE)%MAXSIZE];
Q->length--;
return 1;
}
2.31 假设称正读和反读都相同的字符序列为“回文”，试写一算法判别读入的一个以 @为结束的字符序列是否为“回文”。
int huiwen()
{ InitStack(S); InitQueue(Q);
while ((c=getchar())!=‘@’)
{ Push(S,c),
EnQueue(Q,c); }
while (!StackEmpty(S))
{ Pop(S,c1); DeQueue(Q,c2);
if (c1!=c2) return 0;
}
return 1;