Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Стеки
Програма працює із простим стеком цілих чисел. Програма виконує три дії на вибір:
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.
Завдання 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;}
};
//три класи-нащадки із специфікатором доступу public
class a:public fazer{
private:
int inf;
public:
virtual void prin(){cout<<"->class A";}
a(){inf=13;}
~a(){}
};
class b:public fazer{
private:
char inf;
public:
virtual void prin(){cout<<"->class B";}
b(){inf='A';}
~b(){}
};
class c:public fazer{
private:
double inf;
public:
virtual void prin(){cout<<"->class C";}
c(){inf=3.12;}
~c(){}
};
int main()
{
fazer *head=new fazer;
int ch=1;
cout<<"1: Dodatu element class A do stack"<<endl;
cout<<"2: Dodatu element class B do stack"<<endl;
cout<<"3: Dodatu element class C do stack"<<endl;
cout<<"4: Vudalutu element"<<endl;
cout<<"5: Exit"<<endl;
while(ch!=5)
{cout<<"vvedit: ";
cin>>ch;
cout<<" Stack: ";
switch (ch) {
case 1: {a *d=new a;
head->push(d);
break;}
case 2: { b *f=new b;
head->push(f);
break;}
case 3:{ c *d=new c;
head->push(d);
break;}
case 4:{if (head->Size()) head->pop();
break;}
case 5: {return 0;}
}
head->druc();
cout<<endl;
}
getch();
return 0;
}
При виконанні програми можливі результати:
1: Dodatu element class A do stack
2: Dodatu element class B do stack
3: Dodatu element class C do stack
4: Vudalutu element
5: Exit
vvedit: 1
Stack: ->class A
vvedit: 2
Stack: ->class B->class A
vvedit: 3
Stack: ->class C->class B->class A
vvedit: 4
Stack: ->class B->class A
vvedit: 4
Stack: ->class A
vvedit: 4
Stack:
vvedit:
ЧЕРГИ
Завдання1.
Програма пропонує виконати наступні дії на вибір: поставити вузол у чергу (функція enqueue), видалити вузол із черги (функція dequeue), і вийти із програми.
Prog_3.cpp
/*Програма створення простої черги*/
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
struct queueNode {
char data;
struct queueNode *nextPtr; };
typedef struct queueNode QUEUENODE;
typedef queueNode *QUEUENODEPTR;
/* function prototypes */
void printQueue(QUEUENODEPTR);
int isEmpty(QUEUENODEPTR);
char dequeue(QUEUENODEPTR *, QUEUENODEPTR *);
void enqueue (QUEUENODEPTR *, QUEUENODEPTR *, char);
void instructions (void);
using std::cout;
using std::endl;
main () {
QUEUENODEPTR headPtr = NULL, tailPtr = NULL;
int choice;
char item;
instructions ();
printf ("? ");
scanf("%d", &choice);
while (choice !=3) { switch(choice) {
case 1 :
printf("Enter a character: ");
scanf("\n%c", &item);
enqueue(&headPtr, &tailPtr, item);
printQueue(headPtr);
break;
case 2 :
if (! isEmpty(headPtr)) {
item = dequeue(&headPtr, &tailPtr);
printf("%c has been dequeued.\n" , item);
}
printQueue(headPtr);
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 your choice:\n"
" 1 to add an item to the queue\n"
" 2 to remove an item from the queue\n" " 3 to end\n"); }
void enqueue(QUEUENODEPTR *headPtr, QUEUENODEPTR *tailPtr,char value) {
QUEUENODEPTR newPtr;
newPtr =new QUEUENODE;
if (newPtr != NULL) { newPtr->data = value; newPtr->nextPtr = NULL;
if (isEmpty(*headPtr))
*headPtr = newPtr; else
(*tailPtr)->nextPtr = newPtr;
*tailPtr = newPtr; } else
printf("%c not inserted. No memory available.\n", value);
}
char dequeue(QUEUENODEPTR *headPtr, QUEUENODEPTR *tailPtr) {
char value;
QUEUENODEPTR tempPtr;
value = (*headPtr)->data;
tempPtr = *headPtr;
*headPtr = (*headPtr)->nextPtr;
if (*headPtr == NULL) *tailPtr = NULL;
free(tempPtr); return value; }
int isEmpty(QUEUENODEPTR headPtr) {
return headPtr == NULL; }
void printQueue(QUEUENODEPTR currentPtr) {
if (currentPtr == NULL)
printf("Queue is empty.\n\n"); else {
printf("The queue is :\n");
while (currentPtr != NULL) {
cout<< currentPtr->data<<"-->";
currentPtr = currentPtr->nextPtr; }
printf("NULL\n\n"); }
}
При виконанні програми можливі результати:
Enter your choice:
1 to add an item to the queue
2 to remove an item from the queue
3 to end ? 1
Enter a character: A
The queue is:
A --> NULL
? 1
Enter a character: В
The queue is:
A --> В --> NULL
? 1
Enter a character: Z
The queue is:
A --> В --> Z -->NULL
? 2
A has been dequeued.
The queue is:
B --> Z --> NULL
? 2
В has been dequeued.
The queue is:
Z --> NULL
? 2
Z has been dequeued.
Queue is empty.
? 2
Queue is empty.
? 4
Invalid choice.
Enter your choice:
1 to add an item to the queue
2 to remove an item from the queue
3 to end ? 3
End of run.
Завдання 2.
Нехай нам потрібно реалізуйте динамічну структуру типу черга, що працювала б із об’єктами довільних класів, програма яку ми напишемо буде подібною до програми реалізації динамічних структури стеку із класами:
Prog_3_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){
if (this->n!=NULL) this->n->push(l);
else 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;}
};
//три класи нащадки із специфікатором доступу public
class a:public fazer{
private:
int inf;
public:
virtual void prin(){cout<<"class A<-";}
a(){inf=13;}
~a(){}
};
class b:public fazer{
private:
char inf;
public:
virtual void prin(){cout<<"class B<-";}
b(){inf='A';}
~b(){}
};
class c:public fazer{
private:
double inf;
public:
virtual void prin(){cout<<"class C<-";}
c(){inf=3.12;}
~c(){}
};
int main()
{
fazer *head=new fazer;
int ch=1;
cout<<"1: Dodatu element class A do queue"<<endl;
cout<<"2: Dodatu element class B do queue"<<endl;
cout<<"3: Dodatu element class C do queue"<<endl;
cout<<"4: Vudalutu element"<<endl;
cout<<"5: Exit"<<endl;
while(ch!=5)
{cout<<"vvedit: ";
cin>>ch;
cout<<"Queue: ";
switch (ch) {
case 1: {a *d=new a;
head->push(d);
break;}
case 2: { b *f=new b;
head->push(f);
break;}
case 3:{ c *d=new c;
head->push(d);
break;}
case 4:{if (head->Size()) head->pop();
break;}
case 5: {return 0;}
}
head->druc();
cout<<endl;
}
getch();
return 0;
}
При виконанні програми можливі результати:
1: Dodatu element class A do queue
2: Dodatu element class B do queue
3: Dodatu element class C do queue
4: Vudalutu element
5: Exit
vvedit: 1
Queue: class A<-
vvedit: 2
Queue: class A<-class B<-
vvedit: 3
Queue: class A<-class B<-class C<-
vvedit: 4
Queue: class B<-class C<-
vvedit: 4
Queue: class C<-
vvedit: 4
Queue:
vvedit: