我现在正在做第4部分的功课,我想弄清楚如何从一个字符串数组中只对前14个字符进行二进制搜索。我们得到了两个.csv文件。
01110011100110是一个模拟的条形码。
Inventory.csv:用逗号分隔的库存项目--条形码、产品、价格前五行。
01001010100011,Air freshener,12.43
01101000111101,Alfredo sauce,10.71
10000010100101,All spice,4.14
00011011001111,Allergy medication,20.06
00101010111011,Aluminum foil,8.92
Carts.csv: 购物车包含了购买的条形码前五行:
01000011010100,00010011010100
00110111100000
00100110100000,01011000110111,01011101000110,01011101000000,01001110000010
01110101100101,00100111110101,00101101110110,00100110000000,00100000001100,00101101011100
00101100111110,01000110110000,01010110111110,00100111111001,01011101101010,01011011010011,00010011010100,01010111101001
我正在做Part4的作业:Part4:写一个函数来读取Carts.csv文件。 每次读入一行并进行处理。 处理步骤是:a.根据逗号分隔符将每个购物车中的条形码分开;b.对于每个条形码,在产品列表中查找条形码;c.从产品字符串数据行中提取价格,并将其添加到购物车的运行总数中;d.处理行后,输出购物车的总价格;e.从步骤(a)重复,直到文件结束。
当我尝试查找时,它的返回值是-1,它是在比较整行而不是只比较一部分。如何做二进制搜索只是字符串的一部分。下面是我的代码摘录。
int binarySearch(string* list, int size, string value){
int first = 0,
last = size - 1, middle,
position = -1;
bool found = false;
while (!found && first <= last){
middle = (first + last) / 2;
if (list[middle].compare(value) == 0){
found = true;
position = middle;
}
else if (list[middle].compare(value) > 0)
last = middle - 1;
else
first = middle + 1;
}
return position;
}
void processFile(string filename, string* list, int size){
ifstream file(filename);
string line;
int count = 1;
if (file.is_open()){
while (!file.eof()){
int ctr = 0;
int start = 0;
getline(file, line);
string substring = "";
int find = line.find(COMMA);
cout << "Cart " << count << ": ";
while (find != string::npos){
substring = line.substr(start, find - start);
int position = binarySearch(list, size, substring);
cout << position << " ";
start = find + 1;
ctr++;
find = line.find(COMMA, start);
}
if (ctr > 0 || find == -1){
substring = line.substr(start, line.length() - start);
int position = binarySearch(list, size, substring);
cout << position << endl;
count++;
}
}
}
file.close();
}
试着用以下函数实现
int binarySearch( const std::string* list, int size, std::string value )
{
int position = -1;
int first = 0, last = size - 1;
while ( first <= last )
{
int middle = ( first + last ) / 2;
int result = list[middle].substr( 0, value.size() ).compare( value );
if ( result == 0 )
{
position = middle;
break;
}
else if ( result > 0 )
{
last = middle - 1;
}
else
{
first = middle + 1;
}
}
return position;
}
当然数组列表必须按照条形码的升序进行排序。