Студопедия

КАТЕГОРИИ:


Архитектура-(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);

}

 

<== предыдущая лекция | следующая лекция ==>
Пример описания, реализации и использования интерфейса | Лекция 16. Онтогенез
Поделиться с друзьями:


Дата добавления: 2014-01-04; Просмотров: 457; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.01 сек.