Замена звеньев друг с другом в двух-направленом связаном списке на С++ привет. Допустим есть двух напрвленные связанный список A->B->C->D->...->Z и нужно менять звенья местами для сортировки покажите ваши варианты замены звеньев друг другом уже несколько часов долблюсь например чтобы могло менять местами A и B или С и Z Тоесть любые звенья
самое простое Code: typedef struct _node *nodep; typedef void * itemp; struct _node { itemp data; nodep next; nodep prev; }; имеем список A->B->C->D->...->Z тогда просто обмениваем содержимое указателей data Code: void swap_node(nodep link1, nodep link2) { itemp data; return_if_fail(link1); return_if_fail(link2); data = link1->data; link1->data = link2->data; link2->data = data; }
спасибо но замена данных структуры местами не самое лучшее.... данные нужно не трогать а лишь менять указатели Это так сказать увеличит скорость обработки да и данные у меня могут отличаться по структуре там у меня данные имеют в себе указатель на массив указателей, например : struct Box { struct Box *next; struct Box *prev; char *Quest; //Тут храниться вопрос char *Answ[100]; //Тут храняться ответы int count; //Тут храниться колл. ответов }; ))))))))))) В общем нужно менять указатели не трогая сами данные я уже начал писать замену указателей как допишу и протестирую выложу тут
скачайте исходники GLIB там два файла glist.c и gslist.c реализуют одно и двух напрвленные списки а вообще Code: struct Box { struct Box *next; struct Box *prev; char *Quest; //Тут храниться вопрос char *Answ[100]; //Тут храняться ответы int count; //Тут храниться колл. ответов }; это плохо в структуре лучше храните один указатель на данные а при таком раскладе у вас код обработки списка будет зависеть от типа данных в списке лучше сделать универсальный вот например структура нормальная Code: typedef struct _GList GList; struct _GList { gpointer data; GList *next; GList *prev; }; это кстати код из glib'овского списка
Вроде сделал но не тестировал на все 100 % скорее на 80 % протестил тоесть полагаться на 100 низя сортировку связаного списка делаб пузырьковым методом Code: void __fastcall SvSp::SortLenth(void) { struct Box *ptr_n, *ptr_p; current = Box_first; bool Flag =true; while(Flag) { Flag = false; for(current = Box_first; current->next; current = current->next) { if(strlen(current->Quest) < strlen(current->next->Quest)) { //Replace(current, current->next, Box, next, prev); tmp = current->next; Replace(current, tmp, Box, next, prev); current = current->prev; Flag = true; } } } } А сама функция замены организован как макрос Code: //Заменить местами link_1, link_2, //при услови что движение замены идет слева на право //Например при сортировке #define Replace(link_1, link_2, name, next, prev) \ do { \ if( (link_1)->next == tmp ) \ { \ if ( (link_1)->prev ) \ { \ (link_1)->prev->next = (link_2); \ (link_2)->prev = (link_1)->prev; \ } \ else \ { \ (link_2)->prev = NULL; \ name##_first = (link_2); \ } \ if( (link_2)->next ) \ { \ (link_2)->next->prev = (link_1); \ (link_1)->next = (link_2)->next; \ } \ else \ { \ (link_1)->next = NULL; \ name##_last = (link_1); \ } \ (link_1)->prev = (link_2); \ (link_2)->next = (link_1); \ } \ else \ { \ (link_1)->next->prev = (link_2); \ (link_2)->prev->next = (link_1); \ if( (link_1)->prev ) \ { \ (link_1)->prev->next = (link_2); \ ptr_p = (link_2)->prev; \ (link_2)->prev = (link_1)->prev; \ } \ else \ { \ ptr_p = (link_2)->prev; \ (link_2)->prev = NULL; \ Box_first = (link_2); \ } \ if( (link_2)->next ) \ { \ (link_2)->next->prev = (link_1); \ ptr_n = (link_1)->next; \ (link_1)->next = (link_2)->next; \ } \ else \ { \ ptr_n = (link_1)->next; \ (link_1)->next = NULL; \ Box_last = (link_1); \ } \ (link_1)->prev = ptr_p; \ (link_2)->next = ptr_n; \ } \ } while(0)
Ra$cal ладно макрос от которого есть профит например реализация интрузивных списков в ядре линукса там всякие foreach за счет использования макросов тут понятно почему макрос для каждого entry внутри другой структуры свое смещение вычисляемое в момент компиляции тут они упрятаны в макросы а в макросе ТС код обработки списка одинаковый для разных типов можно спокойно в простую функцию вставить или если хочется такой же эффективности в inline функцию вот ниже пример где без макроса никак из за структуры самого списка Code: /** 398 * list_for_each_entry - iterate over list of given type 399 * @pos: the type * to use as a loop cursor. 400 * @head: the head for your list. 401 * @member: the name of the list_struct within the struct. 402 */ 403#define list_for_each_entry(pos, head, member) \ 404 for (pos = list_entry((head)->next, typeof(*pos), member); \ 405 prefetch(pos->member.next), &pos->member != (head); \ 406 pos = list_entry(pos->member.next, typeof(*pos), member)) 407 408/** 409 * list_for_each_entry_reverse - iterate backwards over list of given type. 410 * @pos: the type * to use as a loop cursor. 411 * @head: the head for your list. 412 * @member: the name of the list_struct within the struct. 413 */ 414#define list_for_each_entry_reverse(pos, head, member) \ 415 for (pos = list_entry((head)->prev, typeof(*pos), member); \ 416 prefetch(pos->member.prev), &pos->member != (head); \ 417 pos = list_entry(pos->member.prev, typeof(*pos), member)) 418 419/** 420 * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue 421 * @pos: the type * to use as a start point 422 * @head: the head of the list вот пример где без макросов не обойтись сколько бы не говорили что они плохи попробуйте реализовать list_for_each_entry_reverse или list_for_each_entry без макроса
std::foreach с boost::bind. Ну правда в том же бусте есть BOOST_FOREACH, но учитывая лямбды нового стандарта все будет очень просто и с обычным std::foreach без boost::bind. Ну и к слову - про макросы я конкретно в этом примере сказал, что они неуместны
