數(shù)據(jù)結(jié)構(gòu) 課件 第2章 線性表

第2章線性表總體要求：熟悉線性表的定義熟悉線性表的抽象數(shù)據(jù)類型描述中各種操作的含義熟練掌握順序存儲線性表的建立、插入、刪除和定位算法熟練掌握鏈?zhǔn)酱鎯€性表的建立、插入、刪除和定位算法核心技能點：線性表各種存儲結(jié)構(gòu)應(yīng)用于實際問題的能力擴展技能點：線性表各種存儲結(jié)構(gòu)和算法C語言環(huán)境下的實現(xiàn)1第2章線性表相關(guān)知識點：C語言數(shù)組的知識C語言結(jié)構(gòu)體的知識C語言指針的知識C語言函數(shù)的知識C語言類型定義學(xué)習(xí)重點：熟悉線性表的定義熟悉線性表的抽象數(shù)據(jù)類型描述中各種操作的含義掌握線性表各種存儲結(jié)構(gòu)下算法的實現(xiàn)2第2章線性表2.1線性表實例及概念在計算機應(yīng)用中，線性表是一種常見的數(shù)據(jù)類型。諸如在文件、內(nèi)存、數(shù)據(jù)庫等管理系統(tǒng)中經(jīng)常需要對屬于線性表的數(shù)據(jù)類型進(jìn)行處理。例如，表2.1表示的是一個有關(guān)學(xué)生情況的信息文件，文件中每個記錄對應(yīng)于一個學(xué)生的情況，它由學(xué)號、姓名、性別、年齡及籍貫等信息組成。

表2.1學(xué)生情況信息文件3第2章線性表

在這個實例中我們可以看到，文件中的記錄一個接著一個，它們之間存在著一種前后關(guān)系。為了研究這種數(shù)據(jù)結(jié)構(gòu)中元素間的關(guān)系，我們可以忽略記錄中的具體內(nèi)容，而只將它看作結(jié)構(gòu)中的一個元素。從數(shù)據(jù)結(jié)構(gòu)的視點來看，可以將上例中的整個信息文件看作為一個線性表，而文件中的每一個記錄可看作為線性表中的一個數(shù)據(jù)元素。一般，一個線性表是由n個元素組成的有限序列，可記作：L=（a0,a1,…an-1）其中，每個ai都是線性表L的數(shù)據(jù)元素。數(shù)據(jù)元素可以是各種各樣的。例如，它可以是一個數(shù)，一個符號或一個記錄等，但同一線性表中的元素必須屬于同一種數(shù)據(jù)對象。4第2章線性表

線性表的結(jié)構(gòu)是通過數(shù)據(jù)元素之間的相鄰關(guān)系來體現(xiàn)的。在線性表L中，元素ai-1與ai相鄰并位于ai之前，稱為ai的直接前驅(qū)，而ai+1與ai相鄰并位于ai之后，稱為ai的直接后繼。元素a0稱為L的最先元素，除最先元素外，L中的其他元素都有且僅有一個直接前驅(qū)；元素an-1稱為L的最后元素，除最后元素外，L中的其他元素都有且僅有一個直接后繼。元素ai是第i個數(shù)據(jù)元素，稱i為數(shù)據(jù)元素ai在線性表中的位序。線性表中的元素個數(shù)n稱為線性表的長度，長度為0的線性表稱為空表。為了對線性表及其有關(guān)操作的實現(xiàn)方法有比較直觀的了解，我們先要考慮線性表的存儲方式，其次是有關(guān)的操作。在以下幾節(jié)中我們將圍繞上述這些問題展開討論。5第2章線性表

2.2線性表的存儲方式在編制程序之前，我們總是要考慮一下在該程序中涉及到哪些數(shù)據(jù)，這些數(shù)據(jù)應(yīng)該以何種方式存儲到計算機中等問題。如果是使用某種程序設(shè)計語言來編程，則要考慮在該程序中應(yīng)定義哪些變量，這些變量的類型是什么或應(yīng)如何定義等等。那么，對于線性表應(yīng)采取什么存儲方式呢?線性表一般有順序存儲結(jié)構(gòu)與鏈?zhǔn)酱鎯Y(jié)構(gòu)兩種存儲方式。按順序存儲結(jié)構(gòu)建立起來的線性表稱為順序表，按鏈?zhǔn)酱鎯Y(jié)構(gòu)建立起來的線性表稱為線性鏈表。6第2章線性表

2.2.1線性表的順序存儲結(jié)構(gòu)在計算機內(nèi)可以用不同的方式來表示線性表，其中最簡單和最常用的方式是用一片連續(xù)的存儲區(qū)域，也就是用一組地址連續(xù)的存儲單元來依次存儲線性表的各個元素。線性表(a0，a1，a2，…，ai，…，an-1)的順序存儲結(jié)構(gòu)如圖2.1所示,這種存儲方式的特點是用存儲單元物理位置的相鄰來表示相鄰元素間的邏輯關(guān)系。7圖2.1線性表的順序存儲結(jié)構(gòu)示意圖第2章線性表8

假設(shè)線性表的每個元素需占用s個存儲單元，并以第一個存儲單元的地址作為數(shù)據(jù)元素的存儲位置，則線性表中第i+1個數(shù)據(jù)元素的存儲位置LOC(ai+1)和第i個數(shù)據(jù)元素的存儲位置LOC(ai)之間滿足下列關(guān)系：

LOC(ai+1)=LOC(ai)+s

一般來說，線性表中第i個元素ai的存儲地址為LOC(ai)=LOC(a0)+i*s式中，LOC(a0)為線性表的第一個元素a0的存儲地址，通常稱為線性表的開始地址或基地址。在線性表的順序存儲結(jié)構(gòu)中，應(yīng)該包括存儲數(shù)據(jù)元素的一個一維數(shù)組，取名為list，其長度可取一個適當(dāng)?shù)淖畲笾礛axSize，另外還應(yīng)包括一個表示元素個數(shù)的整型變量，取其名為size，如圖2.2所示。第2章線性表9

使用C語言，我們可以定義以下的記錄(結(jié)構(gòu))類型來表示順序表，其類型名用SeqList表示。

MaxSize線性表可能達(dá)到的最大長度；typedefstruct{DataTypelist[MaxSize]; intsize;}SeqList;

