數(shù)據(jù)結構（C語言版）課件 第2章線性表

數(shù)據(jù)結構（C語言版）線性表第2章第2章線性表第3章棧和隊列第4章串、數(shù)組和廣義表

若結構是非空有限集，則有且僅有一個開始結點和一個終端結點，并且所有結點都最多只有一個直接前趨和一個直接后繼?？杀硎緸椋海╝1,a2,……,an）線性結構的定義：近3周上課內容線性結構（邏輯、存儲和運算）線性結構的特點：①只有一個首結點和尾結點；②除首尾結點外，其他結點只有一個直接前驅和一個直接后繼。線性結構表達式：（a1,a2,……,an）

線性結構包括線性表、堆棧、隊列、字符串、數(shù)組等等，其中，最典型、最常用的是線性表簡言之，線性結構反映結點間的邏輯關系是

一對一的近3周上課內容了解線性結構的特點掌握順序表的定義、查找、插入和刪除掌握鏈表的定義、創(chuàng)建、查找、插入和刪除能夠從時間和空間復雜度的角度比較兩種存儲結構的不同特點及其適用場合01OPTION02OPTION03OPTION04OPTIONtarget目標目錄導航2.12.22.32.42.52.62.72.82.9線性表的定義和特點案例引入線性表的類型定義線性表的順序表示和實現(xiàn)線性表的鏈式表示和實現(xiàn)順序表和鏈表的比較線性表的應用案例分析與實現(xiàn)LeetCode算法練習題Contents（a1,a2,…,ai-1,ai,ai＋1,…,an）線性表的定義：用數(shù)據(jù)元素的有限序列表示。n=0時稱為數(shù)據(jù)元素線性起點ai的直接前驅ai的直接后繼空表線性終點線性表的定義和特點下標，是元素的序號，表示元素在表中的位置。n為元素總個數(shù)，即表長。線性表（LinearList）：線性表的定義和特點由n（n≥0）個數(shù)據(jù)特性相同的數(shù)據(jù)元素構成的有限序列。數(shù)據(jù)元素的個數(shù)n（n≥0）定義為線性表的長度；當

n=0

時稱為空表；對于非空的線性表，每個數(shù)據(jù)元素都有一個確定的位置，可表示為L=（a1,a2,…,ai-1,ai,ai＋1,…,an）；元素ai（1≤i≤n）只是一個抽象的符號，其具體含義在不同的情況下可以不同。（A,B,C,D,……,Z）例2分析學生情況登記表數(shù)據(jù)元素都是學生記錄，

元素間關系是線性。同一線性表中的元素必定具有相同特性。學號姓名性別年齡班級041810205于春梅女1804級計算機1班041810260何仕鵬男2004級計算機2班041810284王爽女1904級計算機3班041810360王亞武男1804級計算機4班：：：

：：例1

分析26個英文字母組成的英文表數(shù)據(jù)元素都是字母，元素間關系是線性。線性表的定義和特點線性表的特點：線性表的定義和特點順序性（序列）：元素具有線性順序，除第一個數(shù)據(jù)元素無前驅、最后一個數(shù)據(jù)元素無后繼之外，其他每個數(shù)據(jù)元素均有一個前驅和一個后繼

；有限性（有限）：元素個數(shù)有限，在計算機中處理的對象都是有限的

；相同性（相同特性）：所有數(shù)據(jù)元素的類型相同，即數(shù)據(jù)元素來自于同一數(shù)據(jù)對象

；抽象性（元素類型不確定）：數(shù)據(jù)元素的類型需要根據(jù)實際的具體問題而確定，在定義中是不具體的，而是抽象的。目錄導航2.12.22.32.42.52.62.72.82.9線性表的定義和特點案例引入線性表的類型定義線性表的順序表示和實現(xiàn)線性表的鏈式表示和實現(xiàn)順序表和鏈表的比較線性表的應用案例分析與實現(xiàn)LeetCode算法練習題Contents2.2案例引入案例2.1：一元多項式的運算

案例2.2：稀疏多項式的運算指數(shù)（下標i）01234系數(shù)p[i]105-432案例2.1：一元多項式的運算Pn(x)

=

p0

+

p1x

+

p2x2

+

…

+

pnxn線性表P

=

(p0,p1,p2,…,pn)P(x)

=

10

+

5x

-

4x2

+

3x3

+

2x4數(shù)組表示（每一項的指數(shù)i隱含在其系數(shù)pi的序號中）Rn(x)

=

Pn(x)

+

Qm(x)線性表R

=

(p0

+

q0,p1

+

q1,p2

+

q2,…,pm

+

qm,pm+1,…,pn)稀疏多項式S(x)

=

1

+

3x10000

+

2x20000案例2.1：一元多項式的運算將會造成存儲空間浪費，怎么辦？下標i0123下標i012系數(shù)a[i]7395系數(shù)b[i]822-9指數(shù)01817指數(shù)178多項式非零項的數(shù)組表示

線性表P

=((p1,e1),(p2,e2),…,(pm,em))案例2.2：稀疏多項式的運算（a）A(x)

=

7

+

3x

+

9x8

+

5x17

（b）B(x)

=

8x

+

22x7

?

9x8案例2.2：稀疏多項式的運算01創(chuàng)建一個新數(shù)組c。分別從頭遍歷比較a和b的每一項：指數(shù)相同，對應系數(shù)相加，若其和不為零，則在c中增加一個新項；指數(shù)不相同，則將指數(shù)較小的項復制到c中。一個多項式已遍歷完畢時，將另一個剩余項依次復制到c中即可。0203A17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8-1703198517-181227-98ABpapb順序存儲結構存在問題存儲空間分配不靈活運算的空間復雜度高鏈式存儲結構案例2.2：稀疏多項式的運算多項式相加A17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8-1703198517-181227-98ABpapb多項式相加A17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8181227-98ABpapb多項式相加A17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8181227-98papbAB多項式相加A17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8181227-98ABpapb馬克思主義唯物論從實際出發(fā)以客觀存在的事物為出發(fā)點，深入了解和把握事物的本質和規(guī)律。實事求事將理論與實踐相結合?？茖W方法論歸納與演繹，分析與綜合。案例2.3：圖書信息管理系統(tǒng)實現(xiàn)一個圖書信息管理系統(tǒng)，包括以下6個具體功能：（1）查找

（2）插入

（3）刪除

（4）修改（5）排序

（6）計數(shù)圖書表抽象為線性表表中每本圖書抽象為線性表中的數(shù)據(jù)元素圖書順序表圖書鏈表案例2.3：圖書信息管理系統(tǒng)線性表中數(shù)據(jù)元素的類型可以為簡單類型，也可以為復雜類型。許多實際應用問題所涉的基本操作有很大相似性，不應為每個具體應用單獨編寫一個程序。從具體應用中抽象出共性的邏輯結構和基本操作（抽象數(shù)據(jù)類型），然后實現(xiàn)其存儲結構和基本操作?？偨Y030102目錄導航2.12.22.32.42.52.62.72.8線性表的定義和特點案例引入線性表的類型定義線性表的順序表示和實現(xiàn)線性表的鏈式表示和實現(xiàn)順序表和鏈表的比較線性表的應用案例分析與實現(xiàn)Contents線性表的類型定義線性表的抽象數(shù)據(jù)類型定義

：ADTList{數(shù)據(jù)對象

：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}數(shù)據(jù)關系

：R={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}基本操作:InitList(&L);DestroyList(&L);......}

線性表的類型定義線性表的基本操作

：

InitList(&L)

操作結果

：構造一個空的線性表L。

DestroyList(&L)

初始條件

：線性表L已存在。

操作結果

：銷毀線性表L。

ClearList(&L)

初始條件：線性表L已存在。

操作結果

：將L重置為空表。

ListEmpty(L)

初始條件：線性表L已存在。

操作結果

：若L為空表，則返回true，否則返回false。線性表的類型定義線性表的基本操作

：

ListLength(L)

初始條件

：線性表L已存在。

操作結果

：返回L中數(shù)據(jù)元素的個數(shù)。

GetElem(L,i,&e)

初始條件

：線性表L已存在，且1≤i≤ListLength(L)。

操作結果

：用e返回L中第i個數(shù)據(jù)元素的值。

LocateElem(L,e)

初始條件

：線性表L已存在。

操作結果

：返回L中第1個值與e相同的元素在L中的位置。若這樣的數(shù)據(jù)元素

不存在，則返回值為0。

線性表的類型定義線性表的基本操作

：

PriorElem(L,cur_e,&pre_e)

初始條件

：線性表L已存在。

操作結果

：若cur_e是L的數(shù)據(jù)元素，且不是第一個，則用pre_e返回其前驅，否則操

作失敗，pre_e無定義。

NextElem(L,cur_e,&next_e)

初始條件

：線性表L已存在。

操作結果

：若cur_e是L的數(shù)據(jù)元素，且不是最后一個，則用next_e返回其后繼，

否則操作失敗，next_e無定義。線性表的類型定義線性表的基本操作

：

ListInsert(&L,i,e)

初始條件

：線性表L已存在，且1≤i≤ListLength(L)+1。

操作結果

：在L中第i個位置之前插入新的數(shù)據(jù)元素e，L的長度加1。

ListDelete(&L,i)

初始條件

：線性表L已存在且非空，且1≤i≤ListLength(L)。

操作結果：刪除L的第i個數(shù)據(jù)元素，L的長度減1。

TraverseList(L)

初始條件

：線性表L已存在。

操作結果

：對線性表L進行遍歷，在遍歷過程中對L的每個結點訪問一次。

目錄導航2.12.22.32.42.52.62.72.82.9線性表的定義和特點案例引入線性表的類型定義線性表的順序表示和實現(xiàn)線性表的鏈式表示和實現(xiàn)順序表和鏈表的比較線性表的應用案例分析與實現(xiàn)LeetCode算法練習題Contents數(shù)據(jù)的存儲結構邏輯結構存儲結構映射邏輯結構是數(shù)據(jù)關系的抽象描述，存儲結構是這些關系的具體實現(xiàn)。同一邏輯結構可以有不同的存儲結構（順序存儲、鏈式存儲）實現(xiàn)。存儲結構的選擇影響操作效率。存儲結構是邏輯結構在計算機中的映射存儲所有元素存儲數(shù)據(jù)元素間的關系

線性表的順序表示又稱為順序存儲結構或順序映像。線性表的順序表示和實現(xiàn)0102順序存儲定義把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元中的存儲結構。邏輯相鄰，物理相鄰順序存儲方法用一組地址連續(xù)的存儲單元依次存儲線性表的元素，可通過數(shù)組V[n]來實現(xiàn)。是一個典型的線性表的順序存儲結構線性表的順序表示和實現(xiàn)例如，線性表（A,B,C,D,E）的存儲結構：

A

B

C

D

E存儲結構：不是一個線性表的順序存儲結構

A

B

C

D

E依次存儲，地址連續(xù)中間沒有空出存儲單元地址不連續(xù)中間存在空的存儲單元線性表的順序存儲結構是用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。通常，稱這種存儲結構的線性表為順序表（SequentialList）。元素n……..元素i……..元素2元素1LOC(a1)

存儲地址存儲內容線性表的順序表示和實現(xiàn)

一般來說，線性表的第i個數(shù)據(jù)元素ai的存儲位置為：

基地址線性表的順序表示和實現(xiàn)順序表（元素）線性表表長可變（刪除）數(shù)組長度不可動態(tài)定義地址連續(xù)依次存放隨機存取類型相同數(shù)組（元素）用一維數(shù)組表示順序表一維數(shù)組的定義方式：

