Double Pointer to a data type that is already a pointer!

nicm · 04-03-2009, 08:28 PM

I'm writing a function to recursively merge and sort a linked-list. (An improved merge-sort algorithm that avoids scanning the list.)

The function needs to return the sorted first half of the list and the rest of the list. The function is passed the length of the list as an argument n, it recursively calles itself with length n/2 to split the list into single elements before merging it back together in sorted order.

I think I have determined the algorithm that is required - i'm struggling with the C implementation.

As the function is required to return 2 values, I think I need to use a double pointer when calling the function. (So it can modify the calling pointer to point to the second half of the list.)

I have been provided with the following struct definition:

insert

Code:

typedef struct node Node;
typedef Node* Link;
struct node{int item; Link next;}

My interpretation of the line [typedef Node* Link] is that it defines the type Link to be a pointer, that points to something of type Node.

I'm struggling with the concept of using a double pointer to point to something that is already defined as a pointer.

Can anyone help me with which is the appropraite function prototype in order to have the pointer that is passed to the function, updated by the function? (it needs to return a pointer to a node in the linked list)

Link mergesort_no_scan(int n, Link **list)
-> this to me looks like a double pointer to something that is already a pointer (triple pointer?)

Link mergesort_no_scan(int n, Link *list)
-> Link is already a pointer. If I define the function like this am I calling the function with a double pointer?

Link mergesort_no_scan(int n, Node **list)
-> Or should I be avoiding using the Link pointer when calling the function, and passing the function a pointer to a pointer to a node instead?

Help! I'm totally confusing myself with all this pointer talk!

quzah · 04-03-2009, 08:32 PM

I hate people who typedef pointers.

Link is already a pointer. It points to a node. So all you need is a pointer to a Link.

Quzah.

nicm · 04-03-2009, 08:43 PM

Thanks. As I thought.
Is there any benefit to typedef'ing a pointer? All I can think is it means you don't have to type Node *list, just Link list.

quzah · 04-03-2009, 08:46 PM

For some people, they find it easier to deal with pointers that way. I don't like them because if I'm dealing with a pointer, I want that visibility when I'm using it.

Code:

Datatype x;

Is that a pointer or not? Who knows, now I have to go hunt up the typedef.

Code:

Datatype *x;

Is that a pointer? Yes, yes it is.

Quzah.

iMalc · 04-04-2009, 01:54 AM

I dislike people typedefing pointers when they are not named such that it is obviously a pointer, but otherwise it's fine.
I often prefer:

Code:

typedef Node *NodePtr;

NodePtr x;

over

Code:

Node *x;

, which I always prefer over

Code:

typedef Node *Link;

Link x;

Elysia · 04-04-2009, 03:45 AM

I fail to see a good reason to typedef pointers. They get longer to type and you lose track of the type unless it's really well named, but then again, what need have you for doing that? You're only going to have to type an obfuscated name or a longer name.
So avoid them.

04-03-2009, 08:28 PM	#1
nicm Registered User Join Date: Apr 2009 Posts: 2	Double Pointer to a data type that is already a pointer! I'm writing a function to recursively merge and sort a linked-list. (An improved merge-sort algorithm that avoids scanning the list.) The function needs to return the sorted first half of the list and the rest of the list. The function is passed the length of the list as an argument n, it recursively calles itself with length n/2 to split the list into single elements before merging it back together in sorted order. I think I have determined the algorithm that is required - i'm struggling with the C implementation. As the function is required to return 2 values, I think I need to use a double pointer when calling the function. (So it can modify the calling pointer to point to the second half of the list.) I have been provided with the following struct definition: insert Code: typedef struct node Node; typedef Node* Link; struct node{int item; Link next;} My interpretation of the line [typedef Node* Link] is that it defines the type Link to be a pointer, that points to something of type Node. I'm struggling with the concept of using a double pointer to point to something that is already defined as a pointer. Can anyone help me with which is the appropraite function prototype in order to have the pointer that is passed to the function, updated by the function? (it needs to return a pointer to a node in the linked list) Link mergesort_no_scan(int n, Link *list) -> this to me looks like a double pointer to something that is already a pointer (triple pointer?) Link mergesort_no_scan(int n, Link list) -> Link is already a pointer. If I define the function like this am I calling the function with a double pointer? Link mergesort_no_scan(int n, Node **list) -> Or should I be avoiding using the Link pointer when calling the function, and passing the function a pointer to a pointer to a node instead? Help! I'm totally confusing myself with all this pointer talk!
nicm is offline

04-03-2009, 08:32 PM	#2
quzah +++ OK NO CARRIER Join Date: Oct 2001 Posts: 10,262	I hate people who typedef pointers. Link is already a pointer. It points to a node. So all you need is a pointer to a Link. Quzah. __________________ Hundreds of thousands of dipshits can't be wrong. Are you up for the suck?
quzah is offline

04-03-2009, 08:43 PM	#3
nicm Registered User Join Date: Apr 2009 Posts: 2	Thanks. As I thought. Is there any benefit to typedef'ing a pointer? All I can think is it means you don't have to type Node *list, just Link list.
nicm is offline

04-03-2009, 08:46 PM	#4
quzah +++ OK NO CARRIER Join Date: Oct 2001 Posts: 10,262	For some people, they find it easier to deal with pointers that way. I don't like them because if I'm dealing with a pointer, I want that visibility when I'm using it. Code: Datatype x; Is that a pointer or not? Who knows, now I have to go hunt up the typedef. Code: Datatype *x; Is that a pointer? Yes, yes it is. Quzah. __________________ Hundreds of thousands of dipshits can't be wrong. Are you up for the suck?
quzah is offline

04-04-2009, 01:54 AM	#5
iMalc Algorithm Dissector Join Date: Dec 2005 Location: New Zealand Posts: 2,476	I dislike people typedefing pointers when they are not named such that it is obviously a pointer, but otherwise it's fine. I often prefer: Code: typedef Node NodePtr; NodePtr x; over Code: Node x; , which I always prefer over Code: typedef Node *Link; Link x; __________________ My homepage Advice: Take only as directed - If symptoms persist, please see your debugger
iMalc is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
sorting the matrix question..	transgalactic2	C Programming	47	12-22-2008 03:17 PM
failure to import external C libraries in C++ project	nocturna_gr	C++ Programming	3	12-02-2007 03:49 PM
newbie needs help with code	compudude86	C Programming	6	07-23-2006 08:54 PM
Unknown Math Issues.	Sir Andus	C++ Programming	1	03-06-2006 06:54 PM
HUGE fps jump	DavidP	Game Programming	23	07-01-2004 10:36 AM