程序填空题：使用栈和队列进行回文判断
使用栈和队列进行回文判断
```c
#include
#include
typedef char DataType;
struct Node {
DataType data;
struct Node* next;
};
typedef struct Node *PNode;
typedef struct Node *LinkStack;
struct Queue
{
PNode f;
PNode r;
};
typedef struct Queue *LinkQueue;
LinkStack SetNullStack_Link()
{
LinkStack top = (LinkStack)malloc(sizeof(struct Node));
if (top != NULL) top->next = NULL;
else printf("Alloc failure");
return top;
}
int IsNullStack_link(LinkStack top)
{
if (top->next == NULL)
return 1;
else
return 0;
}
void Push_link(LinkStack top, DataType x)
{
PNode p;
p = (PNode)malloc(sizeof(struct Node));
if (p == NULL)
printf("Alloc failure");
else
{
p->data = x;
p->next = top->next;
top->next = p;
}
}
void Pop_link(LinkStack top)
{
PNode p;
if (top->next == NULL)
printf("it is empty stack!");
else
{
p = top->next;
top->next = p->next;
free(p);
}
}
DataType Top_link(LinkStack top)
{
if (top->next == NULL)
{
printf("It is empty stack!");
return 0;
}
else
return top->next->data;
}
LinkQueue SetNullQueue_Link()
{
LinkQueue lqueue;
lqueue = (LinkQueue)malloc(sizeof(struct Queue));
if (lqueue != NULL)
{
lqueue->f = NULL;
lqueue->r = NULL;
}
else
printf("Alloc failure! \n");
return lqueue;
}
int IsNullQueue_link(LinkQueue lqueue)
{
return (lqueue->f == NULL);
}
void EnQueue_link(LinkQueue lqueue, DataType x)
{
PNode p;
p = (PNode)malloc(sizeof(struct Node));
if (p == NULL)
printf("Alloc failure!");
else {
p->data = x;
p->next = NULL;
if (lqueue->f == NULL)
{
lqueue->f = p;
lqueue->r = p;
}
else
{
lqueue->r->next = p;
lqueue->r = p;
}
}
}
void DeQueue_link(LinkQueue lqueue)
{
struct Node * p;
if (lqueue->f == NULL)
printf("It is empty queue!\n ");
else
{
p = lqueue->f;
lqueue->f = lqueue->f->next;
free(p);
}
}
DataType FrontQueue_link(LinkQueue lqueue)
{
if (lqueue->f == NULL)
{
printf("It is empty queue!\n");
return 0;
}
else
return (lqueue->f->data);
}
int main()
{
DataType ch;
int flag;
LinkStack stack_pal = SetNullStack_Link();
LinkQueue queue_pal = SetNullQueue_Link();
ch = getchar();
while (ch != '#')
{
Push_link(stack_pal, ch);
EnQueue_link(queue_pal, ch);
ch = getchar();
}
flag = 1;
while (@@[(!IsNullStack_link(stack_pal)) &&(!IsNullQueue_link(queue_pal))](3))
{
if (@@[Top_link(stack_pal) != FrontQueue_link(queue_pal)](2))
{
flag = 0;
break;
}
else
{
@@[ Pop_link(stack_pal)](2);
@@[DeQueue_link(queue_pal)](2);
}
}
if (@@[flag|flag==1](1))
printf("this is palindromic");
else
printf("this is NOT palindromic");
return 0;
}
```
答案：
第1空：(!IsNullStack_link(stack_pal)) &&(!IsNullQueue_link(queue_pal))
第2空：Top_link(stack_pal) != FrontQueue_link(queue_pal)
第3空： Pop_link(stack_pal)
第4空：DeQueue_link(queue_pal)
第5空：flag|flag==1
```c
#include
#include
typedef char DataType;
struct Node {
DataType data;
struct Node* next;
};
typedef struct Node *PNode;
typedef struct Node *LinkStack;
struct Queue
{
PNode f;
PNode r;
};
typedef struct Queue *LinkQueue;
LinkStack SetNullStack_Link()
{
LinkStack top = (LinkStack)malloc(sizeof(struct Node));
if (top != NULL) top->next = NULL;
else printf("Alloc failure");
return top;
}
int IsNullStack_link(LinkStack top)
{
if (top->next == NULL)
return 1;
else
return 0;
}
void Push_link(LinkStack top, DataType x)
{
PNode p;
p = (PNode)malloc(sizeof(struct Node));
if (p == NULL)
printf("Alloc failure");
else
{
p->data = x;
p->next = top->next;
top->next = p;
}
}
void Pop_link(LinkStack top)
{
PNode p;
if (top->next == NULL)
printf("it is empty stack!");
else
{
p = top->next;
top->next = p->next;
free(p);
}
}
DataType Top_link(LinkStack top)
{
if (top->next == NULL)
{
printf("It is empty stack!");
return 0;
}
else
return top->next->data;
}
LinkQueue SetNullQueue_Link()
{
LinkQueue lqueue;
lqueue = (LinkQueue)malloc(sizeof(struct Queue));
if (lqueue != NULL)
{
lqueue->f = NULL;
lqueue->r = NULL;
}
else
printf("Alloc failure! \n");
return lqueue;
}
int IsNullQueue_link(LinkQueue lqueue)
{
return (lqueue->f == NULL);
}
void EnQueue_link(LinkQueue lqueue, DataType x)
{
PNode p;
p = (PNode)malloc(sizeof(struct Node));
if (p == NULL)
printf("Alloc failure!");
else {
p->data = x;
p->next = NULL;
if (lqueue->f == NULL)
{
lqueue->f = p;
lqueue->r = p;
}
else
{
lqueue->r->next = p;
lqueue->r = p;
}
}
}
void DeQueue_link(LinkQueue lqueue)
{
struct Node * p;
if (lqueue->f == NULL)
printf("It is empty queue!\n ");
else
{
p = lqueue->f;
lqueue->f = lqueue->f->next;
free(p);
}
}
DataType FrontQueue_link(LinkQueue lqueue)
{
if (lqueue->f == NULL)
{
printf("It is empty queue!\n");
return 0;
}
else
return (lqueue->f->data);
}
int main()
{
DataType ch;
int flag;
LinkStack stack_pal = SetNullStack_Link();
LinkQueue queue_pal = SetNullQueue_Link();
ch = getchar();
while (ch != '#')
{
Push_link(stack_pal, ch);
EnQueue_link(queue_pal, ch);
ch = getchar();
}
flag = 1;
while (@@[(!IsNullStack_link(stack_pal)) &&(!IsNullQueue_link(queue_pal))](3))
{
if (@@[Top_link(stack_pal) != FrontQueue_link(queue_pal)](2))
{
flag = 0;
break;
}
else
{
@@[ Pop_link(stack_pal)](2);
@@[DeQueue_link(queue_pal)](2);
}
}
if (@@[flag|flag==1](1))
printf("this is palindromic");
else
printf("this is NOT palindromic");
return 0;
}
```
答案：
第1空：(!IsNullStack_link(stack_pal)) &&(!IsNullQueue_link(queue_pal))
第2空：Top_link(stack_pal) != FrontQueue_link(queue_pal)
第3空： Pop_link(stack_pal)
第4空：DeQueue_link(queue_pal)
第5空：flag|flag==1
