算法与数据结构

作者: chappie2017 | 来源:发表于2017-06-28 22:57 被阅读0次

数据结构与算法 - 查找
思维导图之数据结构+算法
数据结构与算法 - 树形结构
最新完整数据结构与算法
数据结构与算法
算法与数据结构（1），List
数据结构与算法-目录
算法与数据结构（3），并发结构
算法与数据结构（2），Map
数据结构与算法

1.深度优先搜索

下面是深度优先搜索遍历的一个例子，我们用整数标记节点，G记录有向边，G[u][v]表示节点u指向节点v。用数组c[M]记录遍历状态：
c[u]==-1----表示u被dfs调用，但还没有返回
c[u]==0----表示从来没有遍历过
c[u]==1----表示已经遍历并返回

#include <iostream>

#define M 100
int c[M];
int G[M][M];
bool dfs(int u){
    c[u]=-1;
    for(int v=0; v<M ; ++v)
        if(G[u][v]){
            if(c[v]==-1) return false;//说明有环
            if(c[v]==0 && !dfs(v) ) return false;//如果c[v]是0，则遍历v，此时如果子图有环，则停止遍历，返回false
        }
    std::cout<<u<<std::endl;
    c[u]=1;
    return true;
}

从注释也容易看出来了，深度优先搜索可以用来判断一个图是否有环。另外，深度优先搜索的顺序，恰恰满足拓扑排序

2.欧拉回路

2.1.无向图

我们把和一个点相连的边数是这个点的度数，因为一条边对应于两个点，因此，所有点的度数之和肯定是偶数。
一笔画的充要条件是：除了起点和终点外，其它点的度数一定是偶数。

2.2.有向图

对于有向图，除了起点终点外，入度等于出度，并且，起点的出度比入度大1，终点的入度比出度大1.

3.子集生成

我们把问题简化：假设集合有n个元素，是从1到n的整数。

3.1.增量构造法

A表示集合数组，n是集合数组内元素的个数，cur表示子集中元素的数目，当然，cur==0表示空集，此外，我们还假设，最开始的时候，A已经排好了序。

void print_sub_set(int A[], int n, int cur){
    for(int i=0 ; i<cur; ++i)
        std::cout<<A[i]<<" "<<std::flush;
    std::cout<<std::endl;
    int s=cur?A[cur-1]:0;
    for(int i=s ; i<n ; i++){
        A[cur]=i+1;
        print_sub_set(A ,n, cur+1);
    }
}

3.2.位向量法

对于每一个元素，用一个位表示它是否在子集中

void bit_vector(int B[], int n , int cur){
    if(cur==n){
        for(int i=0 ; i<n ; ++i)
            if(B[i])
                std::cout<<i+1<<std::flush;
        std::cout<<std::endl;
        return;
    }
    B[cur]=1;
    bit_vector(B, n, cur+1);
    B[cur]=0;
    bit_vector(B, n, cur+1);
}

3.3.二进制法

位向量法就是一种二进制法，此外，集合的并，交，差等运算，是可以转化成二进制运算的，所以。。。

4.回溯法

回溯法在递归构造中，把生成和检查结合起来，有效减少不必要的枚举。
举例：n皇后问题

void queen_(int *A , int n, int cur , int *tot){
    if(cur==n) ++(*tot);
    else for(int i=0; i<n ;++i){
        A[cur]=i;
        bool ok=true;
        for(int j=0; j<cur ; ++j)
            if(A[j]==A[cur] || A[j]+j==A[cur]+cur || A[j]-j==A[cur]-cur) ok=false;
        if(ok) queen_(A, n, cur+1, tot);
    }
}

int queen(int n){
    int *A=new int[n];
    int tot=0;
    queen_(A, n , 0 , &tot);
    delete[] A;
    return tot;
}

5.广度优先搜索

比如二叉树层次遍历，就是广度优先搜索的一个例子。我们用一个先进先出的队列，实现了树的广度优先搜索
对于图，仍然是要用队列来实现广度优先搜索，然而，图的情况稍微复杂，除了采用队列外，还应该引入另外的数据结构，来防止节点被重复遍历到。
举例：八数码问题
其实八数码问题可以归结为路径寻找问题，把每个状态看做一个节点，移动空格相邻的滑块，到达另一个节点，因此每种移动方式可以看做是一条边。
因为是图，因此需要特定的数据结构记录那些节点被遍历过了，如果考虑用一个数来表示，比如序列123456780就用123456780表示，这将耗费9^9这么多的空间，如果采用int型存储，这将是几百M的空间，显然这是不合理的。实际上，节点总数只有9！=362880，只有几M的空间，因此，我们需要一种编码方式，使得每个状态，和0到362880之间的整数一一对应，一种方式就是按字典序映射，下面的代码实现了这个功能：

