Как реализовать связанный список в C?
Таким образом, на самом деле проблема не в времени жизни потока, в котором работает ваш блок, а в том, что для этого конкретного потока не настроен и не запущен цикл запуска для получения каких-либо событий, возвращающихся из соединения.
Итак, как вы решаете это? Есть разные варианты для размышления. Я могу перечислить несколько, и я уверен, что другие перечислят больше.
1 - Здесь вы можете использовать синхронное соединение. Одним из недостатков является то, что вы не получите обратные вызовы для аутентификации, перенаправления, кэширования и т. Д. (Все обычные недостатки синхронных соединений.) Кроме того, каждое соединение, конечно, будет блокировать поток на некоторый период времени, так что если вы делаете Многие из них могут потенциально блокировать несколько потоков одновременно, что дорого.
2 - Если ваше соединение простое и вы используете iOS5, то вы можете использовать этот метод:
+ (void)sendAsynchronousRequest:(NSURLRequest *)request
queue:(NSOperationQueue*) queue
completionHandler:(void (^)(NSURLResponse*, NSData*, NSError*))
Это запустит асинхронное соединение, а затем позволит вам указать обработчик завершения (для успеха или неудачи) и a NSOperationQueue, для которого вы хотите, чтобы этот блок был запланирован.
Опять же, у вас есть недостатки в том, что вы не можете получить обратные вызовы, которые вам могут понадобиться для аутентификации, кэширования и т. Д. Но по крайней мере у вас нет зависающих потоков, заблокированных соединениями, которые находятся в полете.
3 - Другой вариант для iOS5 - установить очередь для всех обратных вызовов делегата :
- (void)setDelegateQueue:(NSOperationQueue*) queue NS_AVAILABLE(10_7, 5_0);
Если вы используете это тогда все методы делегата будут выполняться в контексте любого указанного вами NSOperationQueue. Так что это похоже на вариант № 2, ожидайте, что теперь вы получите все методы делегата для обработки аутентификации, перенаправления и т. Д.
4 - Вы можете настроить свой собственный поток, которым вы управляете специально для управления этими соединениями. И при настройке этого потока вы настраиваете runloop соответствующим образом. Это хорошо работает в iOS4 и 5 и, очевидно, дает вам все обратные вызовы делегатов, которые вы хотите обработать
5 - вы можете подумать о том, какие части вашей асинхронной обработки соединений являются ] действительно мешает вашему интерфейсу. Как правило, установление соединения или получение обратных вызовов делегатов не так уж и дорого. Дорогие (или неопределенные) затраты часто связаны с обработкой данных, которые вы собираете в конце. Вопрос, который нужно задать, заключается в том, действительно ли вы экономите время, планируя блок в какой-то очереди, чтобы просто запустить асинхронное соединение, которое немедленно разорвется и все равно выполнит свою работу в другом потоке?
Так что вы можете просто запустить соединение из основного потока и получение всех обратных вызовов делегатов в основном потоке, а затем в вашей реализации этих методов делегатов отключают любую дорогостоящую работу, которую вам нужно выполнить в какой-либо другой очереди или потоке.
Так что-то вроде этого:
- (void)connectionDidFinishLoading:(NSURLConnection *)connection {
// go ahead and receive this message on the main thread
// but then turn around and fire off a block to do the real expensive work
dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^{
// Parse the data we've been collecting
});
}
Опять же, это не является исчерпывающим. Есть много способов справиться с этим, в зависимости от ваших конкретных потребностей здесь. Но я надеюсь, что эти мысли помогут.
9 ответов
В вашем случае голова и хвост могут просто указывать на начало и конец связанного списка. В односвязном списке действительно нужна только голова. По сути, связанный список может быть создан с помощью структуры типа:
typedef struct listnode
{
//some data
struct listnode *next;
}listnodeT;
listnodeT *list;
listnodeT *current_node;
list = (listnodeT*)malloc(sizeof(listnodeT));
current_node = list;
, и до тех пор, пока список всегда указывает на начало списка, а для последнего элемента установлено значение NULL, все в порядке. и может использовать current_node для просмотра списка. Но иногда, чтобы упростить переход по списку и сохранить любые другие данные о списке, используются токены заголовка и хвоста, которые, как и вы, заключены в их собственную структуру. Тогда ваши функции добавления и инициализации будут выглядеть примерно так (без обнаружения ошибок)
// Initialize linked list
void initialize(list_t *list)
{
list->head = NULL;
list->tail = NULL;
}
void add(list_t *list, int code, char name[], int cost)
{
// set up the new node
product_data_t *node = (product_data_t*)malloc(sizeof(product_data_t));
node->code = code;
node->cost = cost;
strncpy(node->product_name, name, sizeof(node->product_name));
node->next = NULL;
if(list->head == NULL){ // if this is the first node, gotta point head to it
list->head = node;
list->tail = node; // for the first node, head and tail point to the same node
}else{
tail->next = node; // append the node
tail = node; // point the tail at the end
}
}
В этом случае, поскольку это односвязный список, хвост действительно полезен только для добавления элементов в список. Чтобы вставить элемент, вы Придется пройти по списку, начиная с головы. Там, где хвост действительно пригодится, так это в двусвязном списке, он позволяет вам перемещаться по списку, начиная с любого конца. Вы можете перемещаться по этому списку как
// return a pointer to element with product code
product_data_t* seek(list_t *list, int code){
product_data_t* iter = list->head;
while(iter != NULL)
if(iter->code == code)
return iter;
iter = iter->next;
}
return NULL; // element with code doesn't exist
}
. Часто голова и хвост представляют собой полностью сконструированные узлы, которые сами используются как сигнальные для обозначения начала и конца списка. Они не хранят данные сами (точнее, их данные представляют собой сигнальный маркер), они просто занимают место для передней и задней части. Это может упростить кодирование некоторых алгоритмов, работающих со связанными списками, за счет необходимости иметь два дополнительных элемента. В целом, связанные списки представляют собой гибкие структуры данных с несколькими способами их реализации.
О да, и Ник прав, игра со связанными списками - отличный способ научиться работать с указателями и косвенным обращением. И они также являются отличным способом попрактиковаться в рекурсии! После того, как вы освоитесь со связанным списком, попробуйте затем построить дерево и использовать рекурсию для обхода дерева.
В памяти ваши элементы связаны указателями в структуре списка
item1 -> item2
Почему бы не сделать структуру списка частью вашего элемента?
Затем вы выделяете элемент продукта, и структура списка находится внутри него.
typedef struct product_data
{
int product_code;
char product_name[PRODUCT_NAME_LEN];
int product_cost;
struct list_t list; // contains the pointers to other product data in the list
}product_data_t;
Если вы изучаете теорию указателей C, это хорошее упражнение. В противном случае кажется, что для кода, который не является универсальным (как в библиотеке), слишком много косвенного обращения.
Вместо выделения статической 128-байтовой символьной строки вы можете захотеть попрактиковаться в использовании указателя и использовать выделенную строку точной длины которые вы убираете при выходе.
С академической точки зрения структура kungfucraig s выглядит более общей, чем та, которую вы определили.
Возможно, вы хотите, чтобы структура данных вашего списка была внешней по отношению к данным, которые он хранит.
Допустим, у вас есть:
struct Whatever
{
int x_;
}
Тогда ваша структура списка будет выглядеть так:
struct Whatever_Node
{
Whatever_Node* next_
Whatever* data_
}
Ryan Оберой прокомментировал аналогично, но без примера.
Я не пишу здесь код, но вам необходимо сделать следующее:
- Создать объект списка, он останется глобальным на протяжении всей программы.
- Malloc размер of product _ data _ t.
- Для первого элемента (заголовок равен NULL) укажите заголовок на назначенный адрес.
- Чтобы добавить следующий элемент, перейдите в конец списка и затем добавьте указатель ошибочного адреса к следующему за последним элементом. (Следующим за последним элементом всегда будет NULL, так что вы переходите к концу.)
- Забудьте на время о хвосте.
Вы вызываете пространство для своей структуры list_t, просто указатели на начало и конец списка, а это не то, что вы хотите делать.
Когда вы добавляете в связанный список выделите место для фактического узла в списке, которым является ваша структура product_data_t.
Если вы ищете чтобы лучше понять основы связанных списков, взгляните на следующий документ:
Вы выделяете неправильный фрагмент памяти. Вместо того, чтобы выделять память для каждого элемента списка, вы выделяете память для заголовка и хвоста списка.
Для простоты избавьтесь от отдельной структуры для головы и хвоста. Сделайте их глобальными переменными (в той же области видимости, в которой они находятся сейчас) и измените их на listhead и listtail. Это сделает код более читаемым (вам не придется без нужды просматривать отдельную структуру), и вы не совершите ошибку, выделив неправильную структуру.
Вам не нужен указатель на хвост, если только вы не ' собираемся составить двусвязный список. Это не главный элемент, который нужно добавлять после создания связного списка, но и не обязательно.
Перейти по маршруту STL. Объявление связанных списков не должно зависеть от данных. Если вам действительно нужно написать это самостоятельно, посмотрите, как это реализовано в STL или Boost.
Вы даже не должны хранить указатель * next в своей структуре данных. Это позволяет вам использовать структуру данных вашего продукта в различном количестве структур данных - деревьях, массивах и очередях.
Надеюсь, эта информация поможет в вашем дизайнерском решении.
Изменить:
Поскольку сообщение помечено как C, у вас есть эквивалентные реализации с использованием указателей void *, которые следуют базовому принципу проектирования. Для примера посмотрите:
Документация | list.c | list.h