연결리스트 삽입, 그래프(인접행렬과 인접리스트)

문자 입력받고 해당 문자 뒤에 삽입하기

#include <iostream>
using namespace std;
struct Node{
    char a;
    Node *next;
};
Node *head;

void init(char a)
{
    head = new Node({a, head});
}

void insert(char a)
{
    for(Node *q= head; q != NULL; q =  q->next)
    {
        if(q->a == a)
        {
            Node *temp = new Node({'Z', NULL});
            temp->next = q->next;
            q->next = temp;
        }
        if(q->next == NULL)
            break;
    }
}
void print()
{
    for(Node *p = head; p != NULL; p = p->next)
    {
      
        cout << p->a << ' ' ;
        if(p->next == NULL)
            break;
    }
}
int main()
{
    char fi;
    cin >> fi;

    init('F');
    init('E');
    init('D');
    init('C');
    init('B');
    init('A');
    insert(fi);
    print();
    return 0;
}

특정 노드 삭제하는 함수

void del(char a)
{
    
    if(head->a == a)
    {
        Node *temp = head->next;
        delete head;
        head = temp;
        return;
    }
    Node *p;
    for(p = head; p != NULL; p= p->next)
    {
        if(p->next == NULL) return;
        if(p->next->a == a)
            break;
    }
    p->next = p->next->next;
        
}

 

우선 delet의 경우 2가지로 나눠서 생각해야 한다.

head->a가 삭제할 노드라면 바로 삭제한다. 그러나 그 뒤의 노드라면 탐색을 진행해야 한다. 하지만 이전 노드를 통해 탐색해야 삭제를 진행할 수 있기에 if(p->next->a)를 사용하였다. 

 

삭제의 경우 메모리를 할당하지 않는 경우가 있는데 꼭 할당 해제 습관을 들이자

 

 

노드 위치 바꾸기

void switchs(char what, char where)
{
    for(Node *p = head; p != NULL; p = p->next)
    {
        
        
        if(p->a == where)
        {
            temp.next = p->next;
            p->next = &temp;
        }
        if(p->next == NULL) break;
    }
}


int find(char a)
{
    if(head->a == a)
    {
        temp.a = head->a;
        head = head->next;
    }
    Node *q;
    for(q = head; q != NULL; q= q->next)
    {
        if(q->next == NULL) return 0;
        if(q->next->a == a) break;
    }
    temp.a = q->next->a;
    q->next = q->next->next;
    return 1;
}

 

 

그래프는 인접리스트와 인접행렬로 나타낼 수 있다.

인접 리스트로 그래프 표현

#include <iostream>
using namespace std;
struct Node{
    int x;
    Node *next;
};
Node *head[4], *tail[4];

void addNode(int from, int a)
{
    if(head[from] == NULL)
    {
        tail[from] = head[from] = new Node({a, head[from]});
        return;
    }
    tail[from] = tail[from]->next = new Node({a, NULL});
    
}
int main()
{
    addNode(0, 1);
    addNode(0, 3);
    addNode(0, 2);
    addNode(1, 3);
    addNode(2, 3);
    
    int debug = 1;
    return 0;
}

인접행렬로 표현하기

#include <iostream>
using namespace std;
int map[4][4] = {
    0, 1, 1, 1,
    0, 0, 0, 1,
    0, 0, 0, 1,
    0, 0, 0, 0
};

int main()
{
    int max_cnt = -21e8,maxIndex = -1;
    for(int i=0; i<4; i++)
    {
        int cnt = 0;
        for(int j=0; j<4; j++)
        {
            if(map[i][j] == 1)
                cnt++;
        }
        if(max_cnt < cnt)
        {
            max_cnt = cnt;
            maxIndex = i;
        }
    }
    cout << maxIndex;
    return 0;
}