lina
lina

Reputation: 1707

creating a queue of pointers in c

i have a dynamic number of pointers all having the same size. i need to store all the addresses of my pointers in some place like a link List in order to fetch them later on.
my question is what structs should i use. is the following correct:

struct Node{
    int *k;
Node*Next;
}

struct LS{
    Node*first,*last;
    void push(Node*n);
    Node* GetFirst();
    Node* GetLast();
}

the LS is the linked list that stores Nodes. and a Node is a struct that holds the address of my pointer and a pointer to the next Node.
am i using int *k to store the address of my pointer correctly? should i continue with this implementation or is there any easier way to do this?

Upvotes: 0

Views: 6701

Answers (3)

Ivan Bohannon
Ivan Bohannon

Reputation: 707

WDM.H (microsoft header) has a bunch of linked list stuff to look at ( http://msdn.microsoft.com/en-us/library/ff547799(VS.85).aspx ) , I've cut and pasted from that, and added a very simple example.

typedef struct _LIST_ENTRY {
   struct _LIST_ENTRY *Flink;
   struct _LIST_ENTRY *Blink;
} LIST_ENTRY, *PLIST_ENTRY;

typedef struct _MY_THING
{
    LIST_ENTRY           ListEntry;
    ULONG                randomdata1;
    ULONG                randomdata2;
    ULONG                randomdata3;
    ULONG                randomdata4;
} MY_THING, *PMY_THING;

#define CONTAINING_RECORD(address, type, field) ((type *)( \
                                                  (PCHAR)(address) - \
                                                  (ULONG_PTR)(&((type *)0)->field)))


VOID
InsertHeadList(
    IN PLIST_ENTRY ListHead,
    IN PLIST_ENTRY Entry
    )
{
    PLIST_ENTRY Flink;

    Flink = ListHead->Flink;
    Entry->Flink = Flink;
    Entry->Blink = ListHead;
    Flink->Blink = Entry;
    ListHead->Flink = Entry;
}

VOID
InitializeListHead(
    IN PLIST_ENTRY ListHead
    )
{
    ListHead->Flink = ListHead->Blink = ListHead;
}

PLIST_ENTRY
RemoveHeadList(
    IN PLIST_ENTRY ListHead
    )
{
    PLIST_ENTRY Flink;
    PLIST_ENTRY Entry;

    Entry = ListHead->Flink;
    Flink = Entry->Flink;
    ListHead->Flink = Flink;
    Flink->Blink = ListHead;
    return Entry;
}



void main()
{
    LIST_ENTRY HeadOfMyList;
    MY_THING Thing; 

    InitializeListHead(&Head);
    // example of add thing to list.    
    InsertHeadList(&HeadOfMyList, &Thing.ListEntry);

    // example of removing thing from the list
    PLIST_ENTRY listEntry = RemoveHeadList(&HeadOfMyList);
    PMY_THING pThing = (PMY_THING) CONTAINING_RECORD(listEntry, MY_THING, ListEntry);
}

Upvotes: 0

scatman
scatman

Reputation: 14575

this sample code may help you start...

#include <stdio.h>  

struct Node{
int *k;
Node *Next;
}* Temp;
struct LS
{
Node *first,*last;
void push(Node *MyNode)
{
    MyNode->Next=NULL;
    if(empty())
    {
        first=MyNode;
        last=MyNode;
    }
    else
    {           
        last->Next = MyNode;
        last=MyNode;
    }
}
Node* front()
{
    return first;
}
void pop()
{   
    free(first->k);
    first=first->Next;      
}
bool empty()
{       
    if(first==NULL) return true;    
    return false;
}
};
int N=10;

int main() 
{
LS Q;Q.first=NULL;
for(int i=0;i<3;i++)
{
    Node *NewNode= (Node*)malloc(sizeof(Node));
    NewNode->k = (int*)malloc(sizeof(int)*N);
    for(int k=0;k<N;k++) NewNode->k[k]=i;
    Q.push(NewNode);
}
while(!Q.empty())
{
    Temp=Q.front(); 
    for(int i=0;i<N;i++) printf("%d ",Temp->k[i]);
    printf("\n");
    Q.pop();
}

return 1;
}

Upvotes: 1

Jim Clay
Jim Clay

Reputation: 1003

Yes, your Node struct is correct.

As to whether there is an easier way it depends. If there is a maximum number of pointers that you will need then an array of pointers would be easier. If you can do it in C++ then an STL vector (can use it like an array, but underneath the hood it can grow dynamically as needed) is easier. If you have to do it in C and it has to be dynamic, though, then no, there is not an easier way.

Upvotes: 0

Related Questions