精华内容
下载资源
问答
  • 数据结构查找

    2020-01-30 21:56:00
    目录前言基于线性表的查找法基于树的查找法哈希查找法 前言 查找的基本方法分为两大类:比较式查找法和计算式查找法。...顺序查找法的特点是,用所给关键字与线性表各元素的关键字逐个比较,直到...

    前言

    查找的基本方法分为两大类:比较式查找法计算式查找法
    比较式查找法根据数据元素的组织结构分为:基于线性表的查找法基于树的查找法
    计算式查找法也称为哈希查找法

    比较式查找法

    基于线性表的查找法

    基于线性表的查找法具体可分为:顺序查找法折半查找法以及分块查找法
    1.顺序查找法
    顺序查找法的特点是,用所给关键字与线性表中各元素的关键字逐个比较,直到成功或失败。存储结构通常为顺序结构,也可为链式结构。
    顺序结构数据类型的定义:

    #define LIST_SIZE 20
    typedef struct
    {
    	KeyType key;
    	OtherType other_data;
    }RecordType;
    typedef struct
    {
    	RecordType r[LIST_SIZE+1];		/*r[0]为工作单元*/
    	int length;
    }RecordList;
    

    (1)设置监视哨的顺序查找法

    int SeqSearch(RecordList l,KeyType k)
    {
    	l.r[0].key=k;i=l.length;
    	while(l.r[i].key!=k)
    		i--;
    	return(i);
    }
    

    (2)不设置监视哨的顺序查找法

    int SeqSearch(RecordList l,KeyType k)
    {
    	i=l.length;
    	while(i>=1&&l.r[i].key!=k)
    		i--;
    	if(i>=1)
    		return(i);
    	else 
    		return 0;
    }
    

    2.折半查找法
    折半查找法又称为二分查找法,这种方法对待查找的列表有两个要求:
    (1)必须采用顺序存储结构
    (2)必须按关键字大小有序排列

    int BinSrch(RecordList l,KeyType k)
    {
    	low=1;
    	high=l.length;
    	while(low<=high)
    	{
    		mid=(low+high)/2;
    		if(k==l.r[mid].key)
    			return(mid);
    		else if(k<l.r[mid].key)
    			high=mid-1;
    		else 
    			low=mid+1;
    	}
    	return 0;
    }
    

    3.分块查找法
    在这里插入图片描述
    先将列表组织成以下两种索引顺序结构。
    (1)首先将列表分成若干个块(子表)。一般情况下,块的长度均匀,最后一块可以不满。每块中元素任意排列,即块内无序,但块与块之间有序。
    (2)构造一个索引表。其中每个索引项对应一个块并纪录每块的起始位置,以及每块中的最大关键字(或最小关键字)。索引表按关键字有序排列。
    分块查找的基本过程如下:
    (1)首先,将待查关键字k与索引表中的关键字进行比较,以确定待查记录所在的块。具体的可用顺序查找法或折半查找法进行。
    (2)进一步用顺序查找法,在相应块内查找关键字为k的元素。

    基于树的查找法

    基于树的查找法是将待查表组织成特定树的形式并在树结构上实现查找的方法,故又称为树表式查找法,主要包括二叉排序树、平衡二叉排序树和B树等
    1.二叉排序树
    二叉排序树又称为二叉查找树,它是一种特殊的二叉树。其定义为:二叉排序树或者是一颗空树,或者是具有如下性质的二叉树。
    (1)若它的左子树非空,则左子树上所有结点的值均小于根结点的值。
    (2)若它的右子树非空,则右子树上所有结点的值均大于(或大于等于)根结点的值。
    (3)它的左右子树也分别为二叉排序树。
    二叉排序树的结点结构:

    typedef struct node
    {
    	KeyType key;					/*关键字的值*/
    	struct node *lchild,*rchild;	/*左右指针*/
    }BSTNode,*BSTree;
    

    (1)二叉排序树的插入

    void InsertBST(BSTree *bst,KeyType key)
    {
    	BiTree s;
    	if(*bst==NULL)
    	{
    		s=(BSTree)malloc(sizeof(BSTNode));
    		s->key=key;
    		s->lchild=NULL;s->rchild=NULL;
    		*bst=s;
    	}
    	else if(key<(*bst)->key)
    		InsertBST(&((*bst)->lchild),key);
    	else if(key>(*bst)->key)
    		InsertBST(&((*bst)->rchild),key);
    }
    

    (2)创建二叉排序树

    void CreateBST(BSTree *bst)
    {
    	KeyType key;
    	*bst=NULL;
    	scanf("%d",&key);
    	while(key!=ENDKEY)
    	{
    		InsertBST(bst,key);
    		scanf("%d",&key);
    	}
    }
    

    (3)二叉排序树查找的递归算法

    BSTree SearchBST(BSTree bst,KeyType key)
    {
    	if(!bst)
    		return NULL;
    	else if(bst->key==key)
    		return(bst);
    	else if(bst->key>key)
    		return SearchBST(bst->lchild,key);
    	else
    		return SearchBST(bst->rchild,key);
    ]
    

    (4)二叉排序树查找的非递归算法

    BSTree SearchBST(BSTree bst,KeyType key)
    {
    	BSTree q;
    	q=bst;
    	while(q)
    	{
    		if(q->key==key)
    			return q;
    		else if(q->key>key)
    			q=q->lchild;
    		else
    			q=q->rchild;
    	}
    	return NULL;                
    }
    

    (5)二叉排序树的删除
    在这里插入图片描述
    基本思想:删除操作首先查找要删除的结点,看是否在二叉排序树中,若不在则不做任何操作;否则,假设要删除的结点为p,结点p的双亲结点为f,并假设结点p是结点f的左孩子。下面分三种情况讨论。
    情况一:若p为叶结点,则可直接将其删除:
    f->lchild=NULL;free§
    情况二:若p结点只有左子树,或只有右子树,则将p的左子树或右子树,直接改为其双亲结点f的左子树。即:f->lchild=p->lchild(或 f->lchild=p->rchild);free§。
    情况三:若p既有左子树,又有右子树,可以首先找到p结点在中序序列中的直接前驱s结点,然后用s结点的值代替p结点的值,再将s结点删除,原s结点的左子树改为s的双亲结点q的右子树:
    p->data=s->data;q->rchild=s->lchild;free(s);
    算法如下:

     BSTNode *DelBST(BSTree t,KeyType k)
     {
     	BSTNode *p,*f,*s,*q;
     	p=t;f=NULL;
     	while(p)
     	{
     		if(p->key==k) break;
     		f=p;
     		if(p->key>k)  p=p->lchild;
     		else p=p->rchild;
     	}
     	if(p==NULL) return t;
     		if(p->lchild==NULL)
     		{
     			if(f==NULL) t=p->rchild;
     			else if(f->lchild==p)
     				f->lchild=p->rchild;
     			else
     				f->rchild=p->rchild;
     			free(p);
     		}
     		else
     		{
     			q=p;s=p->lchild;
     			while(s->rchild)
     			{q=s;s=s->rchild;}
     			if(q==p) q->lchild=s->lchild;
     			else q->rchild=s->lchild;
     			p->key=s->key;
     			free(s);
     		}
     		return t;
     }
    

    2.平衡二叉排序树
    平衡二叉排序树又称AVL树。一颗平衡二叉树或者是空树,或者是具有下列性质的二叉排序树。
    (1)左子树和右子树的高度之差的绝对值小于等于1。
    (2)左子树和右子树也是平衡二叉排序树。
    引入平衡二叉排序树的目的:为了提高查找效率,其平均查找长度为O(log2n)。
    3.B树
    B树:
    在这里插入图片描述
    一颗B树是一颗平衡的m路查找树,它或者是空树,或者是满足如下性质的树:
    (1)树中每个结点最多有m颗子树。
    (2)根结点至少有两颗子树。
    (3)除根结点之外的所有非叶结点至少有[m/2]颗子树。
    (4)所有叶结点出现在同一层上,并且不含信息,通常称为失败结点。失败结点为虚结点,在B树中并不存在,指向它们的指针为空指针。引入失败结点是为了便于分析B树的查找性能。
    B+树:
    在这里插入图片描述
    在B+树中,所有纪录结点都是按键值的大小顺序存放在同一层的叶结点中,各叶结点指针进行连接。
    B+树比较B树的优点:
    (1)单一结点储存更多的元素。
    (2)所有查询都要查找到叶子结点,查询性能稳定。
    (3)所有叶子结点形成有序链表,便于范围查询。
    注: B树中每个结点的每个关键字都有卫星数据,B+树中间结点没有卫星数据,只有索引。所以B树的查找只需找到匹配元素即可,最好情况查找到根结点,最坏情况下查找到叶子结点,所以性能很不稳定。而B+树每次必须查找到叶子结点,性能稳定。

    哈希查找法

    基本思想: 首先在元素的关键字k和元素的存储位置p之间建立一个对应关系H,使得p=H(k),H称为哈希函数。创建哈希表时,把关键字为k的元素直接存入地址为H(k)的单元;以后当查找关键字为k的元素时,再利用哈希函数计算出该元素的存储位置p=H(k),从而达到按关键字直接存取元素的目的。可见,哈希法是计算式查找的方法。
    要解决的问题: 如何构造哈希函数和如何处理冲突。
    1.哈希函数的构造方法
    构造哈希函数原则:一是函数本身便于计算;二是计算出来的地址分布均匀,即对任一关键字k,H(k)对应不同地址的概率相等,目的是尽可能减少冲突。
    构造哈希函数常用的五种方法:
    (1)数字分析法
    事先要知道关键字集合,并且每个关键字的位数比哈希表的地址码位数多时,可以从关键字中选出分布较均匀的若干位,构成哈希地址。
    例如:有80个记录,关键字为8位十进制整数 d1 d2 d3 …d7 d8,如哈希表长度取为100,则哈希表的地址空间为0-99.假设经过分析,各关键字中d4和d7的取值分布较均匀,则哈希函数为H(key)=H(d1d2…d7d8)=d4d7.
    (2)平方取中法
    当无法确定关键字中哪几位分布较均匀时,可以先求出关键字的平方值,然后按需要取平方值的中间几位作为哈希地址。
    (3)分段叠加法
    按哈希表地址位数将关键字分成位数相等的几部分(最后一部分可以较短),然后将这几部分相加,舍弃最高进位后的结果就是该关键字的哈希地址。
    具体方法:折叠法和移位法。折叠法是从一端向另一端沿分割界来回折叠(奇数段为正序,偶数段为倒序),然后将各段相加。
    (4)除留余数法
    假设哈希表长为m,p为小于等于m的最大素数,则哈希函数为 H(k)=k%p 其中%为模p取余运算。(冲突较多的话,取较大的m值和p值)
    (5)伪随机数法
    采用一个伪随机函数作为哈希函数,即H(key)=random(key)。
    2.处理冲突的办法
    常用的解决冲突方法有以下四种。
    (1)开放定址法
    当关键字key的初始哈希地址h0=H(key)出现冲突时,以h0为基础,产生另一个地址h1,如果h1仍然冲突,再以h0为基础,产生另一个哈希地址h2…直到找出一个不冲突的地址hi,将相应元素存入其中。
    通用的再散列函数形式为:hi=(H(key)+di)%m i=1,2…n(m为表长,di称为增量序列)
    (2)再哈希法
    同时构造多个不同的哈希函数:Hi=RHi(key) i=1,2…k
    当哈希地址H1=RH1(key)发生冲突时,再计算H2=RH2(key)…直到冲突不再产生。
    (3)链地址法
    将所有哈希地址为i的元素构成一个称为同义词链的单链表,并将单链表的头指针存在哈希表的第i个单元中,因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
    (4)建立公共溢出区
    将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素一律填入溢出表。
    哈希表的查找算法

    int HashSearch(HashTable ht,KeyType k)
    {
    	h0=hash[k];
    	if(ht[h0].key==NULLKEY)	return -1;
    	else if(ht[h0].key==k)	return(h0);
    	else
    	{
    		for(i=1;i<=m-1;i++)
    		{
    			hi=(h0+i)%m;
    			if(ht[hi].key==NULLKEY)	return -1;
    			else if(ht[hi].key==k)	return(hi);
    		}
    		return -1;
    	}
    }
    
    展开全文
  • 返回目录:Chilan Yu:《数据结构》目录链接​zhuanlan.zhihu.com具有顺序查找法、折半查找法和分块查找法三种8.2.1 顺序查找法顺序查找的特点是:用所给关键字与线性表各元素的关键字逐个比较,直到成功或失败...

    e1fdd1fc8443f6e91bf2557ccfded010.png

    返回目录:

    Chilan Yu:《数据结构》目录链接zhuanlan.zhihu.com
    e17fd1d588575e953fe46c97403ee91a.png

    具有顺序查找法折半查找法分块查找法三种

    8.2.1 顺序查找法

    顺序查找法的特点是:用所给关键字与线性表中各元素的关键字逐个比较,直到成功或失败。
    存储结构通常为顺序结构或者链式结构

    算法思想

    在表的一端设置一个称为“监视哨”的附加单元,存放要查找元素的关键字。从表的另一端开始查找,如果在“监视哨”找到要查找元素的关键字,返回失败信息,否则返回相应下标。

    算法分析

    用平均查找长度分析顺序查找算法的性能。
    假设列表长度为n,那么查找第i个数据元素时需进行n-i+1次比较,即Ci=n-i+1。又假设查找每个数据元素的概率相等,即Pi=1/n,则顺序查找算法的平均查找长度为:

    #include <iostream>
    using namespace std;
    
    #define LIST_SIZE 50//顺序表最大长度
    int RecordList[LIST_SIZE];//存储顺序表的数组
    int len;//定义待查找顺序表的长度
    int key;//定义待查找的元素
    
    /*在顺序表RecordList中查找其关键字等于key的元素,若找到,则函数值为该元素在表中的位置,否则为0*/
    int SeqSearch(){//设置监视哨的顺序查找法
        RecordList[0] = key;//设置监视哨
        int i = len;
        while(RecordList[i]!=key) i--;
        return i;
    }
    int SeqSearch(){//不设置监视哨的顺序查找法
        int i = len;
        while(i>=1 && RecordList[i]!=key) i--;
        if(i>=1) return i;
        else return 0;
    }
    
    int main()
    {
        cout << "输入待查找顺序表的长度:";
        cin >> len;//输入长度
        cout << "依次输入顺序表元素(整型):";
        for(int i=1;i<=len;++i){//输入顺序表
            cin >> RecordList[i];
        }
        cout << "输入待查找的元素:";
        cin >> key;
        cout << endl << "待查找元素在顺序表中的位置:";
        cout << SeqSearch() << endl;
        return 0;
    }
    

    返回目录:

    Chilan Yu:《数据结构》目录链接zhuanlan.zhihu.com
    e17fd1d588575e953fe46c97403ee91a.png
    展开全文
  • 1、了解静态查找和动态查找的概念,掌握常用查找算法的存贮结构。 2、掌握二分法查找算法和哈希表查找算法,掌握这二种算法的存贮的要求及特点。 二. 实验内容与要求 1.采用顺序存贮结构构造顺序查找表,使用...
    一、实验目的
    1、了解静态查找和动态查找的概念,掌握常用查找算法的存贮结构。
    2、掌握二分法查找算法和哈希表查找算法,掌握这二种算法的存贮的要求及特点。
    二. 实验内容与要求
    1.采用顺序存贮结构构造顺序查找表,使用二分法技术查找给定的关键字记录,并显示查找结果情况。
    2. 对选定的一组关键字采用除留余数法构造哈希表,要求表中含有关键字、其它信息及搜索次数等内容。
    3. 对构建的哈希表进行查找、删除、显示哈希表等运算。
    4. 实现:
       在二分法查找算法中,要求关键字有序;在哈希表查找中,选择相适应的哈希函数,注意解决冲突的方法使用线性探测法进行。

       ,并有相应的交互信息,根据输出结果进行检验。


    #include <stdio.h>
    #define MAXL 100 //定义表中最多记录个数
    #define NULLKEY -1 //定义空关键字值
    #define DELKEY -2 //定义被删关键字值
    typedef int KeyType; //关键字类型
    typedef char * InfoType;
    typedef char InfoType1[10]; //其他数据类型
    typedef struct
    {
    KeyType key; //关键字域
    InfoType data; //其他数据域
    int count; //探查次数域
    } HashTable[MAXL]; //哈希表类型


    typedef struct 
    {
    KeyType key;                 //KeyType为关键字的数据类型
        InfoType1 data;               //其他数据
    } NodeType;
    typedef NodeType SeqList[MAXL]; //顺序表类型
    int BinSearch(SeqList R,int n,KeyType k) //二分查找算法
    {
    int low=0,high=n-1,mid,count=0;
    while (low<=high) 
    {
    mid=(low+high)/2;

    if (R[mid].key==k)   //查找成功返回
    return mid;
    if (R[mid].key>k)     //继续在R[low..mid-1]中查找
    high=mid-1;
    else
    low=mid+1;       //继续在R[mid+1..high]中查找
    }
    return -1;
    }




    void InsertHT(HashTable ha,int &n,KeyType k,int p)  //将关键字k插入到哈希表中
    {
    int i,adr;
    adr=k % p;
    if (ha[adr].key==NULLKEY || ha[adr].key==DELKEY) //x[j]可以直接放在哈希表中
    {
    ha[adr].key=k;
    ha[adr].count=1;
    }
    else //发生冲突时采用线性探查法解决冲突
    {
    i=1; //i记录x[j]发生冲突的次数
    do 
    {
    adr=(adr+1) % p;
    i++;
    } while (ha[adr].key!=NULLKEY && ha[adr].key!=DELKEY);
    ha[adr].key=k;
    ha[adr].count=i;
    }
    n++;
    }
    void CreateHT(HashTable ha,KeyType x[],int n,int m,int p)  //创建哈希表
    {
    int i,n1=0;
    for (i=0;i<m;i++) //哈希表置初值
        {
            ha[i].key=NULLKEY;
       ha[i].count=0;
        }
    for (i=0;i<n;i++)
    InsertHT(ha,n1,x[i],p);
    }
    int SearchHT(HashTable ha,int p,KeyType k) //在哈希表中查找关键字k
    {
    int i=0,adr;
    adr=k % p;
    while (ha[adr].key!=NULLKEY && ha[adr].key!=k)
    {
    i++; //采用线性探查法找下一个地址
    adr=(adr+1) % p;
    }
    if (ha[adr].key==k) //查找成功
    return adr;
    else //查找失败
    return -1;
    }
    int DeleteHT(HashTable ha,int p,int k,int &n) //删除哈希表中关键字k
    {
    int adr;
    adr=SearchHT(ha,p,k);
    if (adr!=-1) //在哈希表中找到该关键字
    {
    ha[adr].key=DELKEY;
    n--; //哈希表长度减1
    return 1;
    }
    else //在哈希表中未找到该关键字
    return 0;
    }
    void DispHT(HashTable ha,int n,int m)    //输出哈希表
    {
    int i;
    printf("哈希表地址:\t");
    for (i=0;i<m;i++) 
    printf(" %3d",i);
    printf(" \n");
        printf("哈希表关键字:\t");
    for (i=0;i<m;i++) 
    if (ha[i].key==NULLKEY || ha[i].key==DELKEY)
    printf("    "); //输出3个空格
    else
    printf(" %3d",ha[i].key);
    printf("\n");
    printf("搜索次数:\t");
    for (i=0;i<m;i++)
    if (ha[i].key==NULLKEY || ha[i].key==DELKEY)
    printf("    "); //输出3个空格
    else
    printf("%4d",ha[i].count);
    printf(" \n");
    }
    void avglen(HashTable ha,int n,int m)    //求平均查找次数
    {
    float avg=0;
    int i;
        for (i=0;i<m;i++)
    if (ha[i].key!=NULLKEY && ha[i].key!=DELKEY)
    avg=avg+ha[i].count;
    avg=avg/n;
    printf("平均查找长度:  ASL(%d)=%g\n",n,avg);
    }


    /*void main()//非菜单实现主函数
    {
    SeqList R;
    KeyType k=9;
    int x[]={1,2,3,4,5,6,7,8,9,10,11},i,n=11,m=13,p=13;
    for (i=0;i<n;i++) //建立顺序表
    R[i].key=x[i];
    if ((i=BinSearch(R,n,k))!=-1)
    printf("元素%d的位置是%d\n",k,i);
    else
    printf("元素%d不在表中\n",k);
    HashTable ha;
    CreateHT(ha,x,n,m,p);
    DispHT(ha,n,m);
    i=SearchHT(ha,p,k);
    if (i!=-1)
    printf(" ha[%d].key=%d\n",i,k);
    else
    printf(" 提示:未找到%d\n",k);
    k=77;
    printf("删除关键字%d\n",k);
    DeleteHT(ha,p,k,n);
    DispHT(ha,n,m);
    i=SearchHT(ha,p,k);
    if (i!=-1)
    printf(" ha[%d].key=%d\n",i,k);
    else
    printf(" 提示:未找到%d\n",k);
    printf("插入关键字%d\n",k);
    InsertHT(ha,n,k,p);
    DispHT(ha,n,m);
    printf("\n");
    }*/
    void main()//用菜单实现主函数
    {   SeqList R;
    KeyType k=9;
    int x[]={1,2,3,4,5,6,7,8,9,10,11},i,n=11,m=13,p=13;


        int j;
    {
          printf("\n\n********************************************************");
          printf("\n\n********************************************************");
          printf("\n***                 查找算法的实现                   ***\n\n");
          printf("***      请选择:                                    ***\n\n");
          printf("***                 1:建立顺序表                     ***\n\n");
          printf("***                 2:建立哈希表                     ***\n\n");
          printf("***            3:顺序表的二分查找:             ***\n\n");
          printf("***            4:在哈希表中插入关键字           ***\n\n");
          printf("***            5:在哈希表中删除关键字           ***\n\n");
          printf("***            6:在哈希表中查找关键字           ***\n\n");
          printf("***            7:哈希表的输出                   ***\n\n");
          printf("***            8:哈希平均查找的长度             ***\n\n");
     printf("***                 0:退出                           ***");
          printf("\n\n********************************************************");
          printf("\n\n********************************************************");
    }


     while(1)
     {
    printf("\n选择进行的操作");
      do
      {
     scanf("%d",&j);
     if(j<0||j>8)
     printf("输入错误,请重新输入\n");
      }while(j<0||j>8);
       switch(j)
      { case 1:
    printf("关键字内容:1,2,3,4,5,6,7,8,9,10,11\n");
          for (i=0;i<n;i++) //建立顺序表
       R[i].key=x[i];
               printf("已建立顺序表\n");
    break;
        case 2: 
              HashTable ha;                 //建立哈希表
            CreateHT(ha,x,n,m,p);     
                printf("已建立哈希表\n",k);    
       break;
       case 3: 
                if ((i=BinSearch(R,n,k))!=-1)
          printf("元素%d的位置是%d\n",k,i);
                else
          printf("元素%d不在表中\n",k);
       printf("\n");
       break;


    case 4: 

       printf("插入关键字%d\n",k);
           InsertHT(ha,n,k,p);
              DispHT(ha,n,m);
           printf("\n");
    break;
       case 5: 

     
           printf("删除关键字%d\n",k);
           DeleteHT(ha,p,k,n);
           DispHT(ha,n,m);
           printf("\n");
    break;
        case 6: 
                DispHT(ha,n,m);
           i=SearchHT(ha,p,k);
           if (i!=-1)
         printf(" ha[%d].key=%d\n",i,k);
            else
            printf(" 提示:未找到%d\n",k);
    break;
        case 7: 
           DispHT(ha,n,m);
    break;
        case 8: 
           avglen(ha,n,m);
    break;
    default:
     
                 break;
    }
    }
    }

    用两种方式实现查找,需要注意两者之间存储结构的差异,因实现同一组关键字的查找,所以关键字必须有序!!

    展开全文
  • 数据结构Data Structures张 凯计算机学院 软件工程系2011年3月12日第9章 查找查找的基本概念静态查找表动态查找表哈希表9.2 动态查找表动态查找表 特点表结构本身是在查找过程动态生成的即对于给定值 key 若表...
  • 各类数据结构的特点

    2016-11-18 18:05:12
    算法对这些结构中的数据进行各种处理。例如,查找一条特殊数据项或对数据进行排序。 掌握这些知识以后可以解决哪些问题呢? 现实世界数据存储 程序员工具 建模 数据结构的特性: 数组:优点是插入快,如果...

    数据结构是对在计算机内存中(有时在磁盘中)的数据的一种安排。数据结构包括数组、链表、栈、二叉树、哈希表等等。算法对这些结构中的数据进行各种处理。例如,查找一条特殊的数据项或对数据进行排序。
    掌握这些知识以后可以解决哪些问题呢?
    现实世界数据存储
    程序员的工具
    建模
    数据结构的特性:
    数组:优点是插入快,如果知道下标,可以非常快地存取。缺点是查找慢,删除慢,大小固定。
    有序数组:优点是比无序的数据查找快。缺点是删除和插入慢,大小固定。
    栈:优点是提供后进先出方式的存取。缺点是存取其他项很慢。
    队列:提供先进先出方式的存取。缺点是存取其他项很慢。
    链表:优点是插入快,删除快。缺点是查找慢。
    二叉树:优点是查找、插入、删除都快(如果树保持平衡)。缺点是删除算法复杂。
    红-黑树:查找、插入、删除都快。树总是平衡的。缺点是算法复杂。
    2-3-4树:优点是查找、插入、删除都快。树总是平衡的。类似的树对磁盘存储有用。缺点是算法复杂。
    哈希表:优点是如果关键字已知则存取极快。插入快。缺点是删除慢,如果不知道关键字则存取很慢,对存储空间使用不充分。
    堆:优点是插入、删除快,对最大数据项的存取很快。缺点是对其他数据项存取慢。
    图:优点是对现实世界建模。缺点是有些算法且复杂。
    对于大多数数据结构来说,都需要知道如何插入一条新的数据项,如何寻找某一特定的数据项,如何删除某一特定的数据项,还需要知道如何迭代地访问某一数据结构中的各数据项,以便进行显示或其他操作。另一种重要的算法范畴是排序。

    这里写图片描述

    一、通用数据结构:数组,链表,树,哈希表
    它们被称之为通用的数据结构是因为它们通过关键字的值来存储并查找数据,这一点在通用数据库程序中常见到(栈等特殊结构正好相反,它们只允许存取一定的数据项)。
    通用数据结构可以完全按照速度的快慢来分类:
    数组和链表是最慢的,树相对较快,哈希表是最快的。
    但并不是使用最快的结构永远是最好的方案。这些最快的结构也有缺陷,首先,它们的程序在不同程度上比数组和链表的复杂;其次,哈希表要求预先知道要存储多少数据,数据对存储空间的利用率也不是非常高。普通的二叉树对顺序的数据来说,会变成缓慢的O(N)级操作;而平衡树虽然避免了上述的问题,但是它的程序编制起来却比较困难。

    数组在下列情况下很有用:
    数据量较小
    数据量的大小事先可预测
    如果存储空间足够大的话,可以放松第二条,创建一个足够大的数组来应付所有可以预见的数据输入。
    如果插入速度很重要的话,使用无序数组。如果查找速度很重要的话,使用有序数组,并用二分查找。数组元素的删除总是很慢,这是由于为了填充空出来的单元,平均半数以上的数组元素要被移动。在有序数组中的遍历是很快的,而在无序的数组不支持这种功能。
    向量(如Java中的向量类)是一种当数据太满时可以自己扩充空间的数组。向量可以应用于数据量不可预知的情况下。然而,在向量扩充时,要将旧的数据拷入一个新的空间中,这一过程会造成程序明显的周期性暂停。
    如果需要存储的数据量不能预知或者需要频繁地插入删除数据元素时,考虑使用链表。当有新的元素加入时,链表就开辟新的所需要的空间,所以它甚至可以占满全部可用内存;在删除过程中没有必要像数组那样添补“空洞”。

    二、专用数据结构:栈,队列,优先级队列
    三、排序:插入排序,希尔排序,快速排序,归并排序,堆排序
    四、图:邻接矩阵,邻接表
    五、外部存储:顺序存储,索引文件,B-树,哈希方法

    展开全文
  • 本篇博客主要用于对查找方面的数据结构做一个简单介绍,能满足面试时候问问题深度即可,所以不会给出代码实现。一、静态查找表 静态查找表主要满足一下两点: a.查找某个“特定”数据元素是否在查找;...
  • 1掌握排序算法及基本思想及实现技术能够根据实际问题特点的要求选择合理排序方法理解排序在数据处理中的重要性 学会比较各种排序方法稳定性分析以及在最好 最坏和平均情况时间性能分析 掌握顺序查找和折半...
  • 1.掌握顺序查找、折半查找及二叉排序树上查找的基本思想和算法实现,了解怎样对各种查找方法进行时间性能(平均查找长度)分析。 2.掌握各种排序方法的基本思想、排序过程、算法实现,能进行时间和空间性能的分析...
  • 如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。 ...
  • 数据结构-二叉查找

    2020-02-29 14:20:29
    二叉查找树是二叉树最常见的一种类型,是为了实现快速查找而存在的, 最大的特点是支持快速的增删查,的每个节点的值都大于左子树节点的值**,小于右子树节点**的值。 二叉查找的特点是任意一个节点的左子树...
  • 数据结构】分块查找

    千次阅读 2019-04-24 20:39:40
    1.分块查找的步骤: 选取各块的最大关键字构成一个索引表 对索引表尽心二分查找或顺序查找,对块数据进行顺序查找 2.分块查找特点: 索引表为有序表 块内节点可以无序 前一块的的最大值要小于后一块的...
  • 数据结构中的

    2015-04-01 17:45:45
    数据结构中为了存储和查找的方便,用各种树结构来存储文件,本章就浅谈一下各种树的表示方法、特点及各自的用途,本章设计的树结构包括:二叉查找树(二叉排序树)、平衡二叉树(AVL树)、红黑树、B-树、B+树、字典...
  • 数据结构中的各种树

    2020-07-06 12:09:16
    数据结构中为了存储和查找的方便,用各种树结构来存储文件,本章就浅谈一下各种树的表示方法、特点及各自的用途,本章设计的树结构包括:二叉查找树(二叉排序树)、平衡二叉树(AVL树)、红黑树、B-树、B+树、字典...
  • 数据结构 第九章查找

    2021-04-12 20:40:20
    顺序查找的性能分析 空间复杂度:一个辅助空间。 时间复杂度: 查找成功时的平均查找长度 设表各记录查找概率相等 ASLs(n)=(1+2+ … +n)/n =(n+1)/2 查找不成功时的平均查找长度 ASLf =n+1 特点 ...
  • 数据结构 查找 动态查找表一

    千次阅读 2007-04-11 19:38:00
    动态查找的特点:表结构本身实在查找过程动态生成的,即对于给定值key,若表存在关键字等于key的记录,则查找成功返回,否则插入关键字等于key的记录。(1)二叉排序树(binary sort tree,或二叉查找树)中序...
  • 数据结构-静态表查找

    2019-09-06 11:28:04
    静态表查找 顺序查找 核心:从数据的第一个元素...特点:顺序查找平均关键字匹配次数为表长的一半,其时间复杂度为O(n),顺序查找的优点是对表无要求,插入数据可在O(1)内完成。缺点是时间复杂度较大,数据规模较大...
  • 数据结构中数据存储几种形式 1.栈:数据从一个口进,从一个口出 特点:先入后出 2.队列:数据用两个口进,从两个口出 特点:先入先出 3.数组: 特点查找容易,增删难 例子: int [] arr = new int [1,2,3,4]; 当...
  • 二叉查找树(Binary Search Tree)Ⅰ 前言Ⅱ 什么是二叉查找树Ⅲ ...二叉查找树最大的特点就是,支持动态数据集合的快速插入、删除以及查找操作。 Ⅱ 什么是二叉查找树 二叉查找树是二叉树最常用的一种类型,也叫二
  • 一、二叉查找树    1.定义特点维基百科 ... =》理解RootNode为整个数中的一个中间节点key  =》Quick Sort概念  =》实例化时候不用找到某两个节点范围  =》按照InOrder Trav...
  • 数据结构中为了存储和查找的方便,用各种树结构来存储文件,本章就浅谈一下各种树的表示方法、特点及各自的用途,本章设计的树结构包括:二叉查找树(二叉排序树)、平衡二叉树(AVL树)、红黑树、B-树、B+树、字典...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,332
精华内容 932
关键字:

数据结构中查找的特点

数据结构 订阅