Не могу добавить элемент в начало списка

[tomsoier]

Вот код

Используется синтаксис C++

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define STR_BUF_LEN 80
int k, g, j;
 
//g=0;
// Определяем типы ///////////////////////////////////////////////
enum BOOL
  {
    FALSE,
  TRUE
  };                         // Перечисление для булевых значений
 
typedef char * T;            // Тип данных по варианту
 
typedef struct Node * PNode; // Указатель на узел
 
typedef struct Node
  {                          // Структура узла
    PNode prev;              // Предыдущий
    PNode next;              // Следующий
    T data;                  // Собственно данные (нагрузка)
  } Node;
 
typedef struct
  {                           // Итератор
    PNode node;               // Узел итератора
  } Iterator;
 
typedef Iterator * PIterator; // Указатель на итератор
 
typedef struct
  {                           // Список
    PNode head;               // Барьерный узел (БУ)
    PIterator ci;             // Итератор списка определяет тек.узел данного списка
    int size;                 // Текущая длина списка
  } List;
 
typedef List * PList;         // Указатель на список
 
// Прототипы функций ////////////////////////////////////////////////
PList Create ( );                          // Создать список
void Destroy ( PList l );                  // Разрушить список
void Insert ( PList l, const T data );     // Вставить узел в список
void Update ( PIterator i, const T data ); // Изменить данные узла по итератору
enum BOOL Delete ( PList l, PIterator i ); // Удалить элемент из списка
PIterator First ( PList l, PIterator i );  // Первый элемент списка
PIterator Prev ( PList l, PIterator i );   // Следующий элемент
PIterator Next ( PList l, PIterator i );   // Следующий элемент
T Fetch ( PIterator i );                   // Извлечь данные из итератора
void Display ( PList l );                  // Отобразить список
enum BOOL Exec ( PList l );                // Задание по варинту
 
PList list;
 
////////////////////////////////
PList Create ( ) // Создать список
  ////////////////////////////////
  {
    PList l = (PList)malloc(sizeof(List));       // Выделить память под список
    l->head = (PNode)malloc(sizeof(Node));       // Выделить память под барьерный эл-т (БЭ)
    l->head->prev = l->head;                     // Инициализируем БЭ ссылка назад на БЭ
    l->head->next = l->head;                     // ссылка вперёд на БЭ стало  БЭ<-{БЭ}->БЭ
    l->head->data = 0;                           // Пусть в данных БЭ записано 'T' (Terminator) ;)
    l->ci = (PIterator)malloc(sizeof(Iterator)); // Место под итератор списка (тек.элемент списка)
    l->ci->node = l->head;                       // Пусть итератор указывает сам на себя
    l->size = 0;                                 // Обнулить длину списка
    return l;                                    // Возвратим указатель на созданный список
  }
 
/////////////////////////////////////////
void Destroy ( PList l ) // Разрушить список
  /////////////////////////////////////////
  {
    // Удалить все созданные элементы
    if ( First(l, l->ci) )
      {                            // Если встали на первый узел (если он есть)
        Display(l);
 
        while ( Delete(l, l->ci) ) // Удаляем узлы пока удаляются
            Display(l);
      }
 
    // Освободить память данных списка и собственно списка
    free(l->head);
    free(l->ci);
    free(l);
  }
 
///////////////////////////////////////
void Insert ( PList l, const T data ) // Вставить узел в список
  ///////////////////////////////////////
  {
    PNode n = (PNode)malloc(sizeof(Node)); // Выделим память под структуру узла
 
    PNode cnode = l->ci->node;             // Тек.узел
    n->data = data;                        // Сохраним данные
    n->prev = cnode;                       // Ссылка на пред.узел
    n->next = cnode->next;                 // Ссылка на след.узел
    ((PNode)cnode->next)->prev = n;        // Ссылка со след.узла на новый узел
    cnode->next = n;                       // Ссылка с тек.узла на новый
    l->ci->node = n;                       // Делаем новый узел текущим
    l->size++;
    j = l->size;                           // Увеличим длину списка
  }
 
/////////////////////////////////////////////////////////////
void Update ( PIterator i, const T data ) // Изменить данные узла по итератору
  /////////////////////////////////////////////////////////////
  {
    free(i->node->data); // Освободить помять под старые данные
    i->node->data = data;
  }
 
//////////////////////////////////////////////////////////////
enum BOOL Delete ( PList l, PIterator i ) // Удалить узел из списка
  //////////////////////////////////////////////////////////////
  {
    if ( i->node == l->head ) return FALSE; // Удалять БУ нельзя
 
    PNode cnode = i->node;                  // Тек.узел
    PNode pnode = cnode->prev;              // Пред.узел
    PNode nnode = cnode->next;              // След.узел
 
    // Разберёмся с взаимными ссылками оставшихся узлов
    pnode->next = nnode; // (=P=C=N=) P.n->C.n | P.n->N
    nnode->prev = pnode; // P<-N.p
 
    // Назначение нового текущего узла
    if ( cnode == l->ci->node )
      {                               // Удаляем текущий узел списка
        if ( cnode->next == l->head ) // Если следующий узел барьерный
        l->ci->node = cnode->prev;
 
        else l->ci->node = cnode->next;
      }
 
    free(cnode->data); // Освободить память под данные
    free(cnode);       // Освобождение памяти
    l->size--;         // Длину списка уменьшим
 
    return TRUE;
  }
 
