【文章內(nèi)容簡(jiǎn)介】 ? 數(shù)據(jù)結(jié)構(gòu) 是指數(shù)據(jù)元素之間的相互關(guān)系的集合，包括了數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)以及數(shù)據(jù)的運(yùn)算。 ? ⑴ 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系。數(shù)據(jù)之間可以根據(jù)不同的關(guān)系組成不同的數(shù)據(jù)結(jié)構(gòu)。 ? 線性結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)中，如果數(shù)據(jù)元素之間存在著前后順序的關(guān)系，即除了第一個(gè)數(shù)據(jù)元素和最后一個(gè)元素外，其他每個(gè)元素都有惟一的一個(gè)前驅(qū)和一個(gè)后繼元素，這樣的數(shù)據(jù)元素之間的關(guān)系被稱為線性結(jié)構(gòu)。 ? 樹形結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)中，如果數(shù)據(jù)元素之間有順序關(guān)系，且除了一個(gè)被稱為根節(jié)點(diǎn)的元素外，每個(gè)元素都有一個(gè)前驅(qū)節(jié)點(diǎn)，并且可以有多個(gè)后繼節(jié)點(diǎn)，這種邏輯結(jié)構(gòu)稱為樹形結(jié)構(gòu)。 ? 圖形結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)中，如果任何一個(gè)數(shù)據(jù)元素都可以有多個(gè)前驅(qū)節(jié)點(diǎn)和多個(gè)后繼節(jié)點(diǎn)，這種邏輯結(jié)構(gòu)稱為圖形結(jié)構(gòu)。 ? (2) 數(shù)據(jù)的物理結(jié)構(gòu) 數(shù)據(jù)的物理結(jié)構(gòu)是指邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的表示。數(shù)據(jù)的物理結(jié)構(gòu)不僅要存儲(chǔ)數(shù)據(jù)本身，還要存儲(chǔ)表示數(shù)據(jù)間的邏輯關(guān)系。 數(shù)據(jù)的物理結(jié)構(gòu)主要有四種，分別是順序結(jié)構(gòu)、鏈表結(jié)構(gòu)、索引結(jié)構(gòu)及散列結(jié)構(gòu)。 ? ① 順序結(jié)構(gòu) 把所有元素存放在一片連續(xù)的存儲(chǔ)單元中，邏輯上相鄰的元素存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元中，由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)。 順序存儲(chǔ)結(jié)構(gòu)常借助于程序設(shè)計(jì)語(yǔ)言中的數(shù)組來(lái)實(shí)現(xiàn)。優(yōu)點(diǎn)是使用方法簡(jiǎn)單，缺點(diǎn)是必須預(yù)先分析出所需定義數(shù)組的大小。 ? ② 鏈表結(jié)構(gòu) 對(duì)邏輯上相鄰的元素不要求其物理位置相鄰，元素間的邏輯關(guān)系通過(guò)附設(shè)的指針域來(lái)實(shí)現(xiàn)，由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通常借助于程序設(shè)計(jì)語(yǔ)言中的指針來(lái)實(shí)現(xiàn)。 ? ③ 索引結(jié)構(gòu) 針對(duì)每個(gè)數(shù)據(jù)結(jié)構(gòu)建立一張所謂的索引表，每個(gè)數(shù)據(jù)元素占用表中的一項(xiàng)，每個(gè)表項(xiàng)包含一個(gè)能夠惟一識(shí)別一個(gè)元素的關(guān)鍵字和用以指示該元素的地址指針。 ? ④散列結(jié)構(gòu) 通過(guò)構(gòu)造相應(yīng)的散列函數(shù)，由散列函數(shù)的值來(lái)確定元素存放的地址。 ? (3) 數(shù)據(jù)運(yùn)算 數(shù)據(jù)操作的集合。常見的數(shù)據(jù)操作有數(shù)據(jù)的插入、刪除、查找、遍歷等。 數(shù)據(jù)操作通常由計(jì)算機(jī)程序加以實(shí)現(xiàn)，通常也叫 算法實(shí)現(xiàn) 。 線性表 ? 1．定義 ? 線性表 是由有限個(gè)相同的數(shù)據(jù)元素構(gòu)成的序列，元素之間是一對(duì)一的線性關(guān)系，除了第一個(gè)元素只有直接后繼、最后一個(gè)元素只有直接前驅(qū)外，其余數(shù)據(jù)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼，如圖。 元素 1 ua n su 元素 2 1 元素 3 1 元素 n 1 ? ua? 2．運(yùn)算和實(shí)現(xiàn) 線性表通常采用順序和鏈表兩種物理實(shí)現(xiàn)。對(duì)于經(jīng)常變化的表，通常采取鏈表結(jié)構(gòu)。線性表常用的運(yùn)算主要有：插入、刪除、查詢和遍歷。 ? ① 插入 在保持原有的存儲(chǔ)結(jié)構(gòu)的前提下，根據(jù)插入要求，在適當(dāng)?shù)奈恢貌迦胍粋€(gè)元素。插入操作要求線性表要有足夠的存放新元素的空間，如果空間不足，插入操作無(wú)法進(jìn)行，線性表會(huì)溢出。 ? ②刪除 在線性表中，找到滿足條件的數(shù)據(jù)元素，并刪除。如果線性表為空，刪除就會(huì)失敗。 ? ③ 查詢 在線性表中，按照查詢條件，定位數(shù)據(jù)元素的過(guò)程就是查詢。查詢的條件一般根據(jù)數(shù)據(jù)元素中的關(guān)鍵字進(jìn)行。實(shí)際上，數(shù)據(jù)的插入和刪除都需要首先定位數(shù)據(jù)元素。對(duì)于空的線性表是無(wú)法查詢的。 ? ④遍歷 是指按照某種方式，逐一訪問(wèn)線性表中的每一個(gè)數(shù)據(jù)元素，并執(zhí)行相同處理的操作。這里的處理可以是讀、寫、或查詢等。 棧 ? 1．定義 對(duì)于由 N個(gè)數(shù)據(jù)元素構(gòu)成的一個(gè)線性序列，如果只允許在其固定的一端位置插入和刪除一個(gè)數(shù)據(jù)元素，那么這種邏輯結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)稱為 堆棧或棧 (stack)。 允許插入或刪除的這一端稱為 棧項(xiàng) ，另一個(gè)固定端稱為 棧底 。當(dāng)表中沒(méi)有元素時(shí)稱為 空棧 。 2．運(yùn)算和實(shí)現(xiàn) ? 棧的基本運(yùn)算主要有：入棧、出棧和判斷。 ? ①入棧 入棧也叫壓棧，是在棧頂添加新元素的操作，新的元素入棧后成為新的棧頂元素。 ? ②出棧 出棧也叫退棧或彈棧，是將棧頂元素從棧中退出并傳遞給用戶程序的操作 D C B A 入棧數(shù)據(jù)元素 E E D C B A D C B A 出棧數(shù)據(jù)元素 D C B A ? ③ 判斷 判斷操作用來(lái)檢查棧內(nèi)數(shù)據(jù)是否為空，返回結(jié)果是一個(gè)邏輯值：真或假。如果棧頂和棧底重合，說(shuō)明堆棧為空。 隊(duì)列 ? 1．定義 對(duì)于由 N個(gè)數(shù)據(jù)元素構(gòu)成的一個(gè)線性序列，如果在其固定的一端只允許插入數(shù)據(jù)元素，且在另一端只允許刪除數(shù)據(jù)元素，則這種邏輯結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)稱為 隊(duì)列 (queue)。 把允許插入的一端叫 隊(duì)尾 (rear)，把只允許刪除的一端叫 隊(duì)首 (front)。 2．運(yùn)算 ? 隊(duì)列的基本運(yùn)算主要有：入隊(duì)、出隊(duì)和判斷。 ? ①入隊(duì) 入隊(duì)是在隊(duì)列中插入一個(gè)新數(shù)據(jù)元素的過(guò)程，插入在隊(duì)尾進(jìn)行，新的元素成為隊(duì)尾。 ? ②出隊(duì) 出隊(duì)是在隊(duì)列中刪除一個(gè)數(shù)據(jù)元素的過(guò)程，刪除在隊(duì)首進(jìn)行并把出來(lái)的數(shù)據(jù)傳遞給用戶程序。 A B C D E 頭指針 尾指針 A B C D E F G 頭指針 尾指針 F ， G 入隊(duì) A B C D E 頭指針 尾指針 D E F G 頭指針 尾指針 A ， B ， C 出隊(duì) ? ③ 判斷： 判斷操作用來(lái)檢查隊(duì)列是否為空，返回結(jié)果是一個(gè)邏輯值：真或假，如圖。 頭指針 尾指針 3．循環(huán)隊(duì)列的實(shí)現(xiàn) F G A B C D E 頭指針 尾指針 內(nèi)存塊第一個(gè)存儲(chǔ)單元 內(nèi)存塊最后一個(gè)存儲(chǔ)單元 隊(duì)列移動(dòng) 樹 ? 1．定義 樹形數(shù)據(jù)結(jié)構(gòu)中，每個(gè)數(shù)據(jù)元素稱為是一個(gè)節(jié)點(diǎn)，除了一個(gè)惟一的所謂 根節(jié)點(diǎn) 外，其他每個(gè)節(jié)點(diǎn)都有且只有一個(gè)父節(jié)點(diǎn)，每個(gè)元素可以有多個(gè)子節(jié)點(diǎn)。 樹主要用在大型、動(dòng)態(tài)列表的搜索，人工智能系統(tǒng)和編碼算法等問(wèn)題中。 2．運(yùn)算 ? 樹常見的基本運(yùn)算有：插入、刪除和遍歷。 ? ①插入 在樹中合適的位置，添加一個(gè)節(jié)點(diǎn)，通常插入新的節(jié)點(diǎn)后，仍然應(yīng)該保持該樹本身所具有的性質(zhì)。 ? ②刪除 在樹中找到滿足條件的節(jié)點(diǎn)并刪除。通常刪除節(jié)點(diǎn)后，也要保持該樹本身所具有的性質(zhì)。 ? ③遍歷 按照某種順序或規(guī)則，對(duì)樹中的每個(gè)節(jié)點(diǎn)逐一進(jìn)行訪問(wèn)的過(guò)程。 3．實(shí)現(xiàn) Left A Right Left B Right ^ C Right ^ D ^ ^ E ^ ^ F ^ 圖 ? 1．定義 在圖形結(jié)構(gòu)中，每個(gè)數(shù)據(jù)元素稱為一個(gè)頂點(diǎn)，任意兩個(gè)頂點(diǎn)之間都可能相關(guān)，這種相關(guān)性用一條邊來(lái)表示，頂點(diǎn)之間的鄰接關(guān)系可以是任意的。 圖可以用來(lái)描述計(jì)算機(jī)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，以及圖論中獲得最小生成樹。除此以外，圖在自然科學(xué)、社會(huì)科學(xué)和人文科學(xué)等許多領(lǐng)域也都有著非常廣泛的應(yīng)用。 2．運(yùn)算 ? 常見的基本運(yùn)算有：添加頂點(diǎn)、刪除頂點(diǎn)、添加邊、刪除邊和遍歷