Thread: i'm having trouble with linked lists

the above is code for padding the numbers with 0's where necessary rt? i put it in properly, but i'm still having the same problems i mentioned before.

alrite...i padded it with 0's, but now the problem that i'm having is that its adding to the end of the list...so if i put in two integers like 12345 and 1...it makes 1 = 10000 instead of 00001. ne ideas?

Code:

  if(count1 > count2)
  {
    printf("count1 is greater\n");
    for(i=1; i <= (count1 - count2); i++)
      {
		pTemp = create_newnode(c - '0');
		pSecond = insert_newnode(pSecond, pTemp);
      }
  }

Code:

PNODE create_newnode(int x)
{
  PNODE pTemp;
  int i;

  pTemp = (PNODE) malloc (sizeof(NODE));
  if (pTemp == NULL)
    {
      printf("Out of memory, could not store number!\n");
      exit(1);
    }
  else
    {
	  pTemp->digit = 0;
	  pTemp->next = NULL;
	}

  return pTemp;
}

PNODE insert_newnode(PNODE pList, PNODE pNew)
{
  pNew->next = pList;
  pList = pNew;
  return pNew;
}

alrite...after tons of hours of working on this damn program...i got everything working except a couple of cases. basically...if i enter two integers which have the same number of digits, and also their starting digits are the same, my program crashes. this is because i have not been able to extract only the first digit when the counts r equal. even if i am able to do that, i will face further problems when both the first and second digits of the two integers r same...and so on. ne ideas of how to get around this? also...my display function works so nicely...isnt there any way to just input the integer from that display function and then subtract using that. everytime i try to set a = display_number(pFirst), it gives me some weird values. any help will be appreciated...programming is soo tiring...

how can i compare two linked lists?? i've been trying to write a function like that but didnt see how it was possible

hey guys...thanks for all ur help...i finally finished the program...i made a compare function, and was also able to pad it with 0's properly...turned out real well.

anyway you could post the finished and complete code of your program snafu???

yea sure...here is the finished code

Code:

#include <stdio.h>
#define TRUE 1
#define FALSE 0 

 
typedef struct node
{
  int digit;
  struct node *next;
  struct node *prev;
} NODE;

typedef NODE *PNODE;

PNODE create_node(int);
PNODE add_zeros(int);
PNODE create_prev_links(PNODE);
PNODE insert_node(PNODE, PNODE);
PNODE insert_newnode(PNODE, PNODE);
PNODE compare(PNODE, PNODE);
PNODE sub_numbers(PNODE ,PNODE); 
void display_number(PNODE);
void free_list(PNODE);
int count1=0, count2=0;


int main(void)
{
  /*
    pFirst and pSecond store digits of input in backwards order.
    pDiff stores the difference and pTemp is a temporary node.
  */
  PNODE pFirst = NULL, pSecond = NULL, pSum = NULL, pDiff = NULL,pTemp;
  char c;
  int i;

  /* Read input from user. */
  printf("Enter first positive integer: ");
  while ((c = getchar()) != '\n') {
    pTemp = create_node(c - '0');
    pFirst = insert_node(pFirst, pTemp);
    count1++;
  }
  printf("Enter second positive integer: ");
  while ((c = getchar()) != '\n') {
    pTemp = create_node(c - '0');
    pSecond = insert_node(pSecond, pTemp);
    count2++;
  }
  
 /* 
   Count1 and Count2 count the number of digits in each list.
   Depending on which list has lesser number of digits, it is
   padded with zeros in order to be used for subtraction.
 */  
  if(count1 > count2)
  {
    for(i=1; i <= (count1 - count2); i++)
      {
		pTemp = add_zeros(c - '0');
		pSecond = insert_newnode(pSecond, pTemp);
      }

  }
  
  if(count2 > count1)
  {
    for(i=1; i <= (count2 - count1); i++)
      {
		pTemp = add_zeros(c - '0');
		pFirst = insert_newnode(pFirst, pTemp);
      }
  }
  
  /* 
    Previous links are created for the newly padded lists
    to allow traversing the list in both directions.
  */
  pFirst = create_prev_links(pFirst);
  pSecond = create_prev_links(pSecond);
  
  /*The numbers are compared and the subtraction is done*/
  compare(pFirst,pSecond);  

  /* Free memory. */
  free_list(pFirst);
  free_list(pSecond);
  free_list(pDiff);
  return 0;
}

/* Creates a node for given data and return pointer to it. */
PNODE create_node(int x)
{
  PNODE pTemp;

  pTemp = (PNODE) malloc (sizeof(NODE));
  if (pTemp == NULL)
    {
      printf("Out of memory, could not store number!\n");
      exit(1);
    }
  else
    {
      pTemp->digit = x;
      pTemp->next = NULL;
    }

  return pTemp;
}

/* Creates a node for zeros and return pointer to it. */
PNODE add_zeros(int x)
{
  PNODE pTemp;
  int i;

  pTemp = (PNODE) malloc (sizeof(NODE));
  if (pTemp == NULL)
    {
      printf("Out of memory, could not store number!\n");
      exit(1);
    }
  else
    {
	  pTemp->digit = 0;
	  pTemp->next = NULL;
	}

  return pTemp;
}

