emmm.....
自由选择什么的最扎心了,因为我是一个重度的选择困难症患者....
首先我选择的是图的遍历
题目:图的遍历
功能:实现图的深度优先,广度优先遍历算法,并输出原图结构及遍历结果。
实现要求:
(1)建立图的邻接矩阵或邻接表;
(2)实现图的遍历算法。
看起来很简单,所以我飞快地写了一段代码...就是创建图的邻接矩阵的算法了。代码如下:
<code lang="c++">
void CreateMap(Map &x) {
    cout << "请输入顶点个数" << endl;
    cin >> x.length;
    cout << "请依次输入顶点" << endl;
    for (int i = 0; i < x.length; i++) {
        cin >> x.vec[i];
        x.tag[i] = false;
    }
    cout << "请输入两个顶点间的距离:如a b 1" << endl;
    char a, b;
    int c;
    for (int i = 0; i < x.length; i++) {
        for (int j = 0; j < x.length; j++) {
            if (i == j) {
                x.rel[i][j] = 0;
            }
            else {
                x.rel[i][j] = -1; //先假设所有边都是未连接的,则边长度为无限,用-1代表
            }
        }
    }
    //如果两个顶点都存在,则将该输入数值放到关系数组里,否则提示关系不存在
    while (cin >> a >> b >> c) {
        if (a == '#'&&b == '#') break;
        if (findvec(x, a) && findvec(x, b)) { //如果能找到两条边,则把关系存起来
            for (int i = 0; i < x.length; i++) {
                if (x.vec[i] == a) {
                    for (int j = 0; j < x.length; j++) {
                        if (x.vec[j] == b) {
                             x.rel[i][j] = c;  //将关系加入数组里
                        }
                    }
                }
            }
        }
        else {
            cout << "顶点不存在" << endl;
        }
    }
}//图创建完成
</code>
但是问题来了,我突然发现我不知道深度遍历和广度遍历到底要输出啥....于是....迫不得已放弃了.....然后我选择了导游图....题目是这样的:
公园的导游图
问题描述::给出一张某公园的导游图,游客通过终端询问可知:
从某一景点到另一景点的最短路径。游客从公园大门进入,选一条最佳路线,使游客可以不重复地游览各景点,最后回到出口(出口就在入口旁边)。
实现要求:
初步完成总体设计,搭好框架,确定人机对话的界面,确定函数个数;
完成要求:建立一个文件,包括5个景点情况,能完成遍历功能;
进一步要求:进一步扩充景点数目,画出景点图,有兴趣的同学可以自己扩充系统功能。
乍一看好像还行,emmmm...只要输出一条最佳路线,然后我又开始写....用贪心从最短的路径里选一条不会重复走过景点的...代码如下:
<code lang="c++">
int dfs(Map &x,char start,int road=0) {
    int min=MAX,vec_next;
    if (isCheck(x)) {
        return road;
    }
    for (int i = 0; i < x.length; i++) {
        if (x.vec[i] == start) {
            x.tag[i] = true;
            for (int j = 0; j < x.length; j++) {
                if (x.rel[i][j] !=-1&&x.rel[i][j]!=0&&!x.tag[j]) { //如果当前路径的下一个路径未被标记,且存在路径,则将其入队    

                    if (min < x.rel[i][j]) {
                        min = min;
                    }
                    else {
                        min = x.rel[i][j];
                        vec_next = j;
                    }
                }
            }
        }
    }
    x.tag[vec_next] = true;
    road += min;
    cout << start << "——>" << x.vec[vec_next]<<" ";
    dfs(x, x.vec[vec_next], road);
}
</code>
emmmm....后来发现我想的太简单了...它居然还要一个人机交互界面!!!这玩意儿我没搞过呀....所以不得不浅浅的学了一波c++的MFC编程以及相关的函数什么的。
于是我学到了这两个函数:
<code lang="c++">
        CString str;
    Count.GetWindowTextW(str);
    COUNT.SetWindowTextW(str);
