КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Программирование типовых операций
Лекция 16. Обработка списков ДАЛЕЕ РЕАЛИЗУЮТСЯ ВСЕ МЕТОДЫ ИНТЕРФЕЙСА Class Monster: IAction Interface IAction { void Draw(); //простой метод вывода имени монстра int Attack(int a); //реализация атаки с заданной силой void Die(); // метод вывода на экран сообщения о смерти монстра int Power { get; } //свойство, вычисляющее силу монстра } { public Monster() { this.health = 100; this.ammo = 100; this.name = "Noname"; } public Monster(string name) : this() { this.name = name; } public Monster(int health, int ammo, string name) { this.health = health; this.ammo = ammo; this.name = name; } public int Health { get { return health; } set { if (value > 0) health = value; else health = 0; } } public int Ammo { get { return ammo; } set { if (value > 0) ammo = value; else ammo = 0; } } public string Name { get { return name; } } public void Passport() { Console.WriteLine("Monster {0} \t health ={1} ammo={2}", name, health, ammo); } public void Draw() { Console.WriteLine("Здесь был монстр " + name); } public int Attack(int a) { ammo -= a; if (ammo > 0) Console.WriteLine("ба-бах!"); else ammo = 0; return ammo; } public void Die() { Console.WriteLine("Монстр " + name + "умер"); health = 0; } public int Power { get { return ammo * health; } } string name; int health, ammo; } class Program { static void Main(string[] args) { Monster Вася = new Monster(50, 50, "Вася как класс "); Вася.Draw(); IAction IВася = new Monster(10, 10, "Вася как интерфейс "); IВася.Draw(); Вася.Passport(); ((Monster)IВася).Passport(); IВася.Attack(10); Вася.Attack(20); Console.WriteLine("У монстра "+ Вася.Name+ "сила равна "+Convert.ToString (((IAction)Вася).Power)); Console.WriteLine("У монстра " + ((Monster)IВася).Name + "сила равна " + Convert.ToString(IВася.Power)); if (Вася.Ammo <= 0) Вася.Die(); if (((Monster)IВася).Ammo <= 0) IВася.Die(); Console.ReadLine(); } } }
Приведем примеры фрагментов выполнения типовых операций над списком из примеров 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 <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); }
Дата добавления: 2014-01-04; Просмотров: 457; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |