數(shù)據(jù)結(jié)構(gòu)（從概念到算法）課件

第2章線性表01020304目錄CONTENTS05線性表的基本概念線性表順序存儲結(jié)構(gòu)定義及實(shí)現(xiàn)線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)定義及實(shí)現(xiàn)順序表與鏈表的比較應(yīng)用實(shí)例06本章小結(jié)01PART線性表的基本概念線性表（LinearList）是由n（n≥0）個數(shù)據(jù)元素(a1,a2,…,an)構(gòu)成的有限序列，記作L=(a1,a2,…,an)。其中線性表的表長即是表中所包含數(shù)據(jù)元素的個數(shù)，而空表指的是不含數(shù)據(jù)元素的線性表。線性表在理論上的定義如下：對于線性表L=(a1,a2,…,ai-1,ai,ai+1,…,an)，有

（1）ai-1

在

ai之前，稱

ai-1

是

ai的直接前驅(qū)（1＜i≤n）；

（2）ai+1在

ai之后，稱

ai+1是

ai的直接后繼（1≤i＜n）；

（3）首元素a1沒有前驅(qū)；

（4）尾元素an沒有后繼；

（5）任意元素ai（1＜i＜n）有且僅有一個直接前驅(qū)和一個直接后繼。線性表的基本概念線性表的抽象數(shù)據(jù)類型從邏輯上定義線性表這種數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)對象、數(shù)據(jù)對象之間的關(guān)系，以及相關(guān)的基本操作。其中，數(shù)據(jù)對象說明線性表中的每個數(shù)據(jù)元素均屬于某個類型（如整型、實(shí)型或字符型等），用一個集合表示：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}。其中，線性關(guān)系運(yùn)用<ai-1,ai>序偶對來表示前驅(qū)和后繼的關(guān)系。線性表的基本概念線性表的抽象數(shù)據(jù)類型定義如下：02PART線性表順序存儲結(jié)構(gòu)定義及實(shí)現(xiàn)線性表順序存儲結(jié)構(gòu)指的是將線性表中的數(shù)據(jù)元素依次存放到計算機(jī)存儲器內(nèi)一組地址連續(xù)的存儲單元中，這種分配方式稱為順序分配或順序映像。在順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個數(shù)據(jù)元素在物理存儲空間中也相鄰。線性表順序存儲結(jié)構(gòu)定義及實(shí)現(xiàn)其中，線性表(a1,a2,…,an)順序存儲結(jié)構(gòu)的一般形式如下圖所示。下圖用一個“井”狀結(jié)構(gòu)來表示內(nèi)存，每一個格子表示存儲一個數(shù)據(jù)元素的空間，a1,a2,…,an按順序存儲在以b開始的連續(xù)地址空間中。b：表示表的首地址/基地址/元素a1的地址。p：表示1個數(shù)據(jù)元素所占據(jù)存儲單元的數(shù)量。MaxLength：表示最大長度，通常為某個常數(shù)。線性表順序存儲結(jié)構(gòu)定義及實(shí)現(xiàn)線性表順序存儲結(jié)構(gòu)的定義如下：其中，elem是一個大小為MaxLength的數(shù)據(jù)元素數(shù)組；length為線性表表長；SqList為此結(jié)構(gòu)類型定義的名稱。線性表順序存儲結(jié)構(gòu)定義及實(shí)現(xiàn)前面的順序存儲是靜態(tài)分配的。靜態(tài)分配是指在編譯時分配給線性表一個固定大小的存儲空間（一般是程序運(yùn)行時邏輯空間的?？臻g（StackSpace））。如果插入的元素超過這個存儲空間的大小，就會發(fā)生溢出。為解決這一問題，引入了順序存儲結(jié)構(gòu)的動態(tài)分配。線性表順序存儲結(jié)構(gòu)定義及實(shí)現(xiàn)動態(tài)分配，即當(dāng)數(shù)據(jù)元素超過所分配存儲空間的大小時，在堆空間中再找一片更大的連續(xù)空間重新分配，將所有的數(shù)據(jù)元素放入。順序存儲的動態(tài)分配定義如下：其中，LIST_INIT_SIZE表示第一次為順序表分配的存儲空間大?。籐ISTINCREMENT表示次需要擴(kuò)充存儲空間時的增量；elem是一個元素的指針，保存存儲空間中第一個數(shù)據(jù)元素的地址，并且一旦需要擴(kuò)充線性表的存儲空間，可能需要改變elem，使其指向新空間的起始位置。線性表順序存儲結(jié)構(gòu)定義及實(shí)現(xiàn)1、插入元素順序表插入新元素：設(shè)L.elem[0]…L.elem[MaxLength-1]中有l(wèi)ength個元素，在第i個元素（L.elem[i-1]）之前插入新元素e，其中1≤i≤length+1，當(dāng)i等于length+1時，表示在尾部添加一個新元素。在線性表L=(a1,a2,…,ai-1,ai,ai+1,…,an)中的第i個元素前插入元素e，an、an-1……ai+1、ai均要依次往后移動，那么移動元素的下標(biāo)范圍是i-1～n-1或i-1～L.length-1，這里L(fēng).length的值為n。注意移動元素的方向是從an到ai方向依次把每個元素往后移動一個位置，如下圖所示。線性表順序存儲結(jié)構(gòu)定義及實(shí)現(xiàn)順序表插入算法分為靜態(tài)分配順序表插入算法和動態(tài)分配順序表插入算法。靜態(tài)分配插入算法的基本思想為：先判斷插入的位置是否合理，接著判斷表長是否達(dá)到分配空間的最大值，然后從線性表中的最后一個元素到插入位置的所有元素，依次往后移動一個元素的位置，這樣給待插入的元素留出一個空位置，最后把新增元素插入這個空位置，表長增加1，插入成功返回。在動態(tài)分配空間的順序表中，如果插入元素使得表長超過所分配的空間大小，就利用realloc這個函數(shù)尋找更大片的連續(xù)地址空間。如果沒有找到，說明還是會溢出（當(dāng)然這種情況很少發(fā)生）；如果找到了，就將基地址改為新的地址，分配的存儲空間也增加。而動態(tài)分配插入新元素所做的操作與靜態(tài)分配是一樣的，均是移動相應(yīng)元素。線性表順序存儲結(jié)構(gòu)定義及實(shí)現(xiàn)2、刪除元素在順序表中刪除元素也存在移動元素的過程，不過移動方向與插入元素相反。假如在順序表中刪除第i個元素ai，1≤i≤length，那么就將元素ai+1,…,an

依次往前移動，使得元素ai-1與元素ai+1相鄰，ai元素就刪除了，如下圖所示：線性表順序存儲結(jié)構(gòu)定義及實(shí)現(xiàn)順序表刪除元素算法的基本思想為：首先判斷刪除元素的下標(biāo)是否存在，然后用一個for循環(huán)來移動元素，移動元素下標(biāo)范圍為i～length-1，最后修改表長為原表長減1。算法如下所示：03PART線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)定義及實(shí)現(xiàn)鏈?zhǔn)酱鎯Y(jié)構(gòu)是指將線性表中的數(shù)據(jù)元素存放到計算機(jī)存儲器內(nèi)一組非連續(xù)存儲單元中。在鏈?zhǔn)浇Y(jié)構(gòu)中，只能通過指針來維護(hù)數(shù)據(jù)元素間的關(guān)系。由于這個原因，對線性表中的元素只能進(jìn)行順序訪問。單鏈表是鏈?zhǔn)酱鎯Y(jié)構(gòu)中最基礎(chǔ)、也是最具代表的一種存儲結(jié)構(gòu)形式。單鏈表是指線性表的每個結(jié)點(diǎn)分散地存儲在內(nèi)存空間中，先后依次用一個指針串聯(lián)起來。單鏈表可以分為不帶表頭結(jié)點(diǎn)和帶表頭結(jié)點(diǎn)兩種情形。線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)定義及實(shí)現(xiàn)不帶表頭結(jié)點(diǎn)的單鏈表如下圖所示：結(jié)點(diǎn)包含兩個屬性：data稱為數(shù)據(jù)域，它用于保存元素值；next稱為指針域/鏈域，它用于保存直接后繼元素結(jié)點(diǎn)的指針、維護(hù)元素間的線性關(guān)系。head為頭指針，它用于存放首元素結(jié)點(diǎn)的指針。當(dāng)head==NULL時，表示為空表，否則表示為非空表。線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)定義及實(shí)現(xiàn)帶表頭結(jié)點(diǎn)的單鏈表：①非空表。單鏈表中至少存儲一個元素為非空表；其中，頭指針head指向表頭結(jié)點(diǎn)，表頭結(jié)點(diǎn)的數(shù)據(jù)域不放元素，指針域指向首元素結(jié)點(diǎn)

