2-4線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及實(shí)現(xiàn)v第二章線性表單鏈表的引入靜態(tài)存儲(chǔ)分配順序表事先確定容量單鏈表動(dòng)態(tài)存儲(chǔ)分配運(yùn)行時(shí)分配空間連續(xù)不連續(xù)零散分布單鏈表：線性表的鏈接存儲(chǔ)結(jié)構(gòu)存儲(chǔ)思想：用一組任意的存儲(chǔ)單元存放線性表單鏈表的存儲(chǔ)結(jié)構(gòu)單鏈表的實(shí)現(xiàn)學(xué)什么？雙鏈表循環(huán)鏈表2-4-1單鏈表的存儲(chǔ)結(jié)構(gòu)v第二章線性表0200020803000325…………a1a2a3a4例：(a1,a2,a3,a4)的存儲(chǔ)示意圖0200

03250300∧存儲(chǔ)特點(diǎn)：邏輯次序和物理次序不一定相同2.元素之間的邏輯關(guān)系用指針表示單鏈表的存儲(chǔ)方法觀察1：?jiǎn)捂湵碛扇舾山Y(jié)點(diǎn)構(gòu)成觀察2：?jiǎn)捂湵淼慕Y(jié)點(diǎn)只有一個(gè)指針域datanext單鏈表的結(jié)點(diǎn)結(jié)構(gòu)數(shù)據(jù)域data：存儲(chǔ)數(shù)據(jù)元素指針域next：存儲(chǔ)指向后繼結(jié)點(diǎn)的地址0200020803000325…………a1a2a3a40200

03250300∧頭指針：指向第一個(gè)結(jié)點(diǎn)的存儲(chǔ)地址尾標(biāo)志：終端結(jié)點(diǎn)的指針域?yàn)榭說irsta1a2an∧非空表first=NULL空表空表和非空表不統(tǒng)一，有什么缺點(diǎn)？first單鏈表的存儲(chǔ)方法頭結(jié)點(diǎn)：在第一個(gè)元素結(jié)點(diǎn)之前附設(shè)一個(gè)類型相同的結(jié)點(diǎn)firsta1a2an∧first∧非空表空表頭結(jié)點(diǎn)簡(jiǎn)化了對(duì)邊界的處理——插入、刪除、構(gòu)造等頭指針：指向第一個(gè)結(jié)點(diǎn)的存儲(chǔ)地址尾標(biāo)志：終端結(jié)點(diǎn)的指針域?yàn)榭諉捂湵淼拇鎯?chǔ)方法structNode{data;structNode*next;}Node;template<typenameDataType>DataType單鏈表的結(jié)點(diǎn)結(jié)構(gòu)定義firsta1a2an∧指針的相關(guān)問題如何引用結(jié)點(diǎn)p的數(shù)據(jù)域（指針域）？firsta1a2an∧p該結(jié)點(diǎn)用*p來表示，*p為結(jié)點(diǎn)變量。將“指針p所指結(jié)點(diǎn)”簡(jiǎn)稱為“結(jié)點(diǎn)p”p->data*p.datap->next*p.next*p*(p->next)如何表示結(jié)點(diǎn)p的下一個(gè)結(jié)點(diǎn)？設(shè)指針p指向某個(gè)Node類型的結(jié)點(diǎn)2-4-2單鏈表的實(shí)現(xiàn)v第二章線性表單鏈表的類定義template<typenameDataType>classLinkedList{public:

LinkedList();//無參構(gòu)造函數(shù)，建立只有頭結(jié)點(diǎn)的空鏈表LinkedList(DataTypea[],intn);//有參構(gòu)造函數(shù)，建立有n個(gè)元素的單鏈表~LinkedList();//析構(gòu)函數(shù)intLength();//求單鏈表的長(zhǎng)度DataTypeGet(inti);//按位查找。查找第i個(gè)結(jié)點(diǎn)的元素值intLocate(DataTypex);//按值查找。查找值為x的元素序號(hào)voidInsert(inti,DataTypex);//插入操作，第i個(gè)位置插入值為x的結(jié)點(diǎn)DataTypeDelete(inti);//刪除操作，刪除第i個(gè)結(jié)點(diǎn)intEmpty();//判斷線性表是否為空voidPrintList();//遍歷操作，按序號(hào)依次輸出各元素private:Node<DataType>*first;//單鏈表的頭指針};單鏈表的實(shí)現(xiàn)——初始化∧first初始化一個(gè)單鏈表要完成哪些工作呢？template<typenameDataType>LinkedList<DataType>::LinkedList(){

first=newNode<DataType>;

first->next=nullptr;}空單鏈表滿足什么條件呢？template<typenameDataType>int

