美文网首页
数据结构第四次作业

数据结构第四次作业

作者: XXX_f47c | 来源:发表于2019-05-14 16:39 被阅读0次

当前文档版本：v1.3

更新日志：

  • v1.3
    • 添加了第一题的提示
  • v1.2
    • 修复了参考资料的“邻接链表-BFS”代码的一些bug，具体修改了destoryGraph、 addEdge、bfs这三个函数......
  • v1.1
    • 更新第一题题目描述

第一题：二叉搜索树的操作

引用自维基百科：

二叉查找树（英语：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

  • 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  • 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
  • 任意节点的左、右子树也分别为二叉查找树；
  • 没有键值相等的节点。

对于一颗树节点定义包含父节点指针的二叉搜索树，你需要实现以下函数：

  • Node* insert(Node* &root, int key);
    • 在树中插入一个关键字为key的节点，并返回新插入的节点的位置
    • 因为该树是一颗二叉搜索树，所以你需要按照二叉搜索树的规则进行插入
    • 该操作相当于是对一个不带头结点的双向链表进行操作。对于树为空的情况需要做特殊处理，且需要修改树的根节点指针，所以这里参数需要加引用类型（C++语法，代码需保存为.cpp，否则需要使用二级指针）。
  • Node* minimum(Node* root);
    • 返回树中最小值节点的位置
  • Node* next(Node* current);
    • 返回中序遍历序列中该节点的下一个节点的位置
    • 如果该节点已经是序列的最后一个节点，则返回NULL
    • 只能借助节点的parent指针实现，不能使用stack等（即要求空间复杂度为O(1)，平均时间复杂度O(1)，最坏时间复杂度为O(树的高度)）。

题目背景：对于二叉树的非递归遍历，通常可以使用栈来完成。但如果节点包含父节点指针，可根据遍历序列的特点借助parent指针完成遍历操作（这道题不允许使用栈等方式保存路径）。这里的中序遍历操作参考了C++ map容器的迭代器实现方式，感兴趣的同学可以自行查阅。

代码框架如下（使用了引用语法，需保存为.cpp）：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node {
    int key;
    struct Node* parent;    //注意该树的节点包含父节点指针
    struct Node *lchild, *rchild;
}Node;

Node* createNode(int key) {
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->key = key;
    temp->lchild = temp->rchild = temp->parent = NULL;
    return temp;
}

//在树中插入一个节点
Node* insert(Node* &root, int key) {
    //TODO
}

//返回树中最小值节点的位置
Node* minimum(Node* root) {
    //TODO
}

//返回该树中序遍历序列起始节点的位置
Node* begin(Node* root) {
    return minimum(root);
}

//返回中序遍历序列中该节点的下一个节点的位置
//如果该节点已经是序列的最后一个节点，则返回NULL
Node* next(Node* current) {
    //TODO
}

//返回序列中最后一个节点的下一个节点的位置，也就是NULL
Node* end(Node* root) {
    return NULL;
}

int main() {
    Node* root = NULL;  //一棵空树
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        int x;
        scanf("%d", &x);
        insert(root, x);
    }

    //进行一次中序遍历
    for (Node* p = begin(root); p != end(root); p = next(p)) {
        printf("%d ", p->key);
    }
    printf("\n");
    return 0;
}

样例输入

7
3 1 2 5 4 7 9

样例输出

1 2 3 4 5 7 9

样例二叉搜索树结构

               3                                   
            /     \                                
          1          5                              
            \      /   \                          
             2    4      7                          
                          \                      
                            9

提示


对于中序遍历来说，树的遍历序列的第一个节点一定是位于最左下角，此时可从根节点开始，沿着lchind指针一直往下走，将其想象成一个单链表，找到该链表的最后一个节点。对于二叉搜索树来说，找到的节点一定是该树当中值最小的节点。
对于next函数，考虑以下几种情况：
  1. 若该节点存在右孩子，则应该进入其右子树，并找到该子树的起始节点位置。
    例如当前节点是7，则应当进入其右子树（子树的根节点为6），并找到该子树的起始节点位置（一直沿着左下角走，最终找到5）。

