bsuir.info
БГУИР: Дистанционное и заочное обучение
(файловый архив)
Вход (быстрый)
Регистрация
Категории каталога
Другое [134]
АВС [6]
КПиЯП [77]
ОАиП [305]
ОКТ [77]
СиСПО [8]
Форма входа
Логин:
Пароль:
Поиск
Статистика

Онлайн всего: 3
Гостей: 3
Пользователей: 0
Файловый архив
Файлы » ПОИТ » КПиЯП

ПОИТ (д.), КПиЯП, Лабораторная работа №2, 2015
Подробности о скачивании 15.12.2015, 16:18
Преподаватель: Бахтизин.
Задание: Разработать программу формирования стека с последующим его преобразованием в двунаправленную очередь. Двунаправленная очередь является динамической структурой данных, каждый элемент которой хранит не одну ссылку (указатель на следующий элемент, как в стеке), а две. Из них одна указывает на предыдущий элемент, другая – на следующий элемент очереди.

Листинг программы.
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

/* У стека три значения. capacity - максимальное кол-во элементов.
size - текущее кол-во, елементы - указатель на предыдущее значение */
typedef struct Stack
{
int capacity;
int size;
int *elements;
}Stack;
/* в функцию creatStack передается макс. кол-во элементов, стек создается, возвращает указаель на Stack. */
Stack * createStack(int maxElements)
{
Stack *S;
S = (Stack *)malloc(sizeof(Stack));
/* устанавливаем значения стека */
S->elements = (int *)malloc(sizeof(int)*maxElements);
S->size = 0;
S->capacity = maxElements;
/* Возвращаем указатель на созданный стек */
return S;
}
void pop(Stack *S)
{
/* Если size=0 выходим, из стека ничего нельзя достать */
if(S->size==0)
{
printf("Stack is Empty\n");
return;
}
/* удаляем элемент */
else
{
S->size--;
}
return;
}
int top(Stack *S)
{
if(S->size==0)
{
printf("Stack is Empty\n");
exit(0);
}
/* возвращаем самый верхний элемент */
return S->elements[S->size-1];
}
void push(Stack *S,int element)
{
/* Проверка на заполненность стека, если полон - положить в него ничего нельзя.*/
if(S->size == S->capacity)
{
printf("Stack is Full\n");
}
else
{
/* Кладем значение в самый вверх стека */
S->elements[S->size++] = element;
}
return;
}
/* Объявляем структуру и называем ее node */
typedef struct Node
{
int data;
struct Node *next;
struct Node *prev;
}node;

/* Функция вставки нового элемента */
void insert(node *pointer, int data)
{
/* Проходим по списку, до тех пор, пока он не закончится */
while(pointer->next!=NULL)
{
pointer = pointer -> next;
}
/* Выделяем память для node и вносим в нее данные */
pointer->next = (node *)malloc(sizeof(node));
(pointer->next)->prev = pointer;
pointer = pointer->next;
pointer->data = data;
pointer->next = NULL;
}

int find(node *pointer, int key)
{
pointer = pointer -> next; //первая node всегда содержит NULL и указывает на первое значение (next)
/* продвигаемся по списку и ищем искомое значение */
while(pointer!=NULL)
{
if(pointer->data == key) //значение не найдено
{
return 1;
}
pointer = pointer -> next;//ищем в следующем
}
/* Поиск завершен, ничего не найдено */
return 0;
}

void Delete(node *pointer, int data)
{
/* идем к node, для которой следующее значение то, что мы удаляем */
while(pointer->next!=NULL && (pointer->next)->data != data)
{
pointer = pointer -> next;
}
if(pointer->next==NULL)
{
printf("Element %d is not present in the list\n",data);
return;
}
/* Указатель смотрит на node, у которой next смотрит в node, что мы удаляем */
node *temp;
temp = pointer -> next;
/* temp указывает на node, что мы удаляем */
pointer->next = temp->next;
temp->prev = pointer;
/* Удаляем node, которая следуюящая для pointer */
free(temp);
/* Освобождаем память, т.к. мы удалили это значение из списка. */
return;
}

/* Функция для отображения списка */
void print(node *pointer)
{
if(pointer==NULL) {
return;
}
printf("%d ",pointer->data);
print(pointer->next);
}

int main()
{
int max, curr, tmp, data, query;
puts("Enter stack's capacity");
scanf("%d",&max);
Stack *S = createStack(max); // Выделяем память для стека
/* start всегда указывает на первую node в списке.
temp указывает на последнюю node в списке.*/
node *start,*temp;
start = (node *)malloc(sizeof(node));
temp = start;
temp -> next = NULL;
temp -> prev = NULL;
/* Первый элемент списка (первая node) не содержит данных, но указывает на след. элемент, который содержит. */
/* Инициализаци стека */
tmp=max;
while(max--) {
printf("Enter the value: ");
scanf("%d",&curr);
printf("\n");
push(S,curr);
}
max=tmp;
/* Печатаем стек и создаем двунаправленный список */
while (max--) {
printf("Top element of stack[%d] is %d\n",tmp,top(S));
data=top(S);
pop(S);
insert(start,data);
}

/* Выбираем действие со списком */
while(1) {
printf("1. Delete\n");
printf("2. Print\n");
printf("3. Find\n");
printf("4. Exit\n");

scanf("%d",&query);
if(query==1) {
puts("Which data is need to be Deleted");
scanf("%d",&data);
Delete(start,data); //Удаляем элемент
}
else if(query==2)
{
printf("The list is ");
print(start->next); //Печатаем весь список
printf("\n");
}
else if(query==3) {
puts("Which data is need to be found");
scanf("%d",&data);
int status = find(start,data); //Существует ли элемент в списке?
if(status) {
printf("Element Found\n"); //Существует
}
else {
printf("Element Not Found\n");//Такого элемента нет в списке
}
}
else if(query==4) {
return 0; //Выходим из программы
}
}
}
Категория: КПиЯП | Добавил: ksu
Просмотров: 848 | Загрузок: 12
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]