線性表
#pragma once
template<class T>
class LinearList//線性表抽象基類
{
public:
LinearList() {}; //構(gòu)造函數(shù)
~LinearList; //析構(gòu)函數(shù)
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個表項(xiàng)的值
virtual bool setDate(int i, T& x) = 0; //修改第i個表項(xiàng)的值
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;//復(fù)制
};
線性表的結(jié)構(gòu)特點(diǎn)：除第一及最后一個元素外，每個結(jié)點(diǎn)都只有一個前趨和只有一個后繼。
表長：元素總個數(shù)n
空表：n=0
線性起點(diǎn)：a1
線性終點(diǎn)：an
下標(biāo)：是元素的序號，表示元素在表中的位置
表頭：第一個元素
表尾：最后一個元素
順序表
優(yōu)點(diǎn)：
⑴ 無需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲空間；
⑵ 隨機(jī)存?。嚎梢钥焖俚卮嫒”碇腥我晃恢玫脑?。
缺點(diǎn)：
⑴ 插入和刪除操作需要移動大量元素；
⑵ 表的容量難以確定，表的容量難以擴(kuò)充；
⑶ 造成存儲空間的碎片。
// 順序表.cpp : 此文件包含 "main" 函數(shù)。程序執(zhí)行將在此處開始并結(jié)束。
//
#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; //存放數(shù)組
int maxSize; //最大項(xiàng)數(shù),項(xiàng)數(shù)?。?！
int last; //最后位置下標(biāo)，初始化為-1
void reSize(int newSize); //改變數(shù)組大小
public:
SeqList(int sz = defaultSize);
SeqList(SeqList<T>& L); //復(fù)制構(gòu)造函數(shù)
~SeqList() { delete[] data; }
int Size()const { return maxSize; } //最大可容納表項(xiàng)個數(shù),用const更加安全
int Length()const { return last + 1; } //計(jì)算表長度，const：不能改變數(shù)據(jù)成員的值，
//const成員函數(shù)不能調(diào)用非const成員函數(shù)
int Search(T& x)const; //搜索x在表中的位置，函數(shù)返回表項(xiàng)序號
int Locate(int i)const; //搜索第i個表項(xiàng)，函數(shù)返回表項(xiàng)序號
bool getData(int i, T& x)const //取第i個表項(xiàng)的值,復(fù)制給x
{
if (i > 0 && i <= last + 1)
{
x = data[i - 1];
return true;
}
else
return false;
}
void setData(int i, T& x) //修改第i個表項(xiàng)的值
{
if (i > 0 && i <= last + 1)data[i - 1] = x;
}
bool Insert(int i, T & x); //用x來修飾第i個表項(xiàng)的值
bool Remove(int, T & x); //刪除第i個表項(xiàng)，通過x返回表項(xiàng)的值
bool IsEmpty()
{
return(last == -1) ? true : false; //判斷表項(xiàng)是否為空
}
bool IsFull()
{
return(last == maxSize - 1) ? true : false;//判斷表滿
}
void input(); //輸入建立順序表
void output(); //輸出
SeqList<T>operator=(SeqList<T> & L); //表整體賦值
};
//構(gòu)造函數(shù)和復(fù)制構(gòu)造函數(shù)
template<class T>
SeqList<T>::SeqList(int sz)
{
if (sz > 0)
{
maxSize = sz;
last = -1;
data = new T[maxSize]; //順序表動態(tài)存儲數(shù)組
if (data == NULL)
{
cerr << "存儲分配失?。? << endl;
exit(1);
}
}
}
template<class T>
SeqList<T>::SeqList(SeqList<T> & L) //復(fù)制構(gòu)造函數(shù)創(chuàng)建L
{
maxSize = L.Size();
last = L.Length() - 1;
T value;
data = new T[maxSize]; //順序表動態(tài)存儲數(shù)組
if (data = NULL)
{
cerr << "內(nèi)存分配錯誤" << 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) //改變數(shù)組大小,擴(kuò)大存儲容量
{
if (newSize == 0)
{
cerr << "無效的數(shù)組大小" << endl;
return;
}
if (newSize != maxSize) //修改
{
T* newarray = new T[newSize]; //新建數(shù)組
if (newarray == NULL)
{
cerr << "存儲分配錯誤" << endl;
exit(1);
}
int n = last + 1;
T* srcptr = data; //源數(shù)組首地址
T* destptr = newarray; //目的數(shù)組首地址
while (n--)
{
*destptr++ = *srcptr++; //復(fù)制
}
delete[]data; //刪除老數(shù)組
data = newarray; //data指向新數(shù)組
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) //插入操作,插入數(shù)字作為第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 << "開始建立順序表,請輸入表中元素個數(shù)（不超過" << maxSize << "個)" << endl;
while (1)
{
cin >> last;
if (i >= maxSize)
break;
cout << "錯誤，輸入元素個數(shù)最大為" << maxSize << "。" << endl;
}
for (int i = 0; i <= last; i++)
{
cout << "請輸入第" << i + 1 << "個數(shù):";
cin >> data[i];
}
}
template<class T>
void SeqList<T>::output() //將整個表輸出
{
cout << "現(xiàn)在輸出整個表，表中總共有" << last + 1 << "項(xiàng)元素，下面是各項(xiàng)元素:" << 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]; //順序表動態(tài)存儲數(shù)組
if (data = NULL)
{
cerr << "內(nèi)存分配錯誤" << endl;
exit(1);
}
for (int i = 1; i <= last; i++) //i是邏輯位置
{
L.getData(i, value);
data[i - 1] = value;
}
}
單鏈表
頭指針:指向第一個結(jié)點(diǎn)的地址
尾標(biāo)志：終端結(jié)點(diǎn)的指針域?yàn)榭?br>
空表：first=NULL
頭結(jié)點(diǎn)：在單鏈表的第一個元素結(jié)點(diǎn)之前附設(shè)一個類型相同的結(jié)點(diǎn)，以便在表的不同位置，或空表和非空表處理統(tǒng)一。
存儲特點(diǎn)：
（1）邏輯次序和物理次序不一定相同。
（2）元素之間的邏輯關(guān)系用指針表示。
順序表和鏈表的比較：
空間性能是指某種存儲結(jié)構(gòu)所占用的存儲空間的大小。
時間性能是指實(shí)現(xiàn)基于某種存儲結(jié)構(gòu)的基本操作（即算法）的時間復(fù)雜度。
//對鏈表的操作都是通過指針來的
#include<iostream>
#include"linearList.h"
#include<stdlib.h>
using namespace std;
template <class T>
struct LinkNode //結(jié)點(diǎn)類型定義
{
T data; //結(jié)點(diǎn)數(shù)據(jù)域
LinkNode<T>* Link; //鏈指針域
LinkNode(LinkNode<T>* ptr = NULL) { Link = ptr; }//初始化成員指針的構(gòu)造函數(shù)
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>; } //構(gòu)造函數(shù)
List(const T& x) { first = new LinkNode<T>(x); }//構(gòu)造函數(shù)
List(List<T>& L); //復(fù)制構(gòu)造函數(shù)
~List() { makeEmpty(); } // 析構(gòu)函數(shù)
void makeEmpty(); // 制表為空表
int Length()const; //計(jì)算表長
LinkNode<T>* getHead()const { return first; } //返回頭結(jié)點(diǎn)地址
LinkNode<T>* Search(T x); //搜索存有x的結(jié)點(diǎn)的地址
LinkNode<T>* Locate(int i); //定位第i個結(jié)點(diǎn)的地址
bool getData(int i, T& x)const; //返回第i個結(jié)點(diǎn)中的值
void setData(int i, T& x); //修改第i個結(jié)點(diǎn)中的值
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); //重載復(fù)制函數(shù)
};
template<class T>
List<T>::List(List<T>& L) //復(fù)制構(gòu)造函數(shù)
{
T value;
LinkNode<T>* scrptr = L.getHead(); //從頭節(jié)點(diǎn)開始
LinkNode<T>* destptr = first = new LinkNode<T>; //初始化一個頭結(jié)點(diǎn)
while (scrptr->Link != NULL)
{
value = scrptr->Link->data;
destprt->Link = new LinkNode<T>(value);
destptr = destptr->Link;
scrptr = scrptr->Link;
}
destptr->Link = NULL; //末尾結(jié)點(diǎn)處理
}
template<class T>
void List<T>::makeEmpty() // 制表為空表
{
LinkNode<T>* q;
while (first->Link != NULL) //當(dāng)表不為空
{
q = first->Link;
first->Link = first->Link->Link;
delete q; //一個一個刪
}
}
template<class T>
int List<T>::Length()const //計(jì)算表長
{
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) //返回存有某個元素的結(jié)點(diǎn)的下標(biāo)
{
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個結(jié)點(diǎn)的地址
{
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個結(jié)點(diǎn)的元素
{
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個結(jié)點(diǎn)
{
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 << "內(nèi)存分配失敗" << 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 << "開始建立單鏈表,請輸入需要記錄的數(shù)據(jù)個數(shù)" << endl;
int x, num = 0;
cin >> x;
if (x <= 0)return;
cout << "請依次輸入需要記錄的數(shù)據(jù)：" << 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(); //從頭節(jié)點(diǎn)開始
LinkNode<T>* destptr = first = new LinkNode<T>; //初始化一個頭結(jié)點(diǎn)
while (scrptr->Link != NULL)
{
value = scrptr->Link->data;
destprt->Link = new LinkNode<T>(value);
destptr = destptr->Link;
scrptr = scrptr->Link;
}
destptr->Link = NULL; //末尾結(jié)點(diǎn)處理
}
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: 火車出站
題目描述
鐵路進(jìn)行列車調(diào)度時，常把站臺設(shè)計(jì)成棧式結(jié)構(gòu)的站臺，試問：
設(shè)有編號為1到n的n輛列車，順序開入棧式結(jié)構(gòu)的站臺，則可能的出棧序列有多少種？
輸入
輸入包含多組測試數(shù)據(jù)。每組為一個正整數(shù)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" 函數(shù)。程序執(zhí)行將在此處開始并結(jié)束。
//
#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; } //返回棧中元素個數(shù)
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 << "內(nèi)存分配失敗" << 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進(jìn)棧
{
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;
}
二叉樹
二叉樹問題
題目描述
現(xiàn)給定一棵二叉樹的先序遍歷序列和中序遍歷序列，要求你計(jì)算該二叉樹的高度。
輸入
輸入包含多組測試數(shù)據(jù)，每組輸入首先給出正整數(shù)N（<=50），為樹中結(jié)點(diǎn)總數(shù)。下面2行先后給出先序和中序遍歷序列，均是長度為N的不包含重復(fù)英文字母（區(qū)別大小寫）的字符串。
輸出
對于每組輸入，輸出一個整數(shù)，即該二叉樹的高度。
樣例輸入
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) //若沒有結(jié)點(diǎn)，為空樹
{
return 0; //搜索到底了就返回長度
}
int i = 0;
for(;i<n;i++) //這個n???????
{
if (mid[i] == pre[0]) //找到根結(jié)點(diǎn)在中序的位置
break; //跳出循環(huán)時,i的值為結(jié)點(diǎn)下標(biāo)加1,即為元素個數(shù)
}
int left = find(pre + 1, mid, i); //左子樹的深度,根節(jié)點(diǎn)左邊就是左子樹的元素個數(shù)
int right = find(pre + i + 1, mid + i + 1, n - i - 1); //右子樹的深度,根節(jié)點(diǎn)的右邊就是右子樹元素的個數(shù)
return max(left, right) + 1; //返回左右子樹深度中的較大值+根結(jié)點(diǎn)
}
int main()
{
int n;
while (cin >> n)
{
char* pre = new char[n + 1];
char* mid = new char[n + 1];
/*先序和中序,字符數(shù)組要多開辟一個存儲單元放\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); //設(shè)置監(jiān)哨
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();
}
}
}
二叉排序樹
題目描述
輸入一系列整數(shù)，建立二叉排序數(shù)，并進(jìn)行前序，中序，后序遍歷。
輸入
輸入第一行包括一個整數(shù)n(1<=n<=100)。接下來的一行包括n個整數(shù)。
輸出
可能有多組測試數(shù)據(jù)，對于每組數(shù)據(jù)，將題目所給數(shù)據(jù)建立一個二叉排序樹，
并對二叉排序樹進(jìn)行前序、中序和后序遍歷。每種遍歷結(jié)果輸出一行。每行最后一個數(shù)據(jù)之后有一個空格。
樣例輸入
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;
}
}
二叉排序樹刪除結(jié)點(diǎn)
//改進(jìn)的二叉搜索樹結(jié)點(diǎn)刪除
void BinSearchTree::delete(BinNode *pointer)
{
if(pointer==NULL)
return;
BinNode *temppointer; //替換結(jié)點(diǎn)
BinNode *tempparent; //替換結(jié)點(diǎn)的父節(jié)點(diǎn)
BinNode *parent=Parent(pointer); //待刪除結(jié)點(diǎn)的父節(jié)點(diǎn)
if(pointer->leftchild==NULL) //待刪除結(jié)點(diǎn)無左節(jié)點(diǎn)時
temppointer=pointer->rightchild;
else
{
temppointer=pointer->leftchild;
while(temppointer->rightchild!=NULL)
{
tempparent=temppointer;
temppointer=temppointer->rightchild; //向右下降找最大值
}
if(temppointer==NULL)
pointer->leftchild=temppointer; //如果被刪結(jié)點(diǎn)左子樹第一個結(jié)點(diǎn)沒有右孩子
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: 哈夫曼樹
題目描述
哈夫曼樹，第一行輸入一個數(shù)n，表示葉結(jié)點(diǎn)的個數(shù)。需要用這些葉結(jié)點(diǎn)生成哈夫曼樹，
根據(jù)哈夫曼樹的概念，這些結(jié)點(diǎn)有權(quán)值，即weight，題目需要輸出所有結(jié)點(diǎn)的值與權(quán)值的乘積之和。
輸入
輸入有多組數(shù)據(jù)。
每組第一行輸入一個數(shù)n，接著輸入n個葉節(jié)點(diǎn)（葉節(jié)點(diǎn)權(quán)值不超過100，2<=n<=1000）。
輸出
輸出權(quán)值。
樣例輸入
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;
}
遞歸
題目描述
小明置身于一個迷宮，請你幫小明找出從起點(diǎn)到終點(diǎn)的最短路程。
小明只能向上下左右四個方向移動。
輸入
輸入包含多組測試數(shù)據(jù)。輸入的第一行是一個整數(shù)T，表示有T組測試數(shù)據(jù)。
每組輸入的第一行是兩個整數(shù)N和M（1<=N,M<=100）。
接下來N行，每行輸入M個字符，每個字符表示迷宮中的一個小方格。
字符的含義如下：
‘S’：起點(diǎn)
\‘E’：終點(diǎn)
‘-’：空地，可以通過
‘#’：障礙，無法通過
輸入數(shù)據(jù)保證有且僅有一個起點(diǎn)和終點(diǎn)。
輸出
對于每組輸入，輸出從起點(diǎn)到終點(diǎn)的最短路程，如果不存在從起點(diǎn)到終點(diǎn)的路，則輸出-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; //走過的設(shè)為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; //都不行就設(shè)置成0
}
int main()
{
int times;
cin>>times; //表示有times組測試數(shù)據(jù)
int m,n;
int starti=0,startj=0,endi=0,endj=0; //起點(diǎn)和終點(diǎn)
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 ; //起點(diǎn)和終點(diǎn)
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; //把迷宮轉(zhuǎn)化為數(shù)字矩陣
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; //最開始把起點(diǎn)步數(shù)設(shè)成2 了
}
int main()
{
int times;
cin >> times; //表示有times組測試數(shù)據(jù)
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三根足夠長的細(xì)柱，在A柱上放有2n個中間有空的圓盤，共有n個不同的尺寸，每個尺寸都有兩個相同的圓盤，注意這兩個圓盤是不加區(qū)分的(下圖為n=3的情形）?，F(xiàn)要將 這些國盤移到C柱上，在移動過程中可放在B柱上暫存。要求:
(1)每次只能移動一個圓盤；
(2) A、B、C三根細(xì)柱上的圓盤都要保持上小下大的順序；
任務(wù):設(shè)An為2n個圓盤完成上述任務(wù)所需的最少移動次數(shù)，對于輸入的n，輸出An。
輸入
輸入文件hanoi.in為一個正整數(shù)n，表示在A柱上放有2n個圓盤。
輸出
輸出文件hanoi.out僅一行，包含一個正整數(shù)，為完成上述任務(wù)所需的最少移動次數(shù)An。
樣例輸入
1
樣例輸出
2
提示
對于50%的數(shù)據(jù)， 1<=n<=25
對于100% 數(shù)據(jù)， 1<=n<=200
設(shè)法建立An與An-1的遞推關(guān)系式。
#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個正整數(shù)n，表示共有n個整數(shù)需要參與排序。其中n不超過100000。
第二行包含n個用空格隔開的正整數(shù)，表示n個需要排序的整數(shù)。
輸出
只有1行，包含n個整數(shù)，表示從小到大排序完畢的所有整數(shù)。
請?jiān)诿總€整數(shù)后輸出一個空格，并請注意行尾輸出換行。
樣例輸入
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)
{
// 以最左邊的數(shù)(left)為基準(zhǔn)
int base = list[left];
while (left < right) {
// 從序列右端開始，向左遍歷，直到找到小于base的數(shù)
while (left < right && list[right] >= base)
right--;
// 找到了比base小的元素，將這個元素放到最左邊的位置
list[left] = list[right];
// 從序列左端開始，向右遍歷，直到找到大于base的數(shù)
while (left < right && list[left] <= base)
left++;
// 找到了比base大的元素，將這個元素放到最右邊的位置
list[right] = list[left];
}
// 最后將base放到left位置。此時，left位置的左側(cè)數(shù)值應(yīng)該都比left??；
// 而left位置的右側(cè)數(shù)值應(yīng)該都比left大。
list[left] = base;
return left;
}
void quickSort(int* list, int left, int right){
// 左下標(biāo)一定小于右下標(biāo)，否則就越界了
if (left < right) {
// 對數(shù)組進(jìn)行分割，取出下次分割的基準(zhǔn)標(biāo)號
int base = division(list, left, right);
// 對“基準(zhǔn)標(biāo)號“左側(cè)的一組數(shù)值進(jìn)行遞歸的切割，以至于將這些數(shù)值完整的排序
quickSort(list, left, base - 1);
// 對“基準(zhǔn)標(biāo)號“右側(cè)的一組數(shù)值進(jìn)行遞歸的切割，以至于將這些數(shù)值完整的排序
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;
}
常規(guī)cpp
題目1168：
字符串的查找刪除
題目描述：
給定一個短字符串（不含空格），再給定若干字符串，在這些字符串中刪除所含有的短字符串。
輸入：
輸入只有1組數(shù)據(jù)。
輸入一個短字符串（不含空格），再輸入若干字符串直到文件結(jié)束為止。
輸出：
刪除輸入的短字符串(不區(qū)分大小寫)并去掉空格,輸出。
樣例輸入：
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的下標(biāo)加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;
}
