Any C programmers in the building?

[Overdriven]

I've got a question.

What I've done so far:

I've created an array, supports 7 different items. I can get said items to list in the order, no problem.

Now (Not sure what it is, the pop/push methods?) I'm not sure how to do this:

I need item in position 0 to move/'leave' the array, item in positon 1 to move to 0 and so fourth (so eventually each item will leave, and come back but starting at the end of the 'que') .. and I need to be able to display that.

I've got other stuff after that, such as having to be able to add to a random part of the arraay, if there is space, moving items backwards to make room.. but that's for a different time.

Any advise? (Or should I just learn pop/push?)

Cheers.

 

[kirennia]

Psuedo code inc!

//If you want to make this avaliable for any item in the array, declare 'x'
//beforehand and make it equal the item + 1

//get the size of the array

for (int x = 0; i < arraySize - 1; i++)
array[x] = array[x+1];

//Delete the last item in the array.


It's a shame arrays aren't dynamic really. I would recommend looking up STL vectors if you've been doing the language for a little while. So so much easier to use, dynamic, have their own quick functions for most calls.

 

[Overdriven]

Ah cheers Kir, got the first bit working thanks to that. I don't want to ask help for the rest of what I want to do, trying to work it out from the code you just gave me. Will probably hear me crying for help in a bit again

 

[SheepCow]

Popping and pushing are simply operations that can be done on a large number of structures. A queue if first in, first out (FIFO) you "push" a item on to the end of it and "pop" items off the front (things come out in the order they were put in)

I need item in position 0 to move/'leave' the array, item in positon 1 to move to 0 and so fourth (so eventually each item will leave, and come back but starting at the end of the 'que') .. and I need to be able to display that.

What you're describing there is a pop. You're popping the first element out of the queue and moving the rest up.

 

[Overdriven]

Oooh, cheers Sheep. *Will look into it* That may probably be what I need to do honestly.

Anywhere you suggest looking? (I'm not the best C programmer in the world =<)

 

[SheepCow]

Well if you want to do it with an array (a good place to start) then I'd advice making 2 functions. One to push an item on to the array, another to pop an item off.

Without writing it for you, since half of the fun is in the coding, I'd try something like this for a queue of integers:

#define ARRAYSIZE 10

void mypush(int array[], int size, int newItem);
int mypop(int array[], int size);

int main(void)
{
    int value;
    int myQueue[ARRAYSIZE] = { -1 }; /* fills array with -1's */

    mypush(myQueue, ARRAYSIZE, 5);
    ...

    result = mypop(myQueue, ARRAYSIZE);
    ...

    return 1;
}

You'd then need to create the mypop and mypush functions. The push one would simply work through the array looking for the first unused position and put the new item there.

Popping would remember the first value in the array, then move all the others down, doing something like (which is what kirennia said above):

int i, result;

result = array[0];

for (i = 0; i < size-1; i++)
{
    array[i] = array[i+1];
}

return result;

In that I'm using a value of -1 to mean "there's nothing in this position", so obv. sticking a -1 in to the queue will break it

Edit: I had a quick look on Wikipedia but it's not that helpful. This page here isn't bad, they use some global variables to remember how far in to the queue you are.

 

[Overdriven]

Ah funky, much thanks. Aye, I'm doing it via an array. I'll try and work it out (If I can get it working by mid week I'll be happy) and see what happens. This'll probably help me in Java too actually. (Which I actually prefer to basic C)

 

[Chilly]

linked lists! far more efficient as you dont need to mess about moving everything along one. When you have queues 5 million long doing a shift == insane.

ini java you use the pop() and push(object) methods on any o the myriad list/array classes

 

[Overdriven]

Well, good news is.. Me getting the first part was enough to keep the tutor happy.
Now, time to get this functioning to a point where it works...

*re-googles pop/push methods for C and tries to get it complete in the next hour* Kinda looked up at it today during my C lecture (Algorithms and Data Structures in C )

@Chilly: Linked lists comes next week

 

[kirennia]

Well, good news is.. Me getting the first part was enough to keep the tutor happy.
Now, time to get this functioning to a point where it works...

*re-googles pop/push methods for C and tries to get it complete in the next hour* Kinda looked up at it today during my C lecture (Algorithms and Data Structures in C )

@Chilly: Linked lists comes next week

Have you been explicitally told to do arrays? If not, I don't mind giving you a run down on STL vectors, they're extremely useful mate. Correct me if I'm wrong Chilly (It's been a little while since I used Java), but aren't link lists pretty much the java equivalent to STL vectors? Thus it's useful to know both

 

[Overdriven]

· The queue is to be implemented as an array of some maximum size.
· Taxi registration numbers are to be integers.
· The menu options for the nine tasks above are to be the integers, 1 to 7, and 8 for
exit.

That was the easy bit. - Quick switch statement, but it requires the push/pop functionality (still researching)

2nd bit:

The queue is to be implemented as a linear linked list.
· Taxi registration numbers are to be alpha-numeric, e.g. A1234.
· The menu options for the nine tasks above are to be strings, e.g. “arrive” etc.

This linked list should only be accessed by two pointers:

front which indicates the front node in the queue
rear which indicates the last node in the queue

Pointers, front and rear, should be encapsulated in a C struct.
A linked list node structure should also be encapsulated in a C struct.

Which we've not yet been taught, so I'm gonna look at it later or tomorrow.

 

[Chilly]

Have you been explicitally told to do arrays? If not, I don't mind giving you a run down on STL vectors, they're extremely useful mate. Correct me if I'm wrong Chilly (It's been a little while since I used Java), but aren't link lists pretty much the java equivalent to STL vectors? Thus it's useful to know both

Kids these days! (im only 24, probably about your age, ahem )

A linked list is a fundamental data structure used in *all* programming languages that are any use.

There are two (main) types of linked list, singly and doubly linked.

signly: A0 is the only bit of data in the list. Lets push(A1). A0 now has a link to the memory address of A1 stored in its local struct (each list item will be (in C terms) a struct that has two fields: payload (a pointer) and a link to the next item (also a reference)). Thus if I need to traverse the list from A0 through A1 to An, I have to follow each of these links, jumping from item to item.

this has two implications for programmers: if you need fast, random access to your list, dont use linked lists. You cant do var = list[5] in constant time. some list implementations support this feature, but it's not fast and you are probably making a mistake by using it. If, however, you only ever care about the current item and the next one in the list, then an array is a waste of overhead and a linked list is much nicer. also of note with linked lists is the ability to insert an item into any location in the list with (in the case of singly linked lists) only three operations:
break current link from An to An+1, link A1 to Anew and link Anew to An+1 (all of which you have to hand in current memory).

Imagine popping an item off the end of a linked list, it's one operation (maybe two or three depending on how you have implemented it and various other things you can do) instead of one operation PLUS shunting everything along one in the array (which is horrible).

Doubly linked lists are pretty much exactly the same but each item is linked to the node in front AND the node behind, allowing bi-directional traversal where singly linked lists only offer unidirectional traversal.

Oh and linked lists can and are fragmented in memory and dynamic by their nature. Arrays in C are continuous lumps of memory and if the OS cannot give you the size block you asked for in one go it WILL bail out, even if there is plenty of ram available but fragmented. I suspect they cause much pain for garbage collectors too

Capiche?

 

[kirennia]

Kids these days! (im only 24, probably about your age, ahem )

A linked list is a fundamental data structure used in *all* programming languages that are any use.

There are two (main) types of linked list, singly and doubly linked.

signly: A0 is the only bit of data in the list. Lets push(A1). A0 now has a link to the memory address of A1 stored in its local struct (each list item will be (in C terms) a struct that has two fields: payload (a pointer) and a link to the next item (also a reference)). Thus if I need to traverse the list from A0 through A1 to An, I have to follow each of these links, jumping from item to item.

this has two implications for programmers: if you need fast, random access to your list, dont use linked lists. You cant do var = list[5] in constant time. some list implementations support this feature, but it's not fast and you are probably making a mistake by using it. If, however, you only ever care about the current item and the next one in the list, then an array is a waste of overhead and a linked list is much nicer. also of note with linked lists is the ability to insert an item into any location in the list with (in the case of singly linked lists) only three operations:
break current link from An to An+1, link A1 to Anew and link Anew to An+1 (all of which you have to hand in current memory).

Imagine popping an item off the end of a linked list, it's one operation (maybe two or three depending on how you have implemented it and various other things you can do) instead of one operation PLUS shunting everything along one in the array (which is horrible).

Doubly linked lists are pretty much exactly the same but each item is linked to the node in front AND the node behind, allowing bi-directional traversal where singly linked lists only offer unidirectional traversal.

Oh and linked lists can and are fragmented in memory and dynamic by their nature. Arrays in C are continuous lumps of memory and if the OS cannot give you the size block you asked for in one go it WILL bail out, even if there is plenty of ram available but fragmented. I suspect they cause much pain for garbage collectors too

Capiche?

Pfft, I'm 25 going on 26 so right back at you

As for linked lists, they do sound an awful lot like STL vectors which are dynamic in memory allocation also, except you can access any part of it, inserting new instances with relative ease. Sometimes arrays just don't cut it imo... in the first year of uni they taught them almost religiously before explaining how they do have limited use, then we moved onto linked lists and finally STL vectors in C++ which are so so much easier to use, so long as you structure your classes right.

Being that I'm trying to implement a scalable graphics engine which creates through AI a randomly generated city of any size (potentially, as my final year project), these have proven very valuable as I would expect for nigh on any game or large system. The overhead costs are however a bit of a worry but using the vectors pre-runtime with only minimal access during a programs operation, then they come into fruition. Out of paranoia, I have been populating them pre-runtime all together before moving onto loading other parts, just so that the initial basis of the vectors are all pretty close in the meory space (although I suspect that isn't quite how it works).

I still remember the days of creating an array of 1000 just so it'd not fill up easily, then getting to the point where it's just not possible to continue with them.

Both have merits, vectors are easier and more dynamic imo, but are c++ only (correct me if I'm wrong)

 

[Chilly]

You could just write your own version of stl vector in C, probably. might not be quite as easy to use but will do everything stl vector does. Again, I'd like to point out that linked lists are the BASIS for many "modern" data structures and are a fundamental idea in computer science, going back a long time.

 

[Overdriven]

*Googles*

PS: Am 21, 22 in October. So, not much younger.

 

[SheepCow]

You were much better off getting used to how it works with an array before moving in to the land of pointers and structures, but now you're there

Massive spoilers ahead, only read if you're stuck

I don't know how much C you know, so in an effort to make this usable by others in the future I'll assume you're a nubcake.

Pointers

In C you get these little things called pointers. A pointer is an address in memory, the thing you're interested in is at the address the pointer "points" to.

Of course you need somewhere to put the pointer, so you put it in a variable.

You then have a variable, that's a pointer, to something more interesting.

These pointers are what come in handy for linked lists and pretty much everything ever. Rather than moving your data around (which might be a 1MB lump of widgets) you just modify a pointer (32-bit, 64-bit, or whatever) -- obviously changing a few bytes is faster than moving 1MB.

There are a few operators in C you'll need to know about, they are * and &.

The * operator means "I want whatever is at the address this pointer points to", e.g. in the picture below "ptr" is a pointer to memory location 0x000A. THe contents of memory location 0x000A is the integer 5. So *ptr means 5 and ptr means 0x000A.

The & operator means "I want the address of the variable", e.g. in the picture below "x" is a variable with integer value 5, and is at memory location 0x000B. So &x means 0x000B, x means 5. If you did *x, you'd be say "give me the value at memory location 5" -- which while valid is 99.9% of the time going to be in someone elses memory and you'll get a segmentation fault.

You define a pointer like by doing:

int *pointerToAnInt;

/* set the value to 5, this will actually explode unless you've allocated enough memory at the location etc. */
*pointerToAnInt = 5;

/* this is not what you meant, this sets the pointer to point at memory location 5, which is highly unlikely to be what you wanted */
pointerToAnInt = 5;

Now you know what a pointer is, you can hopefully imagine this:

Instead of a fixed length array, have a pointer to the start of your queue. Each item in the queue has a pointer to the next item (this is a singly linked list). So to find something you'd start at the front, following the "next" pointers until you got to the one you want or the end.

Structures

In C a structure is about as close to an object as you'll get. A structure just gives you a nice way to group some related bits of data together. If you wanted a linked list of integers, you might want a structure with an integer (the value) and a pointer (to point to the next item).

struct ListItem {
  int value;
  struct ListItem *next;
};

You'd then have some code like this:

/* pointer to the head of the linked list, NULL is typically a void pointer to 0 */
struct ListItem *head = NULL;

When adding an item you'd

struct ListItem *listPtr = NULL;

/*
listPtr is set to the head of the list
while the listPtr is not NULL, follow the list to the next item
*/
for (listPtr = head; listPtr != NULL; listPtr = listPtr->next)
{
  /* print out the value */
  printf("%d\n", listPtr->value);
}

I've used the -> operator above, it's to do with pointers and structs, you can look it up. You'll also want to look up malloc (memory allocate) so you can get some memory to put your structures in.

There's plenty of stuff on the web to do with C, just make sure if you want C you're doing C and not C++.

 

[Chilly]

outdone by a crossbreed between a sheep and a cow!

 

[Overdriven]

Okay, I got it working. Was just missing a for loop. I can now add them (have to add first!) delete them (works \o/) but slight problem.. When I've deleted all 5, I can't add more. Hmm.. *Takes a look at the add code now*

EDIT: Fixed it. Rofl.. All I needed was this "back--;" just outside the loop.. It all works now.

 

[Bahumat]

Hehe I love these threads, never understand a bloody word of what's going on, but I can almost picture Matt Damon turning up with all the answers!

 

[Chilly]

matt damon....? what is wrong with you?

 

[Milkshake]

What is WRONG with you Dahhhhling?

 

[Bahumat]

Good Will Hunting lol

 

[Overdriven]

Mister nubcake has a NEW C based question..

I've got a menu implemented (yay at using millions of functions for this one) and the user has to type out their decision.

Any idea how I do this? Since string doesn't exist just char. I know I have to declare a char lenght (say.. 10, to be safe) but I'm not sure about the rest

 

[Overdriven]

Okay, since I missed the timer (and need to write down thoughts.)

declar a char and a max length
create a function which loops through each letter inpoutted (hmm..)
if the loop relates to a menu option, do output.
... and make some of it only doable via linked lists and structs

 

[SheepCow]

Look up scanf()

 

[Overdriven]

Look up scanf()

I'm not that much of a nubcake

 

[Overdriven]

I'm not that much of a nubcake

I found my cure.. strcmp. That'll solve all my issues I think. Hoorah.

(I seem more nubbish than I actually am =o, I'd hope so anyway.. Being in the 8th week of C lectures.. -_-)

 

[Chilly]

all of the str* functions will help. C isnt *quite* that cuntish that you have to do your own string comparisons. What you want to do is use a case block, or at least a if elseif else block.

 

[SheepCow]

Anyway, scanf() will happily read a "string" in to your buffer for you to then strcmp. Or you may want to read 1 char at a time to ensure you don't buffer overrun. As you can't do a switch on a char* you may prefer to use atoi() to convert the "123" to an integer 123.

 

[Overdriven]

Anyway, scanf() will happily read a "string" in to your buffer for you to then strcmp. Or you may want to read 1 char at a time to ensure you don't buffer overrun. As you can't do a switch on a char* you may prefer to use atoi() to convert the "123" to an integer 123.

Hmm.. I'll see what happens when I start coding it. Next set of inputted data has to be "A123", "B123", "C123" etc.