Заранее прошу войти в моё положение. (Если у кого-то достаточно доброе сердце, то следущие 3 обзаца можно пропустить)
Вообще, я в школе начал програмить на Си (чистом). Но это было так называемое "олимпиадное" программирование, которое даже скорее выявляло не программистов а математиков, пототму как нам объяснили только азы (стандартные переменные, функции, циклы... и вроде бы все). В школе как-то все равно было на каком языке пишешь, потому что уровень программирования все равно ниже плинтуса давался. 
Но вот, пошел в универ, а тут все преподают на паскале... Пробовал на паскале писать, но не смог - откровенно говоря, затошнило... продолжил писать на Си (уже к этому времени Си++, но как понимаете, разницу вряд ли на своем уровне смог уловить). Но появилась серьезная проблемма - курс програмухи включает в себя ООП (кое-как через РНР научился) и рекурентные типы данных... И вот на последних и смотрю теперь как баран на новые ворота...
Самое страшное. что у меня через 3 дня экзамен, а я до сих опр до конца не врубился в обозначения и механизмы.

А вот теперь вопрос конкретно по проге. Код брал  из коллекции тов Смита... 


Ну и собственно вопросы практически по каждой строчке...
1. Сама по себе структура (struct), это как бы класс, в котором нету методов? Т.е. есть конечно различия, но в целом, можно ли такое сказать?
2. item *list;  Объявляет (хм, как бы это сказать) "полноценный" элемент списка, или только ссылку на первый(последний???) элемент?
3. Объясните вообще, так сказать, на пальцах, как организуется доступ к каждому элементу списка. Что значит "->", в чем отличие i->prev->next от i->next->prev?

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

Где-то так.

Если вместо указателей переменные,то доступ к ним осуществляется с помощью точки.
Например.
struct item    
{    
  int element;    
  int prev;    
  int next;    
};
item list;
list.element=2;
list.prev=3;
list.next=4;
Если же это указатели,то вместо точки ставится указатель -> на данное.
struct item    
{    
  int element;    
  item *prev;    
  item *next;    
};    
item *list;
list->element=0;    
  list->next=list;    
  list->prev=list;

Next-это поле prev,а prev-это следующее поле в next. 

У тебя prev и next имеют тип структуры,в который они входят,поэтому они имеют такие же поля,как и структура. 

Угу... Все-таки не совсем понятно насчет i->prev->next от i->next->prev...

Как я понял, в первом случае будет от заданной записи перескакивать на предыдущую (->prev) а после можно будет работать с инфой, вписанной в поле next этой записи... блин... сам почти запутался... 

ТРЕТЬ, 
Структура почти тоже самое, что и класс (она тоже может иметь методы и участвовать в наследовании).
Отличается она от класса тем, что по умолчанию доступ к элементам открыт (public), а для класса - закрыт (private).
Больше, лично мне никаких различий обнаружить не удалось (ну хотя еще, при наследовании структуры от струтктуры наследование по-умолчанию открытое)

item* list; - это определение переменной list, которая может хранить ссылку на экземпляр типа item, но пока еще она не инициализирована (то есть еще не указывает на какой-либо экземпляр типа item). Зовется переменная list указателем на тип item.

-> - это оператор доступа к полю через ссылку (т.е. через значение указателя). То есть, если мы пишем 
то мы теперь можем иметь доступ к полям этой структуры через оператор ->:
Если же объявить list как обычную переменную, то доступ к полю осуществляется через точку:

На третий твой вопрос ответ должен быть уже ясен по идее.

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

i->prev->next=i
i->next->prev=i 

Так... во-первых всем ОГРОМНОЕ спасибо!!!
Сегодня встретил одного умного человека, он мне тож пообъяснял...

Теперь вот сам сел, решил сам свой список написать, причем не глядя на скрипт Смита, но что-то подобное...
Вообчем, то все работает, только осталось всего несколько вопросиков... Точнее они появились....
1. Самое интересное на текущий момент...

и

какова по сути разница между такими функциями? На сколько я понял, в первом варианте, если встретится например list = list->next, то у нас как бы "бегунок" переместится на следущую позицию списка (заранее извиняюсь, за самодеятельность типа "бегунок" и т.д., но просто я сейчас еменно так это воспринимаю)... А во втором случае по возращению в основную программу list останется таким как был... Или второй вариант вообще что-то другое из себя представляет?

*Далее несколько вопросов скорее по поводу стиля, а не работы алгоритма в целом.*
2. Не становится ли односвязный список почти бесполезной схемой в силу своей односторонности?
3. Тов Смит дал пример как создавать замкнутые списки, т.е. кольца по сути. Это дает сразу классную возможность не отслеживать конец списка, что очень удобно (по сути проверка конца списка - проверка не попали ли мы в начало), но если список не замкнут, то как отследить его конец и не "выскочить" куда не надо?
4. Когда понял, что список замкнут, то подумал, может можно как-то избежать такого понятия, как базовый элемент. Правда мысль пошла каким-то странным путём... Получилось примерно следущее - "А можно ли сделать так, чтобы базовый элемент вообще обстрактным - т.е. после первого инсерта (см. скрипт из первого поста) у нас только появлялся первый элемент списка?"
Как думаете, похоже на бред?
5. Так сказать "question 1 revisited"... Этакое перемещение "бегунка" считается допустимым в главной программе, или все-таки считается, что как мы создали первый элемент, так он первым и должен оставаться?


Я очень извиняюсь, что вопросы звучат неразборчиво - просто я еще только начинаю понимать, что это такое, так что с терминологией у меня полный завал...

И еще... Не могли бы вы дать пример программы, которая использовала бы списки не потому что та задание звучит, а потому что это удобно... 

ТРЕТЬ, 
На счет первого вопроса - весь код напиши. Нифига не понимаю.
2. Есть задачи, где элементы должны следовать строго в определенном порядке с первого до последнего.
3. Поле next у последнего элемента приравнивается к NULL (аналог нуля для указателя). При прохождении проверяем next на равенство NULL.
4. Как только список замыкается, то начальный элемент - это уже условность. У кольца начала и конца нет. Можно любой элемент за первый считать.
5. Опять не особо понял вопрос. При работе со списками как правило хранят указатель на первый элемент, чтобы его "не потерять", и используют хоть сотню "бегунков".

Так тебе текст программы нужен, или формулировка задачи? 

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

2 SaDFromSpb, 
насчет первого вопроса... Вот 2 кода, отличаются только на * в аргументе...


Первый работает, это уже проверено... А что насчет второго варианта? Вызывать еготочно так же как первый? Будет ли вообще что-то меняться по выполнению такой процедуры? И вообще нет ли в нем ошибок? 

Второй кусок вобще скомпилиться не должен, так как i не указатель, оператор -> для доступа к элементам использовать нельзя.
В первом примере мы на вход получаем адрес элемента, который нужно удалить (он хранится в перменной i). 
Во втором же к нам идет попадает копия элемента списка, подлежащего удалению.
Здесь можно написать вот так:
Но это все при условии, что в функцию передана структура, у которой верно заполнены поля prev и next. Стоит отметить, что здесь идет передча параметра по значению, то есть в i содержится копия того элемента списка, который нужно удалить. Следовательно, оригинал можно удалить сразу, что и делается в первой строчке. 
И последнее: второй способ - это изврат =), так как чаще всего стоит задача удалить элемент по такому-то адресу или с таким-то содержанием (например, с определенным номером, если элементы нумеруются).  

Это сообщение отредактировал(а) SaDFromSpb - 22.6.2006, 12:31

ТРЕТЬ, можно почитать про спики на С++ здесь 

Ладно... Впринципе есть еще один вопрос. но не думаю. что он уж очень важен...

Всем огромное спасибо!!!

Вопрос закрываю... И открываю новый=)


Что за тип данных такое "граф"? Насчет деревьев, стеков и иже с ними разобрался, а вот графа так и не встретил с нормальными комментариями... На сколько понял, это тоже что-то основанное на списках, или нет... Вообчем напишите. Очень будет сдорово, если найдется пример, хоть самый простой, но только чтобы можно было его сразу компилить - т.е. законченная прога была. Как правило, имея пример я уже могу разобраться. 

Нельзя. В Си это просто набор переменных, объединённых одним именем, в Си++ - это синоним класса, отличающийся от него только тем, что доступ в классе по умолчанию protected, в структуре - public. Во всём остальном struct = class. 

private

Добавлено @ 21:03 

не совсем
по умолчанию при наследовании от структуры используется модификатор public
 

Читаем здесь:

• Граф (математика) (http://ru.wikipedia.org)
• Графы. Поиск маршрутов (http://algolist.manual.ru)
• Операции с графами (http://alglib.sources.ru)

 

  
Всмысле почитал, интересно конечно, но просто ОЧЕНЬ хочется самый простой пример на СИ++ (вплоть до простого объявления структуры)

Эту уже последний вопрос, так что после его ответа буду помечать вопрос как решенный.