線性表

#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;          //求表長(zhǎng)度
    virtual int Search(T& x)const = 0;      //求給定x下表（搜索）
    virtual int Locate(int i)const = 0;     //定位第i個(gè)元素的位置
    virtual bool getDate(int i, T& x) = 0;  //求第i個(gè)表項(xiàng)的值
    virtual bool setDate(int i, T& x) = 0;  //修改第i個(gè)表項(xiàng)的值
    virtual bool Insert(int i, T& x) = 0;   //在第i個(gè)位置插入
    virtual bool Remove(int i, T& x) = 0;   //刪除第i個(gè)位置的值
    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)：除第一及最后一個(gè)元素外，每個(gè)結(jié)點(diǎn)都只有一個(gè)前趨和只有一個(gè)后繼褪尝。
表長(zhǎng)：元素總個(gè)數(shù)n
空表：n=0
線性起點(diǎn)：a1
線性終點(diǎn)：an
下標(biāo)：是元素的序號(hào)，表示元素在表中的位置
表頭：第一個(gè)元素
表尾：最后一個(gè)元素

順序表

優(yōu)點(diǎn)：
⑴ 無需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間孩等；
⑵ 隨機(jī)存攘в础：可以快速地存取表中任一位置的元素。
缺點(diǎn)：
⑴ 插入和刪除操作需要移動(dòng)大量元素产艾；
⑵ 表的容量難以確定疤剑，表的容量難以擴(kuò)充；
⑶ 造成存儲(chǔ)空間的碎片闷堡。

// 順序表.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)個(gè)數(shù),用const更加安全
    int Length()const { return last + 1; }  //計(jì)算表長(zhǎng)度管钳，const：不能改變數(shù)據(jù)成員的值钦铁，
                                            //const成員函數(shù)不能調(diào)用非const成員函數(shù)
    int Search(T& x)const;                  //搜索x在表中的位置，函數(shù)返回表項(xiàng)序號(hào)
    int Locate(int i)const;                 //搜索第i個(gè)表項(xiàng)才漆，函數(shù)返回表項(xiàng)序號(hào)
    bool getData(int i, T& x)const          //取第i個(gè)表項(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個(gè)表項(xiàng)的值
    {
        if (i > 0 && i <= last + 1)data[i - 1] = x;
    }
    bool Insert(int i, T & x);              //用x來修飾第i個(gè)表項(xiàng)的值
    bool Remove(int, T & x);                //刪除第i個(gè)表項(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];              //順序表動(dòng)態(tài)存儲(chǔ)數(shù)組
        if (data == NULL)
        {
            cerr << "存儲(chǔ)分配失敗栽烂！" << 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];                  //順序表動(dòng)態(tài)存儲(chǔ)數(shù)組
    if (data = NULL)
    {
        cerr << "內(nèi)存分配錯(cuò)誤" << 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ò)大存儲(chǔ)容量
{
    if (newSize == 0)
    {
        cerr << "無效的數(shù)組大小" << endl;
        return;
    }
    if (newSize != maxSize)                 //修改
    {
        T* newarray = new T[newSize];       //新建數(shù)組
        if (newarray == NULL)
        {
            cerr << "存儲(chǔ)分配錯(cuò)誤" << 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個(gè)
{
    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++;                             //這個(gè)很重要ｕ锍稹Ａ到拧腺办！
    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 << "開始建立順序表,請(qǐng)輸入表中元素個(gè)數(shù)（不超過" << maxSize << "個(gè))" << endl;
    while (1)
    {
        cin >> last;
        if (i >= maxSize)
            break;
        cout << "錯(cuò)誤，輸入元素個(gè)數(shù)最大為" << maxSize << "糟描。" << endl;
    }
    for (int i = 0; i <= last; i++)
    {
        cout << "請(qǐng)輸入第" << i + 1 << "個(gè)數(shù):";
        cin >> data[i];
    }
}


template<class T>
void SeqList<T>::output()           //將整個(gè)表輸出
{
    cout << "現(xiàn)在輸出整個(gè)表怀喉，表中總共有" << 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];                  //順序表動(dòng)態(tài)存儲(chǔ)數(shù)組
    if (data = NULL)
    {
        cerr << "內(nèi)存分配錯(cuò)誤" << endl;
        exit(1);
    }
    for (int i = 1; i <= last; i++)         //i是邏輯位置
    {
        L.getData(i, value);
        data[i - 1] = value;
    }
}

單鏈表

頭指針:指向第一個(gè)結(jié)點(diǎn)的地址
尾標(biāo)志：終端結(jié)點(diǎn)的指針域?yàn)榭?br> 空表：first=NULL
頭結(jié)點(diǎn)：在單鏈表的第一個(gè)元素結(jié)點(diǎn)之前附設(shè)一個(gè)類型相同的結(jié)點(diǎn)船响，以便在表的不同位置躬拢，或空表和非空表處理統(tǒng)一。
存儲(chǔ)特點(diǎn)：
（1）邏輯次序和物理次序不一定相同见间。
（2）元素之間的邏輯關(guān)系用指針表示聊闯。
順序表和鏈表的比較：
空間性能是指某種存儲(chǔ)結(jié)構(gòu)所占用的存儲(chǔ)空間的大小。
時(shí)間性能是指實(shí)現(xiàn)基于某種存儲(chǔ)結(jié)構(gòu)的基本操作（即算法）的時(shí)間復(fù)雜度米诉。

//對(duì)鏈表的操作都是通過指針來的
#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ì)算表長(zhǎng)
    LinkNode<T>* getHead()const { return first; }   //返回頭結(jié)點(diǎn)地址
    LinkNode<T>* Search(T x);       //搜索存有x的結(jié)點(diǎn)的地址
    LinkNode<T>* Locate(int i); //定位第i個(gè)結(jié)點(diǎn)的地址
    bool getData(int i, T& x)const; //返回第i個(gè)結(jié)點(diǎn)中的值
    void setData(int i, T& x);      //修改第i個(gè)結(jié)點(diǎn)中的值
    bool Insert(int i, T& x);       //在第i個(gè)元素后插入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>;     //初始化一個(gè)頭結(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;       //一個(gè)一個(gè)刪
    }
}

