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

8/8/2023

1第2章表

學(xué)習(xí)要點:理解表是由同一類型的元素組成的有限序列的概念。熟悉定義在抽象數(shù)據(jù)類型表上的基本運算。掌握實現(xiàn)抽象數(shù)據(jù)類型的一般步驟。掌握用數(shù)組實現(xiàn)表的步驟和方法。掌握用指針實現(xiàn)表的步驟和方法。掌握用間接尋址技術(shù)實現(xiàn)表的步驟和方法。掌握用游標(biāo)實現(xiàn)表的步驟和方法。掌握單循環(huán)鏈表的實現(xiàn)方法和步驟。掌握雙鏈表的實現(xiàn)方法和步驟。熟悉表的搜索游標(biāo)的概念和實現(xiàn)方法。7/29/20231第2章表學(xué)習(xí)要點:學(xué)生成績登記表姓名英語數(shù)據(jù)結(jié)構(gòu)高數(shù)學(xué)號丁一9678870101李二8790780102張三6786860103孫紅6981960104王冬8774660105學(xué)生成績登記表姓名英語數(shù)據(jù)結(jié)構(gòu)高數(shù)學(xué)號丁一967887線性結(jié)構(gòu)的特點法學(xué)院8523101

國貿(mào)學(xué)院8522105工商學(xué)院8523150計算機學(xué)院8521088會計學(xué)院8525789統(tǒng)計學(xué)院8528136……外語學(xué)院8523026

例：“第一個”數(shù)據(jù)元素“最后一個”數(shù)據(jù)元素直接前驅(qū)直接后繼存在唯一一個被稱作“第一個”的數(shù)據(jù)元素；存在唯一一個被稱作“最后一個”的數(shù)據(jù)元素；除第一個之外的數(shù)據(jù)元素均只有一個直接前驅(qū)；除最后一個之外的數(shù)據(jù)元素均只有一個直接后繼。數(shù)據(jù)元素的非空有限集線性結(jié)構(gòu)的特點法學(xué)院85231018/8/2023

42.1ADT表(List)2.1.1ADT表的數(shù)據(jù)模型

表是由n(n0)個同一類型(通常記為datatype類型)的元素(結(jié)點)a(1)，a(2)，…，a(n)組成的有限序列。1.有限性：線性表中數(shù)據(jù)元素的個數(shù)是有窮的。2.相同性：線性表中數(shù)據(jù)元素的類型是同一的。3.順序性：線性表中相鄰的數(shù)據(jù)元素ai-1和ai之間存在序偶關(guān)系(ai-1,ai)，即ai-1是ai的前驅(qū)，ai是ai-1的后繼；a1

無前驅(qū)，an無后繼，其它每個元素有且僅有一個前驅(qū)和一個后繼。

7/29/202342.1ADT表(List)2.1.12.1.2有關(guān)的概念與術(shù)語表的長度（Length）：表的元素的個數(shù)即數(shù)據(jù)模型中的n?？眨‥mpty）表：n=0的表。表中元素(結(jié)點)的位置（Position）：當(dāng)n1時，說k是表中第

k個元素a(k)的位置，k=1，2，…，n。表中元素(結(jié)點)的前驅(qū)：當(dāng)n>1時，說a(k)是a(k+1)的前驅(qū)

(k=1，2，…，n-1)。表中元素(結(jié)點)的后繼：當(dāng)n>1時，說a(k+1)是a(k)的后繼(k=1，2，…，n-1)。2.1.2有關(guān)的概念與術(shù)語非空表記為：L＝（a1,a2,…,ai-1,ai,…,an)a1a3a4ana2非空表記為：L＝（a1,a2,…,ai-1,ai8/8/2023

72.1ADT表（List）2.1.3ADT表的邏輯特征非空表有且僅有一個開始元素a(1)，它沒有前驅(qū)。當(dāng)n>1時，它有一個后繼a(2)。非空表有且僅有一個結(jié)束元素a(n)，它沒有后繼。當(dāng)n>1時，它有一個前驅(qū)a(n-1)。當(dāng)n>2時，表的其余元素a(k)(2kn-1)都有一個前驅(qū)和一個后繼。表中元素按其位置的順序關(guān)系是它們之間的邏輯關(guān)系。7/29/202372.1ADT表（List）2.1.3線性表的基本操作： （1）初始化（置空表）—可由構(gòu)造函數(shù)實現(xiàn) （2）求表長（Length）

（3）查找或定位（Find） （4）插入（Insert）

（5）刪除（Remove） （6）排序（Sort）

（7）判空（IsEmpty）線性表的抽象數(shù)據(jù)類型線性表的基本操作：線性表的抽象數(shù)據(jù)類型8/8/2023

92.1ADT表（List）2.1.4ADT表上定義的常用的基本運算(1)Empty():(2)Size():(3)Locate(x):(4)Retrieve(k,x):獲取表中位置k處的元素，存入x中(5)Insert(k,x):在表的位置k之后插入元素x(6)Erase(k,x):從表中刪除位置k處的元素，存入x中(7)PrintList():注意：運算名稱的取法、需要的形式參數(shù)的個數(shù)、各參數(shù)的取名和含義、具體運算的約定、各參數(shù)取值（特別是邊界值）和返回值的約定、各參數(shù)取值和返回值的類型的確定。

7/29/202392.1ADT表（List）2.1.4進一步說明:（1）線性表的基本操作根據(jù)實際應(yīng)用是而定；（2）復(fù)雜的操作可以通過基本操作的組合來實現(xiàn)；（3）對不同的應(yīng)用，操作的接口可能不同。進一步說明:線性表的抽象數(shù)據(jù)類型應(yīng)用擴大線性表LA，將存在于線性表LB中而不存在于線性表LA中的數(shù)據(jù)元素插入到線性表LA中去。線性表的抽象數(shù)據(jù)類型應(yīng)用擴大線性表LA，將存在于線性表思路：

1．從LB中取出一個數(shù)據(jù)元素；2．依值在LA中進行查詢；3．若不存在，則插入之。重復(fù)上述三步直至LB中的數(shù)據(jù)元素取完為止。其中的每一步能否利用抽象數(shù)據(jù)類型線性表中定義的基本操作來完成呢？思路：其中的每一步能否利用抽象數(shù)據(jù)類型線性表中定義

在實際的程序設(shè)計中要引用線性表的基本操作，必須先實現(xiàn)線性表類型。確定存儲結(jié)構(gòu)實現(xiàn)基本操作在實際的程序設(shè)計中要引用線性表的基本操作，確實在計算機中用一組地址連續(xù)的存儲單元依次存儲線性表的各個數(shù)據(jù)元素，稱作線性表的順序存儲結(jié)構(gòu)或順序映象。用這種方法存儲的線性表稱作順序表。在計算機中用一組地址連續(xù)的存儲單例：線性表(1,2,3,4,5,6)的存儲結(jié)構(gòu)：123456是一個典型的線形表順序存儲結(jié)構(gòu)。不是一個線形表順序存儲結(jié)構(gòu)。123456依次存儲，地址連續(xù)——中間沒有空出存儲單元。

存儲結(jié)構(gòu)：地址不連續(xù)——中間存在空的存儲單元。例：線性表(1,2,3,4,5,6)的存儲如何實現(xiàn)順序表的內(nèi)存分配？順序表一維數(shù)組用一維數(shù)組表示順序表類型相同用一變量表示順序表的長度屬性線性表長可變（刪除）順序表（元素）地址連續(xù)隨機存取依次存放數(shù)組（元素）數(shù)組長度不可動態(tài)定義如何實現(xiàn)順序表的內(nèi)存分配？順序表一維數(shù)組用一維數(shù)組類型相同8/8/2023

172.2用數(shù)組(data)實現(xiàn)ADT表（List）

2.2.1用數(shù)組實現(xiàn)的ADT表的特征數(shù)據(jù)及其類型表的元素的類型：為了適應(yīng)表元素類型（datatype）的變化，應(yīng)將表類List定義為一個模板類。在該模板類中，用T來表示用戶指定的元素類型（datatype）。表的長度:n(約定n=0為空表)數(shù)組能容納的表的最大長度:MaxSize約定數(shù)組下標(biāo)為k-1的分量存放表的第k個元素，k=1,2,3,…,n。其結(jié)構(gòu)如下圖7/29/2023172.2用數(shù)組(data)實現(xiàn)ADT用什么屬性來描述順序表？存儲空間的起始位置順序表的容量（最大長度）順序表的當(dāng)前長度用什么屬性來描述順序表？存儲空間的起始位置順序表的容量（最大8/8/2023

19a1a2an01n-112n內(nèi)存data數(shù)組下標(biāo)元素位置MaxSize-1備用空間7/29/202319a1a2an01n-112n內(nèi)存da8/8/2023

202.2.2用數(shù)組實現(xiàn)的ADT表（List）的定義template<classT>classList{private:intn;intMaxSize;

T

*data;//表元素數(shù)組

public:List(intMax=10); //構(gòu)造函數(shù)

~List(){delete[]data;} //析構(gòu)函數(shù)，復(fù)雜性O(shè)（1）

boolEmpty()const{returnn==0;} //復(fù)雜性O(shè)（1）

intSize()const{returnn;} //復(fù)雜性O(shè)（1）

intLocate(constT&x)const；

//返回表中元素x位置

boolRetrieve(intk,T&x)const;//返回表中第k個元素，存于x中

List<T>&Insert(intk,constT&x);//在表的位置k處之后插入元素x

List<T>&Erase(intk,T&x);//從表中刪除位置k處的元素，存入x中

voidPrintList(ostream&out)const;}；

7/29/2023202.2.2用數(shù)組實現(xiàn)的ADT表（Li8/8/2023

212.2.3ADT表（List）的定義中未實現(xiàn)的函數(shù)的實現(xiàn)與分析（1）構(gòu)造函數(shù):List(intMax)template<classT>List<T>::List(intMax) //構(gòu)造函數(shù){MaxSize=Max;data=newT[MaxSize];n=0;}

最壞情況時間復(fù)雜性O(shè)（1）7/29/2023212.2.3ADT表（List）的定內(nèi)存分配

MaxSizedatan內(nèi)存分配MaxSizedatan8/8/2023

232.2.3ADT表（List）的定義中未實現(xiàn)的函數(shù)的實現(xiàn)與分析（續(xù)）（2）為元素x定位:intLocate(constT&x)consttemplate<classT>intList<T>::Locate(constT&x)const{ for(inti=0;i<n;i++) if(data[i]==x)return++i; return0;}

最壞情況時間復(fù)雜性O(shè)（n）7/29/2023232.2.3ADT表（List）的定8/8/2023

242.2.3ADT表（List）的定義中未實現(xiàn)的函數(shù)的實現(xiàn)與分析（續(xù)）（3）檢索第k個元素給x:boolRetrieve(intk,T&x)const;template<classT>boolList<T>::Retrieve(intk,T&x)const{if(k<1||k>n)returnfalse;x=data[k-1];returntrue;

}最壞情況時間復(fù)雜性O(shè)（1）7/29/2023242.2.3ADT表（List）的8/8/2023

25插入定義：線性表的插入是指在第k（0k

n）個元素之后插入一個新的數(shù)據(jù)元素x，使長度為n的線性表

變成長度為n+1的線性表

需將第k+1至第n共（n-k)個元素后移2.2.3ADT表（List）的定義中未實現(xiàn)的函數(shù)的實現(xiàn)與分析（續(xù)）（4）在位置k后插入元素x:List<T>&Insert(intk,constT&x);圖示算法：復(fù)雜性分析7/29/202325插入定義：線性表的插入是指在第k（0ai-1和ai之間的邏輯關(guān)系發(fā)生了變化順序存儲要求存儲位置反映邏輯關(guān)系存儲位置要反映這個變化ai-1和ai之間的邏輯關(guān)系發(fā)生了變化順序存儲要求存儲位置反33例：（35，12，24，42），在i=2的位置上插入33。435122442a1a2a3a401234422412335什么時候不能插入？注意邊界條件33例：（35，12，24，42），在i=2的位置上插入338/8/2023

28內(nèi)存data數(shù)組下標(biāo)元素位置a1a2akak+1an01k-1n-1kn12kk+1nn+1內(nèi)存data數(shù)組下標(biāo)元素位置a1a2akak+1an01k-1n-1kn12kk+1nn+1an-1x7/29/202328內(nèi)存data數(shù)組下標(biāo)元素位置a1a2template<classT>List<T>&List<T>::Insert(intk,constT&x){

if(k<0||k>n) cout<<"out_bounds"; elseif(n==MaxSize) cout<<"no_mem"; else {

for(inti=n-1;i>=k;i--) data[i+1]=data[i];

data[k]=x; n++; }

return*this;}template<classT>8/8/2023

30算法時間復(fù)雜度T(n)最壞情況時間復(fù)雜性：O(n)平均情況時間復(fù)雜性：設(shè)Pk是在第k個元素之后插入一個元素的概率，則在長度為n的線性表中插入一個元素時，所需移動的元素次數(shù)的平均次數(shù)為：7/29/202330算法時間復(fù)雜度T(n)8/8/2023

31刪除定義：線性表的刪除是指將第k（1kn）個元素刪除，使長度為n的線性表

變成長度為n-1的線性表

需將第k+1至第n共（n-k)個元素前移2.2.3ADT表（List）的定義中未實現(xiàn)的函數(shù)的實現(xiàn)與分析（續(xù)）（5）刪除位置k處的元素給x:List<T>&Erase(intk,T&x);

圖示算法：復(fù)雜性分析7/29/202331刪除定義：線性表的刪除是指將第k（1ai-1和ai之間的邏輯關(guān)系發(fā)生了變化順序存儲要求存儲位置反映邏輯關(guān)系存儲位置要反映這個變化ai-1和ai之間的邏輯關(guān)系發(fā)生了變化順序存儲要求存儲位置反例：（35,33,12,24,42），刪除i=2的數(shù)據(jù)元素。535a1a2a3a401234422412334a5122442例：（35,33,12,24,42），刪除i=2的數(shù)8/8/2023

34內(nèi)存a1a2akak+1an01k-1data數(shù)組下標(biāo)n-1kn12k元素序號k+1nn+1內(nèi)存a1a2ak+1data數(shù)組下標(biāo)01k-1n-1kn12k元素序號k+1nn+1anak+2n-2n-17/29/202334內(nèi)存a1a2akak+1an01k-template<classT>List<T>&List<T>::Erase(intk,T&x){

if(Retrieve(k,x)) {

for(inti=k;i<n;i++) data[i-1]=data[i];

n--;

return*this; } else { cout<<"outbounds";

return*this; }}template<classT>8/8/2023

36故在順序表中插入或刪除一個元素時，平均移動表中約一半的元素，當(dāng)n很大時，效率很低算法時間復(fù)雜度T(n)最壞情況時間復(fù)雜性：O(n)平均情況時間復(fù)雜性：設(shè)Qk是刪除第k個元素的概率，則在長度為n的線性表中刪除一個元素時，所需移動的元素次數(shù)的平均次數(shù)為：7/29/202336故在順序表中插入或刪除一個元素時，平8/8/2023

372.2用數(shù)組(data)實現(xiàn)ADT表（List）2.2.3ADT表（List）的定義中未實現(xiàn)的函數(shù)的實現(xiàn)與分析(續(xù)）（6）輸出所有元素:voidPrintList(ostream&out)const;template<classT>voidList<T>::PrintList(ostream&out)const{for(inti=0;i<n;i++)out<<data[i]<<"";}

最壞情況時間復(fù)雜性O(shè)（n）

7/29/2023372.2用數(shù)組(data)實現(xiàn)ADT8/8/2023

382.2.4用數(shù)組(data)實現(xiàn)ADT表（List）的優(yōu)缺點優(yōu)點邏輯相鄰，物理相鄰=>無須為表示表中元素之間的 邏輯關(guān)系而增加額外的存儲空間可隨機存取任一元素缺點插入、刪除操作需要移動大量的元素預(yù)先分配空間需按最大空間分配，利用不充分表容量難以擴充2.2用數(shù)組(data)實現(xiàn)ADT表（List）7/29/2023382.2.4用數(shù)組(data)實現(xiàn)AD8/8/2023

392.3用指針實現(xiàn)ADT表（List）2.3.0用指針實現(xiàn)ADT表動因和構(gòu)想動因：用數(shù)組實現(xiàn)表存在兩個缺點。構(gòu)想：表的每一個元素(data)存放在隨時向操作系統(tǒng)申請到的單元（結(jié)點）內(nèi)，前后結(jié)點靠一個指針來鏈接（單鏈）。結(jié)構(gòu)如下圖：7/29/2023392.3用指針實現(xiàn)ADT表（List8/8/2023

402.3.1用指針實現(xiàn)ADT表的特征數(shù)據(jù)及其類型表的元素的類型：為了適應(yīng)表元素類型（datatype）的變化，應(yīng)將表類List定義為一個模板類。在該模板類中，用T來表示用戶指定的元素類型（datatype）。表的結(jié)點類型：一個結(jié)點存放一個元素和一個指針，用類Node<T>表示。指針指向類Node<T>的結(jié)點。單鏈表的結(jié)構(gòu)如下圖：

只需指向表的第一個結(jié)點的指針（first）便可表示單鏈表。數(shù)據(jù)域指針域結(jié)點7/29/2023402.3.1用指針實現(xiàn)ADT表的特征8/8/2023

41例線性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)4313103771925數(shù)據(jù)域指針域LIQIANSUNWANGWUZHAOZHENGZHOU存儲地址1713192531374331first第一個元素指針ZHAOQIANSUNLIZHOUWUZHENGWANG0first7/29/202341例線性表(ZHAO,QIAN有幾個節(jié)點?第一個節(jié)點的地址存儲在哪個指針里?除了首元結(jié)點外，任一結(jié)點的存儲位置由______________指示每個節(jié)點包括哪兩部分?有幾個節(jié)點?434344current=head;44current=head;45current=current->link;45current=current->link;4646建立包含三個結(jié)點的鏈表。#include<iostream.h>classNode{

public:intdata;Node*next;};建立包含三個結(jié)點的鏈表。voidmain(){ Node*first,*a,*b,*c,*q; a=newNode; b=newNode; c=newNode;

first=a; a->data=1;

a->next=b; b->data=2;

b->next=c; c->data=3;

c->next=NULL;

q=first;

while(q!=NULL) { cout<<q->data<<"";

q=q->next; }}voidmain()q=first;8/8/2023

492.3用指針實現(xiàn)ADT表(List)2.3.2結(jié)點模板類的定義template<classT>classList; //前視聲明template<classT>classNode{friendclassList<T>; private:Tdata;Node<T>*next;};7/29/2023492.3用指針實現(xiàn)ADT表(List8/8/2023

502.3.3用指針實現(xiàn)的ADT表（List）的定義template<classT>classIterator; //前視聲明(去掉)template<classT>classList{

friendclassIterator<T>; private:Node<T>*first;public:List(){first=0;}~List();boolEmpty()const{returnfirst==0;}intLength()const;boolRetrieve(intk,T&x)const;intLocate(constT&x)const;List<T>&Insert(intk,constT&x);List<T>&Delete(intk,T&x);voidPrintList(ostream&out)const;};7/29/2023502.3.3用指針實現(xiàn)的ADT表（8/8/2023

512.3用指針實現(xiàn)ADT表(List)2.3.4表（List）的定義中未實現(xiàn)的函數(shù)的實現(xiàn)與分析（1）析構(gòu)函數(shù):~List();template<classT>List<T>::~List(){Node<T>*next;while(first){next=first->next;deletefirst;first=next;}}

最壞情況時間復(fù)雜性7/29/2023512.3用指針實現(xiàn)ADT表(List8/8/2023

522.3用指針實現(xiàn)ADT表(List)2.3.4表（List）的定義中未實現(xiàn)的函數(shù)的實現(xiàn)與分析（續(xù)）（2）求表長:intLength()const;template<classT>intList<T>::Length()const{Node<T>*current=first;

intlen=0;while(current){len++;

current=current->next;}returnlen;}最壞情況時間復(fù)雜性7/29/2023522.3用指針實現(xiàn)ADT表(List8/8/2023

532.3用指針實現(xiàn)ADT表(List)2.3.4表（List）的定義中未實現(xiàn)的函數(shù)的實現(xiàn)與分析（續(xù)）（3）為元素x定位:intLocate(constT&x);template<classT>intList<T>::Locate(constT&x)const{Node<T>*current=first;

intindex=1; //indexofcurrentwhile(current&¤t->data!=x){

current=current->next;index++;}if(current)returnindex;return0;

}

最壞情況時間復(fù)雜性O(shè)（n）7/29/2023532.3用指針實現(xiàn)ADT表(List核心操作（關(guān)鍵操作）：工作指針后移。從頭結(jié)點（或開始結(jié)點）出發(fā)，通過工作指針的反復(fù)后移而將整個單鏈表“審視”一遍的方法稱為掃描（或遍歷）。firsta1pa2pan∧aipp檢索成功p檢索失敗檢索第k個元素給x:boolRetrieve(intk,T&x)const;firsta1pa2pan∧aipp檢索成功p檢索失敗檢索第1.工作指針current初始化;累加器index初始化;2.1工作指針current后移;2.2累加器index加1;2.循環(huán)直到current為空或current指向第i個結(jié)點3.若current為空，則第i個元素不存在，拋出查找位置異常；否則查找成功，返回結(jié)點current的數(shù)據(jù)元素；1.工作指針current初始化;累加器index初始化8/8/2023

562.3用指針實現(xiàn)ADT表(List)2.3.4ADT表（List）的定義中未實現(xiàn)的函數(shù)的實現(xiàn)與分析（續(xù)）（4）檢索第k個元素給x:boolRetrieve(intk,T&x)const;template<classT>boolList<T>::Retrieve(intk,T&x)const{if(k<1)returnfalse;Node<T>*current=first;intindex=1;while(index<k&¤t){

current=current->next;index++;}if(current){x=current->data;returntrue;}returnfalse;

}

時間復(fù)雜性Current++能否完成指針后移？a1a27/29/2023562.3用指針實現(xiàn)ADT表(List8/8/2023

572.3用指針實現(xiàn)ADT表(List)2.3.4ADT表（List）的定義中未實現(xiàn)的函數(shù)的實現(xiàn)與分析（續(xù)）（5）在位置k后插入元素x:

List<T>&Insert(intk,constT&x);

函數(shù)的運算步驟是：先掃描鏈表找到插入位置p，然后建立一個存儲待插入元素的新結(jié)點y，再將結(jié)點y插入到結(jié)點p之后。插入的示意圖如下

yyy->next=first;firstfirst=y;py->next=p->next;p->next=y;7/29/2023572.3用指針實現(xiàn)ADT表(List1.工作指針p初始化；累加器j清零；2.查找第i-1個結(jié)點并使工作指針p指向該結(jié)點；3.若查找不成功，說明插入位置不合理，拋出插入位置異常；否則，3.1生成一個元素值為x的新結(jié)點s；3.2將新結(jié)點s插入到結(jié)點p之后；1.工作指針p初始化；累加器j清零；8/8/2023

592.3.4（5）（續(xù)）template<classT>List<T>&List<T>::Insert(intk,constT&x){if(k<0)throwOutOfBounds();Node<T>*p=first;//找插入位置for(intindex=1;index<k&&p;index++)p=p->next;if(k>0&&!p)throwOutOfBounds();

Node<T>*y=newNode<T>;y->data=x;if(k){//在位置p處插入

y->next=p->next; p->next=y;}else{//在表首插入需要特殊處理（若引入表頭結(jié)點則可納入一般情況）

y->next=first; first=y;}return*this;

}

時間復(fù)雜性O(shè)（k）7/29/2023592.3.4（5）（續(xù)）8/8/2023

602.3用指針實現(xiàn)ADT表(List)2.3.4ADT表（List）的定義中未實現(xiàn)的函數(shù)的實現(xiàn)與分析（續(xù)）（6）刪除位置k處的元素給x:

List<T>&Delete(intk,T&x);

函數(shù)的運算步驟是：依次處理以下3種情況。（?。﹌<1或鏈表為空；（ⅱ）刪除的是表首元素，即k=1；（ⅲ）刪除的是非表首元素，即k>1。其刪除的示意圖如下p=q->next;q->next=p->next;deletep;7/29/2023602.3用指針實現(xiàn)ADT表(List8/8/2023

612.3.4（6）（續(xù)）template<classT>List<T>&List<T>::Delete(intk,T&x){if(k<1||!first)throwOutOfBounds();Node<T>*p=first;if(k==1)//刪除表首元素需要特殊處理（若引入哨兵結(jié)點則可納入一般情況）

first=first->next;else{//找表中第k-1個元素所在結(jié)點qNode<T>*q=first;for(intindex=1;index<k-1&&q;index++)q=q->next;if(!q||!q->next)throwOutOfBounds();p=q->next;//讓p指向

第k個元素所在結(jié)點

q->next=p->next;}//刪除結(jié)點px=p->data;//第k個元素存入x并釋放結(jié)點pdeletep;return*this;}

時間復(fù)雜性O(shè)（k）？？？!q=>因為q為空而退出for循環(huán)=>index<k-1，即：表中不存在第k個元素；!q->next=>找到index=k-1的位置，但該位置已是表尾， 即：q->next=0。7/29/2023612.3.4（6）（續(xù)）？？？!q在鏈表中設(shè)置頭結(jié)點在鏈表中設(shè)置頭結(jié)點線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表0200020803000325…………a10200a20325a30300a4∧firsta1a2an∧非空表first=NULL空表頭指針：指向第一個結(jié)點的地址。尾標(biāo)志：終端結(jié)點的指針域為空。線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表020002080302.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表0200020803000325…………a10200a20325a30300a4∧firsta1a2an∧非空表first=NULL空表空表和非空表不統(tǒng)一，缺點？如何將空表與非空表統(tǒng)一？2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表02000208頭結(jié)點：在單鏈表的第以一個元素結(jié)點之前附設(shè)一個類型相同的結(jié)點，以便空表和非空表處理統(tǒng)一。2.3線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn)單鏈表非空表firsta1a2an∧空表first∧頭結(jié)點：在單鏈表的第以一個元素結(jié)點之前附設(shè)一個類型相同的結(jié)點頭結(jié)點：在單鏈表的第一個結(jié)點之前人為地附設(shè)的一個結(jié)點。數(shù)據(jù)域La1a2an^…L^頭指針

頭結(jié)點頭指針存放頭結(jié)點的地址。頭結(jié)點不存放任何數(shù)據(jù)存放附加信息（鏈表的結(jié)點個數(shù)等）。指針域存放第一個結(jié)點的地址（若線性表為空表，則“空”，用^表示。）頭結(jié)點：在單鏈表的第一個結(jié)點之前人為地附設(shè)的一個結(jié)點。數(shù)據(jù)問題：在鏈表中設(shè)置頭結(jié)點有什么好處？作用：可以對空表、非空表進行統(tǒng)一處理；可以對首元結(jié)點及其他結(jié)點統(tǒng)一處理。結(jié)論：編程更方便。問題：在鏈表中設(shè)置頭結(jié)點有什么好處？作用：結(jié)論：編程更方8/8/2023

682.3用指針實現(xiàn)ADT表(List)2.3.4ADT表（List）的定義中未實現(xiàn)的函數(shù)的實現(xiàn)與分析（續(xù)）（7）輸出所有元素:voidPrintList(ostream&out)const;template<classT>voidList<T>::PrintList(ostream&out)const{Node<T>*current;for(current=first;current;current=current->next)out<<current->data<<"";

}

時間復(fù)雜性O(shè)（n）7/29/2023682.3用指針實現(xiàn)ADT表(List8/8/2023

692.3用指針實現(xiàn)ADT表(List)2.3.6用指針實現(xiàn)ADT表（List）的優(yōu)缺點優(yōu)點：

避免了數(shù)組要求連續(xù)的單元存儲元素的缺點，因而在執(zhí)行插入或刪除運算時，不再需要移動元素來騰出空間或填補空缺。(當(dāng)元素的粒度很大時，移動元素是很費時的。)缺點：

需要在每個單元中設(shè)置指針來表示表中元素之間的邏輯關(guān)系，因而增加了額外的存儲空間，為獲得上述優(yōu)點付出代價。7/29/2023692.3用指針實現(xiàn)ADT表(List補充#include<iostream.h>classNode{public:intdata;Node*next;};classList{private:Node*first;public:List(){first=0;}~List();boolEmpty()const{returnfirst==0;}intLength()const;boolRetrieve(intk,int&x)const;intLocate(constint&x)const;List&Insert(intk,constint&x);List&Delete(intk,int&x);voidPrintList()const;};先寫這些代碼，然后編譯看是否有問題？能不能鏈接？補充#include<iostream.h>先寫這些代碼，然voidmain(){ Listl1;}如果想能運行，調(diào)用了什么函數(shù)？需加哪個函數(shù)的實現(xiàn)？voidmain()如果想能運行，調(diào)用了什么函數(shù)？需加哪個voidmain(){ Listl1; l1.Insert(0,3); l1.PrintList();}如果想能運行，又調(diào)用了什么函數(shù)？需加哪個函數(shù)的實現(xiàn)？voidmain()如果想能運行，又調(diào)用了什么函數(shù)？需加哪List&List::Insert(intk,constint&x){if(k<0){ cout<<"outbounds"; return*this; }Node*p=first;//找插入位置

for(intindex=1;index<k&&p;index++)p=p->next;if(k>0&&!p){ cout<<"outbounds"; return*this; }Node*y=newNode;y->data=x;if(k){//在位置p處插入

y->next=p->next; p->next=y;}else{//在表首插入需要特殊處理（若引入表頭結(jié)點則可納入一般情況）

y->next=first; first=y;}return*this;}voidList::PrintList()const{Node*current;for(current=first;current;current=current->next)cout<<current->data<<"";}List&List::Insert(intk,cons如何建立鏈表？使用構(gòu)造函數(shù)?（1）從無到有創(chuàng)建；（2）利用原始數(shù)據(jù)直接建立非空鏈表；頭插法建單鏈表尾插法建表看相關(guān)動畫如何建立鏈表？數(shù)據(jù)結(jié)構(gòu)第2章線性表鏈表部分課件數(shù)據(jù)結(jié)構(gòu)第2章線性表鏈表部分課件

從單鏈表中某結(jié)點p出發(fā)如何找到其前驅(qū)？firsta1a2an∧

從單鏈表中某結(jié)點p出發(fā)如何找到其前驅(qū)？firsta1a2a8/8/2023

782.6用單循環(huán)鏈實現(xiàn)表

2.6.1用單循環(huán)鏈實現(xiàn)表的動因和構(gòu)想動因：在用指針實現(xiàn)表時，表尾結(jié)點中的指針為空指針

NULL。人們希望把這個指針用起來，提高查找的效率。構(gòu)想：引入哨兵結(jié)點，并將尾結(jié)點的空指針改為指向哨兵結(jié)點的指針，使整個鏈表形成一個環(huán)。然后，用指向最后結(jié)點的指針表征我們的ADT表，結(jié)構(gòu)如下圖。

(a)非空表(b)空表

7/29/2023782.6用單循環(huán)鏈實現(xiàn)表2.6.1firsta1ai-1anai如何查找開始結(jié)點和終端結(jié)點？開始結(jié)點：first->next終端結(jié)點：將單鏈表掃描一遍，時間為O(n)firsta1ai-1anai如何查找開始結(jié)點和終端結(jié)點？開照此，找最后元素只需O(1),找首元素仍只需O(1)。一個存儲結(jié)構(gòu)設(shè)計得是否合理，取決于基于該存儲結(jié)構(gòu)的運算是否方便，時間性能是否提高。

一個存儲結(jié)構(gòu)設(shè)計得是否合理，取決于基于該存儲結(jié)構(gòu)的運算是否方在循環(huán)鏈表上實現(xiàn)各種運算與鏈表的情形類似，不同之處：循環(huán)終止條件不是p或p->next是否為空，而是判斷是否指向表首；在循環(huán)鏈表上實現(xiàn)各種運算與鏈表的情形類似，不同之處：8/8/2023

822.6用單循環(huán)鏈實現(xiàn)表2.6.2用單循環(huán)鏈實現(xiàn)的表的特征數(shù)據(jù)及其類型表的元素的類型：同指針實現(xiàn)的類T。表的結(jié)點類型：同指針實現(xiàn)的類Node<T>。用單循環(huán)鏈實現(xiàn)的表本身需要的數(shù)據(jù)

intn;//表的長度

Node<T>*last;//指向表尾的指針7/29/2023822.6用單循環(huán)鏈實現(xiàn)表2.6.28/8/2023

832.6.3單循環(huán)鏈表List的模板類的定義template<classT>classIterator;template<classT>classList{friendclassIterator<T>;private:

intn;//表的長度

Node<T>*last;//指向表尾的指針

public:List();~List();boolEmpty()const{returnn==0;}intLength()const{returnn;}boolRetrieve(intk,T&x)const;intLocate(constT&x)const;List<T>&Insert(intk,constT&x);List<T>&Delete(intk,T&x);voidPrintList(ostream&out)const;};區(qū)別于單鏈表中無表長的定義！7/29/2023832.6.3單循環(huán)鏈表List的8/8/2023

842.6用單循環(huán)鏈實現(xiàn)表2.6.4ADT表（List）的定義中未實現(xiàn)的函數(shù)的實現(xiàn)與分析（1）構(gòu)造函數(shù)List();//初始化一個空表template<classT>List<T>::List(){Node<T>*y=newNode<T>;

y->next=y;last=y;//表中只有一個哨兵結(jié)點

n=0;}

//時間復(fù)雜性為O（1）7/29/2023842.6用單循環(huán)鏈實現(xiàn)表2.6.48/8/2023

852.6用單循環(huán)鏈實現(xiàn)表2.6.4表的定義中未實現(xiàn)的函數(shù)的實現(xiàn)與分析（2）析構(gòu)函數(shù):~List();template<classT>List<T>::~List(){Node<T>*next;while(!Empty()){ //非空表的釋放

next=last->next;deletelast;

n--;last=next;}

deletelast;

//空表的釋放

}

//時間復(fù)雜性為O（n）7/29/2023852.6用單循環(huán)鏈實現(xiàn)表2.6.48/8/2023

862.6.4表的定義中未實現(xiàn)的函數(shù)的實現(xiàn)與分析（續(xù)）（3）為元素x定位:intLocate(constT&x);template<classT>intList<T>::Locate(constT&x)const{Node<T>*current=last->next->next;intindex=1;

last->next->data=x;//技巧

while(current->data!=x){//找元素x所在的結(jié)點

current=current->next;index++;}return((current==last->next)?0:index);

}

//最壞情況時間復(fù)雜度為O（n）7/29/2023862.6.4表的定義中未實現(xiàn)的函數(shù)8/8/2023

872.6.4表的定義中未實現(xiàn)的函數(shù)的實現(xiàn)與分析（續(xù)）（4）檢索第k個元素給x:boolRetrieve(intk,T&x)const;template<classT>boolList<T>::Retrieve(intk,T&x)const{if(k<1||k>n)returnfalse;//k值越界

Node<T>*current=last->next->next;//工作指針的初始化

intindex=1;//元素序號初始化

while(index<k){//找第k個元素所在的結(jié)點

current=current->next;index++;}x=current->data;returntrue;

}

//時間復(fù)雜性為O（k）7/29/2023872.6.4表的定義中未實現(xiàn)的函數(shù)8/8/2023

882.6用單循環(huán)鏈實現(xiàn)表2.6.4表的定義中未實現(xiàn)的函數(shù)的實現(xiàn)與分析（續(xù)）（5）在位置k后插入元素x:

List<T>&Insert(intk,constT&x);template<classT>List<T>&List<T>::Insert(intk,constT&x){if(k<0||k>n)throwOutOfBounds();//k值越界

Node<T>*p=last->next;//借助p搜索第k個元素

for(intindex=1;index<=k;index++)p=p->next;Node<T>*y=newNode<T>;//申請新結(jié)點，之后插入表中

y->data=x;

y->next=p->next;p->next=y;if(k==n)last=y;n++;//表長增1return*this;

}//時間復(fù)雜性為O（k）7/29/2023882.6用單循環(huán)鏈實現(xiàn)表2.6.48/8/2023

892.6用單循環(huán)鏈實現(xiàn)表2.6.4表的定義中未實現(xiàn)的函數(shù)的實現(xiàn)與分析（續(xù)）（6）刪除位置k處的元素給x:

List<T>&Delete(intk,T&x);template<classT>List<T>&List<T>::Delete(intk,T&x){if(k<1||k>n)throwOutOfBounds();//k值越界

Node<T>*q=last->next;//借助q搜索第k-1個元素

for(intindex=1;index<＝

k-1;index++)

q=q->next;Node<T>*p=q->next;//q和p分別指向第k－1和k個元素所在的結(jié)點

q->next=p->next;//表中的第k個元素被刪除

if(k==n)last=q;//如果k=n，則第k－1元素所在的結(jié)點成為新表尾結(jié)點

x=p->data;//將原表的第k個元素賦予xdeletep;

n--;return*this;

}

//時間復(fù)雜度為O（k）7/29/2023892.6用單循環(huán)鏈實現(xiàn)表2.6.48/8/2023

902.6用單循環(huán)鏈實現(xiàn)表2.6.4表的定義中未實現(xiàn)的函數(shù)的實現(xiàn)與分析（續(xù)）（7）輸出表中所有元素:voidPrintList(ostream&out)const;template<classT>voidList<T>::PrintList(ostream&out)const{Node<T>*current;for(current=last->next->next;current!=last->next;

current=current->next)//從第1個元素開始逐個輸出

out<<current->data<<"";

}

//時間復(fù)雜度為O（n）7/29/2023902.6用單循環(huán)鏈實現(xiàn)表2.6.48/8/2023

912.6用單循環(huán)鏈實現(xiàn)表2.6.5與單鏈表相比，用單循環(huán)鏈實現(xiàn)表的優(yōu)點：可在O(1)的時間里找到表首元素和表尾元素。7/29/2023912.6用單循環(huán)鏈實現(xiàn)表2.6.5用雙鏈實現(xiàn)表如何求結(jié)點p的直接前驅(qū)，時間性能？firsta1ai-1anai為什么可以快速求得結(jié)點p的后繼？如何快速求得結(jié)點p的前驅(qū)？用雙鏈實現(xiàn)表如何求結(jié)點p的直接前驅(qū)，時間性能？firsta18/8/2023

932.7用雙鏈實現(xiàn)表

2.7.1用雙鏈實現(xiàn)表的動因和構(gòu)想動因：無論在用指針實現(xiàn)表還是在用單循環(huán)鏈實現(xiàn)表時，對于表中任一元素x,都不可能在O（1）時間里找到它的前驅(qū)。為了能在O（1）時間里既能找到前驅(qū)又能找到后繼，提出了雙鏈表。構(gòu)想：在用指針實現(xiàn)表的每一個結(jié)點中增加一個指向前驅(qū)的指針。結(jié)構(gòu)如下圖7/29/2023932.7用雙鏈實現(xiàn)表2.7.18/8/2023

942.7用雙鏈實現(xiàn)表2.7.2用雙鏈實現(xiàn)的表的特征數(shù)據(jù)及其類型表的元素的類型：同指針實現(xiàn)的類T表的結(jié)點類型：DNode<T>

template<classT>classDouble;template<classT>classDNode{friendclassDouble<T>;private:Tdata;DNode<T>*left,*right;}用雙鏈實現(xiàn)的表本身需要的數(shù)據(jù)

intn;//表的長度

DNode<T>*LeftEnd,*RightEnd;//指向表的首、尾指針7/29/2023942.7用雙鏈實現(xiàn)表2.7.2用8/8/2023

952.7.3雙鏈表List的模板類的定義。

template<classT>classDouble{public:Double(){LeftEnd=RightEnd=0;};~Double();boolEmpty()const{returnn==0;}intLength()const{returnn;}boolRetrieve(intk,T&x)const;intLocate(constT&x)const;Double<T>&Insert(intk,constT&x);Double<T>&Delete(intk,T&x);voidPrintList(ostream&out)const;private:intn;DNode<T>*LeftEnd,*RightEnd;};7/29/2023952.7.3雙鏈表List的模板類8/8/2023

962.8用雙循環(huán)鏈實現(xiàn)表2.8.1用雙循環(huán)鏈實現(xiàn)表的動因和構(gòu)想動因：從雙鏈到雙循環(huán)鏈類似于從單鏈到單循環(huán)鏈。構(gòu)想：引入哨兵結(jié)點，并將雙鏈表的首、尾結(jié)點的空指針改為指向哨兵結(jié)點的指針，而哨兵結(jié)點的左、右指針分別指向尾元素、首元素所在的結(jié)點，使整個鏈表形成一個雙鏈環(huán)。然后，用指向哨兵結(jié)點的指針表征我們的ADT表。結(jié)構(gòu)如下圖。7/29/2023962.8用雙循環(huán)鏈實現(xiàn)表2.8.18/8/2023

972.8用雙循環(huán)鏈實現(xiàn)表2.8.2用雙循環(huán)鏈實現(xiàn)的表的特征數(shù)據(jù)及其類型表的元素的類型：同指針實現(xiàn)的類T。表的結(jié)點類型：同雙鏈表的類DNode<T>用雙循環(huán)鏈實現(xiàn)的表本身需要的數(shù)據(jù)

intn;//表的長度

DNode<T>*header;//指向表的哨兵結(jié)點的指針7/29/2023972.8用雙循環(huán)鏈實現(xiàn)表2.8.28/8/2023

982.8.3雙循環(huán)鏈表List的模板類的定義。template<classT>classDouble{public:Double();~Double();boolEmpty()const{returnn==0;}intLength()const{returnn;}boolRetrieve(intk,T&x)const;intLocate(constT&x)const;Double<T>&Insert(intk,constT&x);Double<T>&Delete(intk,T&x);voidPrintList(ostream&out)const;private:intn;DNode<T>*header;};

7/29/2023982.8.3雙循環(huán)鏈表List的模8/8/2023

992.8用雙循環(huán)鏈實現(xiàn)表2.8.4表的定義中未實現(xiàn)的函數(shù)的實現(xiàn)與分析（1）構(gòu)造函數(shù):List()template<classT>Double<T>::Double(){DNode<T>*y=newDNode<T>;y->left=y;y->right=y;header=y;n=0;}//時間復(fù)雜度為O（1）

7/29/2023992.8用雙循環(huán)鏈實現(xiàn)表2.8.48/8/2023

1002.8.4表的定義中未實現(xiàn)的函數(shù)的實現(xiàn)與分析（2）析構(gòu)函數(shù):~List();template<classT>Double<T>::~Double(){DNode<T>*current;DNode<T>*next;current=header->right;while(!Empty()){//從第一個元素開始逐個地釋放

next=current->right;deletecurrent;n--;current=next;}deleteheader;//最后釋放哨兵結(jié)點

}

//時間復(fù)雜度為O（n）

7/29/20231002.8.4表的定義中未實現(xiàn)的8/8/2023

1012.8用雙循環(huán)鏈實現(xiàn)表2.8.4表的定義中未實現(xiàn)的函數(shù)的實現(xiàn)與分析（3）檢索第k個元素給x:boolRetrieve(intk,T&x)const;template<classT>boolDouble<T>::Retrieve(intk,T&x)const{if(k<1||k>n)returnfalse;//k值越界

DNode<T>*current=header->right;intindex=1;while(index<k){//找表中第k個元素

current=current->right;index++;}x=current->data;//找到表中第k個元素賦予xreturntrue;

}//時間復(fù)雜度為O（k）7/29/20231012.8用雙循環(huán)鏈實現(xiàn)表2.8.8/8/2023

1022.8用雙循環(huán)鏈實現(xiàn)表2.8.4表的定義中未實現(xiàn)的函數(shù)的實現(xiàn)與分析（4）為元素x定位:intLocate(constT&x);template<classT>intDouble<T>::Locate(constT&x)const{DNode<T>*current=header->right;intindex=1;header->data=x;//技巧：將x放入哨兵結(jié)點

while(current->data!=x){//找元素x所在的結(jié)點

current=current->right;index++;}return((current==header)?0:index);

}

//最壞情況時間復(fù)雜度為O（n）7/29/20231022.8用雙循環(huán)鏈實現(xiàn)表2.8.8/8/2023

1032.8.4表的定義中未實現(xiàn)的函數(shù)的實現(xiàn)與分析（5）在位置k后插入元素x:

List<T>&Insert(intk,constT&x);template<classT>Double<T>&Doub