#include <iostream>
#include <string>
using namespace std;
int BF_Find(string &s, string &t)
{
    int i = 0, j = 0, count = 0;
    while(i < s.size())
    {

        if(s.at(i) == t.at(j))
        {
            i++;
            j++;
            count++;
        }
        else
        {
            i++;
            j = 0;
            count = 0;
        }
        if(count == t.size())
        {
            cout << "模式匹配成功,起始位置是:" << i - count + 1 << endl;
            return (i - count + 1);
        }

    }
    cout << "字符串匹配失败!" << endl;
    return 0;
}
int main()
{
    string str1, str2;
    cout << "请输入主串:" << endl;
    cin >> str1;
    cout << "请输入子串:" << endl;
    cin >> str2;
    BF_Find(str1, str2);
    return 0;
}

#include <iostream>
#include <list>
using namespace std ;

typedef list<int> LISTINT;

LISTINT listAnother;
LISTINT list_result;

int d[4][4] = {{ -1, 3, 6, 7}, {2, -1, 8, 6}, {7, 3, -1, 5,}, {7, 3, 7, -1}}; //路径权值
int matrix_length = 4;

int getPath(int n, LISTINT list_org)
{

    LISTINT::iterator i;

    int minValue;
    if(n == 1)
    {
        i = list_org.begin();
        minValue = d[*i - 1][0];
        if(list_org.size() == matrix_length - 1)
        {
            list_result = list_org;
        }
    }
    else
    {
        int temp;
        i = list_org.begin();
        temp = *i;
        list_org.erase(i);
        i = list_org.begin();
        minValue = d[temp - 1][*(i) - 1] + getPath(n - 1, list_org);
        if(list_org.size() == matrix_length - 1)
        {
            list_result = list_org;
        }

        for(int j = 2; j < n; j++)
        {
            i = list_org.begin();
            for(int k = 1; k < j; k++)
            {
                i++;
            }

            int tempvalue = *i;
            list_org.erase(i);
            list_org.push_front(tempvalue);
            i = list_org.begin();
            tempvalue = d[temp - 1][*(i) - 1] + getPath(n - 1, list_org);

            if(tempvalue < minValue)
            {
                if(list_org.size() == matrix_length - 1)
                {
                    list_result = list_org;
                }
                minValue = tempvalue;
            }

        }
    }
    return minValue;
}
int main(int argc, char *argv[])
{

    LISTINT list_org;
    LISTINT::iterator h;
    list_org.push_front(4);
    list_org.push_front(3);
    list_org.push_front(2);
    list_org.push_front(1);
    cout << "旅行商问题动态规划算法" << endl;
    cout << "路线长度的矩阵表示如下 （-1表示无限大）" << endl;
    for(int j = 0; j < matrix_length; j++)
    {
        cout << endl;
        for(int k = 0; k < matrix_length; k++)
        {
            cout << " " << d[j][k];
        }
    }
    cout << endl;


    cout << "计算结果:" << getPath(4, list_org) << endl;
    list_result.push_front(1);
    list_result.push_back(1);
    cout << "要走的路径:---->:";
    for (h = list_result.begin(); h != list_result.end(); ++h)

        cout << *h << " ";


    cout << endl;
    int i;
    cin >> i;
    return 0;
}

#include<iostream>
using namespace std;

template<class T> //类型不限
void HeapAdjust(T A[], int a, int z)
{
    for(int i = a, j = 2 * i; j <= z; i = j, j = 2 * i) //i为父，j为子
    {
        if(j < z && A[j + 1] > A[j]) j++; //大顶堆，沿大孩子方向下行
        if(A[i] < A[j])
            swap(A[i], A[j]);
        else
            break;
    }
}

template<class T>
void HeapSort(T A[], int n)
{
    for(int i = n / 2; i >= 1; i--) //从倒数第一个非叶子结点，自下而上堆化
        HeapAdjust(A, i, n);
    for(int i = n; i > 1; i--) //交换A[1]与最后元素A[i]（i=n, ..., 1）, 再堆化
    {
        swap(A[1], A[i]);
        HeapAdjust(A, 1, i - 1);
    }
}