若该节点没有右孩子：

  1. 若该节点没有父节点，则返回NULL。
  2. 若该节点是其父节点的左孩子，应返回其父节点指针。例如当前是2节点，对于其父节点7来说，它的左子树已经遍历完，此时应访问根节点7。
  3. 若该节点其父节点的右孩子，此时应一直往父节点走，直到遇到了情况2或3。
    例如当前是节点11，此时属于情况4；向上走到节点6，此时还是属于情况4；再向上走到节点7，此时属于情况3，按照情况3处理，返回其父节点2的指针。
    当然实际代码实现的时候，2、3、4可以合并起来。

第二题：最短路径问题

使用Dijkstra算法输出该图给定起终点的一条最短路径。

题目保证所给的起终点必定连通。

若存在多条最短路径，则只需任意输出一条路径即可。

该题要求使用邻接矩阵存储图。

样例输入：

//10个顶点（编号分别为0-9），12条边，起点编号0，终点编号6
10 12 0 6
0 1 3
0 3 6
0 2 2
1 3 2
1 4 4
2 3 1
2 5 3
3 4 1
3 6 4
4 6 3
5 6 4
7 8 3

样例输出：

min distance: 7
0 -> 2 -> 3 -> 6    //或者是其它路径，结果可能不唯一

该样例对应的图如下：

非联通图

第三题：最长路径问题

输出该图的一条最长路径，路径经过的顶点均不重复（关键路径）。

由于关键路径存在的前提是该图必须是有向无环图（DAG, Directed Acyclic Graph），所以若该图出现环路，则输出A loop was detected in this graph.。

若存在多条最长路径，则只需任意输出一条路径即可。

该题要求使用邻接链表存储图。

样例输入1：

//10个顶点（编号分别为0-9），12条边
10 12
0 1 3
0 3 6
0 2 2
1 3 2
1 4 4
2 3 1
2 5 3
3 4 1
3 6 4
4 6 3
5 6 4
7 8 3

样例输出1：

max length: 10
0 -> 1 -> 4 -> 6    //或者是其它路径，结果可能不唯一

该样例对应的图如下：

非联通图

样例输入2：

4 3
0 1 1
1 2 1
2 0 1

样例输出2：

A loop was detected in this graph.

提示：

对于关键路径的求法，教材上采用的是根据每个事件的最早/最晚开始时间来做的，但这种方法实现起来较为复杂。这里更推荐采用动态规划的做法（不要被名字吓到）：

int dp[MAXN] = {0};

dp[i]表示以顶点i为起点的最长路径的长度。

dp[i] = \max{\{dp[j] + length(i \rightarrow j)}\} \qquad (i,j)∈E

可按照逆拓扑排序顺序来求解dp数组。

进阶要求

针对学有余力的同学...如果你实现了以下部分功能，麻烦在提交作业的问卷的备注那栏注明一下。

对于第一题，你可以对二叉搜索树实现更多的操作，包括search、remove等操作，甚至实现二叉搜索树在插入删除节点后的平衡操作（avl树、红黑树等等）。如果你能实现平衡操作，你的代码能力应该可以碾压95%的同学。

另外还可以将二叉搜索树改为关联性容器，即每个节点存放key-value键值对。这里需要区分关键字key、词条entry的概念。

对于第二/三题，若存在多条最短/长路径，则按照路径各节点编号的字典顺序输出所有的路径。

比如对于第一题的样例，应当输出：

min distance: 7
0 -> 2 -> 3 -> 4 -> 6
0 -> 2 -> 3 -> 6

对于第二题的样例1，应当输出：

max length: 10
0 -> 1 -> 4 -> 6
0 -> 3 -> 4 -> 6
0 -> 3 -> 6

图论参考资料

非联通图 
//10个顶点（编号分别为0-9），12条边
10 12
0 1 3
0 3 6
0 2 2
1 3 2
1 4 4
2 3 1
2 5 3
3 4 1
3 6 4
4 6 3
5 6 4
7 8 3

