Массивы и связные списки. Массивы и связанные списки. В предыдущих главах переменные типа int и char
 Скачать 287.28 Kb.
|
0: //Listing 13.9. ????????? ??????? ??????? ?? ????? ?????????? 1: 2: #include 3: using namespace std; 4: int main() 5: { 6: int AllocationSize = 5; 7: int *pArrayOfNumbers = new int[AllocationSize]; 8: int ElementsUsedSoFar = 0; 9: int MaximumElementsAllowed = AllocationSize; 10: int InputNumber = -1; 11: 12: cout << endl << "Next number = "; 13: cin >> InputNumber; 14: 15: while (InputNumber>0) 16: { 17: pArrayOfNumbers[ElementsUsedSoFar++] = InputNumber; 18: 19: if (ElementsUsedSoFar == MaximumElementsAllowed) 20: { 21: int *pLargerArray = 22: new int[MaximumElementsAllowed+AllocationSize]; 23: 24: for (int CopyIndex=0; 25: CopyIndex 27 : { 28: pLargerArray[CopyIndex] = pArrayOfNumbers[CopyIndex]; 29: }; 30: 31: delete [] pArrayOfNumbers; 32: pArrayOfNumbers = pLargerArray; 33: MaximumElementsAllowed += AllocationSize; 34: }; 35: cout << endl << "Next number = "; 36: cin >> InputNumber; 37: } 376 ?????? 2. ???????? ??????? 38: 39: for (int Index=0; Index 41: cout << pArrayOfNumbers[Index] << endl; 42: } 43: return 0; 44: } ????????? Next number = 10 Next number = 20 Next number = 30 Next number = 40 Next number = 50 Next number = 60 Next number = 70 Next number = 0 10 20 30 40 50 60 70 ?????? В этом примере запрашиваются и сохраняются в массиве числа, введенные одно за другим. При вводе числа, равного или меньше 0 , собранный массив чисел отобража- ется на экране. Рассмотрим этот код подробнее. В строках 6—9 объявлены несколько переменных. А именно: в строке 6 задан исходный размер массива ( 5 ), код строки 7 создает массив в распределяемой памяти, а его адрес присваивает указателю pArrayOfNumbers Код строк 12—13 запрашивает у пользователя первое число и помещает его в пере- менную InputNumber . Если введенное значение больше нуля, в строке 15 начинается его обработка; в противном случае управление переходит к строке 38. В строке 17 значение переменной InputNumber помещается в массив. Сначала все происходит без проблем, поскольку выделенного участка памяти еще хватает. Код строки 19 проверяет, не является ли текущий элемент последним (т.е. обладает ли массив свободными ячейками). Если свободный участок памяти имеется, управление проходит к строке 35, в противном случае выполняется код тела оператора if , позво- ляющий увеличить размер массива (строки 20—34). Новый массив создается в строке 21. Его размер будет на пять элементов ( AllocationSize ) больше, чем текущего. Затем код строк 24—29 копирует содержимое старого массива в новый. Здесь использована стандартная для массива форма записи, но можно было использовать также и арифметические операции над указателями. Код строки 31 удаляет старый массив, а код строки 32 заменяет старый указатель указателем на больший массив. Строка 33 увеличивает значение переменной MaximumElementsAllowed так, чтобы оно соответствовало новому размеру. Код строк 39—42 отображает полученный в результате массив на экране. ???? 13. ??????? ? ????????? ?????? 377 ????????????? ?? ????????????? ???????, ??? ?????? ?? n ????????? ???????????? ?? 0 ?? n-1 ????????? ??? ??????? ? ????????? ??????? ???????, ? ??? ??????? ? ?????????? ??????? — ???????? ????????. ???????????? ???????? delete[] , ????? ??????? ???? ??????, ????????? ? ???????????? ??????. ???????? delete ??? ?????????? ?????? ?????? ?????? ?????? ??????? ???????. ?????????? ? ?????? ?????? ??? ???????? ???????. ?????? ?????? ?????????? ? ?????????? ?? ??????. ???????? ?????????? ??????, ?????????? ??? ?????? ????????? new ??????? ???????? ? ?????? Строка в стиле C представляет собой массив символов, завершающийся пустым значением ( null ). До сих пор в этой книге единственными строками в стиле C были безымянные строковые константы, например: cout << "hello world.\n"; Строку стиля C можно объявить и инициализировать, как и любой другой массив: char Greeting[] = { 'H', 'e', 'l', 'l', 'o', ' ', 'W','o','r','l','d', '\0' }; В данном случае объявлен массив символов Greeting , который инициализирован набором символов. Последний символ, '\0' , является пустым (символом null ). Именно он служит для функций языка C++ признаком конца строки. Хотя такой “посимвольный” подход и работоспособен, но труден для вывода и порождает слиш- ком много ошибок. Язык C++ допускает использование более кратких форм. Напри- мер, объявление предыдущей строки может выглядеть так: char Greeting[] = "Hello World"; Обратите внимание на следующие две особенности такого синтаксиса: вместо отдельных символов в одинарных кавычках, разделенных запятыми и окруженных фигурными скобками, применяются лишь двойные кавычки; добавлять символ null в конце строки не нужно, компилятор сделает это сам. При объявлении строковой переменной необходимо удостовериться, что ее размер достаточен для выполнения поставленной задачи. Длину строки в стиле C составляет количество символов строки, включая символы пробела и завершающий нулевой сим- вол. Например, строка “ Hello World ” в стиле C занимает 12 байтов: Hello – 5 бай- тов, пробел – 1, World – 5 и символ null – еще один. Можно также создавать и неинициализированные символьные массивы. Однако при этом следует удостовериться, что в буфер будет записано данных не больше его вместимости. Листинг 13.10 демонстрирует использование неинициализированного буфера. ??????? 13.10. ?????????? ??????? 0: // ??????? 13.10. ?????? ??? ?????????? ????? 1: 2: #include 378 ?????? 2. ???????? ??????? 3: 4: int main() 5: { 6: char buffer[80]; 7: std::cout << "Enter the string: "; 8: std::cin >> buffer; 9: std::cout << "Here is's the buffer: " << buffer << std::endl; 10: return 0; 11: } ????????? Enter the string: Hello World Here's the buffer: Hello ?????? В строке 6 объявлен буфер размером 80 символов. Он достаточно велик, чтобы со- держать 79-символьную строку в стиле C и завершающий символ null В строке 7 пользователю предлагают ввести строку, которая будет (в строке 8) вве- дена в буфер. Концевой символ null добавляется оператором cin Здесь возникают две проблемы (см. листинг 13.10). Во-первых, если пользователь вводит строку длиннее 79-ти символов, то оператор cin запишет данные за пределами буфера. Во-вторых, если пользователь введет пробел, то cin воспримет его как конец строки и остановит запись в буфер. Для разрешения этих проблем необходимо создать специальный метод cin.get() , которому передают три параметра: буфер для заполнения; максимальное количество символов; символ для завершения ввода. По умолчанию критерием завершения ввода является символ новой строки. Лис- тинг 13.11 демонстрирует применение этого метода. ??????? 13.11. ?????????? ??????? ???????????? ??????????? ???????? 0: // ??????? 13.11. ?????????? ?????? cin.get() 1: 2: #include 3: using namespace std; 4: 5: int main() 6: { 7: char buffer[80]; 8: cout << "Enter the string: "; 9: cin.get(buffer, 79); // ?????? 79 ??? ????? ?????? 10: cout << "Here's the buffer: " << buffer << endl; 11: return 0; 12: } ????????? Enter the string: Hello World Here's the buffer: Hello World ???? 13. ??????? ? ????????? ?????? 379 ?????? В строке 9 расположен вызов метода cin.get() . Буфер, объявленный в строке 7, передается в качестве первого аргумента. Второй аргумент – максимальное количест- во вводимых символов. В данном случае – 79, чтобы учесть завершающий символ null . Третий параметр (символ завершения ввода) необязателен, поскольку по умол- чанию признаком завершения является новая строка. При вводе пробелов, символов табуляции или других непечатаемых символов они также войдут в состав строки. Символом новой строки заканчивается ввод. Ввод 79-ти символов также приведет к завершению ввода. Это можно проверить, повторно запус- тив код и попытавшись ввести строку, длиннее 79-ти символов. ??????? strcpy() ? strncpy() Язык С++ унаследовал от языка С библиотеку функций для строковых операций. Существует множество встроенных функций, две из них осуществляют копирование одной строки в другую. Это функции strcpy() и strncpy() . Функция strcpy() ко- пирует содержимое строки в указанный буфер, а функция strncpy() копирует опре- деленное количество символов из одной строки в другую. Листинг 13.12 демонстриру- ет применение функции strcpy() ??????? 13.12. ????????????? ??????? strcpy() 0: // ??????? 13.12. ????????????? ??????? strcpy() 1: 2: #include 3: #include 4: using namespace std; 5: 6: int main() 7: { 8: char String1[] = "No man is an island"; 9: char String2[80]; 10: 11: strcpy(String2,String1); 12: 13: cout << "String1: " << String1 << endl; 14: cout << "String2: " << String2 << endl; 15: return 0; 16: } ????????? String1: No man is an island String2: No man is an island ?????? Файл заголовка string.h подключен в строке 3. Этот файл содержит прототип функции strcpy() , принимающей два символьных массива: результирующий и ис- ходный. Если исходный массив окажется больше результирующего, функция strcpy() осуществит запись за пределами результирующего буфера. Во избежание этой ошибки стандартная библиотека располагает функцией strncpy() . Этому варианту передают максимальное количество копируемых символов. 380 ?????? 2. ???????? ??????? Функция strncpy() осуществляет копирование до первого символа null или макси- мального количества символов, определенного для результирующего буфера. Лис- тинг 13.13 демонстрирует применение функции strncpy() ??????? 13.13. ????????????? ??????? strncpy() 0: // ??????? 13.13. ????????????? ??????? strncpy() 1: 2: #include 3: #include 4: 5: int main() 6: { 7: const int MaxLength = 80; 8: char String1[] = "No man is an island"; 9: char String2[MaxLength+1]; 10: 11: strncpy(String2,String1,MaxLength); 12: 13: std::cout << "String1: " << String1 << std::endl; 14: std::cout << "String2: " << String2 << std::endl; 15: return 0; 16: } ????????? String1: No man is an island String2: No man is an island ?????? Еще один простой пример кода. Подобно предыдущему листингу, здесь данные из одной строки просто копируются в другую. В строке 11 обращение к функции strcpy() было заменено на обращение к функции strncpy() , которой передают третий параметр: максимальное количество символов для копирования. Буфер String2 объявлен как массив из MaxLength+1 символов. Дополнительный элемент предназначен для символа null , который обе функции, strcpy() и strncpy() , до- бавляют в конец строки автоматически. ??????? ???????????????????? ? ???????? 13.9 ????????????? ???* ?????, ??????? ?????????? ???????? ????? ????? ????????, ??????* ??? ? ?????????????? ?????? ????? ????????? ??????? ? ?????????? ? ???? ???????? ????????. ? ???????? ?????? ??????? ????? C++, ??????????? ????????????? ??????????? ? ????????? ?? ??????, ? ????? ????????? ??? ??????? ???????? ?? ???????? ?????, ???????????? ??????? ??????. ????????? ?????? Язык C++ унаследовал завершающий строку символ null от языка C вместе с со- держащей функцию strcpy() библиотекой функций, но эти функции не интегрирова- ны в объектно-ориентированную среду. Стандартная библиотека содержит класс String , инкапсулирующий специальный набор данных и функций для управления ими. Открыты лишь функции доступа, а сами данные класса String от клиента скрыты. ???? 13. ??????? ? ????????? ?????? 381 В качестве упражнения создадим собственный специальный класс String . Этот класс должен преодолеть исходные ограничения символьных массивов. Подобно всем остальным массивам, символьные массивы статичны. Их размер задается при объяв- лении, и независимо от того, какое количество элементов массива используется, раз- мер занимаемого участка памяти остается неизменным, а запись за пределами масси- ва чревата неприятностями. ??????????? ????? String , ??????????, ????? ????? ???????????? ??????????? ? ?? ????? ??????????? ? ???????????? ?????. ??? ??* ???, ??? ??????????? ?????????? ??????????? ?????? ? ???????? ???* ???? ?????? String Грамотно разработанный класс String занимает столько памяти, сколько необхо- димо для хранения переданных ему данных. Если класс не сможет выделить достаточ- ного количества памяти, следует предусмотреть элегантный выход из этой ситуации. Листинг 13.14 представляет реализацию класса String в первом приближении. ??????? 13.14. ????????????? ?????? String 0: // ??????? 13.14. ????????????? ?????? String 1: 2: #include 3: #include 4: using namespace std; 5: 6: // ????????????? ????? string 7: class String 8: { 9: public: 10: // ???????????? 11: String(); 12: String(const char *const); 13: String(const String &); 14: String(); 15: 16: // ????????????? ????????? 17: char & operator[](unsigned short offset); 18: char operator[](unsigned short offset) const; 19: String operator+(const String&); 20: void operator+=(const String&); 21: String & operator= (const String &); 22: 23: // ????? ?????? ??????? 24: unsigned short GetLen() const { return itsLen; } 25: const char * GetString() const { return itsString; } 26: 27: private: 28: String (unsigned short); // ???????? ??????????? 29: char * itsString; 30: unsigned short itsLen; 31: }; 32: 33: // ??????????? ??????????? ??????? ?????? ??????? ????? 34: String::String() 35: { 36: itsString = new char[1]; 382 ?????? 2. ???????? ??????? 37: itsString[0] = '\0'; 38: itsLen=0; 39: } 40: 41: // ???????? ( ??????????????? ) ??????????? , 42: // ???????????? ?????? ???????? ?????? ??? ???????? 43: // ????? ??????????? ????? , ??????????? ???????? null. 44: String::String(unsigned short len) 45: { 46: itsString = new char[len+1]; 47: for (unsigned short i=0; i<=len; i++) 48: itsString[i] = '\0'; 49: itsLen=len; 50: } 51: 52: // ??????????? ?????????? ?????? ? ?????? 53: String::String(const char * const cString) 54: { 55: itsLen = strlen(cString); 56: itsString = new char[itsLen+1]; 57: for (unsigned short i=0; i 59: itsString[itsLen]='\0'; 60: } 61: 62: // ??????????? ????? 63: String::String (const String & rhs) 64: { 65: itsLen=rhs.GetLen(); 66: itsString = new char[itsLen+1]; 67: for (unsigned short i=0; i 69: itsString[itsLen] = '\0'; 70: } 71: 72: // ?????????? , ??????????? ?????????? ?????? 73: String::String () 74: { 75: delete [] itsString; 76: itsLen = 0; 77: } 78: 79: // ???????? ?????????? , ??????????? ???????????? ?????? , 80: // ? ????? ???????? ?????? ? ?? ?????? 81: String& String::operator=(const String & rhs) 82: { 83: if (this == &rhs) 84: return *this; 85: delete [] itsString; 86: itsLen=rhs.GetLen(); 87: itsString = new char[itsLen+1]; 88: for (unsigned short i=0; i 90: itsString[itsLen] = '\0'; 91: return *this; 92: } 93: 94: // ???????????? ???????? ?????????????? , ?????????? ???? 13. ??????? ? ????????? ?????? 383 95: // ?????? ?? ?????? , ??? ??? ?? ????? 96: // ???????? 97: char & String::operator[](unsigned short offset) 98: { 99: if (offset > itsLen) 100: return itsString[itsLen-1]; 101: else 102: return itsString[offset]; 103: } 104: 105: // ?????????? ???????? ?????????????? ??? ????????????? 106: // ? ??????????? ????????? ( ?? ??????????? ????? ) 107: char String::operator[](unsigned short offset) const 108: { 109: if (offset > itsLen) 110: return itsString[itsLen-1]; 111: else 112: return itsString[offset]; 113: } 114: 115: // ??????? ????? ?????? , ???????? ??????? 116: // ?????? ? rhs 117: String String::operator+(const String& rhs) 118: { 119: unsigned short totalLen = itsLen + rhs.GetLen(); 120: String temp(totalLen); 121: unsigned short i; 122: for (i= 0; i 124: for (unsigned short j=0; j 126: temp[totalLen]='\0'; 127: return temp; 128: } 129: 130: // ???????? ??????? ?????? , ?????? ?? ????????? 131: void String::operator+=(const String& rhs) 132: { 133: unsigned short rhsLen = rhs.GetLen(); 134: unsigned short totalLen = itsLen + rhsLen; 135: String temp(totalLen); 136: unsigned short i; 137: for (i=0; i 139: for (unsigned short j=0; j 141: temp[totalLen]='\0'; 142: *this = temp; 143: } 144: 145: int main() 146: { 147: String s1("initial test"); 148: cout << "S1:\t" << s1.GetString() << endl; 149: 150: char * temp = "Hello World"; 151: s1 = temp; 152: cout << "S1:\t" << s1.GetString() << endl; 384 ?????? 2. ???????? ??????? 153: 154: char tempTwo[20]; 155: strcpy(tempTwo,"; nice to be here!"); 156: s1 += tempTwo; 157: cout << "tempTwo:\t" << tempTwo << endl; 158: cout << "S1:\t" << s1.GetString() << endl; 159: 160: cout << "S1[4]:\t" << s1[4] << endl; 161: s1[4]='x'; 162: cout << "S1:\t" << s1.GetString() << endl; 163: 164: cout << "S1[999]:\t" << s1[999] << endl; 165: 166: String s2(" Another string"); 167: String s3; 168: s3 = s1+s2; 169: cout << "S3:\t" << s3.GetString() << endl; 170: 171: String s4; 172: s4 = "Why does this work?"; 173: cout << "S4:\t" << s4.GetString() << endl; 174: return 0; 175: } ????????? S1: initial test S1: Hello World tempTwo: ; nice to be here! S1: Hello World; nice to be here! S1[4]: o S1: Hellx World; nice to be here! S1[999]: ! S3: Hellx World; nice to be here! Another string S4: Why does this work? ?????? Простой класс String объявлен в строках 7—31. Строки 11—13 содержат объявле- ния трех конструкторов: стандартного, конструктора копий и конструктора, которому передают строку стиля C, завершающуюся символом null Чтобы облегчить пользователю работу со строками, класс String перегружает не- сколько операторов, включая оператор индекса ( [] ), оператор плюс ( + ) и оператор присвоения с суммой ( += ). Оператор индекса перегружен дважды: один раз – как по- стоянная функция, возвращающая значение типа char , и второй раз – как непосто- янная функция, возвращающая ссылку на значение типа char Непостоянная версия используется в таких операторах, как S1[4]='x'; (строка 161). Это обеспечивает прямой доступ к любому символу строки. Получив таким об- разом ссылку на символ и вызвав эту функцию, можно изменить его значение. Постоянная версия оператора используется в тех случаях, когда необходимо полу- чить доступ к постоянному объекту класса String , например, в реализации конструк- тора копий (строка 63). Обратите внимание, что rhs[i] доступен, хотя rhs был объяв- лен как const String & . К этому объекту невозможно получить доступ, используя непостоянные функции-члены. Следовательно, оператор индекса необходимо пере- грузить как постоянный. ???? 13. ??????? ? ????????? ?????? 385 Если возвращаемый объект окажется слишком большим, придется вернуть не сам объект, а постоянную ссылку на него. Но поскольку один символ занимает только один байт, нет смысла так поступать. Стандартный конструктор реализован в строках 34—39. Он создает строку нулевой дли- ны. Длина строки в классе String измеряется без учета концевого символа null . Таким образом, строка, созданная по умолчанию, содержит лишь концевой символ null Конструктор копий реализован в строках 63—70. Он устанавливает длину новой строки на единицу больше исходной (дополнительный символ необходим для завер- шающего null ), а затем копирует каждый символ исходной строки во вновь создан- ную и завершает ее символом null В строках 53—60 реализован конструктор, которому передают исходную строку в стиле C (с концевым null ). Этот конструктор подобен конструктору копий. Длина исходной строки вычисляется с помощью функции strlen() из стандартной библиотеки String В строке 28 как закрытая функция-член объявлен еще один конструктор, String(unsigned short) . Таково было намерение автора, чтобы ни один из клиентов этого класса не мог создать строку произвольной длины. Этот конструктор создает стро- ки для внутреннего использования, такие, как, например, operator+= в строке 131. Бо- лее подробная информация об операторе operator+= приведена далее в этой главе. Конструктор String(unsigned short) заполняет все элементы строки нулевым символом ( '\0' ). Поэтому условием выхода из цикла for будет i<=len , а не i не забыты квадратные скобки, иначе вместо всего массива будет удален лишь первый его элемент. Сначала оператор присвоения проверяет, не равна ли строка справа от оператора строке слева. Если это не так, то, удалив прежнюю строку, он создает новую и копи- рует в нее исходную. В качестве результата возвращается ссылка на новую строку, что позволяет осуществить присвоение типа: String1 = String2 = String3; Оператор индекса перегружен дважды (в строках 97—103 и 107—113). И в обоих случаях осуществляется проверка пределов массивов. Если пользователь попытается получить доступ к символу вне пределов массива, то последним возвращаемым сим- волом окажется последний символ массива, т.е. len-1 элемент. В строках 117—127 оператор плюс ( + ) перегружается в оператор конкатенации. Бы- ло бы очень удобно иметь возможность осуществлять конкатенацию строк аналогично простому сложению: String3 = String1 + String2; Для реализации этой возможности функция, заменяющая оператор плюс ( + ), вы- числяет суммарную длину обеих строк и на основании результата создает временную строку temp . Для этого применяется закрытый конструктор, который получает целое число и создает строку, заполненную пустыми символами ( null ). Впоследствии эти пустые символы будут заменены содержимым двух исходных строк. Сначала во вре- менную строку копируется левая исходная строка ( *this ), затем – правая ( rhs ). Оператор суммы (строка 127) возвращает временную строку как значение, которое присваивается строке, расположенной слева от оператора ( string1 ). Оператор += (строки 131—143) работает с уже существующими строками, находящимися слева от оператора string1 += string2 . Он работает аналогично оператору суммы, за исключением того, что временное значение присваивается текущей строке *this = temp (строка 142). Функция main() (строки 145—175) проверяет работоспособность созданного клас- са. В строке 147 создается объект класса String с помощью конструктора, получаю- щего строку в стиле C с пустым символом в конце. Строка 148 выводит на экран ее содержимое, используя функцию доступа GetString() . В строке 150 создается другая 386 ?????? 2. ???????? ??????? строка стиля C. Строка 151 проверяет оператор присвоения, а строка 152 выводит на экран результаты. В строке 154 создается третья строка стиля C – tempTwo . В строке 155 вызов функции strcpy() заполняет буфер символами “ ; nice to be here! ”. Строка 156 вызывает оператор += и добавляет к строке s1 строку tempTwo . Строка 158 выводит результаты на экран. В строке 160 возвращается и выводится на экран пятый символ строки s1 . В строке 161 с помощью оператора индекса ( [] ) ему присваивается новое значение, а в строке 162 на экран выводится результат, демонстрирующий факт внесения изменений. В строке 164 предпринята попытка доступа к символу за пределами массива, но возвращен был лишь последний символ массива, как и было задумано. В строках 166 и 167 создаются еще два объекта класса String , а в строке 168 про- исходит их сложение. Строка 169 выводит результаты на экран. В строке 171 создается новый объект класса String – s4 , вызов оператора при- своения расположен в строке 172, а строка 173 выводит результат на экран. Можно было бы засомневаться: “В строке 21 оператор присвоения определен так, чтобы по- лучать постоянную ссылку на объект класса String , а здесь передается строка в стиле C. Допустимо ли это?” Хоть компилятор и ожидает объект класса String , но, получив символьный мас- сив, он проверяет, можно ли преобразовать его в строку. А в строке 12 как раз объяв- лен конструктор, который создает объекты класса String из символьных массивов. Компилятор создает из символьного массива временную строку и передает ее опера- тору присвоения. Этот процесс известен под названием неявное приведение (implicit casting, или promotion). Если бы не был объявлен соответствующий конструктор для реализации подобной функции, такое присвоение привело бы к ошибке компиляции. Как можно заметить, просмотрев листинг 13.14, созданный класс String получил- ся вполне работоспособным. Его код, правда, достаточно велик, но, к счастью, стан- дартная библиотека C++ предоставляет даже более удобный класс String , которым можно воспользоваться, подключив библиотеку ????????? ?????? ? ?????? ????????? Массивы напоминают лоток для яиц. Это прекрасный контейнер фиксированного размера. Если контейнер слишком велик, то избыток пространства будет растрачен впустую. Если контейнер мал, его не хватит для размещения содержимого. Один из способов решения этой проблемы продемонстрирован в листинге 13.9. Но при использовании больших массивов или при перемещении, удалении и вставке в массив элементов большое количество операций выделения и освобождения памяти может оказаться весьма накладным. Еще одним решением этой проблемы являются связанные списки. Связанный спи- сок – это структура данных, состоящая из небольших контейнеров, способных под- держивать связь с аналогичными контейнерами. Основная мысль состоит в том, что- бы создать класс, который содержит один объект пользовательского типа (например, Cat или Rectangle ) и указатель на следующий контейнер. Таким образом, создан- ный контейнер способен хранить один объект необходимого типа, а также поддержи- вать связь со следующим аналогичным контейнером, что позволяет построить из них цепочку необходимой длины. Связанные списки – это отдельная тема для рассмотрения. Более подробная ин- формация о них содержится в приложении Д, “Связанные списки”. ???? 13. ??????? ? ????????? ?????? 387 ?????? ???????? Использование собственного класса массива вместо стандартного встроенного мас- сива предоставляет множество преимуществ. Во-первых, можно предотвратить воз- можность записи за пределами массива. Во-вторых, можно создать такой класс масси- ва, размер которого будет изменяться динамически: при создании он будет размером в один элемент, а по мере добавления новых приобретет необходимый размер. Элементы массива можно автоматически сортировать и выстраивать в необходи- мом порядке. Кроме того, такой подход позволяет создать целый ряд специальных типов массивов. Наиболее популярными из них являются: |