1.1.8Операции со списками в динамических массивах типизированных указателей

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

Тексты основных процедур будут иметь вид:

// -------- Расширение массива указателей ---------//

void ExpendArrPtr (void* &PtrArPtrElmList, int &SizeAr, int Cnt)

/*увеличение размера массива указателей*/

{

int SizeW;

void* PtrArPtrElmListW; /*вспомогательный бестиповый указатель на на чало

массива указателей*/

SizeW = SizeAr; /*сохранение старого размера массива*/

SizeAr = SizeAr + Delta; /*определение нового размера массива*/

PtrArPtrElmListW = PtrArPtrElmList; /*сохранение указателя на старый массив*/

PtrArPtrElmList = new TElmList* [SizeAr]; /*выделение места для нового

массива*/

/*копирование старого массива индексов в новый массив*/

for (int J = 0; J <=Cnt - 1; J++)

{

((TElmList**)PtrArPtrElmList) [J] = ((TElmList**)PtrArPtrElmListW) [J];

}

delete [ ] PtrArPtrElmListW; /*удаление ста-рого массива*/

} /*ExpendArrPtr*/

//------------- Вывод списка в ListView ---------------//

void PrintListInListView(void* PtrArrPtrElList, int count, System:: Windows:: Forms::

ListView * listView)

{

listView->Items->Clear();

if (count==0) return;

for(int i=0; i<count;i++)

{

listView->Items->Add(((TElmList**)PtrArrPtrElList) [i]->Name);

listView->Items->Item[i]->SubItems->Add(((TElmList**)PtrArrPtrElList)[i]->Address);

}

} /*PrintListInListView*/

// ------------- Простой поиск ---------------- //

void FindElList1(void* PtrArrPtrElLst, int Cnt, char *Key, int &PosFndEl,

bool &FindOK)

/*процедура имеет двойное назначение - поиск месторасположения искомого элемента и поиск места вставки добавляемого элемента*/

{

FindOK = false; /*элемент не найден*/

for (int J=0; J<Cnt; J++)

{

if ( strcmp ( ((TElmList**)PtrArrPtrElLst)[J]->Name, Key) >= 0 )

{

PosFndEl = J; /*позиция найденного или следующего большего эле

мента*/

if ( strcmp (((TElmList**)PtrArrPtrElLst) [J]->Name, Key ) == 0 )

{

FindOK = true; /*элемент найден. В противном случае

PosFndEl содержит позицию

возможной вставки нового элемента*/

}

return;

}

} /*for*/

PosFndEl = Cnt; /*перебран весь массив. Определена позиция возможной

вставки нового элемента*/

} /*FindElList1*/

//------------ Быстрый поиск -------------------//

void FindElList2 (void* PtrArrPtrElLst, int Cnt, char *Key, int &PosFndEl,

bool &FindOK)

/*Поиск выполняется методом половинного деления*/

/*процедура имеет двойное назначение - поиск месторасположения искомого элемента и поиск места вставки добавляемого элемента*/

{

int Middl; /*Middl выступает как средняя граница обрабатываемой части

массива*/

int Hi, Low; /*текущие границы - верхняя, нижняя*/

FindOK = false; /*элемент не найден*/

if (Cnt == 0)

{

PosFndEl = 0;

return;

}

Low = 0;

Hi = Cnt - 1;

do

{

Middl = (Hi - Low) / 2 + Low; /* Middl = (Hi + Low) / 2 */

switch (strcmp(((TElmList**)PtrArrPtrElLst)[Middl]->Name, Key))

{

case 0: PosFndEl = Middl; /*элемент найден*/

FindOK = true; /*элемент найден*/

return;

case 1: Hi = Middl - 1;

break;

case -1:Low = Middl + 1;

break;

}

} while (Low <= Hi);

PosFndEl = Low; /*Перебран весь массив. Искомый элемент не найден. Оп-

ределена позиция возможной вставки нового эле-мента*/

} /*FindElList2*/

// -------- Добавление в отсортированный список ---//

void AddElSortList(void* PtrArrPtrElList, int &Cnt, TElmList* NewP, int PosAddEl)

{

if (PosAddEl == Cnt)

{

((TElmList**)PtrArrPtrElList)[PosAddEl] = NewP;

}

else

{

/*добавляемый элемент располагается в начале или внутри списка*/

for (int K = Cnt-1; K>=PosAddEl; K--) /*смещение на одну позицию вниз*/

{

((TElmList**)PtrArrPtrElList)[K+1] =((TElmList**)PtrArrPtrElList)[K];

}

((TElmList**)PtrArrPtrElList) [PosAddEl] = NewP;

}

Cnt++;

return ;

} /*AddElSortList*/

//--------- Удаление элемента -----------//

void DelElList (void* PtrArrPtrElList, int &Cnt, int PosDelEl)

{

if (Cnt == 0)

{ /*Список пуст*/

return;

}

/*по окончании поиска месторасположения удаляемого элемента в списке - имеющего позицию PosDelEl}

/*удаление элемента списка*/

delete ((TElmList**)PtrArrPtrElList)[PosDelEl];

/*возможная корректировка содержимого списка указателей*/

if (PosDelEl != Cnt - 1)

{

/*удаляемый элемент внутри списка*/

for (int K=PosDelEl+1; K <= Cnt - 1; K++)

{

/*смещение на одну позицию вниз*/

((TElmList**)PtrArrPtrElList)[K-1] = ((TElmList**)PtrArrPtrElList)[K];

}

}

Cnt--;

} /*DelElList*/

///-------- Удаление списка --------///

void DelList (void* &PtrArPtrElList, int &Cnt, int &SizeAr)

/*Удаление списка сводится к поочередному удалению всех эле-ментов списка. По окончанию удаления списка счетчик его элементов равен 0. Таким образом, удаляются только элементы списка, а массив указателей на элементы списка сохраняется для возможного после-дующего наращивания списка. Размер SizeArr массива указателей со-кращается до начального размера SizeArrH. Для полной очистки памяти от списка вслед за вызовом этой процедуры необходимо удалить массив указателей*/

{

if (Cnt != 0) /*список не пуст*/

{

/*удаление всех элементов внутри списка*/

for (int K = 0; K <= Cnt - 1; K++)

{

delete ((TElmList**)PtrArPtrElList)[K];

}

Cnt = 0; /*сброс счетчика элементов списка в 0*/

/*сокращение размера массива указателей от SizeArr до

SizeArrH*/

/*освобождение места, занимаемого старым массивом*/

delete [ ] PtrArPtrElList;

/*выделение места для нового массива*/

PtrArPtrElList = new TElmList*[SizeArrH];

SizeAr = SizeArrH;

}

} /*DelList*/

Рассмотрим общую схему работы с динамическими списками на основе динамических массивов.

Примечание. Данные об элементе списка вводятся в компонент textbox. Свойство Text данного компонента содержит строку ввода и имеет тип System::String*, а строковое поле элемента списка объявлено как массив символов (например, char [30]). Для перевода значения типа System::String* в char* воспользуемся дополнительной функцией

char* SystemStringToChar(System::String* string)

char* SystemStringToChar(System::String * string)

{

return (char*) (void*) System:: Runtime:: InteropServices:: Marshal:: StringToHGlobalAnsi(string);

}

Кнопка – создание списка. Массив динамический, создание списка состоит в инициализации переменной Count , которая содержит количество элементов списка, переменной SizeArr, которая содержит размер массива и выделении места для массива указателей размером SizeArr.

void Form1::buttonCreate_Click(System::Object * sender, System::EventArgs * e)

{

Count = 0; /*список пуст, колич.элементов - 0*/

/*Устанавливаем начальный размер массива SizeArH*/

SizeArr = SizeArrH;

/*Выделяем место в динамической памяти для массива указа

телей размером SizeARH*/

PtrDynArrPtrElmList = new TElmList*[SizeArrH];

}

Занесение нового элемента списка осуществляется по нажатию кнопки Добавить на главной форме. Для ввода полей нового элемента создана дополнительная форма FAdd, которая содержит компоненты textBox для ввода и кнопку "+" для подтверждения окончания ввода информации о новом элементе.

