快捷導航

高級數(shù)據(jù)結(jié)構(gòu)及應(yīng)用之使用bitmap進行字符串去重的方法實例

更新時間：2019年02月18日 09:00:40 作者：Inside_Zhang

今天小編就為大家分享一篇關(guān)于高級數(shù)據(jù)結(jié)構(gòu)及應(yīng)用之使用bitmap進行字符串去重的方法實例，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧

bitmap 即為由單個元素為 boolean（0/1, 0 表示未出現(xiàn)，1 表示已經(jīng)出現(xiàn)過）的數(shù)組。

如果C/C++ 沒有原生的 boolean 類型，可以用 int 或 char 來作為 bitmap 使用，如果我們要判斷某字符（char）是否出現(xiàn)過

使用 int 作為 bitmap 的底層數(shù)據(jù)結(jié)構(gòu)，bitmap 即為 int 數(shù)組，一個 int 長度為 32 個 bit 位，

c / 32 ⇒ bitmap 中的第幾個 int
c % 32 ⇒ bitmap 中的某 int 中的第幾個 bit 位；

使用 char 作為 bitmap 的底層數(shù)據(jù)結(jié)構(gòu)，bitmap 即為 char 數(shù)組，一個 char 長度為 8 個 bit 位；

c / 8 ⇒ bitmap 中的第幾個 char
c % 8 ⇒ bitmap 中某 char 中的第幾個 bit 位；

ASCII

A-Z：65-90
a-z：97-122

如果使用 char 作為 bitmap 的替代底層數(shù)據(jù)結(jié)構(gòu)，為了實現(xiàn)字符串的去重需要 char 的長度為多少呢？122/8+1 ⇒ 16。如果使用 int 作為 bitmap 的底層實現(xiàn)，則需要 int 數(shù)組的長度為 122/32 + 1 ⇒ 4

1. int 作為底層數(shù)據(jù)結(jié)構(gòu)

void dedup(const char* src, char* dst)
{
  unsigned int exists[4] = { 0 };
  int i = 0, j = 0;
  unsigned int mask;
  char c;
  while (src[i])
  {
    c = src[i];
    mask = 1 << (c % 32);
    if ((exists[c / 32] & mask) == 0)
    {
      dst[j++] = c;
      exists[c / 32] |= mask;
    }
    i++;
  }
  dst[j] = '\0';
}

2. 使用 char 作為底層數(shù)據(jù)結(jié)構(gòu)

void dedup(const char* src, char* dst)
{
  unsigned char exists[16] = { 0 };
  int i = 0, j = 0;
  unsigned int mask;
  char c;
  while (src[i])
  {
    c = src[i];
    mask = 1 << (c % 8);
    if ((exists[c / 8] & mask) == 0)
    {
      dst[j++] = c;
      exists[c / 8] |= mask;
    }
    i++;
  }
  dst[j] = '\0';
}

總結(jié)

以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對大家的學習或者工作具有一定的參考學習價值，謝謝大家對腳本之家的支持。如果你想了解更多相關(guān)內(nèi)容請查看下面相關(guān)鏈接

您可能感興趣的文章:

相關(guān)文章

JVM優(yōu)先級線程池做任務(wù)隊列的實現(xiàn)方法
這篇文章主要介紹了JVM優(yōu)先級線程池做任務(wù)隊列的實現(xiàn)方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
2020-08-08
Java實現(xiàn)局域網(wǎng)聊天小程序
這篇文章主要為大家詳細介紹了Java實現(xiàn)局域網(wǎng)聊天小程序，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2022-05-05
Java調(diào)用windows系統(tǒng)的CMD命令并啟動新程序
本文教你如何使用java程序調(diào)用windows系統(tǒng)的CMD命令啟動新程序方法,需要的朋友可以參考下
2023-05-05
MyBatis創(chuàng)建存儲過程的實例代碼_動力節(jié)點Java學院整理
本節(jié)需要用到的有2部分，第一部分是如何在Derby中創(chuàng)建存儲過程，第二部分是如何在Mybatis中調(diào)用存儲過程，具體實例代碼大家參考下本文吧
2017-09-09
Java連接數(shù)據(jù)庫JDBC技術(shù)之prepareStatement的詳細介紹
這篇文章主要介紹了Java連接數(shù)據(jù)庫JDBC技術(shù)之prepareStatement的詳細介紹，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
2020-07-07
一文了解mybatis的延遲加載
本文主要為大家詳細介紹下mybatis的延遲加載，從原理上介紹下怎么使用、有什么好處能規(guī)避什么問題。感興趣的小伙伴可以跟隨小編一起學習一下
2022-07-07
Java中mybatis的三種分頁方式
這篇文章主要介紹了Java中mybatis的三種分頁方式，文章圍繞主題展開詳細的內(nèi)容介紹，具有一定的參考價值，需要的小伙伴可以參考一下
2022-08-08
Jmeter內(nèi)置變量vars和props的使用詳解
JMeter是一個功能強大的負載測試工具,它提供了許多有用的內(nèi)置變量來支持測試過程,其中最常用的變量是 vars 和 props,本文通過代碼示例詳細給大家介紹了Jmeter內(nèi)置變量vars和props的使用,需要的朋友可以參考下
2024-08-08
詳解Spring cloud使用Ribbon進行Restful請求
這篇文章主要介紹了詳解Spring cloud使用Ribbon進行Restful請求，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
2018-04-04
java并查集算法帶你領(lǐng)略熱血江湖
這篇文章主要為大家介紹了java并查集算法，以大家熱愛的方式，帶你領(lǐng)略熱血江湖中的并查集算法，有需要的朋友可以借鑒參考下，希望能夠有所幫助
2021-11-11