datawhale算法与数据结构（上）day3-栈与递归

程序员文章站 2022-03-10 19:54:32

...

datawhale算法与数据结构（上）day3-栈与递归

task03: 栈与递归

用数组实现一个顺序栈
用链表实现一个链栈
理解递归的原理

理论部分

一、栈

定义
栈是线性表，但是限定仅在表尾进行插入或删除操作。表尾称为栈顶，尾头端称为栈底。

退栈的第一个元素为栈顶元素，栈的修改是按后进先出的原则进行的。因此栈又被称为后进先出的线性表（LIFO结构）。这个特点可以用铁路调度站形象的表示。
用数组实现顺序栈

/*
栈的数组实现
*/
 
#include<iostream>
using namespace std;
 
#define MAXSIZE 10;
 
template<class T>
class Stack
{
public:
	//默认构造函数
	Stack();
 
	Stack(size_t maxElements);
	Stack(T data[],size_t maxElments);
	~Stack();
 
	//入栈
	void Push(T data);
 
	//出栈并返回
	T Pop();
 
	//返回栈顶元素
	T Top();
 
	//判断是否为空栈
	bool isEmpty();
 
	//栈是否已满
	bool isFull();
 
	//清空栈
	void Clear();
 
	//获得栈里元素的个数
	size_t GetSize();
 
private:
	//栈标指示器
	size_t top;
 
	//数组
	T *arrays;
 
	//栈的容量
	size_t maxSize;
};
 
template<class T>
Stack<T>::Stack():
	maxSize(MAXSIZE),top(-1)
{
	arrays=new T[maxSize];
	if(arrays==NULL)
		cout<<"动态分配内存失败";
}
 
template<class T>
Stack<T>::Stack(size_t maxElements):
	maxSize(maxElements),top(-1)
{
	arrays=new T[maxSize];//创建存储栈的数组
}
 
template<class T>
Stack<T>::Stack(T data[],size_t maxElements):
	maxSize(maxElements),top(-1)
{
	arrays=new T[maxSize];//创建存储栈的数组
 
	for(size_t i=0;i<maxSize;i++)
	{
		arrays[i]=data[i];
	}
	top+=maxSize;
}
 
template<class T>
Stack<T>::~Stack()
{
	delete[] arrays;
}
 
template<class T>
void Stack<T>::Push(T data)
{
	if(isFull())
	{
		throw runtime_error("Full stack");
	}
	else
	{
		top++;//指向栈顶
		arrays[top]=data;	
	}
}
 
template<class T>
T Stack<T>::Pop() 
{
	if(isEmpty())
	{
		throw runtime_error("No elements in the stack");
	}
	else
	{
		T data=arrays[top];
		top--;
		return data;
	}
}
 
template<class T>
T Stack<T>::Top()
{
	if(isEmpty())
	{
		throw runtime_error("No elements in the stack");
	}
	else
	{
		return arrays[top];
	}
}
 
template<class T>
bool Stack<T>::isEmpty()
{
	return top==-1;
}
 
template<class T>
bool Stack<T>::isFull()
{
	return top==maxSize-1;
}
 
template<class T>
void Stack<T>::Clear()
{
	while (top!=-1)
	{
		top--;
	}
}
 
template<class T>
size_t Stack<T>::GetSize()
{
	return top+1;
}
 
int main()
{
	/*别忘了捕获异常*/
	try
	{
		/*测试*/
		int a[6]={2,4,3};
		Stack<int> s(a,6);
 
		s.Pop();
		s.Push(5);
 
		for(int i=0;i<6;i++)
			cout<<s.Pop()<<" ";
 
	}
	catch(exception e)
	{
		cout<<e.what()<<endl;
	}
 
	cout<<endl;
	system("pause");
	return 0;
}

用链表实现链栈

#include <iostream>
using namespace std;
 
 
template <class T>
class LinkStackNode {
public:
	T data;
	LinkStackNode<T>* next;
	LinkStackNode(T& d) : data(d), next(NULL){}
};
 
 
template <class T>
class LinkStack {
public:
	LinkStack() : top(NULL){}
	~LinkStack();
	void push(T& value);
	T& getTop();
	T pop();
	bool isEmpty();
private:
	LinkStackNode<T> * top;
};
 
 
template <class T>
LinkStack<T>::~LinkStack() {
	delete top;
}
 
template <class T>
void LinkStack<T>::push(T& value) {
	LinkStackNode<T>* addNode = new LinkStackNode<T>(value);
	addNode->next = top;
	top = addNode;
}
 
 
template <class T>
T& LinkStack<T>::getTop()
{
	return top->data;
}
 
 
template <class T>
T LinkStack<T>::pop()
{
	T value = top->data;
	LinkStackNode<T>* p = top;
	top = top->next;
	delete p;
	return value;
}
 
 
template <class T>
bool LinkStack<T>::isEmpty()
{
	return top == NULL;
}

二、递归

一个直接调用自己或通过一系列的调用语句间接地调用自己地函数，称作递归函数。最典型的就是汉诺塔问题和实现Fibonacci数列

练习

根据要求完成车辆重排的程序代码

假设一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1至n，货运列车按照第n站至第1站的次序经过这些车站。车厢的编号与它们的目的地相同。为了便于从列车上卸掉相应的车厢，必须重新排列车厢，使各车厢从前至后按编号1至n的次序排列。当所有的车厢都按照这种次序排列时，在每个车站只需卸掉最后一节车厢即可。

我们在一个转轨站里完成车厢的重排工作，在转轨站中有一个入轨、一个出轨和k个缓冲铁轨（位于入轨和出轨之间）。图（a）给出一个转轨站，其中有k个（k=3）缓冲铁轨H1，H2 和H3。开始时，n节车厢的货车从入轨处进入转轨站，转轨结束时各车厢从右到左按照编号1至n的次序离开转轨站（通过出轨处）。在图（a）中，n=9，车厢从后至前的初始次序为5，8，1，7，4，2，9，6，3。图（b）给出了按所要求的次序重新排列后的结果。
datawhale算法与数据结构（上）day3-栈与递归
编写算法实现火车车厢的重排，模拟具有n节车厢的火车“入轨”和“出轨”过程。

#include "RailRoad.h"
using std::cout;
using std::cin;
 
bool RailRoad(int r[], int n, int k)
{
      LinkedStack<int> *H;
      H = new LinkedStack<int>[k + 1];
     int NowOut = 1;//可以直接移入出轨的车厢号
     int MinH = n+2;//缓冲轨顶部最小的车厢号
     int MinS;//最小车厢号的缓冲轨号
     for (int i = 0; i < n;++i)
     {
         if (r[i]==NowOut)
         {
             cout << "将车厢" << NowOut << "从入轨直接移动到出轨" << std::endl;
             ++NowOut;
             while (MinH == NowOut)//检查缓冲轨最小车厢号，相等则输出
             {
                 output(MinH, MinS, H, k, n);
                 ++NowOut;
             }
         }
         else
         {
             if(!movetocache(MinH, MinS, H, k, n, r[i]))
             {
                 return false;
             }
         }            
     }
 
     return true;
 }

//复杂度O（k）
void output(int& MinH, int& MinS, LinkedStack<int> *H, int k, int n)
 {
     cout << "将车厢" << MinH << "从缓冲轨" << MinS << "移动到出轨上" << std::endl;
     H[MinS].Delete(MinH);
     MinH = n + 2;
     for (int i = 1; i < k + 1;++i)
     {
         if (!H[i].IsEmpty() && H[i].Top()<MinH)
         {
             MinH = H[i].Top();
             MinS = i;
         }
     }
 }

//复杂度O（k）
bool movetocache(int &MinH, int &MinS, LinkedStack<int>* H, int k, int n, int num)
 {
     
     int besttrack = 0;
     int BestTop = n + 1;
     int x;
     for (int i = 1; i < k + 1;++i)
     {
         if (H[i].IsEmpty())
         {
             H[i].Add(num);
             cout << "将车厢" << num << "移动到缓冲轨" << i << std::endl;
             if (num < MinH)
             {
                 MinH = num;
                 MinS = i;
             }
             return true;
         }
 
         x = H[i].Top();
         if (num<x&&x<BestTop)
         {
             BestTop = x;
             besttrack = i;
         }
     }
 
     if (!besttrack)
     {
         return false;
     }
 
     H[besttrack].Add(num);
     cout << "将车厢" << num << "移动到缓冲轨" << besttrack << std::endl;
     if (num < MinH)
     {
         MinH = num;
         MinS = besttrack;
     }

    return true;
}

【来源】
[1] 数据结构（C语言版）
[2] https://blog.csdn.net/typist_/article/details/45116843
[3] https://blog.csdn.net/liutianjia2014/article/details/45694637
[4] https://www.cnblogs.com/haoliuhust/p/4261182.html

datawhale算法与数据结构（上）day3-栈与递归