나는 진지하게 프로그래밍한 지 이미 1년이 되었다.그 동안 저는python 기술을 배웠고 HTML/CSS에 관한 유튜브 과정을 마쳤으며 자바스크립트를 배웠고 React 응용 프로그램을 개발했습니다.지금까지 모든 것이 좋았다.나는 코드를 작성하는 것을 좋아한다. 이 여정은 나로 하여금 뇌의 기술과 창조성을 빈틈없이 통합시킬 수 있게 한다.그러나 최근에 나는 흔들리지 않는 문제에 부딪혔다. 나의 프로그램은 성능에 대해 최적화를 했습니까?
호기심은 나로 하여금 컴퓨터 과학의 기초 지식을 더욱 깊이 연구하게 했다. 나는 이것이 내가 이전에 공부했던 단계에서 부족한 것이라고 생각한다.물론 나는 코드 쓰는 것을 배우고 있다.귀신이 곡할 노릇이다. 나는 심지어'교정지옥'을 벗어나 곧 스스로 프로젝트를 하기 시작했다.그러나 나는 내가 가장 좋은 코드를 쓰고 있다는 것을 확신하기 위해 필요한 이론이 부족하다.
데이터 구조에 대한 소개를 입력하십시오.지난 몇 달 동안 나는 낡은 스탠퍼드 CS106B 과정을 주목해 왔다.이 과정은 당신이 어떻게 인코딩을 하는지 아는 사람에서 컴퓨터로 문제를 해결하는 방법을 아는 사람으로 바뀌게 해 준다.

데이터 구조

그렇다면 당신은 왜 데이터 구조를 배워야 합니까?집을 지을 때 많은 공구들이 독특한 용도로 사용되고, 컴퓨터 과학의 각종 문제를 해결할 때 다양한 데이터 구조도 유용하다.여기서, 나는 C++로 이루어진 창고, 대기열, 집합, 비추는 이론과 응용을 간략하게 토론할 것이다.

쌓아올리다

말 그대로 한 무더기의 물건은 한 무더기의 물건이다.이 구조에서는 맨 위에서만 항목을 추가하거나 삭제할 수 있습니다.창고의 순서는'후진선출'또는 마지막으로 들어간 항목이 첫 번째로 나온 항목이라고 한다.

상상해 봐, 너는 시험지를 고치고 있어. 매번 한 부를 완성할 때마다, 너는 시험지를 책상 위에 가지런히 쌓아 놓고 있어.네가 일어서서 그 시험지를 볼 때, 네가 본 첫 번째 장은 네가 마지막으로 평점을 완성한 것이다.마찬가지로, 만약 당신이 다른 새 종이에 점수를 매기고 그것을 종이 더미 안에 넣으면, 그것은 지금 종이 더미의 꼭대기에 있다.창고는 이렇다.
창고에서 세 가지 기본 동작은 top,push,pop입니다.창고에서 'top' 을 호출하면 맨 위의 항목을 검사할 수 있지만 삭제할 수 없습니다.프로젝트를 창고에 밀어 넣으면 맨 위에 놓으세요.창고에서 팝업을 할 때, 맨 위의 항목을 제거합니다.

int main(){
    stack<int> s;
    s.push(1); // s -> {1}
    s.push(2); // s -> {1,2}
    cout << s.top() << endl;
    s.pop(); // s -> {1}
    s.push(3); // s -> {1,3}
    cout << s.top() << endl;
    s.pop(); // s -> {1}
    cout << s.top() << endl;
    return 0;
}

2
3
1

많은 응용 프로그램에서 창고가 유용하다.그 중에서 가장 유행하는 것은 워드프로세서에서 사용하는 취소 기능이다.문서를 변경할 때마다 변경 사항이 스택에 추가됩니다.CMD + Z (또는 Ctrl + Z, 내 윈도우즈 친구) 를 누르면 최신 동작이 창고에서 팝업됩니다.창고의 또 다른 용도는 평형 프로그램의 큰 괄호와 둥근 괄호이다.컴파일러는 창고 데이터 구조를 실현하여 괄호가 일치하는지 확인합니다.

줄을 서다

대열은 또 다른 데이터 구조로 잡화점이나 영화관의 줄 서기와 매우 유사하다.영화관에서 사람들은 줄을 서는 순서에 따라 서비스를 받는다.첫 번째로 줄을 서는 사람이 바로 첫 번째로 표를 받은 사람이다.대기열의 순서를'FIFO'라고 부르거나 첫 번째로 들어간 항목이 첫 번째로 나온 항목이다.

대기열의 기본 조작은 창고의 기본 조작과 매우 비슷하다.대기열로 밀어넣거나, 대기열에서 팝업할 수도 있고, 대기열의 맨 앞과 맨 뒤의 요소를 검사할 수도 있습니다.그러나 차이점은 요소의 대기열(밀어넣기)과 탈퇴(플라이아웃) 순서입니다.원소를 줄을 서서 뒤에 놓고 앞에서 제거합니다.

int main(){
    queue<int> q;
    q.push(1); // q -> {1}
    q.push(2); // q -> {1,2}
    q.push(3); // q -> {1,2,3}
    cout << q.front() << endl; 
    cout << q.back() << endl;
    q.pop(); // q -> {2,3}
    cout << q.front() << endl;
    return 0;
}

1
3
2

창고와 마찬가지로 대열은 각종 문제에서 매우 유용하다.예를 들어, 대기열을 사용하여 프린터 처리 항목의 순서를 지정할 수 있습니다.대기열이 잘하는 또 다른 문제는 광범위한 우선 검색 알고리즘의 실현이다.