以下代码使用了输入重定向：

  • 在源代码所在目录新建一个纯文本文件input.txt，将输入数据存放其中。

  • 在代码main函数开头加上一行代码：freopen("input.txt", "r", stdin);

  • 这样在运行代码时就不用每次都要复制粘贴输入数据了。

邻接矩阵-DFS

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct Vertex {
    int id;
    int inDegree;
    int outDegree;
    //可以根据实际需求在此添加顶点的其余属性
}Vertex;

typedef struct Edge {
    bool isExist;
    int dist;
    //可以根据实际需求在此添加边的其余属性
}Edge;

typedef struct Graph {
    int vertexNum;
    int edgeNum;
    Edge** AdjMatrix;
    Vertex* vertexs;
    //可以根据实际需求在此添加图的其余属性
}Graph;

Graph* createGraph(int vertexNum) {
    Graph* g = (Graph*)malloc(sizeof(Graph));
    g->vertexNum = vertexNum;
    g->edgeNum = 0;

    //动态分配二维数组
    g->AdjMatrix = (Edge**)malloc(vertexNum * sizeof(Edge*));
    for (int i = 0; i < vertexNum; i++) {
        g->AdjMatrix[i] = (Edge*)malloc(vertexNum * sizeof(Edge));
    }
    //初始化邻接矩阵，令所有的边都不存在
    for (int i = 0; i < vertexNum; i++) {
        for (int j = 0; j < vertexNum; j++) {
            g->AdjMatrix[i][j].isExist = false;
        }
    }

    g->vertexs = (Vertex*)malloc(vertexNum * sizeof(Vertex));
    for (int i = 0; i < vertexNum; i++) {
        g->vertexs[i].id = i;
        g->vertexs[i].inDegree = 0;
        g->vertexs[i].outDegree = 0;
    }
    return g;
}

void destoryGraph(Graph* G) {
    //释放动态分配的二维数组的顺序与创建时的相反
    for (int i = 0; i < G->vertexNum; i++) {
        free(G->AdjMatrix[i]);
    }
    free(G->AdjMatrix);

    free(G->vertexs);
    free(G);
}

void addEdge(Graph* G, int u, int v, int dist) {
    G->AdjMatrix[u][v].isExist = true;
    G->AdjMatrix[u][v].dist = dist;
    G->vertexs[u].outDegree += 1;
    G->vertexs[v].inDegree += 1;
    G->edgeNum += 1;
}

void dfs(Graph* G, int u, bool visited[]) {
    visited[u] = true;
    printf("%d ", u);
    for (int v = 0; v < G->vertexNum; v++) {
        if (G->AdjMatrix[u][v].isExist &&
            visited[v] == false) {
            dfs(G, v, visited);
        }
    }
}

void DFS(Graph* G) {
    bool* visited = (bool*)malloc(G->vertexNum * sizeof(bool));
    memset(visited, false, G->vertexNum * sizeof(bool));
    for (int i = 0; i < G->vertexNum; i++) {
        if (visited[i] == false) {
            dfs(G, i, visited);
        }
    }
    free(visited);
    printf("\n");
}

int main() {
    freopen("input.txt", "r", stdin);   //输入重定向
    int N, M;
    scanf("%d %d", &N, &M);
    Graph* G = createGraph(N);
    for (int i = 0; i < M; i++) {
        int u, v, dist;
        scanf("%d %d %d", &u, &v, &dist);
        addEdge(G, u, v, dist);
    }

    DFS(G);

    destoryGraph(G);
    return 0;
}

输出结果：

0 1 3 4 6 2 5 7 8 9

邻接链表-BFS

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct Edge {
    int from, to;
    int dist;
    //可以根据实际需求在此添加边的其余属性
}Edge;

typedef struct Vertex {
    int id;
    int inDegree;
    int outDegree;
    //可以根据实际需求在此添加顶点的其余属性
}Vertex;

