Лекция №13 Динамикалы

Іс жүзінде кезектерді бір өлшемді массивтер немесе байланыстырылған тізімдер көмегімен жүзеге асыруға болады , бұл деректер құрылымының логикалық және физикалық деңгейлері арасындағы айырмашылықты жақсы көрсетеді ( физикалық деңгейдегі массив логикалық кезек болып табылады ) . Архитектурасы бойынша кезектер сызықты сақиналы ( циклдік ) болып бөлінеді . Жазу және оқу позицияларының саны бойынша – қарапайым және басым болып бөлінеді . Сонымен қатар , кезектің ерекше түрі бар — қоскірісті кезек немесе дек ( DEQue - Double Ended Queue ; queue - кезек )

Дек немесе екі жақты кезек әдеттегі кезектен ерекшеленеді , өйткені мұндай кезектегі мәліметтер екі бағытта да " қозғалады " ( физикалық немесе виртуалды ) ; дектің " басы " бір уақытта оның " соңы " және керісінше бола алады . Декті іске асырудың бір нұсқасы – қос байланысты сақиналы тізім . Байланыстарды ұйымдастыру тәсілі бойынша ( немесе архитектурасы бойынша ) тізімдер сызықты және сақиналы ( циклдік ) болуы мүмкін . ( Егер тізім сызықты да , сақиналы да болмаса , онда жалғыз нұсқа қалады – бұл ағаш тәрізді мәліметтер құрылымының бірі болып табылатын тармақталған тізім . )

Байланыстар саны бойынша ( және бір мезгілде , бағыты бойынша ) тізімдер бір байланысқан ( бір бағытты ) , екі байланысқан ( екі бағытты ) және көп байланысқан болады . Егер сызықтық байланыстырылған тізімнің соңғы буыны көрсеткішінің мәнi nil ( немесе NULL ) жетекші буын адресіне ауыстырылса , онда сызықтық тізім бір байланыстырылған сақина тізіміне айналады . Қос байланыстырылған тізім үшін , сонымен қатар , жетекші буындағы екінші көрсеткіштің мәнін nil - мен соңғы буын адресіне ауыстыру керек . Екі байланысты сақиналы ( циклдік ) тізім алынады .

• 
  
  
• 
  
  
• 
  Сақиналы қос байланыстырылған тізім үшін мәліметтер түрі қос байланыстырлған сызықты тізіммен бірдей . Бір байланыстырылған тізімдер үшін де дәл солай . Тізімнің буыны типі бойынша оның архитектурасын бағалау мүмкін емес , тек байланыстардың саны туралы ғана айтуға болады . Жетекші буынның артындағы еркін позицияға буын қосу .
  
• 
  Loc- > prev = Pred ; // 4
  
• 
  Pred- > next = Loc ; // 5
  
• 
  Loc- > next- > prev = Loc ; // 6
  
• 
  }
  
• 
  
  
• 
  Тізімнің жетекші буынының артындағы кез келген жерінен сілтемені жою .
  
• 
  void Delete2 ( Link2 * Del )
  
• 
  {
  
• 
  Del- > prev- > next = Del- > next ; // 1
  
• 
  Del- > next- > prev = Del- > prev ; // 2
  
• 
  delete Del ; // 3
  
• 
  }
  
• 
  Іздеу
  
• 
  int Search2 ( Link2 * Start , Link2 * & Find , int Key )
  
• 
  {
  
• 
  Link2 * Cur = Start- > next ;
  
• 
  int Success = 0 ;
  
• 
  while ( Cur ! = Start && ! Success )
  
• 
  {
  
• 
  if ( Cur- > data == Key )
  
• 
  {
  
• 
  Find = Cur ;
  
• 
  Success = 1 ;
  
• 
  break ;
  
• 
  }
  
• 
  Cur = Cur- > next ;
  
• 
  }
  
• 
  return Success ;
  
• 
  }
  
• 
  Көп байланыстырылған тізімдер – бұл буындар арасында қосымша байланыстары бар бір немесе екі байланыстырылған тізімдерге негізделген динамикалық деректер құрылымы .