c/c++ 数据结构 回文 栈 队列 的应用 自己做的

根据给定的文件信息，我们可以总结出以下几个关键的知识点： ### 一、C/C++中的数据结构基础 #### 1. 结构体定义 在 C/C++ 中，`struct` 关键字用于定义结构体类型，它允许我们创建包含不同类型的变量的自定义类型。 - **栈（Stack）**： ```cpp struct SqStact { char* top; char* base; int stactsize; }; ``` - `top`: 指向当前栈顶元素。 - `base`: 指向栈底元素。 - `stactsize`: 栈的最大容量。 - **队列（Queue）**： ```cpp struct QNode { char date; QNode* next; }; struct ListQueue { QNode* rear; QNode* front; }; ``` - `QNode`: 单个队列节点，包含数据和指向下一个节点的指针。 - `ListQueue`: 链表实现的队列，包含队尾指针和队头指针。 #### 2. 动态内存分配 在 C/C++ 中，可以使用 `new` 和 `delete` 进行动态内存分配与释放。 - **栈动态分配**： ```cpp s.base = new char(); s.top = s.base; ``` - `new char()`：为字符分配内存。 - **队列动态分配**： ```cpp QNode* p = new QNode(); Q.rear = Q.front = p; p->next = NULL; ``` - `new QNode()`：为队列节点分配内存。 - 初始化队列的前后指针并设置 `next` 为空。 ### 二、回文字符串的应用 #### 1. 基本概念 **回文** 是一种正读反读都一样的字符串或数字序列。例如，“level” 和 “12321”。 #### 2. 应用场景 - **栈的应用**：可以利用栈的后进先出特性来判断一个字符串是否是回文。 - **队列的应用**：可以利用队列的先进先出特性来辅助判断回文。 #### 3. 实现过程 - **栈的实现**： - 使用循环读取输入字符，并将字符压入栈中。 - 再次遍历栈，弹出栈顶元素并输出。 ```cpp while (s.top != s.base) { *s.top--; cout << *s.top << ""; *s.top = NULL; } ``` - **队列的实现**： - 将输入字符依次插入到队列尾部。 - 遍历队列，依次删除队头元素并输出。 ```cpp while (Q.front != Q.rear) { Q.front = Q.front->next; cout << Q.front->date << ""; } ``` ### 三、判断字符串是否为回文 #### 1. 思路 - 利用栈和队列的特性来判断一个字符串是否为回文。 - 字符串中的字符依次被压入栈和插入到队列尾部。 - 比较栈顶元素和队头元素是否相同。 #### 2. 实现代码 - **初始化栈和队列**： ```cpp SqStact s; s.base = new char(); s.top = s.base; ListQueue Q; Q.front = Q.rear = new QNode(); ``` - **读取字符并进行判断**： ```cpp int m = 0; int t = 0; while (true) { cin >> n; if (n == '@') break; *s.top = n; s.top++; QNode* q = new QNode(); q->date = n; Q.rear->next = q; q->next = NULL; Q.rear = q; t++; } ``` - **判断回文**： ```cpp while (s.top != s.base) { s.top--; Q.front = Q.front->next; if (*s.top == Q.front->date) { m++; } } if (m == t) cout << "It is!" << endl; else cout << "It is not" << endl; ``` 通过以上分析，我们可以看到该程序主要实现了对回文字符串的判断，其中涉及到了栈和队列的基本操作以及它们在实际问题中的应用。