skapa tom lista och skapa listnod genom att allokera minne

Nu var det ett tag sedan jag använde C, men är ganska säker på att du just nu allokerar 5st noder, av storleken node och initierar allting till 0. 

Jag skulle tippa på att du vill använda Malloc, men om du verkligen vill använda calloc, skapa inte 5st noder varje gång du vill skapa en nod. 

Utan att se hela din kod är det svårt att säga vad du skall göra. 

Det ser ut som att du håller på med en länkad lista, och då ska du koppla noderna som en kedja. Vidare spelar det roll om den är enkellänkad  eller dubbellänkad.

Dracaena skrev:

Nu var det ett tag sedan jag använde C, men är ganska säker på att du just nu allokerar 5st noder, av storleken node och initierar allting till 0. 

Jag skulle tippa på att du vill använda Malloc, men om du verkligen vill använda calloc, skapa inte 5st noder varje gång du vill skapa en nod. 

Utan att se hela din kod är det svårt att säga vad du skall göra. 

Det ser ut som att du håller på med en länkad lista, och då ska du koppla noderna som en kedja. Vidare spelar det roll om den är enkellänkad  eller dubbellänkad.

Fick tipset av en vän att jag skulle skriva 1 istället för 5. 

Jag har valt att köra med dubbellänkad.

Här är mina filer med koder :

#include <stdio.h>
#include "list.h"
#include <assert.h>
/*Denna kan du anvanda for att testa specifika funktioner
 (du far givetvis skriva en egen menyfunktion om du vill det)*/
void menu(List head);