#include <iostream>

int encode(int *A, int n){
    if(A==NULL || n<1)
        return -1;
    if(n==1)
        return 0;
    int *table=new int[n];
    table[0]=1;
    for(int i=1 ; i< n ; ++i)
        table[i]=table[i-1]*i;
    int *exist=new int[n];
    for(int i=0 ; i<n ; ++i)
        exist[i]=0;
    int sum=0;
    for(int i=0; i<n-1 ; ++i ){
        int temp=A[i];
        exist[temp]=1;
        for(int j=0 ; j<A[i] ;++j)
            if(exist[j])
                --temp;
        sum+=temp*table[n-1-i];
    }

    delete[] table;
    delete[] exist;

    return sum;
}

int decode(int A[], int n, int code){
    if(A==NULL || n<1 || code<0)
        return 0;
    int *table=new int[n+1];
    table[0]=1;
    for(int i=1 ; i< n+1 ; ++i)
        table[i]=table[i-1]*i;
    if(code >=table[n])
        return -1;
    int *exist=new int[n];
    for(int i=0 ; i<n ; ++i)
        exist[i]=0;
    int rank;
    for(int i=0; i<n ; ++i){
        int val;
        rank=code/table[n-1-i];
        for(int j=0 ; j<n ; ++j){
            if(!exist[j])
                --rank;
            if(rank<0){
                val=j;
                break;
            }
        }
        A[i]=val;
        exist[val]=1;
        code=code%table[n-1-i];
    }
    return 1;
}


/********test***************/

void print(int *A, int n){
    for(int i=0; i<n ; ++i)
        std::cout<<A[i]<<" "<<std::flush;
    std::cout<<std::endl;
}

int main(){

    int n;
    while(std::cin>>n){
        if(n<=0)
            break;
        int *A=new int[n];
        int code=0;
        int term=1;
        while(term==1){
            term=decode(A, n, code);
            if(term != 1)
                break;
            int t=encode(A, n);
            if(code != t){
                std::cout<<"wrong !"<<std::endl;
                std::cout<<"A:"<<std::endl;
                print(A, n);
                std::cout<<"code: "<<code<<std::endl;
                std::cout<<"encode: "<<t<<std::endl;
                break;
            }
            ++code;
        }
        std::cout<<"code: "<<code<<std::endl;
        delete[] A;
    }

    return 0;
}

利用上面编码规则，对八数码问题的解决办法：

/*
这个代码调试的也让人累觉不爱了。。。
1.memcpy函数按字节数拷贝内存，所以，是9*sizeof(int), 而不是9！！！
2.突然冒出个想法：不必要对d进行pop_front操作，把迭代器向前移动就可以了，然而。。。当插入或删除vector内的元素的时候，面临这迭代器失效问题。。。囧。。。
3.为了避免死循环，father对start也要有记录
*/
#include <iostream>
#include <vector>
#include <cstring>

int encode(int *A, int n){
    if(A==NULL || n<1)
        return -1;
    if(n==1)
        return 0;
    int *table=new int[n];
    table[0]=1;
    for(int i=1 ; i< n ; ++i)
        table[i]=table[i-1]*i;
    int *exist=new int[n];
    for(int i=0 ; i<n ; ++i)
        exist[i]=0;
    int sum=0;
    for(int i=0; i<n-1 ; ++i ){
        int temp=A[i];
        exist[temp]=1;
        for(int j=0 ; j<A[i] ;++j)
            if(exist[j])
                --temp;
        sum+=temp*table[n-1-i];
    }

    delete[] table;
    delete[] exist;

    return sum;
}

int decode(int A[], int n, int code){
    if(A==NULL || n<1 || code<0)
        return 0;
    int *table=new int[n+1];
    table[0]=1;
    for(int i=1 ; i< n+1 ; ++i)
        table[i]=table[i-1]*i;
    if(code >=table[n])
        return -1;
    int *exist=new int[n];
    for(int i=0 ; i<n ; ++i)
        exist[i]=0;
    int rank;
    for(int i=0; i<n ; ++i){
        int val;
        rank=code/table[n-1-i];
        for(int j=0 ; j<n ; ++j){
            if(!exist[j])
                --rank;
            if(rank<0){
                val=j;
                break;
            }
        }
        A[i]=val;
        exist[val]=1;
        code=code%table[n-1-i];
    }
    return 1;
}


