`

算法学习 之查询

    博客分类:
  • c++
 
阅读更多

 

/******************顺序查找******************/
//假设静态查找表的顺序存储结构为
typedef struct
{
ElemType *elem;   // 数据元素存储空间基址,建表时
// 按实际长度分配,0号单元留空
int length;         // 表的长度
} SSTable;

int Search_Seq(SSTable ST, KeyType key) 
{  /*在顺序表ST中顺序查找其关键字等于key的数据元素。若找到,则函数值为该元素在表中的位置,否则为0。*/
ST.elem[0] = key;      // “哨兵”
for (i=ST.length; ST.elem[i] != key; --i); // 从后往前找
return i; // 找不到时,i为0
} // Search_Seq

/****************比较无监视哨的查找算法***********/
int location (SSTable ST , ElemType& e) 
{
k = 1;
while ( k <= ST.length && ST.elem[k] !=e) 
k++;
if ( k<=ST.length) return k; 
else return 0;
} //location
//在表长>1000时,将使算法的执行时间几乎增加一倍。
//为此,改写顺序表的查找算法, 算法中附设监视哨,以避免循环时每一步都要判别是否数组出界。

/******************有序表折半查找******************/
int Search_Bin ( SSTable ST, KeyType key ) 
{  // 在有序表ST中折半查找其关键字等于key的数据元素。
// 若找到,则函数值为该元素在表中的位置,否则为0。
low = 1;    high = ST.length;  //置区间初值
while ( low <= high ) 
{
mid = (low + high) / 2;
if (ST.elem[mid] == key)   return mid;  //找到
else if ( ST.elem[mid] < key )
high = mid - 1; // 继续在前半区间进行查找
else  low = mid + 1; // 继续在后半区间进行查找
}
return 0; // 顺序表中不存在待查元素
} // Search_Bin
分享到:
评论
1 楼 sblig 2012-05-22  
#include <stdio.h>
#include <stdlib.h>
#define  OK 1
#define  ERROR  0
#define LIST_INIT_SIZE  80
typedef struct {
  ElemType  *elem;
  int       length;
  int       listsize;
} SqList;

int ListLength_Sq(SqList L)
{
    return(L.length);
}
Status InitList_Sq(SqList &L)
{
    L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)) ;
    L.length=0;
    L.listsize=LIST_INIT_SIZE;
    return OK;
}
Status GetElem_Sq(SqList L, int i, int &e)
{
  e=L.elem[i-1];
  return OK;
}
int LocateElem_Sq(SqList L, int e)
{
    int i=0;
    while(i<L.length&&L.elem[i]!=e)
          i++;
    if(i==L.length)return 0;
    else return i;
}
Status ListInsert_Sq (SqList &L, int pos, ElemType e)
{
   ElemType *q,*p;
   if (pos<1||pos>L.length+1)  return ERROR;
   if (L.length >= L.listsize) return ERROR;

    q =&(L.elem[pos-1]);
    for (p=&(L.elem[L.length-1]); p>=q; p--)
       *(p+1) = *p;
   *q = e;
   L.length++;

  return OK;
}

相关推荐

    数据库查询优化算法

    在数据库领域,有三种经典的查询优化算法:基于成本的优化、基于规则的优化以及动态规划优化。下面将详细介绍这三种算法及其在实际应用中的作用。 1. 基于成本的优化(Cost-Based Optimization, CBO) 基于成本的...

    算法学习笔记.pdf

    算法学习是计算机科学与技术领域中非常重要的基础知识,掌握常用算法对于解决各类问题至关重要。在本篇算法学习笔记中,对一系列重要且常用的算法进行了整理和总结,以下是对文档内容中提及的知识点的详细解读。 一...

    算法 图论 查询文件

    5. **最小生成树**:Kruskal和Prim算法可以找到一个加权无向图的最小生成树,即包含所有顶点且边权重之和最小的子集。这两种算法分别基于并查集和贪心策略。 6. **网络流**:如Ford-Fulkerson方法和Edmonds-Karp...

    数据结构和算法学习笔记

    ### 数据结构和算法学习笔记之复杂性分析及补偿分析法详解 #### 一、引言 数据结构和算法是计算机科学中的核心概念,对于软件开发人员来说至关重要。它们不仅能够帮助我们有效地解决问题,还能优化程序的性能。在...

    基于BM算法的字符查询程序

    通过学习和理解这个程序,开发者不仅可以掌握BM算法的原理和实现,还能加深对.NET Core平台的理解,提升跨平台开发的能力。同时,对于需要处理大量文本查询的场景,这样的工具无疑提供了强大的助力。

    基于半连接的分布式数据库查询优化算法探讨

    分布式数据库查询优化是关系数据库管理系统领域中的一个重要课题,它直接影响到数据库系统的性能,尤其在处理大量数据和复杂查询时,高效的查询优化算法可以显著减少查询响应时间,提高系统吞吐量。本文讨论的基于半...

    公交查询及换乘的算法源代码示例

    公交查询及换乘的算法是计算机科学在交通信息系统中的一项重要应用,主要目的是为用户提供最优化的公共交通路线建议。...通过学习这些材料,你可以深入了解公交查询系统的实现细节,提升自己的算法设计和编程能力。

    深度学习算法汇总

    反向传播算法是深度学习训练过程中最核心的技术之一,它利用链式法则计算梯度并更新权重。通过反向传播,可以高效地调整网络中的参数以优化性能。 #### 二、深度学习进阶篇 在掌握了基础概念之后,本部分将进一步...

    算法学习攻略

    《算法学习攻略》 在计算机科学领域,算法是解决问题的核心工具,它关乎程序的效率和效果。本攻略旨在提供一个全面的算法学习路径,帮助初学者及进阶者提升算法能力,同时也适用于准备ACM(国际大学生程序设计竞赛...

    算法学习:暴雪哈希算法

    ### 暴雪哈希算法详解 #### 一、引言 在计算机科学领域,哈希算法被广泛应用于数据检索、存储以及管理等场景。暴雪哈希算法作为一款高效且经典的哈希算法,在游戏开发及文件管理等领域具有重要的应用价值。本文将...

    Way-to-Algorithm-算法之路.pdf

    算法之路概览 本资源摘要信息涵盖了算法之路的概览,包括排序、搜索、数据结构、动态规划、图论等领域的重要知识点。...本资源摘要信息涵盖了算法之路的重要知识点,为读者提供了一个系统的算法学习指南。

    数据库系统基础讲义第19讲数据库查询实现算法I一趟扫描算法

    通过对数据库查询实现算法的理解,特别是通过学习一趟扫描算法,我们可以更好地理解数据库是如何高效地处理查询请求的。在实际应用中,合理选择和优化查询执行算法可以显著提升数据库系统的性能和响应速度。随着技术...

    学习算法之路

    ### 学习算法之路知识点详解 #### 第一阶段:经典常用算法 本阶段主要针对一些基础但非常重要的算法进行深入学习和练习,旨在通过大量重复练习达到熟练掌握的程度。 ##### 1. 最短路算法 - **Floyd算法**:适用于...

    一种改进的分布式数据库查询优化遗传算法.pdf

    然而,分布式数据库存在查询处理速度慢的问题,这也是目前研究的热点之一。查询优化是解决该问题的有效方法,目的是使得通信费用最低而响应时间最短。典型的查询优化算法包括基于半连接的SDD-1算法、基于直接连接的R...

    机器学习算法PageRank

    此外,算法的某些扩展,例如本文件中提到的“时序PageRank”(Timed-PageRank),表明了算法还在不断演化中,以适应网络环境的变化和用户查询行为的演变。时序PageRank考虑了网页排名随时间变化的因素,为网络上的...

    改进粒子群优化算法的数据库查询优化方法.pdf

    数据库查询优化技术是数据库管理系统中的关键技术之一。在数据库查询过程中,优化算法能够帮助设计出高效的查询计划,从而减少查询时间,提高查询的准确性。然而,现有的数据库查询优化方法存在查询效率低和查询错误...

    算法课程设计文件查询

    在“算法课程设计文件查询”这个主题中,我们可以深入探讨几个关键知识点,这些知识点对于学习和理解算法设计、文件查询以及课程设计过程至关重要。在这个压缩包中,包含了任务书、课程报告以及源代码,这些都是一个...

    SQL查询语句转换成图结构的算法设计与实现.pdf

    SQL查询语句转换成图结构的算法设计与实现 本文旨在设计并实现将SQL查询语句转换成图结构的算法,利用图神经网络对SQL查询语句进行分析和处理。该算法可以将SQL查询语句中的字段、表名、函数、操作符、值和关键字...

    机器学习十大经典算法总结

    PageRank算法的优点是完全独立于查询,只依赖于网页间的链接结构,可以离线计算。但它忽略了时效性和新页面的排名问题,旧网页由于积累了许多链接可能排名过高。 7. AdaBoost算法 AdaBoost算法通过迭代训练不同的...

Global site tag (gtag.js) - Google Analytics