Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Лінійні однозв’язні списки
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2011
Тип роботи:
Лабораторна робота
Предмет:
Алгоритми і структури даних
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
ТЕХНІЧНИЙ КОЛЕДЖ НАЦІОНАЛЬНОГО УНІВЕРСИТЕТУ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
ВІДДІЛЕННЯ ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ ТА КОМП'ЮТЕРНОЇ ТЕХНІКИ
Лабораторна робота №6
з алгоритмів і структури даних
на тему:
Лінійні однозв’язні списки
Мета: Отримання практичних навиків роботи з динамічними змінними і динамічними структурами даних.
Завдання: Написати програму формування списку друзів з вказаними телефонами та адресами.
Теоретична інформація
Зв'язаний список в програмуванні — одна з найважливіших структур даних, в якій елементи лінійно впорядковані, але порядок визначається не номерами елементів, а вказівниками, які входять в склад елементів списку та вказують на наступний за даним елемент (в однозв'язаних або однобічно зв'язаних списках) або на наступний та попередній елементи (в двозв'язаних або двобічно зв'язаних списках). Список має «голову» — перший елемент та «хвіст» — останній елемент.
Зв'язані списки мають серію переваг порівняно з масивами. Зокрема, в них набагато ефективніше (за час О(1), тобто незалежно від кількості елементів) виконуються процедури додавання та вилучення елементів. Натомість, масиви набагато кращі в операціях, які потребують безпосереднього доступу до кожного елементу, що у випадку зі зв'язаними списками неможливо та потребує послідовного перебору усіх елементів, які передують даному.
В однобічно зв'язаному списку, який є найпростішим різновидом зв'язаних списків, кожний елемент складається з двох полів: data або даних, та вказівника next на наступний елемент. Якщо вказівник не вказує на інший елемент (інакше: next = NULL), то вважається, що даний елемент — останній в списку.
Приклад однозв’язного списку:
Код програми
#include "stdafx.h"
#include <conio.h>
#include <iostream>
using namespace std;
class list
{
private:
struct item
{
char first_name[15];
char last_name[15];
char street[15];
int house;
int apartment;
long int phone;
item *next;
};
item *phead;
bool isEmpty;
public:
list() {phead=new(item); (*phead).next=NULL; isEmpty=true;}
~list() { delete phead;}
void create()
{
item *t;
char a = 'y';
t = phead;
cout<<"\n";
while (a!='n')
{
(*t).next = new (item);
t = (*t).next;
cout<<"\tFirst Name: "; cin>>(*t).first_name;
cout<<"\tLast Name: "; cin>>(*t).last_name;
cout<<"\tStreet: "; cin>>(*t).street;
cout<<"\tHouse: "; cin>>(*t).house;
cout<<"\tApartment: "; cin>>(*t).apartment;
cout<<"\tPhone: "; cin>>(*t).phone;
(*t).next = NULL;
cout<<"\nEnter next? y/n\n";
cin>>a;
}
isEmpty=false;
}
void show()
{
if (!isEmpty)
{
item *t;
t =(*phead).next;
cout<<"List: ";
while (t!=NULL)
{
cout<<"\n";
cout<<"\n\tFirst Name:\t"<<(*t).first_name;
cout<<"\n\tLast Name:\t"<<(*t).last_name;
cout<<"\n\tStreet:\t"<<(*t).street;
cout<<"\n\tHouse:\t"<<(*t).house;
cout<<"\n\tApartment:\t"<<(*t).apartment;
cout<<"\n\tPhone:\t"<<(*t).phone;
t = (*t).next;
}
cout<<endl;
}
else
{
cout<<"\nList is empty!";
}
}
void clear()
{
item *q,*q1;
q = phead;
q1 = (*q).next;
while (q1!=NULL)
{
q = q1;
q1 = (*q1).next;
delete q;
}
isEmpty=true;
}
};
int main()
{
system("cls");
list list1;
list1.create();
list1.show();
list1.clear();
list1.show();
_getch();
return 0;
}
Блок-схема:
Результат виконання:
Висновок: навчився реалізовувати однозв’язний список.
06.02.2014 19:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора