Re: HELP, INFINIT LOOP... simple LINKED LIST
From: Richard Heathfield (dontmail_at_address.co.uk.invalid)
Date: 10/23/03
- Next message: Alan: "[C] how to search a string ?"
- Previous message: Artie Gold: "Re: HELP, INFINIT LOOP... simple LINKED LIST"
- In reply to: na1paj: "HELP, INFINIT LOOP... simple LINKED LIST"
- Next in thread: T.M. Sommers: "Re: HELP, INFINIT LOOP... simple LINKED LIST"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Thu, 23 Oct 2003 03:40:24 +0000 (UTC)
na1paj wrote:
> here's a simple linked list program.
It's not as simple as you think.
> the DeleteNode function is
> producing an infinit loop i think, but i can't figure out where..
>
>
> #include <stdio.h>
> typedef struct
> {
> char *str; //str is a dynamic array of characters
If you have a C99 compiler, okay, fine. Do you? If not, // is a syntax
error.
> int length; //number of characters
Were you planning on having a negative number of characters for any reason?
In fact, your code seems not to use the length field at all.
> } String;
>
> typedef struct node
> {
> String Data;
> struct node* Link;
> } ListNode;
>
> typedef struct listStuct
> {
> ListNode *Head;
> }List;
>
> void AddNode(List *L, String item)
> {
> ListNode *currNode, *newNode;
> currNode = L->Head;
> if (L->Head == NULL)
> {
> L->Head = (ListNode*)malloc(sizeof(ListNode));
Undefined behaviour. Your compiler would have warned you about it, too, if
only you hadn't put in that stupid cast.
Rewrite this as:
L->Head = malloc(sizeof *L->Head);
In general, if p is a pointer to some object type, then:
p = malloc(sizeof *p);
Don't forget to #include <stdlib.h> for the malloc prototype (the absence of
which is what gives you undefined behaviour in the above code).
> L->Head->Data = item;
You forgot to check malloc's return value, which could easily have been NULL
(meaning "couldn't allocate the requested memory"). If it was, then
dereferencing that pointer (as you do here) invokes undefined behaviour.
> L->Head->Link = NULL;
> }
> else
> {
> while(currNode->Link != NULL)
> currNode = currNode->Link; //go to the last
> newNode = (ListNode*)malloc(sizeof(ListNode));
newNode = malloc(sizeof *newNode);
Don't forget to check for NULL.
> newNode->Data = item;
> newNode->Link = NULL;
> currNode->Link = newNode;
> }
> }
>
> void DeleteNode(List *L, String item)
> {
> ListNode *currNode, *prevNode;
> currNode = L->Head;
> prevNode = L->Head;
> if (L->Head == NULL)
> {
> printf("empty list");
> }
> while(currNode != NULL) //check if first
> {
> if(strcmp(currNode->Data.str,item.str)==0) //found
> {
> if(currNode == L->Head) //first one
> {
> L->Head == currNode->Link;
> currNode->Link = NULL;
> free(currNode);
> printf("Remove First");
> }
> else
> {
> prevNode->Link = currNode->Link;
> currNode->Link = NULL;
> free(currNode);
> printf("removed ");
> }
> }
> else
> {
> prevNode = currNode;
> currNode = currNode->Link; //go to next one
> }
> }
> }
I had a quick look at this, but the complete absence of indentation made the
code very hard to follow, so I gave up.
>
>
> int main()
> {
> FILE *fp = NULL;
> List list;
> String string;
> int i;
> int records = 0;
> char filename[100];
> //list.Head = (ListNode*)malloc(sizeof(ListNode));
> list.Head = NULL;
> string.str = (char *)malloc(sizeof(char) *20);
string.str = malloc(20 * sizeof *string.str);
Note: 20 may not be enough. If not, you risk a buffer overrun attack.
Test for NULL.
> printf("Enter filename\n");
> scanf("%s", filename);
Danger of buffer overrun attack by careless or malicious user.
> fp = fopen(filename, "r");
>
> if (fp == NULL)
> { printf ("Error\n");
> exit(0);
0 indicates success. On error, I suggest using EXIT_FAILURE (which is
another good reason to #include <stdlib.h>).
> }
> else
> {
> fscanf(fp, "%d", &records);
> for (i = 0; i<records; i++)
> {
> fscanf(fp, "%s", string.str);
Buffer overrun may occur.
> AddNode(&list, string);
> printf("%s ", string.str);
> }
> printf("\n\nEnter a Node to delete: ");
Either print a newline here or fflush(stdout);
> scanf("%s", string.str);
Buffer overrun may occur.
> DeleteNode(&list, string);
> }
> return 1;
return EXIT_SUCCESS or return 0 would be a much better idea. Google the
archives for an explanation.
> }
-- Richard Heathfield : binary@eton.powernet.co.uk "Usenet is a strange place." - Dennis M Ritchie, 29 July 1999. C FAQ: http://www.eskimo.com/~scs/C-faq/top.html K&R answers, C books, etc: http://users.powernet.co.uk/eton
- Next message: Alan: "[C] how to search a string ?"
- Previous message: Artie Gold: "Re: HELP, INFINIT LOOP... simple LINKED LIST"
- In reply to: na1paj: "HELP, INFINIT LOOP... simple LINKED LIST"
- Next in thread: T.M. Sommers: "Re: HELP, INFINIT LOOP... simple LINKED LIST"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
