Программирование типовых операций

Лекция 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