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

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

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

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

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

Ответ
 
Опции темы Поиск в этой теме
Старый 30.06.2011, 23:01   #1
Alexander1205
Пользователь
 
Аватар для Alexander1205
 
Регистрация: 22.01.2011
Сообщений: 78
По умолчанию списки

Доброго всем времени суток!! Есть прога добавления и удаления элементов в списке, из начала, конца. А вот с серединой что-то туговато.. Кто подскажет функцию добавления и удаления из середины списка?

Код:
#include<iostream>
using namespace std;
 
class Node
{
private:
        int data;
public:
        Node *next;
        Node(int x = 0)
        {
                data = x;
                next = NULL;
        }
        int get(){return data;}
};
class List
{
private:
        Node *first,*end;
public:
        List()
        {
                first = NULL;
                end = NULL;
        }
        void Display()
        {
                Node *tmp = first;
                if(tmp==NULL)return;
                do
                {
                cout<<tmp->get()<<" ";
                if(tmp==end)break;
                tmp = tmp->next;
                }while(true);
                cout<<"\n\n";
        }
        void AddToBegin(int value)
        {
                Node *n = new Node(value);//создание нового узла
                if(first == NULL)//проверка,есть ли что-то в списке
                {
                        first = n;
                        end = n;
                }
                else
                {
                        n->next = first;//связывание нового с первыми
                        first = n;
                }
        }
        void AddToEnd(int value)
        {
                Node *n = new Node(value);//создание нового узла
                if(first == NULL)//проверка,есть ли что-то в списке
                {
                        first = n;
                        end = n;
                }
                else
                {
                        end->next = n;//связывание последнего с новым и переопределение последнего
                        end = n;
                }
        }
        void DelFromBegin()//функция удаления из начала списка
        {
                if(first==NULL)return;
                if(first==end)
                {
                        delete first;
                        first = NULL;
                        end = NULL;
                }
                else
                {
                        Node *d = first;
                        first = first->next;
                        d->next=NULL;
                        delete d;
                }
        }
        void DelFromEnd()//функция удаления из конца списка
        {
                if(first==NULL)return;
                if(first==end)
                {
                        delete first;
                        first = NULL;
                        end = NULL;
                }
                else
                {
                        Node *d = first;
                        while(d->next!=end)
                        {
                                d = d->next;
                        }
                        delete end;
                        end = d;
                        end->next = NULL;
                }
        }
};
 
void main()
{
List L;
L.AddToEnd(6);
L.AddToEnd(16);
L.Display();
L.AddToBegin(5);
L.AddToBegin(15);
L.Display();
L.DelFromBegin();
L.Display();
L.DelFromEnd();
L.Display();
}
Alexander1205 вне форума Ответить с цитированием
Старый 30.06.2011, 23:57   #2
Alexander1205
Пользователь
 
Аватар для Alexander1205
 
Регистрация: 22.01.2011
Сообщений: 78
По умолчанию списки

Добавление в середину списка вроде наваял, а вот удаление...

Код:
void AddToMiddle(int value)
	{
		Node *n = new Node(value);//создание нового узла
		if(first == NULL)//проверка,есть ли что-то в списке
		{
			first = n;
			end = n;
		}
		else
		{
			n->next = first;//связывание предыдущего с новым
			first->next;    //связывание нового со следующим
		}
	}
Alexander1205 вне форума Ответить с цитированием
Старый 01.07.2011, 00:31   #3
An1ka
C++,DirectX/OpenGL
Форумчанин
 
Регистрация: 09.01.2011
Сообщений: 422
По умолчанию

Код:
	Node * find ( int value, Node** prev)
	{
		Node *tmp = first; *prev = NULL;
		while ( tmp)
		{
			if ( tmp->data == value ) break;
			*prev = tmp;
			tmp = tmp->next;
		}
	    return tmp;
	}
	 bool find_delete_element( int value)
	{
		Node *prev, *tmp;
		if ( tmp = find ( value, &prev))
		{
			if ( tmp == first)
			{
				first = first->next;
			}
			else if ( tmp == end)
			{
				end = prev;
				end->next = NULL;
			}
			else 
			{
				prev->next = tmp->next;
			}
		    delete tmp;
		    return true;
		}
	  return false;
	}
Поиск и удаление по ключу. Только data надо открытую сделать, чтобы поиск работал.
An1ka вне форума Ответить с цитированием
Старый 01.07.2011, 00:55   #4
Dogmat
Пользователь
 
Регистрация: 12.06.2008
Сообщений: 76
По умолчанию

В качестве позиции используется указатель на узел:
Нужно добавить публичные функции Begin() и End(), возвращающие first и end соответственно.
Код:
Node *Insert(Node *position, int data)  // возвращает указатель на вставленный элемент
{
    if (position == NULL)
        return NULL;

    Node *prev = NULL;
    Node *current = first;

    while (current != position)
    {
        if (current == NULL)
            return NULL;

        prev = current;
        current = current->next;
    }

    Node *newNode = new Node(data);

    if (prev != NULL)
        prev->next = newNode;
    else
        first = newNode;

    newNode->next = current;

    if (newNode->next == NULL)
        end = newNode;

    return newNode;
}

Node *Erase(Node *position) // возвращает указатель на элемент следующий за удаленным
{
    if (position == NULL)
        return NULL;

    Node *prev = NULL;
    Node *current = first;

    while (current != position)
    {
        if (current == NULL)
            return NULL;

        prev = current;
        current = current->next;
    }

    Node *next = current->next;

    if (prev != NULL)
        prev->next = next;
    else
        first = next;

    delete current;

    if (next == NULL)
        end = prev;

    return next;
}

 Node *Begin()
{
    return first;
}

Node *End()
{
    return end;
}
Код:
void main()
{
List L;
L.AddToEnd(6);
L.AddToEnd(16);
L.Display();
L.AddToBegin(5);
L.AddToBegin(15);
L.Display();
L.DelFromBegin();
L.Display();
L.DelFromEnd();
L.Display();

Node *first = L.Begin();

L.Insert(first, 13);
L.Display();

first = L.Begin();

L.Erase(first);
L.Display();

first = L.End();

L.Erase(first);
L.Display();

cin.get();
}
Dogmat вне форума Ответить с цитированием
Ответ


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

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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
списки mansp Visual C++ 3 06.02.2011 14:02
Списки Хорнет Паскаль, Turbo Pascal, PascalABC.NET 0 09.06.2010 09:55
Списки Chief Паскаль, Turbo Pascal, PascalABC.NET 4 03.06.2009 18:29
с++ списки Blizzz Общие вопросы C/C++ 3 04.12.2008 21:19