專題九：數據結構知識

　　數據結構是計算機軟件的一門基礎課程,計算機科學各個領域及有關的應用軟件都要用到各種數據結構.語言編譯要使用棧、散列表及語法樹;操作系統中用隊列、存儲管理表及目錄樹等;數據庫系統運用線性表、多鏈表及索引樹等進行數據管理;而在人工智能領域，依求解問題性質的差異將涉及到各種不同的數據結構，如廣義表、集合、搜索樹及各種有向圖等等。學習數據結構目的是要熟悉一些最常用的數據結構，明確數據結構內在的邏輯關系，知道它們在計算機中的存儲表示，并結合各種典型應用說明它們在進行各種操作時的動態性質及實際的執行算法，進一步提高軟件計和編程水平。通過對不同存儲結構和相應算法的對比，增強我們根據求解問題的性質選擇合理的數據結構，并將問題求解算法的空間、時間及復雜性控制在一定范圍的能力。

　　軟件設計師考試大綱對數據結構部分的要求是熟練掌握常用數據結構和常用算法，因此，本專題從數據結構的概述出發，對基本的概念引出常用的數據結構類型的介紹和講解，同時在講解各種數據結構中間采用算法與數據結構相結合的方式，在算法步驟中使用數據結構，對數據結構的重點、難點進行了分析，最后講解了與數據結構緊密相關的排序和查找算法，以及一些以往考試題的分析。

　　1. 數據結構概述

　　數據結構研究了計算機需要處理的數據對象和對象之間的關系;刻畫了應用中涉及到的數據的邏輯組織;也描述了數據在計算機中如何存儲、傳送、轉換。

　　學習數據結構注意的問題：

　　n 系統掌握基本數據結構的特點及其不同實現。

　　n 了解并掌握各種數據結構上主要操作的實現及其性能(時間、空間)的分析。

　　n 掌握各種數據結構的使用特性，在算法設計中能夠進行選擇。

　　n 掌握常用的遞歸、回溯、迭代、遞推等方法的設計

　　n 掌握自頂向下、逐步求精的程序設計方法。

　　n 掌握自頂向下、逐步求精的程序設計方法。

　　在學習數據結構的知識之前，我們要了解一下數據結構中的基本概念。

　　數據：對客觀事物的符號表示，在計算機中就是指所有能輸入到計算機中并被計算機程序所處理的符號的總稱。

　　數據項： 是數據的不可分割的最小單位;

　　數據元素：是數據的基本單位，在計算機程序中通常作為一個整體進行處理;一個數據元素可由若干個數據項組成。

　　數據對象：是性質相同的數據元素的集合，是數據的一個子集。

　　數據結構上的基本操作： ◆插入操作 ◆刪除操作 ◆更新操作 ◆查找操作 ◆排序操作

　　數據結構是指數據對象及相互關系和構造方法，一個數據結構B形式上可以用一個二元組表示為B=(A，R)。其中，A是數據結構中的數據(稱為結點)的非空有限集合，R是定義在A上的關系的非空有限集合。

　　根據數據元素之間的關系的不同特性，通常有下列4類基本結構。

　　Ø 集合——結構中的數據元素除了“同屬于一個集合”的關系外，別無其他關系。

　　Ø 線性結構——結構中的數據元素之間存在一個對一個的關系。

　　Ø 樹形結構——結構中的元素之間存在一個對多個的關系。

　　Ø 圖狀結構或網狀結構——結構中的元素之間存在多個對多個的關系。

　　數據結構中，結點與結點間的相互關系是數據的邏輯結構。數據結構在計算機中的表示(又稱為映象)稱為數據的物理結構，也稱存儲結構。

　　數據元素之間的關系在計算機中有兩種不同的表示方式：順序映象和非順序映象，并由此得到兩種不同的存儲結構：順序存儲結構和鏈式存儲結構。

　　任何一個算法的設計取決于選定的數據(邏輯)結構，而算法的實現依賴于采用的存儲結構。

　　數據的邏輯結構分為兩類：

　　線性結構：線性表、棧、隊列和串

　　非線性結構：樹、圖

　　數據的存儲方法有四類：

　　順序存儲方法

　　鏈接存儲方法

　　索引存儲方法

　　散列存儲方法

　　　　　　　計算機軟考軟件設計師練習試題及答案解析匯總