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