Поврзани листи

 
   

При решавање на голем број проблеми потребни се динамички листи, чија големина не мора однапред да е зададена, туку ја дефинираме во текот на програмата. Поврзана листа е структура на податоци која се користи за моделирање токму на динамички листи.

 Концепт    низи – поврзани листи

 



Поврзана листа е линеарна структура на податоци, во која елементите не се складираат на соседни мемориски локации, што е случај кај низите. Елементите може да ги сместиме било каде во меморија, а потоа ги поврзуваме така што секој елемент (освен првиот) е поврзан со претходниот во листата, елементите  се поврзани со помош на покажувачи..

Секој елемент (jazol) е структура од 2 дела:

·       еден кој ги чува податоците (data field) и

·       друг кој ја чува адресата на следбеникот (link) - покажувач кој служи како врска кон наредниот јазол од низата

 
Мора да започнеме од некаде, па на адресата на првиот јазол и даваме посебно име наречено HEAD. Исто така, последниот јазол во поврзаната листа може да се идентификува бидејќи неговиот следен дел укажува на NULL.

 struct node {

  int data;

  struct node *next;

};

Секој структурен јазол има податочна ставка и покажувач кон друг структурен јазол

Постојат неколку типови на поврзани листи: еднострано поврзани, двострано поврзани и кружни листи.

 Еднострано поврзани листи

// A Single linked list node

struct Node {
int data;
Node* next;
};

 Секој јазол од листата има свој следбеник (освен последниот) и свој предходник (освен првиот). Должината на поврзана листа се изразува преку бројот на јазли од кои е составена. Листа која не содржи јазли се нарекува празна листа.

 https://www.geeksforgeeks.org/insertion-in-linked-list/

 

/* Node of a doubly linked list */

class Node {
public:
int data;
Node* next; // Pointer to next node in DLL
Node* prev; // Pointer to previous node in DLL
};

 

Основни операции со поврзани листи

Премин - пристап до секој елемент од поврзаната листа
Вметнување - додава нов елемент на поврзаната листа
Бришење - отстранува постоечките елементи
Пребарување - најдете јазол во поврзаната листа
Подреди - сортирајте ги јазлите од поврзаната листа


 Запомни

·   главата покажува на првиот јазол од поврзаната листа
· следниот покажувач на последниот јазол е NULL, па ако следниот тековен јазол е NULL, стигнавме до крајот на поврзаната листа

 

Во сите примери, ќе претпоставиме дека поврзаната листа има три јазли 1 --->2 --->3

Поминување  низ листата


#include <bits/stdc++.h>
// #include <iostream>
using namespace std;

// Creating a node
struct Node {
int value;
Node* next;
};

int main() {
Node* head;
//Node* one = NULL;
Node* two = NULL;
Node* three = NULL;

// allocate 3 nodes in the heap
Node *one = new Node();
two = new Node();
three = new Node();

// Assign value values
one->value = 1;
two->value = 2;
three->value = 3;

// Connect nodes
one->next = two;
two->next = three;
three->next = NULL;

// print the linked list value
head = one;
while (head != NULL) {
cout << head->value;
head = head->next;
}
}

Излез: 123

Додавање елемент во листа

Разликуваме 2 случаи:

1.       листата е празна пред додавањe на новиот елемент

2.       листата не е празна

      При додавање на елемент во празна листа, главата (head) на листатa е покажувач кој има вредност NULL (не покажува на ниту еден елемент). По додавање на нов елемент, главатa на листата станува покажувач на тој елемент

2.      Кога листата не е празна главатa покажува на првиот елемент. За да се додаде елемент на крај од листатa, треба да се помине низ сите елементi за да се дојде до последниот, а потоа да се додаде нов елемент. 

// Linked list operations in C++

#include <stdlib.h>

#include <iostream>
using namespace std;

// Create a node
struct Node {
  int data;
  struct Node* next;
};

void insertAtBeginning(struct Node** head_ref, int new_data) {
  // Allocate memory to a node
  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

  // insert the data
  new_node->data = new_data;
  new_node->next = (*head_ref);

  // Move head to new node
  (*head_ref) = new_node;
}

// Insert a node after a node
void insertAfter(struct Node* prev_node, int new_data) {
  if (prev_node == NULL) {
  cout << "the given previous node cannot be NULL";
  return;
  }

  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
  new_node->data = new_data;
  new_node->next = prev_node->next;
  prev_node->next = new_node;
}

// Insert at the end
void insertAtEnd(struct Node** head_ref, int new_data) {
  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
  struct Node* last = *head_ref; /* used in step 5*/

  new_node->data = new_data;
  new_node->next = NULL;

  if (*head_ref == NULL) {
  *head_ref = new_node;
  return;
  }

  while (last->next != NULL) last = last->next;

  last->next = new_node;
  return;
}

// Delete a node
void deleteNode(struct Node** head_ref, int key) {
  struct Node *temp = *head_ref, *prev;

  if (temp != NULL && temp->data == key) {
  *head_ref = temp->next;
  free(temp);
  return;
  }
  // Find the key to be deleted
  while (temp != NULL && temp->data != key) {
  prev = temp;
  temp = temp->next;
  }

  // If the key is not present
  if (temp == NULL) return;

  // Remove the node
  prev->next = temp->next;

  free(temp);
}

// Search a node
bool searchNode(struct Node** head_ref, int key) {
  struct Node* current = *head_ref;

  while (current != NULL) {
  if (current->data == key) return true;
  current = current->next;
  }
  return false;
}

// Sort the linked list
void sortLinkedList(struct Node** head_ref) {
  struct Node *current = *head_ref, *index = NULL;
  int temp;

  if (head_ref == NULL) {
  return;
  } else {
  while (current != NULL) {
    // index points to the node next to current
    index = current->next;

    while (index != NULL) {
    if (current->data > index->data) {
      temp = current->data;
      current->data = index->data;
      index->data = temp;
    }
    index = index->next;
    }
    current = current->next;
  }
  }
}

// Print the linked list
void printList(struct Node* node) {
  while (node != NULL) {
  cout << node->data << " ";
  node = node->next;
  }
}

// Driver program
int main() {
  struct Node* head = NULL;

  insertAtEnd(&head, 1);
  insertAtBeginning(&head, 2);
  insertAtBeginning(&head, 3);
  insertAtEnd(&head, 4);
  insertAfter(head->next, 5);

  cout << "Linked list: ";
  printList(head);

  cout << "\nAfter deleting an element: ";
  deleteNode(&head, 3);
  printList(head);

  int item_to_find = 3;
  if (searchNode(&head, item_to_find)) {
  cout << endl << item_to_find << " is found";
  } else {
  cout << endl << item_to_find << " is not found";
  }

  sortLinkedList(&head);
  cout << "\nSorted List: ";
  printList(head);
}

OUTPUT 
Linked list: 3 2 5 1 4 
After deleting an element: 2 5 1 4 
3 is not found
Sorted List: 1 2 4 5

Задачи:
Што ќе се прикаже 
(еднострано поврзана листа)
#include <iostream>
using namespace std;
struct Node {
   int data;
   struct Node *next;
};
struct Node* head = NULL;
void insert(int new_data) {
   struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
   new_node->data = new_data;
   new_node->next = head;
   head = new_node;
}
void display() {
   struct Node* ptr;
   ptr = head;
   while (ptr != NULL) {
      cout<< ptr->data <<" ";
      ptr = ptr->next;
   }
}
int main() {
   insert(3);
   insert(1);
   insert(7);
   insert(2);
   insert(9);
   cout<<"The linked list is: ";
   display();
   return 0;
}

1. Напиши програма со која се креира еднострано поврзана листа со n елементи цели броеви Додавање на елемент е на почеток  на листата. Да се испечати листата

#include <iostream>
using namespace std;

struct jazol
{
 int x;
 jazol *pok;
};
int main()
{
 jazol *poc,*nov, *sleden;
 nov=new jazol;
 int n; //се креира почетен елемент на листата
 cout<<"vnesi broj "<<endl;
 cin>>nov->x; //внеси вредност на елементот
 nov->pok=NULL; //првиот елемент е единствен во листата и покажувачот има вредност NULL
 poc=nov; //првиот елемент е почеток на листата
 cout<<"vnesi broj na elementi "<<endl;
 cin>>n;
 for(int i=1;i<=n;i++)
 {
 cout<<"vnesi broj "<<endl;
 sleden=new jazol; //се креира нов елемент на листата
 cin>>sleden->x; //внеси вредност на елементот
 sleden->pok=NULL; //новиот елемент е последен во листата па неговиот покажувач 
                    //покажува на NULL
 nov->pok=sleden; //покажувачот од претходниот елемент од листата покажува на 
                    //новиот елемент
 nov=sleden; //претходниот елемент има вредност на последниот за да може 
            //постапката да се повторува се додека треба да се додадат нови елементи. Додавањето на нов елемент е на 
            //крајот на листата
 }
 while(poc!=NULL)
 {
 cout<<poc->x<<" ";
 poc=poc->pok;
 }
 return 0;
}

2. Да се креира еднострано поврзана листа со 10 елементи цели броеви и 
да се испечатат само парните броеви

#include <iostream>
using namespace std;
struct jazol
{
 int x;
 jazol *pok;
};
int main()
{
 jazol *poc,*nov, *sleden;
 nov=new jazol;       //се креира почетен елемент на листата
 cout<<"vnesi broj ";
 cin>>nov->x;        //внеси вредност на елементот
 nov->pok=NULL; //првиот елемент е единствен во листата и покажувачот има вредност NULL
 poc=nov; //првиот елемент е почеток на листата
 for(int i=1;i<10;i++)
 {
 cout<<"vnesi broj  ";
 sleden=new jazol;      //се креира нов елемент на листата
 cin>>sleden->x;          //внеси вредност на елементот
 sleden->pok=NULL; //новиот елемент е последен во листата па неговиот покажувач покажува на NULL
 nov->pok=sleden; //покажувачот од претходниот елемент од листата покажува на новиот елемент
 nov=sleden;               //претходниот елемент има вредност на последниот за да 
                              //може постапката да се повторува се додека треба да се додадат нови елементи. //Додавањето на нов елемент  е на крајот на листата
 }
 while(poc!=NULL)
 {
 if (poc->x%2==0) //печатење на парните елементи од листата
 cout<<poc->x<<" ";
 poc=poc->pok;
 }
 return 0;
}

3. Kреираj еднострано поврзана листа со n елементи цели броеви. Избриши го првиот елемент од  листата и испечати ја.

#include <iostream>
using namespace std;
struct jazol
{
 int x;
 jazol *pok;
};
int main()
{
 jazol *poc,*nov, *sleden, *temp;
 int n;
 nov=new jazol; //се креира почетен елемент на листата
 nov->pok=NULL; //првиот елемент е единствен во листата и покажувачот
                    //има вредност NULL
 poc=nov; //првиот елемент е почеток на листата
 cout<<"vnesi broj na elementi na listata ";
 cin>>n;
 for(int i=1;i<=n;i++)
 {
 cout<<"vnesi broj ";
 sleden=new jazol; //се креира нов елемент на листата
 cin>>sleden->x; //внеси вредност на елементот
 sleden->pok=poc; //новиот елемент е прв па неговиот покажувачсе насочува
                  //да покажува на почеток
 poc=sleden; //pocetok има вредност на последниот елемент
 }
 cout<<"pecatenje na pocetnata lista"<<endl;
 while(poc->pok!=NULL)
 {
 cout<<poc->x<<" ";
 poc=poc->pok;
 }
 poc=sleden;
 temp=poc; //во привремена пром. се сместува poc
 poc=poc->pok; // poc прима вредност на следниот елемент
 delete temp; //се бриши привремената променлива
 cout<<"\nnovata lista e"<<endl;
 while(poc->pok!=NULL)
 {
 //печатење на елементите од листата
 cout<<poc->x<<" ";
 poc=poc->pok;
 }
 return 0;
}

vnesi broj na elementi na listata 4
vnesi broj 12
vnesi broj 08
vnesi broj 234
vnesi broj 0
pecatenje na pocetnata lista
0 234 8 12 
novata lista e
234 8 12 



No comments:

Post a Comment

Subscribe to: Posts (Atom)