2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Не могу добавить элемент в начало списка
Сообщение01.06.2010, 19:22 


27/04/10
20
Вот код
код: [ скачать ] [ спрятать ]
Используется синтаксис C++
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. #define STR_BUF_LEN 80
  6. int k, g, j;
  7.  
  8. //g=0;
  9. // Определяем типы ///////////////////////////////////////////////
  10. enum BOOL
  11.   {
  12.     FALSE,
  13.   TRUE
  14.   };                         // Перечисление для булевых значений
  15.  
  16. typedef char * T;            // Тип данных по варианту
  17.  
  18. typedef struct Node * PNode; // Указатель на узел
  19.  
  20. typedef struct Node
  21.   {                          // Структура узла
  22.     PNode prev;              // Предыдущий
  23.     PNode next;              // Следующий
  24.     T data;                  // Собственно данные (нагрузка)
  25.   } Node;
  26.  
  27. typedef struct
  28.   {                           // Итератор
  29.     PNode node;               // Узел итератора
  30.   } Iterator;
  31.  
  32. typedef Iterator * PIterator; // Указатель на итератор
  33.  
  34. typedef struct
  35.   {                           // Список
  36.     PNode head;               // Барьерный узел (БУ)
  37.     PIterator ci;             // Итератор списка определяет тек.узел данного списка
  38.     int size;                 // Текущая длина списка
  39.   } List;
  40.  
  41. typedef List * PList;         // Указатель на список
  42.  
  43. // Прототипы функций ////////////////////////////////////////////////
  44. PList Create ( );                          // Создать список
  45. void Destroy ( PList l );                  // Разрушить список
  46. void Insert ( PList l, const T data );     // Вставить узел в список
  47. void Update ( PIterator i, const T data ); // Изменить данные узла по итератору
  48. enum BOOL Delete ( PList l, PIterator i ); // Удалить элемент из списка
  49. PIterator First ( PList l, PIterator i );  // Первый элемент списка
  50. PIterator Prev ( PList l, PIterator i );   // Следующий элемент
  51. PIterator Next ( PList l, PIterator i );   // Следующий элемент
  52. T Fetch ( PIterator i );                   // Извлечь данные из итератора
  53. void Display ( PList l );                  // Отобразить список
  54. enum BOOL Exec ( PList l );                // Задание по варинту
  55.  
  56. PList list;
  57.  
  58. ////////////////////////////////
  59. PList Create ( ) // Создать список
  60.   ////////////////////////////////
  61.   {
  62.     PList l = (PList)malloc(sizeof(List));       // Выделить память под список
  63.     l->head = (PNode)malloc(sizeof(Node));       // Выделить память под барьерный эл-т (БЭ)
  64.     l->head->prev = l->head;                     // Инициализируем БЭ ссылка назад на БЭ
  65.     l->head->next = l->head;                     // ссылка вперёд на БЭ стало  БЭ<-{БЭ}->БЭ
  66.     l->head->data = 0;                           // Пусть в данных БЭ записано 'T' (Terminator) ;)
  67.     l->ci = (PIterator)malloc(sizeof(Iterator)); // Место под итератор списка (тек.элемент списка)
  68.     l->ci->node = l->head;                       // Пусть итератор указывает сам на себя
  69.     l->size = 0;                                 // Обнулить длину списка
  70.     return l;                                    // Возвратим указатель на созданный список
  71.   }
  72.  
  73. /////////////////////////////////////////
  74. void Destroy ( PList l ) // Разрушить список
  75.   /////////////////////////////////////////
  76.   {
  77.     // Удалить все созданные элементы
  78.     if ( First(l, l->ci) )
  79.       {                            // Если встали на первый узел (если он есть)
  80.         Display(l);
  81.  
  82.         while ( Delete(l, l->ci) ) // Удаляем узлы пока удаляются
  83.             Display(l);
  84.       }
  85.  
  86.     // Освободить память данных списка и собственно списка
  87.     free(l->head);
  88.     free(l->ci);
  89.     free(l);
  90.   }
  91.  
  92. ///////////////////////////////////////
  93. void Insert ( PList l, const T data ) // Вставить узел в список
  94.   ///////////////////////////////////////
  95.   {
  96.     PNode n = (PNode)malloc(sizeof(Node)); // Выделим память под структуру узла
  97.  
  98.     PNode cnode = l->ci->node;             // Тек.узел
  99.     n->data = data;                        // Сохраним данные
  100.     n->prev = cnode;                       // Ссылка на пред.узел
  101.     n->next = cnode->next;                 // Ссылка на след.узел
  102.     ((PNode)cnode->next)->prev = n;        // Ссылка со след.узла на новый узел
  103.     cnode->next = n;                       // Ссылка с тек.узла на новый
  104.     l->ci->node = n;                       // Делаем новый узел текущим
  105.     l->size++;
  106.     j = l->size;                           // Увеличим длину списка
  107.   }
  108.  
  109. /////////////////////////////////////////////////////////////
  110. void Update ( PIterator i, const T data ) // Изменить данные узла по итератору
  111.   /////////////////////////////////////////////////////////////
  112.   {
  113.     free(i->node->data); // Освободить помять под старые данные
  114.     i->node->data = data;
  115.   }
  116.  
  117. //////////////////////////////////////////////////////////////
  118. enum BOOL Delete ( PList l, PIterator i ) // Удалить узел из списка
  119.   //////////////////////////////////////////////////////////////
  120.   {
  121.     if ( i->node == l->head ) return FALSE; // Удалять БУ нельзя
  122.  
  123.     PNode cnode = i->node;                  // Тек.узел
  124.     PNode pnode = cnode->prev;              // Пред.узел
  125.     PNode nnode = cnode->next;              // След.узел
  126.  
  127.     // Разберёмся с взаимными ссылками оставшихся узлов
  128.     pnode->next = nnode; // (=P=C=N=) P.n->C.n | P.n->N
  129.     nnode->prev = pnode; // P<-N.p
  130.  
  131.     // Назначение нового текущего узла
  132.     if ( cnode == l->ci->node )
  133.       {                               // Удаляем текущий узел списка
  134.         if ( cnode->next == l->head ) // Если следующий узел барьерный
  135.         l->ci->node = cnode->prev;
  136.  
  137.         else l->ci->node = cnode->next;
  138.       }
  139.  
  140.     free(cnode->data); // Освободить память под данные
  141.     free(cnode);       // Освобождение памяти
  142.     l->size--;         // Длину списка уменьшим
  143.  
  144.     return TRUE;
  145.   }
  146.  
  147. ///////////////////////////////////////////
  148. PIterator First ( PList l, PIterator i ) // Встать на первый узел списка
  149.   ///////////////////////////////////////////
  150.   {
  151.     i->node = l->head->next;  // Встаём
  152.  
  153.     if ( i->node == l->head ) // Если это БУ
  154.     return i;
  155.  
  156.     return i;                 // Возврат ссылки на итератор с первый узлом
  157.   }
  158.  
  159. ////////////////////////////////////////////
  160. PIterator Prev ( PList l, PIterator i ) // Переход на пред.узел
  161.   ////////////////////////////////////////////
  162.   {
  163.     if ( i->node->prev == l->head ) // Если БУ
  164.     return 0;
  165.     i->node = i->node->prev;
  166.     return i; // Ссылка на итератор с пред.узлом
  167.   }
  168.  
  169. ////////////////////////////////////////////
  170. PIterator Next ( PList l, PIterator i ) // Переход на cлед.узел
  171.   ////////////////////////////////////////////
  172.   {
  173.     if ( i->node->next == l->head ) // Если БУ
  174.     return 0;
  175.     i->node = i->node->next;
  176.     return i; // Ссылка на итератор со след.узлом
  177.   }
  178.  
  179. ///////////////////////////////////////////////////
  180. T Fetch ( PIterator i ) // Извлечь данные из итератора
  181.   ///////////////////////////////////////////////////
  182.   {
  183.     return i->node->data;
  184.   }
  185.  
  186. //////////////////////////////////////////
  187. void Display ( PList l ) // Отобразить список
  188.   //////////////////////////////////////////
  189.   {
  190.     printf(">>> List[%d]: ", l->size); // Вывод длины списка
  191.     Iterator i;
  192.  
  193.     if ( First(l, &i) )
  194.       { // Встаём на начало и если встали то
  195.         do
  196.           {
  197.             if ( i.node == l->ci->node )      // Вывод тек.узла
  198.             printf("\n> %s <", Fetch(&i));
  199.  
  200.             else printf("\n  %s", Fetch(&i)); // Вывод очередного (нетекущего) узла
  201.           } while ( Next(l, &i) );            // Переход на след.узел по списку пока переходится
  202.       }
  203.     puts("");
  204.   }
  205.  
  206.  
  207. ///////////////////////////////////////////
  208. int main ( int argc, char * * argv )
  209.   //////////////////////////////////////////
  210.   {
  211.     printf("*** KP8 Start ***\n");
  212.  
  213.     char action = -1;               // Для кода операции
  214.     T buf2;
  215.     T gogi;                         // Временный указатель под данные узла
  216.     T buf = (T)malloc(STR_BUF_LEN); // Буфер для консольного ввода строки
  217.  
  218.     // Определяем и создаём список для работы, экземпляр данных (уже не тип).
  219.     list = Create( ); // Создали список (Реальное выделение памяти)
  220.  
  221.     while ( action != 0 )
  222.       {
  223.         printf("1-Prev 2-Next 3-Insert 4-Update 5-Delete 6-Display 7-Exec 0-Exit :");
  224.  
  225.         scanf("%d", &action);
  226.  
  227.         switch ( action )
  228.           {
  229.             case 0:
  230.                 printf("EXIT\n");
  231.                 break;
  232.  
  233.             case 1:
  234.                 Prev(list, list->ci);
  235.                 Display(list);
  236.                 break; // Left
  237.  
  238.             case 2:
  239.                 Next(list, list->ci);
  240.                 Display(list);
  241.                 break; // Right
  242.  
  243.             case 3:    // Insert
  244.                 printf("Enter data: ");
  245.                 scanf("\n%s", buf);
  246.                 gogi = buf;
  247.                 buf2 = (T)malloc(strlen(buf) + 1);
  248.                 strcpy(buf2, buf);
  249.                 Insert(list, buf2);
  250.                 Display(list);
  251.                 break;
  252.  
  253.             case 4: // Update
  254.                 printf("Update data[%s]: ", Fetch(list->ci));
  255.                 scanf("\n%s", buf);
  256.                 buf2 = (T)malloc(strlen(buf) + 1);
  257.                 strcpy(buf2, buf);
  258.                 Update(list->ci, buf2);
  259.                 Display(list);
  260.                 break;
  261.  
  262.             case 5:
  263.                 Delete(list, list->ci);
  264.                 Display(list);
  265.                 break; // Delete
  266.  
  267.             case 6:    /* Display */
  268.                 Display(list);
  269.                 break;
  270.  
  271.             case 7:
  272.                 for ( g = 0; g < 20; g++ )
  273.                     Prev(list, list->ci);
  274.                 //Display(list);
  275.                 printf("\n");
  276.                 //printf("\n> %s <", gogi);
  277.  
  278.                 printf("Input k\n");
  279.                 scanf("%d", &k);
  280.                 for ( g = 0; g < k; g++ )
  281.                     Insert(list, gogi);
  282.                 Display(list);
  283.                 break;
  284.  
  285.             default:
  286.                 printf("ERROR: Nedopustimuy kod (%d)\n", action);
  287.           }
  288.       //   Display(list);
  289.       }
  290.  
  291.     Destroy(list); // Разрушим список (освобождение памяти)
  292.     free(buf);     // Освободим буфер под ввод данных
  293.  
  294.     printf("*** KP8 Finish ***\n");
  295.   }
  296.  





нужно добавить элемент k раз в начало списка, а получается только после первого элемента. Помошите разобраться!

 Профиль  
                  
 
 Re: Не могу добавить элемент в начало списка
Сообщение01.06.2010, 23:08 
Заслуженный участник


26/07/09
1559
Алматы
2tomsoier
Цитата:
получается только после первого элемента

Такова логика функции Insert... Посмотрите на строку 103, в ней вы добавляете новый элемент после текущего.

Попробуйте переписать эту функцию...

P.S.: А добавление элемента в конец списка у вас правильно работает? Просто с концом списка вы вообще очень грубо обходитесь (строка 102) и защита от дурака видна только в функции Next.

 Профиль  
                  
 
 Re: Не могу добавить элемент в начало списка
Сообщение02.06.2010, 20:08 


27/04/10
20
это всё понятно только потому что я не смог переписать функцию Insert я и написал сюда

 Профиль  
                  
 
 Re: Не могу добавить элемент в начало списка
Сообщение02.06.2010, 21:02 
Заслуженный участник


04/05/09
4586
Не разглядывал внимательно код, но возможно проблема в том, что итератор должен уметь не только указывать на элемент списка, но также и на конец - за последним элементом (ну или наоборот, перед первым элементом). Т.е. если в списке 4 элемента, то у итератора должно быть 5 состояний. У Вас так?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group