6.1數(shù)據(jù)結(jié)構(gòu)概述6.2幾種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)介紹第6章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)6.1數(shù)據(jù)結(jié)構(gòu)概述第6章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)6.1數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)課程的地位：數(shù)據(jù)結(jié)構(gòu)課程是計(jì)算機(jī)專業(yè)的一門核心專業(yè)基礎(chǔ)課程。數(shù)據(jù)結(jié)構(gòu)幾乎是所有計(jì)算機(jī)核心課程的必修先行課，如數(shù)據(jù)庫概論、軟件工程、編譯原理、操作系統(tǒng)等，此外更是高層次的計(jì)算機(jī)應(yīng)用處理技術(shù)及科學(xué)的根基所在，如人工智能、模式識別和機(jī)器學(xué)習(xí)，網(wǎng)絡(luò)信息處理及安全、多媒體技術(shù)(圖像、音視頻和文本)等。6.1數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)課程的地位：6.1.2基本概念和術(shù)語數(shù)據(jù)：客觀事物的符號表示，在計(jì)算機(jī)中是指所有能輸入計(jì)算機(jī)并能被計(jì)算機(jī)處理的符號的總稱。數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)元素之間邏輯上的聯(lián)系，是從邏輯關(guān)系上來描述數(shù)據(jù)，通常把數(shù)據(jù)的邏輯結(jié)構(gòu)簡稱為數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)分為兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)6.1.2基本概念和術(shù)語數(shù)據(jù)：客觀事物的符號表示，在計(jì)算機(jī)6.1.2基本概念和術(shù)語線性結(jié)構(gòu)如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個(gè)條件有且只有一個(gè)根結(jié)點(diǎn)；每一個(gè)結(jié)點(diǎn)最多有一個(gè)前驅(qū)，也最多有一個(gè)后繼。則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。線性表、棧、隊(duì)列都屬于線性結(jié)構(gòu)。非線性結(jié)構(gòu)如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱為非線性結(jié)構(gòu)。樹、圖等都屬于非線性結(jié)構(gòu)。6.1.2基本概念和術(shù)語線性結(jié)構(gòu)6.1.2基本概念和術(shù)語常用的數(shù)據(jù)結(jié)構(gòu)有集合、線性結(jié)構(gòu)、樹、圖①集合②線性結(jié)構(gòu)③樹④圖6.1.2基本概念和術(shù)語常用的數(shù)據(jù)結(jié)構(gòu)有集合、線性結(jié)構(gòu)、樹6.1.2基本概念和術(shù)語數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲設(shè)備中的映像，包括數(shù)據(jù)元素的表示和關(guān)系的表示。數(shù)據(jù)的存儲結(jié)構(gòu)有兩種：順序結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)順序存儲結(jié)構(gòu)是將邏輯上相鄰的元素存儲在物理位置上相鄰的存儲單元里，元素之間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)，如圖所示6.1.2基本概念和術(shù)語數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)6.1.2基本概念和術(shù)語鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)借助于指示數(shù)據(jù)元素地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。如圖2所示6.1.2基本概念和術(shù)語鏈?zhǔn)酱鎯Y(jié)構(gòu)6.1.2基本概念和術(shù)語數(shù)據(jù)的運(yùn)算不同的數(shù)據(jù)結(jié)構(gòu)各有其相應(yīng)的若干運(yùn)算，常用的運(yùn)算有插入、刪除、修改、查找、排序等。6.1.2基本概念和術(shù)語數(shù)據(jù)的運(yùn)算6.2幾種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)介紹

6.2幾種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)介紹

6.2幾種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)介紹6.2.1線性表6.2.2棧和隊(duì)列6.2.3樹6.2.4圖6.2幾種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)介紹6.2.1線性表6.2.1線性表

6.2.1線性表

6.2.1線性表復(fù)雜的線性表學(xué)號姓名性別專業(yè)出生日期201307024114張慧媛女計(jì)算機(jī)1994-2-25201307024126柳青女電子信息1996-4-8201405034209韓旭男會計(jì)1995-12-12201405034208趙琳琳女英語1995-10-10201405034213袁小梅女安全工程1996-2-196.2.1線性表復(fù)雜的線性表學(xué)號姓名性別專業(yè)出生日期2016.2.1線性表非空線性表有如下特征：有且只有一個(gè)根結(jié)點(diǎn)無前驅(qū)；有且只有一個(gè)終端結(jié)點(diǎn)無后繼；除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其它結(jié)點(diǎn)有且只有一個(gè)前驅(qū)，也有且只有一個(gè)后繼；線性表結(jié)點(diǎn)的個(gè)數(shù)n稱為線性表的長度。當(dāng)n=0時(shí)，稱為空表。6.2.1線性表非空線性表有如下特征：6.2.1線性表

6.2.1線性表

6.2.1線性表順序表的基本運(yùn)算（2）刪除線性表的刪除運(yùn)算是指將表的第i個(gè)元素刪去，使長度為n的線性表變成長度為n-1的線性表，如圖6.6所示。6.2.1線性表順序表的基本運(yùn)算6.2.1線性表順序表的基本運(yùn)算（3）查找

查找運(yùn)算可采用順序查找法實(shí)現(xiàn)，即從第一個(gè)元素開始，依次將表中元素與被查找的元素相比較，若相等則查找成功，否則返回失敗信息。6.2.1線性表順序表的基本運(yùn)算6.2.1線性表

(a)插入前(b)插入后6.2.1線性表

