[자료구조 - C언어] 자료구조 제14강: Music Library Program(8)

[자료구조 - C언어] 자료구조 제14강: Music Library Program(8)

2022. 11. 4. 19:17ㆍCS/자료구조

728x90

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

0. 실행 예

~~Data file name? - 프로그램을 실행하면 어떤 데이터 파일을 load 할지 물어본다.~~
- 입력 없이 Enter를 치면 데이터 파일로부터 데이터를 읽지 않고 프로그램을 실행
~~status - 저장된 모든 노래의 번호, 가수, 제목, 파일의 경로명을 출력~~
- 노래의 번호는 입력 순서 대로 번호 할당
- 출력 시 가수 이름 알파벳 순으로 출력
  - 동일한 가수 이름이면 노래 제목으로 알파벳 순으로 출력
~~add - 가수 이름, 제목, 파일명으로 추가~~
- 파일명은 지정하지 않아도 된다.
~~search - 가수 이름과 노래 제목으로 검색~~
- 제목 없이 가수 이름만 검색해도 된다.
play 4 - 4번 노래를 play
remove 6 - 6번 노래를 목록에서 삭제
save as my_collection.txt - 목록을 파일에 저장
~~exit - 종료~~
~~파일 형식~~
```
가수#노래제목#경로#
LESSERAFIM#Sour Grapes# #
```
- 가수#노래제목#경로# 순서
- #문자를 필드 간의 구분자
- 존재하지 않는 항목의 경우 하나의 공백 문자로 표시
  - 모든 라인은 반드시 구분자로 끝난다.

1. 검색함수 분리하기

1-1. SNode find_snode(Artist ptr_artist, char *title)

함수의 재사용성을 위해서 분리

//library.c

//artist 이름과 노래 제목으로 snode를 찾는 함수 분리하기
SNode *find_snode(Artist *ptr_artist, char *title){
    SNode *ptr_snode = ptr_artist->head;
    //노래제목은 알파벳 순 정렬
    while(ptr_snode != NULL && strcmp(ptr_snode->song->title, title) < 0)
        ptr_snode = ptr_snode->next;
    
    if(ptr_snode != NULL && strcmp(ptr_snode->song->title, title) == 0)
        return ptr_snode;
    else
        return NULL;
}

1-2. void search_song(char artist, char title) 수정

//library.c 

void search_song(char *artist, char *title){
    Artist *ptr_artist = find_artist(artist);
    
    if(ptr_artist == NULL){
        printf("No such artist exists.\\n");
        return;
    }

    SNode *ptr_snode = find_snode(ptr_artist, title);
    
    if(ptr_snode != NULL){
        printf("Found:\\n");
        print_song(ptr_snode->song);
    }
    else{
        printf("No such song exists.\\n");
        return;
    }
}

1-3. 결과

2. 프로토타입의 위치

어떤 함수의 프로토타입은 .c 파일에 두고
- 같은 파일 내에서 호출
어떤 함수의 프로토타입은 .h 파일에 두는지
- 다른 소스파일에서 호출

3. play 구현하기

노래를 재생하기 위해 번호로 검색을 할 때 모든 아티스트를 거쳐 검색하지 않고
인덱스로 검색하면 효율적으로 검색할 수 있다.
- index_directory의 인덱스를 SIZE로 나누었을 때 나머지끼리 단방향 연결
- 정의해둔 SNode의 prev 필드는 사용하지 않지만, 그냥 SNode를 사용
Artist와 연결된 Song 객체와 동일, Song 객체는 노래 하나당 하나만 존재한다.
- Artist에는 다른 SNode가 존재하고, 하나의 Song 객체는 두 개 이상의 SNode에 연결

3-1. index_directory에 Song 추가하기

index_directory를 초기화하고, add_song 동작 시 index_directory에도 Song을 삽입하기

//library.c

#define SIZE_INDEX_TABLE 100
SNode *index_directory[SIZE_INDEX_TABLE];

void initialize(){    
		...

    for(int i=0; i<SIZE_INDEX_TABLE; i++)
        index_directory[i] = NULL;
}

void add_song(char *artist, char *title, char *path){
		...

		//index_directory에도 추가
    insert_to_index_directory(ptr_song);
}

SNode의 단방향 연결 리스트를 배열로 가지고 있는 index_directory에 인덱스 값을 계산해서 Song 삽입

//library.c

void insert_to_index_directory(Song *ptr_song){
    SNode *ptr_snode = (SNode *)malloc(sizeof(SNode));
    ptr_snode->song = ptr_song;
    ptr_snode->next = NULL;
    ptr_snode->prev = NULL;    //unused
    
    int index = ptr_song->index % SIZE_INDEX_TABLE;
    
    //insert the snode into the single linked list at index_directory[index]
    //인덱스 디렉토리에 인덱스 칸에 메달려 있는 단방향 연결리스트 안에 ptr_snode가 가리키고 있는 노드를 insert
    //ex. 계산한 나머지가 2였다면 index_directory의 2번째 칸에 삽입
    
    SNode *p = index_directory[index];
    SNode *q = NULL;    //단방향 정렬된 연결리스트
    while(p!=NULL && strcmp(p->song->title, ptr_song->title) < 0){
        q = p;
        p = p->next;
    }
    
    //add_first
    if(q==NULL){
        ptr_snode->next = p;
        index_directory[index] = ptr_snode;
    }
    //add_after q
    else{
        ptr_snode->next = p;
        q->next = ptr_snode;
    }  
}

3-2. void handle_play()

//main.c

void process_command(){
	...
	else if(strcmp(command, "play")==0)
		  handle_play();
  ...
}

void handle_play(){
    //tokenizing을 계속하는 상황
    char *id_str = strtok(NULL, " ");
    int index = atoi(id_str);
    play(index);
}

//library.c

//노래 번호로 노래 찾기
SNode *find_song(int index){
    SNode *ptr_snode = index_directory[index % SIZE_INDEX_TABLE];
    while(ptr_snode != NULL && ptr_snode->song->index != index)
        ptr_snode = ptr_snode->next;
    
    return ptr_snode;
}

void play(int index){
    SNode *ptr_snode = find_song(index);
    if(ptr_snode == NULL){
        printf("No such song exists.\\n");
    }
    printf("Found the song: %s\\n", ptr_snode->song->title);
}

//library.h

void play(int index);

3-3. 결과

4. 전체 코드

main.c

//
//  main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "string_tools.h"
#include "library.h"

#define BUFFER_LENGTH 200


void process_command();
void handle_add();
void handle_load();
void handle_search();
void handle_play();



int main(){
    initialize();
    handle_load();
    process_command();
}

void handle_load(){
    char buffer[BUFFER_LENGTH];
    
    printf("Data file name ?  ");
    
    //data 파일을 로드하지 않겠다
    if(read_line(stdin, buffer, BUFFER_LENGTH) <=0)
        return;
    
    char filePath[BUFFER_LENGTH] = "/ ~ 파일주소 ~ /";
    char *file = NULL;
    file = strcat(filePath, buffer);

    FILE *fp = fopen(filePath, "r");
//    File *fp = fopen(buffer, "r");
    //사용자가 입력한 파일이 존재하지 않는다면
    if (fp==NULL){
        printf("No such file exists. \n");
        return;
    }
    
    load(fp);
    fclose(fp);
    
    
}

void process_command(){
    
    char command_line[BUFFER_LENGTH];    //한 라인의 데이터를 읽어올 데이터 배열
    char *command;
    while(1){       //무한 루프
        printf("$ ");    //prompt 출력
        
        //사용자의 입력을 라인단위로 받음 - 실제로 읽은 길이를 리턴
        //stdin - 표준 입력 파일로 부터
        //리턴값이 0이하라면 사용자가 입력을 하지 않고 Enter
        if(read_line(stdin, command_line, BUFFER_LENGTH) <=0)
            continue;
        
        command = strtok(command_line, " ");
        if(strcmp(command, "add")==0)
            handle_add();
        else if(strcmp(command, "search")==0)
            handle_search();
//        else if(strcmp(command, "remove")==0)
//            handle_remove();
        else if(strcmp(command, "status")==0)
            status();
        else if(strcmp(command, "play")==0)
            handle_play();
//        else if(strcmp(command, "save")==0)
//            handle_save();
        else if(strcmp(command, "exit")==0)
            break;
    }
}




void handle_add(){
    
    char buffer[BUFFER_LENGTH];
    char *artist = NULL, *title = NULL, *path = NULL;
    
    printf("    Artist: ");
    if(read_line(stdin, buffer, BUFFER_LENGTH)>0)
        artist = strdup(buffer);        //buffer에 저장한 값을 복사해서 대입
    
    printf("    Title: ");
    if(read_line(stdin, buffer, BUFFER_LENGTH)>0)
        title = strdup(buffer);
    
    printf("    Path: ");
    if(read_line(stdin, buffer, BUFFER_LENGTH)>0)
        path = strdup(buffer);
    
    
    //테스트 삼아 컴파일 에러 점검
//    printf("%s  %s  %s\n", artist, title, path);
    
    //add to the music library
    add_song(artist, title, path);
}

void handle_search(){
    char name[BUFFER_LENGTH], title[BUFFER_LENGTH];
    printf("    Artist: ");
    if(read_line(stdin, name, BUFFER_LENGTH) <= 0){
        printf("    Artist name required.\n");
        return;
    }

    //제목을 입력하면 해당 노래만 출력
    //제목을 입력하지 않으면 가수이름으로 검색 ~ 가수의 모든 노래 출력
    printf("    Title: ");
    int title_len = read_line(stdin, title, BUFFER_LENGTH);

    if(title_len <= 0)
        //이름으로만 검색
        search_song_artist(name);
    else
        search_song(name, title);
}

void handle_play(){
    //tokenizing을 계속하는 상황
    char *id_str = strtok(NULL, " ");
    int index = atoi(id_str);
    play(index);
}

library.h

//
//  library.h

#ifndef LIBRARY_H
#define LIBRARY_H

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


//타입정의는 일반적으로 헤더파일에 정의
//순환적인 순서 -> 구조체를 정의하기 전에 typedef를 먼저
typedef struct song Song;
typedef struct snode SNode;
typedef struct artist Artist;


struct song{
    Artist *artist;
    char *title;
    char *path;
    int index;
};

struct snode{
    struct snode *next, *prev;
    Song *song;    //SNode는 하나의 Song을 거느리고 있다
};

struct artist {
    char *name;
    struct Artist *next;
    SNode *head, *tail;
};

void initialize();
void add_song(char *artist, char *title, char *path);
void status();
void load(FILE *fp);
void search_song(char *artist, char *title);
void search_song_artist(char *artist);
void play(int index);


#endif /* LIBRARY_H */

library.c

//
//  library.c


#include "library.h"
#include "string_tools.h"

#define NUM_CHARS 256    //한 바이트가 가질 수 있는 모든 값(2^8)
#define SIZE_INDEX_TABLE 100
#define BUFFER_LENGTH 200


//공유하지 않는 다면 소스코드 파일에 정의
//영어 뿐만 아니라 한글까지 표현 && 한 글자로 이니셜 => 256
Artist *artist_directory[NUM_CHARS];
int num_index = 0;

SNode *index_directory[SIZE_INDEX_TABLE];

//add하기 전 초기화 -> main에서 호출
void initialize(){
    for(int i=0; i<NUM_CHARS; i++)
        artist_directory[i] = NULL;
    
    for(int i=0; i<SIZE_INDEX_TABLE; i++)
        index_directory[i] = NULL;
}

