Упорядочение данных
Методика упорядочивания таблицы "Магазин", состоящей из наименования, цены и количества товара. Упорядочивание по возрастанию цены методом пирамидальной (древесной) сортировки. Преобразование таблицы, посредством удаления товаров дороже заданной цены.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | лабораторная работа |
| Язык | русский |
| Дата добавления | 02.06.2013 |
| Размер файла | 20,2 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Министерство образования и науки РФ
Новосибирский государственный технический университет
Кафедра прикладной математики
Лабораторная работа №5
по теме «УПОРЯДОЧЕНИЕ ДАННЫХ»
Факультет: ПМИ
Группа: ПМ-22
Студент: Хохлова Т.Ю.
Преподаватель: Еланцева И. Л.
Новосибирск 2013
Условие задачи
Дана таблица «Магазин», состоящая из наименования, цены и количества товара. Упорядочить таблицу по возрастанию цены методом пирамидальной (древесной) сортировки. Преобразовать таблицу, удалив товары дороже заданной цены.
Анализ задачи
Дано:
T[i] ::= <магазин >, i=1,N, где N - максимальное количество элементов таблицы
<магазин >::= <наименования> <цена> <количество><магазин>|<наименования> <цена> <количество>
<наименования> ::= символы из подмножества латинских букв
<цена> ::= целое число
<количество> ::= целое число
- заданная цена
Результат:
T[i] ::= <магазин >, i=1,N, где N - максимальное количество элементов таблицы
<магазин >::= <наименования> <цена> <количество><магазин>|<наименования> <цена> <количество>
<наименования> ::= символы из подмножества латинских букв
<цена> ::= целое число
<количество> ::= целое число
(Упорядоченная по цене таблица «Магазин» без элементов дороже заданной цены)
Или сообщение о том, что таблица пуста
Решение:
1) Ввод таблицы
При i=0, n=0;
Записываем первый элемент А в таблицу
n=n+1
повторять
T[i]=A
n=n+1
i=n-1
Пока не конец файла
2) Сортировка
n - размер таблицы
1.1. Пирамида(Таблица T, L, R)
i=L
j=2L+1
x=TL
Если , то j=j+1
Пока
Повторять
k=T[i]
T[i]=T[j]
T[j]=k
i=j
j=2j+1
Если , то j=j+1
Сортировка
L=n/2
R=n-1
Пока L>0
Повторять
L=L-1
Пирамида(T,L,R)
Пока R>0
Повторять
X=T[0]
T[0]=T[R]
T[R]=x
Пирамида(T,L,R)
Удаление элементов дороже заданной цены из упорядоченной по цене таблицы:
При i=0
Повторять
i=i+1
Пока
n=i
если n=0, то таблица пуста
Структура основных входных и выходных данных
Внешнее представление:
Входные данные представлены в файле в виде таблицы.
Выходные данные так же представлены в виде таблицы.
Внутреннее представление:
Данные представлены в виде статической таблицы, вида:
struct shop
{
char name[10];
int price;
int col;
};
struct table
{
shop s[N];
int n;
};
Алгоритм
Ввод таблицы
Записать первый элемент A в таблицу
T->s[i]=A;
T->n=T->n+1;
while(не конец файла «Магазин»)
{
Записать следующий элемент A в таблицу
i++;
T->s[i]=A;
T->n=T->n+1;
i=T->n-1;
}
Пирамида (таблица T, L, R)
{
i=L;
j=2*L+1;
x=T->s[L];
if ((j<R) && (T->s[j].price<T->s[j+1].price))
j++;
while ((j<=R) && (x.price<T->s[j].price))
{
k=T->s[i];
T->s[i]=T->s[j];
T->s[j]=k;
i=j;
j=2*j+1;
if ((j<R) && (T->s[j].price<T->s[j+1].price))
j++;
}
}
Сортировка(Таблица Т, n)
{
L=n/2; R=n-1;
while (L>0)
{
L=L-1; pir(T,L,R);
}
while (R>0)
{
x=T->s[0];
T->s[0]=T->s[R];
T->s[R]=x;
R--;
pir(T,L,R);
}
}
Удаление
{
for (i=0;i<T->n && T->s[i].price<z; i++);
T->n=i;
if (i==0) таблица пуста;
}
Текст программы
таблица пирамидальный сортировка упорядочивание
#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <conio.h>
#define N 100
struct shop
{
char name[10];
int price;
int col;
};
struct table
{
shop s[N];
int n;
};
int del(table *T, int z)
{
int i;
for (i=0;i<T->n && T->s[i].price<z; i++);
T->n=i;
if (i==0) {printf("net");
return 0;}
return 1;
}
void pir(table *T, int L, int R)
{
int i,j;
shop k,x;
i=L;
j=2*L+1;
x=T->s[L];
if ((j<R) && (T->s[j].price<T->s[j+1].price))
j++;
while ((j<=R) && (x.price<T->s[j].price))
{
k=T->s[i];
T->s[i]=T->s[j];
T->s[j]=k;
i=j;
j=2*j+1;
if ((j<R) && (T->s[j].price<T->s[j+1].price))
j++;
}
}
void Sort (table *T, int n)
{
int L,R;
shop x;
L=n/2; R=n-1;
// построение пирамиды из исходного массива
while (L>0)
{
L=L-1; pir(T,L,R);
}
//сортировка:пирамида=>отсортированный массив
while (R>0)
{
x=T->s[0];
T->s[0]=T->s[R];
T->s[R]=x;
R--;
pir(T,L,R);
}
}
void main()
{
FILE *f;
int i=0,t,j,k=1,z;
table *T;
shop A,x;
T=new table;
T->n=0;
if ((f=fopen("shop.txt","r"))==NULL) printf("error");
else
{
fscanf(f,"%s %d %d",&A.name,&A.price,&A.col);
T->s[i]=A;
T->n=T->n+1;
if (T->n==N) {printf("polna\n"); k=0;}
while(!feof(f) && k)
{
fscanf(f,"%s %d %d",&A.name,&A.price,&A.col);
i++;
if (T->n==N) {printf("polna\n"); k=0;}
T->s[i]=A;
T->n=T->n+1;
i=T->n-1;
}
if (k)
{
i=0;
printf("name|price|col");
printf("\n---------");
for(i=0;i<T->n;i++)
printf("\n%s %d %d\n", T->s[i].name,T->s[i].price,T->s[i].col);
Sort (T,T->n);
printf("name|price|col");
printf("\n---------");
for(i=0;i<T->n;i++)
printf("\n%s %d %d\n", T->s[i].name,T->s[i].price,T->s[i].col);
printf("\nPrice:");
scanf("%d",&z);
if (del(T,z))
{
printf("name|price|col");
printf("\n---------");
for(i=0;i<T->n;i++)
printf("\n%s %d %d\n", T->s[i].name,T->s[i].price,T->s[i].col);
}
}
}
_getch();
fclose(f);
}
Тесты
|
«Магазин» |
Заданная цена |
Результат |
Примечания |
|
|
dvd 5 40 bag 7 30 toy 2 10 dog 5 7 cat 2 3 av 5 6 cc 3 4 |
4 |
toy 2 10 cat 2 3 cc 3 4 |
не упорядочено |
|
|
dvd 5 40 bag 7 30 toy 2 10 dog 5 7 cat 2 3 av 5 6 |
7 |
toy 2 10 cat 2 3 cc 3 4 av 5 6 dog 5 7 dvd 5 40 |
не упорядочено |
|
|
dvd 5 40 bag 7 30 toy 2 10 dog 5 7 cat 2 3 av 5 6 cc 3 4 |
1 |
net |
Нет элементов меньше заданной цены |
Размещено на Allbest.ru
...Подобные документы
Использование электронной таблицы как базы данных. Сортировка и фильтрация данных в Microsoft Excel 97. Сортировка - это упорядочение данных по возрастанию или по убыванию. При фильтрации базы отображаются только записи, обладающие нужными свойствами.
реферат [6,6 K], добавлен 17.11.2002Алгоритмы сортировки методами простых вставок и пузырька. Зависимость среднего времени сортировки от числа сортируемых элементов. Функции, осуществляющие сортировку любого количества элементов методом простых вставок, на основе сортировки таблицы адресов.
курсовая работа [557,1 K], добавлен 26.05.2010Проектирование структуры базы данных. Конструирование структуры будущих таблиц баз данных, основные приемы их заполнения и редактирования. Простая сортировка значений таблицы. Поиск записей по образцу. Как правильно сохранить и загрузить базу данных.
практическая работа [4,4 M], добавлен 02.04.2009Разработка исходной таблицы для хранения данных о выставках города. Сортировка данных и подведения промежуточных итогов. Параметры сортировки. Пример использования автофильтра. Сводные таблицы. Создание презентации в MS Powerpoint. Слайды презентации.
контрольная работа [4,1 M], добавлен 16.12.2013Создание макроса, позволяющего вставить строку текста, содержащую фамилию и группу, начиная с текущей ячейки, задать для таблицы чисел, состоящей из четырех столбцов и трех строк, найти сумму элементов таблицы, задать границы для полученной таблицы.
контрольная работа [1,3 M], добавлен 28.12.2009Определение условий рынка продукции полиграфии. Разработка структуры таблицы для хранения и обработки информации. Прогнозирование изменения цены по каждому товару с помощью линии тренда. Построение листа интерфейса для управления оптимизационной задачей.
курсовая работа [478,7 K], добавлен 13.12.2014Применение Microsoft Access в базах данных. Создание системы управления базами данных, обеспечивающей информационную работу магазина "Автозапчасти" и позволяющей сотрудникам магазина быстро просматривать ассортимент товара, наличие его на складе, цены.
курсовая работа [2,7 M], добавлен 13.10.2012Структура таблицы и типы данных. Ввод данных в ячейки таблицы. Создание запросов на выборку, удаление, обновление и добавление записей, на создание таблицы. Основное различие между отчетами и формами, их назначение. Создание отчетов для базы данных.
курсовая работа [1,9 M], добавлен 17.06.2014Составление таблицы согласно образцу в программе MS Excel. Создание данных таблицы базы данных. Введение формул в программе MS Excel. Установление связи между таблицами. Создание запроса на выборку данных из одной таблицы с помощью мастер запросов.
контрольная работа [4,0 M], добавлен 17.04.2016Учет товаров, контроль их срока хранения на складах фирмы как предметная область проектируемой базы данных "Хранение товаров". Содержание основных запросов базы данных. Методы сортировки массива данных - пузырька, цифровой сортировки и деревьев сравнений.
контрольная работа [3,4 M], добавлен 12.02.2014Подключение форм через макросы для добавления, удаления, поиска, сортировки и изменения данных. Назначение расширенного фильтра. Вывод промежуточных итогов и последовательность действий при создании сводной таблицы. Способы создания макросов в MS Excel.
курсовая работа [852,1 K], добавлен 15.11.2013Разработка модели информационной системы "Рыболовный магазин" с помощью СУБД Firebird. Компоненты программного продукта. Физическая диаграмма базы данных, обзор функций добавления, изменения, удаления и сортировки данных. Руководство администратора.
курсовая работа [406,2 K], добавлен 21.02.2016Создание и оформление исходных таблиц, их связывание; расчеты в таблицах с применением "Мастера функций"; обработка данных посредством сортировки и выборки (фильтрации); построение диаграмм; оформление отчета в виде комплексного текстового документа.
контрольная работа [1,7 M], добавлен 26.03.2012Особенности поиска среднеарифметического значения элементов массива. Общая характеристика проблем разработки в среде Turbo Pascal программы упорядочивания массива по возрастанию. Рассмотрение основных этапов разработки программы на языке PASCAL.
курсовая работа [896,7 K], добавлен 18.05.2014Исследование основных особенностей алгоритмов быстрой и поразрядной сортировки данных. Построение графиков зависимости времени сортировки от количества элементов в файле и от степени перемешенности элементов. Описания сортировки чисел и строковых данных.
лабораторная работа [1,2 M], добавлен 23.07.2012Вычисление суммы ряда с заданной точностью. Форма представления исходных данных. Разработка алгоритма и его описание. Выбор метода обработки информации. Упорядочение элементов строк матрицы по возрастанию. Программа подсчета числа слов в предложении.
курсовая работа [23,9 K], добавлен 11.02.2016Языки разметки и таблицы стилей. Базы данных и СУБД для web-приложений. Поддержка, обслуживание и продвижение сайтов. Этапы составления индекса и поиска по нему. Программно-технические средства приложения. Верстка страниц, публикация данных сайта.
дипломная работа [1,6 M], добавлен 12.12.2013Анализ предметной области - магазин "Канцелярские товары". Проектирование и реализация учебной базы данных магазина. Перечень хранимой информации: таблицы, поля, типы. Выделение сущностей, атрибутов, ключей, связей. Создание и запуск базовых запросов SQL.
курсовая работа [2,4 M], добавлен 09.08.2015Автоматизация процесса распознавания и сравнения файлов Excel. Поиск минимальной цены для каждого наименования. Решение проблемы по причине существующих различий в минимальной партии товара. Тестирование программы с Excel файлами с разным числом строк.
контрольная работа [484,9 K], добавлен 25.01.2014Структурные элементы электронной таблицы: форматирование рабочего листа, работа с именованными блоками, создание списков для ввода данных. Возможности функции ЕСЛИ при выполнении расчетов. Анализ данных в электронных таблицах и требования к ним.
курсовая работа [24,2 K], добавлен 16.04.2014
