美文网首页
C++编写算法(五)——查找问题之符号表与二分查找

C++编写算法(五)——查找问题之符号表与二分查找

作者: 俊仔系滑翔机 | 来源:发表于2019-01-18 21:34 被阅读0次

    一、符号表

    定义：符号表是一种存储键值对的数据结构，支持两种操作：插入(put)，即将一组新的兼职对存入表中；查找(get)，即根据给定的键得到相应的值。

    创建符号表

    无序符号表

    符号表即是键值对的存储结构，结合最近刚学习的类的定义，将符号表写成类的形式，对用户隐藏了键值对的数据，留给用户一下接口调用键值对。
    首先是创建一个无序表，无序表的创建比较简单。输入什么键值对便存储什么键值对。

    // JunzHeader.h
#ifndef JunzHeader_H_
#define JunzHeader_H_
struct DATA
{
    char key;
    int value;
};

typedef DATA DataType;

class SLType
{
private:
    enum { MAX = 100 }; // define the max length of table
    DataType data[MAX]; 
    int TbLength;       // length at present
public:
    SLType();                               // create an empty table
    int CalculateLength(); // calculate the length of Table
    bool insertNode();           // insert a node
    bool deleteNode(DataType kv); // delete a node
    int searchNode(DataType kv);  // search a node
    void show() const;        // display table
    
};
#endif // !JunzHeader_H_

    //JunzHeader.cpp
#include<iostream>
#include"JunzHeader.h"

// create an empty table
SLType::SLType()
{
    for (int i = 0; i < MAX; i++)
        data[i] = { '0', 0 };
    TbLength = 0;
}

int SLType::CalculateLength()
{
    return TbLength;
}

bool SLType::insertNode()
{
    using std::cout;
    using std::cin;
    if (TbLength >= MAX - 1)
        return false;
    else
    {
        cout << "Please input the key: ";
        cin >> data[TbLength].key;
        cout << "Please input the value: ";
        cin >> data[TbLength].value;
        TbLength = TbLength + 1;
        return true;
    }
}

int SLType::searchNode(DataType kv)
{
    int temp = -2;
    if (TbLength == 0)
    {
        return -1;
    }
    else
    {
        for (int i = 0; i < TbLength; i++)
        {
            if (kv.key == data[i].key)
                temp = i;
            else
                continue;
        }
        return temp;
    }
}


bool SLType::deleteNode(DataType kv)
{
    if (TbLength == 0)
        return false;
    else
    {
        int temp = searchNode(kv);
        if (temp == -2)
            return false;
        else
        {
            for (int j = temp + 1; j < TbLength; j++)
            {
                data[j - 1].key = data[j].key;
                data[j - 1].value = data[j].value;
            }
            TbLength = TbLength - 1;
            return true;
        }
    }
}

void SLType::show() const
{
    using std::cout;
    using std::endl;
    for (int i = 0; i < TbLength; i++)
    {
        cout << data[i].key << " " << data[i].value << endl;
    }
}

    //Main.cpp
#include <iostream>
#include "JunzHeader.h"
using namespace std;
const int NUM = 5;
int main()
{
    SLType ST;                     // create an empty table
    bool flag;
    for (int i = 0; i < NUM; i++)
    {
        flag = ST.insertNode();
        if (flag == false)
        {
            cout << "Input Error in " << i + 1 << "step!" << endl;
            break;
        }
    }
    cout << "A:10 is in " << ST.searchNode({ 'A',10 }) + 1 << endl;
    ST.deleteNode({ 'A',10 });
    cout << "A:10 is delete!" << endl;
    ST.show();
        
    system("pause");
    return 0;
}
    有序符号表

    上面这种符号表仅实现了<Key,Value>对的存储。经过咨询做服务器的同学，这种存储有时候需要使有序的，有序可以是键的有序，也可以是值的有序。但是<Key,Value>中强调的是通过Key寻求对应的Value值，因此，采用键有序是比较合理的。顺序符号表的好处是易查找。但是它需要在插入和删除表元素中付出较无序表更加高昂的代价。

    //JunzHeader.h
#ifndef JunzHeader_H_
#define JunzHeader_H_
struct DATA
{
    char key;
    int value;
};

typedef DATA DataType;

class SLType
{
private:
    enum { MAX = 100 }; // define the max length of table
    DataType data[MAX]; 
    int TbLength;       // length at present
public:
    SLType();                               // create an empty table
    int CalculateLength(); // calculate the length of Table
    bool insertNode();           // insert a node
    bool deleteNode(DataType kv); // delete a node
    int searchNode(DataType kv);  // search a node
    void show() const;        // display table
    
};
#endif // !JunzHeader_H_

    //JunzFuncDef.cpp
#include<iostream>
#include"JunzHeader.h"

// create an empty table
SLType::SLType()
{
    for (int i = 0; i < MAX; i++)
        data[i] = { '0', 0 };
    TbLength = 0;
}

int SLType::CalculateLength()
{
    return TbLength;
}

bool SLType::insertNode()
{
    using std::cout;
    using std::cin;
    int Lc = TbLength;
    DataType temp;
    if (TbLength >= MAX - 1)
        return false;
    else
    {
        cout << "Please input the key: ";
        cin >> data[TbLength].key;
        cout << "Please input the value: ";
        cin >> data[TbLength].value;

        temp = data[TbLength];

        for (int i = TbLength; i >= 0; i--)
        {
            if (data[TbLength].key < data[i].key)
                Lc = i;
            else
                continue;
        }
        if (Lc != TbLength)
        {
            for (int j = TbLength; j > Lc; j--)
            {
                data[j] = data[j - 1];
            }
            data[Lc] = temp;
        }

        TbLength = TbLength + 1;
        return true;
    }
}

int SLType::searchNode(DataType kv)
{
    int temp = -2;
    if (TbLength == 0)
    {
        return -1;
    }
    else
    {
        for (int i = 0; i < TbLength; i++)
        {
            if (kv.key == data[i].key)
                temp = i;
            else
                continue;
        }
        return temp;
    }
}


bool SLType::deleteNode(DataType kv)
{
    if (TbLength == 0)
        return false;
    else
    {
        int temp = searchNode(kv);
        if (temp == -2)
            return false;
        else
        {
            for (int j = temp + 1; j < TbLength; j++)
            {
                data[j - 1].key = data[j].key;
                data[j - 1].value = data[j].value;
            }
            TbLength = TbLength - 1;
            return true;
        }
    }
}

void SLType::show() const
{
    using std::cout;
    using std::endl;
    for (int i = 0; i < TbLength; i++)
    {
        cout << data[i].key << " " << data[i].value << endl;
    }
}

    //Main.cpp
#include <iostream>
#include <fstream>
#include <string>
#include "JunzHeader.h"

using namespace std;
const int NUM = 5;
int main()
{
    SLType ST;                     // create an empty table
    bool flag;
    for (int i = 0; i < NUM; i++)
    {
        flag = ST.insertNode();
        if (flag == false)
        {
            cout << "Input Error in " << i + 1 << "step!" << endl;
            break;
        }
    }
    ST.show();
    cout << "A:10 is in " << ST.searchNode({ 'A',10 }) + 1 << endl;
    ST.deleteNode({ 'A',10 });
    cout << "A:10 is delete!" << endl;
    ST.show();
        
    system("pause");
    return 0;
}

    符号表的应用

    符号表的其中一种应用是词频统计。上面的符号表需要根据词频统计的需求进行一定的修改。
    1、插入键值对不再需要键入进行插入，而是从txt文本中按字符串插入。
    2、寻找键值对需要通过键进行搜寻，并非通过键值对。
    3、需要加入一个修改value值的函数，对词频进行计数。
    4、需要在插入时判断key是否已经存在。

    //JunzHeader.h
#include <iostream>

#ifndef JunzHeader_H_
#define JunzHeader_H_
struct DATA
{
    std::string key;
    int value;
};

typedef DATA DataType;

class SLType
{
private:
    enum { MAX = 100 }; // define the max length of table
    DataType data[MAX]; 
    int TbLength;       // length at present
public:
    SLType();                               // create an empty table
    int CalculateLength(); // calculate the length of Table
    bool insertNode(std::string & str);           // insert a node
    int searchNode(std::string & str);  // search a node
    bool ModifyVal(std::string & str);  // modify the value in a certain key
    void show() const;        // display table
    
};
#endif // !JunzHeader_H_

    //JunzFuncDef.cpp
