рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

ЛАБОРАТОРНАЯ РАБОТА N 7

ЛАБОРАТОРНАЯ РАБОТА N 7 - раздел Программирование, Программирование алгоритмов сортировки массивов Операции Над Списковыми Структурами   1.принципы Реали...

Операции над списковыми структурами

 

1.Принципы реализации динамических структур данных

 

Линейный список является примером динамической структуры данных, т.е. такой, которая формируется в процессе выполнения программы. Каждый элемент линейной структуры имеет свой порядковый номер в этой структуре, и для каждого элемента, кроме первого, существует предыдущий элемент с номером, на единицу меньшим, и для каждого элемента, кроме последнего, существует последующий элемент с номером, на единицу б’ольшим. Такая линейная упорядоченность в динамической структуре организуется с помощью дополнительного поля, которое, помимо некоторого количества информационных полей, присутствует в каждом элементе списка, и которое содержит указатель, или адрес, следующего элемента линейной структуры. В C-программе описание такой структуры выполняется по схеме:

 

struct listrec{

<тип1> info1; //информационные

. . .

<типn>infon; //поля

listrec *link; //поле указателя

};

Динамический линейный список является примером структуры с последовательным доступом. Он задается указателем (т.е., с использованием вышеприведенных обозначений, - переменной-указателем на данные типа listrec) на первый элемент списка, и для того, чтобы получить доступ к i-ому элементу, необходимо последовательно просмотреть i-1 элементов списка, начиная с первого:

base=first;

for( j=1; j<= i-1; j++)

base=base->link;

Приведенный фрагмент программы подразумевает, что переменные base и first имеют тип: listrec *first, *base ; и в переменной first содержится адрес первого элемента списка. Результатом выполнения фрагмента является значение переменной base - адрес i-го элемента списка.

Формирование элементов динамической структуры выполняется в два действия: отведение памяти для элемента и заполнение отведенной памяти некоторыми значениями. Первое действие выполняется оператором: <указатель>=new <тип>. Результатом его выполнения является выделение из динамической области фрагмента памяти, объем которого определяется типом, указанным после new, а адрес выделенного фрагмента будет помещен в переменную-указатель. Полученное значение, таким образом, следует поместить в поле link предыдущего по отношению к формируемому элемента списка. В поле link последнего элемента списка следует поместить «пустой» адрес, который обозначается зарезервированным словом NULL. Заполнение остальных (информационных) полей элемента списка осуществляется в соответствии с назначением списка в конкретной задаче и алгоритмом ее решения. При этом доступ к полю организуется через указатель на элемент списка, например:

base->info1=<значение типа <тип 1>>;

если base содержит адрес формируемого элемента списка.

Нижеприведенная программа формирует линейный список из последовательности записей текстового файла.

void main()

{

struct list{ //тип элемента списка

char *inf;

list *link;

}

FILE *f;

list *first, *base, *r;

f=fopen(”file.txt”,”r”); //файл с данными для списка

first=new list; //отведение памяти для первого элемента списка

base=first; r=base;

while( !feof(f)) {

base->inf=new char [5]; // заполнение информационного

fgets(base->inf,5,f,); // поля элемента списка

base->link=new list; //отведение памяти для очередного элемента и заполнение //поля указателя предыдущего элемента списка

r=base;

base=base->link; //перемещение текущего указателя на следующий элемент списка

};

delete base; //освобождение напрасно отведенной памяти

 

if (r!=first ) r->link=NULL; else first=NULL; //заполнение поля указателя последнего

//элемента списка

}

 

2.Задание на лабораторную работу

 

Написать программу построения линейной списковой структуры, содержащей данные символьного типа, а также процедуру, реализующую в соответствии с вариантом задания одну из операций над списковой структурой.

1.Включение в список новой записи после записи с заданным номером k.

2.Удаление из списка записи с заданным номером k.

3.Обмен данными записей с заданными номерами k и l.

4.Включение в список новой записи после записи с заданным значением поля данных.

5.Удаление из списка записи с заданным значением поля данных.

6.Разбиение списка на два списка одинаковой длины (+-1).

7.Изменение порядка следования записей в списке на противоположный.

8.Объединение двух заданных списков в один.

9.Построение копии заданного списка.

10.Преобразование заданного линейного списка в кольцевой с указателем на первую запись, имевшую в линейном списке номер k.

 

– Конец работы –

Эта тема принадлежит разделу:

Программирование алгоритмов сортировки массивов

Государственное образовательное учреждение... Высшего профессионального образования... Санкт Петербургский государственный университет...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: ЛАБОРАТОРНАЯ РАБОТА N 7

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Санкт-Петербург
Составители: Т.М.Максимова   Рецензент: В.П.Попов     В методические указания включены краткие теоретические сведения, необходимые д

ОБЩИЕ ТРЕБОВАНИЯ К СОДЕРЖАНИЮ ОТЧЕТОВ
  В методические указания включены задания на 8 лабораторных работ, содержанием которых является разработка программы на языке С. Процесс разработки программы студент должен отразить

Текст программы
  void sort(int *a, char n) //функция сортировки n первых элементов (n<=100) массива a { bool f=true; //признак выполнения операции обмена char

ЛАБОРАТОРНАЯ РАБОТА N 1
Встроенные типы данных   1. Основные типы данных Язык С поддерживает несколько базовых типов данных, которые также называют простыми. Перечислим некоторые из них.

ЛАБОРАТОРНАЯ РАБОТА N 2
Программирование операций ввода-вывода   1.Некоторые библиотечные функции для работы с файлами   Функции файлового ввода-вывода используют указатель фа

ЛАБОРАТОРНАЯ РАБОТА № 3
Целочисленная арифметика   1. Введение в постановку задачи 1.1. Позиционные системы счисления При записи числа в позиционной системе счисления вклад каждой

ЛАБОРАТОРНАЯ РАБОТА № 4
Вещественная арифметика   1. Генератор псевдослучайных чисел   Для многих задач программирования, связанных с математическими моделями случайных явлени

ЛАБОРАТОРНАЯ РАБОТА № 5
Операции над многословными операндами   1. Многословные операнды   Арифметические выражения в языке C представляют собой формулы для вычисления значени

ЛАБОРАТОРНАЯ РАБОТА N 6
Работа со структурами   1 Понятие табличной структуры данных   Таблицей называется структура данных, элементы которой представляют собой записи, состоя

ЛАБОРАТОРНАЯ РАБОТА N 8
Шаблоны функций   1.Перегрузка и шаблоны функций   В одной программе может быть размещено несколько функций с одним и тем же именем, если списки формал

БИБЛИОГРАФИЧЕСКИЙ СПИСОК
  1. Вирт Н. Алгоритмы и структуры данных. - М.: Мир,1989. - 360с. 2. Карпов Б., Баранова Т. С++: Специальный справочник. – СПб.: Питер, 2001. – 480с. 3. Кнут Д. Иск

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги