常用数据结构的C++实现

第13章常用数据结构的C++实现

本章要点：

链表的C++实现

二叉树的C++实现

哈希表的的C++实现13.1循序渐进学理论

13.1.1链表链表是线性表的一种存储形式，具有存储长度可变，插入、删除运算效率高等优点，由表头指针和一系列相继链接的结点组成。结点由值域和链域组成，值域用来存储链表中元素的值，链域用来存储下一个结点的地址，最后一个结点的链域为空。本节讨论简单链表的C++实现，具有插入、删除和遍历等操作。它的逻辑状态图如图13-1所示。图13-1简单链表的逻辑状态图1.结点类Node的定义和实现结点是链表的基本组成单位，每一个结点都有值域和链域，并且具有两种操作方法，一是删除当前结点，二是在当前结点的后面增加一个新的结点。基于模板的结点类的定义如下：template<classType>classNode{public:Typedata;Node(constType&item,Node<Type>*ptrnext=NULL);voidinsertAfer(Node<Type>*p);Node<Type>*deleteAfter();Node<Type>*nextNode()const;private:Node<Type>*next;};构造函数Node()的代码如下，其每个结点的链域的缺省值为NULL：template<classType>Node<Type>::Node(constType&item,Node<Type>*ptrnext=NULL):data(item),next(ptrnext){}成员函数nextNode()用于访问当前结点中的链域next，其代码如下：template<classType>Node<Type>*Node<Type>::nextNode()const{returnnext;}成员函数insertAfter()用于在当前结点的后面插入一个新的结点。假设新结点为P，其代码如下：template<classType>voidNode<Type>::insertAfter(Node<Type>*p){p->next=next;next=p;}成员函数deleteAfter()用于删除当前结点的后续结点。如果当前结点没有后续结点，函数返回NULL，否则返回已被删除的结点的地址，供释放内存之用，其代码如下：template<classType>Node<Type>*Node<Type>::deleteAfter(){Node<Type>*tempPtr=next;if(next==NULL)returnNULL;next=tempPtr->next;returntempPtr;}2.链表类List的定义和实现

在结点类的基础上再定义链表类List，为用户提供更高层次的抽象，而无需关心数据是如何存储在Node中的。其定义如下：template<classType>classList{public:List();

List(List<Type>&l);~List();Type&data();//读取当前结点中的数据

voidnext();//向后移一个结点

voidreset(intpos=0);//设定当前指针的位置

voidinsert(constType&item);//插入操作

voiddeleteNode();//删除操作

voidtraversal(intpos=0);//遍历操作

private:

intsize;//链表的长度

Node<Type>*head,*rear,*currPtr,*prePtr;Node<Type>*getNode(constType&item,Node<Type>*prtNext=NULL);voidFreeNode(Node<Type>*p);};成员函数getNode()动态生成一个新结点，如果分配成功，则返回指向新结点的指针，否则退出程序，其代码如下：template<classType>Node<Type>*List::getNode(Type&item,Node<Type>*nextPtr=NULL){Node<Type>*newNode;newNode=newNode<Type>(item,nextPtr);if(newNode==NULL){cout<<”内存空间分配错误！”<<endl;exit(-1);}returnnewNode;}成员函数data()用于读取结点中的数据，如果链表为空，或者当前地址为空，则显示警告信息，其代码如下：template<classType>Type&List<Type>::data(){if(size==0||currPtr==NULL)cout<<“无法读取当前位置的数据”;elsereturncurrPtr->data;}成员函数insert()将一个新结点插入到链表当前位置的后面，需要注意的是，插入操作可能会发生在链表的首部、中部和尾部，必须仔细考虑各种情况下头指针和尾指针的变化。template<classType>voidList<Type>::insert(constType&item){Node<Type>*newNode;if(currPtr==NULL)//判断是否在首部插入

{newNode=getNode(item,head);head=newNode;}else{newNode=getNode(item);

currPtr->insertAfter(newNode);prePtr=currPtr;}if(prePtr==NULL)//如果在尾部插入，则修改尾指针

rear=newNode;currPtr=newNode;size++;}成员函数delete()用于删除当前位置的结点，删除操作可以发生在首部、中部和尾部。

template<classType>voidList<Type>::deleteNode(){Node<Type>*p,*temp;if(currPtr==NULL)//链表空或当前指针指向链表的尾部

{cout<<"删除操作失败！"<<endl;return;}if(prePtr==NULL)//判断被删除的结点是否是首结点

{p=head;head=p->nextNode();}else p=prePtr->deleteAfter();//删除当前结点

currPtr=p->nextNode();//重新设置当前指针if(p==rear)//如果被删除结点是尾部结点

{rear=prePtr;

currPtr=prePtr;

prePtr=NULL; temp=head; while(temp!=currPtr) {prePtr=temp; temp=temp->nextNode(); } }

freeNode(p);size--;}3.链表的实现和验证

