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

这篇具有很好参考价值的文章主要介绍了[数据结构习题]栈——中心对称链。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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



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

👉[王道数据结构]习题导航💎: 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

到了这里,关于[数据结构习题]栈——中心对称链的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】数组和字符串(三):特殊矩阵的压缩存储:三角矩阵、对称矩阵——一维数组

    【数据结构】数组和字符串(一):矩阵的数组表示   矩阵是以按行优先次序将所有矩阵元素存放在一个一维数组中。但是对于特殊矩阵,如对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等, 如果用这种方式存储,会出现大量存储空间存放重复信息或零元素的情况,这样会造

    2024年02月08日
    浏览(52)
  • 数据结构习题9---查找

    一、填空题 1 .   在数据的存放无规律而言的线性表中进行检索的最佳方法是    顺序查找(线性查找)    。 2 . 线性有序表( a 1 , a 2 , a 3 ,…, a 256 ) 是从小到大排列的,对一个给定的值k,用二分法检索表中与k相等的元素,在查找不成功的情况下,最多需要检索   

    2024年02月09日
    浏览(63)
  • 数据结构习题集

    目录 第一章 绪论 一 选择题。  二 填空题。 第二章.线性表 一 选择题。 二 填空题。 第三章.栈、队列 一 选择题。 二 填空题。 第六章.树与二叉树 一 选择题。 二 填空题。 三 简答题。 第七章.图 一 选择题。 二 填空题。 三 简答题。 第九章.查找 一 选择题。 二

    2024年02月07日
    浏览(53)
  • 数据结构习题7---图

    一、单选题                   (   C  )1. 在一个图中,所有顶点的度数之和等于图的边数的        倍。              A. 1/2            B.  1             C.  2             D.  4   (   B   )2. 在一个有向图中,所有顶点的入度之和等于所有

    2024年02月06日
    浏览(41)
  • 数据结构——图(习题篇)

    本文会挑选图中 相关例题 进行讲解,并复习相关的知识点 建议先将题做一次,再看题解和答案 题1 设图的邻接矩阵如下所示,各顶点的度依次是( ) A.1,2,1,2 B.2,2,1,1 C.3,4,2,3 D.4,4,2,2 [ 0 1 0 1 0 0 1 1 0 1 0 0 1 0 0 0 ] left[ begin{matrix} 0 1 0 1\\\\ 0 0 1 1\\\\ 0 1 0 0\\\\ 1 0 0 0 end{matrix} right] ​ 0 0

    2024年01月19日
    浏览(49)
  • 【数据结构】——图的相关习题

    1、具有n个顶点的有向完全图有()条弧边。 A、n(n-1)/2 B、n(n-1) C、n(n+1)/2 D、n(n+1) 解析: (B) 若一个有向图中,若每个顶点都有互相相反的两条弧连接,则称为有向完全图,在一个含有n个顶点的有向完全图中,共有 n(n-1) 条弧。 例如,含有4个顶点的有向完全图

    2024年02月05日
    浏览(48)
  • 【数据结构】复习题(一)

    一、选择题 1.组成数据的基本单位是()。 A. 数据项 B.数据类型 C.数据元素 D.数据变量 2.设数据结构A={D,R},其中D={1,2,3,4},R={r},r={1,2,2,3, 3,4,4,1},则数据结构A是()。 A.线性结构 B.树型结构 C.图型结构 D.集合 3.数组的逻辑结构不同于下列()的逻辑结构。 A.线性表 B.栈 C.队列 D.树 4.二

    2024年02月04日
    浏览(43)
  • 数据结构习题24/12/24

    这道题目可以考虑,如果前缀是一样的长度,那么只需要两个链表同时向后检索,直到找到一样的元素为止。所以应该先找到两个链表的长度,然后将较长的一个链表的多出来的前缀部分删掉,也就不去看这一部分。因为后缀都是一样的,所以长度的差异只可能来自前缀。

    2024年02月04日
    浏览(41)
  • 【数据结构】第二章课后练习题——线性结构

    1、线性表是 一个有限序列,可以为空 2、链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素,则采用 单循环链表 存储方式最节省运算时间 3、若某线性表中最常用的操作实在最后一个元素之后插入一个元素和删除第一个元素,则采用 仅有尾结点的

    2024年02月07日
    浏览(57)
  • 【数据结构】——栈、队列的相关习题

    1、栈和队列都是()。 A、顺序存储的线性结构 B、链式存储的非线性结构 C、限制存取点的线性结构 D、限制存取点的非线性结构 解析: (C) 栈 是一种只允许在一端进行插入或删除操作的线性表,它是一种特殊的线性表,它与队列具有相同的逻辑结构,都属于 线性结构

    2024年02月12日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包