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

Bądź aktywny! Zaloguj się lub utwórz konto

Tylko zarejestrowani użytkownicy mogą komentować zawartość tej strony

Utwórz konto

Zarejestruj nowe konto, to proste!

Zarejestruj nowe konto

Zaloguj się

Posiadasz własne konto? Użyj go!

Zaloguj się
Zaloguj się, aby obserwować  

×