void load(FILE *fp) {
    char buffer[BUFFER_LENGTH];    //한 라인의 데이터를 읽어올 데이터 배열
    char *name, *title, *path;
    while(1){       //무한 루프
        //끝에 도달 - 종료
        if(read_line(fp, buffer, BUFFER_LENGTH) <=0)
            break;
        
        name = strtok(buffer, "#");
        if(strcmp(name, " ")==0)
            name = NULL;
        else
            name = strdup(name);
        
        title = strtok(NULL, "#");
        if(strcmp(title, " ")==0)
            title = NULL;
        else
            title = strdup(title);
      
        path = strtok(NULL, "#");
        if(strcmp(path, " ")==0)
            path = NULL;
        else
            path = strdup(path);
    
//        printf("%s %s % s\n", name, title, path);
        add_song(name, title, path);
    }
}



Artist *find_artist(char *name){
    //이름의 첫 글자를 배열 인덱스로
    Artist *p = artist_directory[(unsigned char)name[0]];     //인덱스의 첫 번째 artist
    //name[0]: 00000000 ~ 11111111 사이의 값 -> 배열의 인덱스
    //(unsigned char): 8비트의 첫 번째 자리가 1로 시작하는 경우 -> 음수 를 방지하기 위해
    
    //이름은 알파벳순 정렬이기 때문에 strcmp 값이 적을 때까지만 루프를 순환
    // strcmp(p->name, name) != 0 : 조건은 같은 이름을 찾을 때 까지 루프를 순환
    while(p!=NULL && strcmp(p->name, name) < 0)
        p = p->next;
    
    if(p!=NULL && strcmp(p->name, name) == 0)
        return p;
    else
        return NULL;
}

Artist *create_artist_instance(char *name){
    Artist *ptr_artist = (Artist *)malloc(sizeof(Artist));
    ptr_artist->name = name;
    ptr_artist->head = NULL;
    ptr_artist->tail = NULL;
    ptr_artist->next = NULL;
    return ptr_artist;
}

Artist *add_artist(char *name){
    Artist * ptr_artist = create_artist_instance(name);
    //p는 head 노드의 주소를 가지게 됨
    Artist *p = artist_directory[(unsigned char)name[0]];    //first node
    Artist *q = NULL;
    
    //ordered_list
    while(p!=NULL && strcmp(p->name, name) <0 ){
        q = p;
        p = p->next;
    }
    
    //empty list
    if(p==NULL && q==NULL){
        artist_directory[(unsigned char)name[0]] = ptr_artist;    //유일한 노드
    }
    //add at the front: 새로운 노드를 제일 앞에
    else if(q==NULL){
        ptr_artist->next = artist_directory[(unsigned char)name[0]];
        artist_directory[(unsigned char)name[0]] = ptr_artist;
    }
    else{
        //add_after
        ptr_artist->next = p;
        q->next = ptr_artist;
        
    }
    
    return ptr_artist;
    
    /* if add_first
    ptr_artist -> next = artist_directory[(unsigned char)name[0]];
    artist_directory[(unsigned char)name[0]]; = ptr_artist;
  */
}

Song * create_song_instance(Artist *ptr_artist, char *title, char *path){
    Song *ptr_song = (Song*)malloc(sizeof(Song));
    ptr_song->artist = ptr_artist;
    ptr_song->title = title;
    ptr_song->path = path;
    ptr_song->index = num_index;    //모든 노래들이 서로 다른 index값을 가져야 한다
    num_index++;
    
    return ptr_song;
}

void insert_node(Artist *ptr_artist, SNode *ptr_snode){
    //ordered by title
    SNode *p = ptr_artist->head;
    while(p!=NULL && strcmp(p->song->title, ptr_snode->song->title)<0)
        p=p->next;
    
    //add ptr_snode before p
    //case 1. empty
    if(ptr_artist->head == NULL){
        ptr_artist->head = ptr_snode;
        ptr_artist->tail = ptr_snode;
    }
    //case 2. at the front
    else if(p==ptr_artist->head){
        ptr_snode->next = ptr_artist->head;
        ptr_artist->head->prev = ptr_snode;
        ptr_artist->head = ptr_snode;
    }
    //case 3. at the end
    else if(p==NULL){
        ptr_snode->prev = ptr_artist->tail;
        ptr_artist->tail->next = ptr_snode;
        ptr_artist->tail =ptr_snode;
    }
    //case 4. in the middle
    else{
        ptr_snode->next = p;
        ptr_snode->prev = p->prev;
        p->prev->next = ptr_snode;
        p->prev = ptr_snode;
    }
}

void insert_to_index_directory(Song *ptr_song){
    SNode *ptr_snode = (SNode *)malloc(sizeof(SNode));
    ptr_snode->song = ptr_song;
    ptr_snode->next = NULL;
    ptr_snode->prev = NULL;    //unused
    
    int index = ptr_song->index % SIZE_INDEX_TABLE;
    
    //insert the snode into the single linked list at index_directory[index]
    //인덱스 디렉토리에 인덱스 칸에 메달려 있는 단방향 연결리스트 안에 ptr_snode가 가리키고 있는 노드를 insert
    //ex. 계산한 나머지가 2였다면 index_directory의 2번째 칸에 삽입
    
    SNode *p = index_directory[index];
    SNode *q = NULL;    //단방향 정렬된 연결리스트
    while(p!=NULL && strcmp(p->song->title, ptr_song->title) < 0){
        q = p;
        p = p->next;
    }
    
    //add_first
    if(q==NULL){
        ptr_snode->next = p;
        index_directory[index] = ptr_snode;
    }
    //add_after q
    else{
        ptr_snode->next = p;
        q->next = ptr_snode;
    }
}


void add_song(char *artist, char *title, char *path){
    //case 1. artist가 artist_directory에 이미 존재 -> song을 추가
    //case 2. 존재하지 않는 경우 -> artist를 추가 -> song 추가
    
    //artist가 존재하는지 부터 검색 - 존재하지 않으면 NULL 리턴
    Artist *ptr_artist = find_artist(artist);
    
    if(ptr_artist == NULL){
        //artist_directory에 artist 등록하고 주소 리턴하기
        ptr_artist = add_artist(artist);
    }
    
    //add the song to the artist pointed by ptr_artist
    //prt_artist는 값을 가지고, song을 add할 수 있다
    Song *ptr_song = create_song_instance(ptr_artist, title, path);
    //각각의 Song은 자신을 거느리고 있는 SNode를 가지고 있다, SNode는 이중연결리스트
    SNode *ptr_snode = (SNode *)malloc(sizeof(SNode));
    ptr_snode->song = ptr_song;
    ptr_snode->next = NULL;
    ptr_snode->prev = NULL;
    
    
    //ptr_artist에 ptr_snode 넣기
    insert_node(ptr_artist, ptr_snode);
    
    //index_directory에도 추가
    insert_to_index_directory(ptr_song);
}


void print_song(Song *ptr_song){
    printf("    %d: %s, %s\n", ptr_song->index, ptr_song->title, ptr_song->path);
}

//p가 가리키는 artist를 출력
void print_artist(Artist *p){
    printf("%s\n", p->name);
    SNode *ptr_snode = p->head;
    while(ptr_snode !=NULL){
        print_song(ptr_snode->song);
        ptr_snode=ptr_snode->next;
    }
}


void status(){
    for (int i=0; i<NUM_CHARS;i++){
            Artist *p = artist_directory[i];
        while(p!=NULL){
            print_artist(p);
            p=p->next;
        }
    }
}

