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

  1. #1
    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!

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  3. #3
    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.

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Popular pages Recent additions subscribe to a feed

Similar Threads

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

Tags for this Thread