基本概念

一刀诬、數(shù)據(jù)

數(shù)據(jù)是信息的載體陕壹，是描述客觀事物屬性的數(shù)树埠、字符以及所有能輸入到計(jì)算機(jī)并被計(jì)算機(jī)程序處理和識(shí)別的符號(hào)的集合怎憋。數(shù)據(jù)是計(jì)算機(jī)程序加工的原料。

通俗點(diǎn)來說毕匀，一個(gè)字符癌别，一段文字，一段音頻躁垛，甚至一部電影，都可以說是數(shù)據(jù)逊谋。而站在計(jì)算機(jī)的角度來看活玲，數(shù)據(jù)就是一串0101二進(jìn)制字符舒憾。

二、數(shù)據(jù)元素丁溅、數(shù)據(jù)項(xiàng)

2021中國(guó)富豪排行榜

三挟冠、數(shù)據(jù)結(jié)構(gòu)知染、數(shù)據(jù)對(duì)象

所謂“結(jié)構(gòu)”斑胜，就是用來描述元素之間的邏輯關(guān)系的。那顧名思義掺炭，數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)之間的相互關(guān)系凭戴；數(shù)據(jù)對(duì)象的是具有相同性質(zhì)的數(shù)據(jù)元素之集合么夫。 還說富豪榜的例子，按財(cái)富從高到低排名涉枫，錢多的在前腐螟，錢少的在后，這樣的先后關(guān)系就是數(shù)據(jù)之間的結(jié)構(gòu)。具有這樣結(jié)構(gòu)的數(shù)據(jù)元素放在一起锯仪，就組成了一個(gè)數(shù)據(jù)對(duì)象趾盐。數(shù)據(jù)對(duì)象是數(shù)據(jù)的子集救鲤。

總結(jié)來說，數(shù)據(jù)對(duì)象是具有相同性質(zhì)的數(shù)據(jù)元素的集合斥扛，是數(shù)據(jù)的一個(gè)子集丹锹；數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

數(shù)據(jù)結(jié)構(gòu)關(guān)心的是各個(gè)數(shù)據(jù)元素之間的邏輯關(guān)系匾灶，以及對(duì)數(shù)據(jù)的各種操作阶女，而不在意數(shù)據(jù)的內(nèi)容是什么樣的。那么當(dāng)我們?cè)谠O(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)的時(shí)候衬鱼，應(yīng)該注意數(shù)據(jù)節(jié)結(jié)構(gòu)的哪些方面呢馁启？

數(shù)據(jù)結(jié)構(gòu)的三要素

一芍秆、邏輯結(jié)構(gòu)

• 邏輯結(jié)構(gòu)
  1.集合結(jié)構(gòu)

  
  
  集合結(jié)構(gòu)

  這個(gè)概念和數(shù)學(xué)里的邏輯集合是一樣的妖啥。例如：中國(guó)最有錢的10個(gè)人中就可以構(gòu)成一個(gè)集合，而你我這樣的普通人是不屬于這個(gè)集合的蒿偎。

2. 線性結(jié)構(gòu)

   
   
   線性結(jié)構(gòu)
   
   

   數(shù)據(jù)元素之間是一對(duì)一的關(guān)系诉位，除了第一個(gè)元素和最后一個(gè)元素之外菜枷，任何一個(gè)元素都有惟一的前驅(qū)和惟一的后繼啤誊。比如：富豪排行榜中除了排行第一個(gè)的和排行最后一個(gè)的人，中間的每一個(gè)人都有一個(gè)人在他的前面瞳筏，也總有一個(gè)人在他的后面牡昆。說的專業(yè)一點(diǎn)兒，除了首部和尾部钻心，每一個(gè)元素都有自己的前驅(qū)和自己的后繼捷沸。擁有這種唯一前驅(qū)和唯一后記結(jié)構(gòu)的數(shù)據(jù)的結(jié)構(gòu)，稱為線性結(jié)構(gòu)说墨。

3. 樹形結(jié)構(gòu)

   
   
   樹形結(jié)構(gòu)

   數(shù)據(jù)元素是一對(duì)多的關(guān)系苍柏。例如我們的磁盤文件夾的層層包含的關(guān)系试吁，就是一個(gè)樹形結(jié)構(gòu)。

4. 圖結(jié)構(gòu)

   
   
   圖結(jié)構(gòu)

   數(shù)據(jù)元素是多對(duì)多的關(guān)系。這種結(jié)構(gòu)在生活中也很常見余耽，比如我們?cè)诿枋鰞蓚€(gè)城市或者幾個(gè)城市之間互相是否存在一條道路碟贾，也就是地圖。用到的就是這種圖結(jié)構(gòu)杀餐。

