Home     |     .Net Programming    |     cSharp Home    |     Sql Server Home    |     Javascript / Client Side Development     |     Ajax Programming

Ruby on Rails Development     |     Perl Programming     |     C Programming Language     |     C++ Programming     |     IT Jobs

Python Programming Language     |     Laptop Suggestions?    |     TCL Scripting     |     Fortran Programming     |     Scheme Programming Language


 
 
Cervo Technologies
The Right Source to Outsource

MS Dynamics CRM 3.0

C++ Programming

Question about usage of pointer in trees, linked list (The double indirection)


When implementing Linked list, stack, or trees, we always use pointers
to 'link' the nodes.
And every node is always defined as:
struct node
{
  type data; //data this node contains
  ...
  node * nPtr; //the next node's pointer

}

And we also define operations as insert, delete, etc. on the data
structure.
MY QUESTION IS:
why we always pass node**(pointer to the pointer to the node) as
argument to these operations? Why we can not just use the node *?

Thank you!

Ji

So the value of the pointer can be changed, as well as the value the
pointer point to.

--
Ian Collins.

In a good implementation of a linked list, the nodes are completely
hidden. You would never pass node* or node** to any operations.

What you are looking at is a bad implementation of a linked list. I
can't tell you why it uses node** or node* without seeing the code. It
shouldn't use either.

john

On Mar 10, 3:48 pm, John Harrison <john_androni@hotmail.com> wrote:

What does it mean by nodes are completely hidden(as being refered to,
nodes means the pointers to the actual struct block in memory, or the
structs themselves?)

> What you are looking at is a bad implementation of a linked list. I
> can't tell you why it uses node** or node* without seeing the code. It
> shouldn't use either.

> john

I paste the sample code below, which came from the book 'C how to
program'. John, could you please offer me a good example of
implementation of linked list? Thank you.

**********************************************************************
#include <stdio.h>
#include <stdlib.h>

struct listNode
{
  char data;
  struct listNode *nextPtr;

};

typedef struct listNode ListNode;
typedef ListNode *ListNodePtr;

void insert(ListNodePtr *, char);
char delete(ListNodePtr *, char);
int isEmpty(ListNodePtr);
void printList(ListNodePtr);
void instructions(void);

int main()
{
  ListNodePtr startPtr=NULL;
  int choice;
  char item;

  instructions(); //display the menu;
  printf(">");
  scanf("%d",&choice);

  while(choice!=3)
  {
    switch (choice)
    {
        case 1:
          printf("Enter a character: ");
          scanf("\n%c",&item);
          insert(&startPtr,item);
          printList(startPtr);
          break;

        case 2:
          if(!isEmpty(startPtr))
          {
            printf("Enter character to be deleted: ");
            scanf("\n%c",&item);

            if(delete(&startPtr,item))
            {
              printf("%c deleted.\n",item);
              printList(startPtr);
            }
            else
                printf("%c not found.\n\n",item);
          }
          else
            printf("List is empty.\n\n");
            break;
        default:
           printf("Invalid choice.\n\n");
           instructions();
           break;
    }
    printf(">");
    scanf("%d",&choice);
  }
  printf("End of run.\n");
  return 0;

}

void instructions(void)
{
   printf("Enter your choice:\n");
   printf("1 to insert an element into the list.\n"
          "2 to delete an element from the list.\n"
          "3 to exit the program.\n");

}

void insert(ListNodePtr *sPtr, char value)
{
  ListNodePtr newPtr, previousPtr, currentPtr;

  newPtr=malloc(sizeof(ListNode));
  if(newPtr !=NULL)
  {
    newPtr->data=value;
    newPtr->nextPtr=NULL;

   //set the searching index(previousPtr and
   //currentPtr)to the start of the list.
    previousPtr=NULL;
    currentPtr=*sPtr;

    while(currentPtr !=NULL && value>currentPtr->data)
    {
      previousPtr=currentPtr;
      currentPtr=currentPtr->nextPtr;
    }  //keep going

    if(previousPtr==NULL)
    {
      newPtr->nextPtr=*sPtr;
      *sPtr=newPtr;//insert the node at the beginning of the list
    }
    else
    {
      previousPtr->nextPtr=newPtr;
      newPtr->nextPtr=currentPtr;
    }
  }
  else
  {
    printf("%c not inserted. No memory available.\n",value);
  }

}

char delete(ListNodePtr *sPtr, char value)
{
  ListNodePtr previousPtr,currentPtr,tempPtr;

  if (value==(*sPtr)->data)
  {
    tempPtr=*sPtr;
    *sPtr=(*sPtr)->nextPtr;
    free(tempPtr);
    return value;
  }
  else
  {
    previousPtr=*sPtr;
    currentPtr=(*sPtr)->nextPtr;//setup the cursor at the beginning

  //when the cursor didn't reach the tail and cursor didn't find the
  //specified value, the cursor keep going along the list
  while(currentPtr !=NULL && currentPtr->data !=value)
  {
    previousPtr=currentPtr;
    currentPtr=currentPtr->nextPtr;//move on to next node
  }

  if(currentPtr !=NULL)//if not reaching the tail
  {
    tempPtr=currentPtr;
    previousPtr->nextPtr=currentPtr->nextPtr;
    free(tempPtr);
    return value;
  }
 }
 return '\0';//return null char;

}

int isEmpty(ListNodePtr sPtr)
{
  return sPtr==NULL;

}

void printList(ListNodePtr currentPtr)
{
  if(currentPtr==NULL)
  {
    printf("List is Empty.\n\n");
  }
  else
  {
    printf("The list is:\n");
    while(currentPtr !=NULL)
    {
        printf("%c--> ",currentPtr->data);
        currentPtr=currentPtr->nextPtr;
    }
    printf("NULL\n\n");
  }

}

****************************************************************
On Mar 10, 4:44 pm, "william" <william.m@gmail.com> wrote:

Above is all the code.

here is the segment that confuses me:

in 'main':
ListNodePtr startPtr=NULL;
...
...
insert(&startPtr,item);
...
And the prototype of 'insert' is:
void insert(ListNodePtr *, char);
// you can find the content in the code segment I posted just now.

So, is there any CONVENTION that how programmers implement different
data structure:
LINKED LIST
TREE
QUEQUE
STACK
and define operations on those data structure?

Where can I find a good resource talking about this?

william wrote:

> Above is all the code.

> here is the segment that confuses me:

> in 'main':
> ListNodePtr startPtr=NULL;
> ....
> ....
> insert(&startPtr,item);
> ....
> And the prototype of 'insert' is:
> void insert(ListNodePtr *, char);

What part of this confuses you?  If insert didn't take the address of
startPtr, how could it change it?

--
Ian Collins.

> I paste the sample code below, which came from the book 'C how to
> program'. John, could you please offer me a good example of
> implementation of linked list? Thank you.

I didn't realise you were programming in C. C and C++ are different
languages, what is good in C not the same as what is good in C++.

The code below is probably fine in C, but it wouldn't be good C++. In
C++ it's much easier to seperate the interface from the implementation.

If you haven't got your answer already (Ian has given you the answer)
you should probably ask questions about this code on comp.lang.c, it's C
not C++.

john

william wrote:

[snip]

> So, is there any CONVENTION that how programmers implement different
> data structure:
> LINKED LIST
> TREE
> QUEQUE
> STACK
> and define operations on those data structure?

Yes, there is: you don't implement them yourself, you use the standard
library instead. It provides (among other things):

std::list
std::queue
std::stack

and for problems involving search trees:

std::set, std::multiset
std::map, std::multimap

> Where can I find a good resource talking about this?

Any introduction to the standard library should cover the standard container
classes and adaptors.

Best

Kai-Uwe Bux

On Mar 10, 5:00 pm, Ian Collins <ian-n@hotmail.com> wrote:

Thank you Ian, I understand it now. The whole structure is a
pointer(to the starting struct), so we need to change it if we insert
a new node at the beginning, right?

On Mar 10, 5:09 pm, Kai-Uwe Bux <jkherci@gmx.net> wrote:

Thank you for your reply! I got it.

regards

Ji

Add to del.icio.us | Digg this | Stumble it | Powered by Megasolutions Inc