Динамічні списки в багатьох задачах кількість даних наперед не встановлена


НазваДинамічні списки в багатьох задачах кількість даних наперед не встановлена
Дата конвертації01.04.2013
Розмір445 b.
ТипЗадача


Динамічні списки

  • В багатьох задачах кількість даних наперед не встановлена,

  • передбачається введення нових елементів у вже

  • сформований набір даних, відалення окремих елементів чи

  • інші зміни складу й конфігурації набору даних. У цих

  • випадках застосовують динамічні інформаційні структури.

  • Вони формуються на основі взаємозв’язку елементів. Так,

  • кожен елемент лінійного списку пов’язується через відповідні

  • вказівники з одним або декількома сусідніми елементами.

  • Дані Дані Дані

  • Адреса Адреса ……… NULL


  • Програмно елемент списку можна реалізувати через

  • структурний тип, який містить щонайменше два поля:

  • інформаційне, в якому зберігаються дані цього елемента,

  • та адресне, через яке він пов’язується з іншим елементом.

  • Наприклад, шаблон структури елементу списку:

  • typedef long elemtype;

  • typedef stuct list_elem {

  • elemtype val;

  • struct list_elem *next;

  • } list;

  • тут elemtype - визначає тип даних лінійного списку. Можна

  • використовувати будь-який стандартний тип даних,

  • включаючи структури; list - визначає структуру елемента

  • лінійного списку ( val - значення, яке зберігається у вузлі,

  • next – покажчик на наступний елемент).

  • Лінійний список, кожен елемент якого містить посилання на

  • один сусідній, називається однозв’язним або

  • однонаправленим.



  • Для звертання до списку достатньо зберігати адресу

  • тільки одного початкового елемента, який називають

  • вершиною або головою списку. Наприклад, адреса

  • початку списку зберігається в змінній-вказівнику first

  • list * first;

  • Кінцевий елемент, який не має наступників, називають

  • хвостом списку, а в його адресне поле заносять

  • константу NULL.

  • Поширені також двозв’язні списки, в яких кожен елемент

  • зберігає адреси двох сусідніх.

  • Списки розрізняють також за способом приєднання

  • нових елементів:

  • приєднання до вершини списку;

  • приєднання до кінця списку;

  • - вставлення елементів у визначені позиції списку.



Основні операції над списками

  • Включення елемента в початок списку.

  • list *addbeg (list *first, elemtype x) {      list *vsp;      vsp = (list *) malloc(sizeof(list));      vsp->val=x;      vsp->next=first;      first=vsp;      return first; }



  • 2. Видалення елемента з початку списку.

  • list *delbeg(list *first) {       list *vsp;      vsp=first->next;      free(first);      return vsp; }



  • 3. Включення нового елемента у список.

  • list *add(list *pred, elemtype x) {       list *vsp;      vsp = (list *) malloc(sizeof(list));      vsp->val=x;      vsp->next=pred->next;      pred->next=vsp;      return vsp; }

  • 4. Видалення елемента зі списку.



  • elemtype del(list *pred) {       elemtype x;      list *vsp;      vsp=pred->next;      pred->next=pred->next->next;      x=vsp->val;      free(vsp);      return x; }

  • 5. Друк значень списку.

  • void print(list *first) {      list *vsp;      vsp=first;



  •      while (vsp)      {           printf("%i\n",vsp->val);           vsp=vsp->next;      } }

  • 6. Перевірка, чи порожній список

  • int pust(list *first) {  return !first;

  • }

  • 7. Знищення списку

  • list *kill(list *first) {      while (!pust(first)) first=delbeg(first);      return first; }



Черги

  • Черги – це лінійний список, для якого виконується

  • приєднання елементів до кінця списку і дані зчитуються у

  • тому ж порядку, як їх записували.

  • n n n n

  • next next next … … NULL

  • Черга реалізує принцип FIFO (first in - first out)

  • Приклад: програма запису чисел в чергу, почергове

  • виведення всіх парних елементів

  • #include

  • #include

  • struct st {

  • int n;

  • st *sp;

  • } *first=NULL,*last,*q;



  • void Add (int N) { //Функція приєднання елементу

  • q=(st*)malloc(sizeof(st)); //Звільнення пам'яті для елементу

  • if (first==NULL) first=q; //Якщо не було елементів робимо

  • // першим

  • else last->sp=q; // інакше дописуємо елемент в

  • // кінець черги

  • q->n=N; //Заносимо значення в останній

  • // елемент

  • last=q; //Ставимо елемент останнім

  • last->sp=NULL;

  • }

  • int View() //Функція перегляду першого

  • // елементу списку

  • { return first->n; } //повертаємо значення елементу





  • while (first!=NULL) { //Доки список не пустий

  • k=View(); //робимо k рівним першому

  • // елементу в списку

  • if (k%2==0) printf("%d ",k); //якщо елемент парний

  • //виводимо його на екран

  • Delete(); //Видаляємо перший елемент

  • }

  • }





  • Приклад: програма перевірки балансу дужок в тексті.

  • Будь-які символи, крім дужок ігноруються

  • #include

  • #include

  • typedef struct st //Оголошення типу STACK

  • { char ch;

  • struct st *ps; } STACK;

  • STACK *p=NULL,*q;

  • void putinstack(char w); //Функція запису елемента в

  • //стек

  • char viewstack(); //Функція, яка повертає

  • //значення останнього eлемента

  • //стеку

  • void deletestack(); //Функція видалення останнього

  • // елементу

  • void clearstack(); //Функція очищення стеку





  • {

  • puts("NO"); //в іншому випадку умова

  • // не виконується

  • return 0; //завершення головної функції

  • }

  • }

  • if (p==NULL) puts("YES"); //Якщо стек пустий умова

  • //виконується

  • else

  • {

  • puts("NO"); //якщо ні – умова не

  • // виконується

  • clearstack();

  • } //Звільнюємо виділену пам'ять

  • return 0;

  • }





  • void deletestack() {

  • q=p; //Встановлення вказівника q на

  • //останній елемент

  • p=q->ps; //Встановлення вказівника р на

  • //попередній елемент

  • free(q); //Звільнення динамічної пам'яті

  • }

  • void clearstack() {

  • while (p!=NULL) //Доки стек не буде пустий

  • deletestack(); //видаляємо останній елемент

  • }



Схожі:

Динамічні списки в багатьох задачах кількість даних наперед не встановлена iconДля багатьох додатків достатньо використовувати динамічні множини, які підтримують лише стандартні словникові операції вставки, пошуку та видалення

Динамічні списки в багатьох задачах кількість даних наперед не встановлена iconАвтоматизоване видалення та оновлення даних Проблемна ситуація
Якщо в базі даних кілька тисяч записів для учнів багатьох шкіл і наприкінці навчального року їх потрібно "перевести " в наступний...
Динамічні списки в багатьох задачах кількість даних наперед не встановлена iconГідросфера льодовики
Утворюються на ділянках земної поверхні за умови, що кількість атмосферних опадів, які випадають протягом багатьох років, перевищує...
Динамічні списки в багатьох задачах кількість даних наперед не встановлена iconДіаграма – це представлення даних таблиці в графічному вигляді, яке використовується для аналізу і порівняння
Якщо електронна таблиця містить велику кількість числових даних, то проаналізувати їх (порівняти, оцінити їх зміни з протягом часу,...
Динамічні списки в багатьох задачах кількість даних наперед не встановлена iconЛекція 2: Теги мови html гіперпосилання Зображення Списки Таблиці Гіперпосилання Гіперпосилання
Таблиці з невидимою межою довгий час використовувалися для верстки веб-сторінок, дозволяючи розділяти документ на модульні блоки....
Динамічні списки в багатьох задачах кількість даних наперед не встановлена iconРозділ Бази даних. Системи управління базами даних Інформатика 11 клас
Програмне забезпечення, призначене для створення баз даних, оновлення даних, що зберігаються в них, забезпечення зручного доступу...
Динамічні списки в багатьох задачах кількість даних наперед не встановлена iconНавчальний посібник Розділ І. Натуральні числа. Геометричні фігури І величини, 5 клас в задачах на рух розглядаються в задачах на рух розглядаються
Відстань між автомобілями 345 км. На якій відстані вони будуть знаходитися через дві години, якщо швидкість одного 72 км /год., а...
Динамічні списки в багатьох задачах кількість даних наперед не встановлена iconРозглянути послідовність чисел Фібоначчі як джерело багатьох
Дослідницька робота з вимірювання різних частин тіла людини та обробка одержаних даних
Динамічні списки в багатьох задачах кількість даних наперед не встановлена iconПогляд ззаду наперед

Динамічні списки в багатьох задачах кількість даних наперед не встановлена iconІнформатика 9клас Розділ 14 Стиснення та архівування даних Стиснення даних
Стиснення даних – це процедура перекодування даних з метою зменшення їхнього обсягу

Додайте кнопку на своєму сайті:
dok.znaimo.com.ua


База даних захищена авторським правом ©dok.znaimo.com.ua 2013
звернутися до адміністрації
dok.znaimo.com.ua
Головна сторінка