Покупки в супермаркете

Сканер в кассе супермаркета выдает последовательность штрих-кодов для товаров в корзине покупок, например:

1234, 4719, 3814, 1112, 1111, 1111, 1234,

которая должна быть преобразована в чек следующего вида:

C supermarket
Dry Sherry, 1lt .......... (x2)  $108.02
Fish Fingers ............. (x1)   $12.11
Orange Jelly ............. (x1)    $5.61
Giant Hula Hoops ......... (x1)   $13.31
Hula Hoops ............... (x2)    $4.22
TOTAL .......................... $143.45

Решение начнем с анализа данных. Для представления номенклатурной единицы супермаркета создадим структуру, хранящую данные о штрих-коде товара, его наименовании и цене. Цену будем хранить в центах. Определение структуры:

/// Информация о товаре магазина
struct Item {
	/// штрих-код товара
	int m_barCode;
	/// наименование товара, не более 85 символов
	char m_name[86];
	/// цена 1 единицы товара в центах
	int m_price;
};

База данных (БД) товаров в простейшем случае – массив, который хранит структуры товара и количество номенклатурных позиций супермаркета. Опишем БД товаров в виде следующей структуры:

/// База данных товаров
struct ItemDatabase {
	/// количество товаров в БД
	int m_count;
	/// массив товаров
	struct Item *m_items;
};

Для поиска товара по его штрих-коду в БД создадим функцию FindItem(), которая будет принимать два аргумента: указатель на БД товаров и штрих-код товара, информацию по которому необходимо извлечь из БД:

/// Поиск товара в БД по штрих-коду
struct Item *
FindItem (const struct ItemDatabase *database, int barCode)
{
	int i;
	assert (database != NULL);
	assert (database->m_count > 0);
	for (i = 0; i < database->m_count; ++i)
		if (database->m_items[i].m_barCode == barCode)
			return database->m_items + i;
	return database->m_items;
}

Функция линейным поиском проходит по БД товаров, и если ей удается найти товар с соответствующим штрих-кодом, возвращает указатель на структуру с информацией о нем. Если товара с таким штрих-кодом нет, функция возвращает указатель на первый товар в БД.

Для представления товара в чеке введем дополнительную структуру, которая будет хранить пару "товар – количество товара в чеке":

/// Строка счета
struct BillItem {
	/// товар
	const struct Item *m_item;
	/// количество в счете
	int m_quantity;
};

// Чек – это массив структур BillItem.
/// Счет
struct Bill {
	/// количество товаров в счете
	int m_count;
	/// массив товаров в счете
	struct BillItem *m_items;
};

Создадим две вспомогательные функции, которые будут выполнять управление памятью для структуры чека. Функция AllocBill() выделяет память под структуру чека и резервирует память под массив товаров; функция FreeBill() освобождает всю память, связанную с чеком:

/// Выделяет память под счет
struct Bill * AllocBill (int itemsCount) {
	struct Bill *result;

	result = malloc (sizeof (struct Bill));
	if (!result)
		return NULL; // выделение памяти было неуспешным
	result->m_count = 0;
	result->m_items = malloc (itemsCount * sizeof (struct BillItem));
	if (!result->m_items && itemsCount > 0) {
		free (result);
		return NULL;
	}
	return result;
}


/// Освобождает память, связанную со структурой счета
void FreeBill (struct Bill *bill) {
	assert (bill != NULL);

	if (bill->m_items)
		free (bill->m_items);
	free (bill);
}

Для печати чека на экране создадим функцию PrintBill(). На входе она принимает указатель на печатаемый чек и выводит его на экран с соответствующим форматированием:

/// Печатает счет на экран
void PrintBill (const struct Bill *bill) {
	int i;
	int totalBill = 0;
	assert (bill != NULL);
// печатаем заголовок 
	printf ("C supermarket\n\n");
	// печатаем список товаров
	for (i = 0; i < bill->m_count; ++i) {
int totalLine = bill->m_items[i].m_item->m_price*bill->m_items[i].m_quantity;
		
		totalBill += totalLine;
		printf ("%s (x%d) $%d.%d\n", 
				bill->m_items[i].m_item->m_name,
				bill->m_items[i].m_quantity,
				totalLine / 100,
				totalLine % 100
			);
	}
	// печатаем строку итого
printf ("\nTOTAL $%d.%d\n", totalBill / 100, totalBill % 100);
}

Центральной функцией является функция ProduceBill(), которая по массиву штрих-кодов создает структуру счета. Функция сначала выделяет память под результат при помощи AllocBill(), затем проходит по списку переданных штрих-кодов, ищет информацию о соответствующем товаре в БД и включает ее в счет. Если в счете уже имеется такой товар, то функция просто увеличивает его количество. Если такого товара еще нет, функция включает в счет новую строку:

/// Создает счет по списку товаров
struct Bill *
ProduceBill (const struct ItemDatabase *database, const int *barCodes, int count)
{
	int i;
	struct Bill *result;
	assert (database != NULL);
	assert (barCodes != NULL);

	result = AllocBill (count);	
	if (!result)
		return NULL;
// формируем счет
	for (i = 0; i < count; ++i) {
// выполняем поиск элемента в счете, может он был добавлен ранее
		int index = IndexOfBillItem (result, barCodes[i]);
		if (index == -1) {
			// не нашли, добаляем новый элемент
result->m_items[result->m_count].m_item = FindItem (database, barCodes[i]);
		result->m_items[result->m_count].m_quantity = 1;
			++result->m_count;
		}
		else {
			// нашли, тогда увеличиваем количество
			++result->m_items[index].m_quantity;
		}
	}
	return result;
}

Для проверки, есть ли уже товар с некоторым штрих-кодом в счете, функция ProduceBill() использует специальную вспомогательную функцию IndexOfBillItem(). Функция возвращает индекс товара в счете либо число –1, если такого товара в счете нет. Программный код вспомогательной функции IndexOfBillItem():

/// Поиск товара в счете
int IndexOfBillItem (const struct Bill *bill, int barCode)
{
	int i;
	assert (bill != NULL);
	for (i = 0; i < bill->m_count; ++i)
		if (bill->m_items[i].m_item->m_barCode == barCode)
			return i;
	return -1;
}

Базу данных товаров определим в виде константы с помощью спецификатора static:

/// База данных товаров в супермаркете
static struct Item g_databaseItems[] = {
	{ 0, "Unknown item", 0 },
	{ 4719, "Fish Fingers", 1211 },
	{ 5643, "Nappies", 1010 },
	{ 3814, "Orange Jelly", 561 },
	{ 1111, "Hula Hoops", 211 },
	

     { 1112, "Giant Hula Hoops", 1331 },
	{ 1234, "Dry Sherry, 1lt", 5401 }
};
const struct ItemDatabase g_database = {
	sizeof (g_databaseItems) / sizeof (g_databaseItems[0]), 
	g_databaseItems
};

Функция main() выполняет создание и печать счета:

int main (int argc, char* argv[])
{ 	int codes[] = { 1234, 4719, 3814, 1112, 1111, 1111, 1234 };
	struct Bill *bill = ProduceBill (&g_database, codes, sizeof (codes) / sizeof (codes[0]));
	if (!bill) {
		printf ("Error: out of memory while creating a bill");
		return -1;
	}
	PrintBill (bill);
	FreeBill (bill);
	return 0; }

Задание

1. Произведите сборку программы и проведите ее компиляцию.
2. Форматирование счета. Измените функцию PrintBill(), чтобы она печатала счет в соответствии с форматированием, приведенным в условии. Ширина строки счета – 40 символов.
3. Отбрасывание неизвестных товаров. Измените функцию ProduceBill() таким образом, чтобы товары, не найденные в БД, не включались в счет.
4. Вычисление скидки. За каждые две купленные бутылки шерри (код 1234) супермаркет дает скидку $5.00 с суммы счета. Добавьте вычисление скидки по счету. Результирующий счет должен выглядеть следующим образом:

   C supermarket
   
   Dry Sherry, 1lt .......... (x2)  $108.02
   Fish Fingers ............. (x1)   $12.11
   Orange Jelly ............. (x1)    $5.61
   Giant Hula Hoops ......... (x1)   $13.31
   Hula Hoops ............... (x2)    $4.22
   
   Discount ......................... $5.00
   
   TOTAL .......................... $138.27
5. Оптимизация поиска товара в БД. Функция FindItem() имеет сложность O(N). Измените структуру БД или тело функции FindItem() таким образом, чтобы уменьшить алгоритмическую сложность поиска.
6. Загрузка БД из файла. Разработайте функции, выполняющие загрузку списка товаров супермаркета из CSV-файла. CSV-файлом (или файлом значений, разделенных запятыми, comma-separated values) называется текстовый файл, в котором содержаться записи, состоящие из нескольких полей. При этом каждая новая строка соответствует одной записи. Поля одной записи разделяются запятыми. Если значение поля не содержит запятых, то оно записывается непосредственно. Если значение содержит запятые, то оно заключается в двойные кавычки (").Если в такой последовательности содержится двойная кавычка, она удваивается. Имеется разновидность формата, когда все строковые значения заключаются в кавычки. Пример БД товаров в CSV-файле:

   4719,"Fish Fingers",1211
   5643,"Nappies",1010
   3814,"Orange Jelly",561
   1111,"Hula Hoops",211
   1112,"Giant Hula Hoops",1331
   1234,"Dry Sherry, 1lt",5401
7. Редактирование БД. Добавьте функции для добавления/удаления товаров в БД. Функция AddItem() должна добавлять описание товара в БД. При этом если товар с таким штрих-кодом уже существует в БД, он должен замещаться новым. Функция RemoveItem() должна удалять товар по его штрих-коду из БД.
8. Анализ продаж. Разработайте функцию TotalSales(), которая принимает на вход массив чеков и печатает на экране таблицу проданных товаров по всем чекам. В таблице должна присутствовать информация о названии товара, проданном количестве, сумме (возможно, с учетом скидки по соответствующим позициям).
9. Разработайте функцию AnalyzeSales(), которая принимает на вход массив чеков и печатает на экране таблицу пар товаров, которые чаще всего покупают вместе. Пара товаров должна включаться в таблицу пар, если она присутствует более чем в одном чеке.