數(shù)據(jù)結(jié)構(gòu)(c語言版)-嚴蔚敏版-第2章-線性表-信大(第2講)

緒論要點回顧數(shù)據(jù)結(jié)構(gòu)定義——指互相有關(guān)聯(lián)的數(shù)據(jù)元素的集合，用D_S=(D,S)數(shù)據(jù)結(jié)構(gòu)是相互之間存在著一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)內(nèi)容——數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和運算

算法效率指標——時間效率和空間效率數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容邏輯結(jié)構(gòu)唯一存儲結(jié)構(gòu)不唯一運算的實現(xiàn)依賴于存儲結(jié)構(gòu)近期

上課

內(nèi)容第2章線性表第3章棧和隊列第4章串第5章數(shù)組和廣義表

線性結(jié)構(gòu)(邏輯、存儲和運算)

若結(jié)構(gòu)是非空有限集，則有且僅有一個開始結(jié)點和一個終端結(jié)點，并且所有結(jié)點都最多只有一個直接前趨和一個直接后繼。可表示為：(a1,a2,……,an)線性結(jié)構(gòu)的定義：線性結(jié)構(gòu)的特點：①只有一個首結(jié)點和尾結(jié)點；②除首尾結(jié)點外，其他結(jié)點只有一個直接前驅(qū)和一個直接后繼。線性結(jié)構(gòu)包括線性表、堆棧、隊列、字符串、數(shù)組等等，其中，最典型、最常用的是------簡言之，線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是一對一

的第二章線性表第2章線性表2.1線性表的類型定義2.2線性表的順序表示和實現(xiàn)2.3線性表的鏈式表示和實現(xiàn)圖2.1線性表的邏輯結(jié)構(gòu)2.1線性表的類型定義2.1.1線性表的邏輯結(jié)構(gòu)（a1,a2,…ai-1，ai,ai＋1

，…,an）線性表的定義：是n個數(shù)據(jù)元素的有限序列n=0時稱為數(shù)據(jù)元素表頭ai的直接前趨ai的直接后繼下標，是元素的序號，表示元素在表中的位置n為元素總個數(shù)，即表長空表表尾例1分析26個英文字母組成的英文表

（A,B,C,D,……,Z）例2分析學生情況登記表數(shù)據(jù)元素都是記錄;元素間關(guān)系是線性數(shù)據(jù)元素都是字母;元素間關(guān)系是線性同一線性表中的元素必定具有相同特性

線性表的特點可概括如下：同一性有窮性有序性

線性表是最常見的數(shù)據(jù)結(jié)構(gòu)，因為矩陣、數(shù)組、字符串、堆棧、隊列等都符合線性條件。練：判斷下列敘述的正誤：1.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶按使用需要建立的。2.線性表的邏輯結(jié)構(gòu)定義是唯一的，不依賴于計算機。3.數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種關(guān)系的數(shù)據(jù)元素的全體。4.線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是一對一的。5.一維向量是線性表，但二維或N維數(shù)組不是。6.“同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有相同的特性”是指數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)都相等?！獭痢獭獭痢晾?-1兩個集合La和Lb的合并假設(shè)兩個集合La{7,2,3}Lb{8,4,5,6}怎樣將他們合并呢？1，首先知道La的長度是3和Lb的長度是42，之后把Lb集合中的元素依次和La中的元素進行比對形成一個循環(huán)，首先Lb中的8與La的元素依次比對，8與所有La中元素不同，將8插入La中，3，2與2相同進入Lb的下一個元素，都不相同，之后將元素合并到La中，例2-2兩個非遞減有序的線性表La和Lb的合并

如La{2,4,6}Lb{4,7,9,10}合并1，定義Lc,長度是La長度+Lb長度2，La中2與Lb中4，把小La中的2的插入Lc，La進入下一個元素3,La中4與Lb中4比較，把La的4插入Lc,LaLb都下一個元素4,La中6與Lb中7比較，把小的La中的6的插入Lc，La進入下一個元素，無元素了5，就將Lb中剩余元素依次加入Lc中LaLbLc2.2線性表的順序表示和實現(xiàn)2.2.1線性表的順序存儲結(jié)構(gòu)用一組地址連續(xù)的存儲單元依次存儲線性表的元素，可通過數(shù)組來實現(xiàn)。把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元中的存儲結(jié)構(gòu)。順序存儲定義：順序存儲方法：簡言之，邏輯上相鄰，物理上也相鄰線性表順序存儲特點：1.邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；2.若已知表中首元素在存儲器中的位置，則其他元素存放位置亦可求出（利用數(shù)組下標）。計算方法是：設(shè)首元素a1的存放地址為LOC(a1)（稱為首地址），設(shè)每個元素占用存儲空間（地址長度）為L字節(jié)，則表中任一數(shù)據(jù)元素的存放地址為：

