Библиотека Рефераты Курсовые Дипломы Поиск
Библиотека Рефераты Курсовые Дипломы Поиск
сделать стартовой добавить в избранное
Кефирный гриб на сайте www.za4et.net.ru

Компьютеры, Программирование Компьютеры, Программирование     Программное обеспечение Программное обеспечение

Динамические структуры данных: списки

Ночник-проектор "Звездное небо, планеты", черный.
Оригинальный светильник-ночник-проектор. Корпус поворачивается от руки. Источник света: 1) Лампочка (от карманных фанариков); 2) Три
350 руб
Раздел: Ночники
Совок большой.
Длина 21,5 см. Расцветка в ассортименте, без возможности выбора.
21 руб
Раздел: Совки
Совок №5.
Длина совка: 22 см. Цвет в ассортименте, без возможности выбора.
18 руб
Раздел: Совки

Введение В языках программирования (Pascal, C, др.) существует и другой способ выделения памяти под данные, который называется динамическим. В этом случае память под величины отводится во время выполнения программы. Такие величины будем называть динамическими. Раздел оперативной памяти, распределяемый статически, называется статической памятью; динамически распределяемый раздел памяти называется динамической памятью (динамически распределяемой памятью). Использование динамических величин предоставляет программисту ряд дополнительных возможностей. Во-первых, подключение динамической памяти позволяет увеличить объем обрабатываемых данных. Во-вторых, если потребность в каких-то данных отпала до окончания программы, то занятую ими память можно освободить для другой информации. В-третьих, использование динамической памяти позволяет создавать структуры данных переменного размера. Работа с динамическими величинами связана с использованием еще одного типа данных — ссылочного типа. Величины, имеющие ссылочный тип, называют указателями. Указатель содержит адрес поля в динамической памяти, хранящего величину определенного типа. Сам указатель располагается в статической памяти. Адрес величины — это номер первого байта поля памяти, в котором располагается величина. Размер поля однозначно определяется типом. Далее будем более подробно обсуждать указатели и действия с ними в языке Pascal, примеры будем приводить на Pascal и C. Величина ссылочного типа (указатель) описывается в разделе описания переменных следующим образом:  Var &l ;идентификатор> : ^&l ;имя типа>; Вот примеры описания указателей: ype Mas1 = Array Of I eger; Var  P1 : ^I eger;  P2 : ^S ri g;  Pm : ^Mas1; Здесь P1 — указатель на динамическую величину целого типа; P2 — указатель на динамическую величину строкового типа; Pm — указатель на динамический массив, тип которого задан в разделе ype. Сами динамические величины не требуют описания в программе, поскольку во время компиляции память под них не выделяется. Во время компиляции память выделяется только под статические величины. Указатели — это статические величины, поэтому они требуют описания. Каким же образом происходит выделение памяти под динамическую величину? Память под динамическую величину, связанную с указателем, выделяется в результате выполнения стандартной процедуры EW. Формат обращения к этой процедуре:   EW(&l ;указатель>); Считается, что после выполнения этого оператора создана динамическая величина, имя которой имеет следующий вид:  &l ;имя динамической величины> := &l ;указатель>^ Пусть в программе, в которой имеется приведенное выше описание, присутствуют следующие операторы:   EW(P1); EW(P2); EW(Pm); После их выполнения в динамической памяти оказывается выделенным место под три величины (две скалярные и один массив), которые имеют идентификаторы: P1^, P2^, Pm^ Например, обозначение P1^ можно расшифровать так: динамическая переменная, на которую ссылается указатель P1. Дальнейшая работа с динамическими переменными происходит точно так же, как со статическими переменными соответствующих типов. Им можно присваивать значения, их можно использовать в качестве операндов в выражениях, параметров подпрограмм и пр.

