Читайте также:
|
free (i); osvob(i);
Пример 16.5. Включение элемента *j в начало списка с указателем p (рис. 15.2):
j->uk = p; /* Соединить *j с первым элементом списка p */
p = j; /* Прицепить *j к указателю списка */
 |
Рис. 16.2. Включение элемента *j в начало списка p
Эта операция выполняется правильно и для пустого списка.
Пример 16.6. Включение элемента *j в список после элемента *i (рис. 15.3). В примере 15.5 указатель списка p заменится на i->uk:
 |
Рис. 16.3. Включение элемента *j в список после *i
j->uk = i->uk; /* Соединить *j с преемником элемента *i */
i->uk = j; /* Прицепить *j к элементу *i */
Эта операция выполняется и в конце списка, когда элемент *i не имеет преемника.
Пример 16.7. Исключение первого элемента из списка p:
if (p!= NULL) /* Cуществует первый элемент */
{ j = p; /* Запомнить адрес исключаемого эл-та */
p = p->uk; /* Соединить p со вторым элементом */
free(j); /* Освободить память *j */
}
else... /* Исключение невозможно: список пуст */
Пример 16.8. Исключение из списка преемника элемента *i (в примере 15.7 p заменится на i->uk):
if (i->uk!= NULL) /* Существует преемник элемента *i */
{ j = i->uk; /* Запомнить адрес преемника *i */
i->uk = i->uk->uk; /* Соединить *i с преемником его преемника */
free (j); /* Освободить память */
}
else... /* Исключение невозможно */
Если исключаемый элемент не требуется уничтожать (он может, например, входить еще и в другой список), память не освобождают.
Пример 16.9. Проход по списку p (в том числе пустому) с обработкой всех его элементов:
i = p;
while (i!= NULL) /* Существует *i (не конец списка) */
{... /* Обработка текущего элемента *i */
i = i->uk; /* Переход к следующему элементу списка */
}
Вариант с оператором for:
for (i = p; i!= NULL; i = i->uk)
... /* Обработка текущего элемента *i */
Задача 16.1. Дана последовательность из n идентификаторов. Длина каждого идентификатора не более 8 символов. Напечатать идентификаторы в лексикографическом порядке.
Пример теста:
n=7
Исх.посл-ть: Результат:
SIMV A
X A1
A1 SIMV
SL SL
Z20 TEXT
A X
TEXT Z20
Задачу можно решить, сцепляя идентификаторы в список в лексикографическом порядке по мере их ввода. В приведенной ниже
программе 16.1 после чтения очередного идентификатора сразу происходит добавление его в список, сформированный из предшествующих идентификаторов. На рис. 16.4 показано, как изменяется список в процессе включения в него очередных идентификаторов.
Еще несколько пояснений к программе. Идентификаторы поочередно вводятся в массив t_id с помощью функции gets(). Сравнение двух идентификаторов производится с помощью функции strcmp(), которая возвращает значение 0, если идентификаторы равны, и разность кодов двух соответствующих несовпавших символов, если идентификаторы не равны. Значит, значение функции будет < 0, если первый идентификатор в лексикографическом порядке должен следовать раньше второго, и значение будет > 0 в противном случае.
Рис. 16.4. Пример процесса формирования списка идентификаторов
Функция strcpy() служит для копирования строк символов, имеет два аргумента: указатель на строку, куда копировать, и указатель на строку, откуда копировать.
Программа 16.1:
#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 = (struct EL_SP *) 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 PechSp (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); /* включение ид-ра в список */
}
PechSp (p); /* печать списка */
printf ("\n\nДля завершения нажмите любую клавишу\n");
getch();
}
Контрольные вопросы и упражнения
1. Как создать пустой список?
2. Как создать новый элемент списка?
3. Как включить в начало списка новый элемент, на который ссылается указатель i?
4. Напишите фрагмент включения элемента * i в конец списка.
5. Как удалить из списка 1-й элемент?
6. Приведите пример исходных данных для программы 15.1 и нарисуйте список, который сформирует программа.
7. Где в программе 16.1 происходит формирование списка?
8. Почему функции Vkl() передается адрес указателя списка p, а функции PechSp() – значение указателя p?
9. В функции Vkl() параметр p какого типа?
10. Как в функции Vkl() происходит обращение к указателю списка?
11. Изменится ли указатель списка p в главной программе, если функцию печати списка изменить следующим образом:
void PechSp (struct EL_SP *p)
{
printf ("\nРезультат:\n");
for (; p!= NULL; p =p -> sled)
puts (p -> id);
}
Дата добавления: 2015-02-16; просмотров: 100 | Поможем написать вашу работу | Нарушение авторских прав |