int main(){

    std::vector<int> father(362880);
    std::vector<int> dist(362880);
    int dx[]={-1, 1, 0, 0};
    int dy[]={0, 0, -1, 1};

    int goon;
    std::cout<<"go on ??"<<std::endl;
    while (std::cin>>goon) {
        if(goon==0)
            break;

        int *star=new int[9];
        int *dest=new int[9];
        std::cout<<"input start:"<<std::endl;
        for(int i=0 ; i<9 ; ++i)
            std::cin>>star[i];
        std::cout<<"input dest:"<<std::endl;
        for(int i=0; i<9 ; ++i)
            std::cin>>dest[i];

        for(auto &s:father)
            s=-1;
        std::vector<int> d;
        int estar=encode(star, 9);
        int edest=encode(dest, 9);
        d.push_back(estar);
        dist[d[0]]=0;
        father[d[0]]=d[0];
        int front=0;
        while(front != d.size()){
            int cur=d[front];
            int S[9];
            decode(S, 9, cur);
            int z;
            for(z=0; z < 9 ; ++z)
                if(S[z]==0)
                    break;
            int row=z/3;
            int col=z%3;

            bool ok=false;
            for(int di=0; di<4 ; ++di){
                int nrow=row+dx[di];
                int ncol=col+dy[di];
                if(nrow>=0 && nrow<3 && ncol>=0 && ncol<3){

                    int nz=nrow*3+ncol;
                    int nS[9];
                    std::memcpy(&nS[0], &S[0], 9*sizeof(int));
                    nS[z]=nS[nz];
                    nS[nz]=0;
                    int enS=encode(nS, 9);
                    if(father[enS] == -1){

                            father[enS]=cur;
                            dist[enS]=dist[cur]+1;
                            if(enS==edest){
                                ok=true;
                                break;
                            }
                            d.push_back(enS);

                    }
                }
            }
            if(ok)
                break;
            ++front;

        }

        std::cout<<"shortest: "<<dist[edest]<<std::endl;
        
        delete[] star;
        delete[] dest;
        std::cout<<"go on ??"<<std::endl;

    }
    return 0;
}

/*
2 6 4 1 3 7 0 5 8
8 1 5 7 3 6 4 0 2
*/

也可以用map结构来记录哪些被搜索过了。我们知道，map采用树的结构存储的。查找，插入等时间复杂度是O(logn)，因此比前面的方法慢些。为了便于讨论，我们省去了father，只用dist记录:

#include <iostream>
#include <vector>
#include <map>
#include <cstring>

int encode(int A[], int n){
    int sum=0;
    for(int i=0; i< n ; ++i)
        sum=sum*10+A[i];
    return sum;
}

void decode(int A[], int n , int code){
    for(int i=n-1; i>=0 ; --i){
        A[i]=code%10;
        code/=10;
    }
}

int main(){

    int dx[]={-1, 1, 0, 0};
    int dy[]={0, 0, -1, 1};

    int goon;
    std::cout<<"go on ??"<<std::endl;
    while (std::cin>>goon) {
        if(goon==0)
            break;

        int *star=new int[9];
        int *dest=new int[9];
        std::cout<<"input start:"<<std::endl;
        for(int i=0 ; i<9 ; ++i)
            std::cin>>star[i];
        std::cout<<"input dest:"<<std::endl;
        for(int i=0; i<9 ; ++i)
            std::cin>>dest[i];

        std::map<int, int> dist;

        std::vector<int> d;
        int en_star=encode(star, 9);
        int en_dest=encode(dest, 9);
        d.push_back(en_star);
        dist[en_star]=0;
        int front=0;
        while(front != d.size()){
            int cur=d[front];
            int S[9];
            decode(S, 9, cur);
            int z;
            for(z=0; z<9 ; ++z)
                if(S[z]==0)
                    break;
            int row = z/3;
            int col = z%3;
            bool ok=false;
            for(int i=0; i<4 ; ++i){
                int nrow=row+dx[i];
                int ncol=col+dy[i];
                if(nrow>=0 && nrow<3 && ncol>=0 && ncol<3){
                    int nz=nrow*3+ncol;
                    int nS[9];
                    memcpy(nS, S, 9*sizeof(int));
                    nS[z]=nS[nz];
                    nS[nz]=0;
                    int enS=encode(nS, 9);
                    if(dist.find(enS) == dist.end()){
                        dist[enS]=dist[cur]+1;
                        if(enS==en_dest){
                            ok=true;
                            break;
                        }
                        d.push_back(enS);
                    }
                }
            }

            if(ok)
                break;

            ++front;
        }

        if(dist.find(en_dest) != dist.end())
            std::cout<<"shortest steps: "<<dist[en_dest]<<std::endl;
        else
            std::cout<<"do not exist ! ! ! "<<std::endl;

        delete[] star;
        delete[] dest;
        std::cout<<"go on ??"<<std::endl;

    }
    return 0;
}

/*
2 6 4 1 3 7 0 5 8
8 1 5 7 3 6 4 0 2
*/