Double Linked List test

L

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;
Objects.n_link = Temp;
Objects.p_link = Temp->p_link;
Temp->p_link = &Objects;
Objects.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));
}
 
K

Keith Thompson

Little said:
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.
Click to expand...

[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.
 
F

Flash Gordon

Little said:
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.
Click to expand...

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)
Click to expand...

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
Click to expand...

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 ;
Click to expand...

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;
Click to expand...

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)
Click to expand...

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))
Click to expand...

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;
Objects.n_link = Temp;
Objects.p_link = Temp->p_link;
Temp->p_link = &Objects;
Objects.p_value = &Values[j];
i = i+1;
Click to expand...


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;
Click to expand...

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)
Click to expand...

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];
Click to expand...

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;
Click to expand...

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)
Click to expand...

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 *);
Click to expand...

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");
Click to expand...

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);
Click to expand...

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;
}
Click to expand...

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;
Click to expand...

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;
}
Click to expand...

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;
}
Click to expand...

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";
Click to expand...

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));
}
Click to expand...

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
 
R

Rod Pemberton

Little said:
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
Click to expand...

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
 
R

Rod Pemberton

Rod Pemberton said:
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?
Click to expand...

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
 
B

Ben Bacarisse

I have this program...
Click to expand...
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);
}
Click to expand...

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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Program Assistance 4
Program Help 2
Fibonacci 0
Multiple Double Linked Lists 1
Beginner at c 0
Adding adressing of IPv6 to program 1
Double Linked List Code 1
Need help in debugging tic tac toe (Beginner) 0

Members online

No members online now.
Total: 19 (members: 0, guests: 19)
Robots: 379

Forum statistics

Threads
473,769
Messages
2,569,582
Members
45,065
Latest member
OrderGreenAcreCBD

Latest Threads

Top