笔记.txt

用栈表示汉诺塔
//text.h
#ifndef _TEXT_H_
#define _TEXT_H_
#include<iostream>
template <class Type> class LStack;
template <class Type> class Node {
	friend class LStack<Type>;
	Type data;
	Node <Type> *link;
};
template <class Type> class LStack {
private:
	Node <Type> *top;
public:
	LStack() { top = NULL; }
	void push(Type x) {
		Node <Type> *p;
		p = new Node <Type>;
		p->data = x; p->link = top; top = p;
	}
	int empty()
	{
		if (top == NULL)
			return 1;
		else return 0;
	}
	Type gettop()
	{
		if (top == NULL) { cout << "No elements" << endl; return 0; }
			return top->data;
	}

	int pop(Type *x) {
		
		Node <Type> *p;
		if (top == NULL) return -1;
		*x = top->data; p = top; top = top->link; delete p;
		return 0;
	}
	~LStack() {
		while (top != NULL) {
			Node <Type> *p = top;
			top = top->link;
			delete p;
		}
	}
};
#endif

//源.cpp
#include"text.h"
#include<iostream>
using namespace std;

int main()
{
	int n, A, B, C;
	LStack<int>  s;
	int m=0,*p;
	p = &m;
	cin >> n >> A >> B >> C;
	s.push(n);
	s.push(A);
	s.push(B);
	s.push(C);
 	while (1)
	{		
		if (s.pop(&C)==-1) break;
		s.pop(&B);
		s.pop(&A);
		s.pop(&n);
		if (n == 1) cout << A << "->" << C << endl;
		else {
			s.push(n - 1);
			s.push(B);
			s.push(A);
			s.push(C);
			s.push(1);
			s.push(A);
			s.push(B);
			s.push(C);
			s.push(n-1);
			s.push(A);
			s.push(C);
			s.push(B);
		}
	}
	return 0;
}

//ackerman函数
int main()
{
	int m=0, n;
	LStack<int>  mm;
	cin >> m >> n;
	mm.push(m);
	while (mm.pop(&m) != -1)
	{
	
		if (m == 0) n++;
		else {
			if (n == 0)
			{
				mm.push(m - 1);
				n = 1;
			}
			else {
				mm.push(m - 1);
				mm.push(m);
				n--;
			}
		}
	}
	cout << n << endl;
	return 0;
}

//堆排序 l=0,r=n-1
void fixdown(int a[],int k,int n)
{
	while (n >= 2 * k+1)
	{
		int i, j=2*k+1;
		if (j < n&&a[j] < a[j + 1]) j++;
		if (a[j] <= a[k]) break;
		i = a[j]; a[j] = a[k]; a[k] = i;
		k = j;
	}
}
void sort(int a[], int l, int r)
{
	int k, n = r - l+1 ;
	int t, *p = a + l ;
	for (k = (n-2 ) / 2; k >= l; k--)
		fixdown(p, k, n-1);
	while (n > 1)
	{
		t = p[0]; p[0] = p[n-1]; p[n-1] = t;
		fixdown(p, 0, (--n)-1);
	}
}
//快排
void exchange(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}
int partition(int a[], int l, int r)
{
	int i = l - 1, j = r,t=a[r];
	for (;;)
	{
		while (a[++i] < t);
		while (a[--j] > t) if (j == l) break;
		if (j <= i) break;
		exchange(a[i], a[j]);
	}
	exchange(a[i], a[r]);
	return i;
}
void quicksort(int a[], int l, int r)
{
	if (r <= l) return;
	int i = partition(a, l, r);
	quicksort(a, l, i - 1);
	quicksort(a, i + 1, r);
}

//二分查找
int twosearch(int a[], int i, int l, int r)
{
	while (r>=l) {
		int m = (l + r) / 2;
		if (a[m] == i) return 1;
		else {
			if (a[m] > i) r = m - 1;
			else l = m + 1;
		}
	}
	return 0;
}

//最大正方形
int a[3000][3000];
	int min(int a, int b, int c)
	{
		if (a < b) { return (a<c) ? a : c; }
		else { return (b<c) ? b : c; }
	}
	int main()
	{
		ifstream read("input.txt");
		ofstream write("output.txt");
		int m=1, n; int t, number; int i, j; bool in; 
		
			read  >> n; 
			for (i = 0; i <n; ++i)
			{
				for (j = 0; j < n; ++j)
				{
					read>> in; if (in) { a[i][j] = 0; }
					else { a[i][j] = 1; }
				}
			}
			for (i = 1; i < n; ++i)
			{
				for (j = 1; j < n; ++j)
				{
					if (a[i][j] != 0)

					{
						a[i][j] += min(a[i - 1][j], a[i - 1][j - 1], a[i][j - 1]);
					}
				}
			}

			int biggest = a[0][0];
			for (i = 0; i < n; ++i)
			{
				for (j = 0; j < n; ++j)

				{
					
					if (a[i][j] == biggest) { m++; }
					if (a[i][j] > biggest) { biggest = a[i][j];m=1; }
				}

			}
			write << biggest*biggest << " "<<m<<endl;
			read.close();
		 return 0;
	}

//建树
void findandset(string pre, string mid, BTNODE<char>& p)//build up a tree by two strings
{

	string a, b;
	char c = pre[0];

	p.data = c;

	char t; int i, j, m = 0, k;
	if (pre.length() == 2)
	{
		for (i = 0; mid[i] != '\0'; i++)
			if (mid[i] == c) break;
		if (i == 0)
		{
			p.fch = NULL;
			p.rch = new BTNODE<char>();
			p.rch->data = mid[1];
		}
		if (i == 1)
		{
			p.rch = NULL;
			p.fch = new BTNODE<char>();
			p.fch->data = mid[0];
		}
	}
	else if (pre.length() == 3)     ？？？只有一边呢？
	{
		p.fch = new BTNODE<char>();
		p.rch = new BTNODE<char>();
		p.fch->data = mid[0];
		p.rch->data = mid[2];
	}
	else {
		p.fch = new BTNODE<char>('a');

		p.rch = new BTNODE<char>('a');
		for (i = 0; mid[i] != '\0'; i++)
			if (mid[i] == c) break;

		for (j = 0; j < i; j++)
			for (k = 0; pre[k] != '\0'; k++)
				if ((mid[j] == pre[k]) && k>m)  m = k;

		a = pre.substr(1, m);             ???判别m是否合理再决定
		b = mid.substr(0, i);
		findandset(a, b, *(p.fch));

		a = pre.substr(m + 1, pre.length() - m - 1);
		b = mid.substr(i + 1, mid.length() - i - 1);
		findandset(a, b, *(p.rch));
	}
}