(a)插入前(b)插入后6.2.1線性表單鏈表的基本運(yùn)算（2）刪除單鏈表的刪除運(yùn)算是指刪除第i個(gè)位置的結(jié)點(diǎn)，刪除操作也需要從單鏈表的頭地址開始遍歷，直到找到第i個(gè)位置的結(jié)點(diǎn)。(a)刪除前(b)刪除后6.2.1線性表單鏈表的基本運(yùn)算(a)刪除前(b)刪除后6.2.1線性表單鏈表的基本運(yùn)算（3）查找單鏈表中的按值查找是指在表中查找其值滿足給定值的結(jié)點(diǎn)。查找運(yùn)算同樣還是從頭地址開始遍歷，依次將被遍歷到的結(jié)點(diǎn)的值與給定值比較，若相等，則返回查找成功信息，否則返回失敗信息。6.2.1線性表單鏈表的基本運(yùn)算6.2.2棧和隊(duì)列棧棧（Stack）也可稱為堆棧，是一種特殊的線性表，這種線性表只允許在線性表的一端（稱為棧頂，Top）進(jìn)行插入和刪除運(yùn)算，而棧的另一端則稱為棧底（Bottom）。當(dāng)棧中沒有元素時(shí)，稱為空棧。棧的基本運(yùn)算有三種：入棧、出棧與讀棧頂元素6.2.2棧和隊(duì)列棧棧的基本運(yùn)算（1）入棧運(yùn)算入棧運(yùn)算是指在棧頂位置插入一個(gè)新元素，這個(gè)運(yùn)算有兩個(gè)基本操作：首先將棧頂指針加1（top+1），然后將新元素插入到棧頂指針指向的位置。若棧頂指針已經(jīng)指向存儲空間的最后一個(gè)位置時(shí)，說明棧空間已滿，不能進(jìn)行入棧操作。（2）出棧運(yùn)算出棧運(yùn)算是指取出棧頂元素并賦值給一個(gè)指定的變量。這個(gè)運(yùn)算有兩個(gè)基本操作：首先將棧頂元素賦值給指定的變量，然后將棧頂指針減1（top-1）。若棧頂指針為0時(shí)，說明?？眨荒苓M(jìn)行出棧操作。（3）讀棧頂元素讀棧頂元素是指將棧頂元素賦值給一個(gè)指定的變量，注意：這個(gè)運(yùn)算不刪除棧頂元素，因此棧頂?shù)闹羔槻蛔儭．?dāng)棧頂指針為0時(shí)，說明棧空，讀不到棧頂元素。棧的基本運(yùn)算（1）入棧運(yùn)算6.2.2棧和隊(duì)列隊(duì)列隊(duì)列是另一種特殊的線性表，在這種表中，刪除運(yùn)算限定在表的一端進(jìn)行，而插入操作在表的另一端進(jìn)行。約定把允許插入的一端稱為隊(duì)尾（rear），把允許刪除的一端稱為隊(duì)首（front）。位于隊(duì)首和隊(duì)尾的元素分別叫做隊(duì)首元素和隊(duì)尾元素。隊(duì)列又被稱為先進(jìn)先出表（FirstInFirstOut，F(xiàn)IFO）隊(duì)列的基本運(yùn)算有三種：入隊(duì)、出隊(duì)6.2.2棧和隊(duì)列隊(duì)列隊(duì)列的基本運(yùn)算（1）入隊(duì)運(yùn)算入隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的隊(duì)尾加入一個(gè)新元素。這個(gè)運(yùn)算有兩個(gè)基本操作：首先將隊(duì)尾指針加1，當(dāng)rear=m+1時(shí)置rear=1，然后將新元素插入到隊(duì)尾指針指向的位置。當(dāng)循環(huán)隊(duì)列非空（s=1）且隊(duì)尾指針等于隊(duì)頭指針時(shí)，說明循環(huán)隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算。（2）出隊(duì)運(yùn)算出隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的隊(duì)首位置退出一個(gè)元素并賦值給指定的變量。這個(gè)運(yùn)算有兩個(gè)操作：首先將隊(duì)頭指針加1，并當(dāng)front=m+1時(shí)置front=1，然后將隊(duì)頭指針指向的元素賦給指定的變量。當(dāng)循環(huán)隊(duì)列為空（s=0）時(shí)，不能進(jìn)行出隊(duì)運(yùn)算。隊(duì)列的基本運(yùn)算（1）入隊(duì)運(yùn)算6.2.3樹樹（tree）是由n（n≥0）個(gè)有限結(jié)點(diǎn)組成的一個(gè)具有層序關(guān)系的集合。把它叫做“樹”是因?yàn)樗雌饋硐褚活w倒置的樹。樹具有以下特點(diǎn)。每個(gè)結(jié)點(diǎn)有零個(gè)或多個(gè)子結(jié)點(diǎn)；每個(gè)子結(jié)點(diǎn)只有一個(gè)父結(jié)點(diǎn)；沒有前驅(qū)的結(jié)點(diǎn)為根結(jié)點(diǎn)；除了根結(jié)點(diǎn)外，每個(gè)子結(jié)點(diǎn)可以分為m個(gè)不相交的子樹。6.2.3樹樹（tree）是由n（n≥0）個(gè)有限結(jié)點(diǎn)組成的樹樹的相關(guān)術(shù)語（1）結(jié)點(diǎn)：結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素及描述與其它結(jié)點(diǎn)關(guān)系的信息（如前驅(qū)、后繼指針），一般出現(xiàn)在鏈?zhǔn)酱鎯Y(jié)構(gòu)中。（2）結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)含有的子樹的個(gè)數(shù)稱為該結(jié)點(diǎn)的度。（3）樹的度：一棵樹中，最大的結(jié)點(diǎn)的度稱為樹的度樹樹的相關(guān)術(shù)語樹樹的相關(guān)術(shù)語（4）葉結(jié)點(diǎn)或終端結(jié)點(diǎn)：度為零的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)，也稱為葉子結(jié)點(diǎn)，葉子結(jié)點(diǎn)是無后繼結(jié)點(diǎn)的。（5）非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)：度不為零的結(jié)點(diǎn)稱為非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)。（6）雙親結(jié)點(diǎn)或父結(jié)點(diǎn)：若一個(gè)結(jié)點(diǎn)含有子結(jié)點(diǎn)，則這個(gè)結(jié)點(diǎn)稱為其子結(jié)點(diǎn)的父結(jié)點(diǎn)或雙親結(jié)點(diǎn)。孩子結(jié)點(diǎn)和雙親結(jié)點(diǎn)是相對的。樹樹的相關(guān)術(shù)語樹樹的相關(guān)術(shù)語（7）孩子結(jié)點(diǎn)或子結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)含有的子樹的根結(jié)點(diǎn)稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)或孩子結(jié)點(diǎn)。（8）結(jié)點(diǎn)的層數(shù)：樹中規(guī)定根的層數(shù)為1，其余結(jié)點(diǎn)的層數(shù)等于其雙親結(jié)點(diǎn)的層數(shù)加1。（9）樹的深度：樹中結(jié)點(diǎn)層數(shù)的最大值稱為該樹的深度或高度樹樹的相關(guān)術(shù)語二叉樹

二叉樹

二叉樹(a)滿二叉樹(b)完全二叉樹二叉樹(a)滿二叉樹(b)完全二叉樹二叉樹的存儲結(jié)構(gòu)二叉樹的結(jié)構(gòu)是非線性的，每個(gè)結(jié)點(diǎn)最多可有兩個(gè)后繼。通常用鏈?zhǔn)酱鎯Y(jié)構(gòu)對二叉樹進(jìn)行存儲。二叉樹的存儲結(jié)構(gòu)二叉樹的結(jié)構(gòu)是非線性的，每個(gè)結(jié)點(diǎn)最多可有兩個(gè)二叉樹的遍歷二叉樹的遍歷是指按照一定的規(guī)則訪問二叉樹的各個(gè)結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)都被且只被訪問一次。二叉樹遍歷的實(shí)質(zhì)是將非線性結(jié)構(gòu)的數(shù)據(jù)線性化的過程。在遍歷二叉樹的過程中，一般先遍歷左子樹，然后再遍歷右子樹。根據(jù)訪問根結(jié)點(diǎn)的次序二叉樹遍歷可以分為三種：前序遍歷、中序遍歷和后序遍歷。二叉樹的遍歷二叉樹的遍歷是指按照一定的規(guī)則訪問二叉樹的各個(gè)結(jié)二叉樹的遍歷(1)前序遍歷訪問根結(jié)點(diǎn)；前序遍歷左子樹；前序遍歷右子樹；前序遍歷結(jié)點(diǎn)的次序?yàn)椋篈、B、D、E、H、I、C、F、J、G。(2)中序遍歷中序遍歷左子樹；訪問根結(jié)點(diǎn)；中序遍歷右子樹；中序遍歷結(jié)點(diǎn)的次序?yàn)椋篋、B、H、E、I、A、F、J、C、G。(3)后序遍歷后序遍歷左子樹；后序遍歷右子樹；訪問根結(jié)點(diǎn)；后序遍歷結(jié)點(diǎn)的次序?yàn)椋篋、H、I、E、B、J、F、G、C、A。二叉樹的遍歷(1)前序遍歷6.2.4圖圖（Graph）是非空的頂點(diǎn)集合和描述頂點(diǎn)之間關(guān)系——邊或弧的集合的組成，如圖6.21所示。圖的定義形式為：G=(V,E)，其中，G表示圖，V表示頂點(diǎn)的集合，E表示邊或弧的集合。6.2.4圖圖（Graph）是非空的頂點(diǎn)集合和描述頂點(diǎn)之間6.2.4圖圖的相關(guān)術(shù)語無向圖有向圖頂點(diǎn)的度6.2.4圖圖的相關(guān)術(shù)語小結(jié)1.數(shù)據(jù)結(jié)構(gòu)的基本術(shù)語2.線性表3.棧4.隊(duì)列5.樹6.圖小結(jié)1.數(shù)據(jù)結(jié)構(gòu)的基本術(shù)語6.1數(shù)據(jù)結(jié)構(gòu)概述6.2幾種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)介紹第6章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)6.1數(shù)據(jù)結(jié)構(gòu)概述第6章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)6.1數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)課程的地位：數(shù)據(jù)結(jié)構(gòu)課程是計(jì)算機(jī)專業(yè)的一門核心專業(yè)基礎(chǔ)課程。數(shù)據(jù)結(jié)構(gòu)幾乎是所有計(jì)算機(jī)核心課程的必修先行課，如數(shù)據(jù)庫概論、軟件工程、編譯原理、操作系統(tǒng)等，此外更是高層次的計(jì)算機(jī)應(yīng)用處理技術(shù)及科學(xué)的根基所在，如人工智能、模式識別和機(jī)器學(xué)習(xí)，網(wǎng)絡(luò)信息處理及安全、多媒體技術(shù)(圖像、音視頻和文本)等。6.1數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)課程的地位：6.1.2基本概念和術(shù)語數(shù)據(jù)：客觀事物的符號表示，在計(jì)算機(jī)中是指所有能輸入計(jì)算機(jī)并能被計(jì)算機(jī)處理的符號的總稱。數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)元素之間邏輯上的聯(lián)系，是從邏輯關(guān)系上來描述數(shù)據(jù)，通常把數(shù)據(jù)的邏輯結(jié)構(gòu)簡稱為數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)分為兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)6.1.2基本概念和術(shù)語數(shù)據(jù)：客觀事物的符號表示，在計(jì)算機(jī)6.1.2基本概念和術(shù)語線性結(jié)構(gòu)如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個(gè)條件有且只有一個(gè)根結(jié)點(diǎn)；每一個(gè)結(jié)點(diǎn)最多有一個(gè)前驅(qū)，也最多有一個(gè)后繼。則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。線性表、棧、隊(duì)列都屬于線性結(jié)構(gòu)。非線性結(jié)構(gòu)如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱為非線性結(jié)構(gòu)。樹、圖等都屬于非線性結(jié)構(gòu)。6.1.2基本概念和術(shù)語線性結(jié)構(gòu)6.1.2基本概念和術(shù)語常用的數(shù)據(jù)結(jié)構(gòu)有集合、線性結(jié)構(gòu)、樹、圖①集合②線性結(jié)構(gòu)③樹④圖6.1.2基本概念和術(shù)語常用的數(shù)據(jù)結(jié)構(gòu)有集合、線性結(jié)構(gòu)、樹6.1.2基本概念和術(shù)語數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲設(shè)備中的映像，包括數(shù)據(jù)元素的表示和關(guān)系的表示。數(shù)據(jù)的存儲結(jié)構(gòu)有兩種：順序結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)順序存儲結(jié)構(gòu)是將邏輯上相鄰的元素存儲在物理位置上相鄰的存儲單元里，元素之間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)，如圖所示6.1.2基本概念和術(shù)語數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)6.1.2基本概念和術(shù)語鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)借助于指示數(shù)據(jù)元素地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。如圖2所示6.1.2基本概念和術(shù)語鏈?zhǔn)酱鎯Y(jié)構(gòu)6.1.2基本概念和術(shù)語數(shù)據(jù)的運(yùn)算不同的數(shù)據(jù)結(jié)構(gòu)各有其相應(yīng)的若干運(yùn)算，常用的運(yùn)算有插入、刪除、修改、查找、排序等。6.1.2基本概念和術(shù)語數(shù)據(jù)的運(yùn)算6.2幾種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)介紹

6.2幾種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)介紹

6.2幾種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)介紹6.2.1線性表6.2.2棧和隊(duì)列6.2.3樹6.2.4圖6.2幾種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)介紹6.2.1線性表6.2.1線性表

6.2.1線性表

6.2.1線性表復(fù)雜的線性表學(xué)號姓名性別專業(yè)出生日期201307024114張慧媛女計(jì)算機(jī)1994-2-25201307024126柳青女電子信息1996-4-8201405034209韓旭男會計(jì)1995-12-12201405034208趙琳琳女英語1995-10-10201405034213袁小梅女安全工程1996-2-196.2.1線性表復(fù)雜的線性表學(xué)號姓名性別專業(yè)出生日期2016.2.1線性表非空線性表有如下特征：有且只有一個(gè)根結(jié)點(diǎn)無前驅(qū)；有且只有一個(gè)終端結(jié)點(diǎn)無后繼；除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其它結(jié)點(diǎn)有且只有一個(gè)前驅(qū)，也有且只有一個(gè)后繼；線性表結(jié)點(diǎn)的個(gè)數(shù)n稱為線性表的長度。當(dāng)n=0時(shí)，稱為空表。6.2.1線性表非空線性表有如下特征：6.2.1線性表

6.2.1線性表

6.2.1線性表順序表的基本運(yùn)算（2）刪除線性表的刪除運(yùn)算是指將表的第i個(gè)元素刪去，使長度為n的線性表變成長度為n-1的線性表，如圖6.6所示。6.2.1線性表順序表的基本運(yùn)算6.2.1線性表順序表的基本運(yùn)算（3）查找