類型說明符

數(shù)組名[常量表達式]例如：inta[10];說明：常量表達式中可以包含常量和符號常量，不能包含變量，即C語言中不允許對數(shù)組的大小作動態(tài)定義。#defineMAXSIZE100//最大長度typedefstruct

{

ElemType*elem;//指向數(shù)據(jù)元素的基地址

intlength;//線性表的當前長度

}SqList；順序表的類型定義#defineMAXSIZE10000 //圖書表可能達到的最大長度typedef

struct //圖書信息定義{charno[20]; //圖書ISBNcharname[50]; //圖書名字floatprice; //圖書價格}Book;typedef

struct{Book*elem; //存儲空間的基地址

intlength; //圖書表中當前圖書個數(shù)}SqList; //圖書表的順序存儲結構類型為SqList圖書表的順序存儲結構類型定義#defineMAXSIZE100 //多項式可能達到的最大長度typedef

struct //多項式非零項的定義{floatcoef; //系數(shù)intexpn; //指數(shù)}Polynomial;typedef

struct{

Polynomial*elem; //存儲空間的基地址

intlength; //多項式中當前項的個數(shù)}SqList; //多項式的順序存儲結構類型為SqList多項式的順序存儲結構類型定義線性表P

=((p1,e1),(p2,e2),…,(pm,em))補充：C語言的動態(tài)分配函數(shù)（<stdlib.h>）malloc(m)開辟m字節(jié)長度的地址空間，并返回這段空間的首地址sizeof(x)計算變量x的長度。free(p)釋放指針p所指變量的存儲空間，即徹底刪除一個變量補充：數(shù)組定義typedefstruct{ElemType*elem;intlength;}SqList//順序表類型typedefstruct{ElemTypeelem[MAXSIZE];intlength;}SqList//順序表類型數(shù)組靜態(tài)分配數(shù)組動態(tài)分配SqListL;L.elem=(ElemType*)malloc(sizeof(ElemType)*MAXSIZE);new類型名T（初值列表）功能：申請用于存放T類型對象的內存空間，并依初值列表賦以初值結果值：成功：T類型的指針，指向新分配的內存失?。?（NULL）int*p=newint;

或int*p=newint(10);補充：C++的動態(tài)存儲分配delete指針p功能：

釋放指針p所指向的內存，p必須是new操作的返回值deletep;函數(shù)調用時傳送給形參表的實參必須與形參在類型、個數(shù)、順序上保持一致。補充：C++中的參數(shù)傳遞參數(shù)傳遞有兩種方式傳值方式（參數(shù)為整型、實型、字符型等）傳地址參數(shù)為指針變量參數(shù)為引用類型參數(shù)為數(shù)組名傳值方式把實參的值傳送給函數(shù)局部工作區(qū)相應的副本中，函數(shù)使用這個副本執(zhí)行必要的功能。函數(shù)修改的是副本的值，實參的值不變。voidmain(){ floata,b;

cin>>a>>b; swap(a,b);

cout<<a<<endl<<b<<endl;}#include<iostream.h>voidswap(floatm,floatn){ floattemp; temp=m; m=n; n=temp;}傳地址方式－－指針變量作參數(shù)voidmain(){ floata,b,*p1,*p2;

cin>>a>>b; p1=&a;p2=&b; swap(p1,p2);

cout<<a<<endl<<b<<endl;}#include<iostream.h>voidswap(float*m,float*n){ floatt; t=*m; *m=*n; *n=t;}形參變化影響實參。傳地址方式－－指針變量作參數(shù)voidmain(){ floata,b,*p1,*p2;

cin>>a>>b;

p1=&a;p2=&b; swap(p1,p2);

cout<<a<<endl<<b<<endl;}#include<iostream.h>voidswap(float*m,float*n){ float*t; t=m; m=n; n=t;}形參變化不影響實參？？傳地址方式－－引用類型作參數(shù)引用：它用來給一個對象提供一個替代的名字。#include<iostream.h>voidmain(){ inti=5; int&j=i;

i=7;

cout<<"i="<<i<<"j="<<j;}什么是引用？？？j是一個引用類型,代表i的一個替代名。i值改變時,j值也跟著改變，所以會輸出。i=7j=7傳地址方式－－引用類型作參數(shù)voidmain(){floata,b;

cin>>a>>b;swap(a,b);

cout<<a<<endl<<b<<endl;}#include<iostream.h>voidswap(float＆m,float＆n){ floattemp; temp=m; m=n; n=temp;}引用類型作形參的三點說明傳遞引用給函數(shù)與傳遞指針的效果是一樣的，形參變化實參也發(fā)生變化。引用類型作形參，在內存中并沒有產生實參的副本，它直接對實參操作；而一般變量作參數(shù)，形參與實參就占用不同的存儲單元，所以形參變量的值是實參變量的副本。因此，當參數(shù)傳遞的數(shù)據(jù)量較大時，用引用比用一般變量傳遞參數(shù)的時間和空間效率都好。1指針參數(shù)雖然也能達到與使用引用的效果，但在被調函數(shù)中需要重復使用“*指針變量名”的形式進行運算，這很容易產生錯誤且程序的閱讀性較差；另一方面，在主調函數(shù)的調用點處，必須用變量的地址作為實參。23傳地址方式－－數(shù)組名作參數(shù)#include<iostream.h>voidsub(char);voidmain（void）{chara[10]=“hello”;sub(a);

cout<<a<<endl;}voidsub(charb[]){b[]=“world”;}傳遞的是數(shù)組的首地址，對形參數(shù)組所做的任何改變都將反映到實參數(shù)組中。#include<iostream.h>#defineN10intmax(inta[]);voidmain(){ inta[10]; inti,m; for(i=0;i<N;i++)

