Односвязный линейный список

Структуры данных / Односвязный линейный список

 

Каждый узел однонаправленного (односвязного) линейного списка (ОЛС) содержит одно поле указателя на следующий узел. Поле указателя последнего узла содержит нулевое значение (указывает на NULL).
Односвязный линейный список
Узел ОЛС можно представить в виде структуры

 
 
 
 
 
struct list
{
  int field; // поле данных
  struct list *ptr; // указатель на следующий элемент
};

Основные действия, производимые над элементами ОЛС:

  • Инициализация списка
  • Добавление узла в список
  • Удаление узла из списка
  • Удаление корня списка
  • Вывод элементов списка
  • Взаимообмен двух узлов списка

 

Инициализация ОЛС

Инициализация списка предназначена для создания корневого узла списка, у которого поле указателя на следующий элемент содержит нулевое значение.
Инициализация односвязного линейного списка

1
2
3
4
5
6
7
8
9
struct list * init(int a) // а- значение первого узла
{
  struct list *lst;
  // выделение памяти под корень списка
  lst = (struct list*)malloc(sizeof(struct list));
  lst->field = a;
  lst->ptr = NULL// это последний узел списка
  return(lst);
}


 

Добавление узла в ОЛС

Функция добавления узла в список принимает два аргумента:

  • Указатель на узел, после которого происходит добавление
  • Данные для добавляемого узла.

Процедуру добавления узла можно отобразить следующей схемой:
Добавление элемента односвязного линейного списка
Добавление узла в ОЛС включает в себя следующие этапы:

  • создание добавляемого узла и заполнение его поля данных;
  • переустановка указателя узла, предшествующего добавляемому, на добавляемый узел;
  • установка указателя добавляемого узла на следующий узел (тот, на который указывал предшествующий узел).

Таким образом, функция добавления узла в ОЛС имеет вид:

1
2
3
4
5
6
7
8
9
10
struct list * addelem(list *lst, int number)
{
  struct list *temp, *p;
  temp = (struct list*)malloc(sizeof(list));
  p = lst->ptr; // сохранение указателя на следующий узел
  lst->ptr = temp; // предыдущий узел указывает на создаваемый
  temp->field = number; // сохранение поля данных добавляемого узла
  temp->ptr = p; // созданный узел указывает на следующий элемент
  return(temp);
}

Возвращаемым значением функции является адрес добавленного узла.

 

Удаление узла ОЛС

В качестве аргументов функции удаления элемента ОЛС передаются указатель на удаляемый узел, а также указатель на корень списка.
Функция возвращает указатель на узел, следующий за удаляемым.

Удаление узла может быть представлено следующей схемой:
Удаление элемента односвязного линейного списка
Удаление узла ОЛС включает в себя следующие этапы:

  • установка указателя предыдущего узла на узел, следующий за удаляемым;
  • освобождение памяти удаляемого узла.

1
2
3
4
5
6
7
8
9
10
11
12
struct list * deletelem(list *lst, list *root)
{
  struct list *temp;
  temp = root;
  while (temp->ptr != lst) // просматриваем список начиная с корня
  { // пока не найдем узел, предшествующий lst
    temp = temp->ptr;
  }
  temp->ptr = lst->ptr; // переставляем указатель
  free(lst); // освобождаем память удаляемого узла
  return(temp);
}


 

Удаление корня списка

Функция удаления корня списка в качестве аргумента получает указатель на текущий корень списка. Возвращаемым значением будет новый корень списка — тот узел, на который указывает удаляемый корень.

1
2
3
4
5
6
7
struct list * deletehead(list *root)
{
  struct list *temp;
  temp = root->ptr;
  free(root); // освобождение памяти текущего корня
  return(temp); // новый корень списка
}


 

Вывод элементов списка

В качестве аргумента в функцию вывода элементов передается указатель на корень списка.
Функция осуществляет последовательный обход всех узлов с выводом их значений.

1
2
3
4
5
6
7
8
9
void listprint(list *lst)
{
  struct list *p;
  p = lst;
  do {
    printf("%d ", p->field); // вывод значения элемента p
    p = p->ptr; // переход к следующему узлу
  } while (p != NULL);
}


 

Взаимообмен узлов ОЛС

В качестве аргументов функция взаимообмена ОЛС принимает два указателя на обмениваемые узлы, а также указатель на корень списка. Функция возвращает адрес корневого элемента списка.

Взаимообмен узлов списка осуществляется путем переустановки указателей. Для этого необходимо определить предшествующий и последующий узлы для каждого заменяемого. При этом возможны две ситуации:

  • заменяемые узлы являются соседями;
  • заменяемые узлы не являются соседями, то есть между ними имеется хотя бы один элемент.

При замене соседних узлов переустановка указателей выглядит следующим образом:
Замена соседних элементов односвязного линейного списка
При замене узлов, не являющихся соседними переустановка указателей выглядит следующим образом:
Замена элементов односвязного линейного списка
При переустановке указателей необходима также проверка, является ли какой-либо из заменяемых узлов корнем списка, поскольку в этом случае не существует узла, предшествующего корневому.

Функция взаимообмена узлов списка выглядит следующим образом:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
struct list * swap(struct list *lst1, struct list *lst2, struct list *head)
{
  // Возвращает новый корень списка
  struct list *prev1, *prev2, *next1, *next2;
  prev1 = head;
  prev2 = head;
  if (prev1 == lst1)
    prev1 = NULL;
  else
    while (prev1->ptr != lst1) // поиск узла предшествующего lst1
      prev1 = prev1->ptr;
  if (prev2 == lst2)
    prev2 = NULL;
  else
    while (prev2->ptr != lst2) // поиск узла предшествующего lst2
      prev2 = prev2->ptr;
  next1 = lst1->ptr;  // узел следующий за lst1
  next2 = lst2->ptr;  // узел следующий за lst2
  if (lst2 == next1)
  {                       // обмениваются соседние узлы
    lst2->ptr = lst1;
    lst1->ptr = next2;
    if (lst1 != head)
      prev1->ptr = lst2;
  }
  else
    if (lst1 == next2)
    {
      // обмениваются соседние узлы
      lst1->ptr = lst2;
      lst2->ptr = next1;
      if (lst2 != head)
        prev2->ptr = lst2;
    }
    else
    {
      // обмениваются отстоящие узлы
      if (lst1 != head)
        prev1->ptr = lst2;
      lst2->ptr = next1;
      if (lst2 != head)
        prev2->ptr = lst1;
      lst1->ptr = next2;
    }
  if (lst1 == head)
    return(lst2);
  if (lst2 == head)
    return(lst1);
  return(head);
}


Назад: Структуры данных