a1。②空表。單鏈表中還沒有存儲數(shù)據(jù)元素為空表；當(dāng)head->next==NULL時，表示為空表，否則表示為非空表。線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)定義及實(shí)現(xiàn)首先定義單鏈表的結(jié)構(gòu)類型，每個結(jié)點(diǎn)有兩個部分：一個部分是數(shù)據(jù)域data；另一個部分是指針域next。具體定義如下。指向結(jié)點(diǎn)的指針變量head、p、q可定義為：線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)定義及實(shí)現(xiàn)1、先進(jìn)先出單鏈表單鏈表建立后，如果想要輸出單鏈表中元素的值，則先加入單鏈表的元素會先輸出、后加入的后輸出。所以這個單鏈表也可以稱為“先進(jìn)先出”單鏈表。該單鏈表中一個結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)按如下方式定義：線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)定義及實(shí)現(xiàn)可以通過尾插法創(chuàng)建單鏈表，算法步驟如下。（1）生成表頭結(jié)點(diǎn)，head和tail都指向表頭結(jié)點(diǎn)。（2）輸入元素的值

e，當(dāng)元素不是結(jié)束標(biāo)記時，重復(fù)下列操作，否則轉(zhuǎn)至步驟（3）。①生成新結(jié)點(diǎn)p，e保存到p結(jié)點(diǎn)的數(shù)據(jù)域。②使用tail->next=p;將p結(jié)點(diǎn)鏈接到單鏈表的表尾。③使用tail=p;讓tail指向當(dāng)前的表尾結(jié)點(diǎn)。（3）使用tail->next=NULL;將最后一個結(jié)點(diǎn)的指針域賦值為空。（4）返回head，完成“先進(jìn)先出”單鏈表的創(chuàng)建。線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)定義及實(shí)現(xiàn)2、先進(jìn)后出單鏈表單鏈表建立后，如果想要輸出單鏈表中元素的值，則先加入單鏈表的元素會后輸出、后加入的先輸出。這個單鏈表稱為“先進(jìn)后出”單鏈表。為實(shí)現(xiàn)創(chuàng)建“先進(jìn)后出”單鏈表，每當(dāng)輸入一個元素后，生成的結(jié)點(diǎn)不是放在表尾而是插入表頭，成為新的首元素結(jié)點(diǎn)，使用這種插入方式創(chuàng)建單鏈表的方法俗稱首插法，首插法具體如下圖所示。當(dāng)前單鏈表中已有i個元素結(jié)點(diǎn)，元素輸入次序?yàn)閍1,…,ai，現(xiàn)輸入第i+1個元素ai+1，具體操作為：第①步生成新結(jié)點(diǎn)p，并保存新元素ai+1；第②步通過p->next=head->next使得新結(jié)點(diǎn)指針指向原首結(jié)點(diǎn)；第③步通過head->next=p讓表頭結(jié)點(diǎn)的指針域指向新結(jié)點(diǎn)ai+1，不再指向ai，將新結(jié)點(diǎn)作為首元素，即可完成將新結(jié)點(diǎn)插入表頭的操作。線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)定義及實(shí)現(xiàn)3、插入元素一般情況下插入元素的操作如下：（1）在已知p指針指向的結(jié)點(diǎn)后插入一個元素x首先用一個指針f指向新結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閤，然后此新結(jié)點(diǎn)next域賦值為p指針指向結(jié)點(diǎn)的next域，最后p指針指向結(jié)點(diǎn)的next域賦值為f。線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)定義及實(shí)現(xiàn)（2）在已知p指針指向的結(jié)點(diǎn)前插入一個元素x因?yàn)閱捂湵砻總€結(jié)點(diǎn)只有一個指針指向其后繼結(jié)點(diǎn)，如果在結(jié)點(diǎn)前插入一個新結(jié)點(diǎn)，就需要得到p指向結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)指針，假設(shè)該指針為q，如下圖所示。這樣問題就轉(zhuǎn)換成在指針q指向的結(jié)點(diǎn)之后插入一個結(jié)點(diǎn)，即將該問題（2）轉(zhuǎn)換成問題（1）求解。線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)定義及實(shí)現(xiàn)循環(huán)單鏈表：有的時候，為了應(yīng)用方便，我們可以將鏈表中最后一個結(jié)點(diǎn)的next域指向鏈表的第一個結(jié)點(diǎn)而形成一個環(huán)，這種單鏈表稱為循環(huán)單鏈表。帶表頭結(jié)點(diǎn)的循環(huán)單鏈表示意圖如下圖所示。其中（a）為非空循環(huán)單鏈表，（b）為空循環(huán)單鏈表。線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)定義及實(shí)現(xiàn)在有些情況下，需要對單鏈表尾結(jié)點(diǎn)進(jìn)行訪問。為了提高算法的效率，此時還可采用只帶尾指針tail，不帶頭指針的循環(huán)鏈單鏈表。在這種只帶尾指針的循環(huán)單鏈表方式中，tail->next的值就是表頭結(jié)點(diǎn)的指針，其相當(dāng)于頭指針，所以能方便地完成頭指針循環(huán)單鏈表的各種操作。其中，（a）為只帶尾指針的非空循環(huán)單鏈表，（b）為空循環(huán)單鏈表。線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)定義及實(shí)現(xiàn)雙向鏈表：單鏈表和循環(huán)單鏈表每個結(jié)點(diǎn)中只有一個指針指向其后繼。對于循環(huán)單鏈表，一個結(jié)點(diǎn)需要訪問其前驅(qū)結(jié)點(diǎn)時要順著next域掃描整個鏈表一遍，此時效率顯然不高。這里為了方便訪問結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)而引入雙向鏈表。在雙向鏈表中，其中，每個結(jié)點(diǎn)除了數(shù)據(jù)域之外，還有兩個指針域（一個指向其直接前驅(qū)結(jié)點(diǎn)，另一個指向其直接后繼結(jié)點(diǎn)）。數(shù)據(jù)結(jié)構(gòu)的定義如下。線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)定義及實(shí)現(xiàn)雙向鏈表的一般形式如圖（a）和圖（b）所示，它們分別列出了非空雙向鏈表和空雙向鏈表。其中，L為頭指針，L指向表頭結(jié)點(diǎn)；通過首結(jié)點(diǎn)的next指針域可以依次訪問各個結(jié)點(diǎn)；通過尾結(jié)點(diǎn)的prior指針域可以逆序訪問鏈表中的各個結(jié)點(diǎn)。我們可以根據(jù)L->next==NULL是否成立來判斷是否為空表。線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)定義及實(shí)現(xiàn)在實(shí)際應(yīng)用中，一般會在雙向鏈表中加上循環(huán)，形成雙向循環(huán)鏈表。雙向循環(huán)鏈表的一般形式如下圖所示，我們可以根據(jù)L->next==L或L->prior==L是否成立來判斷是否為空表。線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)定義及實(shí)現(xiàn)從雙向鏈表中刪除結(jié)點(diǎn)時，需要注意兩個指針的變化。例如，已知雙向鏈表中包含結(jié)點(diǎn)A、B、C，指針p指向結(jié)點(diǎn)B，刪除B，那么所做的操作如下。向雙向鏈表中插入結(jié)點(diǎn)時，也需要注意兩個指針的變化。例如，已知雙向鏈表中包含兩個相鄰結(jié)點(diǎn)A和C，指針p指向結(jié)點(diǎn)C，現(xiàn)在插入一個新的結(jié)點(diǎn)到A和C之間，由f指向該待插入的結(jié)點(diǎn)B，那么所做的操作如下。04PART順序表與鏈表的比較

優(yōu)點(diǎn)缺點(diǎn)

順序表（1）順序表是一種隨機(jī)存取結(jié)構(gòu)，存取任何元素的時間是一個常數(shù)，速度快；（2）結(jié)構(gòu)簡單，邏輯上相鄰的元素在物理上也是相鄰的；（3）不需要使用指針，節(jié)省存儲空間；（4）順序表在實(shí)現(xiàn)上使用的是連續(xù)的內(nèi)存空間，我們可以借助CPU的緩存機(jī)制預(yù)讀順序表中的數(shù)據(jù)，所以訪問效率更高（1）插入和刪除元素要移動大量元素，需要消耗大量時間；（2）需要一塊連續(xù)的存儲空間；（3）插入元素可能發(fā)生“溢出”，不易擴(kuò)充；（4）自由區(qū)中的存儲空間不能被其他數(shù)據(jù)占用（共享），存在浪費(fèi)空間的問題

鏈表

（1）插入和刪除元素不需要移動大量元素，不需要消耗大量時間；（2）不需要一塊連續(xù)的存儲空間；（3）鏈表本身沒有大小的限制，天然地支持動態(tài)擴(kuò)容，插入元素一般不會發(fā)生“溢出”；（4）用多少就取多少，不存在自由區(qū)中的存儲空間不能被其他數(shù)據(jù)占用（共享）的情況，從而避免浪費(fèi)空間的問題（1）不是一種隨機(jī)存取結(jié)構(gòu)；（2）邏輯上相鄰的元素在物理上不一定是相鄰的；（3）需要使用指針，存儲密度小于1，浪費(fèi)一定的空間；（4）額外存儲指針結(jié)點(diǎn)，頻繁進(jìn)行增刪操作容易造成內(nèi)存碎片；（5）鏈表在內(nèi)存中并不是連續(xù)存儲，對CPU緩存不友好，無法有效預(yù)讀05PART應(yīng)用實(shí)例遞增有序單鏈表生成算法：例：輸入一列整數(shù)，以

0

為結(jié)束標(biāo)志，生成遞增有序單鏈表（不包括

0）。首先以不帶表頭結(jié)點(diǎn)的單鏈表作為存儲結(jié)構(gòu)來設(shè)計算法。假設(shè)有一個遞增有序的單鏈表，結(jié)點(diǎn)元素是1,4,10,17,…,78，現(xiàn)要插入一個新元素7，那么先從頭指針開始訪問單鏈表的結(jié)點(diǎn)，比較每個結(jié)點(diǎn)中的元素與7的大小，如果比7小，就往后進(jìn)行訪問；如果碰到一個結(jié)點(diǎn)的元素值比7大就停止訪問，說明新元素7應(yīng)該插入到此結(jié)點(diǎn)之前。前分析過，如果要把新結(jié)點(diǎn)插入某個結(jié)點(diǎn)之前，還需要用指針指向此結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，因此在從頭指針開始掃描單鏈表時，應(yīng)該用q、p兩個指針來指向可能要插入的位置。開始時，p指向首結(jié)點(diǎn)，q指向剛訪問過的結(jié)點(diǎn)，初始值為NULL。當(dāng)p指向的結(jié)點(diǎn)數(shù)據(jù)小于待插入數(shù)據(jù)時，說明待插入數(shù)據(jù)要插入p結(jié)點(diǎn)之后的某個位置上，目前無法確定，這樣需要首先將p賦予q，再移動p指向下一個結(jié)點(diǎn)，p和q同步移動。當(dāng)p指向的結(jié)點(diǎn)數(shù)據(jù)大于待插入數(shù)據(jù)時，說明待插入數(shù)據(jù)要插入p結(jié)點(diǎn)之前，也就是剛訪問過的結(jié)點(diǎn)q之后，完成定位。應(yīng)用實(shí)例一般情況下，當(dāng)q、p都不為空時，確定位置后，f指向的新結(jié)點(diǎn)就插入q與p之間，f指向新結(jié)點(diǎn)的next域賦值為p，q指向結(jié)點(diǎn)的next域賦值為f，具體操作為：f->next=p;q->next=f。但這種情況只是一般情形。在掃描單鏈表過程中，還可能碰到p、q可能為NULL的情況，此時需要進(jìn)行特殊處理。（1）p、q同時為空，意味著往空表中插入第一個結(jié)點(diǎn)。（2）僅p為空，q不為空，尾部插入，即數(shù)據(jù)插入單鏈表的尾部。（3）僅q為空，p不為空，首部插入，即插入的數(shù)據(jù)作為單鏈表的第一個結(jié)點(diǎn)。（4）p、q均不為空，在p與q之間插入一個新結(jié)點(diǎn)。應(yīng)用實(shí)例為了應(yīng)對p、q可能為NULL的情況，保證算法的正確性，給出了下面的不帶頭結(jié)點(diǎn)插入算法。圖中流程圖的左邊是通過p、q

