• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

implementacja listy-dopisz funkcje. Czy o to chodzi?

VPS Starter Arubacloud
+1 głos
446 wizyt
pytanie zadane 30 listopada 2019 w C i C++ przez sandy001 Nowicjusz (130 p.)
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
 int val;
 struct node * next;
} node_t;
node_t* create_node(int val)
{
node_t * head = NULL;
head = malloc(sizeof(node_t));
if (head == NULL) {
return NULL;
}
head->val = val;
head->next = NULL;
}
void print_list(node_t * head)
{
 node_t * current = head;
 while (current != NULL) {
 printf("%d\n", current->val);
 current = current->next;
 }
}
void insert_end(node_t * head, int val)
{
 node_t * current = head;
 while (current->next != NULL) {
 current = current->next;
 }
 current->next = malloc(sizeof(node_t));
 current->next->val = val;
 current->next->next = NULL;
}
void insert_begin(node_t ** head, int val)
{
 node_t * new_node;
 new_node = malloc(sizeof(node_t));
 new_node->val = val;
 new_node->next = *head;
 *head = new_node;
}
int remove_first(node_t ** head)
{
 int retval = -1;
 node_t * next_node = NULL;
 if (*head == NULL) {
 return -1;
 }
 next_node = (*head)->next;
 retval = (*head)->val;
 free(*head);
 *head = next_node;
 return retval;
}
int remove_last(node_t * head) {
 int retval = 0;
 if (head->next == NULL) {
 retval = head->val;
 free(head);
 return retval;
 }
 node_t * current = head;
 while (current->next->next != NULL) {
 current = current->next;
 }
 retval = current->next->val;
 free(current->next);
 current->next = NULL;
 return retval;
}

int remove_by_index(node_t * head,int num) {

if(num<1 || head==NULL){

 return -1;

}

if(num==1){

 return remove_first(&head);

}

node_t * current = head;

int current_num=2;

int retval=0;

while (current->next != NULL) {

 if (current_num==num){

  node_t * free_node=current->next;

  retval=free_node->val;

  current->next=current->next->next;

  free(free_node);

  return retval;

 }

 current=current->next;

 current_num=current_num+1;

}

return -1;

}



int remove_by_val(node_t * head,int val) {

if(num<1 || head==NULL){

 return -1;

}

node_t * current = head;

node_t * previous=NULL;

int retval=0;

while (current->next != NULL) {

 retval=retval+1;

 if (current->val==val){

  if(previous==NULL){

   return remove_first(&head);

  }else{

   node_t * free_node=current;

   previous->next=current->next;

   free(free_node);

   return retval;

  }

 }

 previous=current;

 current=current->next;

}

return -1;

}


/** Przykłady użycia listy jednokierunkowej */
int main() {
node_t *list;
list = create_node(1);
insert_end( list, 2 );
insert_end( list, 3 );
insert_end( list, 4 );
insert_end( list, 5 );
insert_end( list, 6 );
print_list( list );
printf("------------------\n");
remove_first( &list );
remove_last( list );
print_list( list );

Czesc wam oto moje zadanie i jego rozwiazanie. Przyznam jestem totalnie zielona w tym temacie, wydaje mi sie, ze nie wykonalam go poprawnie: 

Dopisz do poniższej implementacji listy funkcje: - remove_by_index(int num) - remove_by_val(int value)
W funkcji main dodaj kilka przykładów prezentujących możliwości i działanie powyższych funkcji.

komentarz 30 listopada 2019 przez mmarszik Mądrala (7,390 p.)

Trudne. Widzę kilka blędów które trudno objaśnić, np. wskaźnk na wskaźnik w funkcji pośrednej nie będzie tym samym wskaźnikiem na wskaźnik co w funkci main.

Czy nie możesz zmienić implementacji na łatwiejszą? Np. na listę cykliczną która ma wartownika?

Zobacz linię 83:

return remove_first(&head);

To jest wskaźnik na zmienną lokalną, w funkcji wywołującej nie będzie efektu.


Pozdrawiam

2 odpowiedzi

0 głosów
odpowiedź 30 listopada 2019 przez adrian17 Ekspert (344,100 p.)

Na oko, wydają się całkiem niezłe?

Mam parę zastrzeżeń, ale kluczowe pętle na oko wydają się być napisane poprawnie.

Pierdoła: skąd te przerwy co linię? Zakładam że to jakiś artefakt przy kopiowaniu na tą stronę, a nie w Twoim kodzie, bo dziwnie to wygląda.

Nie zrobiłaś też "dodaj kilka przykładów prezentujących możliwości i działanie powyższych funkcji".

int remove_by_val(node_t *head, int val) {
  if (num < 1 || head == NULL) {

To się nie kompiluje, nie ma zmiennej 'num'.

  if (num == 1) {
    return remove_first(&head);

Nie wiem co mówił nauczyciel, ale zazwyczaj w programowaniu indeksuje się od zera - czyli argument num==0 (a nie 1) rozumiałbym jako usunięcie pierwszego elementu.

No i ogólnie obie funkcje błędnie się zachowają jeśli będą usuwały pierwszy element - zastanów się, dlaczego funkcja remove_first bierze wskaźnik na wskaźnik zamiast "pojedynczego" wskaźnika i czy może podobnie nie powinno być też w Twoich funkcjach.

TBH najbardziej mnie niepokoi ta nie kompilująca się zmienna 'num', bo to sugeruje że nie próbowałaś kompilować i testować tego kodu. Tak było? Zdecydowanie sugeruję testować kod na bieżąco, a nie na ślepo oddawać zadanie i mieć nadzieję że działa ;)

0 głosów
odpowiedź 1 grudnia 2019 przez mmarszik Mądrala (7,390 p.)

Ja robiłem tak listę, bez podwójnych wskaźników i jako listę cykliczną. Jest łatwiej:

#include <cstdio>
#include <cstdlib>

struct node;
typedef struct node node_t;

typedef struct node {
    int val;
    node_t *next;
} node_t;

node_t* create_empty_list() {
    node_t *head = (node_t*)malloc( sizeof(node_t) );
    head->next = head;
    return head;
}

node_t* find_nth_element( const node_t *head , const int nr) {
    node_t *node = head->next;
    int i=0;
    while( node != head ) {
        if( i == nr ) {
            return node;
        }
        i++;
        node = node->next;
    }
    return NULL;
}


void insert( node_t *head , const int val ) {
    node_t *newNode = (node_t*)malloc( sizeof(node_t) );
    newNode->next = head->next;
    head->next = newNode;
    newNode->val = val;
}

node_t* remove( node_t *head , node_t *node ) {
    if( node->next == head ) {
        node->next = head->next;
        free( head );
        return node;
    } else {
        node_t *toRemove = node->next;
        node->next = node->next->next;
        node->val  = node->next->val;
        free( toRemove );
        return head;
    }
}

int main() {
    srand(25);
    int sizeList = 0;
    node_t *head = create_empty_list();
    for( int i=0 ; i<1024 ; i++ ) {
        for( int j=0 ; j<1024 ; j++ ) {
            insert( head , rand() % 1000 );
            sizeList ++ ;
        }
        int cntRemove = sizeList - rand() % ( i == 1023 ? 20 : 5 );
        for( int j=0 ; j<cntRemove ; j++ ) {
            node_t *node = find_nth_element( head , rand() % sizeList );
            head = remove( head , node );
            sizeList--;
        }
    }
    printf("sizeList = %d\n" , (int)sizeList);
    node_t *node = head->next;
    int i=1;
    while (node != head) {
        printf("%d] %d\n" , (int)i++, (int)node->val );
        node = node->next;
    }
    fflush(stdout);
    return 0;
}

 

Podobne pytania

0 głosów
0 odpowiedzi 546 wizyt
0 głosów
0 odpowiedzi 370 wizyt
pytanie zadane 11 listopada 2016 w C i C++ przez Wiciorny Ekspert (269,120 p.)
0 głosów
0 odpowiedzi 379 wizyt

92,453 zapytań

141,262 odpowiedzi

319,088 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...