[C] 리스트와 연결리스트(2)

단순 연결리스트(simply linked list)로 리스트를 구현해보자.

리스트와 연결리스트(1)에서는 전역변수를 사용하여 head를 정의해주었다. 이번에는 전역변수를 사용하지 않아야 한다는 조건을 추가로 달아보자.

일단은 이중포인터를 이용해야 한다. 하지만 필자는 이중포인터의 개념을 잘 이해하지 못했다(하하). 수업 내용과 경험(?)을 통해 call by reference를 어떻게 잘 이용해봐야겠다는 결론을 내렸다. 애초에 그냥 포인터로 넘겨주면 함수 밖으로 나왔을 때 변수의 값이 바뀌지가 않는다,는 멍청한 경험을 통해... 어떻게든 해보았다.

 

주제: 할 일 목록 만들기

 

• 할 일을 넘버링을 통해 매긴다(Line number와 할 일 쌍으로 입력받기)
• 삽입, 삭제, 탐색, 전체 출력을 할 수 있는 함수들을 만든다.
• 삭제는 Line number로 해야한다
• 무조건 Line number를 순차적으로 받게 한다. 만약 0번줄 다음 2번줄 입력받으려 하면 오류 띄워야함.
• 전역변수의 사용을 금한다

사용한 함수들의 역할은 직전 포스트 참고!

조건을 보면 알겠지만 구조체에 data필드가 int가 아닌 string으로 입력되어야 한다. 그렇다면 element를 char로 바꿔야 겠지. 나머지 설명은 주석에 달아놨다.

 

나중에 해결하고 싶은 것들
1. head를 함수에서 initialize할 수 없나? 전 포스트에서처럼 함수로 초기화하고 싶은데 할 때마다 쓰레기값들이 들어가있음;; 그래서 일단은 maind에서 =NULL로 걍 초기화함.
2. **와 *와 &와 아무것도 안붙은 변수^^ 언제 뭘 붙어야할지 해도해도 모르겠네~ 똑같은 포인터변수 넘겨줘도 왜 어디엔 &붙고 어디엔 안붙는다. 그리고 왜 어디는 이중포인터 붙여서 넘기고 어디는 하나만 붙여..
3. 굳이 element를 만들어야 할까? 걍 data를 char형으로 받자.

 

<소스코드>

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 81
 
typedef struct {
    char sentence[MAX_SIZE];
} element; //이런 비효율적이고 멍청한 짓 하지 말자
typedef struct Node {
    element data;
    struct Node* link;
} Node;
 
int size(Node* head) {
    Node* q;
    int count = 0;
    for (q = head; q != NULL; q = q->link)
        count++;
    return count;
}
Node* get_entry(Node* head, int pos) {
    Node* p = head;
    for (int i = 0; i < pos; i++) {
        p = p->link;
        if (p == NULL) return NULL;
    }
    return p;
}
int is_empty(Node* head) {
    if (head == NULL) return 0;
    else return 1;
}
void insert_next(Node* prev, Node* n) {
    if (n != NULL) {
        n->link = prev->link;
        prev->link = n;
    }
}
void insert(Node** head, int pos) {
    Node* new_node, * prev;
    new_node = (Node*)malloc(sizeof(Node));
 
    if (pos < 0 || pos > size(*head)) printf("  Wrong Line Number!!\n");
    else {
 
        printf("  Input Strings: ");
        while (getchar() != '￦n') {
            fgets(new_node->data.sentence, sizeof(new_node->data.sentence), stdin);
            break;
        }
        new_node->link = NULL; //노드 새로 생성해서 문자열 받아오고, 일단 붙일 데가 아직 정의되지 않았으니 NULL로 배정
        /*
        밑으로는 세가지 경우로 나눔(근데 2번은 뭐임..? 없어도 잘돌아감;)
        1. 리스트에 아무것도 없을 때, 즉 head = NULL
        2. ?
        3. 중간에 삽입
        */
        if ((*head) == NULL)
            *head = new_node;
        else if (pos == 0) {
            new_node->link = *head;
            *head = new_node;
        }
        else {
            prev = get_entry(*head, pos - 1);
            if (prev != NULL)
                insert_next(prev, new_node);
        }
    }
}
Node* remove_next(Node* prev) {
    Node* removed = prev->link;
    if (removed != NULL)
        prev->link = removed->link;
    return removed;
}
void delete(Node** head, int pos) {
    Node* removed, * prev;
 
    if (pos < 0 || pos > size(*head)) printf("  Wrong Line Number!!\n"); //이게 존나 머리아프다. 사용자가 순차적으로 line number 입력하지 않으면 다시 입력하라고 해줌.
    else {
        if (pos == 0 && is_empty(*head) == 1) { //여기도 존나 머리아프다. 위치 정보가 0이고 공백리스트가 아니어야 함. 하나 남았을 때.
            removed = *head;
            *head = (*head)->link;
            free(removed);
        }
        else {
            prev = get_entry(*head, pos - 1);
            if (prev != NULL) {
                removed = remove_next(prev);
                free(removed);
            }
        }
    }
}
void print_all(Node* head) {
    Node* p;
    int i;
    printf("\n");
    for (i = 0, p = head; p != NULL; i++, p = p->link)
        printf("%02d:%s", i, p->data.sentence);
    printf("\n");
}
void free_all(Node** head) {
    int i, s;
    s = size(*head);
    for (i = 0; i < s; i++) delete(head, 0);
}
 
int main(void) {
    Node* head = NULL;
    int sel, num;
 
    while (1) {
        do {
            printf("[ 1.Display 2.Line Insert 3.Line Delete 0.Exit ]: ");
            scanf("%d", &sel);
        } while (sel < 0 || sel > 3);
        if (sel == 1) {
            if (is_empty(head) == 0) printf("  Line is Empty!!\n");
            else print_all(head);
        }
        else if (sel == 2) {
            printf("  Line number: ");
            scanf("%d", &num);
            insert(&head, num);
        }
        else if (sel == 3) {
            if (is_empty(head) == 0)
                printf("  Line is Empty!!\n");
            else {
                printf("  Line number: ");
                scanf("%d", &num);
                delete(&head, num);
            }
        }
        else break;
    }
    free_all(&head);
    return 0;
}

 

<결과 창>

 

 

하라는 공부는 열심히 안하고 할 일 목록에 있는 것들만 열심히 했네^^! 내 자신이 정말 자랑스럽다!

그리고 이중포인터 너무 어렵다!