Обработка списков

Лекция 16. Обработка списков Программирование типовых операций Приведем примеры фрагментов выполнения типовых операций над списком из примеров 15.1 и 15.2 (лекция 15). Алгоритмы выполнения операций для ссылочных переменных и параллельных массивов одинаковы. Отличаются только обозначения операндов (см. табл. 15.1) и функций управления памятью. Поэтому для параллельных массивов даны лишь некоторые операции. Для параллельных массивов используются функции управления памятью из примера 14.3. В этом случае перед началом работы требуется инициализация кучи: inic_kuchi (); Пример 16.1. Переход к следующему элементу списка (продвижение указателя i к преемнику элемента *i) (рис. 16.1). а) Ссылочные переменные б) Параллельные массивы i = i->uk; i = uk[i]; Эта операция аналогична операции перехода к следующему элементу в векторе: i = i + 1; где i - индекс некоторого элемента вектора. а) в векторе: i = i+1; б) в списке: i = i->uk; (или i = uk[i];) Рис. 16.1. Переход к следующему элементу Пример 16.2. Создание пустого списка с указателем p а) Ссылочные переменные б) Параллельные массивы p = NULL; p = NOL; Пример 16.3. Создание нового элемента *i и запись в него значения nov_id. а) Ссылочные переменные i =(struct el_sp *) malloc (sizeof(struct el_sp)); /* Получение памяти */ if (i != NULL) /* Есть место */ strcpy(i->id, nov_id); /* Запись значения */ else ... /* Нет свободной памяти для нового элемента */ б) Параллельные массивы i = nov_el(); /* Получение памяти */ if (i != NOL) /* Есть место */ strcpy (zn[i] , nov_id); /* Запись значения */ else ... /* Нет свободной памяти для нового элемента */ Пример 16.4. Уничтожeние элемента *i (освобождение занимаемой им памяти): а) Ссылочные переменные б) Параллельные массивы 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 #include #include #include #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 ("(после каждого нажимайте клавишу )\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); } Выполнение контрольных заданий 1. Получите у преподавателя индивидуальное задание. 2. Напишите функцию на языке С и подберите тесты для ее проверки на компьютере. Все входные данные должны передаваться функции как параметры. 3. Включите свою функцию в программу 16.1, добавив в основную программу ввод необходимых для функции данных, ее вызов и вывод результата. Если функция должна изменить список, то для проверки результата вызовите функцию печати списка. Отладьте программу на компьютере. 4. Оформите и сдайте отчет. Контрольные задания Дан список идентификаторов. Длина каждого идентификатора не более 8 символов. Идентификаторы в списке расположены в лексикографическом порядке. Составить функции (подпрограммы) для следующих операций: 1. Удалить из списка а) первый элемент; б) второй элемент; в) первые два элемента; г) k-й по порядку элемент; д) все элементы, начиная с k-го по порядку; е) k первых элементов; ж) предпоследний элемент; з) последний элемент; и) два последних элемента; к) заданный идентификатор (первый по порядку, если таких в списке несколько); л) все идентификаторы, совпадающие с заданным; м) все идентификаторы, начинающиеся с заданной буквы; н) все идентификаторы, следующие в списке после заданного идентификатора; о) все идентификаторы, следующих в списке до заданного идентификатора; п) все элементы. 2. Заменить на заданный идентификатор значение а) k-го по порядку элемента списка; б) предпоследнего элемента списка; в) последнего элемента списка. 3. Определить количество идентификаторов в списке, а) начинающихся с заданной буквы; б) следующих после заданного идентификатора; в) следующих до заданного идентификатора. 4. Записать в массив A а) все идентификаторы из списка; б) все идентификаторы, начинающиеся с заданной буквы; в) k первых идентификаторов списка (k > 1); г) все идентификаторы, следующие в списке до заданного идентификатора; д) идентификаторы с нечетными порядковыми номерами (1,3,5…). Указание. В качестве драйвера (программы отладки) своих функций возьмите программу 16.1, добавив в нее описания своих функций, их вызовы и печать результатов.