1.1.3Операции со списками в статических массивах указателей

Вывод содержимого списка. Вывод выполняется по полю Name и полю Address. Для этого перебираются все элементы массива указателей и выполняется вывод соответствующих полей. Функция осуществляет вывод списка в компонент listView.

До вызова этой функции комопонент должен быть подготовлен к выводу. Чтобы он имел вид таблицы, свойству View необходимо задать значение Details. ListView должен содержать необходимое количество колонок и шапку таблицы.

Рисунок 1.2 - Вид формы с компонентом listView, в котором выведен список.

void PrintListInListView(TElmList* Arr, int count, System:: Windows::Forms::ListView * listView)

{

listView->Items->Clear();

if (count==0) return;

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

{

listView -> Items -> Add ( Arr [ i ] -> Name);

listView->Items->Item[i]->SubItems->Add(Arr[i]->Address);

}

} /* PrintListInListView */

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

Поиск элемента в упорядоченном списке. Пусть поиск выполняется по полю Name, Key - ключ поиска. Функция поиска элемента списка по ключу возвращает FindEl - номер позиции в массиве, в которой содержится указатель найденного элемента, при FindOK = true, или номер позиции в массиве, в которой может размещаться указатель на добавляемый элемент, если искомого элемента в списке нет, при FindOK = false. Ниже приводятся два варианта функции поиска – перебором элементов массива и методом половинного деления:

void FindElList1(TArrPtrElmList ArrPtrElLst, int Cnt, char *Key, int &PosFndEl,

bool &FindOK)

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

{

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

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

{

if (strcmp(ArrPtrElLst[J]->Name, Key)>=0)

{

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

if (strcmp(ArrPtrElLst[J]->Name,Key)==0)

{

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

содержит позицию возможной вставки нового

элемен-та*/

}

return;

}

} /*for*/

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

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

} //indElList1

void FindElList2(TArrPtrElmList ArrPtrElLst, 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 (ArrPtrElLst[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*/

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

TElmList* NPtrElm;

NPtrElm=new TElmList;

NPtrElm ->Age=…;

strcpy(NPtrElm ->Name, …);

strcpy(NPtrElm ->Address, …);

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

Общий вид этого оператора такой:

Указатель = new тип_элемента_для_которого_выделяется_память;

Обратный ему оператор delete – освобождает память, выделенную ранее оператором new и имеет вид:

delete указатель;

Добавление элемента в неупорядоченный список. Самым естественным является добавление элемента в конец списка, так как для этого необходимо занести новый указатель в элемент списка с номером Count. При этом необходимо следить за тем, чтобы не выйти за пределы массива. Если элемент невозможно добавить из-за переполнения массива – функция вернет False, если же добавление успешно – True.

bool AddElEndList (TArrPtrElmList &ArrPtrElList, int &Cnt, TPtrElmList NewP )

{

if (Cnt <= SizeArrH)

{

ArrPtrElList[Cnt] = NewP;

Cnt++;

return true;

}

else

{

return false;

}

} /*AddElEndList*/

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

Если добавляемый элемент оказывается последним в списке, то указатель на него располагается в позиции Count массива указателей.

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

В обоих случаях счетчик элементов списка Count увеличивается на 1.

Функция добавления элемента в упорядоченный список в качестве параметров получает указатель на добавляемый элемент - NewP и позицию в массиве, на которой должен размещаться этот указатель. Функция имеет следующий вид:

bool AddElSortList(TArrPtrElmList &ArrPtrElList, int &Cnt, TPtrElmList NewP,

int PosAddEl)

{

int K;

if (Cnt == SizeArrH + 1)

{

return false;

}

//если массив переполнен, то функция возвращает False

if (PosAddEl == Cnt) //добавляемый элемент располагается в конце списка

{

ArrPtrElList[PosAddEl] = NewP;

}

else

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

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

{

ArrPtrElList[K+1] = ArrPtrElList[K];

}

ArrPtrElList[PosAddEl] = NewP;

}

Cnt++;

} //AddElSortList

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

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

Если позиция удаляемого элемента списка находится в конце списка, т.е. в элементе массива с номером Count-1, то удаление элемента требует только освобождения памяти, занимаемой этим элементом списка.

Если позиция удаляемого элемента списка находится в начале или внутри списка, то его удаление требует освобождения памяти, занимаемой этим элементом списка и перемещение всех элементов массива, начиная с элемента в позиции J+1 и до Count-1 на одну позицию вверх.

В обоих случаях счетчик количества элементов списка уменьшается на 1.

Функция удаления элемента списка в качестве параметра получает значение позиции DelEl, на которой располагается удаляемый элемент. Функция имеет следующий вид:

void DelElList (TArrPtrElmList &ArrPtrElList, int &Cnt, int PosDelEl)

{

if (Cnt == 0)

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

return;

}

//по окончании поиска месторасположения удаляемого элемента в списке –

//имеющего позицию PosDelEl

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

delete ArrPtrElList[PosDelEl];

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

if (PosDelEl != Cnt - 1)

{

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

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

{

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

ArrPtrElList[K] = ArrPtrElList[K+1];

}

}

Cnt--;

} /*DelElList*/

Удаление списка. Процесс удаление списка не зависит от вида списка – упорядоченный список или нет.

Удаление списка сводится к поочередному удалению всех элементов списка. По окончанию удаления списка счетчик его элементов равен 0. Статический массив указателей на элементы списка сохраняется неизменным и может быть использован для последующего наращивания списка.

Функция удаления списка имеет следующий вид:

void DelList (TArrPtrElmList &ArrPtrElList, int &Cnt)

{

if ( Cnt = 0) //Список пуст

{return;}

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

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

{

delete ArrPtrElList[K];

}

Cnt=0;

} /*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 , которая содержит количество элементов списка.

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

{

Count=0;

}

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

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

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

Рисунок 1.4 - Установка свойства DialogResult для кнопки «+»

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

{

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

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

//FAdd будет нажата кнопка «+»(добавить), то при закрытии //доп.формы возвратится значение DialogResult::OK

{

TPtrElmList NPtrElm =new ElmList; //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(ArrPtrElmList,Count,NPtrElm ->Name,PosAdd,FindOK);

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

bool okAdd=AddElSortList (ArrPtrElmList,Count, NPtrElm, PosAdd );

if (!okAdd) /* если okAdd=false – элемент не добавлен в список из-за

переполнения массива*/

{

MessageBox(NULL,"Массив переполнен","Добавить эле-

мент невозможно",MB_OK);

}

PrintListInListView(ArrPtrElmList, Count, listView1);/*Вывод списка на

экран в listView*/

}

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

Void Form1::buttonFind_Click(System::Object * sender, System::EventArgs * e)

{

int PosFndEl;

bool FindOK;

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

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

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

if (FindOK) /*Если элемент найден*/

{

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

char* findResult=SystemStringToChar(String::Concat(textBoxFind->Text,

S", адрес: ", ArrPtrElmList[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::buttonDelList_Click(System::Object * sender, System::EventArgs * e)

{

DelList (ArrPtrElmList, Count);

}