线性表查找

程序员文章站 2024-03-22 18:42:34

...

引入Key类。
Key类指要查找的数据中最关键最有标识性的部分，查找时通过key的比较，快速判断出这个数据是否是要查找的数据。

#include<iostream>

using namespace std;

class Key
{
   int key; //数据中的关键部分，有辨识度
public:
   //static int comparisons; //比较次数
   Key (int x = 0);
   int the_key() const;
};

//int Key::comparisons = 0;

bool operator == (const Key &x,const Key &y); //"=="运算符重载
bool operator > (const Key &x,const Key &y); //">"运算符重载
bool operator < (const Key &x,const Key &y); //"<"运算符重载
bool operator >= (const Key &x,const Key &y); //">="运算符重载
bool operator <= (const Key &x,const Key &y); //"<="运算符重载
bool operator != (const Key &x,const Key &y); //"!="运算符重载

Key::Key(int x)
{
    key = x;
}

int Key::the_key() const
{
    return key;
}

bool operator == (const Key &x, const Key &y)
{
   //Key::comparisons++;
   return x.the_key() == y.the_key();
}

bool operator > (const Key &x, const Key &y)
{
   //Key::comparisons++;
   return x.the_key() > y.the_key();
}

bool operator < (const Key &x, const Key &y)
{
   //Key::comparisons++;
   return x.the_key() < y.the_key();
}

bool operator >= (const Key &x, const Key &y)
{
   //Key::comparisons++;
   return x.the_key() >= y.the_key();
}

bool operator <= (const Key &x, const Key &y)
{
   //Key::comparisons++;
   return x.the_key() <= y.the_key();
}

bool operator != (const Key &x, const Key &y)
{
   //Key::comparisons++;
   return x.the_key() != y.the_key();
}

一.顺序查找(待查找的线性表已经是一个有序线性表)

查找有顺序的线性表,从线性表的第一项开始，逐个进行比较。

#include "list.cpp"
#include "key.cpp"
typedef Key Record;

Error_code sequential_search(const List<Record> &the_list,const Key &target,int &position) //the_list引用提供的线性表，target引用数据中的关键部分，如果查找到将其位置赋给position
{
    int s = the_list.size(); //线性表大小
    for(position = 0;position < s;position++) //遍历
    {
        Record data;
        the_list.retrieve(position,data); //将当前位置中存储的数据赋给data
        if(data == target) return success; //如果data是要查找的数据，则查找成功，position正好是其位置
    }
    return not_present; //如果遍历完仍未找到，说明该线性表中没有这个数据
}

2.2. 查找有顺序的线性表。加入一个哨兵，先将要查找的这一项插入表的末尾，这样遍历表时一定能找到一个正确位置，只需判断所得的位置是否是最后一个位置即可。省去了判断位置信息，不用担心查找超界。

#include "list.cpp"
#include "key.cpp"
typedef Key Record;

Error_code sequential_search(List<Record> &the_list,const Key &target,int &position) //the_list引用提供的线性表，target引用数据中的关键部分，如果查找到将其位置赋给position
{
    Record data;
    int s = the_list.size(); //线性表大小

    the_list.insert(s,target); //将要查找的数据插入表的末尾
    for(position = 0;;position++) //遍历
    {
        the_list.retrieve(position,data); //将当前位置中存储的数据赋给data
        if(data == target) break;//如果data是要查找的数据，则跳出
    }
    the_list.remove(s,data); //删除插入的数据
    if(position < s) return success; //如果position不是最后一项，则成功，position正好是其位置
    return not_present;//如果遍历完仍未找到，说明该线性表中没有这个数据
}

二.插半查找
引出 Orlist类.
将数据有顺序的插入表中,要重载insert函数，覆盖insert，replace函数。

#include "key.cpp"
#include "list.cpp"
typedef Key Record;

class Ordered_list:public List<Record>
{
public:
    Ordered_list(); //构造函数
    Error_code insert(const Record &data); //只传入要插入的数据，由程序找合适的位置插入
    Error_code insert(int position, const Record &data); //传入要插入的数据和指定位置，如果数据在该位置合适则插入，不合适则不插入，返回相应信息
    Error_code replace(int position, const Record &data);//传入要替换的数据和指定位置，如果数据在该位置合适则替换，不合适则不替换，返回相应信息
};

Ordered_list::Ordered_list() //构造函数
{}

Error_code Ordered_list::insert(const Record &data) //以插入的数据为参数传入
{
    int s = size(); //获取线性表的大小
    int position;
    for (position = 0; position < s; position++) //遍历
    {
        Record list_data;
        retrieve(position, list_data); //返回当前位置的数据
        if (data <= list_data) break; //如果当前位置的数据大于等于要插入的数据，跳出
    }
    return List<Record>::insert(position, data); //将新的数据插入这个位置，这个位置原本的数据向后移一位
}

Error_code Ordered_list::insert(int position, const Record &data) //传入要插入的数据和指定位置
{
    Record list_data;
    if (position > 0) //如果指定位置不是线性表头
    {
        retrieve(position - 1, list_data); //返回前一个位置的数据
        if (data < list_data) //判断，要插入的数据应该大于等于前一个位置的数据
            return fail; //如果要插入的数据小于前一个位置的数据，则不能插入
    }
    if (position < size()) //判断指定位置是否合法
    {
        retrieve(position, list_data);//返回当前位置的数据
        if (data > list_data)//判断，要插入的数据应该小于等于当位置的数据
            return fail;//如果要插入的数据大于当前位置的数据，则不能插入
    }
    return List<Record>::insert(position, data); //将新的数据插入这个位置，这个位置原本的数据向后移一位
}

