Преподаватель: Бахтизин. Задание: Разработать программу формирования стека с последующим его преобразованием в двунаправленную очередь. Двунаправленная очередь является динамической структурой данных, каждый элемент которой хранит не одну ссылку (указатель на следующий элемент, как в стеке), а две. Из них одна указывает на предыдущий элемент, другая – на следующий элемент очереди.
/* У стека три значения. 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; //Выходим из программы } } }
