數(shù)據(jù)結(jié)構(gòu)(本)課程輔導(dǎo)與練習(xí)線性表一、相關(guān)術(shù)語線性表、直接前驅(qū)、直接后繼、順序表、鏈表、指針、指針變量、結(jié)點、數(shù)據(jù)域、單向鏈表、單向循環(huán)鏈表、雙向循環(huán)鏈表、插入、刪除二、線性表的定義及特點線性表(linear_list)是屬于同一個數(shù)據(jù)對象的數(shù)據(jù)元素的有限序列。通常表示為：(%%，％.?.，%)其中n為線性表的長度，當n=0時，表示一個空表。線性表是一種最常用的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)元素之間的關(guān)系表現(xiàn)為：除第一個元素無直接前驅(qū)，最后一個元素無直接后繼外，其余元素均有且僅有一個直接前驅(qū)和一個直接后繼。線性表的存儲結(jié)構(gòu)有兩種實現(xiàn)方法式：順序存儲和鏈式存儲。三、順序表.順序表的定義(1)順序存儲方法即把線性表的結(jié)點按邏輯次序依次存放在一組地址連續(xù)的存儲單元里的方法。(2)順序表(SequentialList)用順序存儲方法存儲的線性表簡稱為順序表(SequentialList)。.結(jié)點ai的存儲地址不失一般性，設(shè)線性表中所有結(jié)點的類型相同，則每個結(jié)點所占用存儲空間大小亦相同。假設(shè)表中每個結(jié)點占用c個存儲單元，其中第一個單元的存儲地址則是該結(jié)點的存儲地址，并設(shè)表中開始結(jié)點a1的存儲地址(簡稱為基地址)是LOC(a1)，那么結(jié)點ai的存儲地址LOC(aj可通過下式計算：LOC(ai)=LOC(a1)+(i-1)*cIWiWn注意：在順序表中，每個結(jié)點ai的存儲地址是該結(jié)點在表中的位置i的線性函數(shù)。只要知道基地址和每個結(jié)點的大小，就可在相同時間內(nèi)求出任一結(jié)點的存儲地址。是一種隨機存取結(jié)構(gòu)。.順序表類型定義typedefstruct{datatypedata[MAXSIZE]；/*定義線性表為一維數(shù)組*/intlength；/*length為線性表當前的長度*/}SeqList；其中data是一維數(shù)組，MAXSIZE是數(shù)組data所能容納元素的最大值，也稱為順序表的容量；length是線性表當前的實際長度，線性表中第1,2，…，length個元素分別存放在數(shù)組第0,1,…，length-1的位置上；datatype是線性表元素的類型，應(yīng)視具體情況而定，可以是整形、字符型等，例如線性表是英文字母表，則datatype就是字符型。.順序表的特點順序表的特點是邏輯上相鄰的結(jié)點其物理位置也相鄰。.順序表上實現(xiàn)的基本運算(1)插入線性表的插入運算是指在表的第i（1WiWn+1）個位置上，插入一個新結(jié)點x,使長度為n的線性表：（a1，…，ai1，a.，…a）變成長度為n+1的線性表：（a1，…，a.1，x，a.，…a）在順序表中，結(jié)點的物理順序必須和結(jié)點的邏輯順序保持一致，因此必須將表中位置為n，n-1，…，i上的結(jié)點，依次后移到位置n+1，n，…，i+1上，空出第i個位置，然后在該位置上插入新結(jié)點x。僅當插入位置i=n+1時，才無須移動結(jié)點，直接將x插入表的末尾。具體算法描述教材P9【算法2-1】線性表的順序存儲具有三個弱點：（1）在做插入或刪除操作時，需要移動大量元素；（2）由于難以估計，必須預(yù)先分配較大的空間，往往使存儲空間不能得到充分的利用;（3）表的容量難以擴充。?算法分析①問題的規(guī)模表的長度L->length（設(shè)值為n）是問題的規(guī)模。②移動結(jié)點的次數(shù)由表長n和插入位置i決定算法的時間主要花費在for循環(huán)中的結(jié)點后移語句上。該語句的執(zhí)行次數(shù)是n-i+1。當i=n+1：移動結(jié)點次數(shù)為0,即算法在最好時間復(fù)雜度是0（1）

當i=1：當i=1：移動結(jié)點次數(shù)為n,即算法在最壞情況下時間復(fù)雜度是0(n)(5)刪除線性表的刪除運算是指將表的第i(IWiWn)個結(jié)點刪去，使長度為n的線性表(a/…，a」，a.,a.+i，…，a)變成長度為n-1的線性表(ai，…，ai-i，%,???,an)在順序表上實現(xiàn)刪除運算必須移動結(jié)點，才能反映出結(jié)點間的邏輯關(guān)系的變化。若i=n,則只要簡單地刪除終端結(jié)點，無須移動結(jié)點；若1WiWn-1,則必須將表中位置i+1,i+2,…，n的結(jié)點，依次前移到位置i,i+1,…，n-1上，以填補刪除操作造成的空缺。具體算法描述參見教材P11【算法2-2】?算法分析①結(jié)點的移動次數(shù)由表長n和位置i決定：i=n時，結(jié)點的移動次數(shù)為0,即為0(1)i=1時，結(jié)點的移動次數(shù)為n-1,算法時間復(fù)雜度分別是0(n)②移動結(jié)點的平均次數(shù),順序表上做刪除運算，平均要移動表中約一半的結(jié)點，平均時間復(fù)雜度也是0(n)。四、鏈表.鏈接存儲方法鏈接方式存儲的線性表簡稱為鏈表(LinkedList)。鏈表的具體存儲表示為:①用一組任意的存儲單元來存放線性表的結(jié)點（這組存儲單元既可以是連續(xù)的，也可以是不連續(xù)的）②鏈表中結(jié)點的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點間的邏輯關(guān)系，在存儲每個結(jié)點值的同時，還必須存儲指示其后繼結(jié)點的地址（或位置）信息（稱為指針（pointer）或鏈（link））注意：鏈式存儲是最常用的存儲方式之一，它不僅可用來表示線性表，而且可用來表示各種非線性的數(shù)據(jù)結(jié)構(gòu)。.鏈表的結(jié)點結(jié)構(gòu)datanextdata域：存放結(jié)點值的數(shù)據(jù)域next域：存放結(jié)點的直接后繼的地址（位置）的指針域（鏈域）注意：①鏈表通過每個結(jié)點的鏈域?qū)⒕€性表的n個結(jié)點按其邏輯順序鏈接在一起的。②每個結(jié)點只有一個鏈域的鏈表稱為單鏈表（SingleLinkedList）。.malloc函數(shù)和free函數(shù)①生成結(jié)點變量的標準函數(shù)mallocp=（ListNode*）malloc（sizeof（ListNode））；/*函數(shù)malloc分配一個類型為ListNode的結(jié)點變量的空間,并將其首地址放入指針變量p中*/②釋放結(jié)點變量空間的標準函數(shù)free（free(p)；/*釋放p所指的結(jié)點變量空間*/4、單鏈表的運算(1)尾插法建表算法思路：從一個空表開始,重復(fù)讀入數(shù)據(jù),生成新結(jié)點,將讀入數(shù)據(jù)存放在新結(jié)點的數(shù)據(jù)域中,然后將新結(jié)點插入到當前鏈表的表尾上,直到讀入結(jié)束標志為止。頭結(jié)點是在鏈表的開始結(jié)點之前附加一個結(jié)點。它具有兩個優(yōu)點：(1)由于開始結(jié)點的位置被存放在頭結(jié)點的指針域中,所以在鏈表的第一個位置上的操作就和在表的其它位置上操作一致,無須進行特殊處理；(2)無論鏈表是否為空，其頭指針都是指向頭結(jié)點的非空指針(空表中頭結(jié)點的指針域空)，因此空表和非空表的處理也就統(tǒng)一了。具體算法參見教材P15【算法2-3】。注意：(1)采用尾插法建表，生成的鏈表中結(jié)點的次序和輸入順序一致(2)須增加一個尾指針r,使其始終指向當前鏈表的尾結(jié)點(2)頭插法建表算法思路：從一個空表開始,重復(fù)讀入數(shù)據(jù),生成新結(jié)點,將讀入數(shù)據(jù)存放在新結(jié)點的數(shù)據(jù)域中,然后將新結(jié)點插入到當前鏈表的表頭上,直到讀入結(jié)束標志為止。具體算法參見教材P17【算法2-4】。注意：該方法生成的鏈表的結(jié)點次序與輸入順序相反。(3)按序號查找①鏈表不是隨機存取結(jié)構(gòu)在鏈表中，即使知道被訪問結(jié)點的序號i,也不能像順序表中那樣直接按序號i訪問結(jié)點，而只能從鏈表的頭指針出發(fā)，順鏈域next逐個結(jié)點往下搜索，直至搜索到第i個結(jié)點為止。因此，鏈表不是隨機存取結(jié)構(gòu)。②查找的思想方法計數(shù)器j置為0后，掃描指針p指針從鏈表的頭結(jié)點開始順著鏈掃描。當p掃描下一個結(jié)點時，計數(shù)器j相應(yīng)地加1。當j=i時，指針p所指的結(jié)點就是要找的第i個結(jié)點。而當p指針指為null且jWi時，則表示找不到第i個結(jié)點。注意：頭結(jié)點可看做是第0個結(jié)點。③具體算法實現(xiàn)ListNode*GetNode(LinkListhead,inti){/*在帶頭結(jié)點的單鏈表head中查找第i個結(jié)點，若找到(OWiWn),則返回該結(jié)點的存儲位置，否則返回NULL。*/intj;ListNode*p;p=head;j=0;/*從頭結(jié)點開始掃描*/while(p->next&&j<i){/*順指針向后掃描，直到p->next為NULL或i=j為止*/p=p->next;j++;if（i==j）returnp;/*找到了第i個結(jié)點*/elsereturnNULL;/*當i<0或i>0時，找不到第i個結(jié)點*/）（4）插入運算思想方法插入運算是將值為x的新結(jié)點插入到表的第i個結(jié)點的位置上，即插入到ai-1與ai之間。具體步驟：（1）找到a-置p（2）生成一個數(shù)據(jù)域為x的新結(jié)點*s（3）令結(jié)點*p的指針域指向新結(jié)點（4）新結(jié)點的指針域指向結(jié)點ai。（2）具體算法實現(xiàn)參見教材P18【算法2-5】（3）算法分析算法的時間主要耗費在查找操作上，故時間復(fù)雜度亦為O（n）。（5）刪除運算思想方法刪除運算是將表的第i個結(jié)點刪去。具體步驟：(1)找到ai-1的存儲位置p(因為在單鏈表中結(jié)點ai的存儲地址是在其直接前趨結(jié)點ai1的指針域next中)(2)令p->next指向ai的直接后繼結(jié)點(即把曾從鏈上摘下)(3)釋放結(jié)點ai的空間，將其歸還給〃存儲池〃。具體算法實現(xiàn)參見教材P20【算法2-6】注意：設(shè)單鏈表的長度為n,則刪去第i個結(jié)點僅當IWiWn時是合法的。當i=n+1時，雖然被刪結(jié)點不存在，但其前趨結(jié)點卻存在，它是終端結(jié)點。因此被刪結(jié)點的直接前趨*p存在并不意味著被刪結(jié)點就一定存在，僅當*p存在(即p!二NULL)且*p不是終端結(jié)點(即p->next!二NULL)時，才能確定被刪結(jié)點存在。線性表的鏈式存儲結(jié)構(gòu)一般來說克服了順序存儲結(jié)構(gòu)的三個弱點，首先，插入和刪除操作不需要移動元素，只修改指針；其次，不需要預(yù)先分配空間，可根據(jù)需要動態(tài)申請空間；其三是表容量只受可用內(nèi)存空間的限制。?算法分析算法的時間復(fù)雜度也是O(n)。鏈表上實現(xiàn)的插入和刪除運算，無須移動結(jié)點，僅需修改指針。五、順序表和鏈表的比較順序表和鏈表各有優(yōu)缺點。在實際應(yīng)用中究竟選用哪一種存儲結(jié)構(gòu)呢？這要根據(jù)具體問題的要求和性質(zhì)來決定。通常有以下幾方面的考慮：

順序表鏈表基于空間考慮基于時間考慮分配方式靜態(tài)分配。程序執(zhí)行之前必須明確規(guī)定存儲規(guī)模。若線性表長度n變化較大，則存儲規(guī)模難于預(yù)先確定估計。過大將造成空間浪費，估計太小又將使空間溢出機會增多。動態(tài)分配只要內(nèi)存空間尚有空閑，就不會產(chǎn)生溢出。因此，當線性表的長度變化較大，難以估計其存儲規(guī)模時，以采用動態(tài)鏈表作為存儲結(jié)構(gòu)為好。存儲密度為1。當線性表的長度變化不大，易于事先確定其大小時，為了節(jié)約存儲空間，宜采用順序表作為存儲結(jié)構(gòu)。<1存取方法隨機存取結(jié)構(gòu)，對表中任一結(jié)點都可在O（1）時間內(nèi)直接取得線性表的操作主要是進行查找，很少做插入和刪除操作時，采用順序表做存儲結(jié)構(gòu)為宜。順序存取結(jié)構(gòu)，鏈表中的結(jié)點，需從頭指針起順著鏈掃描才能取得。插入刪除操作在順序表中進行插入和刪除，平均要移動表中近一半的結(jié)點，尤其是當每個結(jié)點的信息量較大時，移動結(jié)點的時間開銷就相當可觀。在鏈表中的任何位置上進行插入和刪除，都只需要修改指針。對于頻繁進行插入和刪除的線性表，宜采用鏈表做存儲結(jié)構(gòu)。若表的插入和刪除主要發(fā)生在表的首尾兩端，則采用尾指針表示的單循環(huán)鏈表為宜六、練習(xí)題（一）單項選擇題.線性表在鏈式存儲中各結(jié)點之間的地址（）。A.必須連續(xù)B.部分地址必須連續(xù)C.不能連續(xù)D.連續(xù)與否無所謂.有關(guān)線性表的正確說法是（ ）。A.每個元素都有一個直接前驅(qū)和一個直接后繼B.線性表至少要求一個元素C.表中的元素必須按由小到大或由大到下排序D.除了一個和最后一個元素外，其余元素都有一個且僅有一個直接前驅(qū)和一個直接后繼3.一個線性表第一個元素的存儲地址是100,每個元素的長度為4,則第5個元素的地址是（）。A.110B.116C.100D.120.在一個長度為n的順序存儲線性表中，向第i個元素（1￡i￡n）之前插入一個新元素時，需要依次后移（）個元素。n-in-i+1n-i-1i.在一個長度為n的順序存儲線性表中，刪除第i個元素（1￡i￡n）,需要前移（）個元素。A.n-in-i+1C.n-i-1D.i.鏈表不具有的特點是（）。A.可隨機訪問任一元素B.插入刪除不需要移動元素C.不必要事先估計存儲空間D.所需空間與線性表長度成正比.用鏈表表示線性表的優(yōu)點是（ ）。A.便于隨機存取B.花費的存儲空間較順序存儲少C.便于插入和刪除D.數(shù)據(jù)元素的物理順序和邏輯順序相同.帶頭結(jié)點的鏈表為空的判斷條件是（ ）（設(shè)頭指針為head）。head==NULLhead->next==NULLhead->next==headhead!=NULL.非空的單向循環(huán)鏈表的尾結(jié)點滿足（ ）（設(shè)頭指針為head,指針p指向尾結(jié)點）。A.p->next==NULLB.p==NULLp->next==headD.p==head10.在一個單鏈表中，p、q分別指向表中兩個相鄰的結(jié)點，且q所指結(jié)點是p所指結(jié)點的直接后繼，現(xiàn)要刪除q所指結(jié)點，可用語句（ ）。p=q->nextp->next=qC.p->next=q->nextD.q->next=NULL(二)填空題1.已知L是無表頭結(jié)點的單鏈表，且P結(jié)點既不是首結(jié)點也不是尾結(jié)點，