线性表
#pragma once
template<class T>
class LinearList//线性表抽象基类
{
public:
LinearList() {}; //构造函数
~LinearList; //析构函数
virtual int Size()const = 0; //求表最大体积
virtual int Length()const = 0; //求表长度
virtual int Search(T& x)const = 0; //求给定x下表（搜索）
virtual int Locate(int i)const = 0; //定位第i个元素的位置
virtual bool getDate(int i, T& x) = 0; //求第i个表项的值
virtual bool setDate(int i, T& x) = 0; //修改第i个表项的值
virtual bool Insert(int i, T& x) = 0; //在第i个位置插入
virtual bool Remove(int i, T& x) = 0; //删除第i个位置的值
virtual bool IsEmpty()const = 0; //判断表空
virtual bool IsFull()const = 0; //判断表满
virtual void Sort() = 0; //排序
virtual void input = 0; //输入
virtual void output() = 0; //输出
virtual LinearList<T>operator=(LinearList<T>& L) = 0;//复制
};
线性表的结构特点：除第一及最后一个元素外，每个结点都只有一个前趋和只有一个后继。
表长：元素总个数n
空表：n=0
线性起点：a1
线性终点：an
下标：是元素的序号，表示元素在表中的位置
表头：第一个元素
表尾：最后一个元素
顺序表
优点：
⑴ 无需为表示表中元素之间的逻辑关系而增加额外的存储空间；
⑵ 随机存取：可以快速地存取表中任一位置的元素。
缺点：
⑴ 插入和删除操作需要移动大量元素；
⑵ 表的容量难以确定，表的容量难以扩充；
⑶ 造成存储空间的碎片。
// 顺序表.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include<stdlib.h>
#include"linearList.h"
using namespace std;
const int defaultSize = 100;
template<class T>
class SeqList :public LinearList<T> //顺序表
{
protected:
T* data; //存放数组
int maxSize; //最大项数,项数！！！
int last; //最后位置下标，初始化为-1
void reSize(int newSize); //改变数组大小
public:
SeqList(int sz = defaultSize);
SeqList(SeqList<T>& L); //复制构造函数
~SeqList() { delete[] data; }
int Size()const { return maxSize; } //最大可容纳表项个数,用const更加安全
int Length()const { return last + 1; } //计算表长度，const：不能改变数据成员的值，
//const成员函数不能调用非const成员函数
int Search(T& x)const; //搜索x在表中的位置，函数返回表项序号
int Locate(int i)const; //搜索第i个表项，函数返回表项序号
bool getData(int i, T& x)const //取第i个表项的值,复制给x
{
if (i > 0 && i <= last + 1)
{
x = data[i - 1];
return true;
}
else
return false;
}
void setData(int i, T& x) //修改第i个表项的值
{
if (i > 0 && i <= last + 1)data[i - 1] = x;
}
bool Insert(int i, T & x); //用x来修饰第i个表项的值
bool Remove(int, T & x); //删除第i个表项，通过x返回表项的值
bool IsEmpty()
{
return(last == -1) ? true : false; //判断表项是否为空
}
bool IsFull()
{
return(last == maxSize - 1) ? true : false;//判断表满
}
void input(); //输入建立顺序表
void output(); //输出
SeqList<T>operator=(SeqList<T> & L); //表整体赋值
};
//构造函数和复制构造函数
template<class T>
SeqList<T>::SeqList(int sz)
{
if (sz > 0)
{
maxSize = sz;
last = -1;
data = new T[maxSize]; //顺序表动态存储数组
if (data == NULL)
{
cerr << "存储分配失败！" << endl;
exit(1);
}
}
}
template<class T>
SeqList<T>::SeqList(SeqList<T> & L) //复制构造函数创建L
{
maxSize = L.Size();
last = L.Length() - 1;
T value;
data = new T[maxSize]; //顺序表动态存储数组
if (data = NULL)
{
cerr << "内存分配错误" << endl;
exit(1);
}
for (int i = 1; i <= last; i++) //i是逻辑位置
{
L.getData(i, value);
data[i - 1] = value;
}
}
template<class T>
void SeqList<T>::reSize(int newSize) //改变数组大小,扩大存储容量
{
if (newSize == 0)
{
cerr << "无效的数组大小" << endl;
return;
}
if (newSize != maxSize) //修改
{
T* newarray = new T[newSize]; //新建数组
if (newarray == NULL)
{
cerr << "存储分配错误" << endl;
exit(1);
}
int n = last + 1;
T* srcptr = data; //源数组首地址
T* destptr = newarray; //目的数组首地址
while (n--)
{
*destptr++ = *srcptr++; //复制
}
delete[]data; //删除老数组
data = newarray; //data指向新数组
maxSize = newSize; //改变masSize
}
}
template<class T>
int SeqList<T>::Search(T & x)const //搜索
{
for (int i = 0; i <= last; i++)
{
if (x == data[i])
return i + 1;
}
return -1;
}
template<class T>
int SeqList<T>::Locate(int i)const //定位
{
if (i < last + 1 && i >= 0)
return i - 1;
return -1;
}
template<class T>
bool SeqList<T>::Insert(int i, T & x) //插入操作,插入数字作为第i个
{
if (last == maxSize - 1)
return false;
if (i <= 0 || i >= maxSize)
return false;
for (int j = last; j >= i; j--)
data[j + 1] = data[j];
data[i] = x;
last++; //这个很重要！！！
return true;
}
template<class T>
bool SeqList<T>::Remove(int i, T & x) //删除
{
if (last == -1)
return false;
if (i >= last + 1 || i < 1)
return false;
x = data[i - 1];
for (int j = i - 1; j < last; j++)
data[j] = data[j + 1];
data[last] = NULL;
last--;
return true;
}
template<class T>
void SeqList<T>::input() //输入建立顺序表
{
cout << "开始建立顺序表,请输入表中元素个数（不超过" << maxSize << "个)" << endl;
while (1)
{
cin >> last;
if (i >= maxSize)
break;
cout << "错误，输入元素个数最大为" << maxSize << "。" << endl;
}
for (int i = 0; i <= last; i++)
{
cout << "请输入第" << i + 1 << "个数:";
cin >> data[i];
}
}
template<class T>
void SeqList<T>::output() //将整个表输出
{
cout << "现在输出整个表，表中总共有" << last + 1 << "项元素，下面是各项元素:" << endl;
for (int i = 0; i <= last; i++)
cout << "#" << i + 1 << ":" << data[i] << endl;
}
template<class T>
SeqList<T> SeqList<T>::operator=(SeqList<T> & L)
{
maxSize = L.Size();
last = L.Length() - 1;
T value;
data = new T[maxSize]; //顺序表动态存储数组
if (data = NULL)
{
cerr << "内存分配错误" << endl;
exit(1);
}
for (int i = 1; i <= last; i++) //i是逻辑位置
{
L.getData(i, value);
data[i - 1] = value;
}
}
单链表
头指针:指向第一个结点的地址
尾标志：终端结点的指针域为空
空表：first=NULL
头结点：在单链表的第一个元素结点之前附设一个类型相同的结点，以便在表的不同位置，或空表和非空表处理统一。
存储特点：
（1）逻辑次序和物理次序不一定相同。
（2）元素之间的逻辑关系用指针表示。
顺序表和链表的比较：
空间性能是指某种存储结构所占用的存储空间的大小。
时间性能是指实现基于某种存储结构的基本操作（即算法）的时间复杂度。
//对链表的操作都是通过指针来的
#include<iostream>
#include"linearList.h"
#include<stdlib.h>
using namespace std;
template <class T>
struct LinkNode //结点类型定义
{
T data; //结点数据域
LinkNode<T>* Link; //链指针域
LinkNode(LinkNode<T>* ptr = NULL) { Link = ptr; }//初始化成员指针的构造函数
LinkNode(const T& item, LinkNode<T>* ptr = NULL)
{
data = item;
link = ptr;
}
};
template<class T>
class List :public LinearList<T>
{
protected:
LinkNode<T>* first;
public:
List() { first = new LinkNode<T>; } //构造函数
List(const T& x) { first = new LinkNode<T>(x); }//构造函数
List(List<T>& L); //复制构造函数
~List() { makeEmpty(); } // 析构函数
void makeEmpty(); // 制表为空表
int Length()const; //计算表长
LinkNode<T>* getHead()const { return first; } //返回头结点地址
LinkNode<T>* Search(T x); //搜索存有x的结点的地址
LinkNode<T>* Locate(int i); //定位第i个结点的地址
bool getData(int i, T& x)const; //返回第i个结点中的值
void setData(int i, T& x); //修改第i个结点中的值
bool Insert(int i, T& x); //在第i个元素后插入x
bool Remove(int i, T& x); //删除元素
bool IsEmpty()const //判断表空
{
return first->Link == NULL ? true : false;
}
bool IsFull()const { return false; } //判断表满
void Sort(); //排序
void input(); //输出
void output(); //输入
List<T>& operator=(List<T>& L); //重载复制函数
};
template<class T>
List<T>::List(List<T>& L) //复制构造函数
{
T value;
LinkNode<T>* scrptr = L.getHead(); //从头节点开始
LinkNode<T>* destptr = first = new LinkNode<T>; //初始化一个头结点
while (scrptr->Link != NULL)
{
value = scrptr->Link->data;
destprt->Link = new LinkNode<T>(value);
destptr = destptr->Link;
scrptr = scrptr->Link;
}
destptr->Link = NULL; //末尾结点处理
}
template<class T>
void List<T>::makeEmpty() // 制表为空表
{
LinkNode<T>* q;
while (first->Link != NULL) //当表不为空
{
q = first->Link;
first->Link = first->Link->Link;
delete q; //一个一个删
}
}
template<class T>
int List<T>::Length()const //计算表长
{
LinkNode* q = first->Link;
int count = 0;
while (p != NULL) //一个一个找直到表尾
{
p = p->Link;
count++;
}
return count;
}
template<class T>
LinkNode<T>* List<T>::Search(T x) //返回存有某个元素的结点的下标
{
LinkNode* q = first->Link;
while (q != NULL)
{
if (q->data == x)
return q;
q = q->Link;
}
if (q == NULL)
return NULL;
}
template<class T>
LinkNode<T>* List<T>::Locate(int i) //定位第i个结点的地址
{
if (i < 0)
return NULL;
LinkNode* current = first;
int k = 0;
while (current != NULL && k < i)
{
current = current->Link;
k++;
}
if (current == NULL)
return NULL;
else
return current;
}
template<class T>
bool List<T>::getData(int i, T & x)const //返回第i个结点的元素
{
if (i < = 0)
return NULL;
LinkNode<T> * current = Locate(i);
if (current == NULL)
return false;
else
{
x = current->data;
return true;
}
}
template<class T>
void List<T>::setData(int i, T & x) //重置第i个结点
{
if (i <= 0)
return;
LinkNode * current = Locate(i);
if (current == NULL)
return;
else
current->data = x;
}
template<class T>
bool List<T>::Insert(int i, T & x) //在第i个元素后插入x
{
if (i <= 0)
return false;
LinkNode * current = Locate(i);
LinkNode * p = new LinkNode<T>(x);
if (p == NULL)
{
cerr << "内存分配失败" << endl;
return false;
}
if (current == NULL)
return false;
p->Link = current->Link;
current->Link = p;
return true;
}
template<class T>
bool List<T>::Remove(int i, T & x) //删除第i个元素
{
LinkNode* current = Locate(i - 1);
LinkNode * p = current->Link;
if (i <= 1)
return false;
if (p == NULL || current == NULL)
return false;
current->Link = p->Link;
x = p->data;
delete p;
return true;
}
template<class T>
void List<T>::output()
{
LinkNode<T>* current = first->Link;
while (current != NULL)
{
cout << current->data << endl;
current = current - Link;
}
}
template<class T>
void List<T>::input()
{
cout << "开始建立单链表,请输入需要记录的数据个数" << endl;
int x, num = 0;
cin >> x;
if (x <= 0)return;
cout << "请依次输入需要记录的数据：" << endl;
LinkNode<T> * p = first;
T k;
while (1)
{
cin >> k;
LinkNode<T>* q = new LinkNode<T>(k);
p->Link = q;
p = p->Link;
num++;
if (num == x)
break;
}
q->Link = NULL;
}
template<class T>
List<T>& List<T>::operator=(List<T> & L)
{
T value;
LinkNode<T>* scrptr = L.getHead(); //从头节点开始
LinkNode<T>* destptr = first = new LinkNode<T>; //初始化一个头结点
while (scrptr->Link != NULL)
{
value = scrptr->Link->data;
destprt->Link = new LinkNode<T>(value);
destptr = destptr->Link;
scrptr = scrptr->Link;
}
destptr->Link = NULL; //末尾结点处理
}
template<class T>
void List<T>::Sort()
{
LinkNode<T>* scrptr, change, p;
scrptr = first->Link;
T q;
for (; scrptr->Link != NULL; scrptr = scrptr->Link)
{
change = scrptr;
for (p = change->Link; p != NULL; p = p->Link)
{
if (change->data > p->data)
change = p;
}
if (change != scrptr)
{
q = scrptr->data;
scrptr->data = change->data;
change->data = q;
}
}
return;
}
栈
问题 C: 火车出站
题目描述
铁路进行列车调度时，常把站台设计成栈式结构的站台，试问：
设有编号为1到n的n辆列车，顺序开入栈式结构的站台，则可能的出栈序列有多少种？
输入
输入包含多组测试数据。每组为一个正整数n（1<=n<=20），表示有n辆列车。
输出
输出可能的出栈序列有多少种。
样例输入
4
3
样例输出
14
5
//#define debug
#define undebug
#include <iostream>
#include<vector>
using namespace std;
void fuction(int n)
{
vector<long long> array;
array.push_back (1);
array.push_back(1);
long long b, c;
if(n>1)
{
for(long long i=2;i<n+1;i++)
{
long long a = 0;
for(long long j=0;j<i;j++)
{
b = array[j];
c= array[i - j-1];
a+=b*c;
}
array.push_back(a);
}
}
cout<< array[n]<<endl;
return;
}
int main()
{
int n;
#ifdef debug
for(int i=1;i<=20;i++)
fuction(i);
return 0;
#endif
#ifdef undebug
while(cin>>n)
fuction(n);
return 0;
#endif
}
栈的类建立：
// 顺序栈.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include<assert.h>
#include"stack.h"
const int stackIncreasement = 20; //溢出时的空间增量
template<class T>
class SeqStack:public Stack<T>
{
private:
T* elements;
int top;
int maxSize;
void overflowProcess();
public:
SeqStack(int sz = 50); //建立一个空栈
~SeqStack()
{
delete[]elements;
}
void Push(const T& x); //把x插入到栈顶（如果栈没有满）
bool Pop(T& X); //退掉栈顶元素
bool getTop(T& x); //获取栈顶元素值
bool IsEmpty()const { return(top == -1) ? true : false; } //判断栈空
bool IsFull()const { return (top = maxSize - 1) ? true : false; } //判断栈是否满
int getSize()const { return top + 1; } //返回栈中元素个数
void MakeEmpty() { top = -1; }
friend ostream& operator<<(ostream& os, SeqStack<T>& s); //输出
};
template<class T>
SeqStack<T>::SeqStack(int sz) :top(-1), maxSize(sz)
{
elements = new T[maxSize];
assert(elements != NULL);
}
template<class T>
void SeqStack<T>::overflowProcess() //溢出处理
{
T* newArray = new T[maxSize + stackIncreasement];
if (newArray == NULL)
{
cerr << "内存分配失败" << endl;
exit(1);
}
for (int i = 0; i <= top; i++)
newArray[i] = elements[i];
maxSize += stackIncreasement;
delete[]elements;
elements = newArray;
}
template<class T>
void SeqStack<T>::Push(const T& x) //x进栈
{
if (IsFull)
overflowProcess();
elements{ ++top } = x;
}
template<class T>
bool SeqStack<T>::Pop(T& x) //top出栈
{
if (IsEmpty)
return false;
x = elements[top--];
return true;
}
template<class T>
bool SeqStack<T>::getTop(T& X) //取top的值
{
if (IsEmpty)
return false;
x = top;
return true;
}
template<class T>
ostream& operator<<(ostream& os, SeqStack<T>& s) //输出
{
os << "top=" << s.top << endl;
for (int i = 0; i <= s.top; i++)
{
os << i << ":" << s.elements << endl;
}
return os;
}
二叉树
二叉树问题
题目描述
现给定一棵二叉树的先序遍历序列和中序遍历序列，要求你计算该二叉树的高度。
输入
输入包含多组测试数据，每组输入首先给出正整数N（<=50），为树中结点总数。下面2行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母（区别大小写）的字符串。
输出
对于每组输入，输出一个整数，即该二叉树的高度。
样例输入
9
ABDFGHIEC
FDHGIBEAC
7
Abcdefg
gfedcbA
样例输出
5
7
#include<iostream>
#include<algorithm>
using namespace std;
int find(char* pre, char* mid, int n) //用先序序列和中序序列求二叉树的高度
{
if (n == 0) //若没有结点，为空树
{
return 0; //搜索到底了就返回长度
}
int i = 0;
for(;i<n;i++) //这个n???????
{
if (mid[i] == pre[0]) //找到根结点在中序的位置
break; //跳出循环时,i的值为结点下标加1,即为元素个数
}
int left = find(pre + 1, mid, i); //左子树的深度,根节点左边就是左子树的元素个数
int right = find(pre + i + 1, mid + i + 1, n - i - 1); //右子树的深度,根节点的右边就是右子树元素的个数
return max(left, right) + 1; //返回左右子树深度中的较大值+根结点
}
int main()
{
int n;
while (cin >> n)
{
char* pre = new char[n + 1];
char* mid = new char[n + 1];
/*先序和中序,字符数组要多开辟一个存储单元放\0*/
cin >> pre;
cin >> mid;
cout << find(pre, mid, n) << endl;
}
return 0;
}
非递归前序遍历
void BinaryTree::PreOrder(BinNode *root)
{
stack<BinaryTree>astack;
BinNode *pointer=root;
astack.push(NULL); //设置监哨
while(pointer)
{
visit(pointer->value);
if(pointer->rightchild!=NULL);
astack.push(pointer->leftchild);
if(pointer->leftchild!=NULL)
pointer=pointer->leftchild; //左路下降
else
{
pointer=astack.top();
astack.pop();
}
}
}
二叉排序树
题目描述
输入一系列整数，建立二叉排序数，并进行前序，中序，后序遍历。
输入
输入第一行包括一个整数n(1<=n<=100)。接下来的一行包括n个整数。
输出
可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，
并对二叉排序树进行前序、中序和后序遍历。每种遍历结果输出一行。每行最后一个数据之后有一个空格。
样例输入
1
2
2
8 15
4
21 10 5 39
样例输出
2
2
2
8 15
8 15
15 8
21 10 5 39
5 10 21 39
5 10 39 21
#include<iostream>
using namespace std;
struct BinTreeNode
{
int data;
BinTreeNode* leftchild, * rightchild;
BinTreeNode(int num=0)
{
data = num;
leftchild = NULL;
rightchild = NULL;
}
};
void set(int x, BinTreeNode* current )
{
current->data = x;
}
void makeBinTree(int n,BinTreeNode *bin) //建立二叉树
{
int num;
cin>>num;
set(num,bin);
BinTreeNode *p=new BinTreeNode;
p = bin;
for(int i=1;i<n;i++)
{
cin>>num;
p=bin;
while (p != NULL)
{
if (p->data == num)
break;
if (p->data > num)
{
if (p->leftchild == NULL)
{
p->leftchild = new BinTreeNode(num);
break;
}
p = p->leftchild;
}
else
{
if (p->rightchild== NULL)
{
p->rightchild = new BinTreeNode(num);
break;
}
p = p->rightchild;
}
}
}
}
void preOrder(BinTreeNode *bin) //先序遍历
{
if(bin!=NULL)
{
cout<<bin->data<<" ";
preOrder(bin->leftchild);
preOrder(bin->rightchild);
}
}
void inorder(BinTreeNode *bin) //中序遍历
{
if(bin!=NULL)
{
inorder(bin->leftchild);
cout<<bin->data<<" ";
inorder(bin->rightchild);
}
}
void postorder(BinTreeNode *bin) //后序遍历
{
if(bin!=NULL)
{
postorder(bin->leftchild);
postorder(bin->rightchild);
cout<<bin->data<<" ";
}
}
int main()
{
int n;
while(cin>>n)
{
BinTreeNode *bin=new BinTreeNode;
makeBinTree(n,bin);
preOrder(bin);
cout << endl;
inorder(bin);
cout << endl;
postorder(bin);
cout << endl;
}
}
二叉排序树删除结点
//改进的二叉搜索树结点删除
void BinSearchTree::delete(BinNode *pointer)
{
if(pointer==NULL)
return;
BinNode *temppointer; //替换结点
BinNode *tempparent; //替换结点的父节点
BinNode *parent=Parent(pointer); //待删除结点的父节点
if(pointer->leftchild==NULL) //待删除结点无左节点时
temppointer=pointer->rightchild;
else
{
temppointer=pointer->leftchild;
while(temppointer->rightchild!=NULL)
{
tempparent=temppointer;
temppointer=temppointer->rightchild; //向右下降找最大值
}
if(temppointer==NULL)
pointer->leftchild=temppointer; //如果被删结点左子树第一个结点没有右孩子
else
tempparent->rightchild=temppointer->leftchild;
temppointer->leftchild=pointer->leftchild;
temppointer->rightchild=pointer->rightchild;
}
if(parent==NULL)
root=temppointer;
else if(parent->leftchild==pointer)
parent->leftchild=temppointer;
else
parent->rightchild=temppointer;
pointer=NULL;
delete pointer;
return;
}
哈夫曼树
问题 B: 哈夫曼树
题目描述
哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，
根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。
输入
输入有多组数据。
每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。
输出
输出权值。
样例输入
2
2 8
3
5 11 30
样例输出
10
62
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int main()
{
int n,num,a,b;
while(cin>>n)
{
priority_queue<int,vector<int>,greater<int>>A;
for(int i=0;i<n;i++)
{
cin>>num;
A.push(num);
}
int total=0;
while(A.size()!=1) //最后一个不用再加了
{
a=A.top();
A.pop();
b=A.top();
A.pop();
total=total+a+b;
A.push(a+b);
}
cout<<total<<endl;
}
return 0;
}
递归
题目描述
小明置身于一个迷宫，请你帮小明找出从起点到终点的最短路程。
小明只能向上下左右四个方向移动。
输入
输入包含多组测试数据。输入的第一行是一个整数T，表示有T组测试数据。
每组输入的第一行是两个整数N和M（1<=N,M<=100）。
接下来N行，每行输入M个字符，每个字符表示迷宫中的一个小方格。
字符的含义如下：
‘S’：起点
\‘E’：终点
‘-’：空地，可以通过
‘#’：障碍，无法通过
输入数据保证有且仅有一个起点和终点。
输出
对于每组输入，输出从起点到终点的最短路程，如果不存在从起点到终点的路，则输出-1。
样例输入
1
5 5
S-###
-----
##---
E#---
---##
样例输出
9
DFS:
#include <iostream> //注意，这个程序是n行m列，和我们平常的nm的含义不一样
#include<vector>
#include<queue>
using namespace std;
priority_queue<int, vector<int>, greater<int> > q; //存路径
void visit( vector< vector<int> > cell,int i,int j,int endi,int endj,int n,int m) //找路径
{
if(i==endi&&j==endj)
{
int all=0;
for(int nn=0;nn<n;nn++)
for(int mm=0;mm<m;mm++)
if(cell[nn][mm]==1)
all++;
q.push(all);
}
cell[i][j]=1; //走过的设为1
if(j-1>=0&&cell[i][j-1]==0)
visit(cell,i,j-1,endi,endj,n,m);
if(j+1<m&&cell[i][j+1]==0)
visit(cell,i,j+1,endi,endj,n,m);
if(i-1>=0&&cell[i-1][j]==0)
visit(cell,i-1,j,endi,endj,n,m);
if(i+1<n&&cell[i+1][j]==0)
visit(cell,i+1,j,endi,endj,n,m);
cell[i][j]=0; //都不行就设置成0
}
int main()
{
int times;
cin>>times; //表示有times组测试数据
int m,n;
int starti=0,startj=0,endi=0,endj=0; //起点和终点
char current;
for(int i=0;i<times;i++)
{
cin>>n; //n行
cin>>m; //m列
vector< vector<int> > cell(n, vector<int>(m));
for(int nn=0;nn<n;nn++) //录入迷宫
for(int mm=0;mm<m;mm++)
{
cin>>current;
if(current=='S')
{
starti=nn;
startj=mm;
cell[nn][mm]=0;
}
if(current=='E')
{
endi=nn;
endj=mm;
cell[nn][mm]=0;
}
if(current=='-')
cell[nn][mm]=0; //表示可以走
if(current=='#')
cell[nn][mm]=2; //表示围墙
}
visit(cell,starti,startj,endi,endj,n,m);
if(q.size()==0)
cout<<-1;
if(q.size()!=0)
cout<<q.top();
while(!q.empty())
q.pop();
}
return 0;
}
BFS：
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int starti , startj , endi , endj ; //起点和终点
struct Position //记录四个移动方向
{
int row;
int col;
Position(int x,int y):row(x),col(y){}
};
vector< vector<int> >Input(int n,int m)
{
vector< vector<int> > cell(n + 2, vector<int>(m + 2)); //n+2行,m+2列
char current;
for (int nn = 0; nn < n + 2; nn++) //录入迷宫
for (int mm = 0; mm < m + 2; mm++)
{
if (nn == 0 || mm == 0 || nn == n + 1 || mm == m + 1)
{
cell[nn][mm] = 2; //最外面一圈用2围起来
continue;
}
cin >> current; //把迷宫转化为数字矩阵
if (current == 'S')
{
starti = nn;
startj = mm;
cell[nn][mm] = 2; //初始的位置不能再走了
}
if (current == 'E')
{
endi = nn;
endj = mm;
cell[nn][mm] = 0;
}
if (current == '-')
cell[nn][mm] = 0; //表示可以走
if (current == '#')
cell[nn][mm] = 2; //表示围墙
}
return cell;
}
/*寻找路径，若找到返回长度，没有路径返回-1*/
int FindPath(vector< vector<int> > cell)
{
Position offsets[4] = { {0,1},{1,0},{0,-1},{-1,0} };
Position here(starti,startj),nbr(0,0);
queue<Position>Q;
while(1)
{
for(int i=0;i<4;i++)
{
nbr.row=here.row+offsets[i].row;
nbr.col=here.col+offsets[i].col;
if (cell[nbr.row][nbr.col] == 0)
{
cell[nbr.row][nbr.col] = cell[here.row][here.col] + 1;
Q.push(nbr); //能走才存，不能走不存
}
if(nbr.row==endi&&nbr.col==endj)
break;
}
if(nbr.row==endi&&nbr.col==endj)
break;
if(Q.empty())
return -1;
here=Q.front();
Q.pop();
}
return cell[nbr.row][nbr.col]-2; //最开始把起点步数设成2 了
}
int main()
{
int times;
cin >> times; //表示有times组测试数据
int m, n;
for (int i = 0; i < times; i++)
{
cin >> n; //n行
cin >> m; //m列
vector< vector<int> > cell=Input(n, m);
cout<<FindPath(cell)<<endl;
}
return 0;
}
汉诺塔
//求解n阶汉诺塔
#include<iostream>
#include<string.h>
using namespace std;
void Hanoi(int n,string A,string B,string C)
{
if(n==1)
cout<<"Move top desk from peg"<<A<<"to peg"<<C<<endl;
else
{
Hanoi(n-1,A,C,B);
cout<<"Move top desk from peg"<<A<<"to peg"<<C<<endl;
Hanoi(n-1,B,A,C);
}
}
int main()
{
int n;
cin>>n;
Hanoi(n,'A','B','C');
return 0;
}
Hanoi双塔问题
题目描述
给定A,B,C三根足够长的细柱，在A柱上放有2n个中间有空的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的(下图为n=3的情形）。现要将 这些国盘移到C柱上，在移动过程中可放在B柱上暂存。要求:
(1)每次只能移动一个圆盘；
(2) A、B、C三根细柱上的圆盘都要保持上小下大的顺序；
任务:设An为2n个圆盘完成上述任务所需的最少移动次数，对于输入的n，输出An。
输入
输入文件hanoi.in为一个正整数n，表示在A柱上放有2n个圆盘。
输出
输出文件hanoi.out仅一行，包含一个正整数，为完成上述任务所需的最少移动次数An。
样例输入
1
样例输出
2
提示
对于50%的数据， 1<=n<=25
对于100% 数据， 1<=n<=200
设法建立An与An-1的递推关系式。
#include <iostream>
#include<cmath>
#include <sstream>
using namespace std;
int main()
{
stringstream sstream;
long long n;
cin >> n;
sstream.precision(0);
sstream << fixed << pow(2.0L, n + 1);
string a = sstream.str();
a[a.length() - 1]--;
a[a.length() - 1]--;
cout << a << endl;
return 0;
}
排序
快速排序
输入
输入的第一行包含1个正整数n，表示共有n个整数需要参与排序。其中n不超过100000。
第二行包含n个用空格隔开的正整数，表示n个需要排序的整数。
输出
只有1行，包含n个整数，表示从小到大排序完毕的所有整数。
请在每个整数后输出一个空格，并请注意行尾输出换行。
样例输入
10
2 8 4 6 1 10 7 3 5 9
样例输出
1 2 3 4 5 6 7 8 9 10
#include <iostream>
#include<algorithm>
using namespace std;
int division(int *list, int left, int right)
{
// 以最左边的数(left)为基准
int base = list[left];
while (left < right) {
// 从序列右端开始，向左遍历，直到找到小于base的数
while (left < right && list[right] >= base)
right--;
// 找到了比base小的元素，将这个元素放到最左边的位置
list[left] = list[right];
// 从序列左端开始，向右遍历，直到找到大于base的数
while (left < right && list[left] <= base)
left++;
// 找到了比base大的元素，将这个元素放到最右边的位置
list[right] = list[left];
}
// 最后将base放到left位置。此时，left位置的左侧数值应该都比left小；
// 而left位置的右侧数值应该都比left大。
list[left] = base;
return left;
}
void quickSort(int* list, int left, int right){
// 左下标一定小于右下标，否则就越界了
if (left < right) {
// 对数组进行分割，取出下次分割的基准标号
int base = division(list, left, right);
// 对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序
quickSort(list, left, base - 1);
// 对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值完整的排序
quickSort(list, base + 1, right);
}
}
int main()
{
int n;
cin>>n;
int *A=new int[n];
int a;
for (int i = 0; i < n; i++)
{
cin >> a;
A[i] = a;
}
quickSort(A,0,n-1); //初始与末尾位置
for(int i = 0; i < n; i++)
cout << A[i] << " ";
cout<<endl;
return 0;
}
常规cpp
题目1168：
字符串的查找删除
题目描述：
给定一个短字符串（不含空格），再给定若干字符串，在这些字符串中删除所含有的短字符串。
输入：
输入只有1组数据。
输入一个短字符串（不含空格），再输入若干字符串直到文件结束为止。
输出：
删除输入的短字符串(不区分大小写)并去掉空格,输出。
样例输入：
in
#include
int main()
{printf(" Hi ");
}
样例输出：
#clude
tma()
{prtf("Hi")}
提示：
注:将字符串中的In、IN、iN、in删除。**/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
using namespace std;
int Equal(char a, char b) {
//通过a和b的绝对值判断两个字母是否“相等”
if (abs(a - b) == 32 || a == b) return 1;
else return 0;
}
int main()
{
char c[1000], b[1000];
gets(c);
while (gets(b) != NULL) {
int len = strlen(b);
for (int i = 0; i < len; i++) {
//如果b字符串中有字符和c[0]相等的字符就开始匹配
if (Equal(b[i], c[0])) {
int j = 1;
i++; //b的下标加1
while (j < strlen(c) && Equal(b[i], c[j])) {
i++;
j++;
}
//表示匹配成功，将b中匹配到的部分置为空格
if (j == strlen(c)) {
for (int k = i - j; k < i; k++) {
b[k] = ' ';
}
}
i--;
}
}
//去除空格输出
for (int i = 0; i < len; i++) {
if (b[i] != ' ') {
cout<<b[i];
}
}
cout<<endl;
}
return 0;
}
