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

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

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

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

  • Стек #3

  • Очередь #4

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

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

    Указатели? Это просто! С++ #2

    Доброго дня всем.

    Итак, сейчас я продолжу рассказ о указателях, который начал вот в этой статье.

    Допустим, мы объявили целочисленную переменную и присвоили ей значение 10:

    int a=10;

    В результате данных манипуляций процессор выделил ячейку в памяти размером 4 байта и присвоил ей некий адрес. И обратится к ней мы можем двумя способами:

    1. По адресу в памяти — прямая адресация.
    2. По идентификатору (имени переменной) — косвенная адресация.

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

    В языках высокого уровня (языки, которые далеки от машинного кода) повсеместно используется косвенная адресация — это намного удобнее.

    Все, теперь поговорим, собственно, о указателях (не может быть!).

    Указатели — это обычные переменные, которые созданы для хранения адресов других переменных. Для них точно так же выделяется ячейка памяти (в неё помещается какой-либо адрес вместо значения, как в случае обычных переменных) и этой ячейке присваивается шестнадцатеричный адрес, как и всем другим переменным . Стоит отметить, что размер этой ячейки зависит от архитектуру ОС, т.е., если система 32-х разрядная, то для  того, чтобы в указатель могли поместится любые адреса, нужно 4 байта (4 байт = 32 бит), а в случае 64-х разрядной системы потребуется уже 8 байт. Такие вот пирожки с котятами.

    Для объявления указателя в С++ используется оператор  «звездочка» — «*».  И делается это вот таким макаром:

    int *pointer;

    В результате мы получили указатель на целочисленную переменную. Тип указателя очень важен! Если мы объявили указатель как целочисленный, то мы можем помещать в него адреса только переменных типа int. Т.е., если объявили указатель типа float (тип с плавающей точкой), то и адреса туда можно помещать только переменных типа float. «Зачем это нужно? Ведь все указатели и так будут занимать одно и то же количество памяти» — спросите вы. На ваш логичный (и очень правильный!) вопрос я отвечу чуть позже (там будет все просто, как и всегда :)).

    Мы объявили указатель, но он ни на что не указывает! Как же быть?

    А вот для этого, есть еще один оператор — «&» (амперса́нд). Он называется оператором взятия адреса (еще он служит для создания ссылок, но это тема для отдельной статьи). Далее пример:

    int variable=10; //Объявили обычную переменную и присвоили ей значение
    int *pointer;   // Объявили указатель типа int
    pointer=&variable; // (&variable) - это мы взяли адрес переменной variable
                       //и записали его в указатель

    Теперь в указателе хранится адрес переменной variable. И если мы выведем значение указателя вот таким образом:

    cout<<pointer<<endl;

    То получим что-то такое:

    addr

    0032F9DC — это адрес переменной variable в оперативной памяти.

    Теперь очень важный момент (сосредоточиться!). «*» служит не только для объявления указателя, но и является оператором для обращения по адресу хранящемуся в указателе (звездочка работает в этом ключе только с указателями).

    Например, cout<<*pointer; равносильно cout<<variable;

    Для наглядности скомпилируем этот код:

    system("chcp 1251"); int variable=10; int *pointer; pointer=&variable; cout<<"Обращаем к variable через указатель : "<<*pointer<<endl; cout<<"Обращаемся непосредственно к variable : "<<variable<<endl; system("pause"); Читать дальше

    Указатели? Это просто! С++ #1

    Так. С вами снова Алексей. Вы думаете, что я буду рассказывать о бинарных деревьях (обещал в прошлой статье)? А вот и нет! Что все структуры да структуры — скучно…

    Сегодня я вам расскажу, не побоюсь это слова, самой интересной вещи в С++ — о указателях. Указатели являются краеугольным камнем С++, без них невозможно написание ни одной серьезной программы (даже злосчастные списки реализованы с помощью указателей). Но, к сожалению, при изучении указателей начинающих берет оторопь. И зря! Указатели — это просто! Читать дальше

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

    Доброй ночи всем.

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

    Двусвязный список — это динамическая структура данных, а именно, он является разновидностью связных списков. Его «двусвязность» заключается в наличии двух ячеек для хранения адресов. В одной хранится адрес следующего элемента, а в другой — предыдущего (привет Кэп 🙂 ). В этом и все отличие от односвязного списка.

    Крайний слева элемент так же называется головой, а крайний справа — хвостом.

    Вот небольшая иллюстрация двусвязного списка:

    twolist

    Здесь А3 — голова, А1 — хвост. Еще бывают случаи, когда А1 и А3 связаны — такой список называется кольцевым.

    circular

    Преимущества двусвязного списка перед односвязным заключается в более удобной навигации (перемещении) по списку, при этом элемент двусвязного списка занимает больше памяти, что является минусом (в наши времена этот минус незначителен — вон недавно вышла планка оперативки на 128 ГБ). Наиболее серьезным минусом сабжа является сложная реализация вставки и удаления элементов — это обусловлено тем, что приходится изменять постоянно две ячейки адреса у элементов списка.

    Но не так страшен черт, как его малюют. Его реализация на С++ вполне понятна и не должна вызывать недоумения (я надеюсь). Вот, собственно, и она:

    // Реализация двусвязного списка (С)Swamp_Dok 09.04.2014 #include<iostream> using namespace std; class two_list // Объявляем класс двусвязного списка { private: struct list // Создаем структуру для хранения элемента списка //Теперь ячеек адреса две { int value; // Тут значение элемента стека list *back; // Указатель на элемет справа в сторону хвоста) list *next; //На элемент слева }; list *head; // Указатель на голову списка int size; // Кол-во элементов стека public: two_list(int value) //Конструктор класса { head=new(list); // Выделяем память под первый элемент head->value=value; // Записываем значение head->next=0; //Нули, так как они никуда не ссылаются. head->back=0; size=1; // Элемент появился, значит ++ 🙂 } int list_size() // Возвращает количество элементов списка { return size; } void list_add(int value, int k) //Добавляет value на k-е место //Элементы списка считаются с нуля // При k=0 вставится новая голова //При k=size вставится новый хвост { if( k>size || k<0) //Проверка на позицию { cout<<"Такого элемента нет!"; return;//Завершаем ф-ю } size++;// Увеличиваем количество list *temp=head; //Записываем адрес головы if(k == 0) // Добавляется новая голова { head=new(list); // Память для новой головы temp->next=head; // Записываем в next старой головы head->back=temp; // Записываем в back новой головы адрес старой head->next=0; // Ноль, так как слева от головы ничего нету head->value=value; // Записываем значение в новую голову return; //Завершаем функцию и ничего не возвращаем } for(int i=1; i<k ; i++) temp=temp->back; // Находим и записываем в temp адрес элемента с номером (k-1) //temp->back -- элемент, стоящий справа от вставляемого //temp->next -- элемент, стоящий слева от вставляемого list *buff=new(list); // Выделяем память и записываем адрес выделенной памяти в buf buff->next=temp; // Записываем в next нового элемента адрес элемента, стоящего слева. buff->back=temp->back; // Записываем в back нового элемента адрес элемента, стоящего справа. if(temp->back!= 0 ) // Проверяем на хвостатость temp { temp->back->next=buff;//Записывает в next элемента, стоящего справа от нового, адрес нового } temp->back=buff; // Записываем в элемент, стоящий слева от нового, адрес добавленного элемента buff->value=value; // записываем значение в новый элемент } void list_delete(int k, int *ret) //Вытокнуть k-й элемент в ret //Если k=0, то выталкивается голова { if( k>=size || k<0) // Проверка { cout<<"Такого элемента нет!"; return; //Завершаем ф-ю } size--; // Уменьшаем кол-во элементов list *temp=head; //Записываем адрес головы if(k == 0) //Удаляется голова { *ret= head->value; // Записываем значение головы head=head->back; //Изменяем адрес головы delete temp; // Удаляем старую голову head->next=0; // Ноль, так слева от головы ничего нету return; } for(int i=1; i<=k ; i++) temp=temp->back; // Находим и записываем в temp адрес элемента с номером k //temp->back -- элемент, стоящий справа от удаляемого //temp->next -- элемент, стоящий слева от удаляемого *ret=temp->value; if(temp->back!=0) temp->back->next=temp->next; // Проверяем, является ли удаляемый элемент хвостом temp->next->back=temp->back; delete temp; } void list_read_elem(int k,int *ret) // Cчитываем k-й и записываем в ret { if( k>=size || k<0) { cout<<"Такого элемента нет!"; return;//Завершаем ф-ю } list *temp=head; for(int i=0; i<k ; i++) temp=temp->back; // Находим и записываем в temp адрес элемента с номером k *ret=temp->value;//Записываем значение элемента под номером k } };// Конец класса Читать дальше

    Очередь #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;// Выгружаем значение головы } };// Конец класса очереди Читать дальше