【文章內(nèi)容簡(jiǎn)介】 /*新元素插入 */ Llast + +。 /*表長(zhǎng)加 1， last仍指向最后元素 */ return 1。 /*返回插入成功 */ } ?時(shí)間復(fù)雜度分析 ?最好情況下時(shí)間復(fù)雜度為 O(1) ?最壞情況下時(shí)間復(fù)雜度為 O(n) ?算法的平均時(shí)間復(fù)雜度 在長(zhǎng)度為ｎ的線性表中插入一個(gè)元素時(shí)所需移動(dòng)數(shù)據(jù)元素次數(shù)的期望值（平均移動(dòng)次數(shù)）為： 11E ( ) ( 1 )ni s iin p n i??? ? ??11 1E ( ) ( 1 ) ( 1 )12nni s iiinn p n i n in????? ? ? ? ? ? ????等概率情況下，平均移動(dòng)次數(shù)為： ? 刪除后使原表長(zhǎng)為ｎ的線性表 （ a1， a2， … ， ai1， ai， ai+1， … ， an） 變成長(zhǎng)度為ｎ－ 1 的線性表 （ a1， a2， … ， ai1， ai+1， … ， an） 圖 2. 4 順序表中刪除元素的過程 ?刪除算法的Ｃ函數(shù)如下： int deleteElem (SeqList *L,int i) { int j。 if(i1 || iLlast+1) /*檢查空表及刪除位置的合法性 */ { printf (第 %d個(gè)元素不存在 ,i)。 return 0。 } for(j=i。j=Llast。j++) Ldata[j1]=Ldata[j]。 /*向前移動(dòng)元素 */ Llast 。 /*表長(zhǎng)減 1*/ return 1。 /*刪除成功 */ } ?刪除時(shí)要檢查刪除位置的有效性，空表和大于表長(zhǎng)的位置是不能刪除的。 ?時(shí)間復(fù)雜度分析 ?最好情況下時(shí)間復(fù)雜度為 O(1) ?最壞情況下時(shí)間復(fù)雜度為 O(n) ?在等概率情況下，平均時(shí)間復(fù)雜度也為Ｏ (n) 1111E ( ) ( ) ( )2nnd e iiinn q n i n in???? ? ? ? ???? 3. 按值查找 按值查找算法的Ｃ函數(shù)如下： int LocateElem (SeqList *L, DataType x) { int i。 for(i=0。i=Llast 。i++) if( Ldata[i]== x) return i+1。 /*返回的是序號(hào) */ return 0。 } ?時(shí)間復(fù)雜度分析 ?最好情況下時(shí)間復(fù)雜度為 O(1) ?最壞情況下時(shí)間復(fù)雜度為 O(n) ?在等概率情況下，平均比較次數(shù)為（ n+1） /2，平均時(shí)間復(fù)雜度為 O(n)。 167。 2． 3 鏈表 ?線性表的順序存儲(chǔ)方法的優(yōu)缺點(diǎn) ?線性表的順序存儲(chǔ)方法有明顯的優(yōu)點(diǎn)： ?（ 1）這種方法最簡(jiǎn)單，最容易被大多數(shù)人理解和使用。 ?（ 2）可以隨機(jī)存取表中任一元素，存儲(chǔ)位置可以通過一個(gè)簡(jiǎn)單直觀的公式來表示，訪問元素速度快。 ?（ 3）不需要增加額外的空間來表示結(jié)點(diǎn)間的邏輯關(guān)系，存儲(chǔ)利用率高。 ?線性表的順序存儲(chǔ)方法的弱點(diǎn)： ?（ 1）除表尾的位置外，在做插入、刪除時(shí)需要移動(dòng)大量數(shù)據(jù)元素，效率較低。 ?（ 2）由于順序表要求分配一塊連續(xù)的存儲(chǔ)區(qū)域，不能利用小塊存儲(chǔ)區(qū)。 ?（ 3）一般采用靜態(tài)存儲(chǔ)分配方法。在程序執(zhí)行前，要預(yù)先分配存儲(chǔ)空間，當(dāng)表長(zhǎng)變化較大時(shí)，難以確定合適的存儲(chǔ)規(guī)模。若按可能達(dá)到的最大長(zhǎng)度進(jìn)行分配，則可能一部分空間不能得到充分利用；若事先對(duì)表長(zhǎng)估計(jì)不足，則插入操作又可能造成表空間的溢出。 ? 鏈表的定義及形式 ?鏈表 （ Linked List）是采用鏈接方式存儲(chǔ)的線性表。鏈接存儲(chǔ)需要通過附加指針來表示結(jié)點(diǎn)之間的關(guān)系。 ?線性表鏈接存儲(chǔ)的特點(diǎn) 是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。 ?數(shù)據(jù)元素 ai的存儲(chǔ)映象 ：對(duì)每個(gè)數(shù)據(jù)元素 ai來說，除了存儲(chǔ)其自身的信息之外，還需要和 ai一起存放表示元素間邏輯關(guān)系的信息（后繼或前趨的指針，即附加的指針域）。這兩部分信息組成數(shù)據(jù)元素 ai的存儲(chǔ)映象，稱為 結(jié)點(diǎn) （ node）。 ?根據(jù)鏈表附加指針域個(gè)數(shù)的不同，可以將鏈表分成不同的形式。 ?最常用的鏈表形式是每個(gè)結(jié)點(diǎn)附加一個(gè)指針域，指向后繼結(jié)點(diǎn)，稱為 單鏈表 ； ?如果每個(gè)結(jié)點(diǎn)附加兩個(gè)指針域，分別指向前趨結(jié)點(diǎn)和后繼結(jié)點(diǎn)，則稱之為雙鏈表 ； ?在單鏈表上進(jìn)行簡(jiǎn)單的改進(jìn)（利用終端結(jié)點(diǎn)的空指針域指向表頭）可以得到 單循環(huán)鏈表 ； ?在雙鏈表上進(jìn)行簡(jiǎn)單的改進(jìn)（也是利用空指針域）可以得到 雙循環(huán)鏈表 。 ?根據(jù)鏈表存儲(chǔ)空間分配方式的不同，可以將鏈表分為 動(dòng)態(tài)鏈表 和 靜態(tài)鏈表 。 ?單鏈表 ?單鏈表的定義 ?單鏈表中第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址保存在頭指針里，而其它數(shù)據(jù)元素的地址都保存在前趨結(jié)點(diǎn)的指針域中，所以整個(gè)鏈表的存取必須從頭指針開始 ?單鏈表可由頭指針唯一確定，通常用 “頭指針”來標(biāo)識(shí)一個(gè)單鏈表，如 單鏈表 L是指某鏈表的頭指針為Ｌ。 例：Ｌ =（ a， b， c， d， e， f， g） 采用單鏈表存儲(chǔ) n ex td ata單鏈表結(jié)點(diǎn)結(jié)構(gòu) ?單鏈表的存儲(chǔ)結(jié)構(gòu)用Ｃ語(yǔ)言描述如下： typedef struct Node /*結(jié)點(diǎn)類型定義 */ { DataType data。 /*數(shù)據(jù)域 */ struct Node *next。/*指針域 */ }LinkList。 LinkList *L， *p； /*定義指針變量 */ ?調(diào)用標(biāo)準(zhǔn)函數(shù) malloc()和 free(p)申請(qǐng)和釋放空間 ? 申請(qǐng)空間： p =（ LinkList *） malloc（ sizeof（ LinkList））； ?釋放空間： free(p) ?單鏈表結(jié)構(gòu)的一般形式 圖 2 . 8 單 鏈 表 的 一 般 圖 示 法b gdcafeL?假設(shè)指針變量 p指向單鏈表中第 i個(gè)結(jié)點(diǎn)，請(qǐng)區(qū)分以下幾種表示法： ?p：是一個(gè) LinkList *類型的指針，它保存的是數(shù)據(jù)域?yàn)?ai的 結(jié) 點(diǎn)的首地址； ?*p：是一個(gè) LinkList類型的結(jié)構(gòu)體變量，它的值包括兩個(gè)分量 pdata和 pnext； ?pdata：是一個(gè) DataType類型的變量，表示 p所指結(jié)點(diǎn)中的 數(shù)據(jù)域，它的值是元素 ai； ?pnext：是一個(gè) LinkList *類型的指針，表示 p所指結(jié)點(diǎn)的指針域，它的值是數(shù)據(jù)域?yàn)?ai+1的結(jié)點(diǎn)的首地址，即 q=pnext。 pnext是指向線性表中第 i+1個(gè)結(jié)點(diǎn)的指針，即 pnextdata的值是 ai+1 。同理 r=pnextnext，即 r=qnext。 ?p=pnext，它的作用是將 p所指結(jié)點(diǎn)中的指針域的值賦給指針 p，形象的可表示為指針 p沿著“鏈”向后移動(dòng)了一個(gè)結(jié)點(diǎn)。 Lanai + 1aia1ai + 2…qrp圖 2 . 9 指 針 變 量 p 及 其 指 向 結(jié) 點(diǎn) 的 關(guān) 系?單鏈表上基本運(yùn)算的實(shí)現(xiàn) （ 1）建立單鏈表 頭插法和尾插法 ?頭插法 ?基本思想： 頭插法即在鏈表的頭部插入結(jié)點(diǎn)建立單鏈表。建立單鏈表從空表開始，重復(fù)讀入數(shù)據(jù)，每讀入一個(gè)數(shù)據(jù)即向系統(tǒng)申請(qǐng)存儲(chǔ)空間建立一個(gè)新結(jié)點(diǎn)，并將讀入的數(shù)據(jù)存放在新結(jié)點(diǎn)的數(shù)據(jù)域中，然后插在鏈表的頭部，直到讀入結(jié)束標(biāo)志 1為止。 L = N U L L/ * 初 始 狀 態(tài) * /4 1L2354 1L231L231L21L1L23 s( a ) 將 數(shù) 據(jù) 元 素 3 插 入 到 單 鏈 表 中 的 過 程( b ) 頭 插 法 每 插 入 一 個(gè) 數(shù) 據(jù) 元 素 到 單 鏈 表 中 的 結(jié) 果圖 2 . 1 0 頭 插 法 建 立 單 鏈 表?頭插法建立單鏈表算法的Ｃ函數(shù)如下： LinkList *createHeadList( ) /*以頭插法建立不帶頭結(jié)點(diǎn)的單鏈表 */ { LinkList *L=NULL。 /*置空表 */ LinkList *s。 int x。 /*設(shè)數(shù)據(jù)元素的類型為 int*/ scanf(%d,amp。x)。 while (x!=1) /*以 1為輸入結(jié)束標(biāo)志 */ { s=( LinkList *)malloc(sizeof(LinkList))。 sdata=x。 snext=L。 L=s。 scanf (%d,amp。x)。 } return L。 /*返回表頭指針 */ } ?尾插法 ?基本思想： 尾插法是在單鏈表的尾部插入結(jié)點(diǎn)建立單鏈表。尾插法建立單鏈表時(shí)每次將新結(jié)點(diǎn)插入到鏈表的尾部，此時(shí)可設(shè)置一個(gè)尾指針 r，用來指向鏈表中的尾結(jié)點(diǎn)，能夠方便的實(shí)現(xiàn)將新結(jié)點(diǎn)插入到鏈表的尾部，而不用每次插入時(shí)都從頭到尾掃描一遍單鏈表來找到尾結(jié)點(diǎn)。 L= N U L L r = N U L L/ * 初 始 狀 態(tài) * /1rL21rL321rL53321rL4321rLr s / * 尾 部 插 入 數(shù) 據(jù) 元 素 2 的 具 體 過 程 * /圖 2 . 1 1 尾 插 法 建 立 單 鏈 表?尾插法建立單鏈表算法的Ｃ函數(shù)如下： LinkList *createTailList( ) /*以尾插法建立不帶頭結(jié)點(diǎn)的單鏈表 */ { LinkList *s, *r , *L。 int x。 /*設(shè)數(shù)據(jù)元素的類型為 int*/ L=NULL。 /*置空表 */ r=NULL。 scanf(%d,amp。x)。 while (x!=1) { s=( LinkList *) malloc(sizeof(LinkList))。 sdata=x。 if (!L) L=s。 /*第一個(gè)結(jié)點(diǎn)的處理 */ else rnext=s。 /*其他結(jié)點(diǎn)的處理 */ r=s。 /*r 指向新的尾結(jié)點(diǎn) */ scanf(%d,amp。x)。 } if ( r ) rnext=NULL。 /*對(duì)于非空表，尾結(jié)點(diǎn)的指針域置空 */ return L。 } ?頭結(jié)點(diǎn)的作用 ?頭結(jié)點(diǎn)的加入使得鏈表一經(jīng)建立就非空（至少有頭結(jié)點(diǎn)），從而解決了“空表”問題。 ?在第一個(gè)結(jié)點(diǎn)前插入一個(gè)結(jié)點(diǎn)，或者刪除第一個(gè)結(jié)點(diǎn)，都與頭指針無關(guān)，只需修改頭結(jié)點(diǎn)的指針域即可，與在表的其他位置上的操作完全一致，無須特殊處理。 …a1anLa2( b ) 非 空 表L( a ) 空 表圖 2 . 1 2 帶 頭 結(jié) 點(diǎn) 的 單 鏈 表?引入頭結(jié)點(diǎn)后的頭插法和尾插法 ?尾插法建立帶頭結(jié)點(diǎn)的單鏈表算法的Ｃ函數(shù)如下： LinkList *createTailList ( ) /*以尾插法建立帶頭結(jié)點(diǎn)的單鏈表 */ { LinkList *