Структуры данных. Список статей

Здравствуйте. На этой странице будут собраны ссылки на статьи по структурам данных для более удобного чтения.

  • Введение в динамические структуры данных #1

  • Связные списки #2

  • Стек #3

  • Очередь #4

  • Двусвязный список #5

  • Читать дальше

    Очередь #4

    Доброго всем вечера.

    В этой статья, как и обещал, я опишу что есть из себя очередь, ей структуру и ее реализацию на С++ в конце статьи. Вот предыдущая статья о стеке.

    По сути, очередь почти не отличается от стека — это все тот же односвязный список. Все его отличие заключается в способе добавления и удаления элемента.

    Основной принцип очереди:»Первый пришёл — первый вышел» (или FIFO, First In — First Out). Проще всего себе представить очередь очередью (извините за тавтологию) в магазин:

    Очередь, связный список

    То есть, тот, кто пришел первым в магазин и уйдет из него первым (правда просто? 🙂 ). В этом и заключается смысл очереди.

    Теперь поговорим о его представлении в памяти. Элементы очереди добавляются всегда! справа от хвоста (самый крайний правый элемент), а это значит, что каждый раз создается новый хвост.

    А вот выталкивается (извлекается из списка, помним про pop?) элемент  всегда! с головы (элемент который находится «слева»). Наглядная структура очереди:

    queue (2)

    Вот и все. Теперь перейдем к реализации очереди средствами С++.

    Код класса очереди содержит те же самые методы, что и класс стека: pop, push и peek. Однако, было добавлено одно поле tail (хвост). Это поле хранит адрес хвоста очереди. А вот и сам код:

    #include<iostream> using namespace std; class queue //Класс очереди { private: struct queue_ob// Структура для хранения элементов очереди { int value;//Поле для хранения значения элемента очереди queue_ob *addr; // Поле для хранения слеющего элемента }; queue_ob *head; // указатель, хранящий адресс головы очереди queue_ob *tail; // Указатель хранящий адрес хвоста int size; //Текущий размер очереди public: queue(int x)// Конструктор класса //В параметр передается голова очереди { head=new(queue_ob); //Выделяем память под элемент tail=head; // При создании очереди хвост и голова являются одним и тем же элементом head->value=x; // Записываем значение head->addr=0; // Адрес ноль, так как следующего элемента пока нет size=1; // После выделения памяти и заполянения полей структуры очередь стала иметь размер 1 } int stack_size()//Функция возвращает размер очереди(кол-во элеменетов) { return size; } void push(int value)// Добавляет(вталкивает) элемент в очередь { size++;// Кол-во элементов очереди увеличивается queue_ob *temp=new(queue_ob); // Выделяем память под новый хвост очереди temp->addr=0; // Записываем в поле адреса нового хвоста ноль, так как за ничего нету temp->value=value; //Заполняем поле значения нового хвоста tail->addr=temp; // Записываем в поле адреса старого хвоста адрес нового хвоста tail=temp; //Записываем в указель хвоста адрес действительного хвоста } void pop(int *ret)//Удаляет элемент(выталкивает) и возвращает его // По адресу, хранящемся в ret, передается значение удаляемой головы { if(size == 0) { cout<<"Очередь пуста - удалять нечего!"<<endl; return; } queue_ob *temp=head; // записываем адрес головы *ret=head->value; // записываем значени головы head=head->addr; // изменяем адрес головы delete temp; // удаляем старую голову size--; // уменьшаем размер } void peek(int *ret)//Выгружает значение по адресу, передаваемому в парметре { if(size == 0) // Если очередь пуста(size == 0), то ничего не выгружает { cout<<"Очередь пуста!"<<endl; return; } *ret=head->value;// Выгружаем значение головы } };// Конец класса очереди Читать дальше

    Стек #3

    Здравствуйте, уважаемые читатели.

    Две предыдущие статьи по структуре данных (раз и два) несли общие знания без конкретизации и реализации. А в этой статье и следующих будут рассмотрены динамически структуры по отдельности и с реализацией.

    Для реализации структур данных я буду использовать язык программирования С++. Мое решение было обусловлено, тем, что  этот язык является очень популярным и имеет широкие возможности по работе с памятью.

    Теперь приступим к теме статьи.

    Что такое стек и с чем его едят?

    Как я писал в предыдущих статьях, стек является односвязным списком. Его особенность заключается в реализации. Но сразу к коду переходить не будем и поговорим о стеке «на пальцах».

    Стек можно представить себе как стакан с монетками, лежащими столбиком.

    Т.е. мы кладем монетку на дно, потом еще одну сверху и так далее. И, чтоб достать монетку, которую мы опустили в стакан первой, нужно вытащить все предыдущие. В этом и заключается принцип стека и звучит он так: «Последним пришёл — первым вышел». Великие мира сего даже придумали специальную аббревиатуру  LIFO (англ. last in — first out).

    Теперь монетки переведем в информационный эквивалент.

    Имеем мы значит односвязный список. Добавили туда первый элемент (хвост списка), далее добавляем все новые элементы только слева от хвоста, т.е. каждый раз создаем новую голову. А удаляем наоборот —  с головы до хвоста. Таким образом, элемент, который последний попал в стек, выйдет из него первым (помним про LIFO). Вот небольшая картинка для наглядности:

    С++ программирование стек

    Все, как видите, очень просто. Для работы со стеком принято реализовывать три основные функции:

    1. Push — втолкнуть элемент.

    2. Pop — вытолкнуть элемент.

    3. Peek — считать вершину (голову) стека.

    Если вы решите создать собственную реализацию стека, то желательно использовать эти названия для функций, так, при чтении вашего кода, любой человек поймет, что делает данная функция/метод, даже без комментариев.

    Далее прилагаю код реализации (исходник можно будет скачать в конце статьи):

    #include<iostream> using namespace std; class stack//Класс стека { private: struct stack_ob// Структура для хранения элементов стека { int value;//Поле для хранения значения элемента стека stack_ob *addr; // Поле для хранения слеющего элемента }; stack_ob *head; // указатель, хранящий адресс головы стека int size; //Текущий размер стека public: stack(int x)// Конструктор класса //В параметр передается хвост стека { head=new(stack_ob); //Выделяем память под элемент head->value=x; // ЗАписываем значение head->addr=0; // Адрес ноль, так как это хвост стека - элемент добавленный первым size=1; // После выделения памяти и заполянения полей структуры стек стал иметь размер 1 } int stack_size()//Функция возвращает размер стека(кол-во элеменетов) { return size; } void push(int value)// Добавляет(вталкивает) элемент в стек { size++;// Кол-во элементов стека увеличивается stack_ob *temp=head; // Записываем адрес старой головы(вершины) стека head=new(stack_ob); //Выделяем память под новый элемент head->addr=temp; // Записываем в поле адреса головы адрес старой головы head->value=value; //Записываем значение новой головы } void pop(int *ret)//Удаляет элемент(выталкивает) и возвращает его // По адресу, хранящемся в ret, передается значение удаляемой головы { if(size == 0) { cout<<"Стек пуст - удалять нечего!"<<endl; return; } stack_ob *temp=head; // записываем адрес головы *ret=head->value; // записываем значени головы head=head->addr; // изменяем адрес головы delete temp; // удаляем старую голову size--; // уменьшаем размер } void peek(int *ret)//Выгружает значение по адресу, передаваемому в парметре { if(size == 0) // Если стек пуст(size == 0), то ничего не выгружает { cout<<"Стек пуст!"<<endl; return; } *ret=head->value;// Выгружаем значение головы } };// Конец класса стека Читать дальше

    Связные списки #2

    Всем доброго времени суток.

    Этим прекрасным апрельским вечером я хочу с вами поговорить о одной из разновидностей динамических структур( как раз на них я остановился в прошлой статье), а именно о связных списках. 

    Из название легко видно ( привет матану:) ), что сабж представляет из себя список ( набор каких-то отдельных элементов) и все эти элементы как-то между собой связаны (а теперь привет уже Кэпу). Читать дальше