查找算法

Suzhou
• 阅读 61
顺序查找

顺序查找又称为线性查找,对线性表和链表都适用。 线性表可以通过数组下标递增来顺序扫描每个元素,链表可以通过next指针依次扫描每一个元素。

::: tip 指针实现顺序表时,顺序表中是指针时,在定义顺序表的结构体后,需要对顺序表初始化,初始化时为指针申请堆空间,堆空间的使用类似于数组,和数组形式的区别是可以动态控制数组的大小。 :::

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//指针实现顺序表
typedef int Elemtype;
//定义顺序表
typedef struct
{
    Elemtype* elem;  //指针,类型自定,申请堆空间的起始地址存入elem
    int TableLen;  //存储在动态数组中元素的个数
}SSTable;

void ST_Init(SSTable& ST, int len)
{
    ST.TableLen = len + 1;  //需要多申请一个位置,原因是0号位置存放“哨兵”
    ST.elem = (Elemtype*)malloc(sizeof(Elemtype) * ST.TableLen);  //指针elem指向的每个元素都是Elemtype类型的(int)
    int i;
    srand(time(NULL));  //随机数生成
    for (i = 1; i < ST.TableLen; i++)  //0号位置是哨兵,随机数从1号位置开始
    {
        ST.elem[i] = rand() % 100;  //%100使得生成的随机数在0-99之间
    }
}

//打印顺序表
void ST_Print(SSTable ST)
{
    int i;
    for (i = 1; i < ST.TableLen; i++)
    {
        printf("%3d", ST.elem[i]);  //类似于数组访问,elem相当于数组名
    }
    printf("\n");
}

int search_seq(SSTable ST, Elemtype key)
{
    ST.elem[0] = key;  //key存在0号位置,作为哨兵,哨兵的存在可有可无,哨兵存在的意义是循环判断条件不用写i>=0
    int i;
    for (i = ST.TableLen - 1; ST.elem[i] != key; i--);
    return i;
}
int main()
{
    SSTable ST;
    ST_Init(ST, 10);
    ST_Print(ST);  //打印顺序表中的元素(顺序表中的元素位置从1开始)
    Elemtype key;
    printf("请输入要查找的key值\n");
    scanf("%d", &key);
    int pos;  //查找函数返回的下标位置
    pos = search_seq(ST, key);
    if (pos)
    {
        printf("找到了,位置为%d\n", pos);
    }
    else
    {
        printf("没有找到\n");
    }
    return 0;
}

折半查找

::: warning 折半查找又称二分查找,只适用于有序顺序表(升序或降序都可以)。 ::: 折半查找的基本思想:首先将给定值key与表中中间位置的元素比较,若相等则查找成功,返回该元素的存储位置;若不等,则所需查找的元素只能在中间元素以外的前半部分或后半部分(例如,在查找表升序排列时,若给定值key大于中间元素,则所查找的元素只可能在后半部分),然后在缩小的范围内继续进行同样的查找,如此重复。直到找到为止,或确定表中没有所需要查找的元素,则查找不成功,返回查找失败的信息。 ::: warning qsort只能用来排序数组,不能用来排序链表。 ::: qsort函数头文件:#include<stdlib.h> 函数原型:void qsort(void * base,size_t num,size_t size,int ( * compare)(const void * ,const void * )) base:指向要排序的数组的第一个元素的指针(数组地址)。 num:由 base 指向的数组中元素的个数(参与排序的目标数组元素个数)。 size:数组中每个元素的大小,以字节为单位(推荐使用sizeof(s[0])这样的表达式)。 int ( * compare)(const void * ,const void * )是一个函数指针,需要编写实现compare函数,将函数名传递到qsort函数中作为参数调用。

::: tip 折半查找代码流程: 1、初始化顺序表,输入随机10个元素。 2、使用qsort进行排序,排序完毕后打印。 3、输入要查找的元素值,存入变量key 中。 4、通过二分查找查找对应key值,找到则输出在顺序表中的位置,没找到输出未找到。 :::

compar:用来比较两个元素的函数,即函数指针(回调函数)。 compare函数定义是int compare(const void * a,const void * b); 如果是升序,即a比b大,返回正值;如果是降序,即a比b小,返回负值;a和b相等则返回0。 a和b指向数组中的任意两个元素,qsort可以对多种类型的数组进行排序,在使用a和b之前需要先将a和b由void类型强制转换成其它类型。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef int Elemtype;
typedef struct
{
    Elemtype* elem;  //整型指针
    int TableElem;  //存储在动态数组中的元素个数
}SSTable;
//随机树表初始化,没有使用哨兵
void InitTable(SSTable& ST, int len)
{
    ST.TableElem = len;
    ST.elem = (Elemtype*)malloc(sizeof(Elemtype));
    int i = 0;
    srand(time(NULL));
    for (i; i < ST.TableElem; i++)
    {
        ST.elem[i] = rand() % 100;
    }
}
//打印随机数
void PrintTable(SSTable ST)
{
    int i = 0;
    for (i; i < ST.TableElem; i++)
    {
        printf("%3d", ST.elem[i]);
    }
    printf("\n");
}
//二分查找
int binary_search(SSTable ST, Elemtype key)
{
    int low = 0, high = ST.TableElem - 1;
    int mid;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (key < ST.elem[mid])
        {
            high = mid - 1;
            mid = (low + high) / 2;

        }
        else if (key > ST.elem[mid])
        {
            low = mid + 1;
            mid = (low + high) / 2;

        }
        else
        {
            return mid;
        }
    }
    return -1;
}

//函数名compare中存放着函数入口地址,是函数指针类型
int compare(const void* left, const void* right)
{
    return *(int*)left - *(int*)right;  //从小到大排序,(int*)表示强制类型转换,*表示解引用,通过地址找到指针指向的元素
    //如果是升序,即left比right大,返回正值;如果是降序,left比right小,返回负值;left和right相等,返回0
    //return *(int*)right-*(int*)left;  //从大到小排序
}

int main() {
    SSTable ST;
    int x;
    scanf("%d", &x);
    InitTable(ST, x);
    PrintTable(ST);
    qsort(ST.elem, ST.TableElem, sizeof(Elemtype), compare);
    PrintTable(ST);
    Elemtype key;
    printf("input search key\n");
    scanf("%d", &key);
    int ret = binary_search(ST, key);
    if (ret != -1)
    {
        printf("search success,location %d\n", ret);
    }
    else {
        printf("seasrch faild\n");
    }
    return 0;
}

二叉排序树

二叉排序树又称二叉查找树。 ::: tip 二叉排序树或者是一棵空树,或者是具有下列特点的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值; (3)左、右子树也分别为二叉排序树; ::: 二叉排序树的最大查找次数是树的高度。 二叉排序树的遍历使用中序遍历(其他遍历方式无意义)。 中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。相当于将二叉排序树踩扁,自左向右遍历,此时二叉排序树中序遍历后结果是有序(由小到大)的。 注:二叉排序树不考虑树中存放相等的元素。 ::: warning 二叉排序树删除节点时的特殊情况:如果要删除的节点是根节点或含有左右子树的节点,可以将该节点的左子树最右侧的节点值(左子树中的最大数据)或右子树最左侧的节点值(右子树中的最大数据)替换到删除结点的位置,替换后左子树最右侧的节点或右子树最左侧的节点被删除,由下面的左子树或右子树顶上,重新组成的二叉树仍满足二叉排序树的要求。 (拿到左子树的最右侧节点的方法是先拿到左子树的根节点,然后循环不断向下拿到右孩子,右子树的最左节点类似。) ::: 如果没有找到删除的节点时,删除函数中根节点T变为NULL,return 0,程序结束。

#include <stdio.h>
#include <stdlib.h>

typedef int Keytype;
//存放树的节点
typedef struct BSTNode
{
    Keytype data;
    struct BSTNode* lchild;
    struct BSTNode* rchild;
}BSTNode, * BiTree;

//非递归方式创建二叉排序树
//二叉排序树的节点插入
int BST_Insert(BiTree& T, Keytype k)
{
    BiTree TreeNew = (BiTree)calloc(1, sizeof(BSTNode));  //节点进入后创建节点存储新申请的空间
    TreeNew->data = k;
    if (NULL == T)
    {
        T = TreeNew;  //树为空时,新节点TreeNew作为树根
        return 0;
    }
    BiTree p = T, parent = NULL;  //树根存在时使用p从树根开始查找新节点TreeNew应该存放的位置
    while (p)
    {
        parent = p;  //parent为p的父节点
        //不考虑元素相等的情况
        if (k < p->data)
        {
            p = p->lchild;  //p置为NULL
        }
        else if (k > p->data)
        {
            p = p->rchild;  //p置为NULL
        }
        else
        {
            return -1;  //元素相等
        }
    }
    //while循环结束后p找到应该存放的位置
    //判断新节点TreeNew放在parent的位置
    if (k < parent->data)
    {
        parent->lchild = TreeNew;  //小于放在父节点左边
    }
    else {
        parent->rchild = TreeNew;  //大于放在父节点右边
    }
    return 0;
}

