컴공 일기239
게시글 주소: https://orbi.kr/00066243627
운영체제들이 사용하고 있는 파일시스템의 구조를 흉내내본 코드입니다.
C++의 표준 라이브러리로 구현하기가 쉬운 관계로 자료구조를 N-항트리로 채택하긴 했습니다만 실제 다수의 운영체제에서는
B-트리를 채택하고 있지요. 개인적으로, 많은 자료구조 전공서적들이 B 트리를 다루어주었으면 하는데 좀 아쉽습니다. 물론 입문자 입장에서 꽤 어려운 구조이긴 합니다만.. 그래도, 당장 데이터베이스나 운영체제를 배울 때 무조건 나올 수밖에 없는 중요한 자료구존데…
그런 관계로, 연휴기간 동안에는 B트리 기반으로 자료구조를 바꾸어서, 이 코드를 약간 수정해볼까 합니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//N항 트리
struct n_ary_node
{
string name;
bool is_dir;
vector<n_ary_node*> children;
};
struct file_system
{
using node = n_ary_node;
using node_ptr = node*;
private:
node_ptr root;
node_ptr cwd;
public:
file_system()
{
root = new node{"/", true, {}};
cwd = root; //처음에는 루트를 현재 디렉터리로 설정한다.
}
node_ptr find(const string& path)
{
if(path[0] == '/')
{
return find_impl(root, path.substr(1));
}
else
{
return find_impl(cwd, path);
}
}
private:
node_ptr find_impl(node_ptr directory, const string& path)
{
if(path.empty())
return directory;
auto sep = path.find('/');
string current_path = sep == string::npos ? path : path.substr(0, sep);
string rest_path = sep == string::npos ? "" : path.substr(sep+1);
auto found = find_if(directory->children.begin(), directory->children.end(), [&](const node_ptr child)
{
return child->name == current_path;
});
//현재 디렉터리 내부가 current_path를 포함한다면 즉, path의 첫 번째 디렉터리를 찾았다면
if(found != directory->children.end())
{
//해당 경로로 접속한 후, 계속 탐색한다.
return find_impl(*found, rest_path);
}
//디렉터리나 파일을 찾지 못한 경우 NULL 반환
return NULL;
}
public:
bool add(const string& path, bool is_dir)
{
if(path[0] == '/')
{
return add_impl(root, path.substr(1), is_dir);
}
else
{
return add_impl(cwd, path, is_dir);
}
}
private:
bool add_impl(node_ptr directory, const string& path, bool is_dir)
{
if(not directory->is_dir)
{
cout << directory->name << "은(는) 파일입니다. " << endl;
return false;
}
auto sep = path.find('/');
//path에 '/'가 없는 경우
if(sep == string::npos)
{
auto found = find_if(directory->children.begin(), directory->children.end(), [&](const node_ptr child)
{
return child->name == path;
});
if(found != directory->children.end())
{
cout << directory->name << "에 이미" << path << "이름의 파일/디렉터리가 있습니다." << endl;
return false;
}
directory->children.push_back(new node{path, is_dir, {}});
return true;
}
//path에 '/'가 있는 경우, 즉, 디렉터리 이름을 포함하는 경우
string next_dir = path.substr(0, sep);
auto found = find_if(directory->children.begin(), directory->children.end(), [&](const node_ptr child)
{
return child->name == next_dir && child->is_dir;
});
if(found != directory->children.end())
{
return add_impl(*found, path.substr(sep+1), is_dir);
}
//디렉토리 파일을 찾을 수 없는 경우
cout << directory->name << "에 " << next_dir << "이름의 디렉터리가 없습니다. " << endl;
return false;
}
public:
bool change_dir(const string& path)
{
auto found = find(path);
if(found && found->is_dir)
{
cwd = found;
cout << "현재 디렉토리를 " << cwd->name << "로 이동합니다." << endl;
return true;
}
cout << path << "경로를 찾을 수 없습니다. " << endl;
return false;
}
public:
void show_path(const string& path)
{
auto found = find(path);
if(not found)
{
cout << path << "경로가 존재하지 않습니다" << endl;
return;
}
if(found->is_dir)
{
for(auto child : found->children)
{
cout << (child->is_dir ? "d " : "- ") << child->name << endl;
}
}
else{
cout << "- " << found->name << endl;
}
}
};
int main()
{
file_system fs;
fs.add("usr", true);
fs.add("etc", true);
fs.add("var", true);
fs.add("tmp_file", false);
cout << "\"/\"의 파일/디렉터리 목록: " << endl;
fs.show_path("/");
cout << endl;
fs.change_dir("usr");
fs.add("gilbut", true);
fs.add("gilbut/Downloads", true);
fs.add("gilbut/Downloads/newFile.cpp", false);
cout << "현재 디렉터리에서 usr의 파일 / 디렉터리 목록: " << endl;
fs.show_path("/usr"); // 현재 디렉터리에는 usr 디렉터리가 없으므로 정상적으로 출력하지 못한다.
cout << "\"/usr/gilbut/Downloads\"의 파일/디렉터리 목록" << endl;
fs.show_path("/usr/gilbut/Downloads");
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
초딩때 웩슬러 풀배터리 했던게 집에 남아있는지 모르겠는데 1 0
아동용 웩슬러 4였을거임 아마 시기상 저 4개로 나오는데 언어이해는 꽤 높았고...
-
난 모름 좀 알려줘
-
하루 루틴에 1 1
새르비가 포함되어버렸어 아.
-
헬스장 등록해야하는데 개귀찮 0 0
헬스장 등록하러 가기도 귀찮아서 가방에 두꺼운책 넣어가지고 덤벨 비스무리하게 만들어서 운동함
-
수능 150일 남았다 7 1
님들의 100일은 내가 접수해서 150일인거임
-
나름 예시문항이 단원 순서대로 배치된걸 감안하면 25번 에너지 자원에 이게 그대로...
-
전 아이큐 낮아서 2 0
수학이 안오르는거같던데
-
현타 개씨게 옴 0 0
아직 코코이 안침
-
시대재종 1 0
시대재종 다니는데.. 진짜 서울대 가고싶은데.. 왤케 조바심이 나지.. 수학도...
-
고작 그 숫자에 내 능력의 한계를 평가하는 나 자신을 보니 어느순간 현타가 왔음...
-
IQ높다고 수능잘보고 대학잘가는거면 멘사는 의사협회임?
-
모든 것의 창조, 그 끝에는 0 0
어떠한 생기도, 감정도, 없음이란 개념조차 없어진 깊이를 알 수 없는 공허만이 기다릴 뿐이다
-
눈치게임 10 0
시 작.
-
내가 아이큐만 따지면 아마 오르비에서 꽤나 낮을거임 7 1
전에 인터넷에서 쟀을때 98이었음 그래서 난 그런걸 안믿음
-
국어 끝 생윤시작 0 0
가보자잇
-
갑자기생각난건데 14 1
오르비에 최상위권이 이렇게 많은데 그럼 오르비언이 검사도 되고 판사도 되는거ㄴ가...
-
좀 무계지언한 이야기긴 한데 3 3
수능만점 받아도 오르비에는 밝히지 않는걸로 근데 ㅅㅂ 고교 선택과목 다 까져서 의미가 있을려나
-
죽자 3 0
-
지피티 5.4 pro 후기 3 1
얘는 아직도 한국어 구사 수준이 븅딱임근데 요즘 제미나이가 얌전한데 내가 볼 때...
-
헤이헤이 대답해줘 8 1
아무도 없는걸까?
-
영어나 국어는 할수있는데 수학은 걍 못하겠음
-
독서 인강 추천 2 0
대성쓰고있어요 유대종선생님 독해 독서 듣고있는데 너무 어렵습니다 ㅜㅜ 추천부탁드려요
-
고3재수들 사탐런 많이함? 6 1
틀딱이라 07 08들 트렌드 못따라감
-
우리는 이미 특이점 초반부에 있다고 생각함 나도 이미 출제 관련 터미널 프로토타입은...
-
의견을 수렴해주세요
-
근데난클린유저라 특정당해도 딱히 상관없지않을까 20 0
라는생각을해봣어요
-
목에 빅맥 끼운 목소리남 5 1
시발
-
김동욱 문학 ㅁㅌㅊ? 3 0
ㅁㅌㅊ?
-
이 글의 댓글을 18개로 맞춰주세요 22 0
-
잘자요 0 0
늘 건강하시구요
-
오 이거 부남옷 아님?? 7 0
자꾸 이런거만 보이넹
-
통사 지리 1 0
ㅈㄴ 어려운데 어케 공부해야함 내신
-
독서로 치면 대부분 단일 지문 하나(에서 5~10개) 정도로 영역 구분 없이...
-
오노추 1 1
-
본인 통사 통과 틀린 것들 1 0
통사 늪이 습지인가? 이지랄 5분하다가 틀림 사상이랑 이 문제 두 개 남았고 답...
-
메가스터디 N제 3 0
좋아? 후기 남겨보셈 진짜 풀거 없어지면 푸려고
-
으아 목이 너무 아프다 10 1
-
저능해졌어요 6 2
우땨따
-
통사모고가 어려우면 범죄라고? 2 0
나는 극악무도한 범죄자다
-
객관적으로 진짜 이걸 이길 문제는 없다 싶은것도 이성으론 좋다는걸 알지만 감성으론...
-
통과, 통사의 모순 3 0
.5점 의미 1도 없음 차피 표점 산출 마지막 단계에서 정수로 반올림하기 때문...
-
진짜 통사 통과 안어렵네? 18 1
내가 지리 제외 다른거 안익숙해서 그런지 통사가 오히려 어려워보인다 근데 이...
-
오루비잘자 5 1
-
오랜만입니다 14 1
-
내신교재로 기출픽쓸꺼야 3 0
좋아?
-
합답형,빈칸보고 얼탱이없어서 현웃터졌는데 22번 점화식아닌거보고 당황했던 내 저열한...
-
헤해해
-
통사 통과 고1 모고 어려움? 18 0
안쳐봐서 모르겠네
-
의외로 0 1
개념완성 전국연합학력평가 ( 통과 ) 개조음.. ㅇㅇ 가볍고
-
코코이쳐야겠다 0 0
손씻기
B트리 학교에서 배웠는데.. 기억이...저도 아직 헷갈립니다… 비선형 자료구조라 아무래도 삭제 로직이 굉장히 복잡하고…
심지어 삽입 로직도 꽤 어려운 축에 속하고.. 하지만! 전공자라면 알고는 있어야 할 자료구조랄까요…
아 맞아요
remove 구현이 과제였던거로 기억해요
좀 까다로웠던 기억이..