[数据结构习题]栈——中心对称链
👉知识点导航💎:【数据结构】栈和队列
👉[王道数据结构]习题导航💎: p a g e 70.4 page70.4 page70.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 data data 为字符串数组, t o p top top 为栈顶指针
#define Maxsize 50
typedef struct SqStack { //定义一个栈
char data[Maxsize];
int top;
}SqStack;
②初始化&判空
由于 S . t o p S.top S.top 指向的是栈顶元素,而当栈空时: S . t o p = − 1 S.top=-1 S.top=−1,以此来实现初始化与判空
void InitStack(SqStack& S) {
S.top = -1; //初始化栈顶
}
bool Empty(SqStack& S) {
if (S.top == -1)
return true;
return false;
}
3. 中心对称链的判断
做完了前期准备之后,我们就要判断链是否中心对称了
算法思想:使用栈来判断链表中的数据元素是否中心对称,首先,让单链表的前半段元素放入栈中,在处理链表的后半段元素时,每访问链表的一个元素,就让栈弹出栈顶元素与之进行比较,若相等,则继续判断后续元素,直到链表后半段的元素全部比较完成,此时,若栈为空,则为中心对称链;否则,不成立
图解算法:
①前段元素进栈
由于已知链表的长度为 n n n,因此,只需要遍历 ⌊ n 2 ⌋ ⌊\frac{n}{2}⌋ ⌊2n⌋ 次即遍历完成前半段所有元素
指针
p
p
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
n
n 为偶数,则指针
p
p
p 直接指向后半段的首结点;若链表长度为奇数,则指向中心结点,此时需要让:p=p->next
if (n % 2 != 0) //如果n为奇数
p = p->next; //让p指向后半段首位置
②前段元素出栈
当前状态为:
不断比较 S.data[S.top]
和 p->next
直到
p
=
=
N
U
L
L
p==NULL
p==NULL,如果此时栈为空且指针
p
p
p指向
N
U
L
L
NULL
NULL,则说明中心对称
防止中间存在元素不相等而提前退出
代码实现:
while (p != NULL && p->data == S.data[S.top]) {
S.top-=1;
p = p->next;
}
if (Empty(S) && p==NULL)
return true;
else
return 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;
else
return 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;
}
输出结果:
文章来源:https://www.toymoban.com/news/detail-466966.html
文章来源地址https://www.toymoban.com/news/detail-466966.html
到了这里,关于[数据结构习题]栈——中心对称链的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!