LAB9
.RTF
Л а б о р а т о р н а я р а б о т а N 9
Организация списков с помощью
указателей и структур
Список - это последовательность элементов, в которой каждый
элемент содержит ссылку на следующий. Последний элемент содержит
нулевую (пустую) ссылку. Доступ к списку обеспечивается с помощью
указателя списка, ссылающегося на первый элемент списка. Таким об-
разом, каждый элемент списка состоит из двух полей - поля информа-
ции и поля ссылки (рис.1).
0
/ / \ ... /
Указатель поле поле нулевая
списка информации ссылки ссылка
Рис.1. Cписок.
На языке Си список организуется с помощью указателей и струк-
тур или же с помощью параллельных массивов.
Рассмотрим организацию списков с помощью структур и указате-
лей.
Структура используется, когда нужно логически объединить дан-
ные разных типов. В данном случае в виде структуры описывается
элемент списка, состоящий из двух полей разных типов. Указатель
списка и поле ссылки на следующий элемент описываются как перемен-
ные типа указатель на структуру. Например:
/* описание списка идентификаторов */
struct el_sp /* тип элемента списка */
{ char id[9], /* идентификатор */
struct el_sp *sled; /* ссылка на след. элемент */
};
struct el_sp *p; /* указатель списка */
Здесь p - это переменная типа указатель на структуру типа
el_sp. Обратите внимание: el_sp - это не переменная, а имя типа
структуры, память для элемента списка здесь не выделяется.
Чтобы выделить память для очередного элемента списка, нужно
вызвать функцию malloc(). Аргументом этой функции является размер
памяти в байтах, а возвращает она адрес выделенного участка памяти
(при использовании этой функции нужно включать файл stdlib.h). На-
пример, оператор присваивания
p = malloc (sizeof(struct el_sp));
выделяет память для первого элемента списка и устанавливает указа-
тель p. Операция sizeof(el_sp) определяет размер памяти в байтах
для структуры типа el_sp. Функция malloc выделяет требуемый объем
памяти и возвращает адрес этого блока памяти, который присваивает-
ся указателю p.
Освобождение памяти при удалении элемента из списка осущест-
вляется функцией free(), где аргументом должен быть указатель на
элемент списка, например, free(p).
Доступ к отдельным полям структуры, на которую ссылается ука-
затель, осуществляется с помощью операции ->. Например, для приве-
денного выше списка идентификаторов
p -> id - это поле id (идентификатор) 1-го элемента списка, а
p ->sled - это поле sled 1-го элемента, т.е. ссылка на 2-й эл-т
списка.
Пустая ссылка обозначается константой NULL. Например, оператор
p = NULL;
означает, что указатель списка ни на что не будет ссылаться, т.е.
список становится пустым. Поле ссылки последнего элемента списка
должно иметь значение NULL.
Пример.
Задача. Дана последовательность из n идентификаторов. Длина
каждого идентификатора не более 8 символов. Напечатать идентифика-
торы в лексикографическом порядке.
Пример теста.
Исх.посл-ть: Результат:
SIMV A
X A1
A1 SIMV
SL SL
Z20 TEXT
A X
TEXT Z20
Задачу можно решить, сцепляя идентификаторы в список в лекси-
кографическом порядке по мере их ввода. В приведенной ниже про-
грамме после чтения очередного идентификатора сразу происходит до-
бавление его в список, сформированный из предшествующих идентифи-
каторов. На рис.2 показано, как изменяется список в процессе вклю-
чения в него очередных идентификаторов.
0
0
SIMV
P
----------
0
0
0
0
X
X
SIMV
P SIMV ¦ -
-------+---
A1
0
X
SIMV
A1
P ¦ 0
0
SL
X
A1
SIMV
P ¦ -+->¦ S -+->¦ X ¦
. . .
SL
SIMV
A1
A
p
0
Z20
X
TEXT
Рис.2. Пример процесса формирования списка идентификаторов.
Еще несколько пояснений к программе. Идентификаторы поочередно
вводятся в массив t_id с помощью функции gets(), которая символ
перевода строки заменяет на признак конца строки "нуль-символ"
('\0'). Сравнение двух идентификаторов производится с помощью
функции strcmp(), которая возвращает значение 0, если идентифика-
торы равны, и разность кодов двух соответствующих несовпавших сим-
волов, если идентификаторы не равны. Значит, значение функции бу-
дет < 0, если первый идентификатор в лексикографическом порядке
должен следовать раньше второго, и значение будет > 0 в противном
случае.
Функция strcpy() служит для копирования строк символов, имеет
два аргумента: указатель на строку, куда копировать, и указатель
на строку, откуда копировать.
Функция puts() выводит строку символов, заканчивающуюся '\0'.
Аргументом ее должен быть указатель на строку символов. После вы-
вода курсор на экране перемещается на новую строку.
Программа:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#define MAXDL 9 /* макс.длина ид-ра (строки символов с
признаком конца '\0' ) */
struct el_sp /* элемент списка */
{ char id [MAXDL]; /* идентификатор */
struct el_sp *sled; /* ссылка на следующий элемент */
};
/*----------------------------------------------------------*/
/* функция включения очередного идентификатора в список */
/*----------------------------------------------------------*/
void vkl ( struct el_sp **p, char t_id[] )
/* Вх. данные: *p - указатель списка идентификаторов в
лексикографическом порядке,
t_id - включаемый в список (текущий) ид-р */
/* Вых. данные: *p */
{ struct el_sp *pt, /* указатель включаемого эл-та */
*k,*j; /* указатели очередного и предыдущего
элементов списка */
/* выделение памяти для нового эл-та списка */
pt=malloc(sizeof(struct el_sp));
strcpy(pt->id,t_id);
if (*p==NULL || strcmp(pt->id,(*p)->id)<0)
{ /* включение ид-ра в начало списка */
pt->sled=*p; *p=pt;
}
else
{ /* поиск элемента списка, после которого нужно
включить идентификатор */
k=*p;
while (k!=NULL && strcmp(pt->id,k->id)>=0)
{ j=k; k=k->sled; }
/* включение эл-та *pt после элемента *j */
j->sled=pt; pt->sled=k;
}
}
/*----------------------------------------------------------*/
/* функция печати списка */
/*----------------------------------------------------------*/
void pech_sp ( struct el_sp *p )
/* Вх. данные: p - указатель начала списка */
{ struct el_sp *i; /* указатель текущего элемента списка */
printf ("\nРезультат:\n");
for ( i=p; i!=NULL; i=i->sled )
puts (i->id);
}
/*------------------------------------------------*/
/* О С Н О В Н А Я П Р О Г Р А М М А */
/*------------------------------------------------*/
main()
{ struct el_sp *p; /* указатель начала списка */
unsigned n ; /* количество идентификаторов */
unsigned i ; /* параметр цикла */
char t_id[MAXDL]; /* текущий идентификатор */
printf ("\nВведите число идентификаторов\n n=");
scanf ("%u",&n);
getchar(); /* пропуск символа "перевод строки" */
p=NULL; /* список пока пуст */
printf ("Введите идентификаторы ");
printf ("(после каждого нажимайте клавишу <Enter> )\n");
for ( i=1; i<=n; i++ )
{ gets (t_id);
vkl (&p,t_id); /* включение ид-ра в список */
}
pech_sp (p); /* печать списка */
printf ("\n\nДля завершения нажмите любую клавишу\n");
getch();
}
Задания.
Дан список идентификаторов. Длина каждого идентификатора не более 8 символов. Идентификаторы в списке расположены в лексикографическом порядке. Составить функции (подпрограммы) для следующих операций:
1) Удалить из списка
а) первый элемент;
б) второй элемент;
в) первые два элемента;
г) k-й по порядку элемент;
д) все элементы, начиная с k-го по порядку;
е) k первых элементов;
ж) предпоследний элемент;
з) последний элемент;
и) два последних элемента;
к) заданный идентификатор (первый по порядку, если таких в
списке несколько);
л) все идентификаторы, совпадающие с заданным;
м) все идентификаторы, начинающиеся с заданной буквы;
н) все идентификаторы, следующие в списке после заданного
идентификатора;
о) все идентификаторы, следующих в списке до заданного иден-
тификатора;
п) все элементы.
2) Заменить на заданный идентификатор значение
а) k-го по порядку элемента списка;
б) предпоследнего элемента списка;
в) последнего элемента списка.
3) Определить количество идентификаторов в списке,
а) начинающихся с заданной буквы;
б) следующих после заданного идентификатора;
в) следующих до заданного идентификатора.
4) Записать в массив A
а) все идентификаторы из списка;
б) все идентификаторы, начинающиеся с заданной буквы;
в) k первых идентификаторов списка (k>1);
г) все идентификаторы, следующих в списке до заданного иден-
тификатора;
д) идентификаторы с нечетными порядковыми номерами (1,3,5…).
Указание. В качестве драйвера (программы отладки) своих функций возьмите программу, приведенную в примере, добавив в нее описания своих
функций, их вызовы и печать результатов.