在定義了順序表的類型SeqList之后，我們就可以定義屬于這種類型的線性表，例如：SeqListLa，Lb；此后，可在程序中引用線性表La，Lb的相應(yīng)成分，例如La.list[0]表示線性表的第一個元素，La.size表示線性表的當(dāng)前長度等等。圖2-2線性表的類型定義示意圖第2章線性表102.2.2線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)以上我們研究了線性表的順序存儲結(jié)構(gòu)，它的特點是邏輯關(guān)系上相鄰的兩個元素在物理位置上也相鄰，因此順序表中任一元素的存儲位置都可以用一個簡單直觀的公式來表示。然而，從另一方面看，這種存儲結(jié)構(gòu)也有許多不足之處：首先，我們難以確定適當(dāng)?shù)拇鎯臻g的大小，如果指定得太小，則難以擴充；如果指定得太大，則存儲空間不能得到充分的利用。其次，在做插入或刪除時需移動大量元素。本節(jié)我們還將討論另一種存儲結(jié)構(gòu)——鏈?zhǔn)酱鎯Y(jié)構(gòu)。由于它不要求邏輯關(guān)系上相鄰的元素在物理位置上也相鄰，因此它沒有順序存儲結(jié)構(gòu)存在的缺點。第2章線性表11

線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)也有很多種類。按鏈的類別來分類，可以分為單鏈表、循環(huán)鏈表、雙向鏈表、雙向循環(huán)鏈表等；按結(jié)點的分配方式來分類，可以分為動態(tài)鏈表和靜態(tài)鏈表。下面分別進(jìn)行介紹。1．單鏈表單鏈表存儲結(jié)構(gòu)是用一組任意的存儲單元來存儲線性表的數(shù)據(jù)元素。為了表示數(shù)據(jù)元素間的邏輯關(guān)系，對數(shù)據(jù)元素ai來說，除了存儲其本身的信息外，還需存儲一個直接后繼的信息。圖2.3表示線性表（A,B,C,D）采用單鏈表存儲結(jié)構(gòu)時在內(nèi)存中的存儲狀態(tài)。圖2-3單鏈表存儲狀態(tài)示例第2章線性表12

在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，數(shù)據(jù)元素ai的存儲映像，稱為結(jié)點。單鏈表的結(jié)點包括兩個域：存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域；存儲直接后繼存儲位置的域稱為指針域。n個結(jié)點ai(0≤i≤n-1)的存儲映像鏈結(jié)成一個鏈表，即為線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點是：數(shù)據(jù)元素之間的邏輯關(guān)系是由結(jié)點中的指針指示的。由于此鏈表的每個結(jié)點中只包含一個指針域故稱為單鏈表。對單鏈表的存取必須從頭指針開始進(jìn)行，頭指針指向鏈表中的第一個結(jié)點。同時由于最后一個數(shù)據(jù)元素沒有直接后繼，因此線性表中最后一個結(jié)點的指針域為“空”(NULL)。第2章線性表13

由于一個線性鏈表的鏈頭指針可以確定整個的線性鏈表，因此我們往往用這個鏈頭指針來表示它所指向的線性鏈表。有時，為了適應(yīng)算法的需要，需在單鏈表的第一個結(jié)點之前附設(shè)一個結(jié)點，稱為頭結(jié)點。頭結(jié)點的數(shù)據(jù)域可以不存儲任何信息，頭結(jié)點的指針域存儲指向第一個結(jié)點的指針，此時，單鏈表的頭指針指向頭結(jié)點。帶頭結(jié)點的單鏈表邏輯結(jié)構(gòu)表示如圖2.4所示。（提示：為了方便表示，本書以后的鏈表都用邏輯結(jié)構(gòu)表示）圖2-4帶頭結(jié)點的單鏈表第2章線性表14

為了表示線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，首先要定義存放數(shù)據(jù)元素的結(jié)點類型，其次是指向這種結(jié)點的指針類型，然后我們就可以定義一個屬于這種類型的指針型變量并使其指向頭結(jié)點來表示一個線性表。假設(shè)結(jié)點類型名為SLNode，結(jié)點指針類型名為SLlink，結(jié)點類型中數(shù)據(jù)域名為data，指針域名為next，數(shù)據(jù)元素的類型為DataType，我們就可以用以下的類型及變量定義來表示線性表。

typedefstructNode{DataTypedata;structNode*next;}SLNode,*SLlink;

在定義了單鏈表的結(jié)點類型SLNode及結(jié)點指針類型SLlink之后，就可定義一個SLlink型的變量來表示屬于這種類型的線性表，例如：SLlinkhead；在相關(guān)的程序中，先使head指向某一個單鏈表的頭結(jié)點或第一個結(jié)點，然后就可對這個用head所表示的單鏈表進(jìn)行各種操作。第2章線性表15

2．靜態(tài)鏈表上述這種存儲結(jié)構(gòu)的特點是動態(tài)地生成結(jié)點，通過存放在結(jié)點中的指針域?qū)⒔Y(jié)點中的數(shù)據(jù)元素鏈接起來。但在有的高級語言中沒有指針類型，也不能動態(tài)地生成結(jié)點。在這種場合下，我們可以借用一個一維數(shù)組來存儲線性鏈表。這種數(shù)組的類型及變量定義如下：

MaxSize為鏈表可能的最大長度；

Typedefstruct{DataTypedata;intnext;}node;nodeslspace[MaxSize]；在上述定義中，變量slspace是一個結(jié)構(gòu)型的數(shù)組，用于存放鏈表中的結(jié)點。該數(shù)組中每一個元素表示線性鏈表中的一個結(jié)點。這種結(jié)點由data與next兩個域組成，data部分存放數(shù)據(jù)元素，而next部分存放指示下一個結(jié)點在數(shù)組中位置的整型指示器。使用這種存儲方式所存儲的線性鏈表稱為靜態(tài)鏈表。第2章線性表163．雙向循環(huán)鏈表對于單鏈表來說，在其每個結(jié)點中設(shè)置一個指針，指針指向該結(jié)點的后繼結(jié)點，因此鏈表中最后一個結(jié)點的指針域必定為空。單鏈表存儲結(jié)構(gòu)的這種特點決定了對它的訪問方式。我們只能從單鏈表的鏈頭開始對單鏈表中的數(shù)據(jù)元素進(jìn)行訪問而不能從其中的任一結(jié)點開始，其次我們只能由前向后地對單鏈表進(jìn)行訪問，而不能由后向前地進(jìn)行訪問。這對某些應(yīng)用來說是不方便的，為此我們要對單鏈表的存儲結(jié)構(gòu)進(jìn)行一些改造。首先我們使鏈表中最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表就形成一個環(huán)，這樣形成的鏈表稱為循環(huán)鏈表。對于循環(huán)鏈表，可以從鏈表中的任一點出發(fā)找到鏈表中所有的其他結(jié)點。循環(huán)鏈表的結(jié)構(gòu)形式如圖2.5所示。第2章線性表17圖2-5循環(huán)鏈表結(jié)構(gòu)示意圖(a)非空表(b)空表第2章線性表18

在對循環(huán)鏈表進(jìn)行處理時所要注意的是：算法中判別當(dāng)前指針p是否達(dá)到鏈尾的條件不是判別p是否等于NULL，而是要判別p是否等于頭指針。其他方面與單鏈表基本一致。其次，我們在鏈表的結(jié)點中增加了一個指向前驅(qū)結(jié)點的指針域，這樣形成的鏈表稱為雙向鏈表。對于雙向鏈表，既可以對數(shù)據(jù)元素由前向后地進(jìn)行訪問，又可以由后向前地進(jìn)行訪問。雙向鏈表的結(jié)點及結(jié)點指針類型可定義如下：

typedefstructNode{DataTypedata;structNode*prior;structNode*next;}DLNode,*DLlink;第2章線性表19

如果線性鏈表的存儲結(jié)構(gòu)中同時采用上述兩種鏈接方式，則就形成雙向循環(huán)鏈表。在圖2.6中所表示的是線性表d1=(A，B，C)的雙向循環(huán)鏈表的存儲結(jié)構(gòu)圖。圖2-6雙向循環(huán)鏈表的示意圖第2章線性表202.3線性表的有關(guān)操作在確定了線性表的存儲結(jié)構(gòu)后，應(yīng)考慮對線性表所施行的操作。從邏輯上講可以對線性表施行數(shù)據(jù)元素的插入、刪除等各種操作，但這些操作實現(xiàn)過程及執(zhí)行效率又完全取決于數(shù)據(jù)的存儲結(jié)構(gòu)。下面我們按順序表、單鏈表以及雙向循環(huán)鏈表幾種存儲方式來介紹有關(guān)算法的實現(xiàn)過程。2.3.1順序表的操作實現(xiàn)順序表是以順序存儲方式存儲的線性表。如前所述，順序存儲方式的特點是用一片連續(xù)的存儲區(qū)域依次存儲線性表的各個元素。在這種存儲方式下，線性表的某些操作容易實現(xiàn)。下面著重討論在順序存儲結(jié)構(gòu)方式下，線性表的查找(求位序)、插入及刪除等操作的實現(xiàn)。第2章線性表211.查找(求位序)函數(shù)線性表的查找函數(shù)是指在指定的線性表L中查找指定的元素x。若L中存在其值與x相等的數(shù)據(jù)元素，則函數(shù)值為該數(shù)據(jù)元素在線性表中的位序，否則為-1。從上述所說明的查找函數(shù)的含義中我們可以看到，對查找的函數(shù)應(yīng)該設(shè)置兩個參數(shù)，即在參數(shù)中指定被查找的線性表及所查找的元素。假設(shè)被查找的線性表SeqlistL在本函數(shù)之外已說明，而所查找的元素為DataTypex，查找函數(shù)取名為ListLocate，則該函數(shù)可表示為:intListLocate(SeqlistL,DataTypex)；第2章線性表22

功能是:在線性表L中查找數(shù)據(jù)元素x。若L中存在與x相等的數(shù)據(jù)元素，則返回該數(shù)據(jù)元素在線性表中的序號，否則返回-1。處理過程:從第一個元素起，依次將L中的元素與x進(jìn)行比較，直至某一個元素與x比較相等，則返回該元素的序號，或與n個元素全比較都不相等，則返回-1。程序如下：

intListLocate(SeqlistL,DataTypex){inti=0;while(i<L.size&&L.list[i]!=x)i++;if(i<L.size)return(i);elsereturn(-1);}

在上述程序中，while循環(huán)的條件是必須同時滿足(i<=L.size&&L.data[i]!=x)。其中，第一個條件表示還沒有比較完，第二個條件表示還沒有查到。只有在這兩個條件同時滿足時才能繼續(xù)往下查找。第2章線性表23

2．插入操作如圖2.7所示，線性表的插入操作是指在線性表的第i-1個數(shù)據(jù)元素與第i個數(shù)據(jù)元素之間插入一個新的元素。由于我們所采用的是順序的存儲結(jié)構(gòu)，插入后元素間的邏輯關(guān)系會發(fā)生變化，為了仍然保持邏輯上相鄰的數(shù)據(jù)元素在存儲位置上也相鄰，則必須將第i號到第n-1號元素向后移動一個位置，除非插入位置是i=n。插入后線性表的長度應(yīng)該由原來的n變?yōu)閚+1。圖2.7順序表插入操作示意圖

(a)插入前(b)插入后第2章線性表24

從上述所說明的插入操作的含義中我們可以看到，對該操作應(yīng)該設(shè)置三個參數(shù)，即在參數(shù)中指定所插入的線性表、插入位置及插入的元素。假設(shè)所插入的線性表SeqList*L在本操作之外已說明，而插入位置及插入的元素分別為inti及DataTypex，插入操作取名為ListInsert，則該操作可表示為：

intListInsert(SeqList*L,inti,DataTypex)；功能為：在線性表*L中的第i號元素之前插入數(shù)據(jù)元素x，其中，0≤i≤L->size操作的處理過程為：⑴檢查插入位置i是否合法；⑵將第i號到第L->size-1號元素向后移動一個位置；⑶在位置i處存入元素x。第2章線性表25程序如下：intListInsert(SeqList*L,inti,DataTypex){intj;if(L->size>=MaxSize-1){printf("順序表已滿無法插入!\n"); return0;}elseif(i<0||i>L->size+1){printf("參數(shù)i不合法!\n");return0;}Else{for(j=L->size;j>i;j--)L->list[j]=L->list[j-1];/*為插入做準(zhǔn)備*/L->list[i]=x;/*插入*/L->size++;/*元素個數(shù)加1*/return1;}}在上述程序中我們要注意的是元素后移時應(yīng)該從最后一個元素開始移動，所以for語句采用了j--形式。第2章線性表26

3．刪除操作如圖2.8所示，線性表的刪除操作是指在線性表中刪除其中的第i個數(shù)據(jù)元素。由于我們所采用的是順序的存儲結(jié)構(gòu)，刪除后元素間的邏輯關(guān)系會發(fā)生變化，為了仍然保持邏輯上相鄰的數(shù)據(jù)元素在存儲位置上也相鄰，則必須將第i+1號到第n-1號元素向前移動一個位置，除非刪除的是最后一個元素。刪除后線性表的長度應(yīng)該由原來的n變?yōu)閚-1。圖2-8順序表刪除操作示意圖(a)刪除前；(b)刪除后第2章線性表27

從上述所說明的刪除操作的含義中我們可以看到，對該操作應(yīng)該設(shè)置三個參數(shù)，即在參數(shù)中要指定一個線性表及刪除元素的序號。假設(shè)作為操作對象的線性表SeqList*L在本操作之外已說明，而刪除元素的序號用i表示，刪除元素DataType*x，刪除操作取名為ListDelete，則該操作可表示為：

intListDelete(SeqList*L,inti,DataType*x)；功能為：在順序表*L中刪除第i號元素，其中，

0≤i≤L->size-1

處理過程為：⑴檢查刪除位置i是否合法；⑵將第i+1號到第L->size-1號元素向前移動一個位置；⑶數(shù)據(jù)元素個數(shù)減1。第2章線性表28程序如下：intListDelete(SeqList*L,inti,DataType*x) {intj;if(L->size==0){printf("順序表已空無數(shù)據(jù)元素可刪!\n");return0;}elseif(i<0||i>L->size-1){printf("參數(shù)i不合法");return0;}else{*x=L->list[i];/*保存刪除的元素到參數(shù)x中*/for(j=i+1;j<L->size;j++)L->list[j-1]=L->list[j];/*依次前移*/L->size--;/*數(shù)據(jù)元素個數(shù)減1*/return1;}}第2章線性表29

從上述插入及刪除算法可見，當(dāng)在順序結(jié)構(gòu)的線性表中某個位置上插入或刪除一個數(shù)據(jù)元素時，其時間主要消耗在移動元素上(換句話說，移動元素的操作為預(yù)估算法時間復(fù)雜度的基本操作)，而移動元素的個數(shù)取決于插入或刪除元素的位置。以插入算法為例，當(dāng)插入位置i為n時，移動次數(shù)為0次；當(dāng)插入位置i為0時，移動次數(shù)為n次，平均次數(shù)為n/2，可表示成線性階O(n)。第2章線性表30

4.逆置操作線性表的逆置操作是指對指定的線性表進(jìn)行逆置，即反向排列該線性表中的所有數(shù)據(jù)元素，逆置后線性表的長度仍保持不變。對該操作應(yīng)通過設(shè)置一個參數(shù)來指定一個線性表。假設(shè)參數(shù)為SeqList*L逆置操作取名為Listinver，則該操作可表示為：

ListInver(SeqList*L)；功能為：對順序表L中的所有元素進(jìn)行逆置。處理過程為：是將整個元素的序列分為前后兩部分，然后將這兩部分中所有對應(yīng)的元素進(jìn)行交換。第2章線性表31程序如下：Listinver(SeqList*L){inti,m,n;DataTypetemp;n=L->size;m=n/2;for(i=0;i<m;i++){temp=L->list[i];L->list[i]=L->list[n-i-1];L->list[n-i-1]=temp;}}從上述逆置過程可以看到，交換的次數(shù)是L->size/2，與元素的個數(shù)有關(guān)。第2章線性表322.3.2單鏈表的操作實現(xiàn)線性鏈表即以鏈?zhǔn)酱鎯Ψ绞酱鎯Φ木€性表。如前所述，鏈?zhǔn)酱鎯Ψ绞降奶攸c是用一組任意的存儲單元來存儲線性表的各個元素，數(shù)據(jù)元素之間的邏輯關(guān)系是由指針來表示的。在這種存儲方式下，線性表的操作可通過對指針的訪問或改變指針來實現(xiàn)。在下面的討論中，線性鏈表主要是指單鏈表，主要討論在帶表頭單鏈表存儲結(jié)構(gòu)方式下，線性表的取元素操作及插入、刪除等操作的實現(xiàn)。第2章線性表33

1.取元素操作取元素操作是指在指定的線性表L中取其第i個數(shù)據(jù)元素。若0≤i≤ListLength(L)-1，則函數(shù)值為1，否則為0。對該操作我們一般應(yīng)設(shè)置三個參數(shù)，即在參數(shù)中指定線性表、所取元素的序號及帶回值的變量。在線性鏈表的存儲結(jié)構(gòu)下，線性表可以用指向鏈頭的指針型變量來表示。假設(shè)指定的線性表SLlinkhead在本操作之外已說明，而元素序號為inti，取元素操作取名為SLinkGet，則該操作可表示為：

intSLinkGet(SLlinkhead,inti,DataType*x)；功能為：取帶頭結(jié)點的單鏈表head中的第i個數(shù)據(jù)元素。若0≤i≤ListLength(L)-1，則返回1，表中的第i個數(shù)據(jù)元素由x帶回，否則返回0。操作的處理過程為：⑴初始化，使指針p指向第一個元素的結(jié)點；⑵是指針逐個后移直至指針指向第i個元素結(jié)點或指針為空；⑶若第i個元素結(jié)點存在則由x帶回該元素返回1，否則返回0。第2章線性表34程序如下：intSLinkGet(SLlinkhead,inti,DataType*x)/*取數(shù)據(jù)元素ai和刪除函數(shù)類似，只是不刪除數(shù)據(jù)元素ai結(jié)點*/{SLNode*p;intj;p=head;j=-1;while(p->next!=NULL&&j<i){p=p->next; j++; }if(j!=i){printf("取元素位置參數(shù)錯！");return0;}*x=p->data;return1;}第2章線性表35