兩個指針從頭指針開始掃描單鏈表，掃描過程中判斷比較結(jié)點(diǎn)數(shù)據(jù)域值與插入結(jié)點(diǎn)數(shù)據(jù)域值；如果找到，就停止掃描，進(jìn)行流程圖右邊的操作——將指針f

指向新插入的結(jié)點(diǎn)，接下來判斷p、q

兩個指針是否為空，分為①、②、③、④4

個分支（其中，①代表空表插入；②代表尾部插入；③代表首部插入；④代表一般插入），然后針對4

種不同的情況分別采取不同的操作。應(yīng)用實(shí)例應(yīng)用實(shí)例InsertList1算法是針對遞增有序單鏈表插入一個新的元素，那么對輸入的一組數(shù)生成一個遞增有序的單鏈表只需要在主函數(shù)中調(diào)用此算法即可。每輸入一個數(shù)，就調(diào)用此函數(shù)生成一個遞增有序單鏈表，直到輸入0為止。此主函數(shù)算法如下。應(yīng)用實(shí)例為了生成帶表頭結(jié)點(diǎn)的遞增有序單鏈表，給出下面的算法：首先從頭指針head開始掃描單鏈表，按q=head;p=head->next進(jìn)行初始化，然后根據(jù)待插入整數(shù)值的大小確定插入位置，用q、p兩個指針來指向可能要插入的位置。由于在此情況下該遞增有序單鏈表一定有一個不為空的頭結(jié)點(diǎn)head，因此在確定插入位置后，q永遠(yuǎn)不為空。應(yīng)用實(shí)例InsertList2算法是針對遞增有序單鏈表插入一個新的元素，那么對輸入的一組數(shù)生成一個遞增有序的單鏈表只需在主函數(shù)中不斷調(diào)用此算法。每輸入一個數(shù)，就調(diào)用此函數(shù)把該整數(shù)插入該遞增有序單鏈表中，直到輸入0為止。此主函數(shù)算法如下。應(yīng)用實(shí)例單鏈表插入、刪除算法：單鏈表插入算法是在單鏈表的指定位置插入新元素，其中輸入?yún)?shù)主要包

括頭指針L、位置i、數(shù)據(jù)元素e，而輸出為成功返回OK，否則ERROR。首先分析這個算法，在指定位置i上插入一個新的元素，使得插入的元素成為鏈表的第i個元素，那么需要運(yùn)用指針p從頭掃描單鏈表，并對所訪問的結(jié)點(diǎn)進(jìn)行計數(shù)。如果在第i個位置結(jié)束，指針p指向第i個位置，新元素就要插入指針p指向的結(jié)點(diǎn)之前；之前分析過，如果插入某個結(jié)點(diǎn)之前，就需要另一個輔助指針q來指向指針p的前驅(qū)結(jié)點(diǎn)。實(shí)際上，我們是可以簡化此過程的，即計數(shù)到i-1的時候就停止，指針p指向這個結(jié)點(diǎn)，然后新元素插入指針p所指向結(jié)點(diǎn)的后面就達(dá)到目的了。掃描的過程即是執(zhí)行p=L，當(dāng)指針p指向的結(jié)點(diǎn)不為空時，則需執(zhí)行p=p->next指令i-1次，從而定位到第i-1個結(jié)點(diǎn)。當(dāng)i<1或指針p指向的結(jié)點(diǎn)為空時，則插入點(diǎn)錯是錯誤的，否則新結(jié)點(diǎn)加到p指向結(jié)點(diǎn)之后。應(yīng)用實(shí)例應(yīng)用實(shí)例單鏈表刪除元素：在單鏈表中刪除某個結(jié)點(diǎn)，一定先找到將要被刪除的結(jié)點(diǎn)，還要找到其前驅(qū)結(jié)點(diǎn)。例如，單鏈表中有3個結(jié)點(diǎn)，分別是A、B、C，q指針指向數(shù)據(jù)域?yàn)锳的結(jié)點(diǎn)，p指針指向數(shù)據(jù)域?yàn)锽的結(jié)點(diǎn)。如果刪除數(shù)據(jù)域?yàn)锽的結(jié)點(diǎn)，首先執(zhí)行q->next=p->next;，即A的next域指向的地址（B的

next域），然后執(zhí)行free(p);釋放

