Динамические структуры данных: дек (стр. 2 из 2)
Удаление элемента из конца дека
Для удаления элемента из начала дека используется метод класса delete_end.
Для удаления элемента из конца дека надо создать новый элемент структуры Node (el). Элементу el присваивается указатель на первый элемент. Пока el не примет значения NULL, элемент будет принимать значения следующего элемента. Затем el удаляется и ссылке на последний элемент присваивается значение el. Количество ячеек уменьшается.
Проверка дека на наличие в нем элемента
Для проверки дека используется метод класса prov. Этот метод имеет тип Boolean.
Для проверки на наличие элементов в деке, создается новый элемент структуры Node и ему присваивается указатель на первый элемент дека. Если ячейка не пуста, то возвращается значение true, в противном случае, false.
Функция вывода дека в StringGrid
Данная функция необходима для отображения вставки и удаления элементов в таблицу StringGrid. Функция увеличивает количество ячеек таблицы, если обнаруживает, что ячейка не пуста.
Приложение 1
Текст программы
#include <vcl.h>
#pragma hdrstop
#include <iostream>
#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
int s, count=0;
struct Node
{
int key;
Node *next;
};
class deq
{
private:
Node *first;
Node *last;
public:
deq()
{first=NULL;
last=NULL;}
void deq::add(int b)
{
Node *el=new Node;
el->key=b;
if (first==NULL)
{
el->next=first;
first=el;
last=first;
}
else
{
el->next=first;
first=el;
}
count++;
}
void deq::del()
{
Node *el=new Node;
el=first;
first=el->next;
delete el;
count--;
}
void deq::add_end(int b)
{
Node *el=new Node;
el->key=b;
last->next=el;
last=el;
last->next=NULL;
count++;
}
void deq::del_end()
{
Node *el=new Node;
el=first;
while (el->next->next!=NULL)
el=el->next;
delete el->next;
last=el;
last->next=NULL;
count--;
}
bool deq::prov()
{ Node *el=new Node;
el=first;
if (first==NULL)
return true;
else
return false;
}
void Draw ()
{
for (int i=0; i<10; i++)
Form1->StringGrid1->Cells[0][i]="";
Node* temp=first;
for (int i=0; i<count; i++)
{
Form1->StringGrid1->Cells[0][i]=temp->key;
if (temp->next!=NULL)
temp=temp->next;
}
}
};
deq a;
int i=0;
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
a.add(StrToInt(Edit2->Text));
a.Draw();
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button2Click(TObject *Sender)
{
a.add_end(StrToInt(Edit2->Text));
a.Draw();
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button3Click(TObject *Sender)
{
if(a.prov())
ShowMessage("Дек пуст. Нечего удалять") ;
else
a.del();
a.Draw();
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button4Click(TObject *Sender)
{
if(a.prov())
ShowMessage("Дек пуст!");
else
ShowMessage("Дек не пуст!");
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button5Click(TObject *Sender)
{
Edit3->Text=StrToInt(count);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button6Click(TObject *Sender)
{
if(a.prov())
ShowMessage("Дек пуст. Нечего удалять") ;
else {
a.del_end();
a.Draw();}
}
//---------------------------------------------------------------------------
Приложение 2
Форма
Главная форма содержит:
· Label (Введите добавляемый элемент)
· GroupBox1 (Добавление элементов)
o Button1 (Добавление элемента в начало дека)
o Button2 (Добавление элемента в конец дека)
· GroupBox2 (Удаление элементов)
o Button3 (Удаление первого элемента)
o Button6 (Удаление последнего элемента)
· GroupBox3 (Другие функции)
o Button4 (Проверка на наличие элементов)
o Button5 (Узнать размер дека)
o Edit3 (Используется для вывода количества элементов в деке)
· StringGrid (Отображение дека)
· Edit2 (Значение, введенное с клавиатуры в Edit2, добавляется в дек)
Рис. 4. Главная форма