проверить, если элемент уже существует в связанном списке в с

Предположим, что у меня есть связанный список, который хранит книгу структура и следующий указатель узла:проверить, если элемент уже существует в связанном списке в с

struct book { 
    unsigned short size_of_content; 
    unsigned short price; 
    unsigned char *content; 
}; 

struct list { 
    struct book p; 
    struct list *next; 
};

И когда я построения связного списка, я буду проверьте, совпадает ли цена новой книги с ценой одной из книг, которые были связаны. В основном убедитесь, что нет дублирующих цен.

У меня есть идея построить ценовой массив и сравнить новую цену с существующими. Однако, поскольку C не поддерживает неограниченный размер массивов, я не думаю, что мой путь - хорошая идея. Что мне делать? Спасибо

источник

2014-02-12 Pig

Зачем нужен дополнительный массив? Почему бы просто не пройти через связанный список и не проверить цены? Кроме того: пока ни один язык программирования в юниверсе никогда не будет поддерживать * неограниченные длины * массивы (не считая лениво оцениваемых языков), C, как и многие другие языки, поддерживает массивы * переменной длины *. – Kninnug

Если вы не хотите повторять элементы, создание упорядоченного дерева (время O (logn)) вместо списка может быть хорошей идеей. В противном случае вам придется проходить весь список каждый раз, что является O (n). – imreal

Связанный список является плохим выбором в этом случае. Используйте некоторую структуру данных для хранения книг, упорядоченных с использованием времени доступа O (log (n)) '' (например, дерева двоичного поиска), это невероятно быстро, чтобы проверить существующую цену. –

Вместо создания массива или всего этого джаза вы можете просто проверить, существует ли цена в связанном списке. Другим методом может быть добавление цены, когда вы добавляете ее в связанный список в массив с динамическим размером, используя функцию malloc. http://www.cplusplus.com/reference/cstdlib/malloc/

Но это кажется неэффективным, потому что вам придется проверять массив каждый раз, даже когда он растет до n размера.

Я думаю, что это был бы лучший способ сделать это.

Вы даже можете использовать лучшую структуру данных, которая основана на связанном списке и называется списком пропусков.

Читайте здесь, в списках пропуска http://en.wikipedia.org/wiki/Skip_list Это действительно действительно круто. Возможно, стоит потратить время, чтобы попытаться реализовать этот путь.

EDIT: Как прокомментировали другие, двоичное дерево поиска будет лучшей структурой данных для этой проблемы.

источник

2014-02-12 23:20:25 diaz994

Как вы можете найти связанный список, используя бинарный поиск? –

Правда, почему-то я предположил, что это было приказано. – diaz994

Даже если он заказан, вы не можете выполнять бинарный поиск в связанном списке - вы не можете легко получить доступ к случайным элементам. Двоичный поиск работает только в массивах; если это недостаточно гибко, вместо этого следует использовать древовидную структуру. Чистые связанные списки, даже если они упорядочены, не доступны для поиска в 'O (log (n))' время, период. –

Если ваша цена является целым числом, это будет легко: выделить несколько байтов, инициализировать их до 0. Прежде чем добавить новую книгу с ценой m, проверьте m-й бит в этих байтах, если это 1, то у вас уже была цена; если нет, добавьте эту книгу и установите для m-го бита значение 1. В этом случае вам не нужно снова и снова просматривать связанный список, чтобы найти цену, а также стоимость хранения ограничена.

источник

2014-02-13 00:05:32 NonStatic

Должен ли я создать указатель * char? Кроме того, что, если в файле, который я читаю, есть больше, чем «некоторые байты»? – Pig

@LesbianSquirtle, подписанный короткий от 0 до 255, поэтому вам нужно всего 256/8 = 32 байта. Это фиксированная длина памяти, поэтому вы можете использовать массив, отличный от связанного списка. – NonStatic

Вы говорите, что значение переменных с типом «unsigned short» может быть не более 255? – Pig

проверить, если элемент уже существует в связанном списке в с

ответ

Смежные вопросы