Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Структури даних: однозв’язні списки
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра СКС
Інформація про роботу
Рік:
2012
Тип роботи:
Курсова робота
Предмет:
Програмування частина 4 Технологія системного програмування
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Національний університет «Львівська політехніка»
Інститут дистанційного навчання
Кафедра СКС
КУРСОВА РОБОТА
з дисципліни «Програмування»
на тему «Структури даних: однозв’язні списки»
Варіант № 12
Завдання на курсову роботу:
Реалізувати метод сортування двохшляхового злиття послідовності, яка представлена у вигляді лінійного однозв’язного списку, елементи якого містять по декілька інформаційних полів, одне з яких є ключовим , і всі зміни положення елементів в послідовності виконуються не перестановкою самих елементів, а перестановкою їх зв'язків. Намалювати схему алгоритму для конкретного прикладу послідовності з десяти цілих чисел зі знаком. Дослідити метод на стійкість. Дослідити ефективність метода. Дослідити метод на економність використання пам'яті. Дослідити метод на можливу специфіку вхідної послідовності.
Змоделювати фабрику, що виробляє вироби з менших вузлів. Назвемо елементарною деталлю такий вузол, що не складається з дрібніших вузлів. Написати програму, що зчитує набір рядків, які містять чотирьох символьні номери деталей. Перший такий номер у рядку означає неелементарну деталь, а решта чисел означають деталі, з яких складається ця неелементарна деталь. Ці складові деталі можуть бути елементарними, а можуть складатися з інших частин (у такому випадку їх номери з’являться першим номером у якомусь іншому рядку). Програма складає список з елементом заголовку для кожної неелементарної деталі. Заголовок містить назву неелементарної деталі і вказівник на список елементів, що описує її складові частини вказівники на заголовки списків послідовно записуються в список. Для описаного представлення написати програму:
а) роздруку всіх неелементарних деталей.
б) виведення для кожної неелементарної деталі списку всі елементарні деталей з яких вона складається.
ЗМІСТ
ВСТУП……………………………………………………………………….
4
1.
СТАТИЧНА СТРУКТУРА……………………………………………
5
1.1
Синтаксичний аналізатор, що працює зі змінними…………………...
5
1.2
Тестування для наступних значень змінних…………………………..
7
2.
СОРТУВАННЯ З РОЗДІЛЕННЯМ………………………………….
8
2.1
Ідея алгоритму…………………………………………………………..
10
2.1.1 Псевдокод алгоритму……………………………………………..
10
2.2
Виконання алгоритму…………………………………………………...
11
3.
СПИСКИ………………………………………………………………..
16
3.1
Поняття про однонапрямлені однозв’язні списки…………………….
16
3.2
Робота з однозв'язними списками………………………………………
17
3.3
Додавання елемента на початок списку………………………………..
17
3.4
Додавання елемента в кінець списку…………………………………..
19
4.
ОРГАНІЗАЦІЯ ОДНОЗВ’ЯЗНИХ СПИСКІВ……………………...
21
4.1
Операція виділення елемента структури через вказівник…………….
21
4.2
Постановка завдання…………………………………………………….
21
4.3
Опис програми…………………………………………………………..
22
4.4
Текст програми…………………………………………………………..
24
4.5
Результати виконання програми……………………………………….
26
ВИСНОВКИ………………………………………………………………….
27
СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ……………………………..
28
ВСТУП
За допомогою обчислень комп'ютер здатний обробляти інформацію по наперед певному алгоритму. Крім того, комп'ютер за допомогою програмного забезпечення здатний приймати, зберігати і здійснювати пошук інформації, виводити інформацію на різні види пристроїв висновку. Свою назву комп'ютери одержали по своїй основній функції — проведенню обчислень. В даний час функція обчислень для комп'ютерів стає другорядною, і більшість комп'ютерів використовуються для обробки і управління інформацією, а також ігор.
Виконання поставлених перед ним завдань комп'ютер може забезпечувати за допомогою переміщення яких-небудь механічних частин, рухи потоків електронів, фотонів, квантових частинок або за рахунок використання ефектів від будь-яких інших добре вивчених фізичних явищ.
Термін «комп'ютер» є синонімом абревіатури «ЕОМ» (електронної обчислювальної машини).
Після появи персональних комп'ютерів (від англ. personal computer, PC), термін ЕОМ згодом практично витиснений з вживання і замінений зручнішим терміном «комп'ютер».
Архітектура комп'ютерів може безпосередньо моделювати вирішувану проблему, максимально близько (у сенсі математичного опису) відображаючи досліджувані фізичні явища. Так, електронні потоки можуть використовуватися як моделі потоків води при моделюванні гребель або дамб. Так само сконструйовані аналогові комп'ютери були звичайні в 1960-х роках, проте сьогодні стали достатньо рідкісним явищем. У більшості сучасних комп'ютерів проблема спочатку описується в зрозумілому їм вигляді, при цьому вся необхідна інформація представляється в двійковій формі (у вигляді одиниць і нулів), після чого дії по її обробці зводяться до застосування простої алгебри логіки. Оскільки практично вся математика може бути зведена до виконання булевих операцій, достатньо швидкий електронний комп'ютер може бути застосовний для вирішення більшості математичних завдань (а також і більшості завдань по обробці інформації, які можуть бути легко зведені до математичних).
СТАТИЧНА СТРУКТУРА
Незважаючи на те, що стандарт мови С++ досить широкий, деякі теми в ньому не розглядаються. Тут мається на увазі: синтаксичний аналіз виразів. Програми синтаксичного аналізу використовуються для обчислення алгебраїчних виразів, наприклад (100-23)*213. Вони досить корисні і використовуються в багатьох програмах. В цей момент синтаксичні аналізатори оточені певною загадковістю. По різним причинам процедури, використовуючись в процесі синтаксичного розбору, залишаються спадком вибраних.
Дійсно багато програмістів достатньо розумних здаються перед процесом синтаксичного аналізу виразів. Насправді синтаксичний аналіз - виразів досить проста процедура. В багатьох відношеннях вона більш ніж проста задача перед програмістом. Її простота виявляється наслідком строгих правил алгебри. В цій роботі ми розглянемо програму рекурсивного спуску аналізу(recursive-descent parser) і всі процедури, потрібні для аналізу, які дозволять обчислити арифметичні вирази. Однак перш тим як приступити до розробки синтаксичного аналізатору, треба зробити короткий вступ про вирази і правила їх граматичного поділу.
1.1. Синтаксичний аналізатор, що працює зі змінними
Всі мови програмування, багато калькуляторів і електронні таблиці використовують змінні для запам'ятовування значень. У всіх них застосовується синтаксичний аналіз виразів, тому потрібно навчитись обробляти змінні. Щоб досягти цього, нам потрібно удосконалити наш синтаксичний аналіз виразів. Як заявлено раніше, для визначення змінних ми використовуватимемо букви від а до z. Змінні будуть запам'ятовуватися в масиві класу parser . Як наслідок, в клас parser потрібно включити новий член.
#include "macros.h"
struct dummy {
vi A;
dummy(int N) : A(vi(N, 0)) {
}
void change(int i, int v) {
A[i] += v;
}
int sum(int i) {
return accumulate(A.begin(), A.begin() + i + 1, 0);
}
};
struct ftree {
vi B;
ftree(int N) : B(vi(N, 0)) {
}
void change(int i, int v) {
B[i] += v;
int mask = 1;
while(true) {
if(!(i & mask)) {
i |= mask;
if(i >= sz(B)) {
break;
}
B[i] += v;
}
mask <<= 1;
}
}
int sum(int i) {
int r = 0;
while(i >= 0) {
r += B[i];
i = (i&(i+1))-1;
}
return r;
}
};
1.2. Тестування для наступних значень змінних
B1= true, якщо день народження парне число;
false, якщо день народження непарне число;
і1-день народження;
і2 =-і1;
і3= і1*125;
і4 = -і3;
і5 = і3;
r1 – дробове число: ціла частина – місяць народження, дробова частина- рік народження;
r2= r1*125;
r3 = -r2;
Результати тестування:
Якщо дата народження 21.10.1982. то
і 1= 20; і2= -20; і3= 2625; і4= -2625; і5= 2625;
r 1 = 10.1928; r2= 1274.775; r3= - 1274.775;
m[i , j ] – символ, який дорівнює відповідній цифрі номера мобільного телефону:
приклад якщо номер моб.тел. є 80671234567 то:
Результати тестування:
m[ 0,0]=0, m[0,1]= 6, m[0,2]= 7, m[0,3]= 1, m[0,4]= 2,
m[1,0]= 3, m[1,1]=4, m[1,2]=5, m[1,3]=6, m[1,4]=7
2. СОРТУВАННЯ З РОЗДІЛЕННЯМ
Даний метод є одним з кращих методів внутрішнього сортування і вельми ефективний для великих таблиць. Метою кожного кроку в даному методі є приміщення чергового даного запису на кінцеву позицію усередині таблиці. Якщо поступати у такий спосіб, то всі записи, попередні дані, матимуть менший ключ, тоді як все подальші - більший. При використанні такого методу таблиця завжди ділиться на дві підтаблиці. Аналогічний процес може бути застосований до кожної з цих підтаблиць і повторюватися до тих пір, поки всі записи не будуть встановлені на їх кінцеві позиції.
Використовуються два індекси i і j з початковими значеннями меж таблиці. Порівнюються ключі до[i] і до[j], і якщо перестановка не потрібна, то j зменшується на 1, і процес повторюється. У тому випадку, коли до[i]>=k[j], записи r[i] і r[j] міняються місцями. Потім цей процес повторюється з i, збільшеним на 1, і фіксованим j до тих пір, поки не виникає інша перестановка.
Кожного разу таблиця розбивається на дві підтаблиці, одна з яких обробляється, тоді як межі другої запам'ятовуються з тим, щоб вона була оброблена пізніше. У цих цілях може бути використаний стек, що є матрицею з двох стовпців. У першому стовпці зберігаються нижні межі підтаблиць, що розділяються, в другому - верхні межі. Всякий раз одна з отриманих в результаті розділення підтаблиць піддається подальшому розділенню, а межі іншою поміщаються у вільний рядок стека (зазвичай в стек поміщаються межі більшої по довжині таблиці, оскільки це зменшує необхідний розмір стека). Як тільки завершується процес розділення поточної підтаблиці, тобто її довжина стане менше трьох, для розділення береться підтаблиця, межі якої були занесені в стек останніми. Рядок стека, в якому зберігалися ці межі, звільняється. Процес впорядкування завершується, коли стек повністю звільняється. Розділення слід застосовувати для підтаблиць, довжина яких більше 9, а короткі подтаблиці упорядковувати методом вставки.
Стек займає мало місця. Наприклад, стек з 20 рядків дозволяє упорядкувати таблицю, що містить до 10**7 записів. Крім того, в сучасних мовах програмування при роботі рекурсивних програм занесення і витягання із стека виконується автоматично, тому рекомендується використовувати саме цей механізм. Середнє число порівнянь для даного алгоритму складає n*log(n) де n - число записів в сортованій таблиці, m - розмір підтаблиці, сортованої методом вставки.
Якнайгіршою ситуацією при використанні розглянутого алгоритму є випадок, коли таблиця вже відсортована. При цьому число порівнянь порядку n, тобто алгоритм не кращий за сортування вибіркою.
Як приклад розглянемо записи з наступними ключами:
42 23 74 11 36 58 94
Нижче приведена послідовність перестановок при переміщенні запису з ключем 42 на його кінцеву позицію. Підкреслені ключі, значення яких порівнювалися.
42 23 74 11 36 58 94 ~~~ ~~~ 42 23 74 11 36 58 94 ~~~ ~~~ 42 23 74 11 36 58 94 ~~~ ~~~ ----------------------------------- 36 23 74 11 42 58 94 ~~~ ~~~ 36 23 74 11 42 58 94 ~~~ ~~~ ----------------------------------- 36 23 42 11 74 58 94 ~~~ ~~~ ---------------------------------- 36 23 11 42 74 58 94 ~~
В результаті запису з початковими ключами розбиті на дві подтаблиці, а саме, на набори [36,23,11] і [74,58,94],к яким застосовується той же метод.
Як розділяє можна вибрати x - будь-який елемент таблиці, наприклад, середній (l=n/2). Спочатку таблиця розглядається зліва від x до тих пір, поки не виявиться ключ до[i]>x (до[i]<=x, i:=i+1; якщо до[i]>x, то i фіксується). Потім таблиця є видимою справа, поки виконується до[j]>=x (j:= j-1; якщо до[j] Для кожної з отриманих частин процес повторюється.
Сортування підрахунком (англ. Counting sort) — алгоритм впорядкування, що застосовується при малій кількості різних елементів (ключів) у масиві даних. Час його роботи лінійно залежить як від загальної кількості елементів у масиві так і від кількості різних елементів.
2.1. Ідея алгоритму
Ідея алгоритму полягає в наступному: спочатку підрахувати скільки разів кожен елемент (ключ) зустрічається в вихідному масиві. Спираючись на ці дані можна одразу вирахувати на якому місці має стояти кожен елемент, а потім за один прохід поставити всі елементи на свої місця.
2.1.1 Псевдокод алгоритму
Для простоти будемо вважати, що всі елементи (ключі) є натуральними числами що лежать в діапазоні 1..K. Процедура виконує сортування масиву :
1 — масив з K елементів, заповнений нулями
2 for to
3 do
4 for to
5 do
6 for downto
7 do
8
9
2.2. Виконання алгоритму
В алгоритмі присутні тільки прості цикли: в рядках 2, 6, 9 — цикл довжини N (довжина масиву), в рядку 4 — цикл довжини K (величина діапазону). Отже складність роботи алгоритму є .
В алгоритмі використовуються два додаткових масиви: і . Тому алгоритм потребує додаткової пам'яті.
В такій реалізації алгоритм є стабільним. Саме ця його властивість дозволяє використовувати його як частину інших алгоритмів сортування (напр. сортування за розрядами).
Використання даного алгоритму є доцільним тільки у випадку малих K (порядку N).
3. Виконання програми
#include <iostream.h>
#include <conio.h>
#include <fstream.h>
int i, j, k, p, cur;
int start, n, m;
main()
{
ifstream input ("input.txt");
input>>n>>m>>start;
int *FIFO;
int **Graf;
int *Label;
input>>n>>m>>start;
FIFO=new int [n];
Graf=new int *[n];
for (i=0; i<n; i++);
Graf[i]=new int [n];
Label=new int [n];
for (k=; k<m; k++);
{
input>>i>>j;
Graf[i] [j]=1;
}
for (i=0; i<m;i++)
{
FIFO[i]=0;
Label[i]=32767;
}
p=0;
k=1;
FIFO[p]=start;
Label[start]=0;
while (p!=k)
{
cur=FIFO[p];
p++;
for (i=0; i<n; i++);
if (Graf[cur][i]==1 && Label[i]>Label[cur]+1)
{
FIFO[k]=1;
k++;
Label[i]=Label[cur]+1;
}
}
p=0;
for (i=0; i<n; i++)
if (Label[i]==32767)
{
p=1;
break;
}
{input>>n;
Graf=new int *[n];
for (i=0; i<n; i++)
Graf[i]=new int [2];
for (i=0; i<2; i++)
for (j=0; j<n; j++)
Graf[i][j]=0;
pos=0;
while (!input.eof())
{
input>>i>>j;
Graf[0][pos]=i;
Graf[1][pos]=j;
pos++;
}
{void OVS (int, int[], int[]);
int i, j, k, p, cur;
int Start, n, m;
int **Graf;
main ()
{
int *FIFO;
int *All_Label;
int *Label;
ifstream input ("input.txt");
input>>n>>m;
FIFO=new int [n];
Label=new int [n];
All_Label=new int [n];
for (i=0; i<n; i++);
{
Label[i]=0;
All_Label[i]=0;
FIFO[i]=0;
}
Graf=new int *[n];
for (i=0; i<n; i++);
Graf[i]=new int [n];
for (i=0; i<n; i++)
for (j=0; j<n; j++)
Graf[i][j]=0;
for (k=0; k<m; k++)
{
input>>i>>j;
Graf[i][j]=1;
}
OVS(0,FIFO,Label)
for(i=0; i<n; i++)
All_Label[i]=Label[i];
for(i=1; i<n; i++)
{
OVS(i,FIFO,Label);
for (j=0; j<n; j++)
if (All_Label[j]!=Label[j] && Label[j]!=0)
if (All_Label[j]==0) All_Label[j]=Label[j];
else All_Lebel[j]=-1;
}
int Temp=0;
for (i=0; i<n; i++)
if (All_Label[i]!=-1)
{cout<<i<<" ";
Temp=1;
}
if (Temp==0) cout<<"Nema kor reber";
getch();
return 0;
}
void OVS(int start, int FIFO[], int Label[])
{
int z;
for (z=0; z<n; z++)
{
FIFO[z]=0;
Label[z]=32767;
}
p=0;
k=1;
FIFO[p]=start;
Label[start]=0;
while (p!=k)
{
cur=FIFO[p];
p++;
for (z=0; z<n; z++)
if(Graf[cur][z]==1 && Label[z]>Label[cur]+1)
{
FIFO[k]=z;
k++;
Label[z]=Label[cur]+1; }}}
3. СПИСКИ
3.1 Поняття про однонапрямлені однозв’язні списки
Кожний елемент однонапрямленого списку являє собою структуру. Структура містить набір змінних, які необхідні для збереження інформації списку. Крім того в структурі є ще один елемент – вказівник. Цей вказівник визначає зв’язок між елементами в списку. Простий приклад структури:
struct spysok {
char name[10];
struct spysok *next;
}
Тут визначенно структурний тип spysok, елементами якого є:
масив name[10] з десяти символів;
вказівник на структуру того ж типу.
Тому кожна структура типу spysok може зберігати певну кількість даних і вказівник на іншу аналогічну структуру. На рис. 3.1. показано зв’язок елементів в однозв’язному списку.
Рис. 3.1. Зв’язки між елементами в однозв’язному списку
Кожна структура spysok вказує на наступну структуру spysok. Останній елемент ні на що не вказує. Вказівнику останнього елементу списку присвоєно нульове значення для його вирізнення. Структури, які утворюють однозв’язний список ще називають ланками або вузлами.
Для розпізнавання першого елементу списку використовується спеціальний вказівник не структурного типу – початковий вказівник. Він завжди вказує на перший елемент в списку. Перший елемент містить вказівник на другий елемент, другий на третій і т. д. до тих пір, поки не зустрінеться елемент з вказівником NULL.
3.2. Робота з однозв'язними списками
Елементи до списку можна додавати, викидати або замінювати. Так як елементи списку зв’язані між собою вказівниками, то при додаванні або викиданні елементів списку необхідно маніпулювати цими вказівниками. Елементи можна додавати на початок списку, в середину та в кінець.
Для організації списку необхідно визначити структуру даних і описати початковий вказівник. Так як список створюється пустим, то його початковий вказівник рівний NULL.
Опишемо вказівники на перший елемент масиву head і вказівник new, за допомогою якого будемо додавати нові елементи в список:
struct spysok {
char name[10];
struct spysok *next;
}
struct spysok * new;
struct spysok * head;
head = NULL;
3.3. Додавання елемента на початок списку
Якщо початковий вказівник рівний NULL, то список порожній і його новий елемент стане його першим членом. Якщо початковий вказівник не рівний NULL, то список вже має один або декілька елементів. Але процедура додавання елементів в початок списку залишається незмінною і складається з наступних кроків:
Створити екземпляр структури з виділенням для нього пам’яті з допомогою функції malloc();
Встановити вказівник наступного елементу в структурі нового елементу списку рівним текучому значенню початкового вказівника. Якщо це пророжній список, то це буде NULL, якщо не порожній, то адреса текучого першого елемента;
Встановити початковий вказівник рівним адресі нового елементу.
Цю схему реалізує наступний фрагмент програми:
new=( struct spysok *)malloc(sizeof(struct spysok));
new- > next= head;
head-> new;
Схему додавання нового елементу на початок порожнього списку показано на рис. 3.2.
Рис. 3.2. Додавання нового елемента в пустий список
Рис 3.3. демонструє процедуру додавання нового елементу на початку непустого списку.
Рис. 3.3. Додавання нового першого елемента в непустий список
3.4. Додавання елемента в кінець списку
Для додавання елемента в кінець списку треба спочатку пройти від початкового вказівника до останнього елементу в списку. Після знаходження останнього елемента необхідно виконати наступні операції:
Створити екземпляр структури даних, розподіливши перед тим динамічно пам’ять за допомогою функції malloc();
Встановити вказівник в текучому останньому елементі на доданий елемент, адрес якого повернула функція malloc();
Встановити вказівник в доданому елементі NULL, щоб зробити його новим останнім елементом в списку.
Фрагмент програми для виконання цих операцій:
struct spysok {
char name[10];
struct spysok *next;
};
struct spysok * new;
struct spysok * head;
struct spysok *sp;
sp= head;
while (sp-> next!= NULL)
sp= sp-> next;
new=( struct spysok *)malloc(sizeof(struct spysok));
sp-> next= new;
new- > next= = NULL;
Процедуру додавання нового елементу в кінець зв’язаного списку показано на рис. 3.4.
Рис. 3.4. Додавання нового елемента в кінець зв’язаного списку
4. ОРГАНІЗАЦІЯ ОДНОЗВ’ЯЗНИХ СПИСКІВ
4.1. Операція виділення елемента структури через вказівник
Операція для звертання до елементів структури через вказівник на структуру позначається стрілкою —>. Синтаксис операції
Вказівник на структуру —> ім’я поля.
Наприклад,
struct data {
int a1;
int a2;
float a3;} x, y[5];
Адресою 0-го елементу масиву структур y[5] є y, (y+2) – адреса 2-го елементу масиву структур y[5]. Звертання до 1 поля a1 2-го елементу масиву структур y[5] за допомогою операції “стрілка” має вигляд:
(y+2) —> a1;
Вказівникова форма звертання до елементів структури ефективна, коли для роботи з масивом структур використовують зовнішні вказівники, базовий тип яких збігається з типом структур – елементів масиву.
4.2. Постановка завдання
Змоделювати фабрику, що виробляє вироби з менших вузлів. Назвемо елементарною деталлю такий вузол, що не складається з дрібніших вузлів. Написати програму, що зчитує набір рядків, які містять чотирьох символьні номери деталей. Перший такий номер у рядку означає неелементарну деталь, а решта чисел означають деталі, з яких складається ця неелементарна деталь. Ці складові деталі можуть бути елементарними, а можуть складатися з інших частин (у такому випадку їх номери з’являться першим номером у якомусь іншому рядку). Програма складає список з елементом заголовку для кожної неелементарної деталі. Заголовок містить назву неелементарної деталі і вказівник на список елементів, що описує її складові частини вказівники на заголовки списків послідовно записуються в список. Для описаного представлення написати програму:
а) роздруку всіх неелементарних деталей.
б) виведення для кожної неелементарної деталі списку всії елементарних деталей з яких вона складається.
4.3 Опис програми
Підключення бібліотечних файлів.
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
char c[12];
Визначення структури елементів списку.
struct data {
char name[12];
struct data *next; };
Опис і визначення функції f() для пропусків при друці.
void f(int k)
{char d=' ';
int i;
for (i=1; i<=k; i++)
printf("%c", d); return;}
Опис і визначення функції free_memory_list для очистки пам’яті.
void free_memory(LINK first)
{
LINK cur_ptr;
LINK nex_rec;
cur_ptr = first; /* Початкова адреса */
while (cur_ptr != NULL) /* Перевірка на закінчення списку */
{
nex_rec = cur_ptr->next; /* Одержання адреси наступного запису */
free(cur_ptr); /* Звільнення поточного запису */
cur_ptr = nex_rec; /* Перехід на наступний запис*/
}
}
int main( void )
{int i;
Виведення на екран введених елементів списку
printf(" %lld\n", new);
printf(" ---------\n");
printf(" %lld \n", new->name);
printf(" %s \n", new->name);
printf(" ---------\n");
printf(" %lld \n", new->next);
Виведення на екран значень елементів списку
current = head;
printf("%lld", current->name);
i=8;
while (current != NULL)
{ printf("\n");
f(i) ;
printf("%s",current->name);
printf("\n");
f(i) ;
printf("%lld", (current->next));
i=i+8;
current = current->next; }
printf("\n");
Звільнення виділеної пам’яті для елементів однозв’язного списку.
current = head;
free_memory(current);
system("pause");
return 0; }
Нижче наведено повний текст програми, введення елементів списку та результати роботи програми.
4.4. Текст програми
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char *KOD_NAME(char cc)
{ char a[]="NED-A";
char b[]="NED-B";
char c[]="NED-C";
char d[]="NED-D";
char e[]="NED-E";
char ed1[]="ED-1";
char ed2[]="ED-2";
char ed3[]="ED-3";
char ed4[]="ED-4";
char ed5[]="ED-5";
char ed6[]="ED-6";
char ed7[]="ED-7";
char ed8[]="ED-8";
char ed9[]="ED-9";
char rez[10];
switch (cc)
{ case 'A': strcpy (rez,a); break;
case 'B': strcpy (rez,b); break;
case 'C': strcpy (rez,c); break;
case 'D': strcpy (rez,d); break;
case 'E': strcpy (rez,e); break;
case '1': strcpy (rez,ed1); break;
case '2': strcpy (rez,ed2); break;
case '3': strcpy (rez,ed3); break;
case '4': strcpy (rez,ed4); break;
case '5': strcpy (rez,ed5); break;
case '6': strcpy (rez,ed6); break;
case '7': strcpy (rez,ed7); break;
case '8': strcpy (rez,ed8); break;
case '9': strcpy (rez,ed9); break;
}
return rez;
}
struct list {
char *s;
char *n ;
struct list *next;};
main () {
struct list head, *ptr;
int i=0, j;
char n1[6];
char s1[6];
ptr=&head;
ptr->next=NULL;
do {
printf (" %d) ",i+1);
fgets (s1,6,stdin);
if (!strcmp(s1,"0\n")) {
break;}
else {
ptr->n=(char *)malloc(strlen(n1));
ptr->s=(char *)malloc(strlen(s1));
strcpy (ptr->n,KOD_NAME(s1[0]));
strcpy (ptr->s,s1);
ptr->next=(struct list *)malloc(sizeof(struct list));
ptr=ptr->next;
ptr->next=NULL;
}
i++;
} while (1);
ptr=&head;
i=1;
while (ptr->next!=NULL) {
printf ("%d) %10s%10s\n",i++,ptr->n, ptr->s);
ptr=ptr->next;
}
printf (" \n\n");
ptr=&head;
i=1;
while (ptr->next!=NULL) {
printf ("%d) %10s%10s ",i++,ptr->n, ptr->s);
printf (" -> ");
for (j=1; j<4; j++ )
if ( (ptr->s[j])>='1'&& (ptr->s[j])<='9' )
{
printf ("%10s ",KOD_NAME(ptr->s[j]));
}
printf (" \n");
ptr=ptr->next;
}
system("PAUSE");
}
4.5. Результати виконання програми
1) A123
2) BA34
3) D345
4) C4AD
5) ACBD
6) 0
1) NED-A A123
2) NED-B BA34
3) NED-D D345
4) NED-C C4AD
5) NED-A ACBD
1) NED-A A123
-> ED-1 ED-2 ED-3
2) NED-B BA34
-> ED-3 ED-4
3) NED-D D345
-> ED-3 ED-4 ED-5
4) NED-C C4AD
-> ED-4
5) NED-A ACBD
ВИСНОВКИ
У курсовій роботі було проведено огляд статичних та динамічних структур, що широко застосовуються у програмуванні. Розглянуто їх властивості і практичне значення.
Було проведено детальний аналіз літератури та Інтернет джерел, що дало змогу сформувати як теоретичні основи понять стек, черга так і основні алгоритми реалізації та роботи із цими структурами.
Було проаналізовано застосування однозв'язних списків: додавання елемента на початок списку; додавання елемента в кінець списку; додавання елемента в середину списку; видалення елемента з список; а також організацію однозв’язних списків.
Програми, що написані під час виконання курсової роботи є наглядними, не складними у розумінні і при всьому цьому реалізують всі види дій, які можна
21.11.2013 11:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора