Search Tools Links Login

Get relative URL of current page: mstrGetURL


Returns relative URL of current page. Example: /vb/test.asp. See http://www.planet-source-code.com/vb/scripts/ShowCode.asp?lngWId=4&txtCodeId=5 to get the fully qualified URL string.

Original Author: Ian Ippolito (vWorker)

Code

//Jeff Letendre
#include //for malloc()
#include //for printf(), scanf(), fflush()
void main (void);    ///////////////////////////////////////
struct node * merge (struct node *, struct node *);    ///////////////////////////////////////
struct node * reverse (struct node **); ///////////////////////////////////////
struct node * createList (void); ///////////////////////////////////////
struct node * subtract (struct node *, struct node *);    ///////////////////////////////////////
struct node * addSort(int, struct node **); ///////////////////////////////////////
struct node * getMemory(void); ///////////////////////////////////////
struct node * InsertAfter (struct node **); ////////////// prototype //////////////
struct node * intersection (struct node *, struct node *); ////////////// section //////////////
struct node * search (int, struct node *); ///////////////////////////////////////
struct node * bubbleSort (struct node *);           ///////////////////////////////////////
void PrintList (struct node *); ///////////////////////////////////////
void deleteNode (struct node **); ///////////////////////////////////////
void free_node (struct node **); ///////////////////////////////////////
int palindrome (struct node *plist); ///////////////////////////////////////
void errorExit (char *); ///////////////////////////////////////
struct node //structure template
  {
  struct node *previous; //pointer to previous node in list
  int data; //integer list data
  struct node *next; //pointer to next node in the list
  };
////////////END OF HEADER SECTION////////////////

void main (void)
  {
  struct node *plist = NULL; //pointer for first list
  struct node *plist2 = NULL; //pointer for second list
  struct node *pnode = NULL;    //pointer for node
  struct node *tempList = NULL;           //misc. pointer for returned lists
  int option = 0, choice = 0;           //variables for user input

  while (true) //main program loop set to infinite loop
   {
   printf(" Please make a selection: "); //prompt for input
   printf(" 0 = Add in sorted order ");
   printf(" 1 = Create a list ");
   printf(" 2 = Seek and destroy ");
   printf(" 3 = Exit ");
   printf(" 4 = Search ");
   printf(" 5 = Intersection ");
   printf(" 6 = Print ");
   printf(" 7 = Merge two lists ");
   printf(" 8 = Create another list ");
   printf(" 9 = Palindrome? ");
   printf("10 = Reverse list ");
   printf("11 = Subtract two lists ");
   printf("12 = Insert after ");
   fflush(stdin); //clear input buffer
   scanf("%d", &option);             //scan new option
   switch(option)
     {
     case 0:
  {
  printf("Enter an integer to be added to the list or -99999 ");
      scanf("%d", &choice);
  while (choice != -99999)    //call addSort
        {
    plist = addSort(choice, &plist);
    printf("Enter another integer or -99999 to quit ");
    fflush(stdin);
    scanf ("%d", &choice);
    }
      break;
      }
     case 1:
  {
      plist = createList();
  break;
  }
     case 2:
  {
  deleteNode(&plist); //no return modifying original list
  break;
  }
     case 3:
  {
  exit(1);
  break;
  }
     case 4:
  {
  printf("Enter a value to search the list for: ");
  scanf("%d", &choice);
      tempList = search(choice, plist);
      if (tempList == NULL)
        {
        printf("The value %d was not found in the list ", choice);
        break;
        }
  else
        {
        if(tempList->previous == NULL && tempList->next == NULL)
         printf("%d is the only value in the list ", tempList->data);
        else if(tempList->previous == NULL && tempList->next != NULL)
         printf("%d is the first value in the list followed by %d ",
           tempList->data, (tempList->next)->data);
        else if(tempList->previous != NULL && tempList->next == NULL)
         printf("%d comes after %d and is the last value in the list ",
           tempList->data, (tempList->previous)->data);
        else if(tempList->previous != NULL && tempList->next != NULL)
         printf("%d comes after %d and before %dlist ", tempList->data,
           (tempList->previous)->data, (tempList->next)->data);
        break;
        }
  }  
     case 5:
  {
      tempList = intersection (plist, plist2);
      if(tempList != NULL)
        {
        tempList = bubbleSort(tempList);
        PrintList(tempList);
        }
  break;
  }
     case 6:
  {
  PrintList(plist);
  break;
  }
     case 7:
      {
     tempList = merge (plist, plist2);
      PrintList(tempList);
  break;
  }
     case 8:
  {
  plist2 = createList();
  break;
  }
     case 9:
  {
  if(palindrome(plist))    //if palindrome returns 1
    {
    PrintList(plist);
    printf(" it is a palindrome. ");
    }
  else
        {
    PrintList(plist);      //else list is not a palindrome
    printf(" it is not a palindrome. ");
    }
  break;
  }
     case 10:
  {
      PrintList(plist);           //print list before reversing
      printf(" Reversing... ");
  plist = reverse(&plist);    //call to reverse func
      PrintList(plist);           //print reversed list      
  break;
  }
     case 11:
  {
  printf("How shall I subtract your lists? ");
      printf("1 = First list entered minus second list entered or ");
      printf("2 = Second list entered minus first list entered? ");
      scanf("%d", &choice);
  if (choice == 1)
        {
        tempList = subtract (plist, plist2);
        }
      else if (choice == 2)
        {
        tempList = subtract (plist2, plist);
        }
      else
        {
        printf("Incorrect choice escaping to main menu ");
        break;
        }
      PrintList(tempList);
      break;
  }
     case 12:
  {
  plist = InsertAfter(&plist); //Insert After has capability to
  break;               //start a new list if plist is empty
  }
     default:
  {
  printf("Your only options are zero (0) through eleven (11) ");
  printf("Enter new option ");
  break;
  }
     }  //end switch    
   }  //end while
  }//////////////end main()/////////////////
struct node * addSort(int newVal, struct node **plist)
  {
  struct node *newNode;
  struct node *ptemp;
  ptemp = *plist;
  newNode = getMemory(); //call getMemory to allocate and test
  newNode->data = newVal; //copy int into struct
  while(ptemp != NULL && ptemp->data <= newNode->data && ptemp->next != NULL)
   ptemp = ptemp->next;
  if(ptemp == NULL) //if list is empty
   {
   newNode->next = NULL; //set next to NULL
   newNode->previous = NULL;    //set previous to NULL
   *plist = newNode; //set list pointer to newNode
   }
  else if(ptemp->previous == NULL && ptemp->data > newNode->data)//at begining of list
   {
   newNode->previous = ptemp->previous;
   newNode->next = ptemp;
   ptemp->previous = newNode;
   *plist = newNode;
   }
  else if(ptemp->next == NULL) //at end of list
   {
   newNode->previous = ptemp;
   newNode->next = ptemp->next;
   ptemp->next = newNode;
   }
  else if(ptemp->data > newNode->data) //inbetween begining and end of list
   {
   newNode->next = ptemp;
   newNode->previous = ptemp->previous;
   (ptemp->previous)->next = newNode;
   ptemp->previous = newNode;
   }
  return(*plist); //pass back list pointer
  } ////////////end add sort//////////////////

struct node * bubbleSort (struct node *listHead)//sorts a doubly linked list of ints
  {                      //returns pointer to sorted list
  struct node * listp1 = NULL;
  struct node * listp2 = NULL;
  listp1 = listHead;              //assign pointer to list head
  listp2 = listHead->next;           //assign pointer to next node
  while(listp1 != NULL && listp2 != NULL)
   {
   if(listp1->data <= listp2->data)     //if in ascending order w/ next node
     {
     listp2 = listp2->next;         //skip to next 2 nodes
     listp1 = listp1->next;
     }
   else                   //else swap order
     {
     listp1->next = listp2->next;
     listp2->previous = listp1->previous;
     if(listp1->previous != NULL)      //if not the first node
      (listp1->previous)->next = listp2; //point previous node's next field to listp2
     listp1->previous = listp2;
     if(listp2->next != NULL)        //if there is a next node
      (listp2->next)->previous = listp1; //point its previous field to listp1
     listp2->next = listp1;
     if(listp1 == listHead)         //reset pointers to begining of
      listHead = listp2;
     listp1 = listHead;
     listp2 = listp1->next;
     }
   }  //end while
  return listHead;
  }///////////////////end bubbleSort///////////////////////

struct node * createList(void)
  {
  struct node * plist = NULL; //pointer for new list
  struct node * temp = NULL; //pointer for inserting into list
  struct node * pinsert = NULL; //pointer for node allocation
  pinsert = getMemory(); //call getMemory to allocate and test
  pinsert->next = NULL; //set node pointers to NULL
  pinsert->previous = NULL;
  plist = pinsert; //point list pointer to first node
  printf("Type a list of integers to be created ");
  printf("Enter -99999 to finish input cycle ");
  printf("Enter first integer for new list ");
  scanf("%d", &(pinsert->data));    //scan new value
  while (pinsert->data != -99999)
   {
   temp = pinsert;
   pinsert = getMemory(); //call getMemory to allocate and test
   pinsert->next = NULL; //copy NULL to new node's next field
   pinsert->previous = temp;
   temp->next = pinsert;
   printf("Enter an integer to be added after %d: ", temp->data);
   scanf("%d", &(pinsert->data)); //scan into struct's data element value
   }
  fflush(stdin);
  free(pinsert); //free node which contains sentinel (-99999)
  temp->next = NULL;              //assign last node's next pointer to NULL
  return (plist); //returns NULL if list contains sentinel only
  } //////////////End createList/////////////

void deleteNode (struct node ** plist)     //deletes node from list
  {
  struct node *temp = NULL;
  struct node *next1 = NULL;
  int delVal = 0;
  next1 = *plist; //set pointer to list head
  printf("Enter a value and I will delete all nodes ");
  printf("whose data element matches your value ");
  scanf("%d", &delVal);
  while(next1 != NULL) //search through whole list
   {
   if(next1->data == delVal) //if delVal is found
     {
if(next1->next == NULL && next1->previous == NULL) //if deleting only node
  {    //deleting only node. Point plist to NULL
  free(next1);
  *plist = NULL;
  }
else if(next1->previous == NULL) //if deleting first node
      {
  next1 = next1->next; //skip next1 to next node
  next1->previous = NULL; //since first node assign previous to NULL
  *plist = next1; //point the list pointer to the new first node
      free(temp); //free old first node
  temp = *plist; //point temp to list
  }
     else if(next1->next == NULL) //if deleting last node
      {
  temp->next = NULL; //set temp as last node
  free(next1); //free last node in list
  next1 = temp->next; //point next1 to NULL;
  }                  //end else
     else                  //else deleting a node between nodes
      {
  temp->next = next1->next; //shift pointer to skip over node to be deleted
  (next1->next)->previous = temp; //point previous element of 1st node after deleted node to temp
  free(next1); //free node
  next1 = temp->next; //point next1 to next node
      }  //end else
     }  //end if
   else
     {
temp = next1;
next1 = next1->next; //go through list
}                   //end else
   }                   //end while
  }////////////////end deleteNode()///////////////

void errorExit(char *string)          //prints error & exits program
  {
  printf("%s", &string);
  exit(1);
  }/////////////end errorExit()///////////////

void free_node (struct node **pnode)
  {
  struct node *ptemp; //temp pointer used for swaping structure pointers
  if(pnode == NULL) //if list is empty
   errorExit("Attempt to delete from a NULL node pointer");
  ptemp == (*pnode)->previous;    //point to previous node
  ptemp->next = (*pnode)->next; //mend break in links
  free(pnode); //release memory back to OS
  }/////////end free_node/////////

struct node * getMemory(void)          //allocates & tests return value
  {
  struct node * newPtr = NULL;
  if((newPtr = (struct node *) malloc(sizeof(struct node))) == NULL)
   {   //if malloc returns a NULL pointer
   printf("ERROR! Unable to allocate memory - Abort ");
   abort(); //print error msg & abort function
   return(0); //make the compiler happy :>)
   }
  else
   return newPtr;
  }   ///////////////////end getMemory///////////////

struct node * InsertAfter(struct node **plist)
  {
  struct node *tempNode;
  struct node *tempList;
  int afterVal = 0, choice = 0;
  tempList = *plist;
  tempNode = getMemory(); //call getMemory to allocate and test
  if (tempList == NULL) //if list is empty
   {
   printf("Your list is empty. Should I create a list for you? ");
   printf("1 = Yes 2 = No ");
   scanf("%d", &choice);
   if(choice == 1)
     {
     printf("Enter an integer ");     //prompt and get input
     while(scanf("%d", &choice) < 1)    //testing scanf//reusing choice for data input
      printf("Incorrect value entered. Please try again: ");  
     tempNode->data = choice;    
     tempNode->previous = NULL;       //set pointers
     tempNode->next = NULL;
     }
   else if(choice == 2)           //if user doesn't want to create list
     tempNode = NULL;            //set return pointer to NULL
   return tempNode;             //return pointer
   }  //end if
  else                 //list is not empty
   {     
   printf("Enter an integer to insert the next node after ");
   scanf("%d", &afterVal); //assign new value to data field
   for(; tempList != NULL && tempList->data != afterVal; tempList = tempList->next);
     if (tempList == NULL)
      {
      printf("Error list value not found "); //print error msg.
      return(tempList); //return NULL pointer
  }
else if(tempList->data == afterVal)
      {
  printf("Enter an integer to be added after %d ", tempList->data);
  scanf("%d", &(tempNode->data)); //get new data value
  tempNode->next = tempList->next; //assign new node's next field to plist's next field
  tempList->next = tempNode;    //copy temp into plist's next field
  tempNode->previous = tempList; //copy plist to temp's previous field
      }
  }  //end else
return (*plist);
  }///////////End InsertAfter////////////

struct node * intersection (struct node *opList1, struct node *opList2)
  {
  struct node *temp = NULL;
  struct node *intList = NULL;
  
  temp = getMemory();
  intList = temp;               //list head pointer
  if(opList1 == NULL || opList2 == NULL)
   {
   printf("Empty list(s) - can not take intersection ");
   temp = NULL;
   return temp;
   }
  while (opList1 != NULL)
   {
   if(search(opList1->data, opList2) != NULL)  
     {                   //if data is not in list
     temp->previous = opList1->previous;   //copy node into new list
temp->data = opList1->data;
temp->next = getMemory();       //allocate more memory
     (temp->next)->previous = temp;     //point next nodes previous field to current node    
     temp = temp->next;           //point temp to next node
     opList1 = opList1->next;
     }  //end if
   else
     opList1 = opList1->next;
   }  //end while
  (temp->previous)->next = NULL;         //terminate links w/ NULL
  free(temp);                 //release extra node back to OS
  return intList;
  } /////////////end intersection////////////////

struct node * merge (struct node *listA, struct node *listB)
  {
  struct node * listHead = NULL;       //pointer to new merged list
  listHead = listA;               //set pointers to begining of listA
  while (listA->next != NULL)         //skip to end of listA
   listA = listA->next;  
  listB->previous = listA;       //append listA with listB
  listA->next = listB;
  listHead = bubbleSort(listHead);       //sort new list
  return listHead;               //return pointer to new merged sorted list
  } ////////////end merge//////////////////

int palindrome (struct node *plist)
  {
  struct node *temp1;
  struct node *temp2;
  int i = 0, j = 0;
  
  temp1 = temp2 = plist; //set both temp vars to the list pointer
  for (i=0; temp2->next != NULL; temp2 = temp2->next, i++); //terminated for loop to move to end of list
   for(j = 0; j < i; j++)
     {
     if (temp1->data != temp2->data) //if values not equal
  return (0);
else
      {
  temp1 = temp1->next; //increment temp1
  temp2 = temp2->previous; //decrement temp2
      }
     }  //end for loop
  return(1);
  } ///////////end palendrome///////////////

void PrintList (struct node *plist)
  {
  int i = 0;
  if(plist != NULL)
   {
   printf("Here is your list:");
   while (plist != NULL)
     {
if((i % 10) == 0)        //CRLF first line then print ten values per line
printf(" ");
printf("--> %d ", plist->data);
plist = plist->next;          //point plist to next node
i++;
}  //end while loop
   }  //end else statement
  } ///////////////end PrintList()////////////////

struct node * reverse (struct node ** plist)
  {
  struct node *rList = NULL;
  struct node *ptemp = NULL;
  struct node *pt2 = NULL;
  
  ptemp = *plist;
  while(ptemp->next != NULL)
   {
   ptemp = ptemp->next;      //point ptemp to end of list
   }
  rList = ptemp;
  *plist = rList;    //set list pointer to end of list
  while(ptemp != NULL)
   {
   ptemp = ptemp->previous;
   rList->previous = rList->next;
   rList->next = ptemp;
   rList = ptemp;
   }
  return(*plist);
  } //////////end reverse////////////////////

struct node * search (int data, struct node *pstack)
  {
  struct node *ptemp;
  for (ptemp=pstack; ptemp != NULL && ptemp->data != data; ptemp = ptemp->next);
  return ptemp;                 //returns NULL if data not found
  }///////////end of search///////////////

struct node * subtract (struct node *opList1, struct node *opList2)
  {
  struct node *temp = NULL;
  struct node *subList = NULL;
  
  temp = getMemory();
  subList = temp;               //list head pointer
  while (opList1 != NULL)
   {
   if(search(opList1->data, opList2) == NULL)  
     {                   //if data is not in list
     temp->previous = opList1->previous;   //copy node into new list
temp->data = opList1->data;
temp->next = getMemory();       //allocate more memory
     (temp->next)->previous = temp;     //point next nodes previous field to current node    
     temp = temp->next;           //point temp to next node
opList1 = opList1->next;
     }                   //end if
   else
     opList1 = opList1->next;
   }                     //end while
  (temp->previous)->next = NULL;         //terminate links w/ NULL
  free(temp);                 //release extra node back to OS
  return subList;
  }//////////end subtract////////////////
/////////////////////////////////// END PROGRAM /////////////////////////////

About this post

Posted: 2002-06-01
By: ArchiveBot
Viewed: 150 times

Categories

ASP/ HTML

Attachments

No attachments for this post


Loading Comments ...

Comments

No comments have been added for this post.

You must be logged in to make a comment.