Error_code Ordered_list::replace(int position, const Record &data) //传入要替换的数据和指定位置
{
    Record list_data;
    if (position > 0) //如果指定位置不是线性表头
    {
        retrieve(position - 1, list_data); //返回前一个位置的数据
        if (data < list_data) //判断，要替换的数据应该大于等于前一个位置的数据
            return fail;//如果要替换的数据小于前一个位置的数据，则不能替换
    }
    if (position < size()-1) //判断指定位置是否越界
    {
        retrieve(position+1, list_data);//返回下一个位置的数据
        if (data > list_data)//判断，要替换的数据应该小于等于下一个位置的数据
            return fail;//如果要替换的数据小于下一个位置的数据，则不能替换
    }
    return List<Record>::replace(position, data); //替换这个位置的数据
}

1.将要查找的数据先与线性表的中间位置做比较，如果小于中间位置则说明要找的元素在后半部分，然后继续折半查找后半部分；如果小于中间位置则说明要找的元素在前半部分，然后继续折半查找前半部分。直到前后指针指向同一个元素，判断是否是要查找的元素。

#include<iostream>
#include "ordlist.cpp"

using namespace std;

Error_code recursive_binary_2(const Ordered_list &the_list, const Key &target,int bottom, int top, int &position)//传入排好序的链表，关键字，当前前指针的位置，当前后指针的位置，如果查到了将位置赋给position，
{
    Record data;
    if (bottom <= top)
    {
        int mid = (bottom + top) / 2; //找出中间坐标
        the_list.retrieve(mid, data); //返回中间坐标的值
        if (data == target)
        {
            position = mid;
            return success; //如果中间的值等于要查找的值，则成功
        }

        else if (data < target) //如果中间的值小于要查找的值，说明要查找的值在后半部分
            return recursive_binary_2(the_list, target, mid + 1, top, position); //递归，此时前指针移到中间位置的后一个位置
        else //如果中间的值大于要查找的值，说明要查找的值在前半部分
            return recursive_binary_2(the_list, target, bottom, mid - 1, position); //递归，后指针移到中间位置的前一个位置
    }
    else return not_present;
}

Error_code run_recursive_binary_2(const Ordered_list &the_list,const Key &target, int &position)
{
  return recursive_binary_2(the_list, target, 0, the_list.size() - 1, position); //给递归函数传入初始值
}

2.要找到该数第一次出现的位置，我们只能在找出一个正确位置时先将它保存起来，这样最后前后指针指向同一个元素时，如果是要查找的数据则一定是第一个。

#include<iostream>
#include "ordlist.cpp"

using namespace std;

Error_code recursive_binary_1(const Ordered_list &the_list, const Key &target,int bottom, int top, int &position)//传入排好序的链表，关键字，如果查到了将位置赋给position
{
    Record data;
    if (bottom < top) //当前指针小于后指针
    {
        int mid = (bottom + top) / 2;//找出中间坐标
        the_list.retrieve(mid, data);//返回中间坐标的值
        if (data < target)   //如果中间的值小于要查找的值，说明要查找的值在后半部分
            return recursive_binary_1(the_list, target, mid + 1, top, position);//递归，前指针移到中间位置的后一个位置
        else       //如果中间的值大于要查找的值，说明要查找的值在前半部分
            return recursive_binary_1(the_list, target, bottom, mid, position); //递归，后指针移到中间位置
    }
    else if (top < bottom)
        return not_present;   //当前指针大于后指针时，说明没有找到
    else {          //当前后指针指向同一个元素时
        position = bottom;//将这个位置赋给position
        the_list.retrieve(bottom, data);//取出这个位置的值
        if (data == target) return success;//如果这个位置的值等于要查找的值，则该位置一定是在这个表中第一次出现的位置
        else return not_present;//如果不是则说明表中没有这个数据
    }
}

Error_code run_recursive_binary_1(const Ordered_list &the_list,const Key &target, int &position)
{
        return recursive_binary_1(the_list, target, 0, the_list.size() - 1, position); //将初始值传给递归函数
}

线性表查找

线性表查找

线性表查找

查找数组中重复元素

8.二分查找[单元素||多元素]难点剖析

第6章查找

剑指 Offer 04. 二维数组中的查找专注技术的小飞

双向链表各种操作（尾插法建表、初始化、求表长、查找、删除、插入、取值）17计科班教学用

算法：查找多数元素

thinkphp实现无限分级进行最顶一级的查找

双循环链表的初始化、查找、插入、删除、定位等操作C语言数据结构（注释详细）

线性表 查找

线性表查找

线性表 查找

查找数组中重复元素

8.二分查找[单元素||多元素]难点剖析

第6章 查找

剑指 Offer 04. 二维数组中的查找 专注技术的小飞

双向链表各种操作（尾插法建表、初始化、求表长、查找、删除、插入、取值）17计科班教学用

算法：查找多数元素

thinkphp实现无限分级 进行最顶一级的查找

双循环链表的初始化、查找、插入、删除、定位等操作C语言数据结构（注释详细）

线性表查找

线性表查找

第6章查找

剑指 Offer 04. 二维数组中的查找专注技术的小飞

thinkphp实现无限分级进行最顶一级的查找