/* Inserts node pNew into pList at the start of the list. */
PNODE insert_node(PNODE pList, PNODE pNew)
{
  pNew->next = pList;
  return pNew;
}

/* Inserts node pNew into pList after the zeros have been added. */
PNODE insert_newnode(PNODE pList, PNODE pNew)
{
  PNODE pCurr = pList;
  while (pCurr->next != NULL)
    pCurr = pCurr->next;
    pCurr->next = pNew;
  return pList;
}


/* Display the number represented by the list. */
void display_number(PNODE pList)
{
  while (pList != NULL)
    {
        putchar(pList->digit + '0');
        pList = pList->next;
	}
  return;
}

/* Free memory associated with list. */
void free_list(PNODE pList)
{
  PNODE pTemp;

  while (pList != NULL)
    {
      pTemp = pList->next;
      free(pList);
      pList = pTemp;
    }

  return;
}

/* Subtract Numbers */
PNODE sub_numbers(PNODE pFirst, PNODE pSecond)  
{  
  PNODE pTemp, pDiff = NULL;  
  int borrow = FALSE;  
  int cur_digit;  
  
  /* Loop through both numbers to subtract at once. */  
  while ((pFirst != NULL) || (pSecond != NULL))  
    {  
       if(borrow) {           // Borrow is used if digit being subtracted from
        pFirst->digit--;      // is larger than the first digit.
        borrow = FALSE;  
      } 
 
      if (pFirst->digit < pSecond->digit)  
     {  
        cur_digit = ((pFirst->digit + 10) - pSecond->digit);  
        borrow = TRUE;  
     }  
      else if(pFirst->digit > pSecond->digit)  
     {  
        cur_digit = pFirst->digit - pSecond->digit;  
     }   
      else if(pFirst->digit == pSecond->digit)  
     {  
        cur_digit = pFirst->digit - pSecond->digit;  
     }
     /* Create a node for the difference */   
      pTemp = create_node(cur_digit);  
      pDiff = insert_node(pDiff, pTemp);  
  
      /* Update each pointer to next digit. */  
      if (pFirst != NULL)  
     pFirst = pFirst->next;  
      if (pSecond != NULL)  
     pSecond = pSecond->next;  
    }  
  
  
  return pDiff;  
}

/* Compare function */
PNODE compare(PNODE pFirst, PNODE pSecond)
{
  PNODE pCurr1 = pFirst;
  PNODE pCurr2 = pSecond;
  PNODE pDiff;
  if(count1 > count2)    /* Number 1 is bigger */
  {			
	pDiff = sub_numbers(pFirst,pSecond);
	printf("Diff = ");
	display_number(pDiff);
	printf("\n");
  }
  
  if(count2 > count1)   /* Number 2 is bigger */
  {			
	pDiff = sub_numbers(pSecond,pFirst);
	printf("Diff = -");
	display_number(pDiff);
	printf("\n");
  }
  /* 
    Determine which number is bigger when they
    have same number of digits.
  */ 
  if(count1 == count2)  
  {
    /* Go to end of lists */
    while (pCurr1->next != NULL)
    {
      pCurr1 = pCurr1->next;
    }
    while (pCurr2->next != NULL)
    {
      pCurr2 = pCurr2->next;
    }
    /* Determine if numbers have different starting digits.*/
    if(pCurr1->digit > pCurr2->digit)
		{
			pDiff = sub_numbers(pFirst,pSecond);
			printf("Diff = ");
			display_number(pDiff);
			printf("\n");
		}        
	else if(pCurr2->digit > pCurr1->digit)
		{
			pDiff = sub_numbers(pSecond,pFirst);
			printf("Diff = -");
			display_number(pDiff);
			printf("\n");
		}
	/*
	  If numbers have same starting digits, check to see when
	  the numbers have different digits and then determine
	  which number is larger, and finally do subtraction.
	*/
	else if(pCurr2->digit == pCurr1->digit)
	{
	  while ((pCurr1->digit == pCurr2->digit) && ((pCurr1->prev != NULL) || (pCurr2->prev != NULL)) )
      {
	    pCurr1 = pCurr1->prev;
	    pCurr2 = pCurr2->prev;
		  if(pCurr1->digit > pCurr2->digit)
		  {
			pDiff = sub_numbers(pFirst,pSecond);
			printf("Diff = ");
			display_number(pDiff);
			printf("\n");
		  }        
		  if(pCurr2->digit > pCurr1->digit)
		  {
			pDiff = sub_numbers(pSecond,pFirst);
			printf("Diff = -");
			display_number(pDiff);
			printf("\n");
		  }
		  if((pCurr1->digit == pCurr2->digit) && ((pCurr1->prev == NULL) || (pCurr2->prev == NULL)) )
		  {
			printf("Diff = 0 ");
			printf("\n");
		  }
	  }
	}
  }        
}

/* Create previous links */
PNODE create_prev_links(PNODE pList)
{
 while(pList->next != NULL)
 {
  pList->next->prev = pList;
  pList = pList->next;
 }

 while(pList->prev != NULL)
 {
  pList = pList->prev;
 }

 return pList;

}