/*Kors programmet felfritt genom denna funktion sa fungerar det som specificerat
(observera att utskriften maste testas manuellt.
  OBS! Innan alla funktioner är implementerade sa kommer exekveringen fastna i
olika asserts*/
void testFunction(List head);
int main(void)
{
    List head = createEmptyList(); /*head ska hela tiden peka på borjan av din
lista, om listan ar tom ska head peka pa NULL */
    
    /*Kommentera eller avkommentera beroende pa om det ar menyn eller
testfunktionen som ska koras*/
    testFunction(head);
    //menu(head);
    
    
    return 0;
}
void menu(List head)
{
    int choice;
    Data data;
    char c; //Anvands endast for att rensa lasbufferten
    
    do
    {
        printf("\n\n--------------MENU--------------\n"
               "1 - Print list\n"
               "2 - Add data first in list\n"
               "3 - Add data last in list\n"
               "4 - Remove first node in list\n"
               "5 - Remove last node in list\n"
               "6 - Remove data in list\n"
               "7 - Number of nodes in list\n"
               "8 - Is the list empty?\n"
               "9 - Get first element in list\n"
               "10 - Get last element in list\n"
               "11 - Search in list\n"
               "12 - Clear list (removes all nodes)\n"
               "13 - End program\n"
               "-----------------------------------\n"
               "Choice: ");
        
        scanf("%d", &choice);
        while((c = getchar()) != '\n' && c != EOF); //Rensar lasbufferten
        
        switch(choice)
        {
            case 1: printf("List: ");
                    printList(head, stdout); break;
                
            case 2: printf("Data to add first: ");
                    scanf("%d%*c", &data);
                    addFirst(&head, data);
                    printf("List: ");
                    printList(head, stdout);
                    break;
                
            case 3: printf("Data to add last: ");
                    scanf("%d%*c", &data);
                    addLast(&head, data);
                    printf("List: ");
                    printList(head, stdout);
                    break;
                
            case 4: removeFirst(&head);
                    printf("First node removed\n");
                    printf("List: ");
                    printList(head, stdout);
                    break;
                
            case 5: removeLast(&head);
                    printf("Last node removed\n");
                    printf("List: ");
                    printList(head, stdout);
                    break;
                
            case 6: printf("Data to remove: ");
                    scanf("%d%*c", &data);
                    if(removeElement(&head, data) == 1)
                        printf("First occurance of node with data %d is removed\n",
data);
                    else
                        printf("No node with data %d\n", data);
                    printf("List: ");
                    printList(head, stdout);
                    break;
                
            case 7: printf("Number of nodes in list: %d\n",
numberOfNodesInList(head)); break;
                
            case 8: if(isEmpty(head) == 1)
                        printf("The list is empty\n");
                    else
                        printf("The list is not empty\n");
                    break;
                
            case 9: printf("First element: %d\n", getFirstElement(head)); break;
                
            case 10: printf("Last element: %d\n", getLastElement(head)); break;
                
            case 11: printf("Data to search for: ");
                scanf("%d", &data);
                if(search(head, data) == 1)
                {
                    printf("%d found in list ", data);
                    printList(head, stdout);
                }
                else
                {
                    printf("%d not found in list ", data);
                    printList(head, stdout);
                }
                break;
                
            case 12: clearList(&head); break;
                
            case 13: printf("\nEnding program");
                
            default: printf("\nWrong input");
        }
    }while(choice != 13);
}
/*Du behöver själv testa funktionen printList, tänk på att testa denna både på en
befintlig lista och på en tom lista
  Testa även att det går att göra clearList på en tom lista utan att programmet
krashar*/
void testFunction(List head)
{
    printf("Starting test\n");
    
    assert(isEmpty(head)); //Listan ska vara tom fran borjan
    //Testar addFirst
    addFirst(&head, 6);
    addFirst(&head, 5);
    addFirst(&head, 4);
    addFirst(&head, 3);
    addFirst(&head, 2);
    assert(numberOfNodesInList(head) == 5);
    assert(getFirstElement(head) == 2);
    assert(getLastElement(head) == 6);
    //listan består nu av 2-3-4-5-6
    
    //Testar addLast på existerande lista
    addLast(&head, 7);
    addLast(&head, 8);
    assert(numberOfNodesInList(head) == 7);
    assert(getFirstElement(head) == 2);
    assert(getLastElement(head) == 8);
    //listan består nu av 2-3-4-5-6-7-8
    //Testar removeFirst på existerande lista
    removeFirst(&head);
    assert(numberOfNodesInList(head) == 6);
    assert(getFirstElement(head) == 3);
    assert(getLastElement(head) == 8);
    //listan består nu av 3-4-5-6-7-8
    
    //Testar removeLast på existerande lista
    removeLast(&head);
    assert(numberOfNodesInList(head) == 5);
    assert(getFirstElement(head) == 3);
    assert(getLastElement(head) == 7);
    //listan består nu av 3-4-5-6-7
    
    //Testar att ta bort en nod (som finns) i mitten av befintlig listan
    removeElement(&head, 5);
    assert(numberOfNodesInList(head) == 4);
    assert(getFirstElement(head) == 3);
    assert(getLastElement(head) == 7);
    //listan består nu av 3-4-6-7
    
    //Testar att ta bort forsta noden med removeElement i befintlig lista
    removeElement(&head, 3);
    assert(numberOfNodesInList(head) == 3);
    assert(getFirstElement(head) == 4);
    assert(getLastElement(head) == 7);
    //listan består nu av 4-6-7
    
    //Testar att ta bort sista noden med removeElement i befintlig lista
    removeElement(&head, 7);
    assert(numberOfNodesInList(head) == 2);
    assert(getFirstElement(head) == 4);
    assert(getLastElement(head) == 6);
    //listan består nu av 4-6
    
    //testar att ta bort en nod som inte finns med removeElement i en befintlig lista
    assert(removeElement(&head, 5) == 0);
    
    assert(!isEmpty(head)); //Listan ska inte vara tom (4 och 6 ar kvar i listan)
    
    //Testar att ta bort ett ensamt element med removeElement
    removeElement(&head, 6);
    assert(numberOfNodesInList(head) == 1);
    assert(getFirstElement(head) == 4);
    removeElement(&head, 4);
    assert(isEmpty(head)); //Listan ska nu vara tom
    
    //Testar att lagga till data till en tomd lista
    addLast(&head, 5); //testar att lägga till sist i tom lista
    assert(getFirstElement(head) == getLastElement(head));
    removeFirst(&head); //ta bort sista elementet med removeFirst
    assert(isEmpty(head)); //tom lista igen
    
    addFirst(&head, 5);
    assert(getFirstElement(head) == getLastElement(head));
    removeLast(&head); //ta bort sista elementet med removeLast
    assert(isEmpty(head)); //tom lista igen
    
    addFirst(&head, 5);
    addFirst(&head, 4);
    addFirst(&head, 3);
    addFirst(&head, 2);
    assert(numberOfNodesInList(head) == 4);
    assert(getFirstElement(head) == 2);
    assert(getLastElement(head) == 5);
    //listan består nu av 2-3-4-5
    
    //Testar search (mitt i, forst, sist, data som inte finns)
    assert(search(head, 4) == 1);
    assert(search(head, 2) == 1);
    assert(search(head, 5) == 1);
    assert(search(head, 7) == 0);
    
    //Testar att tomma hela listan
    clearList(&head);
    assert(isEmpty(head));
    
    assert(search(head, 5) == 0);//Testar att soka i en tom lista
    assert(removeElement(&head, 3) == 0); //testar att ta bort från tom lista
    assert(numberOfNodesInList(head) == 0); //testar att räkna noderna i en tom lista
    
    printf("Congratulations!\nYour program passed the test\n");
}


/* Laboration 2 - Datastrukturer och Algoritmer */
/* Lankad lista */
#ifndef LIST_H
#define LIST_H
#include <stdio.h>
/**********************************************************************/
/*                                                                    */
/* Bestam om du vill gora en enkellankad eller en dubbellankad lista, */
/* valj motsvarande struct-definiton nedan.                           */
/* Oberoende av ditt val sa ser funktionsdeklarationerna likadana ut. */
/*                                                                    */
/* OBS!                                                               */
/* Du ska inte andra nagonting i interfacet                           */
/* Alla funktioner ska implementeras (i list.c)                       */
/**********************************************************************/
typedef int Data;
//Dubbellänkad lista
struct node
{
    Data data;
    struct node *next;
    struct node *previous;
};

/*Valj denna struktdefinition om du vill implementera en enkellankad lista*/
/*struct node
{
    Data data;
    struct node *next;
};*/


//Listan representeras av en nodpekare
typedef struct node *List;
//Returnera en tom lista
List createEmptyList(void);


//Ar listan tom?
//Returnerar 1 om listan ar tom, annars 0
int isEmpty(const List list);


//Lagg till nod forst i listan
void addFirst(List *list, const Data data);


//lagg till nod sist i listan
void addLast(List *list, const Data data);


//Ta bort forsta noden i listan
void removeFirst(List *list);


//ta bort sista noden i listan
void removeLast(List *list);


//ta bort data ur listan (forsta forekomsten), returnera 0 om datat inte finns, annars 1
int removeElement(List *list, const Data data);


//Sok efter data i listan, returnera 1 om datat finns, annars 0.
int search(const List list, const Data data);


//returnera hur manga noder som finns i listan
int numberOfNodesInList(const List list);


//tom listan /ta bort allt data (alla noder) ur listan
void clearList(List *list);


//Skriv ut listan
void printList(const List list, FILE *textfile);


//returnera forsta datat i listan
Data getFirstElement(const List list);


//returnera sista datat i listan
Data getLastElement(const List list);
#endif

#include "list.h"
#include <stdlib.h>
#include <assert.h>

/*Det är helt tillåtet att lägga till egna hjälpfunktioner men de befintliga funktionerna får inte ändras*/

/*Hjalpfunktion till add
  Allokerar minne for en ny nod
  om allokeringen lyckades initieras data samt pekare (pekare initieras till NULL).
  Den nya noden (eller NULL) returneras.*/
static struct node *createListNode(const Data data)
{
    struct node *pNewNode = calloc(1, sizeof(struct node));
    
    if(pNewNode != NULL)
    {
        
    }
    
    //Glom inte att testa sa att allokeringen lyckades innan du initierar noden
    return pNewNode; 
}



/*Returnera en tom lista - funktionen ar fardig*/
List createEmptyList(void)
{
    return NULL;
}



/*Ar listan tom?
  Returnerar 1 om den är tom, annars 0*/
int isEmpty(const List list)
{
    return 0; //ersatt med ratt returvarde
}




