LAB9

Л а б о р а т о р н а я р а б о т а 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…).

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

функций, их вызовы и печать результатов.