Expert: Zlatko - 10/2/2009

Question
QUESTION: Write an ANSI C program to implement a doubly-linked self organising list.A self-organising list is similiar o a regular list, except that all inertions are performed at the front and when an element is accessed by find( ),it is moved to he front of the list without changing the order of the other items. Thus the elts are ordered according to acess time,with the most recently accessed elt at the front of the list and the least recently accessed elt at the end of the list. ur prog should also count how many times each number is accesed.

REQUIRED DATA SRUCTURE
Doubly linkd listwith a header. Nodes on the list should have a field for a number(integer)and a field to count how many times tha number was accesed.

REQUIRED ALGORITHMS
These are the following conditions
creating an empty list
searchin the list for a number
insertin a new node at the front of the list
deletin a node 4m the list
insertin an existin node at the front of the list
printin the list after final access
deletin the list when its no longer needed

REQUIRED INPUT
Ur prog should have the appropriate I/O statement(s) to read 4m the file selforg.dat

REQUIRED OUTPUT
Ur prog should contain appropriate I/O statements to write to an output file. The name of this output file (selforg.run)should be supplied as a command line arguement. A minimally accetable output is attached.

REQUIRED FILES

idbox
selforg.h(header file)
main.c(driver function)
io.c(I/O releted functions)
list.c(functions 4 the list operations)
makefile
selforg.run(output file)

REQUIRED ASSUMPTION

no number is accessed more than 99 times.


CAN U HELP ME....!!

ANSWER: Yes, I can help you but you have not told me what you are having trouble with. I understand your assignment. You need a doubly linked list. That means each node in the list will point to the node before it and the node after it. From your assignment description you need a structure like this.

typedef struct listNode
{
   int number; /* the data of the list */
   int accessCount; /* the number of times the data is accessed */
   struct ListNode* prev; /* the previous node of the list */
   struct ListNode* next; /* the next node on the list */
} ListNode;
ListNode* root = NULL;

I have added the typedef for convenience.
Notice that I've also created a pointer for the root of the list.

These list elements are allocated from the heap. That means you use malloc. The allocation should be done in a separate function. The allocation looks like this.

ListNode* newListNode(int number) /* data is the number that the node is to store */
{
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->number = number;
    newNode->accessCount = 0;
    newNode->prev = NULL;
    newNode->next = NULL;

    return newNode;
}


You will need to #include <stdlib.h> in order to get this to compile.


Now, you should do each of your algorithms separately, starting with what you think is the easiest. The most natural would be to insert a node at the start of the list. The second thing you should do is create a function to print out the list so that you can check the result of each operation. This will help you in testing and fixing your program.

The prototype of the function to insert should look something like this.

void ListInsertAtFront(ListNode* node)
{

}

You can name it anything you like. There are more professional ways of doing it, but I don't know your level of experience.

Do not worry about the I/O functions yet. You should do those later, after you are sure the rest of your list algorithms are working correctly.

From the main function, a new node can be created like this

int main(void)
{
   ListNode* newNode = newListNode(12345);
   ListInsertAtFront(newNode);
   return 0;
}

Now, think about how to insert the element at the start of the list. There are 2 cases; 1) the list is empty, 2) the list is not empty. Draw out on a piece of paper the root pointer, and the new node with its pointers. What has to be done, and in what order, to get the new node on to the list for each case.

For an example of what I mean by a drawing, look at the attached screen shot. It is for a different problem, sorting a singly linked list, but you will get the idea of what I mean by a drawing. You make the drawing, write out the steps, then write the code.

---------- FOLLOW-UP ----------

QUESTION: Am sorry that i didn't mentioned where my doubt is..In my question one part is to count and print how many times each number is accesed.. I need your help to write code for that..

"" REQUIRED DATA STRUCTURE
Doubly linked list with a header. Nodes on the list should have a field for a number(integer)and a field to count how many times the number was accessed. ""

I think now you got what exactly my doubt is..!!
SIR Am expecting your help as early as possible...
THANK YOU...

Answer
Hello Athira.

According to the problem, the node count is incremented whenever a node is found using the search function. When you find the node, you will have a pointer to the node. To increment the node count you would say node->count++; In the search function you would also re-use your functions to remove the node from the list, and to insert the node at the front of the list. So it would make sense to write the insertion function first, and test it. Then write the search function to determine if you can find the node, and then write the removal function.

Below you will find my version of the program with these three functions as well as some test code. I believe my program is correct. Don't read it all at once. Try to create an insertion function, and a print function. Then if you get stuck, look at my List_InsertAtFront and my List_Print functions.

Many years ago, my professor said that if you look at an answer, it will be obvious to you and you will think that you could have developed it yourself but you will be fooling yourself. You need to struggle through the problem to really learn to think about programs.

Good luck in your exams.

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

typedef struct listNode
{
   int number; /* the data of the list */
   int accessCount; /* the number of times the data is accessed */
   struct listNode* prev; /* the previous node of the list */
   struct listNode* next; /* the next node on the list */
} ListNode;
ListNode* root = NULL;

