Programming in C

L'prof

[rant]I hate link list and pointers[/rant]

Just wondering, I'm in second year of a Computer course and this is the first time I've come accross them...my head is in a world of pain!

If I want to become a programmer are they something I can avoid or something I will have to come to grips with?

Giblet

You can avoid them, but really, they aren't that hard and without them, you'd be more suited to program java or something. You just have to think about them logically and practically. What problems are you having specifically?

A linked list is just a structure that allows data in that list to find the next element of data, so you can traverse the list quickly, reshuffling it if you delete or add something to it.
A pointer is a way to point to a memory location to where a variable is stored. You can use variables in two ways, either by the memory location, or their value. (Using the memory location to reference a variable means if it is changed, anything pointing to that memory location will change too, using the value means that it will be copied i.e: not use the same memory location)

i71jskz5xu42pb

jasonorr wrote: »

If I want to become a programmer are they something I can avoid or something I will have to come to grips with?

If you want to be a good programmer you will need to understand them and all the other low level constructs.
Once you've mastered them, with the exception of a few jobs, you'll more that likely work with a language (Java, C#, whatever) that abstracts away all the low level nastiness.

See here for more

L'prof

Well, we've just been introduced to them but our lecturer seems to prefer to introduce new things to us via problem sheets and not actually in lectures! I'm sure its something I'll get the hang of but, I dont need it for the exam!

We have used pointers a small bit but it you look at task 7 here and all of this problem sheet here, we had to figure out how to set it all up and implement them too! Nobody got past task 4 last week so we had to do the link list stuff pretty much from scratch...the furthest anybody got today was setting up the link list stuff and reading in the numbers from a text file and printing out the original grid to the screen! It's a pity because I would have liked to have got this quirky little exercise done!

Tobias Greeshman

Surely a few minutes of google would give you access to sample code that would get your head around them.

Perhaps your lecturer wants you all to work on your own initiative and see how far ye all get? Who knows, but I see where you're coming from, linked lists via pointers in C take a while to get your head around.

I doubt your lecturer expected anybody to get it done in the time alotted, but just wanted to get you all to think about a problem like this. Quite a good problem to give a first year (assume you are), If you're that pissed at not getting it finished, do it in your own time.

L'prof

Nope, second year...shows how good my course is since you're making that assumption :eek:

I know for a fact that he wants us to think about the problem but, sometimes it just seems like he wants us to think about everyhing...if he's ever in a lab and I have a problem, he's the last person I ask because you get a vague response...generally try man "whatever"!

I would normally do problems like this in my own time but, exams are coming up so I only have time for study (and FM08 to unwind when I get bored of that )! Maybe I'll give it a go over the holidays but, prolly not!

Giblet

Well for each of the headers there, you just have to implement how they would work. Basically a linked list works like this.

You first have to create a node called head. This is your first node. By knowing the memory location of this node, you can traverse through all nodes in that list.

To add a new head node to the front, you can make a new node, make it the head node, and have it's *next point to the old head node.

To remove the head node, just make the *next the head node points to, the new head node.

To append a new node, traverse the list (you are given the head node as a parameter), until you have *next == null (all new nodes should have null as their *next), and make *next point to a new node.


This is pretty much your answer without me giving you any code.

L'prof

Thanks for that Giblet, a few of us got that done with a lot of help and a lot of headaches in the lab, we then moved on to reading the numbers into a list from a text file and printing that list out in the form of a Sudoku grid which was task 1 today...by then we had 30 mins remaining of our final lab this semester to finish this problem! Maybe our lecturer will go over this in one of our last 2 lectures but I feel it's very wasteful to help us with a solution after we've spent the best part of 2.5 hours banging our heads off walls and most students just leave out of frustration!

fasty

jasonorr wrote: »

[rant]I hate link list and pointers[/rant]

Just wondering, I'm in second year of a Computer course and this is the first time I've come accross them...my head is in a world of pain!

If I want to become a programmer are they something I can avoid or something I will have to come to grips with?

There are plenty of pre-made implementations of linked lists that you'll be able to use outside of college like those in the Standard Template library, the numerous container classes available through .Net and I think even MFC has a List class.

That said, it's important to have a vague idea what these classes do rather than just assuming they're a black box for data storage.

If you want to be a developer when you finish college, most graduate jobs will have a basic programming competency test and chances are, there will be something linked list related on it.

The best way to learn about it would be to hit your library and look for books that teach Data Structures in C and work through the examples.

monkey tennis

jasonorr wrote: »

If I want to become a programmer are they something I can avoid or something I will have to come to grips with?

In my opinion, if you can't (eventually) get your head around pointers and linked lists, you have no business being a programmer.

L'prof

monkey tennis wrote: »

In my opinion, if you can't (eventually) get your head around pointers and linked lists, you have no business being a programmer.

Sound, only just been introduced to them, I get the basic idea that they work like a fifo (stack) system, it just confused the hell outta me when I tried to implement the code for it and I was basically guessing as to what was a pointer and what wasn't but, I'm sure with a bit of time (which I don't have right now) I'll get my head around it!

I don't think many, if any of my fellow students understood what was going on!

carveone

jasonorr wrote: »

Sound, only just been introduced to them, I get the basic idea that they work like a fifo (stack) system, it just confused the hell outta me when I tried to implement the code for it and I was basically guessing as to what was a pointer and what wasn't but, I'm sure with a bit of time (which I don't have right now) I'll get my head around it!

I don't think many, if any of my fellow students understood what was going on!

I don't know how pointers are taught in college these days. Probably badly It can be a hard concept to understand if you haven't been taught the basics of machine language.

Back in the day, students who'd done some assembly language, primarily on home computers like the Spectrum or BBC, found pointers very easy to comprehend. In assembly language you really don't get any "padding" between you and the machine. Want some storage? Make it yourself...

Here's an example (I'm bored so I've gotta type something!)

You have a machine with a 64KB memory "map". This gives you an address space from 0000 - FFFF (hex of course). Say there's some video memory from F000 to FFFF. (Bear with me :rolleyes:)

So you want to write a character to the screen. You work out the location in memory where the character goes. Say the letter A (0x41) to location 0xF123. In machine language you would do something like:

move the value 0xF123 into a register.
move the value 0x41 into the value the register references.

In asm, this would be written something like mov [dx], ax.

The register dx contains the number 0xF123. If you did something like "mov dx, ax", then dx would now be 0x41. Not useful. The [dx] means put the value into the address that dx has. So 0x41 gets put into the address 0xF123. And lo, something happens on screen.

This is the most basic idea in assembly language. The concept of indirect addressing.

To map to the C language.

dx is a pointer: ie: p
[dx] is the referencing: ie: *p.

It can get really hard to comprehend when you have more levels so what I do is get a bit of paper and write it out:

      1000    1001     1002   1003   1004 ....
    +------+------+------+------+-----+
    +  H   +  e   +   l  +  l   +  o  +
    +------+------+------+------+-----+


      4000
   +------+
p: | 1000 |
   +------+

The boxes are memory. The numbers are the locations of that memory.

char *p;        /* Put some space aside and call it p */

p = 0x1000;   /* I'm still doing everything in hex */

*p      would be  'H';
*(p+1)  would be [1001]  which is 'e'
p++     now p = 0x1001.
*p      would be 'e';

Also:

p = 0x1000;
p[1] is the same thing exactly as *(p+1) and is 'e';

Too Easy?

Ok.

char **bob;

bob = 0x4000;  /* the address of p */
bob = &p;       /* exactly the same thing! */

*bob   would be the value 0x1000.
**bob  would be 'H';

bob[0]      is the same thing as *bob and is 0x1000.
bob[0][0]   is the same thing as **bob and is 'H';

I'm an experienced C programmer and I always get the pen and paper out when it gets to this! Otherwise it starts to wreck my head...

Any more questions?

Conor.

carveone

Just took a look at the task sheet linked to:

Item 1 - Recall from the lectures that an array variable is just a pointer to the first element of the array.

Really? That's fascinating. So if I increment an array variable I get the second item in the array do I.... Ohhh. Wait. No I do not! Sheesh. How about sizeof(array). Is that the same as sizeof(char *)??? Don't think so!

Apparantly your lecturer believes that "equivalent" means "identical to".

Ahem,

Conor.

Mutant_Fruit

carveone wrote: »

Item 1 - Recall from the lectures that an array variable is just a pointer to the first element of the array.

That is exactly right and the code snippet which followed that statement is also right. Unfortunately it teaches very bad practice and is very likely to confuse people.

The only reason why (*pointer) == *(pointer+1) is because char is of size '1'. That point should have been stressed in the handout.

Feelgood

carveone wrote: »

Any more questions?

Conor.

Are you the guy that programmed the Matrix we all live in?

Webmonkey

Assembly is actually an easy instruction based language to learn. You just need patience. I think every computer course should teach it as it gives a person a very clear overview and organisation of the system underneath.

The instructions may look daunting at first but really are very simple to grasp what is going on. Now adays everyone relies on pre compiled libraries or what ever to do the work. In otherwords languages, are becoming more and more abstract but also coming platfrom independent which can only be a good thing for today. But still, it is important to have at least some idea how the computer system underneath is organised.

Take a look at the Art of Assembly. It is a good free ebook though it teaches HLA, high level assembly but still the first few chapters are worth reading.

[ http://www.planetpdf.com/codecuts/pdfs/aoa.pdf ]

Donal

carveone

Feelgood wrote: »

Are you the guy that programmed the Matrix we all live in?

LOL! Guess I asked for that one

carveone

Mutant_Fruit wrote: »

That is exactly right and the code snippet which followed that statement is also right. Unfortunately it teaches very bad practice and is very likely to confuse people.

Not sure if you are agreeing or disagreeing with me! An array variable is a synonym for the first element of the array, not a pointer to it. However, an array lvalue will immediately decay into a pointer to that element. See pg 99 of the K&R C book.

I'm sounding like a complete pedant, but what I took issue with was the implication that an array was a pointer when it isn't. It's a large hole waiting for people to fall into :rolleyes:

The only reason why (*pointer) == *(pointer+1) is because char is of size '1'. That point should have been stressed in the handout.

I don't understand that... Do you mean seq == *(seq + i) ?? If so, that's independent of the array data. seq could be an array of elephants for all the difference it makes.

Conor.

Red Alert

Pointers are very important, and they're not incredibly hard to get your head around. I don't think they're much harder than a lot of programming concepts you'll come across.

A clear understanding of them can also help if you're trying to make qualitative statements about different implementations. Fortran for example doesn't really encourage (or for the most part provide) pointer use - compared to C, where the easy way to reverse say a list is to do it by pointers.

There's an interesting article on the subject here:
http://www.joelonsoftware.com/articles/ThePerilsofJavaSchools.html

(On the whole issue of assembly - i definitely think it should be taught. I had a couple of lectures on assembly and did one lab where we programmed a microcontroller in assembly. Very good for the understanding!)

monkey tennis

jasonorr wrote: »

I get the basic idea that they work like a fifo (stack) system

Not really (and btw, a stack is LIFO) - once the data is in there, you can remove any item at random, you don't have to pop off the top of the stack.

Webmonkey wrote: »

Take a look at the Art of Assembly. It is a good free ebook though it teaches HLA, high level assembly but still the first few chapters are worth reading.

I'd heartily recommend this - although it doesn't use 'proper' assembly language, it teaches the relevant concepts, which is the important thing.

Mutant_Fruit

carveone wrote: »

An array variable is a synonym for the first element of the array, not a pointer to it.

Right now, I think i'm getting mixed up in the point i'm trying to get across I think this will explain it better than i can:
http://www.lysator.liu.se/c/c-faq/c-2.html#2-2

carveone

Mutant_Fruit wrote: »

Right now, I think i'm getting mixed up in the point i'm trying to get across I think this will explain it better than i can:
http://www.lysator.liu.se/c/c-faq/c-2.html#2-2

Ah so we do agree. Excellent

That was the point I was attempting to make too. Much of my pedantry, um, I mean knowledge, comes from the C FAQ. That resource plus a decent C book (Ie: Kernigan and Richie) will answer any question you have on the language. Truly great stuff...

Conor.

L'prof

Hey, thanks for all the replies...I'm snowed under right now with other work for exams but I'm sure I'll find a lot of this very helpful!