LinkedList<DataType>::Empty(

){if(first->next==nullptr)return1elsereturn0;}單鏈表的實(shí)現(xiàn)——遍歷firsta1a2an∧pp核心操作：工作指針后移如何實(shí)現(xiàn)工作指針后移？p++能正確實(shí)現(xiàn)后移嗎？a1a2pp++p->nextp=p->nextfirsta1a2an∧first為什么設(shè)置工作指針？通過頭指針后移掃描單鏈表會(huì)有什么后果？first修改前：(a1,a2,…,an)first修改后：(a2,…,an)單鏈表頭指針的作用是標(biāo)識(shí)單鏈表的開始，通常不修改頭指針first指向頭結(jié)點(diǎn)單鏈表的實(shí)現(xiàn)——遍歷firsta1a2an∧輸入：無功能：遍歷單鏈表PrintList輸出：?jiǎn)捂湵淼母鱾€(gè)數(shù)據(jù)元素1.工作指針p初始化;2.重復(fù)執(zhí)行下述操作，直到指針p為空：

2.1輸出結(jié)點(diǎn)p的數(shù)據(jù)域;2.2工作指針p后移;如何描述遍歷的基本過程？偽代碼——梳理思路的好工具！p單鏈表的實(shí)現(xiàn)——遍歷template<typenameDataType>voidLinkedList<DataType>::PrintList(){Node<DataType>*p=first->next;//工作指針p初始化while(p!=nullptr){cout<<p->data<<"\t";

p=p->next;//工作指針p后移，注意不能寫作p++}cout<<endl;}firsta1a2an∧p單鏈表的實(shí)現(xiàn)——遍歷單鏈表算法的設(shè)計(jì)模式

訪問結(jié)點(diǎn)p進(jìn)行的操作

退出循環(huán)的操作firsta1a2an∧p單鏈表算法的設(shè)計(jì)模式：通過工作指針的反復(fù)后移掃描鏈表p=first->next;//或p=first;，工作指針p初始化while(p!=nullptr)//或p->next!=nullptr，掃描單鏈表{}p=p->next;//工作指針后移單鏈表的實(shí)現(xiàn)——長(zhǎng)度pintLinkedList<DataType>::Length(){

returncount;}first∧注意count的初值和返回值之間的關(guān)系Node*p=first->next;while(p!=nullptr){p=p->next;}intcount=0;count++;firsta1a2an∧pcount=1pcount=2pcount=n單鏈表的實(shí)現(xiàn)——按位查找firsta1aian∧pcount=1pcount=ipi>nDataTypeLinkedList<DataType>::Get(inti){

Node<DataType>*p=first->next;//工作指針p初始化intcount=1;//累加器count初始化

while(p!=nullptr&&count<i){p=p->next;//工作指針p后移count++;}if(p==nullptr)throw"查找位置錯(cuò)誤";elsereturnp->data;}firsta1xan∧pppintLinkedList<DataType>::Locate(DataTypex){

Node<DataType>*p=first->next;//工作指針p初始化intcount=1;//累加器count初始化

while(p!=nullptr){if(p->data==x)returncount;//查找成功，結(jié)束函數(shù)并返回序號(hào)p=p->next;count++;}return0;//退出循環(huán)表明查找失敗}單鏈表的實(shí)現(xiàn)——按值查找單鏈表的實(shí)現(xiàn)——插入pxs如何實(shí)現(xiàn)結(jié)點(diǎn)ai-1、x和ai之間邏輯關(guān)系的變化？s=newNode;s->data=x;firsta1ai-1an∧ai算法描述：s->next=p->next;p->next=s;pxsfirsta1ai-1an∧ai注意分析邊界情況——表頭、表尾？pxspxs∧單鏈表沒有特殊說明，都帶頭結(jié)點(diǎn)s->next=p->next;p->next=s;單鏈表的實(shí)現(xiàn)——插入如果不帶頭結(jié)點(diǎn)，會(huì)怎么樣呢？pxsfirsta1ai-1anais->next=first;first=s;xspxss->next=p->next;p->next=s;操作不一致會(huì)導(dǎo)致算法增加處理步驟，而且容易出錯(cuò)∧單鏈表的實(shí)現(xiàn)——插入算法：Insert輸入：?jiǎn)捂湵淼念^指針first，插入位置i，待插值x輸出：如果插入成功，返回新的單鏈表，否則返回插入失敗信息1.工作指針p初始化為指向頭結(jié)點(diǎn)；2.查找第i-1個(gè)結(jié)點(diǎn)并使工作指針p指向該結(jié)點(diǎn)；

3.若查找不成功，說明插入位置不合理，返回插入失敗信息；否則，生成元素值為x的新結(jié)點(diǎn)s，將結(jié)點(diǎn)s插入到結(jié)點(diǎn)p之后；pxsfirsta1ai-1an∧aipxspxs∧單鏈表的實(shí)現(xiàn)——插入voidLinkedList<DataType>::Insert(inti,DataTypex){Node<DataType>*p=first,*s=nullptr;//工作指針p初始化intcount=0;while(p!=nullptr&&count<i-1)//查找第i–1個(gè)結(jié)點(diǎn){p=p->next;//工作指針p后移count++;}

if(p==nullptr)throw"插入位置錯(cuò)誤";//沒有找到第i-1個(gè)結(jié)點(diǎn)else{

s=newNode<DataType>;s->data=x;//申請(qǐng)結(jié)點(diǎn)s，數(shù)據(jù)域?yàn)閤s->next=p->next;p->next=s;//將結(jié)點(diǎn)s插入到結(jié)點(diǎn)p之后}}時(shí)間復(fù)雜度？O(n)O(1)已知指針p單鏈表的實(shí)現(xiàn)——插入單鏈表的實(shí)現(xiàn)——建立操作接口：Node*LinkedList(DataTypea[],intn)數(shù)組a3512243342頭插法：插在頭結(jié)點(diǎn)的后面first=newNode;first->next=nullptr;初始化first∧s=newNode;s->data=a[0];s->next=first->next;first->next=s;插入第一個(gè)元素結(jié)點(diǎn)35s∧操作接口：Node*LinkedList(DataTypea[],intn)數(shù)組a3512243342頭插法：插在頭結(jié)點(diǎn)的后面依次插入每一個(gè)結(jié)點(diǎn)12sfirst35∧單鏈表的元素順序有什么特點(diǎn)？s=newNode;s->data=a[i];s->next=first->next;first->next=s;單鏈表的實(shí)現(xiàn)——建立template<typenameDataType>LinkedList<DataType>::LinkedList(DataTypea[],intn){

first=newNode<DataType>;first->next=nullptr;//初始化一個(gè)空鏈表for(inti=0;i<n;i++){Node<DataType>*s=nullptr;s=newNode<DataType>;

s->data=a[i];

s->next=first->next;first->next=s;//將結(jié)點(diǎn)s插入到頭結(jié)點(diǎn)之后}}單鏈表的實(shí)現(xiàn)——建立操作接口：Node*LinkedList(DataTypea[],intn)數(shù)組a3512243342尾插法：插在尾結(jié)點(diǎn)的后面初始化firstrearfirst=newNode;rear=first;為方便在尾結(jié)點(diǎn)后面插入結(jié)點(diǎn)，設(shè)指針rear指向尾結(jié)點(diǎn)單鏈表的實(shí)現(xiàn)——建立操作接口：Node*LinkedList(DataTypea[],intn)尾插法：插在尾結(jié)點(diǎn)的后面依次插入每一個(gè)結(jié)點(diǎn)first

35rear

12ss=newNode;s->data=a[i];rear->next=s;rear=s;∧first

35

42srear數(shù)組a3512243342單鏈表的元素順序有什么特點(diǎn)？單鏈表的實(shí)現(xiàn)——建立template<typenameDataType>LinkedList<DataType>::LinkedList(DataTypea[],intn){first=newNode<DataType>;//生成頭結(jié)點(diǎn)Node<DataType>*r=first,*s=nullptr;//尾指針初始化for(inti=0;i<n;i++){s=newNode<DataType>;

s->data=a[i];

r->next=s;r=s;//將結(jié)點(diǎn)s插入到終端結(jié)點(diǎn)之后}

r->next=nullptr;//單鏈表建立完畢，將終端結(jié)點(diǎn)的指針域置空}單鏈表的實(shí)現(xiàn)——建立循環(huán)不變式外提！p如何實(shí)現(xiàn)結(jié)點(diǎn)ai-1、ai和ai+1

之間邏輯關(guān)系的變化？firsta1ai-1an∧aiai+1qq=p->next;x=q->data;p->next=q->next;deleteq;pq注意分析邊界情況——?jiǎng)h除表頭和表尾！

pq表尾的特殊情況：雖然被刪結(jié)點(diǎn)不存在，但其前驅(qū)結(jié)點(diǎn)卻存在！算法描述：?jiǎn)捂湵淼膶?shí)現(xiàn)——?jiǎng)h除pfirsta1ai-1an∧aiai+1qpqpq算法：Delete輸入：?jiǎn)捂湵淼念^指針first，刪除的位置i輸出：如果刪除成功，返回被刪除的元素值，否則返回刪除失敗信息1.工作指針p初始化；累加器count初始化；2.查找第i-1個(gè)結(jié)點(diǎn)并使工作指針p指向該結(jié)點(diǎn)；3.若p不存在或p的后繼結(jié)點(diǎn)不存在，則出現(xiàn)刪除位置錯(cuò)誤，刪除失??；否則，3.1存儲(chǔ)被刪結(jié)點(diǎn)和被刪元素值；3.2摘鏈，將結(jié)點(diǎn)p的后繼結(jié)點(diǎn)從鏈表上摘下；3.3釋放被刪結(jié)點(diǎn)；單鏈表的實(shí)現(xiàn)——?jiǎng)h除DataTypeLinkedList<DataType>::Delete(inti){DataTypex;intcount=0;Node<DataType>*p=first,*q=nullptr;//工作指針p指向頭結(jié)點(diǎn)while(p!=nullptr&&count<i-1)//查找第i-1個(gè)結(jié)點(diǎn){p=p->next;count++;}if(p==nullptr||p->next==nullptr)throw"刪除位置錯(cuò)誤";else{q=p->next;x=q->data;//暫存被刪結(jié)點(diǎn)p->next=q->next;//摘鏈deleteq;returnx;}}單鏈表的實(shí)現(xiàn)——?jiǎng)h除將p!=nullptr修改為p->next!=nullptr是否可以？template<typenameDataType>LinkedList<DataType>::~LinkedList(){Node<DataType>*p=first;while(first!=nullptr)//釋放單鏈表的每一個(gè)結(jié)點(diǎn)的存儲(chǔ)空間{

first=first->next;//first指向被釋放結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)deletep;p=first;//工作指針p后移}}單鏈表的實(shí)現(xiàn)——析構(gòu)函數(shù)單鏈表需要釋放哪些存儲(chǔ)空間？為什么？2-4-3雙鏈表v第二章線性表雙鏈表的引入firsta1ai-1an∧aiai+1p從頭結(jié)點(diǎn)出發(fā)，如何求得結(jié)點(diǎn)p的直接前驅(qū)？如何快速求得結(jié)點(diǎn)p的前驅(qū)？a2a3first

a1a4∧∧雙鏈表：?jiǎn)捂湵淼拿總€(gè)結(jié)點(diǎn)再設(shè)置一個(gè)指向其前驅(qū)結(jié)點(diǎn)的指針域雙鏈表的存儲(chǔ)結(jié)構(gòu)定義a2a3first

a1a4∧∧priordatanext啟示？時(shí)空權(quán)衡——空間換取時(shí)間數(shù)據(jù)表示template<typename

DataType>sructDLNode{

DataTypedata;DLNode<DataType>*prior,*next;};雙鏈表的操作——插入s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;aiai+1pxs注意指針修改的相對(duì)順序s=newDulNode;ai-1aipxss->prior=p->prior;s->next=p;p->prior=s;p->prior->next=s;s=newDulNode;雙鏈表的操作更加靈活ai-1pai+1ai(p-