Temat: Listy powiązane jedno- i dwukierunkowe jako rodzaj struktury danych.
1. Struktury danych w inżynierii oprogramowania, tj. dziedziny wiedzy zajmującej się wszelkimi aspektami tworzenia oprogramowania
●
struktury danych opisują sposób uporządkowania danych, tzn. rozmiar i wzajemne powiązania ; struktury danych są kluczowe na etapie analizy i specyfikacji tworzenia oprogramowania
●
typowe struktury danych to: bit, liczba, znak , tablice , rekordy , listy powiązane , stosy i kolejki , zbiory , tablice asocjacyjne , drzewa, grafy 2. Lista powiązane
Lista składa się z szeregu elementów, powiązanych ze sobą indeksami lub wskaźnikami, w określonej kolejności. Listy są podobne do tablic, z ta różnicą, że pozwalają na dynamiczną alokację danych oraz ułatwiają wstawianie nowych danych oraz usuwanie istniejących. Zaletą listy jest to, że zwalnia nas z konieczności deklarowania określonej ilości danych na początku programu. Listy stosuje się do implementacji bardziej zaawansowanych struktur danych, jak: stosy, kolejki, zbiory, grafy i tablice asocjacyjne. W praktyce stosuje się dwa rodzaje list: jedno- i dwukierunkowe.
●
lista jednokierunkowa
dane
n
dane
n
dane
n
NULL
#include <stdio.h>
struct lista {
int liczba;
struct lista *nastepny;
};
void kasuj (struct lista *e, int nr){
int i=1;
printf("\nKasuje element nr=%d\n",nr); while(e!=NULL) {
if (i==nr-1) {
struct lista *k=e->nastepny; e->nastepny=e->nastepny->nastepny; delete k;
};
e=e->nastepny;
i++;
};
};
void wyswietl (struct lista *e) {
int i=0;
while(e!=NULL) {
i++;
printf("Element[%d]=> liczba=%d\n",i,e->liczba); e=e->nastepny;
};
};
int main()
{
struct lista *element=NULL, *pierwszy=NULL; pierwszy = new struct lista; element=pierwszy;
element->nastepny=NULL;
element->liczba=1;
element->nastepny=new struct lista; element=element->nastepny; element->nastepny=NULL;
element->liczba=2;
element->nastepny=new struct lista; element=element->nastepny; element->nastepny=NULL;
element->liczba=3;
wyswietl(pierwszy);
kasuj(pierwszy,2);
wyswietl(pierwszy);
return 0;
};
●
lista dwukierunkowa
NULL
p
dane
n
p
dane n
p
dane
n
NULL
struct lista {
int liczba;
struct lista *nastepny, *poprzedni;
};
main.cpp
klasa.cpp
#include "klasa.h"
#include "klasa.h"
int main() {
void baza::dane(char *i, char *n, char *t){
class baza *lista=NULL,
strcpy(this->imie,i);
*osoba=NULL;
strcpy(this->nazwisko,n); lista=new baza(NULL);
strcpy(this->telefon,t); osoba=lista;
};
osoba->dane("Jan","Nowak","1"); void baza::wyswietl(){
osoba=new baza(osoba);
cout << "Lista:\n"; osoba->dane("Jan","Nowak","2"); class baza *obiekt=this;
osoba=new baza(osoba);
while (obiekt!=NULL) {
osoba->dane("Jan","Nowak","3"); cout<<"\tImie: "<<obiekt->imie<<"\t"; lista->wyswietl();
cout<<"\tNazw:"<<obiekt->nazwisko <<"\t"; lista->kasuj(2);
cout<<"\tTelefon:"<<obiekt->telefon<<"\n"; lista->wyswietl();
obiekt=obiekt->nastepny; delete lista;
};
return 0;
};
};
void baza::kasuj(int nr){
klasa.h
int i=1;
cout << "Kasuje element nr=" << nr << "\n";
#include <iostream>
class baza *obiekt=this;
#include <string.h>
while(obiekt!=NULL) {
using namespace std;
if (i==nr-1) {
class baza *tmp=obiekt->nastepny; class baza {
obiekt->nastepny=obiekt->nastepny->nastepny; private:
delete tmp;
char imie[10];
};
char nazwisko[25];
obiekt=obiekt->nastepny; char telefon[10];
i++;
class baza *nastepny;
};
public:
};
void dane(char*i,char*n,char*t); baza::baza(class baza *obiekt){
void wyswietl();
this->nastepny=NULL;
void kasuj(int nr);
if (obiekt!=NULL) obiekt->nastepny=this; baza(class baza *obiekt);
};
~baza();
baza::~baza(){
};
cout << "Usuwam liste\n";
};
3) Zadanie: Zmodyfikuj program bazy danych z poprzednich ćwiczeń tak, aby obsługiwał listę dwukierunkową i pozwalał na dopisywanie i kasowanie kolejnych rekordów bazy danych.