C++基于栈实现铁轨问题

本文实例讲述了C++基于栈实现铁轨问题。分享给大家供大家参考。具体分析如下：

示例图如下所示：

经典栈问题！第一次做的时候思路太混乱了，现在看了刘汝佳的书，重新整理下。

#include <stdio.h>
#include <string.h>
/******************************************************************
* 用数组A存储调整前的车厢号序列，用数组B存储调整好的车厢号序列
* 用栈stack存储存放在中转站C中的车厢
*  用ix_A指向A中最前面的车厢，用ix_B指向B中最前面的车厢
*
*  如果ix_B已经指向了\0，则说明所有车厢已经按指定次序出站，否则
*  如果ix_B指向的车厢等于ix_A指向的车厢，则直接把ix_A开到B,否则
*  如果ix_B指向的车厢等于stack中的栈元素，则把栈顶车厢开出,否则
*  如果此时A中还有车厢，则把A开入中转站C中,否则
*  输出无解。
*******************************************************************/
char stack[1010];
char A[1010];
char B[1010];
int main(int argc, char *argv[])
{
 scanf("%s%s",A,B);
 int len_a = strlen(A);
 int len_b = strlen(B);
 /* 初始化栈 */
 int top = -1;
 int tot = 0;
 int ix_a = 0;
 int ix_b = 0;
 while(1)
 {
  if(A[ix_a] == B[ix_b])
  {
   printf("in\n");
   printf("out\n");
   ++ix_b;
   ++ix_a;
   if(ix_b == len_b) /* 车已经全出去了，操作成功 */
    break;
  }
  else if(tot != 0 /* 先检查栈是否为空 */ && B[ix_b] == stack[top])
  {
   printf("out\n");
   --tot;
   --top;
   ++ix_b;
   if(ix_b == len_b)
    break;
  }
  else if(ix_a != len_a)
  {
   printf("in\n");
   ++tot;
   ++top;
   stack[top] = A[ix_a];
   ++ix_a;
   if(ix_b == len_b)
    break;
  }
  else
  {
   printf("无解！\n");
   return 0;
  }
 }
 printf("完成！\n");
 return 0;
}

希望本文所述对大家的C++程序设计有所帮助。

赞 (0)

相关推荐

  • C++中实现队列类链式存储与栈类链式存储的代码示例

    队列类链式存储 代码: linkqueue.hpp // 队列类 #pragma once #include "linklist.hpp" template <typename T> class LinkQueue { public: LinkQueue(); ~LinkQueue(); public: int clear(); int append(T &t); int retieve(T &t); int header(T &t); int le

  • C++中栈结构建立与操作详细解析

    C++中栈结构建立与操作详细解析

    什么是栈结构 栈结构是从数据的运算来分类的,也就是说栈结构具有特殊的运算规则,即:后进先出. 我们可以把栈理解成一个大仓库,放在仓库门口(栈顶)的货物会优先被取出,然后再取出里面的货物. 而从数据的逻辑结构来看,栈结构起始就是一种线性结构. 如果从数据的存储结构来进一步划分,栈结构包括两类:顺序栈结构: 即使用一组地址连续的内存单元依次保存栈中的数据.在程序中,可以定义一个指定大小的结构数组来作为栈,序号为0的元素就是栈低,再定义一个变量top保存栈顶的序号即可.链式栈结构: 即使用链表的的形式

  • C++使用一个栈实现另一个栈的排序算法示例

    本文实例讲述了C++用一个栈实现另一个栈的排序算法.分享给大家供大家参考,具体如下: 题目: 一个栈中元素类型为整型,现在想将该栈从顶到底按从小到大的顺序排序,只许申请一个辅助栈. 除此之外,可以申请新的变量,但不能申请额外的数据结构.如何完成排序? 算法C++代码: class Solution { public: //借助一个临时栈排序源栈 static void sortStackByStack(stack<int>& s) { stack<int>* sTemp =

  • C/C++函数调用栈的实现方法

    本文实例讲述了C/C++函数调用栈的实现方法.可用于实现简单的脚本解释器.分享给大家供大家参考.具体实现方法如下: 头文件声明部分: 复制代码 代码如下: #pragma once const int BUFFERSIZE = 1024; const int growfactor = 2;   // this stack is used as call stack. class TStack{ private: size_t size;   // the stack length size_t

  • C++ 基数排序的实现实例代码

    C++ 基数排序的实现实例代码

    C++ 基数排序 大家好,今天带来的是自己实现的用C++完成基数排序.在数据结构,算法分析和程序设计的学习过程中,我们经常也无法避免的要学到排序的算法.排序算法是程序设计过程中使用频率极高的算法之一,其输入是一组无序的序列,要求以升序或者降序的方式输出一组有序的序列.对于如二分查找等算法,要求输入是有序的序列,也就是要先排序后查找,由此可见排序算法的重要性. 广为人知的排序算法有冒泡排序,还有选择排序,插入排序.高级一些的有快速排序,希尔排序,堆排序,归并排序,基数排序等. 其中时间复杂度为O(

  • C++利用链栈实现表达式求值

    本文实例为大家分享了C++利用链栈实现表达式求值的具体代码,供大家参考,具体内容如下 #include<iostream.h> typedef int Status; typedef char Cstack; #define OK 1 #define ERROR 0 typedef struct StackNode { Cstack data; struct StackNode *next; }StackNode,*LinkStack; Status InitStack(LinkStack &

  • 用C++实现一个链式栈的实例代码

    自定义一个链式栈,c++语言实现,不足之处,还望指正! 复制代码 代码如下: // MyStack.cpp : 定义控制台应用程序的入口点.//自己构造一个链式栈,具有push(入栈),pop(出栈),top(取得栈顶元素),size(返回栈大小),empty(判断是否为空)等功能#include "stdafx.h"#include <iostream>using namespace std;//构造栈的节点template <class T>struct N

  • C++实现单链表按k值重新排序的方法

    本文实例讲述了C++实现单链表按k值重新排序的方法.分享给大家供大家参考,具体如下: 题目要求: 给定一链表头节点,节点值类型是整型. 现给一整数k,根据k将链表排序为小于k,等于k,大于k的一个链表. 对某部分内的节点顺序不做要求. 算法思路分析及代码(C) 思路:将链表分为小于k.等于k.大于k的三个链表,然后再合并. 链表结点定义: typedef struct Node { int data; struct Node* next; }node, *pNode; 算法代码: pNode s

  • c/c++堆栈分布及其设置方法

    一个由C/C++编译的程序占用的内存分为以下几个部分1.栈区(stack)- 由编译器自动分配释放 ,存放函数的参数名,局部变量的名等.其操作方式类似于数据结构中的栈.2.堆区(heap)- 由程序员分配释放, 若程序员不释放,程序结束时可能由OS回收.注意它与数据结构中的堆是两回事,分配方式倒是类似于链表.3.全局区(静态区)(static)-全局变量和静态变量的存储是放在一块的,初始化的全局变量和静态变量在一块区域, 未初始化的全局变量和未初始化的静态变量在相邻的另一块区域.程序结束后由系统

  • C++中用栈来判断括号字符串匹配问题的实现方法

    本文实例主要实现:输入一个括号字符串,依次检验,若为左括号则入栈,若为右括号则出栈一个字符判断是否与之相对应,在最后还需判断栈是否为空,如果不为空则不匹配. 首先回顾栈的基本知识: 1.定义栈的结构体并初始化一个新栈: struct stack { char strstack[stacksize]; int top; }; void InitStack(stack &s) { s.top=-1; } 2.出栈和入栈操作: char Push(stack &s,char a) { if(s.

  • C++ 字符串去重排序实例代码

    C++ 字符串去重排序实例代码

     C++ 字符串去重排序实例代码 入一个字符串,去掉重复出现的字符,并把剩余的字符串排序输出. 实现代码: #include <iostream> #include <string> using namespace std; void sort(string s) { char tmp[100]; int len=s.size(); int count=0,i,j; for (i=0;i<len;i++) { for (j=i+1;j<len;j++) { if (s[

随机推荐