Добавление элементa в середину.
Вставляем элемент в позицию pos+1
1. Создать новый элемент типа список
2. Инициализировать его информационное поле.
3. Если пустой, создать список из одного элемента с пустыми ссылками.
4. Найти позицию для вставки.
5. Следующей ссылке нового элемента присвоить адрес следующего элемента .
6. Предыдущей ссылке - адрес найденного.
7. У предыдущего элемента следующей ссылкой сделать адрес созданного элемента.
8. У следующего элемента предыдущей ссылкой сделать адрес созданного элемента
}
void insert(int data, int pos)
/* вставить в позицию pos+1 */
{ node* tmp = new node;
tmp->item = data;
node* ptmp = head;
if(ptmp == 0)
{ tmp->next = 0;
tmp->prev = 0;
head = tmp;
tail = tmp;
return;
int i = 0;
while ((i<pos)&&(ptmp->next))
{ ptmp = ptmp->next;
i++;
}
if (ptmp->next == 0)
{ ptmp->next = tmp;
tmp->prev = ptmp;
tmp->next = 0;
tail = tmp;
return;
}
ptmp->next->prev = tmp;
tmp->next = ptmp->next;
ptmp->next = tmp;
tmp->prev = ptmp;}
Удалить элемент c позиции pos.
1. Найти адрес элемента для удаления.
2. У предыдущего элемента следующей ссылкой сделать следующую ссылку найденного элемента.
3. У следующего элемента предыдущей ссылкой сделать предыдущую ссылку найденного элемента
4.Удалить найденный
int remove (int pos)
{ node* tmp = head;
for ( int i = 0; i<pos; i++)
{ if(tmp == 0) return 0;
tmp = tmp ->prev; }
tmp->next->prev = tmp->prev;
if(tmp ->prev != 0)
tmp->prev->next = tmp->next;
int res = tmp->item;
delete tmp;
return res; }
Исключить элемент из начала списка int pop_front()
{ if (head)
{ int res = head->item;
node *tmp = head;
if ( head->next)
head->next->prev = 0;
else tail = 0;
head = head->next;
delete tmp; return res;}
else return 0; }
Исключить элемент из конца списка
int pop_back()
{ if(tail)
{ int res = tail->item;
node *tmp = tail;
if(tail->prev) tail->prev -> next = 0;
else head = 0;
tail = tail->prev;
delete tmp;
return res;
}return 0;}
Стек -это специальный тип списка, в котором все вставки и удаления выполняются только на одном конце, называемом вершиной (TOP или HEAD). Для обозначения стеков используют аббревиатуру LIFO (Last-in-First-out)
Для обработки стека обычно используют следующие методы:
InitСоздает пустой стек
PEEKВозвращает элемент из вершины стека
POPУдаляет элемент из вершины стека
PUSHВставляет элемент в вершину стека
EMPTYВозвращает True, если стек пустой
struct stack
{
int item;
stack *prev;
};
stack *top;
void InitStack ()
{
top = NULL;
}
void push (int a)
//Занести в стек
{
stack *temp;
temp = new stack;
temp->prev = top;
temp->item = a;
top = temp;
}
int pop ( )
//Извлечь из стека
{
int res;
stack *temp;
temp = top;
top = top->prev;
res = temp->item;
delete temp;
return res;
}
int peek ()
// Выбор элемента из верхушки стека
{
if (top) return top->item;
}
bool is_empty ()
//Проверка пуст ли стек
{ bool res = false;
if (top == NULL)
res = true;
return res;
}
void removestack ()
//Удаление содержимого стека
{
stack *temp;
temp = top;
while (top)
{
temp = top;
top=top->prev;
delete temp;
}
}
СТЕК с использованием массива
int Size = 100 ;
int size; /* размерность массива */
int* p; * указатель на массив */
int top; /* верхушка стека */
int* ArrayStack(int _size)
{
size = _size > Size ?_size : Size;
p = new int[size];
top = -1;
return p;
}
bool isEmpty() /* пустой стек? */
{
return top == -1;
}
bool isFull() /* полный стек? */
{
return top + 1 == size;
}
void DeleteStack()
/* Удаление стека */
{
top = -1;
size = 0;
delete []p;
p = 0;
}
int push(const int n)
/* втолкнуть элемент в стек */
{
if (isFull ( ) )
return -1;
top++;
p[top] = n;
return top;
}
int pop ( )
/* вытолкнуть элемент из стека */
{ if(!isEmpty())
{ int res = p[top];
top--;
return res;}
return 0;
}
Преобразовать инфиксную строку-выражение в постфиксную строку-выражение и вычислить ее результат.
Инфиксная
(A+B*(D-E))/(F+G)
Префиксная
/*+AB-DE+FG
Постфиксная
ABDE-*+FG+/
Алгоритм:
1. Числа(буквы) записываются в строку том же порядке, в каком встречаются в исходном выражении.
2. Найденный символ арифметической операции заносится в стек при условии, что его приоритет выше приоритета предыдущего символа операции. В противном случае в строку записывается предыдущий символ операции, а найденный заносится в стек.
3. Открывающая скобка заносится в стек. Считается, что ее приоритет ниже приоритета всех арифметических операций. При нахождении закрывающей скобки все содержимое стека до первой открывающей скобки удаляется и записывается в строку. Открывающая скобка удаляется из стека и в строку не записывается.
Очередь- это специальный тип списка, в котором все вставки выполняются в одном конце, называемом последним (REAR),
а удаления выполняются в другом конце, называемом передним (FRONT).Для обозначения стеков используют аббревиатуру FIFO (First-in-First-out: первым вошел – первым вышел).
Включение элемента в очередь
1. создать новый элемент типа очередь
2. инициализировать его информационное поле.
3. изменить его указатель
4. изменить указатель на последний элемент очереди так, чтобы последним стал новый элемент.
Выбор элемента из очереди
1. Информационное поле первого ее элемента присвоить результирующей переменной,
2. Элемент исключить из очереди и удалить.
3. Может быть проверка на то, являлся ли этот элемент в очереди единственным, и если да, то необходимо соответствующим образом изменить указатель на последний элемент