cin>>a[i]; m=max(a);

cout<<"themaxnumberis:"<<m;}用數(shù)組作函數(shù)的參數(shù)，求10個整數(shù)的最大數(shù)intmax(intb[]){inti,n;n=b[0];for(i=1;i<N;i++) if(n<b[i])n=b[i];returnn;}練習用數(shù)組作為函數(shù)的參數(shù)，將數(shù)組中n個整數(shù)按相反的順序存放，要求輸入和輸出在主函數(shù)中完成voidmain(){ inta[10],i; for(i=0;i<N;i++)

cin>>a[i]; sub(a); for(i=0;i<N;i++)

cout<<a[i];}#include<iostream.h>#defineN10voidsub(intb[]){ inti,j,temp,m; m=N/2; for(i=0;i<m;i++){j=N-1-i;temp=b[i]; b[i]=b[j];b[j]=temp; } return;}線性表的重要基本操作初始化基本操作查找插入取值刪除15432操作算法中用到的預定義常量和類型//函數(shù)結構狀態(tài)代碼#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2//Status是函數(shù)的類型，其值是函數(shù)結果狀態(tài)代碼typedefintStatus；typedefcharElemType；初始化線性表L（參數(shù)用引用）StatusInitList_Sq(SqList&L)

//構造一個空的順序表L{

L.elem=newElemType[MAXSIZE];//為順序表分配空間

if(!L.elem)exit(OVERFLOW);//存儲分配失敗

L.length=0; //空表長度為0returnOK;}StatusInitList_Sq(SqList*L)//構造一個空的順序表L{ L->elem=newElemType[MAXSIZE];//為順序表分配空間

if(!L->elem)exit(OVERFLOW);//存儲分配失敗

L->length=0; //空表長度為0returnOK;}初始化線性表L（參數(shù)用指針）補充：幾個簡單基本操作的算法實現(xiàn)voidDestroyList(SqList&L){if(L.elem)delete[]L.elem;//釋放存儲空間}voidClearList(SqList&L){

L.length=0;//將線性表的長度置為0}

銷毀線性表L清空線性表L補充：幾個簡單基本操作的算法實現(xiàn)intGetLength(SqListL){return(L.length);}intIsEmpty(SqListL){if(L.length==0)return1;elsereturn0;}求線性表L的長度判斷線性表L是否為空線性表的重要基本操作初始化基本操作查找插入取值刪除15432intGetElem(SqList

L,int

i,ElemType&e){if(i<1||i>L.length)returnERROR;//判斷i值是否合理，若不合理，返回ERROR

e=L.elem[i-1];//第i-1的單元存儲著第i個數(shù)據(jù)

returnOK;}取值（根據(jù)位置i獲取相應位置數(shù)據(jù)元素的內容）隨機存取獲取線性表L中的某個數(shù)據(jù)元素的內容時間復雜度為O(1)查找（根據(jù)指定數(shù)據(jù)獲取數(shù)據(jù)所在的位置）253457164809012345data查找