【例13-1】将前面的内容综合起来，用类模板实现一个简单链表，并用int型数据验证链表的插入、删除和遍历等基本操作。13.1.2二叉树二叉树也叫二分树，由树结点组成，树结点类似于链表中的结点，由一个值域和两个链域组成，如图13-3所示。每个结点最多只能有两个儿子──左儿子和右儿子，以其为根的子树被称为该结点的左子树和右子树，没有儿子的结点被称为叶子。根结点是二叉树的入口，链域被分成左指针域和右指针域，分别指向其左子树和右子树。叶子的左右指针域均为NULL，表示其不再有子树。

图13-3二叉树结点的组成1.树结点类treeNode的定义和实现树结点中的值域用于存储各个元素的值，和链表中的值域一样，也被定义为公有成员，以便用于辞典一类的高级数据结构中。左、右指针域被定义为私有成员，只能通过公有成员函数Right()和Left()被访问。树结点类treeNode的定义如下：classtreeNode{public:Typedata;//结点的值域

treeNode(constType&item,treeNode<Type>*lptr=NULL,treeNode<Type>*rptr=NULL);treeNode<Type>*&Left(){returnleft;};

treeNode<Type>*&Right(){returnright;};private:

treeNode<Type>*left;//结点的左指针域

treeNode<Type>*right;//结点的右指针域};2.二叉树类Tree的定义和实现在树结点类的基础上定义二叉树类Tree：template<classType>classTree{public:Tree():root(NULL){}~Tree();

treeNode<Type>*root;voidtraversalPreOrder(treeNode<Type>*p);//先序遍历

voidtraversalInOrder(treeNode<Type>*p);//中序遍历

voidtraversalPostOrder(treeNode<Type>*p);//后序遍历

voidmakeTree(inti,intj,intL,int

u,treeNode<Type>*&p);private:treeNode<Type>*getTreeNode(constType&item,treeNode<Type>*lptr=NULL,treeNode<Type>*rptr=NULL);voidfreeTreeNode(treeNode<Type>*p);};函数makeTree()的作用是构造一棵二叉树，它的工作原理是任何一棵有n个树结点的二叉树，都可以由它的中序和先序序列唯一确定。所以，先人工求出二叉树的中序和先序序列，然后利用它们构造出一棵二叉树，其代码如下：template<classType>voidTree<Type>::makeTree(inti,intj,intL,int

u,treeNode<Type>*&p){intm,k;

boolfind=false;if(i>j)p=NULL;else{p=getTreeNode(A[i]);m=L;k=0;while(m<=u){if(B[m]==A[i]){k=m;m=u+1; find=true; break;}elsem++;}if(find==false){cout<<"没有在中序序列中找到元素"<<A[i]<<endl; exit(-1);}else{makeTree(i+1,i+k-L,L,k-1,p->Left());makeTree(i+k-L+1,j,k+1,u,p->Right());}}}3.二叉树的实现和验证【例13-2】请构造一棵如图13-4所示的字符二叉树，并对它进行先序、中序和后序遍历。该二叉树的先序序列是ABDGCEF，中序序列是DGBAECF。图13-4二叉树示例13.1.3哈希表哈希表是一种重要的数据结构，对于某些数据集合，它可以获得最佳的运算效率。在这些数据集合中，元素的排列顺序并不重要，对它们的操作仅仅是查找、插入和删除。查找算法的本质是通过关键字K（也称为键）找到它的存储地址，也就是建立一个从键空间K到地址空间A的映射H：H:K其中，函数H被称为哈希函数，可以将键值K映射为0至n-1内的某个整数值H(K)。常用的哈希函数有：留余数法、数位提取法、平方取中法、折叠法、变换基数法等。

解决冲突的方法通常有两种：开放地址法和链接法。开放地址法的原理是一旦发生冲突则在哈希表中寻找下一个结点，直到找到所要的元素或者空闲地址为止。链接法是把互相冲突的元素组成一个链表。若在插入时发生冲突，则在链表上增加一个结点，查找时则沿着链表搜索。假设哈希表有10个桶，并采用链接法解决冲突，那么它的逻辑结构如图13-6所示。图13-6链接法解决冲突1.哈希表类hashTable的定义和实现采用链接解决冲突法实现的哈希表在本质上是一个链表数组。因此，桶的数据类型为链表List。基于模板的哈希表类hashTable的定义如下：template<classType>classhashTable:publicList<Type>{private:int

numBuckets;//哈希表的长度intdivisor;//模值List*buckets;TypehashFunction(constType&k);//哈希函数public:hashTable(intnum):numBuckets(num),divisor(d){buckets=newList<Type>[num];}voidinsert(constType&k);voiddelete(constType&k);boolfind(constType&k);};成员函数find()用于在哈希表中寻找一个元素，其代码如下：template<classType>bool

hashTable<Type>::find(constType&k){inti=hashFunction(k);

buckets[i].reset();if(buckets[i].size==0)//如果键K对应的桶为空，则无需查找

returnfalse;elsefor(intj=0;j<buckets[i].size;j++) {if(buckets[i].data()==k) returntrue;

buckets[i].next();