Студопедия

КАТЕГОРИИ:


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

Инициализация очереди




Пример

ТОРГОВЫЙ ЗАЛ

Операция insert(q,x)

ПОКУПАТЕЛИ

Операция empty(q)

КАССА


 

НАБЛЮДАТЕЛЬ

J


z


 


с^°г

операция x=remove(q)



Рис. 2.9. Графическое представление очереди Объявление пустой очереди

#define Maxg 5

float git[Maxg];

frnt=l; rear=0;

Игнорируя возможность переполнения очереди, операцию insert(g, x) запишем следующим образом:

геаг++; git[rear] = х;,

а операцию х = remove(g) так:

x = git[frnt\;

frnt++;.

На рис. 2.10 показано, что произойдет при таком представлении.


 

 

 

 

 

 

 

 

 

 

 

 

  git   git   git   git  
5 4 3 2   5 4 3 2 1   5 4 3 2 1 с 5 4 3 2 1 e d с  
 
  с
  b a  
   
frnt= rear= 1 rear= 0 frnt= 3 frnt= 1 rear= 1 rear= 3 frnt=: 5 3

Рис. 2.10. Элементы в очереди

Изначально очередь пуста. Размер массива git будет 5. В результате выполнения операции insert и remove в очереди будут находиться три элемента. Больше поместить нельзя.

Одним из решений этой проблемы является модификация операции remove таким образом, чтобы при удалении элемента смещать очередь к началу.

х = git[0];

for(i=0; i<rear-l; i + +[ {


git [i


git[i+1];


rear-

Переменной frnt не требуется, так как первый элемент — начало очереди. Для пустой очереди rear = 0. Метод непроизводителен, так как требует перемещение оставшихся элементов.

Другой способ предлагает рассматривать массив в виде циклического связанного списка. Недостаток — трудно определить, когда очередь пуста, так как условие rear <frnt не выполняется.

Рассмотрим следующий пример (рис. 2.11). Одним из способов решения проблемы является соглашение о том, что frnt является индексом элемента, предшествующего первому элементу. В этом случае для пустой очереди frnt = rear.


 

             
  e 5-ти элементный   е frnt=3  
4 3 2
масив. Если необходимо разместить элемент f, то он пишется в первую 4 3 2 rear=1 rear<frnt, rear=1 rear<fmt, но  
d d  
с с  
     
      f очередь  
  позицию. не пуста  
frnt=   frnt-    
rear=0 rear=3  

Рис. 2.11. Пример

 

#define Maxg  
float git[Maxg];
f rnt = = Maxg;  
rear = = Maxg;  

Операция empty

if(frnt == rear) empty=l; else empty =0;

Операция remove

 

if (empty == 1)    
  printf( "Очередь пуста") r
if (frnt = = Maxg-1) frnt = 0;
else frnt = frnt + 1;  
remove = g it[frnt];    

При реализации вставки необходимо контролировать ситуацию переполнения, при которой frnt = rear. Это же условие характеризует пустую очередь. Одно из решений проблемы — очередь растет до Maxg-\.

Операция insert

/^выделение места для элемента*/ if (rear == Maxg - 1) rear = 0; else rear = rear + 1;


/^проверка на переполнение */
if (rear = = frnt)  
printf( "Переполнение." );
git [rear] = x;  



Поделиться с друзьями:


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


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



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




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