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, opróż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ą zadanej wartości i zwracającą wskaźnik na znaleziony element, lub NULL i wskaźnik na element poprzedni, jeśli wartości 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;
}