ListNode* newListNode(int number) /* data is the number that the node is to store */
{
   ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
   newNode->number = number;
   newNode->accessCount = 0;
   newNode->prev = NULL;
   newNode->next = NULL;

   return newNode;
}

void List_IntegrityCheck(ListNode* pNode)
{
   if (pNode == NULL)
   {
       printf("Error in IntegrityCheck\n");
       return;
   }

   /* Some integrity checking */
   if (pNode->next != NULL)
   {
       if (pNode->next->prev != pNode)
       {
         printf("Type 1 error in the linking\n");
       }
       if (pNode->prev != NULL)
       {
         if (pNode->next->prev->prev->next != pNode)
         {
         printf("Type 2 error in the linking\n");
         }
       }
   }
   if (pNode->prev != NULL)
   {
       if (pNode->prev->next != pNode)
       {
         printf("Type 3 error in the linking\n");
       }
       if (pNode->next != NULL)
       {
         if (pNode->prev->next->next->prev != pNode)
         {
         printf("Type 4 error in the linking\n");
         }
       }
   }
}

void List_Print(void)
{
   ListNode* pNode = root;

   printf("------------------------------------------------\n");
   while(pNode != NULL)
   {
       printf("Node number %d access count %d\n", pNode->number, pNode->accessCount);
       List_IntegrityCheck(pNode);
       /* advance the node */
       pNode = pNode->next;
   }
}

void List_InsertAtFront(ListNode* newNode)
{
   if (newNode == NULL)
   {
       printf("Error in insert\n");
       return;
   }

   /* NULL the next and prev as a precaution */
   newNode->next = NULL;
   newNode->prev = NULL;

   /*
   There are 2 cases,
   case 1: the list is empty,
   case 2: the list is not empty

   The code below can be made shorter.
   */
   if (root == NULL)
   {
       /* case 1 */
       root = newNode;
   }
   else
   {
       /* case 2 */

       /* step 1: connect newNode to first node */
       newNode->next = root;
       /* step 2: connect first node back to newNode
       The root pointer still points to the old first node */
       root->prev = newNode;
       /* step 3: make root point to the new node */
       root = newNode;
   }
}

void List_RemoveNode(ListNode* toRemove)
{
   if (toRemove == NULL)
   {
       printf("Error in RemoveNode\n");
       return;
   }
   /* there are 3 cases,
   case 1: the node to be removed is at the front
   case 2: the node to be removed is not at the front and not at the end
   case 3: the node to be removed is at the end
   */

   /* a node is at the front if its prev pointer is NULL */

   if (toRemove->prev == NULL)
   {
       /* case 1 */
       /* advance the root */
       root = toRemove->next;

       /* Now be careful, if toRemove is the
       only node on the list, root will now point
       to NULL */
       if (root != NULL)
       {
         root->prev = NULL;
       }
   }
   else
   {
       /* case 2 and 3 */
       toRemove->prev->next = toRemove->next;
       
       if (toRemove->next != NULL)
       {
         /* case 2 */
         toRemove->next->prev = toRemove->prev;
       }
   }

   /* as a precaution, null out the removed node's next and prev pointers */
   toRemove->next = NULL;
   toRemove->prev = NULL;
}

/*
ListSearchForNumber

given a number it finds the first node with the number,
it increments the node's access count,
it moves the node to the front of the list

returns a pointer to the node or returns NULL if node is not found
*/
ListNode* List_SearchForNumber(int number)
{
   ListNode* pNode = root;
   while(pNode != NULL)
   {
       if (pNode->number == number)
       {
         /*
         we have found the node
         so we increment the access count
         */
         pNode->accessCount++;
         /*
         Reuse existing alogrithms to move the node
         to the head of the list, but only if the node
         is not already at the head of the list.
         A node is at the head of the list if its
         prev pointer is NULL
         */
         if (pNode->prev != NULL)
         {
         List_RemoveNode(pNode);
         List_InsertAtFront(pNode);
         }
         return pNode;
       }
       pNode = pNode->next;
   }

   return NULL;
}

int main(void)
{
   int number;

   List_Print();

   for(number = 0; number < 10; ++number)
   {
       ListNode* newNode = newListNode(number);
       List_InsertAtFront(newNode);
   }

   List_Print();

   for(number = 0; number < 10; ++number)
   {
       if (List_SearchForNumber(number) == NULL) printf("Search error\n");
       else
       {
         printf("\n\nSearch for %d done\n", number);
         List_Print();
       }
   }

   for(number = 9; number >= 0; --number)
   {
       if (List_SearchForNumber(number) == NULL) printf("Search error\n");
       else
       {
         printf("\n\nSearch for %d done\n", number);
         List_Print();
       }
   }

   /* Now test search for a number not in the list */
   printf("\nSearching for non-existent number\n");
   if (List_SearchForNumber(99) != NULL)
   {
       printf("Search for non-existent number caused an error\n");
   }
   else
   {
       printf("OK\n");
   }

   return 0;
}