Advertisemen
#include <stdio.h>
#include <stdlib.h>
struct listNode
{
int value;
struct listNode *nextPtr;
};
typedef struct listNode ListNode;
typedef ListNode* ListNodePtr;
void insert ( ListNodePtr *sPtr, int data )
{
ListNodePtr newPtr,prevPtr,currPtr; //pointers to new node, prev node and current node
newPtr = (ListNodePtr) malloc( sizeof(ListNode) ); //allocate memory
if (newPtr != NULL) //if space available
{
newPtr->value = data; //data is the value we are inserting to the list
newPtr->nextPtr = NULL; //setup new ptr to point towards nothing as we haven't found it's insertion point yet
prevPtr = NULL; //no previous nodes as we are starting at the beginning of the list
currPtr = *sPtr; //*sPtr is the node that is at the end of the list
//diagram: prevPtr -> n -> n+1 -> ... -> sPtr
//find correct insertion place
//we first check the value we want to insert against prevPtr, if it's larger than prevPtr, we continue along the list to sPtr
//currPtr moves along the list
//i.e. step (1) prevPtr -> n -> n+1 -> ... -> sPtr
// currPtr
//
// step (2) prevPtr -> n -> n+1 -> ... -> sPtr
// currPtr
//
// step (3) prevPtr -> n -> n+1 -> ... -> sPtr
// currPtr
//
// step (.) prevPtr -> n -> n+1 -> ... -> sPtr
// currPtr
//
// step (n) prevPtr -> n -> n+1 -> ... -> sPtr
// currPtr
while (currPtr != NULL && data > currPtr->value)
{
//move to next node
prevPtr = currPtr;
currPtr = currPtr->nextPtr;
}
if (prevPtr == NULL) //insert the newptr at the beginning of the list, as the data we want to insert is the smallest value
{
newPtr->nextPtr = *sPtr;
*sPtr = newPtr;
}
else //insert newptr between currPtr and prevPtr
{
prevPtr->nextPtr = newPtr;
newPtr->nextPtr = currPtr;
}
}
else printf("Insert of %d failed, no memory available\n",data);
}
lass="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0cm; mso-layout-grid-align: none; text-autospace: none;">char destroy( ListNodePtr *sPtr, int data )
{
ListNodePtr tempPtr,prevPtr,currPtr; //pointers to a temp node, prev node and current node
//delete first node
if ( data == (*sPtr)->value) //if the first node has the value we are looking to delete
{
//we need to clear up the end list pointer, currently it is like
//
// sPtr -> ptr1 -> ... -> ptrn
//
//as we are deleting the starting pointer, we need ptr1 to be the starting pointer:
//
// ptr1 -> ... -> ptrn
tempPtr = *sPtr; //temporarily store sptr (for deletion)
*sPtr = (*sPtr)->nextPtr; //the starting ptr is now the next node in the list (ptr1 in diagram)
free (tempPtr); //clear up the memory used for the old starting pointer
return 1; //return to confirm deletion
}
else
{
//step back in the list
prevPtr = *sPtr;
currPtr = (*sPtr)->nextPtr;
//loop until the element is found in the list
while (currPtr != NULL && currPtr->value != data)
{
prevPtr = currPtr;
currPtr = currPtr->nextPtr;
}
//if node has been found
if (currPtr != NULL)
{
//remove it from the list
// prevPtr -> currPtr -> nextPtr
// remove
//
//so prevPtr needs to point to nextPtr
tempPtr = currPtr; //store for deletion
prevPtr->nextPtr = currPtr->nextPtr; //prevPtr points to the nextPtr
free(tempPtr); //delete unused node memory
return 1; //confirm it has been found
}
}
}
int isEmpty(ListNodePtr sPtr)
{
return sPtr == NULL;
}
void printList(ListNodePtr currPtr)
{
if (currPtr != NULL)
{
printf("The list is:\n");
//while not end of list
while (currPtr != NULL)
{
//print the entry
printf("%d --> ",currPtr->value);
currPtr = currPtr->nextPtr;
}
printf("NULL\n");
}
else printf("The list is empty.\n\n");
}
void displayInstructions();
int main()
{
ListNodePtr startPtr = NULL; //init start of list
int choice; //user's choice
int item; //user's list entry
displayInstructions();
printf("> ");
scanf("%d",&choice); //get input
while (choice != 3) //end program if '3' entered
{
switch (choice)
{
case 1:
printf("Enter a number: ");
scanf("\n%d",&item);
insert(&startPtr,item);
printList(startPtr);
break;
case 2:
if (!isEmpty(startPtr))
{
printf("Enter character to be deleted: ");
scanf("\n%d",&item);
if (destroy(&startPtr,item))
{
printf("%d deleted.\n",item);
printList(startPtr);
}
else printf("%d not found.\n\n",item);
}
else printf("List is empty.\n\n");
break;
case 3:
return 0;
break;
default: break;
}
printf("> ");
scanf("%d",&choice);
}
return 0;
}
void displayInstructions()
{
printf("Enter your choice:\n\t1 to insert an element into the list.\n\t2 to delete an element from the list.\n\t3 to end.\n");
}
Advertisemen
Tidak ada komentar:
Posting Komentar