Skocz do zawartości


Problem - Lista jednokierunkowa - szukanie, sortowanie


Brak odpowiedzi do tego tematu

#1 madeleine

    Nowy na forum

  • Użytkownicy
  • 1 Postów:

Napisano pią, 16 gru 2016 - 22:57

Witam,

mam zrobić projekt z modułem listy jednokierunkowej, w której uwzględnione będą następujące funkcje:
dodawanie na początku, dodawanie na końcu, kasowanie elementu z początku, kasowanie elementu z końca, poróźnianie listy, drukowanie listy.
Z tą częścią jakoś sobie poradziłam.

Następnie mam zmodyfikować listę, aby na początku był zawsze pusty element. I napisać funkcję sortującą przez przewiązanie elementów oraz funkcję szukającą zadanj wartości i zwracającą wskaźnik na znaleziony element, lub NULL i wskaźnik na element poprzedni, jeśli wartosci nie ma na liście.

Tutaj utknęłam. Próbowałam napisać funkcję szukającą, nie dodając pustego elementu, chyba działa dobrze, w przypadku występowania elementu, natomiast gdy nie występuje zwraca wskaźnik na pierwszą wartość z listy.

Bardzo proszę o pomoc jak dodać ten pierwszy pusty element do listy, oraz jak zabrać się za sortowanie. Nie do końca rozumiem na czym ma polegać to " sortowanie przez przewiązanie elementów".


cpp
#include "stdafx.h"
#include <stdlib.h>
#include <iostream>
using namespace std;
typedef struct tagListItem
{
double value;
struct tagListItem* pNext;
}ListItem;
//FUNKCJE
ListItem* lAddFront(double x, ListItem *Head);
void lDelFront(ListItem* &Head);
ListItem* lAddBack(double x, ListItem *Head);
void lDelBack(ListItem* &Head);
void lPrint(ListItem* &Head);
void lRelese(ListItem* &Head);
int lSize(ListItem* &Head);
ListItem* lFind(double n, ListItem* Head);
 
int main(int argc, char* argv[])
{
ListItem* Head;
Head = NULL;
int n;
printf("Podaj n: \n");
scanf("%d", &n);
double val;
 
for (int i = 0; i < n; i++)
{
  val = rand();
  Head = lAddFront(val, Head);
}
lPrint(Head);
printf("\n Rozmiar tablicy: %d \n", lSize(Head));
//usowanie z przodu
printf("_lDelFront_ ile elementow usunac?: \n");
scanf("%d", &n);
for (int i = 0; i < n; i++)
  lDelFront(Head);
lPrint(Head);
printf("\n Rozmiar tablicy: %d \n", lSize(Head));
//dodajemy z tylu
printf("_lAddBack_ ile elementow dodac?: \n");
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
  val = rand();
  Head = lAddBack(val, Head);
}
lPrint(Head);
printf("\n Rozmiar tablicy: %d \n", lSize(Head));
//uswanie z tylu
printf("_lDelBack_ ile elementow usunac?: \n");
scanf("%d", &n);
for (int i = 0; i < n; i++)
  lDelBack(Head);
lPrint(Head);
printf("\n Rozmiar tablicy: %d \n", lSize(Head));
// Szukanie elementu
double x;
printf("_lFind_ podaj szukana wartosc?: \n");
scanf("%lf", &x);
lFind(x, Head);
 
//Oproznianie listy
lRelese(Head);
printf("Lista oprozniona - rozmiar tablicy: %d \n", lSize(Head));
return 0;
}
ListItem* lAddFront(double x, ListItem* Head)
{
ListItem* temp;
temp = Head;
temp = (ListItem *)malloc(sizeof(ListItem));
temp->value = x;
temp->pNext = Head;
Head = temp;
return Head;
}
void lDelFront(ListItem* &Head)
{
ListItem* temp;
temp = Head;
if (temp)
{
  Head = Head->pNext;
  delete temp;
}
else
  printf("Lista pusta - nie mozna usunac elementu!\n");
}
ListItem* lAddBack(double x, ListItem *Head)
{
ListItem* temp;
temp = Head;
ListItem* newtemp;
newtemp = (ListItem *)malloc(sizeof(ListItem));
newtemp->value = x;
newtemp->pNext = NULL;
 
if (temp)
{
  while (temp->pNext)
   temp = temp->pNext;
  temp->pNext = newtemp;
}
else
  Head = newtemp;
return Head;
}
void lDelBack(ListItem* &Head)
{
ListItem* temp;
temp = Head;
if (temp)
{
  if (temp->pNext)
  {
   while (temp->pNext->pNext)
        temp = temp->pNext;
        delete temp->pNext;      
   temp->pNext = NULL;    
  }
  else        
  {
   delete temp;
   Head = NULL;
  }
}
}
ListItem*  lFind(double n, ListItem* Head)
{
ListItem* temp;
temp = Head;
 
while (temp != NULL)
{
  if (temp->value == n)
  {
   printf("Wartosc %lf znaleziono! \n", n);
   printf("zwracany temp %lf \n", temp->value);
   return temp;
  }
  else
   temp = temp->pNext;
}
printf("Nie znaleziono wartosci %f \n", n);
printf("zwracany temp %lf \n", Head->value);
return Head;
}
 
void lPrint(ListItem* &Head)
{
ListItem* temp;
temp = Head;
while (temp)
{
  printf(" %f \t ", temp->value);
  temp = temp->pNext;
}
}
void lRelese(ListItem* &Head)
{
ListItem* temp;
while (Head)
{
  temp = Head;
  Head = Head->pNext;
  delete temp;
}
}
int lSize(ListItem* &Head)
{
int listSize = 0;
ListItem* temp;
temp = Head;
while (temp)
{
  listSize++;
  temp = temp->pNext;
}
return listSize;
}