运算符重载.ppt

运算符重载
第1页，本讲稿共55页
查找的基本概念
查找:查询关键字是否在(数据元素集合）表中的过程。也称作检索。
主关键字:能够惟一区分各个不同数据元素的关键字
次关键字:通常不能惟一区分各个不同数据元素的索引表
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
key
其它域
位置
主表
索引表结构图
索引表中的数据元素由两个域构成，key域为被索引的若干个数据元素中关键字的最大值，link域为被索引的若干个数据元素中第一个数据元素的位置编号。
第9页，本讲稿共55页
完全索引表:和主表项完全相同，但只包含索引关键字和该数据元素在主表中位置信息的索引表
二级索引表:当主表中的数据元素个数非常庞大时，按照建立索引表的同样方法对索引表再建立的索引表。二级以上的索引结构称作多级索引结构
等长索引表:索引表中的每个索引项对应主表中的数据元素个数相等;反之称为不等长索引表。不等长索引表中的索引长度可随着动态插入和动态删除过程改变,因此不仅适用于静态查找问题，而且也适用于动态查找问题。
相关术语
第10页，本讲稿共55页
假设索引表的长度为m，主表中每个子表的长度为s，并假设在索引表上和在主表上均采用顺序查找算法，则索引顺序表上查找算法的平均查找长度为：
算法分析
第11页，本讲稿共55页
动态查找表
动态查找表主要有二叉树结构和树结构两种类型。二叉树结构有二叉排序树、平衡二叉树等。树结构有B-树、B+树等。

一、基本概念
----或是一棵空树；或者是具有如下性质的非空二叉树：
（1）左子树的所有结点均小于根的值；
（2）右子树的所有结点均大于根的值；
（3）它的左右子树也分别为二叉排序树。
第12页，本讲稿共55页
381
12
410
9
40
394
540
35
190
146
476
760
445
600
800
下图所示就是一棵二叉排序树
第13页，本讲稿共55页
二、二叉排序树类
定义如下：
template <class T>
class BiSearchTree
{
//输出流运算符重载
friend istream &operator>> (istream &in, BiSearchTree<T>* &tree);
private:
BiTreeNode<T> *root; //根指针
 
void Insert(BiTreeNode<T>* &ptr, const T &item); //插入
void Delete(BiTreeNode<T>* &ptr, const T &item); //删除
 
//前序、中序和后序遍历，访问操作为Visit()函数
void PreOrder(BiTreeNode<T>* &t, void (*Visit)(T item));
void InOrder(BiTreeNode<T>* &t, void (*Visit)(T item));
void PostOrder(BiTreeNode<T>* &t, void (*Visit)(T item));
第14页，本讲稿共55页
public:
//构造函数和析构函数
BiSearchTree():root(NULL){}; //注意：生成的二叉排序树不带根结点
~BiSearchTree(){};
 
BiTreeNode<T>* Find(const T &item); //查找
void Insert(const T &item) //插入
{Insert(GetRoot(), item);}
void Delete(const T &item) //删除
{Delete(GetRoot(), item);}
 
BiTreeNode<T> * &GetRoot() //取树根
{return root;}
第15页，本讲稿共55页
BiTreeNode<T>* &LeftChild(BiTreeNode<T>* &current) //取左孩子结点
{return root != NULL