數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)(Data Structure)是指數(shù)據(jù)與數(shù)據(jù)之間的關(guān)系。在任何問(wèn)題中，數(shù)據(jù)元素之間都不是孤立的，而是存在著一定的關(guān)系，這種關(guān)系稱為結(jié)構(gòu)(Structure)。
例如，有一張學(xué)生選課表，這個(gè)表就是數(shù)據(jù)；成績(jī)表中記錄了班級(jí)每個(gè)學(xué)生選課的成績(jī)，每個(gè)學(xué)生的姓名為一行組成一條記錄。每個(gè)記錄由姓名、學(xué)號(hào)、課程成績(jī)等字段組成，每個(gè)記錄就是一個(gè)結(jié)點(diǎn)也稱為數(shù)據(jù)元素；每個(gè)字段就是數(shù)據(jù)項(xiàng)。姓名字段取值范圍為字符型，而課程成績(jī)字段取值為整型。學(xué)生選課成績(jī)表的數(shù)據(jù)是一組學(xué)生成績(jī)信息，這組信息具有相同特性，屬于同一數(shù)據(jù)對(duì)象，相鄰數(shù)據(jù)元素之間存在序偶關(guān)系，按照學(xué)號(hào)升序排列。
數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲(chǔ)(物理)結(jié)構(gòu)
邏輯結(jié)構(gòu)
數(shù)據(jù)元素之間的邏輯關(guān)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問(wèn)題抽象出來(lái)的數(shù)學(xué)模型，它與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)。
邏輯結(jié)構(gòu)通常有以下4種。
·集合結(jié)構(gòu)：在集合結(jié)構(gòu)中，數(shù)據(jù)元素間的關(guān)系是“屬于同一個(gè)集合”。集合結(jié)構(gòu)是元素關(guān)系極為松散的一種結(jié)構(gòu)。
·線性結(jié)構(gòu)：該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對(duì)一的關(guān)系，即一個(gè)數(shù)據(jù)元素只與另一個(gè)數(shù)據(jù)元素有關(guān)系。
·樹性結(jié)構(gòu)：該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對(duì)多的關(guān)系，即一個(gè)數(shù)據(jù)元素只與另外多個(gè)數(shù)據(jù)元素有關(guān)系。
·圖性結(jié)構(gòu)：該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著多對(duì)多的關(guān)系，即數(shù)據(jù)元素之間有多個(gè)關(guān)系。圖形結(jié)構(gòu)也稱作網(wǎng)狀結(jié)構(gòu)。
存儲(chǔ)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（又稱映像）稱為數(shù)據(jù)的物理結(jié)構(gòu)，或稱存儲(chǔ)結(jié)構(gòu)。它所研究的是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)方法，包括數(shù)據(jù)結(jié)構(gòu)中元素的表示及元素間關(guān)系的表示。
如線性結(jié)構(gòu)，既要存儲(chǔ)數(shù)據(jù)元素A，B，C，D又要存儲(chǔ)他們之間的關(guān)系A(chǔ)B，BC，CD那么，是用一片連續(xù)的內(nèi)存單元來(lái)存放這些記錄（如用數(shù)組表示），還是隨機(jī)存放各結(jié)點(diǎn)數(shù)據(jù)再用指針進(jìn)行鏈接呢？這就是物理結(jié)構(gòu)的問(wèn)題。根據(jù)分析該結(jié)構(gòu)是線性關(guān)系，故采用數(shù)組來(lái)存儲(chǔ)。
數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可采用順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)的方法。
順序存儲(chǔ)方法是把邏輯上相鄰的元素存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元中，由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)是一種最基本的存儲(chǔ)表示方法，通常借助于程序設(shè)計(jì)語(yǔ)言中的數(shù)組來(lái)實(shí)現(xiàn)。
鏈?zhǔn)酱鎯?chǔ)方法是對(duì)邏輯上相鄰的元素不要求其物理位置相鄰，元素間的邏輯關(guān)系通過(guò)附設(shè)的指針字段來(lái)表示，由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通常借助于程序設(shè)計(jì)語(yǔ)言中的指針類型來(lái)實(shí)現(xiàn)。
除了通常采用的順序存儲(chǔ)方法和鏈?zhǔn)酱鎯?chǔ)方法外，有時(shí)為了查找的方便還采用索引存儲(chǔ)方法和散列存儲(chǔ)方法。
線性結(jié)構(gòu)和非線性結(jié)構(gòu)
“線性”和“非線性”，只在邏輯層次上討論，而不考慮存儲(chǔ)層次，所以雙向鏈表和循環(huán)鏈表依舊是線性表。
這句話的理解是：
- 雙向鏈表有兩個(gè)直接后繼，它們只是存儲(chǔ)層次上的，不是邏輯層次上的，因?yàn)閿?shù)據(jù)元素之間還是一對(duì)一的關(guān)系。
- 二叉樹同樣也有兩個(gè)直接后繼，但它是邏輯層次上的。為什么？因?yàn)閿?shù)據(jù)元素之間一對(duì)多的關(guān)系。
數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。
線性結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)中線性結(jié)構(gòu)指的是數(shù)據(jù)元素之間存在著“一對(duì)一”的線性關(guān)系的數(shù)據(jù)結(jié)構(gòu)。
常用的線性結(jié)構(gòu)有：線性表，棧，隊(duì)列，雙隊(duì)列，數(shù)組，串。
線性表與線性結(jié)構(gòu)的關(guān)系
線性表是最基本、最簡(jiǎn)單、也是最常用的一種線性結(jié)構(gòu)。
線性結(jié)構(gòu)的特點(diǎn)是數(shù)據(jù)元素之間是一種線性關(guān)系，數(shù)據(jù)元素"一個(gè)接一個(gè)的排列"。
線性表是由同一類型的數(shù)據(jù)元素構(gòu)成的線性結(jié)構(gòu)。
這句話的我的理解是線性結(jié)構(gòu)中的數(shù)據(jù)元素是同一類型就可以說(shuō)是線性表。
線性結(jié)構(gòu)的邏輯存儲(chǔ)
線性結(jié)構(gòu)的邏輯存儲(chǔ)有兩種表示：順序表示和鏈?zhǔn)奖硎?/p>
順序表示：指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素，稱為線性表的順序存儲(chǔ)結(jié)構(gòu)。它以“物理位置相鄰”來(lái)表示線性表中數(shù)據(jù)元素間的邏輯關(guān)系，可隨機(jī)存取表中任一元素。
鏈?zhǔn)奖硎荆褐傅氖怯靡唤M任意的存儲(chǔ)單元存儲(chǔ)線性表中的數(shù)據(jù)元素，稱為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它的存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。在表示數(shù)據(jù)元素之間的邏輯關(guān)系時(shí)，除了存儲(chǔ)其本身的信息之外，還需存儲(chǔ)一個(gè)指示其直接后繼的信息（即直接后繼的存儲(chǔ)位置），這兩部分信息組成數(shù)據(jù)元素的存儲(chǔ)映像，稱為結(jié)點(diǎn)（node）。它包括兩個(gè)域；存儲(chǔ)數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域；存儲(chǔ)直接后繼存儲(chǔ)位置的域稱為指針域。指針域中存儲(chǔ)的信息稱為指針 。
順序表:
順序表是在計(jì)算機(jī)內(nèi)存中以數(shù)組的形式保存的線性表，是指用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu)。線性表采用順序存儲(chǔ)的方式存儲(chǔ)就稱之為順序表。順序表是將表中的結(jié)點(diǎn)依次存放在計(jì)算機(jī)內(nèi)存中一組地址連續(xù)的存儲(chǔ)單元中。
順序結(jié)構(gòu)：
將表中元素一個(gè)接一個(gè)的存入一組連續(xù)的存儲(chǔ)單元中，這種存儲(chǔ)結(jié)構(gòu)是順序結(jié)構(gòu)。
采用順序存儲(chǔ)結(jié)構(gòu)的線性表簡(jiǎn)稱為“ 順序表”。
非線性結(jié)構(gòu)
相對(duì)應(yīng)于線性結(jié)構(gòu)，非線性結(jié)構(gòu)的邏輯層次是一個(gè)結(jié)點(diǎn)元素可能對(duì)應(yīng)多個(gè)直接前驅(qū)和多個(gè)后繼。
常見的非線性結(jié)構(gòu)有：二維數(shù)組，多維數(shù)組，廣義表，樹(二叉樹等)，圖。
用來(lái)描述復(fù)雜度O(nlog2n)是什么意思？
O()代表不超過(guò)括號(hào)內(nèi)數(shù)值的最大整數(shù)值。
n*log2(n) n乘以n的以2為底的對(duì)數(shù)
