[P4C 4기] 6주차 과제 - Doubly Linked List 구현, 구구단 with 어셈블리어, Stack 문서 요약

1. Doubly LInked List(이중 연결 리스트, 이하 DLL)

 

이중 연결 리스트

 

DLL은 데이터를 저장하는 자료구조의 하나로 연결 리스트와 비슷합니다.

차이점이 있다면 다음 노드만이 아닌 이전 노드에 대해서도 연결되어 있습니다.

 

맨 첫 번째 노드는 Head가 되고 맨 마지막 노드는 Tail이 됩니다.

typedef struct linkedlist {
    struct Node* head;
    struct Node* tail;
    int count; //노드의 개수
}linkedlist;

 

각 노드가 가지는 정보는 다음과 같습니다.

typedef struct Node {
    char data[10];
    struct Node* prev; // 이전 노드 포인터
    struct Node* next; // 다음 노드 포인터
}Node;

 

 

사용된 함수는 다음과 같습니다.

void Create_Node(linkedlist* L);
void Read_Node(linkedlist* L);void Update_Node(linkedlist* L);void Delete_Node(linkedlist* L);int Is_empty(linkedlist* L);
int Find_Node(linkedlist* L, char get_data[]);
void Clear_Node(linkedlist* L);

 

 

실행 결과

초기 화면

 

1. 데이터 생성

 

2. 데이터 출력

 

3. 데이터 변환 후 출력

 

4. 데이터 삭제 후 출력

 

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
 
 
typedef struct linkedlist {
    struct Node* head;
    struct Node* tail;
    int count; //노드의 개수
}linkedlist;
 
typedef struct Node {
    char data[10];
    struct Node* prev; // 이전 노드 포인터
    struct Node* next; // 노드의 오른쪽 링크
}Node;
 
void Create_Node(linkedlist* L);
void Read_Node(linkedlist* L);void Update_Node(linkedlist* L);void Delete_Node(linkedlist* L);int Is_empty(linkedlist* L);
int Find_Node(linkedlist* L, char get_data[]);
void Clear_Node(linkedlist* L);
 
 
int main() {
    int choice;
 
    linkedlist* L = (linkedlist*)malloc(sizeof(linkedlist));
    //Node* info;
    L->head = NULL;
    L->count = 0;
 
    printf("  Program start! \n\n");
 
    while (1) {
        printf("  1. Create a Data \n");
        printf("  2. Read all Data \n");
        printf("  3. Update a Data \n");
        printf("  4. Delete a Data \n");
        printf("  5. Exit \n");
        printf("  >> ");
        scanf_s("%d", &choice);
 
        if (choice == 1) {
            printf("  ========================================\n");
            Create_Node(L);
            printf("  ========================================\n");
        }
 
        if (choice == 2) {
            printf("  ========================================\n");
            Read_Node(L);
            printf("  ========================================\n");
        }
 
        if (choice == 3) {
            printf("  ========================================\n");
            Update_Node(L);
            printf("  ========================================\n");
        }
        if (choice == 4) {
            printf("  ========================================\n");
            Delete_Node(L);
            printf("  ========================================\n");
        }
        if (choice == 5) {
            printf("  ========================================\n");
            Clear_Node(L);
            printf("  ========================================\n");
            return 0;
        }
    }
}
 
void Create_Node(linkedlist* L) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    printf("  Enter the Data: ");
    scanf_s("%s", newNode->data, sizeof(newNode->data));
 
    newNode->next = NULL;
 
    if (L->head == NULL) {
        L->head = newNode;
        L->tail = newNode;
        L->head->prev = L->head->next = NULL;
        L->tail->prev = L->tail->next = NULL;
        L->count++;
    }
    else {
        newNode->prev = L->tail;
        newNode->next = NULL;
        L->tail->next = newNode;
        L->tail = newNode;
        L->count++;
    }
 
    printf("  Create Node success!!\n");
    return ;
}
 
void Read_Node(linkedlist* L) {
    if (Is_empty(L))
        return 0;
 
    Node* info = L->head;
    int index = 1;
 
    while (info != NULL) {
        printf("  %d. Data : %s \n", index, info->data);
 
        if (info->next != NULL)
            printf("  ----------------------------------------\n");
 
        info = info->next;
        index++;
    }
    return ;
}
int Is_empty(linkedlist* L) {
    if (L->head == NULL) {
        printf("  There is no data.\n");
        return 1;
    }
    else
        return 0;
}
 
void Update_Node(linkedlist* L) {
    if (Is_empty(L))
        return 0;
 
    Node* node = L->head;
    char get_data[10];
 
    printf("  Enter the data want to update: ");
    scanf_s("%s", get_data, sizeof(get_data));
 
    if (Find_Node(L, get_data)) {
        printf("  There is no \"%s\".\n.", get_data);
        return 0;
    }
 
    while (strcmp(node->data, get_data))
        node = node->next;
    printf("  Enter the new data: ");
    scanf_s("%s", node->data, sizeof(node->data));
    printf("  Update Node success!!\n");
 
    return;
}
 