2.插入操作線性鏈表插入操作是指對某一個線性鏈表，在序號為i的結(jié)點之前插入一個指定元素值的新結(jié)點。假設(shè)在序號為i-1，i兩個結(jié)點之間插入一個數(shù)據(jù)元素值為x的新結(jié)點，已知p為該鏈表中指向ai-1結(jié)點的指針，如圖2.9所示。圖2.9帶頭結(jié)點的線性鏈表插入操作第2章線性表36

為插入數(shù)據(jù)元素x，首先要生成一個數(shù)據(jù)域為x的結(jié)點，然后插入在單鏈表中。根據(jù)插入操作的邏輯定義，需要修改ai-1結(jié)點的指針域，使其指向結(jié)點x，而結(jié)點x中的指針域應(yīng)指向ai結(jié)點，從而實現(xiàn)三個元素ai-1，ai和x之間邏輯關(guān)系的變化。假設(shè)p為指向結(jié)點ai-1的指針，q為指向結(jié)點x的指針，則上述指針修改可用語句描述為：

q->next=p->next；p->next=q； 從上述說明的插入操作的含義中我們可以看到，對該操作應(yīng)該設(shè)置三個參數(shù)，即在參數(shù)中指定所插入的線性鏈表、插入位置及插入的元素。假設(shè)所插入的線性鏈表SLlinkhead在本操作之外已說明，而插入位置及插入的元素分別為inti,DataTypex，插入操作取名為SLinkInsert，則該操作可表示為：

intSLinkInsert(SLNode*head,inti,DataTypex)；功能為：在帶頭結(jié)點的單鏈表head中的第i號結(jié)點之前插入數(shù)據(jù)元素值為x的新結(jié)點。操作的處理過程為：⑴尋找第i-1個結(jié)點，使指針p指向該結(jié)點；⑵若由于i不合理而找不到相應(yīng)的結(jié)點，則輸出信息，否則，生成一個新結(jié)點q,并將q插入到結(jié)點p之后。第2章線性表37程序如下：intSLinkInsert(SLNode*head,inti,DataTypex){SLNode*p,*q;intj;p=head;/*p指向頭結(jié)點*/j=-1;/*j初始為-1*/while(p->next!=NULL&&j<i-1)/*指針p指向數(shù)據(jù)元素ai-1結(jié)點*/{p=p->next;j++;}if(j!=i-1){printf("插入位置參數(shù)錯！");return0;}if((q=(SLNode*)malloc(sizeof(SLNode)))==NULL)exit(1);q->data=x;q->next=p->next;/*給指針q->next賦值*/p->next=q;/*給指針p->next重新賦值*/return1;}第2章線性表38

3.刪除操作線性鏈表的刪除操作是指刪除線性鏈表中的第i號結(jié)點。如圖2.10所示，p為指向結(jié)點ai-1的指針。為在單鏈表中實現(xiàn)元素之間邏輯關(guān)系的變化，僅需修改結(jié)點p中的指針域即可，指針修改可用語句描述為：

s=p->next;/*指針s指向數(shù)據(jù)元素ai結(jié)點*/*x=s->data;/*把指針s所指結(jié)點的數(shù)據(jù)元素域值賦予x*/p->next=p->next->next;圖2.10帶頭結(jié)點的線性鏈表刪除操作第2章線性表39

從上述說明的刪除操作的含義中我們可以看到，對該操作應(yīng)該設(shè)置三個參數(shù)，即在參數(shù)中要指定一個線性鏈表及刪除元素的結(jié)點序號。假設(shè)作為操作對象的線性鏈表SLNodehead在本操作之外已說明，而刪除元素的序號用inti表示，刪除操作取名為SLinkDelete,由DataType*x帶回刪除元素，則該操作可表示為：

intSLinkDelete(SLNode*head,intiDataType*x)；功能為：在帶頭結(jié)點的單鏈表head中刪除第i個結(jié)點并返回該結(jié)點中的元素值。處理過程為：⑴尋找第i號結(jié)點，使指針p指向該結(jié)點的前驅(qū)結(jié)點；⑵若由于i不合理而找不到相應(yīng)的結(jié)點，則輸出信息，返回0。否則，改變p的指針域，使得第i號結(jié)點從鏈表中被刪除，釋放該結(jié)點并返回1。第2章線性表40程序如下：intSLinkDelete(SLNode*head,inti,DataType*x){SLNode*p,*s;intj;p=head;/*p指向頭結(jié)點*/j=-1;/*j初始為-1*/while(p->next!=NULL&&p->next->next!=NULL&&j<i-1)/*最終讓指針p指向數(shù)據(jù)元素ai-1結(jié)點*/{p=p->next;j++;}if(j!=i-1){printf("插入位置參數(shù)錯！");return0;}s=p->next; /*指針s指向數(shù)據(jù)元素ai結(jié)點*/*x=s->data; /*把指針s所指結(jié)點的數(shù)據(jù)元素域值賦予x*/p->next=p->next->next;/*把數(shù)據(jù)元素ai結(jié)點從單鏈表中刪除指*/free(s); /*釋放指針s所指結(jié)點的內(nèi)存空間*/return1;}第2章線性表41

4.逆置操作單鏈表的逆置操作是指對一個用帶頭結(jié)點的鏈表表示的線性表進(jìn)行逆置。當(dāng)線性表采用順序存儲結(jié)構(gòu)表示時，可借助數(shù)據(jù)元素的交換來完成逆置操作。而當(dāng)采用單鏈表存儲結(jié)構(gòu)時，則以修改指針來完成逆置操作。單鏈表逆置前后的狀態(tài)如圖2.11所示。圖2.11單鏈表逆置操作示意圖第2章線性表42

在該操作中所涉及的參數(shù)是指定單鏈表的鏈頭指針SLNode*head。假設(shè)本操作取名為SLinkinver，則逆置操作可表示為：

SLinkinver(SLNode*head)；功能是a0與an-1互換，a1與an-2互換…依次類推。該操作在處理過程中，如果把逆置后的鏈表看成是一個新的鏈表，則處理過程如下：⑴建立一個新的鏈表作為逆置后的鏈表(使用原帶頭結(jié)點)，其初始狀態(tài)為空表；⑵依次從原鏈表中取下一個結(jié)點，并將該結(jié)點從鏈頭插入到新的鏈表中；

⑶重復(fù)過程⑵，直至原鏈表中的結(jié)點全部取完。第2章線性表43程序如下：SLinkinver(SLNode*head){SLNode*p,*s;p=head->next;head->next=NULL;while(p!=NULL){s=p;p=p->next;s->next=head->next;head->next=s;}}第2章線性表44

5．建鏈表操作線性鏈表的建表操作是指由一個一維數(shù)組a中的n個元素的值，建立一個長度為n的線性鏈表，其操作的含義如圖2.12所示。圖2.12建表操作示意圖第2章線性表45

在該操作中所涉及的參數(shù)是鏈表的長度n，存放n個元素的一維數(shù)組a中，表示所生成線性鏈表的鏈頭指針為head。假設(shè)這些參數(shù)均在本操作之外已說明，本操作取名為CrtLink，則建表操作表示為：

CrtLink(SLNode*head,intn,DataTypea[])；功能是建立一個由head指向的長度為n的單鏈表(帶頭結(jié)點)，并使其n個數(shù)據(jù)元素的值依次等于一維數(shù)組a中的n個元素的值。該操作的處理過程為：⑴建立一個空表；⑵生成一個結(jié)點，按從后到前上的次序從數(shù)組a中取出元素作為結(jié)點中的元素值，然后從鏈頭插入該結(jié)點；⑶重復(fù)執(zhí)行過程⑵，直至生成n個結(jié)點。第2章線性表46程序如下：CrtLink(SLNode*head,intn,DataTypea[]){SLNode*p;inti;head=(SLNode*)malloc(sizeof(SLNode));head.next=NULL;for(i=n-1;i>=0;i--){p=(SLNode*)malloc(sizeof(SLNode));p->data=a[i];p->next=head->next;head->next=p;}}第2章線性表472.3.4雙向循環(huán)鏈表的操作實現(xiàn)對雙向循環(huán)鏈表的操作的處理過程需同時考慮到雙向鏈和循環(huán)鏈兩個特點。有些操作如：Length(L)、Get(L，i)、locate(L，x)等僅需涉及一個方向的指針，則它們的算法描述和單鏈表的操作相類似，但在插入、刪除時有很大的不同。在進(jìn)行結(jié)點鏈接時，既要設(shè)置后繼鏈，又要設(shè)置前驅(qū)鏈。另外，在判別是否鏈末時，其條件是當(dāng)前指針是否與頭指針重合。下面我們給出對雙向循環(huán)鏈表進(jìn)行定位、插入與刪除的算法。第2章線性表481.雙向循環(huán)鏈表的取元素操作雙向循環(huán)鏈表的取元素操作可表示為：

intDLinkGet(DLNode*head,inti,DataType*x)；功能：在雙向循環(huán)鏈表DLNode*head中，確定第i個結(jié)點，若存在，返回1，若第i個結(jié)點不存在，則返回0。處理過程：從頭結(jié)點開始沿后繼鏈指針逐個后移直至指向第i個結(jié)點或指針p->next=head，則分別返回1或返回0。第i個結(jié)點的值由x帶回。第2章線性表49程序如下：intDLinkGet(DLNode*head,inti,DataType*x){DLNode*p;intj;p=head;j=-1;while(p->next!=head&&j<i)/*尋找第i個結(jié)點,*/{p=p->next;j++;}if(j!=i){printf("位置參數(shù)出錯!");return0;}*x=p->data;return1;}第2章線性表50

2.雙向循環(huán)鏈表的插入雙向循環(huán)鏈表的插入可表示為intDLinkInsert(DLNode*head,inti,DataTypex);

功能：在雙向循環(huán)鏈表DLNode*head中的第i個結(jié)點之后插入元素x。處理過程：⑴由參數(shù)i得到結(jié)點的指針p；⑵生成一個新的結(jié)點s，其元素值為x⑶若p!=head，則將s所指向的結(jié)點插入到雙向循環(huán)鏈表中由p所指向的結(jié)點之后，如圖2.13所示。圖2.13雙向循環(huán)鏈表插入結(jié)點時指針的變化第2章線性表51程序如下：intDLinkInsert(DLNode*head,inti,DataTypex){DLNode*p,*s;intj;p=head;j=-1;while(p->next!=head&&j<i) /*尋找第i個結(jié)點*/{p=p->next;j++;}if(j!=i){printf("插入位置參數(shù)出錯!");return0;}if((s=(DLNode*)malloc(sizeof(DLNode)))==NULL)exit(0);s->data=x;s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;return1;}第2章線性表523．雙向循環(huán)鏈表的刪除雙向循環(huán)鏈表的刪除可表示為：intDLinkDelete(DLNode*head,inti,DataType*x)；功能：刪除雙向循環(huán)鏈表DLNode*head中的第i個結(jié)點。處理過程：⑴由參數(shù)i得到結(jié)點的指針p；⑵若p!=head，則刪除雙向循環(huán)鏈表中的由p所指向的結(jié)點并釋放該結(jié)點，如圖2.14所示。圖2-14雙向循環(huán)鏈表刪除結(jié)點時指針的變化第2章線性表53程序如下：intListDelete(DLNode*head,inti,DataType*x){DLNode*p;intj;p=head;j=-1;while(p->next!=head&&j<i)/*尋找第i個結(jié)點*/{p=p->next;j++;}if(j!=i){printf("刪除位置參數(shù)出錯!");return0;}p->prior->next=p->next;p->next->prior=p->prior;free(p);return1;}第2章線性表542.4線性表的ADT定義以上我們討論了線性表的結(jié)構(gòu)特征、存儲方式及其相關(guān)操作的實現(xiàn)，在本節(jié)中我們將給出線性表的ADT定義即抽象數(shù)據(jù)類型定義，為以后面向?qū)ο蟪绦蛟O(shè)計中的類定義奠定基礎(chǔ)。根據(jù)面向?qū)ο蟪绦蛟O(shè)計的原則，實現(xiàn)部分與接口部分兩者應(yīng)該分離。接口部分可以用ADT定義即抽象數(shù)據(jù)類型定義來進(jìn)行描述。一種數(shù)據(jù)類型的ADT定義由數(shù)據(jù)元素、結(jié)構(gòu)及操作三部分組成。元素：ai同屬于一個數(shù)據(jù)元素類，i=0，1，2，…，n-1n≥0；結(jié)構(gòu)：對所有的數(shù)據(jù)元素ai(i=0，1，2，…，n-1)存在次序關(guān)系<ai，ai+1>，a0無前驅(qū)，an-1無后繼；第2章線性表55對線性表可執(zhí)行基本操作為：⑴Initiate(L)：初始化操作?？稍O(shè)定一個空的線性表L。⑵Length(L)：求長度函數(shù)。函數(shù)值為給定線性表L中數(shù)據(jù)元素的個數(shù)。⑶Empty(L)：判空表函數(shù)。若L為空表，則返回1，否則返回0⑷Clear(L)：表清空操作。操作的結(jié)果使L成為空表。⑸Get(L，i)：取元素函數(shù)。若0≤i≤Length(L)-1，則函數(shù)值為給定線性表L中第i個數(shù)據(jù)元素，否則為空元素NULL。稱i為該數(shù)據(jù)元素在線性表中的位序。⑹Locate(L，x)：定位函數(shù)。若線性表L中存在其值與x相等的數(shù)據(jù)元素，則函數(shù)值為該數(shù)據(jù)元素在線性表中的位序，否則為-1。若線性表中與x相等的數(shù)據(jù)元素不止一個，則函數(shù)值為這些元素在線性表中的位序的最小值。第2章線性表56⑺Prior(L，elem)：求前驅(qū)函數(shù)。已知elem為線性表L中的一個數(shù)據(jù)元素，若它的位序大于0，則函數(shù)值為elem的前驅(qū)，否則為空元素。⑻Next(L，elem)：求后繼函數(shù)。已知elem為線性表L中的一個數(shù)據(jù)元素，若它的位序小于Length(L)-1，則函數(shù)值為elem的后繼，否則為空元素。⑼Insert(L，i，x)：插入操作(前插)。在線性表L的第i號元素之前插入一個新元素x。⑽Delete(L，i)刪除操作。若0≤i≤Length(L)-1，則刪除線性表L中的第i號元素，否則此操作無意義。對線性表還可進(jìn)行一些更復(fù)雜的操作。如：將兩個或兩個以上的線性表合并成一個線性表；把一個線性表拆成兩個或兩個以上的線性表；復(fù)制一個線性表；對線性表中的元素進(jìn)行排序；對有序表進(jìn)行插入等等。第2章線性表572.5線性表的應(yīng)用-多項式相加問題2.5.1存儲結(jié)構(gòu)的選取

任一一元多項式可表示為Pn(x)=P0x0+P1x1+P2x2+...+Pnxn，顯然，由其n+1個系數(shù)可惟一確定該多項式。故一元多項式可用一個僅存儲其系數(shù)的線性表來表示，多項式指數(shù)i隱含于Pi的序號中。

P=(P0，P1，P2，...，Pn)

若采用順序存儲結(jié)構(gòu)來存儲這個線性表，那么多項式相加的算法實現(xiàn)十分容易，同位序元素相加即可。但當(dāng)多項式的次數(shù)很高而且變化很大時，采用這種順序存儲結(jié)構(gòu)極不合理。例如，多項式S(x)=1+3x+12x999需用一長度為1000的線性表來表示，而表中僅有三個非零元素，這樣將大量浪費內(nèi)存空間。此時可考慮另一種表示方法，如線性表S(x)可表示成S=((1,0)，(3,1),(12,999))，其元素包含兩個數(shù)據(jù)項：系數(shù)項和指數(shù)項。

第2章線性表582.5.2一元多項加法運算的實現(xiàn)采用單鏈表結(jié)構(gòu)來實現(xiàn)多項加法運算，無非是前述單向鏈表基本運算的綜合應(yīng)用。其數(shù)據(jù)結(jié)構(gòu)描述如下，typedefstuctPnode{floatcoef;intexp;structpnode*next;}Pnode;圖2.15給出了多項式A(x)=15+6x+9x7+3x18

和B(x)=4x+5x6+16x7的鏈?zhǔn)酱鎯Y(jié)構(gòu)(設(shè)一元多項式均按升冪形式存儲，頭結(jié)點指數(shù)域為-1)。圖2-15多項式鏈表第2章線性表59

若上例A+B結(jié)果仍存于A中，根據(jù)一元多項式相加的運算規(guī)則，其實質(zhì)是將B逐項按指數(shù)分情況合并于“和多項式”A中。設(shè)p,q分別指向A,B的第一個結(jié)點，如圖2.16所示，其算法思路如下：

(1)p->exp<q->exp,應(yīng)使指針后移p=p->next，如圖2.16(a)所示。

(2)p->exp=q->exp,將兩個結(jié)點系數(shù)相加，若系數(shù)和不為零，則修改p->ceof，并借助s釋放當(dāng)前q結(jié)點,而使q指向多項式B的下一個結(jié)點，如圖2.16(b)所示；若系數(shù)和為零，則應(yīng)借助s釋放p,q結(jié)點,而使p,q分別指向多項式A,B的下一個結(jié)點。

(3)p->exp>q->exp，將q結(jié)點在p結(jié)點之前插入A中,并使q指向多項式B的下一個結(jié)點，如圖2.16(c)所示。直到q=NULL為止或p=NULL，將B的剩余項鏈到A尾。最后釋放B的頭結(jié)點。第2章線性表60圖2-16多項式相加過程第2章線性表61本章小結(jié)本章主要討論線性表的邏輯結(jié)構(gòu)和物理存儲結(jié)構(gòu)以及各種存儲結(jié)構(gòu)下的算法實現(xiàn)。是以后學(xué)習(xí)棧和隊列的基礎(chǔ)。其主要內(nèi)容包括：1.基本概念和術(shù)語⑴線性表一般，一個線性表是由n個元素組成的有限序列，可記作：L=(a0,a1,…,an-1)其中，ai代表一個數(shù)據(jù)元素，a0

稱為表頭（或頭結(jié)點），an-1稱為表尾（或尾結(jié)點），ai(0≤i≤n-1）稱為ai+1的直接前驅(qū)，ai+1稱為ai的直接后繼。線性表中數(shù)據(jù)元素的個數(shù)稱為線性表的長度，長度為0的線性表稱為空表。⑵線性表的順序存儲最簡單和最常用的方式是用一片連續(xù)的存儲區(qū)域，也就是用一組地址連續(xù)的存儲單元來依次存儲線性表的各個元素。線性表(a0，a1，…，ai，…，an-1)的順序存儲結(jié)構(gòu)如圖2.1所示，這種存儲方式的特點是用存儲單元物理位置的相鄰來表示相鄰元素間的邏輯關(guān)系。第2章線性表62

一般來說，線性表中第i個元素ai的存儲地址為：LOC(ai)=LOC(a0)+(i)*s式中，LOC(a0)為線性表的第一個元素a0的存儲地址，通常稱為線性表的開始地址或基地址。它的特點是邏輯關(guān)系上相鄰的兩個元素在物理位置上也相鄰，因此順序表中任一元素的存儲位置都可以用一個簡單直觀的公式來表示。然而，從另一方面看，這種存儲結(jié)構(gòu)也有許多不足之處：首先，我們難以確定適當(dāng)?shù)拇鎯臻g的大小，如果指定得太小，則難以擴充；如果指定得太大，則存儲空間不能得到充分的利用。其次，在做插入或刪除時需移動大量元素。第2章線性表63①單鏈表存儲結(jié)構(gòu)是用一組任意的存儲單元來存儲線性表的數(shù)據(jù)元素。為了表示數(shù)據(jù)元素間的邏輯關(guān)系，對數(shù)據(jù)元素ai來說，除了存儲其本身的信息外，還需存儲一個直接后繼的信息。在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，數(shù)據(jù)元素ai的存儲映像，稱為結(jié)點。單鏈表的結(jié)點包括兩個域：存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域；存儲直接后繼存儲位置的域稱為指針域。n個結(jié)點(0≤i≤n-1)的存儲映象鏈結(jié)成一個鏈表，即為線性表(a0,a1,…,an-1)的鏈?zhǔn)酱鎯Y(jié)構(gòu)。線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點是，數(shù)據(jù)元素之間的邏輯關(guān)系是由結(jié)點中的指針指示的。由于此鏈表的每個結(jié)點中只包含一個指針域故稱為單鏈表。第2章線性表64

為了適應(yīng)算法的需要，需在單鏈表的第一個結(jié)點之前附設(shè)一個結(jié)點，稱為表頭結(jié)點。表頭結(jié)點的數(shù)據(jù)域可以不存儲任何信息，頭結(jié)點的指針域存儲指向第一個結(jié)點的指針，此時，單鏈表的頭指針指向表頭結(jié)點。②我們使鏈表中最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表就形成一個環(huán)，這樣形成的鏈表稱為循環(huán)鏈表。對于循環(huán)鏈表，可以從鏈表中的任一點出發(fā)找到鏈表中所有的其它結(jié)點。③在鏈表的結(jié)點中增加了一個指向前驅(qū)結(jié)點的指針域，這樣形成的鏈表稱為雙向鏈表。對于雙向鏈表，既可以對數(shù)據(jù)元素由前向后地進(jìn)行訪問，又可以由后向前地進(jìn)行訪問。第2章線性表652.線性表的存儲結(jié)構(gòu)⑴順序存儲使用C語言，我們可以定義以下的記錄(結(jié)構(gòu))類型來表示順序表，其類型名用SeqList表示。MaxSize線性表可能達(dá)到的最大長度；typedefstruct{DataTypelist[MaxSize];intsize;}SeqList;⑵單鏈表單鏈表的結(jié)點及結(jié)點指針類型可定義如下：第2章線性表66typedefstructNode{DataTypedata;structNode*next;}SLNode,*SLlink;⑶雙向鏈表雙向鏈表的結(jié)點及結(jié)點指針類型可定義如下：typedefstructNode{DataTypedata;structNode*prior;structNode*next;}DLNode,*DLlink;第2章線性表673.線性表的有關(guān)操作在確定了線性表的存儲結(jié)構(gòu)后，應(yīng)考慮對線性表所施行的操作。從邏輯上講可以對線性表施行數(shù)據(jù)元素的插入、刪除等各種操作，但這些操作實現(xiàn)過程及執(zhí)行效率又完全取決于數(shù)據(jù)的存儲結(jié)構(gòu)。第2章線性表68習(xí)題一、填空1.在順序表中插入或刪除一個元素，需要平均移動

元素，具體移動的元素個數(shù)與

有關(guān)。2.線性表中結(jié)點的集合是

的，結(jié)點間的關(guān)系是

的。3.向一個長度為n的向量的第i個元素(0≤i≤n-1)之前插入一個元素時，需向后移動

個元素。4.向一個長度為n的向量中刪除第i個元素(0≤i≤n-1)時，需向前移動

個元素。5.在順序表中訪問任意一結(jié)點的時間復(fù)雜度均為

，因此，順序表也稱為

的數(shù)據(jù)結(jié)構(gòu)。6.順序表中邏輯上相鄰的元素的物理位置

相鄰。單鏈表中邏輯上相鄰的元素的物理位置

相鄰。7.在單鏈表中，除了第一個結(jié)點外，任一結(jié)點的存儲位置由

指示。8.在n個結(jié)點的單鏈表中要刪除已知結(jié)點*p，需找到它的

，其時間復(fù)雜度為

。第2章線性表69二、判斷正誤（）1.鏈表的每個結(jié)點中都恰好包含一個指針。（）2.鏈表的物理存儲結(jié)構(gòu)具有同鏈表一樣的順序。（）3.鏈表的刪除算法很簡單，因為當(dāng)刪除鏈中某個結(jié)點后，計算機會自動將后續(xù)各個單元向前移動。（）4.線性表的每個結(jié)點只能是一個簡單類型，而鏈表的每個結(jié)點可以是一個復(fù)雜類型。（）5.順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機存取。（）6.順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。（）7.線性表在物理存儲空間中也一定是連續(xù)的。（）8.線性表在順序存儲時，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。（）9.順序存儲方式只能用于存儲線性結(jié)構(gòu)。（）10.線性表的邏輯順序與存儲順序總是一致的。第2章線性表70三、單項選擇題（）