查找運(yùn)算可采用順序查找法實(shí)現(xiàn)，即從第一個(gè)元素開始，依次將表中元素與被查找的元素相比較，若相等則查找成功，否則返回失敗信息。6.2.1線性表順序表的基本運(yùn)算6.2.1線性表

(a)插入前(b)插入后6.2.1線性表

(a)插入前(b)插入后6.2.1線性表單鏈表的基本運(yùn)算（2）刪除單鏈表的刪除運(yùn)算是指刪除第i個(gè)位置的結(jié)點(diǎn)，刪除操作也需要從單鏈表的頭地址開始遍歷，直到找到第i個(gè)位置的結(jié)點(diǎn)。(a)刪除前(b)刪除后6.2.1線性表單鏈表的基本運(yùn)算(a)刪除前(b)刪除后6.2.1線性表單鏈表的基本運(yùn)算（3）查找單鏈表中的按值查找是指在表中查找其值滿足給定值的結(jié)點(diǎn)。查找運(yùn)算同樣還是從頭地址開始遍歷，依次將被遍歷到的結(jié)點(diǎn)的值與給定值比較，若相等，則返回查找成功信息，否則返回失敗信息。6.2.1線性表單鏈表的基本運(yùn)算6.2.2棧和隊(duì)列棧棧（Stack）也可稱為堆棧，是一種特殊的線性表，這種線性表只允許在線性表的一端（稱為棧頂，Top）進(jìn)行插入和刪除運(yùn)算，而棧的另一端則稱為棧底（Bottom）。當(dāng)棧中沒有元素時(shí)，稱為空棧。棧的基本運(yùn)算有三種：入棧、出棧與讀棧頂元素6.2.2棧和隊(duì)列棧棧的基本運(yùn)算（1）入棧運(yùn)算入棧運(yùn)算是指在棧頂位置插入一個(gè)新元素，這個(gè)運(yùn)算有兩個(gè)基本操作：首先將棧頂指針加1（top+1），然后將新元素插入到棧頂指針指向的位置。若棧頂指針已經(jīng)指向存儲空間的最后一個(gè)位置時(shí)，說明?？臻g已滿，不能進(jìn)行入棧操作。（2）出棧運(yùn)算出棧運(yùn)算是指取出棧頂元素并賦值給一個(gè)指定的變量。這個(gè)運(yùn)算有兩個(gè)基本操作：首先將棧頂元素賦值給指定的變量，然后將棧頂指針減1（top-1）。若棧頂指針為0時(shí)，說明?？?，不能進(jìn)行出棧操作。（3）讀棧頂元素讀棧頂元素是指將棧頂元素賦值給一個(gè)指定的變量，注意：這個(gè)運(yùn)算不刪除棧頂元素，因此棧頂?shù)闹羔槻蛔?。?dāng)棧頂指針為0時(shí)，說明?？?，讀不到棧頂元素。棧的基本運(yùn)算（1）入棧運(yùn)算6.2.2棧和隊(duì)列隊(duì)列隊(duì)列是另一種特殊的線性表，在這種表中，刪除運(yùn)算限定在表的一端進(jìn)行，而插入操作在表的另一端進(jìn)行。約定把允許插入的一端稱為隊(duì)尾（rear），把允許刪除的一端稱為隊(duì)首（front）。位于隊(duì)首和隊(duì)尾的元素分別叫做隊(duì)首元素和隊(duì)尾元素。隊(duì)列又被稱為先進(jìn)先出表（FirstInFirstOut，F(xiàn)IFO）隊(duì)列的基本運(yùn)算有三種：入隊(duì)、出隊(duì)6.2.2棧和隊(duì)列隊(duì)列隊(duì)列的基本運(yùn)算（1）入隊(duì)運(yùn)算入隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的隊(duì)尾加入一個(gè)新元素。這個(gè)運(yùn)算有兩個(gè)基本操作：首先將隊(duì)尾指針加1，當(dāng)rear=m+1時(shí)置rear=1，然后將新元素插入到隊(duì)尾指針指向的位置。當(dāng)循環(huán)隊(duì)列非空（s=1）且隊(duì)尾指針等于隊(duì)頭指針時(shí)，說明循環(huán)隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算。（2）出隊(duì)運(yùn)算出隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的隊(duì)首位置退出一個(gè)元素并賦值給指定的變量。這個(gè)運(yùn)算有兩個(gè)操作：首先將隊(duì)頭指針加1，并當(dāng)front=m+1時(shí)置front=1，然后將隊(duì)頭指針指向的元素賦給指定的變量。當(dāng)循環(huán)隊(duì)列為空（s=0）時(shí)，不能進(jìn)行出隊(duì)運(yùn)算。隊(duì)列的基本運(yùn)算（1）入隊(duì)運(yùn)算6.2.3樹樹（tree）是由n（n≥0）個(gè)有限結(jié)點(diǎn)組成的一個(gè)具有層序關(guān)系的集合。把它叫做“樹”是因?yàn)樗雌饋硐褚活w倒置的樹。樹具有以下特點(diǎn)。每個(gè)結(jié)點(diǎn)有零個(gè)或多個(gè)子結(jié)點(diǎn)；每個(gè)子結(jié)點(diǎn)只有一個(gè)父結(jié)點(diǎn)；沒有前驅(qū)的結(jié)點(diǎn)為根結(jié)點(diǎn)；除了根結(jié)點(diǎn)外，每個(gè)子結(jié)點(diǎn)可以分為m個(gè)不相交的子樹。6.2.3樹樹（tree）是由n（n≥0）個(gè)有限結(jié)點(diǎn)組成的樹樹的相關(guān)術(shù)語（1）結(jié)點(diǎn)：結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素及描述與其它結(jié)點(diǎn)關(guān)系的信息（如前驅(qū)、后繼指針），一般出現(xiàn)在鏈?zhǔn)酱鎯Y(jié)構(gòu)中。（2）結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)含有的子樹的個(gè)數(shù)稱為該結(jié)點(diǎn)的度。（3）樹的度：一棵樹中，最大的結(jié)點(diǎn)的度稱為樹的度樹樹的相關(guān)術(shù)語樹樹的相關(guān)術(shù)語（4）葉結(jié)點(diǎn)或終端結(jié)點(diǎn)：度為零的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)，也稱為葉子結(jié)點(diǎn)，葉子結(jié)點(diǎn)是無后繼結(jié)點(diǎn)的。（5）非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)：度不為零的結(jié)點(diǎn)稱為非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)。（6）雙親結(jié)點(diǎn)或父結(jié)點(diǎn)：若一個(gè)結(jié)點(diǎn)含有子結(jié)點(diǎn)，則這個(gè)結(jié)點(diǎn)稱為其子結(jié)點(diǎn)的父結(jié)點(diǎn)或雙親結(jié)點(diǎn)。孩子結(jié)點(diǎn)和雙親結(jié)點(diǎn)是相對的。樹樹的相關(guān)術(shù)語樹樹的相關(guān)術(shù)語（7）孩子結(jié)點(diǎn)或子結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)含有的子樹的根結(jié)點(diǎn)稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)或孩子結(jié)點(diǎn)。（8）