??個(gè)人主頁(yè)：聆風(fēng)吟
??系列專(zhuān)欄：數(shù)據(jù)結(jié)構(gòu)、算法模板、匯編語(yǔ)言
??少年有夢(mèng)不應(yīng)止于心動(dòng)，更要付諸行動(dòng)。

??前言

?????? 文章主要介紹：本系列主要對(duì)數(shù)據(jù)結(jié)構(gòu)的進(jìn)行由淺入深的講解，希望對(duì)你今后的學(xué)習(xí)有一定的幫助。如果有發(fā)現(xiàn)錯(cuò)誤的地方還請(qǐng)?jiān)谠u(píng)論區(qū)告知，非常感謝！
?????? 系列專(zhuān)欄：本期文章收錄在《圖解數(shù)據(jù)結(jié)構(gòu)》，大家有興趣可以瀏覽和關(guān)注，后面將會(huì)有更多精彩內(nèi)容！
?????? 歡迎大家關(guān)注??點(diǎn)贊??收藏??留言??

一. 數(shù)組結(jié)構(gòu)起源

摘錄：
????早期人們都把計(jì)算機(jī)理解為數(shù)值計(jì)算工具，就是感覺(jué)計(jì)算機(jī)當(dāng)然是用來(lái)計(jì)算的，所以計(jì)算機(jī)解決問(wèn)題，應(yīng)該是先從具體問(wèn)題中抽象出一個(gè)適當(dāng)?shù)臄?shù)據(jù)模型，設(shè)計(jì)出一個(gè)解此數(shù)據(jù)模型的算法，然后再編寫(xiě)程序，得到一個(gè)實(shí)際的軟件。可現(xiàn)實(shí)中，我們更多的不是解決數(shù)值計(jì)算的問(wèn)題，而是需要一些更科學(xué)有效的手段(比如表、樹(shù)和圖等數(shù)據(jù)結(jié)構(gòu))的幫助，才能更好地處理問(wèn)題。所以：
????數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題的操作對(duì)象，以及他們之間的關(guān)系和操作等相關(guān)問(wèn)題。

????1968年，美國(guó)的高德納(Donald E. Knuth)教授在其所寫(xiě)的《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》第一卷《基本算法》中，較系統(tǒng)地闡述了數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)及其操作，開(kāi)創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的課程體系。同年，“數(shù)據(jù)結(jié)構(gòu)” 作為一門(mén)獨(dú)立的課程，在計(jì)算機(jī)科學(xué)的學(xué)位課程中開(kāi)始出現(xiàn)。也就是說(shuō)，那之后計(jì)算機(jī)相關(guān)專(zhuān)業(yè)的學(xué)生開(kāi)始接受“數(shù)據(jù)結(jié)構(gòu)”的“折磨”——其實(shí)應(yīng)該是享受才對(duì)。

????之后，20世紀(jì)70年代初，出現(xiàn)了大型程序，軟件也開(kāi)始相對(duì)獨(dú)立，結(jié)構(gòu)程序設(shè)計(jì)成為程序設(shè)計(jì)方法學(xué)的主要內(nèi)容，人們?cè)絹?lái)越重視“數(shù)據(jù)結(jié)構(gòu)”，認(rèn)為 程序設(shè)計(jì)的實(shí)質(zhì)是對(duì)確定的問(wèn)題選擇一種好的結(jié)構(gòu)，加上設(shè)計(jì)一種好的算法?？梢?jiàn)，數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計(jì)當(dāng)中占據(jù)了重要的地位。

二. 基本概念和術(shù)語(yǔ)

2.1 數(shù)據(jù)

????數(shù)據(jù)：是描述客觀事物的符號(hào)，是計(jì)算機(jī)中可以操作的對(duì)象，是能被計(jì)算機(jī)識(shí)別的，并輸入給計(jì)算機(jī)處理的符號(hào)集合。 數(shù)據(jù)不僅僅包括整形、實(shí)型等數(shù)值類(lèi)型，還包括字符及聲音、圖像、視頻等非數(shù)值類(lèi)型。

2.2 數(shù)據(jù)元素

????數(shù)據(jù)元素：是組成數(shù)據(jù)的、有一定意義的基本單位，在計(jì)算機(jī)中通常作為整體處理，也被稱(chēng)為記錄。 比如在人類(lèi)中，人是數(shù)據(jù)元素；在禽獸類(lèi)中，牛、馬、雞等動(dòng)物都是禽獸類(lèi)的數(shù)據(jù)元素。

2.3 數(shù)據(jù)項(xiàng)

????數(shù)據(jù)項(xiàng)：一個(gè)數(shù)據(jù)元素可以由若干數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小元素。 比如人這樣一個(gè)數(shù)據(jù)元素，可以有眼睛、耳朵、鼻子、嘴巴、手、腳這些數(shù)據(jù)項(xiàng)，也可以有名字、年齡、性別、家庭地址、聯(lián)系電話、郵政編碼、等數(shù)據(jù)項(xiàng)，具體有哪些數(shù)據(jù)項(xiàng)有你來(lái)決定。

2.4 數(shù)據(jù)對(duì)象

????數(shù)據(jù)對(duì)象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。其中，性質(zhì)相同是指數(shù)據(jù)元素具有相同的數(shù)量和類(lèi)型的數(shù)據(jù)項(xiàng)。

2.5 數(shù)據(jù)結(jié)構(gòu)

????以上是關(guān)于數(shù)據(jù)的定義。結(jié)構(gòu)的定義是：不同數(shù)據(jù)數(shù)據(jù)元素之間不是相互獨(dú)立的，而是存在特定關(guān)系，我們稱(chēng)這些關(guān)系為結(jié)構(gòu)。介紹了數(shù)據(jù)和結(jié)構(gòu)的定義，那數(shù)據(jù)結(jié)構(gòu)的定義呢？

數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合

三. 邏輯結(jié)構(gòu)和物理結(jié)構(gòu)

????按照視點(diǎn)的不同，我們把數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。

3.1 邏輯結(jié)構(gòu)

????邏輯結(jié)構(gòu)：是指數(shù)據(jù)對(duì)象中數(shù)據(jù)元素的之間的相互關(guān)系。邏輯結(jié)構(gòu)分為一下四種:

1. 集合結(jié)構(gòu)
   集合結(jié)構(gòu)：集合結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一個(gè)集合外，他們之間沒(méi)有其他關(guān)系。如下圖所示：
   
   

2. 線性結(jié)構(gòu)
   線性結(jié)構(gòu)：線性結(jié)構(gòu)中的數(shù)據(jù)元素之間是一對(duì)一的關(guān)系。如下圖所示：
   
   
   

3. 樹(shù)形結(jié)構(gòu)
   樹(shù)形結(jié)構(gòu)：樹(shù)形結(jié)構(gòu)中的數(shù)據(jù)元素存在一種一對(duì)多的層次關(guān)系。如下圖所示：
   
   
   

4. 圖形結(jié)構(gòu)
   圖形結(jié)構(gòu)：圖形的數(shù)據(jù)元素是多對(duì)多的關(guān)系。如下圖所示：
   

注意事項(xiàng)： 用示意圖表示數(shù)據(jù)的邏輯時(shí)，需要注意一下兩點(diǎn)：

• 將每一個(gè)數(shù)據(jù)元組看作一個(gè)結(jié)點(diǎn)，用圓圈表示；
• 元素之間的邏輯關(guān)系用結(jié)點(diǎn)之間的連線表示，如果這個(gè)關(guān)系是有方向的，那么用帶箭頭的連線表示。

3.2 物理結(jié)構(gòu)

????物理結(jié)構(gòu)（在很多書(shū)中也稱(chēng)存儲(chǔ)結(jié)構(gòu)）：是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)形式。數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)形式有兩種：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。

1. 順序存儲(chǔ)結(jié)構(gòu)
   順序存儲(chǔ)結(jié)構(gòu)：是把數(shù)據(jù)元素存放在地址連續(xù)的存儲(chǔ)單元里，其數(shù)據(jù)間的邏輯關(guān)系和物理關(guān)系是一致的。如下圖所示：
   
   
   

2. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
   鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：是把數(shù)據(jù)元素存放在任意的存儲(chǔ)單元里，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。因?yàn)閿?shù)據(jù)元素的存儲(chǔ)關(guān)系并不能直接反映其邏輯關(guān)系，因此需要用一個(gè)指針存放數(shù)據(jù)元素的地址，這樣通過(guò)地址就可以找到相數(shù)據(jù)元素的位置。如下圖所示：
   

四. 數(shù)據(jù)類(lèi)型

????數(shù)據(jù)類(lèi)型：是指一組性質(zhì)相同的值的集合及定義在此集合上的一些操作的總稱(chēng)。

4.1 數(shù)據(jù)類(lèi)型的定義

????數(shù)據(jù)類(lèi)型是按照值的不同進(jìn)行劃分的。在高級(jí)語(yǔ)言中，每個(gè)變量、常量和表達(dá)式都有各自的取值范圍。類(lèi)型就是用來(lái)說(shuō)明變量或表達(dá)式的取值范圍和所能進(jìn)行的操作。在c語(yǔ)言中，按照值的不同，數(shù)據(jù)可以分為兩類(lèi)：

• 原子類(lèi)型
  原子類(lèi)型是不可以在分解的基本類(lèi)型，包括整型、實(shí)型、字符型等。
• 結(jié)構(gòu)類(lèi)型
  結(jié)構(gòu)類(lèi)型是由若干個(gè)類(lèi)型組合而成，是可以再分解的。例如，整型數(shù)組是由若干整型數(shù)據(jù)組合而成。

4.2 抽象數(shù)據(jù)類(lèi)型

????抽象數(shù)據(jù)類(lèi)型（Abstract Data Type，ADT）是指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作。抽象類(lèi)型的定義取決于它的一組邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無(wú)關(guān)。

????實(shí)際上，抽象數(shù)據(jù)類(lèi)型體現(xiàn)了程序設(shè)計(jì)中問(wèn)題分解、抽象和信息隱藏的特性。抽象數(shù)據(jù)類(lèi)型把實(shí)際生活中的問(wèn)題分解為多個(gè)規(guī)模小且容易處理的問(wèn)題，然后建立一個(gè)計(jì)算機(jī)能處理的數(shù)據(jù)模型，并把每個(gè)功能模塊的實(shí)現(xiàn)細(xì)節(jié)作為一個(gè)獨(dú)立的單元，從而使具體實(shí)現(xiàn)過(guò)程隱藏起來(lái)。
????抽象數(shù)據(jù)類(lèi)型的標(biāo)準(zhǔn)格式：

ADT 抽象數(shù)據(jù)類(lèi)型名
Data
  數(shù)據(jù)元素之間的邏輯關(guān)系的定義
Operation
  操作 1
  		初始條件
  		操作結(jié)果描述
  操作 2
  		......
  操作 n
  		......
 endADT

??全文總結(jié)

????本文主要講解了數(shù)據(jù)結(jié)構(gòu)的起源、基本概念、數(shù)據(jù)結(jié)構(gòu)的分類(lèi)等相關(guān)基礎(chǔ)知識(shí)，意在讓大家對(duì)數(shù)據(jù)結(jié)構(gòu)有個(gè)初步了解，為后面的學(xué)習(xí)打下基礎(chǔ)。

???? 今天的干貨分享到這里就結(jié)束啦！如果覺(jué)得文章還可以的話，希望能給個(gè)三連支持一下，聆風(fēng)吟的主頁(yè)還有很多有趣的文章，歡迎小伙伴們前去點(diǎn)評(píng)，您的支持就是作者前進(jìn)的最大動(dòng)力！
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-787334.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)初探：揭開(kāi)數(shù)據(jù)結(jié)構(gòu)奧秘的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！