Problem - Lista jednokierunkowa - szukanie, sortowanie

[madeleine]

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