二朱巨、數(shù)據(jù)的運(yùn)算

針對(duì)某一種邏輯結(jié)構(gòu)蔬崩，結(jié)合實(shí)際需求定義出來的基本運(yùn)算搀暑。例如：2021中國(guó)富豪排行榜（我們已經(jīng)知道這是一個(gè)線性結(jié)構(gòu)），我們就針對(duì)這一線性邏輯結(jié)構(gòu)桐罕，結(jié)合和實(shí)際需求功炮，定義如下幾種運(yùn)算：

• 來查找第i個(gè)數(shù)據(jù)元素
• 在第i個(gè)位置插入新的數(shù)據(jù)元素
• 刪除第i個(gè)位置的元素
  這是一個(gè)特例，只針對(duì)這一個(gè)富豪排行榜的操作滚澜，但是我們完全可以把這些運(yùn)算擴(kuò)展到其他的擁有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)上去嫁怀。
  從確定邏輯結(jié)構(gòu)塘淑，到定義幾種運(yùn)算，我們就相當(dāng)于定義出來了一種數(shù)據(jù)結(jié)構(gòu)槐沼。接下來我們要用計(jì)算機(jī)去實(shí)現(xiàn)這一數(shù)據(jù)結(jié)構(gòu)捌治，那么就要考慮數(shù)據(jù)結(jié)構(gòu)的第三個(gè)要素了物理結(jié)構(gòu)了具滴。

三、物理結(jié)構(gòu)

物理結(jié)構(gòu)由叫做存儲(chǔ)結(jié)構(gòu)周蹭，這里我們要討論的是如何用計(jì)算機(jī)表示數(shù)據(jù)元素的邏輯關(guān)系疲恢。一般來說存儲(chǔ)結(jié)構(gòu)分為四種：順序存儲(chǔ)显拳、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)和散列存儲(chǔ)宛畦。接下來揍移，我們以線性邏輯結(jié)構(gòu)為例那伐，來探討如何用計(jì)算機(jī)表示出這種關(guān)系：

• 順序存儲(chǔ)：
  把邏輯上相鄰的的元素存儲(chǔ)在物理上也相鄰的存儲(chǔ)單元中石蔗，元素之間的關(guān)系由單元之間的鄰接關(guān)系來體現(xiàn)养距。

  
  
  順序存儲(chǔ)

• 鏈?zhǔn)酱鎯?chǔ)
  邏輯上相鄰的元素在物理位置上是可以不相鄰的棍厌，借助元素存儲(chǔ)地址的指針來表示元素之間的順序關(guān)系碍遍。

  
  
  鏈?zhǔn)酱鎯?chǔ).png

• 索引存儲(chǔ)
  在存儲(chǔ)元素信息的同時(shí)怕敬，還建立一個(gè)附加的索引表。索引表中的每一項(xiàng)稱為索引項(xiàng)畸陡，索引項(xiàng)的一般形式是(關(guān)鍵字虽填，地址)斋日。所謂關(guān)鍵字就是可以區(qū)分這些數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)，例如：我們每一個(gè)人都有唯一的身份證號(hào)碼第献，那么這個(gè)身份證號(hào)碼就可以作為區(qū)分的關(guān)鍵字庸毫。再例如衫樊，富豪排行榜中的姓名，就可以作為關(guān)鍵字(我們假設(shè)沒有重名的情況)载佳，當(dāng)我們需要查詢某一個(gè)數(shù)據(jù)元素時(shí)蔫慧，可以姓名作為關(guān)鍵字挂脑。

  
  
  索引存儲(chǔ)
• 散列存儲(chǔ)
  散列存儲(chǔ)又叫哈希(Hash)存儲(chǔ)崭闲，會(huì)根據(jù)元素的關(guān)鍵字直接算出元素的存儲(chǔ)地址。這里先不多說橄仍，后面會(huì)單獨(dú)介紹侮繁。

除了順序存儲(chǔ)之外如孝，其他的存儲(chǔ)方式在實(shí)際的物理內(nèi)存空間中都是不相鄰的第晰，因此我們把鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)品抽、散列存儲(chǔ)都通稱為非順序存儲(chǔ)甜熔。

若采用順序存儲(chǔ)腔稀，則各個(gè)元素之間在物理內(nèi)存上必須是連續(xù)的；若采用非順序存儲(chǔ)弱左，則各個(gè)數(shù)據(jù)元素的物理空間可以是離散的拆火。

