数据结第一部分

《数据结第一部分》由会员分享，可在线阅读，更多相关《数据结第一部分（272页珍藏版）》请在装配图网上搜索。

1、1第一部分第一部分 线性表线性表 具有线性关系的数据集合的处理具有线性关系的数据集合的处理 包括三部分内容包括三部分内容 线性表线性表 栈栈 队列队列2第二章第二章 线性表线性表 线性表的概念线性表的概念 线性表的实现线性表的实现 线性表类的实现线性表类的实现 STL中线性表的实现中线性表的实现3线性表的概念线性表的概念 线性表是线性表是N N个具有相同特征的结点个具有相同特征的结点A A0 0,A,A1 1,A,AN-1N-1构成的集合。在这个集合中，除了构成的集合。在这个集合中，除了A A0 0 和和A AN-1N-1 外，外，每个元素都有唯一的前趋和后继。对于每个每个元素都有唯一的前趋和

2、后继。对于每个A Ai i，它，它的前驱是的前驱是A Ai-1i-1，它的后继是，它的后继是A Ai+1i+1。A A0 0只有后继没有前只有后继没有前驱，驱，A AN-1N-1只有前驱没有后继。只有前驱没有后继。表的术语：表的术语：N N为表的大小为表的大小A A0 0称为首结点，称为首结点，A AN-1N-1称为尾结点称为尾结点空表：元素个数为零的表。空表：元素个数为零的表。位置：元素位置：元素A Ai i在表中的位置为在表中的位置为i i4表的基本操作表的基本操作 创建一个线性表创建一个线性表create()create()：创建一个空的线性表：创建一个空的线性表;清除一个线性表清除一个

3、线性表clear()clear()：删除线性表中的所有数：删除线性表中的所有数据元素；据元素；求线性表的长度求线性表的长度length()length()：返回线性表的长度：返回线性表的长度;在第在第i i个位置插入一个元素个位置插入一个元素insert(iinsert(i,x),x)：使线性：使线性表从（表从（a a0 0,a,a1 1,a ai-1i-1,a,ai i,a an-1n-1）变成）变成（a a0 0,a,a1 1,a ai-1i-1,x x,a,ai i,a an-1n-1），参数），参数i i的合法取值的合法取值范围是范围是0 0到到n n；5 删除第删除第i i个位置的元

4、素个位置的元素removeremove（i i）：使线性表从）：使线性表从（a a0 0,a,a1 1,a ai-1i-1,a,ai i,a,ai+1i+1 a an-1n-1）变成（）变成（a a0 0,a,a1 1,a ai-1i-1,a ai+1 i+1,a an-1n-1），参数），参数i i的合法取值范围是的合法取值范围是0 0到到n-1;n-1;搜索某个元素在线性表中是否出现搜索某个元素在线性表中是否出现search(xsearch(x)：在：在线性表中搜索线性表中搜索x x是否出现，并返回是否出现，并返回x x的位置的位置;访问线性表的第访问线性表的第i i个元素个元素visit

5、visit（i i）：返回线性表）：返回线性表中第中第i i个数据元素的值个数据元素的值;遍历线性表运算遍历线性表运算traverse()traverse()：按序访问线性表的每：按序访问线性表的每一数据元素。一数据元素。6第二章第二章 线性表线性表 线性表的概念线性表的概念 线性表的实现线性表的实现 线性表类的实现线性表类的实现 STL中线性表的实现中线性表的实现7线性表的实现线性表的实现 线性表的顺序实现线性表的顺序实现 线性表的链接实现线性表的链接实现8线性表的顺序存储结构线性表的顺序存储结构 线性表中结点存放在存储器上一块连续的线性表中结点存放在存储器上一块连续的空间中。空间中。借助存

6、储空间的连续性，结点可以按照其借助存储空间的连续性，结点可以按照其逻辑顺序依次存放。逻辑顺序依次存放。结点存放的物理位置和它的逻辑位置是一结点存放的物理位置和它的逻辑位置是一致的。致的。线性表的顺序实现通常称为顺序表。线性表的顺序实现通常称为顺序表。9线性表的顺序存储线性表的顺序存储 在程序设计语言中，一块连续的存储空间可以用一在程序设计语言中，一块连续的存储空间可以用一个数组实现。由于线性表中的元素个数是动态的，个数组实现。由于线性表中的元素个数是动态的，因此采用了动态数组。因此采用了动态数组。保存一个动态数组，需要两个变量：指向线性表元保存一个动态数组，需要两个变量：指向线性表元素类型的指

7、针，数组规模（容量），数组中的元素素类型的指针，数组规模（容量），数组中的元素个数（表长）。个数（表长）。线性表必须支持插入或删除，在申请空间时要留有线性表必须支持插入或删除，在申请空间时要留有余地。余地。一般要比实际元素个数多一点一般要比实际元素个数多一点。anan-1a2a1a0maxSizelengthdata10顺序表的运算实现顺序表的运算实现 length()length()：只需要返回：只需要返回lengthlength的值的值 visitvisit（i i）：返回）：返回dataidatai 的值的值 traverse()traverse()：输出数组：输出数组datadata的

8、前的前lengthlength个元素个元素 clear()clear()：只要将：只要将lengthlength置为置为0 0即可即可 create(maxSizecreate(maxSize)：申请一个：申请一个maxSizemaxSize大大小的动态数组小的动态数组11search 运算的实现运算的实现int search(x)for(num=0;num=i;-j)dataj+1=dataj;datai=x;+length;14resize 操作的实现操作的实现 resizeresize操作按一定的比例扩大数组的空间，操作按一定的比例扩大数组的空间，常用的比例是扩大一倍。常用的比例是扩大一

9、倍。数组空间在内存中必须是连续的，因此，扩数组空间在内存中必须是连续的，因此，扩大数组空间的操作必须重新申请一个更大规大数组空间的操作必须重新申请一个更大规模的动态数组，将原有数组的内容拷贝到新模的动态数组，将原有数组的内容拷贝到新数组中，释放原有数组空间，将新数组作为数组中，释放原有数组空间，将新数组作为存储线性表的存储区。存储线性表的存储区。15a0a1 an-1andatatmp16remove（i）运算的实现运算的实现anai+1aia1a0void remove(i)for(j=i;j length-1;+j)dataj=dataj+1;-length;17顺序实现的算法分析顺序实现

10、的算法分析 length,visitlength,visit和和clearclear的实现与表中的元素个数无的实现与表中的元素个数无关，因此它们的时间复杂度是关，因此它们的时间复杂度是O O（1 1）。）。traverse()traverse()操作遍历整个表中的所有元素，因此时操作遍历整个表中的所有元素，因此时间复杂度为间复杂度为O(nO(n)。createcreate操作需要申请一块动态数组的空间，并设表操作需要申请一块动态数组的空间，并设表为空。因此也是为空。因此也是O(1)O(1)的时间复杂度。的时间复杂度。插入操作，需要移动结点。当插入操作，需要移动结点。当i i等于等于n n时，移

11、动次数时，移动次数为为0 0。当。当i i等于等于0 0时，移动次数为时，移动次数为n n。最好情况下的时间复杂度为最好情况下的时间复杂度为O(1)O(1)最坏情况下的时间复杂度为最坏情况下的时间复杂度为O(nO(n)平均的时间复杂度：如果在每个位置上的插入都是等概平均的时间复杂度：如果在每个位置上的插入都是等概率的，则插入算法的平均时间复杂度为率的，则插入算法的平均时间复杂度为n/2n/22)(110ninnni2)(110ninnni18线性表的顺序实现总结线性表的顺序实现总结 由于要保持逻辑次序和物理次序的一致性，由于要保持逻辑次序和物理次序的一致性，顺序表在插入删除时需要移动大量的数据

12、，顺序表在插入删除时需要移动大量的数据，性能不太理想。性能不太理想。由于逻辑次序和物理次序的一致性使得定由于逻辑次序和物理次序的一致性使得定位访问的性能很好。位访问的性能很好。顺序表比较适合静态的、经常做定位访问顺序表比较适合静态的、经常做定位访问的线性表。的线性表。19表的实现表的实现 线性表的顺序实现线性表的顺序实现 线性表的链接实现线性表的链接实现20线性表的链接存储结构线性表的链接存储结构 将每个结点放在一个独立的存储单元中，将每个结点放在一个独立的存储单元中，结点间的逻辑关系依靠存储单元中附加的结点间的逻辑关系依靠存储单元中附加的值针来给出。值针来给出。结点的存储单元在物理位置上可以

13、相邻，结点的存储单元在物理位置上可以相邻，也可以不相邻。也可以不相邻。21线性表的链接存储线性表的链接存储 单链表单链表 双链表双链表 循环链表循环链表22单链表单链表 每个结点附加了一个指针字段，如每个结点附加了一个指针字段，如nextnext，该指针指向它的直接后继结点，最后一个该指针指向它的直接后继结点，最后一个结点的结点的nextnext字段为空。字段为空。nilhead23insertai+1aixp24头结点头结点、头指针、头指针 为了消除特殊情况，通常在表头额外增加一为了消除特殊情况，通常在表头额外增加一个相同类型的特殊结点，称之为头结点。它个相同类型的特殊结点，称之为头结点。它

14、们不是线性表中的组成部分。们不是线性表中的组成部分。头结点的出现，使得在表头位置上进行插入头结点的出现，使得在表头位置上进行插入和删除和在其它结点位置上是完全一致的，和删除和在其它结点位置上是完全一致的，从而使得插入和删除算法得到简化。从而使得插入和删除算法得到简化。25带头结点的单链表带头结点的单链表a0a1an-1head26Create函数的实现函数的实现 申请一块存储结点的空间，设结点的指针申请一块存储结点的空间，设结点的指针部分为空指针。部分为空指针。将结点地址存入代表单链表的变量将结点地址存入代表单链表的变量headhead。head27清除一个线性表清除一个线性表clear()把

15、所有结点的空间还给系统把所有结点的空间还给系统 ，把头结点的，把头结点的指针部分置为空指针指针部分置为空指针 void clear()void clear()p=p=头结点的直接后继；头结点的直接后继；While(p!=While(p!=空指针空指针)q=p;p=p q=p;p=p的直接后继地址；的直接后继地址；释放释放q q的空间；的空间；头结点的后继指针置为空指针；头结点的后继指针置为空指针；28求表的长度求表的长度length()方法方法1 1：从起始结点开始，沿着后继指针链一：从起始结点开始，沿着后继指针链一个一个往后数，数到一个结点，长度加个一个往后数，数到一个结点，长度加1 1 i

16、ntint length()length()len len=0;=0;p=p=头结点的直接后继；头结点的直接后继；While(p!=While(p!=空指针空指针)+len +len;p=p;p=p的直接后继的地址；的直接后继的地址；方法方法2 2：用空间换取时间的方法。在保存单链：用空间换取时间的方法。在保存单链表的时候增加一个变量，保存表的长度表的时候增加一个变量，保存表的长度 29在第在第i个位置插入一个元素个位置插入一个元素insert(i,x)void insert(i,x)for(j=0,p=head;j i;+j)p=p的直接后继的地址；的直接后继的地址；tmp=new 结点；结

17、点；tmp指向的结点的数据部分指向的结点的数据部分=x；tmp指向的结点的指针部分指向的结点的指针部分=p的直接后继的地址；的直接后继的地址；p指向的结点的指针部分指向的结点的指针部分=tmp；30删除第删除第i个位置的元素个位置的元素remove（i）void remove(i)for(j=0,p=head;j i;+j)p=p的直接后继的地址；的直接后继的地址；tmp=p的直接后继的地址；的直接后继的地址；p的指针部分的指针部分=tmp的直接后继的地址；的直接后继的地址；delete tmp；31搜索某个元素在线性表中是否出现搜索某个元素在线性表中是否出现int search(xint s

18、earch(x)num=0;num=0;p=p=头结点的直接后继；头结点的直接后继；while(p!=while(p!=空指针空指针&p&p的数据部分的数据部分 ！=x)=x)+num;p=p +num;p=p的直接后继的地址；的直接后继的地址；if if（p=p=空指针）空指针）num=-1num=-1；return num;return num;32访问线性表的第访问线性表的第i个元素个元素visit（i）dataType visit(i)for(j=0,p=head;j i;+j)p=p的直接后继的地址；的直接后继的地址；return p指向的结点的数据部分；指向的结点的数据部分；33遍

19、历运算遍历运算traverse()void traverse()void traverse()p=p=头结点的直接后继；头结点的直接后继；While(p!=While(p!=空指针空指针)cout cout p p指向结点的数据部分；指向结点的数据部分；p=pp=p的直接后继的地址；的直接后继的地址；34线性表的链接存储线性表的链接存储 单链表单链表 双链表双链表 循环链表循环链表35双链表双链表 每个结点附加了两个指针字段，如每个结点附加了两个指针字段，如priorprior和和nextnext priorprior字段给出直接前驱结点的地址字段给出直接前驱结点的地址 nextnext给出直

20、接后继结点的地址。给出直接后继结点的地址。36双链表的头尾节点双链表的头尾节点 为了消除在表头、表尾插入删除的特殊情况，通常为了消除在表头、表尾插入删除的特殊情况，通常双链表设一头结点，设一尾节点双链表设一头结点，设一尾节点 头结点中头结点中priorprior字段为空，它的字段为空，它的nextnext字段给出线性字段给出线性表中的首结点的地址表中的首结点的地址 尾结点中尾结点中nextnext字段为空，它的字段为空，它的priorprior字段给出线性字段给出线性表中最后一个节点的地址表中最后一个节点的地址headtail37create运算运算 创建一个双链表就是创建一个只有头尾结创建一

21、个双链表就是创建一个只有头尾结点的链表，把头结点的地址保存在点的链表，把头结点的地址保存在headhead中，中，尾结点的地址保存在尾结点的地址保存在tailtail中中 headtail38insertxp39removexp40线性表的链接存储线性表的链接存储 单链表单链表 双链表双链表 循环链表循环链表41单循环链表单循环链表 一般单循环链表不带头结点一般单循环链表不带头结点head42双循环链表双循环链表 头结点中头结点中priorprior字段给出尾结点的地址，字段给出尾结点的地址，尾结点中尾结点中nextnext字段给出头结点的地址字段给出头结点的地址 一般也不设头尾结点一般也不设

22、头尾结点43第二章第二章 线性表线性表 线性表的概念线性表的概念 线性表的实现线性表的实现 线性表类的实现线性表类的实现 STL中线性表的实现中线性表的实现44线性表类的实现线性表类的实现 线性表抽象类线性表抽象类 顺序表类顺序表类 双链表类双链表类45线性表的抽象类线性表的抽象类 线性表的抽象类是一个类模板线性表的抽象类是一个类模板 抽象类包括了除抽象类包括了除createcreate运算以外的所有运算以外的所有运算。运算。createcreate运算由每个线性表类的构运算由每个线性表类的构造函数完成造函数完成 增加了一个虚析构函数，以防内存泄漏增加了一个虚析构函数，以防内存泄漏46线性表的

23、抽象类线性表的抽象类template class list public:virtual void clear()=0;virtual int length()const=0;virtual void insert(int i,const elemType&x)=0;virtual void remove(int i)=0;virtual int search(const elemType&x)const=0;virtual elemType visit(int i)const=0;virtual void traverse()const=0 virtual list();47线性表类的实现线

24、性表类的实现 线性表抽象类线性表抽象类 顺序表类顺序表类 双链表类双链表类48顺序表类的定义顺序表类的定义class OutOfBound;class IllegalSize;template class seqList:public list private:elemType*data;int currentLength;int maxSize;void doubleSpace();49public:seqList(int initSize=10);seqList()delete data;void clear()currentLength=0;int length()const retur

25、n currentLength;void insert(int i,const elemType&x);void remove(int i);int search(const elemType&x)const;elemType visit(int i)const;void traverse()const;50构造函数构造函数template seqList:seqList(int initSize)if(initSize=0)throw IllegalSize();data=new elemTypeinitSize;maxSize=initSize;currentLength=0;maxSiz

26、elength51inserttemplate void seqList:insert(int i,const elemType&x)if(i currentLength)throw OutOfBound();if(currentLength=maxSize)doubleSpace();for(int j=currentLength;j i;j-)dataj=dataj-1;datai=x;+currentLength;52removetemplate void seqList:remove(int i)if(i currentLength-1)throw OutOfBound();for(i

27、nt j=i;j currentLength-1;j+)dataj=dataj+1;-currentLength;53doubleSpacetemplate void seqList:doubleSpace()elemType*tmp=data;maxSize*=2;data=new elemTypemaxSize;for(int i=0;i currentLength;+i)datai=tmpi;delete tmp;54其他函数其他函数 自己实现自己实现55线性表类的实现线性表类的实现 线性表抽象类线性表抽象类 顺序表类顺序表类 双链表类双链表类56链表类的设计链表类的设计 以双链表为例以

28、双链表为例 链表类的数据成员：头指针、尾指针，以及链表类的数据成员：头指针、尾指针，以及为了提高时间性能而设置的数据成员为了提高时间性能而设置的数据成员currentLength 链表类必须实现线性表的所有操作。为保证链表类必须实现线性表的所有操作。为保证这一点，链表类从线性表的抽象类继承。这一点，链表类从线性表的抽象类继承。链表的插入、删除操作都需要将指针移到被链表的插入、删除操作都需要将指针移到被操作结点。特设计函数操作结点。特设计函数move实现实现57结点及其组成结点及其组成 链表中的结点包含三部分：数据字段、前趋指针和链表中的结点包含三部分：数据字段、前趋指针和后继指针字段。后继指针

29、字段。数据字段可以是任何类型的数据，这里仍然用数据字段可以是任何类型的数据，这里仍然用ElemTypeElemType表示；指针字段用于存放其他相关结点的表示；指针字段用于存放其他相关结点的地址值。地址值。由于结点类型是链表专用的，因此可设为内嵌类。由于结点类型是链表专用的，因此可设为内嵌类。由于链表的操作是通过对结点的操作实现的，于是由于链表的操作是通过对结点的操作实现的，于是把结点类定义成把结点类定义成structstruct，以方便链表类访问。，以方便链表类访问。58双链表类的定义双链表类的定义template class linkList:public list private:str

30、uct node elemType data;node*prev,*next;node(const elemType&x,node*p=NULL,node*n=NULL)data=x;next=n;prev=p;node():next(NULL),prev(NULL)node();node *head,*tail;int currentLength;node*move(int i)const;59public:linkList();linkList()clear();delete head;delete tail;void clear();int length()const return cu

31、rrentLength;void insert(int i,const elemType&x);void remove(int i);int search(const elemType&x)const ;elemType visit(int i)const;void traverse()const;60构造函数构造函数template linkList:linkList()head=new node;head-next=tail=new node;tail-prev=head;currentLength=0;headtail61cleartemplate void linkList:clear

32、()node *p=head-next,*q;head-next=tail;tail-prev=head;while(p!=tail)q=p-next;delete p;p=q;currentLength=0;62movetemplate linkList:node*linkList:move(int i)const node*p=head-next;if(i currentLength)throw OutOfBound();while(i-)p=p-next;return p;63template void linkList:insert(int i,const elemType&x)nod

33、e*pos,*tmp;pos=move(i);tmp=new node(x,pos-prev,pos);pos-prev-next=tmp;pos-prev=tmp;+currentLength;insertposxtmp64removetemplate void linkList:remove(int i)node*pos;pos=move(i);pos-prev-next=pos-next;pos-next-prev=pos-prev;delete pos;-currentLength;xpospos65searchtemplate int linkList:search(const el

34、emType&x)const node*p=head-next;int i=0;while(p!=tail&p-data!=x)p=p-next;+i;if(p=tail)return-1;else return i;66visittemplate elemType linkList:visit(int i)const node*p=move(i);return p-data;67traversetemplate void linkList:traverse()constnode*p=head-next;cout endl;while(p!=tail)cout data next;cout e

35、ndl;68缺点缺点 双链表类仅实现了线性表的基本运算，双链表类仅实现了线性表的基本运算，并没有用到双链表的特点，如逆向查找并没有用到双链表的特点，如逆向查找等等 69第二章第二章 线性表线性表 表的概念表的概念 表的实现表的实现 线性表类的实现线性表类的实现 STL中表的实现中表的实现70STLSTLSTL（标准模版库）是（标准模版库）是C+C+中数据结构的中数据结构的实现。这些数据结构被称为集合或容器。实现。这些数据结构被称为集合或容器。STLSTL中线性表的实现有两种：中线性表的实现有两种：vectorvector：线性表的顺序实现：线性表的顺序实现 listlist：线性表的双链表的实

36、现：线性表的双链表的实现71vector和和list 共同支持的操作共同支持的操作所有的容器都支持的整体操作：求规模、清所有的容器都支持的整体操作：求规模、清空和判空空和判空在表尾的插入和删除以及取表头表尾元素在表尾的插入和删除以及取表头表尾元素 listlist特有的操作：表头的插入和删除特有的操作：表头的插入和删除 vectorvector特有的操作：特有的操作：的重载，按下标取的重载，按下标取元素，求容量，重新设置数组的大小。元素，求容量，重新设置数组的大小。迭代器：两者都能用迭代器访问迭代器：两者都能用迭代器访问72STL中的迭代器操作中的迭代器操作 获取一个迭代器：获取一个迭代器：b

37、eginbegin：返回一个指向第一个节点的迭代器：返回一个指向第一个节点的迭代器endend：返回一个指向最后一个节点的迭代器：返回一个指向最后一个节点的迭代器 迭代器本身的方法：向后移动，取迭代器指向的迭代器本身的方法：向后移动，取迭代器指向的元素值，判迭代器相等和不相等元素值，判迭代器相等和不相等 需要迭代器的容器操作：需要迭代器的容器操作：在指定位置上插入一元素在指定位置上插入一元素删除指定位置的元素删除指定位置的元素删除指定位置之间的所有元素删除指定位置之间的所有元素73STL中线性表的实现中线性表的实现 vectorvector：线性表的顺序实现，：线性表的顺序实现，且大小可增长且

38、大小可增长 listlist：线性表的双链表实现：线性表的双链表实现74vector的特性的特性 vectorvector维护一个维护一个C+C+的原始数组、容量及大小规模的原始数组、容量及大小规模 提供拷贝构造函数和赋值运算符的重载函数，实提供拷贝构造函数和赋值运算符的重载函数，实现了对数组的整体操作现了对数组的整体操作 可以修改数组的容量可以修改数组的容量 提供提供运算符重载运算符重载 提供了一个内嵌的迭代器提供了一个内嵌的迭代器 头文件：头文件：vectorvector75vector的定义的定义template class vector private:int theSize;int

39、theCapacity;object *objects;public:enum SPARE_CAPACITY=16;76explicit vector(int initSize=0);vector(const Vector&R);vector();const vector&operator=(const Vector&R);void resize(int newsize);/重新设置表的大小重新设置表的大小void reserve(int newCapacity);/重新设置数组的容量重新设置数组的容量/重载重载object&operator(int index);const object&o

40、perator(int index)const;不允许隐式转换不允许隐式转换77 bool empty()const;int size()const;int capacity()const;/对数据元素的操作对数据元素的操作 void push_back(const object&x);/添加在表尾添加在表尾 void pop_back();/删除表尾元素删除表尾元素 const object&back()const;/返回表尾元素的值返回表尾元素的值78/迭代器操作迭代器操作typedef object*iterator;typedef const object*const_iterator

41、;iterator begin();/返回元素返回元素0的地址的地址const_iterator begin()const;/返回元素返回元素0的地址的地址iterator end();/指向最后一个元素的地址指向最后一个元素的地址const_iterator end()const;/指向最后一个元素的地址指向最后一个元素的地址;79vector的使用的使用#include#include using namespace std;int main()vector v;cout the initial size of v is:v.size()n the initial capacity of

42、v is:v.capacity()endl;80v.push_back(2);cout n after push 2,capacity of v is:v.capacity()endl;v.push_back(3);cout n after pust 3,capacity of v is:“v.capacity()endl;v.push_back(4);cout n after push 4,capacity of v is:“v.capacity()endl;coutn the size of v is:v.size()n the capacity of v is:“v.capacity()

43、endl;81 coutn contents of v using :;for(int i=0;iv.size();i+)cout vi ;cout endl;coutn contents of v using iterator notation:;vector:const_iterator p;for(p=v.begin();p!=v.end();p+)cout *p ;cout endl;82执行结果执行结果the initial size of v is:0the initial capacity of v is:0After push 2,capacity of v is:1After

44、 push 3,capacity of v is:2After push 4,capacity of v is:4the size of v is:3the capacity of v is:4contents of v using :2 3 4contents of v using iterator notation:2 3 483STL中表的实现中表的实现 vectorvector：线性表的顺序实现，：线性表的顺序实现，且大小可增长且大小可增长 listlist：线性表的双链表实现：线性表的双链表实现STLSTL（标准模版库）是（标准模版库）是C+C+中数据结构的实现。中数据结构的实现。8

45、4list的实现的实现采用了带头节点的双链表实现采用了带头节点的双链表实现headtail85list的功能的功能 允许在任何位置插入和删除允许在任何位置插入和删除 支持双向迭代器支持双向迭代器 头文件：头文件：list86list的定义的定义template class list private:struct node .;int the size;node*head,*tail;void init();87public:class const_iterator class iterator:public const_iterator list();list(const list&r);li

46、st();const list&operator=(const list&r);88/迭代器操作迭代器操作iterator begin();const_iterator begin()const;iterator end();const_iterator end()const;iterator insert(iterator itr,const Object&x)；iterator erase(iterator itr)；iterator erase(iterator start,iterator end)；89int size()const;bool empty()const;void cl

47、ear();object&front()；const object&front()const；object&back()；const object&back()const；void push_front(const object&x)；void push_back(const object&x)；void pop_front()；void pop_back()；;90list的应用的应用#include#include using namespace std;template void printall(const list&v);int main()list v1;v1.push_front

48、(1);v1.push_front(2);v1.push_back(4);v1.push_back(3);printall(v1);list:iterator itr=v1.begin(),itre=v1.end();for(int i=5;itr!=itre;+itr,+i)v1.insert(itr,i);printall(v1);return 0;contents of values is:2 1 4 3contents of values is:5 2 6 1 7 4 8 391template void printall(const list&v)if(v.empty()coutn

49、list is empty!;else list:const_iterator itr,itre;itr=v.begin();itre=v.end();do cout *itr ;+itr;while(itr!=itre);cout endl;92作业93第三章第三章 栈栈 栈的概念栈的概念 栈的顺序实现栈的顺序实现 栈的链接实现栈的链接实现 栈类的实现栈类的实现 STLSTL中的栈中的栈 栈的应用栈的应用94栈栈 后进先出后进先出(LIFO,Last In First Out)(LIFO,Last In First Out)或先或先进后出进后出(FILO,First In Last Out)

50、(FILO,First In Last Out)结构，结构，最先最先(晚晚)到达栈的结点将最晚到达栈的结点将最晚(先先)被删除。被删除。乒乓球进盒、乒乓球进盒、出盒出盒95相关概念相关概念an-1an-2a1a0出栈出栈进栈进栈栈底栈底栈顶栈顶96相关概念相关概念 栈底栈底(bottom)(bottom)：结构的首部：结构的首部(结点最早到结点最早到达的部分达的部分)栈顶（栈顶（toptop）：结构的尾部）：结构的尾部(结点最晚到达结点最晚到达的部分的部分)出栈（出栈（PopPop）：结点从栈顶删除）：结点从栈顶删除 进栈（进栈（PushPush）：结点在栈顶位置插入）：结点在栈顶位置插入 空

51、栈空栈 ：栈中结点个数为零时：栈中结点个数为零时97栈的运算栈的运算 创建一个栈创建一个栈create()create()：创建一个空的栈；：创建一个空的栈；进栈进栈push(xpush(x)：将：将x x插入栈中，使之成为栈顶元插入栈中，使之成为栈顶元素；素；出栈出栈pop()pop()：删除栈顶元素并返回栈顶元素值；：删除栈顶元素并返回栈顶元素值；读栈顶元素读栈顶元素top()top()：返回栈顶元素值但不删除栈：返回栈顶元素值但不删除栈顶元素；顶元素；判栈空判栈空isEmptyisEmpty()()：若栈为空，返回：若栈为空，返回truetrue，否则，否则返回返回falsefalse。

52、98第三章第三章 栈栈 栈的概念栈的概念 栈的顺序实现栈的顺序实现 栈的链接实现栈的链接实现 栈类的实现栈类的实现 STLSTL中的栈中的栈 栈的应用栈的应用99栈的顺序实现栈的顺序实现 用连续的空间存储栈中的结点，即数组用连续的空间存储栈中的结点，即数组 进栈和出栈总是在栈顶一端进行，不会引起类进栈和出栈总是在栈顶一端进行，不会引起类似顺序表中的大量数据的移动。用数组的后端似顺序表中的大量数据的移动。用数组的后端表示栈顶。表示栈顶。ana1a0top_p栈底maxSizeelem100顺序存储时的运算实现顺序存储时的运算实现 create()create()：按照用户估计的栈的规模申请一个动

53、态数：按照用户估计的栈的规模申请一个动态数组，将数组地址保存在组，将数组地址保存在datadata中，数组规模保存在中，数组规模保存在maxSizemaxSize中，并设中，并设top_ptop_p的值为的值为-1-1。push(xpush(x)：将：将top_ptop_p加加1 1，将，将x x放入放入top_ptop_p指出的位置中。指出的位置中。但要注意数组满的情况。但要注意数组满的情况。pop()pop()：返回：返回top_ptop_p指出的位置中的值并将指出的位置中的值并将top_ptop_p减减1 1。top()top()：与：与poppop类似，只是不需要将类似，只是不需要将t

54、op_ptop_p减减1 1。isEmptyisEmpty()()：若：若top_ptop_p的值为的值为-1-1，返回，返回truetrue，否则返回，否则返回falsefalse。101顺序实现性能分析顺序实现性能分析 除了进栈操作以外，所有运算实现的时间复杂度都除了进栈操作以外，所有运算实现的时间复杂度都是是O O（1 1）。）。进栈运算在最坏情况下的时间复杂度是进栈运算在最坏情况下的时间复杂度是O O（N N）。）。但最坏情况在但最坏情况在N N次进栈操作中至多出现一次。如果次进栈操作中至多出现一次。如果把扩展数组规模所需的时间均摊到每个插入操作，把扩展数组规模所需的时间均摊到每个插入

55、操作，每个插入只多了一个拷贝操作，因此从平均的意义每个插入只多了一个拷贝操作，因此从平均的意义上讲，插入运算还是常量的时间复杂度。这种分析上讲，插入运算还是常量的时间复杂度。这种分析方法称为均摊分析法。方法称为均摊分析法。102第三章第三章 栈栈 栈的概念栈的概念 栈的顺序实现栈的顺序实现 栈的链接实现栈的链接实现 栈类的实现栈类的实现 STLSTL中的栈中的栈 栈的应用栈的应用103栈的链接实现栈的链接实现 栈的操作都是在栈顶进行的，因此不需要栈的操作都是在栈顶进行的，因此不需要双链表，用单链表就足够了，而且不需要双链表，用单链表就足够了，而且不需要头结点头结点 对栈来讲，只需要考虑栈顶元素

56、的插入删对栈来讲，只需要考虑栈顶元素的插入删除。从栈的基本运算的实现方便性考虑，除。从栈的基本运算的实现方便性考虑，可将单链表的头指针指向栈顶。可将单链表的头指针指向栈顶。104栈的链接实现栈的链接实现an-1an-2a0top_p105链接存储时的运算实现链接存储时的运算实现 create()create()：将：将top_ptop_p设为空指针。设为空指针。push(xpush(x)：将：将x x插入到单链表的表头插入到单链表的表头void push(xvoid push(x)p=new p=new 结点；结点；p p指向的结点的数据部分指向的结点的数据部分 =x=x；p p指向的结点的指

57、针部分指向的结点的指针部分 =top_p=top_p；top_ptop_p=p;=p;106链接存储时的运算实现链接存储时的运算实现 pop()pop()：删除表头元素：删除表头元素dataTypedataType pop()pop()p=top_p p=top_p;top_p=top_p top_p=top_p指向的结点的指针部分；指向的结点的指针部分；x=px=p指向的结点的数据部分；指向的结点的数据部分；delete p;delete p;return x;return x;107链接存储时的运算实现链接存储时的运算实现 top()top()：返回：返回top_ptop_p指向的结点的值

58、。指向的结点的值。isEmptyisEmpty()()：若：若top_ptop_p的值为空指针，返的值为空指针，返回回truetrue，否则返回，否则返回falsefalse。108链接栈的性能分析链接栈的性能分析 由于所有的操作都是对栈顶的操作，邮由于所有的操作都是对栈顶的操作，邮展中的元素个数无关。所以，所有运算展中的元素个数无关。所以，所有运算的时间复杂度都是的时间复杂度都是O O（1 1）109第三章第三章 栈栈 栈的概念栈的概念 栈的顺序实现栈的顺序实现 栈的链接实现栈的链接实现 栈类的实现栈类的实现 STLSTL中的栈中的栈 栈的应用栈的应用110栈的抽象类栈的抽象类templat

59、e class stack public:virtual bool isEmpty()const=0;virtual void push(const elemType&x)=0;virtual elemType pop()=0;virtual elemType top()const=0;virtual stack();111顺序栈类顺序栈类template class seqStack:public stack private:elemType*elem;int top_p;int maxSize;void doubleSpace();112public:seqStack(int initSi

60、ze=10)elem=new elemTypeinitSize;maxSize=initSize;top_p=-1;seqStack()delete elem;bool isEmpty()const return top_p=-1;113 void push(const elemType&x)if(top_p=maxSize-1)doubleSpace();elem+top_p=x;elemType pop()return elemtop_p-;elemType top()const return elemtop_p;114doubleSpacetemplate void seqStack:d

61、oubleSpace()elemType*tmp=elem;elem=new elemType2*maxSize;for(int i=0;i maxSize;+i)elemi=tmpi;maxSize*=2;delete tmp;115链接栈类链接栈类template class linkStack:public stack private:struct node elemType data;node*next;node(const elemType&x,node*N=NULL)data=x;next=N;node():next(NULL)node();node*elem;116public:

62、linkStack()elem=NULL;linkStack();bool isEmpty()const return elem=NULL;void push(const elemType&x)node*tmp=new node(x,elem);elem=tmp;elemType pop()node*tmp=elem;elemType x=tmp-data;elem=elem-next;delete tmp;return x;elemType top()const return elem-data;117析构函数析构函数 template linkStack:linkStack()node*t

63、mp;while(elem!=NULL)tmp=elem;elem=elem-next;delete tmp;118第三章第三章 栈栈 栈的概念栈的概念 栈的顺序实现栈的顺序实现 栈的链接实现栈的链接实现 栈类的实现栈类的实现 STLSTL中的栈中的栈 栈的应用栈的应用119STLSTL中的栈中的栈 栈本质上是一个线性表，在栈本质上是一个线性表，在STLSTL中栈类是中栈类是借助于线性表类实现的。借助于线性表类实现的。STLSTL中的栈提供四个标准运算：中的栈提供四个标准运算：pushpush、poppop、toptop和和emptyempty。在在STLSTL中，借助于其他容器存储数据的容中

64、，借助于其他容器存储数据的容器称为容器适配器。栈就是一个容器适配器称为容器适配器。栈就是一个容器适配器器 120栈的类模板栈的类模板 定义一个栈对象要指明栈中元素的类型以及借定义一个栈对象要指明栈中元素的类型以及借助于哪一个容器，因此栈的类模板有两个模板助于哪一个容器，因此栈的类模板有两个模板参数：栈元素类型和所借助的容器类型。参数：栈元素类型和所借助的容器类型。栈可以借助的容器有栈可以借助的容器有vector,listvector,list和和dequedeque。栈的类模板的第二个参数带有缺省值栈的类模板的第二个参数带有缺省值dequedeque 四个标准运算分别通过调用四个标准运算分别通

65、过调用push_back,push_back,pop_backpop_back,back,back 和和 empty empty 实现实现121STL栈的使用栈的使用#include#include using namespace std;int main()stackint,vector s1;stackint,list s2;int i;for(i=0;i 10;+i)s1.push(i);while(!s1.empty()cout s1.top();s1.pop();cout endl;for(i=0;i 10;+i)s2.push(i);while(!s2.empty()cout s2

66、.top();s2.pop();cout=high)return;mid=divide(a,low,high);quicksort(a,low,mid-1);quicksort(a,mid+1,high);132划分过程 从右向左开始检查。如果high的值大于k，high减1，继续往前检查，直到遇到一个小于k的值。将小于k的这个值放入low的位置。然后从low位置开始从左向右检查，直到遇到一个大于k的值。将low位置的值放入high位置，重复第一步，直到low和high重叠。将k放入此位置。5730421968lowhighK=5133730421968lowhighk=5730421968lowhigh173042968lowhigh130427968lowhigh123047968lowhigh134divide函数int divide(int a,int low,int high)int k=alow;do while(low=k)-high;if(low high)alow=ahigh;+low;while(low high&alow=k)+low;if(low=high)re