[자료구조] 그룹 엑티비티 3 전문

IT 프로그래밍/자료구조

[자료구조] 그룹 엑티비티 3 전문

기술1 2024. 10. 22. 22:47

#include <iostream>
#include <vector>
using namespace std;

struct Node {
    int data;
    Node *next;
    Node(int d, Node *p): data(d), next(p) {}
};

Node *make_list(vector<int> &v) {
    Node *head = nullptr;
    for (auto it=v.rbegin(); it!=v.rend(); it++)
        head = new Node(*it, head);
    return head;
}

void print_list(Node *head) {
    Node *p = head;
    while(p != nullptr) {
        cout << p->data << ' ';
        p = p->next;
    }
    cout << endl;
}

Node *concatenate(Node *first, Node *second) {
    if (first == nullptr) return second;
    if (second == nullptr) return first;
    Node *t = first;
    while(t->next != nullptr)
        t = t->next;
    t->next = second;
    return first;
}

void remove_multiple_three(Node *head) {

    Node *p = head;
    while (p->next->data % 3 != 0)   // (1) 첫 번째 노드를 검사하지 않는다. (2) p==nullptr or p->next == nullptr인 경우 오류
        p = p->next;
    if (p->next == nullptr)
        return;
    p->next = p->next->next;
                                        // (3) head가 변경된 경우?
}

Node *remove_multiple_three2(Node *head) {
    Node *p = head, *q = nullptr;
    while (p != nullptr && p->data % 3 != 0) {
        q = p;
        p = p->next;
    }
    if (p == nullptr) return head;
    if (q == nullptr) {
        Node *tmp = head;
        head = head->next;
        delete tmp;
        return head;
    }
    q->next = p->next;
    delete p;
    return head;
}

void func(Node* head) {
    Node* prev = nullptr;
    Node* current = head;
    Node* next;
    while (current != nullptr) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
}

Node *func2(Node* head) {
    Node* prev = nullptr;
    Node* current = head;
    Node* next;
    while (current != nullptr) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

Node *circular_shift(Node *head) {
    if (head == nullptr || head->next == nullptr)
        return head;
    Node *last_minus_one = head;
    while(last_minus_one->next->next != nullptr)
        last_minus_one = last_minus_one->next;
    Node *last = last_minus_one->next;
    last->next = head;
    last_minus_one->next = nullptr;
    return last;
}

void rearrange(Node *list) {
    Node *p, *q;
    int temp;
    if (list==nullptr || list->next==nullptr)
        return;
    p = list;
    q = list->next;
    while(q!=nullptr) {
        temp = p->data;
        p->data = q->data;
        q->data = temp;
        p = q->next;
        q = (p != nullptr ? p->next : 0);
    }
}

int main() {
    vector<int> v1{1, 2, 3, 4};
    Node *h1 = make_list(v1);
    print_list(h1);
    vector<int> v2{10, 20, 30};
    Node *h2 = make_list(v2);
    print_list(h2);

    print_list(concatenate(h1, h2));

    vector<int> v3{1, 3, 6, 9, 11, 5, 4, 8, 12};
    Node *h3 = make_list(v3);
    remove_multiple_three(h3);
    print_list(h3);

    vector<int> v4{1, 3, 6, 9, 11, 12};
    Node *h4 = make_list(v4);
    h4 = func2(h4);
    print_list(h4);

    vector<int> v5{1, 3, 6, 9, 11, 12};
    Node *h5 = make_list(v5);
    h5 = circular_shift(h5);
    print_list(h5);

    vector<int> v6{1, 3, 6, 9, 11, 12, 13};
    Node *h6 = make_list(v6);
    rearrange(h6);
    print_list(h6);
    return 0;
}

1. 구조체 정의 및 기본 함수들

struct Node {
	int data;
    Node *next;
    Node(int d, Node *p) : data(d), next(p) {}
};

Node 구조체: 연결 리스트의 노드를 정의합니다. 각 노드는 data와 next를 갖고 있습니다.
- data는 정수형 데이터를 저장합니다.
- next는 다음 노드의 주소를 가리키는 포인터입니다.
- 생성자: Node(int d, Node *p)는 노드를 생성할 때 data와 next를 설정합니다.

Node *make_list(vector<int> &v) {
    Node *head = nullptr;
    for (auto it = v.rbegin(); it != v.rend(); it++)
        head = new Node(*it, head);
    return head;
}

make_list 함수: 주어진 벡터를 사용하여 연결 리스트를 생성합니다.

v는 정수형 벡터로, 이 벡터의 요소들을 연결 리스트로 변환합니다.
벡터의 끝에서부터 순회(rbegin() 사용)하면서 각 요소를 새로운 노드로 생성하고, 새로 생성한 노드를 리스트의 head로 설정합니다.
최종적으로 연결 리스트의 head를 반환합니다.

void print_list(Node *head) {
    Node *p = head;
    while(p != nullptr) {
        cout << p->data << ' ';
        p = p->next;
    }
    cout << endl;
}

print_list 함수: 연결 리스트의 모든 노드를 출력하는 함수입니다.

head에서 시작하여 리스트 끝까지 각 노드의 data 값을 출력합니다.
p가 nullptr이 될 때까지 노드를 순차적으로 탐색하며 데이터를 출력합니다

2. 연결 리스트 병합 함수

Node *concatenate(Node *first, Node *second) {
    if (first == nullptr) return second;
    if (second == nullptr) return first;
    Node *t = first;
    while(t->next != nullptr)
        t = t->next;
    t->next = second;
    return first;
}

concatenate 함수: 두 개의 연결 리스트를 병합하는 함수입니다.

첫 번째 리스트가 nullptr이면 두 번째 리스트를 반환하고, 두 번째 리스트가 nullptr이면 첫 번째 리스트를 반환합니다.
첫 번째 리스트의 마지막 노드까지 탐색한 뒤, 마지막 노드의 next를 두 번째 리스트의 head로 연결하여 두 리스트를 병합합니다.

3. 3의 배수를 삭제하는 함수

Node *remove_multiple_three2(Node *head) {
    Node *p = head, *q = nullptr;
    while (p != nullptr && p->data % 3 != 0) {
        q = p;
        p = p->next;
    }
    if (p == nullptr) return head;
    if (q == nullptr) {
        Node *tmp = head;
        head = head->next;
        delete tmp;
        return head;
    }
    q->next = p->next;
    delete p;
    return head;
}

remove_multiple_three2 함수: 개선된 버전으로, 연결 리스트의 첫 번째 3의 배수 노드를 삭제합니다.

리스트의 첫 번째 노드가 3의 배수일 경우도 처리하고 있습니다.
리스트에서 3의 배수인 노드를 삭제한 후 새로 갱신된 head를 반환합니다.

4. 역순으로 뒤집기 함수

void func(Node* head) {
    Node* prev = nullptr;
    Node* current = head;
    Node* next;
    while (current != nullptr) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
}

func 함수: 연결 리스트를 역순으로 뒤집는 함수입니다.

prev, current, next를 사용하여 리스트의 연결 방향을 반대로 변경합니다.
이 함수는 리스트를 뒤집지만 결과를 반환하지 않기 때문에, 리스트의 head는 바뀌지 않게 됩니다.

Node *func2(Node* head) {
    Node* prev = nullptr;
    Node* current = head;
    Node* next;
    while (current != nullptr) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

반환되는 버전

5. 마지막 노드를 맨 앞으로 이동

Node *circular_shift(Node *head) {
    if (head == nullptr || head->next == nullptr)
        return head;
    Node *last_minus_one = head;
    while(last_minus_one->next->next != nullptr)
        last_minus_one = last_minus_one->next;
    Node *last = last_minus_one->next;
    last->next = head;
    last_minus_one->next = nullptr;
    return last;
}

circular_shift 함수: 리스트의 마지막 노드를 맨 앞으로 이동시키는 함수입니다.

last_minus_one은 마지막 노드 바로 앞 노드를 가리키며, 그 뒤의 마지막 노드를 찾아 맨 앞으로 이동시킵니다.
마지막 노드가 맨 앞으로 이동한 후, 그 노드를 새로운 head로 반환합니다.

6. 노드값 교환함수

void rearrange(Node *list) {
    Node *p, *q;
    int temp;
    if (list == nullptr || list->next == nullptr)
        return;
    p = list;
    q = list->next;
    while(q != nullptr) {
        temp = p->data;
        p->data = q->data;
        q->data = temp;
        p = q->next;
        q = (p != nullptr ? p->next : nullptr);
    }
}

rearrange 함수: 인접한 노드끼리 데이터 값을 교환하는 함수입니다.

첫 번째와 두 번째 노드의 값을 교환한 후, 세 번째와 네 번째 노드의 값을 교환합니다.
리스트 끝까지 이러한 교환을 반복합니다.

int main() {
    vector<int> v1{1, 2, 3, 4};
    Node *h1 = make_list(v1);
    print_list(h1);
    vector<int> v2{10, 20, 30};
    Node *h2 = make_list(v2);
    print_list(h2);

    print_list(concatenate(h1, h2));

    vector<int> v3{1, 3, 6, 9, 11, 5, 4, 8, 12};
    Node *h3 = make_list(v3);
    remove_multiple_three(h3);
    print_list(h3);

    vector<int> v4{1, 3, 6, 9, 11, 12};
    Node *h4 = make_list(v4);
    h4 = func2(h4);
    print_list(h4);

    vector<int> v5{1, 3, 6, 9, 11, 12};
    Node *h5 = make_list(v5);
    h5 = circular_shift(h5);
    print_list(h5);

    vector<int> v6{1, 3, 6, 9, 11, 12, 13};
    Node *h6 = make_list(v6);
    rearrange(h6);
    print_list(h6);
    return 0;
}

테스트 케이스를 위한 코드입니다. 각 함수들이 제대로 동작하는지 확인하기 위해 여러 연결 리스트가 생성되고, 각 함수가 호출된 후 그 결과를 출력합니다.

v1, v2: 각각의 리스트를 출력한 후, 두 리스트를 병합하고 결과 출력.
v3: 3의 배수를 제거하고 결과 출력.
v4: 리스트를 역순으로 뒤집은 후 결과 출력.
v5: 마지막 노드를 맨 앞으로 이동하고 결과 출력.
v6: 인접한 노드끼리 데이터를 교환한 후 결과 출력.

결론:

주어진 코드는 연결 리스트를 다루는 다양한 기능을 구현한 함수들을 포함하고 있으며, 각각의 함수가 올바르게 동작하는지 테스트하기 위한 main() 함수도 잘 작성되어 있습니다

'IT 프로그래밍 > 자료구조' 카테고리의 다른 글

[자료구조] 과제2 (2)	2024.10.23
[자료구조] 그룹 액티비티 4 (0)	2024.10.23
[자료구조] 그룹 액티비티 3 (0)	2024.10.22
[자료구조] 프로그래밍 과제1 (0)	2024.10.20
[자료구조] 그룹액티비티2 (1)	2024.10.20

현재글[자료구조] 그룹 엑티비티 3 전문

기술 블로그

오블완, 녹색혁명, 백준 10813, 백준2284번, nmn^2, 거듭제곱 구하는 법, 따배시, 빈곤이란 무엇인가?, haring :, 빈곤이란, string 설명, 빈곤의 사회학적 정의, 따배시 강의, 따배시 강의 요약, x5x6, 티스토리챌린지, C++, 프로그래밍 예제, 말레이시아 경제, strtok기능,

일	월	화	수	목	금	토
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30

기술 블로그