linked lists (searching/moving a link) 
Author Message
 linked lists (searching/moving a link)

Hello-

I am trying to write a program where I can enter data and search for it
using a key.  It is basically a lookup table.  I am having problems
however, with the searching function.  I want to write a search function
that when the correct record is found in the linked list, it is MOVED to
the front of the linked list and the associated pointers are adjusted
appropriately.  The program works except for the search function so any,
help, advice, guidance would be much appreciated....

Here is the code:
===================================

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

struct record
{
  int key;
  int info;
  struct record *next;

Quote:
};

typedef struct record REC;
typedef REC *pRECORD;

void enter (pRECORD *top, int key, int info);
pRECORD search (pRECORD *top, int key);
void print (pRECORD top);
int is_table_empty (pRECORD link);
int retrieve (pRECORD *link);

main()
{
  pRECORD table = NULL;

  int a=0;
  int k=0;
  int i=0;
  int q=0;
  int srch=0;
  int ctr,z;

  printf("How many records would you like to enter?\n");
  scanf("%d", &a);

  for (ctr=0;ctr<a;ctr++)
    {
      printf("Please enter the key for record number %d.\n", ctr);
      scanf("%d", &k);

      printf("Please enter the info for record number %d.\n", ctr);
      scanf("%d", &i);

      enter (&table, k, i);
      print (table);
    }

  printf("\nHow many searches would you like to do?\n");
  scanf("%d", &q);

  for (z=0; z<q; z++)
    {
      printf("Please enter search key: ");
      scanf("%d", &srch);

      table = search (&table, srch);

      if (table != NULL)
        printf("The number %d was found!\n", table->info);
      else
        printf("Sorry, your number is not in the table!\n");
    }

  printf("\nOriginal table:\n");
  print (table);

Quote:
}

void enter (pRECORD *top, int key, int info)
{
  pRECORD new;

  new = (pRECORD) malloc (sizeof(REC)); /* allocate mem for new link */

  if (!new)       /* if mem is not available then exit prg with error */
    {
      printf("Unable to allocate memory...Table is full!\n");
      exit (1);
    }

  new->info = info;
  new->key = key;
  new->next = *top;
  *top = new;

Quote:
}

void print (pRECORD top)
{
  if (is_table_empty(top) == 1)
    printf("Nothing to print...the table is empty!\n");
  else
    {
      while (is_table_empty(top) == 0)
          printf("Printing table...%d\n", retrieve(&top));
    }

Quote:
}

int retrieve (pRECORD *link)
{
  pRECORD first = *link;
  int val = 0;

  if (is_table_empty (first) == 0)
    {
      val = first->info;
      *link = first->next;
    }
  return (val);

Quote:
}

int is_table_empty (pRECORD link)
{
  int rv = 0;

  if (link == NULL)
    rv=1;

  return (rv);

Quote:
}

pRECORD search (pRECORD *top, int key)
{
  pRECORD tmp_orig = *top;
  pRECORD tmp = NULL;

  while (is_table_empty (*top) == 0)
    {
      if (key == (*top)->key)
        return (*top);
      else
        if (key == (*top)->next->key)
          {
            (*top)->next = (*top)->next->next;
            (*top)->next->next = tmp_orig;
            tmp = (*top)->next;
            return (tmp);
          }
        else
          (*top) = (*top)->next;
    }

  *top = tmp_orig;
  return (NULL);

Quote:
}

======================================================


Mon, 10 May 1999 03:00:00 GMT  
 linked lists (searching/moving a link)



Quote:
>Hello-

>I am trying to write a program where I can enter data and search for it
>using a key.  It is basically a lookup table.  I am having problems
>however, with the searching function.  I want to write a search function
>that when the correct record is found in the linked list, it is MOVED to
>the front of the linked list and the associated pointers are adjusted
>appropriately.  The program works except for the search function so any,
>help, advice, guidance would be much appreciated....

>Here is the code:
>===================================

I think you might have more success if you broke your code up into
much smaller functions so that the logic is much simpler, and you
could test the individual functions.

Anyway, here is code to delete a target object from a linked list.
Follwoing that I have provided the modification to move the deleted
object to the front of the list. I have included specifications and
diagrams, etc., as I think it is always a good idea to do so.

 +--------------------------------------------------------------------+
  Operation delete_target (list, target)
      result    : Deletes the the object containing target from the list.
      exceptions: if (the list is empty) return empty_failure
                : elsif (the list does not contain target)
                :    return target_failure
                : end exceptions
      note      : If the list contains several target objects only the
                :    first is deleted.

                                 +----------+
           +-+   +---+    +---+  |   +---+  |   +---+    +---+
           |*+-->|obj|    |obj|  |  target  |   |obj|    |obj|
           +-+   +---+    +---+  |   +---+  |   +---+    +---+
            L    | *-+--->| *-+--+..>| *-+..+-->| *-+--->| *-+->NULL
                 +---+    +---+      +---+      +---+    +---+

 +--------------------------------------------------------------------+
    typedef struct {
      int   key;
      char  name[10];
   } object;

   typedef struct node {
      object        the_object;
      struct node  *next;
   } list_node;

   typedef list_node *list;
 +--------------------------------------------------------------------+

    int delete_target  (list *L_ptr, int tkey) {
       list_node *ptr = *L_ptr;

       if (*L_ptr == NULL) return 0;
       else if (ptr->the_object.key == tkey)
          *L-ptr = ptr->next;
       else {  
          while (ptr->next != NULL && ptr->next->the_object.key != tkey)
             ptr = ptr->next;
          if (ptr->next == NULL) return 0;
          else ptr->next = ptr->next->next;
       }
       return 1;
    }

A direct modification of the above to move the target object to the
front of the list is: (the if statement needs cleaning up)
 +--------------------------------------------------------------------+
    int move_to_front (list *L_ptr, int tkey) {
       list_node *ptr = *L_ptr, *save;

       if (ptr == NULL) return 0;               /* the list is empty */
       else if (ptr->the_object.key == tkey)
          ;                           /* target already at the front */
       else {  
          while (ptr->next != NULL && ptr->next->the_object.key != tkey)
             ptr = ptr->next;
          if (ptr->next == NULL) return 0;
          else {
             save = ptr->next;
             ptr->next = save->next;
             save->next = *L_ptr;
             *L_ptr = ptr->next;
          }
       }
       return 1;
    }
 +--------------------------------------------------------------------+

And a diagram of what the above code does:

                                   +-----------+
    +-+    +-+      +---+    +---+ |    +---+  |   +---+    +---+
    |*|--->|*+--+..>|obj|    |obj| |    tkey   |   |obj|    |obj|
    +-+    +-+  |   +---+    +---+ |    +---+  |   +---+    +---+
   L_ptr    L   |   | *-+--->| *-+-+.+->| *-++.+-->| *-+--->| *-+->NULL
                |   +-^-+    +---+   |  +---+|     +---+    +---+
                |     +--------------+-------+
                +--------------------+



Tue, 11 May 1999 03:00:00 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. link list of a linked list (chained links?)

2. Incompatible NULL Assignments || Linked List inside Linked List

3. Clearing Memory || Linked List INSIDE of a Linked List

4. Freeing a Linked List inside of a Linked List

5. Linked List of Linked Lists

6. Define a linked list of a linked list

7. Link List to Link List, HELP friends

8. Moving Backwards through Link List

9. how do you move data in a linked list

10. Moving around in linked list?

11. Linked List Sort/Search/delete code ??Help????

12. Search algorithm for linked list.

 

 
Powered by phpBB® Forum Software