資料 構造

위키百科, 우리 모두의 百科事典.

해시 테이블 로 알려진 資料 構造
李瑱 트리 의 예

資料構造 (資料構造, 英語 : data structure )는 컴퓨터 科學 에서 效率的인 接近 및 修正을 可能케 하는 資料의 組織, 管理, 貯藏을 意味한다. [1] [2] [3] 더 正確히 말해, 資料 構造는 데이터 값의 모임, 또 데이터 間의 關係, 그리고 데이터에 適用할 수 있는 函數나 命令을 意味한다. [4] 愼重히 選擇한 資料構造는 보다 效率的인 알고리즘 을 使用할 수 있게 한다. 이러한 資料構造의 選擇問題는 大槪 抽象 資料型 의 選擇으로부터 始作하는 境遇가 많다. 效果的으로 設計된 資料構造는 實行時間 或은 메모리 容量과 같은 資源을 最小限으로 使用하면서 演算을 遂行하도록 해준다.

資料構造에는 여러 種類가 있으며, 이러한 各各의 資料構造는 各自의 年産 및 目的에 맞추어져 있다. 例를 들어 B-트리 는 데이터베이스에 效率的이며, 라우팅 테이블 은 네트워크(인터넷, 인트라넷)에 一般的이다.

多樣한 프로그램을 設計할 때, 어떠한 資料構造를 選擇할지는 가장 優先的으로 考慮되어야 한다. 이는 큰 시스템을 製作할 때 具現의 難易度나 最終 結果物의 性能이 資料構造에 크게 依存한다는 것을 많은 經驗이 뒷받침하기 때문이다. 一旦 資料構造가 選擇되면 適用할 알고리즘 은 相對的으로 明確해지기 마련이다. 때로는 反對 順序로 定해지기도 하는데, 이는 目標로 하는 演算이 特定한 알고리즘을 반드시 必要로 하며, 該當 알고리즘은 特定 資料構造에서 가장 나은 性能을 發揮할 때와 같은 境遇이다. 어떠한 境遇든, 適切한 資料構造의 選擇은 必須的이다.

이러한 觀點은 알고리즘보다 資料構造가 보다 重要한 要素로 適用되는 많은 定型化된 開發論 그리고 프로그래밍 言語 의 開發을 觸發시켰다. 大部分의 言語는 一定 水準의 모듈槪念을 가지고 있으며, 이는 資料構造가 檢證된 具現은 감춘 채 인터페이스만을 利用하여 다양한 프로그램에서 使用되는 것을 可能하게 해준다. C++ , 자바 와 같은 客體志向 프로그래밍 言語는 特別히 이러한 目的으로 客體를 使用한다.

이러한 資料構造의 重要性으로 말미암아, 最近의 프로그래밍 言語 및 開發 環境은 다양한 標準 라이브러리 를 提供하고 있다. 例로, C++의 標準 템플릿 라이브러리 나 자바의 자바 API , 마이크로소프트 .NET 과 같은 것들을 들 수 있다.

資料構造에서 가장 기초적인 單位는 行列 , 레코드 , 유니온 , 參照 와 같은 것이다. 例를 들어, Nullable 參照는 參照와 유니온의 組合으로 나타낼 수 있으며, 가장 單純한 資料構造 가운데 하나인 連結 리스트 는 레코드와 Nullable 參照로 나타낼 수 있다.

分類 [ 編輯 ]

資料의 特性과 크기, 主要 使用法과 遂行하는 演算의 種類, 具現에 必要한 記憶 空間 크기에 따라 여러 가지 種類의 資料構造 中 하나를 選擇할 수 있다. 資料構造의 種類로는 資料兄의 따라 分類하는 單純 構造와 資料 間 關係가 1 對 1人 線形 構造, 1 對 다 或은 다 대 다 構造인 非線形 構造, 마지막으로 파일 構造가 있다. [5]