/*Lagg till nod forst i listan*/
/*Postcondition: Det nya datat ligger forst i listan (testa med assert)*/
void addFirst(List *list, const Data data)
{
    //Anropa createListNode for att skapa den nya noden
    //Glom inte att testa att den nya noden faktiskt kunde skapas/tilldelas minne innan du fortsatter
    //Tank pa att listan kan vara tom nar en ny nod laggs till
}




/*Lagg till nod sist i listan
  Tips, nar du hittat ratt plats kan du anvanda funktionen addFirst for att lagga till*/
void addLast(List *list, const Data data)
{
    
}



/*Ta bort forsta noden i listan
  Precondition: listan ar inte tom (testa med assert)
  Noden ska lankas ur och minnet frigoras, resten av listan ska finnas kvar*/
void removeFirst(List *list)
{
    //Glom inte att frigora minnet for den nod som lankas ur listan.
    //Tank pa att listans huvud efter bortlankningen maste peka pa den nod som nu ar forst.
}



/*Ta bort sista noden i listan
  Precondition: listan ar inte tom (testa med assert)t*/
void removeLast(List *list)
{
    //Glom inte att frigora minnet for den nod som lankas ur listan.
    //Tank pa att den nod som nu ar sist inte pekar nagonstans, dess pekare maste nollstallas
}



/*Ta bort data ur listan (forsta forekomsten)
  Returnera 1 om datat finns, annars 0
  Tips, nar du hittar ratt nod kan du anvanda en av de ovanstaende funktionerna for att ta bort noden*/
int removeElement(List *list, const Data data)
{
    return 0; //Ersatt med ratt returvarde
}



/*Finns data i listan?
  Om datat finns returneras 1, annars 0
  Tank pa att listan kan vara tom*/
int search(const List list, const Data data)
{
    return 0; //Ersatt med ratt returvarde
}



/*Returnera antalet noder i listan*/
int numberOfNodesInList(const List list)
{
    return 0; //Ersatt med ratt returvarde
}



/*Ta bort alla noder ur listan
  Glom inte att frigora minnet
  Postcondition: Listan ar tom, *list är NULL (testa med assert)*/
void clearList(List *list)
{
    //Alla noder maste tas avallokeras en och en, det racker inte att endast frigora list.
}



/*Skriv ut listan
  Vid anropet kan man ange stdout som argument 2 for att skriva ut på skarmen.
  Anvanda fprintf for att skriva ut.
  Den har typen av utskriftfunktion blir mer generell da man kan valja att skriva ut till skarmen eller till fil.*/
void printList(const List list, FILE *textfile)
{
    
}



/*Returnera forsta datat i listan
  Precondition: listan ar inte tom (testa med assert)*/
Data getFirstElement(const List list)
{
    return 0; //Ersatt med ratt returvarde
}



/*Returnera sista datat i listan
  Precondition: listan ar inte tom (testa med assert)*/
Data getLastElement(const List list)
{
    return 0; //Ersatt med ratt returvarde
}

Det du har gjort är att allokera en vektor, inte en lista.

För att göra en lista skall du ha noder som pekar på varandra, det kan vara enkel eller dubbel länkar.

En enkel lista kan se ut så här

type struct node
{
  int value;
  Node* next;

} Node;


Node* start = calloc(1, sizeof(Node));
start->value = 1;
Node* nyNod = calloc(1, sizeof(Node));
nyNod->value = 2;
start->next = nyNod;

// start pekar på första noden.

Fast man brukar ha en "last" pekare också för att göra det lättare att lägga till utan att söka listan efter den sista noden varje gång man vill lägga till en nod.

Node* start = NULL;
Node* last = NULL;
start = last = calloc(1, sizeof(Node));
start->value = 1;
Node* nyNod = calloc(1,sizeof(Node));
nyNod->value = 2;
last->next = nyNod;
last = nyNod;



// för att lägga till fler noder använder du bara 

nyNod = calloc(1,sizeof(Node));
nyNod->value = 3;
last->next = nyNod;
last = nyNod;

// osv.

sen skall du också avallokera minnet, det gör det genom att gå igenom listan och gör free() på varje nod