void Delete_Node(linkedlist* L) {
    Node* p = NULL;  // remove의 이전 노드
    Node* remove = L->head;
    char get_data[10];
 
    if (Is_empty(L))
        return 0;
 
    printf("  Enter the Data want to delete : ");
    scanf_s("%s", get_data, sizeof(get_data));
 
    if (Find_Node(L, get_data)) {
        printf("  There is no \"%s\". \n", get_data);
        return 0;
    }
 
    while (1) {
        if (!strcmp(get_data, remove->data)) {
            if (remove == L->head) {    //맨 처음 노드 삭제
                if (L->head->next == NULL) { //노드가 1개밖에 없는 경우에서의 삭제
                    L->head = NULL;
                    L->tail = NULL;
                    free(remove);
                    L->count--;
                    break;
                }
                L->head = remove->next;
                L->head->prev = NULL;
                L->head->next = remove->next->next;
                free(remove);
                L->count--;
                break;
            }
 
            else if (remove->next == NULL) {   //맨 마지막 노드 삭제
                L->tail = p;
                L->tail->prev = remove->prev->prev;
                L->tail->next = NULL;
                free(remove);
                L->count--;
                break;
            }
 
            else {  //중간 노드 삭제
                p->next = remove->next;
                remove->next->prev = p;
                free(remove);
                L->count--;
                break;
            }
        }
        p = remove;
        remove = remove->next;
    }
    printf("  Delete Node success!!\n");
    return;
}
 
int Find_Node(linkedlist* L, char get_data[]) {
    Node* node = L->head;
    int i = 0;
 
    for (i = 0; i < L->count; i++) {
        if (!strcmp(node->data, get_data))
            return 0;
        node = node->next;
    }
    return 1;
}
 
void Clear_Node(linkedlist* L) {
    Node* remove = L->head;
    Node* p = NULL;
 
    if (Is_empty(L)) {
        printf("  Program exit.\n");
        return 0;
    }
 
    while (remove != NULL) {
        free(remove);
        remove = p;
        if (p != NULL)
            p = p->next;
    }
    printf(" Program exit.\n");
    return ;
}

 

참고

https://en.wikipedia.org/wiki/Doubly_linked_list

Doubly linked list - Wikipedia

 

 

 

2. 구구단 with 어셈블리어

.str1: 구구단 출력하기 위한 string -> "%d * %d = %d\n"

.str2: 단을 구분하기 위한 구분 선 string -> "===========\n"

 

.start: 메인 함수 시작을 위한 함수 프롤로그 및 스택 할당, -4(%ebp)에 2대 -> 2단부터 시작, Block2로 점프

 

.Block_2: -4(%ebp)의 값이 9와 같은지 확인

                같지 않다면 Block_5로 점프 -> 9단까지 반복해야하기 때문 

                같다면 메인 함수 에필로그 및 종료

            

.Block_5: -8(%ebp)에 1 할당 후 Block_3로 점프 -> -8(%ebp)에 곱할 수 할당

 

.Block_3: 9와 -8(%ebp)의 값이 같은지 확인

               같지 않다면 Block_4로 점프 -> 

               같다면 puts을 이용해 단을 구분하기 위한 구분선인 str2 출력 -> 하나의 단 출력 완료

               단수(-4(%ebp)) 증가

 

.Block_4:  연산을 위해 -4(%ebp) 값을 %eax에 저장 후 -8(%ebp)와 곱셈

                 printf 함수 호출을 위한 인자 배치

                 곱하는 값(-8(%ebp)) 1 증가

             

출력 결과

 

 

 

3. Stack 문서 요약

지역변수와 stack

C언어의 변수에는 ‘지역 변수’와 ‘전역 변수’가 있습니다.

‘지역 변수’는 함수 실행 시에만 할당되고, ‘전역 변수’는 한 번 생성하면 어떤 함수에서든 사용할 수 있습니다. ‘지역 변수’는 메모리의 stack에서 생성되고 사라지게 됩니다.

stack은 ‘선입후출(Last In First Out’의 구조를 가지고 있습니다. 쌓아올린 접시처럼 들어온 순서의 역순으로 데이터가 나가게 됩니다.

stack은 stack pointer(rsp)를 이용해 데이터를 넣고, 데이터를 반환합니다. 항상 맨 위에서부터 데이터를 넣고, 맨 위의 데이터부터 반환합니다.

 

함수가 호출될 때마다 ‘함수 프롤로그’가, 함수가 반환될 때마다 ‘함수 에필로그’가 일어납니다.

 

함수 프롤로그

함수 프롤로그는 rbp를 스택에 넣고 rsp가 가지는 값을 rbp에 대입합니다. 그리고 사용할 만큼의 stack 공간을 할당합니다. 필요한 stack의 크기는 컴파일 될 때 계산됩니다.

 

함수 에필로그

함수 에필로그는 할당된 스택공간을 정리하기 위해 rbp가 가지는 값을 rsp에 대입합니다. 이전에 저장된 rbp값을 현재 rbp에 대입합니다. 그리고 프롤로그 때 저장한 이후 명령어를 실행합니다.

 

call과 ret

함수 프롤로그와 에필로그가 호출될 ‘때’와 반환될 ‘때’라면, 함수가 호출되기 ‘전’에 call 명령어를 수행하고 반환된 ‘후’ ret 명령어를 수행합니다.

‘call’ 명령어는 호출한 함수가 다시 제자리로 돌아온 뒤 실행해야할 코드의 주소 값을 스택에 push합니다. 그리고 해당 호출한 함수로 점프하여 함수 프롤로그를 진행합니다.

‘ret’ 명령어는 함수 에필로그를 진행한 뒤 call 명령어로 인해 저장된 다음 주소 값을 pop 하여 명령어 포인터 레지스터에 저장합니다.

‘ret’ 명령어는 ‘call’ 명령어와 단짝친구입니다. ‘call’ 명령어로 호출 된 코드면, ‘ret’ 명령어를 반드시 수행해야합니다.

 

스택에 저장된 변수를 참조할 경우엔 변수의 주소 값이 아닌 rbp에서 얼마나 떨어져 있는가를 이용합니다. 변수의 주소를 이용하는 것보다 base pointer인 rbp에서 오프셋을 계산하는 방식이 더 효율적이기 때문입니다.