加载中…
个人资料
_陌上花开7_
_陌上花开7_
  • 博客等级:
  • 博客积分:0
  • 博客访问:68,244
  • 关注人气:29
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

查找的基本概念以及线性表的查找技术

(2013-08-24 15:39:08)
标签:

查找

线性表

查找算法

it

分类: 数据结构

1.  基本概念

2.  查找表(Search Table):由同一类型的数据元素构成的集合,是一种非常灵活的数据结构。

3.  静态查找表:只对查找表进行查询某个特定的数据元素或某个特定数据元素的各种属性的操作。 如:查询成绩表中是否有某学生或该学生某门课程的成绩。

4.  动态查找表:对查找表进行插入或删除某个数据元素的操作。

5.  查找(Search):也称检索,是根据给定的某个值,在查找表中确定一个关键字等于给定值的记录或数据元素。查找的结果通常有两种可能:

查找成功:即找到满足条件的数据对象,这时作为结果可报告该对象在结构中的位置, 还可给出该对象中的具体信息。

  查找不成功:或搜索失败。作为结果应报告一些信息, 如失败标志、位置等。
关键字(key):数据元素中某个数据项的值。当数据元素中只有一个数据项时,其关键字就是该数据元素的值。

主关键字(Primary key):可以唯一标识一个记录的关键字

平均查找长度(ASL——Average Search Length):为确定记录在表中的位置所进行的和关键字比较的次数的期望值,是衡量一个查找算法好坏的依据。

查找的基本概念以及线性表的查找技术

式中n为查找表的长度,即表中所含元素的个数,Pi为查找第i个元素的概率,一般认为查找每个元素的概率相同,Ci是查找第i个元素时同给定值K所需比较的次数。

 

2.常用查找方法

名称

查找方式

区别

顺序(线性)查找

从表的第一个元素开始,将给定的值与表中逐个元素的关键字进行比较,直到两者符合,查到所要找的元素为止。否则就是表中没有要找的元素,检索不成功。

· 对表结构为有序表、无序表均可适用;

· 对存储结构为向量和线性链表均适用

· 平均查找长度最大,查找成功时:     ASL=(n+1)/2
· 适合于短表,方法简单;

· 不适合长表,检索起来太慢。
· 时间复杂度O(n)

二分(对半)查找

首先选择表中间的一个记录,比较其关键字的值,若要找的记录的关键字值大,则再取表的后半部的中间记录进行比较;否则取前半部的中间记录进行比较,如此反复,直到找到为止。

· 仅适用于有序表 ;
· 只适用顺序存储结构的表,要求表中元素基本不变,在需要插入或删除运算时,影响检索效率 ;

·查找的基本概念以及线性表的查找技术

分块(索引顺序)查找

要求将n个元素均匀地分成块,每块有s个记录,块间按大小排序,块内元素不排序。要建立一个块的最大(或最小)关键字表。查找时,先用对半法由最大关键字查出所在的块,再用线性法在块中查找。

· 要求表中元素是逐段有序的;
· 对存储结构为顺序和线性链表的均适用;

· 平均查找长度比线性查找小;
 

散列查找

在记录的存储位置和它的关键字之间建立一个确定的对应关系,由关键字作某种运算后直接确定元素的地址。用散列函数(或称哈希函数)来表示关键字与元素地址的关系。

在散列存储中会引起冲突,降低冲突的途径:

1) 降低装填因子α

2) 选择合适的散列函数

3)选择合适的解决冲突的方法

 
 
下面讨论一下C++中具体的算法分析问题

BiTree.h内容如下

#ifndef BITREE_H_

#define BITREE_H_

 

#define MAXSIZE 100

 

template<class DataType>

struct BiNode

{

    DataType data;

    BiNode<DataType> *lchild, *rchild;

};

template<class DataType>

struct Node

{

    DataType data;

    Node<DataType> *next;

};

 

template<class DataType>

class BiTree

{

    public:

       BiTree(){root=creat(root);}      //构造函数,建立一棵二叉树

       ~BiTree(){RELEASE(root);}      //析构函数,释放各节点的存储空间

       void PreOrder(){PreOrder(root);}    //前序遍历二叉树

       void InOrder(){InOrder(root);}      //中序遍历二叉树

       void PostOrder(){PostOrder(root);}  //后序遍历二叉树

       void LeverOrder();                  //层序遍历二叉树

 

    private:

       BiNode<DataType>*root;                    //指向根节点的头指针

       BiNode<DataType>*Creat(BiNode<DataType>*bt); //构造遍历函数调用

       void Release(BiNode<DataType>*bt);          //析构遍历函数调用

       void PreOrder(BiNode<DataType>*bt);         //前序遍历函数调用

       void InOrder(BiNode<DataType>*bt);          //中序遍历函数调用

       void PostOrder(BiNode<DataType>*bt);       //后序遍历函数调用

 

   

};

 

#endif

 

 

Bitree.cpp中的内容:

#include <iostream>

#include"BiTree.h"

 

using namespace std;

 

//二叉树前序遍历递归算法PreOrder

template<class DataType>

void BiTree<DataType>::PreOrder(BiNode<DataType>*bt)

{

    if(bt==NULL)    //递归调用的结束条件

       return;

    else

    {

       cout<<bt->data;        //访问根节点bt的数据域

       PreOrder(bt->lchild);  //前序递归遍历bt的左子树

       PreOrder(bt->rchild);  //前序递归遍历bt的右子树

    }

}

 

 

 

//二叉树中序遍历递归算法InOrder

 

template<class DataType>

void BiTree<DataType>::InOrder(BiNode<DataType>*bt)

{

    if(bt==NULL)                         //递归调用的结束条件  

       return;

    else

    {

       InOrder(bt->lchild);           //中序递归遍历bt的左子树

       cout<<bt->data;                //访问根节点bt的数据域

       InOrder(bt->rchild);          //中序递归遍历bt的右子树

    }

}

 

 

 

//二叉树后序遍历递归算法PostOrder

 

template<class DataType>

void BiTree<DataType>::PostOrder(BiNode<DataType>*bt)

{

    if(bt==NULL)                         //递归调用的结束条件  

       return;

    else

    {

       PostOrder(bt->lchild);           //后序递归遍历bt的左子树

       PostOrder(bt->rchild);          //后序递归遍历bt的右子树

       cout<<bt->data;                //访问根节点bt的数据域

    }

}

 

//二叉树层序遍历算法PostOrder

 

template<class DataType>

void BiTree<DataType>::LeverOrder()

{

    int front=-1,rear=-1;          //采用顺序队列,并假定不会发生上溢

    BiNode<DataType> *q;                    

    BiNode<DataType>*Q[MAXSIZE];               

 

    if(root=NULL)                  //二叉树为空,算法结束

       return;

    Q[++rear]=root;         

    while(front!=rear)

    {

       q=Q[++front];             //出队

       cout<<q->data;

       if(q->lchild!=NULL)

           Q[++rear]=q->lchild;

       if(q->rchild!=NULL)

           Q[++rear]=q->rchild;

      

    }

}

 

 

//建立二叉链表算法create

 

template<class DataType>

BiNode<DataType>*BiTree<DataType>::Creat(BiNode<DataType>*bt)

{

    DataType ch;

    cin>>ch;                          //输入节点的数据信息,假设为字符

    if(ch=='#')                       //建立一棵空树

       bt=NULL;

    else

    {

       bt=new BiNode;

       bt->data=ch;                     //生成一个节点,数据域为ch

       bt->lchild=Creat(bt->lchild);   //递归建立左子树

       bt->rchild=Creat(bt->rchild);   //递归建立右子树

    }

    return bt;

}

 

 

//析构函数:释放二叉链表算法

template<class DataType>

void BiTree<DataType>::Release(BiNode<DataType>*bt)

{

    if(bt!=NULL)

    {

       Release(bt->lchild);//释放左子树

       Release(bt->rchild);//释放右子树

       delete bt; //释放根节点

    }

      

}

主函数main.cpp

#include <iostream>

#include "BiTree.h"

using namespace std;

 

int i;

 

//顺序表的查找算法

 

int SeqSearch1(int r[],int n,int k)           //从数组下标1开始存放待查集合

{

    r[0]=k;                                   //下标用0做监视哨

    i=n;

    while(r[i]!=k)

    {

       i--;                                  //不用判断i是否越界

    }

    return i;

}

 

//单链表的顺序查找算法

 

int SeqSearch2(Node<int>*first,int k)        

{

    Node *p=first->next;                     //工作指针p初始化为指向第一个元素结点

    int count=1;

    while (p!=NULL&&p->data!=k)

    {

       p=p->next;                            //工作指针后移

       count++;

    }

    if (p->data==k)

       return count;                        //查找成功,返回元素在查找集合中的序号

    else return 0;                           //查找失败,返回0

}

 

 

//折半查找非递归算法

 

int BinSearch1(int r[],int n,int k)          //从数组下标1开始存放待查集合

{

    int low=1;                              //设置查找区间

    int high=n;

    while(low<=high)                        //当查找区间存在时

    {

       int mid=(low+high)/2;

       if(k<r[mid])

           high=mid-1;

       else if(k>r[mid])

           low=mid+1;

       else

           return mid;                  //查找成功,返回元素序号

    }

}

 

//折半查找递归算法

 

int BinSearch2(int r[],int low ,int high,int k)

{

    int mid;

    if(low<high)

       return 0;

    else

    {

       mid=(low+high)/2;

       if(k<r[mid])

           return BinSearch2(r,low ,mid-1,k);

       else if(k>r[min])

           return BinSearch2(r,mid+1,high,k);

       else return mid;

    }

}

 

//

int main()

{

              //具体内容可有所需的来写

}

 

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
后一篇:平衡二叉树
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

    后一篇 >平衡二叉树
      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有