p所指向的結(jié)點(diǎn)空間。第一個刪除算法是在帶表頭結(jié)點(diǎn)的單鏈表中刪除元素值為e的結(jié)點(diǎn)，第一步掃描此單鏈表以找到元素值為e的結(jié)點(diǎn)。應(yīng)用實(shí)例這段代碼執(zhí)行后，要么p指針為空，要么p所指向結(jié)點(diǎn)數(shù)據(jù)域的值為e；找到要刪除的結(jié)點(diǎn)后，就可以進(jìn)行刪除操作了。刪除操作的代碼如下：應(yīng)用實(shí)例第二個算法是在單鏈表中刪除指定位置的元素。在這個Delete算法中，刪除第i個元素時，該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)同樣重要，因此定位結(jié)點(diǎn)也是定位在i-1這個位置上，即執(zhí)行p=L;，L是頭指針，當(dāng)p->next不為空時執(zhí)行p=p->next;i-1次，從而定位到第i-1個結(jié)點(diǎn)。接著，判斷i值，當(dāng)i<1或p->next為空時刪除點(diǎn)位置出錯，否則p指向后繼結(jié)點(diǎn)的后繼，從而將第i個元素結(jié)點(diǎn)從單鏈表中刪除。應(yīng)用實(shí)例單鏈表合并算法：將兩個帶表頭結(jié)點(diǎn)的有序單鏈表La和Lb合并為有序單鏈表Lc，該算法利用原單鏈表的結(jié)點(diǎn)。單鏈表合并示意圖如圖所示。應(yīng)用實(shí)例根據(jù)上圖，單鏈表La有元素2、5，Lb有元素3、8、20，在合并中要用到3個指針pa、pb、pc。其中pa用來掃描單鏈表La，pb用來掃描單鏈表Lb，pc用來指向合并過程中得到的鏈表Lc的當(dāng)前表尾結(jié)點(diǎn)，合并操作就是通過這3個指針的變化來完成的。開始時，Lc中還沒有結(jié)點(diǎn)，所以尾結(jié)點(diǎn)就是表頭結(jié)點(diǎn)，pc首先指向La的表頭結(jié)點(diǎn)，pa、pb分別指向單鏈表La和Lb的首結(jié)點(diǎn)。然后比較pa和pb所指向兩個結(jié)點(diǎn)的數(shù)據(jù)域值大小，如果pa指向結(jié)點(diǎn)的數(shù)據(jù)域值小，就將pa指向的結(jié)點(diǎn)插入pc指向的結(jié)點(diǎn)后面，pc指向剛插入的結(jié)點(diǎn)，pa往后面移動，否則就將pb指向的結(jié)點(diǎn)插入pc指向的結(jié)點(diǎn)后面，pc指向剛插入的結(jié)點(diǎn)，pb往后面移動。接著不斷按照這種模式比較pa和pb所指向結(jié)點(diǎn)的數(shù)據(jù)域值大小，pa、pb、pc指針根據(jù)不同的情況發(fā)生變化，直到pa或pb為空為止。如果pa為空，表示鏈表La已經(jīng)掃描結(jié)束，則將pb指向的結(jié)點(diǎn)以及后面所有結(jié)點(diǎn)鏈接在pc指向的結(jié)點(diǎn)之后；反之，如果pb為空，表示鏈表Lb已經(jīng)掃描結(jié)束，則將pa指向的結(jié)點(diǎn)以及后面所有結(jié)點(diǎn)鏈接在pc指向的結(jié)點(diǎn)之后。應(yīng)用實(shí)例單鏈表的逆置：假定以單鏈表作為線性表L=(a1,a2,…,an)的存儲結(jié)構(gòu)，現(xiàn)要求設(shè)計算法，將線性表逆置為L=(an,an-1,…,a1)。這個問題就涉及將一個單鏈表中結(jié)點(diǎn)翻轉(zhuǎn)的操作，下面給出該問題求解的4種算法，并進(jìn)行效率分析。1．遞歸算法一：采用遞歸的思想完成逆置操作。當(dāng)為空單鏈表時，作為遞歸出口，直接返回；對非空單鏈表，首先將最后一個結(jié)點(diǎn)從單鏈表中移出，將剩下長度減一的單鏈表翻轉(zhuǎn)過來，再將剛移出的結(jié)點(diǎn)作為首結(jié)點(diǎn)插入這個單鏈表中。該算法每次為了移出最后一個結(jié)點(diǎn)，需要對單鏈表遍歷一次，共需要做n次移出結(jié)點(diǎn)操作，平均每次訪問結(jié)點(diǎn)的個數(shù)為n/2，所以算法的時間復(fù)雜度T(n)=O(n2)；遞歸深度為n，每一次遞歸調(diào)用時，都會在運(yùn)行時邏輯空間的?？臻g中分配單元，所以空間復(fù)雜度S(n)=O(n)。應(yīng)用實(shí)例2．遞歸算法二：同樣是采用遞歸算法，這里換一種移出結(jié)點(diǎn)的方法。當(dāng)單鏈表結(jié)點(diǎn)個數(shù)不大于1時，作為遞歸出口，直接返回；對有2個或2個以上結(jié)點(diǎn)的單鏈表，首先將第一個結(jié)點(diǎn)從單鏈表中移出，將剩下長度