template<class T>
int List<T>::Length()const      //計(jì)算表長(zhǎng)
{
    LinkNode* q = first->Link;
    int count = 0;
    while (p != NULL)       //一個(gè)一個(gè)找直到表尾
    {
        p = p->Link;
        count++;
    }
    return count;
}

template<class T>
LinkNode<T>* List<T>::Search(T x)       //返回存有某個(gè)元素的結(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個(gè)結(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個(gè)結(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個(gè)結(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個(gè)元素后插入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個(gè)元素
{
    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 << "開始建立單鏈表,請(qǐng)輸入需要記錄的數(shù)據(jù)個(gè)數(shù)" << endl;
    int x, num = 0;
    cin >> x;
    if (x <= 0)return;
    cout << "請(qǐng)依次輸入需要記錄的數(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>;     //初始化一個(gè)頭結(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í)菱蔬，常把站臺(tái)設(shè)計(jì)成棧式結(jié)構(gòu)的站臺(tái)，試問：
設(shè)有編號(hào)為1到n的n輛列車史侣，順序開入棧式結(jié)構(gòu)的站臺(tái)拴泌，則可能的出棧序列有多少種？
輸入
輸入包含多組測(cè)試數(shù)據(jù)惊橱。每組為一個(gè)正整數(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;       //溢出時(shí)的空間增量
template<class T>
class SeqStack:public Stack<T>
{
private:
    T* elements;
    int top;
    int maxSize;
    void overflowProcess();
public:
    SeqStack(int sz = 50);      //建立一個(gè)空棧
    ~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; }      //返回棧中元素個(gè)數(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ì)算該二叉樹的高度。
輸入
輸入包含多組測(cè)試數(shù)據(jù)卓囚，每組輸入首先給出正整數(shù)N（<=50）瘾杭，為樹中結(jié)點(diǎn)總數(shù)。下面2行先后給出先序和中序遍歷序列哪亿，均是長(zhǎng)度為N的不包含重復(fù)英文字母（區(qū)別大小寫）的字符串粥烁。
輸出
對(duì)于每組輸入贤笆，輸出一個(gè)整數(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;       //搜索到底了就返回長(zhǎng)度
    }
    int i = 0;
    for(;i<n;i++)       //這個(gè)n???????
    {
        if (mid[i] == pre[0])  //找到根結(jié)點(diǎn)在中序的位置
            break;      //跳出循環(huán)時(shí),i的值為結(jié)點(diǎn)下標(biāo)加1,即為元素個(gè)數(shù)
    }
    int left = find(pre + 1, mid, i);  //左子樹的深度,根節(jié)點(diǎn)左邊就是左子樹的元素個(gè)數(shù)
    int right = find(pre + i + 1, mid + i + 1, n - i - 1);   //右子樹的深度,根節(jié)點(diǎn)的右邊就是右子樹元素的個(gè)數(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ù)組要多開辟一個(gè)存儲(chǔ)單元放\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)行前序埋涧，中序，后序遍歷奇瘦。
輸入
輸入第一行包括一個(gè)整數(shù)n(1<=n<=100)棘催。接下來的一行包括n個(gè)整數(shù)。
輸出
可能有多組測(cè)試數(shù)據(jù)耳标，對(duì)于每組數(shù)據(jù)醇坝，將題目所給數(shù)據(jù)建立一個(gè)二叉排序樹，
并對(duì)二叉排序樹進(jìn)行前序次坡、中序和后序遍歷呼猪。每種遍歷結(jié)果輸出一行。每行最后一個(gè)數(shù)據(jù)之后有一個(gè)空格砸琅。
樣例輸入
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)時(shí)
        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)左子樹第一個(gè)結(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: 哈夫曼樹
題目描述
哈夫曼樹宋距，第一行輸入一個(gè)數(shù)n，表示葉結(jié)點(diǎn)的個(gè)數(shù)症脂。需要用這些葉結(jié)點(diǎn)生成哈夫曼樹谚赎，
根據(jù)哈夫曼樹的概念，這些結(jié)點(diǎn)有權(quán)值摊腋，即weight沸版，題目需要輸出所有結(jié)點(diǎn)的值與權(quán)值的乘積之和。
輸入
輸入有多組數(shù)據(jù)兴蒸。
每組第一行輸入一個(gè)數(shù)n视粮，接著輸入n個(gè)葉節(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)      //最后一個(gè)不用再加了
        {
            a=A.top();
            A.pop();
            b=A.top();
            A.pop();
            total=total+a+b;
            A.push(a+b);
        }
        cout<<total<<endl;
    }
    return 0;
}

遞歸

題目描述
小明置身于一個(gè)迷宮，請(qǐng)你幫小明找出從起點(diǎn)到終點(diǎn)的最短路程岛啸。
小明只能向上下左右四個(gè)方向移動(dòng)钓觉。
輸入
輸入包含多組測(cè)試數(shù)據(jù)。輸入的第一行是一個(gè)整數(shù)T坚踩，表示有T組測(cè)試數(shù)據(jù)荡灾。
每組輸入的第一行是兩個(gè)整數(shù)N和M（1<=N,M<=100）。
接下來N行，每行輸入M個(gè)字符批幌，每個(gè)字符表示迷宮中的一個(gè)小方格础锐。
字符的含義如下：
‘S’：起點(diǎn)
\‘E’：終點(diǎn)
‘-’：空地，可以通過
‘#’：障礙荧缘，無法通過
輸入數(shù)據(jù)保證有且僅有一個(gè)起點(diǎn)和終點(diǎn)皆警。
輸出
對(duì)于每組輸入，輸出從起點(diǎn)到終點(diǎn)的最短路程截粗，如果不存在從起點(diǎn)到終點(diǎn)的路丐巫，則輸出-1淹父。
樣例輸入
1
5 5
S-###
-----
##---
E#---
---##
樣例輸出
9

DFS:

#include <iostream>     //注意染乌，這個(gè)程序是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組測(cè)試數(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     //記錄四個(gè)移動(dòng)方向
{
    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;
}

/*尋找路徑联喘，若找到返回長(zhǎng)度纳鼎，沒有路徑返回-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組測(cè)試數(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三根足夠長(zhǎng)的細(xì)柱契耿，在A柱上放有2n個(gè)中間有空的圓盤靡羡，共有n個(gè)不同的尺寸系洛，每個(gè)尺寸都有兩個(gè)相同的圓盤，注意這兩個(gè)圓盤是不加區(qū)分的(下圖為n=3的情形）÷圆剑現(xiàn)要將 這些國盤移到C柱上描扯，在移動(dòng)過程中可放在B柱上暫存。要求:
(1)每次只能移動(dòng)一個(gè)圓盤趟薄；
(2) A绽诚、B、C三根細(xì)柱上的圓盤都要保持上小下大的順序杭煎；
任務(wù):設(shè)An為2n個(gè)圓盤完成上述任務(wù)所需的最少移動(dòng)次數(shù)恩够，對(duì)于輸入的n，輸出An羡铲。
輸入
輸入文件hanoi.in為一個(gè)正整數(shù)n蜂桶，表示在A柱上放有2n個(gè)圓盤。
輸出
輸出文件hanoi.out僅一行也切，包含一個(gè)正整數(shù)扑媚，為完成上述任務(wù)所需的最少移動(dòng)次數(shù)An。
樣例輸入
1
樣例輸出
2
提示
對(duì)于50%的數(shù)據(jù)雷恃， 1<=n<=25
對(duì)于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個(gè)正整數(shù)n倒槐，表示共有n個(gè)整數(shù)需要參與排序旬痹。其中n不超過100000。
第二行包含n個(gè)用空格隔開的正整數(shù)，表示n個(gè)需要排序的整數(shù)两残。
輸出
只有1行羡忘，包含n個(gè)整數(shù)，表示從小到大排序完畢的所有整數(shù)磕昼。
請(qǐng)?jiān)诿總€(gè)整數(shù)后輸出一個(gè)空格卷雕，并請(qǐng)注意行尾輸出換行。
樣例輸入
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小的元素，將這個(gè)元素放到最左邊的位置
        list[left] = list[right];

        // 從序列左端開始峰鄙，向右遍歷浸间，直到找到大于base的數(shù)
        while (left < right && list[left] <= base)
            left++;
        // 找到了比base大的元素，將這個(gè)元素放到最右邊的位置
        list[right] = list[left];
    }

    // 最后將base放到left位置吟榴。此時(shí)魁蒜，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) {
        // 對(duì)數(shù)組進(jìn)行分割狭瞎，取出下次分割的基準(zhǔn)標(biāo)號(hào)
        int base = division(list, left, right);

        // 對(duì)“基準(zhǔn)標(biāo)號(hào)“左側(cè)的一組數(shù)值進(jìn)行遞歸的切割细移，以至于將這些數(shù)值完整的排序
        quickSort(list, left, base - 1);

        // 對(duì)“基準(zhǔn)標(biāo)號(hà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：
字符串的查找刪除
題目描述：
給定一個(gè)短字符串（不含空格）熊锭，再給定若干字符串弧轧，在這些字符串中刪除所含有的短字符串。
輸入：
輸入只有1組數(shù)據(jù)碗殷。
輸入一個(gè)短字符串（不含空格）精绎，再輸入若干字符串直到文件結(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的絕對(duì)值判斷兩個(gè)字母是否“相等”
    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;
}