3. Динамический массив. List.
1. Динамический массив
Давайте вспомним, что изучаемая нами сейчас тема называется «Алгоритмизация и структуры данных»
Пришла пора начать говорить о структурах данных.
Условие: Вам заказали программу для игрового сервера регистрации, которая должна обрабатывать запросы от игроков. Понятно, что данные хранятся в виде базы данных, но (для того, чтобы ускорить работу) данные дублируются в оперативную память сервера. Нам необходимо разработать систему хранения данных и обработки запросов в оперативной памяти сервера.
Каждый запрос начинается с кода запроса (цифра от 0 до 3), причем 1 – это запрос на добавление, 2 – на изменение, 3 – на удаление, 0 – на вывод актуальных данных.
Далее вводятся и обрабатываются необходимые данные.
Для простоты будем считать, что в системе достаточно хранить логин и пароль игрока.
Первое, что необходимо сделать при решении подобных задач – продумать систему хранения данных. Конечно, пока других вариантов, кроме массива данных, вы не знаете, но…
Если вам нужно неизменное количество объектов, то массив вполне подходит. Но, допустим, вам нужно добавить в массив ещё один элемент. В простом массиве этого сделать невозможно. Допустим, вам нужно удалить элемент из массива. В простом массиве это так же невозможно. Вы привязаны к одному количеству элементов.
Для решения нашей задачи нужен массив, размер которого можно менять.
Поэтому нам лучше выбрать динамический массив — это массив, который может изменять свой размер.
Как же так?! Изменять размер массива нельзя, но, если надо, то можно?
Удивительно, но противоречия нет. И вы скоро поймете, почему.
Вариант 1. Изменение размера массива.
Если вам необходимо изменить размер массива, то вы можете воспользоваться методом Resize класса System.Array
public static void Main(string[] args)
{
int[] massiv = new int[10];
Console.WriteLine(massiv.Length);
Array.Resize(ref massiv,15);
Console.WriteLine(massiv.Length);
}
Фантастика! Был массив из 10 элементов, а стал из 15!
На самом деле никакой фантастики нет. И вы сами могли это сделать уже знакомыми вам командами. Метод Resize просто в данном случае создал новый массив из 15 элементов, первые 10 скопировал в новый массив из старого, а потом дал новому массиву то же имя. Очень затратная по времени операция.
Вариант 2. Коллекции. List(предпочтительный вариант).
Для решения проблем хранения информации в массивах Microsoft были разработаны коллекции с обобщенными типами (их ещё называют дженерики), они расположены в пространстве имен System.Collections.Generic. Пространство System.Collections.Generic содержит большой набор коллекций, которые позволяют удобно и эффективно решать широкий круг задач. Постепенно мы с ними познакомимся.
Начнем наше знакомство с коллекциями с класса List<T>. Эта коллекция является аналогом типизированного массива, который может динамически расширяться. В качестве типа можно указать любой встроенный либо пользовательский тип.
Создание объекта класса List<T>
Можно создать пустой List и добавить в него элементы позже, с помощью метода Add():
using System;
using System.Collections.Generic;
namespace ConsoleApplication9
{
internal class Program
{
public static void Main(string[] args)
{
List<int> numsList = new List<int>();
numsList.Add(1);
numsList.Add(2);
numsList.Add(5);
for (int i = 0; i < numsList.Count; i++)
{
Console.WriteLine(numsList[i]);
}
}
}
}
Либо воспользоваться синтаксисом, позволяющем указать набор объектов, который будет храниться в списке:
List<int> nums = new List<int> {1, 2, 3, 4, 5}; var words = new List<string> {"one", "two", "three"};
Ниже приведены таблицы, в которых перечислены некоторые полезные свойства и методы класса List<T>.
- Count - Количество элементов в списке.
- Capacity - Емкость списка – количество элементов, которое может вместить список без изменения размера.
Добавление к динамическому массиву:
При добавлении объекта к динамическому массиву происходит несколько действий. Класс массива проверяет, достаточно ли в нём места. Если Count < Capacity, то в массиве есть место для добавления. Если места недостаточно, то размещается больший внутренний массив, и всё копируется в новый внутренний массив. Значение Capacity увеличивается до нового расширенного значения. Если места достаточно, то добавляется новый элемент. Каждый элемент после точки вставки должен быть скопирован на соседнее место во внутреннем массиве, и после завершения копирования пустота заполняется новым объектом, а значение Count увеличивается на единицу.
Например, для добавления числа 5 в центр, необходимо было сдвинуть элементы 3, 9, 6 вправо, увеличив размер динамического массива на 1.
Поскольку необходимо перемещать каждый объект после точки вставки, то наилучшим случаем будет добавление элемента к концу. При этом нужно перемещать ноль элементов (однако внутренний массив всё равно требует расширения). Динамический массив лучше всего работает при добавлении элемента в конец, а не в середину.
Удаление из динамического массива:
Удаление объектов требует меньше работы, чем добавление. Во-первых, уничтожается сам объект. Во-вторых, каждый объект после этой точки сдвигается на один элемент. Наконец, Count уменьшается на единицу.
Как и при добавлении к концу массива, удаление из конца массива является наилучшим случаем, потому что при этом нужно перемещать ноль объектов. Также стоит заметить, что нам не нужно изменять размер внутреннего массива, чтобы сделать его меньше. Выделенное место может оставаться таким же, на случай, если мы позже будем добавлять объекты.
- Add(T) -Добавляет элемент к списку
- Clear() - Очистка списка
- IndexOf(T) - Возвращает индекс переданного элемента
- Insert(Int32, T) - Вставляет элемент в указанную позицию
- Remove(T) - Удаляет указанный элемент из списка
- RemoveAt(Int32) - Удаляет элемент из заданной позиции
- Sort() - Сортирует список
- Reverse() - Меняет порядок расположения элементов на противоположный
Недостатки динамических массивов:
Допустим, массив очень велик, а вам нужно часто добавлять и удалять объекты. А эти операции требуют постоянного изменения размеров массива, а, значит, его постоянного копирования. Операция это небыстрая, поэтому если вам нужно вносить частые изменения в середине динамического массива, то для этого есть более подходящие типы линейной структуры данных… А о них мы поговорим позже.
А сейчас вернемся к решению нашей задачи.
using System;
using System.Collections.Generic;
namespace ConsoleApplication10
{
public class Player
{
public Player(string login, string password)
{
Login = login;
Password = password;
}
public string Login;
public string Password;
}
internal class Program
{
private static List<Player> _players = new List<Player>();
public static void Main(string[] args)
{
Input();
}
private static void Input()
{
while (true)
{
Console.WriteLine("Введите код запроса: " +
"1 - добавить игрока, " +
"2 - удалить игрока, " +
"3 - изменить данные игрока, " +
"0 - вывести актуальный список игроков");
int code = Convert.ToInt32(Console.ReadLine());
MakeRequest(code);
}
}
private static void MakeRequest(int code)
{
string login = "";
string password = "";
if (code >= 1 && code <= 3)
{
Console.WriteLine("Логин игрока:");
login = Console.ReadLine();
Console.WriteLine("Пароль:");
password = Console.ReadLine();
}
switch (code)
{
case 1:
{
Player tempPlayer = new Player(login, password);
_players.Add(tempPlayer);
break;
}
case 2:
{
var index = SearchPlayer(login, password);
if (index >= 0 && _players[index].Password == password)
{
_players.RemoveAt(index);
Console.WriteLine("Игрок удален!");
}
else
{
Console.WriteLine("Игрок не найден или неверный пароль! Операция отменена!");
}
break;
}
case 3:
{
var index = SearchPlayer(login, password);
if (index >= 0 && _players[index].Password == password)
{
Console.WriteLine("Новый логин игрока:");
string newLogin = Console.ReadLine();
Console.WriteLine("Новы пароль игрока:");
string newPassword = Console.ReadLine();
_players[index].Login = newLogin;
_players[index].Password = newPassword;
Console.WriteLine("Данные изменены!!");
}
else
{
Console.WriteLine("Неверный пароль! Операция отменена!");
}
break;
}
case 0:
{
Print();
break;
}
default:
{
Console.WriteLine("Неверный код операции! Повторите ввод!");
break;
}
}
}
private static int SearchPlayer(string login, string password)
{
int resultIndex = -1;
for (int i = 0; i < _players.Count; i++)
{
if (_players[i].Login == login && _players[i].Password == password)
{
resultIndex = i;
}
}
return resultIndex;
}
private static void Print()
{
Console.WriteLine("Актуальный список игроков:");
for (int i = 0; i < _players.Count; i++)
{
Console.WriteLine("Логин: " + _players[i].Login + " Пароль: " + _players[i].Password);
}
}
}
}Какой из запросов (1, 2 или 3) в среднем будет выполняться дольше и почему?
Итоги занятия
Сегодня мы научились изменять размеры массива и познакомились со структурой List, разобрались с ее достоинствами и недостатками.
А на следующем занятии нас ждут примеры по-настоящему гениальных алгоритмов, придуманных задолго до изобретения компьютера.