typedef struct EdgeNode {
    Edge edge;
    struct EdgeNode* next;
}EdgeNode;

typedef struct VertexNode {
    Vertex vertex;
    EdgeNode* first;    //不带头节点的链表的第一个节点指针
    EdgeNode* rear;     //链表最后一个节点的指针
}VertexNode;

typedef struct Graph {
    int vertexNum;  //顶点个数
    int edgeNum;    //边的个数
    VertexNode* AdjList;    //邻接链表
    //可以根据实际需求在此添加图的其余属性
}Graph;

Graph* createGraph(int vertexNum) {
    Graph* g = (Graph*)malloc(sizeof(Graph));
    g->vertexNum = vertexNum;
    g->edgeNum = 0;
    g->AdjList = (VertexNode*)malloc(vertexNum * sizeof(VertexNode));
    for (int i = 0; i < vertexNum; i++) {
        g->AdjList[i].first = NULL;
        g->AdjList[i].rear = NULL;
        g->AdjList[i].vertex.id = i;
        g->AdjList[i].vertex.inDegree = 0;
        g->AdjList[i].vertex.outDegree = 0;
    }
    return g;
}

void destoryGraph(Graph* G) {
    for (int i = 0; i < G->vertexNum; i++) {
        //销毁不带头节点的单链表
        EdgeNode* p = G->AdjList[i].first;
        while (p != NULL) {
            EdgeNode* next = p->next;
            free(p);
            p = next;
        }
    }
    free(G->AdjList);
    free(G);
}

void addEdge(Graph* G, int u, int v, int dist) {
    EdgeNode* temp = (EdgeNode*)malloc(sizeof(EdgeNode));
    temp->edge.from = u;
    temp->edge.to = v;
    temp->edge.dist = dist;
    temp->next = NULL;
    //这里为了避免后面代码变量的名字太长，使用了二级指针变量
    //在C++中可以使用引用语法给变量取一个别名
    EdgeNode** pFirst = &G->AdjList[u].first;
    EdgeNode** pRear = &G->AdjList[u].rear;
    if (*pFirst == NULL) {
        *pFirst = temp;
        *pRear = temp;
    }
    else {
        (*pRear)->next = temp;
        *pRear = (*pRear)->next;
    }
    G->AdjList[u].vertex.outDegree += 1;
    G->AdjList[v].vertex.inDegree += 1;
    G->edgeNum += 1;
}

void bfs(Graph* G, int root, bool visited[]) {
    int Queue[1005];
    int front = 0, rear = 0;
    Queue[rear++] = root;   //根节点入队
    visited[root] = true;
    while (rear != front) { //只要队列不为空
        int u = Queue[front++]; //出队
        printf("%d ", u);
        for (EdgeNode* p = G->AdjList[u].first; p != NULL; p = p->next) {
            int v = p->edge.to;
            if (visited[v] == false) {
                Queue[rear++] = v;
                visited[v] = true;
            }
        }
    }
}

void BFS(Graph* G) {
    bool* visited = (bool*)malloc(G->vertexNum * sizeof(bool));
    memset(visited, false, G->vertexNum * sizeof(bool));
    for (int i = 0; i < G->vertexNum; i++) {
        if (visited[i] == false) {
            bfs(G, i, visited);
        }
    }
    free(visited);
    printf("\n");
}

int main() {
    freopen("input.txt", "r", stdin);   //输入重定向
    int N, M;
    scanf("%d %d", &N, &M);
    Graph* G = createGraph(N);
    for (int i = 0; i < M; i++) {
        int u, v, dist;
        scanf("%d %d %d", &u, &v, &dist);
        addEdge(G, u, v, dist);
    }

    BFS(G);

    destoryGraph(G);
    return 0;
}

输出结果：
邻接链表的遍历顺序取决于添加边的顺序

0 1 3 2 4 5 6 7 8 9

相关文章

网友评论

      本文标题：数据结构第四次作业

      本文链接：https://www.haomeiwen.com/subject/btheaqtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|数据结构第四次作业|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！