Комментариев к записи: 72

  • Здравствуйте. Вы описали работу со списками в одно-поточном случае, но современные многоядерные процессоры более эффективны для мульти-поточных приложений. А там при использовании списков без синхронизации не обойтись - все манипуляции выполняются под закрытым семафорным элементом (как правило, мьютексом). Возникает вопрос: существует ли алгоритм работы (представляют интерес только операции добавления в хвост и изъятие с головы) с односвязными списками типа "очередь" (FIFO, два описателя - "голова" и "хвост"), не использующий семафорные элементы, а только атомарные операции (например, типа "сравнить-и-обменять")? Для списков типа "стек" (LIFO, один описатель - "голова") такая реализация не вызывает затруднений и работает без проблем.

  • Александр
    Добрый день. Не понимаю список в чужом коде. Как он работает? В нем нет поля данных, только указатель на такой же узел в списке:
    1
    2
    typedef struct _P_NEXT P_NEXT;
    struct _P_NEXT { P_NEXT* p_el; };

  • Здравствуйте. Помогите пожалуйста. Не работает функция разбиения списка на четные и нечетные.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    struct list {
      int ptr; 
      list *next;
    };

    void input_list(list *&first, int n) {
      first = new list;
      cinn >> first->ptr;
      list *q = first;
      for (int i = 0; i < n - 1; i++) {
        q->next = new list;
        q = q->next;
        cin>>q->ptr;
      }
      q->next = 0;
    }
    void print_list(list *q) {
      while (q) {
        cout << q->ptr << " ";
        q = q->next;
      }
      cout << endl;
    }

    void razbienie_list(list *&first){
      list *q = first;
      list *chet = new list;
      list *nechet = new list;
      list *q1 = chet;
      list *q2 = nechet;
      list *w1 = q1;
      list *w2 = q2;
      while (p) {
        if (q->ptr % 2) {
          q2->ptr = p->ptr;
          q2->next = new list;
          w2 = q2;
          q2 = q2->next;
        }
        else {
          q1->ptr = p->ptr;
          q1->next = new list;
          q1 = q1;
          q1 = q1->next;
        };
        q = q->next;
      }
      w1->next = 0;
      w2->next = 0;
    }

    int main(){
            list *first = 0;
      int n = 5;
      input_list(first, n);
      print_list(first);
            razbienie_list(first);
            print_list(first);
            return 0;
    }

  • Добрый день! Подскажите пожалуйста как мне в main найти указатель pos чтобы удалить элемент структуры:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    #include <iostream>
    #include <string>
    using namespace std;
    const int maxSize = 100;
    //Описываем структуру Wood со следующими полями:
    //index - номер дерева в базе;
    //name - название дерева;
    //type - его тип;
    //MaximumHeight - максимальная высота;
    //lifespan - продолжительность жизни;
    struct Wood
    {
      char name[maxSize];
      char type[maxSize];
      double MaximumHeight;
      double lifespan;
      Wood* Next;
    };
    Wood* Head;
    //Функция для ввода информации об очередном дереве.
    void WoodInput(char name[maxSize], char type[maxSize], double& MaximumHeight, double& lifespan)
    {
      cout << "Name = ";
      cin.get();
      cin.get(name, sizeof(name));
      cout << "Type = ";
      cin.get();
      cin.get(type, sizeof(type));
      cout << "MaximumHeight = ";
      cin >> MaximumHeight;
      cout << "lifespan = ";
      cin >> lifespan;
      cout << endl;
    }

    //Функция для вывода массива деревьев.
    void PrintWood(Wood* Head)
    {
      Wood* j = Head; // j указывает на начало
      while (j != NULL); // Пока не конец списка
      {
        cout << "Wood: "  << j->name << ";" << j->type << ";" << j->MaximumHeight << ";" << j->lifespan << ";"
        j = j->Next; // переход к следующему элементу
      }
      cout << endl;

    }

    //Функция для поиска в базе деревьев с определенной продолжительностью жизни.
    //Выводит найденные деревья и возвращает их количество.
    //Входные параметры:
    //ar - массив деревьев;
    //n - число деревьев в массиве;
    //age - возраст для поиска;
    Wood* WoodSearch(Wood* Head, double lifespan)
    {
      Wood* p = Head; // указывает на начало
      while (p != NULL//Пока не конец списка
      {
        if (p->lifespan == lifespan) //Если элемент найден, то
          break//прерываем цикл
        p = p->Next; //Переход к следующему элемент
      }
      return p;
    }

      
    //Функция удаления дерева по значению поля
    void DeleteWood(Wood*& pbeg, Wood* pos)
    {
      //если список пуст или pos равен NULL
      if (pbeg == NULL || pos == NULL)
        return//выходим
      //Если pos указывает
      //на начало
      if (pos == pbeg)
      {   //Пусть pbeg укажет на
        //следующий элемент
        pbeg = pbeg->Next;
        //Освобождаем память,
          //на которую указывает
          //pos
        delete pos;
      }
      else
      {
        Wood* prev = pbeg;
        while (prev != NULL && prev->Next != pos)
          prev = prev->Next;
        if (prev != NULL)
        {
          prev->Next = pos->Next;
          delete pos;   
        }
      } 


    void FreeWood(Wood*& pbeg)
    {
      Wood* p;
      while (pbeg != NULL)
      {
        p = pbeg;
        pbeg = pbeg->Next;
        delete p;
      }
    }

    int main()
    {
      char name[maxSize] = {'\0'};
      char type[maxSize] = {'\0'};
      double MaximumHeight;
      double lifespan;
      
      Wood* Head = nullptr;
      int n;
      
      //Вводим число деревьев, которые будем хранить в массиве
      cout << "Number of Wood = ";
      cin >> n;
      //Вводим информацию о всех деревьях с помощью реализованной функции
      for (int i = 0; i < n; i++)
      {
        WoodInput(name, type, MaximumHeight, lifespan);
      }

      // удаление элемента
      cout << " deleted Woods = ";
      cin >> lifespan;
      DeleteWood(Head, WoodSearch(Head, lifespan)); // ЗДЕСЬ ОШИБКА
      PrintWood(Head);

      FreeWood(Head);

      system("pause");
      return 0;
    }

    • Елена Вставская
      А Head как был nullptr, так и остался... И следующая проблема возникнет, когда при выводе будут все деревья, равные последней записи. Потому что память выделяется один раз, а дальше только ссылки на нее создаваться будут.



      • Что-то вроде такого, только на си. Мне просто задали сделать вычитание из двух списков, но я сам не понимаю как это сделать.

        • Елена Вставская
          Создать 3 списка: A, B и C. Заполнить списки A и B исходными данными. Сделать вложенный цикл.
          1
          2
          3
          4
          5
          6
          7
          8
          9
          10
          11
          12
          13
          14
          15
          16
          17
          b = B;
          do {
            a=A;
            int flag = 0; // есть ли элемент списка B в списке A
            do {
              if(a->num == b->num)
                {
                  flag = 1; // такой элемент имеется
                  ... // удалить a, чтоб второй элемент с таким же значением из списка B с ним не сравнивался
                  break;
                }
              a = a->ptr;
            }while(a!=NULL);
            if(flag == 0)
              ...//Добавляем элемент в список C
            b = b->ptr;
          while(b!=NULL); 

          • Вот мой код, но первый элемент не удаляется.
            1
            2
            3
            4
            5
            6
            7
            8
            9
            10
            11
            12
            13
            14
            15
            16
            17
            18
            19
            20
            21
            22
            23
            24
            25
            26
            27
            28
            29
            30
            31
            32
            33
            34
            35
            36
            37
            38
            39
            40
            41
            42
            43
            44
            45
            46
            47
            48
            49
            50
            51
            52
            53
            54
            55
            56
            57
            58
            59
            60
            61
            62
            63
            64
            65
            66
            67
            68
            69
            70
            71
            72
            73
            74
            75
            76
            77
            78
            79
            80
            81
            82
            83
            84
            85
            86
            87
            88
            89
            90
            91
            92
            93
            94
            95
            96
            97
            98
            99
            100
            101
            102
            103
            104
            105
            106
            107
            108
            109
            110
            111
            112
            113
            114
            115
            116
            117
            118
            119
            120
            121
            122
            123
            124
            125
            126
            127
            128
            129
            130
            131
            132
            133
            134
            135
            136
            137
            138
            139
            140
            141
            142
            143
            144
            145
            146
            147
            148
            149
            150
            151
            152
            153
            154
            155
            156
            157
            158
            159
            160
            161
            162
            163
            164
            165
            166
            167
            168
            169
            170
            171
            172
            173
            174
            175
            176
            177
            178
            179
            180
            181
            182
            183
            184
            185
            186
            187
            188
            189
            190
            191
            192
            193
            194
            195
            196
            197
            198
            199
            200
            201
            202
            203
            204
            205
            206
            207
            208
            209
            210
            211
            212
            213
            214
            215
            216
            217
            218
            219
            220
            #define _CRT_SECURE_NO_WARNINGS
            #include <stdio.h>
            #include <stdlib.h>
            #include <malloc.h>
            #include <locale.h>
            struct list
            {
                int field;
                struct list* ptr;
            };
            // Инициализация списка (ОЛС)

            struct list* init(int a)
            {
                struct list* head = (struct list*)malloc(sizeof(struct list));
                head->field = a;
                head->ptr = NULL;
                return (head);
            }
            // Добавление элемента (возвращает добавленный элемент) (ОЛС)
            struct list* addelem(struct list* lst, int number)
            {

                struct list* temp, * p;
                temp = (struct list*)malloc(sizeof(struct list)); // выделение памяти под узел списка
                p = lst->ptr;        // временное сохранение указателя
                lst->ptr = temp;      // предыдущий узел указывает на создаваемый
                temp->field = number;    // сохранение поля данных добавляемого узла
                temp->ptr = p;      // созданный узел указывает на следующий элемент
                return(temp);
            }

            // Удаление корня списка (возвращает новый корень) (ОЛС)
            struct list* deletehead(struct list* root)
            {
                struct list* temp;
                temp = root->ptr;
                free(root);
                return(temp); // новый корень списка
            }

            // Удаление элемента списка (возвращает предшествующий элемент) (ОЛС)
            struct list* deletelem(struct list* lst, struct  list* root)
            {
                struct list* temp;
                temp = root;
                while (temp->ptr != lst)        // просматриваем список начиная с корня
                {        // пока не найдем узел, предшествующий lst
                    temp = temp->ptr;
                }
                temp->ptr = lst->ptr; // переставляем указатель
                free(lst);    // освобождаем память удаляемого элемента
                return(temp);
            }

            // Вывод элементов списка (ОЛС)
            void listprint(struct list* lst)
            {
                struct list* p;
                p = lst;
                do {
                    printf("%d ", p->field);  // вывод значения элемента p
                    p = p->ptr;        // переход к следующему элементу
                } while (p != NULL);
            }

            struct list* add(struct list* head, int data)
            {
                struct list* temp, * p;
                p = head->ptr;
                temp = (struct list*)malloc(sizeof(struct list));
                head->ptr = temp;
                temp->field = data;
                temp->ptr = p;
                return (temp);
            }


            void print(struct list* a)
            {
                struct list* p = a;
                while (p != NULL)
                {
                    printf(" %d", p->field);
                    p = p->ptr;
                }
            }
            void del(struct list* p, int v)
            {
                if (p == NULL)
                    return;
                struct list* t = p;
                if (t->ptr == v)
                {
                    p = t->ptr;
                    free(t);
                    return;
                }

                struct  list* t1 = t->ptr;
                while (t1)
                {
                    if (t1->field == v)
                    {
                        t->ptr = t1->ptr;
                        free(t1);
                        return;
                    }
                    t = t1;
                    t1 = t1->ptr;
                }
            }

            void sub(struct list* a, struct list* b)
            {
                struct list* p2;
                for (struct list* p2 = b; p2; p2 = p2->ptr)
                    del(a, p2->field);
                /*struct list* p2;
                p2 = b;
                while (p2)
                {
                    del(a, p2->field);
                    p2 = p2->ptr;
                }*/

                /* struct  list* p1, * p2;
                 p1 = a;
                 p2 = b;
                 while (p1)
                 {
                     while (p2)
                     {
                         if (p1->field == p2->field)
                             deletelem(p1, p1->field);
                         p2 = p2->ptr;
                     }
                     p1 = p1->ptr;
                 }*/

            }
            int main()
            {
                setlocale(LC_ALL, "Russian");

                /* struct  list* p1 = (struct list*)malloc(sizeof(struct list));
                 struct  list* p2 = (struct list*)malloc(sizeof(struct list));

                 p1 = init(5);
                 add(p1, 6);
                 add(p1, 9);
                 p2 = init(6);
                 add(p2, 7);

                 sub(p1, p2);
                 print(p1);
                 putchar('\n');
                 print(p2);*/



                struct list* head, * head1, * r;
                int a, n, e, l;
                struct  list* p1 = (struct list*)malloc(sizeof(struct list));
                struct  list* p2 = (struct list*)malloc(sizeof(struct list));
                system("chcp 1251");
                system("cls");
                printf("n= ");
                scanf_s("%d", &n);
                head = 0;
                head1 = 0;
                p2 = 0;
                p1 = 0;

                // Создание списка
                for (int i = 0; i < n; i++)
                {
                    printf("Введите элемент:");
                    scanf_s("%d", &a);
                    if (i == 0)
                    {
                        head = p1 = init(a);
                        head1 = init(a);
                        head = p1;
                    }
                    else
                        p1 = add(p1, a);
                }
                // Вывод списка
                listprint(head);
                putchar('\n');
                printf("e= ");
                scanf_s("%d", &e);

                for (int i = 0; i < e; i++)
                {
                    printf("Введите элемент:");
                    scanf_s("%d", &l);
                    if (i == 0)
                    {
                        head1 = p2 = init(l);
                        head1 = init(l);
                        head1 = p2;
                    }
                    else
                        p2 = add(p2, l);
                }
                listprint(head1);
                putchar('\n');
                sub(head, head1);
                sub(p1, p2);
                print(head);
                putchar('\n');
                //print(head1);




                free(p1);
                free(p2);
                //getch();
                return 0;
            }

          • Елена Вставская
            Для удаления первого элемента есть функция deletehead(). Надо проверить, если элемент является корнем, то ее вызвать

  • Здравствуйте, подскажите, пожалуйста, почему у меня не работает вставка
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    #include <iostream>
    using namespace std;
    struct list
    {
      char inf;
      list* next;
    };
    list* creat_1(char sym);
    list* creat_ost();
    void print(list* head);
    void insert(list* head,char x,char y);
    int main()
    {
      struct list* head,*cur,*u=NULL;
      head = creat_ost();
      print(head);
      cout << endl;
      cout << "after!!!" << endl;
      char x, y;
      cout << "vvedi y" << endl;
      cin >> y;
      cout << "vvedi x" << endl;
      cin >> x;
      insert(head, x, y);
      
      print(head);
      return 0;
    }
    list* creat_1(char sym)
    {
      list* first;
      first = new list;
      first->inf = sym;
      first->next = NULL;
      return first;
    }

    void print(list* head)
    {
      list* tmp;
      tmp = head;
      cout << "PRINT" << endl;
      while (tmp != NULL)
      {
        cout << tmp->inf;
        tmp = tmp->next;
      }
    }
    list* creat_ost()
    {
      list* cur;
      struct list* head;
      char ch;
      cin.get(ch);
      head = creat_1(ch);
      cur = head;
      cin.get(ch);
      while (ch != '.')
      {
        cur->next = new list;
        cur = cur->next;
        cur->inf = ch;
        cur->next = NULL;
        cin.get(ch);
      }
      return head;
    }
    void insert(list* head, char x, char y)
    {
      struct list* cur,*tmp;
      cur = head;
      while (cur->next = NULL)
      { 
        if (cur->inf == y)
        {
          tmp = new struct list;
          tmp->inf = x;
          tmp->next = cur->next;
          cur->next = tmp;
        }
        else
          cur = cur->next;
        
      }

      
      return head;
    }

  • Подскажите, как можно добавить или удалить элемент в конец списка? Реализовать динамическую структуру данных, описывающую предметную область в виде линейного односвязного списка, и процедуры:
    добавления элемента в начало списка; добавления элемента в конец списка; удаления элемента из начала списка; удаления элемента из конца списка; удаления из списка элемента, указанного его порядковым номером; изменение данных элемента списка, указанного его порядковым номером; вывода элементов списка на экран
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    #include <iostream>
    #include <forward_list>
    #include<climits>
    #include <windows.h>
    #include <cstring>
    #include <iomanip>

    using namespace std;

    struct Facult
    {
      char facultet[70];
      int kolvo_student;
      float sr_ball;
      int kolvo_otlich;
    };

    std::forward_list<Facult> facultList;
    Facult f;


    /*ФУНКЦИЯ ЗАНОСИТ ДАННЫЕ В НАЧАЛО СПИСКА*/
    void GetData(std::forward_list<Facult>& v)
    {

      // вводим поля f
      std::cout << "\n";
      std::cout << "Факультет: ";
      std::cin >> f.facultet;
      std::cout << "Кол-во студентов: ";
      std::cin >> f.kolvo_student;
      std::cout << "Средний балл: ";
      std::cin >> f.sr_ball;
      std::cout << "Кол-во отличников: ";
      std::cin >> f.kolvo_otlich;

      v.push_front(f); // добавляем введённую структуру в начало списка
      
    }
    /*ФУНКЦИЯ ЗАНОСИТ ДАННЫЕ В КОНЕЦ СПИСКА*/
    void GettData(std::forward_list<Facult>& v)
    {

      // вводим поля f
      std::cout << "\n";
      std::cout << "Факультет: ";
      std::cin >> f.facultet;
      std::cout << "Кол-во студентов: ";
      std::cin >> f.kolvo_student;
      std::cout << "Средний балл: ";
      std::cin >> f.sr_ball;
      std::cout << "Кол-во отличников: ";
      std::cin >> f.kolvo_otlich;


      auto iter = v.end();
      iter = v.insert_after(iter, f); // добавляем введённую структуру в начало списка

    }

    /*ФУНКЦИЯ ИЗВЛЕКАЕТ ЗАПИСЬ*/
    void ShowData(const std::forward_list<Facult>& v)
    {
      std::cout << "\n";
      std::cout << "Список факультетов\n";
      std::cout << '\n';



      /*ЯЧЕЙКИ-ЗАГОЛОВКИ*/
      std::cout << std::setw(20) << "Факультет" << '|';
      std::cout << std::setw(16) << "Кол-во студентов" << '|';
      std::cout << std::setw(14) << "Средний балл" << '|';
      std::cout << std::setw(18) << "Кол-во отличников" << '|';


      /*КОНЕЦ ЯЧЕЕК-ЗАГОЛОВКОВ*/
      std::cout << '\n';
      
      /*ВЫВОДИМ МАССИВ СТРУКТУР ПОСТРОЧНО*/

      for (const auto& f : v)
      {
        std::cout << std::setw(20) << f.facultet <<  '|';
        std::cout << std::setw(16) << f.kolvo_student << '|';
        std::cout << std::setw(14) << f.sr_ball << '|';
        std::cout << std::setw(18) << f.kolvo_otlich << '|';
        std::cout << std::endl;
      }

      /*КОНЕЦ ПОСТРОЧНОГО ВЫВОДА*/
      std::cout << '\n';
    }

    int main()
    {
      SetConsoleOutputCP(1251);
      SetConsoleCP(1251);

      while (true) {

        int variant;
        std::cout << "Выберите вариант\n" << std::endl;
        std::cout << "1. Добавить элемент в начало списка\n"
          << "2. Добавить элемент в конец списка\n"
          << "3. Удалить элемент из начала списка\n"
          << "4. Удалить элемент из конца списка\n"
          << "5. Удалить элемент по порядковому номеру\n"
          << "6. Изменить данные элемента списка\n"
          << "7. Вывести элементы списка\n" << std::endl;
        std::cout << ">>> ";
        std::cin >> variant;

        switch (variant) {
        case 1:
        {
          GetData(facultList);              //Добавление элемента в начало списка
          break;
        }
        case 2:
        {
          GettData(facultList);              //Добавление элемента в начало списка
          break;
        }
        case 3:
        {
          facultList.pop_front();             //Удаление элемента из начала списка
          break;
        }
        
        case 7:
        {
          ShowData(facultList);             //Вывод элементов экран
          break;
        }

        }
      }
      return 0;
    }

  • здравствуйте! подскажите, пожалуйста, что не так с моим кодом. Программа вроде бы читает его, но выводит какой-то бред. Спасибо большое!
    если это важно, то я программирую на маке в Xcode
    Задание: для односвязного списка груп (поля title, amount_of_students) реализовать функции : а)добавление элемента в голову списка б)удаление элемента из головы списка в)изменить порядок следования элементов г)напечатать весь список, фомат: "Group: title(amount_of_students)"; д)удалить весь список
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    #include <stdio.h>
    #include <stdlib.h>
    const char delim[] = "_________________________________________\n";
    const char menu[] = "\nChoose option:\n1. Add before head\n2. Delete head\n3. Reverse list\n4. Print list\n5. Clear list\n0. Quit\n";
    typedef struct list_node {
       char title[20];
       int amount;
       struct list_node* next;
    } Node;
    Node* add_in_head(Node* cur) {
    Node* new_head;
    new_head = (Node*)malloc(sizeof(Node));
    printf("Enter group: ");
    getchar();
    gets(new_head->title, 20);
    printf("Enter amount of students: ");
    scanf("%d", &(new_head->amount));
    new_head->next = cur;
       return new_head;
    }
    Node* delete_head(Node* head) {
       Node* t;
    t = head->next;
    printf("Element deleted: %s (%d)\n", head->title, head->amount); free(head);
    return t;
    }
    Node* reverse(Node* head) {
    Node* n_head = NULL, *t = NULLwhile (head) {
    n_head = head; head = head->next; n_head->next = t; t = n_head;
    }
       return n_head;
    }
    void show(Node* head) {
        if (!head) printf(" Listis empty!!!!!\n");
        while(head){
    } }
    Node* delete_all(Node* head)
    {
    if (!head) return NULL;
    delete_all(head->next);
    printf("Element deleted: %s (%d)\n", head->title, head->amount); free(head);
    return NULL;
    }
    int main() {
    int opt = -1, count = 0; Node *head = NULL;
    do {
    printf(delim);
    printf(menu);
    printf(">> ");
    count = scanf("%d", &opt); printf(delim); printf("\n");
    switch (opt)
    {
    case 1:
            head = add_in_head(head);
          break;
    case 2:
            head = delete_head(head);
          break;
    case 3:
            head = reverse(head);
          break;
    case 4:
            show(head);
                   break;
    case 5:
            head = delete_all(head);
            break;
    case 0:
            head =  delete_all(head);
            printf("Quitting........\n");
            break;
            default:
            printf("Unknown option!!!!\n"); break;
                     }
               } while (count && opt);
        return 0;
    }

    • Елена Вставская
      "Виснет" функция вывода элементов списка, поскольку не реализован сам вывод и переход к следующему элементу.
      1
      2
      3
      4
      5
      6
      7
      void show(Node* head) {
        if (!head) printf(" Listis empty!!!!!\n");
        while (head) {
          printf("%s %d\n", head->title, head->amount);
          head = head->next;
        }
      }

  • Пожалуйста помогите.В консоль выводит только последний элемент структуры.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    #define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    #include <iostream>


    using namespace std;

    struct list
    {

      
      char *name;
      char* author;
      char* edition;
      char* year;
      char* type;
      // поле данных
      struct list* next; // указатель на следующий элемент
    };
    //list* Head = NULL;

    struct list* init(char name1[20],char author1[20],char edition1[20],char year1[10],char type1[20]) // а- значение первого узла
    {
      struct list* lst;
      
      // выделение памяти под корень списка
      lst = (struct list*)malloc(sizeof(struct list));

      lst->name = name1;

      lst->author = author1;

      lst->edition = edition1;

      lst->year = year1;

      lst->type = type1;

      lst->next = lst;; // это последний узел списка
      return(lst);
    }

    struct list* addelem(list* lst,char str_n[20],char str_a[20],char str_e[20],char str_y[10],char str_t[20])
    {
      struct list* temp, * p;
      temp = (struct list*)malloc(sizeof(list));
      
      p = lst->next; // сохранение указателя на следующий узел
      lst->next = temp; // предыдущий узел указывает на создаваемый

      temp->name = str_n;

      temp->author = str_a;

      temp->edition = str_e;

      temp->year = str_y;

      temp->type = str_t;

      temp->next = p; // созданный узел указывает на следующий элемент
      return(temp);
    }
    void listprint(list* lst)
    {
      struct list* p;
      p = lst;
      
      do {
        printf(" %s %s %s %s %s", p->name,p->author,p->edition,p->year,p->type); // вывод значения элемента p
        p = p->next; // переход к следующему узлу
      } while (p != lst);
    }
    int main() {

      struct list* head, * r, * p;
      head = 0;
      p = 0;

      char name_[20] = { "" };
      char author_[20] = { "" };
      char edition_[20] = { "" };
      char year_[10] = { "" };
      char type_[20] = { "" };

      cout << "how many elements?\n";
      int k;
      cin >> k;
      for (int i = 0; i < k; i++) {
        
        cout << "Name of a book: ";
        cin >> name_; 
        cout << "Name of author: ";
        cin >> author_; 
        cout << "Name of edition: ";
        cin >> edition_; 
        cout << "Year: ";
        cin >> year_; 
        cout << "Name of a type: ";
        cin >> type_; 

        if (i == 0)
        {
          p = init(name_,author_,edition_,year_,type_);
          head = p;
        }
        else
          p = addelem(p,name_, author_, edition_, year_, type_);
        
      }
      listprint(head);
    return 0;

    • Елена Вставская
      Проблема тут:
      1
      2
      3
      4
      5
      char name_[20] = { "" };
      char author_[20] = { "" };
      char edition_[20] = { "" };
      char year_[10] = { "" };
      char type_[20] = { "" };
      Нельзя выделять память статически. После того, как Вы вели новые значения, они заменились для всех элементов. Используйте указатели.

  • Добрый день. Можете помочь с реализацией кода. Дано два непересекающихся линейных списка. В списке №1 имеется указатель t, в списке №2 – указатель х. Вставить в список №1 после указателя t все узлы списка №2, следующие после указателя х.

    • Елена Вставская
      Могу, если покажете свой вариант и сообщите, что конкретно не получается. Делать задачу за Вас не буду.

      • 1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        30
        31
        32
        33
        34
        35
        36
        37
        38
        39
        40
        41
        42
        43
        44
        45
        46
        47
        48
        49
        50
        51
        52
        53
        54
        55
        56
        57
        58
        59
        60
        61
        62
        63
        64
        65
        66
        67
        68
        69
        70
        71
        72
        73
        74
        75
        76
        77
        78
        79
        80
        81
        82
        83
        84
        85
        86
        87
        88
        #include <iostream> 
        #include <string> 
        using namespace std; 


        struct node
        {
            double value;
            node *next = NULL;
        };

        struct stack
        {
            node *head = NULL;
        } stck;

        void add(double value)
        {
            node *n = new node();
            n->value = value;
            n->next = stck.head;
            stck.head = n;
        }
        double get()
        {
            if(stck.head)
            {
                double output = stck.head->value;
                stck.head = stck.head->next;
                return output;
            }
            else
                return 0;
        }

        void parse_string(string str)
        {
            int i = 0;
            string tmp = "";
            while(str[i] != '\0')
            {
                if(str[i] != ' ')
                {
                    switch(str[i])
                    {
                        case '+':
                            add(get() + get());
                            break;
                        case '-':
                            add(get() - get());
                            break;
                        case '*':
                            add(get() * get());
                            break;
                        case '/':
                            add(get() / get());
                            break;
                        default:
                            tmp += str[i];
                            break;
                    }
                }
                else if(tmp != "")
                {
                    add(stod(tmp.c_str()));
                    tmp = "";
                }
                i++;
            }
            printf("Answer is: %f\n", get());
        }
        int main()
        {
            string str;
            while(true)
            {
                stck.head = NULL;
                cout << "Enter exspression ('E' to exit)\n";
                getline (cin, str); 
                if(str[0] == 'E')
                    return 0;
                else
                {
                    parse_string(str);
                }
            }
            return 0;
        }

  • Можете ли вы код что представленный сверху объединить в одно целое. Я что-то не могу понять как все работает

  • Василий
    Добрый день! Подскажите пожалуйста, верно ли реализована функция добавления в конец списка, с трудом доходит эта тема...
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    struct Elem
    {
      int key;
      Elem *next;
    };


    bool AddtoTail(int key, Elem **list)
    {
      Elem *ptr = new Elem;
      if (ptr)
      {
        ptr->key = key;
        ptr->next = NULL;
        if(list == NULL)
        {
          *list = ptr;
          return true;
        }
        else
        {
          Elem *p = new Elem;
          p = *list;
          while (p->next)
            p = p->next;
          p->next = ptr;
          return true;
        }
      }
      return false;
    }

    • Елена Вставская
      Похоже на правду. Строчка Elem *p = new Elem; лишняя.
      1
      2
      Elem *p;
      p = *list;

  • Добрый день.А функция удаления узла должна возвращать указатель на элемент<следующий за удаляемым,то есть temp->ptr?А если вернуть просто temp,то получится предшествующий узел.

  • Здравствуйте! Не могу понять, как вывести на консоль элемент кольцевого односвязного списка вместе с его порядковым номером. Можете помочь?

    • Елена Вставская
      Для этого нужен счетчик элементов списка при его просмотре. А вообще кольцевой список подробно рассмотрен здесь.

  • Вячеслав
    Здравствуйте, как будет выглядеть задача с такими условиями: Создать односвязный список, потом проверить есть ли в списке узел, содержащий 0, и если есть, то вставить после него еще 3 узла со значением 0. Заранее спасибо!!

    • Елена Вставская
      Затрудняюсь ответить. Нужно реализовать функции инициализации списка, добавления элемента и вывода списка.
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      struct list lst, head;
      int num;
      scanf("%d",&num);
      head=init(num);
      lst = head;
      for(int i=0;i<9;i++)
      {scanf("%d",&num);
       lst = addelem(lst, num);
      }
      listprint(head);
      lst = head;
      while(lst != NULL)
      {if(lst->field ==0)
      {
      lst =addelem(lst,0);
      lst =addelem(lst, 0);
      lst =addelem(lst, 0);
      }
      }
      listprint(head);

  • помогите пожалуйста, не работает этот код что нужно поменять ?
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    #include <stdio.h> 
     
    struct Node{
      Node* next;
      int data;
    };
     
    void push_back(Node **head, Node **last, int data){
      Node *node = new Node;
      node->next = NULL;
      node->data = data;
      if (*last != NULL)
        (*last)->next = node;
      *last = node;
      if (*head == NULL)
        *head = *last;
    }
     
    void print(Node *head){
      while (head != NULL){
        std::cout <data <next;
      }
    }
     
    int main(){
      Node *head = NULL, *last = NULL;
      for (int i = 0; i < 100; i++){
        push_back(&head, &last, i);
      }
      print(head);
      return 0;
    }

    • Елена Вставская
      Вроде работает. Правда, скопировался с ошибками. Но это - мой недосмотр.

  • Дмитрий
    Как рабить указаный список на два по указанному элементу . Вот код :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    #include "stdafx.h"
    #include "stdio.h"
    #include "locale.h"
    #include "stdlib.h"
    typedef struct Node {
      int value;
      struct Node *next;
    }Node;

    void push(struct Node** head, int num)
    {
      struct Node* current = *head;
      Node *newNode = (Node*)malloc(sizeof(struct Node));
      newNode->value = num;
      newNode->next = NULL;
      if (current == NULL) {
        *head = newNode;
      }

      else {
        while (current->next != NULL) {
          current = current->next;
        }
        current->next = newNode;
      }
    }

    void printFromHead(const Node* list) {
      if (list) {
        printf("%d ", list->value);
        printFromHead(list->next);
      }
    }
    void main()
    {
      setlocale(LC_ALL, "ukr");
      int x, z;
      Node *head = NULL;
      printf("Вкажiть розмiр списку - ");
      if ((scanf("%d", &x)) != 1) {
        printf("Неверное введенное значение");
      }
      printf("\n");
      for (int i = 0; i < x; i++)
      {
        z = 0 + rand() % 100;
        push(&head, z);
      }
      printf("\n");
      printFromHead(head);
      printf("\n");
      system("pause");
    }

  • Створити зв’язаний список з n-елементі (де n-випадкове число). Видаляти по кругу кожен третій елемент, доки не залишиться 1. Кожен крок повертати на екран.Как это сделать помогите пожалуйста.

    • Елена Вставская
      Не могу понять условие, записанное на незнакомом мне языке :(

  • Здравствуйте! В функции init(int a) нельзя исключать возможность того, что функция malloc() не сможет выделить память и вернет NULL. В таком случае значение первого узла а присваивается непонятно чему, т.к. lst = NULL и инструкция 
    lst->field = a;
    завершится ошибкой.
    Правильнее было бы всегда проверять значение, возвращаемое malloc() на NULL. То же самое относится и к функции addelem(list *lst, int number).
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    struct list * init(int a) // а- значение первого узла
    {
    struct list *lst;
    // выделение памяти под корень списка
    lst = (struct list*)malloc(sizeof(struct list));
    // Проверяем успешность выделения памяти под корень списка
    ifNULL == lst) return NULL;
    lst->field = a;
    lst->ptr = NULL// это последний узел списка
    return(lst);
    }


      • Прошу простить великодушно за мою настырность, но позволю себе обозначить еще один источник потенциальных проблем. Если рассматривать многопоточную среду исполнения, то все данные функции не обладают свойством реентерабельности, т.е. не потокобезопасны. В том плане, что процедура связывания или удаления узлов списка должна быть атомарной операцией, т.е. код в той части, где выполняются манипуляции над указателями и полями данных должен быть расположен в критической секции, что-то типа
        1
        2
        3
        4
        5
        6
        7
        8
        Enter_Critical();
        p = lst->ptr; // сохранение указателя на следующий узел
        lst->ptr = temp; // предыдущий узел указывает на создаваемый
        temp->field = number; // сохранение поля данных добавляемого узла
        temp->ptr = p; // созданный узел указывает на следующий элемент

        Exit_Critical();
        ...
        Рассмотрим такой пример. Пусть наш список состоит из 3-х элементов:
        1
        root => elem1 => elem2 => elem3 => NULL
        Предположим существует два параллельных потока (задачи, нити и т.д. на разных платформах это называется по-разному, но сути не меняет), в которых  мы хотим добавить элемент в конец списка (далее псевдокод в порядке его выполнения во времени)
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        //Поток 1
        // тут какой-то код
        last_element = find_last_elem(root); // Получаем указатель на последний элемент
        addelem(last_elem, number); // добавляем новый элемент в конец списка
        // тут какой-то код

        //Поток 2
        // тут какой-то код
        last_element = find_last_elem(root); // Получаем указатель на последний элемент
        addelem(last_elem, number); // добавляем новый элемент в конец списка
        // тут какой то код
        пусть в данный момент поток 1 исполняется и мы получили указатель на последний элемент списка, в нашем случае это элемент 3, а затем вызвали функцию addelem(), которая начинает исполняться:
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        30
        31
        32
        33
        34
        35

        //Поток 1
        temp = (struct list*)malloc(sizeof(list));
        p = lst->ptr; // сохранение указателя на следующий узел, в нашем случае он последний p = NULL

        // Уупс! Исполнение переключилось на поток 2 никто не гарантирует, что этого не может случиться именно в этом месте

        // поток 2 - теперь мы в потоке 2

        // нашли последний элемент списка - это (какая неожиданность !!) элемент 3, т.к. мы просто не успели переназначить //указатели
        // теперь мы вошли в функцию addelem() повторно

        temp = (struct list*)malloc(sizeof(list));
        p = lst->ptr; // сохранение указателя на следующий узел, это NULL
        lst->ptr = temp; // предыдущий узел указывает на создаваемый, теперь это элемент 4
        temp->field = number; // сохранение поля данных добавляемого узла
        temp->ptr = p; // созданный узел указывает на следующий элемент, в нашем случае NULL
        return(temp);

        // вернулись в функцию потока 2
        // у нас должен быть следующий список root => elem1 => elem2 => elem3 => elem4 => NULL
        // выполняем какой-то код потока 2
        // упс!!! опять переключение на поток 1!!!!

        // Поток 1
        // Продолжаем с того места на котором прервались

        // lst у нас по-прежнему указывает на element 3, хотя это уже не последний элемент списка!!!!
        lst->ptr = temp; // предыдущий узел указывает на создаваемый, но это не элемент 4 добавленный в потоке 2
        // таким образом указатель на элемент 4, созданный в потоке 2 затирается
        temp->field = number; // сохранение поля данных добавляемого узла
        temp->ptr = p; // созданный узел указывает на следующий элемент
        return(temp);

        // возврат в функцию потока 1, выполняем какой-то код потока 1
        Итак, подытоживая, что мы видим. Мы видим, что в поле ptr элемента 3 указатель на элемент 4, добавленный в конец списка в потоке 2, затирается старым значением в потоке1, а сам он безвозвратно теряется. Помимо потери самого элемента, это создает опасную ситуацию утечки памяти, т.к. указатель на элемент 4 созданный в потоке 2 безвозвратно утерян, и мы никак уже не сможем освободить память выделенную под него.

        • возможно, я не правильно выразился. Функции то в принципе могут быть реентерабельны, но не потокобезопасны, тк. не обеспечивают в данном случае правильный доступ к разделяемым данным (в нашем случае списку).

        • Елена Вставская
          Из Вашего комментария проблема ясна, но не понятны пути ее решения. Я приводила пример для однопоточного приложения.


  • Александр
    Здравствуйте. Спасибо за хорошую статью. Применяю Ваш метод перестановки двух звеньев, чтобы поменять минимум и максимум в списке. Для нахождения звеньев использую другие функции. На данный момент все работает, но только если звенья в середине, т.е. не первое и не последнее. Причем не важно, рядом элементы или нет. Посоветуйте, какое условие написать для обоих вариантов, чтобы все работало. Заранее спасибо. Вот мой код:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    void switchMinMax(Node *head) 
    {
      Node *prevMax, *prevMin, *postMax, *postMin, *tmp;   
      Node *Max, *Min;   
      Max = getMax(head);   
      Min = getMin(head);   
      prevMax = head;   
      prevMin = head;   
      if (prevMax == Max)     
        prevMax = NULL;   
      else     
        while (prevMax->next != Max)       
          prevMax = prevMax->next;   
      if (prevMin == Min)     
        prevMin = NULL;   
      else     
        while (prevMin->next != Min)       
          prevMin = prevMin->next;   
      postMax = Max->next;   
      postMin = Min->next;   
      if (Min == postMax) 
      { //Соседние узлы
        Min->next = Max;     
        Max->next = postMin;     
        if (Max != head)       
          prevMax->next = Min;     
        if (Max == head)       
          prevMin = NULL;   
      }   
      else if (Max == postMin)   
      { //Соседние узлы
        Max->next = Min;     
        Min->next = postMax;     
        if (Min != head)       
          prevMin->next = Min;     
        if (Min == head)       
          prevMax == NULL;   
      }   
      else
      { //В разных местах
        if (Max != head)       
          prevMax->next = Min;     
        Min->next = postMax;     
        if (Min != head)       
          prevMin->next = Max;     
        Max->next = postMin;   
      } 
    }

    • Елена Вставская
      Для того, чтобы поменять корневой узел с каким-либо, нужно вернуть новый корень списка. В текст вставлен блок определения нового корня и исправлено несколько недочётов.
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      // Будем возвращать новый корень списка
      Node * switchMinMax(Node *head) 
      {   
        Node *prevMax, *prevMin, *postMax, *postMin, *tmp;   
        Node *Max, *Min;   
        Max = getMax(head);   
        Min = getMin(head);   
        // - - - Добавилось - определение нового корня
        Node *newhead = head;   
        if (Max == head) 
          newhead = Min;   
        if (Min == head) 
          newhead = Max;   
        // - - - - - - - - - - - - - -
        prevMax = head;   
        prevMin = head;   
        if (prevMax == Max)     
          prevMax = NULL;   
        else     
          while (prevMax->next != Max)       
            prevMax = prevMax->next;   
        if (prevMin == Min)     
          prevMin = NULL;   
        else
          while (prevMin->next != Min)       
            prevMin = prevMin->next;   
        postMax = Max->next;   
        postMin = Min->next;   
        if (Min == postMax)   
        { //Соседние узлы
          Min->next = Max;     
          Max->next = postMin;     
          if (Max != head)       
            prevMax->next = Min;     
          //else // не нужно
          // prevMin = NULL;
        }   
        else if (Max == postMin)   
        { //Соседние узлы
          Max->next = Min;     
          Min->next = postMax;     
          if (Min != head)       
            prevMin->next = Max; // изменилось
            //if (Min == head) // не нужно
          // prevMax == NULL;
        }   
        else   
        { //В разных местах
          if (Max != head)       
            prevMax->next = Min;     
          Min->next = postMax;     
          if (Min != head)       
            prevMin->next = Max;     
          Max->next = postMin;   
        }   
        return newhead; 
      }


      • Александр
        Все таки сделал по своему, но передал в функцию указатель на указатель. Спасибо большое за подсказку где искать. Долго пытался. Извините что не воспользовался вашим кодом, свой роднее и понятнее :-). Ну и если кому то понадобится, собственно код:
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        30
        31
        32
        33
        34
        35
        36
        37
        38
        39
        40
        41
        42
        43
        44
        45
        46
        47
        48
        49
        50
        51
        52
        53
        54
        55
        56
        57
        switchMinMax(Node **head) //<замена>
        {
          Node *prevMax, *prevMin, *postMax, *postMin, *tmp;
          Node *Max, *Min;
          Max = getMax(*head);  //Передаем значение Max и Min
          Min = getMin(*head);

          prevMax = *head;
          prevMin = *head;
          if (prevMax == Max)
            prevMax = NULL;
          else
            while (prevMax -> next != Max)  //Находим элементы перед Max и Min
              prevMax = prevMax ->next;
          if (prevMin == Min)
            prevMin = NULL;
          else
            while(prevMin -> next != Min)
              prevMin = prevMin -> next;
          postMax = Max -> next;            //Определяем элементы стоящие после Max и Min
          postMin = Min -> next;
          if (Min == postMax)
            { //Соседние узлы
              Min -> next = Max;
              Max -> next = postMin;
              if (Max != *head)
                prevMax -> next = Min;
              else *head = Min;
              prevMin = NULL;
            }
          else if (Max == postMin)
            { //Соседние узлы
              Max -> next = Min;
              Min -> next = postMax;
              if (Min != *head)
                prevMin -> next = Max;
              else *head = Max;
              prevMax = NULL;
            }
          else
            { //В разных местах
              if (Max != *head)
                prevMax -> next = Min;
              Min -> next = postMax;
              if (Min != *head)
                prevMin -> next = Max;
              Max -> next = postMin;
            }
          if (Max == *head)
            *head = Min;
          prevMin = NULL;
          Min -> next = postMax;
          if (Min == *head)
            *head = Max;
          prevMax = NULL;
          Max -> next = postMin;
        }
        А вызывать функцию так: switchMinMax(&head);

      • Иван Петухов
        Уважаемая Елена, спешу Вам сообщить, что в коде, который Вы нам предоставили имеются ошибки. Так, в строке 42 не выполняется оператор ветвления, а в следующей за ней строке не выполняется операция присвоения.

        • Елена Вставская
          Честно говоря, не поняла, к какому коду относится Ваш комментарий.

  • Кристина
    Здравствуйте! не могли бы вы помочь ?! Задание такое: дан линейный список, в нем нужно найти максимальный элемент и потом его поставить в начало списка.

  • Создать односвязный список на основе класса, объекты которого будут формировать этот список. В описание класса должны входить данные для хранения комплексных чисел; функции для доступа к отдельным компонентам списка, вывод на экран элементов списка в формате ai+b, добавление элемента в начало списка, удаление элемента списка. Использовать указатель this.


  • Добрый день! Может кто поможет, не получается никак решить задачу такого типа, нужно сформировать стек чисел и занести в новый список до максимума из первого стека - списка. Мое решение, все работает, кроме копирования в новый список.. вот сама функция записи (стек уже заполнен)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    struct Stack *new_list = NULL// указатель на стек, в который будем записывать
    void task(struct Stack*begin) {
      struct Stack *temp = begin;  // создали указатель на стек
      int max = 0;
      printf("\n От вершины до максимального значения:\n");
      while (temp != NULL) { // заносим значения в новый стек до max
        if ((temp->number) > max) {
          new_list = (struct Stack*)malloc(sizeof(struct Stack));
          new_list->number = temp->number;
          new_list->next = new_list;
          max = (temp->number);
        }
        temp = temp->next;
      }
      printf("\nПросмотр\n");
      while (new_list != NULL) {
        printf("%4d", new_list->number);
        new_list = new_list->next;
      }

    • Елена Вставская
      Нужно в цикле определить максимальный элемент и запомнить его указатель.
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      struct Stack *maxelem = begin; 
      int max = maxelem->number; 
      while (temp != NULL

        if ((temp->number) > max) 
        { 
          maxelem = temp;     
          max = (temp->number); 
        }   
        temp = temp->next; 
      }
      Только после этого, когда мы знаем максимальный элемент и указатель на него, можно формировать новый список.

      • Большое спасибо за быстрый ответ.. наверное, я что-то не понял, определил указатель на макс элемент, занес в новый список значения, но на консоли не отображается.  Не могли бы вы посмотреть, очень благодарен вам за помощь.
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        30
        31
        struct Stack *new_list = NULL
        void task(struct Stack*begin) 

          struct Stack *temp = begin;   
          struct Stack *maxelem = begin;   
          int max = maxelem->number;   
          printf("\n От вершины до максимального значения:\n");   
          while (temp != NULL
          { 
            if ((temp->number) > max) 
            { 
              maxelem = temp;       
              max = (temp->number); 
            }     
            temp = temp->next; 
          }   
          struct Stack*temp2 = begin;   
          while (temp2 != maxelem) 
          { 
            new_list = (struct Stack*)malloc(sizeof(struct Stack));   
            new_list->number = temp2->number;   
            new_list->next = new_list;   
            temp2->next = temp2; 
          }   
          printf("\nПросмотр\n");   
          while (new_list != NULL
          { 
            printf("%4d", new_list->number);   
            new_list = new_list->next; 
          } 
        }

        • Елена Вставская
          Ошибка в выделенной строчке. Вы зацикливаете указатель на сам элемент. Поле указателя на следующий элемент нужно инициализировать в момент создания этого "следующего" элемента.

          • Так в цикле я создаю структуру и инициализирую ее поля ,т.е. присваиваю в новую структуру адрес предыдущей.. запутался..

          • Елена Вставская
            1
            2
            3
            4
            5
            6
            7
            8
            9
            10
            11
            12
            struct Stack *new_list = (struct Stack*)malloc(sizeof(struct Stack)); 
            new_list->number = begin->number; // это корень нового списка
            new_list->next = NULL;   
            while (temp2 != maxelem) 
            {   
              struct Stack *temp3 = new_list;   
              new_list = (struct Stack*)malloc(sizeof(struct Stack));   
              new_list->number = temp2->number;   
              temp3->next = new_list;   
              new_list->next = NULL;   
              temp2 = temp2->next;   
            }

  • Николай
    В функции addelem() уже известен адрес узла, который содержит NULL. А я не понимаю как его найти.
    Допустим, при инициализации списка известен адрес корня, который и есть последним узлом. Теперь, допустим, у меня возникла необходимость добавить в этот список еще узел. Тут все понятно. Узел root имеет адрес. Я создаю вашей функцией новый. Заполняю его. Сохраняю в промежуточном указателе адрес поля рут т.е NULL.
      Далее меняю указатель рута на адрес нового узла, и потом переписываю указатель добавленного узла на NULL.
    Теперь я еще добавляю узел. Знаю о существовании рута. Если я воспользуюсь вашей функцией то перепишу указатель рута и нового узла. Опс...Все понял спасибо.
    Но тогда еще вопрос. Таким образом, я получу список задом наперед. Если я имею словарь с уже отсортированными словами от а до я. То в памяти буква я станет в начале списка, а А в конце. Можете помочь разобраться с этим?

    • Елена Вставская
      В функцию addelem() Вы передаете указатель на элемент, после которого необходимо осуществить добавление. Указатель корня списка при этом должен быть сохранен в другой переменной, и вывод списка необходимо осуществлять с корня.

      • Николай
        Значит я должен реализовать просмотр списка и как только я найду узел с NULL передать его указатель в функцию добавления узла. Благодарю за помощь. Со словарем не понятно. Имею файл с отсортированными словами от А до Я. Мне нужно его загрузить в память так что бы возле корня была буква А. С NULL буква Я. Ваша функция добавляет новый узел в конец списка. А как сделать наоборот?
        Я только учусь. Поэтому вопросы могут быть простыми для вас...

        • Елена Вставская
          В этом случае нужна функция, которая будет добавлять элемент в начало списка, наподобие этой
          1
          2
          3
          4
          5
          6
          7
          struct list * addroot(list *root, int number) {
            struct list *temp;
            temp = (struct list*)malloc(sizeof(list));
            temp->ptr = root; // создаваемый узел на предыдущий корень
            temp->field = number; // сохранение поля данных добавляемого узла
            return(temp); // возвращаем новый корень списка
          }

  • Николай
    У меня вопрос. В самом начале в списке один узел и его указатель = NULL. После добавления в список еще одного узла, указатель корневого станет показывать адрес добавленного узла, а у того, что добавился станет NULL. Как добавить следующий узел? Ведь единственный известный - это корневой

    • Елена Вставская
      Для этой цели в статье предлагается использовать функцию addelem()

  • Мне кажется в описании функции удаления узла есть ошибка: "Функция возвращает указатель на узел, следующий за удаляемым", но в приведенной функции возвращается как раз предшествующий, т.е. тот, чей ptr и переписали ("пока не найдем узел, предшествующий lst"). и, в принципе, зачем что-то возвращать, если можно просто сделать функцию как void.

    • Елена Вставская
      Вы можете использовать функции по своему усмотрению. Например, можно было бы объединить функции удаления узла и удаления корня и возвращать всегда новый корень списка.


  • Здравствуйте!) Можете пожалуйста объяснить что означает  (struct list*) перед функцией mallocа в строчке
    lst = (struct list*)malloc(sizeof(struct list));
    когда мы создаем корень списка?

    • Елена Вставская
      Это - приведение типа. Поскольку функция malloc() возвращает указатель неопределенного типа, чтобы не возникало ошибки его нужно привести к требуемому значению. Значение типа должно совпадать с тем, что стоит в левой части равенства. В данном случае это указатель lst, имеющий тип (struct list *).

      • 1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        30
        31
        32
        33
        34
        35
        36
        37
        38
        39
        40
        41
        42
        43
        44
        45
        46
        47
        48
        49
        50
        51
        52
        53
        54
        55
        56
        57
        58
        59
        60
        61
        62
        63
        64
        65
        66
        67
        68
        69
        70
        71
        72
        73
        74
        75
        76
        77
        78
        79
        80
        81
        82
        83
        84
        85
        86
        87
        88
        89
        90
        91
        92
        93
        94
        95
        96
        97
        98
        99
        100
        101
        102
        103
        104
        105
        106
        107
        108
        109
        110
        111
        112
        113
        114
        115
        116
        117
        118
        119
        120
        121
        122
        123
        124
        125
        126
        127
        128
        129
        130
        131
        132
        133
        134
        135
        136
        137
        138
        139
        140
        141
        142
        143
        144
        145
        146
        147
        148
        149
        150
        151
        152
        153
        154
        155
        156
        157
        158
        159
        160
        161
        162
        163
        164
        165
        166
        167
        168
        169
        170
        171
        172
        173
        174
        175
        176
        177
        178
        179
        #include <conio.h>
        #include <stdio.h>
        #include <string.h>
        #include <stdlib.h>
        #include <iostream>
        #include <iomanip>
        #include <cmath>
        #include <cstdlib>
        #include <math.h>

        using namespace std;
         #define pi 3.141592653
        int x;
         long double low, high, step;
         unsigned long long  SS;

        struct person { //описание структуры
         char f[30]; //фамилия
         char d[30]; //должность
         float zp,pr; //зарплата, премия
         char prof; //профсоюз
         float SS;
          long double low, high, step;
          int x;

         person *next; //указатель на следующего в списке
        };

        person vvesti() { //ввод элемента с клавиатуры
         person p;

         low=0;
         high=pi/4;
         step=pi/40;




         return p;
        }

        int show (person *head) { //показ всего списка с определением количества элементов

         unsigned long long count=0;

         if (head) while (1) {

                       std::cout << " X        | Y(X)          |\n----------+---------------+" << std::endl;
         for (  double  x = low; x <= high;   x += step ){

             std::cout << ' ' << std::fixed << std::setprecision(3) << std::left << std::setw(9) << x << "| "
             << std::left << std::setw(14) <<  sin(3*x)+cos(2*x)
             << "\n----------+---------------+" << std::endl;
        }
          count++;
          if (head->next == NULLbreak;
          head = head->next;
         }

         printf ("\nAll=%d",count);
         return count;
        }
        void search (person *head, char *st) { //поиск в списке строки st
         if (head==NULLreturn;
         person *next = head;
         do {
          char *find = strstr (next->f, st);
          if (find!=NULL) printf ("\n%s",next->f);
          if (next->next==NULLbreak;
          next = next->next;
         } while (1);
        }

        void copy1 (person *to, person *from) { //копирование одной записи
         strcpy (to->f, from->f);
         strcpy (to->d, from->d);
         to->zp = from->zp; to->pr = from->pr; to->prof =  from->prof;
        }

        person *add1 (person *head, person *st) { //добавление элемента st в начало списка
         //*st уже заполнен данными
         person *current = new person;
         copy1 (current, st); //копирует 1 запись
         if (head==NULL) current->next = NULL;
         else {
          current->next = head;
          head = current;
         }
         return current;
        }

        person *add2 (person *head, person *st) { //добавление элемента st в конец списка
         person *last = NULL;
         if (head!=NULL) {
          last=head;
          while (last->next!=NULL) last=last->next;
         }
         person *current = new person;
         copy1 (current,st);
         current->next = NULL;
         if (last) last->next = current;
         return current;
        }

        person *delete1 (person *head0, int n) { //удаление элемента по номеру 1..N
         // удалит элемент номер n и вернет указ.на нач.
         person *head = head0;
         if (head==NULLreturn NULL;
         if (n==1) { //удаляем первый
          person *ptr = head->next;
          delete head;
          return ptr;
         }
         person *prev = NULL, *start = head; int i=1;
         while (i<n) { //Ищем n-ый элемент
          prev = head; head = head->next;
          if (head==NULLreturn start;
          i++;
         }
         person *ptr = head->next;
         delete head;

         prev->next = ptr;
         return start;
        }

        person *sort (person *ph) { //сортировка списка методом вставок
         person *q, *p, *pr, *out=NULL;
         while (ph != NULL) {
          q = ph; ph = ph->next; //исключить эл-т
          //ищем, куда его включить:
          for (p=out,pr=NULL ; p!=NULL &&
            strcmp(q->f,p->f)>0; pr=p,p=p->next) ;
            //или ваш критерий, когда переставлять!
          if (pr==NULL) { q->next=out;out=q; } //в нач.
          else { q->next=p; pr->next=q; } //после пред.
         }
         return out;
        }

        int main() { //меню и главная программа
         person *head = NULL;
         while (1) {
          printf ("\n 1. Show all \
                   \n 2. Add in head \
                   \n 3. Add in tail \
                   \n 4. Delete by number \
                   \n 5. Sort by name \
                   \n 0. Exit ");
          fflush (stdin);
          char c;
          scanf ("%c",&c);
          person p;
          person *cur;
          int n, all;
          switch (c) {
           case '1': show (head);
           break;
           case '2': p = vvesti(); head=add1(head,&p);
           break;
           case '3': p = vvesti();
               cur = add2 (head,&p);
               if (head==NULL) head=cur;
           break;
           case '4':
            all = show(head);
            while (1) {
             printf ("\nVvedi nomer (1-%d): ",all);
             fflush (stdin); scanf("%d",&n);
             if (n>=1 && n<=all) break;
            }
            head = delete1 (head,n);
           break;
           case '5': head = sort (head);
           break;
           case '0': exit (0); break;
          }
         }
        }
        помогите мне реализовать так чтоб можно било удалять елементи вивода буду благодарен

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *