找、插入、刪除、合並、排序、統計以及簡單計算等的操作過程。在早期,計算機主要用於科學和工程計算,進入八十年代以後,計算機主要用於數據處理。據有關統計資料表明,現在計算機用於數據處理的時間比例達到80%以上,隨著時間的推移和計算機應用的進一步普及,計算機用於數據處理的時間比例必將進一步增大。
分類
數據結構是指同一數據元素類中各數據元素之間存在的關係。數據結構分別為邏輯結構、存儲結構(物理結構)和數據的運算。數據的邏輯結構是對數據之間關係的描述,有時就把邏輯結構簡稱為數據結構。邏輯結構形式地定義為(K,R)(或(D,S)),其中,K是數據元素的有限集,R是K上的關係的有限集。
數據元素相互之間的關係稱為結構。有四類基本結構:集合、線性結構、樹形結構、圖狀結構(網狀結構)。樹形結構和圖形結構全稱為非線性結構。集合結構中的數據元素除了同屬於一種類型外,別無其它關係。線性結構中元素之間存在一對一關係,樹形結構中元素之間存在一對多關係,圖形結構中元素之間存在多對多關係。在圖形結構中每個結點的前驅結點數和後續結點數可以任意多個。
數據結構在計算機中的表示(映像)稱為數據的物理(存儲)結構。它包括數據元素的表示和關係的表示。數據元素之間的關係有兩種不同的表示方法:順序映象和非順序映象,並由此得到兩種不同的存儲結構:順序存儲結構和鏈式存儲結構。順序存儲方法:它是把邏輯上相鄰的結點存儲在物理位置相鄰的存儲單元裡,結點間的邏輯關係由存儲單元的鄰接關係來體現,由此得到的存儲表示稱為順序存儲結構。順序存儲結構是一種最基本的存儲表示方法,通常借助於程序設計語言中的數組來實現。鏈接存儲方法:它不要求邏輯上相鄰的結點在物理位置上亦相鄰,結點間的邏輯關係是由附加的指針字段表示的。由此得到的存儲表示稱為鏈式存儲結構,鏈式存儲結構通常借助於程序設計語言中的指針類型來實現。索引存儲方法:除建立存儲結點信息外,還建立附加的索引表來標識結點的地址。散列存儲方法:就是根據結點的關鍵字直接計算出該結點的存儲地址。
數據結構中,邏輯上(邏輯結構:數據元素之間的邏輯關係)可以把數據結構分成線性結構和非線性結構。線性結構的順序存儲結構是一種隨機存取的存儲結構,線性表的鏈式存儲結構是一種順序存取的存儲結構。線性表若采用鏈式存儲表示時所有結點之間的存儲單元地址可連續可不連續。邏輯結構與數據元素本身的形式、內容、相對位置、所含結點個數都無關。
數據結構與算法
算法的設計取決於數據(邏輯)結構,而算法的實現依賴於采用的存儲結構。數據的存儲結構實質上是它的邏輯結構在計算機存儲器中的實現,為了全麵的反映一個數據的邏輯結構,它在存儲器中的映象包括兩方麵內容,即數據元素之間的信息和數據元素之間的關係。不同數據結構有其相應的若乾運算。數據的運算是在數據的邏輯結構上定義的操作算法,如檢索、插入、刪除、更新和排序等。
數據的運算是數據結構的一個重要方麵,討論任一種數據結構時都離不開對該結構上的數據運算及其實現算法的討論。
數據結構的形式定義為:數據結構是一個二元組:
ᴏᴏᴘ.ᴛᴡ 呈現最新的小說章節
Data-Structure=(D,S)
其中:D是數據元素的有限集,S是D上關係的有限集。
數據結構不同於數據類型,也不同於數據對象,它不僅要描述數據類型的數據對象,而且要描述數據對象各元素之間的相互關係。
數據類型是一個值的集合和定義在這個值集上的一組操作的總稱。數據類型可分為兩類:原子類型、結構類型。一方麵,在程序設計語言中,每一個數據都屬於某種數據類型。類型明顯或隱含地規定了數據的取值範圍、存儲方式以及允許進行的運算。可以認為,數據類型是在程序設計中已經實現了的數據結構。另一方麵,在程序設計過程中,當需要引入某種新的數據結構時,總是借助編程語言所提供的數據類型來描述數據的存儲結構。
計算機中表示數據的最小單位是二進製數的一位,叫做位。我們用一個由若乾位組合起來形成的一個位串表示一個數據元素,通常稱這個位串為元素或結點。當數據元素由若乾數據項組成時,位串中對應於各個數據項的子位串稱為數據域。元素或結點可看成是數據元素在計算機中的映象。
一個軟件係統框架應建立在數據之上,而不是建立在操作之上。一個含抽象數據類型的軟件模塊應包含定義、表示、實現三個部分。
對每一個數據結構而言,必定存在與它密切相關的一組操作。若操作的種類和數目不同,即使邏輯結構相同,數據結構能起的作用也不同。
不同的數據結構其操作集不同,但下列操作必不可缺:
1,結構的生成;
2.結構的銷毀;
3,在結構中查找滿足規定條件的數據元素;
4,在結構中插入新的數據元素;
5,刪除結構中已經存在的數據元素;
6,遍曆。
:為義定的TDA。集作操本基的D對是P,集係關的上D是S,象對據數是D。)P,S,D(:示表組元三下以用可型類據數象抽。法算組一的上構結此在及以構結輯邏的據數個一了義定它為因。義定的構結據數該對是就上際實型類據數象抽。作操組一的上型模該在義定及以型模學數個一:型類據數象抽
{名型類據數象抽TDA
)合集素元據數(:象對據數
)合結組元二係關據數(:係關據數
)列羅的數函作操(:作操本基
;名型類據數象抽TDA}
:性特要重個兩有型類據數象抽
象抽據數
。)法方的它用使界外即(口接的戶用部外和它及以能功的成完能所其、征特的質本其是的調強,時體實的理處序程述描TDA用
裝封據數
。節細現實部內其藏隱戶用部外對且並,離分節細現實部內其和性特部外的體實將
,體載的息信是)ataD(據數