著名建筑设计网站,开发网站需求设计,工程公司管理制度,北京网站建设方案外包[数据结构习题]栈——中心对称链 #x1f449;知识点导航#x1f48e;#xff1a;【数据结构】栈和队列
#x1f449;[王道数据结构]习题导航#x1f48e;#xff1a; p a g e 70.4 page70.4 page70.4 本节为栈和链表综合练习题 题目描述#xff1a; #x1f387;思路…[数据结构习题]栈——中心对称链 知识点导航【数据结构】栈和队列
[王道数据结构]习题导航 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 50typedef 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 直接指向后半段的首结点若链表长度为奇数则指向中心结点此时需要让pp-next
if (n % 2 ! 0) //如果n为奇数p p-next; //让p指向后半段首位置②前段元素出栈
当前状态为 不断比较 S.data[S.top] 和 p-next 直到 p N U L L pNULL pNULL如果此时栈为空且指针 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) pNULL)return true;elsereturn false;完整代码实现
#includeiostream
#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) pNULL)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;
}输出结果 这是一道栈和链表的综合练习题不是很难但有利于知识点的回顾~ 如有错误欢迎指正~