#include<iostream>
#include<string>
#include"JunzHeader.h"

// create an empty table
SLType::SLType()
{
    for (int i = 0; i < MAX; i++)
        data[i] = { "0000", 0 };
    TbLength = 0;
}

int SLType::CalculateLength()
{
    return TbLength;
}

bool SLType::insertNode(std::string & s)
{
    using std::cout;
    using std::cin;
    int Lc = TbLength;
    DataType temp;
    if (TbLength >= MAX - 1)
        return false;
    else
    {
        data[TbLength].key = s;
        data[TbLength].value += 1;
        temp = data[TbLength];

        for (int i = TbLength; i >= 0; i--)
        {
            if (data[TbLength].key < data[i].key)
                Lc = i;
            else
                continue;
        }
        if (Lc != TbLength)
        {
            for (int j = TbLength; j > Lc; j--)
            {
                data[j] = data[j - 1];
            }
            data[Lc] = temp;
        }

        TbLength = TbLength + 1;
        return true;
    }
}

int SLType::searchNode(std::string & str)
{
    int temp = -2;
    if (TbLength == 0)
    {
        return -1;
    }
    else
    {
        for (int i = 0; i < TbLength; i++)
        {
            if (str == data[i].key)
                temp = i;
            else
                continue;
        }
        return temp;
    }
}


void SLType::show() const
{
    using std::cout;
    using std::endl;
    for (int i = 0; i < TbLength; i++)
    {
        cout << data[i].key << " " << data[i].value << endl;
    }
}

bool SLType::ModifyVal(std::string & str)
{
    int index_tmp = searchNode(str);
    if (index_tmp < 0)
        return false;
    else
    {
        data[index_tmp].value += 1;
        return true;
    }
}

    //Main.cpp
#include <iostream>
#include <fstream>
#include <string>
#include "JunzHeader.h"

using namespace std;
const int NUM = 5;
int main()
{
    SLType ST;
    bool flag1,flag2;
    ifstream ifs("tinyTale.txt");
    string temp;
    while (ifs >> temp)
    {
        if (ST.searchNode(temp) < 0)
        {
            flag1 = ST.insertNode(temp);
            if (flag1 == false)
            {
                cout << "Input Error!!!" << endl;
                break;
            }
        }   
        else
            flag2 = ST.ModifyVal(temp);
    }
    ifs.close();
    ST.show();
    system("pause");
    return 0;
}

    所采用的tinyTale.txt文件采用了狄更斯的《双城记》中的一段话:

    it was the best of time it was the worst of times
    it was the age of wisdom it was the age of foolishness
    it was the epoch of belief it was the epoch of incredulity
    it was the season of light it was the season of darkness
    it was the spring of hope it was the winter of despair

    最后统计可以得到如下结果：


    词频统计结果.png

    不仅统计了词频，而且单词是按照字母排序的。
    当然，C++有更加高级的<Key,Value>模板可供选择，本人的这个程序只是对符号表理解后，结合类的思想，对其进行一个简单的实现。
    C++可以使用unordered_map来实现<Key,Value>模板！更高效快捷地创建符号表。

    查找算法

    无序链表的顺序查找

    无序链表的顺序查找的思路非常简单。通过遍历搜索和比较，查找到对应的键值对。
    这种方法实现比较简单，之前的代码就是通过顺序查找的方法对相应值进行搜寻的。但无序链表的顺序查找算法的复杂度比较高，不利于实际的搜索。因此，我们需要寻找一些更加便捷的算法。

    向一个空表中插入N个不同的键需要~N^2/2次比较

    有序数组的二分查找

    1、二分查找所使用的符号表的数据结构是一对平行的数组，一个数组存储键，一个数组存储值。这样方便查找数据。
    2、使用有序数组存储键值对的好处上面已经提到，虽然在插入时步骤比较麻烦，但是在查询时能够使用复杂度更低的算法。
    二分查找可以用两种方法实现：
    --根据之前的学习，通常对数组一分为二，再二分为四等等的方法让我想到了归并排序以及快速排序的处理。没错，这样的处理能采用递归思想。
    --但递归算法比较麻烦，递归算法对我们这些小白特别不友好。因此，可以采用迭代的方法进行处理。

    先来看一个递归的版本,只需要在头文件处加入声明二分查找函数的语句：

    // addition in JunzHeader.h
int Binarysearch(char k, int lo, int hi);

    然后在定义中加入该二分查找函数即可：

    // JunzFuncDef.cpp
#include<iostream>
#include<string>
#include"JunzHeader.h"

// create an empty table
SLType::SLType()
{
    for (int i = 0; i < MAX; i++)
    {
        Key[i] = '0';
        Value[i] = 0;
    }
    TbLength = 0;
}

int SLType::CalculateLength()
{
    return TbLength;
}

bool SLType::insertNode()
{
    using std::cout;
    using std::cin;
    int Lc = TbLength;
    char temp1;
    int temp2;
    if (TbLength >= MAX - 1)
        return false;
    else
    {
        cout << "Please Input the Key: ";
        cin >> Key[TbLength];
        cout << "Please Input the value: ";
        (cin >> Value[TbLength]).get();
        temp1 = Key[TbLength];
        temp2 = Value[TbLength];

        int index = Binarysearch(Key[TbLength], 0, TbLength);
        Lc = index;
        if (Lc != TbLength)
        {
            for (int j = TbLength; j > Lc; j--)
            {
                Key[j] = Key[j - 1];
                Value[j] = Value[j - 1];
            }
            Key[Lc] = temp1;
            Value[Lc] = temp2;
        }
        TbLength = TbLength + 1;
        return true;
    }
}

int SLType::Binarysearch(char k, int lo, int hi)
{ 
    if (hi <= lo)
        return lo;
    int mid = (hi - lo) / 2 + lo;
    if (k < Key[mid])
        return Binarysearch(k, lo, mid - 1);
    else if (k > Key[mid])
        return Binarysearch(k, mid + 1, hi);
    else
        return mid;
}

std::ostream & operator<<(std::ostream & os, const SLType & s)
{
    for (int i = 0; i < s.TbLength; i++)
    {
        os << s.Key[i] << " " << s.Value[i] << "\n";
    }
    return os;
}

    递归固然能帮助理解思路，但是迭代更加高效。所以二分查找也有迭代版本：

    //
int SLType::Binarysearch(char k, int lo, int hi)
{ 
    int mid = 0;
    while (true)
    {
        if (hi <= lo)
            break;
        mid = lo + (hi - lo) / 2;
        if (Key[mid] < k)
        {
            lo = mid + 1;
            continue;
        }
        else if (Key[mid] > k)
        {
            hi = mid - 1;
            continue;
        }
        else
            return mid;
    }
    return lo;
        
}

    这里在编程的时候，return lo处我一开始编写的是return mid。这样是不对的，因为mid有可能会因为lo和hi取到前半段而变小。此时，mid已经失去了元素可插入位置的信息。所以，应该采用lo作为返回值。

    这里我总结一下我理解的迭代和递归在算法中的实现。
    递归即是通过函数重复有规律的步骤。
    迭代即是通过循环改变某些变量，以重复相同的步骤。
    递归是为了减少繁杂的逻辑而想出的巧妙的解决方法。一般我们说“天才程序员使用递归”。比如汉诺塔游戏，如果采用非递归方法实现的话，太繁杂。而使用递归仅用几行代码便可实现。但是递归的性能比较差，因此不是所有的算法都用递归实现就可以。
    迭代是以逻辑来设计的解决方法。虽然说使用递归比较帅，比较牛。但是有时候迭代的性能要比递归高的多。
    所以使用迭代还是递归，需要取决实际。

    一般情况下二分查找都比顺序查找快得多，它也是众多实际应用程序的最佳选择。

    相关文章

      网友评论

          本文标题：C++编写算法(五)——查找问题之符号表与二分查找

          本文链接：https://www.haomeiwen.com/subject/yutlrqtx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|C++编写算法(五)——查找问题之符号表与二分查找|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！