Стеки являются структурой данных, в которой обработка данных (ввод и вывод) осуществляется по принципу LIFO– Last In First Out – последний пришел - первый ушел.

СТРУКТУРЫ ДАННЫХ

DATA STRUCTURES

СТЕКИ

Стеки являются структурой данных, в которой обработка данных (ввод и вывод) осуществляется по принципу LIFO – Last In First Out – последний пришел - первый ушел.

Функциональное описание

Будем предполагать, что при организации стека имеется ограничение на его длину. Основные операции со стеком: Создать, Втолкнуть, Вытолкнуть, Проверить «на пустоту», Проверить на переполнение.

Создать

Вход: -

Выход: Стек

Проверить «на пустоту»

Вход: Стек, Empty

Выход: Стек, Empty присвоено 0 или 1

Проверить на переполнение

Вход: Стек, Full

Выход: Стек, Full присвоено 0 или 1

Втолкнуть

Вход: Стек, X

Выход: в Стек добавлен элемент X если он не переполнен,

иначе ОШИБКА

Вытолкнуть

Вход: Стек, X

Выход: из Стека удален последний элемент если стек не пуст,

иначе ОШИБКА

Логическое представление (алгоритм)

createStack(){

Объявляем массив Stack

Возвращаем Stack

}

stackEmpty(){

Определяем длину l массива

ЕСЛИ l=0

Empty=1

ИНАЧЕ

Empty=0

КОНЕЦ_ЕСЛИ

}

stackFull(){

Определяем длину l массива

ЕСЛИ l=max

Full=1

ИНАЧЕ

Full=0

КОНЕЦ_ЕСЛИ

}

Физическое представление (Код)

//функции для работы со стеком

function createStack(){

var st=new Array();

return st;

}

function pushStack(){

var val=prompt("Введи число:");

Stack1.push(val);

}

function popStack(){

Stack1.pop();

}

// Основная программа

var Stack1=createStack();

pushStack();

alert(Stack1.length);

popStack();

alert(Stack1.length);

// РАЗДЕЛЕНИЕ КУЧИ

// НА ДВЕ ПРИМЕРНР РАВНОГО ВЕСА

//*******************************

// СОЗДАНИЕ КУЧИ

var heap=new Array(10,3,2,15,5,7,11);

// НОВЫЕ КУЧИ И ИХ ВЕС

var heap1=new Array();

var heap2=new Array();

var weith1=0;

var weith2=0;

// СОРТИРУЕМ МАССИВ ПО УБЫВАНИЮ

function compare(num1,num2){

return num2-num1;

}

heap.sort(compare);

alert(heap);

heap.reverse();

alert(heap);

// ПЕРЕБИРАЕМ КУЧУ

while(heap.length>0){

var stone=heap.pop(); //БЕРЕМ КАМЕНЬ,

if(weith1<=weith2){ // КЛАДЕМ В ПЕРВУЮ

heap1.push(stone);

weith1=weith1+stone;

//alert(heap1);

}else{ // КЛАДЕМ ВО ВТОРУЮ

heap2.push(stone);

weith2=weith2+stone;

//alert(heap2);

}

}

alert(heap1+" "+heap2);

Стеки. Упражнения

В книге [2] всего 16 глав, из них гл. 3-8 посвящены алгоритмам и структурам данных, гл. 9 - параллельным вычислениям, гл. 10-11 – ООП и гл. 12 – базам данных. Это большая часть книги. Структуры данных и алгоритмы занимают существенную часть книги.

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

«Почему именно связные списки?

Интервьюеров привлекает простота вопросов относящихся к связным спискам, так как именно она позволяет за час собеседования рассмотреть две или даже три задачи…(стр.59»

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

Стеки. Задания для самостоятельного решения.

Пусть S –это стек целых чисел, а x - целочисленная переменнаяС использованием основных функций работы со стеками, напишите программы, выполняющие перечисленные ниже задачи Вы можете объявлять дополнительные переменные и использовать в своих программах второй стек, если это потребуется.

(a) Присвойте x значение первого элемента стека, не изменив стек. Если стек пуст, присвойте x значение 1000.

(b) Присвойте x значение третьего сверху элемента. Если в стеке меньше трех элементов, то x присваивается значение 1000

(c) Присвойте x значение последнего элемента или 1000.

(d) Задав x, удалите из стека все вхождения этого значения.

(e) Присвойте x значение минимального элемента стека.

// получение значения первого поступившего в стек

// элемента, который выйдет последним

var S = new Array();

var S1 = new Array();

var x;

S.push(10);

S.push(7);

S.push(13);

S.push(22);

alert(S);

if(S.length==0){

x=1000;

}else{

var l = S.length

for(var i=0;i<l;i++){

x = S.pop();// в x сожраняется последнее значение

S1.push(x);

//alert(x);

}

//S.push(x);

}

alert(x);

for(i=0;i<l;i++){

var y = S1.pop();

S.push(y);

}

alert(S);

ОЧЕРЕДИ

Очереди являются структурой данных, в которой обработка данных (ввод и вывод) осуществляется по принципу FIFO – First In First Out – первый пришел - первый ушел.

Функциональное описание (постановка задачи)

Будем предполагать, что при организации очереда имеется ограничение на её длину. Основные операции с очередью: Создать, Поставить (в очередь), Обслужить, Проверить «на пустоту», Проверить на переполнение.

Создать

Вход: -

Выход: Queue - очередь

Проверить «на пустоту»

Вход: Queueк, Empty

Выход: Queue, Empty присвоено 0 или 1

Проверить на переполнение

Вход: Queue, Full

Выход: Queue, Full присвоено 0 или 1

Поставить (в очередь)

Вход: Queue, X

Выход: в Queue добавлен элемент X если очередь не переполнена,

иначе ОШИБКА

Обслужить

Вход: Queue, X

Выход: из Queue удален последний элемент, если очередь не пуста,

иначе ОШИБКА

Логическое представление (алгоритм)

createQueue(){

Объявляем массив Queue

Возвращаем Queue

КОНЕЦ_функции

queueEmpty(){

Определяем длину l массива

ЕСЛИ l=0

Empty=1

ИНАЧЕ

Empty=0

КОНЕЦ_ЕСЛИ

КОНЕЦ_функции

queueFull(){

Определяем длину l массива

ЕСЛИ l=max

Full=1

ИНАЧЕ

Full=0

КОНЕЦ_ЕСЛИ

КОНЕЦ_функции

append()

queueFull()

ЕСЛИ(Full=1)

ОШИБКА

ИНАЧЕ

l=длина массива Queue

Queue[l]=X

КОНЕЦ_ЕСЛИ

КОНЕЦ_функции

serve()

queueEmpty()

ЕСЛИ(Empty=1)

ОШИБКА

ИНАЧЕ

X=Queue[0]

l=длина массива Queue

Сдвигаем все элементы начиная со второго

на одну позицию вверх

Последний элемент надо сделать неопределенным

КОНЕЦ_ЕСЛИ

КОНЕЦ_функции

Физическая реализация (код)

//функции для работы с очередью

var qu=new Array();

var max=10;

function append(){

var l=qu.length;

if(l==max){

alert("Очередь ПОДНА");

}lse{

var val=prompt("Введи число:");

qu[l]=val;

}

}

function serve(){

var l=qu.length;

if(l==0){

alert("Очередь ПОДНА");

}lse{

X=qu[0];

for(var i=0;i<l-1;i++){

qu[i]=qu[i+1];

}

qu.length=l-1;

}

}

Очереди.

Задачи для самостоятельного решения

1. Напишите функцию Traverse(), изменяющую порядок в очереди на обратный.

2. Создайте класс MyQueue, который реализует очередь с использованием двух стеков.

3. В приюте для животных есть только собаки и кошки, а работа осуществляется в порядке очереди. Люди должны каждый раз должны забирать «самое старое» (по времени пребывания в питомнике) животное, но могут выбрать кошку или собаку (животное в любом случае будет «самым старым»). Нельзя выбрать любое понравившееся животное. Создайте структуру данных, обслуживающую эту систему и реализующую операции enqueue, dequeueAny, dequeueDog и dequeueCat.

(ЛИНЕЙНЫЕ) СПИСКИ

Линеный список – это такая структура данных, в которой данные хранятся в последовательном порядке, так что обращение к данным осуществляется по номеру позиции.

Массивы являются примером линейных списков. Точнее, говорят, чтосплошным представлением линейного списка является массив.

Основные операции с линейными списками – это добавление и удаление элементов, причем эти операции требуют указания позиции, после которой элемент добавляется или с которой он удаляется.

Физическое представление (Код)

var qu=new Array(); LIST

// ДОБАВИТЬ

function insertEl(){

var l=qu.length;

var p=1*prompt("Введи позицию <="+l);

if(p>l){

alert("ОШИБКА");

}else {

var val=prompt("Введи элемент списка");

for(var j=l-1;j>=p;j--){

qu[j+1]=qu[j];

}

qu[p]=val;

}

}

function removeEl(){

var l=qu.length;

var p=1*prompt("Введи позицию <"+l);

if(p>=l){

alert("ОШИБКА");

}else{

for(var i=p;i<l-1;i++){

qu[i]=qu[i+1];

}

qu.length=l-1;

}

}

// ПОКАЗАТЬ

function display(){

alert(qu);

}

(ЛИНЕЙНЫЕ) СПИСКИ

Линеный список – это такая структура данных, в которой данные хранятся в последовательном порядке, так что обращение к данным осуществляется по номеру позиции.

Массивы являются примером линейных списков. Точнее, говорят, чтосплошным представлением линейного списка является массив.

Основные операции с линейными списками – это добавление и удаление элементов, причем эти операции требуют указания позиции, после которой элемент добавляется или с которой он удаляется.

Функциональное описание

Основные операции со списком: Создать список, Создать узел, Добавить узел, Удалить узел.

Создать узел/список.

Вход: -

Выход: Узел/Узел Head(начало списка)

Добавить

Вход: Список (Head), Узел, после которого надо добавить

новый узел, Новый узел.

Выход: в Список с добавлен новый узел

Удалить узел

Вход: Список (Head), Узел, который надо удалить.

Выход: из Списка удален указанный узел.

Логическое представление (алгоритм)

Функция Добавить (insert)

Просматривая список, найти элемент, после которого

надо вставить.

Изменить указатели в найденном и новом узлах так,

чтобы новый узел был после найденного.

КОНЕЦ_ Добавить

Функция Удалить (remove)

Просматривая список, найти элемент, который надо удалить и

предыдущий узел.

надо вставить.

Изменить указатель предыдущего узла так, чтобы он показывал

на следующий за удаляемым узел.

КОНЕЦ_ Удалить

Физическое представление (Код)

//LIST

//*******************************************************

var qu=new Array(); LIST

//alert(qu); LIST

LIST

// ДОБАВИТЬ

function insertEl(){

var l=qu.length;

var p=1*prompt("Введи позицию <="+l);

alert(l+" "+p);

if(p>l){

alert("ОШИБКА");

}else {

var val=prompt("Введи элемент списка");

for(var j=l-1;j>=p;j--){

qu[j+1]=qu[j];

}

// alert(val);

qu[p]=val;

}

//alert(qu);

}

function removeEl(){

var l=qu.length;

var p=1*prompt("Введи позицию <"+l);

alert(l+" "+p);

if(p>=l){

alert("ОШИБКА");

}else{

for(var i=p;i<l-1;i++){

qu[i]=qu[i+1];

}

qu.length=l-1;

//alert(qu);

}

}

// ПОКАЗАТЬ

function display(){

alert(qu);

}

СВЯЗНЫЕ СПИСКИ

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

Объекты называются узлами. Каждый узел соответствует одному элементу списка и имеет указатель на узел, соответствующий следующему элементу списка (или соответствует концу списка

header

bacon

milk

bread

eggs

null

Head

Node1

Node2

Node3

Node4

cookies

NewNode

Рис 1. Связный список

Новый элемент можно добавить после любого элемента списка, а также как первый элемент, после узла Head.

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

header

bacon

milk

bread

eggs

cookies

null

Рис 2. Добавление узла “ cookie s” в связный список

Однако при удалении узла, изменяется ссылка предыдущего узла. Т.е. для удаления узла надо иметь доступ к предыдущему узлу.

header

bacon

milk

bread

eggs

cookies

null

Рис 3. Удаление узла ” bread ” из связного списка

Функциональное описание

Основные операции со стеком: Создать список, Создать узел, Добавить узел, Удалить узел.

Создать узел/список.

Вход: -

Выход: Узел/Узел Head(начало списка)

Добавить

Вход: Список (Head), Узел, после которого надо добавить

новый узел, Новый узел.

Выход: в Список с добавлен новый узел

Удалить узел

Вход: Список (Head), Узел, который надо удалить.

Выход: из Списка удален указанный узел.

Логическое представление (алгоритм)

Функция Добавить (insert)

Просматривая список, найти элемент, после которого

надо вставить.

Изменить указатели в найденном и новом узлах так,

чтобы новый узел был после найденного.

КОНЕЦ_ Добавить

Функция Удалить (remove)

Просматривая список, найти элемент, который надо удалить и

предыдущий узел.

надо вставить.

Изменить указатель предыдущего узла так, чтобы он показывал

на следующий за удаляемым узел.

КОНЕЦ_ Удалить

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

Физическое представление (Код)

// LINKED LIST

//*******************************************************

var findedNode; //найденный узел, который радо удалить

// или после которого надо вставить новый узел

var prevNode; // предыдущий узел

// создание узла

//***********************

function Node(element){

this.element=element;

this.next=null;

}

var head= new Node("header");

var Node1= new Node("Ann");

var Node2= new Node("Mary");

var Node3= new Node("Michel");

// создание списка вручную"

head.next=Node1;

Node1.next= Node2;

Node2.next= Node3;

// ПоОКАЗАТЬ СПИСОК

function DisplayList(){

if(head.next==null){

alert("СПИСОК ПУСТ!");

}else{

var curr=head; // текуший элемент

while(!(curr.next==null)){

curr=curr.next;

alert("текущий элемент: "+curr.element);

}

}

}

// НАЙТИ УЗЕЛ С ЗАДАННЫМ ЭЛЕМЕНТОМ

function find(elem){

var curr=head; // текуший элемент

var prev=null;

while(curr.element!==elem){

prev=curr;

curr=curr.next;

// alert("текущий элемент: "+curr.element);

}

//alert(curr.element);

//alert(prev.element);

findedNode=curr;

prevNode=prev;

}

function removeFinded(){

prevNode.next=findedNode.next;

findedNode.next=null;

}

function insertNew(item){

item.next=findedNode.next;

findedNode.next=item;

}

//find("Michel");

//removeFinded();

//DisplayList();

find("Ann");

newNode=new Node("JOAN");

insertNew(newNode);

DisplayList();

ЗАДАЧИ

для самостоятельного решения

1. Для односвязного списка разработать программу, которая выводит значение узла m с начала списка.

2. Для односвязного списка нужно разработать эффективный (с точки зрения как времени, так и пространства) алгоритм поиска элемента с номером m, если считать с конца. Реализуйте этот алгоритм с учетом сопутствующих условий ошибок. Переменная m определяется таким образом, что при её равенстве нулю возвращается последний элемент списка.

3. Напишите код, удаляющий дубликаты из неотсортированного связного списка.

Дополнительно:

Как вы будете решать задачу, если запрещается использовать временный буфер?

4. Реализуйте алгоритм, удаляющий узел из середины односвязного списка.

5. Напишите код, разбивающий связный список вокруг значения x, так чтобы все узлы, меньшие x, оказались перед узлами, большими или равными x.

6. Два числа хранятся в виде связных списках, в которых каждый узел содержит один разряд. Все числа хранятся в обратном порядке, при этом первая цифра числа находится в начале списка. Напишите функцию, которая суммирует два числа, и возвращает результат в виде связного списка.

Литература

1. Круз Рю Структуры данных и проектирование программ

2. M[chael McMillan/ Data Structures and Algorithms with JavaScript.

3. Лакман Макдауэлл Г. Карьера программиста

4. Монгар Дж., Киндлер Н., Гижере Э. Работа мечты для программиста

Дата добавления: 2015-11-04