컬렉션

집합은 하나의 데이터 구조로 한 그룹의 유일한 값을 나타낸다.집합은 중복항을 포함할 수도 없고, 벡터처럼 색인을 작성할 수도 없다.따라서 집합에서 항목을 추가하고 삭제하는 것은 효과적이다. 벡터와 달리 이런 작업 기간에 다른 요소에 대한 색인을 다시 작성하지 않았기 때문이다.

집합에는 세 가지 주요 조작이 있는데 그것이 바로 삽입, 지우기와 계수이다.[삽입]은 요소를 컬렉션에 추가합니다. 요소가 고유한 경우 [지우기]는 컬렉션에서 요소를 삭제하고 계수는 컬렉션에 요소가 있는지 확인합니다.물론, 너는 텔레비전으로 많은 다른 일을 할 수 있다. 만약 네가 흥미가 있다면 C++ STL reference page.에서 볼 수 있다

int main(){
    set<int> st;
    st.insert(1); // set contains 1
    st.insert(2); // set contains 1,2
    st.insert(2); // 2 is not unique and set is unchanged
    st.insert(3); // set contains 1,2,3
    st.insert(4); // set contains 1,2,3,4
    cout << st.count(2) << endl; // return of 1 -> set contains element
    st.erase(2); // set contains 1,3,4
    cout << st.count(2) << endl; // return of 0 -> set does not contain element
    cout << "--" << endl;
    for (int item : st){
        cout << item << endl;
    }
    return 0;
}

1
0
--
1
3
4

집합은 앞에서 언급한 다른 데이터 구조와 유사하여 특정 상황에서 사용하는 것이 이상적이다.집합을 실현하는 하나의 예는 쇼핑 리스트다.우리는 쇼핑 리스트에 상품을 추가할 수도 있고 삭제할 수도 있지만, 우리는 리스트에 있는 상품의 순서에 진정으로 관심이 없다.관건은 명세서에 있는 모든 물건을 쇼핑 카트에 한 번만 넣는 것이다.또 다른 생각나는 장면은 책 속의 독특한 단어의 수를 정하는 것이다.이 경우 책을 해석하고 모든 단어를 집합에 삽입합니다.집합은 중복 항목을 무시하기 때문에 같은 단어를 여러 번 추가하려고 시도해도 아무런 효과가 없습니다.해석이 끝날 때, 우리는 집합의 항목 수만 계산하여 책의 유일한 단어를 나타낼 수 있다.

지도.

python에 익숙하다면, C++의 맵은python dict 과 비슷합니다.더욱 정식으로 말하면 맵은 키 값이 맞는 데이터 구조를 저장한다.직관적으로 말하면 지도는 사전과 같고 단어는 유일한 키를 대표하며 그에 상응하는 정의는 그들의 값을 대표한다.색인의 개념은 지도에 여전히 존재한다. 비록 '색인' (키) 이 반드시 필요하지는 않지만 int.
맵은 여러 가지 동작을 지원하지만, 주로 키 값 쌍, 삭제 키, 검색 키를 삽입합니다.맵에서 키를 제거하면 해당 키와 연관된 값도 삭제됩니다.

앞의 장면을 고려하면 이 장면은 책 속의 모든 유일한 단어를 찾기 위한 집합을 실현했다.문서에 있는 모든 유일한 단어의 계수를 얻고 싶을 뿐만 아니라, 단어마다 나오는 횟수를 알고 싶을 뿐이라고 상상해 보세요.매핑을 통해 다음과 같은 이점을 얻을 수 있습니다.

// this file is named document.txt

to be or not to be
to be a not

void readFile(const string& filename){
    ifstream file;
    map <string, int> tally;
    file.open(filename);
    string word;
    while (file >> word){
        if (!tally.count(word)){
            // tally.insert({word,1});
            tally[word] = 1; 
        }
        else{
            tally[word]++;
        }
    }
    for (auto& s : tally)  {
    cout << '{' << s.first << ':' << s.second << '}' << endl;
    } 
}

int main(){
    readFile("document.txt");
    return 0;
}

{a:1}
{be:3}
{not:2}
{or:1}
{to:3}

이 간단한 예 외에 지도는 여러 가지 문제에도 광범위하게 사용된다.소셜 미디어 플랫폼의 사용자와 친구 목록을 추적하는 데 사용되는 지도 유형의 구조를 상상할 수 있다.이와 유사하게 지도는 정보를 전화번호부에 저장하는 완벽한 데이터 구조가 될 것이다.지도는 관련 데이터를 저장하는 데 매우 유용하다.

다음 단계

물론 이것은 모든 서로 다른 유형의 데이터 구조의 상세한 목록이 아니다.만약 당신이 더 많은 것을 알고 싶다면, 이 책은 내가 이곳에서 공유한 것보다 더 많은 세부 사항을 제공한다.나는 지금까지 그의 수업에 참가한 적이 없지만, 마티 스트레프는 자료를 소개하는 데 매우 뛰어나다.
만약 당신이 내가 어떻게 프로그래밍에 참여했는지 읽는 것에 흥미가 있다면, 나는 미디어 글을 한 편 썼을 것이다. here.마찬가지로, 만약 당신이 이 분야의 최신 진전을 알고 싶다면, 나의 GitHub를 방문하십시오: https://github.com/michaelarn0ld
계속 인코딩...