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

1、會計學(xué)1數(shù)據(jù)結(jié)構(gòu)與算法分析數(shù)據(jù)結(jié)構(gòu)與算法分析 線性表線性表本章重點難點第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類型的指針，存儲線性表實例 int maxSize; /實例的最大長度 int curLe

2、n; /實例的當(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)建順序表的實例 第5頁/共27頁增加一個元素 bool Append(const T value) aListposition=value; positio

3、n+; curLen+; 修改一個元素 bool Change(const int pos,const T value) aListpos=value;讀取一個元素 bool Read（const int pos) cout p; i-) aListi= aListi-1; aListp=value; curLen+; return true;刪除一個元素 bool Dele(const int p) int i; for(i=p;icurLen-1;i+) aListi=aListi+1; curLen-; return true;查找一個元素 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頁適合存儲靜態(tài)數(shù)據(jù)第7頁/共27頁第8頁/共27頁a3a2a4a1數(shù)據(jù)域指針域結(jié)點頭結(jié)點head頭結(jié)點作用：標(biāo)示一個鏈表；空表和非空表的處理統(tǒng)一；使表中第一個結(jié)點和其它位置上的結(jié)點操作一致第9頁/共27頁template class Linkpublic:T data; /結(jié)點的數(shù)據(jù)域Link * next; /結(jié)點的指針域Link( T in

5、fo, Link * nextValue= NULL)/具有兩個參數(shù)的List構(gòu)造函數(shù) data =info; next =nextValue;Link( Link * nextValue=NULL)/具有一個參數(shù)的List構(gòu)造函數(shù) next =nextValue; ;第10頁/共27頁template class linkList :public Link /繼承結(jié)點類private:Link * head; /定義頭指針int len; /存儲鏈表的長度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é)點的數(shù)據(jù)域doubleLink * next; /結(jié)點的后繼指針doubleLink * pre; /結(jié)點的前驅(qū)doubleLink( T info, doubleLink * nextValue= NULL， doubleLink * preValue= NULL ) /具有三個參數(shù)的List構(gòu)造函數(shù)data =info; next =nextValue; pre = preValue；doubleLink(doubleLink * nextValue=NULL ，

9、 doubleLink * preValue= NULL ) /具有兩個參數(shù)的List構(gòu)造函數(shù)next =nextValue; pre = preValue； ;第19頁/共27頁template class doubleList :public doubleLink /繼承結(jié)點類private:doubleLink * head; /定義頭指針int len; /存儲鏈表的長度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