С++: Ввод в структуры данных. Линейный список и очередь

Немного теории...

1. Линейный список

Линейный список представляет собой динамическую структуру, доступ к элементам которой осуществляется через указатель на первый элемент (голову списка). Каждый элемент связанного списка , во-первых, хранит какую-то информацию (данные), во-вторых, указывает на следующий за ним или предыдущий элемент. Для представления списка с помощью указателей вводится тип:

struct Node

{

      int data;      //информационное поле, данные, любой порядковый тип

      Node *next;         //указатель на следующий элемент

};

typedef Node * PNode;

      Очередь – это линейный список, работающий по принципу: удаляются элементы только из начала списка, а добавляются только в конец. Для этого вводится два указателя – ссылки на первый и последний элементы (first и last).

Операции, выполняемые с элементами линейного списка

1. Добавление элемента в конец списка.

q – последний элемент.

void Insert_end (PNode &q, int number)

{

Pnode temp_p;

temp_p = new Node;    //выделение области памяти

temp_p-> data = number;      //заполнение информационного поля

temp_p-> next = NULL;

q-> next = temp_p;       //наведение связей

q = temp_p;

}    //Insert_end

2. Установить указатель на последний элемент списка.

void Point_end (PNode &q, PNode first)

{

q = first;

while (q->next != NULL)         //пока указатель не пуст

q = q->next;                  //установить на следующий

}

3. Вставить элемент после заданного q.

void Insert_after_q (PNode &q, int number)

{

PNode p;

p=new Node;         //выделение области памяти

p->data = number; //заполнение информационного поля

p->next = q->next;

q->next = p;          //наведение связей

}             //inset_after_q

4. Удалить элемент, стоящий после заданного q.

void Delete_after_q (PNode &q, int &number)

{

PNode p;

p = q-> next;

q-> next = p-> next;      //наведение связей

number = p-> data;       //сохранение данных

delete p;               //освобождение памяти

}             //Delete_after_q

int Delete_after_q (PNode &q)

{

PNode p;

p = q-> next;

q-> next = p-> next;      //наведение связей

return p-> inf;      //сохранение значения удаляемого элемента

delete p;               //освобождение памяти

}             //Delete_after_q

5. Проверить список на пустоту (first – первый элемент).

bool Empty (PNode first)

{

return (first == NULL);          //возвращает true, если список пуст

}