Списки стеки очереди в C (стр. 3 из 5)
Вказівники, подібно до будь-яких інших змінних, перед своїм використанням повинні бути оголошені. Оголошення
int *countP;
оголошує перемінну countP типу int* (тобто вказівник за ціле число). Символ * в оголошенні вказує що йде оголошення вказівника. Вказівники можна оголошувати, що вказувати на об’єкти довільного типу.
Вказівники повинні бути ініціалізовані або при своєму оголошенні, або в операторі присвоєння. Вказівник можу бути ініціалізований значенням 0, NULL або адресом. Вказівник із значенням 0 або NULL ні на що не вказує.
Для вказівників характерні ряд операцій, так поряд із ними використовується операція адресації або ж &, - унарна операція, що повертає адрес свого операнда. Наприклад, якщо маємо оголошення
int y=5;
int *yP;
то операнд
yP-&y;
присвоює адрес змінної у вказівнику уР. Кажуть, що змінна уР «вказує» на у.
Операція *, зазвичай називається операцією побічною адресацією або операцією розіменування, повертає значення об’єкта, на який вказує її операдн (тобто вказівник). Наприклад, оператор
cout<<*yP<<endl;
виводить значення змінної у. Використання * вказаним способом називається розіменуванням вказівника. Варто відзначити, що розіменування вказівника можливе також в лівій частині оператора присвоєння, наприклад,
*уР=9;
де 9 присвоюється у. Розіменований вказівник може також використовуватися для отримання вхідної величини, наприклад,
cin<<*yP;
Нижче наведемо приклад програми, що буде виконувати всі перераховані вище операції:
Prog_1.cpp
#include <iostream>
#include "conio.h"
using std::cout;
using std::endl;
int main(void)
{
int a=7; // a – ціле
int *aP; // *аР – вказівник на ціле число
aP=&a; // аР – отримує адрес а
cout<<"Adres a= "<<&a<<endl<<"Znachena aP= " <<aP<<endl;
cout<<"Znachena a= "<<a<<endl<<"Znachena *aP= " <<*aP<<endl;
*aP=10; // розіменовується вказівник і отримує значення 10
cout<<"Znachena aP= "<<aP<<endl<<"Znachena *aP= "<<*aP<<endl;
getch();
return 0;
}
Результат роботи програми:
Adres a= 0хfff4
Znachena aP= 0хfff4
Znachena a= 7
Znachena *aP= 7
Znachena aP= 10
Znachena *aP= 0хfff4
2.1.2. Операції NEW та DELETE
Для роботи із пам’яттю в С++ можна використовувати досить багато операцій та функцій, це і malloc, calloc, free та інші. Проте найбільш зручними є операції new і delete.
Операція new і delete забезпечують біль зручні засоби для реалізації динамічного розпроділення динамічної пам’яті.
Операція new служить для виділення пам’яті. Синтаксично допускається 3 способи її використання :
1. new type_name
Приклад: float *r=new float;
При такому оголошенні r буде вказівником на значення типу float, причому вказувати він буде на початок вже виділеної області пам’яті розміром float, на відміну від оголошення float *r;, де пам’ять не виділяється.
2. new (type_name)
Приклад: float *r=new (float);
Цей випадок аналогічний попередньому.
3. new type_name [expression]
Приклад: float*r=new float [20];
Цей випадок показує що вказівник r вказує на масив із десяти елементів типу float.
Використовуючи операцію new вказівнику вже при ініціалізації можна присвоїти початкове значення:
int *d = new int(12);
Операція delete служить для звільнення пам’яті в “кучі”. Відповідно до операції new, синтаксично допускаються такі способи її використання
1. delete var_name;
Приклад: float*r=new float [20];
delete r;
2. delete [expr] var_name
Приклад: float*r=new float [20];
delete [20] r;
Відмітимо, що дія в першому та другому випадках аналогічна. Виділивши пам’ять , наприклад, так:
float *r = new float [20];
можемо звільнити її будь-яким з наступних способів:
delete [200] r; delete [20] r; delete [10] r; delete [ ] r; delete r;
Якщо вказівник залишається не видаленим із пам’яті, це може призвести до непоправних наслідків, аж до збою у роботі ОС.
2.2 Стеки
Для роботи зі стеком достатньо мати покажчик head на його вершину та допоміжний покажчик (наприклад current) на елемент стеку. Наведемо алгоритми основних операцій зі стеком – вставка та видалення його елемента.
Алгоритм вставки елемента до стеку
1. Виділити пам’ять для нового елемента стеку.
2. Ввести дані до нового елемента.
3. Зв’язати допоміжний елемент із вершиною.
4. Встановити вершину стеку на новостворений елемент.
Графічне представлення алгоритму вставки елемента до стеку
Зауважимо, що значення покажчика head на вершину порожнього стеку є NULL. Тому для створення стеку слід виконати оператор Head=NULL та повторити щойно наведений алгоритм потрібну кількість раз.
Алгоритм видалення елемента із непорожнього стеку
1. Створити копію покажчика на вершину стеку
2. Перемістити покажчик на вершину стеку на наступний елемент
3. Звільнити пам’ять із-під колишньої вершини стеку.
Зрозуміло, що для очищення всього стеку слід повторювати кроки 1-3 доти, доки покажчик head не дорівнюватиме NULL.
Графічне представлення алгоритму видалення елемента із непорожнього стеку
Для наглядної ілюстрації роботи із стеком напишемо програму , основні функції, використовувані при роботі зі стеками — push і pop. Функція push створює новий вузол і поміщає його на вершину стека. Функція pop видаляє верхній вузол стека, звільняє пам'ять, що була виділена вилученому вузлу, і повертає вилучене значення.
Програма на працює із простим стеком цілих чисел. Програма виконує три дії на вибір:
1) поміщає значення в стек (функція push);
2) вилучає значення зі стека (функція pop);
3) завершує роботу.
Prog_2.cpp
/*Програма створення простого стеку*/
#include <iostream>
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
struct stackNode {/*структура, що посилається на себе*/
int data;
struct stackNode *nextPtr;
};
typedef struct stackNode STACKNODE;
typedef STACKNODE *STACKNODEPTR;
void push(STACKNODEPTR *, int);
int pop(STACKNODEPTR *);
int isEmpty(STACKNODEPTR);
void printStack(STACKNODEPTR);
void instructions(void);
using std::cout;
using std::endl;
main() {
STACKNODEPTR stackPtr = NULL; /*Вказівник на вершину*/
int choice, value;
instructions();
printf ("? ");
scanf("%d", &choice) ;
while (choice !=3) {
switch (choice) {
case 1: /*Занесення значення в стек*/
printf("Enter an integer: ");
scanf("%d", &value);
push (&stackPtr, value);
printStack (stackPtr);
break;
case 2: /*Видалення значення із стеку*/
if (!isEmpty(stackPtr))
printf("The popped value is %d.\n", pop(&stackPtr)) ;
printStack(stackPtr);
break;
default:
printf("Invalid choice.\n\n");
instructions();
break;
}
printf ("? ");
scanf("%d", &choice); }
printf("End of run.%n"); return 0;
}
/*Вивід інструкції на екран*/
void instructions(void) {
printf("Enter choice:\n"
"1 to push a value on the stack\n"
"2 to pop a value off the stack\n"
"3 to end program\n"); }
/*Занесення нового значення у вершинку стеку*/
void push (STACKNODEPTR *topPtr, int info)
{ STACKNODEPTR newPtr;
newPtr =new STACKNODE;
if (newPtr != NULL) {
newPtr->data = info;
newPtr->nextPtr = *topPtr;
*topPtr = newPtr; } else
printf("%d not inserted. No memory available.\n", info);
}
/*Видалення вузла на вершині стеку*/
int pop(STACKNODEPTR *topPtr)
{ STACKNODEPTR tempPtr;
int popValue;
tempPtr = *topPtr;
popValue = (*topPtr)->data;
*topPtr = (*topPtr)->nextPtr;
free(tempPtr); return popValue;
}
/*Друк стеку*/
void printStack(STACKNODEPTR currentPtr)
{ if (currentPtr == NULL)
printf ("The stack is empty.\n\n");
else { printf("The stack is:\n");
while (currentPtr != NULL) {
cout<<currentPtr->data<<"-->";
currentPtr = currentPtr->nextPtr;}
printf("NULL\n\n"); }
}
/*Перевірка чи пустий стек*/
int isEmpty(STACKNODEPTR topPtr)
{ return topPtr == NULL;}
При виконанні програми можливі результати:
Enter choice:
1 to push a value on the stack
2 to pop a value off the stack
3 to end program? 1
Enter an integer: 5 The stack is:
5 --> NULL
? 1
Enter an integer : 6
The stack is:
6-->5-->NULL
? 1
Enter an integer: 4 The stack is:
4--> 6 --> 5 --> NULL
? 2
The popped value is 4.
The Stack is:
6 --> 5 --> NULL
? 2
The popped value is 6. The Stack is:
5 --> NULL
? 2
The popped value is 5.
The stack is empty.
? 2
The stack is empty.
? 4
Invalid choice.
Enter choice.:
1 to push a value on the stack
2 to pop a value off the stack
3 to end program ? 3
End of run.
Функція push поміщає новий вузол на вершину стека. За попередньо наведеним алгоритмом маємо: створення нового вузла відбувається за допомогою виклику операції new, при цьому вказівник newPtr має адресу блоку виділеної пам'яті, змінній newPtr->data привласнюється значення, яке необхідно помістити в стек, і покажчику newPtr->nextPtr вказує NULL, далі вказівнику newPtr->nextPtr привласнюється *topPtr (вказвник на вершину стека); єднальний елемент newPtr тепер вказує на вузол, що був верхнім до цього. *topPtr привласнюється значення newPtr, *topPtr тепер вказує на нову вершину стека.
Функція pop видаляє верхній вузол стека. Відзначимо, що перед тим як викликати pop, main визначає, чи не порожній стек. Функція pop працює наступним чином:
1) Покажчику tempPtr привласнюється *topPtr (tempPtr буде використаний для звільнення вільної пам'яті).
2) Змінній popValue привласнюється значення (*topPtr)->data (зберігається значення, що перебувало у верхньому вузлі).
3) *topPtr привласнюється (*topPtr)->nextPtr (*topPtr привласнюється адреса нового верхнього вузла).
4) Звільнення пам'яті, на яку вказує tempPtr.
5) Відбувається повертається значення popValue функції main.
Реалізувати стек використовуючи класи теж не видається складним. Наприклад, маємо Завдання 1: Реалізуйте динамічну структуру типу стек, що працювала б із об’єктами довільних класів, ми можемо отримати наступну програму:
Prog_2_1.cpp
#include <iostream>
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
using std::cout;
using std::cin;
using std::endl;
//Батьківський клас, що посилається сам на себе
class fazer{
protected:
fazer *n;
public:
//конструктор
fazer(){n=NULL;}
//деструктор
~fazer(){delete n;}
//віртуальна функція, що буде виводити імя класу відповідного обєка
virtual void prin(){};
//занесення обєкта класу до стеку
void push(fazer *l){
l->n=this->n;
this->n=l;
}
//перехід по стеку із вивиденням елементів
void druc(){
if (this->n!=NULL) {this->n->prin(); this->n->druc();}
}
void pop(){
this->n=this->n->n;
}
//перевірка чи не порожній стек
int Size(){if (this->n!=NULL) return 1; else return 0;}