Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Для новичков > Связаные списки

Автор: FortMax 6.4.2009, 07:59

Кто-нибудь может на пальцах обьяснить что такое связанные списки ???

Автор: zim22 6.4.2009, 08:03

http://ru.wikipedia.org/wiki/Связный_список

Автор: FortMax 6.4.2009, 08:15

zim22, это-то понятно, а вот как и для чего их применять ???

Автор: GoldFinch 6.4.2009, 08:32

FortMax, тебе их применять не надо

Автор: FortMax 6.4.2009, 08:36

Цитата(GoldFinch @  6.4.2009,  08:32 ) FortMax, тебе их применять не надо   это почему ???

Автор: Static 6.4.2009, 08:49

имеется в виду, что если б было надо - вопрос стоял бы по-другому  Например - а как сделать ОТАК? А в ответ - используй связный список

Автор: zim22 6.4.2009, 08:54

Цитата(FortMax @  6.4.2009,  08:15 ) , это-то понятно, а вот как и для чего их применять ??? это динамическая структура данных. она испольуется тогда, когда необходима. если она вам не нужна - не заморачивайтесь

Автор: FortMax 6.4.2009, 08:55

я просто пока теорию штудирую=) вот на них и наткнулся, но так муторно написано, хотелось просто узнать когда и как их используют   Добавлено через 1 минуту и 19 секунд Цитата(zim22 @  6.4.2009,  08:54 ) если она вам не нужна - не заморачивайтесь smile   ладно пока не буду

Автор: andrew_121 6.4.2009, 09:10

Цитата(FortMax @  6.4.2009,  08:55 ) ладно пока не буду Ответ убил

Автор: afanp 6.4.2009, 15:27

FortMax,  это такая фигня для хранения данных. и все данные связаны между собой одним или двумя узлами ( ну это все грубо говоря ) эх, помню долго врубался в эти указатели. если что спрашивай )

Автор: bsa 6.4.2009, 16:10

FortMax, есть несколько типов контейнеров: vector - динамический массив list - двусвязный список и др. вектор - простейший массив, размеры которого могут меняться во время выполнения программы. Все значения хранятся в непрерывном участке памяти в порядке заполнения (т.е. это аналог обычному выделению памяти через new[], только с автоматическим управлением памятью). Время доступа к каждому элементу постоянно (не зависит от размера массива и номера элемента). Добавление/вставка/удаление не с конца могут быть довольно продолжительными. Все эти операции могут вызвать инвалидацию итераторов (т.е. сделают их не валидными). лист (список) - это двусвязный список, доступ к случайному элементу которого занимает линейное время (зависит от номера элемента), вставка/удаление элементов - константна. Любая такая операция не приводит к инвалидации итераторов (кроме того, который указывал на удаляемый элемент). В простейшем виде, он делается путем добавления в структуру, описывающую элемент списка, указателей prev и next, которые указывают на предыдущий и следующий элемент списка соответственно.

Автор: Cheloveck 6.4.2009, 16:12

Напугали человека, теперь он будет связные списки всячески избегать. На самом деле если разобраться, то это абсолютно просто. Есть минимум два класса (хотя, можно обойтись и одним, но это сложнее и запутаннее), первый класс имеет указатель на объект второго класса и называется головным. Второй класс, в нашем случае (довольно упрощённом), является телом. В нём находится указатель на объект того же класса. Когда мы добавляем к списку новый объект, мы сообщаем об этом головному классу. Тот смотрит, если в его указатель уже что-то записано, то он делегирует размещение нового элемента этому объекту (иначе новый элемент заносится в этот указатель). Объект проверяет свой указатель и если он пуст, присваивает ему адрес нового элемента, если нет - передаёт дальше. Преимуществом такого подхода является манипулирование группой объектов из головного класса и наличие только одного указателя. Недостатком - время выполнения, чтобы получить доступ к определённому объекту, нужно найти его какой-либо идентификатор (конечно нужно позаботится о его создании заранее)  перебирая по порядку все объекты. Цитата FortMax, есть несколько типов контейнеров: vector - динамический массив list - двусвязный список и др. нельзя применять контейнеры не зная, что они делают... имхо

Автор: Slammer 6.4.2009, 17:54

Всем привет. Решил не создавать новую тему, потому что тоже начал учить связной список, поскольку надо выполнить задачку: Сделать односторонний связной список, в который вводим целые числа. И к ней функцию, которая выкидывает из списка те элементы, за которыми идут парные числа. Можно попросить пдправить ошибки в этом коде, чтобы хотябы компилятор не ругался?(( Спасибо! Код #include <iostream> using namespace std; struct node{        int info;        node *next; } node *p = NULL; void nodeDel(node *p){      node *tmp;      while(p && ((p->info % 2) == 0)){              tmp = p;              p = p->next;              delete tmp;      }   } int main(){          int menu;     int x;     int many;           //saraksta viedosana     cout << "How many elements you will use? ";      cin >> many;     cout << "Input list of elements seperating by enter: ";     node *p;     p = new node;          for(int i = 0; i < many; i++){           cin >> x;           p->info = x;           p = p->next;     }     //menu     cout << "Use Function && Print List (1) \n Print List (2) \n Delete List & Exit (3) \n";     cin >> menu;      //(1)     if(menu == 1){          nodeDel(node);         for(int i = 0; p != NULL; i++){                 cout << p->info << ", ";                 p = p->next;         }     }     //(2)     if(menu == 2){          for(int i = 0; p != NULL; i++){                 cout << p->info << ", ";                 p = p->next;         }     }          //(3)         delete node;   system("pause");     return 0;     }

Автор: zim22 6.4.2009, 18:06

Цитата(Slammer @  6.4.2009,  17:54 ) чтобы хотябы компилятор не ругался?(( не ругается. Код #include <iostream> using namespace std; struct node{        int info;        node *next; }; node *p = NULL; void nodeDel(node *p){      node *tmp;      while(p && ((p->info % 2) == 0)){              tmp = p;              p = p->next;              delete tmp;      }   } int main(){          int menu;     int x;     int many;           //saraksta viedosana     cout << "How many elements you will use? ";      cin >> many;     cout << "Input list of elements seperating by enter: ";     node *p;     p = new node;          for(int i = 0; i < many; i++){           cin >> x;           p->info = x;           p = p->next;     }     //menu     cout << "Use Function && Print List (1) \n Print List (2) \n Delete List & Exit (3) \n";     cin >> menu;      //(1)     if(menu == 1){          nodeDel(p);         for(int i = 0; p != NULL; i++){                 cout << p->info << ", ";                 p = p->next;         }     }     //(2)     if(menu == 2){          for(int i = 0; p != NULL; i++){                 cout << p->info << ", ";                 p = p->next;         }     }          //(3)         delete p;   system("pause");     return 0;     }

Автор: FortMax 7.4.2009, 07:09

Автор: zim22 7.4.2009, 07:42

FortMax, ?

Автор: Slammer 12.4.2009, 17:22

Спасибо zim22. Есть ещё один вопросик косательно функции.  Ф-я должна выбросить все те элементы из списка, за которыми идут парные числа. Вродебы написал логически правильно, но она не работает .. ? хелп Код #include <iostream> using namespace std; struct node{        int info;        node *next; }; node *first = NULL, *last = NULL, *p; void nodeDel(node *first){      node *tmp;      tmp = first;      while(tmp->next != NULL){           tmp = tmp->next;            if((tmp->info % 2) == 0){                 delete first;                 first = tmp;           }           else {                first = first->next;           }           } } int main(){          int menu;     int x;     int many;           cout << "How many elements you will use? ";      cin >> many;     cout << "Input list of elements seperating by enter: ";          //node *p;     //p = new node;          for(int i = 0; i < many; i++){               cin >> x;               p = new node;               p->info = x;               p->next = NULL;               if(first == NULL){                        first = last = p;               }               else{                    last->next = p;                    last = last->next;               };     }     //menu     while(menu != 3){         cout << "Use Function on List (1)\nPrint List (2)\nDelete List & Exit (3)\n";         cin >> menu;         //(1)         if(menu == 1){              nodeDel(p);         }         //(2)         if(menu == 1 || menu == 2){              cout << "List consist of: " << endl;                 for(p = first; p != NULL; p=p->next){                     cout << p->info << endl;             }         }     }     //(3)     p = first;     while (p != NULL)     {         first = first->next;         delete p;         p = first;     }; system("pause");     return 0;     }

Автор: zim22 12.4.2009, 18:52

Цитата(Slammer @  12.4.2009,  17:22 ) Ф-я должна выбросить все те элементы из списка, за которыми идут парные числа. Цитата(Slammer @  12.4.2009,  17:22 )   if((tmp->info % 2) == 0){ вы здесь проверяете число на чётность или не чётность. и в зависимости от этого уже удаляете его или нет. по крайней мере пытаетесь  Код         if(menu == 1){              nodeDel(p); // неправильно. необходимо  nodeDel(first)         } мой вам совет: используйте http://forum.vingrad.ru/index.php?showtopic=252209&view=findpost&p=1818870.

Автор: Slammer 15.4.2009, 22:02

Спасибки. Немного подравил, но всёравно где-то допустил ошибку, или в удаление или в печати. Поможете найти? В приложении показан ввод и нправильный вывод (должны быть 2 двойки) Зарание признателен. Код #include <iostream> using namespace std; struct node{        int info;        node *next; }; node *first = NULL, *last = NULL, *p; node *start; void nodeDel(node *&first){      node *tmp;      tmp = first;      while(tmp->next != NULL){           tmp = tmp->next;                       if((tmp->info % 2) == 0){                 delete first;                 first = tmp;           }           else {                first = first->next;           }           } } int main(){          int menu;     int x;     int many;           //saraksta viedosana     cout << "How many elements you will use? ";      cin >> many;     cout << "Input list of elements seperating by enter:" << endl;     for(int i = 0; i < many; i++){//aizpildam sarakstu ar elementiem               cin >> x;               p = new node;               p->info = x;               p->next = NULL;               if(first == NULL){                        first = last = p;               }               else{//izveidojam noradi uz pedejo elementu                    last->next = p;                    last = last->next;               };     }     //nodublejam     start = first;          //menu     while(menu != 3){         cout << "Use Function on List (1)\nPrint List (2)\nDelete List & Exit (3)\n";         cin >> menu;         //(1)         if(menu == 1){              nodeDel(first);         }         //(2)         if(menu == 1 || menu == 2){              cout << "List consist of: " << endl;                 for(p = first; p != NULL; p=p->next){                     cout << p->info << endl;             }         }     }     //(3)     p = start;     while (p != NULL)     {         first = first->next;         delete p;         p = first;     }; system("pause");     return 0;     }

Автор: bsa 16.4.2009, 15:01

Slammer, а отлаживать пробовал? Пройдись по шагам.

Автор: Dov 18.4.2009, 05:54

Код struct info {     int     number;     bool    is_even; }; struct node {     info    elem;     node   *next; }; bool   isEven     ( info   data ); void   inputData  ( info  *data ); void   insertItem ( info   data, node **item, node **last ); void   deleteItem ( node **item ); void   deleteEven ( node **item ); void   cleanList  ( node **item ); void   displayList( node * item ); void   displayMenu( ); int main() {     node   *first    = NULL;      node   *last     = NULL;      info    x;     char    menu;     int     many;      cout << "How many elements you will use? ";      cin  >>  many;     cout << "Input list of elements seperating by enter:\n";     for( int i = 0; i < many; i++ )     {         inputData ( &x );         insertItem( x, &first, &last );     }     do     {         displayMenu();                  cin >> menu;         switch(menu)         {         case '1':                 deleteEven ( &first );                     displayList( first );             break;         case '2':                     displayList( first );             break;         case '3':             cleanList  ( &first );             cout << "\n...Have a nice day...\n\n";                         break;         default:             cout << "\n...No such option!!\n";         }     }while( menu != '3' );     return 0; } bool isEven( info data ) {     return data.is_even; } void inputData( info *data ) {     cin >> data->number;     data->is_even = ( ( data->number ) % 2 ) == 0; } void insertItem( info data, node **item, node **last ) {     node  *tmp;          tmp       =  new node;     tmp->elem =  data;     tmp->next =  NULL;          (*item ? (*last)->next : *item) = *last = tmp; } void deleteItem( node **item ) {     node  *tmp;          tmp    =  *item;     *item  = (*item)->next;          delete tmp; } void deleteEven( node **item ) {     while( (*item)->next != NULL )     {         if(isEven((*item)->next->elem))             deleteItem( item );         else             item = &(*item)->next;     } } void cleanList( node **item ) {     while( *item != NULL )         deleteItem( item ); } void displayList( node *item ) {     cout << "\nList consist of:\n ";          if(item == NULL)         cout << "List empty..";     else         while( item != NULL )         {             cout << item->elem.number << ' ';             item = item->next;         } } void displayMenu() {     cout << "\n\n   Menu: ";     cout << "\n-----------\n";          cout << "1. Function on List\n"          << "2. Print List\n"           << "3. Delete List & Exit\n";          cout << "\nEnter your choice: "; }

Автор: yeputons 19.4.2009, 21:47

FortMax   Связные списки удобно применять для такой задачи, которая регулярно (по крайней мере, у меня) возникает: есть массив, в который хотелось бы научиться быстро добавлять/удалять элементы и перебирать все элементы.     Если реализовывать это через обычные массивы/vector, то при добавлении элемента в начало требуется сдвигать все остальные элементы на  1. Это требуется около N операций, где N - старая длина массива.   Если же решать эту задачу с двухсвязными списками, то удаление/добавление элемента из такого списка происходит за ~3 операции.   Экономия времени очевидна))) Если же не важно время выполнения (например добавляешь/удаляешь элемент один или два раза) - то используй vector - с ним гораздо удобнее и проще.

Автор: zim22 20.4.2009, 07:00

Цитата(yeputons @  19.4.2009,  21:47 )  то при добавлении элемента в начало требуется сдвигать все остальные элементы на  1 используйте deque и будет вам вселенское счастье

Автор: FortMax 23.4.2009, 03:07

спс, всем, примерное представление сформировалось

Автор: Slammer 23.4.2009, 22:24

Dov, это очень мило и я бы даже сказал красиво. Мешок картошки за вложеный труд.. но я больше половины не понял..    Код (*item ? (*last)->next : *item) = *last = tmp;     Опять прошу подправить мой код функции nodeDel. Которая должна удалять те элементы из списка, за которыми идут парные числа, я просто не могу найти ошибку, хоть и кажется что всё правильно. :-( пример список с элементами - 1(первый), 1, 2, 2(четвёртый) должен преоброзоватся в 1(первый), 2(четвёртый->во второй) пожалуйста, обьясните как можно проще. Спасибо всем! Код #include <iostream> using namespace std; struct node{        int info;        node *next; }; node      *first = NULL,      *last = NULL,      *p = NULL; void nodeDel(node *first){      p = first;      node *tmp = p;      while (tmp != NULL){            if(tmp->next != NULL){                 tmp = tmp->next;                 if((tmp->info%2) == 0 ){                     cout << "Element " << p->info << " deleted!";                  first->next=tmp;                                            delete p;                     p = tmp;                 }                 p=tmp;                 //first->next = tmp;             }                  }; } int main(){          int menu;     int x;     int many;           cout << "How many elements you will use? ";      cin >> many;     cout << "Input list of elements seperating by enter:" << endl;     for(int i = 0; i < many; i++){//aizpildam sarakstu ar elementiem               cin >> x;               p = new node;               p->info = x;               p->next = NULL;               if(first == NULL){                        first = last = p;               }               else{//izveidojam noradi uz pedejo elementu                    last->next = p;                    last = last->next;               };     }          //menu     do{                      cout << "__________MENU___________\n\n"               << "Use Function on List (1)\n"              << "Print List (2)\n"              << "Delete List & Exit (3)\n"              << "_________________________\n\n";         cin  >> menu;         cout << "_________________________\n\n";              //(1)         if(menu == 1){               nodeDel(first);         }         //(2)         if(menu == 1 || menu == 2){              cout << "List consist of: " << endl;                 for(p = first; p != NULL; p=p->next){                     cout << p->info << endl;             }         }     }while(menu != 3);     //(3)     p = first;     while (p != NULL){         first = first->next;         delete p;         p = first;     }; system("pause");     return 0;     }

Автор: bsa 23.4.2009, 23:33

Slammer, ну и чего ты не понял? Все элементарно: Код (*item ? (*last)->next : *item) = *last = tmp; можно преобразовать в: Код if (*item != 0)    (*last)->next = tmp; else    *item = tmp; *last = tmp; А по поводу кода своего, ну кто тебе  мешает воспользоваться отладчиком? Он позволяет пройтись по программе шаг за шагом наблюдая все изменения переменных.

Автор: Dov 24.4.2009, 01:23

Цитата(Slammer @  23.4.2009,  22:24 ) Опять прошу подправить мой код функции nodeDel.  Подправляю, если тебе это поможет.. Код void nodeDel( node **first ) {     node   *tmp;     while( (*first)->next != NULL )     {                      if( (( (*first)->next->info) % 2 ) == 0 )             {                 cout << "Element " << (*first)->info << " deleted!\n";                                              tmp     =  *first;                 *first  = (*first)->next;                                  delete tmp;             }             else                 first = &(*first)->next;             } } вызываешь в main так: Код     //(1)     if( menu == 1 )     {         nodeDel(&first );     }

Автор: Slammer 24.4.2009, 20:05

Dov   Отладчик.. некогда им не пользовался (оно и видно), сейчас смотрю.. Всем спасибо

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)