от Курс за ССОК
Увод в програмирането на Perl
Лекция #4 Списъци, масиви и хешове
Скаларите могат да съдържат само една стойност в даден момент. Perl предоставя два фундаментални типа данни - масиви и хешове, които могат да съдържат многобройни стойности. В Perl всяка променлива трябва да бъде предхождана от типов идентификатор. Масивите (arrays) се предхождат от @ символ, а хешовете (hashes) от % символ.
Преди тези два типа данни, ще обсъдим списъците (lists). В Perl списъците представляват колекции от стойности. За да създадем списък, отделяме стойности със запетая, и ги ограждаме в скоби. Например:
("hi", "how", "are", "you")
Както винаги, важно е да знаем контекста, в който променливата ще бъде използвана. Списъчен контекст (list context) е място в програмата, където се изисква списък за изпълнението й. Скаларен контекст (scalar context) е място в програмата, където се очаква единична стойност. Операцията, която се извършва върху променливата спомага за определянето на контекста. Например, скалар от лявата страна на оператор за присвояване дава скаларен контекст на израза отдясно, за да може на променливата отляво да приеме стойност. Аналогично, когато имаме списък от лявата страна на оператор за присвояване, дясната страна се интерпретира в списъчен контекст. Функцията print може да използва списъци като аргументи.
print "3 + 5 = ", 3 + 5, "\n";
Когато се изчислява даден списък, всички подсписъци се изчисляват преди това:
(1, 4, 3 + 5, ('zzz', 7, (9, 8), 6 + 7), 'q') става (1, 4, 8, 'zzz', 7, 9, 8, 13, 'q')
Масивът, от своя страна съдържа списък скалари. Всеки масив може да съдържа 0 или повече скалари. Всеки елемент в масива си има индекс, който ползваме за да достъпим съответния елемент. Основната разлика между масив и списък е, че масива е именувана променлива, докато списъка се брои за константа. Елемент от масив се достъпва с името на масива, предшествано от $ (не @), и индекса на съответния елемент в [] скоби. Ако имаме един масив arr със 100 елемента, то първият елемент е $arr[0], десетият е $arr[9], т.е. i-тия елемент се достъпва като $arr[i – 1]. Важно е да се отбележи, че елементите на масива се достъпват с $ а не с @, защото са скалари. Индекса трябва да е цяло число (integer) или израз, който дава integer. В Perl, да използваме не цяла стойност за индекс не е синтактична грешка, но може да се получи логическа такава. Ако имаме низ (string) за индекс, то този стрингов индекс ще връща 0, давайки ни винаги първия елемент от масива. Няколко примера:
#събираме 3-тия, 4-тия, и 5-тия елемент на arr:
print $arr[2] + $arr[3] + $arr[4], "\n";
#делим 6-тия елемент на 2 и запазваме полученото:
print $arr[6] = $arr[6]/2;
# или
print $arr[6] /= 2;
Индексните скоби ( [] ) са всъщност оператор в Perl, като могат да бъдат приложени и за списъци. Примерно ако имаме списъка ("one", "two", "three"), то можем да напишем ("one", "two", "three")[1], но тази нотация не е много препоръчителна. Също така, в Perl е легално да имаме масив и скалар с еднакви имена, защото имаме различни типови идентификатори, $ и @ (избягвайте го!). За масивите не е задължително и всички елементи да са от един тип (само низове, или само цели числа), но е задължително всички елементи да са скалари.
Има няколко начина за създаване на масив в Perl. Най-лесният е да присвоим списък със стойности на масивна променлива:
@array = ("privet", 100, 300, 19.23, "end");
За да видим какво се съдържа в масива:
$i = 0;
while ($i < 4) {
print("$i $array[$i]\n");
$i++;
}
Ще се върнем към управляващите конструкции, за да поговорим за for. for има следната структура:
for (initialization; test; increment) {
statements;
}
По-горният while може да се напише като:
for ($i = 0; $i < 4; $i++) {
print("$i $array[$i]\n");
}
Видно е, че for отговаря (дава по-компактна версия) на:
initialization;
while (test) {
statements;
increment;
}
Има едно изключение, и това е когато ползваме next в цикъла (по-подробно за това следващата лекция, където ще разгледаме next, last и redo).
Не е добра практика да манипулираме контролната променлива ($i в случая) в тялото на for цикъла. Трите израза в тялото на for не са задължителни. Ако изпуснем test, то Perl приема, че условието за продължаване на цикъла е винаги истина, създавайки безкраен цикъл. Може да изпуснем и инициализацията на променливата, ако тя е направена някъде другаде в програмата. Може да се изпусне и инкремента, ако самия инкремент се изчислява от изрази в тялото или ако не се нуждаем от инкремент. Инкрементът във for действа като едно твърдение в края на тялото на for. Масата предпочита постинкремент ($i++), защото инкрементацията се извършва накрая (преинкрементът е незначително по-ефикасен – макар в Perl и то за целочислени променливи да няма разлика). Пост- и преинкрементите в нашия случая са еквивалентни, тъй като не се ползва върнатата от тях стойност.
Друг начин за създаване на масив е да присвоим стойност на който и да е елемент на масив, който още не съществува. Масива се създава автоматично със брой елементи, колкото да позволи съответния елемент. Например, ако е указан индекс 5, то се създава масив с 6 елемента. По същата логика ако зададем стойност на елемент, който не е съществувал засега, то Perl създава указания елемент, както и всички други елементи между оригиналния последен елемент и новия последен елемент. Ако се опитаме да достъпим несъществуващ елемент на масив, то се връща undef. Можем да ползваме функцията defined, за да проверим дали елемента е дефиниран или не. Пример:
#!/usr/bin/perl
use warnings;
$array[0] = "some string";
print "@array\n";
#element 1 and 2 --> undefined
$array[3] = "ponedelnik";
print "@array\n\n"; #output?
#loop to replace undefined values
for ($i = 0; $i < 4; $i++) {
if ( !defined($array[$i]) ) {
$array[$i] = "defined";
}
}
print "@array\n";
print @array, "\n";
Забелязва се, че когато масива се извежда като част от низ в двойни кавички, елементите се показват разделени от единичен интервал между тях. Когато извеждаме масив без двойни кавички, то стойностите му излизат като един низ. Може да се указва разделителя като ползваме специалната променлива $"(присвояваме низ на нея). Функцията defined връща истина, ако аргумента и е дефиниран и неистина в противен случай. Логическият оператор за отрицание ! обръща стойността – ако израза надясно от него връща истина, ! прави стойността лъжа и обратно. Алокацията (разпределянето) на паметта в Perl е различна от други езици, където трябва да се дефинира точната дължина на масива, преди да се използва.
Perl също така предоставя оператори за създаване на списъци от стойности. За списък от низове (несъдържащи spaces) можем да ползваме qw. Примерно qw(str1 str2 str3) и ('string1', 'string2', 'string3') са еквивалентни.
Друг оператор е .. (range operator). С него можем да създаваме последователни на низови и числови стойности. (1..5) е еквивалентно на (1, 2, 3, 4, 5), както и ('a'..'z') съдържа цялата азбука. Пример:
#!/usr/bin/perl
use warnings;
@arr = qw(tova e masiv ot stringove);
print "@arr\n\n";
@arr2 = (1..5);
print "Stoinost\tVsichko\n";
for ($i = 0; $i < 5; $i++) {
$total += $arr2[$i];
print($arr2[$i], "\t$total\n");
}
@arr2 = ('a'..'z');
print "\n@arr2\n";
Има доста интересни начини за манипулация на масиви. В скаларен контекст, масивът връща броя на елементите си. Списъците пък в скаларен контекст връщат последната си стойност (може да познавате оператора запетая от C). Можем да ползваме функцията scalar, т.е. scalar(@array) ще върне броя на елементите на масива. Фунцкията scalar оценява изразът, даден като аргумент в скаларен контекст. За да намерим последния индекс на един масив, можем да поставим пред името на масива $#, както в $#array. $#array може да бъде ползвано за промяна на големината на масива. Ако присвоим стойност на $#array, то тази стойност ще е новия последен индекс на масива. Ако пък искаме да махнем всички елементи от масива, можем да присвоим на @array празен списък, или ().
Понякога ни се налага да обхождаме един масив в обратен ред, като тук Perl позволява употребата на отрицателни индекси. Примерно $array[-1] ще върне последния елемент на масива. Пример:
#!/usr/bin/perl
use warnings;
@arr = qw(nula edno dve tri chetiri pet shest sedem osem devet deset);
print "Ima ", scalar(@arr), "elementi v @arr.\n";
print "Posledniq indeks v \@arr e $#arr.\n\n";
print "Posledniq element e $arr[$#arr].\n\n";
print "\@arr[-1] e $arr[-1].\n";
print "\@arr[-4] e $arr[-4].\n\n";
#namalqme goleminata na @arr
$#arr = 5;
print "@arr.\n";
#uvelichavame goleminata na @arr
$#arr = 10;
print "@arr.\n";
#mahame vsichki elementi
@arr = ();
print "@arr.\n";
print "Sega ima ", scalar(@arr), "elementi v \@arr.\n";
Операторът [] (bracket operator) може да бъде използван за създаване на списък, съдържащ част от елементите на един масив. Примерно @arr[1, 2, 3] връща списък съдържащ 2-рия, 3-тия и 4-тия елемент на @arr. Тази част от масив се нарича array slice(забележете, че array slice се предхожда от @). Така например ако един масив съдържа списък от стойности (1, 3), то @arr[1] връща списъка (3), докато $arr[1] връща 3. Ако искаме да вземем например първите 5 елемента можем да ползваме @arr[0..4].
Една добра черта на списъците е, че можем да присвоим списък от стойности на списък от скалари:
($first, $second) = (5, 6);
По този начин също по-удобно се разменят стойностите на две променливи:
($first, $second) = ($second, $first);
Array slices могат да бъдат използвани от всяка страна при присвояването на списъци. Ако имаме повече променливи в списъка отляво, то тогава оставащите променливи, които нямат съответствие отдясно стават undef (Какво би станало ако от лявата страна имаме масив? А масив и други променливи?). Пример:
#!/usr/bin/perl
use warnings;
@arr = qw(nula edno dve tri chetiri pet shest sedem osem devet deset);
#slices
print "@arr[1, 3, 5, 7, 9]\n";
print "@arr[2..6]\n";
($var1, $var2) = ("qbulka", "krusha");
print "\$var1 = $var1\n\$var2 = $var2\n";
@arr[1, 3, 5, 7, 9] = qw(1 3 5 7 9);
print "@arr\n\n";
($var1, $var2) = ($var2, $var1);
print "Sled swapping:\n";
print "\$var1 = $var1\n\$var2 = $var2\n\n";
($first, @arr2, $second) = (1..8);
print "\$first = $first\n";
print "\@arr2 = @arr2\n";
print "\$second = $second\n";
Има и други функции за манипулация на масиви, който променят съдържанието на масивите (те не могат да се ползват за списъци). Функцията push приема 2 аргумента, масив и списък с елементи, които да се добавят накрая:
push(@array, $element);
е еквивалентно на
$array[@array] = $element;
Тук @array е използвано в скаларен контекст (броя на елементите на един масив е с 1 повече от последния индекс).
Функцията pop премахва последния елемент на масив, връща елемента, и намалява големината на масива с 1.
Функциите shift и unshift са подобни на push и pop; shift премахва и връща първия елемент, докато unshift добавя елемент в началото на масива. Пример:
#!/usr/bin/perl
use warnings;
for ($i = 1; $i <= 5; $i++) {
push(@arr, $i);
print "@arr\n";
}
while(@arr) {
$total += pop(@arr);
print "@arr\n";
}
print "\$total = $total\n\n";
for ($i = 1; $i <= 5; $i++) {
unshift(@arr, $i);
print "@arr\n";
}
while(@arr) {
$newTotal += shift(@arr);
print "@arr\n";
}
print "\$newTotal = $newTotal\n\n";
Забележете, че условието за продължаване (loop condition) в while е самия масив. В този булев контекст @arr се пресмята до true или false. Ако има още елементи, то се връща true. Ако масива е празен, получава се false и цикъла прекъсва (Какво би станало ако в условието за продължаване поставим @arr[0]?).
Функциите shift/unshift, ползвани за големи масиви могат значително да влошат бързината на изпълнение на програмата (защо?), затова когато е възможно трябва да се ползва push/pop.
Друга интересна функция за манипулация на масиви е splice, която премахва или замества slices. Тя може да има до 4 аргумента. Първият е масива за обработване. Вторият е индекса на първия елемент за модифициране (offset). Третият е дължината на slice. Четвъртият е списък, с който трябва да заменим съответния slice. Ако изпуснем 4-тия аргумент, то съответния slice се изтрива от масива. Ако изпуснем 3-тия и 4-тия аргумент, то се изтрива slice от съответния offset до края на масива. Ако пък имаме само един аргумент (съответния масив) , то splice премахва всички елементи. Във всички случаи, splice връща 1 или повече премахнати елементи, или undef когато няма такива (какво ще върне splice в скаларен и списъчен контекст?). Пример:
#!/usr/bin/perl
use warnings;
@arr = (0 .. 20);
@arr2 = ('A' .. 'F');
print "@arr: @arr\n";
print "@arr2: @arr2\n\n";
@replaced = splice(@arr, 5, scalar(@arr2), @arr2);
print "replaced: @replaced\n",
"with: @arr2\n",
"changed to: @arr\n\n";
@removed = splice(@arr, 15, 3);
print "removed: @removed\n",
"leaving: @arr\n\n";
@chopped = splice(@arr, 8);
print "removed: @chopped\n",
"leaving: @arr\n\n";
splice(@arr);
unless(@arr) {
print "\@arr has no more elements.\n";
}
В допълнение на функциите, работещи върху масиви, има и други които приемат списъци и връщат такива. Функцията reverse приема списък за аргумент и връща списък със съдържанието в обратен ред, като първоначалния списък остава непроменен. Друга функция, която променя копие на списък е sort. При подаване на списък, sort връща копие на списък, сортирано лексикално (ASCII ред). Можем да добавим към sort и ред на сортиране чрез специалните променливи $а и $b (не ги ползвайте другаде извън sort!). За промяна на реда на сортиране ползваме операторите <=> и cmp, като ползваме <=> за числово и cmp за лексикално сортиране. Пример:
#!/usr/bin/perl
use warnings;
@arr = (0..9);
@reversed = reverse(@arr);
print "Original: @arr\n";
print "Reversed: @reversed\n\n";
@arr2 = (12, 34, 2, 100, 9, 3, 43, 1, 24, 17);
@sortedLexically = sort @arr2;
@sortedNumerically = sort {$a <=> $b} @arr2;
print "Not sorted: @arr2\n";
print "Sorted lexically: @sortedLexically\n";
print "Sorted lexically: @sortedNumerically\n\n";
Забелязва се, че функцията sort прави лексикографско (низово) сортиране по подразбиране.
Вторият фундаментален тип данни (не е скалар) за Perl е хеш (hash) или асоциативен масив. Хешът представлява неподредена колекция от ключ-стойност двойки (key-value pairs). Елементите във хеша са достъпвани чрез низ, наречен ключ. Всеки ключ трябва да е уникален. Ако ползваме същия ключ повече от веднъж, то оригиналната стойност за този ключ се замества с новата (това може да се окаже логическа грешка или една естествена update операция). Хешовете са всъщност една имплементация на структура от данни, наречена хеш таблица. Хешовете заемат повече място от масивите (защо?), но вътрешната структура на хешовете осигурява възможност за бързо извличане само в една операция.
Хешовете могат да да се създават по 2 начина: като присвоим списък на хеш променливата или като присвоим стойност на единичен елемент. Пример:
#!/usr/bin/perl
use warnings;
%hash = ( width => '300',
height => '150' );
print "\$hash{'width'} = $hash{'width'}\n";
print "\$hash{'height'} = $hash{'height'}\n\n";
$hash{'color'} = 'green';
print "\$hash{'width'} = $hash{'width'}\n";
print "\$hash{'height'} = $hash{'height'}\n";
print "\$hash{'color'} = $hash{'color'}\n\n";
print "%hash\n";
print %hash, "\n";
Употребен е => оператор, който интерпретира лявата си страна като низ (string), така че няма нужда от кавички. За разлика от масивите, когато достъпваме елементите на хеша ползваме {} (curly braces) с ключа в тях. Още една разлика с масивите е, че хешовете не се интерполират в двойни кавички. Без кавички хешовете излизат като един дълъг низ в реда keyvaluekeyvalue(ключстойностключстойност). Аналогично на масивите, хешовете си имат хеш slices. Ако поставим няколко ключа в {}, то се връща списък със стойностите за тези ключове. Върнатият списък се манипулира като масив от стойности, затова ползваме символа @ за манипулиране на хеш slices, както и за масивни slices. Пример:
#!/usr/bin/perl
use warnings;
%romans = ( one => 'I',
two => 'II',
three => 'III',
four => 'IV',
five => 'V',
six => 'VI',
seven => 'VII',
eight => 'VIII',
nine => 'IX',
ten => 'X' );
print "The Romans for three, five, and eight are: ", "@romans{'three', 'five', 'eight'}\n\n";
Както при масивите, има функции при хешовете който опростяват достъпа и манипулацията при хешовете. Функцията keys връща списък със всички ключове в един хеш. Много е удобна за преминаване през целия хеш и операции върху всяка стойност. Подобно на нея, функцията values връща списък със всички стойности в хеша. Друга интересна функция е each. Тя връща key-valueдвойки като списък,в който първия елемент е ключа, а втория – стойността. Тя запазва докъде в хеша е достигнала, и всеки път връща нова двойка. Накрая, когато няма повече двойки, връща undef. Ако викнем keys или values ще накараме each да започне отначалото при следващото й повикване. Функцията reverse, приложена върху хешове, обръща двойките така че ключовете стават стойности, а те – ключове. Тази функция работи коректно само ако всички стойности са уникални, защото хеша изисква всички ключове да са уникални. Пример:
#!/usr/bin/perl
use warnings;
%presidents = ( Todor => "Jivkov",
Jelio => "Jelev",
Georgi => "Purvanov",
Peter => "Stoqnov" );
@keys = keys(%presidents);
while($key = pop(@keys)) {
print "$key => $presidents{$key}\n";
}
@values = values(%presidents);
print "\nThe values of the hash:\n@values\n\n";
print "%presidents reversed:\n";
%hash = reverse(%presidents);
while(($key, $value) = each( %presidents) ) {
print "$key => $value\n";
}
Следващите функции са съответно delete, exists, и defined. Функцията delete премахва елемент от хеша. Функциите exists и defined ни помагат да различим елемент който съществува, който е дефиниран, елемент със стойност undef и елемент, който се изчислява до true. Ако един елемент не е бил създаван, то той не съществува. Ако елемент е създаден, но на него не е била присвоена стойност, то той е недифиниран. Ако един скалар съдържа стойността 0 (числово) или празен низ (""), то той е false. За да проверим дали една променлива съществува, ползваме exists. За да проверим дали на нея е присвоена стойност, ползваме defined. Пример:
#!/usr/bin/perl
use warnings;
%hash = ( Ivan => 12,
Dragan => 0,
Petko => 100,
Bug => 30,
Emo => undef );
@keys = keys( %hash );
for ($i = 0; $i < @keys; $i++) {
print "$keys[$i] => $hash{$keys[$i]}\n";
}
delete( $hash{'Ivan'} );
while ( $key = pop(@keys) ) {
print "\n";
if ( exists($hash{$key}) ) {
print "$key exists!\n";
} else {
print "$key doesn't exist!\n";
}
if ( defined($hash{$key}) ) {
print "$key is defined as $hash{$key}.\n";
} else {
print "$key is undefined.\n";
}
if ( $hash{$key} ) {
print "$key is true.\n";
} else {
print "$key is false.\n";
}
}
Задачи
Задача 1
Да се напише програма, която създава тесте карти (числата от 1 до 52). Да се разбърка тестето така, че след разбъркването тестето да съдържа стойностите си в реда 1, 27, 2, 28, 3, 29, и т. н.
Задача 2
Да се напише програма, която създава масив от стойности и да се използва хеш, за да се определи дали има повтарящи се стойности в масива.
Задача 3
Да се реализират като програми на Perl алгоритмите за линейно и двоично търсене в масив.
Решения
