數(shù)據(jù)結(jié)構(gòu)主講人：張靜常州信息職業(yè)技術(shù)學(xué)院1.1數(shù)據(jù)結(jié)構(gòu)的基本概念Part01基本概念和術(shù)語數(shù)據(jù)是信息的載體。數(shù)據(jù)是對客觀事物的邏輯歸納，是能夠被計(jì)算機(jī)識別、存儲和加工處理的數(shù)字、字符以及各種符號集合的統(tǒng)稱，是計(jì)算機(jī)程序加工的“原料”。姚明的身高為226厘米，是關(guān)于姚明身高的描述數(shù)據(jù)。數(shù)據(jù)（Data）示例基本概念和術(shù)語截止2020年3月31日，全球新冠肺炎確診病例80萬例。是全球新冠肺炎確診病例的時間和人數(shù)數(shù)據(jù)。數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位，也稱為結(jié)點(diǎn)、頂點(diǎn)、記錄等，在計(jì)算機(jī)程序中通常作為一個整體進(jìn)行考慮和處理。一個數(shù)據(jù)元素可以是一個不可分割的原子項(xiàng)，也可以由若干個數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)元素（DataElement）示例基本概念和術(shù)語圖書的信息包括：書號、書名、作者、出版社。一本圖書的信息就是一個數(shù)據(jù)元素。數(shù)據(jù)項(xiàng)是數(shù)據(jù)元素中具有獨(dú)立含義的最小標(biāo)識單位，也稱為字段、域、屬性。數(shù)據(jù)項(xiàng)（DataItem）基本概念和術(shù)語姚明的的身高數(shù)據(jù)是一個不可再分的整型數(shù)據(jù)，這個整數(shù)既是數(shù)據(jù)元素也是數(shù)據(jù)項(xiàng)；示例一本圖書數(shù)據(jù)元素由書號、書名、作者、出版社等4個數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。性質(zhì)相同指的是數(shù)據(jù)元素具有相同數(shù)量和類型的數(shù)據(jù)項(xiàng)。數(shù)據(jù)對象（DataObject）示例基本概念和術(shù)語每本圖書都有書號、書名、作者、出版社等相同的數(shù)據(jù)項(xiàng)?；靖拍詈托g(shù)語7存儲結(jié)構(gòu)數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)中的存儲表示或?qū)崿F(xiàn)，也稱為物理結(jié)構(gòu)。數(shù)據(jù)的運(yùn)算初始化、判斷是否為空、存取、遍歷、插入、刪除、更新、查找、排序。邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是從具體問題抽象出來的數(shù)學(xué)模型，是數(shù)據(jù)元素之間的邏輯關(guān)系。數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算（操作或算法）。數(shù)據(jù)結(jié)構(gòu)書號書名作者出版社單價出版日期9787040528121計(jì)算機(jī)應(yīng)用基礎(chǔ)任務(wù)化教程眭碧霞高等教育出版社49.52019.129787040527735信息技術(shù)基礎(chǔ)眭碧霞、張靜高等教育出版社39.52019.109787040487282數(shù)據(jù)結(jié)構(gòu)(C語言描述)(第2版)李學(xué)剛高等教育出版社38.12018.039787040509946軟件開發(fā)與項(xiàng)目管理（第2版）朱利華高等教育出版社49.52019.019787040496628JavaEE企業(yè)級項(xiàng)目開發(fā)蔣衛(wèi)祥高等教育出版社47.42018.06Part02數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)常被簡稱為數(shù)據(jù)結(jié)構(gòu)，分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩種，非線性結(jié)構(gòu)主要包括樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)。邏輯結(jié)構(gòu)線性結(jié)構(gòu)是數(shù)據(jù)元素之間具有線性關(guān)系的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)元素之間形成一對一的關(guān)系。它的特征是：除第一個和最后一個元素外，每個數(shù)據(jù)元素有且僅有一個直接前驅(qū)和一個直接后繼元素，第一個元素只有一個直接后繼元素，最后一個元素只有一個直接前驅(qū)元素。數(shù)據(jù)的邏輯結(jié)構(gòu)1.線性結(jié)構(gòu)ABCD非線性結(jié)構(gòu)之一。除了根結(jié)點(diǎn)和葉子結(jié)點(diǎn)之外，樹中任意一個結(jié)點(diǎn)只有一個直接前驅(qū)結(jié)點(diǎn)（父結(jié)點(diǎn)）和多個直接后繼結(jié)點(diǎn)（孩子結(jié)點(diǎn)），根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，葉子結(jié)點(diǎn)沒有后繼結(jié)點(diǎn)。數(shù)據(jù)的邏輯結(jié)構(gòu)2.樹形結(jié)構(gòu)ABCDEFG根結(jié)點(diǎn)葉子結(jié)點(diǎn)圖狀結(jié)構(gòu)也是非線性結(jié)構(gòu)，數(shù)據(jù)元素之間存在多對多的關(guān)系，每個數(shù)據(jù)元素可有多個前驅(qū)元素和多個后繼元素。數(shù)據(jù)的邏輯結(jié)構(gòu)3.圖狀結(jié)構(gòu)ABCDEFG集合結(jié)構(gòu)中的數(shù)據(jù)元素除了屬于同一個集合外，它們之間沒有其他關(guān)系。各個數(shù)據(jù)元素是“平等”的，它們的共同關(guān)系就只是屬于同一個集合。數(shù)據(jù)的邏輯結(jié)構(gòu)4.集合結(jié)構(gòu)Part03數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)主要有兩種：順序存儲和鏈?zhǔn)酱鎯?。為了加快查找速度，引入了索引（分塊）查找和散列（哈希）查找。因此，從形式上看有4種物理存儲方式，但算法實(shí)現(xiàn)主要采用順序存儲和鏈?zhǔn)酱鎯Α４鎯Y(jié)構(gòu)把數(shù)據(jù)元素依次存放在一組地址連續(xù)的存儲單元里，數(shù)據(jù)元素的物理存儲次序和它們的邏輯次序相同，即邏輯上相鄰的結(jié)點(diǎn)存儲在物理位置上相鄰的存儲單元中。通常，使用數(shù)組來實(shí)現(xiàn)順序存儲結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)1.順序存儲結(jié)構(gòu)地址數(shù)據(jù)3000H273004H653008H43300CH893010H103014H3763018H

示例：序列A=(27,65,43,89,10,376)的順序存儲結(jié)構(gòu)把數(shù)據(jù)元素存放在任意的存儲單元里，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的，邏輯上相鄰的數(shù)據(jù)元素在物理位置上不一定相鄰，通常，需要采用指針變量來記載前驅(qū)和后繼元素的存儲地址。數(shù)據(jù)的存儲結(jié)構(gòu)2.鏈?zhǔn)酱鎯Y(jié)構(gòu)示例：序列A=(27,65,43,89,10,376)的鏈?zhǔn)酱鎯Y(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)18索引散列建立附加的索引表來標(biāo)識數(shù)據(jù)元素的地址。它不是獨(dú)立的存儲結(jié)構(gòu)，只是為了在查找運(yùn)算時，能夠減少查找的時間，提高數(shù)據(jù)查找的性能。3.索引存儲結(jié)構(gòu)根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲地址。它是一種能快速實(shí)現(xiàn)訪問的存儲方式，理想情況下，無需比較即可根據(jù)指定值直接定位記錄的存儲位置。4.散列存儲結(jié)構(gòu)通常情況下，一種數(shù)據(jù)結(jié)構(gòu)既可以用順序存儲結(jié)構(gòu)實(shí)現(xiàn)，也可用鏈?zhǔn)酱鎯Y(jié)構(gòu)實(shí)現(xiàn)，還可以組合使用，具體可根據(jù)實(shí)際