[数据结构习题]栈——中心对称链

👉知识点导航💎：【数据结构】栈和队列

👉[王道数据结构]习题导航💎： $p a g e 70.4$

本节为栈和链表综合练习题

在这里插入图片描述

题目描述：

在这里插入图片描述

🎇思路：前段进栈

🔱思路分析：

要判断一个带头结点的单链表是否中心对称，即链表的前半部分和后半部分互为逆序关系，因此，由栈的先进后出特性可以实现逆序

step:

因为涉及链表和栈，我们需要分别实现相关的操作：

1. 单链表实现

①定义结构体：

typedef struct LNode { //定义一个单链表char data;struct LNode* next;
}LNode,*LinkList;

②初始化：

void InitList(LinkList& L, int n) {L = (LNode*)malloc(sizeof(LNode)); //头结点LNode* p = L;char x;for (int i = 0; i < n; i++) {cin >> x;LNode* s = (LNode*)malloc(sizeof(LNode));s->data = x;p->next = s;p = s;}p->next = NULL;
}

2. 顺序栈实现

①定义结构体

我们选择用顺序栈来实现

其中 $d a t a$ 为字符串数组， $t o p$ 为栈顶指针

#define Maxsize 50typedef struct SqStack { //定义一个栈char data[Maxsize];int top;
}SqStack;

②初始化&判空

由于 $S . t o p$ 指向的是栈顶元素，而当栈空时： $S . t o p = - 1$ ，以此来实现初始化与判空

void InitStack(SqStack& S) {S.top = -1; //初始化栈顶
}bool Empty(SqStack& S) {if (S.top == -1)return true;return false;
}

3. 中心对称链的判断

做完了前期准备之后，我们就要判断链是否中心对称了

算法思想：使用栈来判断链表中的数据元素是否中心对称，首先，让单链表的前半段元素放入栈中，在处理链表的后半段元素时，每访问链表的一个元素，就让栈弹出栈顶元素与之进行比较，若相等，则继续判断后续元素，直到链表后半段的元素全部比较完成，此时，若栈为空，则为中心对称链；否则，不成立

图解算法：
在这里插入图片描述

①前段元素进栈

由于已知链表的长度为 $n$ ，因此，只需要遍历 $⌊\frac{n}{2}⌋$ 次即遍历完成前半段所有元素

指针 $p$ 最初指向首结点，每访问到一个链表结点，便将其压入栈中：S.data[++S.top]=p->data

代码实现：

    LNode* p = L->next;for (int i = 0; i < n / 2; i++) {S.data[++S.top] = p->data; //压入栈p = p->next;}

结束时，如果链表长度 $n$ 为偶数，则指针 $p$ 直接指向后半段的首结点；若链表长度为奇数，则指向中心结点，此时需要让：p=p->next

if (n % 2 != 0) //如果n为奇数p = p->next; //让p指向后半段首位置

②前段元素出栈

当前状态为：

在这里插入图片描述

不断比较 S.data[S.top] 和 p->next 直到 $p == N ULL$ ，如果此时栈为空且指针 $p$ 指向 $N ULL$ ，则说明中心对称

防止中间存在元素不相等而提前退出

代码实现：

    while (p != NULL && p->data == S.data[S.top]) {S.top-=1;p = p->next;}if (Empty(S) && p==NULL)return true;elsereturn false;

完整代码实现；

#include<iostream>
#define Maxsize 50
using namespace std;typedef struct LNode { //定义一个单链表char data;struct LNode* next;
}LNode,*LinkList;void InitList(LinkList& L, int n) {L = (LNode*)malloc(sizeof(LNode)); //头结点LNode* p = L;char x;for (int i = 0; i < n; i++) {cin >> x;LNode* s = (LNode*)malloc(sizeof(LNode));s->data = x;p->next = s;p = s;}p->next = NULL;
}typedef struct SqStack { //定义一个栈char data[Maxsize];int top;
}SqStack;void InitStack(SqStack& S) {S.top = -1; //初始化栈顶
}bool Empty(SqStack& S) {if (S.top == -1)return true;return false;
}//判断链表是否中心对称
bool res(LinkList &L, SqStack &S, int n) {LNode* p = L->next;for (int i = 0; i < n / 2; i++) {S.data[++S.top] = p->data; //压入栈p = p->next;}if (n % 2 != 0) //如果n为奇数p = p->next; //让p指向后半段首位置while (p != NULL && p->data == S.data[S.top]) {S.top-=1;p = p->next;}if (Empty(S) && p==NULL)return true;elsereturn false;
}int main() {// 1.定义一个单链表LinkList L;int n;cout << "请输入链表的长度：" << endl;cin >> n;cout << "请输入单链表中的字符：" << endl;InitList(L,n);// 2.定义一个栈SqStack S;InitStack(S);// 3.中心对称字符串cout << "单链表是否中心对称(0/1)：" << res(L, S, n) << endl;system("pause");return 0;
}