具現에 따라 [ 編輯 ]

  • 配列 - 가장 一般的인 構造이다. 메모리 上에 같은 타입의 資料가 連續的으로 貯藏된다. 資料값을 나타내는 가장 작은 單位가 資料를 다루는 單位이다.
  • 튜플 - 둘 以上의 資料兄을 묶음으로 다루는 構造이다.
  • 連結 리스트 - 노드를 單位로 한다. 노드는 資料와 다음 노드를 가리키는 參照값으로 構成되어 있다. 노드가 다음 노드로 아무것도 가리키지 않으면 리스트의 끝이다.
  • 原形 連結 리스트 - 各 노드는 다음 노드를 가리키고, 마지막 노드가 처음 노드를 가리키는 連結 리스트이다.
  • 二重 連結 리스트 - 各 노드는 以前 노드와 다음 노드를 가리키는 參照값으로 構成된다. 처음 노드의 移轉 노드와 마지막 노드의 다음 노드는 없다.
  • 換刑 二重 連結 리스트 - 처음 노드가 移轉 노드로 마지막 노드를 가리키고, 마지막 노드가 다음 노드로 처음 노드를 가리키는 이中 連結 리스트이다.
  • 해시 테이블 - 個體가 해시 값에 따라 인덱싱된다.

形態에 따라 [ 編輯 ]

  • 線形 構造
  • 스택 - 스택 資料構造에 먼저 貯藏된 것이 꺼내어 쓸 때는 第一 나중에 나온다. 反對로, 가장 最近에 貯藏된 것이 꺼내어 쓸 때는 第一 먼저 나온다. 萬若, 資料들의 羅列 順序를 바꾸고 싶다면 스택에 집어 넣었다가 꺼내면 逆順으로 바뀐다.
  • 큐 - 스택과 反對로 큐 資料構造에 먼저 貯藏된 것이 第一 먼저 나온다. 反對로, 가장 나중에 貯藏된 것이 꺼내어 쓸 때는 가장 나중에 나온다.
  • 換刑 큐 - 限定된 길이 안에서 附隨的인 作業 없이 읽고 쓰기를 할 수 있는 큐이다.
  • 덱 - 兩쪽에서 넣기와 빼기를 할 수 있는 一般化된 線形 構造이다.
  • 非線型 構造
  • 그래프 - 꼭짓點과 꼭짓點을 잇는 便으로 構成된다.
  • 有香 그래프 , 무향 그래프 - 變異 方向性을 갖는지 갖지 않는지에 따른 그래프의 分類이다.무향 그래프의 境遇, 循環 이 없는 連結 그래프를 뜻한다. 有香 그래프의 境遇 邊의 方向은 普通 父母를 가리키도록 具現된다.
  • 트리 - 뿌리와, 뿌리 또는 다른 꼭짓點을 單 하나의 父母로 갖는 꼭짓點들로 이루어진 構造. 父母 子息 關係는 便으로 表現된다.
  • 李瑱 트리 - 子息이 最大 두 個인 트리.
    • 힙 - 이진트리의 一種으로 이진트리에 어떤 特性을 附與한 것이라 할 수 있다.

같이 보기 [ 編輯 ]

위키미디어 共用 에 關聯된
미디어 分類가 있습니다.

各州 [ 編輯 ]

  1. ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). 《Introduction to Algorithms, Third Edition》 3板. The MIT Press. ISBN   978-0262033848 .  
  2. ↑ Black, Paul E. (2004年 12月 15日). 〈data structure〉 . Pieterse, Vreda; Black, Paul E. 《Dictionary of Algorithms and Data Structures [online]》. National Institute of Standards and Technology . 2018年 11月 6日에 確認함 .  
  3. ↑ 〈Data structure〉 . 《Encyclopaedia Britannica》. 2017年 4月 17日 . 2018年 11月 6日에 確認함 .  
  4. ↑ Wegner, Peter; Reilly, Edwin D. (2003年 8月 29日). 《Encyclopedia of Computer Science》 . Chichester, UK: John Wiley and Sons. 507?512쪽. ISBN   978-0470864128 .  
  5. ↑ 이지영. 《C로 배우는 쉬운 資料構造》. 한빛미디어. 30쪽.  
元本 住所 " https://ko.wikipedia.org/w/index.php?title=資料_救助&oldid=35741414 "