Линейные однонаправленные списки

 

 

 

 

 

 

 

 

 

Лабораторная работа №2

По теме: «Линейные однонаправленные списки»

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. 2015 
   Условие задачи

1. Написать операции работы  с заданной структурой данных, включив их в один модуль (файл). К основным операциям  
(см. таблицу) добавить операцию, показывающую содержимое структуры после выполнения какого-либо действия с ней. Эту операцию реализовать на основе базовых операций:

а) основные операции над статическим стеком;

       2. Написать  программу, демонстрирующую выполнение  операций над заданной структурой  данных. Эту программу надо поместить  в свой модуль (файл). Модуль с  основными операциями включать  в программу, используя директиву include.

1. Анализ задачи.

Дано:

1)Добавление элемента в стек

A={ai|i[1,n], i}, aiZ

с Z - элемент

2)Изъятие элемента из стека

A={ai|i[1,n], i}, aiZ

3) Узнать размер стека.

A={ai|i[1,n], i}, aiZ

4)Вывод стека

A={ai|i[1,n], i}, aiZ

Результат:

1)Добавление элемента в стек

A={с, ai|i[1,n], i}, aiZ

2)Изъятие элемента из стека

A={ai|i[1,n], i}, aiZ

с Z – элемент

3) Узнать размер стека

A={ai|i[1,n], i}, aiZ

 

n N.

4)Просмотр содержимого стека

A={ai|i[1,n], i}, aiZ

Решение:

1. Если стек не заполнен, то последнему свободному элементу стека приравниваем полученное значение элемента p->A[p->count] = value и увеличиваем колличество элементов в стеке p->count++.
2. Удаляем последний элемент p->count-- и возвращаем его значение return p->A[p->count]. Присваиваем это значение переменной х: int x = Delete(&s).
3. Возвращаем номер последнего заполненного элемента return p->count.
4. Переменной i присваиваем значение 1. Выполняем p->A[p->count - i] и i=i+1, пока p->count - i >=0.
2. Структуры данных.

1. Внешнее представление исходных данных

Навигация по функциям.

number – номер функции, которая будет использованна

2. Внешнее представление результатов

1) Элемент добавлен в стек.

2)  Элемент x удален из стека./x-последний удаленный элемент.

3) Размер стека:n./n-номер последнего заполненного элемента.

4) Последовательность чисел.

3. Внутреннее представление исходных данных.

Линейный ациклический однонаправленный статический список, имеющий заглавное звено.

4. Внутреннее представление результатов.

1) Линейный ациклический однонаправленный  статический список, к которому добавили ещё одно звено, имеющее определенное заданное значение.

2) Линейный ациклический однонаправленный статический список, последнее заполненное звено которого удалено.

3) Номер последнего заполненного  звена линейного ациклического  однонаправленного статического  списка.

4) Линейный ациклический однонаправленный  статический список, имеющий заглавное звено.

 

3. Текст программы.

Proga.h

#ifndef _proga_H

#define _proga_H

const int n = 3;

struct Stack

{

int A[n];

int count;

};

void Creation(Stack *p)

{

p->count = 0;

}

//-----------------------------------------------

void vivodelementov(Stack *p)

{

int i = 1;

do

{

printf("Элемент стека:  %d \n", (p->A[p->count - i]));

i = i + 1;

} while (p->count - i >= 0);

 

}

//-----------------------------------------------

int proverkanapustoty(Stack *p)

{

if (p->count == 0) return 1;

else if (p->count == n) return -1;

else return 0;

}

//-----------------------------------------------

void Add(Stack *p, int value)

{

p->A[p->count] = value;

p->count++;

}

//-----------------------------------------------

int Delete(Stack *p)

{

p->count--;

return p->A[p->count];

}

//-----------------------------------------------

int Size(Stack *p)

{

return p->count;

}

//-----------------------------------------------

#endif

 

ConsoleApplecation15.cpp

 

#include "stdafx.h"

#include <iostream>

#include "proga.h"

using namespace std;

void main()

{

setlocale(LC_ALL, "Russian");

Stack s;

Creation(&s);

int number;

int b = 0;

int value;

do

{

printf("1. Добавить элемент\n");

printf("2. Удалить элемент\n");

printf("3. Узнать размер стека\n");

printf("4. Вывести элементы стека\n");

printf("0. Выйти\n");

printf("Номер команды > ");

scanf_s("%i", &number);

switch (number)

{

case 1:

if (proverkanapustoty(&s) == -1) printf("Стек заполнен\n\n");

else

{

printf("Введите элемент: ");

scanf_s("%d", &value);

Add(&s, value);

printf("Элемент добавлен в стек\n\n");

} break;

//-----------------------------------------------

case 2:

if (proverkanapustoty(&s) == 1) printf("Стек пуст\n\n");

else

{

int x = Delete(&s);

printf("Элемент %d удален из стека\n\n", x);

} break;

//-----------------------------------------------

case 3:

if (proverkanapustoty(&s) == 1) printf("Стек пуст\n\n");

else

printf("Размер стека: %d \n\n", Size(&s));

break;

//-----------------------------------------------

case 4:

if (proverkanapustoty(&s) == 1) printf("Стек пуст\n\n");

else

{

vivodelementov(&s);

} break;

//-----------------------------------------------

case 0: break;

break;

}

} while (number != 0);

 

system("pause");

}

6 Тесты.

 

№	Дано n, (A)	Результат	Примечание
0			Вывод меню
Проверка работоспособности, при одном введенном элементе.
1	1 2		Добавление элемента 2 в стек
2	3		Проверка размера стека
3	4		Вывод элементов стека
4	2		Удаление элемента стека( взятие элемента из стека)
5	0		Выход
Проверка работоспособности, при двух введенных элементах.
1	1 2 1 3		Добавление элементов 2 и 3 в стек
2	3		Проверка размера стека
3	4		Вывод элементов стека
4	2 2		Удаление элементов 3 и 2( взятие элемента из стека)
5	0		Выход
Проверка работоспособности, при трех введенных элементах.
1	1 2 1 3 1 4		Добавление элементов 2 3 и 4 в стек
2	3		Проверка размера стека
3	4		Вывод элементов стека
4	2 2 2		Удаление элементов 2 3 и 4 из стека( взятие элемента из стека)
5	0		Выход
Проверка работоспособности при пустом стеке
1	2		Удаление элемента(взятие элемента)
2	3		Проверка размера стека
3	4		Вывод элементов стека
4	1		Добавление элемента
5	0		Выход

 

 

7 Результаты.

 Результаты тестов соответствуют ожидаемым, что показывает корректность программы решения задачи.