16i253457164809i253457164809i253457164809i查找成功012344查找502534571648datai2534571648i2534571648i2534571648i2534571648i查找失敗查找（根據(jù)指定數(shù)據(jù)獲取數(shù)據(jù)所在的位置）查找算法時間效率分析？？？在線性表L中查找值為e的數(shù)據(jù)元素intLocateELem(SqList

L,ElemTypee){ for(i=0;i<L.length;i++) if(L.elem[i]==e)returni+1;//查找成功，返回序號i+1 return0;//查找失敗，返回0}查找（根據(jù)指定數(shù)據(jù)獲取數(shù)據(jù)所在的位置）平均時間復雜度為O(n)平均查找長度ASL在長度為n的線性表中，查找成功時的平均查找長度為：pi為找到第i個記錄所需要的比較次數(shù)Ci為第i個記錄被查找的概率假設每個元素的查找概率相等：則：為確定元素在順序表中的位置，需和給定值進行比較的數(shù)據(jù)元素個數(shù)的期望值稱為在查找成功時的平均查找長度（AverageSearchLength，ASL)。12345678999插入251247893614插入（插在第i

個結點之前）0+1+2+……n插第4個結點之前，移動6－4+1

次插在第i

個結點之前，移動n-i+1

次25124789361425124789361425124789361425124799893614【算法步驟】01判斷插入位置i

是否合法。02判斷順序表的存儲空間是否已滿。03將第n至第i

位的元素依次向后移動一個位置，空出第i個位置。04將要插入的新元素e放入第i個位置。05表長加1，插入成功返回OK。StatusListInsert_Sq(SqList&L,int

i,ElemTypee){if(i<1||i>L.length+1)returnERROR; //i值不合法

if(L.length==MAXSIZE)returnERROR;//當前存儲空間已滿

for(j=L.length-1;j>=i-1;j--)

L.elem[j+1]=L.elem[j];//插入位置及之后的元素后移

L.elem[i-1]=e;//將新元素e放入第i個位置++L.length; //表長增1returnOK;}【算法描述】在線性表L中第i個數(shù)據(jù)元素之前插入數(shù)據(jù)元素e若插入在尾結點之后，則根本無需移動（特別快）；若元素全部后移（特別慢）；若要考慮在各種位置插入（共n+1種可能）的平均移動次數(shù)，該如何計算？AMN算法時間主要耗費在移動元素的操作上。【算法分析】平均時間復雜度為O(n)123456789刪除2512473614刪除（刪除第i

個結點）

0+1+2+…n-1刪除第4個結點，移動6－4

次刪除第i

個結點，移動n-i

次25124789361425124736142512473614【算法步驟】01判斷刪除位置i

是否合法（合法值為1≤i≤n）。02將欲刪除的元素保留在e中。03將第i+1至第n位的元素依次向前移動一個位置。04表長減1，刪除成功返回OK。StatusListDelete_Sq(SqList&L,int

i){if((i<1)||(i>L.length))returnERROR; //i值不合法

for(j=i;j<=L.length-1;j++)

L.elem[j-1]=L.elem[j];//被刪除元素之后的元素前移

--L.length; //表長減1returnOK;}【算法描述】將線性表L中第i個數(shù)據(jù)元素刪除若刪除尾結點，則根本無需移動（特別快）；若刪除首結點，則表中n-1個元素全部前移（特別慢）；若要考慮在各種位置刪除（共n種可能）的平均移動次數(shù)，該如何計算？算法時間主要耗費在移動元素的操作上【算法分析】平均時間復雜度為O(n)顯然，順序表的空間復雜度S(n)=O(1)（沒有占用輔助空間）。查找、插入、刪除算法的平均時間復雜度為：O(n)利用數(shù)據(jù)元素的存儲位置表示線性表中相鄰數(shù)據(jù)元素之間的前后關系，即線性表的邏輯結構與存儲結構一致。順序表（順序存儲結構）的特點在訪問線性表時，可以快速地計算出任何一個數(shù)據(jù)元素的存儲地址。因此可以粗略地認為，訪問每個元素所花時間相等。

這種存取元素的方法被稱為隨機存取法。01OPTION02OPTION順序表（順序存儲結構）的特點每個結點只放數(shù)據(jù)元素每個結點除存放數(shù)據(jù)元素外，還存儲指向下一結點的指針存儲密度存儲密度=結點占用的空間總量結點數(shù)據(jù)本身占用的空間

存儲密度越大，存儲空間的利用率就越高。順序表的存儲密度為1，而鏈表的存儲密度小于1。如果每個元素數(shù)據(jù)域占據(jù)的空間較小，則指針的結構性開銷就占用了整個結點的大部分空間，這樣存儲密度較小。鏈表的優(yōu)缺點

時間：可以隨機存取表中任一元素?？臻g：存儲密度大（結點本身所占存儲量/結點結構所占存儲量）。優(yōu)點：時間：在插入、刪除某一元素時，需要移動大量元素?？臻g：浪費存儲空間，屬于靜態(tài)存儲形式，數(shù)據(jù)元素的個數(shù)不能

自由擴充。缺點：鏈表為克服這一缺點目錄導航2.12.22.32.42.52.62.72.82.9線性表的定義和特點案例引入線性表的類型定義線性表的順序表示和實現(xiàn)線性表的鏈式表示和實現(xiàn)順序表和鏈表的比較線性表的應用案例分析與實現(xiàn)LeetCode算法練習題Contents例：線性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)存儲結構邏輯狀態(tài)線性表的鏈式表示和實現(xiàn)NULL頭指針L線性表的鏈式表示和實現(xiàn)鏈式存儲結構結點在存儲器中的位置是任意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。線性表的鏈式表示又稱為非順序映像或鏈式映像。如何實現(xiàn)？通過指針來實現(xiàn)單鏈表的存儲映像free(a)可利用存儲空間a0a2a1a3

freefirst(b)經過一段運行后的單鏈表結構線性表的鏈式表示和實現(xiàn)例：畫出26個英文字母表的鏈式存儲結構鏈式存儲結構：邏輯結構：（a,b,…,y,z）aheadb/\z……線性表的鏈式表示和實現(xiàn)例：畫出26個英文字母表的鏈式存儲結構線性表的鏈式表示和實現(xiàn)各結點由兩個域組成：數(shù)據(jù)域：存儲元素數(shù)值數(shù)據(jù)指針域：存儲直接后繼結點的存儲位置指針數(shù)據(jù)與鏈式存儲有關的術語1.結點：數(shù)據(jù)元素的存儲映像，由數(shù)據(jù)域和指針域兩部分組成。2.鏈表：

n個結點由指針鏈組成一個鏈表，是線性表的鏈式存儲映像，稱為線性表的鏈式存儲結構。數(shù)據(jù)域指針域與鏈式存儲有關的術語3.單鏈表、雙向鏈表、循環(huán)鏈表

結點只有一個指針域的鏈表，稱為單鏈表或線性鏈表。

有兩個指針域的鏈表，稱為雙向鏈表。首尾相接的鏈表稱為循環(huán)鏈表。與鏈式存儲有關的術語4.頭指針、頭結點和首元結點頭指針頭結點首元結點a1heada2…infoan^頭指針是指向鏈表中第一個結點的指針。首元結點是指鏈表中存儲第一個數(shù)據(jù)元素a1的結點。頭結點是在鏈表的首元結點之前附設的一個結點，數(shù)據(jù)域內只放空表標志和表長等信息。上例鏈表的邏輯結構示意圖有以下兩種形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH區(qū)別：①

無頭結點②有頭結點與鏈式存儲有關的術語討論1.如何表示空表？有頭結點時，當頭結點的指針域為空時表示空表。非空表 空表0ana0headhead^表頭結點第一個結點與鏈式存儲有關的術語討論2.在鏈表中設置頭結點有什么好處？1.便于首元結點的處理首元結點的地址保存在頭結點的指針域中,所以在鏈表的第一個位置上的操作和其它位置一致，無須進行特殊處理;2.便于空表和非空表的統(tǒng)一處理無論鏈表是否為空，頭指針都是指向頭結點的非空指針，因此空表和非空表的處理也就統(tǒng)一了。與鏈式存儲有關的術語討論3.頭結點的數(shù)據(jù)域內裝的是什么？

頭結點的數(shù)據(jù)域可以為空，也可存放線性表長度等附加信息，但此結點不能計入鏈表長度值。頭結點的數(shù)據(jù)域H與鏈式存儲有關的術語結點在存儲器中的位置是任意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。鏈表（鏈式存儲結構）的特點訪問時只能通過頭指針進入鏈表，并通過每個結點的指針域向后掃描其余結點，所以尋找第一個結點和最后一個結點所花費的時間不等。

這種存取元素的方法被稱為順序存取法。01OPTION02OPTION鏈表的優(yōu)缺點

時間：插入、刪除等操作不必移動數(shù)據(jù)，只需修改鏈接指針，修改

效率較高?？臻g：數(shù)據(jù)元素的個數(shù)可以自由擴充。優(yōu)點：時間：存取效率不高，必須采用順序存取，即存取數(shù)據(jù)元素時，只

能按鏈表的順序進行訪問（順藤摸瓜）。空間：存儲密度小。缺點：練習1.鏈表的每個結點中都恰好包含一個指針。2.順序表結構適宜于進行順序存取，而鏈表適宜于進行隨機存取。3.順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。4.線性表若采用鏈式存儲時，結點之間和結點內部的存儲空間都是可以不連續(xù)的。5.線性表的每個結點只能是一個簡單類型，而鏈表的每個結點可以是一個復雜類型?！?/p>

單鏈表的定義和實現(xiàn)非空表空表單鏈表是由表頭唯一確定，因此單鏈表可以用頭指針的

名字來命名。若頭指針名是L，則把鏈表稱為表L。typedefstructLNode{

ElemTypedata;//數(shù)據(jù)域

struct

LNode*next;//指針域}LNode,*LinkList;//*LinkList為LNode類型的指針單鏈表的存儲結構定義LNode*pLinkList

pLNode*p注意區(qū)分指針變量和結點變量兩個不同的概念若p->data=ai,則p->next->data=ai+1單鏈表的存儲結構定義指針變量p：表示結點地址結點變量*p：表示一個結點單鏈表基本操作的實現(xiàn)初始化基本操作查找插入取值刪除15432【算法步驟】【算法描述】初始化(構造一個空表)StatusInitList_L(LinkList&L){

L=newLNode;//生成新結點作為頭結點，用頭指針L指向頭結點

L->next=NULL;

//頭結點的指針域置空

returnOK;}（1）生成新結點作頭結點，用頭指針L指向頭結點。（2）頭結點的指針域置空。StatusDestroyList_L(LinkList&L){

LinkListp;while(L){p=L;L=L->next;deletep;}returnOK;}補充：幾個簡單基本操作的算法實現(xiàn)銷毀StatusClearList(LinkList&L){

//將L重置為空表

LinkList

p,q;p=L->next;//p指向首元結點

while(p)//沒到表尾

{q=p->next;deletep;p=q;}L->next=NULL;//頭結點指針域為空

returnOK;}補充：幾個簡單基本操作的算法實現(xiàn)清空pLa1a2…...^pi01p2pn==NULLan求表長p=L->next;i=0;while(p){i++;p=p->next;}

補充：幾個簡單基本操作的算法實現(xiàn)“數(shù)”結點：指針p依次指向各個結點；從第一個元素開始“數(shù)”；一直“數(shù)”到最后一個結點。求表長intListLength_L(LinkListL){//返回L中數(shù)據(jù)元素個數(shù)

LinkListp;

p=L->next;//p指向第一個結點

i=0;

while(p){//遍歷單鏈表,統(tǒng)計結點數(shù)

i++;

p=p->next;}

returni;}“數(shù)”結點：指針p依次指向各個結點；從第一個元素開始“數(shù)”；一直“數(shù)”到最后一個結點。補充：幾個簡單基本操作的算法實現(xiàn)判斷表是否為空int

ListEmpty(LinkListL){ //若L為空表，則返回1，否則返回0

if(L->next)

//非空

return0;elsereturn1;}補充：幾個簡單基本操作的算法實現(xiàn)單鏈表基本操作的實現(xiàn)初始化基本操作查找插入取值刪除15432思考：順序表里如何找到第i個元素？鏈表的查找：要從鏈表的頭指針出發(fā)，順著鏈域next逐個結點往下搜索，直至搜索到第i個結點為止。因此，鏈表不是隨機存取結構。取值（根據(jù)位置i獲取相應位置數(shù)據(jù)元素的內容）L211830754256∧ppj1231i=3i=156p7例：分別取出表中i=3和i=15的元素(1)從第1個結點（L->next）順鏈掃描，用指針p指向當前掃描到的結點，p初值p

=

L->next。(2)j做計數(shù)器，累計當前掃描過的結點數(shù)，

j初值為1。(3)當p指向掃描到的下一結點時，計數(shù)器

j加1。(4)當j

=

i時，p所指的結點就是要找的第i個結點?！舅惴ú襟E】取值（根據(jù)位置i獲取相應位置數(shù)據(jù)元素的內容）ppStatusGetElem_L(LinkList

L,int

i,ElemType&e){p=L->next;j=1;//初始化

while(p&&j<i){ //向后掃描，直到p指向第i個元素或p為空

p=p->next;++j;}if(!p||j>i)returnERROR;//第i個元素不存在

e=p->data;//取第i個元素

returnOK;}//GetElem_L

取值（根據(jù)位置i獲取相應位置數(shù)據(jù)元素的內容）獲取線性表L中的某個數(shù)據(jù)元素的內容平均時間復雜度為O(n)查找（根據(jù)指定數(shù)據(jù)獲取數(shù)據(jù)所在的位置）L211830753056∧j1x=30p2p3找到，返回ix=51p1p6p7未找到，返回0(1)從第一個結點起，依次和e相比較。(2)如果找到一個其值與e相等的數(shù)據(jù)元素，則返回其在鏈表中的“位置”或地址。(3)如果查遍整個鏈表都沒有找到其值和e相等的元素，則返回0或“NULL”。【算法步驟】LNode*LocateELem_L(LinkListL，Elemtypee){//返回L中值為e的數(shù)據(jù)元素的地址，查找失敗返回NULLp=L->next;while(p&&p->data!=e)p=p->next; returnp; }【算法描述】在線性表L中查找值為e的數(shù)據(jù)元素平均時間復雜度為O(n)intLocateELem_L(LinkListL，Elemtypee){//返回L中值為e的數(shù)據(jù)元素的位置序號，查找失敗返回0

p=L->next;j=1;while(p&&p->data!=e){p=p->next;j++;} if(p)returnj;elsereturn0;}【算法描述】在線性表L中查找值為e的數(shù)據(jù)元素平均時間復雜度為O(n)將值為e的新結點插入到表的第i個結點的位置上，即插入到ai-1與ai之間s->next=p->next;p->next=s思考：步驟1和2能互換么？插入（插在第i

個結點之前）LNode*LocateELem_L(LinkListL，Elemtypee){//返回L中值為e的數(shù)據(jù)元素的地址，查找失敗返回NULLp=L->next;while(p&&p->data!=e)p=p->next; returnp; }【算法描述】在線性表L中查找值為e的數(shù)據(jù)元素找到ai-1存儲位置p。01OPTION02OPTION03OPTION新結點*s的指針域指向結點ai。令結點*p的指針域指向新結點*s。將新結點*s的數(shù)據(jù)域置為x。生成一個新結點*s。04OPTION05OPTION【算法步驟】StatusListInsert_L(LinkList&L,int

i,ElemTypee){p=L;j=0;

while(p&&j<i?1){p=p->next;++j;} //尋找第i?1個結點

if(!p||j>i?1)returnERROR; //i大于表長

+

1或者小于1s=newLNode; //生成新結點ss->data=e; //將結點s的數(shù)據(jù)域置為e

s->next=p->next; //將結點s插入L中

p->next=s;returnOK;}//ListInsert_L

【算法描述】在L中第i個元素之前插入數(shù)據(jù)元素e（1）找到ai-1存儲位置p。（2）保存要刪除的結點的值。（3）令p-＞next指向ai的直接后繼結點。（4）釋放結點ai的空間。刪除（刪除第i

個結點）將表的第i個結點刪去步驟：p->next=p->next->next???

ai-1ai-1aiaiai+1ai+1pq刪除前刪除后刪除（刪除第i

個結點）刪除（刪除第i

個結點）找到ai-1存儲位置p。01OPTION02OPTION保存要刪除的結點的值。03OPTION令p-＞next指向ai的直接后繼結點。04OPTION釋放結點ai的空間。【算法步驟】

StatusListDelete_L(LinkList&L,int

i,ElemType&e){p=L;j=0;while(p->next&&j<i-1){//尋找第i-1個結點，并令p指向其前驅

p=p->next;++j;}if(!(p->next)||j>i-1)returnERROR;//刪除位置不合理

q=p->next;//臨時保存被刪結點的地址以備釋放

p->next=q->next; //改變刪除結點前驅結點的指針域

e=q->data; //保存刪除結點的數(shù)據(jù)域

deleteq; //釋放刪除結點的空間

returnOK;}//ListDelete_L

【算法描述】將線性表L中第i個數(shù)據(jù)元素刪除但是，如果要在單鏈表中進行前插或刪除操作，由于要從頭查找前驅結點，所耗時間復雜度為O(n)

。鏈表的運算時間效率分析1.查找:

因線性鏈表只能順序存取，即在查找時要從頭指針找起，查找的時間復雜度為

O(n)。2.插入和刪除:

因線性鏈表不需要移動元素，只要修改指針，一般情況下時間復雜度為

O(1)。從一個空表開始，重復讀入數(shù)據(jù)：生成新結點；將讀入數(shù)據(jù)存放到新結點的數(shù)據(jù)域中；將該新結點插入到鏈表的前端。單鏈表的建立（前插法）p->data=anp->data=an-1L->next=pp->next=L->next單鏈表的建立（前插法）voidCreateList_F(LinkList&L,intn){L=newLNode;L->next=NULL;//先建立一個帶頭結點的單鏈表

for(i=n;i>0;--i){p=newLNode;//生成新結點

cin>>p->data;//輸入元素值

p->next=L->next;L->next=p; //插入到表頭

}}//CreateList_F

【算法描述】逆位序輸入n個元素的值，建立帶表頭結點的單鏈表L時間復雜度為O(n)從空表L開始，將新結點逐個插入到鏈表的尾部，尾指針r指向鏈表的尾結點。初始時，r同L均指向頭結點。每讀入一個數(shù)據(jù)元素則申請一個新結點，將新結點插入到尾結點后，r指向新結點。單鏈表的建立（尾插法）voidCreateList_L(LinkList&L,intn){L=newLNode;L->next=NULL;

r=L; //尾指針r指向頭結點

for(i=0;i<n;++i){p=newLNode;

//生成新結點

cin>>p->data; //輸入元素值

p->next=NULL;r->next=p;//插入到表尾

r=p; //r指向新的尾結點

}}//CreateList_L

【算法描述】正位序輸入n個元素的值，建立帶表頭結點的單鏈表L時間復雜度為O(n)【2024年第1題】一個帶頭結點的鏈表L，指針p指向鏈表L中間的某個結點（非首尾結點）。下面的代碼功能是（

）。q=p->next;p->next=q->next;q->next=L->next;L->next=q;將p指向結點移到q指向結點后將q指向結點移到p指向結點后C.將p指向結點插入頭結點后D.將q指向結點插入頭結點后408真題練習D循環(huán)鏈表L->next=L(a)非空單循環(huán)鏈表L(b)空表L說明從循環(huán)鏈表中的任何一個結點的位置都可以找到其他所有結點，而單鏈表做不到。循環(huán)條件：p!=NULLp!=Lp->next!=NULLp->next!=L循環(huán)鏈表中沒有明顯的尾端如何避免死循環(huán)?循環(huán)鏈表說明對循環(huán)鏈表，有時不給出頭指針，而給出尾指針可以更方便的找到第一個和最后一個結點。開始結點：rear->next->next終端結點：rear如何查找開始結點和終端結點？循環(huán)鏈表rear

a1

ai-1

an

ai循環(huán)鏈表頭指針表示單循環(huán)鏈表找a1的時間復雜度：O(1)找an的時間復雜度：O(n)不方便尾指針表示單循環(huán)鏈表a1的存儲位置是：R->next->nextan的存儲位置是：R時間復雜度：O(1)注意：表的操作通常在表的收尾位置上進行RTaa1anTbb1bn循環(huán)鏈表的合并a1anb1bn①p②③④TaTb循環(huán)鏈表a1anb1bn①p②③④TaTbLinkListConnect(LinkList

Ta,LinkListTb){//假設Ta、Tb都是非空的單循環(huán)鏈表//①p存表頭結點//②Tb表頭連結Ta表尾//③釋放Tb表頭結點//④修改指針returnTb;}p=Ta->next;Ta->next=Tb->next->next;deleteTb->next;

Tb->next=p;

循環(huán)鏈表著名猶太歷史學家

Josephus約瑟夫問題在羅馬人占領喬塔帕特后39個猶太人與Josephus及他的朋友躲到一個洞中39個猶太人決定寧愿死也不要被敵人抓到，于是決定了一個自殺方式41個人排成一個圓圈，由第1個人開始報數(shù)，每報數(shù)到第3人該人就必須自殺，然后再由下一個重新報數(shù)，直到所有人都自殺身亡為止然而Josephus和他的朋友并不想遵從，Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡游戲例如n=8m=3約瑟夫問題約瑟夫問題的解法voidJosephus(intn,intm){Firster();//檢驗指針指向第一個結點

for(inti=0;i<n-1;i++){

//執(zhí)行n-1次

for(intj=0;j<m-1;j++)Next();

//循環(huán)m次使current指向被刪除結點

cout<<“出列的人是”<<GetElem_L()<<endl;

//出列人員的數(shù)據(jù)ListDelete();

//刪去每一趟的第m結點

}約瑟夫問題雙向鏈表為什么要討論雙向鏈表?p單鏈表：單鏈表的結點有指示直接后繼的指針域找后繼結點方便即：查找某結點的后繼結點的執(zhí)行時間為

O(1)雙向鏈表：在單鏈表的每個結點里面再增加一個指向其直接前驅的指針域prior，使得鏈表中形成兩個方向不同的鏈。沒有指示之間前驅的指針域找前驅結點難，必須從表頭指針出發(fā)即：查找某結點的前驅結點的執(zhí)行時間為

O(n)typedefstruct

DuLNode{

ElemTypedata;

struct

DuLNode*prior;

struct

DuLNode*next;}DuLNode,*DuLinkList雙向鏈表(a)空雙向循環(huán)鏈表(b)雙向循環(huán)鏈表d->next->prior=d->prior->next=dL->next=L雙向鏈表雙向鏈表的插入雙向鏈表的插入abx......1ps1.s->prior=p->prior;雙向鏈表的插入1.s->prior=p->prior;2.p->prior->next=s;雙向鏈表的插入1.s->prior=p->prior;abx......12ps2.p->prior->next=s;

3.

s->next=p;雙向鏈表的插入1.s->prior=p->prior;2.p->prior->next=s;

3.

s->next=p;abx......1234ps4.p->prior=s;StatusListInsert_DuL(DuLinkList&L,int

i,ElemTypee){if(!(p=GetElemP_DuL(L,i)))returnERROR;s=newDuLNode;s->data=e;

s->prior=p->prior;//將結點*s插入L中p->prior->next=s;//結點p的前驅結點的后繼指向結點*ss->next=p;//結點*s的后繼指向結點pp->prior=s;//結點p的前驅指向結點*sreturnOK;}雙向鏈表的插入雙向鏈表的刪除1.p->prior->next=p->next;雙向鏈表的刪除1.p->prior->next=p->next;2.p->next->prior=p->prior;StatusListDelete_DuL(DuLinkList&L,int

i,ElemType&e){if(!(p=GetElemP_DuL(L,i)))returnERROR;e=p->data;

p->prior->next=p->next;p->next->prior=p->prior;deletep;returnOK;}雙向鏈表的刪除單鏈表、循環(huán)鏈表和雙向鏈表的時間效率比較

操作名稱

鏈表名稱

查找首元結點查找表尾結點查找結點*p的前驅結點帶頭結點的單鏈表LL->next時間復雜度O(1)從L->next依次向后遍歷時間復雜度O(1)通過p->next無法找到其前驅帶頭結點僅設頭指針L的循環(huán)單鏈表L->next時間復雜度O(1)從L->next依次向后遍歷時間復雜度O(n)通過p->next可以找到其前驅時間復雜度O(n)帶頭結點僅設尾指針R的循環(huán)單鏈表R->next->next時間復雜度O(1)R時間復雜度O(1)通過p->next可以找到其前驅時間復雜度O(n)帶頭結點的雙向循環(huán)鏈表LL->next時間復雜度O(1)L->prior時間復雜度O(1)p->prior時間復雜度O(1)目錄導航2.12.22.32.42.52.62.72.82.9線性表的定義和特點案例引入線性表的類型定義線性表的順序表示和實現(xiàn)線性表的鏈式表示和實現(xiàn)順序表和鏈表的比較線性表的應用案例分析與實現(xiàn)LeetCode算法練習題Contents順序表和鏈表的比較

存儲結構

比較項目順序表鏈表空間存儲空間預先分配，會出現(xiàn)空間閑置或溢出現(xiàn)象