數(shù)據(jù)結(jié)構(gòu)與算法分析 線性表PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1數(shù)據(jù)結(jié)構(gòu)與算法分析數(shù)據(jù)結(jié)構(gòu)與算法分析 線性表線性表本章重點(diǎn)難點(diǎn)第1頁/共27頁第2頁/共27頁第3頁/共27頁Tempate Class CList void Clear(); bool Append(const T value); bool Delete(const int p);.;模板是c+的軟件復(fù)用的功能之一，此處定義的是模板類T通常是代表要處理的數(shù)據(jù)元素的類型第4頁/共27頁Tempate Class CarrList：public CList private: T *aList; /T類型的指針，存儲(chǔ)線性表實(shí)例 int maxSize; /實(shí)例的最大長度 int curLe

2、n; /實(shí)例的當(dāng)前長度 int position; / 當(dāng)前處理位置 public: CarrList(const int size) maxSize = size; aList = new TmaxSize; curLen = position=0; CarrList() delete aList; bool Append(const T value) aListposition=value; position+; curLen+; ;創(chuàng)建順序表的實(shí)例 第5頁/共27頁增加一個(gè)元素 bool Append(const T value) aListposition=value; positio

3、n+; curLen+; 修改一個(gè)元素 bool Change(const int pos,const T value) aListpos=value;讀取一個(gè)元素 bool Read（const int pos) cout p; i-) aListi= aListi-1; aListp=value; curLen+; return true;刪除一個(gè)元素 bool Dele(const int p) int i; for(i=p;icurLen-1;i+) aListi=aListi+1; curLen-; return true;查找一個(gè)元素 bool Find(int &p,co

4、nst T value) int i;for(i=0;icurLen;i+)if(value=aListi) p=i; return true;coutthe value is not in the list.n;return false;第6頁/共27頁適合存儲(chǔ)靜態(tài)數(shù)據(jù)第7頁/共27頁第8頁/共27頁a3a2a4a1數(shù)據(jù)域指針域結(jié)點(diǎn)頭結(jié)點(diǎn)head頭結(jié)點(diǎn)作用：標(biāo)示一個(gè)鏈表；空表和非空表的處理統(tǒng)一；使表中第一個(gè)結(jié)點(diǎn)和其它位置上的結(jié)點(diǎn)操作一致第9頁/共27頁template class Linkpublic:T data; /結(jié)點(diǎn)的數(shù)據(jù)域Link * next; /結(jié)點(diǎn)的指針域Link( T in

5、fo, Link * nextValue= NULL)/具有兩個(gè)參數(shù)的List構(gòu)造函數(shù) data =info; next =nextValue;Link( Link * nextValue=NULL)/具有一個(gè)參數(shù)的List構(gòu)造函數(shù) next =nextValue; ;第10頁/共27頁template class linkList :public Link /繼承結(jié)點(diǎn)類private:Link * head; /定義頭指針int len; /存儲(chǔ)鏈表的長度public:linkList( ) head= new Link ( ); len=0; linkList( ) Link *p; wh

6、ile(head!=NULL) p=head; head=head-next; delete p; ；第11頁/共27頁head1P-next = head-nextHead-next = phead12132112312last-next = pp-next = NULL第12頁/共27頁headpre-next = dele-nextDelete dele31pre2dele第13頁/共27頁headP-next = pre -nextpre-next = p31pre24p第14頁/共27頁void Append( T value) Link *p=new Link(value); Li

7、nk *q=head;while(q-next!=NULL)q=q-next; q-next=p;len+;第15頁/共27頁void Show()/顯示鏈表 Link *p=head-next; while(p!=NULL) coutdata ; p=p-next; coutNULLlen)coutthe position is not illegal!;return false;int i; Link *p=head,*q;q=new Link(d);for(i=0;inext;q-next=p-next;p-next=q;len+;return true;第17頁/共27頁a3a1a4a

8、2后繼指針前驅(qū)指針head第18頁/共27頁template class doubleLinkpublic:T data; /結(jié)點(diǎn)的數(shù)據(jù)域doubleLink * next; /結(jié)點(diǎn)的后繼指針doubleLink * pre; /結(jié)點(diǎn)的前驅(qū)doubleLink( T info, doubleLink * nextValue= NULL， doubleLink * preValue= NULL ) /具有三個(gè)參數(shù)的List構(gòu)造函數(shù)data =info; next =nextValue; pre = preValue；doubleLink(doubleLink * nextValue=NULL ，

9、 doubleLink * preValue= NULL ) /具有兩個(gè)參數(shù)的List構(gòu)造函數(shù)next =nextValue; pre = preValue； ;第19頁/共27頁template class doubleList :public doubleLink /繼承結(jié)點(diǎn)類private:doubleLink * head; /定義頭指針int len; /存儲(chǔ)鏈表的長度public:doubleList( ) head= new doubleLink ; len=0; linkList( ) Link *p; while(head!=NULL) p=head; head=head-next; delete p; ；第20頁/共27頁headP-next = head-nextHead -next-pre=pHead-next = pP-pre=head;head321123last-next = pp-pre=last第21頁/共27頁headp-next-pre = p-preP-pre-next=p-nextDelete p312 p第22