LOC(ai)=LOC(a1)+L*(i-1)LOC(ai+1)=LOC(ai)+L它是一種隨機存取的數(shù)據(jù)結(jié)構(gòu)。

注意：C語言中的數(shù)組的下標從0開始，即：V[n]的有效范圍是V[0]～V[n-1]線性表的順序存儲結(jié)構(gòu)示意圖

地址內(nèi)容元素在表中的位序1i2n空閑區(qū)i+1Lb=LOC(a1)b+Lb+(i-1)Lb+(n-1)L一個一維數(shù)組Ｍ，下標的范圍是０到９，每個數(shù)組元素用相鄰的５個字節(jié)存儲。存儲器按字節(jié)編址，設(shè)存儲數(shù)組元素Ｍ[０]的第一個字節(jié)的地址是98，則Ｍ[３]的第一個字節(jié)的地址是

113例1因此：LOC(M[3])=98+5×(3-0)=113解：地址計算通式為：LOC(ai)=LOC(a1)+L*（i-1）用數(shù)組V來存放26個英文字母組成的線性表(a，b，c，…，z)，寫出在順序結(jié)構(gòu)上生成和顯示該表的C語言程序。

voidbuild()/*字母線性表的生成，即建表操作*/{inti;V[0]='a';for(i=1;i<=n-1;i++)

V[i]=V[i-1]+1;

}核心語句：法1V[i]=V[i-1]+1;法2V[i]=’a’+i;法3V[i]=97+i;例2voidbuild();voiddisplay();#define n26intV[n];voidmain(void)/*主函數(shù)，字母線性表的生成和輸出*/{

build();

display();}voiddisplay()/*字母線性表的顯示，即讀表操作*/{inti;for(i=0;i<=n-1;i++)printf("%c",V[i]);printf("\n");}執(zhí)行結(jié)果：abcdefghijklmnopqrstuvwxyz26個字母另一種寫法#include<stdio.h>intmain(){ inti; for(i=0;i<26;i++) if(i%2==0) printf("%c",'A'+i); else printf("%c",'a'+i); printf("\n"); return0;}2.2.2線性表順序存儲結(jié)構(gòu)上的基本運算回憶：數(shù)據(jù)結(jié)構(gòu)基本運算操作有：

修改、插入、刪除、查找、排序1.修改操作

通過數(shù)組的下標便可訪問某個特定元素并修改之。核心語句:

V[i]=x;顯然，順序表修改操作的時間效率是T(n)=O(1)2.存取操作在這種結(jié)構(gòu)中容易實現(xiàn)隨機存取第i個數(shù)據(jù)元素，C語言中數(shù)組的下標從0開始，所以ai應(yīng)在L.elem[i-1]中存取。

3.插入操作在表的第i(1≤i≤n+1)個位置，插入一個新元素e，使長度為n的線性表(e1，…，ei-1，ei，…，en)變成長度為n+1的線性表（e1，…,ei-1，e，ei，…，en）。實現(xiàn)步驟：將第n至第i位的元素向后移動一個位置；將要插入的元素寫到第i個位置；表長加1。注意：事先應(yīng)判斷:插入位置i是否合法?表是否已滿?長度為n的線性表變?yōu)殚L度為n+1的線性表（a1,a2,…,ai-1,ai,…,an）（a1,a2,…,ai-1,x,ai,…,an）

例如：已知線性表(4,9,15,28,30,30,42,51,62)，需在第4個元素之前插入一個元素“21”，則需要將第9個位置到第4個位置的元素依次后移一個位置，然后將“21”插入到第4個位置，如圖2.3所示。請注意區(qū)分元素的序號和數(shù)組的下標。圖2.3順序表中插入元素

插入元素時，時間主要耗費在移動元素上。移動個數(shù)取決于插入位置。for(j=n;j>=i;j--)a[j+1]=a[j];a[i]=x;n++;//元素后移一個位置//插入x//表長加1

4.刪除操作指將表的第i(1≤i≤n)個元素刪去，使長度為n的線性表(e1，…,ei-1，ei，ei+1，…，en)變成長度為n-1的線性表(e1，…,ei-1，ei+1，…，en)。

實現(xiàn)步驟：將第i+1至第n位的元素向前移動一個位置；表長減1。注意：事先需要判斷，刪除位置i是否合法?圖2.4順序表中刪除元素例如：線性表(4,9,15,21,28,30,30,42,51,62)刪除第5個元素，則需將第6個元素到第10個元素依次向前移動一個位置，如圖2.4所示。for(j=i+1;j<=n;j++)a[j-1]=a[j];n--;//元素前移一個位置//表長減1核心語句：線性表順序表示的優(yōu)點是：(1）無需為表示結(jié)點間的邏輯關(guān)系而增加額外的存儲空間（因為邏輯上相鄰的元素其存儲的物理位置也是相鄰的）；(2）可方便地隨機存取表中的任一元素。其缺點是：（1）插入或刪除運算不方便，除表尾的位置外，在表的其它位置上進行插入或刪除操作都必須移動大量的結(jié)點，其效率較低;（2）預分配空間（浪費）；（3）表的擴充不方便。

2.3線性表的鏈式表示和實現(xiàn)鏈式存儲結(jié)構(gòu)特點：其結(jié)點在存儲器中的位置是隨意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。如何實現(xiàn)？通過指針來實現(xiàn)注意：每個存儲結(jié)點都包含兩部分：

數(shù)據(jù)域和指針域例1畫出26個英文字母表的鏈式存儲結(jié)構(gòu)。該字母表在內(nèi)存的鏈式存放示意圖如下：

解：該字母表的邏輯結(jié)構(gòu)為：(a,b,…,y,z)aheadb/\z……各結(jié)點由兩個域組成：數(shù)據(jù)域：存儲元素數(shù)值數(shù)據(jù)；指針域：存儲直接后繼或者直接前驅(qū)的存儲位置。指針數(shù)據(jù)指針數(shù)據(jù)指針或樣式：與鏈式存儲有關(guān)的術(shù)語：1、結(jié)點：數(shù)據(jù)元素的存儲映像。由數(shù)據(jù)域和指針域兩部分組成；2、鏈表：

n個結(jié)點由指針鏈組成一個鏈表。它是線性表的鏈式存儲映像，稱為線性表的鏈式存儲結(jié)構(gòu)。3、單鏈表、雙鏈表、多鏈表、循環(huán)鏈表：結(jié)點只有一個指針域的鏈表，稱為單鏈表或線性鏈表；有兩個指針域的鏈表，稱為雙鏈表；有多個指針域的鏈表，稱為多鏈表；首尾相接的鏈表稱為循環(huán)鏈表。a1heada2an……h(huán)ead循環(huán)鏈表示意圖：4、頭指針、頭結(jié)點和首元結(jié)點

示意圖如下：頭指針頭結(jié)點首元結(jié)點a1heada2…infoan^頭指針是指向鏈表中第一個結(jié)點(或為頭結(jié)點或為首元結(jié)點)的指針；頭結(jié)點是在鏈表的首元結(jié)點之前附設(shè)的一個結(jié)點；數(shù)據(jù)域內(nèi)只放空表標志和表長等信息;首元結(jié)點是指鏈表中存儲線性表第一個數(shù)據(jù)元素a1的結(jié)點。特點：用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素利用指針實現(xiàn)了用不相鄰的存儲單元存放邏輯上相鄰的元素每個數(shù)據(jù)元素ai，除存儲本身信息外還需存儲其直接后繼的信息結(jié)點 數(shù)據(jù)域：元素本身信息指針域：指示直接后繼的存儲位置2.3.1單鏈表由于鏈表的每個結(jié)點只有一個指針域，故將這種鏈表又稱為單鏈表。單鏈表中第一個結(jié)點無前趨，應(yīng)設(shè)一個頭指針H指向第一個結(jié)點。單鏈表中最后一個結(jié)點沒有直接后繼，則指定最后一個結(jié)點的指針域為“空”（NULL）。

整個鏈表的存取必須從頭指針開始。

例如：圖2.5所示為線性表（A,B,C,D,E,F,G）的單鏈表存儲結(jié)構(gòu)，整個鏈表的存取需從頭指針開始進行，依次順著每個結(jié)點的指針域找到線性表的各個元素。圖2.5單鏈表的示例圖圖2.6單鏈表的邏輯狀態(tài)圖2.7帶頭結(jié)點單鏈表圖示一個線性表的邏輯結(jié)構(gòu)為：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存儲結(jié)構(gòu)用單鏈表表示如下，請問其頭指針的值是多少？例：答：頭指針是指向鏈表中第一個結(jié)點的指針，因此關(guān)鍵是要尋找第一個結(jié)點的地址。7ZHAOH31∴頭指針的值是31上例鏈表的邏輯結(jié)構(gòu)示意圖有以下兩種形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH區(qū)別：①無頭結(jié)點②有頭結(jié)點答：討論1.

在鏈表中設(shè)置頭結(jié)點有什么好處？討論2.

如何表示空表？頭結(jié)點即在鏈表的首元結(jié)點之前附設(shè)的一個結(jié)點，該結(jié)點的數(shù)據(jù)域中不存儲線性表的數(shù)據(jù)元素，其作用是為了對鏈表進行操作時，可以對空表、非空表的情況以及對首元結(jié)點進行統(tǒng)一處理，編程更方便。答：無頭結(jié)點時，當頭指針的值為空時表示空表；有頭結(jié)點時，當頭結(jié)點的指針域為空時表示空表。^頭指針^頭指針頭結(jié)點無頭結(jié)點有頭結(jié)點討論3.頭結(jié)點的數(shù)據(jù)域內(nèi)裝的是什么？頭結(jié)點的數(shù)據(jù)域可以為空，也可存放線性表長度等附加信息，但此結(jié)點不能計入鏈表長度值。答：討論4.鏈表的數(shù)據(jù)元素有兩個域，不再是簡單數(shù)據(jù)類型，編程時該如何表示？因每個結(jié)點至少有兩個分量，所以要采用結(jié)構(gòu)體數(shù)據(jù)類型。答：什么是結(jié)構(gòu)類型？如何書寫表達？——補充C語言內(nèi)容

頭結(jié)點的數(shù)據(jù)域H補充結(jié)構(gòu)數(shù)據(jù)類型及其C語言表示法①類型定義和變量說明可以合寫為：typedefstructCh{chardata;//定義數(shù)據(jù)域的變量名及其類型structCh*next;//定義指針域的變量名及其類型}test，*head;/*test是Ch結(jié)構(gòu)類型的變量,*head是Ch結(jié)構(gòu)類型的頭指針*/以26個字母的鏈表為例，每個結(jié)點都有兩個分量：假設(shè)每個結(jié)點用變量test表示，其中兩個分量分別用data和*next表示，則：*nextdatatest補充：結(jié)構(gòu)類型的C語言表示法②對于指向結(jié)構(gòu)變量test首地址的指針，還可說明為：structtest*p,*q;(或用structCh*L；)//注：剛才已經(jīng)定義了test為用戶自定義的Ch類型③每個結(jié)點的分量如何表示？*nextdatatestp方式1：直接用test.data＝'a'；test.next=q方式2：先讓指針變量p指向該結(jié)點的首地址，然后用：

p->data='a';p->next=q;方式3：先讓指針變量p指向該結(jié)點的首地址，然后用：(*p).data='a'；(*p).next＝q單鏈表可以由頭指針唯一確定。單鏈表的存儲結(jié)構(gòu)描述如下：typedef

struct

LNode

{

ElemType

data;struct

LNode

*next;}LNode

,*LinkList;/*LinkList為結(jié)構(gòu)指針類型*/

假設(shè)L是LinkList型的變量，則L是一個結(jié)構(gòu)指針，即單鏈表的頭指針，它指向表中第一個結(jié)點。若L=NULL（對于帶頭結(jié)點的單鏈表為L->next=NULL），則表示單鏈表為一個空表，其長度為0。若不是空表，對于帶頭結(jié)點的單鏈表L，p=L->next指向表中的第一個結(jié)點a1，即p->data=a1，而p->next->data=a2。其余依此類推。1.查找算法描述：查找第i個結(jié)點，從頭指針L出發(fā)，順著鏈域掃描。用指針p指向當前掃描到的結(jié)點，用j做計數(shù)器，累計當前掃描過的結(jié)點數(shù)。當j==i時，指針p所指的結(jié)點就是要找的第i個結(jié)點。2.3.2單鏈表上的基本運算2.單鏈表插入操作算法描述：

要在第i個位置插入元素e，需要找到第i-1個結(jié)點并由指針p指示，然后申請一個新的結(jié)點并由指針s指示，其數(shù)據(jù)域的值為e。

修改第i-1個結(jié)點的指針使其指向s，使s結(jié)點的指針域指向原第i個結(jié)點。插入：s->next=p->next;

p->next=s;在鏈表中插入一個元素的示意圖如下：xsbapabp插入步驟（即核心語句）：Step1：s->next=p->next;Step2：p->next=s；p->nexts->next元素x結(jié)點應(yīng)預先生成：s=(LinkList)malloc(m);s->data=x;s->next=p->next;p->next=s;3.刪除在鏈表中刪除某元素的示意圖如下：cabp刪除步驟（即核心語句）：q=p->next;//保存b的指針，靠它才能指向cp->next=q->next;//a、c兩結(jié)點相連free(q)；//刪除b結(jié)點，徹底釋放p->next思考：省略free(q)語句行不行？(p->next)->next××4.建立單鏈表圖2.10頭插法建立單鏈表圖示2）尾插法建表圖2.11尾插法建表圖示5.應(yīng)用舉例：兩個鏈表的歸并(教材P31)算法要求：已知：線性表A、B，分別由單鏈表LA,LB存儲，其中數(shù)據(jù)元素按值非遞減有序排列，要求：將A，B歸并為一個新的線性表C,C的數(shù)據(jù)元素仍按值非遞減排列。設(shè)線性表C由單鏈表LC存儲。假設(shè)：A=(3，5，8，11)，B=(2，6，8，9，11)預測：合并后C=(2,3,5,6,8,8,9,11，11)用鏈表可表示為：3511/\8

La2611/\8

Lb92365

Lc8頭結(jié)點算法分析：算法主要包括：搜索、比較、插入三個操作：搜索：需要兩個指針搜索兩個鏈表；比較：比較結(jié)點數(shù)據(jù)域中數(shù)據(jù)的大?。徊迦耄簩蓚€結(jié)點中數(shù)據(jù)小的結(jié)點插入新鏈表。La3

5

8

11^

Lb2

6

8

11^9

PaPbPaPbPa、Pb用于搜索La和Lb，

Pc指向新鏈表當前結(jié)點Lc

…

Pa3

PcPa5

Pc11^Pc2

PbPcPa思考：1、不用Lc，直接把La表插到Lb表中；或者把Lb表插到La表中，如何編程？2、要求不能有重復的數(shù)據(jù)元素，如何編程？6，其他形式的鏈表討論1：用一維數(shù)組也能存放鏈表嗎？怎樣實現(xiàn)？答：能。只要定義一個結(jié)構(gòu)類型(含數(shù)據(jù)域和指示域)數(shù)組，就可以完全描述鏈表，這種鏈表稱為靜態(tài)鏈表。注：數(shù)據(jù)域含義與前面相同，指示域相當于前面的指針域。靜態(tài)鏈表的插入與刪除操作與普通鏈表一樣，不需要移動元素，只需修改指示器就可以了。具體實現(xiàn)過程見教材P31-34。討論2：鏈表能不能首尾相連？怎樣實現(xiàn)？答：能。只要將表中最后一個結(jié)點的指針域指向頭結(jié)點即可(P->next=head;)。這種形成環(huán)路的鏈表稱為循環(huán)鏈表。特別：帶頭結(jié)點的空循環(huán)鏈表樣式H參見教材P35

特點：

1、從任一結(jié)點出發(fā)均可找到表中其他結(jié)點。

2、操作僅有一點與單鏈表不同：循環(huán)條件單鏈表-----p=NULL或p->next=NULL循環(huán)鏈表-----p=head或p->next=head圖2.13循環(huán)鏈表討論3：單鏈表只能查找結(jié)點的直接后繼，能不能查找直接前驅(qū)？如何實現(xiàn)？答：能。只要把單鏈表再多開一個指針域即可(例如用*next和*prior;)。雙向鏈表在非線性結(jié)構(gòu)(如樹結(jié)構(gòu))中將大量使用。這種有兩個指針的鏈表稱為雙向鏈表。其特點是可以雙向查找表中結(jié)點。參見教材P35—39。特別：帶頭結(jié)點的空雙向鏈表樣式：圖2.14雙向鏈表的結(jié)點結(jié)構(gòu)

由于在雙向鏈表中既有前向鏈又有后向鏈，尋找任一個結(jié)點的直接前驅(qū)結(jié)點與直接后繼結(jié)點變得非常方便。

設(shè)指針p指向雙鏈表中某一結(jié)點，則有下式成立：p->prior->next=p=p->next->prior圖2.15雙向循環(huán)鏈表圖示1.雙向鏈表的前插操作圖2.16雙向鏈表插入操作2.雙向鏈表的刪除操作算法描述：圖2.17雙向鏈表的刪除操作要點回顧鏈表的表示(包括有關(guān)術(shù)語、結(jié)構(gòu)數(shù)據(jù)類型等)鏈表的實現(xiàn)(建表、輸出、修改、插入、刪除)