int main()
{
    int len = 5;
    int A[] = {0, 9, 7, 5, 6, 4};

    HeapSort(A, len);

    for(int i = 1; i <= len; i++)
        cout << A[i] << ' ';
    cout << endl;
    return 0;
}

#include"stdio.h"
#define Maxv 100
#define INF 100000
void ppath(int path[][Maxv], int i, int j)
{
    int k;
    k = path[i][j];
    if(k == -1)return;
    ppath(path, i, k);
    printf("%d,", k);
    ppath(path, k, j);
}
void Dispath(int A[][Maxv], int path[][Maxv], int n)
{
    int i, j;
    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++)
        {
            if(A[i][j] != INF && A[i][j] != 0)
            {
                printf("从%d到%d的路径为:", i, j);
                printf("%d,", i);
                ppath(path, i, j);
                printf("%d", j);
                printf("路径长度为:%d\n", A[i][j]);
            }
        }
}
void Flofd(int A[][Maxv], int n)
{
    int i, j, k, path[Maxv][Maxv];
    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++)
            path[i][j] = -1;
    for(k = 0; k < n; k++)
        for(i = 0; i < n; i++)
            for(j = 0; j < n; j++)
                if(A[i][j] > A[i][k] + A[k][j])
                {
                    A[i][j] = A[i][k] + A[k][j];
                    path[i][j] = k;
                }
    Dispath(A, path, n);
}
int main()
{
    int n = 4, path[Maxv][Maxv];
    int A[][Maxv] = {{0, 5, INF, 7},
        {INF, 0, 4, 2},
        {3, 3, 0, 2},
        {INF, INF, 1, 0}
    };
    Flofd(A, n);
}

#include<iostream>
using namespace std;

long i, j, k, x, y, z, n;
long a[10001];

void qsort(long l, long r)
{
    long i = l, j = r, x = a[(l + r) / 2], y;
    do
    {
        while(a[i] < x)i++;
        while(a[j] > x)j--;
        if(i <= j)
        {
            y = a[i];
            a[i] = a[j];
            a[j] = y;
            i++;
            j--;
        }
    }
    while(i < j);
    if(i < r)qsort(i, r);
    if(j > l)qsort(l, j);
}

int main()
{
    cin >> n;
    for(i = 1; i <= n; i++)cin >> a[i];
    qsort(1, n);
    for(i = 1; i <= n; i++)cout << a[i] << ' ';
    cout << endl;
    system("pause");
    return 0;
}

#include<stdio.h>

// 一个递归函数
void mergesort(int *num, int start, int end);
// 这个函数用来将两个排好序的数组进行合并
void merge(int *num, int start, int middle, int end);

int main()
{
    // 测试数组
    int num[10] = {12, 54, 23, 67, 86, 45, 97, 32, 14, 65};
    int i;
    // 排序之前
    printf("Before sorting:\n");
    for (i = 0; i < 10; i++)
    {
        printf("%3d", num[i]);
    }
    printf("\n");
    // 进行合并排序
    mergesort(num, 0, 9);
    printf("After sorting:\n");
    // 排序之后
    for (i = 0; i < 10; i++)
    {
        printf("%3d", num[i]);
    }
    printf("\n");
    return 0;
}

//这个函数用来将问题细分

void mergesort(int *num, int start, int end)
{
    int middle;
    if(start < end)
    {
        middle = (start + end) / 2;
        // 归并的基本思想
        // 排左边
        mergesort(num, start, middle);
        // 排右边
        mergesort(num, middle + 1, end);
        // 合并
        merge(num, start, middle, end);
    }
}

//这个函数用于将两个已排好序的子序列合并

