Линейный однонаправленный список - раздел Философия, Конспект лекций по курсу Алгоритмические языки и программирование Основы языка С++ Описание Простейшего Элемента Такого Списка Выглядит Следующим Образом:
...
Описание простейшего элемента такого списка выглядит следующим образом:
struct имя_типа
{
информационное поле;
адресное поле;
};
Информационное поле – это поле любого, ранее объявленного или стандартного, типа;
адресное поле – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес следующего элемента списка.
Информационных полей может быть несколько.
Примеры.
1. struct Node
{
int key;//информационное поле
Node*next;//адресное поле
};
2. struct point
{
char*name;//информационное поле
int age;//информационное поле
point*next;//адресное поле
};
Каждый элемент списка содержит ключ, который идентифицирует этот элемент. Ключ обычно бывает либо целым числом (пример 1), либо строкой (пример 2).
Над списками можно выполнять следующие операции:
- начальное формирование списка (создание первого элемента);
- добавление элемента в конец списка;
- добавление элемента в начало списка;
- удаление элемента с заданным номером;
- чтение элемента с заданным ключом;
- вставка элемента в заданное место списка (до или после элемента с заданным ключом);
- упорядочивание списка по ключу
и др.
Пример1. Создание и печать однонаправленного списка
#include <iostream.h>
#include<string.h>
//описание структуры
struct point
{char *name;//информационное поле
int age;//информационное поле
point*next;//адресное поле
};
point* make_point()
//создание одного элемента
{
point*p=new(point);//выделить память
char s[20];
cout<<"
Enter the name:";
cin>>s;
p->name=new char[strlen(s)+1];//выделить память под динамическую строку символов
strcpy(p->name,s);//записать информацию в строку символов
cout<<"
Enter the age";
cin>>p->age;
p->next=0;//сформировать адресное поле
return p;
}
void print_point(point*p)
//печать информационных полей одного элемента списка
{
cout<<"
NAME:"<<p->name;
cout<<"
AGE:"<<p->age;
cout<<"
--------------------------------
";
}
point* make_list(int n)
//формирование списка из n элементов
{
point* beg=make_point();//сформировать первый элемент
point*r;
for(int i=1;i<n;i++)
{
r=make_point();//сформировать следующий элемент
//добавление в начало списка
r->next=beg;//сформировать адресное поле
beg=r;//изменить адрес первого элемента списка
}
return beg;//вернуть адрес начала списка
}
int print_list(point*beg)
//печать списка, на который указывает указатель beg
{
point*p=beg;//р присвоить адрес первого элемента списка
int k=0;//счетчик количества напечатанных элементов
while(p)//пока нет конца списка
{
print_point(p);//печать элемента, на который указывает элемент p
p=p->next;//переход к следующему элементу
k++;
}
return k;//количество элементов в списке
}
void main()
{
int n;
cout<<"
Enter the size of list";
cin>>n;
point*beg=make_list(n);//формирование списка
if(!print_list(beg)) cout<<"
The list is empty";}//печать списка
Пример 2. Удаление из однонаправленного списка элемента с номером k (рис 5.).
Рис. 5. Удаление элемента с номером k из однонаправленного списка
point*del_point(point*beg,int k)
//удаление элемента с номером к
{
point*p=beg,//поставить вспомогательную переменную на начало списка
*r;//вспомогательная переменная для удаления
int i=0;//счетчик элементов в списке
if(k==0)
{//удалить первый элемент
beg=p->next;
delete[]p->name;//удалить динамическое поле name
delete[]p;//удалить элемент из списка
return beg;//вернуть адрес первого элемента списка
}
while(p)//пока нет конца списка
{
if(i==k-1)//дошли до элемента с номером k-1, чтобы поменять его поле next
{//удалить элемент
r=p->next;//поставить r на удаляемый элемент
if(r)//если p не последний элемент
{
p->next=r->next;//исключить r из списка
delete[]r->name;//удалить динамическое поле name
delete[]r;//удалить элемент из списка
}
else p->next=0;//если p -последний элемент, то в поле next присвоить NULL
Пермский Государственный технический университет... Кафедра информационных технологий и автоматизированных... Викентьева О Л...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Линейный однонаправленный список
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Алгоритм и программа
Алгоритм – точное предписание, определяющий вычислительный процесс, идущий от изменяемых начальных данных к конечному результату, т. е. это рецепт достижения какой-либо цели.
Свойства алгоритма
1. Массовость: алгоритм должен применяться не к одной задаче, а к целому классу подобных задач (алгоритм для решения квадратного уравнения должен решать не одно уравнение, а все квадратные уравнени
Языки программирования
Разные типы процессоров имеют разный набор команд. Если язык программирования ориентирован на конкретный тип процессора и учитывает его особенности, то он называется языком программирования низкого
Состав языка
В тексте на любом естественном языке можно выделить четыре основных элемента: символы, слова, словосочетания и предложения. Алгоритмический язык также содержит такие элементы, только слова называют
Тип int
Значениями этого типа являются целые числа.
Размер типа int не определяется стандартом, а зависит от компьютера и компилятора. Для 16-разрядного процессора под него отводится 2 байта, для
Переменные
Переменная в СИ++ - именованная область памяти, в которой хранятся данные определенного типа. У переменной есть имя и значение. Имя служит для обращения к области памяти, в которой хранится значени
Выражения
Из констант, переменных, разделителей и знаков операций можно конструировать выражения. Каждое выражение представляет собой правило вычисления нового значения.. Если выражение формирует целое или в
Ввод и вывод данных
В языке Си++ нет встроенных средств ввода и вывода – он осуществляется с помощью функций, типов и объектов, которые находятся в стандартных библиотеках. Существует два основных способа: функции уна
Базовые конструкции структурного программирования
В теории программирования доказано, что программу для решения задачи любой сложности можно составить только из трех структур: линейной, разветвляющейся и циклической. Эти структуры называются базов
Программирование арифметических циклов.
Для арифметического цикла заранее известно сколько раз выполняется тело цикла.
Задача №2
Дана последовательность целых чисел из n элементов. Найти среднее арифметическое этой посл
Итерационные циклы
Для итерационного цикла известно условие выполнения цикла.
Задача №5
Дана последовательность целых чисел, за которой следует 0. Найти минимальный элемент этой последовательности.
Массивы
В языке Си/Си++ ,кроме базовых типов, разрешено вводить и использовать производные типы, полученные на основе базовых. Стандарт языка определяет три способа получения производных типов:
-
Формирование псевдодинамических массивов
При описании массива в программе надо обязательно указывать количество элементов массива для того, чтобы компилятор выделил под этот массив нужное количество памяти. Это не всегда бывает удобно, т.
Найти максимальный элемент массива.
#include<iostream.h>
#include<stdlib.h>
void main()
{
int a[100];
int n;
cout<<”
Enter the size of array:”;cin>>n;
Сортировка методом простого включения (вставки)
Элементы массива делятся на уже готовую последовательность и исходную. При каждом шаге, начиная с I=2, из исходной последовательности извлекается I-ый элемент и вставляется на нужное место готовой
Поиск в отсортированном массиве
В отсортированном массиве используется дихотомический (бинарный) поиск. При последовательном поиске требуется в среднем n/2 сравнений, где n – количество элементов в массиве. При дихотомическом пои
Понятии указателя
Указатели являются специальными объектами в программах на Си++. Указатели предназначены для хранения адресов памяти.
Пример: Когда компилятор обрабатывает оператор определения переменной,
Динамические переменные
Все переменные, объявленные в программе размещаются в одной непрерывной области памяти, которую называют сегментом данных (64К). Такие переменные не меняют своего размера в ходе выполнения программ
Одномерные массивы и указатели
При определении массива ему выделяется память. После этого имя массива воспринимается как константный указатель того типа, к которому относятся элементы массива. Исключением является использовании
Многомерные массивы и указатели
Многомерный массив это массив, элементами которого служат массивы. Например, массив с описанием int a[4][5] – это массив из 4 указателей типа int*, которые содержат адреса одномерных массивов из 5
Динамические массивы
Операция new при использовании с массивами имеет следующий формат:
new тип_массива
Такая операция выделяет для размещения массива участок динамической памяти соответствующего разм
Символьная информация и строки
Для символьных данных в Си++ введен тип char. Для представления символьной информации используются символы, символьные переменные и текстовые константы.
Примеры:
const char c=’c’;
Объявление и определение функций
Функция – это именованная последовательность описаний и операторов, выполняющая законченное действие, например, формирование массива, печать массива и т. д.
Функция, во-первых, является од
Прототип функции
Для того, чтобы к функции можно было обратиться, в том же файле должно находиться определение или описание функции (прототип).
double line(double x1,double y1,double x2,double y2);
Параметры функции
Основным способом обмена информацией между вызываемой и вызывающей функциями является механизм параметров. Существует два способа передачи параметров в функцию: по адресу и по значению.
Локальные и глобальные переменные
Переменные, которые используются внутри данной функции, называются локальными. Память для них выделяется в стеке, поэтому после окончания работы функции они удаляются из памяти. Нельзя возвращать у
Передача одномерных массивов как параметров функции
При использовании массива как параметра функции, в функцию передается указатель на его первый элемент, т. е. массив всегда передается по адресу. При этом теряется информация о количестве элементов
Передача многомерных массивов в функцию
При передаче многомерных массивов в функцию все размерности должны передаваться в качестве параметров. По определению многомерные массивы в Си и СИ++ не существуют. Если мы описываем массив с неско
Функции с начальными (умалчиваемыми) значениями параметров
В определении функции может содержаться начальное (умалчиваемое) значение параметра. Это значение используется, если при вызове функции соответствующий параметр опущен. Се параметры, описанные спра
Подставляемые (inline) функции
Некоторые функции в СИ++ можно определить с использованием служебного слова inline. Такая функция называется подставляемой или встраиваемой.
Например:
inline float Line(float x1,f
Функции с переменным числом параметров
В СИ++ допустимы функции, у которых при компиляции не фиксируется число параметров, и , кроме того может быть неизвестен тип этих параметров. Количество и тип параметров становится известным только
Перегрузка функций
Цель перегрузки состоит в том, чтобы функция с одним именем по-разному выполнялась и возвращала разные значения при обращении к ней с различными типами и различным числом фактических параметров. Дл
Шаблоны функций
Шаблоны вводятся для того, чтобы автоматизировать создание функций, обрабатывающих разнотипные данные. Например, алгоритм сортировки можно использовать для массивов различных типов. При перегрузке
Указатель на функцию
Каждая функция характеризуется типом возвращаемого значения, именем и списком типов ее параметров. Если имя функции использовать без последующих скобок и параметров, то он будет выступать в качеств
Структуры
Структура – это объединенное в единое целое множество поименованных элементов данных. Элементы структуры (поля) могут быть различного типа, они все должны иметь различные имена.
Форматы оп
Объединения
Объединение (union)- это частный случай структуры. Все поля объединения располагаются по одному и тому же адресу. Длина объединения равна наибольшей из длин его полей. В каждый момент времени в так
Динамические структуры данных
Во многих задачах требуется использовать данные, у которых конфигурация, размеры и состав могут меняться в процессе выполнения программы. Для их представления используют динамические информационные
Потоковый ввод-вывод
На уровне потокового ввода-вывода обмен данными производится побайтно, т. е. за одно обращение к устройству (файлу) производится считывание или запись фиксированной порции данных (512 или 1024 байт
Открытие и закрытие потока
Прежде, чем начать работать с потоком, его надо инициировать, т. е. открыть. При этом поток связывается со структурой предопределенного типа FILE, определение которой находится в файле <stdio.h&
Символьный ввод-вывод
Для символьного ввода-вывода используются функции:
- int fgetc(FILE*fp), где fp – указатель на поток, из которого выполняется считывание. Функция возвращает очередной символ в форме int из
Строковый ввод-вывод
Для построчного ввода-вывода используются следующие функции:
1) char* fgets(char* s,int n,FILE* f), где
char*s – адрес, по которому размещаются считанные байты,
int n – к
Блоковый ввод-вывод
Для блокового ввода-вывода используются функции:
1) int fread(void*ptr,int size, int n, FILE*f), где
void*ptr – указатель на область памяти, в которой размещаются считанные из фай
Форматированный ввод-вывод
В некоторых случаях информацию удобно записывать в файл без преобразования, т. е. в символьном виде пригодном для непосредственного отображения на экран. Для этого можно использовать функции формат
Прямой доступ к файлам
Рассмотренные ранее средства обмена с файлами позволяют записывать и считывать данные только последовательно. Операции чтения/записи всегда производятся, начиная с текущей позиции в потоке. Начальн
Удаление и добавление элементов в файле
Пример 1:
void del(char *filename)
{
//удаление записи с номером х
FILE *f, *temp;
f=fopen(filename,”rb”);//открыть исходный файл для чтения
te
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов