C语言用栈和队列实现的回文检测功能示例

C语言用栈和队列实现的回文检测功能示例 在计算机科学中，回文检测是指判断给定的字符串是否是一个回文的操作。回文是一种特殊的字符串，它可以从左到右阅读或从右到左阅读，结果是一样的。例如，字符串"madam"就是一个回文。 C语言中，可以使用栈和队列来实现回文检测功能。栈是一种后进先出的数据结构，队列是一种先进先出的数据结构。通过使用栈和队列，可以分别存储字符串的前半部分和后半部分，然后比较两个部分是否相同，以判断字符串是否是一个回文。 下面是使用栈和队列实现回文检测功能的示例代码： 我们需要定义栈和队列的结构体： ```c typedef struct { char a; } SElemType; typedef struct { SElemType *base; SElemType *top; int stacksize; } SqStack; typedef struct { char b; struct QNode *next; } QNode, *QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; } LinkQueue; ``` 然后，我们需要实现栈和队列的操作函数，包括初始化栈、入栈、出栈、判断栈是否为空、获取栈的长度等： ```c Status InitStack(SqStack *S) { S->base = (SElemType *)malloc(SIZE * sizeof(SElemType)); if (!S->base) exit(OVERFLOW); S->top = S->base; S->stacksize = SIZE; return OK; } Status Push(SqStack *S, SElemType e) { if (S->top - S->base >= S->stacksize) { S->base = (SElemType *)malloc((S->stacksize + STACKINCREMENT) * sizeof(SElemType)); if (!S->base) exit(OVERFLOW); S->top = S->base + S->stacksize; S->stacksize += STACKINCREMENT; } *S->top++ = e; return OK; } Status Stackempty(SqStack S) { if (S.top == S.base) return TRUE; else return FALSE; } Status Pop(SqStack *S, SElemType *e) { if (S->top == S->base) return ERROR; *e = *--S->top; return OK; } Status StackLength(SqStack S) { return (S.top - S.base); } ``` 类似地，我们还需要实现队列的操作函数，包括初始化队列、入队、出队、判断队列是否为空、获取队列的长度等： ```c Status InitQueue(LinkQueue *Q) { Q->front = (QueuePtr)malloc(sizeof(QNode)); Q->rear = Q->front; if (!Q->front) exit(OVERFLOW); Q->front->next = NULL; return OK; } Status EnQueue(LinkQueue *Q, char f) { p = (QueuePtr)malloc(sizeof(QNode)); if (!p) exit(OVERFLOW); p->b = f; p->next = NULL; Q->rear->next = p; Q->rear = p; return OK; } Status DeQueue(LinkQueue *Q, char *f) { if (Q->front == Q->rear) return ERROR; p = Q->front->next; *f = p->b; Q->front->next = p->next; if (Q->rear == p) Q->rear = Q->front; free(p); return OK; } Status QueueLength(LinkQueue Q) { int i = 0; p = Q.front; while (Q.rear != p) { i++; p = p->next; } return i; } ``` 我们可以使用栈和队列来实现回文检测功能： ```c void palindromeDetection(char *str) { SqStack S; LinkQueue Q; InitStack(&S); InitQueue(&Q); int i, length = strlen(str); for (i = 0; i < length; i++) { Push(&S, str[i]); EnQueue(&Q, str[i]); } while (!Stackempty(S) && !Queueempty(Q)) { SElemType e; char f; Pop(&S, &e); DeQueue(&Q, &f); if (e.a != f) { printf("不是回文\n"); return; } } printf("是回文\n"); } ``` 在上面的代码中，我们首先初始化栈和队列，然后将字符串的每个字符分别压入栈和队列中。接着，我们从栈和队列中弹出字符，并比较它们是否相同。如果所有字符都相同，则字符串是一个回文。否则，字符串不是一个回文。