Связанные списки в C++

[fixoto]

Знающие, помогите! Я не стал создавать новую тему так как проблема у меня очень похожая. Скажу сразу что все ваши примеры я компилировал, но ни один не скомпилировался, везде ошибки.

Задача у меня следующая: написать программу реализующую работу с простейшим неограниченным по size стеком, с методами pop и push. - это вторая самостоятельная работа из 24х, все остальные я уже сделал! Сдать мне ее нужно было еще в начале сентября, а я до сих пор не могу понять где в ней ошибка в синтаксисе. Написать нужно для интерпретатора c++ 3.1 (досовский). Как я уже только не извращался, но не могу реализовать её и всё тут... Причем на паскале и делфи уже делал подобное и даже более сложное без проблем. А как началось c++ так тут все, полный каюк. Насчет литературы и примеров: кучу их перерыл, но в них везде либо стек ограниченый, либо написан с использованием стандартного (встроенного) класса стека.

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

#include <iostream.h>
#include <stdio.h>

Class Stack
{
Stack ();
Stack (Int2 Number);
{
Push(Number);
};
~Stack ();
Private:
Class IntUnit
{
Int2 Number;
IntUnit * Pointer;
};
IntUnit * Pointer;
Public:
Int2 Pop ()
{
If (Pointer==0) Return 0;
Int2 Number=Pointer.Number;
IntUnit * Pointer2=Pointer.Pointer;
Delete Pointer;
Pointer=Pointer2.Pointer;
//Delete Pointer2;
Return Number;
};
Void Push (Int2 Number)
{
IntUnit NewUnit=New NewUnit;
*NewUnit.Number=Number;
If (Pointer!=0)
NewUnit.Pointer=Pointer;
Pointer=NewUnit;
};
}

Void Main ()
{
}

Примечания:

1) Int2 - беззнаковый целочисленый тип размером в 2 байта
2) Компилятор не умеет сверять указатели с 0 и NULL, так как таких значений для указателей он не знает. Если вы подскажите как их реализовать буду оч благодарен.
3) Ну и естественно прога не компилируется из-за кучи придирок интерпретатора.

Помогите! Пожалуйсто!!

[Koketka]

Привет!!!а как написать функции занесения и извлечения данных на основе связанного списка?!!программка приведенная выше - это похожа на стек на основе массива...

[Ar@gorn]

Вот реализация стэка на C++ (возможно не самая лучшая, но вполне работающая)

struct stack
  {
  int a, b;
  stack *next;
  //указатель на следующий элемент списк
  };
//описание структуры

stack *head = NULL;
//указатель на голову стэка

void push(stack *data)
{
stack *p;
//обявляем указатель на структуру
p = new stack;
//создаём новую динамическую переменную
p->a = data->a;
p->b = data->b;
//заносим в неё данные
p->next = head;
//цепляем в начало стэка
head = p;
//обновляем голову стэка
}
//операция вставки в начало стэка элемента

stack *pop()
{
stack *p;
p = head;
//берём указатель на первый элемент
head = head->next;
//переносим голову стэка на элемент вперёд
return p;
}
//операция получения из стека элемента

bool nihil()
{
if (head == NULL)
  return true;
else
  return false;
}
//функция возвращает true если стэк пустой

Стэк - это структура типа Последний вошёл, первый вышел. Т.е. при получении элемента из стэка выбирается последний помещённый туда элемент. Ещё часто используется очередь - Первый вошёл, первый вышел. Как в нормальной очереди в магазине (в больнице не так, там структура сложнее :-))
Посмотри ещё в нете, про списки очень много инфы, ибо они используются буквально на каждом шагу[/QUOTE]

Классно всё обьяснил,даже ребёнок поймет.Спасибо большое.Думаю посредством твоего кода разберусь со списками)))

[via_82]

Помогите разобраться с реализацией связанных списков на базе массивов

Мне необходимо решить контрольную
Задание:
Структура данных – двусвязная, на базе массива с индексными указателями

Нашел в инете статью: Реализация связанных списков на базе массивов
но в ней пример на Visual Basic 6.0

Не могу найти пример на C++ для понимания данной задачи.

[EricJForster]

ребят подскажите пожалуйста. не могу въехать... как указатель в классе может указывать на другой узел списка если он имеет тип самого этого класса?

[eoln]

Зачем в старую тему залезать? Нужно новую было создать.

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

Что качается "типа" указателя, так это по сути не "тип" указателя, а лишь явное указание на тип объекта, который будет располагаться начиная с этого адреса. Никто не запрещает использовать любой другой тип, т.к. мы всегда попадём на начало этого участка памяти. Правда при работе с содержимым придётся всё-таки использовать приведение типов (если структура объектов разная), а то на начало то мы пришли, а как узнать где настоящий конец не знаем )

[EricJForster]

спасибо большое! Ну ничего страшного, что подняли старую тему. Зато много инфы не потеряется.

[EricJForster]

и еще вопрос есть.
как можно оптимизировать этот код? а то у меня ощущение, что как-то все громоздко получается. Заранее благодарю!!!

#include <iostream>

using namespace std;

class LinkList
{
private:
	struct List
	{
		int value;
		List* next;
	};
	List* head;
	List* curr;
	List* temp;
public:
	LinkList()
	{
		head = NULL;
		temp = NULL;
		curr = NULL;
	}
	void AddList(int data)
	{
		List* nl = new List;
		nl->next = NULL;
		nl->value = data;
		if(head)
		{
			curr = head;
			while(curr->next)
				curr = curr->next;
			curr->next = nl;
		}
		else
			head = nl;
	}

	void DelList(int data)
	{
		List* del = NULL;
		curr = head;
		temp = head;
		if(head->value == data)
		{
			del = head;
			head = head->next;
			curr = head;
			temp = NULL;
			delete del;
		}
		else
		{
			while(curr->next && curr->value != data)
				curr = curr->next;
			del = curr;
			curr = curr->next;
			while(temp->next != del)
				temp = temp->next;
			temp->next = curr;
			delete del;
			temp = NULL;
		}
		
	}

	void Show()
	{
		curr = head;
		while(curr)
		{
			cout << curr->value << endl;
			curr = curr->next;
		}
	}

};