//二叉排序树的创建
void CreatBSTree(BiTree& T, Keytype* str, int len)  //数组名是指针,len表示,数组元素个数
{
    //每次向二叉排序树中放入一个节点
    int i;
    for (i = 0; i < len; i++)
    {
        BST_Insert(T, str[i]);  //引用支持子函数传递
        //函数CreatBSTree使用引用符号,实际引用操作发生在函数CreatBSTree中的BST_Insert内
    }
}

//二叉排序树的中序遍历
void InOrder(BiTree T)
{
    if (NULL != T)
    {
        InOrder(T->lchild);
        printf("%3d", T->data);
        InOrder(T->rchild);
    }
}

//查找
BiTree BST_Search(BiTree T, Keytype k)
{
    while (NULL != T && k != T->data)
    {
        if (k < T->data)
        {
            T = T->lchild;
        }
        else {
            T = T->rchild;
        }
    }
    return T;
}

//通过递归实现删除
void DeleteNode(BiTree& T, Keytype key)
{
    if (NULL == T)
    {
        return;
    }
    if (key < T->data)  //要删除的节点比当前树根节点小
    {
        DeleteNode(T->lchild, key);  //在左子树上删除,执行递归
    }
    else if (key > T->data)  //要删除的节点比当前树根节点大
    {
        DeleteNode(T->rchild, key);  //在右子树上删除,执行递归
    }
    else  //找到要删除的节点
    {
        if (NULL == T->lchild)  //要删除的节点左子树为空时,用该节点的右子树顶替该节点
        {
            BiTree TempNode = T;  //使用临时指针TempNode指向原来指针T指向的空间,指针T指向的空间是要删除的节点的空间
            T = T->rchild;  //该节点的右子树顶替该节点
            free(TempNode);  //释放删除节点的空间
        }
        else if (NULL == T->rchild)  //要删除的节点右子树为空时,用该节点的左子树顶替该节点
        {
            BiTree TempNode = T;  //使用临时指针TempNode指向原来指针T指向的空间,指针T指向的空间是要删除的节点的空间
            T = T->lchild;  //该节点的左子树顶替该节点
            free(TempNode);  //释放删除节点的空间
        }
        else  //左右子树都不为空时
        {
            //拿左子树中的最右节点,左子树中的最右节点就是左子树中的最大数据
            BiTree TempNode = T->lchild;
            while (NULL != TempNode->rchild)  //一直向下拿到右孩子为空时停止
            {
                TempNode = TempNode->rchild;
            }
            T->data = TempNode->data;  //左子树中的最大数据替换掉要删除的值
            DeleteNode(T->lchild, TempNode->data);  
            //删除左子树中的最右节点,不是改变后的根节点,传T->lchild,即要在左子树的上找到要删除的值,并将该节点删除
        }
    }
}

int main()
{
    BiTree T = NULL;  //指向树根的指针
    Keytype str[7] = { 54,20,66,40,28,79,58 };
    CreatBSTree(T, str, 7);
    InOrder(T);  //二叉排序树中序遍历后结果是由小到大的
    printf("\n");
    BiTree search, parent;
    search = BST_Search(T, 66, parent);  //找到后返回查找值的位置和父节点
    if (search)
    {
        printf("find key %d\n", search->data);
    }
    else {
        printf("not find\n");
    }
    DeleteNode(T, 66);
    InOrder(T);
    printf("\n");
    return 0;
}
 20 28 40 54 58 66 79
find key 66
 20 28 40 54 58 79

题目分析

查找算法 查找算法 查找算法 当两个有序序列中的元素个数为奇数时,只能舍弃中位数之前、之后的元素,不能舍弃中位数。 当序列中元素个数为偶数时,如舍弃到最后序列中只剩下两个元素时,此时a<b,元素a前没有可以舍弃的元素时,可以舍弃自己。即小于时舍弃中位数之前的元素包括中位数,大于时舍弃中位数之后的元素。

#include <stdio.h>

int MidSearch(int* A, int* B, int x)
{
    // art简写为s,代表首位数字,end简写为d,代表末位数字,m代表中位数
    int s1 = 0, d1 = x - 1, m1, s2 = 0, d2 = x - 1, m2;  //0和4表示数组下标,m1=(s1+d1)/2,m2=(s2+d2)/2
    while (s1 != d1 || s2 != d2)  //循环结束条件是两个数组最后各剩下一个元素,即s1=d1和s2=d2
    {
        m1 = (s1 + d1) / 2;
        m2 = (s2 + d2) / 2;
        if (A[m1] == B[m2])
        {
            return A[m1];  //或者B[m2],满足条件1
        }
        else if(A[m1] < B[m2])  //满足条件2
        {
            if ((s1 + d1) % 2 == 0)  //数组中元素个数为奇数(s1起始位置为0)
            {
                s1 = m1;  //舍弃数组A中间点m1之前的元素保留中间点m1
                d2 = m2;  //舍弃数组B中间点m2之后的元素保留中间点m2
            }
            else  //数组中元素个数为偶数,m1<m2
            {
                s1 = m1 + 1;  //舍弃数组A中间点m1之前的元素包括中间点m1
                d2 = m2;      //舍弃数组B中间点m2之后的元素保留中间点m2
            }
        }
        else  //A[m1]>B[m2])  //满足条件3(与条件2对称)        
        {
            if ((s1 + d1) % 2 == 0)  //数组中元素个数为奇数(s1起始位置为0)
            {
                d1 = m1;  //舍弃数组A中间点m1之后的元素保留中间点m1
                s2 = m2;  //舍弃数组B中间点m2之后的元素保留中间点m2
            }
            else  //数组中元素个数为偶数,m1<m2
            {
                d1 = m1;      //舍弃数组A中间点m1之后的元素保留中间点m1
                s2 = m2 + 1;  //舍弃数组B中间点m2之后的元素包括中间点m2
            }
        }
    }
    return A[s1] < B[s2] ? A[s1] : B[s2];  //此时s1=d1,s2=d2,题目取中位数11,即较小的值A[s1]
    //三目运算符,如果A[s1] < B[s2]表达式为真,取A[s1],如果A[s1] > B[s2]表达式为假,取B[s2]
}
int main()
{
    int A[] = { 11,13,15,17,19 };
    int B[] = { 2,4,6,8,20 };
    int mid = MidSearch(A, B, 5);
    printf("mid=%d\n", mid);
}
mid=11

练习

读取10个元素 87 7 60 80 59 34 86 99 21 3,然后建立二叉查找树,中序遍历输出3 7 21 34 59 60 80 86 87 99,针对有序后的元素,存入一个长度为10的数组中,通过折半查找找到21的下标(下标为2),然后输出2。

#include <stdio.h>
#include <stdlib.h>

typedef int keytype;
typedef struct Node
{
    keytype data;
    struct Node* lchild;
    struct Node* rchild;
}BSNode,*BiTree;

//插入
void BSTreeInsert(BiTree& T, keytype x)
{
    BiTree NewNode = (BiTree)calloc(1, sizeof(BSNode));
    NewNode->data = x;
    if (NULL == T)
    {
        T = NewNode;
        return;
    }
    BiTree p = T;  //p从根开始寻找新节点存放位置
    BiTree parent = NULL;
    while (p)
    {
         parent = p;
        if (x < p->data)
        {
            p = p->lchild;
        }
        else
        {
            p = p->rchild;
        }
        //不考虑查找树内元素相等的情况
    }
    //新节点放入位置
    if (x < parent->data)
    {
        parent->lchild = NewNode;
    }
    else
    {
        parent->rchild = NewNode;
    }
}

//创建二叉查找树
void BSTree(BiTree& T, keytype* str, int len)
{
    int i = 0;
    for (i; i < len; i++)
    {
        BSTreeInsert(T, str[i]);
    }
}

//中序遍历
void InOrder(BiTree T,int arr[10])
{
    static int i = 0;
    if (NULL == T)
    {
        return;
    }
    InOrder(T->lchild,arr);
    printf("%3d", T->data);
    arr[i] = T->data;
    i++;
    InOrder(T->rchild,arr);
}

//折半查找
int binary_search(int* arr, keytype x)
{
    int low = 0, high = 9, mid = (low + high) / 2;
    while (low <= high)
    {
        if (x < arr[mid])
        {
            high = mid - 1;
        }
        else if (x > arr[mid])
        {
            low = mid + 1;
        }
        else
        {
            return mid;
        }
        mid = (low + high) / 2;
    }
}

int main()
{
    int str[10] = { 87,7,60,80,59,34,86,99,21,3 };
    BiTree T = NULL;
    BSTree(T, str, 10);
    int arr[10] = {};
    InOrder(T,arr);
    printf("\n");
    int a = 21;
    int ret = binary_search(arr,a);
    if (ret)
    {
        printf("%d", ret);
    }
    else
    {
        printf("没有找到");
    }
    return 0;
}

