Skocz do zawartości
Zaloguj się, aby obserwować  
madeleine

Problem - Lista jednokierunkowa - szukanie, sortowanie

Polecane posty

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".

 

 

#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;
}

Udostępnij ten post


Link to postu
Udostępnij na innych stronach

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Gość
Odpowiedz...

×   Wklejony jako tekst z formatowaniem.   Przywróć formatowanie

  Dozwolonych jest tylko 75 emoji.

×   Twój link będzie automatycznie osadzony.   Wyświetlać jako link

×   Twoja poprzednia zawartość została przywrócona.   Wyczyść edytor

×   Nie możesz wkleić zdjęć bezpośrednio. Prześlij lub wstaw obrazy z adresu URL.

Wczytywanie...
Zaloguj się, aby obserwować  

×
×
  • Utwórz nowe...