第4章 链式存储结构的表、 堆栈和队列 4.1 链式存储结构 4.2 单链表 4.3 单循环链表 4.4 双向循环链表 4.5 链式堆栈 4.6 链式队列 4.7 链式存储结构的特点 4.8 应用问题的面向对象程序设计方法

4.1 链式存储结构 链式存储结构是计算机中的另一种最基本和最主要的数据存储结构。 和顺序存储结构不同， 初始时链式存储结构为空链， 每当有新的数据元素需要存储时用户向系统动态申请所需的存储空间插入链中。

new的语法格式是： 名字指针 = new 类型名(初始化值)。 其中， 初始化值可为空。 delete的语法格式是： delete 名字指针。在顺序存储结构中， 用户向系统申请一块地址连续的有限空间用于存储数据元素， 这样任意两个在逻辑上相邻的数据元素在物理上也必然相邻。

链式存储结构存储线性结构数据元素集合的方法是用结 点（Node）构造链。 线性结构数据元素的特点是：除第一个和最后一个元素外，每个元素只有一个惟一的前驱和一个惟一的后继。链式结构中每个结点除数据域外还有一个或一个以上的指针域，数据域用来存放数据元素，指针域用来构造数据元素之间的关系。只有一个指针域的结点结构如图4―1所示。

数据域 指针域 或 data next 图4―1 只有一个指针域的结点结构

根据指针域的不同和结点构造链的方法不同， 链式存储 结构存储线性结构数据元素的方法主要有单链、 单循环链和双向循环链等三种。 这三种结构中每一种又有带头结点结构和不带头结点结构两种。 头结点是指头指针所指的不存放数据元素的结点。 其中， 带头结点的链式结构在表的存储中更为常用， 不带头结点的链式结构在堆栈和队列的存储中更为常用。 图4―2、 图4―3和图4―4是单链、 单循环环和双向循环链的结构示意图。

我们把图中头结点的数据域部分涂上阴影， 以明显表示该结点为头结点。 图4―2和图4―3中的指针域为指向下一个结点的指针。 图4―4中结点右部的指针域为指向下一个结点的指针， 结点左部的指针域为指向上一个结点的指针。 在以后的图示中， 头指针将用head表示。 关于带头结点的链结构和不带头结点的链结构的差别我们将在4. 2节讨论。

图4―2 带头结点的单链结构 (a)空链； (b)非空链

图4―3 带头结点的单循环链结构 (a)空链； (b)非空链

图4―4 带头结点的双循环链结构 (a)空链； (b)非空链

图4―1中的符号“∧”表示空指针， 空指针在算法描述中用NULL表示。 空指针是一个特殊标识， 用来标识链的结束。 NULL在C++中宏定义为0， 因此空指针在C++中也就是0地址。 为与顺序表中数据元素从a0开始相一致， 本章讨论链表时数据元素也从a0开始。 链式存储结构也可以方便地存储非线性结构的数据元素。 链式存储结构存储非线性结构数据元素的最典型的例子是链式结构的二叉树。 链式存储结构存储非线性结构数据元素的方法见第7章和第8章。

4.2 单 链 表 单链表简称链表（Linked List）， 是表数据元素的单链结构存储。 链表是用一个一个的结点链接构成的， 每个结点的结构如图4―1所示。 假设我们用带头结点的单链表存储表数据元素， 则链表中一个元素也没有的空链表的结构如图4-2（a）所示。 设有表元素a0, a1, …, a n-1， 则在空链表中插入表元素a0, a1, …, a n-1后的结构如图4―2（b）所示。

从第3章表的定义我们知道， 表要求允许在任意位置进行插入和删除。 当选用带头结点的单链表时， 在第一个位置插入结点和在其他位置插入结点一样不会改变头指针head的值， 此时改变的是head→next的值， 其插入过程如图4―5所示； 在第一个位置删除结点和在其他位置删除结点一样也不会改变头指针head的值， 此时改变的也是head→next的值， 其删除过程如图4―6所示。 但若选用不带头结点的单链表时， 在第一个位置插入结点时头指针head的值将改变为等于新插入结点的指针s， 其插入过程如图4―7所示；

而在其他位置插入结点时头指针head的值不会改变， 改变的是p→next的值， 其插入过程如图4―8 所示。 不带头结点的单链表在第一个位置删除结点时头指针head的值将改变为等于head→next， 其删除过程如图4―9所示； 而在其他位置删除时头指针head的值将不会改变， 改变的是p→next的值， 其删除过程如图4―10所示。 因此， 单链表一般选用带头结点的单链表。

图4―5 带头结点单链表在第一个位置插入结点过程 （a）插入前； （b）插入后

图4―6 带头结点单链表在第一个位置删除结点过程

图4―7 不带头结点单链表在第一个位置插入结点过程 （a）插入前； （b）插入后

图4―8 不带头结点单链表在其他位置插入结点过程

图4―9 不带头结点单链表在第一个位置删除结点过程

图4―10 不带头结点单链表在其他位置删除结点过程

分析上述单链表结构可见， 单链表的基本组成部分是结点， 一个单链表可用该单链表头指针的头指针表示。 因此， 用面向对象的程序设计方法设计单链表时应先设计结点类， 结点类中的数据成员为结点的数据域和指针域， 成员函数为新建立一个结点；然后, 我们定义单链表类， 单链表类的数据成员为头指针， 其类型为结点类。 也就是说， 头指针是结点类的对象， 单链表类的成员函数主要还是表操作的方法。

4.2.1 结点类的定义和实现 在单链表中， 每个结点构成包括数据域和指针域两部分。 每个结点的基本操作包括初始化构造一个结点对象、 建立一个新结点、 给出当前结点的下一个结点指针等。 本章的类定义使用模板方法， 由于使用模板方法时用Datatype表示数据类型算法的一行太长， 所以在模板方法时我们用T表示数据类型。 模板方法的结点类的定义和实现如下：

＃include <iostream.h> ＃include <stdlib.h> template <class T> class LinList; //前视定义,否则友元无法定义 template <class T> class ListNode { friend class LinList<T>; //定义类LinList<T>为友元 private: ListNode<T> *next; //指向下一结点的指针

public: T data ; //定义为公有成员方便使用 //构造函数,用于构造头结点， 头结点无data域参数 ListNode(ListNode<T> *ptrNext = NULL);  //构造函数,主要用于构造非头结点的结点  ListNode(const T& item, ListNode<T> *ptrNext = NULL); ~ListNode(){}; //析构函数， 为空};

结点类的数据成员有data域和next域。 data域中存放了该结点的数据值， 由于应用问题中要使用链表中的data域值， 所以定义为公有数据成员可方便使用； next域定义为私有数据成员。 结点类的成员函数有两个不同参数的构造函数和一个空操作的析构函数。 析构函数为空是因为结点类的成员函数中没有用new函数向系统申请空间， 而结点对象本身分配的空间系统可自动识别释放。

结点类ListNode<T>的实现如下： template<class T>ListNode<T>::ListNode(Lis tNode<T> *ptrNext):next(ptrNext) //构造函数 {} template<class T>ListNode<T>::ListNode(const T &item, ListNode<T> *ptrNext) //构造函数{ data = item;next = ptrNext;}

由于定义了单链表类LinList<T>是链表结点类ListNode<T>的友元， 链表结点类ListNode<T>中的私有数据成员next可以被单链表类LinList<T>像使用自己的私有数据成员一样使用， 所以链表结点类ListNode<T>中不用再定义取next值的成员函数。

4.2.2 单链表类的定义和实现 单链表类定义和实现如下 template <class T> class LinList { private: ListNode<T> *head; //指向头结点的头指针 int size; //单链表的元素个数 ListNode<T> *currPtr; //当前结点指针 public: //构造函数和析构函数

LinList(void); //构造函数 //表操作的成员函数 int ListSize(void) const; //返回链表的元素个数 int ListEmpty(void) const; //链表空否： 空返回1; 否则返回0 ListNode<T> *Index(int pos); //返回指向第pos个结点的指针 //在第pos个结点前插入一个data域值为item的新结点 void Insert(const T& item, int pos);

T Delete(int pos); //删除第pos个结点并返回被删结点的data T GetData(int pos); //返回第pos个结点的data值 void ClearList(void); //清空表为初始化状态 //遍历链表的成员函数 ListNode<T> *Reset(int pos=0); //currPtr指向结点pos并返回currPtr ListNode<T> *Next(void); //currPtr指向下一个结点并返回currPtr int EndOfList(void) const; //currPtr==head否： 是返回1； 否返回0};

单链表类的数据成员有头指针、 元素个数和当前结点指针。 头指针指向头结点， 任何对单链表中结点的操作都要从头指针进入。 初始状态时结点个数为0。 当前结点指针是遍历链表成员函数使用的数据成员， 遍历链表成员函数通过控制当前结点指针值来遍历链表。

单链表类的成员函数有三组： 构造函数和析构函数、 表操作的成员函数和遍历链表的成员函数。 由于单链表类中的结点是通过new函数向系统申请的， 在释放单链表类对象时系统无法自动释放这些空间， 所以析构函数不能为空， 析构函数必须用delete函数逐个释放这些空间。 表操作成员函数是对表操作的基本成员函数， 这与顺序表类对表操作的成员函数意义相同， 但实现方法不同。 链表的遍历操作每次是寻找当前结点的下一个结点，

由于每次对链表类中结点的操作都要从头指针进入后寻找到相应结点后才可完成， 这样单链表类遍历操作的时间复杂度将会大大增加， 在单链表类中增加一组遍历链表的成员函数可使单链表类遍历操作的时间复杂度不增加， 其应用方法见4.2.3节的应用例子。 单链表类的实现如下： template不同之处是<class T>  LinList<T>::LinList() //构造函数 { head=newListNode<T>(); //头指针指向头结点 size=0;//定义size的初值为0，这样就和顺

序表一样从0 始 } template<classT> LinList<T>::~LinList(void) //析构函数 { ClearList(); //释放所有非头结点的结点 deletehead; //释放头结点 head=NULL; }template<classT>intLinList<T>::ListSize(void)const //返回链表的元素个数

{ returnsize; } template<classT>intLinList<T>::ListEmpty(void)const //链表空否：空返回1;否则返回0 if(size<=0)return1; elseretu rn0;}template<classT>ListNode<T>*LinList<T>::Index(intpos) //返回指向第pos个结点的指针 if(pos<-1||pos>size){cerr<<"参数pos越界出错！"<<endl; exit(1);

} if(pos==-1)return head; //pos为-1时返回头指针head ListNode<T>*p=head->next; //p指向第一个结点 inti=0; //从0开始计数 while(p!=NULL&&i<pos) //寻找第pos个结点 { p=p->next; i++; returnp; //返回第pos个结点指针

} template<classT> voidLinList<T>::Insert(constT&item,intpos) //在第pos个结点前插入一个data域值为item的新结点 { ListNode<T>*p=Index(pos-1); //p为指向第pos-1个结点指针 //构造新结点newNode，newNode的data域值为item，next域值为 p->nextListNode<T>*newNode=newListNode<T>(item,p->next);p->next =newNode; //新结点插入第pos个结点前 size++; //元素个数加1

} template<classT> TLinList<T>::Delete(intpos) //删除第pos个结点并返回被删结点的data { if(size==0) cerr<<"链表已空无元素可删！"<<endl; exit(1); ListNode<T>*q,*p=Index(pos-1); //p为指向第pos-1个结点指针 q=p→next; //q指向第pos个结点p→next=p->next ->next; //第pos个结点脱链

Tdata=q->data; deleteq; //释放第pos个结点空间 size--; //元素个数减1 Return data; //返回第pos个结点的data域值 } template<classT>TLinList<T>::GetData(intpos) //返回第pos个结点的data值 { ListNode<T>*p=Index(pos); //p指向第pos个结点

returnp->data; } template<classT>voidLinList<T>::ClearList(void) //清空表为初始化状态 { ListNode<T>*p,*p1;p=head->next; //p指向第一个结点 while(p!=NULL) //循环释放结点空间直至初始化状态 p1=p;p=p->nex t;deletep1; size=0; //元素个数置为初始化值0

} template<classT> ListNode<T>*LinList<T>::Reset(intpos) //currPtr指向结点pos并返回currPtr { if(head==NULL)returnNULL; if(pos<-1||pos>size) cerr<<"参数出错!"<<endl; exit(1); if(pos==-1)returnhead//pos为-1时返回头指head if(pos==0)currPtr=head->next;else //定位指针currPtr的值

currPtr=head->next; ListNode<T>prevPtr=head; for(inti=0;i<pos;i++) //循环定位currPtr指向结点pos { prevPtr=currPtr; currPtr=currPtr->next; } returncurrPtr; //返回currPtr template<classT>

ListNode<T>*LinLis t<T>::Next(void) //currPtr指向下一个结点并返回currPtr { if(currPtr!=NULL)currPtr=currPtr->next; returncurrPtr; } template<classT>

tLinList<T>::EndOfList(void)const //currPtr是否指在链表尾：是返回1；否返回0 { if(currPtr==NULL)return1; else return0; }

上述类ListNode<T>的定义和实现，以及类LinList<T>的定义和实现放在文件LinList.h中。 类LinList<T>的定义使用了2.2节中的类的构成方法的合成法，即类LinList<T>是由类ListNode<T>合成构成的。对于合成构成的类LinList<T>来说，每个结点都是通过new函数动态申请的，而不是通过定义结点类ListNode<T>的对象自动生成的。当系统退出时，在释放LinList<T>类对象时所有的ListNode<T>类对象不能由系统自动释放，

并且在系统自动释放了LinList<T>类对象后失去了头指针head，所有的ListNode<T>类对象所占用的存储空间都不能再回收利用。这样如果程序多次使用，没有释放的存储空间会越来越多，从而造成系统因无存储空间可用而瘫痪。因此，类LinList<T>定义了析构函数，用delete函数释放所有链表中的结点对象。可以看出，所有用类构造函数自动构造的对象系统都能自动释放（此时类的析构函数为空）；所有用new函数人工构造的对象都要在类的析构函数中用delete函数人工释放（此时类的析构函数不能为空）。