Например, если переменной P1^ нужно присвоить число 25, переменной P2^ присвоить значение символа "Wri e", а массив Pm^ заполнить по порядку целыми числами от 1 до 100, то это делается так:  P1^ := 25;  P2^ := 'Wri e';  For I := 1 o 100 Do Pm^ := I; Кроме процедуры EW значение указателя может определяться оператором присваивания:  &l ;указатель> := &l ;ссылочное выражение>; В качестве ссылочного выражения можно использовать указатель; ссылочную функцию (т.е. функцию, значением которой является указатель); константу il. il — это зарезервированная константа, обозначающая пустую ссылку, т.е. ссылку, которая ни на что не указывает. При присваивании базовые типы указателя и ссылочного выражения должны быть одинаковы. Константу il можно присваивать указателю с любым базовым типом. До присваивания значения ссылочной переменной (с помощью оператора присваивания или процедуры EW) она является неопределенной. Ввод и вывод указателей не допускается. Рассмотрим пример. Пусть в программе описаны следующие указатели:  Var  D, P : ^I eger;   K : ^Boolea ; Тогда допустимыми являются операторы присваивания    D := P; K := il; поскольку соблюдается принцип соответствия типов. Оператор K := D ошибочен, т.к. базовые типы у правой и левой части разные. Если динамическая величина теряет свой указатель, то она становится "мусором". В программировании под этим словом понимают информацию, которая занимает память, но уже не нужна. Представьте себе, что в программе, в которой присутствуют описанные выше указатели, в разделе операторов записано следующее: EW(D); EW(P); {Выделено место в динамической памяти под две целые переменные. Указатели получили соответствующие значения} D^ := 3; P^ := 5; {Динамическим переменным присвоены значения} P := D; {Указатели P и D стали ссылаться на одну и ту же величину, равную 3} Wri eL (P^, D^); {Дважды напечатается число 3} Таким образом, динамическая величина, равная 5, потеряла свой указатель и стала недоступной. Однако место в памяти она занимает. Это и есть пример возникновения "мусора". На схеме показано, что произошло в результате выполнения оператора P := D. В Паскале имеется стандартная процедура, позволяющая освобождать память от данных, потребность в которых отпала. Ее формат:  DISPOSE(&l ;указатель>); Например, если динамическая переменная P^ больше не нужна, то оператор  DISPOSE(P) удалит ее из памяти. После этого значение указателя P становится неопределенным. Особенно существенным становится эффект экономии памяти при удалении больших массивов. В версиях Турбо-Паскаля, работающих под операционной системой MS DOS, под данные одной программы выделяется 64 килобайта памяти (или, если быть точнее, 65520 байт). Это и есть статическая область памяти. При необходимости работать с большими массивами информации этого может оказаться мало. Размер динамической памяти — много больше (сотни килобайт). Поэтому использование динамической памяти позволяет существенно увеличить объем обрабатываемой информации. Следует отчетливо понимать, что работа с динамическими данными замедляет выполнение программы, поскольку доступ к величине происходит в два шага: сначала ищется указатель, затем по нему — величина.

Как это часто бывает, действует "закон сохранения неприятностей": выигрыш в памяти компенсируется проигрышем во времени. Пример. Дан текстовый файл размером не более 64 Кб, содержащий действительные числа, по одному в каждой строке. Переписать содержимое файла в массив, разместив его в динамически распределяемой памяти. Вычислить среднее значение элементов массива. Очистить динамическую память. Создать целый массив размером 10000, заполнить его случайными целыми числами в диапазоне от –100 до 100 и вычислить его среднее значение. {Язык urbo Pascal} Program Sred ee; Co s Max = 10000; ype Diapazo = 1. Max; MasI = Array Of Real; Var PIi : ^MasI ; PReal : ^MasReal; I, Midi : lo gI ; MidReal : Real; : ex ; S : s ri g; Begi Wri e('Введите имя файла: '); ReadL (S); Assig ( , S); Rese ( ); MidReal := 0; MidI := 0; Ra domize; EW(PReal); {Выделение памяти под вещественный массив} {Ввод и суммирование вещественного массива} While o Eof ( ) Do Begi ReadL ( , PReal^ E d; DISPOSE(PReal); {Удаление вещественного массива} EW(PI ); {Выделение памяти под целый массив} {Вычисление и суммирование целого массива} For I := 1 o Max Do Begi PI ^ := -100 Ra dom(201); MidI := MidI PI ^ E d; {Вывод средних значений} Wri eL ('среднее целое равно: ', MidI Div Max); Wri eL ('среднее вещественное равно: ', (MidReal / Max) : 10 : 6) E d. // Язык C #i clude &l ; s dio.h > #i clude &l ; ime.h > #i clude &l ; s dlib.h > #i clude &l ; ios ream.h > #defi e Max 10000 ypedef i MasI ; ypedef floa MasReal; MasI PI ; MasReal PReal; i I, , MidI ; floa MidReal; char S; FILE ; char e dp r; void mai () {     cou &l ;&l ; "Введите имя файла: "; ci >> S;      =fope (S, "r");      MidReal = 0; MidI = 0;      ra domize(); I=0;      / Выделение памяти под вещественный массив /      PReal = (MasReal ) malloc (sizeof(MasReal));      / Ввод и суммирование вещественного массива /      while (!feof( ))       {fge s(S, 255, ); // вводим из файла строку        PReal = s r od(S, &e dp r); // преобразуем введенную строку в вещественное число MidReal = PReal; I ;}      =I 1;      free (PReal); / Удаление вещественного массива /      PI = (MasI ) malloc(sizeof(MasI )); / Выделение памяти под целый массив /      / Вычисление и суммирование целого массива /      for (I=0; I &l ; Max; I )       { PI ;}      / Вывод средних значений /      cou &l ;&l ; " среднее целое равно " &l ;&l ; MidI / double( Max) &l ;&l ; " ";      cou &l ;&l ; "среднее вещественное равно: " &l ;&l ; MidReal / &l ;&l ; " ";      fclose( ); } Списки Обсудим вопрос о том, как в динамической памяти можно создать структуру данных переменного размера. Разберем следующий пример. В процессе физического эксперимента многократно снимаются показания прибора (допустим, термометра) и записываются в компьютерную память для дальнейшей обработки. Заранее неизвестно, сколько будет произведено измерений. Если для обработки таких данных не использовать внешнюю память (файлы), то разумно расположить их в динамической памяти. Во-первых, динамическая память позволяет хранить больший объем информации, чем статическая. А во-вторых, в динамической памяти эти числа можно организовать в связанный список, который не требует предварительного указания количества чисел, подобно массиву.

Часто требуется, чтобы структуры данных меняли свои размеры в ходе решения задачи. Такие структуры данных называются динамическими. К ним относятся стеки, очереди, списки, деревья и др. Описание динамических структур с помощью массивов, записей и файлов приводит к неэкономному использованию памяти ЭВМ и увеличивает время решения задач. Каждая компонента любой динамической структуры представляет собой запись, содержащую, по крайней мере, два поля: одно поле типа «указатель», а второе для размещения данных. В общем случае запись может содержать не один, а несколько указателей и несколько полей данных. Поле данных может быть переменной, массивом, множеством или записью. Если в указующей части содержится адрес одного элемента списка, то список называется однонаправленным (или односвязным). Если же он содержит две компоненты, то двусвязным. Над списками можно проводить различные операции, например: 1)Pдобавление элемента к списку; 2)Pудаление элемента из списка с заданным ключом; 3)Pпоиск элемента с заданным значением ключевого поля; 4)Pсортировка элементов списка; 5)Pделение списка на два и более списков; 6)Pобъединение двух и более списков в один; 7)Pдругие операции

1. Динамические структуры данных: списки

2. Динамические структуры данных: очереди

3. Динамические структуры данных: стеки

4. Динамические структуры данных

5. Динамические структуры данных

6. Разработка алгоритмов и программ выполнения операций над последовательными и связанными представлениями структур данных
7. Структура базы данных
8. Структура и формирование исходных данных, необходимых для расчета параметров технологических схем

9. Структуры данных и алгоритмы

10. Патогенез эндоэкологической болезни и структура заболеваемости жителей г.пущино в динамике с учетом данной экосистемы

11. Структуры Данных и Абстракции Данных

12. Структуры данных

13. Автоматизированная система обработки структур данных

14. Методика создания структуры базы данных на персональном компьютере

15. Структура данных программного комплекса "Q-дерево"

16. Структуры данных и алгоритмы

Глобус географический + политический, с подсветкой "Orion", диаметр 250 мм.
Диаметр: 250 мм. Глобус Земли на подставке с двойной картой и подсветкой. Изготовлен из высококачественного пластика. Может применяться и
2053 руб
Раздел: Глобусы
Игрушка-головоломка "Шар-Лабиринт".
«Шар-лабиринт» - это не только увлекательная, но и развивающая игра, способная улучшить пространственное мышление и внимание, привить
702 руб
Раздел: Головоломки
Настольная игра "Шакал: остров сокровищ".
Стратегическая игра, главная задача которой – найти клад на острове и доставить его на свой корабль. Секрет механики «Шакала» в том, что
1790 руб
Раздел: Классические игры

17. Структуры и организация данных в ЭВМ

18. Динамическое представление данных

19. Неинерциальные полевые принципы формирования структуры материи. Закон динамической гравитации

20. Среда разработки Турбо Паскаль 7.0. Базы данных

21. Елементи та структура програми мови Паскаль

22. Структура и алгоритмы работы спутниковых радионавигационных систем
23. Эволюция, образование и структура Вселенной
24. Анализ медико-биологических данных с использованием Excel и СПП STADIA

25. Структура и состояние водоснабжения и водосброса, подземных вод и артезианских скважин города Киева

26. Подготовка данных и движение по азимутам

27. Статистика населения. Методы анализа динамики и численности и структуры населения

28. Структура транспорта в Европе

29. Экономическая система Дании

30. Минеральный состав, текстуры и структуры руд.

31. Аппарат государственной власти и его структура

32. Движение Сопротивления в Дании и Норвегии

Горшок дорожный и насадка на унитаз "HandyPotty".
Дорожный горшок и насадка на унитаз HandyPotty помогут сделать путешествие еще комфортнее для малыша. Комбинированная модель сочетает в
1128 руб
Раздел: Сиденья
Игра настольная "7 на 9".
Быстрая игра для 2-4 человек. Суть игры в том, что необходимо быстро считать в уме и ещё быстрее действовать — бросать подходящую карту,
390 руб
Раздел: Игры в дорогу
Бумага упаковочная "Путешествие", 70x100 см, 10 листов.
Упаковочная бумага — одна из важнейших деталей презента. Подарочная упаковка с оригинальным дизайном с легкостью дополнит всю прелесть
487 руб
Раздел: Прочие

33. Социально-экономическая структура Верхнеудинска в феодальный период (середина XVII в.- 1862 год)

34. Структура органов власти в США по конституции 1787 года

35. Двухпалатная структура Федерального Собрания

36. Отчет по учебно-ознакомительной практике (c правовыми основами местного самоуправления, формированием представительных и исполнительных органов власти, структурой и функциями органов местного самоуправления)

37. Понятие и структура компетенции местного самоуправления

38. Автоматизированные информационные технологии формирования, обработки и представления данных в налоговой службе
39. Налоги, их состав и структура
40. Понятие права и правовой нормы. Виды и структура правовой нормы. Понятие и виды юридической ответственности

41. Понятие, структура и методики построения страховых тарифов

42. Структура правовых норм

43. Структура и функции государственного аппарата

44. Сравнительное описание слоговых структур английского и каракалпакского языков

45. Культура, её структура и функции

46. Структура и организация учебного процесса в средневековом университете (Болонья, Париж, Прага)

47. Судьба и творчество Даниила Хармса

48. Проблематика и структура пьесы Б. Шоу "Пигмалион"

Чудо трусики для плавания, от 0 до 3-х лет, трехслойные, арт. 1433, для девочек.
Детские специальные трусики для плавания в бассейне и открытом водоеме. Плотно прилегают, отлично защищают! Изготовлены из хлопка, имеют
376 руб
Раздел: Многоразовые
Шторка антимоскитная ТД7-002.
Размеры: 100х220 см. Препятствует проникновению насекомых. Не нарушает естественную циркуляцию воздуха. Подходит для любых типов дверных
372 руб
Раздел: Сетки противомоскитные
Пеленки одноразовые впитывающие BabyMil "Эконом" (60х40 см, 30 штук).
Пеленка разработана специально для малышей. Изделие изготовлено из допущенных Роспотребнадзором материалов. Оно позволяет коже
350 руб
Раздел: Пелёнки

49. Бальзак: структура и основные идеи "Человеческой комедии"

50. Сравнительное описание слоговых структур английского и каракалпакского языков

51. Даниил Галицкий и его внутренняя и внешняя политика (Данило Галицький - його внутрЁшня та зовнЁшня полЁтика)

52. Методы компьютерной обработки статистических данных

53. Основные компоненты систем управления документооборотом. Фрейм: его структура и понятие

54. Интернет: административное устройство и структура глобальной сети
55. Построение сети передачи данных
56. Управление потоками данных в параллельных алгоритмах вычислительной линейной алгебры

57. Оценка методов и средств обеспечения безошибочности передачи данных в сетях

58. Системы и сети передачи данных

59. Структура персонального компьютера. Основные и периферийные устройства, их характеристики и назначение

60. Интерфейсные БИС, параллельный и последовательный в/в, сопроцессор в/в, наиболее известные БИС, Модемы, протоколы обменами данных

61. Организация и применение микропроцессорных систем обработки данных и управления

62. Сжатие данных

63. Анализ структур, характеристик и архитектур 32-разрядных микропроцессоров

64. Формирование структуры электронного учебника и решение задач на ней

Подарочная расчёска для волос "Алена".
Стильная детская расчёска дарит радость и комфорт. Этот практичный аксессуар по достоинству оценят как маленькие модницы, так юные
372 руб
Раздел: Расчески, щетки для волос
Блокнот "Дневник совы".
Дневник магических секретов с 3D обложкой! Блокнот "Дневник совы" - это оригинальная записная книжка, которая придется по душе
733 руб
Раздел: Блокноты художественные
Набор профессиональных фломастеров Edding "E-1880/4S" (0.25, 0.35, 0.5, 0.7 мм) 4 штуки.
Используется для технического и художественного черчения, эскизов и тонкого письма. Круглый наконечник в металлической оправе. Не
393 руб
Раздел: До 6 цветов

65. Различные классы баз данных по предметным областям использования

66. Принципы проектирования и использования многомерных баз данных

67. Проектирование устройства сбора данных

68. Построение информационной и даталогической моделей данных

69. Разработка базы данных `ДЕКАНАТ` в среде программирования "Delphi"

70. База данных "Домашняя библиотека"
71. Современные системы управления базами данных
72. Анализ пакетов обработки экспериментальных данных SABR и BOOTSTRAP

73. Разработка базы данных, отражающей учет успеваемости студентов

74. Разработка базы данных "Кадры"

75. Лекции по теории проектирования баз данных (БД)

76. Разработка базы данных

77. Fox Pro - реляционная модель данных

78. Система управления базами данных ACCESS

79. База данных - Бактериологическая испытательная лаборатория Боханского района

80. Моделирование структуры книги

Стул детский "Ника" складной, моющийся (цвет: синий, рисунок: горошек).
Особенности: - стул складной; - предназначен для детей от 3 до 7 лет; - металлический каркас; - на ножках стула установлены пластмассовые
562 руб
Раздел: Стульчики
Настольная игра "Кот на крыше".
Настольная игра «Кот на крыше» соберет всю семью за столом. С ней вечер пройдет незаметно и крайне увлекательно. Правила просты: нужно
458 руб
Раздел: Игры на ловкость
Карандаши цветные "Kolores", 24 цвета.
Карандаши цветные, трехгранные, заточенные. В комплекте: точилка. Длина карандаша: 175 мм Толщина грифеля: 2,9 мм. Количество цветов: 24.
403 руб
Раздел: 13-24 цвета

81. Разработка приложений на языке VBA в среде MS EXCEL по обработке данных для заданных объектов

82. Обработка данных о студентах

83. Инструкция по эксплуатации базы данных магазина «Телевизоры» средствами Access 2000

84. Системы обработки информации - язык баз данных SQL со средствами поддержания целостности

85. Структура и программирование ПЛИС фирмы Altera в САПР Quartus II, её применение в лабораторном стенде

86. Обзор ситуации с внедрением автоматизированных банковских систем в финансовых структурах России
87. HTML и базы данных
88. Работа в среде EXCEL. Средства управления базами данных в EXCEL

89. Структура сходящихся последовательностей

90. Применение алгоритма RSA для шифрования потоков данных

91. Структура аффинного пространства над телом

92. Исследование регрессии на основе численных данных

93. Общие данные о нервной системе

94. Структура арбитражных судов

95. Взяточничество и коррупция в деятельности преступных структур (сообществ)

96. Федеральная служба Российской Федерации по контролю за оборотом наркотических средств и психотропных веществ: система и структура, основные полномочия

Ручка-стилус шариковая сувенирная "Никита".
Перед Вами готовый подарок в стильной упаковке — шариковая ручка со стилусом. Она имеет прочный металлический корпус, а именная надпись
415 руб
Раздел: Металлические ручки
Конструктор электронный ЗНАТОК "Первые шаги в электронике. Набор В" (15 схем).
Вам будет предложено собрать свой первый светодиодный фонарик, собрать звуковые схемы, познакомится с работой транзистора — всего 15
892 руб
Раздел: Инженерные, научно-технические
Глобус ландшафтный, диаметр 320 мм.
Глобус для занятий по географии на подставке. Компактен и нагляден. Дает представление о строении поверхности Земли. На глобусе нанесено
880 руб
Раздел: Глобусы

97. Влияние экологических и медико-биологических требований на структуру исследований и разработок

98. Биосфера и её структура

99. Структура педагогических способностей преподавателя

100. Научная педагогическая деятельность Даниила Борисовича Эльконина


Поиск Рефератов на сайте za4eti.ru Вы студент, и у Вас нет времени на выполнение письменных работ (рефератов, курсовых и дипломов)? Мы сможем Вам в этом помочь. Возможно, Вам подойдет что-то из ПЕРЕЧНЯ ПРЕДМЕТОВ И ДИСЦИПЛИН, ПО КОТОРЫМ ВЫПОЛНЯЮТСЯ РЕФЕРАТЫ, КУРСОВЫЕ И ДИПЛОМНЫЕ РАБОТЫ. 
Вы можете поискать нужную Вам работу в КОЛЛЕКЦИИ ГОТОВЫХ РЕФЕРАТОВ, КУРСОВЫХ И ДИПЛОМНЫХ РАБОТ, выполненных преподавателями московских ВУЗов за период более чем 10-летней работы. Эти работы Вы можете бесплатно СКАЧАТЬ.