算法基础1

模板

函数模板

语法形式：
template<模板参数表>
函数定义
模板参数表的内容
类型参数 class(或typename)标识符
常量参数 类型说明符 标识符
模板参数 template<参数表>class标识符

函数模板示例：

#include<iostream>
using namespace std;
template <class T>
void outputArray(const T *array,int count){
    for (int i=0;i<count;i++){
        cout<<array[i]<<" ";
    }
    cout<<endl;
}
int main(){
    const int A_COUNT=8,B_COUNT=8,C_COUNT=20;
    int a[A_COUNT]={1,2,3,4,5,6,7,8};
    double b[B_COUNT]={1.1,2.2,3.3,4.4,5.5,6.6,7.7,8.8};
    char c[C_COUNT]="welcome!";
    cout<<"a array contains:"<<endl;
    outputArray(a,A_COUNT);
    cout<<"b array contains:"<<endl;
    outputArray(b,B_COUNT);
    cout<<"c array contains:"<<endl;
    outputArray(c,C_COUNT);
    return 0;
}

类模板

类模板的声明
类模板
template<模板参数表>
class类名
{类成员声明}
如果需要在类模板以外定义其成员函数，则要采用以下的形式:
template<模板参数表>
类型名 类名<模板参数标识符列表>：：函数名(参数表)
void Store::putElem(const T &x)
例子：

#include <iostream>
#include<cstdlib>
using namespace std;
struct Student
{
    int id;
    float gpa;
};
template <class T>
class Store{
    //类模板实现对任意数据进行存取
private:
    T item;//用于存放任意类型数据
    bool haveValue;//标记item是否已被存入内容
public:
    Store();
    T &getElem();//提取数据函数
    void putElem(const T &x);//存入数据函数
};
template<class T>
Store<T>::Store():haveValue(false){}
template <class T>
T&Store<T>::getElem(){
    //如果试图提取未初始化的数据，则终止程序
    if(!haveValue){
        cout<<"No item present!"<<endl;
        exit(1);//退出程序返回操作系统
    }
    return item;//返回item中存放的数据
}
template <class T>
void Store<T>::putElem(const T &x){
    haveValue=true;
    item=x;
}
int main(){
    Store<int> s1,s2;
    s1.putElem(3);
    s2.putElem(-7);
    cout<<s1.getElem()<<" "<<s2.getElem()<<endl;
    Student g={1000,23};
    Store<Student> s3;
    s3.putElem(g);
    cout<<"The Student id is "<<s3.getElem().id<<endl;

    Store<double>d;
    cout<<"Retrieving object D..";
    cout<<d.getElem()<<endl;//d未初始化，执行函数D.getElement()时导致程序终止
    return 0;
}

线性群体

线性群体中的元素次序与其逻辑位置关系是对应的。在线性群体中又可以按照访问元素的不同方法分为直接访问，顺序访问和索引访问
在这里结合扫直接访问和顺序访问

链表类

链表是一种动态数据结构，可以用来表示顺序访问的线性群体
链表是由系列结点组成的，结点可以在运行时动态生成
每一个结点包括数据域和指向链表中下一个结点的指针
（即下一个结点的地址).如果链表每个结点中只有一个指向后继结点的指针，则该链表称为单链表

栈

栈空
栈满
一般状态

栈的基本操作

初始化
入栈
出栈
清空栈
访问栈顶元素
检测栈的状态（满，空）

队列

只能向一端添加元素，从另一端删除元素的线性群体
先进先出
队列的基本状态
队空
队满
一般状态

排序

数据元素：数据的基本单位。在计算机中通常作为一个整体进行考虑。一个数据元素可由若干数据项组成
关键字： 数据元素中某个数据项的值，用它可以标识一个数据元素
在排序过程中需要完成两种基本操作：
比较两个数的大小
调整元素在序列中的位置

内部排序：待排序的数据元素存放在计算机内存中，内存足够容纳所有元素的情况下 内部排序比较。
外部排序：数据规模较大的情况分批次比较，需要对外存进行访问的排序过程。

选择排序

选择排序的基本思想
每次从待排序序列中选择一个关键字最小的元素，
（当需要按关键字升序排列时），
顺序排在已排序序列的最后，直到全部排完

简单选择排序函数模板

template<class T>
void myswap(T &x,T &y){
    T temp =x;
    x = y;
    y =temp;
}
template<class T>
void selectionSort(T a[],int n){
    for (int i =0;i<n-1;i++){
        int leastIndex = i;
        for (int j=i+1;j<n;j++)
            if (a[j]<a[leastIndex]){
                leastIndex = j;
            }
        myswap(a[i],a[leastIndex]);
    }
}

交换排序

最简单的交换排序方法–起泡排序

template<class T>
void myswap(T &x,T &y){
    T temp =x;
    x = y;
    y =temp;
}
void bubbleSort(T a[],int n){
    int i = n-1;
    while(i>0){
        int lastExchangeIndex = 0;
        for (int j =0;j<i;j++)
            if(a[j+1]<a[j]){
                myswap(a[j],a[j+1]);
                lastExchangeIndex = j;
            } 
            i= lastExchangeIndex;
    }
}

顺序查找

从序列的首元素开始，逐个元素与代查找的关键字进行比较，直到找到相等的。若整个序列没有与待查找关键字相等的元素，就是查找不成功。

template<class T>
//子函数调用时，并没有申请一个空间来存放形参key，也不用将实参的值传给形参key，因此使程序运行更简化。
int seqSearch(const T list[],int n,const T&key){
    for (int i= 0;i<n;i++)
        if(list[i] == key)
            return i;
    return -1;
}

二分法查找

对于已按关键字排序的序列，经过一次比较，可将序列分割成两部分，然后只在有可能包含待查元素的一部分中继续查找，并根据试探结果继续分割，逐步缩小查找范围，直到找到或找不到为止。
实现代码如下：

template<class T>
int binSearch(const T list[],int n,const T &key){
    int low =0;
    int high = n-1;
    while(low <= high){
        int mid = (low + high)/2;
        if (key == list[mid])
            return mid;
        else if(key < list)
            high = mid -1
        else
            low = mid +1

    }
    return -1;
}