</code>
首先,我创建的MFC是基于对话框的,而不是基于多个文档的,其次,我用了一些控件:Button、Edit control、Static Text这三个,然后发现如果从Edit control中输入的数值是CString类型的,如果要将其变成int型的话,需要使用函数__ttoi(),然后我们需要用函数去获取窗口里的值,所以这个方法就是GetWindowTextW();
然后我们还要将其显示到另一个窗口,所以就需要用到SetWindowTextW()方法了;最后有一个小问题就是你需要修改一下Static Text的ID,否则无法给它绑定变量,虽然我也不知道为什么,但是这样做就对了....
接着,我又发现问题了,因为我又回去看了一遍题目.....突然发现出口在入口旁边!!!所以,上面那个代码没用了....但是一时我又没有想到该去怎么写那个算法,所以不得已...放弃了,时间不是很多了,所以我只好选一个简单的,最后我选了一个拓扑排序,这个比较简单。
<b>拓扑排序</b>
接下来就是拓扑排序的内容了:
图的算法实现
问题描述:图的存储结构的建立和拓扑排序算法。
实现要求:
(1)建立图的邻接矩阵或邻接表;
(2)实现拓扑排序算法。
之所以选拓扑排序是有原因的,因为构建图的邻接矩阵的算法我之前已经做了,所以复制一下,根据需求再改一下就可以了。
接下来就是拓扑排序的算法了,拓扑排序就是将入度为0的顶点放入队列,但是其实我感觉我的理解也没错,那就是如果没有边指向这个顶点,或者所有指向这个顶点的边的出发顶点都已经被放入队列里了,可以将这个顶点放入队列,这个应该就是算法的实现了。接下来还有一个要考虑的,就是回路的情况,对存放所有节点的数组进行遍历,如果剩下所有的顶点都有边指向这个顶点,或者所有的顶点都是有的指向这个顶点的边的顶点没有放入队列里,那么就是有回路存在了,将有回路存在的情况输出,并将剩下的还未放入队列的顶点输出,证明回路在这些顶点中产生。所以要创建一个函数来判断是否所有的顶点都已经放入队列,在没有所有的顶点都放入队列的情况下就是行拓扑排序。判断是否所有顶点都已入队的函数如下:
<code lang="c++">
bool isCheck(Map &x) { //如果全部的标记都为真,则说明所有顶点都已经被遍历
    for (int i = 0; i < x.length; i++) {
        if (!x.tag[i]) return false;
    }
    return true;
}
还要一个函数用来判断是否所有存在回路。代码如下:
<code lang="c++">
bool isNot(Map &x,int y) { //该函数用来判断当前顶点是否有指针指向它,如果有一个指针指向它,则返回假,否则返回真
    for (int i = 0; i < x.length; i++) {
        if (i == y) continue;
        if (x.rel[i][y] > 0&&!x.tag[i]) {
            return false;
        }
    }
    return true;
}
</code>
接下来就是拓扑排序的函数的代码了:
<code lang="c++">
void DAG(Map &x) { //找出节点没有线指向它的
    queue<char> p;
    while (!isCheck(x)) {
        int tag=false;
        for (int i = 0; i < x.length; i++) { //遍历顶点表,如果在剩下的顶点中全部的顶点都有指针指向它,则直接结束执行,并输出
            if (x.tag[i] == false && isNot(x, i)) {  //如果有一个顶点是没有指针指向它的,则将tag改为真
                tag = true;
            }
        }
        if (!tag) {
            cout << "剩下的顶点无法进行拓扑排序" << endl;
            cout << "剩下的顶点是 ";
            for (int i = 0; i < x.length; i++) {
                if (!x.tag[i]) {
                    cout << x.vec[i] << " ";
                }
            }
            cout << endl;
            return;
        }
        for (int i = 0; i < x.length; i++) { //遍历整个顶点表,挑出没有指针指向它的顶点
            if (isNot(x, i)) { //如果没有指向当前顶点的指针,并且该顶点没有被标记,则将其放入队列
                p.push(x.vec[i]);
                x.tag[i] = true;
            }
        }
    }
    while (!p.empty()) {
        cout << p.front() << " ";
        p.pop();
    }
    cout << endl;
}
</code>
emmmm....以上就是我做的自由选择的题目了,这个故事告诉我们,一定要好好看题目!!!!不过也还好,写了这么多代码,至少还是加深了对函数的理解和应用,至少个人还是比较满意的。