上述类LinList<T>的定位成员函数Index(pos)的图示见图4―11；前插入成员函数Insert(item,pos)的图示见图4―5。定位成员函数与前插入成员函数不同之处是pos（0≤pos≤size）可以插入任意结点。删除成员函数Delete(pos)的图示见图4―6，定位成员函数与删除成员函数不同之处是pos(0≤pos<size）可以删除任意结点。前插入和删除成员函数都首先调用Index()定位到要插入结点的前一个结点位置和要删除结点的前一个结点位置。

图4―11 成员函数Index(pos)定位过程的图示 (a）开始循环；（b）循环结束

4.2.3 单链表类的应用 例4―1把第3章中使用顺序表类的例3―1用单链表类实现。 程序如下：   ＃include"LinList.h“ void main(void) { LinList<int>myList; for(inti=0;i<5;i++) //插入5个整型元素

myList.Insert(i+10,i); cout<<"测试GetData()成员函数结果如下："<<endl;for(i=0;i<5;i++) cout<<myList.GetData(i)<<""; cout<<"测试遍历成员函数结果如下："<<endl;ListNode<int>*p=myList.Reset(); //p指在第1个结点 while(! myList.EndOfList()) //是否到达表尾

cout<<p->data<<"";p=myList.Next(); } 程序输出为： 测试GetData()成员函数结果如下： 10 11 12 13 14 测试遍历成员函数结果如下：

对比例4―1和例3―1可以发现： （1）两个程序完全一样，输出结果也相同，只是所用的类不同。例3―1用的是顺序表类，例4―1用的是链表类。这说明类的设计和应用程序完全分离，类在应用程序中可重复使用。 （2）分析例4―1可以发现，由于程序无法记住当前操作（包括插入结点、取元素结点和删除结点）的指针值，所以当对链表进行遍历操作（如取元素结点）时，每次都是调用Index(pos)成员函数从头指针重新开始定位，这显然效率非常低。

4.3 单循环链表 4.3.1单循环链表类的定义和实现单循环链表类的定义 如下： ＃include<iostream.h> 4.3 单循环链表 4.3.1单循环链表类的定义和实现单循环链表类的定义 如下：  ＃include<iostream.h> ＃include<stdlib.h> template<class T>class CirList; //前视定义,否则友元无法定义

template<classT>classListNode { friendclassCirList<T>; //定义类CirList<T>为友元（其余部分省略） }; （类ListNode的实现部分省略） template<classT>classCirList private:Lis tNode<T>*head; //指向表头的指针 intsize; //单链表的结点个数

ListNode<T>*currPtr; //当前结点指针 public: //构造函数和析构函数 CirList(void); //构造函数 ~CirList(void); //析构函数//循环链表操作的成员函数 intListSize(void)const; //返回链表的结点个数 intListEmpty(void)const; //链表空否:空返回1;否则返回0 ListNode<T>*Index(intpos); //返回指向第pos个结点的指针

//在第pos个结点前插入一个data域值为item的新结点 voidInsert(con stT&item,intpos);TDelete(intpos); //删除第pos个结点并返回被删结点的dataTGetData(intpos); //返回第pos个结点的data值 voidClearList(void); //清空表为初始化状态 //遍历循环链表的成员函数

ListNode<T>*Reset(intpos=0); //currPtr指向结点pos并返回currPtr ListNode<T>*Next(void); //currPtr指向下一个结点并返回currPtr int EndOfList(void)const; //currPtr==head否:是返回1；否返回0

//单循环链表的补充成员函数 int NextEndOfList( )const; //currPtr->next是否链表尾；是返回1；否返回0 T DeleteAfter(); //删除currPtr->next所指结点并返回被删结点的data };

单循环链表的数据成员和成员函数与单链表的类同，只是遍历单循环链表成员函数的实现中的方法不同。在遍历单循环链表成员函数中判断表尾是用条件currPtr→next==head判断表尾的。最后补充的成员函数是为4.3.2节例4―2的约瑟夫问题使用单循环链表类特殊设计的。一个类设计好后应能满足大多数应用问题对成员函数的要求，本书由于以讲述基本方法为首要目标，为节省篇幅，除应用举例中所必须要有的成员函数外，一般每个类只包括基本成员函数。

环链表类的实现如下：  template<classT> CirList<T>::CirList() //构造函数 { head=newListNode<T>(); //头指针指向头结点 head->next=head; //构造循环链表 size=0; //定义size的初值为0 }

template<classT> ListNode<T>*CirList<T>::Next(void) //currPtr指向下一个结点并返回currPtr { currPtr=currPtr->next; //注意：去掉了是否到链尾的判断，构成循环returncurrPtr; } intCirList<T>::EndOfList(void)const //currPtr是否指在链表尾：是返回1；否返回0

if(currPtr==head)return1; //注意循环链表是否到链尾的判断条件 elsereturn0;} template<classT> intCirList<T>::NextEndOfList()const //currPtr->next是否链表尾:是返回1否返回0 { if(currPtr->next==head)return1; elsereturn0; }

template<classT>TCirList<T>::DeleteAfter() //删除currPtr->next所指结点并返回被删结点的data域值 { ListNode<T>*p=currPtr->next; //p指向要删除结点 currPtr->next=p->next; //currPtr->next结点脱链

Tdata=p->data; Delete p; //释放结点空间 size--; //元素个数减1 Return data; //返回被删结点的data域值 } （其他部分省略）

4.3.2 单循环链表类的应用 例4―2约瑟夫（Josephus）问题。设有n个人围成一个圆圈，任意给出一个正整数m，从第一个人开始计数，数到第m个人时第m个人被从圆圈中去除。问最后剩下的是哪个人。 ＃include"CirList.h" template<classT> void Josephus(CirList<T>&CList,intn,intm) { List Node<T>*p;

cout<<"删除次序依次为："<<endl; CList.Reset(-1); for(inti=0;i<n-1;i++) { for(intj=0;j<m-1;j++){ p=CList.Next(); if(CList.EndOfList())p=CList.Next(); } if(CList.NextEndOfList())p=CList.Next();

cout<<"删除第"<<CList.DeleteAfter()<<"人"<<endl; } cout<<"最后剩下的是：第"<<CList.GetData(0)<<"个人"<<endl;} voidmain(void) { CirList<int>myCirList; //定义int型的CirList类对象 intn,m;cout<<"输入n: ";cin>>n;cout<<"输入m:";cin>>m ;for(inti=0;i<n;i++)myCirList.Insert(i+1,i);

cout<<“人员编号依次为：”; ListNode<int>*p=myCir List.Reset();while(!my CirList.End Of List()) { cout<<p->data<<"";p=myCirLi st.Next ();}cout<<endl;Josephus (myCirList,n,m); }

程序的一次运行情况如下： 输入n：7 输入m：20 人员编号依次为：1234567 删除次序依次为： 删除第6人 删除第1人 删除第7人 删除第5人 删除第3人 删除第2人 最后剩下的是：第4人

在上面的函数Josephus(CList,n,m)中，每次数到头结点时应越过不计数，每当要删除的结点是头结点时应改为删除第一个结点，最后剩下的一个人位于第4号结点上。7个人的约瑟夫问题图示见图4―12。

图4―12 7个人的约瑟夫问题 （a）初始状态；（b）结束状态

4.4 双向循环链表 4.4.1 双向循环链表概念 双向循环链表（Double Circular Linked List）是每个结点有后继指针和前驱指针，且后继指针和前驱指针各自构成自己的单循环链表的链表。

在单链表中查找当前结点的后继结点并不困难，可以通过当前结点的next指针进行，但要查找当前结点的前驱结点就要从头指针head开始重新进行。对于一个要频繁查找当前结点的后继结点和当前结点的前驱结点的应用来说，使用单链表的时间效率是非常低的，双向链表是有效解决这类问题的当然选择。 在双向链表中，每个结点包括三个域，分别是data、next和prior。其中，data为数据域，next为后继结点指针，prior为前驱结点指针。图4―13为通常双向链表结点的图示结构。

图4―13 双向链表结点的图示结构

双向链表通常均为双向循环链表。这是因为对双向循环链表，不论是插入还是删除，对第一个结点、最后一个结点的操作和对链表中间任意一个结点的操作过程是相同的，而双向非循环链表对这些结点的操作过程是不相同的。一个带头结点的双向循环链表的结构图见图4― 4。

设指针p指向双向循环链表中的第i个结点，则p→next指向第i+1个结点，p→next→prior仍指向第i个结点，即p→next→prior==p；同样地，p→prior指向第i-1个结点，p→prior→next仍指向第i个结点，即p→prior→next==p。图4―14为双向循环链表的上述指针关系图示。 图4―14 为双向循环链表的指针关系

4.4.2 双向循环链表类定义和实现 双向循环链表只是在单循环链表的基础上又增加了一个指向前驱结点的指针，而且指向前驱结点的指针也构成自己的前向的单循环链表，因此，双向循环链表类的定义和单循环链表类的定义非常类似。双向循环链表类的定义和实现如下： template<class T>class DCirList; template<class T>class DLNode {

Friend class DCirList; private: DLNode<T>*next; DLNode<T>*prior; public: T data; //构造函数,用于构造头结点,头结点无data域参数

DLNode<T>(DLNode<T>*ptrN=NULL,DLNode<T>*ptrP=NULL); //构造函数,用于构造非头结点的结点 DLNode<T>(Titem,DLNode<T>*ptrN,DLNode<T>*ptrP); ~DLNode<T>(){}; //析构函数，为空 }; （成员函数的实现部分省略） template<class T>classDCirList {

private: DLNode<T>*head; intsize; DLNode<T>*currPtr; public: //构造函数和析构函数 DCirList();  ~DCirList(); //双向循环链表的成员函数

intListSize(void)const; //返回链表的结点个数 intListEmpty(void)const; //链表空否,空返回1;否则返回0 DLNode<T>*Index(intpos); //返回指向第pos个结点的指针 //在第pos个结点后插入一个data域值为item的新结点 voidInsert(constT&item,intpos); TDelete(intpos); //删除第pos个结点并返回删除结点的data TGetData(intpos); //返回第pos个结点的data值 voidClearList(void); //清空表为初始化状态

//遍历双向循环链表的成员函数 DLNode<T>*Reset(intpos=0); DLNode<T>*Next(void); DLNode<T>*Prior(void); intEndOfList(void)const;  //双向循环链表的补充成员函数 intNextEndOfList()const; //currPtr->next是否链表尾：是返回1；否则，返回0

intPriorEndOfList()const; //currPtr->prior是否表尾：是返回1；否则，返回0 //删除currPtr结点，新currPtr为原currPtr的前驱，返回被删结点data TDeleteAt(); }; 双向循环链表类的实现如下： template<classT> DCirList<T>::DCirList() //构造函数 { head=newDLNode<T>(); //头指针指向头结点

head->next=head; head->prior=head; size=0; //定义size的初值为0 } template<classT> voidDCirList<T>::Insert(constT&item,intpos) //在第pos个结点前插入一个data域值为item的新结点 { DLNode<T>*p=Index(pos); //p为指向第pos个结点指针 //建立一个新结点

DLNode<T>*newNode=newDLNode<T>(item,NULL,NULL); //把新结点插入p所指结点之前 newNode->prior=p->prior; newNode->next=p; p->prior->next=newNode; p->prior=newNode; size++; //元素个数加1 } template<classT> TDCirList<T>::Delete(intpos) //删除第pos个结点并返回被删结点的data

{ if(size==0) {cerr<<"链表已空，无元素可删！"<<endl; exit(1); } DLNode<T>*p=Index(pos); //p为指向第pos个结点指针 //第pos个结点脱链 p->prior->next=p->next; p->next->prior=p->prior; Tdata=p->data;

deletep; //释放第pos个结点空间 size--; //元素个数减1 returndata; //返回第pos个结点的data域值 } template<classT> intDCirList<T>::PriorEndOfList()const {if(currPtr->prior==head)return1;elsereturn0; template<classT>TDCirList<T>::DeleteAt() //删除currPtr所指结点，新currPtr为原currPtr的前驱，返回被删结点data {

DLNode<T>*p=currPtr->prior; currPtr->prior->next=currPtr->next; currPtr->next->prior=currPtr->prior;   Tdata=currPtr->data; deletecurrPtr; //释放结点空间 currPtr=p; //新currPtr为原currPtr的前驱 size--;

//元素个数减1 return data; //返回被删结点的data域值 } （其余成员函数的实现和单循环链表类成员函数的实现方法相同，省略）上述双向循环链表类定义和实现放在文件"DCirList.h"中。 双向循环链表类的在第pos个结点前插入元素item成员函数Insert(item,pos)过程图示见图4―15。

双向循环链表类的删除第pos个结点Delete(pos)过程图示见图4―16。当pos=0时，图4―16中就没有apos-1元素，该结点就是头结点。双向循环链表类的删除当前结点DeleteAt()过程和Delete(pos)过程类同，只是此时的指针currPtr就是Delete(pos)中的指针p。

图4―15 Insert((item,pos)过程图示

图4―16 Delete(pos)和DeleteAt()过程图示

4.5 链式堆栈 链式堆栈（LinkedStack）是堆栈的链式存储结构表示。我们已知，堆栈是操作受限制的表，堆栈有两端，插入元素和删除元素的一端称为栈顶，另一端称为栈底。对链式结构来说，显然，把链的头指针的一端定为栈顶时插入元素和删除元素十分方便，不需要通过循环找到链的另一端，可直接进行插入和删除。

链式堆栈的插入元素和删除元素都在栈顶进行，不带头结点的链式堆栈插入时可直接把新结点插入到头指针后，删除时直接删除头指针所指的结点，因此链式堆栈不需要头结点时更方便。一个不带头结点、入栈元素为a0,a1,…,an-2,an-1的链式堆栈的结构如图4―17所示。 图4―17 不带头结点的链式堆栈结构

4.5.1链式堆栈类的定义和实现 结点类的定义和实现如下: ＃include<iostream.h> ＃include<stdlib.h> template<classT>classLinStack; //前视定义,否则友元无法定义 template<classT> //模板类型为 Tclass StackNode {

friendclassLinStack<T>; //定义类 LinStack<T>为友元private:StackNode<T>*next; //指向下一结点的指针public: Tdata; //定义为公有成员方便使用 //构造函数 StackNode(constT&item,StackNode<T>*ptrNext=NULL); ~StackNode(){}; };

template<classT>StackNode<T>::StackNode(constT&item,StackNode<T>*ptrNext) { data=item; next=ptrNext; } 链式堆栈类的定义如下： template<classT> class LinStack private:

StackNode<T>*top; //指向栈顶的指针 intsize; //堆栈的结点个数 public: LinStack(void); //构造函数 ~LinStack(void); //析构函数 intStackSize(void)const; //返回堆栈的结点个数 intStackEmpty(void)const; //堆栈空否:空返回1;否则返回0

voidPush(constT&item); TPop(void); //把栈顶结点出栈并返回栈顶元素 TPeek(void); //返回栈顶结点的data值 voidClearStack(void); //清空堆栈为初始化状态 };  

链式堆栈类的实现如下：  template<classT>LinStac k<T>::LinStack() //构造函数 { top=NULL; //头指针指向头结点size=0; //定义size的初值为0} template<classT> LinStack<T>::~LinStack(void) //析构函数

ClearStack(); //释放所有结点 top=NULL; } template<classT> intLinStack<T>::StackSize(void)const //返回堆栈的结点个数 { returnsize;} intLinStack<T>::StackEmpty(void)const //堆栈空否：空返回1;否则返回0

if(size<=0)return1; elsereturn0;} template<classT>voidLinStack<T>::Push(constT&item) //把数据域值为item的结点插入栈顶 { //构造新结点newNode，newNode的data域值为 item，next域值为topStackNode<T>*newNode=newStackNode<T>(item ,top);top=newNode; //新结点为栈顶结点 size++; //元素个数加1 }

template<classT>TLinStack<T>::Pop(void) //把栈顶结点出栈并返回栈顶元素 { if(size==0) cerr<<"堆栈已空，无元素可删！"<<endl;exit(1) ; } StackNode<T>*p=top->next; //p指向新的栈顶结点 Tdata=top->data; //保存原栈顶结点的data域值

deletetop; //释放原栈顶结点空间 size--; //元素个数减1 top=p; //top指向新的栈顶结点 returndata; //返回原栈顶结点的data域值 } template<classT> TLinStack<T>::Peek(void) //返回栈顶结点的data值 { returntop->data;

template<classT>void LinStack<T>::ClearStack(void) //清空堆栈为初始化状态 { StackNode< T>*p,*p1; p=top; //p指向第一个结点 while(p!=NULL) //循环释放结点空间直至初始化状态

p1=p; p=p->next; deletep1; } size=0; //元素个数置为初始化值0  上述结点类和链式堆栈类的定义和实现在文件LinStack.h中。

图4―18（a）为进栈的实现示意图，当堆栈为空时，top等于NULL，新生成结点（由new Node指针指示）的next域值为NULL；当堆栈不为空时，top不等于NULL，新生成结点的next域值为top。图4―18（b）为出栈的实现示意图。当前栈顶结点出栈后，新的栈顶结点为原栈顶结点的next指针所指结点。

图4―18 进栈和出栈实现示意图 （a）进栈实现示意图；（b）出栈实现示意图

4.5.2 链式堆栈类的应用 在这里以后缀表达式值的计算问题为例讨论链式堆栈类的应用。在3.3.2节我们已讨论过，计算后缀表达式值的算法思想是：设置一个堆栈存放操作数，从左到右依次扫描后缀表达式，每读到一个操作数就将其进栈；每读到一个运算符就从栈顶取出两个操作数施以该运算符所代表的运算操作，并把该运算结果作为一个新的操作数入栈；此过程一直进行到后缀表达式读完，最后栈顶的操作数就是该后缀表达式的运算结果。

用链式堆栈类计算后缀表达式值的应用程序如下:  ＃include<ctype.h> //包含isdigit()函数 ＃include"LinStack.h" template<classT>voidPostExp(LinStack<T>&s); voidmain(void){LinStack<float>s; //模板定义为float型 PostExp(s); }

template<classT>voidPostExp(LinStack<T>&s) { charch; Tx,x1,x2; while(cin>>ch,ch!=′＃′) //输入字符直到输入为′＃′ if(isdigit(ch)) //ch为数字 cin.putback(ch); //回退一位 cin>>x; //输入一个数值

s.Push(x); //数值入栈 } else { x2=s.Pop() //退栈得操作数 x1=s.Pop(); //退栈得被操作数 switch(ch) case′+′:{x1+=x2;break;} case′-′:{x1-=x2;break;} case′*′:{x1*=x2;break;} case′/′:{x1*=x2;break;}

} s.Push(x1); //操作结果入栈 cout<<"后缀表达式计算结果为:"<<s.Pop()<<endl; 程序的一次运行如下: 3.0 3.0 * 4.0 4.0 * + ＃ 后缀表达式计算结果为:25

4.6 链式队列 链式队列（Linked Queue）是队列的链式存储结构表示。队列是操作受限制的表，队列有队头和队尾，插入元素的一端称为队尾，删除元素的一端称为队头。这和一般排队的概念一样，后来的人排在队尾，首先对队头的人进行服务，对当前队头的人服务后，原当前队头后的人就排在了当前队头；新来的人排在队尾后，原队尾的人就不再是当前队尾，新来的人就成了当前队尾。

链式队列的队头指针指在队列的当前队头结点位置；队尾指针指在队列的当前队尾结点位置。不带头结点的链式队列,出队列时可直接删除队头指针所指的结点，因此链式队列不需要头结点时更方便。一个不带头结点、入队列元素为a0,a1,…,an-1的链式队列的结构如图4―19所示。 图4―19 不带头结点的链式队列结构

结点类的定义和实现如下：  ＃include<iostream.h> ＃include<stdlib.h> template<classT>classLinQueue; //前视定义,否则友元无法定义 template<classT>classQueueNode { friendclassLinQueue<T>; //定义类LinQueue<T>为友元private:  

Que ueNode<T>*next; //指向下一结点的指针public : Tdata; //定义为共有成员方便使用 //构造函数和析构函数 QueueNode(constT&item,QueueNode<T>*ptrNext=NULL); ~QueueNode(){}; };

template<classT> QueueNode<T>:: QueueNode(constT&item,QueueNode<T>*ptrNext) { data=item; next=ptrNext; }  链式队列类的定义如下： template<classT>classLinQueue private: QueueNode<T>*front; //指向队头的指针 QueueNode<T>*rear; //指向队尾的指针

intsize; //队列的结点个数 public: LinQueue(void); //构造函数 ~LinQueue(void); //析构函数 voidQInsert(constT&item); //入队列 TQDelete(void); //出队列 TQFront(void)const; //读队头元素值 intQueueEmpty(void)const //判队列是否为空 {returnsize<=0 ;};

voidClearQueue(void); //清空队列 intGetSize(void)const //取队列元素个数 {returnsize;}; };  链式队列类的实现如下： template<classT> LinQueue<T>::LinQueue() //构造函数 { front=rear=NULL; //头指针指向头结点

size=0; //定义size的初值为0 } template<classT> LinQueue<T>::~LinQueue(void) //析构函数 { ClearQueue(); //释放所有结点 front=rear=NULL; template<classT>voidLinQueue<T>::QInsert(constT&item) //把数据域值为item的结点插入栈顶

{ //构造新结点newNode，newNode的data域值为item，next域值为NULLQueueNode<T>*newNode=newQueueNode<T>(item,NULL); if(rear!=NULL)rear->next=newNode; //原先不为空链时才要链接 rear=newNode; //新结点为队尾结点

if(front==NULL)front=newNode; size++; //元素个数加1 } template<classT> TLinQueue<T>::QDelete(void) //把栈顶结点出栈并返回栈顶元素 { if(size==0){cerr<<" 队列已空，无元素可删！"<<endl;exit(1); }  

QueueNode<T>*p=front->next; //p指向新的栈顶结点 Tdata=front->data; //保存原队头结点的data域值 deletefront; //释放原队头结点空间 front=p; //front指向新的队头结点 if(front==NULL)real=NULL; size--; //元素个数减1 returndata; //返回原队头结点的data域值 }  

template<classT> TLinQueue<T>::QFront(void)const //返回队头结点的data值 { returnfront->data; } template<classT>voidLinQ ueue<T>::ClearQueue(void) //清空队列为初始化状态 QueueNode<T>*p,*p1;p=front; //p指向第一个结点 while(p!=NULL) //循环释放结点空间直至初始化状态

p1=p;p =p->next; deletep1; } size=0; //元素个数置为初始化值0

图4―20为进队列的实现示意图。当队列为空时，rear和front均等于NULL，新生成结点（由new Node指针指示）入队列后，rear和front均指向新生成结点；当队列不为空时，rear和front均不等于NULL，新生成结点入队列后即链接在原队尾结点的next指针上，新生成结点为新的队尾。图4―21为出队列的实现示意图，当前队头结点出队列后，新的队头结点为原队头结点的next指针所指结点；当队头front为空时，队尾rear也要置为空。

图4―20 进队列实现示意图 （a）进队列前； （b）进队列后

图4―21 出队列实现示意图

顺序队列类的应用举例中所讲的回文问题用链式结构也可实现，程序如下： ＃include<string.h> ＃include"LinQueue.h" //包含链式队列类 ＃include"LinStack.h" //包含链式堆栈类 voidmain(void) { LinStack<char>myStack; //定义字符模板的堆栈对象

LinQueue<char>myQueue; //定义字符模板的队列对象charstr［80］;  cout<<"输入字符序列，回车换行符结束："<<endl;cin.get line(str,80); //从键盘接收字符序列 int h=strlen(str); //求字符序列长度 cout<<"h="<<h<<endl;for(inti=0;i<h;i++) { myQueue.QInsert(str［i］); myStack.Push(str［i］);

} while(!myQueue.QueueEmpty()) { if(myQueue.QDelete()!=myStack.Pop()) cout<<"不是回文!"<<endl; return; cout<<"是回文!"<<endl;

对比使用顺序队列类和顺序堆栈类的回文问题程序与上述使用链式队列类和链式堆栈类的回文问题程序可以发现，两程序除包含文件和定义对象方法不同外，其余部分完全相同。由此我们可进一步理解： （1）本书所讨论的各种基本数据结构（如堆栈和队列）是各种应用程序编程的基本成分，当应用程序中所要用到的各种基本数据结构都已有设计好的可重复使用的类时，以后的程序设计和程序维护将大大简化。

（2）各种基本数据结构（如堆栈和队列）有不同的存储结构，主要有顺序结构和链式结构。应用程序使用哪种存储结构与应用程序实现的逻辑无关，但与应用程序的时间复杂度和空间复杂度有密切关系。

4.7 链式存储结构的特点 与顺序存储结构相比，链式存储结构的主要特点有： 4.7 链式存储结构的特点 与顺序存储结构相比，链式存储结构的主要特点有： （1）结点空间是动态申请和动态释放的，没有像顺序存储结构中数据元素最大个数需预先确定的问题； （2）数据元素的逻辑次序靠结点的指针域实现，这样在插入元素和删除元素时没有像顺序存储结构中需大量移动数据元素的问题。

链式存储结构也有不足，主要表现在： （1）是非随机存储结构，即链式存储结构对任意一个结点的操作不能直接进行，需要从头指针进入逐个查找，造成插入、删除和取元素成员函数的时间复杂度均为O(n)。虽然为降低时间复杂度，可对遍历操作增加一个当前指针数据成员记住当前操作的结点位置，下次操作时就不用再从头指针进入逐个查找，但对随机位置操作的时间复杂度无法降低。

（2）每个结点中指针域需额外占用存储空间，当结点的数据域所用字节不多时，指针域所占存储空间的比例就显得很大。下面我们用计算机实际测试的方法比较一下顺序表和链表的时间复杂度。 测试顺序表时间复杂度的程序如下：   ＃include<iostream.h> typedefintDatatype; ＃include"SeqList.h" //注意，SeqList.h中的MaxListSize必须改为≥32700 void main(void)

{ SeqListlist;inti; for(i=0;i<32700;i++) //为顺序表赋值，int型值不能超过32768 list.Insert(i,i); cout<<"程序开始!"<<endl; for(i=0;i<32700;i++) //测试Delete()和Insert()的最坏情况 list.Delete(0); list.Insert(i,0);}cout<<"程序开始!"<<endl ;}

程序运行如下： 程序开始! 程序结束! //共耗时48秒 测试链式表时间复杂度的程序如下： ＃include<iostream.h> ＃include"LinList.h" voidmain(void) { LinList<int>list;inti; for(i=0;i<32700;i++) //为链表赋值

list.Insert(i,i);cout<<"程序开始!"<<endl; for(i=0;i<32700;i++) //测试Delete()和Insert()的最坏情况 { list.Delete(i);list.Insert(i,i); } cout<<"程序结束!"<<endl;

程序运行如下： 程序开始! 程序结束! //共耗时183秒 可见，虽然链表类的插入、删除操作和顺序表类的插入、删除操作具有相同的时间复杂度，都是O(n)，但链表类的插入、删除操作实际耗时更多一些。由此可见，对链表的遍历操作利用当前指针currPtr设计一组专门的遍历操作成员函数是必要的，此时就不必让指针每次都从头指针开始进入。

4.8 应用问题的面向对象程序设计方法 重新设计的程序如下： ＃include"LinStack.h" template<classT>classPostExp { private:LinStack<T>s; voidEnter(Tnum)； intGetTwoOperands(T&operand1,T&operand2);

voidCompute(charop); public: PostExp(void){}; voidRun(void); voidClear(void); }; template<classT> voidPostExp<T>::Enter(Tnum) { s.Push(num);} intPostExp<T>::GetTwoOperands(T&operand1,T&operand2)

{ if(s.StackEmpty()) cerr<<"缺少操作数!"<<endl; return0; } operand1=s.Pop();

operand2=s.Pop(); return1; } template<classT> voidPostExp<T>::Compute(charop) { Int result; Toperand1,operand2; result=GetTwoOperands(operand1,operand2); if(result=1)

switch(op) { case′+′:s.Push(operand2+operand1); break; case′-′:s.Push(operand2-operand1); case′*′:s.Push(operand2*operand1); case′/′:s.Push(operand2/operand1); break;  

} elses.ClearStack(); template<classT> voidPostExp<T>::Run(void) { charc;TnewOperand; cout<<"输入后缀表达式,以＃号结束:"<<endl; while(cin>>c,c!='＃') {switch(c) case′+′: case′-′:

case′*′: case′/′:Compute(c); break; default:cin.putback(c); cin>>newOperand;Enter(newOperand); } }if(!s.StackEmpty()) cout<<"后缀表达式计算结果为:"<<s.Peek()<<endl;

template<classT> voidPostExp<T>::Clear(void) { s.ClearStack(); }  上述类PostExp<T>放在文件PostExp.h中。

类PostExp<T>的设计与4. 5 类PostExp<T>的设计与4.5.2节的后缀表达式的计算函数PostExp(s)基本思想类同，但是进一步考虑了许多可能出错的情况，这就如我们前面说的部件制造商有精力仔细考虑自己设计的部件，从而使参数指标提高，使维护方便。浮点类型后缀表达式计算的主程序设计如下： ＃include"PostExp.h" void main(void) { PostExp<float>exp; exp.Run(); }

程序的一次运行如下： 输入后缀表达式,以＃号结束: 3.0 3.0 * 4.0 4.0 * + ＃ 后缀表达式计算结果为:25