Лабораторная работа №12
Задание: смоделировать стек на основе односвязного списка и решить на этой структуре задачу по варианту из списка ниже. Создать интерактивное приложение с возможностью выбора команды: а) ввод данных в стек(и) из стандартного или нестандартного текстового файла(ов); б) вывод данных из всех стеков на экран (стандартный текстовый файл); в) решение задачи; г) освобождение стеков; д) выход.
Стек – последовательность однородных элементов с дисциплиной доступа LIFO
(LIFO = Last In First Out)
Порядок работы со стеком для перебора всех элементов:
1. Разбор стека с переносов элементов в дополнительный стек.
2. Возвращение элементов в исходный стек из дополнительного.
Пример 1. Дан стек, хранящий информацию о прохождении теста в виде пар (ФамилияИО, балл). Баллы лежат в пределе от 0 до 100. Найти средний балл за тест. Если стек пуст, средний балл сделать равным -1. Результат вычисления вернуть как результат функции. (см. Пример 2 в конце файла)
Си | Delphi | |
Typedef struct { char FamIO[31]; int Ball; }TInfo; // или без typedef à | struct TInfo{ char FamIO[31]; int Ball; }; | Type TInfo=record FamIO: String[30]; Ball: integer; End; |
// моделирование стека на основе односвязного списка | ||
// достаточно одного рекурсивного типа struct TElem { TInfo Info; // или struct TInfo Info; TElem *Next; // или struct TElem *Next; }; // здесь и далее (зависит от версии) | PElem=^TElem; // нужны два типа TElem=record Info: TInfo; Next: PElem; End; | |
// дополнительная процедура перекладывания элемента из одного стека (StackTop) в другой(Dop) | ||
void TopToTop (TElem **PSt1, TElem **PSt2){ TElem *Elem, *StTop=*PSt1, *Dop=*PSt2; Elem = StTop; StTop = StTop->Next; // или StTop=(*StTop).Next; Elem->Next = Dop; Dop = Elem; *PSt1 = StTop; *PSt2 = Dop; return;} | procedure TopToTop(var StackTop, Dop:PElem); var Elem: PElem; begin Elem:=StackTop; StackTop:= StackTop^.next; Elem^.Next:= Dop; Dop:=Elem; end; | |
//найти средний балл | ||
Double naiti(TElem *StackTop){ TElem *Dop = NULL; int Sum = 0; int N = 0; while (StackTop) { // 1. Разбор стека Sum += StackTop->Info. Ball; N++; TopToTop(&StackTop, &Dop); } while (Dop) { // 2. Возвращение элементов TopToTop(&Dop, &StackTop); } if (N>0) return Sum/(double)N; else return -1; } | function naiti(StackTop: PElem):real; var Dop: PElem; // вершина дополнительного стека Sum: integer; // сумма баллов N: integer; // количество испытуемых Begin Dop:=nil; Sum:=0; N:=0; While StackTop<>nil do {1. Разбор стека } Begin Sum:=Sum+ StackTop^.Info. Ball; Inc(N); TopToTop(StackTop, Dop); End; While Dop<>nil do{2.Возвращение элементов } TopToTop(Dop, StackTop); If N>0 then Naiti:=Sum/N else Naiti:=-1; End; | |
Из двух стеков равной длины создать один стек, не удаляя исходные стеки (создавать копии элементов). При создании нового стека элементы брать по-очереди по одному элементу из каждого стека. Из элементов двух стеков равной длины собрать один стек, изменив связи между элементами (не выделяя новую память). При создании нового стека элементы брать по-очереди по одному элементу из каждого стека.
Из неотрицательных элементов двух стеков с упорядоченными по элементами создать новый стек с упорядоченными элементами, не удаляя исходные стеки (создавать копии элементов). Из неотрицательных элементов двух стеков с упорядоченными по элементами собрать новый стек с упорядоченными элементами, изменив связи между элементами стеков (не выделяя новую память). В исходных стеках должны остаться только отрицательные элементы.
Пример 2. Дан стек, хранящий информацию о прохождении теста в виде пар (ФамилияИО, балл). Баллы лежат в пределе от 0 до 100. Найти средний балл за тест и из отличников, чей балл не менее 85, сформировать второй стек, не удаляя их из исходного стека.
#include <windows. h> // SetConsoleOutputCP, SetConsoleCP
#include <stdio. h> //printf, fgets
#include <conio. h> // getch
#include <string. h> // strcpy, strncmp, strchr
//
struct TInfo{
char FamIO[31];
int Ball;
};
struct TElem { // моделирование стека на основе односвязного списка
TInfo Info; // или struct TInfo Info;
TElem *Next; // или struct TElem *Next; здесь и далее
};
//-прототипы
TElem* PushStack(TElem *St, TInfo Info); // добавить элемент в стек
TInfo PopStack(TElem **PSt); //извлечь элемент из стека
// дополнительная процедура перекладывания элемента из одного стека (StTop) в другой(Dop)
void TopToTop (TElem **PSt1, TElem **PSt2); // без изменения адресов элементов, только связи
//первая часть: создание стека из текстового файла
TElem* CreateStack(TElem *St);
//вторая часть: вывод стека на экран ------
void OutputStack(TElem *St);
//третья часть: решение задачи --
TElem* Decide(TElem **PSt1, TElem *St2);
//четвертая часть: освобождение памяти -----
TElem* FreeStack(TElem *St);
//
int main()
{
TElem *StackTop1=NULL, *StackTop2=NULL;
char ch;
SetConsoleOutputCP(1251);
SetConsoleCP(1251);
do{
printf("\nN - создать новый стек; V - вывод; D - решение; F - освободить; \
E - конец.\nВаш выбор?");
ch=getchar(); fflush(stdin);
ch=toupper(ch);
switch (ch) {
//первая часть: создание стека из текстового
case 'N': if (StackTop1) {
printf("Error: сначала надо освободить память!"); break;
}
StackTop1 = CreateStack(StackTop1);
break;
//вторая часть: вывод стеков на экран ------
case 'V': printf("Первый стек:\n"); OutputStack(StackTop1);
printf("\nВторой стек (отличники):\n"); OutputStack(StackTop2);
break;
//третья часть: решение задачи --
case 'D': StackTop2 = Decide(&StackTop1, StackTop2);
break;
//четвертая часть: освобождение памяти -----
case 'F': StackTop1=FreeStack(StackTop1);
StackTop2=FreeStack(StackTop2);
printf("Вся память под стеки особождена\n");
break;
//-выход--
case 'E': return 0;
default:
printf("Нет такой команды\nPress any key");
getch();
}
} while (ch!='E');
return 0;
}
//
TElem* PushStack(TElem *St, TInfo Info){ // добавить элемент в стек
TElem *Elem= new TElem;
Elem->Info. Ball = Info. Ball;
strcpy(Elem->Info. FamIO, Info. FamIO);
Elem->Next = St;
return Elem; // Адрес новой вершины
}
TInfo PopStack(TElem **PSt){ //извлечь элемент из стека
TElem *Elem = *PSt;
TInfo Info = Elem->Info;
*PSt = Elem->Next;
delete Elem;
return Info;
}
// дополнительная процедура перекладывания элемента из одного стека (StTop) в другой(Dop)
void TopToTop (TElem **PSt1, TElem **PSt2){
TElem *Elem, *StTop=*PSt1, *Dop=*PSt2;
Elem = StTop;
StTop = StTop->Next; // или StTop=(*StTop).Next;
Elem->Next = Dop;
Dop = Elem;
*PSt1 = StTop; *PSt2 = Dop; // сохранить новые адреса вершин по адресам PSt1 и PSt2
return;
}
//первая часть: создание стека из текстового
TElem* CreateStack(TElem *St){
int kol=0;
char *n,*r;
TInfo Info;
char Balls[5];
while(1){
printf("FamIO (или **)=?");
fgets(Info. FamIO,30,stdin); fflush(stdin);
n = strchr(Info. FamIO, '\n'); if (n) Info. FamIO[n-Info. FamIO]='\0';
r = strchr(Info. FamIO, '\r'); if (r) Info. FamIO[r-Info. FamIO]='\0';
if (strncmp(Info. FamIO, "**",2)==0) break; // условие окончания ввода - два первых символа **
printf("Ball =?");
fgets(Balls,4, stdin); fflush(stdin);
Info. Ball = atoi(Balls);
St = PushStack(St, Info);
kol++;
}
printf("Создан стек из %d элементов\n", kol);
printf("Press any key to continue");
getch();
return St;
}
//вторая часть: вывод стека на экран ------
void OutputStack(TElem *St){
TElem *Dop=NULL;
while (St){
printf("%30s %3d\n", St->Info. FamIO, St->Info. Ball);
TopToTop(&St, &Dop);
}
while(Dop) TopToTop(&Dop, &St);
printf("Press any key to continue");
getch();
return;
}
//третья часть: решение задачи --
TElem* Decide(TElem **PSt1, TElem *St2){
TElem * St1= *PSt1, *Dop=NULL;
St2 = FreeStack(St2);
int Sum = 0, N=0;
while (St1){
Sum+= St1->Info. Ball;
N++;
if (St1->Info. Ball>=85) St2=PushStack(St2, St1->Info); // отличники
TopToTop(&St1, &Dop);
}
while(Dop) TopToTop(&Dop, &St1);
if (N) printf("Средний балл = %6.2f\n", (float)Sum/N);
else printf("Стек пуст\n");
printf("Press any key to continue");
getch();
*PSt1 = St1; // новый адрес через параметр (изменение по адресу)
return St2; // новый адрес через результат функции вернется
}
//четвертая часть: освобождение памяти -----
TElem* FreeStack(TElem *St){
TInfo Info;
while (St){
Info = PopStack(&St);
}
return St;
}
//