void merge(int *num, int start, int middle, int end)
{

    int n1 = middle - start + 1;
    int n2 = end - middle;
    // 动态分配内存，声明两个数组容纳左右两边的数组
    int *L = new int[n1 + 1];
    int *R = new int[n2 + 1];
    int i, j = 0, k;

    //将新建的两个数组赋值
    for (i = 0; i < n1; i++)
    {
        *(L + i) = *(num + start + i);
    }
    // 哨兵元素
    *(L + n1) = 1000000;
    for (i = 0; i < n2; i++)
    {
        *(R + i) = *(num + middle + i + 1);
    }
    *(R + n2) = 1000000;
    i = 0;
    // 进行合并
    for (k = start; k <= end; k++)
    {
        if(L[i] <= R[j])
        {
            num[k] = L[i];
            i++;
        }
        else
        {
            num[k] = R[j];
            j++;
        }
    }
    delete [] L;
    delete [] R;
}

#include "process.h"
#include "stdio.h"
#include "assert.h"

const int stackIncreament = 6; //栈溢出时扩展空间的增量

class SeqStack
{
private:
    int top;                    //栈顶指针
    int MAX;                    //栈的最大可容纳个数
    int *elements;              //存放栈中元素的栈数组
    void overflowProcess();     //栈的溢出处理
public:
    SeqStack(int sz = 50);      //构造函数
    ~SeqStack()
    {
        delete[]elements;    //析构函数
    }
    bool pop1(int &x);          //元素出栈
    void push1(const int &x);   //新元素进栈
    bool IsEmpty1()const;       //判断栈空与否
    bool IsFull1()const;        //判断栈满与否
    void output1();              //输出元素进栈顺序
    void output(int x);          //输出x

};

SeqStack::SeqStack(int sz): top(-1), MAX(sz)
{
    elements = new int[MAX];   //创建栈的数组空间
    assert(elements != NULL);  //断言：动态存储分配成功与否
}

bool SeqStack::pop1(int &x)          //栈顶元素出栈
{
    if(IsEmpty1() == true) return false; //判栈空否，若栈空则函数返回
    x = elements[top--];           //栈顶指针退1
    return true;                   //退栈成功
}

void SeqStack::push1(const int &x)     //新元素进栈
{
    if(IsFull1() == true)  overflowProcess(); //栈满则溢出处理
    elements[++top] = x;      //栈顶指针先加1,再进栈
}

bool SeqStack::IsEmpty1() const   //判断栈空与否
{
    return (top == -1) ? true : false;
}

bool SeqStack::IsFull1()const    //判断栈满与否
{
    return (top == MAX - 1) ? true : false;
}

void SeqStack::overflowProcess()  //栈的溢出处理
{
    //私有函数，扩充栈的存储空间。
    int *Array = new int[MAX + stackIncreament];   //和课本不一样 ??????????
    if(Array == NULL)
    {
        printf("存贮分配失败 ! \n");
        exit(1);
    }
    for(int i = 0; i <= top; i++)   Array[i] = elements[i];
    MAX = MAX + stackIncreament;
    delete []elements;
    //elements=Array;
}

void SeqStack::output1()              //元素入栈顺序输出
{
    int n = 0;
    int t = top;
    for(int i = 0; i < top; i++)
    {
        printf("  %d", elements[i]);
        n++;
        if(n % 10 == 0)
            printf("\n");
    }
}

void SeqStack::output(int x)              //栈内元素输出
{
    printf("  %d", x);
}

//----------------------顺序栈函数--------------------------//
void SeqStack1( SeqStack  A)
{
    int x = -1;
    int X;
    printf("请输入要入栈A的元素值,以0结束：\n");
    while(x != 0)                  //新元素进栈
    {
        scanf("%d", &x);
        A.push1(x);
    }
    printf("\n元素进栈顺序是 :");
    A.output1();
    printf("\n\n");

    A.pop1(X);            //元素出栈
    if(!A.pop1(X))
        printf("元素出栈失败 ！\n");
    else
    {
        printf("\n栈顶元素是：  ");
        A.output(X);
        printf("\n");
        printf("\n元素出栈的结果是 : ");
        A.output(X);
        while(A.pop1(X))
            A.output(X);
    }
}

void main()
{
    printf("----------顺序栈的调试----------\n");
    printf("\n \n");
    SeqStack  A;
    SeqStack1(A);
    printf("\n \n");
}

#include<iostream>
using namespace std;



void main()
{

    int data[50][50];

    int maxvalue[50][50];

    int path[50][50];


    int i, j, n;
    cout << "please input the number of rows:";
    cin >> n;
    cout << "please input the date of several tower:" << endl;
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= i; j++)
        {

            cin >> data[i][j];
            maxvalue[i][j] = data[i][j];
            path[i][j] = 0;
        }
    }
    for(i = n - 1; i >= 1; i--)
    {
        for(j = 1; j <= i; j++)
        {
            if(maxvalue[i + 1][j] > maxvalue[i + 1][j + 1])
            {
                maxvalue[i][j] = maxvalue[i][j] + maxvalue[i + 1][j];
                path[i][j] = 0;
            }
            else
            {
                maxvalue[i][j] = maxvalue[i][j] + maxvalue[i + 1][j + 1];
                path[i][j] = 1;
            }
        }
    }
    cout << "maxvalue=" << maxvalue[1][1] << endl;
    j = 1;
    cout << "path:";
    for(i = 1; i <= n - 1; i++)
    {
        cout << data[i][j] << "-->";
        j = j + path[i][j];
    }
    cout << data[n][j] << endl;
}

#include <iostream>
using namespace std;

#define N 9
int P[N][N];

void fill (int number, int begin, int size)
{
    if (size == 0)
        return ;
    if (size == 1)
    {
        P[begin][begin] = number;
        return ;
    }
    int i = 0;
    int h = begin, v = begin;
    P[h][v] = number;
    number++;

    for (i = 0; i < size - 1; i++)
    {
        h++;
        P[h][v] = number;
        number++;
    }
    for (i = 0; i < size - 1; i++)
    {
        v++;
        P[h][v] = number;
        number++;
    }
    for (i = 0; i < size - 1; i++)
    {
        h--;
        P[h][v] = number;
        number++;
    }
    for (i = 0; i < size - 2; i++) //修改的地方
    {
        v--;
        P[h][v] = number;
        number++;
    }
    fill(number, v, size - 2);

}
int main ()
{
    fill(1, 0, N);

    int h, v;
    for (h = 0; h < N; h++)
    {
        for (v = 0; v < N; v++)
            cout << P[h][v] << '\t';
        cout << '\n';
    }
    return 0;
}

#include<stdio.h>

void main()
{
    int i, j, min, temp;
    int a[10];
    printf("请输入十个整数:");
    for(i = 0; i <= 9; i++)
        scanf("%d", &a[i]);
    for(i = 0; i < 9; i++)
    {
        min = i;
        for(j = i + 1; j <= 9; j++)
        {
            if(a[min] > a[j])
            {
                min = j;
            }
            temp = a[j];
            a[j] = a[min];
            a[min] = temp;
        }
    }
    for(i = 0; i <= 9; i++)
        printf("%4d", a[i]);
}

#include<stdio.h>

void main()
{
    int i, j, temp;
    int a[10];
    printf("请输入十个整数:");
    for(i = 0; i <= 9; i++)
        scanf("%d", &a[i]);
    for(i = 0; i < 9; i++)
        for(j = 9; j > i; j--)
        {
            if(a[j] < a[j - 1])
            {
                temp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = temp;
            }
        }
    /*
     for(j=0;j<9-i;j++)
     {
      if(a[j]>a[j+1])
      {
        temp=a[j];
        a[j]=a[j+1];
        a[j+1]=temp;
      }
     }大的气泡往下沉，小的气泡往上浮！！！注意：是a[j-1]还是a[j+1]；
     深刻了解！！！
    */
    for(i = 9; i >= 0; i--)
        printf("%4d", a[i]);
}

#include<iostream>
using namespace std;
int binary_search(char *data, int len, char target)
{
    int high = len - 1, low = 0, mid;
    mid = (high + low) / 2;
    while(high >= low)
    {
        if(target > data[mid])
            low = mid + 1;
        else if(target < data[mid])
            high = mid - 1;
        else return mid;
        mid = (high + low) / 2;
    }
    return -1;
}
int main()
{
    char a[] = "abcdefghijklmn";
    char taget;
    cout << "输入要查找的字符\n";
    cin >> taget;
    int i = binary_search(a, strlen(a), taget);
    if(i == -1)
        cout << "Not Foun!\n";
    else
        cout << "Found  " << a[i] << " in the " << i + 1 << " position";
    return 0;
}

#include <iostream>
#define N 5
using namespace std;


#include <iostream>
#include <cstring>
using namespace std;

class node
{
public:
    node(int i): data(i), left(NULL), right(NULL) {}
    void inorder(node *&root)      //中序遍历，符合升序输出
    {
        if(root != NULL)
        {
            inorder(root->left);
            cout << root->data << ' ';
            inorder(root->right);
        }
    }
    void insert(node *&ptr, int item) //在查找树中插入元素
    {
        if(ptr == NULL)
            ptr = new node(item);
        else if(item < ptr->data)
            insert(ptr->left, item);
        else insert(ptr->right, item);
    }
    node *find(node *&ptr, int item) //在查找树中查找元素,找到返回所在结点指针，找不到返回空指针。
    {
        if(ptr == NULL)
            return NULL;
        if(ptr->data == item)
            return ptr;
        else if(item < ptr->data)
            find(ptr->left, item);
        else find(ptr->right, item);
    }
    node *&findy(node *&ptr, int item) //在查找树中查找肯定存在的元素,并返回其引用
    {
        if(ptr->data == item)
            return ptr;
        else if(item < ptr->data)
            findy(ptr->left, item);
        else findy(ptr->right, item);
    }
    void printfind(node *&ptr, int item) //在查找树中查找元素,并输出经过路径
    {
        if(ptr->data == item)
        {
            cout << item << endl;
            return;
        }
        else if(item < ptr->data)
        {
            cout << ptr->data << ' ' << endl;
            printfind(ptr->left, item);
        }
        else
        {
            cout << ptr->data << ' ' << endl;
            printfind(ptr->right, item);
        }
    }
    node *rl()
    {
        return left;
    }
    node *rr()
    {
        return right;
    }
    void dele(node *&ptr)       //删除值为item所在结点
    {
        if(ptr->rl() == NULL && ptr->rr() == NULL)
            ptr = NULL;
        else if(ptr->rr() == NULL)
            ptr = ptr->rl();
        else if(ptr->rl() == NULL)
            ptr = ptr->rr();
        else
        {
            node *temp = ptr->rl();
            ptr = ptr->rr();
            node *temp2 = ptr;
            while(temp2->rl() != NULL)
                temp2 = temp2->rl();
            temp2->setl(temp);
        }
    }
    void setl(node *l)
    {
        left = l;
    }
private:
    int data;
    node *left;               //左孩子结点
    node *right;              //右孩子结点
};

int main()
{
    char a[10];
    int t, i = 0, j;
    cout << "输入数字个数:";
    cin >> t;
    cout << "输入" << t << "个数字，数字之间用空格隔开:";
    cin >> j;
    node *x = new node(j);
    for(; i < t - 1; i++)
    {
        cin >> j;
        x->insert(x, j);
    }
    cout << "输入操作(当输入串为(0 0)时结束程序):" << endl;
    cin >> a >> j;
    while(strcmp(a, "0") != 0)
    {
        if(strcmp(a, "S") == 0)
        {
            if(x->find(x, j) == NULL)
                cout << "-1" << endl;
            else
                x->printfind(x, j);
        }
        else if(strcmp(a, "D") == 0)
        {
            node *t = x->find(x, j);       //定位结点
            if(t != NULL)
            {
                node *&y = x->findy(x, j);
                x->dele(y);
            }
            x->inorder(x);
        }
        cout << "\n输入操作(当输入串为0时结束程序):" << endl;
        cin >> a >> j;
    }
    return 0;
}