Big problem doing sorted insertion in a list

[Franco Perilli]

I've compiled this code and no problems, but when I run the program, it
prints only the last entry i've inserted. Looks like a problem in the
sorted insertion algorithm. Can u help me plz?

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

/*---data type---*/
typedef int type;
/*---------------*/

/*---the node---*/
struct node
{
type data;
struct node *next;
};
typedef struct node Node; /* <-defines the node object */
typedef Node *NodePtr; /* <-defines the pointer to a node */
/*-------------*/

/*sorted insertion*/
void addsorted(NodePtr *root, type value)
{
NodePtr newptr;
NodePtr back;
NodePtr curr;
if(newptr = malloc(sizeof(Node)))
{
newptr->data = value;
newptr->next = NULL;
back = NULL;
curr = *root;
while(curr != NULL && value > curr->data)
{
back = curr;
curr = curr->next;

}
if(back == NULL) /*value is the smallest number in
the list*/
{
newptr->next = *root;
*root = newptr;
}
else /* back<value<curr */
{
back->next = newptr;
newptr->next = curr;
}
}
}
/*---------------*/

/*-list printer--*/
void printlist(NodePtr root)
{
while(root)
{
printf("\n%d\n", root->data);
root = root->next;
}
}
/*---------------*/

/*---the main----*/
int main()
{
NodePtr root = NULL;
char ins;
printf("Inserisci i numeri della lista, inserisci un carattere
per interrompere\n");
while(1 == scanf("%d", &ins))
{
addsorted(&root, ins);
}
if(root)
printlist(root);
system("Pause");
return 0;
}

 

[Franco Perilli]

Franco Perilli ha scritto:

I've compiled this code and no problems, but when I run the program, it
prints only the last entry i've inserted. Looks like a problem in the
sorted insertion algorithm. Can u help me plz?

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

/*---data type---*/
typedef int type;
/*---------------*/

/*---the node---*/
struct node
{
type data;
struct node *next;
};
typedef struct node Node; /* <-defines the node object */
typedef Node *NodePtr; /* <-defines the pointer to a node */
/*-------------*/

/*sorted insertion*/
void addsorted(NodePtr *root, type value)
{
NodePtr newptr;
NodePtr back;
NodePtr curr;
if(newptr = malloc(sizeof(Node)))
{
newptr->data = value;
newptr->next = NULL;
back = NULL;
curr = *root;
while(curr != NULL && value > curr->data)
{
back = curr;
curr = curr->next;

}
if(back == NULL) /*value is the smallest number in
the list*/
{
newptr->next = *root;
*root = newptr;
}
else /* back<value<curr */
{
back->next = newptr;
newptr->next = curr;
}
}
}
/*---------------*/

/*-list printer--*/
void printlist(NodePtr root)
{
while(root)
{
printf("\n%d\n", root->data);
root = root->next;
}
}
/*---------------*/

/*---the main----*/
int main()
{
NodePtr root = NULL;
char ins;
printf("Inserisci i numeri della lista, inserisci un carattere
per interrompere\n");
while(1 == scanf("%d", &ins))
{
addsorted(&root, ins);
}
if(root)
printlist(root);
system("Pause");
return 0;
}

Solved. It is:

int ins;

Instead of:

char ins;

 

[Andrew Poelstra]

I've compiled this code and no problems, but when I run the program, it
prints only the last entry i've inserted. Looks like a problem in the
sorted insertion algorithm. Can u help me plz?

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

/*---data type---*/
typedef int type;

You might want to call this node_type or something more relevant to
linked lists. If you ever use this code for anything, you'll want to
differentiate between different structures.

/*---------------*/

/*---the node---*/
struct node
{
type data;
struct node *next;
};
typedef struct node Node; /* <-defines the node object */
typedef Node *NodePtr; /* <-defines the pointer to a node */

Do not hide pointers behind typedefs. That's just begging for trouble.
Reading through your code, it's confusing the crap out of me because
you have a bunch of pointers without *'s to indicate their pointerhood.
At a glance, the symbol `*' is much easier to see than `Ptr'.

/*-------------*/

/*sorted insertion*/
void addsorted(NodePtr *root, type value)
{
NodePtr newptr;
NodePtr back;
NodePtr curr;

Just do
Node *new, *prev, *cur;

if(newptr = malloc(sizeof(Node)))

newptr = malloc (sizeof *newptr) is better style and much easier to maintain.

{
newptr->data = value;
newptr->next = NULL;
back = NULL;
curr = *root;
while(curr != NULL && value > curr->data)
{
back = curr;
curr = curr->next;
}
if(back == NULL) /*value is the smallest number in
the list*/

Good comment. May I recommend using 2 or 4-space tabs on Usenet, though? 8
spaces makes lines wrap and it's difficult to read.

{
newptr->next = *root;

This doesn't compile cleanly, does it? You've assigned a Node to a Node *.
Oh, wait. You've assigned to a NodePtr *, which is a Node **. See how
confusing that is?

*root = newptr;

So, (*root)->next == *root? This is a circular list, I see. Perhaps you
should have indicated that somewhere, because the code isn't exactly
self-documenting.

I'll stop here and let some compilers and pedants give you some more
detailed help; fix the typedef'd pointer and wide indentation, and I'll
happily read through the rest.

 

[Franco Perilli]

You might want to call this node_type or something more relevant to
linked lists. If you ever use this code for anything, you'll want to

Yes, maybe, but it's not that important

Do not hide pointers behind typedefs. That's just begging for trouble.
Reading through your code, it's confusing the crap out of me because
you have a bunch of pointers without *'s to indicate their pointerhood.
At a glance, the symbol `*' is much easier to see than `Ptr'.

I did it just to bring some higher level abstraction to the code. I
come from Java and sometimes pointers are a mistery to me, when
variables pointing to objects in memory are not . Though i could
simply remove both the typedef, but what changes?

Good comment. May I recommend using 2 or 4-space tabs on Usenet, though? 8
spaces makes lines wrap and it's difficult to read.

Ok sorry, i'll adapt my codes before posting

So, (*root)->next == *root? This is a circular list, I see. Perhaps you
should have indicated that somewhere, because the code isn't exactly
self-documenting.

That is not Remember i'm not switching objects, i'm switching
pointers
Doing like this:

*------------* *-----------*
| newptr |----->| *root |----->(the rest of the list)
*------------* *-----------*

| |
\ /

*---------* *-------------*
| *root |----->| newptr |----->(the rest of the list)
*---------* *-------------*

This is very basic i think.

I'll stop here and let some compilers and pedants give you some more
detailed help; fix the typedef'd pointer and wide indentation, and I'll
happily read through the rest.

Ok ty