數(shù)據(jù)的存儲(chǔ)會(huì)結(jié)構(gòu)會(huì)影響存儲(chǔ)空間的方便程度涂圆。例如：我們要采用順序存儲(chǔ)的方式存放一百萬(wàn)條數(shù)據(jù)润歉，這就必須要求實(shí)際的物理內(nèi)存空間有足夠大的而且是連續(xù)的空間，否則是不能進(jìn)行存儲(chǔ)的嚼鹉。而采用其他存儲(chǔ)方式則不然，即使沒有那么大的一塊連續(xù)空間匹舞，也可以進(jìn)行數(shù)據(jù)的存儲(chǔ)赐稽。

數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)會(huì)影響對(duì)數(shù)據(jù)的運(yùn)算速度浑侥。如過我們是按照順序存儲(chǔ)的方式存儲(chǔ)數(shù)據(jù)寓落，想要插入一個(gè)數(shù)據(jù)，就必須對(duì)數(shù)據(jù)進(jìn)行大量的移動(dòng)操作才能保持這種順序關(guān)系躏将。這是十分耗時(shí)的事情祸憋。但是如果我們采用鏈?zhǔn)酱鎯?chǔ)的方式肖卧，只需要修改指針的指向即可。其中的細(xì)節(jié)會(huì)在線性表中介紹拦赠。同時(shí)荷鼠，這里要指出的是運(yùn)算的定義是針對(duì)邏輯結(jié)構(gòu)的榔幸，其目的在于指出運(yùn)算的功能削咆。而運(yùn)算的實(shí)現(xiàn)是針對(duì)存儲(chǔ)結(jié)構(gòu)的，其目的在于指出具體的操作步驟鳞陨。

補(bǔ)充：數(shù)據(jù)類型與抽象數(shù)據(jù)類型

數(shù)據(jù)類型

數(shù)據(jù)類型是一個(gè)值的集合和在此集合上的一組操作的總稱厦滤。數(shù)據(jù)類型分為原子類型和結(jié)構(gòu)類型。

1. 原子類型窄俏，其值不可再分割的數(shù)據(jù)類型。例如bool類型碘菜，值的范圍為true和false，可以進(jìn)行的操作是與限寞、或忍啸、非等。int 類型履植，值的范圍是-2147483648~2147483647计雌，可以進(jìn)行的操作是加、減玫霎、乘凿滤、除庶近、模運(yùn)算等等翁脆。
2. 結(jié)構(gòu)類型，其值可以再分解為若干成分（分量）的數(shù)據(jù)類型鼻种。在C語(yǔ)言里面常見的就是結(jié)構(gòu)體：

//定義一個(gè)“人”結(jié)構(gòu)體
struct Person
{
   char * name;  //姓名
   int age;     //年齡
};

那么對(duì)于這個(gè)Person數(shù)據(jù)類型反番，我們也可以定義出來一些基本的操作。比如修改姓名叉钥，計(jì)算與另一個(gè)人的年齡差值等等罢缸。只不過我們不能使用C語(yǔ)言里面的那些符號(hào)運(yùn)算符，但是我們完全可以把這些運(yùn)算封裝成一個(gè)一個(gè)的函數(shù)投队。

抽象數(shù)據(jù)類型（Abstract Data Type枫疆，ADT）

抽象數(shù)據(jù)類型是抽象的數(shù)據(jù)組織以及與之相關(guān)的操作。當(dāng)我們定義出來一個(gè)抽象數(shù)據(jù)類型的時(shí)候敷鸦，就是定義出來了一個(gè)完整的數(shù)據(jù)結(jié)構(gòu)息楔。

上文列出的結(jié)構(gòu)體就可以看成一個(gè)抽象數(shù)據(jù)類型。我們以struct Person結(jié)構(gòu)體為例來做一些解釋以加深理解：它的數(shù)據(jù)組織就是一個(gè)char* 數(shù)據(jù)類型和一個(gè)int 數(shù)據(jù)類型的一個(gè)組合轧膘。我們知道钞螟，int類型的數(shù)據(jù)可以被這樣定義出來: int a。同樣的谎碍，我們定義出來一個(gè)變量：struct Person p鳞滨。int數(shù)據(jù)類型可以進(jìn)行加、減蟆淀、乘拯啦、除的運(yùn)算澡匪。而Person類型的數(shù)據(jù)也可以有自己的運(yùn)算，只不過這里我們沒有定義出來罷了褒链，而這些運(yùn)算正是需要這個(gè)數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)者來完成的唁情。

數(shù)據(jù)結(jié)構(gòu)的使用者只需要知道它的邏輯結(jié)構(gòu)和與之相關(guān)的操作即可。而這個(gè)數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)者甫匹，還應(yīng)該要知道如何存儲(chǔ)這些數(shù)據(jù)元素甸鸟，以及如何實(shí)現(xiàn)這些相應(yīng)的運(yùn)算”福可以這么說抢韭，抽象數(shù)據(jù)類型就是對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)的邏輯特性的描述。