{"id":234,"date":"2026-07-16T12:51:14","date_gmt":"2026-07-16T04:51:14","guid":{"rendered":"https:\/\/www.fishh.top\/?p=234"},"modified":"2026-07-16T16:35:07","modified_gmt":"2026-07-16T08:35:07","slug":"%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84","status":"publish","type":"post","link":"https:\/\/www.fishh.top\/?p=234","title":{"rendered":"\u6570\u636e\u7ed3\u6784"},"content":{"rendered":"\n

\u5916\u90e8\u6392\u5e8f\uff1a<\/h4>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n

\u603b\u65f6\u95f4=I\/O\u65f6\u95f4+\u5185\u90e8\u6392\u5e8f\u65f6\u95f4+\u5185\u90e8\u5f52\u5e76\u65f6\u95f4<\/p>\n\n\n\n

\u4f18\u5316\u601d\u8def\uff0c\u51cf\u5c11i\/o\u6b21\u6570:<\/p>\n\n\n\n

1.\u589e\u5927k\uff0c\u964d\u4f4e\u6811\u9ad8\uff0c\u5373\u51cf\u5c11\u5f52\u5e76\u6392\u5e8f\u8d9f\u6570<\/p>\n\n\n\n

2.\u51cf\u5c11r\uff0c\u51cf\u5c11\u53f6\u8282\u70b9\u4e2a\u6570\uff0c\u5373\u51cf\u5c11\u5f52\u5e76\u6bb5\u4e2a\u6570<\/p>\n\n\n\n

\"\"<\/div><\/figure>\n\n\n\n

r\u4e3a\u53f6\u8282\u70b9\u4e2a\u6570\uff08\u5f52\u5e76\u6bb5\u4e2a\u6570\uff09\uff0ch\u4e3a\u6811\u9ad8\uff08\u5f52\u5e76\u6392\u5e8f\u8d9f\u6570S\uff09\uff0ck\u4e3ak\u53c9\u6811<\/p>\n\n\n\n

\u8d25\u8005\u6811\uff1a\u591a\u8def\u5e73\u8861\u5f52\u5e76<\/p>\n\n\n\n

\"\"<\/div><\/figure>\n\n\n\n

\u8d25\u8005\u6811\uff1a\u7b2c\u4e00\u6b21\u6784\u9020\u65f6\u9700\u8981\u4e24\u4e24\u6bd4\u8f83\uff0c\u6545\u9700\u8981k-1\u6b21\u6bd4\u8f83\u3002<\/p>\n\n\n\n

\u8d25\u8005\u6811LS[x]\u8282\u70b9\u4fdd\u5b58\u7684\u662f\u8d25\u8005\u5f52\u5e76\u6bb5\u53f7\uff0c\u51a0\u519b\u8282\u70b9LS[0]\u4fdd\u5b58\u7684\u662f\u80dc\u8005\u7684\u5f52\u5e76\u6bb5\u53f7\u3002<\/p>\n\n\n\n

\u51b3\u51fa\u4e00\u8f6e\u80dc\u8005\u4ee5\u540e\uff0c\u5bf9\u5e94\u5f52\u5e76\u6bb5\u7684\u4e0b\u4e00\u4e2a\u5143\u7d20\u8865\u4f4d\uff0c\u7ee7\u7eed\u5bf9\u6bd4<\/p>\n\n\n\n

\u51a0\u519b\u8282\u70b9\u4e0d\u8ba1\u5165\u6811\u9ad8<\/p>\n\n\n\n

\u7f6e\u6362\u9009\u62e9\u6392\u5e8f\uff1a\u751f\u6210\u521d\u59cb\u5f52\u5e76\u6bb5<\/p>\n\n\n\n

\"\"<\/div><\/figure>\n\n\n\n

\u6bcf\u6b21\u9009\u62e9\u5de5\u4f5c\u533a\u5185\u7684\u6bd4minimax\u5927\u4e14\u6700\u5c0f\u7684\u6570\uff0cminimax\u8fd8\u9700\u8981\u6ee1\u8db3\u5f52\u5e76\u6bb5\u5185\u6700\u5927\uff1b<\/p>\n\n\n\n

\u6ee1\u8db3\u4e0d\u4e86\u6761\u4ef6\u5219\u5f00\u59cb\u4e0b\u4e00\u4e2a\u5f52\u5e76\u6bb5<\/p>\n\n\n\n

\"\"<\/div><\/figure>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n

\u5176\u4e2d\u9009\u62e9minimax\u7684\u8fc7\u7a0b\u7531\u8d25\u8005\u6811\u5b9e\u73b0\u3002<\/p>\n\n\n\n

\u6700\u4f73\u5f52\u5e76\u6811\uff1ak\u53c9\u54c8\u592b\u66fc<\/p>\n\n\n\n

\"\"<\/div><\/figure>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n

\u4ee3\u7801:<\/h2>\n\n\n\n

\u5e26\u5934\u7ed3\u70b9\u5355\u94fe\u8868:<\/h3>\n\n\n\n
#include <stdio.h>\n#include <stdlib.h>\n\ntypedef int Elemtype;\ntypedef struct Node\n{   \n    Elemtype data;\n    struct Node* next;\n}Node;\n\ntypedef Node Node;\n\n\n\/\/\u5934\u8282\u70b9\u521d\u59cb\u5316\nNode* initList(){\n    Node* list=(Node*)malloc(sizeof(Node));\n    list->data=0;\n    list->next=NULL;\n    return list;\n}\n\n\/\/\u5934\u63d2\u6cd5\nvoid headInsert(Node* list,int data){\n    Node* node=(Node*)malloc(sizeof(Node));\n    node->next=list->next;\n    node->data=data;\n    list->next=node;\n    list->data++;\n}\n\n\/\/\u5c3e\u63d2\u6cd5\nvoid tailInsert(Node* list,int data){\n    Node* temp=list;\n    while(temp->next){\/\/\u627e\u5230\u6700\u540e\u4e00\u4e2a\u8282\u70b9\n        temp=temp->next;\n    }\n    Node* node=(Node*)malloc(sizeof(Node));\n    node->next=NULL;\n    node->data=data;\n    temp->next=node;\n    list->data++;\n}\n\nvoid delete(Node* list,int data){\n    Node* temp=list;\n    while(temp->next){\/\/\u76f4\u5230\u6700\u540e\u4e00\u4e2a\u8282\u70b9\n        if(temp->next->data==data){\/\/\u5982\u679c\u4e0b\u4e00\u4e2a\u8282\u70b9\u7684data\u503c==\u8981\u627e\u7684data\n            Node* t=temp->next;\/\/\u8bb0\u5f55\u4e0b\u4e2a\u8282\u70b9\n            temp->next=t->next;\/\/\u628a\u4e0b\u4e2a\u8282\u70b9\u4ece\u94fe\u8868\u4e2d\u5220\u9664\n            list->data--;\/\/\u66f4\u65b0\u8282\u70b9\u6570\n            free(t);\/\/\u91ca\u653e\u5220\u9664\u6389\u7684\u8282\u70b9\n        }else{\/\/\u5982\u679c\u6ca1\u627e\u5230\u5c31\u4e0b\u4e00\u4e2a\u8282\u70b9\n            temp=temp->next;\n        }\n    }\n\n}\n\nvoid printList(Node* list){\n    Node* t=list;\n    while(t->next){\n        t=t->next;\n        printf(\"%d \",t->data);\n    }\n    printf(\"\\n\");\n}\n\n\n\/\/\u5e26\u5934\u7ed3\u70b9\u5355\u94fe\u8868\nint main(){\n    Node* list=initList();\n    delete(list,1);\n    for(int i=0;i<5;i++){\n        tailInsert(list,i);\n    }\n    for(int i=0;i<5;i++){\n        headInsert(list,i);\n    }\n    delete(list,4);\n    printList(list);\n    return 0;\n}<\/code><\/pre>\n\n\n\n
\u5faa\u73af\u961f\u5217:<\/h3>\n\n\n\n
#include <stdio.h>\n#include <stdlib.h>\n#define MAXSIZE 6\n\ntypedef struct Queue{\n    int* data;\n    int front;\n    int rear;   \n}Queue;\n\n\/\/\u8be5\u5faa\u73af\u961f\u5217\u6700\u591a\u80fd\u653eMAXSIZE-1\u4e2a\u5143\u7d20\nQueue* initQueue(int n){\n    Queue* Q=(Queue*)malloc(sizeof(Queue));\n    Q->data=(int*)malloc(sizeof(int)*n);\n    Q->front=0;\n    Q->rear=0;\n    return Q;\n}\n\n\/\/\u82e5\u5934\u6307\u9488==\u5c3e\u6307\u9488,\u5219\u8868\u793a\u961f\u7a7a\nint isEmpty(Queue* Q){\n    if(Q->front==Q->rear) return 1;\n    return 0;\n}\n\n\/\/\u82e5(\u5c3e\u6307\u9488+1)%MAXSIZE==\u5934\u6307\u9488,\u5219\u8868\u793a\u961f\u6ee1\nint isFull(Queue* Q){\n    if((Q->rear+1)%MAXSIZE==Q->front) return 1;\n    return 0;\n}\n\nint enQueue(Queue* Q,int data){\n    if(isFull(Q)) return 0;\n    Q->data[Q->rear++]=data;\n    Q->rear=(Q->rear+MAXSIZE)%MAXSIZE; \/\/\u9632\u6b62\u8d8a\u754c\n    return 1;\n}\n\nint deQueue(Queue* Q){\n    if(isEmpty(Q)) return 0;\n    Q->front++;\n    Q->front=(Q->front+MAXSIZE)%MAXSIZE; \/\/\u9632\u6b62\u8d8a\u754c\n    return 1;\n}\n\n\/\/\u6253\u5370\u961f\u5217\nint printQueue(Queue* Q){\n    \/\/\u8ba1\u7b97\u5143\u7d20\u4e2a\u6570\n    int size=(Q->rear-Q->front+MAXSIZE)%MAXSIZE;\n    int index=Q->front;\n    for(int i=0;i<size;i++){\n        printf(\"%d \",Q->data[index]);\n        index=(index+1)%MAXSIZE;\n    }\n    printf(\"\\n\");\n}\n\nint main(){\n    Queue* Q = initQueue(MAXSIZE);\n    enQueue(Q, 1);\n    enQueue(Q, 2);\n    enQueue(Q, 3);\n    enQueue(Q, 4);\n    printQueue(Q);\n    deQueue(Q);\n    deQueue(Q);\n    deQueue(Q);\n    deQueue(Q);\n    enQueue(Q, 5);\n    enQueue(Q, 4);\n    enQueue(Q, 3);\n    enQueue(Q, 2);\n    enQueue(Q, 1);\n    printQueue(Q);\n    return 0;\n}<\/code><\/pre>\n\n\n\n
KMP\u6559\u79d1\u4e66\u7248<\/h3>\n\n\n\n
\u624b\u7b97\u65f6(\u4e0b\u6807\u4ece0\u5f00\u59cb),next[i]\u7b49\u4e8e\u524di\u4e2a\u5b57\u7b26(0,1,..,i-1)\u7684\u6700\u957f\u516c\u5171\u524d\u540e\u7f00\u957f\u5ea6<\/p>\n\n\n\n
#include<stdio.h>\n#include<stdlib.h>\n\ntypedef struct String{\n    char* data;\n    int len;\n}String;\n\n\nString* initString(){\n    String* s=(String*)malloc(sizeof(String));\n    s->data=NULL;\n    s->len=0;\n    return s;\n}\n\nvoid stringAssign(String* s,char* data){\n    if(s->data){\n        free(s->data);\n    }\n    int len=0;\n    char* temp=data;\n    while(*temp){\n        len++;\n        temp++;\n    }\n    if(len==0){\n        s->data=NULL;\n        s->len=0;\n        \n    }else{\n        temp=data;\n        s->len=len;\n        s->data=(char*)malloc(sizeof(char)*(len+1));\n        int i;\n        for(i=0;i<len;i++,temp++){\n            s->data[i]=*temp;\n        }\n        s->data[i]='\\0';\n    }\n\n}\n\nvoid printString(String* s){\n    for(int i=0;i<s->len;i++){\n        printf(i==0?\"%c\":\"->%c\",s->data[i]);\n    }\n    printf(\"\\n\");\n}\n\n\/\/next[j]\u8868\u793a\u56de\u9000\u5230\u6307\u5b9a\u4e0b\u6807\nint* getNext(String* s){\n    int* next=(int*)malloc(sizeof(int)*s->len);\n    int i=0;\/\/\u7d22\u5f15\n    int j=-1;\/\/\u503c\n    next[i]=j; \/\/next[0]=-1;\n    while(i<s->len-1){\n        if(j==-1||s->data[i]==s->data[j]){\n            i++;\n            j++;\n            next[i]=j;\n        }else{\n            j=next[j]; \n        }\n    }\n    return next;\n}\n\/\/ABACCABABD\n\nvoid printNext(int* next,int len){\n    for(int i=0;i<len;i++){\n        printf(i==0?\"%d\":\"->%d\",next[i]);\n    }\n    printf(\"\\n\");\n}\n\nvoid kmpMatch(String* master,String* sub,int* next){\n    int i=0;\n    int j=0;\n    while(i<master->len && j<sub->len){\n        if(j==-1||master->data[i]==sub->data[j]){\n            i++;\n            j++;\n        }else{\n            j=next[j];\n        }\n    }\n    if(j==sub->len){\n        printf(\"kmp match success!\\n\");\n    }else{\n        printf(\"kmp match fail!\\n\");\n    }\n}\n\nint main(int argc,char* argv[]){\n    String* s=initString();\n    String* s1=initString();\n    stringAssign(s,\"ABACCABABD\");\n    printString(s);\n    stringAssign(s1,\"ABAB\");\n    int* next=getNext(s1);\n    printNext(next,s1->len);\n    kmpMatch(s,s1,next);\n\n    return 0;\n}\n\n\/\/\u5085\u54e5\u4f18\u5316\u7248\n#include<stdio.h>\n#include<stdlib.h>\n\ntypedef struct String{\n    char* data;\n    int len;\n}String;\n\n\nString* initString(){\n    String* s=(String*)malloc(sizeof(String));\n    s->data=NULL;\n    s->len=0;\n    return s;\n}\n\nvoid stringAssign(String* s,char* data){\n    if(s->data){\n        free(s->data);\n    }\n    int len=0;\n    char* temp=data;\n    while(*temp){\n        len++;\n        temp++;\n    }\n    if(len==0){\n        s->data=NULL;\n        s->len=0;\n        \n    }else{\n        temp=data;\n        s->len=len;\n        s->data=(char*)malloc(sizeof(char)*(len+1));\n        int i;\n        for(i=0;i<len;i++,temp++){\n            s->data[i]=*temp;\n        }\n        s->data[i]='\\0';\n    }\n\n}\n\nvoid printString(String* s){\n    for(int i=0;i<s->len;i++){\n        printf(i==0?\"%c\":\"->%c\",s->data[i]);\n    }\n    printf(\"\\n\");\n}\n\n\/\/next[i]\u8bb0\u5f55\u4e86i\u4e0b\u6807\u4e4b\u524d\u7684i\u4e2a\u5b57\u7b26\u7684\u516c\u5171\u524d\u540e\u7f00\u957f\u5ea6,\u4e5f\u53ef\u4ee5\u7406\u89e3\u4e3a\u56de\u9000\u65f6\u4f1a\u8df3\u8f6c\u7684\u4f4d\u7f6e\nint* getNext(String* s){\n    int* next=(int*)malloc(sizeof(int)*s->len);\n    int i=0;\/\/\u7d22\u5f15\n    int j=-1;\n    next[i]=j; \/\/next[0]=-1;\n    while(i<s->len-1){\n        \/\/\u5bf9\u6bd4\u4e0b\u6807\u4e3ai\u548cj\u7684\u5b57\u7b26\u82e5\u76f8\u540c\u5219\u4ee4next[i+1]=j+1,\u4e0d\u76f8\u540c\u5219\u56de\u9000j\u81f3\u4e0a\u4e00\u4e2a\u516c\u5171\u524d\u540e\u7f00\u957f\u5ea6\n        while(j!=-1&&s->data[i]!=s->data[j]) j=next[j];\n        printf(\"i:%d j:%d \",i,j);\n        i++;\n        j++;\n        next[i]=j;\n        printf(\"next[%d]:%d\\n\",i,next[i]);\n    }\n    return next;\n}\n\/\/ABACCABABD\n\nvoid printNext(int* next,int len){\n    for(int i=0;i<len;i++){\n        printf(i==0?\"%d\":\"->%d\",next[i]);\n    }\n    printf(\"\\n\");\n}\n\nvoid kmpMatch(String* master,String* sub,int* next){\n    int i=0;\n    int j=0;\n    while(i<master->len && j<sub->len){\n        while(j!=-1&&master->data[i]!=sub->data[j]) j=next[j];\n        i++;\n        j++;\n    }\n    if(j==sub->len){\n        printf(\"kmp match success!\\n\");\n    }else{\n        printf(\"kmp match fail!\\n\");\n    }\n}\n\nint main(int argc,char* argv[]){\n    String* s=initString();\n    String* s1=initString();\n    stringAssign(s,\"ABABCABABD\");\n    printString(s);\n    stringAssign(s1,\"ABABB\");\n    printString(s1);\n    int* next=getNext(s1);\n    printNext(next,s1->len);\n    kmpMatch(s,s1,next);\n\n    return 0;\n}\n\n\/**\n * \u4e3b\u4e32:ABABCABABD\n * \u5b50\u4e32:ABABD  i=4\u65f6,\u6700\u957f\u524d\u7f00\u4e3a:AB; \u6700\u957f\u540e\u7f00\u4e3aAB,\u516c\u5171\u524d\u540e\u7f00\u957f\u5ea6\u4e3a2,next[i]=3;\n * \n * next\u6570\u7ec4\u4f1a\u8bb0\u5f55i\u4e4b\u524d\u7684\u6700\u957f\u516c\u5171\u524d\u540e\u7f00\u957f\u5ea6\n * \u5339\u914d\u65f6,\u4e3b\u4e32\u7684C\u5b57\u7b26\u4e0e\u5b57\u4e32\u7684D\u5b57\u7b26\u5bf9\u5e94\u4e0d\u4e0a,\u56e0\u4e3a\u5b57\u4e32D\u5904\u4e4b\u524d\u6709\u516c\u5171\u524d\u540e\u7f00\n * \u53c8\u56e0\u4e3a\u5728C\/D\u4e4b\u524d\u4e3b\u4e32\u548c\u5b50\u4e32\u662f\u5339\u914d\u7684\n * \u90a3\u4e48\u80af\u5b9a\u80fd\u63a8\u65ad\u51faC\/D\u4e4b\u524d\u4e3b\u4e32\u7684\u540e\u9762\u4e00\u90e8\u5206\u4f1a\u7b49\u4e8e\u5b50\u4e32\u7684\u524d\u9762\u4e00\u90e8\u5206\n * \u90a3\u4e48\u5c31\u53ef\u4ee5\u5229\u7528next\u6570\u7ec4\u8fdb\u884c\u56de\u9000\n * next[j]\u7684\u503c\u8868\u793a\u5931\u914d\u65f6\u4f1a\u8df3\u8f6c\u5230\u7684\u4f4d\u7f6e\n * \u8bbe\u516c\u5171\u524d\u540e\u7f00\u957f\u5ea6\u4e3ax,\u90a3\u4e48\u8df3\u8f6c\u5230\u7684\u4f4d\u7f6e\u6b63\u597d\u5904\u4e8e\u6570\u7ec4\u7684\u7b2cx+1\u4e2a\n * \u7531\u4e8e\u6570\u7ec4\u4ece0\u5f00\u59cb,\u90a3\u4e48\u8df3\u8f6c\u4f4d\u7f6e\u7684\u4e0b\u6807\u6b63\u597d\u5c31\u662fx\n * \u56de\u9000\u540e\u7ee7\u7eed\u5339\u914d,\u5982\u679c\u8fd8\u4e0d\u884c,\u5c31\u7ee7\u7eed\u56de\u9000.\n * \n *\/\n<\/code><\/pre>\n\n\n\n
\u6811\u7684\u5e94\u7528:<\/h3>\n\n\n\n
\u4e8c\u53c9\u6392\u5e8f\u6811:<\/h4>\n\n\n\n
#include <stdio.h>\n#include <stdlib.h>\n\ntypedef struct TreeNode{\n\tint data;\n\tstruct TreeNode* lchild;\n\tstruct TreeNode* rchild;\n}TreeNode;\n\nTreeNode* bstSearch(TreeNode* T,int key){\n\tif(T==NULL){\n\t\treturn NULL;\n\t}\n\t\n\tif(T->data==key){\n\t\treturn T;\n\t}else if(T->data>key){\n\t\treturn bstSearch(T->lchild,key);\n\t}else if(T->data<key){\n\t\treturn bstSearch(T->rchild,key);\n\t}\n}\n\n\/\/TreeNode **T:\u521b\u5efa\u8282\u70b9\u7684\u6307\u9488\u7684\u6307\u9488,\u6307\u5411\u8282\u70b9\u7684\u6307\u9488\n\/\/TreeNode *T:\u521b\u5efa\u8282\u70b9\u7684\u6307\u9488,\u6307\u5411\u8282\u70b9\nvoid bstInsert(TreeNode** T,int data){\n\tif(*T==NULL){\n\t\t*T=(TreeNode*)malloc(sizeof(TreeNode));\n\t\t(*T)->data=data;\n\t\t(*T)->lchild=NULL;\n\t\t(*T)->rchild=NULL;\n\t}else if((*T)->data==data){\n\t\treturn;\n\t}else if((*T)->data>data){\n\t\tbstInsert(&(*T)->lchild,data);\n\t}else if((*T)->data<data){\n\t\tbstInsert(&(*T)->rchild,data);\n\t}\n}\n\nvoid inOrder(TreeNode *T){\n    if(T==NULL){\n        return;\n    }\n    inOrder(T->lchild);\n    printf(\"%d \",T->data);\n    inOrder(T->rchild);\n}\n\nint main(){\n\tTreeNode* g_T=NULL;\/\/\u8282\u70b9\u6307\u9488,g_T\u662f\u6839\u8282\u70b9\u7684\u6307\u9488,\u6307\u5411\u6839\u8282\u70b9;*g_T\u662f\u6839\u8282\u70b9\n\tint nums[6]={4,6,7,5,2,1};\n    for(int i=0;i<6;i++){\n        bstInsert(&g_T,nums[i]);\n    }\n    inOrder(g_T);\n    \n\tTreeNode* t=bstSearch(g_T,11);\n\tif(t!=NULL){\n\t\tprintf(\"\\n%d\",t->data);\n\t}else{\n\t\tprintf(\"\\n\u4e0d\u5b58\u5728\");\n\t}\n\n    return 0;\n}<\/code><\/pre>\n\n\n\n
\u5e73\u8861\u4e8c\u53c9\u6811:<\/h4>\n\n\n\n
#include <stdio.h>\n#include <stdlib.h>\n\ntypedef struct TreeNode{\n    int data;\n    int height;\n    struct TreeNode* lchild;\n    struct TreeNode* rchild;\n}TreeNode;\n\n\/\/\u521d\u59cb\u5316\u4e00\u4e2a\u8282\u70b9\nTreeNode* initNode(int data){\n    TreeNode* node=(TreeNode*)malloc(sizeof(TreeNode));\n    node->data=data;\n    node->height=0;\n    node->lchild=NULL;\n    node->rchild=NULL;\n    return node;\n}\n\nint getTreeHeight(TreeNode* T){\n    if(T) return T->height;\n    else return 0;\n}\n\nint getMax(int a,int b){\n    return a>b?a:b;\n}\n\n\/\/\u95ee\u9898\u8282\u70b9\u5de6\u65cb\nvoid llRolation(TreeNode** T){\n    TreeNode* node=(*T)->lchild;\n    (*T)->lchild=node->rchild;\n    node->rchild=*T;\n    (*T)->height=getMax(getTreeHeight((*T)->lchild),getTreeHeight((*T)->rchild))+1;\n    *T=node;\n    (*T)->height=getMax(getTreeHeight((*T)->lchild),getTreeHeight((*T)->rchild))+1;\n}\n\n\/\/\u95ee\u9898\u8282\u70b9\u53f3\u65cb\nvoid rrRolation(TreeNode** T){\n    TreeNode* node=(*T)->rchild;\n    (*T)->rchild=node->lchild;\n    node->lchild=*T;\n    (*T)->height=getMax(getTreeHeight((*T)->lchild),getTreeHeight((*T)->rchild))+1;\n    *T=node;\n    (*T)->height=getMax(getTreeHeight((*T)->lchild),getTreeHeight((*T)->rchild))+1;\n}\n\n\n\n\/\/\u5e73\u8861\u4e8c\u53c9\u6811\u63d2\u5165\nvoid avlInsert(TreeNode** T,int data){\n    if((*T)==NULL){\n        *T=initNode(data);\n    }else if(data==(*T)->data){\n        return;\n    }else if(data<(*T)->data){\n        avlInsert(&(*T)->lchild,data);\n        int l_height=getTreeHeight((*T)->lchild);\n        int r_height=getTreeHeight((*T)->rchild);\n        \/\/\u5224\u65ad\u5931\u8861,\u5f80\u5de6\u8fb9\u63d2\u5165,\u770b\u5de6\u8fb9\u5b50\u6811\u6709\u6ca1\u6709\u6bd4\u53f3\u8fb9\u5b50\u6811\u9ad82\n        if(l_height-r_height>1){\n            \/\/\u5224\u65ad\u662fll\u578b\u8fd8\u662flr\u578b,\u5982\u679cdata\u6bd4*T\u5de6\u5b50\u6811\u7684data\u503c\u8981\u5c0f,\u5219\u63d2\u5728\u4e86*T\u5de6\u5b50\u6811\u7684\u5de6\u8fb9\n            if(data<(*T)->lchild->data){\n                \/\/ll\u578b\n                llRolation(T);\n            }else{\n                \/\/lr\u578b,\u5148\u8ba9*T\u7684\u5de6\u5b50\u6811\u53f3\u65cb,\u7136\u540e*T\u518d\u5de6\u65cb\n                rrRolation(&(*T)->lchild);\n                llRolation(T);\n            }\n        }\n    }else if(data>(*T)->data){\n        avlInsert(&(*T)->rchild,data);\n        int l_height=getTreeHeight((*T)->lchild);\n        int r_height=getTreeHeight((*T)->rchild);\n        \/\/\u5224\u65ad\u5931\u8861\n        if(r_height-l_height>1){\n            if(data>(*T)->rchild->data){\n                \/\/rr\u578b\n                rrRolation(T);\n            }else{\n                \/\/rl\u578b\n                llRolation(&(*T)->rchild);\n                rrRolation(T);\n            }\n        }\n\n    }\n    \/\/\u7ef4\u62a4\u5f53\u524d\u8282\u70b9\u6811\u7684\u9ad8\u5ea6\n    (*T)->height=getMax(getTreeHeight((*T)->lchild),getTreeHeight((*T)->rchild))+1;\n}\n\nvoid preOrder(TreeNode *T){\n    if(T==NULL){\n        return;\n    }\n    printf(\"%d \",T->data);\n    preOrder(T->lchild);\n    preOrder(T->rchild);\n}\n\nint main(){\n    TreeNode* T=NULL;\n    int nums[5]={1,8,6,7,10};\n    for(int i=0;i<5;i++){\n        avlInsert(&T,nums[i]);\n    }\n    preOrder(T);\n\n    printf(\"\\n%d\",getTreeHeight(T));\n    return 0;\n}<\/code><\/pre>\n\n\n\n
\u54c8\u592b\u66fc\u6811:<\/h4>\n\n\n\n
#include <stdio.h>\n#include <stdlib.h>\n\ntypedef struct TreeNode{\n    int parent;\n    int lchild;\n    int rchild;\n    int weight;\n}TreeNode;\n\ntypedef struct HaffmanTree{\n    TreeNode* data;\n    int length;\n}HaffmanTree;\n\n\n\/\/\u521d\u59cb\u5316\nHaffmanTree* initTree(int len,int* nums){\n    HaffmanTree* T=(HaffmanTree*)malloc(sizeof(HaffmanTree));\n    T->data=(TreeNode*)malloc(sizeof(TreeNode)*(len*2-1));\n    T->length=len;\n    for(int i=0;i<len;i++){ \/\/\u521d\u59cb\u5316\u539f\u59cb\u53f6\u5b50\u8282\u70b9\n        T->data[i].lchild=-1;\n        T->data[i].rchild=-1;\n        T->data[i].parent=-1;\n        T->data[i].weight=nums[i];\n    }\n    return T;\n}\n\n\/\/\u4ece\u6ca1\u6709\u7236\u4eb2\u7684\u8282\u70b9\u627e,\u627e\u51fa\u6700\u5c0f\u7684\u4e24\u4e2a\u6570\nint* findMinNum(HaffmanTree* T){\n    int* res=(int*)malloc(sizeof(int)*2);\n    int min=0x3ffff;\n    int second_min=0x3ffff;\n    int minIndex;\n    int second_minIndex;\n    \/\/\u627e\u51fa\u6700\u5c0f\u6570\u7684\u4e0b\u6807   \n    for(int i=0;i<T->length;i++){\n        \/\/\u4ece\u6ca1\u6709\u7236\u4eb2\u7684\u8282\u70b9\u627e\n        if(T->data[i].parent==-1){\n            if(min>T->data[i].weight){\n                min=T->data[i].weight;\n                minIndex=i;\n            }\n        }\n    }\n\n    \/\/\u627e\u51fa\u7b2c\u4e8c\u5c0f\u6570\u7684\u4e0b\u6807\n    for(int i=0;i<T->length;i++){\n        \/\/\u4ece\u6ca1\u6709\u7236\u4eb2\u7684\u8282\u70b9\u627e\n        if(T->data[i].parent==-1&&i!=minIndex){\n            if(second_min>T->data[i].weight){\n                second_min=T->data[i].weight;\n                second_minIndex=i;\n            }\n        }\n    }\n    res[0]=minIndex;\n    res[1]=second_minIndex;\n    return res;\n} \n\n\/**\n * haffman\u6811\u4e00\u5171\u4f1a\u67092n-1\u4e2a\u8282\u70b9,\u4e5f\u5c31\u662f\u8bf4\u9700\u8981\u8fdb\u884cn-1\u8f6e\u5faa\u73af,\u6bcf\u6b21\u5faa\u73af\u627e\u51fa\u6700\u5c0f\u7684\u4e24\u4e2a\u6570\u7ec4\u6210\u65b0\u7684\u8282\u70b9,\u4f1a\u751f\u6210n-1\u4e2a\u65b0\u8282\u70b9\n *\/\n\/\/\u6784\u9020haffman\u6811\nvoid haffmanTreeGenerate(HaffmanTree** T,int len,int* nums){\n    *T=initTree(len,nums);\n    int *res;\n    \/\/n-1\u8f6e\u5faa\u73af\n    for(int i=len;i<2*len-1;i++){\n        \/\/\u627e\u51fa\u6700\u5c0f\u4e24\u4e2a\u6570\u7684\u4e0b\u6807\n        res=findMinNum(*T);\n        int minIndex=res[0];\n        int second_minIndex=res[1];\n        \/\/\u7ec4\u6210\u65b0\u8282\u70b9\n        (*T)->data[i].weight=(*T)->data[minIndex].weight+(*T)->data[second_minIndex].weight;\n        (*T)->data[i].lchild=minIndex;\n        (*T)->data[i].rchild=second_minIndex;\n        (*T)->data[i].parent=-1;\/\/parent==-1,\u4ee4\u5176\u52a0\u5165\u4e0b\u8f6e\u627e\u6700\u5c0f\u503c\u7684\u961f\u4f0d\u4e2d\n        (*T)->length++;\/\/\u52a0\u5165\u65b0\u8282\u70b9,\u957f\u5ea6\u52a0\u4e00\n        \/\/\u66f4\u65b0\u5176parent\n        (*T)->data[minIndex].parent=i;\n        (*T)->data[second_minIndex].parent=i;\n    }\n}\n\nvoid preOrder(HaffmanTree* T,int index){\n\tif(index!=-1){\n\t\tprintf(\"%d \",T->data[index].weight);\n\t\tpreOrder(T,T->data[index].lchild);\n\t\tpreOrder(T,T->data[index].rchild);\n\t}\n}\n\nint main(){\n    HaffmanTree* T=NULL;\n    #define LEN 5\n    int nums[LEN]={1,2,3,4,5};\n    haffmanTreeGenerate(&T,LEN,nums);\n    preOrder(T,T->length-1);\n\tprintf(\"\\n\");\n\tfor(int i=0;i<LEN*2-1;i++){\n\t\tprintf(\"\u4e0b\u6807:%d \u6743\u91cd:%d \u7236\u4eb2:%d \u5de6\u5b69\u5b50:%d \u53f3\u5b69\u5b50:%d\\n\",i,T->data[i].weight,T->data[i].parent,T->data[i].lchild,T->data[i].rchild);\n\t}\n    return 0;\n}<\/code><\/pre>\n\n\n\n
\u56fe\u7684\u6784\u5efa(\u90bb\u63a5\u77e9\u9635):<\/h3>\n\n\n\n
#include <stdio.h>\n#include <stdlib.h>\n#define N 6\n#define MAXSIZE 10\n\ntypedef struct Graph{\n\tchar* vertexs;\n\tint** arcs;\n\tint vertexNum;\n\tint arcNum;\n}Graph;\n\ntypedef struct Queue{\n    int* data;\n    int front;\n    int rear;   \n}Queue;\n\n\nQueue* initQueue(int n){\n    Queue* Q=(Queue*)malloc(sizeof(Queue));\n    Q->data=(int*)malloc(sizeof(int)*n);\n    Q->front=0;\n    Q->rear=0;\n    return Q;\n}\n\nint isEmpty(Queue* Q){\n    if(Q->front==Q->rear) return 1;\n    return 0;\n}\n\nint isFull(Queue* Q){\n    if((Q->rear+1)%MAXSIZE==Q->front) return 1;\n    return 0;\n}\n\nint enQueue(Queue* Q,int data){\n    if(isFull(Q)) return 0;\n    Q->data[Q->rear++]=data;\n    Q->rear=(Q->rear+MAXSIZE)%MAXSIZE; \/\/\u9632\u6b62\u8d8a\u754c\n    return 1;\n}\n\nint deQueue(Queue* Q){\n    if(isEmpty(Q)) return -1;\n    int x=Q->front;\n    Q->front++;\n    Q->front=(Q->front+MAXSIZE)%MAXSIZE; \/\/\u9632\u6b62\u8d8a\u754c\n    return x;\n}\n\n\/\/\u521d\u59cb\u5316\nGraph* initGraph(int vertexNum){\n\tGraph* G=(Graph*)malloc(sizeof(Graph));\n\tG->arcNum=0;\n\tG->vertexNum=vertexNum;\n\tG->vertexs=(char*)malloc(sizeof(char)*vertexNum);\n\tG->arcs=(int**)malloc(sizeof(int*)*vertexNum);\n\tfor(int i=0;i<vertexNum;i++){\n\t\tG->arcs[i]=(int*)malloc(sizeof(int)*vertexNum);\n\t}\n\treturn G;\n}\n\nvoid createGraph(Graph* G,char* vertexs,int *arcs){\n    for(int i=0;i<G->vertexNum;i++){\n        G->vertexs[i]=vertexs[i];\n        for(int j=0;j<G->vertexNum;j++){\n            G->arcs[i][j]=*(arcs+i*G->vertexNum+j);\n            if(G->arcs[i][j]==1){\n                G->arcNum++;\n            }\n        }\n    }\n    G->arcNum\/=2;\n}\n\nvoid dfs(Graph* G,int* visited,int index){\n    visited[index]=1;\n    printf(\"%c \",G->vertexs[index]);\n    for(int i=0;i<G->vertexNum;i++){\n        if(G->arcs[index][i]==1&&visited[i]==0){\n            dfs(G,visited,i);\n        }\n    }\n}\n\nvoid bfs(Graph* G,int *visited,int index){\n    Queue* Q=initQueue(MAXSIZE);\n    enQueue(Q,index);\/\/\u7b2c\u4e00\u4e2a\u9876\u70b9\u5165\u961f\n    visited[index]=1;\/\/\u8bb0\u5f55\u4e3a\u904d\u5386\u8fc7\u7684\n    while(!isEmpty(Q)){\n        index=deQueue(Q);\/\/\u51fa\u961f\u4e00\u4e2a\u9876\u70b9\n        printf(\"%c \",G->vertexs[index]);\n        for(int i=0;i<G->vertexNum;i++){\n            if(G->arcs[index][i]==1&&visited[i]==0){\n                enQueue(Q,i);\/\/\u6ca1\u904d\u5386\u8fc7\u7684\u9876\u70b9\u5165\u961f\n                visited[i]=1;\/\/\u8bb0\u5f55\u4e3a\u904d\u5386\u8fc7\u7684\u9876\u70b9\n            }\n        }\n    }\n\n}\n\nint main(){\n    Graph* G=initGraph(N);\n    int arcs[N][N] = {\n\t    {0,1,1,0,0,0}, \/\/ A\n\t    {1,0,0,1,0,0}, \/\/ B\n\t    {1,0,0,0,1,0}, \/\/ C\n\t    {0,1,0,0,1,1}, \/\/ D\n\t    {0,0,1,1,0,1}, \/\/ E\n\t    {0,0,0,1,1,0}  \/\/ F\n\t};\n    createGraph(G,\"ABCDEF\",(int*)arcs);\n    int visited[N];\n    for(int i=0;i<N;i++) visited[i]=0;\n    dfs(G,visited,0);\n    printf(\"\\n\");\n    for(int i=0;i<N;i++) visited[i]=0;\n    bfs(G,visited,0);\n\treturn 0;\n}\n\n<\/code><\/pre>\n\n\n\n
\u6700\u5c0f\u751f\u6210\u6811<\/h3>\n\n\n\n
prim\u7b97\u6cd5<\/h4>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
#include <stdio.h>\n#include <stdlib.h>\n\n#define N 6\n#define MAX 32767\n\n\/\/MAX\u8868\u793a\u65e0\u6cd5\u5230\u8fbe\u7684\u8ddd\u79bb\uff0c0\u8868\u793a\u81ea\u8eab\ntypedef struct Graph{\n    int vertexNum;\n    char* vertexs;\n    int arcNum;\n    int** arcs;\n}Graph;\n\n\ntypedef struct Edge{\n    char vertex; \/\/U\u96c6\u5408\u5185\u90e8\u8ddd\u79bbi\u6700\u8fd1\u7684\u70b9\n    int weight;\/\/\u9876\u70b9i\u52a0\u5165U\u96c6\u5408\u7684\u5f00\u9500,\u5f00\u9500\u4e3a0\u5219i\u8868\u793a\u5df2\u7ecf\u5728U\u96c6\u5408\u5185\u90e8\n}Edge;\n\nEdge* initEdge(Graph* G,int index){\n    Edge* edge=(Edge*)malloc(sizeof(Edge)*G->vertexNum);\n    for(int i=0;i<G->vertexNum;i++){\n        edge[i].vertex=G->vertexs[index];\n        edge[i].weight=G->arcs[index][i];\n    }\n    return edge;\n}\n\/* edge.vertex\n1 1 1 1 1 1 \n1 3 1 1 3 3 \n1 3 1 6 3 3 \n1 3 1 6 3 3 \n1 3 1 6 2 3 \n*\/\n\/* edge.weight\n0 6 1 5 32767 32767 \n0 5 0 5 6 4 \n0 5 0 2 6 0 \n0 5 0 0 6 0 \n0 0 0 0 3 0 \n*\/\n\n\/\/\u601d\u60f3:\u57fa\u4e8e\u70b9\u627e\u8fb9\n\/**\n * \u7ef4\u62a4\u4e00\u4e2aU\u96c6\u5408,\u8868\u793a\u5c40\u90e8\u6700\u4f18\u89e3,\n * \u7528edge\u6570\u7ec4\u5b9e\u65f6\u8bb0\u5f55\u5176\u4ed6\u8282\u70b9\u60f3\u8981\u52a0\u5165U\u96c6\u5408\u9700\u8981\u7684\u5f00\u9500\u548c\u8ddd\u79bbU\u96c6\u5408\u6700\u8fd1\u7684\u5185\u90e8\u8282\u70b9,\n * \u5148\u628a\u8d77\u59cb\u70b9\u653e\u5165U\u96c6\u5408,\u7136\u540e\u4ece\u8d77\u59cb\u70b9\u51fa\u53d1,\u6bcf\u6b21\u627e\u4e00\u4e2a\u52a0\u5165U\u96c6\u5408\u5f00\u9500\u6700\u5c0f\u7684\u8282\u70b9,\n * \u65b0\u7684\u8282\u70b9\u52a0\u5165U\u96c6\u5408\u4ee5\u540e,\u904d\u5386\u65b0\u52a0\u5165\u8282\u70b9\u5230\u5176\u4ed6\u672a\u52a0\u5165U\u96c6\u5408\u7684\u8282\u70b9\u7684\u5f00\u9500,\n * \u5982\u679c\u901a\u8fc7\u65b0\u52a0\u5165\u8282\u70b9\u53bb\u52a0\u5165U\u96c6\u5408\u5f00\u9500\u6bd4\u539f\u5148\u76f4\u63a5\u52a0\u5165U\u96c6\u5408\u5f00\u9500\u66f4\u5c0f,\n * \u5219\u6307\u5b9a\u8fd9\u4e2a\u65b0\u52a0\u5165\u8282\u70b9\u4e3a\u5b83\u8ddd\u79bbU\u96c6\u5408\u6700\u8fd1\u7684\u5185\u90e8\u8282\u70b9,\u5e76\u66f4\u65b0\u52a0\u5165\u9700\u8981\u7684\u5f00\u9500.\n *\/\nvoid prim(Graph* G,int index){\n    Edge* edge=initEdge(G,index);    \/\/edge[i] \u5bf9\u5e94 G->vertexs[i]\n    for(int i=0;i<G->vertexNum-1;i++){\n        int min=MAX;\n        int minIndex;\n        for(int j=0;j<G->vertexNum;j++){\n            \/\/\u627e\u5230j\u52a0\u5165U\u96c6\u5408\u5f00\u9500\u6700\u5c0f\u7684\u8fb9\u548c\u5bf9\u5e94\u7684\u70b9\n            if(min>edge[j].weight&&edge[j].weight!=0){\n                min=edge[j].weight;\n                minIndex=j;\n            }\n        }\n        printf(\"v%c->v%c weight:%d\\n\",edge[minIndex].vertex,G->vertexs[minIndex],min);\n        edge[minIndex].weight=0;\n        for(int j=0;j<G->vertexNum;j++){\n            \/\/\u7ef4\u62a4j\u52a0\u5165U\u96c6\u5408\u9700\u8981\u6700\u5c0f\u7684\u5f00\u9500\u548cU\u96c6\u5408\u5185\u90e8\u8ddd\u79bbj\u6700\u8fd1\u7684\u70b9\n            if(edge[j].weight>G->arcs[minIndex][j]&&edge[j].weight!=0){\n                edge[j].vertex=G->vertexs[minIndex];\n                edge[j].weight=G->arcs[minIndex][j];\n            }\n        }\n    }\n}\n\nGraph* initGraph(int vertexNum){\n    Graph* G=(Graph*)malloc(sizeof(Graph));\n    G->vertexNum=vertexNum;\n    G->arcNum=0;\n    G->vertexs=(char*)malloc(sizeof(char)*vertexNum);\n\t\/\/\u7c7b\u4f3c\u4e8e\u4e8c\u7ef4\u6570\u7ec4,\u4f46\u5185\u5b58\u5e76\u4e0d\u5b8c\u5168\u8fde\u8d2f\n\tG->arcs = (int**)malloc(sizeof(int*)*vertexNum); \/\/\u521b\u5efa\u6307\u9488\u6570\u7ec4\n\tfor(int i=0; i < vertexNum;i++){\n\t\tG->arcs[i]=(int*)malloc(sizeof(int)*vertexNum); \/\/\u8ba9\u6307\u9488\u6570\u7ec4\u7684\u6bcf\u4e00\u4e2a\u6307\u9488\u6307\u5411\u4e00\u4e2a\u6570\u7ec4\n\t}\n    return G;\n}\n\nvoid createGraph(Graph* G,char* vertexs,int* arcs){\n    for(int i=0;i<G->vertexNum;i++){\n        G->vertexs[i]=vertexs[i];\n        for(int j=0;j<G->vertexNum;j++){\n            G->arcs[i][j]=*(arcs+i*G->vertexNum+j);\n            if(G->arcs[i][j]>0 && G->arcs[i][j]!=MAX) G->arcNum++;\n        }\n    }\n    G->arcNum\/=2;\/\/\u65e0\u5411\u56fe\u4e2d,\u8fb9\u4f1a\u8ba1\u7b97\u4e24\u6b21,\u771f\u5b9e\u8fb9\u6570\u9700\u8981\u96642\n}\n\nvoid dfs(Graph* G,int* visited,int index){\n    printf(\"%c \",G->vertexs[index]);\n    visited[index]=1;\n    for(int i=0;i<G->vertexNum;i++){\n        if(G->arcs[index][i]>0 && G->arcs[index][i]!=MAX && visited[i]==0){\n            dfs(G,visited,i);\n            visited[i];\n        }\n    }\n}\n\nint main(){\n    Graph* G=initGraph(N);\n\tint arcs[N][N] = {\n\t    {0,6,1,5,MAX,MAX},\n        {6,0,5,MAX,3,MAX},\n        {1,5,0,5,6,4},\n        {5,MAX,5,0,MAX,2},\n        {MAX,3,6,MAX,0,6},\n        {MAX,MAX,4,2,6,0}\n\t};\n    int visited[N];\n    for(int i=0;i<N;i++) visited[i]=0;\n    createGraph(G,\"123456\",(int*)arcs);\n    dfs(G,visited,0);\n    printf(\"\\n\");\n    prim(G,0);\n    return 0;\n}<\/code><\/pre>\n\n\n\n
kruskal\u7b97\u6cd5:<\/h4>\n\n\n\n
#include <stdio.h>\n#include <stdlib.h>\n\n#define N 6\n#define MAX 32767\n\n\/\/MAX\u8868\u793a\u65e0\u6cd5\u5230\u8fbe\u7684\u8ddd\u79bb\uff0c0\u8868\u793a\u81ea\u8eab\ntypedef struct Graph{\n    int vertexNum;\n    char* vertexs;\n    int arcNum;\n    int** arcs;\n}Graph;\n\n\n\/\/\u8fb9\ntypedef struct Edge{\n\tint src;  \/\/\u8d77\u59cb\u9876\u70b9\n\tint dst;  \/\/\u76ee\u7684\u9876\u70b9\n\tint weight;  \/\/\u6743\u503c\n}Edge;\n\nEdge* initEdge(Graph* G){\n    Edge* edge=(Edge*)malloc(sizeof(Edge)*G->arcNum);\n    int index=0;\n    for(int i=0;i<G->vertexNum;i++){\n        for(int j=i+1;j<G->vertexNum;j++){\n            if(G->arcs[i][j]>0&&G->arcs[i][j]!=MAX){\n                edge[index].src=i;\n                edge[index].dst=j;\n                edge[index].weight=G->arcs[i][j];\n                index++;\n            }\n        }\n    }\n    return edge;\n}\n\nvoid sortEdge(Edge* edge,int n){\n    for(int i=0;i<n-1;i++){\n        for(int j=0;j<n-i-1;j++){\n            if(edge[j].weight>edge[j+1].weight){\n                Edge t=edge[j];  \/\/c\u8bed\u8a00\u4e2d,\u7ed3\u6784\u4f53\u53ef\u4ee5\u6574\u4f53\u62f7\u8d1d\u8d4b\u503c.\u628a\u6574\u4e2a\u7ed3\u6784\u4f53\u7684\u5185\u5bb9\u9010\u5b57\u8282\u590d\u5236\u4e00\u4efd\u518d\u8d4b\u503c\n                edge[j]=edge[j+1];\n                edge[j+1]=t;\n            }\n        }\n    }\n}\n\n\n\/\/\u82e5\u65e0\u5411\u56fe\u4e0d\u662f\u8fde\u901a\u56fe\uff0c\u4f46\u56fe\u4e2d\u5b58\u50a8\u67d0\u4e2a\u5b50\u56fe\u7b26\u5408\u8fde\u901a\u56fe\u7684\u6027\u8d28\uff0c\u5219\u79f0\u8be5\u5b50\u56fe\u4e3a\u8fde\u901a\u5206\u91cf\n\/\/\u521d\u59cb\u5316\u8fde\u901a\u5206\u91cf\nint* initConnectedComponent(Graph* G){\n    int* connected=(int*)malloc(sizeof(int)*G->vertexNum);\n    for(int i=0;i<G->vertexNum;i++){\n        connected[i]=i;  \/\/\u521d\u59cb\u5316\u8fde\u901a\u5206\u91cf\u7f16\u53f7,\u8ba9\u5404\u4e2a\u9876\u70b9\u7684\u8fde\u901a\u5206\u91cf\u7f16\u53f7\u90fd\u4e3a\u81ea\u5df1\n    }\n    return connected;\n}\n\n\/\/\u601d\u60f3:\u57fa\u4e8e\u8fb9\u6784\u5efa\u6700\u5c0f\u751f\u6210\u6811\n\/**\n * \u5148\u628a\u8fb9\u5168\u90e8\u653e\u5165Edge\u6570\u7ec4,\u6309\u8fb9\u7684\u6743\u503c\u5927\u5c0f\u8fdb\u884c\u4ece\u5c0f\u5230\u5927\u6392\u5e8f.\n * \u6bcf\u4e2a\u8282\u70b9\u90fd\u662f\u4e00\u4e2a\u8fde\u901a\u5206\u91cf,\u4e3a\u6bcf\u4e2a\u9876\u70b9\u8d4b\u4e88\u4e0d\u540c\u7684\u8fde\u901a\u5206\u91cf\u7f16\u53f7\n * \u6bcf\u6b21\u627e\u4e00\u6761\u6743\u503c\u6700\u5c0f\u7684\u8fb9,\u5224\u65ad\u8fb9\u7684\u8d77\u70b9\u548c\u8fb9\u7684\u7ec8\u70b9\u662f\u5426\u5c5e\u4e8e\u540c\u4e00\u4e2a\u8fde\u901a\u5206\u91cf\n * \u82e5\u4e0d\u5c5e\u4e8e\u540c\u4e00\u4e2a\u8fde\u901a\u5206\u91cf,\u5219\u628a\u7ec8\u70b9\u6240\u5c5e\u7684\u8fde\u901a\u5206\u91cf\u5e76\u5165\u8d77\u70b9\u6240\u5c5e\u7684\u8fde\u901a\u5206\u91cf\n *\/\nvoid kruskal(Graph* G){\n    Edge* edge=initEdge(G);\n    sortEdge(edge,G->arcNum);\n    int* connected=initConnectedComponent(G);\n    int cnt=0;\/\/\u8bb0\u5f55\u627e\u5230\u7684\u8fb9\u6570\n    for(int i=0;i<G->arcNum;i++){\n        int s_cc=connected[edge[i].src]; \/\/\u5b50\u56fe1,\u8fde\u901a\u5206\u91cf\u7f16\u53f7:s_cc\n        int d_cc=connected[edge[i].dst]; \/\/\u5b50\u56fe2,\u8fde\u901a\u5206\u91cf\u7f16\u53f7:d_cc\n        if(s_cc!=d_cc){ \/\/\u5982\u679c\u4e24\u4e2a\u5b50\u56fe\u7684\u8fde\u901a\u5206\u91cf\u7f16\u53f7\u4e0d\u4e00\u81f4,\u628ad_cc\u5168\u90e8\u5e76\u5165s_cc\n            for(int j=0;j<G->vertexNum;j++){\n                if(connected[j]==d_cc){\n                    connected[j]=s_cc;\n                }\n            }\n            printf(\"v%c-->v%c weight:%d\\n\",G->vertexs[edge[i].src],G->vertexs[edge[i].dst],edge[i].weight);\n            cnt++;\n            if(cnt==G->vertexNum-1) break;\/\/\u53ea\u9700\u8981\u627e(\u8282\u70b9\u6570-1\u6b21)\u6761\u8fb9\u5c31\u80fd\u6784\u5efa\u51fa\u6700\u5c0f\u751f\u6210\u6811\n        }\n    }\n\n}\n\nGraph* initGraph(int vertexNum){\n    Graph* G=(Graph*)malloc(sizeof(Graph));\n    G->vertexNum=vertexNum;\n    G->arcNum=0;\n    G->vertexs=(char*)malloc(sizeof(char)*vertexNum);\n\t\/\/\u7c7b\u4f3c\u4e8e\u4e8c\u7ef4\u6570\u7ec4,\u4f46\u5185\u5b58\u5e76\u4e0d\u5b8c\u5168\u8fde\u8d2f\n\tG->arcs = (int**)malloc(sizeof(int*)*vertexNum); \/\/\u521b\u5efa\u6307\u9488\u6570\u7ec4\n\tfor(int i=0; i < vertexNum;i++){\n\t\tG->arcs[i]=(int*)malloc(sizeof(int)*vertexNum); \/\/\u8ba9\u6307\u9488\u6570\u7ec4\u7684\u6bcf\u4e00\u4e2a\u6307\u9488\u6307\u5411\u4e00\u4e2a\u6570\u7ec4\n\t}\n    return G;\n}\n\nvoid createGraph(Graph* G,char* vertexs,int* arcs){\n    for(int i=0;i<G->vertexNum;i++){\n        G->vertexs[i]=vertexs[i];\n        for(int j=0;j<G->vertexNum;j++){\n            G->arcs[i][j]=*(arcs+i*G->vertexNum+j);\n            if(G->arcs[i][j]>0 && G->arcs[i][j]!=MAX) G->arcNum++;\n        }\n    }\n    G->arcNum\/=2;\/\/\u65e0\u5411\u56fe\u4e2d,\u8fb9\u4f1a\u8ba1\u7b97\u4e24\u6b21,\u771f\u5b9e\u8fb9\u6570\u9700\u8981\u96642\n}\n\nvoid dfs(Graph* G,int* visited,int index){\n    printf(\"%c \",G->vertexs[index]);\n    visited[index]=1;\n    for(int i=0;i<G->vertexNum;i++){\n        if(G->arcs[index][i]>0 && G->arcs[index][i]!=MAX && visited[i]==0){\n            dfs(G,visited,i);\n            visited[i];\n        }\n    }\n}\n\nint main(){\n    Graph* G=initGraph(N);\n\tint arcs[N][N] = {\n\t    {0,6,1,5,MAX,MAX},\n        {6,0,5,MAX,3,MAX},\n        {1,5,0,5,6,4},\n        {5,MAX,5,0,MAX,2},\n        {MAX,3,6,MAX,0,6},\n        {MAX,MAX,4,2,6,0}\n\t};\n    int visited[N];\n    for(int i=0;i<N;i++) visited[i]=0;\n    createGraph(G,\"123456\",(int*)arcs);\n    dfs(G,visited,0);\n    printf(\"\\n\");\n    kruskal(G);\n    return 0;\n}<\/code><\/pre>\n\n\n\n
\u6700\u77ed\u8def\u5f84:<\/h3>\n\n\n\n
dijkstra\u7b97\u6cd5:<\/h4>\n\n\n\n
\u627e\u5230\u5176\u4ed6\u9876\u70b9\u5230\u8fbe\u8d77\u70b9\u7684\u6700\u77ed\u8def\u5f84<\/p>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
#include <stdio.h>\n#include <stdlib.h>\n\n#define N 6\n#define MAX 32767\n\n\/\/MAX\u8868\u793a\u65e0\u6cd5\u5230\u8fbe\u7684\u8ddd\u79bb\uff0c0\u8868\u793a\u81ea\u8eab\ntypedef struct Graph{\n    int vertexNum;\n    char* vertexs;\n    int arcNum;\n    int** arcs;\n}Graph;\n\n\/\/\u4ece\u672a\u52a0\u5165\u6700\u77ed\u8def\u5f84\u96c6\u5408\u7684\u8282\u70b9\u91cc\u627e\u51fa\u4e00\u4e2a\u52a0\u5165\u96c6\u5408\u8ddd\u79bb\u6700\u8fd1\u7684\u70b9\nint getMinIndex(Graph* G,int* f,int* dist){\n    int min=MAX;\n    int index;\n    for(int i=0;i<G->vertexNum;i++){\n        if(min>dist[i]&&!f[i]){\n            min=dist[i];\n            index=i;\n        }\n    }\n    return index;\n}\n\n\/\/\u601d\u60f3:\u5b9e\u65f6\u7ef4\u62a4\u5404\u8282\u70b9\u53bb\u5f80\u8d77\u70b9\u7684\u6700\u77ed\u8ddd\u79bb\u8868\u548c\u524d\u7f6e\u8282\u70b9\u8868\n\/\/\u4ece\u8d77\u70b9\u51fa\u53d1,\u6bcf\u6b21\u52a0\u5165\u4e00\u4e2a\u65b0\u8282\u70b9,\u5176\u4ed6\u8282\u70b9\u90fd\u4f1a\u53bb\u5c1d\u8bd5\u901a\u8fc7\u65b0\u8282\u70b9\u53bb\u5230\u8d77\u70b9\n\/\/\u82e5\u53d1\u73b0\u8d70\u65b0\u8282\u70b9\u8ddd\u79bb\u66f4\u8fd1,\u90a3\u4e48\u66f4\u65b0\u6700\u77ed\u8ddd\u79bb\u8868,\u5e76\u4ee4\u5176\u6210\u4e3a\u81ea\u5df1\u7684\u524d\u7f6e\u8282\u70b9\n\/\/index:\u8d77\u70b9\nint dijkstra(Graph* G,int index){\n    \/\/\u8bb0\u5f55\u9876\u70b9i\u662f\u5426\u52a0\u5165\u6700\u77ed\u8def\u5f84\u96c6\u5408\n    int* f=(int*)malloc(sizeof(int)*G->vertexNum); \n    \/\/\u8bb0\u5f55\u4efb\u610f\u9876\u70b9i\u5230\u8fbeindex\u7684\u524d\u7f6e\u8282\u70b9\n    int* pre=(int*)malloc(sizeof(int)*G->vertexNum); \n    \/\/\u8bb0\u5f55\u4efb\u610f\u9876\u70b9i\u5230\u8fbeindex\u7684\u6700\u77ed\u8ddd\u79bb\n    int* dist=(int*)malloc(sizeof(int)*G->vertexNum); \n\n    \/\/\u521d\u59cb\u5316\u8f85\u52a9\u6570\u7ec4\n    for(int i=0;i<G->vertexNum;i++){\n        f[i]=0;\n        if(i==index) f[i]=1;\n        pre[i]=-1;\n        if(G->arcs[index][i]>0&&G->arcs[index][i]!=MAX) pre[i]=index;\n        dist[i]=G->arcs[index][i];\n    }\n\n    for(int i=0;i<G->vertexNum-1;i++){\n        \/\/\u627e\u5230\u4e00\u4e2a\u53ef\u52a0\u5165\u6700\u77ed\u8def\u5f84\u96c6\u5408\u7684\u8ddd\u79bb\u6700\u8fd1\u7684\u70b9\n        int newIndex=getMinIndex(G,f,dist);\n        f[newIndex]=1;\n        for(int j=0;j<G->vertexNum;j++){\n            \/\/\u5224\u65ad\u901a\u8fc7\u65b0\u52a0\u5165\u8282\u70b9\u5230\u8fbeindex\u8def\u5f84\u7684\u8ddd\u79bb\u662f\u5426\u66f4\u77ed\n            if(dist[j]>dist[newIndex]+G->arcs[newIndex][j]&&!f[j]){\n                pre[j]=newIndex;\/\/\u4f7f\u5176\u6210\u4e3a\u81ea\u5df1\u7684\u524d\u7f6e\u8282\u70b9\n                dist[j]=dist[newIndex]+G->arcs[newIndex][j];\/\/\u66f4\u65b0\u8ddd\u79bb\n            }\n        }\n    }\n\n\n    for(int i=0;i<G->vertexNum;i++){\n        if(pre[i]==-1){\n            printf(\"vertex:%c \u8d77\u70b9 dist:%d\\n\",G->vertexs[i],dist[i]);\n        }else{\n            printf(\"vertex:%c pre:%c dist:%d\\n\",G->vertexs[i],G->vertexs[pre[i]],dist[i]);\n        }\n    }\n    \n}\n\n\nGraph* initGraph(int vertexNum){\n    Graph* G=(Graph*)malloc(sizeof(Graph));\n    G->vertexNum=vertexNum;\n    G->arcNum=0;\n    G->vertexs=(char*)malloc(sizeof(char)*vertexNum);\n\t\/\/\u7c7b\u4f3c\u4e8e\u4e8c\u7ef4\u6570\u7ec4,\u4f46\u5185\u5b58\u5e76\u4e0d\u5b8c\u5168\u8fde\u8d2f\n\tG->arcs = (int**)malloc(sizeof(int*)*vertexNum); \/\/\u521b\u5efa\u6307\u9488\u6570\u7ec4\n\tfor(int i=0; i < vertexNum;i++){\n\t\tG->arcs[i]=(int*)malloc(sizeof(int)*vertexNum); \/\/\u8ba9\u6307\u9488\u6570\u7ec4\u7684\u6bcf\u4e00\u4e2a\u6307\u9488\u6307\u5411\u4e00\u4e2a\u6570\u7ec4\n\t}\n    return G;\n}\n\nvoid createGraph(Graph* G,char* vertexs,int* arcs){\n    for(int i=0;i<G->vertexNum;i++){\n        G->vertexs[i]=vertexs[i];\n        for(int j=0;j<G->vertexNum;j++){\n            G->arcs[i][j]=*(arcs+i*G->vertexNum+j);\n            if(G->arcs[i][j]>0 && G->arcs[i][j]!=MAX) G->arcNum++;\n        }\n    }\n    G->arcNum\/=2;\/\/\u65e0\u5411\u56fe\u4e2d,\u8fb9\u4f1a\u8ba1\u7b97\u4e24\u6b21,\u771f\u5b9e\u8fb9\u6570\u9700\u8981\u96642\n}\n\nvoid dfs(Graph* G,int* visited,int index){\n    printf(\"%c \",G->vertexs[index]);\n    visited[index]=1;\n    for(int i=0;i<G->vertexNum;i++){\n        if(G->arcs[index][i]>0 && G->arcs[index][i]!=MAX && visited[i]==0){\n            dfs(G,visited,i);\n            visited[i];\n        }\n    }\n}\n\nint main(){\n\tGraph* G=initGraph(N);\n\tint arcs[N][N] = {\n        { 0,  12, MAX, MAX, MAX, 16, 14 }, \/\/ 1\n        { 12,  0, 10,  MAX, MAX,  7, MAX }, \/\/ 2\n        { MAX,10,  0,   3,   5,  6, MAX }, \/\/ 3\n        { MAX,MAX,3,   0,   4, MAX, MAX }, \/\/ 4\n        { MAX,MAX,5,   4,   0,  2,  8 }, \/\/ 5\n        { 16,  7, 6,  MAX,  2,  0,  9 }, \/\/ 6\n        { 14,MAX,MAX,MAX,  8,  9,  0 }  \/\/ 7\n\t};\n    int visited[N];\n    for(int i=0;i<N;i++) visited[i]=0;\n    createGraph(G,\"123456\",(int*)arcs);\n    dfs(G,visited,0);\n    printf(\"\\n\");\n    dijkstra(G,0);\n    return 0;\n}<\/code><\/pre>\n\n\n\n
floyd\u7b97\u6cd5:<\/h4>\n\n\n\n
3for\u7b97\u6cd5<\/p>\n\n\n\n
\u627e\u5230\u5404\u4e2a\u9876\u70b9\u53bb\u5f80\u5176\u4ed6\u5404\u4e2a\u9876\u70b9\u7684\u6700\u77ed\u8def\u5f84<\/p>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
#include <stdio.h>\n#include <stdlib.h>\n#define N 4\n\n#define MAX 32727\ntypedef struct Graph{\n\tchar* vertexs;\n\tint** arcs;\n\tint vertexNum;\n\tint arcNum;\n}Graph;\n\n\/\/\u4e8c\u7ef4\u51fd\u6570\u4f20\u9012\n\/\/int (*pre)[N]:\u6307\u5411\u4e00\u884c\u7684\u6307\u9488,\u4e00\u884c\u6709N\u4e2aint;   int (*pre)[N]\u7b49\u4ef7\u4e8eint pre[][N]\nvoid findLoad(Graph*G,int pre[][N],int src,int dst){\n\t\n\tint i=src;\n\tint j=dst;\n\tprintf(\"\u6700\u77ed\u8def\u5f84:v%c\",G->vertexs[dst]);\n\twhile(pre[i][j]!=-1){\/\/\u4e00\u76f4\u5012\u7740\u8d70,\u4e00\u76f4\u8d70\u5230\u8d77\u70b9\n\t\tint t=pre[i][j];\n\t\tprintf(\"->v%c\",G->vertexs[t]);\n\t\tj=t;\n\t}\n}\n\n\/\/\u6838\u5fc3:pre\u6570\u7ec4\u4f1a\u8bb0\u5f55i\u5230j\u6700\u77ed\u8def\u5f84\u4e0aj\u7684\u524d\u7f6e\u8282\u70b9,\u4ece\u7ec8\u70b9\u5012\u63a8\u56de\u8d77\u70b9\u5373\u53ef\u5f97\u5230\u6700\u77ed\u8def\u5f84\n\/\/\u601d\u60f3:\u4e09\u5c42\u5faa\u73af,\u6bcf\u6b21\u9009\u4e2d\u4e00\u4e2a\u8282\u70b9\u5f53\u4f5c\u4e2d\u8f6c\u8282\u70b9i,\n\/\/\u4f9d\u6b21\u904d\u5386\u5176\u4ed6\u5404\u4e2a\u9876\u70b9j\u80fd\u5426\u901a\u8fc7\u9876\u70b9i\u66f4\u8fd1\u5230\u8fbe\u5176\u4ed6\u5404\u4e2a\u9876\u70b9k\n\/\/\u82e5\u53d1\u73b0\u901a\u8fc7i\u9876\u70b9\u8def\u7a0b\u66f4\u8fd1,\u90a3\u4e48\u8bb0\u5f55i\u4e3aj\u5230k\u7684\u524d\u7f6e\u8282\u70b9,\u5e76\u66f4\u65b0\u6700\u77ed\u8ddd\u79bb\nvoid floyd(Graph* G){\n    int dist[G->vertexNum][G->vertexNum];\/\/\u8bb0\u5f55\u4efb\u610f\u4e24\u70b9\u4e4b\u95f4\u7684\u6700\u77ed\u8ddd\u79bb\n    int pre[G->vertexNum][G->vertexNum];\/\/\u8bb0\u5f55\u4efb\u610f\u4e24\u70b9\u4e4b\u95f4\u7684\u524d\u7f6e\u8282\u70b9.\u524d\u7f6e\u8282\u70b9:\u4ece i \u5230 j \u7684\u6700\u77ed\u8def\u5f84\u4e0a\uff0cj \u7684\u524d\u4e00\u4e2a\u8282\u70b9\n    for(int i = 0;i<G->vertexNum;i++){\n\t\tfor(int j = 0;j<G->vertexNum;j++){\n\t\t\tdist[i][j]=G->arcs[i][j];\n\t\t\tpre[i][j]=-1;\n\t\t\tif(G->arcs[i][j]>0 && G->arcs[i][j]!=MAX) pre[i][j]=i;\n\t\t}\n\t}\n\n\tfor(int i = 0;i<G->vertexNum;i++){\/\/i:\u4e2d\u8f6c\u8282\u70b9\n\t\tfor(int j = 0;j<G->vertexNum;j++){\/\/j:\u8d77\u70b9\n\t\t\tfor(int k = 0;k<G->vertexNum;k++){\/\/k:\u7ec8\u70b9\n\t\t\t\tif(j!=i&&k!=i&&j!=k){\n\t\t\t\t\tif(dist[j][k]>dist[j][i]+dist[i][k]){\n\t\t\t\t\t\tdist[j][k]=dist[j][i]+dist[i][k];\/\/\u5982\u679c\u901a\u8fc7\u4e2d\u8f6c\u8282\u70b9\u5230\u8fbe\u76ee\u7684\u8282\u70b9\u8ddd\u79bb\u66f4\u77ed\u5219\u66f4\u65b0\n\t\t\t\t\t\tpre[j][k]=pre[i][k];\/\/\u66f4\u65b0j\u5230k\u7684\u6700\u77ed\u8def\u5f84\u4e0a,k\u7684\u524d\u4e00\u4e2a\u8282\u70b9\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\tprintf(\"dist:\\n\");\n\tfor(int i = 0;i<G->vertexNum;i++){\n\t\tfor(int j = 0;j<G->vertexNum;j++){\n\t\t\tprintf(\"%d \",dist[i][j]);\n\t\t}\n\t\tprintf(\"\\n\");\n\t}\n\tprintf(\"pre:\\n\");\n\tfor(int i = 0;i<G->vertexNum;i++){\n\t\tfor(int j = 0;j<G->vertexNum;j++){\n\t\t\tprintf(\"%d \",pre[i][j]);\n\t\t}\n\t\tprintf(\"\\n\");\n\t}\n\t\n\tfindLoad(G,pre,0,2);\n\n}\n\nGraph* initGraph(int vertexNum){\n\tGraph* G=(Graph*)malloc(sizeof(Graph));\n\tG->vertexs = (char*)malloc(sizeof(char)*vertexNum);\n\t\n\t\/\/\u7c7b\u4f3c\u4e8e\u4e8c\u7ef4\u6570\u7ec4,\u4f46\u5185\u5b58\u5e76\u4e0d\u5b8c\u5168\u8fde\u8d2f\n\tG->arcs = (int**)malloc(sizeof(int*)*vertexNum); \/\/\u521b\u5efa\u6307\u9488\u6570\u7ec4\n\tfor(int i=0; i < vertexNum;i++){\n\t\tG->arcs[i]=(int*)malloc(sizeof(int)*vertexNum); \/\/\u8ba9\u6307\u9488\u6570\u7ec4\u7684\u6bcf\u4e00\u4e2a\u6307\u9488\u6307\u5411\u4e00\u4e2a\u6570\u7ec4\n\t}\n\tG -> vertexNum=vertexNum;\n\tG -> arcNum=0;\n\treturn G;\n}\n\nvoid createGraph(Graph* G,char* vertexs,int* arcs){\n\tfor(int i=0;i<G->vertexNum;i++){\n\t\tG->vertexs[i]=vertexs[i];\n\t\tfor(int j=0;j<G->vertexNum;j++){\n\t\t\tG->arcs[i][j]=*(arcs + i*G->vertexNum+j);\n\t\t\tif(G->arcs[i][j]!=0&&G->arcs[i][j]!=MAX) G->arcNum++;\n\t\t}\n\t}\n\tG->arcNum\/=2;\/\/\u65e0\u5411\u56fe\u4e2d,\u8fb9\u4f1a\u8ba1\u7b97\u4e24\u6b21,\u771f\u5b9e\u8fb9\u6570\u9700\u8981\u96642\n}\n\n\nvoid dfs(Graph* G,int* visited,int index){\n\tprintf(\"%c \",G->vertexs[index]);\n\tvisited[index]=1;\n\tfor(int i =0;i<G->vertexNum;i++){\n\t\tif(G->arcs[index][i]>0 && G->arcs[index][i]!=MAX &&visited[i]==0){\n\t\t\tdfs(G,visited,i);\n\t\t}\n\t}\n}\n\n\nint main(){\n\tGraph* G=initGraph(N);\n\tint arcs[N][N] = {\n\t\t{0,1,MAX,3},\n\t\t{1,0,3,2},\n\t\t{MAX,3,0,8},\n\t\t{3,2,8,0}\n\t};\n\tcreateGraph(G,\"1234\",(int*)arcs); \n\tint visited[N];\n\tfor(int i=0;i<G->vertexNum;i++){\n\t\tvisited[i]=0;\n\t}\n\tdfs(G,visited,0);\n\tprintf(\"\\n\");\n\tprintf(\"\\n\");\n\tfloyd(G);\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
\u62d3\u6251\u6392\u5e8f:<\/h3>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
#include <stdio.h>\n#include <stdlib.h>\n#define N 6\n#define MAX 32727\ntypedef struct Graph{\n\tchar* vertexs;\n\tint** arcs;\n\tint vertexNum;\n\tint arcNum;\n}Graph;\n\ntypedef struct Node{\n    int data;\n    struct Node* next;\n}Node;\n\nNode* initStack(){\n    Node* stack=(Node*)malloc(sizeof(Node));\n    stack->data=0;\n    stack->next=NULL;\n    return stack;\n}\n\nvoid push(Node* stack,int data){\n    Node* newNode=(Node*)malloc(sizeof(Node));\n    newNode->next=stack->next;\n    newNode->data=data;\n    stack->next=newNode;\n    stack->data++;\n}\n\nint isEmpty(Node* stack){\n    if(stack->next==NULL) return 1;\n    else return 0;\n}\n\nint pop(Node* stack){\n    if(isEmpty(stack)) return -1;\n    Node* t=stack->next;\n    stack->next=t->next;\n    stack->data--;\n    int data=t->data;\n    free(t);\n    return data;\n}\n\nvoid findInDegrees(Graph* G,int* inDegrees){\n    for(int i=0;i<G->vertexNum;i++){\n        inDegrees[i]=0;\n    }\n    for(int i=0;i<G->vertexNum;i++){\n        for(int j=0;j<G->vertexNum;j++){\n            if(G->arcs[i][j]>0&&G->arcs[i][j]!=MAX) inDegrees[j]++; \/\/\u5982\u679c\u88ab\u5176\u4ed6\u8282\u70b9\u6307\u5411\u4e86\uff0c\u5165\u5ea6\u5c31\u52a0\u4e00\n        }\n    }\n}\n\nvoid topologicalSort(Graph* G){\n    Node* stack=initStack();\n    int inDegrees[G->vertexNum];\/\/\u5165\u5ea6\u6570\u7ec4\n    int vertexCount=0;\/\/\u8bb0\u5f55\u88ab\u6458\u4e0b\u8282\u70b9\u7684\u6570\u91cf\n    int top[G->vertexNum];\/\/\u4fdd\u5b58\u62d3\u6251\u6392\u5e8f\u7ed3\u679c\n    findInDegrees(G,inDegrees);\n\n    for(int i=0;i<G->vertexNum;i++){\n        if(inDegrees[i]==0){ \/\/\u6458\u4e0b\u5f53\u524d\u5165\u5ea6\u4e3a0\u7684\u8282\u70b9\n            push(stack,i);\n            top[vertexCount++]=i;\n        }\n    }\n    \n    while(!isEmpty(stack)){\n        int index=pop(stack);\n        for(int i=0;i<G->vertexNum;i++){\n            if(G->arcs[index][i]>0&&G->arcs[index][i]!=MAX&&inDegrees[i]!=0){\n                inDegrees[i]--;  \n                if(inDegrees[i]==0){ \/\/\u6458\u4e0b\u5f53\u524d\u5165\u5ea6\u4e3a0\u7684\u8282\u70b9\n                    push(stack,i);\n                    top[vertexCount++]=i;\n                }\n            }\n        }\n    }\n    for(int i=0;i<vertexCount;i++){\n        printf(\"%c \",G->vertexs[top[i]]);\n    }\n    printf(\"\\n\");\n    if(vertexCount==G->vertexNum){\n        printf(\"\u8be5\u56fe\u65e0\u73af\u8def\\n\");\/\/\u5982\u679c\u6ca1\u6709\u73af\u8def\uff0c\u6240\u6709\u8282\u70b9\u90fd\u80fd\u88ab\u6458\u4e0b\n    }else{\n        printf(\"\u8be5\u56fe\u6709\u73af\u8def\\n\");\/\/\u5982\u679c\u51fa\u73b0\u73af\u8def\uff0c\u5c31\u4f1a\u6709\u8282\u70b9\u65e0\u6cd5\u88ab\u6458\u4e0b\n    }\n}\n\nGraph* initGraph(int vertexNum){\n\tGraph* G=(Graph*)malloc(sizeof(Graph));\n\tG->vertexs = (char*)malloc(sizeof(char)*vertexNum);\n\t\n\t\/\/\u7c7b\u4f3c\u4e8e\u4e8c\u7ef4\u6570\u7ec4,\u4f46\u5185\u5b58\u5e76\u4e0d\u5b8c\u5168\u8fde\u8d2f\n\tG->arcs = (int**)malloc(sizeof(int*)*vertexNum); \/\/\u521b\u5efa\u6307\u9488\u6570\u7ec4\n\tfor(int i=0; i < vertexNum;i++){\n\t\tG->arcs[i]=(int*)malloc(sizeof(int)*vertexNum); \/\/\u8ba9\u6307\u9488\u6570\u7ec4\u7684\u6bcf\u4e00\u4e2a\u6307\u9488\u6307\u5411\u4e00\u4e2a\u6570\u7ec4\n\t}\n\tG -> vertexNum=vertexNum;\n\tG -> arcNum=0;\n\treturn G;\n}\n\nvoid createGraph(Graph* G,char* vertexs,int* arcs){\n\tfor(int i=0;i<G->vertexNum;i++){\n\t\tG->vertexs[i]=vertexs[i];\n\t\tfor(int j=0;j<G->vertexNum;j++){\n\t\t\tG->arcs[i][j]=*(arcs + i*G->vertexNum+j);\n\t\t\tif(G->arcs[i][j]!=0&&G->arcs[i][j]!=MAX) G->arcNum++;\n\t\t}\n\t}\n}\n\n\/\/\u6709\u5411\u56fe\u4e2d,dfs\u548cbfs\u4e0d\u4e00\u5b9a\u80fd\u904d\u5386\u5230\u6240\u6709\u8282\u70b9,\u56e0\u4e3a\u53ef\u80fd\u65ad\u6389.\n\/\/\u82e5\u8981\u904d\u5386\u5168\u90e8\u8282\u70b9,\u53ef\u4ee5\u5bf9\u672a\u904d\u5386\u5230\u7684\u8282\u70b9\u518d\u6b21\u8fdb\u884cdfs\/bfs.\nvoid dfs(Graph* G,int* visited,int index){\n\tprintf(\"%c \",G->vertexs[index]);\n\tvisited[index]=1;\n\tfor(int i=0;i<G->vertexNum;i++){\n\t\tif(G->arcs[index][i]>0 && G->arcs[index][i]!=MAX &&visited[i]==0){\n\t\t\tdfs(G,visited,i);\n\t\t}\n\t}\n}\n\n\nint main(){\n\tGraph* G=initGraph(N);\n\tint arcs[N][N] = {\n        { 0, 1, 1, 1, 0, 0 }, \/\/ 1\n        { 0, 0, 0, 0, 0, 0 }, \/\/ 2\n        { 0, 1, 0, 0, 1, 0 }, \/\/ 3\n        { 0, 0, 0, 0, 1, 0 }, \/\/ 4\n        { 0, 0, 0, 0, 0, 0 }, \/\/ 5\n        { 0, 0, 0, 1, 1, 0 }  \/\/ 6\n\t};\n\tcreateGraph(G,\"123456\",(int*)arcs); \n\tint visited[N];\n\tfor(int i=0;i<G->vertexNum;i++){\n\t\tvisited[i]=0;\n\t}\n\tdfs(G,visited, 0);\n\tprintf(\"\\n\");\n    topologicalSort(G);\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
\u5173\u952e\u8def\u5f84:<\/h3>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
#include <stdio.h>\n#include <stdlib.h>\n#define N 9\n\n#define MAX 32727\ntypedef struct Graph{\n\tchar* vertexs;\n\tint** arcs;\n\tint vertexNum;\n\tint arcNum;\n}Graph;\n\ntypedef struct Node{\n    int data;\n    struct Node* next;\n}Node;\n\nNode* initStack(){\n    Node* stack=(Node*)malloc(sizeof(Node));\n    stack->data=0;\n    stack->next=NULL;\n    return stack;\n}\n\nvoid push(Node* stack,int data){\n    Node* newNode=(Node*)malloc(sizeof(Node));\n    newNode->next=stack->next;\n    newNode->data=data;\n    stack->next=newNode;\n    stack->data++;\n}\n\nint isEmpty(Node* stack){\n    if(stack->next==NULL) return 1;\n    else return 0;\n}\n\nint pop(Node* stack){\n    if(isEmpty(stack)) return -1;\n    Node* t=stack->next;\n    stack->next=t->next;\n    stack->data--;\n    int data=t->data;\n    free(t);\n    return data;\n}\n\nint* findInDegrees(Graph* G){\n    int *inDegrees=(int*)malloc(sizeof(int)*G->vertexNum); \/\/\u7edf\u8ba1\u6bcf\u4e2a\u8282\u70b9\u7684\u5165\u5ea6\n    for(int i=0;i<G->vertexNum;i++){\n        inDegrees[i]=0;   \n    }\n    for(int i=0;i<G->vertexNum;i++){\n        for(int j=0;j<G->vertexNum;j++){\n            if(G->arcs[i][j]&&G->arcs[i][j]!=MAX){ \/\/\u88ab\u5176\u4ed6\u8282\u70b9\u6307\u5411\u4e86,\u5219\u5165\u5ea6++\n                inDegrees[j]++; \n            } \n        }    \n    }\n    return inDegrees;\n}\n\nint* topologicalSort(Graph* G){\n    int *inDegrees=findInDegrees(G);\n    int count=0;  \/\/\u8bb0\u5f55\u88ab\u6458\u4e0b\u7684\u8282\u70b9\u4e2a\u6570\n    \/\/ for(int i=0;i<G->vertexNum;i++){\n    \/\/     printf(\"%d \",inDegrees[i]);\n    \/\/ }\n\n    \/\/\u7528\u6808\u4f18\u5316\n    Node* stack=initStack();\n    int *top=(int*)malloc(sizeof(int)*G->vertexNum);\/\/\u987a\u5e8f\u4fdd\u5b58\u51fa\u6808\u540e\u7684\u8282\u70b9\u7d22\u5f15\n    for(int i=0;i<G->vertexNum;i++){\n        if(inDegrees[i]==0){  \/\/\u627e\u5230\u5165\u5ea6\u4e3a0\u7684\u70b9,\u5165\u6808\n            push(stack,i);\n        }\n    }\n    while(!isEmpty(stack)){\n        int vertex=pop(stack);\n        top[count++]=vertex;\n        for(int i=0;i<G->vertexNum;i++){\n            if(G->arcs[vertex][i]&&G->arcs[vertex][i]!=MAX){\n                inDegrees[i]--;\n                if(inDegrees[i]==0) push(stack,i);\n            }\n        }\n    }\n\n    for(int i=0;i<G->vertexNum;i++){\n        printf(\"%c \",G->vertexs[top[i]]);\n    }\n\n    if(count<G->vertexNum) printf(\"\\n\u8be5\u56fe\u6709\u73af\u8def\");\n    else printf(\"\\n\u8be5\u56fe\u65e0\u73af\u8def\");\n    printf(\"\\n\");\n    return top;\n}\n\nGraph* initGraph(int vertexNum){\n\tGraph* G=(Graph*)malloc(sizeof(Graph));\n\tG->vertexs = (char*)malloc(sizeof(char)*vertexNum);\n\t\n\t\/\/\u7c7b\u4f3c\u4e8e\u4e8c\u7ef4\u6570\u7ec4,\u4f46\u5185\u5b58\u5e76\u4e0d\u5b8c\u5168\u8fde\u8d2f\n\tG->arcs = (int**)malloc(sizeof(int*)*vertexNum); \/\/\u521b\u5efa\u6307\u9488\u6570\u7ec4\n\tfor(int i=0; i < vertexNum;i++){\n\t\tG->arcs[i]=(int*)malloc(sizeof(int)*vertexNum); \/\/\u8ba9\u6307\u9488\u6570\u7ec4\u7684\u6bcf\u4e00\u4e2a\u6307\u9488\u6307\u5411\u4e00\u4e2a\u6570\u7ec4\n\t}\n\tG -> vertexNum=vertexNum;\n\tG -> arcNum=0;\n\treturn G;\n}\n\nvoid createGraph(Graph* G,char* vertexs,int* arcs){\n\tG->vertexs=vertexs; \/\/\u76f4\u63a5\u628a\u6307\u5411\u7684\u5730\u5740\u590d\u5236\u7ed9G->vertexs\n    for(int i=0;i<G->vertexNum;i++){\n\t\tfor(int j=0;j<G->vertexNum;j++){\n\t\t\tG->arcs[i][j]=*(arcs + i*G->vertexNum+j);\n\t\t\tif(G->arcs[i][j]!=0&&G->arcs[i][j]!=MAX) G->arcNum++;\n\t\t}\n\t}\n\tG->arcNum\/=2;\/\/\u65e0\u5411\u56fe\u4e2d,\u8fb9\u4f1a\u8ba1\u7b97\u4e24\u6b21,\u771f\u5b9e\u8fb9\u6570\u9700\u8981\u96642\n}\n\n\nvoid dfs(Graph* G,int* visited,int index){\n\tprintf(\"%c \",G->vertexs[index]);\n\tvisited[index]=1;\n\tfor(int i =0;i<G->vertexNum;i++){\n\t\tif(G->arcs[index][i]>0 && G->arcs[index][i]!=MAX &&visited[i]==0){\n\t\t\tdfs(G,visited,i);\n\t\t}\n\t}\n}\n\n\/\/\u627e\u5230\u9876\u70b9\u5728top\u6570\u7ec4\u4e2d\u7684\u4f4d\u7f6e\u8fd4\u56de\nint getIndex(Graph* G,int* top,int vertex){\n    int j;\n    for(j=0;j<G->vertexNum;j++){\n        if(top[j]==vertex) break;\n    }\n    return j;\n}\n\nvoid criticalPath(Graph* G){\n    int* top=topologicalSort(G);\n    int* early = (int*)malloc(sizeof(int)*G->vertexNum);\/\/\u8bb0\u5f55\u5404\u4e2a\u8282\u70b9\u6700\u65e9\u53d1\u751f\u65f6\u95f4\uff0c\u5143\u7d20\u987a\u5e8f\u4e0etop\u6570\u7ec4\u76f8\u5bf9\u5e94\n    int* late = (int*)malloc(sizeof(int)*G->vertexNum);\/\/\u8bb0\u5f55\u5404\u4e2a\u8282\u70b9\u6700\u665a\u53d1\u751f\u65f6\u95f4\uff0c\u5143\u7d20\u987a\u5e8f\u4e0etop\u6570\u7ec4\u76f8\u5bf9\u5e94\n    for(int i=0;i<G->vertexNum;i++){\n        early[i]=0;\n        late[i]=0;\n    }\n    \/\/1.\u8ba1\u7b97\u4e8b\u4ef6\u6307\u6807\n    \/\/\u8ba1\u7b97top[i]\u8282\u70b9\u6700\u65e9\u5f00\u59cb\u65f6\u95f4,\u5373\u6240\u6709\u524d\u9a71\u8282\u70b9\u7684\u6700\u665a\u5b8c\u6210\u65f6\u95f4\n    for(int i=1;i<G->vertexNum;i++){ \/\/\u62d3\u6251\u5e8f\u5217\uff0c\u8fd9\u91cc\u7684i\u5bf9\u5e94top\u6570\u7ec4\u7684\u7d22\u5f15\n        int max=0;\n        for(int j=0;j<G->vertexNum;j++){ \/\/\u8282\u70b9j\n            if(G->arcs[j][top[i]]>0&&G->arcs[j][top[i]]!=MAX){\n                int index=getIndex(G,top,j); \/\/\u627e\u5230\u524d\u9a71\u8282\u70b9\u5728top\u5e8f\u5217\u7684\u7d22\u5f15\u503c\n                if(max<early[index]+G->arcs[j][top[i]]){\n                    max=early[index]+G->arcs[j][top[i]];\n                }\n            }\n        }\n        early[i]=max;\n    }\n\n    for (int i = 0; i < G ->vertexNum; i++) {\n        printf(\"%d \", early[i]);\n    }\n    printf(\"\\n\");\n\n    \/\/\u8ba1\u7b97top[i]\u8282\u70b9\u6700\u665a\u5f00\u59cb\u65f6\u95f4,\u5373\u4e0d\u803d\u8bef\u6240\u6709\u540e\u7eed\u8282\u70b9\u6309\u65f6\u6267\u884c\u7684\u6700\u665a\u5f00\u59cb\u65f6\u95f4\n    late[G->vertexNum-1]=early[G->vertexNum-1];\/\/\u8d4b\u521d\u503c,\u4e0b\u9762\u5faa\u73af\u53ef\u4ee5\u4ece\u5012\u6570\u7b2c\u4e8c\u4e2a\u8282\u70b9\u5f00\u59cb\n    for(int i=G->vertexNum-2;i>=0;i--){ \/\/\u9006\u62d3\u6251\u6392\u5e8f\u7684\u5e8f\u5217,i\u5bf9\u5e94top\u6570\u7ec4\u7684\u7d22\u5f15\n        int min=MAX;\n        for(int j=0;j<G->vertexNum;j++){ \/\/\u8282\u70b9j\n            if(G->arcs[top[i]][j]>0&&G->arcs[top[i]][j]!=MAX){\n                int index=getIndex(G,top,j); \/\/\u627e\u5230\u540e\u7ee7\u8282\u70b9\u5728top\u5e8f\u5217\u7684\u7d22\u5f15\u503c\n                if(min>late[index]-G->arcs[top[i]][j]){\n                    min=late[index]-G->arcs[top[i]][j];\n                }\n            }\n        }\n        late[i]=min;\n    }\n\n    for (int i = 0; i < G ->vertexNum; i++) {\n        printf(\"%d \", late[i]);\n    }\n    \/\/2.\u627e\u5173\u952e\u6d3b\u52a8\n    for (int i = 0; i < G ->vertexNum; i++) { \/\/\u8282\u70b9i\n        for (int j = 0; j < G ->vertexNum; j++) { \/\/\u8282\u70b9j\n            if(G->arcs[i][j]>0&&G->arcs[i][j]!=MAX){\n                int start=getIndex(G,top,i);\/\/\u627e\u5230i\u8282\u70b9\u5728top\u6570\u7ec4\u7684\u4f4d\u7f6e\n                int end=getIndex(G,top,j);\/\/\u627e\u5230j\u8282\u70b9\u5728top\u6570\u7ec4\u7684\u4f4d\u7f6e\n                int earlyTime=early[start]; \/\/\u6d3b\u52a8\u6700\u65e9\u5b8c\u6210\u65f6\u95f4\n                int lateTime=late[end]-G->arcs[i][j]; \/\/\u6d3b\u52a8\u6700\u665a\u5b8c\u6210\u65f6\u95f4\n                if(earlyTime==lateTime) printf(\"\\n\u5173\u952e\u6d3b\u52a8:v%c->v%c\", G->vertexs[i],G->vertexs[j]);\n            }\n        }\n    }\n    printf(\"\\n\");\n}\n\nint main(){\n\tGraph* G=initGraph(N);\n\tint arcs[N][N] = {\n \/*V0*\/ {0,6,4,5,MAX,MAX,MAX,MAX,MAX},\n \/*V1*\/ {MAX,0,MAX,MAX,1,MAX,MAX,MAX,MAX},\n \/*V2*\/ {MAX,MAX,0,MAX,1,MAX,MAX,MAX,MAX},\n \/*V3*\/ {MAX,MAX,MAX,0,MAX,2,MAX,MAX,MAX},\n \/*V4*\/ {MAX,MAX,MAX,MAX,0,MAX,9,7,MAX},\n \/*V5*\/ {MAX,MAX,MAX,MAX,MAX,0,MAX,4,MAX},\n \/*V6*\/ {MAX,MAX,MAX,MAX,MAX,MAX,0,MAX,2},\n \/*V7*\/ {MAX,MAX,MAX,MAX,MAX,MAX,MAX,0,4},\n \/*V8*\/ {MAX,MAX,MAX,MAX,MAX,MAX,MAX,MAX,0}\n\t};\n\tcreateGraph(G,\"012345678\\0\",(int*)arcs); \n\tint visited[N];\n\tfor(int i=0;i<G->vertexNum;i++){\n\t\tvisited[i]=0;\n\t}\n\tdfs(G,visited,0);\n\tprintf(\"\\n\");\n    criticalPath(G);\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
B\u6811:<\/h3>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
#include <stdio.h>\n#include <stdlib.h>\n#include <time.h>\n\n\/\/B\u6811\u8282\u70b9\ntypedef struct Node{\n    \/\/\u9636\u6570m\n    int level; \n    \/\/\u5173\u952e\u5b57\u4e2a\u6570\n    int keyNum;\n    \/\/\u5b69\u5b50\u4e2a\u6570\n    int childNum;\n    \/\/\u5173\u952e\u5b57\u6570\u7ec4,\u957f\u5ea6\u4e3alevel+1,\u4e0b\u6807\u4ece1\u5230level-1,\u7b2c0\u4e2a\u548c\u7b2clevel\u4e2a\u9884\u7559\n    int* keys; \n    \/\/\u7236\u4eb2\n    struct Node* parent;\n    \/\/\u5b69\u5b50\u6307\u9488\u6570\u7ec4\n    struct Node** children;\n}Node;\n\n\/\/\u521d\u59cb\u5316\u8282\u70b9\nNode* initNode(int level){\n    Node* node=(Node*)malloc(sizeof(Node));\n    node->level=level;\n    node->keyNum=0;\n    node->childNum=0;\n    node->keys=(int*)malloc(sizeof(int)*(level+1));\n    node->parent=NULL;\n    node->children=(Node**)malloc(sizeof(Node*)*level);\n    for(int i=0;i<node->level;i++){\n        node->keys[i]=0;\n        node->children[i]=NULL;\n    }\n    \/\/node->keys[level]=0;\n    return node;\n}\n\n\/\/\u627e\u5230\u8282\u70b9\u5408\u9002\u7684\u63d2\u5165\u4f4d\u7f6e\nint findSuiteIndex(Node* node,int data){\n    int index;\n    for(index=1;index<=node->keyNum;index++){\n        \/\/\u627e\u5230\u6709\u6bd4\u81ea\u5df1\u5927\u7684\u5173\u952e\u5b57\u5c31\u9000\u51fa\u5faa\u73af\n        if(data < node->keys[index]) break;\n    }\n    return index;\/\/1\u5230m\n}\n\n\/\/B\u6811\u7684\u6bcf\u4e2a\u8282\u70b9\u7684\u5b69\u5b50\u6307\u9488\u4e2a\u6570\u4f1a\u6bd4\u5173\u952e\u5b57\u6570\u591a\u4e00\u4e2a\n\/\/\u627e\u5230\u5408\u9002\u7684\u53f6\u5b50\u8282\u70b9. B\u6811\u4e2d\u53f6\u5b50\u8282\u70b9\u90fd\u5728\u540c\u4e00\u5c42\nNode* findSuiteLeafNode(Node* T,int data){\n    if(T->childNum==0){\n        return T;\n    }else{\n        int index=findSuiteIndex(T,data);\n        return findSuiteLeafNode(T->children[index-1],data);\/\/index-1:0\u5230m-1\n    }\n}\n\n\n\/\/\u6dfb\u52a0\u6570\u636e\nvoid addData(Node* node,int data,Node** T){\n    int index=findSuiteIndex(node,data);\n    \/\/\u4e3a\u65b0\u6570\u636e\u632a\u4f4d\u7f6e\n    for(int i=node->keyNum;i>=index;i--){\n        node->keys[i+1]=node->keys[i];\n    }\n    \/\/\u586b\u5165\u65b0\u6570\u636e\n    node->keys[index]=data;\n    node->keyNum++;\n    \/\/\u5173\u952e\u5b57\u8d85\u51fa\u4e0a\u9650,x>m-1\n    \/\/\u8fdb\u884c\u5206\u88c2\n    if(node->keyNum==node->level){\n        \/**\n         * 1.\u5206\u88c2\u51fa\u4e24\u8fb9\u5b50\u8282\u70b9\n         *\/\n        \/\/\u627e\u51famid\u5173\u952e\u5b57\u4f4d\u7f6e\n        int mid=node->level\/2+node->level%2;\n        \/\/\u65b0\u5efa\u4e00\u4e2a\u5de6\u5b69\u5b50\u8282\u70b9,\u521d\u59cb\u5316\n        Node* lchild=initNode(node->level);\n        \/\/\u65b0\u5efa\u4e00\u4e2a\u53f3\u5b69\u5b50\u8282\u70b9,\u521d\u59cb\u5316\n        Node* rchild=initNode(node->level);\n        \n        \/\/\u7ed9mid\u5de6\u8fb9\u5b69\u5b50\u8282\u70b9\u8d4b\u503c\n        for(int i=1;i<mid;i++){\n            addData(lchild,node->keys[i],T);\n        }\n        \/\/\u7ed9mid\u53f3\u8fb9\u5b69\u5b50\u8282\u70b9\u8d4b\u503c\n        for(int i=mid+1;i<=node->keyNum;i++){\n            addData(rchild,node->keys[i],T);\n        }\n\n        \/\/\u628amid\u5de6\u8fb9\u7684\u5b69\u5b50\u4ea4\u7ed9\u5de6\u5b69\u5b50\n        for (int i = 0; i < mid; i++) {\n            lchild -> children[i] = node -> children[i];\n            if (node -> children[i] != NULL) {\n                node -> children[i] -> parent = lchild;\n                lchild -> childNum ++;\n            }\n        }\n\n        \/\/\u628amid\u53f3\u8fb9\u7684\u5b69\u5b50\u4ea4\u7ed9\u53f3\u5b69\u5b50'\n        for(int i=mid;i<node->childNum;i++){\n            rchild->children[i-mid]=node->children[i];\n            if(node->children[i]!=NULL){\n                node->children[i]->parent=rchild;\n                rchild->childNum++;\n            }\n        }\n        \/**\n         * 2.\u628a\u4e2d\u95f4\u5173\u952e\u5b57\u9876\u4e0a\u53bb\u5f53\u65b0\u7239,\u4e3a\u4e24\u8fb9\u5b50\u8282\u70b9\u8bbe\u7f6e\u65b0\u7239,\u5f03\u7528\u5f53\u524d\u8282\u70b9\n         *\/\n        \/\/\u5982\u679c\u5f53\u524d\u8282\u70b9\u662f\u5426\u662f\u6839\u8282\u70b9\n        if(node->parent==NULL){\n            \/\/\u82e5\u662f\u6839\u8282\u70b9\u5219\u5efa\u7acb\u65b0\u7239,\u4ee4\u65b0\u7239\u6210\u4e3a\u65b0\u7684\u6839\u8282\u70b9\n            Node* newParent=initNode(node->level);\n            addData(newParent,node->keys[mid],T);\n            newParent->children[0]=lchild;\n            newParent->children[1]=rchild;\n            lchild->parent=newParent;\n            rchild->parent=newParent;\n            newParent->childNum=2;\n            *T=newParent;\n        }else{\n            \/\/\u82e5\u4e0d\u662f\u6839\u8282\u70b9,mid\u4f1a\u8fdb\u5165\u7239\u8282\u70b9\u6210\u4e3a\u65b0\u7239,\u9700\u8981\u7ef4\u62a4\u7239\u8282\u70b9\n            int index=findSuiteIndex(node->parent,node->keys[mid]);\n            lchild->parent=node->parent;\n            rchild->parent=node->parent;\n            node->parent->children[index-1]=lchild;\n            if(node->parent->children[index]!=NULL){\n                for(int i=node->parent->childNum-1;i>=index;i--){\/\/\u5b69\u5b50\u6307\u9488\u6570\u7ec4\u632a\u4f4d\u7f6e\n                    node->parent->children[i+1]=node->parent->children[i];\n                }\n            }\n            node->parent->children[index]=rchild;\n            node->parent->childNum++;\n            addData(node->parent,node->keys[mid],T);\n        }\n        free(node);\/\/\u5f03\u7528\u5f53\u524d\u8282\u70b9\n    }\n}\n\n\/\/B\u6570\u7684\u63d2\u5165\u64cd\u4f5c\u90fd\u5728\u53f6\u5b50\u8282\u70b9\u5b8c\u6210\n\/\/\u627e\u5230\u5408\u9002\u7684\u53f6\u5b50\u8282\u70b9,\u628a\u5173\u952e\u5b57\u63d2\u5165\u8be5\u8282\u70b9\nvoid insert(Node** T, int data) {\n    Node* node = findSuiteLeafNode(*T, data);\n    addData(node, data, T);\n}\n\nvoid printTree(Node* T){\n    if(T!=NULL){\n        for(int i=1;i<=T->keyNum;i++){\n            printf(\"%d \",T->keys[i]);\n        }\n        printf(\"\\n\");\n        for(int i=0;i<T->childNum;i++){\n            printTree(T->children[i]);\n        }\n    }\n}\n\nNode* find(Node* node,int data){\n    if(node==NULL){\n        return NULL;\n    }\n    int i;\n    for(i=1;i<=node->keyNum;i++){\n        if(node->keys[i]==data) return node;\n        if(data<node->keys[i]) break;\/\/\u9047\u5230\u4e00\u4e2a\u6bd4\u81ea\u5df1\u5927\u7684\u5173\u952e\u5b57\u5c31\u9000\u51fa,\u786e\u8ba4\u4e0b\u964d\u65b9\u5411\n    }\n    if(node->childNum==0) return NULL; \/\/\u627e\u5230\u53f6\u5b50\u8282\u70b9\u90fd\u6ca1\u627e\u5230,\n    return find(node->children[i-1],data);\n}\n\nint main(){\n    clock_t start, end;\n    start = clock();   \/\/ \u8bb0\u5f55\u5f00\u59cb\u65f6\u95f4\n    Node* T = initNode(5);\n    insert(&T, 1);\n    insert(&T, 2);\n    insert(&T, 6);\n    insert(&T, 7);\n    insert(&T, 11);\n    insert(&T, 4);\n    insert(&T, 8);\n    insert(&T, 13);\n    insert(&T, 10);\n    insert(&T, 5);\n    insert(&T, 17);\n    insert(&T, 9);\n    insert(&T, 16);\n    insert(&T, 20);\n    insert(&T, 3);\n    insert(&T, 12);\n    insert(&T, 14);\n    insert(&T, 18);\n    insert(&T, 19);\n    insert(&T, 15);\n    printTree(T);\n    Node* node=find(T,7);\n    for(int i=1;i<=node->keyNum;i++){\n        printf(\"%d \",node->keys[i]);\n    }\n    printf(\"\\n\");\n    end = clock();     \/\/ \u8bb0\u5f55\u7ed3\u675f\u65f6\u95f4\n    double time_used = (double)(end - start) \/ CLOCKS_PER_SEC;\n    printf(\"running time:%f second\\n\", time_used);\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u5916\u90e8\u6392\u5e8f\uff1a \u603b\u65f6\u95f4=I\/O\u65f6\u95f4+\u5185\u90e8\u6392\u5e8f\u65f6\u95f4+\u5185\u90e8\u5f52\u5e76\u65f6\u95f4 \u4f18\u5316\u601d\u8def\uff0c\u51cf\u5c11i\/o\u6b21\u6570: 1.\u589e\u5927k\uff0c\u964d\u4f4e\u6811\u9ad8\uff0c […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[5],"class_list":["post-234","post","type-post","status-publish","format-standard","hentry","category-6","tag-5"],"_links":{"self":[{"href":"https:\/\/www.fishh.top\/index.php?rest_route=\/wp\/v2\/posts\/234","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.fishh.top\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.fishh.top\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.fishh.top\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.fishh.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=234"}],"version-history":[{"count":1,"href":"https:\/\/www.fishh.top\/index.php?rest_route=\/wp\/v2\/posts\/234\/revisions"}],"predecessor-version":[{"id":251,"href":"https:\/\/www.fishh.top\/index.php?rest_route=\/wp\/v2\/posts\/234\/revisions\/251"}],"wp:attachment":[{"href":"https:\/\/www.fishh.top\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=234"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.fishh.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=234"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.fishh.top\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=234"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}