Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 08.04.2013, 15:26   #1
Nekit9401
Пользователь
 
Аватар для Nekit9401
 
Регистрация: 11.12.2012
Сообщений: 56
По умолчанию Реализовать класс список (Си)

Здравствуйте, мне нужно реализовать класс список, ну допустим пусть он будет односвязным. Так вот, объясните мне, незнающему человеку, как вообще нужно создать этот класс? Я знаю, что там должен быть указатель на следующий элемент и т.д. Но с указателями у меня очень туго, я не могу вообще понять принцип действия указателей и следовательно принцип работы списка. Проблема в том, что когда я смотрю какой нибудь пример списка, то я не могу понять все эти указатели, что они делают, на какой элемент они указывают и как потом происходит передача значения другому элементу, для меня это какая-то непробиваемая стена. И мне нужна помощь в этом, не могли бы вы на самом простом примере односвязного списка объяснить это все, как работают указатели в этом классе и вообще все, желательно поподробнее, что бы даже до меня дошло) Вообще классы только недавно начал изучать, но общую суть их понимаю, а вот со списком проблемы)
Nekit9401 вне форума Ответить с цитированием
Старый 08.04.2013, 15:50   #2
Abstraction
Старожил
 
Аватар для Abstraction
 
Регистрация: 25.10.2011
Сообщений: 3,178
По умолчанию

Возможно, Вам будет интересна вот эта тема. Там обсуждение чуть других вопросов, но можно зафиксировать её как базис.

Так вот, список (как обсуждалось в той теме) базируется на том, что указатель на область памяти может занимать меньше места, чем сам блок памяти. Поэтому возможна такая конструкция:
Код:
Адрес 1: ("мама", [указатель на адрес 2])

Адрес 2: ("мыла", [указатель на адрес 3]) 

Адрес 3: ("раму", [указатель "в никуда"])
По каждому из трёх адресов находятся однотипные структуры: "данные"+"адрес". Собственно, класс элемента списка в смысле содержащихся в нём данных имеет такой же вид:
Код:
class ListNode{
private:
  Data m_data; //данные
  ListNode* m_next; //адрес
public:
};
Остальное - методы работы с этими элементами. Скажем, мы хотим убрать элемент, следующий за текущим, и нам известно, что этот элемент был создан с помощью ключевого слова new. Тогда:
Код:
class ListNode{
private:
//...
public:
  void DeleteNextNode(void);
};

void ListNode::DeleteNextNode(void){
  //Если следующего элемента нет - делать ничего не надо
  if(m_next == NULL) return;
  //Иначе, нам нужно "взять в руки" следующий за следующим (это проще нарисовать):
  ListNode* nextNext = m_next->m_next;
  //Затем удаляем "пациента":
  delete m_next;
  //Затем подсоединяем к нашему элементу "взятый":
  m_next = nextNext;
}
Abstraction вне форума Ответить с цитированием
Старый 08.04.2013, 17:59   #3
Nekit9401
Пользователь
 
Аватар для Nekit9401
 
Регистрация: 11.12.2012
Сообщений: 56
По умолчанию

Спасибо, вроде понял, вот написал свой список с двумя функциями добавления элемента в начало и конец списка, как вам такой вариант реализации списка?)

Код:
#include <stdio.h>

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

class ListNode
{
	public:
		Node* first;
		ListNode();
		ListNode(int);
		void AddNodeFront(int);
		void AddNodeBack(int);
		void print();
};

ListNode::ListNode()
{
	first=NULL;
}

ListNode::ListNode(int x)
{
	first=new Node;
	first->data=x;
	first->next=NULL;
}

void ListNode::AddNodeFront(int x)
{
	Node* q=first;
	first=new Node;
	first->data=x;
	first->next=q;
}

void ListNode::AddNodeBack(int x)
{
	if(first==NULL)
	{
		first=new Node;
		first->data=x;
		first->next=NULL;
	}
	else 
	{
		Node* z=first;
		for(;z->next!=NULL;z=z->next)
		{}
		z->next=new Node;
		z->next->data=x;
		z->next->next=NULL;
	}
}

void ListNode::print()
{
	for(Node* z=first;z!=NULL;z=z->next)
		printf("%d",z->data);
		printf("\n");
}

void main()
{
	ListNode s;
	s.AddNodeBack(8);
	s.AddNodeFront(5);
	s.AddNodeBack(6);
	s.print();
}

Последний раз редактировалось Nekit9401; 08.04.2013 в 18:01.
Nekit9401 вне форума Ответить с цитированием
Старый 08.04.2013, 18:35   #4
Abstraction
Старожил
 
Аватар для Abstraction
 
Регистрация: 25.10.2011
Сообщений: 3,178
По умолчанию

1) Данные класса настоятельно рекомендуется уводить в private-секцию, если Вы не находите веских причин для иного.
2) То, что Вы назвали ListNode - это уже сам List, в общем-то.

Дальше начинаются некоторые тонкие вещи.
3) Всякому new обязан соответствовать delete. В нашем случае, для этого лучше всего подходит деструктор класса ListNode:
Код:
class ListNode{
//...
public:
~ListNode(); //Ничего не возвращает, ничего не принимает - это специальная синтаксическая форма
};

ListNode::~ListNode(){
  //Сделать delete всем элементам списка.
  //Имейте в виду: удалённый элемент нельзя использовать. Если нужна информация
  //в нём (указатель на следующий элемент, например), её следует скопировать перед удалением.
}
4) Далее, существуют такие вещи, как конструктор копирования и оператор присваивания. Проблема с ними в том, что, если Вы их не создаёте, компилятор их создаёт за Вас (реализуя как простое побитовое копирование). И в случае, когда класс содержит указатели, такая логика фатальна. Способ раз - реализовать их самостоятельно. Способ два - поместить объявления конструктора копирования и оператора присваивания в закрытую часть класса и не реализовывать: в этом случае попытка скопировать ListNode породит ошибку компиляции, вместо здоровой логической бомбы на стадии выполнения:
Код:
class ListNode{
//...
private:
  ListNode(const ListNode& l); //Прототип конструктора копирования
  const ListNode& operator=(const ListNode& l); //Прототип оператора присваивания
};
5) Методы, не изменяющие состояния объекта, следует объявлять как константные:
Код:
class ListNode
{
//...
public:
	void print(void) const; //Указание того, что этот метод не меняет this
};

void ListNode::print(void) const //Обратите внимание, сюда тоже надо ставить const
{
  /*...*/
}
Среди прочего, это позволяет компилятору отследить, если в результате Вашей ошибки Вы измените в таком методе состояние объекта.
6) При именовании методов лучше бы описывать то, что они делают, а не то, как они это делают: не AddNodeFront, а AddToFront.

А так нормально получилось.
Abstraction вне форума Ответить с цитированием
Старый 08.04.2013, 21:20   #5
Nekit9401
Пользователь
 
Аватар для Nekit9401
 
Регистрация: 11.12.2012
Сообщений: 56
По умолчанию

Спасибо, учту)
Nekit9401 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Реализовать класс 'Распсисание' на java. Alexxl2009 Помощь студентам 0 30.05.2011 17:54
Не получается реализовать глобальный класс RIO Visual C++ 0 08.05.2011 18:12
реализовать контейнерный класс за $$$ B1GBEN Фриланс 2 14.12.2009 00:46
реализовать контейнерный класс B1GBEN Помощь студентам 0 13.12.2009 14:21