伊莉討論區

標題: C++字串比較問題 [打印本頁]

作者: jackyo04 時間: 2018-7-2 11:50 AM 標題: C++字串比較問題

本帖最後由 jackyo04 於 2018-7-5 08:51 AM 編輯

我程式會依照需求，產生N個字串，但每個字串又不能重複，字串的內容是根據條碼機而來的，目前是用了笨方法，我用"strcmp"跟每個字串做比較，譬如我有4個字串，我就讓每個字串比較3次，但程式碼都是一大串...有沒有比較聰明的方式呢？
以下是我目前用的方法..舉利來說：我有4個字串要比較->先將字串轉成char->寫兩層for迴圈如下：

for(int i = 0; i < count;i++){
for (int j = 1; j < count; j++) {
if(j > i){
a[i] = strcmp(ss[i],ss[j]);
if(a[i] == 0){
ShowMessage("第"+String(i+1)+"列條碼與第"+String(j+1)+"重複出現");
return;
}
}
}
}

複製代碼

count是一次要比較的字串數量，未來會一次比100筆，ss[]為字串轉成char的產物，a[]我換成int型態當a[]內的值為0代表比較字串完全重複，非0代表沒重複，所以只要判斷非0就通過
這是我想到的辦法..
請問各位大大有比較好的方法嗎？

作者: DuckPigPig 時間: 2018-7-2 10:20 PM

可以試試用hashmap把每個字串存下來
然后每有一個新的字串，就用hashmap來搜索一下？

作者: jackyo04 時間: 2018-7-3 08:37 AM

DuckPigPig 發表於 2018-7-2 10:20 PM
可以試試用hashmap把每個字串存下來
然后每有一個新的字串，就用hashmap來搜索一下？ ...

我目前是用兩層迴圈來判斷4個字串內有沒有重複，條碼都是印好的，只是判斷當下的4個字串有沒有重複，目前只是測試而已，之後可能擴充到100筆吧，目前執行下來速度還可以接受，還在找bug中，晚點測試100筆的狀況，hashmap好像是JAVA的東西，在我的BCB上找不太到，儲存量大的話會不會影響效率呢？因為可能一天會有幾千筆甚至幾萬筆都有可能..

作者: baepi 時間: 2018-7-4 01:37 AM

本帖最後由 baepi 於 2018-7-5 01:38 AM 編輯

撰寫方式一點都不難...重點在於你的判斷式....真的要把所有比較暫存起來?很抱歉深夜隨手亂寫的程式就是糟糕...我寫的範例錯太大了...已修正
以下程式碼
另外...BCB幾萬年沒去碰過了...自從VS2005出了以後我就對它失去興趣...因此比較字串陣列我不知道是否有list可以使用...有的話就可以自由伸縮了
(說的是以下程式碼的string str[max_count];)
若是沒有list就自己用指標做吧...雖然我不相信沒有...稀疏記得自己在BCB用過

#include<iostream>
#include<windows.h>
#include<string>
using namespace std;
const int max_count = 4;
string str[max_count];
bool *b_flag = NULL;
int b_flag_count = 0;
//隨意填值...反正是測試
void set_data()
{
for (int i = 0; i < max_count; i++)
{
str[i] = i + 48;
}
}
void create_b_flag()
{
if (b_flag != NULL)
{
delete[] b_flag;
b_flag = NULL;
}
b_flag_count = 0;
for (int i = 1; i < max_count; i++)
{
b_flag_count += i;
}
cout << "布林暫存總數 = " << b_flag_count << "\n";
if (b_flag_count > 0)
{
b_flag = new bool[b_flag_count];
}
else
{
b_flag_count = 0;
}
}
void logic()
{
for (int i = 0 , ii = 0; i < max_count; i++)
{
for (int j = i + 1; j < max_count; j++ , ii++)
{
b_flag[ii] = strcmp(str[i].c_str(), str[j].c_str()) == 0;
cout << "前比較字串index = "<<i<<"\t後比較字串index = " <<j<<"\t結果存於布林index = "<<ii<<"\n";//這個留給你檢查驗算用的
}
}
//因為不明白你後面的判斷用意...所以我擅自修改了...覺得我是錯誤的就自行修改判斷方式吧
bool c1 = false;//檢查flag...為true表示兩兩比較的字串有相等的
for (int i = 0; i < b_flag_count; i++)
{
if (b_flag[i])
{
c1 = true;
break;
}
}
if (c1)//有字串一樣的
{
//動作
}
}
void main()
{
set_data();
create_b_flag();
logic();
system("pause");
}

複製代碼

作者: jackyo04 時間: 2018-7-4 08:56 AM

baepi 發表於 2018-7-4 01:37 AM
撰寫方式一點都不難...重點在於你的判斷式....真的要把所有比較暫存起來?我隨便寫個10筆就幾萬個點了....10 ...

list這東西是有的，我來改看看，程式就是要討論才會進步

，對吧
我的作法是將每個String先轉成char，然後用兩層迴圈與一個計時器做判斷，將判斷方式寫在計時器裡，我將我的判斷方法秀出來

bool flag[10]; // 判斷字串用
int count;// 設定一次要比較幾個字串
for(int i = 0; i < count; i++){
for(int j = 1; j < count; j++){
if(i < j){
flag[i] = strcmp(s[i], s[j]);// s[]是我轉換好的char
if(flag[i] == 0){
ShowMessage("發現重複使用：" + String(i + 1) + "與" + String(j + 1));
return;
}
}
}
}

複製代碼

因為條碼這東西是流水號，太多條碼會讓使用者誤刷，或其他原因，所以才需要做判斷，雖然事情不常發生，但我習慣是想到"有可能會發生"，就把它寫進去

作者: baepi 時間: 2018-7-4 02:32 PM

不知是我表達能力太差還是我理解能力太差....聽不太明白大大想表達的意思
首先...我是看到大大在一樓的留言範例

if(i0 == i1 && i0 == i2 && i0 == i3 && i0 == i4 && i0 == i5)
// 動作

複製代碼

這段我不知用來判斷甚麼?
如果只是要判斷\字串之間是否有重複....那只需...如下

#include<iostream>
#include<windows.h>
#include<string>
using namespace std;
const int max_count = 4;
string str[max_count];
//隨意填值...反正是測試
void set_data()
{
/*for (int i = 0; i < max_count; i++)
{
str[i] = i + 48;
}*/
str[0] = "ABC";
str[1] = "ABCD";
str[2] = "BC";
str[3] = "ABCD";
}
void logic()
{
bool c1 = false;
for (int i = 0, ii = 0; i < max_count; i++)
{
for (int j = i + 1; j < max_count; j++, ii++)
{
if (strcmp(str[i].c_str(), str[j].c_str()) == 0)//代表相同
{
c1 = true;
cout << "index = " << i << " 的 " << str[i] << " 和 " << "index = " << j << " 的 " << str[j] << " 是一樣的\n";
//break;//若是抓到一樣就中斷的話....
}
//cout << "前比較字串index = " << i << "\t後比較字串index = " << j << "\t結果存於布林index = " << ii << "\n";
}
}
if (c1)//有字串是一樣的
{
//動作
}
}
void main()
{
set_data();
logic();
system("pause");
}

複製代碼

另外...被大大在一樓的範例誤導 + 我也沒注意...strcmp的回傳是int型態等於0表示兩字串相等...等於1與等於-1都是不相等....所以不能用bool型態紀錄...因為0跟-1都算false

作者: cockroachrun 時間: 2018-7-4 05:08 PM

jackyo04 發表於 2018-7-4 08:56 AM
list這東西是有的，我來改看看，程式就是要討論才會進步，對吧
我的作法是將每個String先轉成char ...

1. 不知道你的string 是那種string
std::string 嗎?
如果是跟本無法直接使用 strcmp(...) 比對
因為strcmp 要求的參數是 const char*
std::string 不是 char* 硬要使用必須轉型使用 std::string 的c_str() 來轉換
如
strcmp(a.c_str(),b.c_str())

2.
int strcmp( const char *string1, const char *string2  );
這是strcmp 的原型. 回傳的是 int
0 表示 string1 跟 string2 一樣
<0 string1 比 string2 小
>0 string1 比 string2 大

3. 你說把 String 轉成char .. 請問怎麼樣子的轉法?
然到你的string 內容都只有一個字元嗎?

最後.  你沒有提足夠的問題描述. 無法給於正確的作法.

作者: sggleeee 時間: 2018-7-5 12:04 AM

用std::vector與std::find 不知道能否達成您的要求...
底下為簡單範例...給您參考看看....

#include <iostream>
#include <vector>
#include <string>
using namespace std;
void ShowData(vector<string> Arr)
{
vector<string>::pointer data_ptr;
data_ptr = Arr.data();
for (size_t n = Arr.size(); 0 < n; --n, data_ptr++)
{
cout<<*data_ptr<<"\n";
}
}
bool isExisted(vector<string> Arr, string InputData)
{
return (find(begin(Arr), end(Arr), InputData)!=end(Arr));
}
void main()
{
vector<string> sArr;
sArr.push_back("abc");
sArr.push_back("ab");
sArr.push_back("acd");
sArr.push_back("bc");
string input="a";
if (isExisted(sArr, input))
cout<<"String "<<input<<" is already existed !\n";
else
sArr.push_back(input);
ShowData(sArr);
system("pause");
}

複製代碼

作者: snowflying 時間: 2018-7-5 12:42 AM

本帖最後由 snowflying 於 2018-7-5 03:18 AM 編輯

我有上網看了一下資料，就如樓下所說的一樣，資料量大一點計算的時間就會相對拉長

不知道 "樓下" 是哪一層樓，底下沒看到有人說這個量大很慢
如果你的資料量是算億的，那麼你需要的是分散式資料庫之類的東西

基本上 map、set 是基於樹狀的資料結構，建完的時間複雜度 O(nlogn)，詢問 O(logn)
而 unordered_map、unoredered_set 則是基於 hash，建立 O(n)，詢問 O(1)
你用兩兩比較的方式，複雜度是 O(n^2)，量稍微大一點點就非常慢了

#include <iostream>
#include <set>
#include <string>
using namespace std;
int main()
{
set<string> s;
string str[4] = {"a", "b", "c", "d"};
string test = "c";
for(int i = 0 ; i < 4 ; ++i)
s.insert(str[i]);
if(s.find(test) != s.end())
cout << "duplicate\n";
else
cout << "unique\n";
return 0;
}

複製代碼

作者: baepi 時間: 2018-7-5 01:34 AM

本帖最後由 baepi 於 2018-7-5 01:38 AM 編輯

snowflying 發表於 2018-7-5 12:42 AM
不知道 "樓下" 是哪一層樓，底下沒看到有人說這個量大很慢
如果你的資料量是算億的，那麼你需要的是分散式 ...

回復snowflying大大
strcmp我是根據自己之前的印象去說明的...或許說明有誤...但是我剛剛去測試了一下...確實測不到0，-1，1以外的回傳值
等於就是0
小於就是-1
大於就是1
大大還有甚麼辦法測出這三個值以外的結果...盼答...還是我又被VS的C++陰了?在別的C或C++會出現0，-1，1以外的回傳值??
另外補充說明一下...樓主說的樓下就是指我...因為我有一個算式寫錯了...因此創造的布林值異常的大...簡單的說...我誤導過他....而等到大大看我的內文時...已經修正程式碼了orz

作者: snowflying 時間: 2018-7-5 03:12 AM

baepi 發表於 2018-7-5 01:34 AM
回復snowflying大大
strcmp我是根據自己之前的印象去說明的...或許說明有誤...但是我剛剛去測試了一下... ...

strcmp 在 cplusplus.com 有說明喔
return value 那邊

http://www.cplusplus.com/reference/cstring/strcmp/

一般的實作是跑迴圈，直到其中一個遇到 '\0' 為止
中途計算字元的值相減，如果是 0 就計算下一個，否則回傳那個相減後算出來的值
很久沒用 VS，不過可以試試像是 strcmp("m", "A")、strcmp("$", 'g') 之類的
字元的 ascii 距離遠一點，看看是不是有其他值
那只是一種實作方式，沒有保證一定是那樣，但是目前遇到不少實作是如此
起碼不一定只有那三種值

作者: baepi 時間: 2018-7-5 09:31 AM

snowflying 發表於 2018-7-5 03:12 AM
strcmp 在 cplusplus.com 有說明喔
return value 那邊

#include<iostream>
#include<windows.h>
#include<string>
using namespace std;
const int max_count = 5;
string str[max_count];
//隨意填值...反正是測試
void set_data()
{
str[0] = (char)1;
str[1] = "ABCD";
str[2] = "~~~~~~~~~~~~~";
str[3] = "ABCD";
str[4] = (char)255;
}
void logic()
{
bool c1 = false;
for (int i = 0, ii = 0; i < max_count; i++)
{
for (int j = i + 1; j < max_count; j++, ii++)
{
int ans = strcmp(str[i].c_str(), str[j].c_str());
if (ans == 0)//代表相同
{
c1 = true;
//cout << "index = " << i << " 的 " << str[i] << " 和 " << "index = " << j << " 的 " << str[j] << " 是一樣的\n";
//break;//若是抓到一樣就中斷的話....
}
cout << "前比較字串index = " << i << "\t" << str[i] << "\t後比較字串index = " << j << "\t" << str[j] << "\t結果 = " << ans << "\n";
}
}
if (c1)//有字串是一樣的
{
//動作
}
}
void main()
{
set_data();
logic();
system("pause");
}

複製代碼

以下是執行結果
重點是index = 0 and 2 and 4

前比較字串index = 0 後比較字串index = 1 ABCD 結果 = -1
前比較字串index = 0 後比較字串index = 2 ~~~~~~~~~~~~~ 結果 = -1
前比較字串index = 0 後比較字串index = 3 ABCD 結果 = -1
前比較字串index = 0 後比較字串index = 4  結果 = -1
前比較字串index = 1 ABCD 後比較字串index = 2 ~~~~~~~~~~~~~ 結果 = -1
前比較字串index = 1 ABCD 後比較字串index = 3 ABCD 結果 = 0
前比較字串index = 1 ABCD 後比較字串index = 4  結果 = -1
前比較字串index = 2 ~~~~~~~~~~~~~ 後比較字串index = 3 ABCD 結果 = 1
前比較字串index = 2 ~~~~~~~~~~~~~ 後比較字串index = 4  結果 = -1
前比較字串index = 3 ABCD 後比較字串index = 4  結果 = -1
請按任意鍵繼續 . . .

複製代碼

依舊是只有0 1 -1 三種結果...生不出其他結果
為此...我還特地去翻閱我撰寫的其他單晶片程式...不同總類的也就只有3種...我知道不多orz...更甚至linux下的C++...執行亦是如此
當然，我知道糾結這節點很沒意思，而且msdn也是如大眾說明說的的0，>0，<0，反正判斷是否相等就用回傳值是否==0罷了...只是就結果論．．．我是真的看不到0 1 -1 以外的回傳值就是

作者: jackyo04 時間: 2018-7-5 10:00 AM

本帖最後由 jackyo04 於 2018-7-5 10:03 AM 編輯

baepi 發表於 2018-7-5 09:31 AM
以下是執行結果
重點是index = 0 and 2 and 4依舊是只有0 1 -1 三種結果...生不出其他結果
為此...我還特 ...

其實我也挺糾結的XD
我用bool來判斷，實驗很多組字串，但它回傳的結果我很意外，目前確定的是，相同為0，不同為非0，這個是可以肯定的。
我特地用int先看輸出的值，然後再改用bool做一次，過程中字串都沒改變，但bool對於非零的值是回傳true耶...
而不是baepi 所說的0跟-1都會算false..，應該是編譯器的問題吧XD

另外，snowflying提供的方法，我做了改進，目前是根據100筆紀錄做比較，比較完就清空內存的東西，因為條碼屬於流水號，所以只做"當下"比較，不會遇到之前的流水號，之前刷完的都會有做些記號，防止重新刷取

作者: snowflying 時間: 2018-7-5 10:03 AM

baepi 發表於 2018-7-5 09:31 AM
以下是執行結果
重點是index = 0 and 2 and 4依舊是只有0 1 -1 三種結果...生不出其他結果
為此...我還特 ...

我用 Dev-C++ 5.11 跑起來也是 0 -1 1 三種
而在 Ubuntu 16.04 用 g++ 編出來的，結果如下

前比較字串index = 0 後比較字串index = 1 ABCD 結果 = -64
前比較字串index = 0 後比較字串index = 2 ~~~~~~~~~~~~~ 結果 = -125
前比較字串index = 0 後比較字串index = 3 ABCD 結果 = -64
前比較字串index = 0 後比較字串index = 4 ▒ 結果 = -254
前比較字串index = 1 ABCD 後比較字串index = 2 ~~~~~~~~~~~~~ 結果 = -61
前比較字串index = 1 ABCD 後比較字串index = 3 ABCD 結果 = 0
前比較字串index = 1 ABCD 後比較字串index = 4 ▒ 結果 = -190
前比較字串index = 2 ~~~~~~~~~~~~~ 後比較字串index = 3 ABCD 結果 = 61
前比較字串index = 2 ~~~~~~~~~~~~~ 後比較字串index = 4 ▒ 結果 = -129
前比較字串index = 3 ABCD 後比較字串index = 4 ▒ 結果 = -190

複製代碼

作者: snowflying 時間: 2018-7-5 10:09 AM

jackyo04 發表於 2018-7-5 10:00 AM
其實我也挺糾結的XD
我用bool來判斷，實驗很多組字串，但它回傳的結果我很意外，目前確定的是，相同為0， ...

非零值是 true 呀

另外，snowflying提供的方法，我做了改進，目前是根據100筆紀錄做比較，比較完就清空內存的東西，因為條碼屬於流水號，所以只做"當下"比較，不會遇到之前的流水號，之前刷完的都會有做些記號，防止重新刷取

不是很懂你的意思
"清空內存的東西" 是指什麼?
"只做"當下"比較，不會遇到之前的流水號，之前刷完的都會有做些記號，防止重新刷取" 又是指什麼?

作者: jackyo04 時間: 2018-7-5 10:32 AM

snowflying 發表於 2018-7-5 10:09 AM
非零值是 true 呀

1.就是說，每次只比較100個流水號，比較完的那些序號就沒用了，所以會將set<string> s裡的資料清除
2.當下比較完100筆後，會將那100個產品做上記號防止沒有意義的刷取，主要是區隔出，哪些序號有登錄，哪些序號未登錄，因為那些序號還要對應指定的編號

作者: z1090128 時間: 2018-7-9 11:50 PM

如果每次先比較每個字串的第一個字母，不符合就往下跳一個，有符合就繼續判別下一個字母，這樣會不會比較快?

作者: jackyo04 時間: 2018-7-10 08:19 AM

本帖最後由 jackyo04 於 2018-7-10 12:57 PM 編輯

z1090128 發表於 2018-7-9 11:50 PM
如果每次先比較每個字串的第一個字母，不符合就往下跳一個，有符合就繼續判別下一個字母，這樣會不會比較快 ...

我有想過這個方法，但判斷式回隨著流水號的增減而改變，不能一勞永逸

作者: cockroachrun 時間: 2018-7-10 11:52 AM

jackyo04 發表於 2018-7-10 08:19 AM
我有想果這個方法，但判斷式回隨著流水號的增減而改變，不能一勞永逸 ...

不用傷這個腦筋.
strcmp 的比較就是用這個方法. 比對第一個字元不一樣就return 了.

作者: love88131496 時間: 2018-7-13 05:58 PM

提示: 作者被禁止或刪除內容自動屏蔽

作者: love88131496 時間: 2018-7-13 06:05 PM

提示: 作者被禁止或刪除內容自動屏蔽

作者: ash1326 時間: 2018-8-8 08:24 PM

for(int i=0;i<count;i++){
for (int j=0;j<i;j++){
if(strcmp(ss[i],ss[j]) == 0){
ShowMessage("第"+String(i+1)+"列條碼與第"+String(j+1)+"重複出現");
return;
}
}
}

作者: ash1326 時間: 2018-8-8 08:27 PM

ash1326 發表於 2018-8-8 08:24 PM
for(int i=0;i

如果只是要字串比對。你的code可以縮減成這樣就行了

演算原理：位於"最後方"的字串，會依序跟"前面"的字串進行比對

歡迎光臨伊莉討論區 (http://www64.eyny.com/)