связанные списки (с++)

[Laticia]

Здравствуйте, все!
Помогите неопытной программистке с филологического факультета СПбГУ научиться создавать эти самые списки и проделывать над ними разные операции при помощи с++.
Что такое связанные списки, я знаю, но если Вы укажете ресурс, где можно познакомиться поближе с этими зверями - против не буду.
Ближайшая задача- создать список из трех элементов и вывести на экран (не смейтесь), но хотелось бы разобраться в общем случае.
Еще укажите, где можно подробно почитать про динамическое распределение памяти.
Заранее всем спасибо.

[Finch]

Еще укажите, где можно подробно почитать про динамическое распределение памяти.

Любой нормальный учебник по С++, который в последствии можно использовать в качестве справочника.

Чтобы начать объяснять, нужно знать уровень твоих знаний в программировании вообше. Насколько ты их оцениваеш сама?

P.S. Это наверно модно стало, Филологов учить программированию. 

[Джон]

Finch, а она и не сказала, что она филолог. Вот что программист делает на филологическом факультете - это другой вопрос.

Laticia, в самом деле - что именно ты уже знаешь? И НАСКОЛЬКО ближе хочешь с ними познакомиться. Там вроде всё просто - объект знает соседей. "Чего же более? Что я могу ещё сказать?"

[LP]

Помогите неопытной программистке с филологического факультета СПбГУ

Это Вы в прошлый раз спрашивали про методы сортировки?

Какие списки интересуют? Односвязанные? Двусвязанные?
На каком компиляторе нужно чтобы работало?

Вот хороший односвязанный список, взятый отсюда:
http://pegasus.rutgers.edu/~elflord/cpp/list_howto/

Код:

class List
{
public:
	struct Node 
	{
		Node(const int& data, Node* next=0):data(data),next(next) {}
		Node* next;
		int data;
	};

	List() : head(0) {}

	List(const List& L) : head(0)
	{
		for ( const Node* i = L.begin(); i!= L.end(); i=i->next )
			push_front(i->data);
		reverse();
	}

	void reverse()
	{
		Node* p = 0; Node* i = begin(); Node* n;
		while (i)
		{
			n = i->next;
			i->next = p;
			p = i; i = n;
		}
		head = p;
	}

	void swap(List& x)
	{
		Node* tmp = head; head = x.head; x.head = tmp;
	}

	List& operator=(const List& x)
	{
		List tmp(x);
		swap(tmp);
		return *this;
	}

	~List() { clear(); }
	void clear() { while (!empty()) pop_front(); }

	bool empty() { return ! head; }

	void push_front(const int& x) { 
		Node* tmp = new Node(x,head); head = tmp; 
	}

	void pop_front() { 
		if (head) { Node* tmp = head; head=head->next; delete tmp; }
	}

	void insert_after(Node* x, const int& data)
	{
		Node* tmp = new Node(data, x->next);
		x->next = tmp;
	}

	void erase_after(Node* x)
	{
		Node* tmp = x->next;
		if (tmp)
		{
			x->next = x->next->next;
			delete tmp;
		}
	}


	int& front() { return head->data; }
	const int& front() const { return head->data; }

	Node* begin() { return head; }
	Node* end() { return 0; }

	const Node* begin() const { return head; }
	const Node* end() const { return 0; }

private:
	Node* head;
};

#include <iostream>
using namespace std;

int main()
{
	List X;
	X.push_front(3);
	X.push_front(2);
	X.push_front(1);

	for (List::Node* it = X.begin(); it; it = it->next )
		cout << it->data << endl;

	X.reverse();

	for (List::Node* it = X.begin(); it; it = it->next )
		cout << it->data << endl;
	return 0;
}

Когда будут конкретные вопросы - задавайте.

[Finch]

LP,  Ты прикалываешся или как? Даеш пример с шаблоном, человеку, который только что начал изучать С++

[Laticia]

Про сортировки я спрашивала, только весной. Теперь там уже все понятно
В школе я Паскаль учила на уровне - напишите программу которая узнает, какой через n минут будет цвет на светофоре...
В прошлом году мы в университете стали изучать С++. Преподаватель у нас не ах - нам не объясняют почти ничего, только задания дают.
Впрочем теорию я более менее знаю в том объеме, как нас спрашивают, а вот записать све как надо - это проблема. Вот на эту программу у меня больше часа ушло :

Код:

#include <stdio.h>
#include <malloc.h>

struct List{
       int data;
       List*next;
       };
int main(){
List* point;
point = (List*) malloc (sizeof (List)); //выделяем место в памяти
point -> data = 1; //присваиваем элементу значение
point -> next = NULL; //следующий элемент отсутствует
printf ("1st value = %d\n", point -> data);
free (point);
point = NULL;
getchar();
}

хотя она элементарная.
знания свои, в общем, оцениваю как начальныеБ а познакомиться хочу подробно - мне экзамен сдавать летом

Да, кстати по сортировкам у меня зачет, так что спасибо

[Finch]

Мыслиш в правильном направлении. Теперь только осталось сделать сам список.

Кстати для работы со списком заведи еше одну переменную-указатель. С помошью ее ты сможеш перемешаться по списку. При этом головной указатель не будет потерян.

[LP]

Сорри, что не сразу ответил, были проблемы с интернетом...

LP, Ты прикалываешся или как? Даеш пример с шаблоном, человеку, который только что начал изучать С++

Извиняюсь, шаблоны из прошлого поста убрал. Получился минимальный список на С++, от которого ИМХО надо отталкиваться.

Вот на эту программу у меня больше часа ушло

Только это скорее Си, чем С++. Далее нужно выделить создание узла в отдельную функцию и добавить пару функций. Примерно так.

Код:

struct List
{
	int data;
	List*next;
};

List* create_node(int dat = 0, List* nxt = NULL)
{
	List* node = (List*)malloc(sizeof(List));
	node->data = dat;
	node->next = nxt;
	return node;
}

void destroy_node(List* node)
{
	free(node);
}
//вставка в позицию после node
List* insert_after(List* node, int dat)
{
	List* newnode = create_node(dat, node->next);
	node->next = newnode;
	return newnode;
}
//вставка в начало списка
List* insert_front(List* first_node, int dat)
{
	return create_node(dat, first_node);
}

void remove_node(List* first_node, List* node)
{
	if(first_node == NULL) return;
	while(first_node->next != NULL && first_node->next != node) 
		first_node = first_node->next;
	if(first_node->next != NULL) 
	{
		first_node->next = node->next;
		destroy_node(node);
	}
}

List* remove_all(List* first_node)
{
	while(first_node != NULL)
	{
		List* t = first_node;
		first_node = first_node->next;
		destroy_node(t);
	}
	return NULL;
}

List* find_node(List* node, int value)
{
	while(node) {
		if(node->data == value) return node;
		node = node->next;
	}
	return NULL;
}

void print_list(List* list)
{
	printf("[ ");
	while(list != NULL)
	{
		printf("%d ", list->data);
		list = list->next;
	}
	printf("]\n");
}

Тестовая программа:

Код:

#include <stdio.h>
#include <malloc.h>

//...

int main()
{
	List* list = NULL;
	print_list(list); // выводит: [ ]
		
	list = create_node(1);
	print_list(list); // [ 1 ]
	
	list = insert_front(list, 10);
	list = insert_front(list, 8);
	print_list(list); // [ 8 10 1 ]
	
	List* node = find_node(list, 10);
	//... [ проверка на NULL пропущена ]
	insert_after(node, 21);
	print_list(list); // [ 8 10 21 1 ]
	
	remove_node(list, node);
	print_list(list); // [ 8 21 1 ]
	
	list = remove_all(list);
	print_list(list); // [ ]
}