数据结构与算法分析 线性表PPT学习教案

1、会计学1数据结构与算法分析数据结构与算法分析 线性表线性表本章重点难点第1页/共27页第2页/共27页第3页/共27页Tempate Class CList void Clear(); bool Append(const T value); bool Delete(const int p);.;模板是c+的软件复用的功能之一，此处定义的是模板类T通常是代表要处理的数据元素的类型第4页/共27页Tempate Class CarrList：public CList private: T *aList; /T类型的指针，存储线性表实例 int maxSize; /实例的最大长度 int curLe

2、n; /实例的当前长度 int position; / 当前处理位置 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+; ;创建顺序表的实例 第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页适合存储静态数据第7页/共27页第8页/共27页a3a2a4a1数据域指针域结点头结点head头结点作用：标示一个链表；空表和非空表的处理统一；使表中第一个结点和其它位置上的结点操作一致第9页/共27页template class Linkpublic:T data; /结点的数据域Link * next; /结点的指针域Link( T in

5、fo, Link * nextValue= NULL)/具有两个参数的List构造函数 data =info; next =nextValue;Link( Link * nextValue=NULL)/具有一个参数的List构造函数 next =nextValue; ;第10页/共27页template class linkList :public Link /继承结点类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后继指针前驱指针head第18页/共27页template class doubleLinkpublic:T data; /结点的数据域doubleLink * next; /结点的后继指针doubleLink * pre; /结点的前驱doubleLink( T info, doubleLink * nextValue= NULL， doubleLink * preValue= NULL ) /具有三个参数的List构造函数data =info; next =nextValue; pre = preValue；doubleLink(doubleLink * nextValue=NULL ，

9、 doubleLink * preValue= NULL ) /具有两个参数的List构造函数next =nextValue; pre = preValue； ;第19页/共27页template class doubleList :public doubleLink /继承结点类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