Лабораторная работа №1 (стек)
.doc
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
КАФЕДРА АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ
Лабораторная работа №1
по дисциплине
«Структуры и алгоритмы»
на тему:
«Программирование линейных структур данных»
|
|
Студент |
|
|
|
Ключанских А.С |
|
||||||||
|
|
|
|
подпись, дата |
|
фамилия, инициалы |
|
||||||||
|
|
Группа |
|
АС-10 |
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
||||||||
|
|
Принял |
|
|
|
|
|
||||||||
|
|
|
|
|
|
Журавлева М.Г. |
|
||||||||
|
|
ученая степень, звание |
|
подпись, дата |
|
фамилия, инициалы |
|
||||||||
Липецк 2011
-
Задание
Разработать программу, реализующую одну из основных линейных структур данных: стек, очередь, дек, список, с использованием нескольких представлений структуры данных в памяти: а) с помощью статического массива, б) с помощью динамического массива, в) с помощью указателей.
Варианты задания представлены в таблице 1. Номер варианта выбирается в соответствии с номером по журналу.
Предусмотреть хранение индекса (номера) каждого элемента структуры данных. Программа должна предоставлять пользователю интерфейс, позволяющий выполнять:
а) выбор одного из трех указанных способов представления структуры данных в памяти;
б) выход из программы;
в) создание структуры данных «с нуля» - вначале структура данных не содержит ни одного элемента;
г) следующие операции над структурой данных:
-
Добавление элемента (если возможно: в начало, конец, произвольную заданную позицию).
-
Удаление элемента (если возможно: из начала, из конца, из произвольной заданной позиции).
-
Поиск элемента.
-
Замена «старого» значения элемента на заданное новое (поиск по значению).
-
Установка значения элемента по заданному индексу (поиск по индексу).
-
Получение значения элемента по заданному индексу.
-
Удаление всех элементов.
-
Генерация структуры данных с заданным числом элементов.
-
Вывод на экран элементов структуры (для стеков, деков, очередей нужно использовать дополнительные временные «хранилища», а не реализовывать не присущие данным структурам функции).
К сгенерированной структуре данных должны быть применимы все остальные функции.
Вариант 1:
Структура данных: стек int + double
-
Блок-схема программы
-
Листинг программы
//Стек
#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
#include <conio.h>
#define LEN 5
struct key{
int i;
double d;
}Y[LEN];
struct st{
int B;
int N;
int V;
struct key *X;
}stack,stack2;
char s[]="\n1. Добавить элемент \n2. Удалить элемент\n3. Показать элемент \n4. Поиск и замена\n5. Вывод всех элементов\n6. Сгенерировать структуру данных\n7. Удалить все \n8. Выход";
struct list
{
struct key value;
struct list * next;
}*head;
enum method{ptr,arr,darr}m;
int i,N;
char ch;
void start(),menu1(),menu2();
void push(struct st &stack,struct key a),push(struct list **head,struct key a),search(struct st &stack),search(struct list **head);
struct key pop(struct st &stack),pop(struct list **head);
void show(struct st stack),show(struct list *head), print(struct key),show_all(struct st &stack),show_all(struct list **head),gen(struct st &stack),gen(struct list **head),remove_all(struct st &stack),remove_all(struct list **head);
struct key fill()
{
struct key z;
printf("\nВведите int: ");
scanf("%d",&z.i);
printf("\nВведите double: ");
scanf("%lf",&z.d);
return z;
}
void main()
{
setlocale(LC_ALL,"Russian");
start();
printf("\nДля продолжения нажмите любую клавишу");
getch();
}
void start()
{
printf("\n Выберите способ представления стека:\n1).Указатели\n2).Массив\n3).Динамический массив\n4). Выход");
ch=-1;
stack.N=0;
while(!(ch>='1'&&ch<='4'))ch=getch();
m=(method)ch;
switch(m)
{
case '2':
{
stack.B=-1;
m=arr;
printf("\n 2 Массив");
stack.X=&Y[0];
stack.V=LEN;
menu1();
break;
}
case '3':
{
m=darr;
printf("\n 3 Динамический массив");
stack.X=(struct key*)malloc(sizeof(struct key));
stack.B=-1;
stack.V=1;
menu1();
break;
}
case '1':
{
m=ptr;
printf("\n 1 Указатели");
menu2();
break;
}
};
}
void print(struct key z)
{
printf("\nint=%d, double=%lf",z.i, z.d);
}
void menu1()
{
// Работа с массивом
while(ch!='8')
{
puts(s);
ch=getch();
while(!(ch>='1'&&ch<='8'))ch=getch();
switch(ch)
{
case '1': push(stack,fill());break;
case '2': pop(stack);break;
case '3': show(stack);break;
case '4': search(stack);break;
case '5': show_all(stack);break;
case '6': gen(stack);break;
case '7': remove_all(stack);break;
}
}
printf("\nВыход");
printf("\nВывод массива");
if(m==darr)free(stack.X);
start();
}
void push(struct st &stack,struct key a)
{
if(stack.N==stack.V)
{
if(m==arr)
{
printf("Стек переполнен, удалите элементы");
return;
}
else
{
if(m==arr)return;
stack.V+=10;
stack.X=(struct key *)realloc(stack.X,stack.V*sizeof(struct key));
}
}
stack.B++;
stack.X[stack.B]=a;
stack.N++;
}
struct key pop(struct st &stack)
{
if(stack.N){stack.N--;stack.B--;}
else return stack.X[stack.B];
return stack.X[stack.B+1];
}
void show(struct st stack)
{
if(stack.N)print(stack.X[stack.B]);
else printf("\nЭлементов нет");
}
void search(struct st &stack)
{
int i;
bool flag=1;
printf("\nВведите искомый элемент:");
struct key a=fill(),b;
struct st stack2;
stack2.B=-1;
stack2.N=0;
stack2.X=(struct key *)malloc(sizeof(struct key));
int n=stack.N;
for(i=0;i<n;i++)
{
b=pop(stack);
if(a.i==b.i&&a.d==b.d)
{
printf("\nЭлемент найден");
printf("\nВведите новое значение");
b=fill();
}
push(stack2,b);
}
for(i=0;i<n;i++)push(stack,pop(stack2));
if(flag)printf("\n Элемент не найден");
}
void show_all(struct st &stack)
{
struct st stack2;
stack2.B=-1;
stack2.N=0;
stack2.X=(struct key *)malloc(sizeof(struct key));
struct key b;
int N=stack.N;
for(i=0;i<N;i++)
{
b=pop(stack);
print(b);
push(stack2,b);
}
for(i=0;i<N;i++)push(stack,pop(stack2));
}
void gen(struct st &stack)
{
printf("\nВведите количество элементов: ");
int n;
scanf("%d",&n);
remove_all(stack);
struct key a;
for(int i=0;i<n;i++)
{
a.i=rand();
a.d=(float)rand()*rand()/rand();
push(stack,a);
}
printf("\nНовые элементы");
show_all(stack);
}
void remove_all(struct st &stack)
{
while(stack.N)pop(stack);
}
void menu2()
{
head=0;
// Работа с односвязным списком
N=0;
while(ch!='8')
{
puts(s);
ch=getch();
while(!(ch>='1'&&ch<='8'))ch=getch();
switch(ch)
{
case '1': push(&head,fill());break;
case '2': pop(&head);break;
case '3': show(head);break;
case '4': search(&head);break;
case '5': show_all(&head);break;
case '6': gen(&head);break;
case '7': remove_all(&head);break;
}
}
}
void push(struct list **head,struct key a)
{
struct list *ptr=*head;
*head=(struct list*)malloc(sizeof(struct list));
(*head)->next=ptr;
(*head)->value=a;
N++;
}
struct key pop(struct list **head)
{
struct key z;
z.d=z.i=0;
if(!*head)
{
printf("Элементов нет");
return z;
}
struct list *ptr=*head;
*head=(*head)->next;
z=ptr->value;
free(ptr);
N--;
return z;
}
void show(struct list *head)
{
if(head)print(head->value);
else printf("\nЭлементов нет");
}
void search(struct list **head)
{
int i;
bool flag=1;
printf("\nВведите искомый элемент:");
struct key a=fill(),b;
struct list *head2;
int n=N;
for(i=0;i<n;i++)
{
b=pop(head);
if(a.i==b.i&&a.d==b.d)
{
printf("\nЭлемент найден");
printf("\nВведите новое значение");
b=fill();
flag=0;
}
push(&head2,b);
}
for(i=0;i<n;i++)push(head,pop(&head2));
if(flag)printf("\n Элемент не найден");
}
void show_all(struct list **head)
{
struct list *head2;
struct key b;
for(i=0;i<N;i++)
{
b=pop(head);
print(b);
push(&head2,b);
}
for(i=0;i<N;i++)push(head,pop(&head2));
}
void gen(struct list **head)
{
printf("\nВведите количество элементов: ");
int n;
scanf("%d",&n);
remove_all(head);
struct key a;
for(int i=0;i<n;i++)
{
a.i=rand();
a.d=(float)rand()*rand()/rand();
push(head,a);
}
printf("\nНовые элементы");
show_all(head);
}
void remove_all(struct list **head)
{
while(N)pop(head);
printf("\nВсе элементы удалены");
}
-
Контрольный пример
-
Выводы о проделанной работе
При выполнении данной лабораторной работы я разработал программу, реализующую одну из основных линейных структур данных: стек.
-
Список использованной литературы
-
Шилдт Г. Искусство программирования на C++. БХВ.2005
-
Шилдт Г. C++ Руководство для начинающих. Вильямс.2005