| Назад | Содержание | Вперед |
Массив представляет собой набор элементов, доступ к которым осуществляется по индексу. Массив создается оператором new и конструктором массива — системной функцией Array. Создать массив из названий дней недели можно, например, следующим образом:
var NDays = new Array("воскресенье","понедельник", "вторник",
"среда", "четверг", "пятница","суббота")
В качестве параметров конструктору передаются значения элементов массива. Можно создать массив, указав в нем лишь число элементов, например, так:
var Ndaysl= new Array(7)
И, наконец, можно использовать конструктор без параметра:
var Ndays2= new Array()
В этом случае определяется лишь, что переменная Ndays2 используется в качестве массива.
Все элементы массива перенумерованы, начиная с нуля. Для получения значения элемента массива необходимо задать имя массива и в квадратных скобках порядковый номер элемента. Для того чтобы получить доступ к первому элементу массива, следует воспользоваться конструкцией Ndays [0] .
Свойство length позволяет определить число элементов в массиве или, как говорят, длину массива. Доступ к последнему элементу массива можно осуществить, например, следующим образом:
Ndays[Ndays.length-1]
При описании переменной Ndaysi задана только длина массива. Значения элементов массива можно указать с помощью оператора присваивания:
Ndays[0]="воскресенье"
Ndays[1]="понедельник"
Ndays[2]="вторник"
Ndays[2]="среда"
Ndays[2]="четверг"
Ndays[2]="пятница"
Ndays[6]="суббота"
Функция определения выходного/рабочего дня
Напишем функцию, которая по строке, являющейся названием дня недели, определяет, является ли этот день выходным или рабочим (листинг 14.1).
Листинг 14.1. Функция определения по номеру дня, выходной он или рабочий
function grd(s)
( var гез="рабочий"
if ((s== NDays[0]) || (s== NDays[6]))
res="выходной"
return res
}
Определение времени посещения Web-страницы
Необходимо написать сценарий, который формирует сведения о текущей дате и времени в следующем виде:
Вы посетили эту страницу
1 ноября 2000 года
в 5:26:03
Сегодня — среда
При решении задачи используется два массива: один для хранения названий месяцев, другой для хранения дней недели. В переменной str формируется строка, которая затем будет выведена в документе (листинг 14.2).
Листинг 14.2. Время посещения страницы с использованием массивов
<HTML>
<HEAD>
<script language="JavaScript">
// Названия месяцев
NMonths = new Array("января", "февраля", "марта", "апреля", "мая",
"июня", "июля", "августа", "сентября",
"октября", "ноября", "декабря")
// Названия дней недели
NDays = new Array("воскресенье", "понедельник", "вторник", "среда",
"четверг", "пятница", "суббота")
function DateTime ()
{ var now = new Date()
var minute = now.getMinutes ()
var second = now.getSeconds ()
var hour = now.getHours()
var min = ( (minute < 10 ) ? ":0" : ":") + minute
var sec = ( (second < 10 ) ? ":0" : ":") + second
var str = "Вы посетили эту страницу<br>"
year = now.getYear() + " "
month = now.getMonth()
imonth = NMonths[ month]
day=now.getDay()
iday= NDays[day]
str += now.getDateO + " " + imonth + " " + year + " года<br>"
str += "в " + hour + min + sec + "<br>"
str += "Сегодня - " + iday
document.write(str)
}
</script>
</HEAD>
<BODY>
<H4 align=center>Пример использования функций
определения времени</Н4>
<CENTER>
<script language = "JavaScript">
DateTime ()
</script>
</CENTER>
</BODY>
</HTML>
Далее рассмотрим несколько классических задач, посвященных работе с массивами. Приведем функции работы с массивами, которые ценны сами по себе и могут применяться в различных программах.
Поиск максимального элемента массива
Напишем функцию, которая определяет максимальный элемент массива.
Сначала в качестве максимального элемента берется первый элемент массива. Затем просматриваются элементы массива, и каждый элемент сравнивается с максимальным значением уже рассмотренных элементов. Если текущий элемент больше максимального значения, то максимальным становится текущий элемент. Таким образом, после просмотра всего массива определяется максимальный элемент.
HTML-код приведен в листинге 14.3.
Листинг 14.3. Максимальный элемент массива
function maxelem (v)
{ var m= v[0]
for (var i=l; i <= v.length-1; i++)
{ if (v[i] > m)
m=v[i]
}
return m
}
Определение количества максимальных элементов в массиве
Напишем функцию, определяющую количество максимальных элементов в массиве. Если задан массив, состоящий из элементов (4, 5, 5, 5, 3, 5, 2, 3, 1, 3, 4), то максимальным значением массива является 5, которое встречается 4 раза.
При просмотре массива кроме максимального значения запоминается количество максимальных значений для просмотренной части массива. Если очередной элемент массива больше, чем максимальное значение для просмотренных элементов, то максимальным становится очередной элемент, а количество максимальных устанавливается в 1. Если очередной элемент совпадает с максимальным, то число найденных максимальных элементов увеличивается на 1 (листинг 14.4).
Листинг 14.4. Количество максимальных элементов в массиве
function nummax (v)
{ var m= v[0] var k=l
for (var i=l; i <= v.length-1; i++)
{ if <v[i] > m)
{m=v[i]; k=l}
else
if (v[i] == m) k++
}
return k
}
Поиск заданного элемента в неупорядоченном массиве
Напишем функцию, определяющую, присутствует ли заданный элемент в массиве.
Если у нас нет дополнительной информации об организации элементов массива, то при поиске элемента следует воспользоваться алгоритмом, который получил название линейный поиск. Согласно этому алгоритму будем сравнивать поочередно все элементы массива v с образцом t. Если очередной элемент совпадает с t, то задача решена. Если искомого элемента в массиве нет, то убедимся в этом, лишь просмотрев все элементы массива. В качестве результата работы функции можно выдавать логическое значение true, если элемент найден, и false — в противном случае. Иногда удобно выводить номер найденного элемента, если же элемента в массиве нет, то отобразить некоторое заданное значение, например, - 1 (листинг 14.5).
Листинг 14.5. Поиск элемента в неупорядоченном массиве
function linsear(v,t)
{ var k=-1
for (var i=0; i <= v.length-1; i++)
if (v[i] == t )
{k=i; break}
return k
}
Поиск заданного элемента в упорядоченном массиве
Напишем функцию, определяющую, присутствует ли заданный элемент в упорядоченном массиве.
Если элементы массива упорядочены, то организовать поиск элемента с заданным значением можно согласно алгоритму бинарного поиска. Пусть переменная i — индекс первого элемента, значение j — индекс последнего элемента массива, среди которых осуществляется поиск. Определяется индекс элемента k, находящегося посередине. Далее k-й элемент массива v[k] сравнивается с образцом t. Если окажется, что t<=v[k], то поиск следует продолжать среди элементов с индексами [i, k], если же t>v[k], искать надо среди элементов [k+i, j]. Процесс поиска продолжается до тех пор, пока исследуемая часть массива не станет равной одному элементу, тогда результат будет зависеть от того, равен этот элемент образцу или нет. Функцию binsear (v, t) опишем так, как указано в листинге 14.6.
Листинг 14.6. Поиск элемента в упорядоченном массиве
function binsear (v,t)
var i=0
var j= v.length-1
var k
while (i < j)
{ k=Math.round((i+j)/2+0.5)-1
if (t <= v[k])
j=k
else
i=k+l
}
if (v[i] == t) { return i}
else return -1
}
Заметим, что значение переменной i может лишь увеличиваться, значение переменной j только уменьшаться, причем при каждом повторении тела цикла либо увеличивается значение переменной 1, либо уменьшается значение переменной j и значение переменной i меньше значения j. Когда значения i и j совпадут, цикл завершит работу. Рассмотрим случай, когда исследуются только два элемента. Значение k на следующем шаге итерации станет равным значению i. Если значение t меньше или равно v[i], то переменной j будет присвоено значение k, значения переменных i и j совпадут, цикл завершит работу. Если же значение t больше v [ i ], то переменной i присвоится значение k+i, и в этом случае значения i и j совпадут.
После выполнения цикла сравнивается значение 1-го элемента со значением t, и результат выдается в качестве работы функции. Пусть исходный массив состоит из элементов, упорядоченных по возрастанию (2, 3, 5, 6, 6, 7, 10, И, 20, 25), а значение t равно 7. Ожидаемый результат — индекс найденного элемента, равный 5.
Бинарный поиск с формированием таблицы результатов
Напишем функцию, которая реализует алгоритм бинарного поиска таким образом, чтобы во время работы программы формировалась таблица значений переменных i, j, k и некоторых выражений так, как показано на рис. 14.1.
|
|
| Рис 14.1. Бинарный поиск с промежуточными значениями Текст функции представлен в листинге 14.7. |
Листинг 14.7. Поиск вупорядоченном массиве с таблицей промежуточных значений
<HTML>
<HEAD>
<TITLE>Бинарный поиск. Таблица промежуточных значений</TITLE>
<script language="JavaScript">
<!-- //
var v=new Array (2, 3, 5, 6, 6, 7,10,11, 20, 25)
function testtab(obj,v,t)
{ var res="i j k v[k] t<= v[k]"+"\r\n"
var i=0
var j= v.length-1
var k
while ( i < j )
{ k=Math.round( (i+j)/2+0.5)-1
res = res + i + " "+j+" "+k+" "+"v[" + k + "]=" + v[k] + " " + t + "<=" + v[k]+"\r\n"
if (t <= v[k] )
j=k
else
i=k+l
}
res += "v[" + i + "]=" +v[i]+"\r\n"
obj.resultl.value=res
if (v[i] == t )
{ return i}
else return -1
}
function test(obj)
{ obj.datal.yalue=v}
//-—>
</script>
</HEAD>
<BODY bgcolor=silver>
<Н4>Реализация алгоритма бинарного поиска</Н4>
<FORM name="forml">
<pre>
Массив: <INPUT type="text" size=40 name="datal" ><hr>
Элемент: <INPUT type="text" size=20 name="data2" ><hr>
Результат поиска: <INPUT type="text" size=20 name="result" ><hr>
Таблица промежуточных значений: <BR>
<textarea cols=50 rows=7 name="result1" > </textarea><hr>
</PRE>
<input type="button" value=0пpeдeлить
onClick="test(form1); forml.result.value=testtab
(form1,v,forml.data2.value)">
<input type="reset" value=Отменить>
</FORM>
</BODY>
</HTML>
Идентификация симметричности массива
Напишем функцию, определяющую, является ли массив симметричным, т. е. совпадает ли его первый элемент с последним, второй с предпоследним и т. д.
Решать задачу будем следующим образом. Сначала сравним первый и последний элементы массива. Если они не совпадают, то задача решена, и массив не является симметричным. Если значения первого и последнего элементов массива совпадают, то анализ массива требуется продолжить. Функция simarri (v) реализует описанный алгоритм (листинг 14.8).
Листинг 14.8. Проверка, является ли массив симметричным
function simarri (v)
{ var p= true
var n= v.length
for {var i=0; i <= (n-l)/2; i++)
if (v[i] !=v[n-l-i]) {p=false; break}
return p
}
Приведем еще один вариант решения задачи. Будем использовать методы работы с объектом Array, определенные в JavaScript. Метод reverse () переставляет элементы массива в обратном порядке, первым элементом становится последний, вторым — предпоследний, а последний — первым. Метод j oin (} преобразует элементы массива в строку. При решении задачи преобразуем исходный массив в строку sv, далее "перевернем" исходный массив и опять преобразуем в строку. Если массив симметричен, то строки должны совпадать. Функция simarr в этом случае может быть описана так:
function simarr(v)
{ var sv=v.join()
v.reverse()
var sw=v.join()
return (sv == sw)
}
Объединение массивов с упорядочиванием результата
Пусть заданы два массива, состоящие из целых чисел, упорядоченных по возрастанию. Требуется написать функцию построения третьего массива, также упорядоченного по возрастанию и содержащего элементы как первого, так и второго массивов.
Опишем алгоритм решения задачи, который называется алгоритмом слияния двух упорядоченных массивов. Исходные массивы просматриваются "параллельно" до тех пор, пока в одном из них не будут исчерпаны все элементы. После этого непросмотренные элементы второго массива переписываются в массив результата без изменений. Пусть i — индекс очередного элемента массива a, j — индекс очередного элемента второго массива ь. В массиве с содержатся уже упорядоченные элементы первого массива в количестве(i-i) и элементы второго массива в количестве (j-i). Если a[i]<=b[j], то в массив с записывается элемент a[i] и осуществляется переход к анализу следующего элемента массива а, т. е. значение переменной i увеличивается на 1. Если же a[i]>b[j], то в массив с помещается j-й элемент массива ь и происходит переход к анализу очередного элемента массива b.
Если один из массивов просмотрен полностью, то в результирующий массив .помещаются элементы другого массива. Опишем функцию sli(a,b) (листинг 14.9, а).
Листинг 14.9, а. Объединение двух упорядоченных массивов. Вариант 1
function sll(a,b)
{ var m=a.length-1
var n=b.length-1
var p=m+n var c=new Array (p)
var i=0; var j=0; var k=0;
while ((i <= m) && (j <= n))
{if (a[i] <= b[j])
{c[k] = a[i]; i++}
else
{c[k] = b[j]; j++}
k++
}
if (i > m )
{ while (j<=n)
{c[k]=b[jl; k++; j++}
}
else
{ while (i <= m)
{c[k]=a[i]; k++; i++}
}
return с
}
Функцию sli можно упростить, если в исходные массивы вслед за основными содержащимися в них элементами поместить элемент, заведомо больший любого элемента исходного массива. Тогда не возникает ситуации "дописывания" непросмотренных элементов какого-либо из массивов. В этом варианте решения в функции sl2 будет использоваться лишь одни цикл (листинг 14.9, б).
Листинг 14.9, б. Объединение двух упорядоченных массивов. Вариант 2
function sl2(a,b)
{ var m=a.length
var n=b.length
a[m]=marker
b[n]=marker
var р=m+n
var c=new Array (p)
var i=0; var j=0; var k=0;
for (k=0; k<p; k++)
{if (a[i] <= b[j])
{c[k] = a[i]; i++}
else
{c[k] = b[j]; j++}
}
return с
}
Результат работы функции представлен на рис. 14.2.
|
| Рис 14.2. Слияние упорядоченных массивов |
При выполнении описанных функций sl1 и sl2 исходные массивы просматриваются только один раз.
Другой вариант решения задачи: соединить два массива в один, а затем отсортировать по возрастанию получившийся массив. Такое решение никак не использует упорядоченность исходных массивов и признано неэффективным из-за алгоритма сортировки. Приведем такое решение, потому что заманчиво использовать тот факт, что объект Array имеет метод sort (), позволяющий упорядочивать элементы массива в лексикографическом порядке, и метод concat (), объединяющий два массива в один. Используя оба метода, опишем функцию si3 (a,b):
function sl3(a,b)
{ var c=new Array()
c=a.concat(b).sort()
return с
}
При использовании метода concat () два массива объединяются в один:
a.concat(b)
а затем, чтобы упорядочить полученный массив, применяется метод sort: с=а.concat(b).sort()
Для исходных данных предыдущего примера в результате работы функции sl3 будет получен результат: 10, 101, 107, И, 12, 14, 20, 25, 3, 34, 35, 4, 44, 5, 56, 6, 7, 78, 8, 9, 92.
Мы видим, что результат неверен, т. к. элементы массива сравниваются как строки. Если элементами исходных массивов действительно являются строки, то функция sl3 работает правильно. Один из тестов приведен на рис. 14.3. Заметим, что если бы исходные массивы были не отсортированы, то результат был бы тот же.
|
| Рис 14.3. Слияние массивов из строк |
Перестановка элементов массива
Пусть в исходном массиве содержатся ненулевые вещественные числа разных знаков. Требуется написать функцию, которая переставляет элементы массива таким образом, что сначала располагаются все отрицательные элементы, а затем все положительные.
При первом варианте решения введем дополнительный массив и в него станем записывать элементы в нужном порядке. При этом будем использовать две переменные, в которых сохраним индексы последних записанных в новый массив значений: отрицательных и положительных. Исходный массив просматривается один раз, и необходимый массив будет сформирован (листинг 14.10).
Листинг 14.10, а. Переформирование массива. Вариант 1
function divar(a)
{ var el
var i=-1
var n=a.length
var j=n
var b=new Array(}
for (var k=0; k <= n-1; k++)
{ el=a[k]
if (el < 0)
{ i++; b[i]=el }
else {j—; b[j]=el}
}
a=b
return a
}
Можно было бы всю работу по формированию массива произвести в исходном массиве. Для этого так же, как и в предыдущем случае, можно использовать две переменные i и j, "движущиеся" навстречу друг другу таким образом, что за переменной i остаются только отрицательные элементы, за переменной j — положительные. На каждом шаге работы цикла проверяются знаки 1-го и j-ro элементов. В зависимости от знаков элементов на i-м и j-м местах сдвигается либо один, либо другой индекс. Если же сдвинуть ни одну из переменных нельзя, то меняются местами крайние элементы рассматриваемой части массива и процесс продолжается (листинг 14.10, б).
Листинг 14.10, б. Переформирование массива. Вариант 2
function divar(a)
{ var n = a.length
var i=0
var j=n-1
var ell=a[i]
var el2=a[j]
while (i < j)
{ if (ell < 0)
{ i++; ell = a[i] }
else
if (el2 >0)
{ j —; e!2=a[j] }
else
{ a[i]=e!2; a[j]=ell; i++; ell=a[i]; j—; el2=a[j] }
}
return a
}
Для решения этой задачи мы могли бы описать простую функцию, которая использует метод сортировки массива Array. В результате выполнения оператора a. sort () (листинг 14.10, в) элементы будут отсортированы в лексикографическом порядке, и хотя для чисел сортировка выполнена неверно, но задача разделения массива, заключающаяся в том, что сначала располагаются отрицательные, затем положительные элементы, выполнена.
Листинг 14.10, в. Переформирование массива. Вариант 3
function divar(a)
{ a. sort ()
return a
}
Исполнение функции на одном из тестовых примеров приведено на рис. 14.4.
|
| Рис 14.4. Переформирование массива |
Добавление элемента в массив без нарушения упорядоченности
Напишем функцию, добавляющую в заданный отсортированный массив элемент, не нарушая упорядоченности.
Будем просматривать элементы массива с конца, сдвигая каждый из них вниз до тех пор, пока не встретится элемент, значение которого меньше значения вставляемого элемента. Когда необходимый элемент найден, на свободное место помещается добавляемый элемент (листинг 14.11).
Листинг 14.11. Добавление элемента в упорядоченный массив
function addar (v,t)
{ var n=v.length
var j=n
while (j > 0)
{ if (t < v[j-l])
{v[j]=v[j-l]; j —-}
else
{v[j]=t; break}
}
if (j==0) v[0]=t
return v
}
Если добавляемый элемент меньше первого элемента массива, то весь массив следует сдвинуть на один элемент вниз, и вне цикла на первое место поместить заданный элемент.
Напишем сценарий, удаляющий из упорядоченного массива элемент, значение которого совпадает с заданным. Если таких элементов несколько, то требуется удалить элемент с наименьшим индексом.
При решении задачи поступим следующим образом. Воспользовавшись функцией бинарного поиска, определим индекс элемента, совпадающего с удаляемым элементом. Если такого элемента нет, то задача решена, а в противном случае, сдвигаем "хвост" массива, начиная с k-ro элемента на одну позицию вверх. HTML-код с описанными в нем функциями представлен в листинге 14.12.
Листинг 14.12. Удаление элемента из упорядоченного массива
<HTML>
<HEAD>
<TITLE>Удаление элемента из упорядоченного массива</TITLE>
<script language="JavaScript">
<!—- //
var v=new Array(4, 5,15,17,31,52,72,79,81,83,89,91,93,94,98)
function test(obj
)
( obj.datal.value=v }
function binsear(v,t)
{ var i=0
var j=v.length-1
var k
while (i < j)
{ k=Math.round((i+j)/2+0.5)-1
if (t <= v[k])
j=k
else
i=k+l
}
if (v[i] = t)
{ return i }
else return -1
}
function delar (v,t)
{ var n=v.length
var k=binsear(v,t)
if (k != - 1)
{ for (var i=k; i <= n-1; i++)
v[i]= v[i+l]
v.length=n-l
}
return v
}
// -—>
</script>
</HEAD>
<BODY>
<Н4>Удаление элемента из упорядоченного массива</Н4>
<FORM name="form1">
<pre>
Массив: <input type="text" size=40 name="datal" ><hr>
Элемент: <input type="text" size=20 name="data2" ><hr>
Результат поиска: <input type="text" size=40 name="result" ><hr>
</pre>
<input type="button" value=Определить
onClick="test(forml); fоrml.result.value= delar
(v,Number(form!.data2.value))">
<input type="reset" value=Отменить>
</FORM>
</BODY>
</HTML>
1. Задан одномерный массив вещественных чисел. Напишите сценарий, который определяет число положительных элементов массива.
2. Задан одномерный массив вещественных чисел. Напишите сценарий, который определяет число отрицательных элементов.
3. Задан одномерный массив целых чисел. Напишите сценарий, который определяет число минимальных элементов.
4. Задан одномерный массив целых чисел. Напишите сценарий, который определяет число элементов, кратных 7.
5. Задан одномерный массив целых чисел. Напишите сценарий, который определяет номер последнего минимального значения.
6. Напишите сценарий, который определяет номер первого максимального значения в одномерном массиве целых чисел.
7. Напишите сценарий, при работе которого определяется число элементов одномерного массива, совпадающих с заданным.
8. Напишите сценарий, при работе которого определяется, есть ли в массиве элементы, значения которых совпадают.
9. Напишите сценарий, определяющий все ли элементы массива различны.
10. Напишите сценарий, определяющий максимальную по длине неубывающую последовательность.
11. Напишите сценарий, который объединяет два упорядоченных массива таким образом, что в результирующем массиве все элементы различны.
12. Напишите сценарий, который по двум массивам строит третий, являющийся пересечением заданных.
13. Напишите сценарий, который определяет, сколько различных чисел в заданном массиве.
14. Напишите сценарий, который для заданного массива целых чисел определяет длину К самой длинной "пилообразной" последовательности идущих подряд чисел: Х р +\ < Х р+2 > Х р+ъ <...> X p+k .
15. Напишите сценарий, который для заданных двух массивов X из п элементов и У из k элементов определяет, существуют ли в X подряд идущие элементы, для которых верно X i+ \ = Y\, X i+ 2 = YI, ..., X i+k = Y k .
16. Задана формула вида ai?a2?... ?an, где ai — либо истина, либо ложь. Вместо знака вопроса (?) может стоять либо дизъюнкция, либо конъюнкция. Напишите сценарий, определяющий все комбинации знаков, при которых формула получает заданное значение.
| Назад | Содержание | Вперед |