Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Робота з розрідженими масивами за допомогою масиву вказівників
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
ЗІ
Кафедра:
Кафедра автоматизованих систем управління
Інформація про роботу
Рік:
2011
Тип роботи:
Розрахункова робота
Предмет:
Програмування частина 4 Технологія системного програмування
Група:
ВП
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Кафедра автоматизованих систем управління
Розрахункова робота
Тема: «Робота з розрідженими масивами за допомогою масиву вказівників»
Львів 2011
ВСТУП
ПРОЕКТУВАННЯ РОЗРІДЖЕНИХ МАСИВІВ
Розглянуто питання створення структурованого типу даних – розріджених масивів (sparse arrays) для здійснення ефективної роботи з матрицями великих розмірів,у яких значна кількість елементів не використовується. Здатність розріджених масивів оптимізувати доступ до таких даних робить їх надзвичайно корисними в багатьох задачах, які виникають під час розроблення сучасних програмних продуктів. До таких задач належить робота з топологічними матрицями, які використовуються для відображення зв'язків елементів у електронних схемах, що асоціюються з її клітинами. Завдяки використанню розріджених масивів пам'ять для зберігання кожної з таких клітин виділяється з пули вільної пам'яті тільки в міру потреби.
Той факт, що пам'ять для масиву виділяється при його створенні, означає, що розмір найбільшого масиву, який ви зможете описати у своїй програмі, обмежений (зокрема) обсягом доступної пам'яті. Якщо вам знадобиться масив більшого розміру, ніж дозволяють можливості комп'ютера, доведеться реалізовувати його якимось іншим чином. Навіть якщо великий масив розміститься в пам'яті, створення його може істотно зменшити доступні ресурси системи, оскільки пам'ять, зайнята великим масивом, виявляється недоступною для іншої частини програми та інших процесів, що працюють в системі. А це в свою чергу може негативно позначитися на загальній продуктивності програми або комп'ютера в цілому. У тих ситуаціях, коли будуть використовуватися не всі елементи масиву, виділення пам'яті під весь масив представляється особливо марнотратною тратою системних ресурсів.
Щоб позбутися від проблем, викликаних потребою в пам'яті для великих рідко заповнених масивів, були придумані деякі прийоми роботи з розрідженими масивами. Всі вони характеризуються однією спільною рисою: пам'ять для елементів масиву виділяється тільки при необхідності.
ОГЛЯД ЛІТЕРАТУРИ
Під час виконання різних інженерних розрахунків часто доводиться
мати справу з так званими розрідженими масивами, значна кількість елемен-
тів яких фактично не використовується. У середовищі фахівців, робота яких пов'язана з дослідженням розріджених масивів, у обігу широко вживають два терміни: логічний і фізичний масиви. Логічний масив є уявним, фігурує тільки у математичних записах і графічних представленнях, а фізичний – фактично існує тільки в програмі. Наприклад, якщо певна електронна схема описується топологічною матрицею (суміжності чи інциденцій) розміром 100×5000 елементів, то логічний масив складатиметься з такої ж самої кількості елементів навіть у тому разі, якщо цей масив у програмі фізично не існує. Якщо у цій матриці фактично використовуються тільки 100 елементів, то саме вони і займатимуть фізичну пам'ять комп'ютера.
Поодинокі елементи чи навіть структури (записи), які зберігаються у звичайному масиві (чий індекс є аналогом ключа), можуть бути знайдені дуже швидко і без будь-яких порівнянь. Якщо відомо ключ (тобто індекс масиву), розмір запису і початкову адресуа масиву, то адресу потрібного запису обчислюємо за допомогою множення і додавання. Зазвичай, це питання стає цікавим тільки тоді, коли нам потрібно зберігати значну кількість записів. Нехай, замість 100 елементів у нас є 5 000, а розмір топологічної матриці залишається попереднім. Наш гіпотетичний масив, який складається з такої кількості елементів, все ще на 99 % порожній, тобто ми тепер не можемо знехтувати проблемою пошуку потрібного запису серед їх півмільйонної кількості. Структурований тип даних, який має назву розріджений масив, якраз і призначений для вирішення таких неоднозначних ситуацій шляхом ефективного пошуку відповідних об'єктів.
Розгляд основних особливостей проектування одно- і двовимірних розріджених масивів для роботи з матрицями, більшість елементів яких не використовується, є актуальним, становить науковий і практичний інтерес, є основною метою даної роботи.
1. Проектування розріджених масивів
Більшість питань, які виникають у програмістів під час обробляння матриць великих розмірів, стосуються в реалізації механізму індексування елементів масивів. Деякі з сучасних прикладних програм працюють з дуже великими масивами, значна частина елементів яких дорівнює нулю або відповідає якомусь іншому значенню за замовчуванням. У процесі розроблення таких програм вигідним є усунення витрат пам'яті не тільки для їх зберігання, але й для здійснення ефективного пошуку потрібного елемента. Розріджені масиви є динамічними структурами об'єктів, які поводяться як масиви, але не вимагають місця в пам'яті комп'ютера для зберігання значень даних, які містять нулі або певні значення за замовчуванням.
Рис. 1. Розподіл пам'яті у дновимірному розрідженому масиві:
а) структура об'єкта;
б) схема динамічної структури об'єктів
На рис. 1 показано розподіл пам'яті у одновимірному розрідженому масиві, об'єкти якого зберігають значення цілих чисел. Кожен об'єкт цієї динамічної структури має три поля: номер стовпця, самі дані і покажчик, який посилається на наступний об'єкт справа. Заголовний об'єкт, крайній зліва, має номер стовпця -1 і не містить даних. Перший значущий об'єкт ( з номером 0) містить значення 4. Другий об'єкт (з номером 1) у структурі не показаний взагалі. В цьому випадку вважається, що об'єкт 1 зберігає значення за замовчуванням. Третій об'єкт (з номером 2) зберігає значення 12.
На рис. 2 показано розподіл пам'яті у двовимірному розрідженому масиві цілих чисел. Незважаючи на те, що це пряме узагальнення одновимірно го розрідженого масиву, кожен об'єкт цієї структури входить у два списки і, окрім номера стовпця, має ще і номер рядка. Хоча двовимірний варіант масиву є дещо складнішим у реалізації порівняно з одновимірним, проте він набагато вигідніший для економного зберігання значень даних. У деяких випадках найбільш важливою частиною розріджених масивів є "дірки" – об'єкти, які явно не зберігаються в пам'яті комп'ютера.
/
Проектуючи динамічну структуру даних – одновимірний розріджений масив, зазвичай використовують перевантаження операторної функції operator[](), яка одночасно реалізує запис і зчитування об'єктів. Проте такий підхід має свої недоліки, їх вдало усувають під час реалізації роботи двовимірного
розрідженого масиву, у якому ця функція взагалі не використовується.
ФОРМУЛЮВАННЯ ЗАДАЧІ
Основним завданням моєї розрахункової роботи є опрацювання задачі написаної на мові програмування С. Суть моєї програми полягає в описі роботи з розрідженими масивами за допомогою масиву вказівників. Після запуску програми буде показаний результат роботи, після чого буде виконаний вихід з програми.
АЛГОРИТМ РОЗВ’ЯЗАННЯ ЗАДАЧІ
Припустимо, що електронна таблиця має розмір 26x100 (від А1 до Z100), тобто складається з 2 `600 елементів. Теоретично можна зберігати елементи таблиці в масиві структур . Але 2 `600, помножене на 137 байтів (розмір цієї структури в байтах), дорівнює 356` 200 байт пам'яті. Це дуже великий обсяг пам'яті, щоб витрачати його на не повністю використовується масив. Тим не менш, можна створити масив вказівників (pointer array) на структури типу cell .Для зберігання масиву покажчиків потрібно набагато менше пам'яті, ніж для масиву структур. При кожному присвоєння клітинці логічного масиву даних під ці дані виділяється пам'ять, а відповідним вказівником в масиві вказівників присвоюється адреса виділеного фрагмента. Така схема дозволяє домогтися більш високої продуктивності, аніж при списку або двійковому дереві.
Цей менший за обсягом займаній пам'яті масив використовується для зберігання вказівників на електронну таблицю даних. При введенні чергового запису в відповідному полі масиву заноситься вказівник на введені дані. На рис. 1. показано, як виглядає в пам'яті розріджений масив, представлений у вигляді масиву вказівників.
+-+-+-+-+-+-+-+-+-+-+-+-+
|.|.| 0 | 0 |. | 0 | 0 | 0 |. | 0 | 0 | 0 |
+|+|+-+-+|+-+-+-+|+-+-+-+
| | | | +----+
| | | '-> | A [8] |
| | | +----+
| | | +----+
| | '-> | A [4] |
| | +----+
| | +----+
| '-> | A [1 ] |
| +----+
| +----+
'-> | A [0] |
+----+
Рис. 1. Подання розрідженого масиву у вигляді масиву вказівників
Перед використанням масиву вказівників кожен його елемент необхідно проініціалізувати нулем), що означає відсутність цього запису.
КОД ПРОГРАМИ
#include "stdafx.h"
#include <stdlib.h>
struct cell {
char cell_name[9];
char formula[128];
} list_entry,*curr;
struct cell *sheet[2600]; /* массив з 2600 вказівників */
void init_sheet(void);
void store(struct cell *i);
void deletecell(struct cell *i);
struct cell *find(char *cell_name);
int main(int argc, CHAR* argv[])
{
printf("Enter name: ");
scanf("%s",list_entry.cell_name);
printf("Enter formule: ");
scanf("%s",list_entry.formula);
char s[30];
init_sheet();
store (&list_entry);
printf("Enter name of cell: ");
scanf ("%s",s);
curr=find(s);
if (curr!=NULL) {
printf("\n\n%s\n",curr->cell_name);
printf("%s\n",curr->formula);
}
return 0;
}
void init_sheet(void) {
register int t;
for(t=0; t < 2600; ++t)
sheet[t] = NULL;
}
void store(struct cell *i) {
int loc;
char *p;
/* знаходження індексу за заданним ім'ям */
loc = *(i->cell_name) - 'A'; /* стовпчик */
p = &(i->cell_name[1]);
loc += (atoi(p)-1) * 26; /* кількість рядків * ширина рядка +
стовпчик */
if(loc >= 2600) {
printf("Komirka za mezamu masyvu.\n");
return;
}
sheet[loc] = i; /* помістити вказівник в масив */
}
void deletecell(struct cell *i) {
int loc;
char *p;
/* знаходження індексу за заданним ім'ям комірки */
loc = *(i->cell_name) - 'A'; /* стовпчик */
p = &(i->cell_name[1]);
loc += (atoi(p)-1) * 26; /* кількість рядків * ширина рядка +
стовпчик */
if(loc >= 2600) {
printf("Komirka za mezamu masyvu.\n");
return;
}
if(!sheet[loc]) return; /* не звільняти, якщо вказівник нульовий
(null) */
free(sheet[loc]); /* звільнити системну пам'ять */
sheet[loc] = NULL;
}
struct cell *find(char *cell_name) {
int loc;
char *p;
/* знаходження індексу за заданним ім'ям комірки */
loc = *(cell_name) - 'A'; /* стовпчик */
p = &(cell_name[1]);
loc += (atoi(p)-1) * 26; /* кількість рядків * ширина рядка +
стовпчик */
if(loc>=2600 || !sheet[loc]) { /* ця комірка пуста */
printf("Komirka ne znaydena.\n");
return NULL; /* пошук невдалий */
}
else return sheet[loc];
}
КОНТРОЛЬНІ ПРИКЛАДИ ТА РЕЗУЛЬТАТИ РЕАЛІЗАЦІЇ
/
ВИСНОВОК
Створюючи дане розрахункове завдання я засвоїла роботу з розрідженими масивами за допомогою масиву вказівників. На основі цього розробила програму.
У своїй роботі я використала мову програмування С, тому здобула хороші навики в роботі з цим середовищем.
Програма швидко і з точністю працює з великими масивами, та багатьма змінними.
Метод реалізації розрідженого масиву на основі масиву вказівників забезпечує набагато швидший доступ до елементів, ніж методи на основі пов'язаного списку та двійкового дерева.Якщо масив не дуже великий, виділення пам'яті для масиву вказівників лише незначно зменшує обсяг вільної пам'яті системи. Тим не менш, в масиві покажчиків для кожного осередку виділяється певний обсяг пам'яті незалежно від того, використовується вона чи ні. У деяких додатках це може бути обмеженням, хоча в загальному випадку це не є проблемою.
25.12.2013 03:12-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора