podział listy jednokierunkowe na dwie części

Question

Dana jest następująca struktura, definiująca element listy – punkt o współrzędnych x, y : struct element { double x, y; struct element* nast; }; oraz następująca definicja typu – adresu do elementu listy: typedef struct element* ADRES; W programie głównym jest zdefiniowana zmienna pierwszy typu ADRES (która jest adresem pierwszego elementu istniejącej listy), oraz dodatnia stała X. Napisz fragment programu, który podzieli listę na dwie części (listy). W pierwszej z nich mają znaleźć się punkty położone w odległości nie większej niż X od środka układu współrzędnych, w drugiej – pozostałe punkty. Adresy początku nowych list zapamiętaj w zmiennych: p_blizej i p_dalej. Podziału listy na dwie części dokonaj bez alokowania nowej pamięci. Względna kolejność elementów w obrębie obu list powinna zostać zachowana.

proszę o ocenienie programu ,czy dobrze to zrozumiałem ,program nie jest pełny,jest to fragment,który dotyczy tego zadania ,z góry dzięki 

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define X 2.2

struct element{

double x,y;
struct element* nast;
};
typedef struct element* ADRES;

int main()
{
    ADRES pierwszy;

    ADRES p_blizej=NULL,p_dalej=NULL;
    ADRES pom=pierwszy;
    float odleglosc=0.0 ;

    while(pom!=NULL)
    {odleglosc=sqrt((pom->x)*(pom->x)+(pom->y)*(pom->y));

        if(odleglosc<=X)
        {
            p_blizej->x=pom->x;
            p_blizej->y=pom->y;
            p_blizej=p_blizej->nast;
        }
        else if(odleglosc>X)
        {
            p_dalej->x=pom->x;
            p_dalej->y=pom->y;
            p_dalej=p_dalej->nast;
        }
        pom=pom->nast;
        odleglosc=0.0;
    }


    return 0;
}

 

Answer 1

Hej Generalnie Twój tok myślenia według mnie wygląda w miarę poprawnie, jednak jest kilka rzeczy, które wypadałoby poprawić. Zauważ, że p_blizej i p_dalej mają startową wartość NULL - czyli gdy wykonasz na takim wskaźniku dereferencje np. p_blizej->x program najprawdopodobniej rzuci segfaulta i zakończy wykonanie crashem. Poza tym nie potrzebujesz przepisywać pól tej listy - tj. x, y - tylko adresy kolejnych elementów.

Więc Twój algorytm, w podobnej formie do tego, co masz teraz mógłby działać następująco (oczywiście chodzi o tą część która dopisuje do p_blizej/p_dalej):

if (p_blizej == NULL)   // Przypadek gdy ustawiamy pierwszy element w naszej liscie
{
    p_blizej = pom;
    p_blizej_start = pom; // Po rozdzieleniu, to bedzie pierwszy element nowej listy
}
else // Przypadek gdy dopisujemy kolejne elementy
{
    p_blizej->nast = pom;   // Dopisz jako kolejny element listy aktualny punkt
    p_blizej = p_blizej->nast;   // Przesun sie do tego punktu
}

Warto tez zadbac, zeby po dopisaniu ustawic p_blizej->nast i p_dalej->nast jako NULL (np. po pętli while) - żeby były to dwie niezależne listy - w innym przypadku moglibyśmy mieć sytuację, gdzie ostatni element z p_blizej wskazuje na jakiś element w p_dalej lub odwrotnie.

Poza tym, po podzieleniu list chcielibyśmy zapewne mieć początki nowych list - Twoje zmienne p_blizej/p_dalej będą zawierały wskaźnik na ostatni element w liście - dlatego można np. dodać zmienne p_blizej_start/p_dalej_start, które będą przechowywały początki list.

Warto jeszcze zauważyć, że else if jest niepotrzebny - dla warunku (odleglosc <= X), else oznacza to, co sprawdzasz drugi raz. Więc można się tego pozbyć np.

if(odleglosc<=X)
{
    // tutaj czesc od wpisywania na p_blizej
}
else // Ten else oznacza, ze odleglosc jest wieksza 
{
    // tutaj czesc od wpisywania na p_dalej
}

W razie pytań pisz - pozdrawiam!

Comments

dzięki za pomoc:)