[자료구조] 선형 리스트 삽입/삭제/탐색/종료

선형리스트에 데이터를 삽입, 삭제, 탐색하는 함수를 구현한 프로그램.

 

배열의 크기 100, 데이터의 갯수 n이 기본 설정이다.

입력받은 데이터를 크기별로 리스트에 넣을 것이다.

 

2,7,5를 순서대로 삽입했을 때 크기별로 저장되어 2, 5, 7이 출력되는 모습

 

선형리스트는 말그대로 선으로 연결되어 있는 자료구조이다. 

따라서 새로운 데이터를 삽입할 때에는 삽입할 위치의 원소를 뒤로, 그 뒤 원소를 또 뒤로 넘겨 한자리씩 이동시켜야 한다. 그렇게 해서 만든 빈 자리에 데이터를 삽입해야 한다.

 

5를 삭제하고 리스트를 출력한 뒤 종료

 

삭제는 반대로 원소를 삭제하고 생긴 공백을 메우기 위해 뒤에 있던 원소들을 한자리씩 앞당겨야 한다.

전체 코드는 아래와 같음.

 

//선형리스트 프로그램
#include<stdio.h>
#include<Windows.h>
#define MAX 100 //배열의 크기
 
int list[MAX] = { 0 };
int n = 0; //데이터의 갯수
 
void print_header(); //프로그램 제목
void menu(); //메뉴
void insert(); //삽입
void delete(); //삭제
void search(); //탐색
void print(); //출력
void end(); //종료
 
int main() { 
 
    int num1 = 0;
    int num2 = 0;
 
    while (num1 != 5) {
        print_header();
        menu();
 
        printf("\n메뉴를 선택하세요...");
        scanf_s("%d", &num1);
 
 
        // 삽입 삭제 탐색 출력 종료 switch문 활용
        switch (num1) {
        case 1:
            printf("데이터를 입력하세요...");
            scanf_s("%d", &num2);
            insert(num2);
            break;
        case 2:
            printf("데이터를 입력하세요...");
            scanf_s("%d", &num2);
            delete(num2);
            break;
        case 3:
            printf("데이터를 입력하세요...");
            scanf_s("%d", &num2);
            search(num2);
            break;
        case 4:
            print();
            break;
        case 5:
            end();
            break;
        }
    }
 
    return 0;
}
 
void print_header() {
    printf("\n\n==================================================\n");
    printf(" \t선형리스트(Linear List) 프로그램         \n");
    printf("==================================================\n\n");
    printf("\n");
}
 
void menu() {
    printf("\n==========================================\n\n");
    printf(" \t\t1. 삽입 \n");
    printf(" \t\t2. 삭제 \n");
    printf(" \t\t3. 탐색 \n");
    printf(" \t\t4. 출력 \n");
    printf(" \t\t5. 종료 \n\n");
    printf("==========================================\n\n");
 
}
 
void insert(int num2) {
    //삽입프로그램
    //하나씩 입력받아 배열에 크기대로 저장
    int i, j, k = 0;
 
    //배열이 꽉 차있는지 비어있는지 확인 후 ERROR 출
    //동일한 데이터를 삽입하려할 때 ERROR 출력
    if (n==MAX) {
        printf("ERROR!! 더 이상 숫자를 넣을 수 없습니다.\n\n");
        system("PAUSE");
        system("cls");
        return;
    }
    for (i = 0; i < n; i++) {
        if (list[i] == num2) {
            printf("ERROR!! 같은 숫자이므로 넣을 수 없습니다.\n\n");
            system("PAUSE");
            system("cls");
            return;
        }
    }
    //0번째와 1번째에 데이터 값을 넣고, 그 후에 받는 데이터는 크기를 구별하여 삽입 
    switch(n) {
    case 0:
        list[0] = num2;
        n++;
        system("cls");
        return;
    case 1:
        if (num2 < list[0]) {
            list[1] = list[0];
            list[0] = num2;
            n++;
            system("cls");
            return;
        }
        else {
            list[1] = num2;
            n++;
            system("cls");
            return;
        }
    default:
        for (i = 0; i < n; i++) {
            if (list[i] < num2 && num2 < list[i + 1]) {
                for (j = n; j > i + 1; j--) {
                    list[j] = list[j - 1];
                }
                list[i + 1] = num2;
                n++;
                system("cls");
                return;
            }
            else if (num2 < list[i]) {
                for (j = n; j >= i + 1; j--) {
                    list[j] = list[j - 1];
                }
                list[i] = num2;
                n++;
                system("cls");
                return;
            }
        }
        if (num2 > list[n - 1]) {
            list[n] = num2;
            n++;
            system("cls");
            return;
        }
        break;
    }
}
 
void delete(int num2) {
    //삭제 프로그램
 
    int cnt = 0;
    int i, j = 0;
 
    //먼저 배열이 비어있는지 확인 후 비어있다면 ERROR 출력
    if (n == 0) {
        printf("ERROR!! 배열이 비어있습니다.\n\n");
        system("PAUSE");
        system("cls");
        return;
    }
    //데이터 값 검색, 데이터가 배열에 있으면 제거, 없으면 ERROR 출력
    for (i = 0; i < n; i++) {
        if (list[i] == num2) {
            list[i] = 0;
            n--;
            for (j = i; j < n; j++) {
                list[j] = list[j + 1];
            }
            printf("삭제되었습니다.\n\n");
            system("PAUSE");
            system("cls");
            return;
        }
        cnt++;
    }
    if (cnt == n) {
        printf("ERROR!! 이 데이터가 배열에 들어있지 않습니다.\n\n");
        system("PAUSE");
        system("cls");
        return;
    }
}
 
void search(int num2) {
    //탐색 프로그램
    //특정 데이터 값 찾고 배열에 있으면 어느 위치에 있는지 출력,
    //없으면 ERROR 메세지 출력
    int cnt = 0;
 
    for (int i = 0; i < n; i++) {
        if (list[i] == num2) {
            printf("%d는 배열 list[%d]에 들어있습니다.\n\n", num2, i);
            system("PAUSE");
            system("cls");
            return;
        }
        cnt++;
    }
    if(cnt == n) {
        printf("ERROR!! %d는 배열에 들어있지 않습니다 !!\n\n",num2);
        system("PAUSE");
        system("cls");
        return;
    }
}
 
void print() {
    //출력 프로그램
    printf("\n선형 리스트의 데이터 갯수는 총 %d개이며, 원소들은 다음과 같다.\n\n",n);
 
    for (int i = 0;i<n; i++) {
        printf("%d  ", list[i]);
    }
    printf("\n\n");
    system("PAUSE");
    system("cls");
    return;
}
 
void end() {
    //종료 프로그램
    printf("\n\n==================================\n");
    printf("\t  종료를 선택하셨습니다.\n");
    printf("==================================\n");
 
}
 

 

메뉴 선택을 위한 switch문 외에는 모두 함수를 호출하도록 만들어 main함수를 깔끔하게 해봤다.

또한 프로그램으로써의 기능을 위해 system("PAUSE"), system("cls") 등을 사용했으나 이 부분은 옵션.