[數(shù)據(jù)結(jié)構(gòu)習(xí)題]棧——中心對(duì)稱鏈

👉知識(shí)點(diǎn)導(dǎo)航💎：【數(shù)據(jù)結(jié)構(gòu)】棧和隊(duì)列

👉[王道數(shù)據(jù)結(jié)構(gòu)]習(xí)題導(dǎo)航💎：$page70.4$

本節(jié)為棧和鏈表綜合練習(xí)題

---

題目描述：

🎇思路：前段進(jìn)棧

🔱思路分析：

要判斷一個(gè)帶頭結(jié)點(diǎn)的單鏈表是否中心對(duì)稱，即鏈表的前半部分和后半部分互為逆序關(guān)系，因此，由棧的先進(jìn)后出特性可以實(shí)現(xiàn)逆序

step:

因?yàn)樯婕版湵砗蜅?#xff0c;我們需要分別實(shí)現(xiàn)相關(guān)的操作：

1. 單鏈表實(shí)現(xiàn)

①定義結(jié)構(gòu)體：

typedef struct LNode { //定義一個(gè)單鏈表char data;struct LNode* next;
}LNode,*LinkList;

②初始化：

void InitList(LinkList& L, int n) {L = (LNode*)malloc(sizeof(LNode)); //頭結(jié)點(diǎn)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. 順序棧實(shí)現(xiàn)

①定義結(jié)構(gòu)體

我們選擇用順序棧來實(shí)現(xiàn)

其中 $data$ 為字符串?dāng)?shù)組，$top$ 為棧頂指針

#define Maxsize 50typedef struct SqStack { //定義一個(gè)棧char data[Maxsize];int top;
}SqStack;

②初始化&判空

由于 $S.top$ 指向的是棧頂元素，而當(dāng)?？諘r(shí)：$S.top=?1$，以此來實(shí)現(xiàn)初始化與判空

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

3. 中心對(duì)稱鏈的判斷

做完了前期準(zhǔn)備之后，我們就要判斷鏈?zhǔn)欠裰行膶?duì)稱了

算法思想：使用棧來判斷鏈表中的數(shù)據(jù)元素是否中心對(duì)稱，首先，讓單鏈表的前半段元素放入棧中，在處理鏈表的后半段元素時(shí)，每訪問鏈表的一個(gè)元素，就讓棧彈出棧頂元素與之進(jìn)行比較，若相等，則繼續(xù)判斷后續(xù)元素，直到鏈表后半段的元素全部比較完成，此時(shí)，若棧為空，則為中心對(duì)稱鏈；否則，不成立

圖解算法：

①前段元素進(jìn)棧

由于已知鏈表的長(zhǎng)度為 $n$，因此，只需要遍歷 $?\frac{n}{2}?$ 次即遍歷完成前半段所有元素

指針 $p$ 最初指向首結(jié)點(diǎn)，每訪問到一個(gè)鏈表結(jié)點(diǎn)，便將其壓入棧中：S.data[++S.top]=p->data

代碼實(shí)現(xiàn)：

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

結(jié)束時(shí)，如果鏈表長(zhǎng)度 $n$ 為偶數(shù)，則指針 $p$ 直接指向后半段的首結(jié)點(diǎn)；若鏈表長(zhǎng)度為奇數(shù)，則指向中心結(jié)點(diǎn)，此時(shí)需要讓：p=p->next

if (n % 2 != 0) //如果n為奇數(shù)p = p->next; //讓p指向后半段首位置

②前段元素出棧

當(dāng)前狀態(tài)為：

不斷比較 S.data[S.top] 和 p->next 直到 $p==NULL$，如果此時(shí)棧為空且指針$p$指向$NULL$，則說明中心對(duì)稱

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

代碼實(shí)現(xiàn)：

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

完整代碼實(shí)現(xiàn)；

#include<iostream>
#define Maxsize 50
using namespace std;typedef struct LNode { //定義一個(gè)單鏈表char data;struct LNode* next;
}LNode,*LinkList;void InitList(LinkList& L, int n) {L = (LNode*)malloc(sizeof(LNode)); //頭結(jié)點(diǎn)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 { //定義一個(gè)棧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;
}//判斷鏈表是否中心對(duì)稱
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為奇數(shù)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.定義一個(gè)單鏈表LinkList L;int n;cout << "請(qǐng)輸入鏈表的長(zhǎng)度：" << endl;cin >> n;cout << "請(qǐng)輸入單鏈表中的字符：" << endl;InitList(L,n);// 2.定義一個(gè)棧SqStack S;InitStack(S);// 3.中心對(duì)稱字符串cout << "單鏈表是否中心對(duì)稱(0/1)：" << res(L, S, n) << endl;system("pause");return 0;
}

輸出結(jié)果：

---

?

🎇這是一道棧和鏈表的綜合練習(xí)題，不是很難，但有利于知識(shí)點(diǎn)的回顧~🎇

如有錯(cuò)誤，歡迎指正~！