1、南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,數(shù)據(jù)結(jié)構(gòu),Data Structures in C+,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,第2章 線性表,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,2.1 線性表ADT 2.2 線性表的順序表示 2.3 線性表的鏈接表示 2.4 多項(xiàng)式的算術(shù)運(yùn)算,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,2.1 線性表ADT,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,線性表的定義 線性表是n(0)個(gè)元素a0,a1,an-1 的線性序列，記為: (a0,a1,an-1)。其中n是線性表中元素的個(gè)數(shù)，稱為線性表的長(zhǎng)度；n=0時(shí)稱為空表。

2、 ai是表中下標(biāo)為i的元素（i=0,1,n-1），稱ai是ai+1的直接前驅(qū)元素，ai+1是ai的直接后繼元素。 線性表是動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，它的表長(zhǎng)可以改變。,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,線性表ADT ADT LinearList 數(shù)據(jù)： 0個(gè)或多個(gè)元素的線性序列（a0,a1,.,an-1），其最大允許長(zhǎng)度為MaxListSize。 運(yùn)算： Create()： 創(chuàng)建一個(gè)空線性表。 Destroy()：撤消一個(gè)線性表。 IsEmpty()：若線性表空，則返回true；否則返回false。 Length()： 返回表中元素個(gè)數(shù)。,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,Fi

3、nd(i,x)：在x中返回表中下標(biāo)為i的元素ai。若不存在，則返回false，否則返回true。 Search(x)：若x不在表中，則返回-1，否則返回x在表中的下標(biāo)。 Insert(i,x)：在元素ai之后插入x。若i=-1，則x插在第一個(gè)元素a0前。若插入成功，則返回true，否則返回false。 Delete(i)：刪除元素ai。若刪除成功，則返回true，否則返回false。 Update(i,x)：將元素ai的值修改為x。若修改成功，則返回true，否則返回false。 Output(out)：把表送至輸出流 / 插入x 到表：（a0,a1,.,an-1）,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳

4、慧南 2006年9月,線性表類 template class LinearList public: virtual bool Find(int i,T,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,2.2 線性表的順序表示,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,2.2.1 順序存儲(chǔ)結(jié)構(gòu),順序存儲(chǔ)表示 是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中元素。 順序表 順序表示的線性表稱為順序表,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,地址計(jì)算公式 若已知順序表中每個(gè)元素占k個(gè)存儲(chǔ)單元，第一個(gè)元素a0在計(jì)算機(jī)內(nèi)存中的首地址是loc(a0)，則表中任意一個(gè)元素ai在內(nèi)存中的存儲(chǔ)地址loc

5、(ai)為 loc(ai)=loc(a0)+i*k 隨機(jī)存取結(jié)構(gòu) 只要給定loc(a0)和k，就可以確定線性表中任意一個(gè)元素的存儲(chǔ)地址，換句話說，順序表是一種隨機(jī)存取結(jié)構(gòu)。,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,2.2.2 順序表類,順序表類 template class SeqList:public LinearList public: /公有函數(shù) SeqList(int mSize); SeqList() delete elements; bool Find(int i,T ,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月, private:/私有數(shù)據(jù) int maxLength

6、;/順序表的最大長(zhǎng)度 T *elements;/動(dòng)態(tài)一維數(shù)組的指針 ;,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,動(dòng)態(tài)存儲(chǔ)分配 構(gòu)造函數(shù)，構(gòu)建一個(gè)空線性表 template SeqList:SeqList(int mSize) maxLength=mSize; elements=new TmaxLength; n=0; ,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,析構(gòu)函數(shù)，撤消一個(gè)順序表 template SeqList: SeqList() delete elements; ,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,2.2.3 線性表運(yùn)算實(shí)現(xiàn),搜索運(yùn)算 Find(i,x)

7、: 查找下標(biāo)為i的元素ai。 在x中返回表中下標(biāo)為i的元素ai (即表中 第i+1個(gè)元素)。如果不存在，則返回 false，否則返回true。,x=elementsi; 漸近時(shí)間復(fù)雜度：O(1),南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,template bool SeqList:Find(int i,T ,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,插入運(yùn)算 Insert(i,x)：在表中下標(biāo)為i的元素ai后插入x。 若i=-1，則將新元素x插在最前面。若插入成功，返回true；,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,插入運(yùn)算的平均時(shí)間復(fù)雜度 分析：設(shè)順序表長(zhǎng)度為n，共有

8、n+1個(gè)可插入元素的位置，并設(shè)在各位置處插入元素的概率是相等的，即Pi=1/(n+1)，在位置i（i=-1,0,n-1）后插入一個(gè)元素要移動(dòng) n-i-1個(gè)元素。,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,template bool SeqList:Insert(int i,T x) /在元素ai之后插入x if (in-1) /越界檢查 couti;j-) elementsj+1=elementsj; elementsi+1=x;n+; return true; ,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,刪除運(yùn)算 Delete(i)： 刪除元素ai。,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧

9、南 2006年9月,刪除運(yùn)算的平均時(shí)間復(fù)雜度 分析: 設(shè)順序表長(zhǎng)度為n,則刪除元素ai（i=0,n-1）,要移動(dòng)n-i-1元素。若刪除表中每個(gè)元素的概率是相等的，即Qi=1/n，,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,template bool SeqList:Delete(int i) /刪除元素ai if (!n) /下溢出檢查 coutn-1) coutOut Of Boundsendl; return false; /從前往后逐個(gè)前移元素 for (int j=i+1;jn;j+) elementsj-1=elementsj; n-; return true; ,南京郵電大學(xué)

10、計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,void main() int x=10; SeqList r(4); r.Insert(-1,x); r.Insert(-1,x); r.Output(cout); /? 請(qǐng)復(fù)習(xí)C+，理解這一函數(shù) ,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,線性表的順序存儲(chǔ)表示的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)： 隨機(jī)存?。?存儲(chǔ)空間利用率高。 缺點(diǎn)： 插入、刪除效率低； 必須按事先估計(jì)的最大元素個(gè)數(shù)分配連續(xù)的存儲(chǔ)空間，難以臨時(shí)擴(kuò)大。,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,2.3 線性表的鏈接表示,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,2.3.1 單鏈表,鏈接存儲(chǔ)表

11、示 單鏈表的結(jié)點(diǎn)結(jié)構(gòu) 單鏈表結(jié)構(gòu),南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,注意事項(xiàng) 頭指針first是指向單鏈表的頭結(jié)點(diǎn)的指針 最后一個(gè)結(jié)點(diǎn)的指針域?yàn)椋刂分禐? 邏輯上相鄰的元素在物理上不一定相鄰 不能出現(xiàn)“斷鏈”現(xiàn)象,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,結(jié)點(diǎn)類 #include linearlist.h template class SingleList；/超前聲明 template class Node private: T element; Node *link; friend class SingleList; ;,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,

12、單鏈表類 template class SingleList:public LinearList public: SingleList() first=NULL; n=0; SingleList(); bool Find(int i,T ,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,. private: Node* first; ;,順序表類SeqList、單鏈表類SingleList是抽象線性表類LinearList類的派生類。,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,構(gòu)造函數(shù) SingleList() first=NULL; n=0; 析構(gòu)函數(shù) template SingleL

13、ist: SingleList() Node *p; while (first) p=first-link; delete first; first=p; ,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,搜索運(yùn)算 必須從頭指針開始沿鏈逐個(gè)計(jì)數(shù)查找，稱為順序查找 搜索運(yùn)算的平均、最壞的漸近時(shí)間復(fù)雜度：O(n),南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,template bool SingleList:Find(int i,T ,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,插入運(yùn)算 修改兩個(gè)指針域的值插入漸近時(shí)間復(fù)雜度：O(1) q-link=p-link; p-link=q；,南京郵

14、電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,插入運(yùn)算步驟： 生成數(shù)據(jù)域?yàn)閤的新結(jié)點(diǎn)，q指向新結(jié)點(diǎn); 從first開始找第i+1個(gè)結(jié)點(diǎn)，p指向該結(jié)點(diǎn)； 將q插入p之后。 表長(zhǎng)加1。,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,template bool SingleList:Insert(int i,T x) if (in1) cout * q=new Node;q-element=x; Node *p=first;/ 找ai元素所在的結(jié)點(diǎn)p for (int j=0; jlink;,first,i=2,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,if(i1) q-link=p-link;

15、/新結(jié)點(diǎn)q插在p之后 p-link=q; else q-link=first; /新結(jié)點(diǎn)q插在頭結(jié)點(diǎn)之前 first=q; n+; return true; / 刪除結(jié)點(diǎn)p是指刪除指針變量p所指示的結(jié)點(diǎn)*p。,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,單鏈表的刪除 只需修改一個(gè)指針“q-link=p-link”，但還需使用“delete p；”語(yǔ)句回收結(jié)點(diǎn)占用的空間。,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,單鏈表的步驟 從first開始找第i+1個(gè)結(jié)點(diǎn)，p指向該結(jié)點(diǎn)，q指向p之前驅(qū)結(jié)點(diǎn); 從單鏈表中刪除p； 釋放p之空間； 表長(zhǎng)減1。,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年

16、9月,template bool SingleList:Delete(int i) if ( !n ) coutn-1 ) cout *p=first,*q=first; for (int j=0; jlink;,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,if (i=0) first=first-link;/ 刪除頭結(jié)點(diǎn) else p=q-link; q-link=p-link; delete p; n-; return true; ,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,單鏈表運(yùn)算的優(yōu)缺點(diǎn) 優(yōu)點(diǎn) 單鏈表插入和刪除只需修改一兩個(gè)指針，無(wú)需移動(dòng)元素。如已知前驅(qū)結(jié)點(diǎn)，插入刪除運(yùn)算的

17、時(shí)間為O(1) 可以動(dòng)態(tài)分配結(jié)點(diǎn)空間，線性表的長(zhǎng)度只受內(nèi)存大小限制。 缺點(diǎn) 查找運(yùn)算費(fèi)時(shí)，只能順序查找，不能隨機(jī)查找,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,2.3.2 帶表頭結(jié)點(diǎn)的單鏈表,請(qǐng)區(qū)分“表頭結(jié)點(diǎn)”和“頭結(jié)點(diǎn)”,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,template HeaderList: HeaderList() Node *first=new Node; first-link=NULL; n=0; ,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,template bool HeaderList:Insert(int i, T x) if (in1) cout

18、*p=first; for (int j=0; jlink; Node * q=new Node; q-element=x; q-link=p-link; p-link=q; n+;return true; ,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,template bool HeaderList:Delete(int i) if ( !n ) coutn1 ) cout *q=first, *p; for (int j=0; jlink; p=q-link; q-link=p-link; delete p; n-; return true; ,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006

19、年9月,2.3.3 單循環(huán)鏈表,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,2.3.4 雙向鏈表,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,結(jié)點(diǎn)類 template class DoubleList;/超前聲明 template class DNode private: T element; DNode *lLink, *rLink; friend DoubleList; ;,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,插入操作的核心步驟如下： （1）DNode *q=new DNode; q-element=x; （2）q-lLink=p-lLink; q-rLink=p; p

20、-lLink-rLink=q; p-lLink=q;,錯(cuò)誤：p-lLink-rLink=q； q-lLink=p-lLink; q-rLink=p; p-lLink=q;,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,刪除操作的核心步驟如下： （1）p-lLink-rLink=p-rLink; p-rLink-lLink=p-lLink; （2）delete p;,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,2.4 多項(xiàng)式的算術(shù)運(yùn)算,多項(xiàng)式相加 p(x)=3x148x8+6x2+2 q(x)=2x10+4x86x2 q(x)p(x)+q(x) 結(jié)果：q(x) =3x14+2x104x8+

21、2,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,多項(xiàng)式的邏輯結(jié)構(gòu)：視為線性表 p(x)=3x14-8x8+6x2+2 數(shù)據(jù)元素 (coef,exp) 表示多項(xiàng)式項(xiàng) coefxexp ，coef是該項(xiàng)的系數(shù)，exp是變?cè)獂的指數(shù)。,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,多項(xiàng)式的存儲(chǔ)表示 p(x)=3x14-8x8+6x2+2 ( (3,14)，(-8,8)，(6,2)，(2,0) ) 順序表示 線性表長(zhǎng)度事先難以確定； 算術(shù)運(yùn)算需插入和刪除元素。,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,多項(xiàng)式的鏈接表示 多項(xiàng)式的項(xiàng),南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,2.4.1

22、項(xiàng)結(jié)點(diǎn)類,項(xiàng)結(jié)點(diǎn)類 Term* InsertAfter（int c,int e） 構(gòu)造一個(gè)新項(xiàng)（c,e）結(jié)點(diǎn)，插在*this項(xiàng)之后，函數(shù)返回新項(xiàng)結(jié)點(diǎn)的地址。,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,class Term public: Term(int c,int e); /構(gòu)造函數(shù)1 Term(int c,int e,Term* nxt); /構(gòu)造函數(shù)2 Term* InsertAfter(int c,int e); private: int coef; int exp; Term *link; friend ostream ,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,構(gòu)造函數(shù)

23、 Term:Term(int c,int e):coef(c),exp(e) link=0; Term:Term(int c,int e,Term *nxt):coef(c),exp(e) link=nxt; Term:Term(int c,int e) coef=c;exp=e; link=0; ,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,InsertAfter函數(shù)實(shí)現(xiàn) Term* Term:InsertAfter(int c,int e) link=new Term(c,e,link); return link; 調(diào)用語(yǔ)句：q=q-InsertAfter(c,e);,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,重載輸出運(yùn)算符 ostream ,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,2.4.3多項(xiàng)式的C+類,class Polynominal public: Polynominal(); Polynominal(); void AddTerms(istream /多項(xiàng)式相加 ,南京郵電大學(xué)計(jì)算機(jī)學(xué)院 陳慧南 2006年9月,private: Term* theList;/單循環(huán)鏈表的表頭指針 friend ostream ,南京郵