数据结构第四次作业

当前文档版本：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
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 203,179评论 5赞 476
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,229评论 2赞 380
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,032评论 0赞 336
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,533评论 1赞 273
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,531评论 5赞 365
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,539评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,916评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,574评论 0赞 256
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,813评论 1赞 296
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,568评论 2赞 320
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,654评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,354评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,937评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,918评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,152评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,852评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,378评论 2赞 342