{"id":663,"date":"2019-06-09T09:11:43","date_gmt":"2019-06-09T01:11:43","guid":{"rendered":"http:\/\/fankasy.xyz\/?p=663"},"modified":"2019-09-25T09:14:37","modified_gmt":"2019-09-25T01:14:37","slug":"noj1047-%e5%9b%be%e7%9a%84%e6%b7%b1%e5%ba%a6%e4%bc%98%e5%85%88%e9%81%8d%e5%8e%86%e5%ba%8f%e5%88%97","status":"publish","type":"post","link":"http:\/\/fankasy.xyz\/index.php\/2019\/06\/09\/noj1047-%e5%9b%be%e7%9a%84%e6%b7%b1%e5%ba%a6%e4%bc%98%e5%85%88%e9%81%8d%e5%8e%86%e5%ba%8f%e5%88%97\/","title":{"rendered":"NOJ1047 \u56fe\u7684\u6df1\u5ea6\u4f18\u5148\u904d\u5386\u5e8f\u5217"},"content":{"rendered":"
#include<stdio.h> \/\/ printf()\r\n#include<stdlib.h> \/\/ malloc(), free()\r\n#include<limits.h> \/\/ INT_MAX for noEdgeValue\r\n\r\ntypedef int ElemType;\r\n\r\ntypedef int BOOL;\r\n#define TRUE 0\r\n#define FALSE -1\r\n\r\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\r\n\/\/ P.34\r\n\/\/ Program 3.2 Queue\r\ntypedef struct\r\n{\r\n    int front;\r\n    int rear;\r\n    int maxSize;\r\n    ElemType* element;\r\n}Queue;\r\n\r\nvoid Create(Queue* Q, int mSize)\r\n{\r\n    Q->maxSize = mSize;\r\n    Q->element = (ElemType*)malloc(sizeof(ElemType) * mSize);\r\n    Q->front = Q->rear = 0;\r\n}\r\n\r\n\/\/ Function name conflicted with Destroy() of mGraph, so I changed its name...\r\nvoid Destroy_Queue(Queue* Q)\r\n{\r\n    Q->maxSize = -1;\r\n    free(Q->element);\r\n    Q->front = Q->rear = -1;\r\n}\r\n\r\nBOOL IsEmpty(Queue* Q)\r\n{\r\n    return Q->front == Q->rear;\r\n}\r\n\r\nBOOL IsFull(Queue* Q)\r\n{\r\n    return (Q->rear + 1) % Q->maxSize == Q->front;\r\n}\r\n\r\nBOOL Front(Queue * Q, ElemType * x)\r\n{\r\n    if (IsEmpty(Q))\r\n        return FALSE;\r\n\r\n    *x = Q->element[(Q->front + 1) % Q->maxSize];\r\n\r\n    return TRUE;\r\n}\r\n\r\nBOOL EnQueue(Queue * Q, ElemType x)\r\n{\r\n    if (IsFull(Q))\r\n        return FALSE;\r\n\r\n    Q->rear = (Q->rear + 1) % Q->maxSize;\r\n    Q->element[Q->rear] = x;\r\n\r\n    return TRUE;\r\n}\r\n\r\nBOOL DeQueue(Queue * Q)\r\n{\r\n    if (IsEmpty(Q))\r\n        return FALSE;\r\n\r\n    Q->front = (Q->front + 1) % Q->maxSize;\r\n\r\n    return TRUE;\r\n}\r\n\r\nvoid Clear(Queue * Q)\r\n{\r\n    Q->front = Q->rear = 0;\r\n}\r\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\r\n\r\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\r\n\/\/ MGraph\r\n\/\/ P.139 - 141\r\n\r\n\/\/ P.139\r\ntypedef int ElemType;\r\ntypedef struct\r\n{\r\n    ElemType** a;\r\n    int n;\r\n    int e;\r\n    ElemType noEdge;\r\n}mGraph;\r\n\r\n\/\/ P.139 Program 9.1\r\n#define ERROR 0\r\n#define OK 1\r\n#define Overflow 2\r\n#define Underflow 3\r\n#define NotPresent 4\r\n#define Duplicate 5\r\ntypedef int Status;\r\n\r\nStatus Init(mGraph * mg, int nSize, ElemType noEdgeValue)\r\n{\r\n    int i, j;\r\n\r\n    mg->n = nSize;\r\n    mg->e = 0;\r\n    mg->noEdge = noEdgeValue;\r\n    mg->a = (ElemType * *)malloc(nSize * sizeof(ElemType*));\r\n    if (!mg->a)\r\n        return ERROR;\r\n\r\n    for (i = 0; i < mg->n; i++)\r\n    {\r\n        mg->a[i] = (ElemType*)malloc(nSize * sizeof(ElemType));\r\n\r\n        for (j = 0; j < mg->n; j++)\r\n            mg->a[i][j] = mg->noEdge;\r\n\r\n        mg->a[i][i] = 0;\r\n    }\r\n\r\n    return OK;\r\n}\r\n\r\n\/\/ P.140 Program 9.2\r\nvoid Destroy(mGraph * mg)\r\n{\r\n    int i;\r\n\r\n    for (i = 0; i < mg->n; i++)\r\n        free(mg->a[i]);\r\n\r\n    free(mg->a);\r\n}\r\n\r\n\/\/ P.140 Program 9.3\r\nStatus Exist(mGraph * mg, int u, int v)\r\n{\r\n    if (u<0 || v<0 || u>mg->n - 1 || v>mg->n - 1 || u == v || mg->a[u][v] == mg->noEdge)\r\n        return ERROR;\r\n\r\n    return OK;\r\n}\r\n\r\n\/\/ P.140 Program 9.4\r\nStatus Insert(mGraph * mg, int u, int v, ElemType w)\r\n{\r\n    if (u<0 || v<0 || u>mg->n - 1 || v>mg->n - 1 || u == v)\r\n        return ERROR;\r\n\r\n    if (mg->a[u][v] != mg->noEdge)\r\n        return Duplicate;\r\n\r\n    mg->a[u][v] = w;\r\n    mg->e++;\r\n\r\n    return OK;\r\n}\r\n\r\n\/\/ P.140 Program 9.5\r\nStatus Remove(mGraph * mg, int u, int v)\r\n{\r\n    if (u<0 || v<0 || u>mg->n - 1 || v>mg->n - 1 || u == v)\r\n        return ERROR;\r\n\r\n    if (mg->a[u][v] == mg->noEdge)\r\n        return NotPresent;\r\n\r\n    mg->a[u][v] = mg->noEdge;\r\n    mg->e--;\r\n\r\n    return OK;\r\n}\r\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\r\n\r\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\r\n\/\/ DFS\r\n\/\/ There are not any DFS programs based on MGraph in the textbook, \r\n\/\/ so I made it...\r\nvoid DFS(int v, int visited[], mGraph g)\r\n{\r\n    int i;\r\n\r\n    printf(\"%d \", v);\r\n    visited[v] = 1;\r\n\r\n    for (i = 0; i < g.n; i++)\r\n    {\r\n        if (g.a[v][i] != 0 && g.a[v][i] != g.noEdge && !visited[i])\r\n        {\r\n            DFS(i, visited, g);\r\n        }\r\n    }\r\n}\r\n\r\nvoid DFSGraph(mGraph g)\r\n{\r\n    int i;\r\n\r\n    \/\/ Init visited\r\n    int* visited = malloc(g.n * sizeof(int));\r\n    for (i = 0; i < g.n; i++)\r\n        visited[i] = 0;\r\n\r\n    \/\/ Do DFS\r\n    for (i = 0; i < g.n; i++)\r\n    {\r\n        if (!visited[i])\r\n        {\r\n            DFS(i, visited, g);\r\n        }\r\n    }\r\n\r\n    free(visited);\r\n}\r\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\r\n\r\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\r\n\/\/ BFS\r\n\/\/ There are not any BFS programs based on MGraph in the textbook, \r\n\/\/ so I made it...\r\nvoid BFS(int v, int visited[], mGraph g)\r\n{\r\n    int i;\r\n\r\n    Queue q;\r\n    Create(&q, g.n);\r\n\r\n    visited[v] = 1;\r\n    printf(\"%d \", v);\r\n\r\n    EnQueue(&q, v);\r\n    while (!IsEmpty(&q))\r\n    {\r\n        Front(&q, &v);\r\n        DeQueue(&q);\r\n\r\n        for (i = 0; i < g.n; i++)\r\n        {\r\n            if (g.a[v][i] != 0 && g.a[v][i] != g.noEdge && !visited[i])\r\n            {\r\n                visited[i] = 1;\r\n                printf(\"%d \", i);\r\n                EnQueue(&q, i);\r\n            }\r\n\r\n        }\r\n    }\r\n}\r\n\r\nvoid BFSGraph(mGraph g)\r\n{\r\n    int i;\r\n\r\n    \/\/ Init visited\r\n    int* visited = malloc(g.n * sizeof(int));\r\n    for (i = 0; i < g.n; i++)\r\n        visited[i] = 0;\r\n\r\n    \/\/ Do BFS\r\n    for (i = 0; i < g.n; i++)\r\n    {\r\n        if (!visited[i])\r\n        {\r\n            BFS(i, visited, g);\r\n        }\r\n    }\r\n\r\n    free(visited);\r\n}\r\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\r\n\r\n\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\r\nint main()\r\n{\r\n    mGraph GBA;\r\n    int nSize = 0, edge = 0;\r\n    int u = 0, v = 0;\r\n    scanf(\"%d %d\", &nSize, &edge);\r\n    Init(&GBA, nSize, 0);\r\n    for (int a = 0; a < edge; a++)\r\n    {\r\n        scanf(\"%d %d\", &u, &v);\r\n        Insert(&GBA, u, v, 1);\r\n        Insert(&GBA, v, u, 1);\r\n    }\r\n    for (int f = 0; f < nSize; f++)\r\n    {\r\n        for (int r = 0; r < nSize; r++)\r\n            printf(\"%d \", GBA.a[f][r]);\r\n        printf(\"\\n\");\r\n    }\r\n    DFSGraph(GBA);\r\n\r\n    Destroy(&GBA);\r\n\r\n    return 0;\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
#include<stdio.h> \/\/ printf() #include<stdlib. […]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[17],"tags":[],"_links":{"self":[{"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/posts\/663"}],"collection":[{"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/comments?post=663"}],"version-history":[{"count":0,"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/posts\/663\/revisions"}],"wp:attachment":[{"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/media?parent=663"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/categories?post=663"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/fankasy.xyz\/index.php\/wp-json\/wp\/v2\/tags?post=663"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}