///////////////////////////////////////////
PIterator First ( PList l, PIterator i ) // Встать на первый узел списка
  ///////////////////////////////////////////
  {
    i->node = l->head->next;  // Встаём
 
    if ( i->node == l->head ) // Если это БУ
    return i;
 
    return i;                 // Возврат ссылки на итератор с первый узлом
  }
 
////////////////////////////////////////////
PIterator Prev ( PList l, PIterator i ) // Переход на пред.узел
  ////////////////////////////////////////////
  {
    if ( i->node->prev == l->head ) // Если БУ
    return 0;
    i->node = i->node->prev;
    return i; // Ссылка на итератор с пред.узлом
  }
 
////////////////////////////////////////////
PIterator Next ( PList l, PIterator i ) // Переход на cлед.узел
  ////////////////////////////////////////////
  {
    if ( i->node->next == l->head ) // Если БУ
    return 0;
    i->node = i->node->next;
    return i; // Ссылка на итератор со след.узлом
  }
 
///////////////////////////////////////////////////
T Fetch ( PIterator i ) // Извлечь данные из итератора
  ///////////////////////////////////////////////////
  {
    return i->node->data;
  }
 
//////////////////////////////////////////
void Display ( PList l ) // Отобразить список
  //////////////////////////////////////////
  {
    printf(">>> List[%d]: ", l->size); // Вывод длины списка
    Iterator i;
 
    if ( First(l, &i) )
      { // Встаём на начало и если встали то
        do
          {
            if ( i.node == l->ci->node )      // Вывод тек.узла
            printf("\n> %s <", Fetch(&i));
 
            else printf("\n  %s", Fetch(&i)); // Вывод очередного (нетекущего) узла
          } while ( Next(l, &i) );            // Переход на след.узел по списку пока переходится
      }
    puts("");
  }
 
 
///////////////////////////////////////////
int main ( int argc, char * * argv )
  //////////////////////////////////////////
  {
    printf("*** KP8 Start ***\n");
 
    char action = -1;               // Для кода операции
    T buf2;
    T gogi;                         // Временный указатель под данные узла
    T buf = (T)malloc(STR_BUF_LEN); // Буфер для консольного ввода строки
 
    // Определяем и создаём список для работы, экземпляр данных (уже не тип).
    list = Create( ); // Создали список (Реальное выделение памяти)
 
    while ( action != 0 )
      {
        printf("1-Prev 2-Next 3-Insert 4-Update 5-Delete 6-Display 7-Exec 0-Exit :");
 
        scanf("%d", &action);
 
        switch ( action )
          {
            case 0:
                printf("EXIT\n");
                break;
 
            case 1:
                Prev(list, list->ci);
                Display(list);
                break; // Left
 
            case 2:
                Next(list, list->ci);
                Display(list);
                break; // Right
 
            case 3:    // Insert
                printf("Enter data: ");
                scanf("\n%s", buf);
                gogi = buf;
                buf2 = (T)malloc(strlen(buf) + 1);
                strcpy(buf2, buf);
                Insert(list, buf2);
                Display(list);
                break;
 
            case 4: // Update
                printf("Update data[%s]: ", Fetch(list->ci));
                scanf("\n%s", buf);
                buf2 = (T)malloc(strlen(buf) + 1);
                strcpy(buf2, buf);
                Update(list->ci, buf2);
                Display(list);
                break;
 
            case 5:
                Delete(list, list->ci);
                Display(list);
                break; // Delete
 
            case 6:    /* Display */
                Display(list);
                break;
 
            case 7:
                for ( g = 0; g < 20; g++ )
                    Prev(list, list->ci);
                //Display(list);
                printf("\n");
                //printf("\n> %s <", gogi);
 
                printf("Input k\n");
                scanf("%d", &k);
                for ( g = 0; g < k; g++ )
                    Insert(list, gogi);
                Display(list);
                break;
 
            default:
                printf("ERROR: Nedopustimuy kod (%d)\n", action);
          }
      //   Display(list);
      }
 
    Destroy(list); // Разрушим список (освобождение памяти)
    free(buf);     // Освободим буфер под ввод данных
 
    printf("*** KP8 Finish ***\n");
  }
 

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

[Circiter]

2tomsoier

Цитата:

получается только после первого элемента

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

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

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

[tomsoier]

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

[venco]

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