С++, Список, односвязный список (?!)

[MoBLer]

PHP код:

#include <iostream>

using namespace std;

struct Node {
    int a;
    Node* next;
};


int main()
{
    Node* tail;
    Node* head ;
    Node* temp;
    
temp= new Node;
temp->a = 1;
temp->next =NULL;

head=temp;
tail=temp;

temp= new Node;
temp->a = 2;
temp->next =NULL;
tail->next=temp;
tail=temp;

temp= new Node;
temp->a = 3;
temp->next =NULL;
tail->next=temp;
tail=temp;
    
    
    temp=head;
    do{
        cout<<temp->a<<endl;
        temp=temp->next;
    }while(temp->next!=NULL);
    cout<<tail->a<<endl;

    cin.get();
    cin.get();
    return 0;
} 


tail-указатель на хвост
head-указатель на начало
temp-временная переменная

[Fanyuus]

MoBLer, огромное вам спасибо!!))))
А вы можете прокомментировать программу? Не совсем понятны некоторые места....)))

Ладно, вот у меня ещё вопрос - 1 структура есть, а если у меня их 10 должно быть - копипастим и радуемся жизни или можно как-то упростить себе жизнь?

*был такой же вопрос в формах - много текстбоксов, его решили путём textBox(c), как-то так, где с - номер текстбокса. Может быть, тут тоже есть что-нибудь похожее?? Ну, а если нет, то не страшно, накопипастю))

[Fanyuus]

Хотя нет, вы знаете, я чуток разобралась и поняла что к чему. Методом проб и ошибок, так сказать

И вот в ходе этих проб и ошибок возникли следующие вопросы:

1 - как использовать в int-массиве указатели\ссылки\адреса на списки? *допустим, на голову?

2 - как устроить поиск элемента в списке? При условии. что в списке будут уже не все 9 элементов, а 5. А в другом будет 2. А в третьем 8.


3 - удаление?

4 - Допусти, у меня есть списки: li1,li2,li3, l4 и li5.
Как мне осуществить их перебор, чтобы не обращаться к каждому в ручную, а в какой-то общий цикл.

Например:

for (i=1; i<6; i++)
{
    //передача значения i к номеру(имени) списка. li1,li2,li3, l4 и li5
    
    for(x=0; x<n; x++)
         {
             Прибавить к значению списка 5;
            //вывести список 
             ...
          }
}

Такое можно реализовать или всё равно всё через "пропиши 150 списков, если у тебя 150 списков"?

[rrrFer]

1 - как использовать в int-массиве указатели\ссылки\адреса на списки? *допустим, на голову?

я ниче не понял

2 - как устроить поиск элемента в списке? При условии. что в списке будут уже не все 9 элементов, а 5. А в другом будет 2. А в третьем 8.

последниъ элемент списка хранит 0 в качестве указателя на следующий элемент, придумайте как исопльзовать этот факт

3 - удаление?

нарисуй список и посмотри что нужно сделать чтобы удалить элемент из начала, из конца и из середины, соответственно в программе рассмотри все эти 3 случая отдельно.

4 - Допусти, у меня есть списки: li1,li2,li3, l4 и li5.
Как мне осуществить их перебор, чтобы не обращаться к каждому в ручную, а в какой-то общий цикл.

засунь свои списки в массив

Node *lists[5]; // массив из 5 эказателей на головы списков

for (i=1; i<6; i++)

индексация в ++ начинается с нуля

[Fanyuus]

RrrFer
1 - ну вот допустим.
Массив из двух элементов.
В первой ячейке 1, а во второй как сделать хранение списка?
Суть "вопроса" такая, что можно ли хранить и цифру/число адрес/указатель/ссылку на список в одном массиве?

4 - т.е., я в цикле пишу тот код, а потом пишу действия, которые мне нужны, а чтобы переходить от одной головы к другой - использовать обычный фор, первый 0, и писать общий алгоритм.
Мыслю верно?

2 - аааа, цикл работает, пока next!=0
Указатель

Вечером буду думать над вопросом, попробую реализовать и выложить код))) спасибо большое, что помогаете))

[BDA]

1) Можно, но это какое-то извращение
Можно создать union со всеми вариантами и сделать массив union'ов (не утверждаю 100%, но с большой долей вероятности можно).

[Abstraction]

2 - void AddItem(List** l, void* item) -- функция по созданию списка, вижу, а переменные item и l - это какие переменные? тип, характер?
И их, похоже, описывать надо в main'е.
(о, я так даже понимаю, что item - число, а l - ссылка на следующую запись в списке?)

Извиняюсь, неверная оценка знаний. Если конструкция void* Вам незнакома, то выкиньте пока этот пример из головы.

И начнём с основ. Все объекты, которые Вы описываете в коде, "создаются" в каком-то месте оперативной памяти.

int variable=0;

Это простейшая инструкция: "найти место под переменную типа int, к которой в дальнейшем я буду обращаться по имени variable; записать туда 0". Сразу нюанс: локальные нестатические переменные функций создаются столько раз, сколько вызвана функция.

int Factorial(int n){
  if(n==0) return 1;
  return n*Factorial(n-1);
}

//Позже, где угодно в коде:
result = Factorial(5);

При этом функция Factorial будет вызывать сама себя, и каждый раз будет создаваться новая переменная n. При выходе из функции все её локальные нестатические переменные уничтожаются, так что к следующему вызову функция "забывает", что было в прошлый раз.
Что не совсем очевидно, функции - тоже переменные:

int Sum(int a, int b){
  return a+b;
}

Это означает "найти место под переменную Sum типа int(*)(int,int), записать туда код функции Sum". Функции в C++ могут быть определены только глобально, нельзя определить одну функцию внутри другой.
"Обычные" же переменные можно определять как глобально, так и внутри некоторой функции. Но в любом случае, переменная - это место в памяти, причём гарантируется, что разные переменные находятся в разных местах. Интересное следствие: если создать тип нулевого размера (это можно сделать), то массив из 1000 объектов такого типа обычно занимает... 1000 байт. Ведь иначе разные элементы массива имели бы один адрес.

Указатель - базовый тип данных. Могут существовать указатели на любую переменную: на int, на char, на массив из double и так далее. Поскольку указатели - тоже переменные, то существуют также указатели на указатели. Но если переменные могут занимать больше или меньше места, то указатели ("обычные" указатели, скажем так) всегда одного размера; на современных архитектурах это 4 или 8 байт. Поэтому в C++ есть специальный тип "просто указателя": void*. Обычно он используется в тех случаях, когда нам важен только кусок памяти, но не то, как он устроен (к примеру, функция memcpy копирует кусок памяти в другое место - и принимает аргументы типа void*).
Два важных момента. Первый: поскольку локальные нестатические переменные функции перестают существовать при выходе из неё, то, если мы нечаянно вернули вызвавшему коду указатель на такую переменную, он в действительности указывает "в никуда", обращение по нему есть ошибка. Второй: при вызове функции все аргументы копируются в локальные переменные функции. Никакие изменения копии не изменят оригинала, и это очень частые грабли начинающих.
Что же делать? Использовать указатели и внимательно следить за тем, как долго живут объекты, на которые они указывают.

void IncreaseBy2(int a){
  a += 2;
}

//...
int variable = 7;
IncreaseBy2(variable);
//variable по-прежнему равно 7. Облом.
IncreaseBy2(2);
//Ничего не случилось, внутри IncreaseBy2 создалась a=2, увеличилась на 2 и сдохла

Теперь указатели:

void IncreaseBy2(int* a){
  *a += 2; //*a - "то, на что указывает a"
}

//...
int variable = 7;
IncreaseBy2(&variable); //& - оператор взятия адреса. В IncreaseBy2 ушёл адрес variable
//Теперь variable равно 9
IncreaseBy2(&2); //Компилятор ругнулся - 2 не переменная, у неё нет адреса

[Abstraction]

Ключевое слово new служит для создания "долгоживущего" куска памяти: в отличие от локальных нестатических переменных, такой кусок памяти можно создать в функции и вернуть "наружу". new Type создаёт (выделяет) в оперативной памяти кусок достаточно большой, чтобы туда влез объект типа Type и возвращает указатель на этот кусок, типа Type*.

int* FaultySum(int a, int b){
  int result = a+b;
  return &result; //Так нельзя - этим результатом не воспользоваться
}

int* RightSum(int a, int b){
  int* result = new int;
  *result = a+b; //Обращаемся к выделенному куску памяти, пишем туда сумму
  return result; //Возвращаем указатель на этот кусок
}

Есть, правда, одна проблема: если мы потеряем (перезапишем чем-нибудь, потеряем при выходе из функции) указатель, выданный нам new, то память останется "занятой" с точки зрения системы управления памятью, до конца работы программы. То есть, мы не сможем использовать этот кусок снова. Такой эффект называется "утечкой памяти" (memory leak) и является настоящим бичом C/C++-программистов (и не только их). Дать понять, что этот кусок памяти вам не нужен, можно с помощью ключевого слова delete. Для каждого блока памяти, выдаваемого new, со временем должен быть вызван delete! В нашем примере:

for(int i=0; i<1000; ++i){
  int* sum = RightSum(x, i); //получили указатель
  if(*sum == 100) cout << i; //использовали
  delete sum; //удалили
}

Всегда должно быть три этих действия.

Структуры - простейший вариант пользовательского типа. Структура C (в C++ она немного "проапгрейдилась", но мы не будем обращать на это внимания) - это просто пачка переменных разных типов:

struct Date{
  int year, month, day;
}

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

Date d;
d.year = 1996; //Обращение к полю структуры делается через оператор .
d.year += 3; //Можно думать о d.year как об обычной переменной типа int
IncreaseBy2(&d.year); //В том числе и брать её адрес

Date* pD = new Date;
(*pD).year = 1998; //Всё знакомо, правда? Но каждый раз писать (*pD). надоедает...
pD->year = 1998; //То же самое по смыслу, просто удобнее писать
pD->day = d.day; //int присваиваем int, всё в порядке
delete pD; //Кончили пользоваться - удаляем. Всегда.

Переменная типа Date, повторюсь, подчиняется тем же правилам, что и все прочие - её можно создать как локальную переменную функции, как глобальную переменную, с помощью new (как переменную "в куче"). Есть и ещё один способ создать "свой" тип - с помощью ключевого слова typedef. Оно просто создаёт "синоним" имени типа:

typedef int Integer;
//Всё, с этого места и далее везде можно вместо int писать Integer

//А вот почему это иногда очень полезно:
typedef std::vector<std::pair<MyPoint, float> >::iterator Iter;
//Далее вместо этого крокодила можно писать просто Iter. Экономит нервы

//Ещё пример:
typedef int HitPoints;
//Тип HitPoints, "на самом деле" - банальный int. Однако синоним позволяет писать более читаемый код
//Кроме того, если в будущем мы решим, что HitPoints должны быть float - менять надо будет только эту строку

[Abstraction]

А теперь собираем всё вместе:

#include <iostream>

struct ListNode{
  ListNode* next; //Указатель, одна штука
  int data; //То, что хранит список
};

typedef ListNode* List; //List, "на самом деле" - просто указатель на первый ListNode

int main(void){
  //создаём список
  List l1 = NULL;

  //Добавляем элемент
  ListNode* toAdd = new ListNode; //создать
  toAdd->data = 42; //внести данные
  toAdd->next = l1; //пришить к списку
  l1 = toAdd;

  //И ещё раз
  ListNode* toAdd2 = new ListNode; //создать
  toAdd2->data = 17; //внести данные
  toAdd2->next = l1; //пришить к списку
  l1 = toAdd2;

  //Убрать элемент
  ListNode* toDelete = l1;
  l1 = toDelete->next;
  delete toDelete;

  //Перебрать все элементы списка
  for(ListNode* cur = l1; cur!=NULL; cur = cur->next){
    std::cout << cur->data;
  }

  //Очистить список - ОБЯЗАТЕЛЬНО!
  //Если просто вызывать delete cur в цикле, то cur->next не сработает
  for(ListNode* cur = l1, cur2; cur!=NULL; cur = cur2){
    cur2 = cur->next;
    delete cur;
  }
  l1 = NULL; //Иначе l1 указывает "в никуда" и поди это пойми
}

А теперь, чтобы не дублировать код (обратите внимание на одинаковые добавления элементов), добавим функции:

#include <iostream>

struct ListNode{
  ListNode* next; //Указатель, одна штука
  int data; //То, что хранит список
};

typedef ListNode* List; //List, "на самом деле" - просто указатель на первый ListNode

void List_init(List* thiz){
  *thiz = NULL; //Передаём указатель на List - нам же его менять 
}

void List_add(int elem, List* thiz){
  ListNode* toAdd = new ListNode; //создать
  toAdd->data = elem; //внести данные
  toAdd->next = *thiz; //пришить к списку
  *thiz = toAdd;
}

void List_remove(List* thiz){
  ListNode* toDelete = *thiz;
  *thiz = toDelete->next;
  delete toDelete;
}

void List_destroy(List* thiz){
  //Если просто вызывать delete cur в цикле, то cur->next не сработает
  for(ListNode* cur = *thiz, cur2; cur!=NULL; cur = cur2){
    cur2 = cur->next;
    delete cur;
  }
  *thiz = NULL;
}

int main(void){
  //создаём список
  List l1;
  List_init(&l1);

  //Добавляем элемент
  List_add(42, &l1);

  //И ещё раз
  List_add(17, &l1);

  //Убрать элемент
  List_remove(&l1);

  //Перебрать все элементы списка
  for(ListNode* cur = l1; cur!=NULL; cur = cur->next){
    std::cout << cur->data;
  }

  //Очистить список - ОБЯЗАТЕЛЬНО!
  List_destroy(&l1);
}

[rrrFer]

Abstraction, решил учебник написать? - я давно заметил )

Суть "вопроса" такая, что можно ли хранить и цифру/число адрес/указатель/ссылку на список в одном массиве?

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