數(shù)據(jù)結構的簡介和線性表及棧隊列和數(shù)組的詳細說明

1.1 引言

兩項基本任務：數(shù)據(jù)表示，數(shù)據(jù)處理

軟件系統(tǒng)生存期：軟件計劃，需求分析，軟件設計，軟件編碼，軟件測試，軟件維護

由一種邏輯結構和一組基本運算構成的整體是實際問題的一種數(shù)學模型，這種數(shù)學模型的建立，選擇和實現(xiàn)是數(shù)據(jù)結構的核心問題。

機外表示 ------邏輯結構 ------存儲結構

處理要求 -----基本運算和運算 -------算法

1.2.1 數(shù)據(jù)，邏輯結構和運算

數(shù)據(jù)：凡是能夠被計算機存儲，加工的對象通稱為數(shù)據(jù)

數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在程序中作為一個整體加以考慮和處理。又稱元素、頂點、結點、記錄。

數(shù)據(jù)項： 數(shù)據(jù)項組成數(shù)據(jù)元素， 但通常不具有完整確定的實際意義， 或不被當作一個整體對待。 又稱字段或域，

是數(shù)據(jù)不可分割的最小標示單位。

1.2.2 數(shù)據(jù)的邏輯結構

邏輯關系：是指數(shù)據(jù)元素之間的關聯(lián)方式，又稱“鄰接關系” 邏輯結構 ：數(shù)據(jù)元素之間邏輯關系的整體稱為邏輯結構。即數(shù)據(jù)的組織形式。四種基本邏輯結構：

1 集合：任何兩個結點間沒有邏輯關系，組織形式松散

2 線性結構：結點按邏輯關系依次排列成一條“鎖鏈”

3 樹形結構：具有分支，層次特性，形態(tài)像自然界中的樹 4. 圖狀結構：各個結點按邏輯關系互相纏繞，任何兩個結點都可以鄰接。

注意點 ： 1. 邏輯結構與數(shù)據(jù)元素本身的形式，內(nèi)容無關。

2. 邏輯結構與數(shù)據(jù)元素的相對位置無關

3. 邏輯結構與所含結點個數(shù)無關。運算：運算是指在任何邏輯結構上施加的操作，即對邏輯結構的加工。加工型運算：改變了原邏輯結構的“值” ，如結點個數(shù)，結點內(nèi)容等。

引用型運算 ：不改變原邏輯結構個數(shù)和值，只從中提取某些信息作為運算的結果。引用：查找，讀取加工：插入，刪除，更新同一邏輯結構 S 上的兩個運算 A 和 B， A 的實現(xiàn)需要或可以利用 B，而 B 的實現(xiàn)不需要利用 A，則稱 A 可以歸約為 B。假如 X 是 S上的一些運算的集合， Y是 X 的一個子集， 使得 X 中每一運算都可以規(guī)約為 Y 中的一個或多個運算，而 Y 中任何運算不可規(guī)約為別的運算，則稱 Y 中運算（相對于 X）為基本運算。將邏輯結構 S和在 S上的基本運算集 X 的整體（ S，X）稱為一個數(shù)據(jù)結構。數(shù)據(jù)結構包括邏輯結構和處理方式。