Double Linked List test

[Little]

I have this program and I need to work on the test portion, which tests
if a Val is in the list. It returns false no matter what could you look
at the part and see what might need to be done to fix it. It reads in
the file and sorts out the files into the four different lists.

F.txt
int main
2
" "
help

boolean test(struct Obj *l, char *value_wanted)
{
int n=0;
struct Obj *current=l->n_link;
char *currentval=Values[n].value;
while(currentval != value_wanted)
{
if(current->n_link==NULL)
return(false);
else
{
n=n+1;
current=current->n_link;
currentval=Values[n].value;
}
}
return(true);
}

#include <stdio.h>
#include <stdlib.h>
#include "scan.h"
#define true 1
#define false 0

struct Val
{
char type;
int length;
char value[256];
} Values[1000];

struct Obj
{
struct Obj *p_link;
struct Val *p_value;
struct Obj *n_link;
} Objects[1000], *IdList, *NrList, *SpList, *UnList ;

int i = 0, j = 0; /* 0 <= i,j <= 999, objects and vcalues indices */
int Id=0, Nr=0, Sp=0, Un=0;
typedef int boolean;

struct Obj *List (struct Obj *h, struct Obj *t)
{
h->p_link = NULL;
h->n_link = t;
h->p_value = NULL;
t->p_link = h;
t->n_link = NULL;
t->p_value = NULL;
return h;
}

boolean empty(struct Obj *l)
{
return (l->n_link->n_link==NULL);
}

int Append(struct Obj *L, struct Val *item)
{
struct Obj *Temp = L->n_link;
while (Temp->n_link != NULL)
Temp = Temp->n_link;
if ((i <= 999))
{
(Temp->p_link)->n_link = &Objects[i];
Objects[i].n_link = Temp;
Objects[i].p_link = Temp->p_link;
Temp->p_link = &Objects[i];
Objects[i].p_value = &Values[j];
i = i+1;
return 1;
}
else return 0;
}

int length(struct Obj *l)
{
int len=0;
struct Obj *q=l;
while(q != NULL)
{
len=len+1;
q=q->n_link;
}
return(len);
}

boolean test(struct Obj *l, char *value_wanted)
{
int n=0;
struct Obj *current=l->n_link;
char *currentval=Values[n].value;
while(currentval != value_wanted)
{
if(current->n_link==NULL)
return(false);
else
{
n=n+1;
current=current->n_link;
currentval=Values[n].value;
}
}
return(true);
}

boolean update(struct Obj *l, char *value_wanted, int place)
{
boolean b;
b=test(l, value_wanted);
if(!b)
return(false);
else
{
Objects[place].p_value = &Values[j];
return(true);
}
}

struct Obj *access_i(struct Obj *l, int num_wanted)
{
struct Obj *current=l;
int j=0;
while (j != num_wanted)
if(current->n_link==NULL)
return(NULL);
else
{
current=current->n_link;
j=j+1;
}
if(current->n_link==NULL)
return(NULL);
else
return(current);
}

struct Obj *access_v(struct Obj *l, char *value_wanted)
{
int n=0;
struct Obj *current=l->n_link;
char *currentval=Values[n].value;
while(currentval != value_wanted)
{
if(current->n_link==NULL)
return(NULL);
else
{
n=n+1;
current=current->n_link;
currentval=Values[n].value;
}
if(current->n_link==NULL)
return(NULL);
else
return(current);
}
}

struct Obj *getPosition(struct Obj *position, int positionWanted)
{
int atPosition=0;
struct Obj *current=position;
while(atPosition != positionWanted)
{
atPosition++;
if(current->n_link==NULL) return NULL;
current=current->n_link;
}
return current;
}

struct Obj *insert(struct Obj *l, int pos)
{
struct Obj *newPosition=NULL, *beforePosition, *afterPosition;
if(pos<0)
return l;
else if(pos == 0)
{
newPosition->n_link=l;
Objects[pos].p_value=&Values[j];
i=i+1;
return l;
}
else
{
beforePosition=getPosition(l,pos-1);
afterPosition=getPosition(l,pos);
beforePosition->n_link=newPosition;
newPosition->n_link=afterPosition;
Objects[pos].p_value=&Values[j];
i=i+1;
return l;
}
}

struct Obj *deletes(struct Obj *l, int pos)
{
struct Obj *current, *beforePosition, *afterPosition;
if(pos<0)
return l;
else if(pos==0)
{
afterPosition=getPosition(l,pos+1);
free(current);
Objects[pos].p_value=&Values[j];
i=i-1;
return afterPosition;
}
else
{
beforePosition=getPosition(l,pos-1);
afterPosition=getPosition(l,pos+1);
beforePosition->n_link=afterPosition;
current->n_link=NULL;
free(current);
Objects[pos].p_value=&Values[j];
i=i-1;
return l;
}
}

int PrintLists(struct Obj *list)
{
struct Obj *Temp = list->n_link;
printf("Type\tLength\tValue\n");
while (Temp->n_link != NULL)
{
printf("%c\t%d\t%s\n", Temp->p_value->type,
Temp->p_value->length, Temp->p_value->value);
Temp = Temp->n_link;
}
}

int main (int argc, char *argv[])
{
extern TKN get_token(FILE *);
TKN Token;
FILE *Input;
int Done = 0;
IdList = List(&Objects[0], &Objects[1]);
NrList = List(&Objects[2], &Objects[3]);
SpList = List(&Objects[4], &Objects[5]);
UnList = List(&Objects[6], &Objects[7]);
i = 8; j = 0;
Input = fopen(argv[1], "r");
while (!Done)
{
Token = get_token( Input );
switch (Token.Code)
{
case 'I':
{
/* process identifier */
printf("Symbol: Identifier %s\n",
Token.String);
if (j < 999)
{
j = j+1;
Values[j].type = 'I';
Values[j].length = strlen(Token.String);
strcpy(Values[j].value, Token.String);
Append (IdList, &Values[j]);
Id++;
}
else
printf("No plave available for this
value\n");
break;
}
case 'N':
{
/* process integer number */
printf("Symbol: Integer number %s\n",
Token.String);
if (j < 999)
{
j = j+1;
Values[j].type = 'N';
Values[j].length = strlen(Token.String);
strcpy(Values[j].value, Token.String);
Append (NrList, &Values[j]);
Nr++;
}
else
printf("No plave available for this
value\n");
break;
}
case 'F':
{
/* process real number */
printf("Symbol: Real number %s\n",
Token.String);
if (j < 999)
{
j = j+1;
Values[j].type = 'F';
Values[j].length = strlen(Token.String);
strcpy(Values[j].value, Token.String);
Append (NrList, &Values[j]);
Nr++;
}
else
printf("No plave available for this
value\n");
break;
}
case 'W':
{
printf("White symbol received\n");
break;
}
case 'U':
{
if (Token.String[0] == 'Z')
Done = 1;
else
printf("Unprintable character
discovered\n");
break;
}
case 'O':
{
printf("Symbol: Separator %s\n",
Token.String);
if (j < 999)
{
j = j+1;
Values[j].type = 'S';
Values[j].length = strlen(Token.String);
strcpy(Values[j].value, Token.String);
Append (SpList, &Values[j]);
Sp++;
}
else
printf("No plave available for this
value\n");
break;
}
case 'E':
{
printf("Error condition: %s\n",
Token.String);
if (j < 999)
{
j = j+1;
Values[j].type = 'E';
Values[j].length = strlen(Token.String);
strcpy(Values[j].value, Token.String);
Append (UnList, &Values[j]);
Un++;
}
else
printf("No plave available for this
value\n");
break;
}
}
} /* end while */
printf("List of NAMES\n");
PrintLists(IdList);
printf("List of NUMBERS\n");
PrintLists(NrList);
printf("List of SEPARATORS\n");
PrintLists(SpList);
printf("List of UNKNOWNS\n");
PrintLists(UnList);

printf("Length of Names: %d\n", Id);
printf("Length of Numbers: %d\n", Nr);
printf("Length of Separators: %d\n", Sp);
printf("Length of Unknowns: %d\n", Un);

printf("is Names empty: %d\n", empty(IdList));
printf("is Numbers empty: %d\n", empty(NrList));
printf("is Separators empty: %d\n", empty(SpList));
printf("is Uknowns empty: %d\n", empty(UnList));

char *testvalue="int";
printf("does int exist in Names: %d\n", test(IdList,testvalue));
}

[Keith Thompson]

"Little" <co************@yahoo.com> writes:

I have this program and I need to work on the test portion, which tests
if a Val is in the list. It returns false no matter what could you look
at the part and see what might need to be done to fix it. It reads in
the file and sorts out the files into the four different lists.

[snip]

I doubt that you have *this* program. You may have something similar
to what you posted.

I saved a copy of your article, deleted the extra copy of the "test"
function, and tried compiling it. I got a number of compilation
errors.

For example, at the beginning of main(), you have:

extern TKN get_token(FILE *);
TKN Token;

The identifier TKN appears nowhere else in what you posted, and
there's no definition of a function called get_token.

If you want help, create a small, complete, compilable program that
illustrates the problem. "Small" means you should delete anything
that's no directly relevant to the problem you're having. "Complete"
means that it shouldn't depend on any external declarations that you
don't provide. "Compilable" means that we should be able to grab a
copy from your posting and try it ourselves. Ideally, you should also
be able to compile it without warnings, even after you've enabled all
possible warnings in your compiler.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Rod Pemberton]

"Little" <co************@yahoo.com> wrote in message
news:11*********************@o13g2000cwo.googlegro ups.com...

I have this program and I need to work on the test portion, which tests
if a Val is in the list. It returns false no matter what could you look
at the part and see what might need to be done to fix it. It reads in
the file and sorts out the files into the four different lists.

F.txt
int main
2
" "
help

Since I just got done reformatting your program with indentations (and
haven't gotten to compiling it yet). I noticed something that appears to be
an error due to your formatting or lack of. access_i() and access_v() both
have while() loops. access_v() has braces for the while() around two if's.
However, access_i() doesn't have braces for the while() so only the first if
is part of the while(). Is this what you intended?

struct Obj *access_i(struct Obj *l, int num_wanted)
{
struct Obj *current=l;
int j=0;
while (j != num_wanted)
if(current->n_link==NULL)
return(NULL);
else
{
current=current->n_link;
j=j+1;
}
if(current->n_link==NULL)
return(NULL);
else
return(current);
}

struct Obj *access_v(struct Obj *l, char *value_wanted)
{
int n=0;
struct Obj *current=l->n_link;
char *currentval=Values[n].value;
while(currentval != value_wanted)
{
if(current->n_link==NULL)
return(NULL);
else
{
n=n+1;
current=current->n_link;
currentval=Values[n].value;
}
if(current->n_link==NULL)
return(NULL);
else
return(current);
}
}

Rod Pemberton

[Flash Gordon]

Little wrote:

I have this program and I need to work on the test portion, which tests
if a Val is in the list. It returns false no matter what could you look
at the part and see what might need to be done to fix it. It reads in
the file and sorts out the files into the four different lists.
First of all, thank you for posting a decent description of the problem.
However, the code you have posted is *not* complete because you have not
included scan.h which presumably defines TKN. Without that we can be of
less help.
F.txt
int main
2
" "
help

boolean test(struct Obj *l, char *value_wanted)
{
int n=0;
struct Obj *current=l->n_link;
char *currentval=Values[n].value;
while(currentval != value_wanted)
Strings are not 1st class citizens in C. What you are doing above is
*not* comparing the strings, it is comparing the pointers to see if they
point to the same place. Consider that if you point one of your fingers
at the first instance of the word "the" in this paragraph and another
finger at the second instance of the word "the" and then look at your
two fingers you will see that although they both point at the word "the"
they point to different places and so have different values.

Look up strcmp.
{
if(current->n_link==NULL)
return(false);
else
{
n=n+1;
current=current->n_link;
currentval=Values[n].value;
}
}
return(true);
}

#include <stdio.h>
#include <stdlib.h>
#include "scan.h"
#define true 1
#define false 0
The above is bad for at least two reasons. In C *any* non-zero value is
considered true, so comparing a variable against your "true" macro will
sometimes produce a different result to simply using the variable as a
boolean. Also, it is normal convention to use upper case names for macros.
struct Val
{
char type;
int length;
char value[256];
} Values[1000];

struct Obj
{
struct Obj *p_link;
struct Val *p_value;
struct Obj *n_link;
} Objects[1000], *IdList, *NrList, *SpList, *UnList ;
Yuk. That's twice I've seen the magic number 1000 and I'll bet it occurs
further down. Declaring a macro NUM_ELEMENTS or something would have
been far more useful than your true/false macros.
int i = 0, j = 0; /* 0 <= i,j <= 999, objects and vcalues indices */
int Id=0, Nr=0, Sp=0, Un=0;
Why are these variable globals rather than locals? If you really do need
globals that for gods sake give them useful names.
typedef int boolean;

struct Obj *List (struct Obj *h, struct Obj *t)
Not, in my opinion, a very good name for this function.
{
h->p_link = NULL;
h->n_link = t;
h->p_value = NULL;
t->p_link = h;
t->n_link = NULL;
t->p_value = NULL;
return h;
}

boolean empty(struct Obj *l)
{
return (l->n_link->n_link==NULL);
}

int Append(struct Obj *L, struct Val *item)
{
struct Obj *Temp = L->n_link;
while (Temp->n_link != NULL)
Temp = Temp->n_link;
if ((i <= 999))
I thought I would see that 1000 appearing again! What if you change the
maximum number of elements? Will you get all the places it needs changing?
{
(Temp->p_link)->n_link = &Objects[i];
Objects[i].n_link = Temp;
Objects[i].p_link = Temp->p_link;
Temp->p_link = &Objects[i];
Objects[i].p_value = &Values[j];
i = i+1;
Why not use the increment operator? i++ (or ++i) is a far more natural
way to write it in C and people don't have to check to see that neither
i is a j.
return 1;
}
else return 0;
}

int length(struct Obj *l)
{
int len=0;
struct Obj *q=l;
while(q != NULL)
{
len=len+1;
Again, use the increment operator. I might even use a for loop rather
than a while loop.
q=q->n_link;
}
return(len);
}

boolean test(struct Obj *l, char *value_wanted)
{
int n=0;
struct Obj *current=l->n_link;
char *currentval=Values[n].value;
while(currentval != value_wanted)
See earlier comment.
{
if(current->n_link==NULL)
return(false);
else
{
n=n+1; n++ current=current->n_link;
currentval=Values[n].value;
}
}
return(true);
}

boolean update(struct Obj *l, char *value_wanted, int place)
{
boolean b;
b=test(l, value_wanted);
if(!b)
return(false);
else
{
Objects[place].p_value = &Values[j];
Your use of globals is making this code horrible to read. I have no idea
what j is or how it changes.
return(true);
}
}

struct Obj *access_i(struct Obj *l, int num_wanted)
{
struct Obj *current=l;
int j=0;
Now we have a local variable j hiding the global variable j. Had I not
noticed this I would assume this function was modifying the global.
Absolutely horrible.
while (j != num_wanted)
if(current->n_link==NULL)
return(NULL);
else
{
current=current->n_link;
j=j+1;
}
if(current->n_link==NULL)
return(NULL);
else
return(current);
}

struct Obj *access_v(struct Obj *l, char *value_wanted)
{
int n=0;
struct Obj *current=l->n_link;
char *currentval=Values[n].value;
while(currentval != value_wanted)
Same mistake as your test function.
{
if(current->n_link==NULL)
return(NULL);
else
{
n=n+1;
current=current->n_link;
currentval=Values[n].value;
}
if(current->n_link==NULL)
return(NULL);
else
return(current);
}
}

struct Obj *getPosition(struct Obj *position, int positionWanted)
{
int atPosition=0;
struct Obj *current=position;
while(atPosition != positionWanted)
{
atPosition++;
if(current->n_link==NULL) return NULL;
current=current->n_link;
}
return current;
}

struct Obj *insert(struct Obj *l, int pos)
{
struct Obj *newPosition=NULL, *beforePosition, *afterPosition;
if(pos<0)
return l;
else if(pos == 0)
{
newPosition->n_link=l;
Objects[pos].p_value=&Values[j];
i=i+1;
return l;
}
else
{
beforePosition=getPosition(l,pos-1);
afterPosition=getPosition(l,pos);
beforePosition->n_link=newPosition;
newPosition->n_link=afterPosition;
Objects[pos].p_value=&Values[j];
i=i+1;
return l;
}
}

struct Obj *deletes(struct Obj *l, int pos)
{
struct Obj *current, *beforePosition, *afterPosition;
if(pos<0)
return l;
else if(pos==0)
{
afterPosition=getPosition(l,pos+1);
free(current);
Objects[pos].p_value=&Values[j];
i=i-1;
return afterPosition;
}
else
{
beforePosition=getPosition(l,pos-1);
afterPosition=getPosition(l,pos+1);
beforePosition->n_link=afterPosition;
current->n_link=NULL;
free(current);
Objects[pos].p_value=&Values[j];
i=i-1;
return l;
}
}

int PrintLists(struct Obj *list)
{
struct Obj *Temp = list->n_link;
printf("Type\tLength\tValue\n");
while (Temp->n_link != NULL)
{
printf("%c\t%d\t%s\n", Temp->p_value->type,
Temp->p_value->length, Temp->p_value->value);
Temp = Temp->n_link;
}
}

int main (int argc, char *argv[])
{
extern TKN get_token(FILE *);
Don't declare functions inside other functions, especially if they are
defined in another file. In this instance the above should presumable be
in scan.h since I assume it is defined in scan.c
TKN Token;
FILE *Input;
int Done = 0;
IdList = List(&Objects[0], &Objects[1]);
NrList = List(&Objects[2], &Objects[3]);
SpList = List(&Objects[4], &Objects[5]);
UnList = List(&Objects[6], &Objects[7]);
i = 8; j = 0;
Input = fopen(argv[1], "r");
What if the user does not give you any parameters? Always check first.
while (!Done)
{
Token = get_token( Input );
switch (Token.Code)
{
case 'I':
{
/* process identifier */
printf("Symbol: Identifier %s\n",
Token.String);
if (j < 999)
{
j = j+1;
Values[j].type = 'I';
Values[j].length = strlen(Token.String);
strcpy(Values[j].value, Token.String);
Check the string isn't too long before copying it, otherwise you have a
buffer overflow waiting to happen.
Append (IdList, &Values[j]);
Id++;
}
else
printf("No plave available for this
value\n");
break;
}
case 'N':
{
/* process integer number */
printf("Symbol: Integer number %s\n",
Token.String);
if (j < 999)
{
j = j+1;
Values[j].type = 'N';
Values[j].length = strlen(Token.String);
strcpy(Values[j].value, Token.String);
Append (NrList, &Values[j]);
Nr++;
}
else
printf("No plave available for this
value\n");
break;
}
This looks remarkably similar to the last case. Duplicating identical
code (or almost identical) is generally a bad thing. Any errors then
have to be corrected in lots of places.
case 'F':
{
/* process real number */
printf("Symbol: Real number %s\n",
Token.String);
if (j < 999)
{
j = j+1;
Values[j].type = 'F';
Values[j].length = strlen(Token.String);
strcpy(Values[j].value, Token.String);
Append (NrList, &Values[j]);
Nr++;
}
else
printf("No plave available for this
value\n");
break;
Again with the repetition of code.
}
case 'W':
{
printf("White symbol received\n");
break;
}
case 'U':
{
if (Token.String[0] == 'Z')
Done = 1;
else
printf("Unprintable character
discovered\n");
break;
}
case 'O':
{
printf("Symbol: Separator %s\n",
Token.String);
if (j < 999)
{
j = j+1;
Values[j].type = 'S';
Values[j].length = strlen(Token.String);
strcpy(Values[j].value, Token.String);
Append (SpList, &Values[j]);
Sp++;
}
else
printf("No plave available for this
value\n");
break;
}
and again. Lots of places to add in the error checking you missed now,
aren't there.
case 'E':
{
printf("Error condition: %s\n",
Token.String);
if (j < 999)
{
j = j+1;
Values[j].type = 'E';
Values[j].length = strlen(Token.String);
strcpy(Values[j].value, Token.String);
Append (UnList, &Values[j]);
Un++;
}
else
printf("No plave available for this
value\n");
break;
}
and again the same code.
}
} /* end while */
printf("List of NAMES\n");
PrintLists(IdList);
printf("List of NUMBERS\n");
PrintLists(NrList);
printf("List of SEPARATORS\n");
PrintLists(SpList);
printf("List of UNKNOWNS\n");
PrintLists(UnList);

printf("Length of Names: %d\n", Id);
printf("Length of Numbers: %d\n", Nr);
printf("Length of Separators: %d\n", Sp);
printf("Length of Unknowns: %d\n", Un);

printf("is Names empty: %d\n", empty(IdList));
printf("is Numbers empty: %d\n", empty(NrList));
printf("is Separators empty: %d\n", empty(SpList));
printf("is Uknowns empty: %d\n", empty(UnList));

char *testvalue="int";
In C89 (the most commonly implemented standard) you can't mix
definitions and executable statements.
printf("does int exist in Names: %d\n", test(IdList,testvalue));
}

Next time please provide a complete example including any required
headers. How knows how many more problems might had been spotted if I
could actually compile and test the program.
--
Flash Gordon
Living in interesting times.
Web site - http://home.flash-gordon.me.uk/
comp.lang.c posting guidlines and intro -
http://clc-wiki.net/wiki/Intro_to_clc

[Rod Pemberton]

"Rod Pemberton" <do*********@sorry.bitbucket.cmm> wrote in message
news:43********@news.bea.com...

"Little" <co************@yahoo.com> wrote in message
news:11*********************@o13g2000cwo.googlegro ups.com...

I have this program and I need to work on the test portion, which tests
if a Val is in the list. It returns false no matter what could you look
at the part and see what might need to be done to fix it. It reads in
the file and sorts out the files into the four different lists.

F.txt
int main
2
" "
help

Since I just got done reformatting your program with indentations (and
haven't gotten to compiling it yet). I noticed something that appears to

be an error due to your formatting or lack of. access_i() and access_v() both have while() loops. access_v() has braces for the while() around two if's. However, access_i() doesn't have braces for the while() so only the first if is part of the while(). Is this what you intended?

Oh boy, where to start? The words "Oh my god! They killed Kenny!" popped
into my head while trying desperately to get this to compile. It's not my
job to correct all those errors. I'm not saying this to insult you
(honestly), but it reminded me of feeding Pascal source into a C compiler
(i.e., real problems). I don't know _what_ happened to the code you posted
between you and the newsgroup. But, you need to take what ended up being
_posted_ and get most of it to compile.
Rod Pemberton

[Ben Bacarisse]

On Sun, 12 Feb 2006 16:33:37 -0800, Little wrote:

I have this program... <big snip> struct Obj *access_i(struct Obj *l, int num_wanted)
{
struct Obj *current=l;
int j=0;
while (j != num_wanted)
if(current->n_link==NULL)
return(NULL);
else
{
current=current->n_link;
j=j+1;
}
if(current->n_link==NULL)
return(NULL);
else
return(current);
}

On 2 Feb someone called duncanblacksmith posted similar odd linked link
access logic. Are you he? If not, you should not have borrowed his code
since it is seriously flawed. If you are he, there were useful comments
made then that do not seem to have been taken up. Mine were, I can see
now, rather too general but they were applicabale and I would have
calarified them if you'd asked.

--
Ben.