//artist 이름과 노래 제목으로 snode를 찾는 함수 분리하기
SNode *find_snode(Artist *ptr_artist, char *title){
    SNode *ptr_snode = ptr_artist->head;
    //노래제목은 알파벳 순 정렬
    while(ptr_snode != NULL && strcmp(ptr_snode->song->title, title) < 0)
        ptr_snode = ptr_snode->next;
    
    if(ptr_snode != NULL && strcmp(ptr_snode->song->title, title) == 0)
        return ptr_snode;
    else
        return NULL;
}


void search_song(char *artist, char *title){
    Artist *ptr_artist = find_artist(artist);
    
    if(ptr_artist == NULL){
        printf("No such artist exists.\n");
        return;
    }

    SNode *ptr_snode = find_snode(ptr_artist, title);
    
    if(ptr_snode != NULL){
        printf("Found:\n");
        print_song(ptr_snode->song);
    }
    else{
        printf("No such song exists.\n");
        return;
    }
}

void search_song_artist(char *artist){
    Artist *ptr_artist = find_artist(artist);
    
    if(ptr_artist == NULL){
        printf("No such artist exists.\n");
        return;
    }
    
    printf("Found:\n");
    print_artist(ptr_artist);
}

//노래 번호로 노래 찾기
SNode *find_song(int index){
    SNode *ptr_snode = index_directory[index % SIZE_INDEX_TABLE];
    while(ptr_snode != NULL && ptr_snode->song->index != index)
        ptr_snode = ptr_snode->next;
    
    return ptr_snode;
}

void play(int index){
    SNode *ptr_snode = find_song(index);
    if(ptr_snode == NULL){
        printf("No such song exists.\n");
    }
    printf("Found the song: %s\n", ptr_snode->song->title);
}

부경대학교 권오흠 교수님의 [c로 배우는 자료구조 및 여러 가지 예제 실습] 강의 정리입니다. 감사합니다.

https://www.youtube.com/watch?v=8e6PKnbj5Vo&t=2149s

728x90

'CS > 자료구조' 카테고리의 다른 글

[자료구조 - C언어] 자료구조 제14강: Music Library Program(10) (0)	2022.11.08
[자료구조 - C언어] 자료구조 제14강: Music Library Program(9) (0)	2022.11.07
[자료구조 - C언어] 자료구조 제14강: Music Library Program(7) (0)	2022.11.04
[자료구조 - C언어] 자료구조 제14강: Music Library Program(6) (0)	2022.11.04
[자료구조 - C언어] 자료구조 제14강: Music Library Program(5) (0)	2022.10.29

무말랭이 떡볶이 존맛, 신전 로제도

무말랭이 떡볶이 존맛, 신전 로제도

태그

최근글

댓글

공지사항

아카이브

0. 실행 예

1. 검색함수 분리하기

1-1. SNode find_snode(Artist ptr_artist, char *title)

1-2. void search_song(char artist, char title) 수정

1-3. 결과

2. 프로토타입의 위치

3. play 구현하기

3-1. index_directory에 Song 추가하기

3-2. void handle_play()

3-3. 결과

4. 전체 코드

'CS > 자료구조' 카테고리의 다른 글

관련글

티스토리툴바

무말랭이 떡볶이 존맛, 신전 로제도

태그

최근글

댓글

공지사항

아카이브

0. 실행 예

1. 검색함수 분리하기

1-1. SNode *find_snode(Artist *ptr_artist, char *title)

1-2. void search_song(char *artist, char *title) 수정

1-3. 결과

2. 프로토타입의 위치

3. play 구현하기

3-1. index_directory에 Song 추가하기

3-2. void handle_play()

3-3. 결과

4. 전체 코드

'CS > 자료구조' 카테고리의 다른 글

관련글

티스토리툴바

1-1. SNode find_snode(Artist ptr_artist, char *title)

1-2. void search_song(char artist, char title) 수정