::: warning 易错点: 1.中序遍历排好序后,将新的顺序输出并放进数组中,需要先打印出来,然后再放入数组。 2.放入数组时不使用新的函数,使用static变量。 原因:中序遍历执行递归时,打印数组时会打印多份数组同一位置数据,使用函数传出去时,也会对数组同一位置多次赋值。 :::

点赞
收藏
评论区
推荐文章
22 22
1年前
【数据结构之链表】看完这篇文章我终于搞懂链表了
一览:本文从零介绍链式存储结构的线性表——单链表。包括以下内容:什么是链式存储存储结构?单链表的结构辨析头结点、头指针等易混淆概念基本的增删改查操作(不带头结点和带头结点)单链表与顺序表的对比线性表的链式存储结构在一文中我们介绍了一种“用曲线连接”的线性表,“曲线”是一种形象化的语言,实际上并不会存在所谓“曲线”的这种东西。所谓“曲线连
林末 林末
1年前
折半查找-Python版(二分查找)
介绍二分查找也称折半查找(BinarySearch),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。前提必须待查找的序列有序时间复杂度O(log2n)原理1)确定该期间的中间位置K2)将查找的值t与arrayk比较,若相等,查找成功返回此位置;否则确定新的查找区域,继续二分
22 22
1年前
【数据结构之栈】用详细图文把「栈」搞明白(原理篇)
【系列文章合集】顺序存储结构的线性表(https://mp.weixin.qq.com/s/OGbxsh0aNh1woHA85weZw)如何掌握C语言的一大利器——指针?(https://mp.weixin.qq.co
22 22
1年前
【数据结构之顺序表】用图和代码让你搞懂顺序结构线性表
什么是线性表?所谓线性,即一条线,这条线可以是直线,也可以是曲线。所谓表,肯定都不陌生,生活中有各种各样的表或者表格。我们在表格中填写各种各样的信息,通过表格,能够很好地对信息进行分类储存和分析。表的特点有:表由若干单元格组成单元格之间有顺序除特殊位置的单元格(首起和结尾)有一个“邻居”外,其他单元格都有两个“邻居”。那么什么是线性表呢?简单来说,就是
Stella981 Stella981
1年前
HashMap的实现原理
HashMap概述HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。HashMap的数据结构在Java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数
Wesley13 Wesley13
1年前
Java HashSet集合的子类LinkedHashSet集合
说明HashSet保证元素的唯一性,可是元素存放进去是没有顺序的。在HashSet下面有一个子类java.util.LinkedHashSet,它是链表哈希表(数组链表或者数组红黑树)组合的一个数据结构。即相对HashSet而言,多了一个链表结构。多了的那条链表,用来记录元素的存储顺序,保证元素有序举例Hash
Wesley13 Wesley13
1年前
D1
1\.数据结构  1.1线性结构  (1)最常用的数据结构,特点是数据元素之间存在一对一的线性关系  (2)有两种不同的存储结构,即顺序存储结构和链式存储结构    顺序存储的线性表称为顺序表,顺序表中的存储元素是连续的    链式存储的线性表称为链表,链表中的存储元素不一定是连续的,元素节点中存放数据元素以及相邻元素的地址信息
Wesley13 Wesley13
1年前
C++ 顺序表 代码实现
线性表存储在计算机中可以采用多种方式,以下是按照顺序存储方式实现:优点:查找很方便缺点:插入元素、删除元素比较麻烦,时间复杂度O(n)1ifndefSeqList_h2defineSeqList_h3include<iostream4usingnamespacestd;
Wesley13 Wesley13
1年前
C语言利用动态数组实现顺序表(不限数据类型)
实现任意数据类型的顺序表的初始化,插入,删除(按值删除;按位置删除),销毁功能。、顺序表结构体  实现顺序表结构体的三个要素:(1)数组首地址;(2)数组的大小;(3)当前数组元素的个数。1//顺序表结构体2structDynamicArray{3voidaddr;//指向数组的首地址(
Suzhou Suzhou
1星期前
线性表
线性表的顺序存储实现(数组形式)称为顺序表。线性表顺序表示原理解析这里描述的线性表是逻辑结构的,独立于存储结构。线性表的顺序表示简称顺序表。顺序表实现线性表的方式是使用数组。线性表第一个元素的数组下标是0。另外一种实现顺序表的方法:使用数组方式比动态分配更
Suzhou
Suzhou
Lv1
这个网站设计堪称垃圾。CTRL+S过后的东西,重启电脑只能保存5行。多按几次CTRL+S还提示频繁保存不了。吐了。
17
文章
2
粉丝
3
获赞