Массивы и связные списки. Массивы и связанные списки. В предыдущих главах переменные типа int и char
 Скачать 287.28 Kb.
|
???? 13 ??????? ? ????????? ?????? В предыдущих главах переменные (типа int и char ) и объекты (типа Cat ) объяв- лялись по одному. Между тем достаточно часто возникает необходимость объявить набор объектов, например, 20 переменных типа int или дюжину объектов типа Cat На сегодняшнем занятии вы узнаете: • что такое массив и как его объявить; • что такое строка и как использовать массивы символов для создания строк; • взаимосвязь между массивами и указателями; • как использовать арифметические операции над указателями с применением массивов; • что такое связанный список. ??? ????? ??????? Массив – это набор элементов, способных хранить данные одного типа. Каждый элемент хранения называется элементом массива. Объявляя массив, необходимо сначала указать тип хранимых данных, а затем имя массива и его размер. Размером массива называет- ся количество его элементов, указываемое в квад- ратных скобках. long LongArray[25]; Здесь, например, объявлен массив LongArray из 25-ти элементов типа long . Обнаружив это объ- явление, компилятор зарезервирует область памяти, достаточную для хранения 25-ти переменных типа long . Поскольку каждой переменной типа long необходимы четыре байта, весь объявленный на- бор займет непрерывную область памяти разме- ром 100 байтов, как показано на рис. 13.1. Рис. 13.1. Объявление массива ???? 13. ??????? ? ????????? ?????? 357 ?????? ? ????????? ??????? К каждому из элементов можно обратиться по его номеру, расположенному в квадратных скобках после имени массива. Номера элементов массива начинаются с нуля. Следовательно, первым элементом массива LongArray будет LongArray[0] , вторым – LongArray[1] и т.д. Например, массив SomeArray[3] состоит из трех элементов: SomeArray[0] , SomeArray[1] и SomeArray[2] . В общем случае массив SomeArray[ n] , состоящий из n элементов, содержит элементы от SomeArray[ 0] до SomeArray[ n-1] Следовательно, массив LongArray[25] пронумерован от LongArray[0] до LongArray[24] . Листинг 13.1 показывает, как объявить массив из пяти целых чисел и заполнить его значениями. ??????? ? ????? ???????, ?????? ????? ? ????????? ?????????? ? ????. ??? ?????? ??? ????????, ??? ??????? ? ????? C++ ?????????? ? ????! ??????? 13.1. ????????????? ??????? ????? ????? 0: // ??????? 13.1. ??????? 1: #include 2: 3: int main() 4: { 5: int myArray[5]; // ?????? ?? 5 ????? ????? 6: int i; 7: for (i=0; i<5; i++) // 0-4 8: { 9: std::cout << "Value for myArray[" << i << "]: "; 10: std::cin >> myArray[i]; 11: } 12: for (i=0; i<5; i++) 13: std::cout << i << ": " << myArray[i] << endl; 14: return 0; 15: } ????????? Value for myArray[0]: 3 Value for myArray[1]: 6 Value for myArray[2]: 9 Value for myArray[3]: 12 Value for myArray[4]: 15 0: 3 1: 6 2: 9 3: 12 4: 15 ?????? Код листинга 13.1 создает массив, позволяет пользователю ввести значения для за- полнения его элементов, а затем отображает их на экране. В строке 5 объявлен массив myArray из пяти целочисленных переменных. Как можно заметить, он объявлен с цифрой 5 в квадратных скобках. Это означает, что массив myArray может содержать 358 ?????? 2. ???????? ??????? пять целочисленных значений. Каждый из элементов этого массива можно рассмат- ривать как обычную целочисленную переменную. В строке 7 начинается цикл от нуля до четырех, перебирающий все пять элементов массива. В строке 9 пользователю предлагается ввести значение, которое сохраняется в соответствующем элементе массива (строка 10). Рассмотрим код строки 10 подробнее. Как можно заметить, для обращения к каж- дому элементу используется имя массива, сопровождаемого значением индекса, ука- занным в квадратных скобках. Каждый из этих элементов может быть впоследствии обработан подобно переменной типа массива. Первое значение сохраняется в элементе массива myArray[0] , второе – в myArray[1] , и т.д. В строках 12 и 13 второй цикл for выводит каждое значение на экран. ???????? ????????: ??????? ?????????? ? 0 , ? ?? ? 1 . ??? ??????? ??????? ?????? ? ??????????, ?????????? ?????????. ????????? ???????, ???????, ??? ?????? ?? ?????? ????????? ?????????? ? ???????? ArrayName[0] ? ????????????? ????????? ArrayName[9] , ? ??????? ArrayName[10] ?? ????????????. ?????? ?????? ?? ????????? ??????? При записи значения в элемент массива компилятор вычисляет необходимую об- ласть памяти на основании размера типа элемента и размера массива. Предположим, необходимо записать значение в переменную LongArray[5] , являющуюся шестым элементом массива. Компилятор умножает индекс ( 5 ) на размер переменной (в дан- ном случае – 4 ). Затем текущий указатель смещается на 20 байтов от начального ад- реса массива, и записывается новое значение. Если попробовать записать значение в элемент LongArray[50] , то компилятор, проигнорировав тот факт, что такого элемента не существует, вычислит смещение от начала массива (200 байтов), а затем запишет значение по этому адресу. Здесь могут оказаться другие данные, и запись нового значения может иметь непредсказуемые по- следствия. Если повезет, программа зависнет сразу. Если нет, результаты проявятся намного позже и в совершенно другом месте. Обнаружить такую ошибку крайне сложно, даже если возникли подозрения, что что-то пошло не так. Подобно слепому, которого попросили отнести предмет в дом номер шесть, ком- пилятор двинется вдоль стенки от дома к дому, решив: “Необходимо отсчитать от первого дома ( MainStreet[0] ) пять зданий. Каждый дом – это четыре больших ша- га. Всего следует сделать 20 шагов”. Но если послать его на MainStreet[100] , размер которой всего 25 зданий, то, сделав 400 шагов, несчастный может угодить под грузо- вик. Так что будьте внимательны, отправляя его куда-либо. Листинг 13.2 демонстрирует, что случается при записи данных за пределами массива. ?? ?????????? ??? ?????????, ??????? ????? ?????????! ??????? 13.2. ?????? ?????? ?? ????????? ??????? 0: // ??????? 13.2. ???????????? ???? , ??? ????????? ??? 1: // ?????? ?????? ?? ????????? ??????? 2: #include 3: using namespace std; 4: 5: int main() 6: { ???? 13. ??????? ? ????????? ?????? 359 7: // ?????? 8: long sentinelOne[3]; 9: long TargetArray[25]; // ?????? ??? ?????????? 10: long sentinelTwo[3]; 11: int i; 12: for (i=0; i<3; i++) 13: { 14: sentinelOne[i] = 0; 15: sentinelTwo[i] = 0 16: } 17: for (i=0; i<25; i++) 18: TargetArray[i] = 10; 19: // ????????? ??????? ???????? ( ?????? ???? 0) 20: cout << "Test 1: \n"; 21: cout << "TargetArray[0]: " << TargetArray[0] << "\n"; 22: cout << "TargetArray[24]: " << TargetArray[24] << "\n\n"; 23: 24: for (i=0; i<3; i++) 25: { 26: cout << "sentinelOne[" << i << "]: "; 27: cout << sentinelOne[i] << "\n"; 28: cout << "sentinelTwo[" << i << "]: "; 29: cout << sentinelTwo[i] << "\n"; 30: } 31: 32: cout << "\nAssigning..."; 33: for (i=0; i<=25; i++) // ?????? ???? ?????? , ??? ????? ! 34: TargetArray[i] = 20; 35: 36: cout << "\nTest 2: \n"; 37: cout << "TargetArray[0]: " << TargetArray[0] << "\n"; 38: cout << "TargetArray[24]: " << TargetArray[24] << "\n"; 39: cout << "TargetArray[25]: " << TargetArray[25] << "\n\n"; 40: for (i=0; i<3; i++) 41: { 42: cout << "sentinelOne[" << i << "]: "; 43: cout << sentinelOne[i]<< endl; 44: cout << "sentinelTwo[" << i << "]: "; 45: cout << sentinelTwo[i]<< endl; 46: } 47: 48: return 0; 49: } ????????? Test 1: TargetArray[0]: 10 TargetArray[24]: 10 SentinelOne[0]: 0 SentinelTwo[0]: 0 SentinelOne[1]: 0 SentinelTwo[1]: 0 SentinelOne[2]: 0 SentinelTwo[2]: 0 360 ?????? 2. ???????? ??????? Assigning... Test 2: TargetArray[0]: 20 TargetArray[24]: 20 TargetArray[25]: 20 SentinelOne[0]: 20 SentinelTwo[0]: 0 SentinelOne[1]: 0 SentinelTwo[1]: 0 SentinelOne[2]: 0 SentinelTwo[2]: 0 ?????? В строках 8 и 10 объявляются два массива по три целых числа, которые выступают в качестве “стражи” массива TargetArray . Эти охранные массивы инициализирова- ны нулевым значением в строках 12—16. В связи с тем, что один из массивов объяв- лен до охраняемого, а второй – после, в памяти они будут расположены в том же порядке: “стража” – по бокам, а основной массив – между ними. Поэтому при выходе массива TargetArray за пределы отведенного ему пространства будут изменены значения ох- ранных массивов. Одни компиляторы рассчитывают память от первого адреса масси- ва, другие – от последнего, поэтому и “охрану” приходится размещать с двух сторон. Строки 20—30 подтверждают, что значения “стражей” при первой проверке рав- ны нулю. В строке 34 всем элементам TargetArray присваивается значение 20 , но счетчик задан так, что значение присваивается и элементу TargetArray[25] , кото- рого не существует. Строки 37—39 выводят на экран значения TargetArray при второй проверке. Обратите внимание, что TargetArray[25] выдает на экран значение 20 . Но когда на экран выво- дятся значения массивов SentinelOne и SentinelTwo , то оказывается, что значение эле- мента SentinelOne[0] изменилось. Дело в том, что участок памяти, являющийся 25-ым элементом от начала массива TargetArray , – это тот же участок, в котором размещает- ся элемент SentinelOne[0] . Если обратиться к несуществующему элементу TargetArray[25] , то на самом деле произойдет обращение к элементу SentinelOne[0] ????? ????????, ??? ? ????? ? ?????????? ? ????????????? ?????? ???* ???? ????????????? ?????????? ?????????? ???? ????????? ????? ????????? ?????. ???????? ??????? ????? ? ?? ???? ????????????. ???? ???? ??????? ???, ?????????? ???????? ?????? 33 ???, ????? ???* ????? ????????????? ?? 25*?, ? 26*? ????????. ??? ???????? ??????* ????? ?????????? “??????”. ??????????, ? ?????????? ????? ???? ????* ???????? ???*?????? ???, ??? ???????? ? ????????? ?????? ???????. Обнаружить эту ошибку иногда бывает очень трудно, поскольку значение SentinelOne[0] было изменено в той части кода, которая к массиву SentinelOne вообще никакого отношения не имеет. ?????? ?????????? ?????? Ошибка записи данных за пределами массива встречается так часто, что для нее придумали термин – ошибка последнего столба (fence post error). Сколько столбов не- обходимо для десятиметровой изгороди, если ставить их через каждый метр? Боль- шинство людей, не задумываясь, ответят: “Десять”, но на самом деле необходимо одиннадцать столбов. Рис. 13.2 демонстрирует это наглядно. ???? 13. ??????? ? ????????? ?????? 361 Рис. 13.2. Ошибка последнего столба Подобный тип подсчета (“минус один”) отравляет жизнь любому начинающему программисту. Но со временем к этому можно привыкнуть и запомнить, что массив из 25-ти элементов заканчивается двадцать четвертым номером, а начинается нулевым. ????????? ???????????? ???????? ??????? ArrayName[0] ???????. ??? ?????? ????????. ???? ??????? ArrayName[0] ???????, ?? ????? ???????? ArrayName[1] ? ??????? ???? ???, ??, ?????? ??????? ArrayName[24] , ?????? ??????, ??? ??? ?? 24*?? ???????, ? 25*??. ??* ????? ?????????? ????????, ??? ArrayName[0] ???????? ?????? ???* ?????? ? ??????? ???????. ????????????? ???????? Небольшой массив переменных встроенных типов (например, int или char ) мож- но инициализировать при объявлении. Для этого после имени массива помещают знак равенства ( = ) и заключенный в фигурные скобки список значений, отделяемых запятой. Например: int IntegerArray[5] = { 10, 20, 30, 40, 50 }; Здесь объявлен массив IntegerArray из пяти целочисленных элементов, которым присвоены значения IntegerArray[0] – 10 , IntegerArray[1] – 20 и т.д. Если размер массива не указан, но список значений присутствует, то будет создан и инициализирован массив достаточного размера, чтобы содержать все перечисленные значения. Таким образом, эта строка аналогична предыдущей: int IntegerArray[] = { 10, 20, 30, 40, 50 }; Нельзя инициализировать количество элементов, превосходящее объявленный размер массива: int IntegerArray[5] = { 10, 20, 30, 40, 50, 60 }; Такая строка приведет к ошибке во время компиляции, поскольку объявлен мас- сив для пяти элементов, а инициализировать пытались шесть. Но следующая запись вполне допустима: int IntegerArray[5] = {10, 20}; В данном случае объявлен массив из пяти элементов, а инициализированы только первые два: IntegerArray[0] и IntegerArray[1] ????????????? ?? ????????????? ????????? ??????????? ?????????????? ????????????? ?????? ???????????????? ????????. ???????? ??????? ???????????? ???????, ??? ? ??? ????????? ??????????. ????????, ??? ?????? ??????? ??????? ????? ??????, ?????? 0 ???????? ? ?????? ?????? ?????????, ??? ?????????. 362 ?????? 2. ???????? ??????? ?????????? ???????? В предыдущем коде для размеров массивов использовались “магические числа”: 3 – для охранных массивов и 25 – для массива TargetArray . Применение размеров констант обеспечивает большую надежность кода, поскольку при необходимости все значения можно изменить в одном месте. Массивы могут иметь любые имена, допустимые для переменных. Имена масси- вов и переменных не могут совпадать в пределах одной области видимости. Следо- вательно, нельзя одновременно объявить массив по имени myCats[5] и перемен- ную myCats Кроме того, при объявлении количества элементов вместо литералов можно ис- пользовать константу или перечисление. Фактически даже желательно использовать именно их, а не литеральное число, поскольку такой подход облегчает контроль над количеством элементов всех массивов, позволяя указать их размеры в едином месте. В листинге 13.2 использовались литеральные числа, но если размер массива TargetArray потребуется уменьшить до 20 , то изменять придется несколько строк кода. Если использовать для этого константу, то достаточно изменить значение только одной константы. Объявление количества элементов (или размера) массива при помощи перечисле- ния осуществляется немного иначе. Это проиллюстрировано в листинге 13.3 на при- мере массива, который содержит значения дней недели. ??????? 13.3. ????????????? ???????????? ? ???????? ? ???????? 0: // ??????? 13.3. ??????? ??????? ??????? 1: // ? ??????? ???????? ? ???????????? 2: 3: #include 4: int main() 5: { 6: enum WeekDays { Sun, Mon, Tue, Wed, 7: Thu, Fri, Sat, DaysInWeek }; 8: int ArrayWeek[DaysInWeek] = { 10, 20, 30, 40, 50, 60, 70 }; 9: 10: std::cout << "The value at Tuesday is: " << ArrayWeek[Tue]; 11: return 0; 12: } ????????? The value at Tuesday is: 30 ?????? В строке 6 создано перечисление WeekDays (дни недели). Оно состоит из восьми членов: Sun (воскресенье) равно 0 , а DaysInWeek (количество дней в неделе) – 7 В строке 8 объявлен массив по имени ArrayWeek , размер которого задан элементом DaysInWeek (со значением 7 ). В строке 10 константа перечисления Tue (вторник) использована в качестве индек- са элемента массива. Поскольку значением Tue является 2 , на экран будет выведено значение третьего элемента массива ( ArrayWeek[2] ), равное 30 ???? 13. ??????? ? ????????? ?????? 363 ??????? ??? ?????????? ??????? ??????? ????????? ??? ????????? ???????, ? ????? ??? ? ?????????? ????????? ???????. ?????? 1: int MyIntegerArray[90]; ?????? 2: long * ArrayOfPointersToLongs[100]; ??? ??????? ? ????????? ??????? ?????????? ???????? ???????. ?????? 1: // ?????????? ???????? ???????? ???????? ??????? // MyIntegerArray ?????????? theNinethInteger int theNinethInteger = MyIntegerArray[8]; ?????? 2: // ?????????? ???????? ???????? ???????? ??????? // ArrayOfPointersToLongs ????????? pLong long * pLong = ArrayOfPointersToLongs[8]; ??????? ?????????? ? ????. ?????? ?? n ????????? ???????????? ?? 0 ?? n-1 ??????? ???????? Массив может хранить любые объекты – как встроенные, так и созданные поль- зователем. При объявлении массива компилятору сообщают тип и количество храни- мых объектов, что позволит выделить участок памяти требуемого размера. Компиля- тор определяет размер памяти, необходимой для одного элемента массива (объекта), на основании объявления класса. Чтобы объекты могли быть созданы при определе- нии массива, класс должен обладать стандартным конструктором, которому не пере- дают никаких аргументов. Доступ к данным-членам объектов, находящихся в массиве, осуществляется в два этапа. Сначала, используя оператор индекса ( [] ), идентифицируют элемент массива, а затем с помощью точечного оператора ( ) получают доступ к определенной перемен- ной-члену. Листинг 13.4 демонстрирует создание массива из пяти объектов класса Cat ??????? 13.4. ???????? ??????? ???????? 0: // ??????? 13.4. ???????? ??????? ???????? 1: 2: #include 3: using namespace std; 4: 5: class Cat 6: { 7: public: 8: Cat() { itsAge = 1; itsWeight=5; } 9: Cat() {} 10: int GetAge() const { return itsAge; } 11: int GetWeight() const { return itsWeight; } 12: void SetAge(int age) { itsAge = age; } 13: 364 ?????? 2. ???????? ??????? 14: private: 15: int itsAge; 16: int itsWeight; 17: }; 18: 19: int main() 20: { 21: Cat Litter[5]; 22: int i; 23: for (i=0; i<5; i++) 24: Litter[i].SetAge(2*i +1); 25: 26: for (i=0; i<5; i++) 27: { 28: cout << "Cat #" << i+1<< ": "; 29: cout << Litter[i].GetAge() << endl; 30: } 31: return 0; 32: } ????????? cat #1: 1 cat #2: 3 cat #3: 5 cat #4: 7 cat #5: 9 ?????? Класс Cat объявлен в строках 5—17. Для создания массива объектов класс Cat должен иметь стандартный конструктор. В данном случае стандартный конструктор объявлен и определен в строке 8. Для каждого объекта класса Cat по умолчанию зада- ется возраст 1 и вес 5 . Не забывайте, что при наличии любого собственного конструк- тора стандартный конструктор компилятором не создается. Поэтому необходимо соз- дать собственный стандартный конструктор. Первый цикл for (строки 23 и 24) устанавливает возраст каждого из пяти объектов класса Cat в массиве. Второй цикл for (строки 26—30) обращается к каждому из эле- ментов и вызывает функцию GetAge() Чтобы вызвать метод GetAge() каждого из объектов класса Cat , приходится при обращении к элементу массива Litter[i] использовать точечный оператор ( ) и имя функции-члена. ??????????? ??????? Можно создать массив более одной размерности. Каждая размерность представляет собой дополнительный индекс массива. Следовательно, двумерный массив имеет два индекса, трехмерный – три и т.д. Массив может иметь любое количество размерно- стей, но в большинстве случаев достаточно одной или двух. Примером двумерного массива может служить шахматная доска. Одна размер- ность представляет собой восемь рядов по горизонтали, другая – восемь рядов по вертикали (рис. 13.3). Предположим, существует класс SQUARE (клетка). Объявление массива Board (доска) выглядело бы следующим образом: SQUARE Board[8][8]; ???? 13. ??????? ? ????????? ?????? 365 Рис. 13.3. Шахматная доска как двумерный массив Те же данные можно представить в виде одномерного массива на 64 клетки, на- пример: SQUARE Board[64]; Но это не будет соответствовать реальному объекту. В начале игры король стоит на четвертой клетке в первом ряду, эта позиция соответствует первому элементу по од- ному индексу и четвертому – по второму. Board[0][3]; ????????????? ??????????? ???????? Многомерные массивы также можно инициализировать. Элементам массива присваивается список значений таким образом, что вслед за последним значением первого индекса массива начинается первое значение второго индекса, и т.д. 1 int theArray[5][3]; Следовательно, если объявлен такой массив, то первые три элемента входят в эле- мент theArray[0] , следующие три – в элемент theArray[1] , и т.д. А инициализируется этот массив следующим образом: int theArray[5][3] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 }; 1 Т.е. двумерный массив разворачивается построчно. – Прим. ред. 366 ?????? 2. ???????? ??????? Чтобы было понятнее, значения при инициализации можно разделить фигурными скобками, например: int theArray[5][3] = { { 1, 2, 3}, { 4, 5, 6}, { 7, 8, 9}, {10,11,12}, {13,14,15} }; Компилятор проигнорирует внутренние фигурные скобки, но они сделают набор чисел нагляднее и понятнее. Вне зависимости от фигурных скобок каждое значение следует отделять запятой. Весь набор значений для инициализации расположен во внешних фигурных скобках и заканчивая точкой с запятой. В листинге 13.5 создается двумерный массив. Первая размерность – набор чисел от 0 до 4 , а вторая размерность состоит из удвоенного значения в первой. |