數(shù)據(jù)結(jié)構(gòu)陳慧南-第02章(編輯修改稿)
2025-08-21 21:27 本頁面
【文章內(nèi)容簡介】 ch(T x) const。 bool Insert(int i,T x)。 bool Delete(int i)。 …… 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 ……. private: NodeT* first。 }。 順序表類 SeqList、單鏈表類 SingleList是抽象線性表類 LinearList類的派生類。 SingleList LinearList SeqList Node friend 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 構(gòu)造函數(shù) SingleList(){ first=NULL。 n=0。 } 析構(gòu)函數(shù) template class T SingleListT:: ~SingleList() { NodeT *p。 while (first){ p=firstlink。 delete first。 first=p。 } } 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 搜索運(yùn)算 必須從頭指針開始沿鏈逐個計數(shù)查找，稱為 順序查找 搜索運(yùn)算的平均、最壞的漸近時間復(fù)雜度：O(n) 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 templateclass T bool SingleListT::Find(int i,Tamp。 x)const { //在 (a0,a1,...,an?1)中找下標(biāo)為 i的元素 ai if (i0 || in?1){ //對 i進(jìn)行越界檢查 cout Out Of Bounds。 return false。 } NodeT *p=first。 for (int j=0。 ji。 j++) p=plink。 x=pelement。 return true。 } 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 插入運(yùn)算 修改兩個指針域的值 插入漸近時間復(fù)雜度： O(1) qlink=plink。 plink=q； 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 插入運(yùn)算步驟 ： 生成數(shù)據(jù)域為 x的新結(jié)點， q指向新結(jié)點 。 從 first開始找第 i+1個結(jié)點， p指向該結(jié)點； 將 q插入 p之后。 表長加 1。 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 templateclass T bool SingleListT::Insert(int i,T x) { if (i?1 || in?1){ cout Out Of Bounds。 return false。 } NodeT * q=new NodeT。qelement=x。 NodeT *p=first。 // 找 ai元素所在的結(jié)點 p for (int j=0。 ji。 j++) p=plink。 first a0 a1 a2 an1 … ∧ 非空單鏈表 first ? 空單鏈表 p p p i=2 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 if(i?1) { qlink=plink。 //新結(jié)點 q插在 p之后 plink=q。 } else { qlink=first。 //新結(jié)點 q插在頭結(jié)點之前 first=q。 } n++。 return true。 } // 刪除結(jié)點 p是指刪除指針變量 p所指示的結(jié)點 *p。 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 單鏈表的刪除 只需修改一個指針 “ qlink=plink”，但還需使用 “ delete p； ” 語句回收結(jié)點占用的空間。 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 單鏈表的步驟 從 first開始找第 i+1個結(jié)點， p指向該結(jié)點， q指向 p之前驅(qū)結(jié)點 。 從單鏈表中刪除 p； 釋放 p之空間； 表長 減 1。 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 templateclass T bool SingleListT::Delete(int i) { if ( !n ) { coutUnderFlowendl。 return false。 } if ( i0 || in1 ) { cout Out Of Boundsendl。 return false； } NodeT *p=first,*q=first。 for (int j=0。 ji1。 j++) q=qlink。 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 if (i==0) first=firstlink。// 刪除頭結(jié)點 else { p=qlink。 qlink=plink。 } delete p。 n。 return true。 } 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 單鏈表運(yùn)算的優(yōu)缺點 優(yōu)點 單鏈表插入和刪除只需修改一兩個指針，無需移動元素。如已知前驅(qū)結(jié)點，插入刪除運(yùn)算的時間為O(1) 可以動態(tài)分配結(jié)點空間，線性表的長度只受內(nèi)存大小限制。 缺點 查找運(yùn)算費(fèi)時，只能順序查找，不能隨機(jī)查找 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 帶表頭結(jié)點的單鏈表 請區(qū)分 “ 表頭結(jié)點 ” 和 “ 頭結(jié)點 ” 南京郵電大學(xué)計算機(jī)學(xué)院 陳慧南 2022年 9月 templateclass T HeaderListT:: HeaderList() { NodeT *first=new NodeT。 firstlink=NULL。 n=0。 } 南京郵電大學(xué)計算機(jī)
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1