Рисунок 1.13 - Дополнительная форма для ввода информации о новом элементе.

Для кнопки "+" на дополнительной форме необходимо установить свойству DialogResult значение OK для того чтобы по окончании ввода информации можно было проанализировать – чем закончился диалог с пользователем – нажатием кнопки "+" или нжатием кнопки Выход.

Рисунок 1.14 - Установка свойства DialogResult для кнопки "+"

void Form1::buttonAdd_Click(System::Object * sender, System::EventArgs * e)

{

FormAdd *FAdd = new FormAdd(); /*Создание дополнительной формы FAdd*/

if (FAdd->ShowDialog() == DialogResult::OK) /*Если на дополнительной форме

FAdd будет нажата кнопка "+", то при закрытии доп. Формы

возвратится значение DialogResult::OK */

{

TElmList* NPtrElm = new TElmList; /*NPtrElm – указатель на новый

элемент списка*/

/*Заполнение полей нового элемента из компонентов textbox

дополнительной формы */

NPtrElm ->Age = Convert::ToInt32(FAdd->textBoxAge->Text);

strcpy(NPtrElm ->Name, SystemStringToChar(FAdd->textBoxName->Text));

strcpy(NPtrElm ->Address, SystemStringToChar(FAdd->textBoxAdress->Text));

int PosAdd;

bool FindOK;

/*Поиск места вставки указателя на новый элемент в массиве*/

FindElList2(PtrDynArrPtrElmList, Count, NPtrElm ->Name, PosAdd, FindOK);

if (SizeArr == Count) /*Если в массиве нет места для нового элемента

то увеличивается размер массива*/

{

ExpendArrPtr(PtrDynArrPtrElmList, SizeArr, Count);

}

/*Добавление элемента в список*/

AddElSortList (PtrDynArrPtrElmList, Count, NPtrElm, PosAdd);

/*Вывод списка на экран в listView*/

PrintListInListView (PtrDynArrPtrElmList, Count, listView1);

}

}

/*Поиск элемента по полю Name*/

void Form1::btnFindEl_Click(System::Object * sender, System::EventArgs * e)

{

int PosFndEl; /*позиция в массиве найденного элемента*/

bool FindOK; /*Результат поиска - true -найден,false-нет такого элемента*/

/* textBoxFind содержит ключ поиска*/

char *Key = SystemStringToChar(textBoxFind->Text); /*Ключ поиска*/

FindElList2(PtrDynArrPtrElmList, Count, Key, PosFndEl, FindOK);

if (FindOK)

{

/*Подготовка строки результата к выводу на экран*/

char* findResult = SystemStringToChar(String::Concat(textBox1->Text, S",

адрес: ", ((TElmList**)PtrDynArrPtrElmList) [PosFndEl]-> Address));

MessageBox(NULL, findResult, "Результат поиска", MB_OK);

}

else

{

MessageBox(NULL, "Элемент не найден", "Результат поиска", MB_OK);

}

}

/*Удаление элемента списка по полю Name*/

void Form1::buttonDel_Click(System::Object * sender, System::EventArgs * e)

{

/*Фамилия для удаления вводится в textBoxDel */

char * Key = SystemStringToChar(textBoxDel->Text);

int PosDel;

bool FindOK;

/*Поиск удаляемого элемента*/

FindElList2(ArrPtrElmList, Count, Key, PosDel, FindOK);

if (FindOK == false) /*Если элемент не найден - выход*/

{

return;

}

/*Удаление элемента из списка*/

DelElList (ArrPtrElmList, Count, PosDel);

/*Вывод списка на экран*/

PrintListInListView(ArrPtrElmList, Count, listView1);

}

/*удаление элементов списка*/

void Form1::btnDelList_Click(System::Object * sender, System::EventArgs * e)

{

DelList (PtrDynArrPtrElmList, Count, SizeArr);

PrintListInListView(PtrDynArrPtrElmList, Count, listView1);

/*удаление массива указателей на элементы списка если того требует задача*/

delete [ ] PtrDynArrPtrElmList;

}