데이터 구조 연구 코드 총화 [기본 보완]

Note： 본 고 는 후기 에 자신 이 복습 하고 편리 하 게 기록 하 는 데 목적 을 둔다.일부 코드 는 실행 가능 한 줄 을 보장 하지 않 습 니 다. 문제 가 있 으 면 지적 해 주 십시오.
글 목록

1. 선형 표

1.1 선형 표 사슬 식 저장 소

1.2 선형 표 의 순서 저장

1.3 순차 스 택

1.4 체인 팀

1.5 순환 대기 열

1.6 KMP and BF

2 나무

2.1 나무의 저장 구조

2.1.1 순차 저장

2.1.2 체인 구조

2.2 각종 옮 겨 다 니 기

2.2.1 전 중 후 + 차원

2.2.2 전 중 후 비 재 귀

2.3 중 순차 단서 화 이 진 트 리

2.4 병 검사 집

3 그림

3.1 그림 의 저장 구조

3.1.1 인접 표

3.1.2 십자 링크

3.1.3 인접 다 중 표

3.2 그림 의 옮 겨 다 니 기

3.2.1 깊이 우선 dfs

3.3 topo 정렬

3.4 더 블 연결 분량

3.4.1 점 더 블 연결 분량 BCC

3.4.2 변 쌍 연통 분량 EBC

3.5 강 연통 분량 SCC

3.6 최소 생 성 트 리 krus

3.7 최 단 로 djk

6 찾기

6.1 절반 할인 찾기

6.3 열의 패턴 일치

6.4 KMP

6.5 산 목록 지퍼 법

6.6 BST 이 진 트 리

6.7 AVL 밸 런 스 이 진 트 리

6.8 키 트 리 (사전 트 리)

7 정렬

7.2 정렬 삽입

7.2.1 간단하게 정렬 삽입

7.2.2 반 으로 접 고 정렬 삽입

7.2.3 힐 정렬

7.3 교환 정렬

7.3.1 거품 정렬

7.3.2 빠 른 정렬

7.4 정렬 선택

7.4.1 간단하게 정렬 선택

7.4.2 더미 정렬

7.4 병합 정렬

1. 선형 표
1.1 선형 표 사슬 식 저장 소

#include 
#include 

typedef char ElemType;

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode, *LinkList;

//           

bool InitList(LinkList& L){
    if(!(L = (LinkNode* )malloc(sizeof(LinkNode)))) { //      
        printf("it is not enough space.
");
        return false;
    }
    L->next = NULL;
    return true;
}
bool DestroyList(LinkList& L){
    free(L);
}
bool ClearList(LinkList& L){
    L->next = NULL;
}
bool ListEmpty(LinkList L){
    return (L->next == NULL) ? true : false;
}
int ListLength(LinkList L){
    int length = 0;
    LinkNode *p = L->next;
    while(p){ 
        length++; p = p->next;
    }
    
    return length;
}

bool GetElem(LinkList L, int i, ElemType &e){
    if(i < 1 || i > ListLength(L)) return false;
    int cnt = 1;
    LinkNode *p = L->next;
    while(p){
        if(cnt == i) {
            e = p->data;
            return true;
        }
        p = p->next;
        cnt++;
    }
}
bool Compare(ElemType a, ElemType b){
    if(a == b) return 0;
    if(a > b) return 1;
    else return -1;
}
 //               
int LocateElem(LinkList L, ElemType e, bool (*Compare)(ElemType, ElemType)){
    LinkNode *p = L->next;
    int pos = 1;
    while(p){
        if(!Compare(p->data, e))  
            return pos;
        ++pos;
        p = p->next;
    }
    return 0; // 0      
}
bool ListInsert(LinkList& L, int i, ElemType e){
    if(i < 1 || i > ListLength(L) + 1) return false;
    LinkNode *p = L->next, *fa = L;
    LinkNode *cur = (LinkNode *) malloc(sizeof(LinkNode));
    cur->data = e; cur->next = NULL;
    int pos = 1;
    while(p){
        if(pos == i)  break; 
        ++pos;
        p = p->next; fa = p->next;
    }

    fa->next = cur;
    cur->next = p;
}

bool LinkDelete(LinkList &L, int i){
    if(i < 1 || i > ListLength(L)) return false;
    LinkNode *p = L->next, *fa = L;
    int pos = 1;
    while(p){
        if(pos == i){
            fa->next = p->next;
            return true;
        }
        ++pos;
        p = p->next;
        fa = fa->next;
    }
}

bool LinkTraverse(LinkList L){
    L = L->next;
    while(L){
        printf("%c ", L->data);
        L = L->next;
    }
    puts(""); //   
}


// test ..
int main(){ 
   
    LinkList L;
    InitList(L);
    ElemType tmp = 'a';
    ListInsert(L, 1, 'a');
    LinkTraverse(L);
    tmp = 'c';
    ListInsert(L, 1, tmp);
    LinkTraverse(L);
    LinkDelete(L, 2);
    LinkTraverse(L);

    return 0;
}

1.2 선형 표 의 순서 저장

#include 
#include 

typedef char ElemType;
#define LIST_INIT_SIZE  100 //              
#define LISTINCRMENT 10  //             
typedef enum {OK, OVERFLOW, ERROR} Status;

typedef struct{
    ElemType  *elem;
    int length;    //       
    int listsize;  //          
}SqList;

Status InitList_Sq(SqList &L){
    L.elem = (ElemType *) malloc(sizeof(ElemType) * LIST_INIT_SIZE);
    if(!L.elem) return OVERFLOW;
    L.listsize = LIST_INIT_SIZE;
    L.length = 0;
    return OK;
}

Status ListInsert_Sq(SqList &L,int i, ElemType e){
    if(i < 1 || i > L.length + 1) return ERROR;
    if(L.length >= L.listsize) { //     ，    
        ElemType *base = (ElemType *) realloc(L.elem, (L.listsize + LISTINCRMENT) * sizeof(ElemType));
        if(!base) exit(OVERFLOW);
        L.elem = base;
        L.listsize += LISTINCRMENT;
    }
    ElemType *q = &(L.elem[i - 1]);
    for(ElemType *p = &(L.elem[L.length - 1]); p >= q; p--) 
        *(p + 1) = *p;
    *q = e;
    ++L.length;
    return OK;
}   

Status ListDelete_Sq(SqList &L, int i){
    if(i < 1 || i > L.length) return ERROR;
    ElemType *p, *q;
    q = &(L.elem[L.length - 1]);
    for(p = &(L.elem[i - 1]); p < q; ++p) 
        *p = *(p + 1);
    --L.length;
    return OK;
}

void Traverse(SqList L){
    for(int i = 0; i < L.length; i++){
        printf("%c ", L.elem[i]);
    }
    puts("");
}
int main(){
    SqList L;
    InitList_Sq(L);
    ElemType e = 'a';
    ListInsert_Sq(L, 1, e);
    e = 'c';
    ListInsert_Sq(L, 1, e);
    Traverse(L);
    ListDelete_Sq(L, 2);
    Traverse(L);
    return 0;
} 

1.3 순차 스 택

#include 
#include 

typedef enum{OK, ERROR, OVERFLOW}Status;
#define STACK_INIT_SIZE 100    //       
#define STACKINCREMENT  10     //        
typedef char ElemType;

typedef struct{
    ElemType *base;
    ElemType *top;
    int stacksize;
}SeqStack;

Status InitStack(SeqStack &S){
    S.base = (ElemType *)malloc(sizeof(ElemType) * STACK_INIT_SIZE);
    if(!S.base) exit(OVERFLOW  );
    S.top = S.base;
    S.stacksize = STACK_INIT_SIZE;
    return OK;
}
Status GetTop(SeqStack S, ElemType &e){
    if(S.top == S.base) return ERROR;
    e = *(S.top - 1);
    return OK;  
}
Status Push(SeqStack &S, ElemType e){
    if(S.top - S.base >= S.stacksize) {//       
        ElemType *base = (ElemType*) realloc(S.base, 
            (S.stacksize + STACKINCREMENT) * (ElemType));
        if(!base) exit(OVERFLOW);
        S.top = S.base + S.stacksize;
        S.stacksize += STACKINCREMENT;
    }
    *S.top++ = e;
    return OK;
}
bool StackEmpty(SeqStack S){
    return S.top == S.base;
}
void StackClear(SeqStack &S){
    S.top = S.base;
}
Status Pop(SeqStack &S, ElemType &e){
    if(S.top == S.base) return ERROR;
    e = *--S.top;
    return OK;
}


// TEST
int main(){
    SeqStack S;
    InitStack(S);
    ElemType c = 'c';
    Push(S, c);

    Push(S, c);
    c = 'a';
    Push(S, c);
    while(!StackEmpty(S)) {
        ElemType t;
        GetTop(S, t);
        printf("%c ", t);
        Pop(S, t);
    }

    return 0;
} 

1.4 체인 팀

#include 
#include 

typedef char ElemType;
typedef struct QNode{
    ElemType data;
    struct QNode *next;
}QNode, *QueuePtr;
typedef struct {
    QueuePtr front, rear;
}LinkQueue;

typedef enum{OK, ERROR, OVERFLOW} Status;

Status InitQueue(LinkQueue &Q){
    Q.front = Q.rear = (QNode*) malloc (sizeof(QNode));
    if(!Q.front)exit(OVERFLOW);
    return OK;    
}
bool QueueEmpty(LinkQueue Q){
    return Q.front == Q.rear;
}
Status DestroyQueue(LinkQueue &Q){
    ElemType *p;
    while(!QueueEmpty(Q)){
        
    }
}
Status EnQueue(LinkQueue &Q, ElemType e){
    QNode *p = (QNode*) malloc(sizeof(QNode));
    if(!p) exit(OVERFLOW);
    p->data = e; p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
    return OK;
}

Status DeQueue(LinkQueue &Q, ElemType &e){
    if(Q.front == Q.rear) return ERROR;
    QNode *p;
    p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if(p == Q.rear) Q.rear = Q.front;
    free(p);
    return OK;
}
Status GetHead(LinkQueue Q, ElemType &e){
    if(Q.front == Q.rear) return ERROR;
    e = Q.front->next->data;
    return OK;
}


int main(){


    return 0;
}

1.5 순환 대기 열

#include 
#include 

typedef char ElemType;
typedef enum{OK, ERROR, OVERFLOW} Status;

#define MAXQSIZE 1000
typedef struct {
    ElemType *que;
    int front, rear;
} SeqQueue;   //                   

Status InitQueue(SeqQueue &Q){
    Q.que = (ElemType*) malloc (sizeof(ElemType) * MAXQSIZE);
    Q.front = Q.rear = 0;
}
Status ClearQueue(SeqQueue &Q){
    Q.front = Q.front = 0;
}

bool QueueEmpty(SeqQueue Q){
    return Q.front == Q.rear; 
}
Status EnQueue(SeqQueue& Q, ElemType e){
    if((Q.rear + 1) % MAXQSIZE == Q.front) return ERROR;
    Q.que[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXQSIZE;
    return OK;
}
Status DeQueue(SeqQueue&Q, ElemType &e){
    if(Q.rear == Q.front) return ERROR;
    e = Q.que[Q.front];
    Q.front = (Q.front + 1) % MAXQSIZE;
    return OK;
}
int QueueLength(SeqQueue Q){
    return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}

int main(){


    return 0;
}

#include 
#include 

typedef char ElemType;
typedef enum{OK, ERROR, OVERFLOW} Status;

#define MAXQSIZE 1000
typedef struct {
    ElemType *que;
    int front, rear;
    bool flag; //   flag       
} SeqQueue;
/*
    if front == rear 
        if flag == 1   
        if flag == 0   
         
    */
Status InitQueue(SeqQueue &Q){
    Q.que = (ElemType*) malloc (sizeof(ElemType) * MAXQSIZE);
    Q.front = Q.rear = 0;
    Q.flag = 1;
}
Status ClearQueue(SeqQueue &Q){
    Q.front = Q.front = 0;
    Q.flag = 1;
}

bool QueueEmpty(SeqQueue Q){
    return (Q.front == Q.rear) && Q.flag; 
}
Status EnQueue(SeqQueue& Q, ElemType e){
    if((Q.front == Q.rear) && !Q.flag) return ERROR;
    Q.que[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXQSIZE;
    Q.flag = 0; 
    return OK;
}
Status DeQueue(SeqQueue&Q, ElemType &e){
    if((Q.rear == Q.front) && Q.flag) return ERROR;
    e = Q.que[Q.front];
    Q.front = (Q.front + 1) % MAXQSIZE;
    Q.flag = 1;
    return OK;
}
int QueueLength(SeqQueue Q){
    return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}

int main(){


    return 0;
}

1.6 KMP and BF

#include 
#include 

bool BF(char *s, char *t){
    int i, j, k;
    i = 0, j = 0;
    int lens = strlen(s), lent = strlen(t);
    while(i < lens){
        while(i < lens && j < lent && s[i] == t[j]) ++i, ++j;
        if(j >= lent) return true;
        j = 0; i = i - j + 1;
    }
}


const int N = 1000; //         

int next[N];
void getnext(char *s, int len){
    next[0] = -1;
    int i, j;
    i = 0; j = -1;
    while(i < len){
        if(j == -1 || s[i] == s[j] )
            next[++i] = ++j;
        else 
            j = next[j];
    }
}
bool Kmp(char *s, char *t){
    int lens = strlen(s), lent = strlen(t);

    getnext(t, lent);
    int i, j;
    i = j = 0; 
    while(i < lens){
        if(j == -1 || s[i] == t[j]) {
            ++i, ++j;
            if(j >= lent) return true;
        }            
        else 
            j = next[j];
    }
}

int main(){


    return 0;
}

나무
2.1 나무의 저장 구조
2.1.1 순차 저장 소

#include 
#include 


#define MAX_TREE_SIZE 100
typedef char ElemType; 
typedef ElemType SqBiTree[MAX_TREE_SIZE];

//               
//     ：                ，        (LCA)

ElemType solve(SqBiTree T, int a, int b){
    while(a != b){
        if(a > b) b /= 2;
        else a /= 2;
    }
    return T[a];
}


int main(){


    return 0;
}

2.1.2 체인 구조

#include 
#include 


#define MAX_TREE_SIZE 100
typedef char ElemType; 
typedef struct BNode{
    ElemType data;
    struct BNode *lchild;
    struct BNode *rchild;
}BNode, *BiTree;

void Inorder(BiTree T){
    if(T == NULL) return ;
    Inorder(T->lchild);
    // visit(T->data);
    printf("%c ", T->data);
    Inorder(T->rchild);
}
void preorder(BiTree T){
    if(T == NULL) return ;
    // visit(T->data);
    printf("%c ", T->data);
    
    Inorder(T->lchild);
    Inorder(T->rchild);
}

void postorder(BiTree T){
    if(T == NULL) return ;
    Inorder(T->lchild);
    Inorder(T->rchild);
    // visit(T->data);
    printf("%c ", T->data);
}

#define MAX 200
void leverorder(BiTree T){
    BiTree queue[MAX]; 
    int front , rear;
    front = rear = 0;
    queue[rear++] = T;
    while(front < rear){
        BiTree p = queue[front++];
        printf("%c ", p->data);
        if(p->lchild) queue[rear++] = p->lchild;
        if(p->rchild) queue[rear++] = p->rchild;
    }   
}

int main(){


    return 0;
}

2.2 여러 가지
2.2.1 앞 뒤 + 차원

#include 
#include 


#define MAX_TREE_SIZE 100
typedef char ElemType; 
typedef struct BNode{
    ElemType data;
    struct BNode *lchild;
    struct BNode *rchild;
}BNode, *BiTree;

void Inorder(BiTree T){
    if(T == NULL) return ;
    Inorder(T->lchild);
    // visit(T->data);
    printf("%c ", T->data);
    Inorder(T->rchild);
}
void preorder(BiTree T){
    if(T == NULL) return ;
    // visit(T->data);
    printf("%c ", T->data);
    
    Inorder(T->lchild);
    Inorder(T->rchild);
}

void postorder(BiTree T){
    if(T == NULL) return ;
    Inorder(T->lchild);
    Inorder(T->rchild);
    // visit(T->data);
    printf("%c ", T->data);
}

#define MAX 200
void leverorder(BiTree T){
    BiTree queue[MAX]; 
    int front , rear;
    front = rear = 0;
    queue[rear++] = T;
    while(front < rear){
        BiTree p = queue[front++];
        printf("%c ", p->data);
        if(p->lchild) queue[rear++] = p->lchild;
        if(p->rchild) queue[rear++] = p->rchild;
    }   
}

int main(){


    return 0;
}

2.2.2 전 중 후 비 재 귀

#include 
#include 
#define MAX_TREE_SIZE 100
typedef char ElemType; 
typedef struct BNode{
    ElemType data;
    struct BNode *lchild;
    struct BNode *rchild;
}BNode, *BiTree;

void inorder(BiTree T){
    InitStack(S);
    BNode *p = T;
    while(!StackEmpty(S) || p){
        if(!p) {
            Push(S, p);
            p = p->lchild;
        }else {
            Pop(S, p);
            printf("%c ", p->data);
            p = p->rchild;
        }
    }
}
void postorder(BiTree T){
    InitStack(S);
    BNode *p = T, *last = NULL;
    while(!StackEmpty(S) || p){
        if(p){
            Push(S, p);
            p = p->lchild;
        }
        else {
            GetTop(S, p);
            if(p->rchild && p == last){ //        
                Pop(S, p);
                printf("%c ", p->data);
                last = p;
                p = NULL;
            }else {
                p = p->rchild;
            }
        }
    }
}

int main(){
    

    return 0;
}

2.3 중간 순서 단서 화 이 진 트 리

#include 
#include 


#define MAX_TREE_SIZE 100
typedef char ElemType; 
typedef struct BNode{
    ElemType data;
    bool ltag, rtag;
    struct BNode *lchild;
    struct BNode *rchild;
}BNode, *BiTree;

void DFS(BiTree T, BiTree &pre){
    if(T == NULL) return ;
    T->ltag = T->rtag = 0;
    DFS(T->lchild, pre);
     
    if(!T->lchild) {
        T->ltag = 1;
        T->lchild = pre;
    }
    if(!pre->rchild) {
        pre->rtag = 1;
        pre->rchild = T;
    }
    pre = T;
    DFS(T->rchild, pre);
}

//            
void BinaryTree_Thread_Inorder(BiTree T){
    BiTree pre = NULL;
    DFS(T, pre);
    pre->rtag = 0;
    pre->rchild = NULL;
}

BiTree First(BiTree T){
    while(!T->ltag) {
        T = T->lchild;
    }
    return T;
}

BiTree Next(BiTree T){
    if(T->rtag) return T->rchild;
    else 
        First(T->rchild);
}
//         
void Traverse_Inorder_Thread(BiTree T){
    BiTree p;
    for(p = First(T); p; p = Next(p)) {
        printf("%c ", p->data);
    }
}

int main(){


    return 0;
}

2.4 병 검사 집

#include 
#include 
#include 

const int N = 1e5 + 11;

int pre[N];
void Init(int n){ // n      
    for(int i = 1; i <= n; i++){
        pre[i] = i; //            
    }
}

int Find(int x) { //     x      
    while(pre[x] != x) {
        x = pre[x];
    }
    return x;
}

void Join(int x,int y){ //  x   y     
    int fx = Find(x);
    int fy = Find(y);
    if(fx != fy){
        pre[fx] = fy;
    }
}
//         ，             ，       。
//            （               ），      

int Find_(int x ) { //           
    return (pre[x] == x) ? x : pre[x] = Find(pre[x]);
}
int main(){


    return 0;
}    

3 도
3.1 그림 의 저장 구조
3.1.1 인접 표

#include 
#include 

#define InfoType char   
#define VertexType char  //     
#define MAX_VERTEX_NUM 100 //       

typedef struct ArcNode{
    int adjvex; //     
    struct ArcNode *next;
    InfoType *info; //          
}ArcNode;

typedef struct VNode{
    VertexType data;
    ArcNode *firstarc;
}VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices;
    int vexnum, arcnum;  //            
    int kind;  //       
}ALGraph;

int main(){
    ALGraph G;
    int n, m; scanf("%d%d", &n, &m);
    ArcNode *arc;
    while(m--){   //   
        int a, b, c; 
        scanf("%d%d%d", &a, &b, &c);  // a --> b  weight c    
            arc = (ArcNode *) malloc(sizeof(ArcNode));
        arc->next = G.vertices[a].firstarc;   //    
        G.vertices[a].firstarc = arc;

            arc = (ArcNode *) malloc(sizeof(ArcNode));
        arc->next = G.vertices[b].firstarc;   //    
        G.vertices[b].firstarc = arc;
    }

    int u = 1;  //       u     v
    for(arc = G.vertices[u].firstarc; arc; arc = arc->next){
        int v = arc->adjvex;
            
    }

    return 0;
}

3.1.2 십자 형 링크

#include 
#include 
#include 
/*
                
                     

    */
#define MAX_VERTEX_NUM 100  //       

typedef char InfoType;
typedef int ElemType;
typedef struct ArcNode{
    int tailvex, headvex;           // tailvex -> headvex     
    struct ArcNode *tlink, *hlink;  //                
    InfoType *info;  //        
}ArcNode;
typedef struct VexNode{
    ElemType data;  //     
    ArcNode *firstin, *firstout; //                       
}VexNode;
typedef struct {
    VexNode xlist[MAX_VERTEX_NUM];
    int vexnum, arcnum;  
}OLGraph;


int main(){
    OLGraph olg;
    int n, m; scanf("%d%d", &n, &m);
    olg.arcnum = m; olg.vexnum = n;
    for(int i = 0; i <= olg.vexnum; i++){
        olg.xlist[i].firstin = olg.xlist[i].firstout = NULL;
    }

    for(int i = 0; i < m; i++){
        int a, b; // a->b     
        scanf("%d%d%d", &a, &b, &c);
        ArcNode *p = (ArcNode *) malloc(sizeof(ArcNode));
        *p = {a, b, olg.xlist[a].firstout, olg.xlist[b].firstin, NULL};  //        
            //{tailvex, headvex, tlink, hlink, info}         
        olg.xlist[a].firstout = olg.xlist[b].firstin = p;

    }
    return 0;
}

3.1.3 인접 다 중 표

#include 
#include 

/*
                

    */

typedef char ElemType;
#define MAX_VEX_NUM 10000
typedef struct ArcNode{
    int ivex, jvex;   
    struct ArcNode *ilink, *jlink;
    //              
}ArcNode;
typedef struct VNode{
    ElemType data; //     
    ArcNode *firstout;
}VNode;

typedef struct {
    VNode adjmulist[MAX_VEX_NUM];
    int vexnum, arcnum;
}AMLGraph;

int main(){
    AMLGraph G;
    int n, m; scanf("%d%d", &n, &m);
    G.vexnum = n; G.arcnum = m;
    for(int i = 0; i <= G.vexnum; i++){ //   
        G.adjmulist[i].firstout = NULL;
    }

    while(m--){
        int a, b; // a->b      
        scanf("%d%d", &a, &b);
        ArcNode *p = (ArcNode *) malloc (sizeof(ArcNode));
        *p = {a, b, G.adjmulist[a].firstout, G.adjmulist[b].firstout};
        G.adjmulist[a].firstout = G.adjmulist[b].firstout = p;
    }

    int u;  //       u     v 
    for(ArcNode *p = G.adjmulist[u].firstout; p; p = p->ilink) {
        int v = p->jvex;

    }
    
    return 0;

}

3.2 그림 의 옮 겨 다 니 기
3.2.1 깊이 우선 dfs

#include 
#include 
#include 

/*
      DFS  
             

    */
#define InfoType char   
#define VertexType char  //     
#define MAX_VERTEX_NUM 100 //       

typedef struct ArcNode{
    int adjvex; //     
    struct ArcNode *next;
    InfoType *info; //          
}ArcNode;

typedef struct VNode{
    VertexType data;
    ArcNode *firstarc;
}VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices;
    int vexnum, arcnum;  //            
    int kind;  //       
}ALGraph;


bool vis[MAX_VERTEX_NUM];
void DFS(ALGraph G, int u){
    printf("%d ", u);
    vis[u] = true;
    for(ArcNode *p = G.vertices[u].firstarc; p; p = p->next){
        int v = p->adjvex;
        if(!vis[v]){
            DFS(G, v);
        }
    }
}
int main(){
    ALGraph G;
    int n, m; scanf("%d%d", &n, &m);
    for(int i = 0; i <= n; i++){
        G.vertices[i].firstarc = NULL; //   
    }
    
    ArcNode *arc;
    while(m--){   //   
        int a, b, c; 
        scanf("%d%d%d", &a, &b, &c);  // a --> b  weight c    
        arc = (ArcNode *) malloc(sizeof(ArcNode));
        *arc = {b, G.vertices[a].firstarc, NULL};
        G.vertices[a].firstarc = arc;
    
        arc = (ArcNode *) malloc(sizeof(ArcNode));
        *arc = {a, G.vertices[b].firstarc, NULL};
        G.vertices[b].firstarc = arc;
    }
    //   DFS  
    memset(vis, false, sizeof(vis));   //     
    for(int i = 1; i <= n; i++){
        if(!vis[i])   //          ,                
            DFS(G, i);
    }
    return 0;
}

/*
input_sample :
5 3 
1 2 0
1 3 0
4 5 1


    */

3.3 topo 정렬

/*
    topo         
    1.          
    2.    topo      
    */
void Topo(G, in){  //  G      in
    int cnt = 0;  //          
    bool flag = true; // topo    
    Init(que);
    int cur = 0;
    for(int i = 0; i < G.vexcnt; i++){
        if(!in[i]) {
            print(i);  //     
            cnt++;
            cur ++;
            Enqueue(que, i);
        }
    }
    if(cur > 1) flag = 0;
    while(!IsEmpty(que)){
         Dequeue(que, v);
         cur = 0;
         for(w = FirstEdge(G, v); w; w = NextEdge(G, v, w)) {
             if(--in[w] == 0) {
                print(w);  //     
                cnt++;
                cur ++;
                Enqueue(que, w);
             }
         }
         if(cur > 1) flag = 0; 
    }

    if(cnt < G.vexcnt) puts("      !");  //               
    else if(!flag) puts("topo    "); //           0  ，  topo    
    else puts("topo   ");
}

3.4 더 블 연결 분량
3.4.1 점 더 블 연결 분량 BCC

#include 
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 1e5 + 11;
const int M = 1e6 + 11;
const int MOD = 1e9 + 7;

vector<int>G[N];
int dfn[N], low[N], clo;
int bcc_cnt, st[N], iscut[N], bccno[N];
void tarjan(int u, int fa){
    dfn[u] = low[u] = ++clo; st[++*st] = u;
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i];

        if(!dfn[v] && v != fa){
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u]) {
                ++bcc_cnt;
                iscut[u] = true;
                do{
                    bccno[st[*st]] = bcc_cnt;
                 }while(st[st[0]--] != u);

                 st[++*st] = u;  //        bcc ，        
            }
        }else 
            low[u] = min(low[u], dfn[v]);
    }
    if(fa == -1 && G[u].size() < 2) iscut[u] = false;
}
void bcc_cut(int n){
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(iscut, false, sizeof(iscut));
    memset(bccno, 0, sizeof(bccno));
    st[0] = bcc_cnt = clo = 0;
    for(int i = 1; i <= n; i++)
        if(!dfn[i])
            tarjan(i, -1);
}
int main(int argc, char **args){
    int n, m; scanf("%d%d", &n, &m);
    while(m--){
        int a, b; scanf("%d%d",&a, &b);
        G[a].push_back(b);
        G[b].push_back(a);
    }

    bcc_cut(n);
    
    for(int i = 1;i <= n;i ++){
        printf("%d %d %d
", i, iscut[i], bccno[i]);
    }
return 0;

}
/*
7 8 
1 2
1 3
1 4
1 6
1 7
4 5
3 5
6 7
    */

3.4.2 변 더 블 연결 분량 EBC

#include 
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 1e5 + 11;
const int M = 1e6 + 11;
const int MOD = 1e9 + 7;

vector<int>G[N];
int dfn[N], low[N], clo;
int ebc_cnt, ebcno[N];
int st[N];
void tarjan(int u,int fa){
    low[u] = dfn[u] = ++clo;  st[++*st] = u;
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i];
        if(!dfn[v] && v != fa){
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v] > dfn[u]){
                //      
            }
        }else 
            low[u] = min(low[u], dfn[v]);
    }
    if(dfn[u] == dfn[u]){
        ++ebc_cnt;
        do{
            ebcno[st[*st]] = ebc_cnt;
        }while(st[st[0]--] != u);
    }
}

void ebc(vector<int> G, int n ){
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    clo = ebc_cnt = 0;
    memset(ebcno, 0, sizeof(ebcno));
    for(int i = 1; i <= n; i++){
        if(!dfn[i])
            tarjan(i, -1);
    }
}
int main(int argc, char **args){

return 0;
}

3.5 강 연통 분량 SCC

#include 
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 1e5 + 11;
const int M = 1e6 + 11;
const int MOD = 1e9 + 7;

vector<int>ve[N];
bool instack[N];
int st[N];
int scc_cnt, sccno[N];
int clo, low[N], dfn[N];
void tarjan(int u){
    low[u] = dfn[u] = ++clo; st[++*st] = u; instack[u] = 1;
    for(int i = 0; i < ve[u].size(); i++){
        int v = ve[u][i];
        if(!dfn[v]){
            tarjan(v);
            if(low[u] > low[v]) low[u] = low[v];
        }else if(instack[v]) {
            if(low[u] > dfn[v]) low[u] = dfn[v];
        }
    }
    if(dfn[u] == low[u]) {  //     scc
        scc_cnt++;
        do{
            sccno[st[*st]] = scc_cnt;
        }while(st[st[0]--] != u);
    }
}

void scc_cut(int n){
    memset(instack, false, sizeof(bool) * (n + 1));
    memset(dfn, 0, sizeof(int) * (n + 1));    
    memset(low, 0, sizeof(int) * (n + 1));    
    memset(sccno, 0, sizeof(int) * (n + 1));
    st[0] = clo = scc_cnt = 0;

    for(int i = 1; i <= n; i++){
        if(!dfn[i])
            tarjan(i);
    }
}

int main(int argc, char **args){
   
return 0;
}

3.6 최소 생 성 트 리 krus

#include  
using namespace std;

struct  Edge {
    int from,to,val;
}edge[MAXN];
bool  cmp(Edge  a,Edge b){
    return a.val<b.val;
}
int par[MAXN];
int n,m,k;

int Find(int x){  //    x       （         ）
    return x==par[x] ? x : par[x]=Find(par[x]);
}  

void join(int a,int  b){
    a=Find(a);
    b=Find(b);
    if(a!=b) par[a]=b;
}
 
void krus(){
    int  sum=0;
    sort(edge,edge+m,cmp);  //   

    for(int i=0;i<m;i++){ 
        Edge  e=edge[i];
        if(Find(e.from)!=Find(e.to)) {  //                  ，              ，      。 
            sum+=e.val;
            join(e.from,e.to);  //         
        }
    }
 
    printf("%d
",sum); //     
}
int  main(){

    scanf("%d%d%d",&n,&m); // n   ，m  
    int a,b,c;
    for(int i=0;i<m;i++)
        scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].val);

    //        
    for(int i=0;i<=n;i++)
        par[i]=i;
     
    krus();
    return 0;
}

3.7 최 단 로 djk

 dijkstra
 #include  
#include  
#define INF 0x3f3f3f  
#define max 100+10  

int dist[max],map[max][max],pre[max],visit[max];  
int n,m;  

void dijkstra()  
{  
    int i,j,start=1;  
    int next;   
    int mindist;//         
    memset(visit,0,sizeof(visit));//      
    for(i=1;i<=n;i++)  
    {  
        dist[i]=map[start][i];  
    }  
    visit[1]=1;  
    for(i=2;i<=n;i++)  
    {  
        mindist=INF;  
        for(j=1;j<=n;j++)  
        {  
            if(visit[j]==0&&mindist>dist[j])  
            {  
                mindist=dist[j];  
                next=j;  
            }  
        }  
        visit[next]=1;  
        for(j=1;j<=n;j++)  
        {  
            if(visit[j]==0&&dist[next]+map[next][j]<dist[j])  
            {  
                dist[j]=dist[next]+map[next][j];  
            }  
        }  
    }  
    printf("%d
",dist[n]);  
}   
int main()  
{  
    int i,j;  
    int x,y,c;  
    while(scanf("%d%d",&n,&m)&&(n!=0||m!=0))  
    {  
        for(i=1;i<=n;i++)  
        {  
            for(j=1;j<=n;j++)  
            {  
                if(i==j)  
                    map[i][j]=0;//        
                else  
                     map[i][j]=INF;  
            }  
        }  

        while(m--)  
        {  
            scanf("%d%d%d",&x,&y,&c);  
            if(map[x][y]>c)//                     
            {  
                map[x][y]=map[y][x]=c;  
            }  
        }  
        dijkstra();  
    }  
    return 0;  
}    

찾다
6.1 절반 으로 찾기

int binary_search(int A[], int n, int key){ // 0 ~ n-1 
	int low, high, mid;
	low = 0, high = n - 1;
	while(low <= high){
		mid = (low + high) / 2;
		if(A[mid] == key) return mid;
		else if(A[mid] > key) high = mid - 1;
		else low = mid + 1;
	}
	return -1; //     
} 

6.3 열의 패턴 일치

int Index(String S,String T, int pos){ // A pos     T   
	int i = pos, j = 1;
	while(i <= S.length && j <= T.length){
		if(S.ch[i] == T.ch[j]) {
			++i; ++j;
		}else {
			i = i - j + 2; j = 1;
		}
	} 
	if(j > T.length) return i - T.length;
	else return 0;
}

6.4 KMP

 
void getnxt(char *s, int *nxt){
    int i, j;
    j = nxt[0] = -1;
    i = 0; int n = strlen(s);
    while(i < n){
        while(j != -1 && s[i] != s[j]) j = nxt[j];
        ++j; ++i;
        if(s[j] == s[i]) nxt[i] = nxt[j];
        else nxt[i] = j;
    }
}

int kmp(char *s, char *t){
	int n = strlen(s), m = strlen(t);
	getnxt(t, next);
	int i = 0, j = -1;
	while(i < n){
		if(j == -1 || s[i] == t[j]) {
			++i; ++j;
			if(j == m - 1) return i - m + 1; //   t 
		}else 
			j = next[j]; 
	} 
	return -1;
}

6.5 산 목록 지퍼 법

#include 
#include 

/*
           
    
                    (eg：c++  map, python    )
    
    */
typedef int ElemType;
#define MAX_KEYS  11000   //         
typedef struct ArcNode{
    ElemType value;
    int key;
    struct ArcNode * next;
}ArcNode;


ArcNode *HashTable[MAX_KEYS];

bool search(int key, ElemType &values){
    ArcNode *p = HashTable[key % MAX_KEYS];
    while(p) {
        if(p->key == key) break;
         p = p->next;
    }
    if(p) values = p->value;
    return p != NULL;
}

bool Insert(int key, ElemType values){
    ElemType e;
    if(search(key, e)) return false; //     ，    
    ArcNode *p = (ArcNode*) malloc (sizeof(ArcNode));
    *p = {values, key, HashTable[key % MAX_KEYS]};
    HashTable[key % MAX_KEYS] = p;
}

//           ，          (           ，        ) 
bool Del(int key){
    ElemType e; 
    if(!search(key, e)) return false; //     ，    
    ArcNode *p = HashTable[key % MAX_KEYS];
    if(p->key == key) HashTable[key % MAX_KEYS] = p->next; //              ，  
    else{ //      ，       （           ，      
        ArcNode *fa = p; p = p->next; 
        while(p && p->key != key) {
            p = p->next;
            fa = fa->next;
        }
        fa->next = p->next;
    }
    return true;
}

int main(){
    for(int i = 0; i < MAX_KEYS;i++) HashTable[i] = NULL;
    
     int op; scanf("%d", &op); //      
    while(op--){
        int kind;
        scanf("%d", &kind);
        if(kind == 1) { //      
            int key;
            ElemType value = 21;
            // scanf("%d %1s", &key, &value);
            scanf("%d %d", &key, &value);
            // printf("insert : %d %c
", key, value);
            Insert(key, value);

        }else if(kind == 2){//      
            int key; scanf("%d", &key);
            Del(key);         
        }else {
            int key; scanf("%d", &key);
            ElemType value;
            if(search(key, value))
                printf("%d
", value);
        }
    }
    return 0;
}
/*
6
1 2 1111
1 3 22222
3 2 
1111
3 3
22222
2 2
3 2
    */

6.6 BST 이 진 트 리

#include 
#include 
/*
    BST （     ）
                       ，    
           ，        ，      AVL，    
         (       ，     ，   、   、     
    ，              )
    */
typedef char ElemType;
typedef struct BNode{
    ElemType data;
    BNode *lchild, *rchild;
}BNode, *BSTree;

BSTree Insert(BSTree T, ElemType e){
    if(!T) {
        T = (BNode*) malloc (sizeof(BNode));
        *T = {e, NULL, NULL};
        return T;
    }
    if(e < T->data) 
        T->lchild = Insert(T->lchild, e);
    else if(e >T->data) 
        T->rchild = Insert(T->rchild, e);
    else {
        //    
    }
}
bool reseach(BSTree T, ElemType e){
    if(!T) return false;
    if(e <T->data ) 
        return reseach(T->lchild, e );
    else if(e >T->data)
        return reseach(T->rchild, e);
    else 
        return true;
}
BSTree Delete(BSTree T, ElemType e){
    if(!T){
        //         
        return NULL;
    }
    if(e < T->data) 
        T->lchild = Delete(T->lchild, e);
    else if(e > T->data)
        T->rchild = Delete(T->rchild, e);
    else {
        if(!T->lchild && !T->rchild)  //     
            return NULL;
        else if(!T->lchild)  //      
            return T->rchild;
        else if(!T->rchild)  //      
            return T->lchild;
        else {  //       

            BNode*p = T->lchild; //    
            while(p->rchild) p = p->rchild;
            T->data = p->data; //       ，       

            return Delete(T->lchild, e); //            
        }
    }
}

int main(){
       
    return 0;
}

6.7 AVL 밸 런 스 이 진 트 리

#include 
#include 
#include 
#include 
using namespace std;

typedef int ElemType;
typedef struct BNode{
    ElemType data;
    struct BNode *lchild, *rchild;
}BNode, *AVLTree;

int getH(BNode *root){
    if(root == NULL) return 0;
    return max(getH(root->lchild), getH(root->rchild)) + 1;
}
BNode *RR(BNode *root){
    BNode * t = root->rchild;
    root->rchild = t->lchild;
    t->lchild = root;
    return t;
}
BNode *LL(BNode *root){
    BNode *t = root->lchild;
    root->lchild = t->rchild;
    t->rchild = root;
    return t;
}
BNode *LR(BNode *root){
    root->lchild = RR(root->lchild);
    return LL(root);
}
BNode *RL(BNode *root){
    root->rchild = LL(root->rchild);
    return RR(root);
}

BNode *Insert(BNode *root,ElemType e){
    if(root == NULL){
        root = (BNode*) malloc(sizeof(BNode));
        root->lchild = root->rchild = NULL;
        root->data = e;
    }else if(e < root->data){
        root->lchild = Insert(root->lchild, e);
        if((getH(root->lchild) - getH(root->rchild) )== 2) {
            if(e < root->lchild->data)   
                root = LL(root);
            else 
                root = LR(root);
        }
    }else {
        root->rchild = Insert(root->rchild, e);
        if((getH(root->rchild) - getH(root->lchild) )== 2){
            if(e < root->rchild->data)
                root = RL(root);
            else 
                root = RR(root);
        }
    }
    return root;
}
bool Search(AVLTree T, ElemType e){
    if(T == NULL) return false;
    if(e < T->data) 
        return Search(T->lchild, e);
    else if(e >T->data) Search(T->rchild, e);
    else 
        return true;
}
BNode *Delte(AVLTree T, ElemType e){
    if(T == NULL){
        exit(0);
    }
    if(e < T->data){
        T->lchild = Delte(T->lchild, e);
        if(getH(T->rchild) - getH(T->lchild) == 2) {
            BNode *t = T->rchild;
            if(getH(t->rchild) >= getH(t->lchild)) 
                T = RR(T);
            else 
                T = RL(T);
        }
    }else if(e > T->data){
        T->rchild = Delte(T->rchild, e);
        if(getH(T->lchild) - getH(T->rchild) == 2){
            BNode *t = T->lchild;
            if(getH(t->lchild) >= getH(t->rchild)) 
                T = LL(T);
            else 
                T = LR(T);
        }
    }else {
        if(T->lchild == NULL && T->rchild == NULL){
            free(T);
            return NULL;
        }else if(T->lchild == NULL) {
            free(T);
            return T->rchild;
        }else if(T->rchild == NULL) {
            free(T);
            return T->lchild;
        }else {
            BNode *p = T->lchild;
            while(p->rchild) p = p->rchild; //     
            swap(T->data,p->data);  //        ,       ，             
            T->lchild = Delte(T->lchild, e); 
        }
    }
    return T;
}

int main(){
    AVLTree avl = NULL;
    int n; scanf("%d", &n);
    int t;
    for(int i = 0; i < n; i++){
        scanf("%d", &t);
        avl = Insert(avl, t);
    }
    printf("%d
", avl->data);
    int q ; scanf("%d", &q);
    while(q--){
        scanf("%d", &t);
        avl = Delte(avl, t);
        printf("%d
", avl->data);
    }
    
    return 0;   
}

/*
5
5 4 3 2 1 
4
4 1 2 3 

*/

6.8 키 트 리 (사전 트 리)

#include 
#include 
#include 

/*
      （   ）
    
    */

#define MAX 26
typedef struct TNode{
    char ch;  //     
    bool end; //           
    int count; //               
    TNode *son[MAX]; //     MAX    
}TNode, *Trie;

bool research(Trie T, char *s){
    int pos = 0; int len = strlen(s);
    TNode * p = T;
    while(p && pos < len) 
        p = p->son[s[pos++] - 'a']; 
    
    return pos == len;
}

void IninNode(Trie &T){
    T = (Trie) malloc(sizeof(TNode));
    for(int i = 0; i < MAX; i++){
        T->son[i] = NULL;
    }
    T->count = 0;
    T->end = false;
}
void Insert(Trie &T, char *s){
    if(!T){  //       
        IninNode(T);
        T->count = 1;
    }
    
    Trie p = T; int pos = 0; int len = strlen(s);
    while(p && pos < len){
        p = p->son[s[pos++] - 'a'];
        if(!p){  //       
            IninNode(p);
        }
        p->count++;
    } 
    p->end = true;
}
bool Del(Trie T, char *s){
    if(!research(T, s)) return false;

    int pos = 0; int len = strlen(s);
    TNode * p = T, *q;
    while(p && pos < len) {
        if(!p->count) q = p;
        p = p->son[s[pos++] - 'a']; 
        p->count --; 
        free(q);
    }
    return pos == len;
}

int main(){
    

    return 0;
}

7 정렬
7.2 정렬 삽입
7.2.1 단순 삽입 정렬

void InsertSort(int A[], int n){ // 1 ~ n
	for(int i = 2; i <= n; i++){
		if(A[i] < A[i - 1])
			A[0] = A[i];  //               。 
			for(int j = i - 1; A[j] > A[0]; j--){
				A[j + 1] = A[j];
			A[j + 1] = A[0];
		}
		
	}
} 

7.2.2 접 기 삽입 정렬

void Insert(int A[], int n ){
	int i, j, low, high, mid;
	for(int i = 2; i <= n; i++){
		A[0] = A[i];
		low = 1, high = i - 1;
		while(low <= high){
			mid = (low + high) / 2;
			if(A[mid] > A[0]) high = mid - 1;
			else 
				low = mid + 1;
		}
		 //   upper_bound        (high + 1) 
		for(int j = i - 1; j >= high + 1; j--) //    
			A[j + 1] = A[j];
		A[high + 1] = A[0];
	}
}

7.2.3 힐 정렬

void shellSort(int A[], int n){
	int i, j, gap;
	for(gap = n / 2; gap > 0; gap /= 2){ //   
	 
		for(i = gap + 1; i <= n; i++){
			A[0] = A[i];
			for(j = i - gap; j > 0 && A[j] > A[0]; j -= gap) //                
				A[j + gap] = A[j];
		}
		A[j + gap] = A[0];
	}
}

7.3 교환 정렬
7.3.1 거품 정렬

void BubbleSort(int A[], int n){
	bool flag;
	for(int i = 1; i <= n; i++){
		flag = false;
		for(int j = n - 1; j >= i; j--){ //      
			if(A[j] > A[j + 1]) {
				swap(A[j], A[j + 1]); 
				flag = true;
			}
		}
		
		if(!flag) break;
	}
}

7.3.2 빠 른 정렬

void qsort(int A[], int low, int high){
	if(low < high){
		int pivot = A[low]; //     
		while(low < high){
			while(low < high && A[high] > pivot) high--;
			A[low] = A[high];
			while(low < high && A[low] <= pivot) low++;
			A[high] = A[low]; 	
		} 
		A[low] = pivot;
		
		qsort(A, low, low - 1); //      
		qsort(A, low + 1, high);
	}
}

7.4 정렬 선택
7.4.1 단순 선택 정렬

/*
		 i   i~(n-1)       
	*/
void SelectSort(int A[], int n){  // 0 - (n-1)

	for(int i = 0; i < n; i++){
		int mn = i;
		for(int j = i + 1; j < n; j++){
			if(A[mn] > A[j])
				mn = j;
		}
		if(mn != i) swap(A[i], A[mn]);
	} 
} 

7.4.2 더미 정렬

/*
	      
	          
	 
	*/
void BuildMaxHeap(int A[], int len){  // 1 - n
	for(int i = len / 2; i > 0; i--) //              ，    
		AdjustDown(A, i, len);
}

void AdjustDown(int A[], int fa, int len){
	A[0] = A[fa];
	for(int i = fa * 2; i <= len; i *= 2){
		if(i < len && A[i] < A[i + 1])
			i++;                     //  key          
			
		if(A[0] >= A[i]) break;  //      
		else {
			A[fa] = A[i];			//      
			fa = i;
		}	
	}
	A[fa] = A[0];
}
void HeapSort(int A[], int len){
	BuildMaxHeap(A, len);
	for(int i = len; i > 1; i--){ //         ， A[i]   ，      。 
		swap(A[i], A[1]);
		AdjustDown(A, 1, i - 1);
	}
}
void Delete(int A[], int &len){ //     len   &，         .
	 swap(A[1], A[len]);   //           
	 len--;
	 AdjustDown(A, 1, len);	//      
}
void insert(int A[],int k){ // A[k]           
	A[0] = A[k];
	for(int p = k / 2; p > 0 && A[p] < A[0];){ // p   k       ，  
		A[k] = A[i];    //         
		k = i; 
		p = k / 2;
	}
	
	A[k] = A[0];
}

7.4 병합 정렬

int *B = (int *) malloc(sizeof(int) * (n + 1));  //      
void Merge(int A[], int low, int mid, int high){
	/*
		A[low ~ mid]   A[mid+1 ~ high]            
	*/
	for(int i = low; i <= high; i++)
		B[i] = A[i];
	int i, j, k;
	for(i = low, j = mid + 1, k = low; i <= mid && j <= high; k++){
		if(B[i] < B[j])
			A[k] = B[i++];
		else 
			A[k] = B[j++];
	} 
	while(i <= mid) A[k++] = A[i++];
	while(j <= mid) A[k++] = A[j++];
} 

void MergeSort(int A[], int low, int high){
	if(low < high){
		int mid = (low + high) / 2;
		MergeSort(A, low, mid);
		MergeSort(A, mid + 1, high);
		
		Merge(A, low, mid, high);
	}
}