컴공 일기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를 선물하세요.
-
#07년생#08년생#독학생 오르비의 주인이 될 기회 37 36
-
전 3시간 부침가루랑 계란하고 2 0
5만원받음 ㅁㅌㅊ
-
표점 0 0
이번에도 표점 비슷하려나 미적 확통
-
이거 임티 왤케 열받지 3 0
진짜 찢어버리고싶게
-
오 랜만에 이륙이구나 2 0
-
붙으면 어디 감?
-
캬 내일 차례 지내서 2 0
동태전 부치는거 도와서 하나 얻어먹었는데 존맛이다 ㄹㅇ
-
수학 실전개념 커리 3 0
고3 정시파이터입니다. 수1,2 모두 이미지 선생님 미친개념 수강했고, 연습문제...
-
-
과외생들이 반포에 밀집해있는데 5 1
여긴 올때마다 말이안됨 부자냄새남
-
내년엔 수능쳐서 연서한뱃따야겠다 10 1
-
2409 수학이 0 0
22번 30번만 킬러로 나왔으면 ㄹㅇ 개빡셌을 시험구성인데 2211수학 상위호환으로
-
저는혈압을잴수록내려가요 0 1
처음 잴때는 긴장해서 155/105 이렇게 나왔다가 재면 잴수록 조금씩 떨어져서...
-
는 별로 연하는 좀
-
평소 무뚜뚝하기로 유명한 과 선배한테 연락이 왔다 5 3
선톡도 잘 안 하구 성격도 무뚜뚝한데 (동성임) 새해 복 많이 받으라고 먼저 연락...
-
학자금대출 받아서 주로 뭐하나요? 10 1
-
경희대 서울캠 자율전공 최초합 중대 자연대 전화추합 마지막 등록은 중앙대 입결이나...
-
똥ㄱ고 0 0
똥꼬꼬드ㅡㅡㅡㅡ
-
24수능 좋긴함 6 1
사탐 만표 평균 67.2 원과목 만표 평균 68.75 투과목 만표 평균 74.75
-
9년 전의 오르비 4 1
https://orbi.kr/00011161813 이때는 배지 안줬는데...
-
27수능에서 생윤사문 표본끼리 지지고 볶다가 갑자기 28수능 이과 최상위권이랑 같이...
-
확통런 김범준vs김기현 0 0
김기현 수1수2듣는중 미적에서 확통런하는데 김범준vs김기현 어떤게 나음? 확통만...
-
머리 개길다 4 1
좀 자를까 …
-
빅가이 빅가이 2 0
스폰지밥 빅가이 팬츠 오케이
-
선착1 4 1
띠하기니의 사랑이 담진 진한 뽑보
-
아니 문제 보기에는 쉬워보여서 풀면 케이스 구하고 범위 구하고 ㄹㅇ 예술임 이건 ㄹㅇ 개지림
-
15년전의 오르비 2 0
https://orbi.kr/000641550/%255B%ED%95%B4%EC%99%...
-
현역 수시공부 정시공부 비율 1 0
정시가 잘나오는걸 일단 목표로 하고 있긴한데 수시도 안버리고 챙길 예정입니다...
-
나보다 심박수 빠른사람 있음? 20 0
커피 안 마셨을 땐데
-
브루노마스는 대체 0 0
어떤 영빨을 받아 작곡했길래 이런 곡을 썼을까 들어도 들어도 안질림
-
에리카 공대 붙었는데.. 3 0
그냥저냥 다닐려했더니 여기서 유명한 에리카 훌리때문에 에리카 ㅈㄴ까이는거보고 학교...
-
중대 폭났나요?? 7 0
-
스노보드 금메달 딴 선수 좋은 곳 사시네 부럽당
-
경남 고성군에 사업장을 둔 SK오션플랜트가 미 해국 MRO(정비·보수·개조) 시장에...
-
볶음밥에 마늘이 너무 많아 1 0
혹시 나?
-
4시간 금연했음 0 0
후우 씨발
-
오늘은 좀 멀리 나갈거에요 4 0
목동가서 푸파하다가 교보 갈거임ㅋㅋㅋㅋ
-
엄지와 중지 너클 부분이 정중앙에 맞는단 느낌으로
-
약대 졸업하자마자 집안에서 개국시켜준다고 가정할때
-
씻어야하나 3 0
저녁에 약속있는데 흠
-
국수 만표 밸런스 잘 맞췄고 영어도 1등급 4-5퍼센특ㅎ 원장연 기준 탐구 만표도 다 비슷함
-
오소독스 기준 왼쪽 다리 근육이 중요함 ㄹㅇ
-
초록 미쿠 4 0
노란미쿠 빨간미쿠
-
작수 2따리 김범준 1 0
통통 백분위 91이었는데 올해 공통 김범준 들으려고 하거든여 ㄱㅊ을까요 공통이...
-
동성혼을 합헌이라 하자 오히려 동성애 반대가 많아졌다니 11 3
이럴수가...
-
메리 크리스마스 2 0
다들 송편 드셈
-
22개정과탐 선행 5 0
수학 어느 진도까지 나가야 화학 물리를 소화할 수 있나요?
-
01년생 오빠랑 사귀고싶음뇨 4 0
누나도좋음
-
재수 사탐 0 0
현역일 때 직업탐구 공부하다가 재수할 때 사회탐구 하려고 하는데 어떤 거 하는게...
-
시대인재 모의고사 0 0
국어 단과 수업을 듣는데 다른 과목 서바이벌 엑셀 등 구매 가능한가요??
-
B트리 학교에서 배웠는데.. 기억이...저도 아직 헷갈립니다… 비선형 자료구조라 아무래도 삭제 로직이 굉장히 복잡하고…
심지어 삽입 로직도 꽤 어려운 축에 속하고.. 하지만! 전공자라면 알고는 있어야 할 자료구조랄까요…
아 맞아요
remove 구현이 과제였던거로 기억해요
좀 까다로웠던 기억이..