/*---------------------------------------------------------------------- File : intlists.c Contents: operations on lists of integer numbers (linked list version) Author : Christian Borgelt History : 04.06.1998 file created ----------------------------------------------------------------------*/ #include #include #include /*---------------------------------------------------------------------- Preprocessor Definitions ----------------------------------------------------------------------*/ #define HEAD NULL /* position at head of list */ #define INVALID NULL /* invalid position */ /*---------------------------------------------------------------------- Type Definitions ----------------------------------------------------------------------*/ typedef struct listelem *LISTPTR; /* a pointer to a list (element) */ typedef struct listelem *POSITION; /* a position in a list */ typedef struct listelem { /* --- a list element --- */ LISTPTR next; /* next element in list (successor) */ int datum; /* datum stored in list element */ } LISTELEM; /* (list element) */ /*---------------------------------------------------------------------- List Functions ----------------------------------------------------------------------*/ LISTPTR create_list (void) { /* --- create an empty list */ return NULL; /* return a pointer to no element */ } /* create_list() */ /*--------------------------------------------------------------------*/ void delete_list (LISTPTR list) { /* --- delete a given list */ LISTPTR tmp; /* buffer for list elements */ while (list != NULL) { /* while list is not empty */ tmp = list; /* note first element, */ list = list->next; /* remove it from the list, */ free(tmp); /* and delete it */ } /* (deallocate the memory) */ } /* delete_list() */ /*--------------------------------------------------------------------*/ int is_empty (LISTPTR list) { /* --- is the list empty? */ return (list == NULL); /* check whether list is NULL */ } /* is_empty() */ /*--------------------------------------------------------------------*/ int get (LISTPTR list, POSITION pos) { /* --- get datum from a list element */ return (pos != NULL) ? /* if there is a list element, */ pos->datum : 0; /* return its contents, */ } /* get() */ /* otherwise return 0 */ /*--------------------------------------------------------------------*/ POSITION next (LISTPTR list, POSITION pos) { /* --- go to next list element */ return (pos != NULL) /* return successor element */ ? pos->next : list; /* or first list element */ } /* next() */ /*--------------------------------------------------------------------*/ int is_last (LISTPTR list, POSITION pos) { /* --- is this the last element? */ return (pos != NULL) /* if the position is a list element, */ ? (pos->next == NULL) /* check whether it has a successor, */ : (list == NULL); /* otherwise check for an empty list */ } /* is_last() */ /*--------------------------------------------------------------------*/ POSITION find (LISTPTR list, int datum) { /* --- find a given datum in a list */ POSITION pos = list; /* to traverse the list */ while ((pos != NULL) /* while not at end of list */ && (pos->datum != datum)) /* and datum not found, */ pos = pos->next; /* go to the next element */ return pos; /* return position of datum */ } /* find() */ /*--------------------------------------------------------------------*/ POSITION find_inspos (LISTPTR list, int datum) { /* --- find insertion position */ POSITION pos = list; /* to traverse the list */ if ((pos == NULL) /* if the list is empty */ || (pos->datum >= datum)) /* or the first element is not less, */ return HEAD; /* datum must be inserted at the head */ while ((pos->next != NULL) /* while not at end of list and */ && (pos->next->datum < datum)) /* datum in element is smaller, */ pos = pos->next; /* go to the successor element */ return pos; /* return insertion position */ } /* find_inspos() */ /*--------------------------------------------------------------------*/ POSITION find_last (LISTPTR list) { /* --- find last list element */ POSITION pos = list; /* to traverse the list */ if (pos == NULL) return NULL; /* check for an empty list */ while (pos->next != NULL) /* while this is not the last elem., */ pos = pos->next; /* go to the next element */ return pos; /* return last element */ } /* find_last() */ /*--------------------------------------------------------------------*/ LISTPTR insert (LISTPTR list, POSITION pos, int datum) { /* --- insert a datum into a list */ LISTPTR tmp; /* buffer for new element */ tmp = (LISTPTR)malloc(sizeof(LISTELEM)); if (!tmp) return NULL; /* create a new list element */ tmp->datum = datum; /* copy datum into new element */ if (pos == NULL) { /* if to insert at head of list, */ tmp->next = list; /* append list to the new element */ return tmp; /* and return the new element as the */ } /* new first element of the list */ tmp->next = pos->next; /* append the tail of the list to tmp */ pos->next = tmp; /* and tmp to the insert position */ return list; /* return the modified list */ } /* insert() */ /*--------------------------------------------------------------------*/ LISTPTR delete (LISTPTR list, int datum) { /* --- delete a datum from a list */ LISTPTR *p = &list; /* to traverse the list */ LISTPTR tmp; /* buffer for a list element */ while ((*p != NULL) /* while not at end of list */ && ((*p)->datum != datum)) /* and datum not found, */ p = &(*p)->next; /* go to the next list element */ if (*p != NULL) { /* if the datum was found, */ tmp = *p; /* note the element holding it, */ *p = tmp->next; /* remove it from the list, */ free(tmp); /* and delete it */ } /* (deallocate the memory) */ return list; /* return the modified list */ } /* delete() */ /*---------------------------------------------------------------------- Main Function ----------------------------------------------------------------------*/ int main (int argc, char *argv[]) { /* --- main function */ LISTPTR list; /* created integer list */ LISTPTR mod; /* buffer for modified list */ POSITION pos; /* current position in list */ int datum; /* number to insert */ int cmd; /* command */ printf("%s --- integer lists (linked list version)\n", argv[0]); printf("type l for a list of commands\n"); list = create_list(); /* create an integer list */ pos = HEAD; /* initial position: at head */ while (1) { /* command evaluation loop */ printf("> "); fflush(stdout); do { cmd = getchar(); /* get next command */ } while (strchr(" \t\n", cmd) != NULL); switch (cmd) { /* evaluate command */ case 'i': case 's': /* -- insert element */ if (scanf(" %i", &datum) != 1) break; /* get number to insert */ if (cmd == 's') /* if to insert sorted, find position */ pos = find_inspos(list, datum); mod = insert(list, pos, datum); if (!mod) printf("not enough memory\n"); else list = mod; /* insert element into list */ break; /* and replace old list */ case 'd': /* --- remove element */ if (scanf(" %i", &datum) != 1) break; /* get number to remove */ list = delete(list, datum); break; /* delete number from the list */ case 'h': /* --- go to the head of the list */ pos = HEAD; break; /* set position to head of list */ case 't': /* --- go to the tail of the list */ pos = find_last(list); break; case 'n': /* --- go to next element */ pos = next(list, pos); break; case 'm': /* --- move to element */ if (scanf(" %i", &datum) != 1) break; /* get number to move to */ pos = find(list, datum); break; /* search for first occurence */ case 'p': /* --- print element */ if (pos == INVALID) break; /* check for a valid position */ datum = get(list, pos); /* get current element and print it */ printf("%i\n", datum); break; case 'a': /* --- print all elements */ pos = HEAD; /* start at head and traverse list */ while ((pos = next(list, pos)) != INVALID) printf("%i\n", get(list, pos)); break; /* print all elements */ case 'l': /* --- print command list */ printf("commands:\n"); printf("i x -- insert number x at current position\n"); printf("s x -- insert number x sorted\n"); printf("d x -- delete number x from list\n"); printf("h -- go to the head of the list\n"); printf("t -- go to the tail of the list\n"); printf("n -- go to the next element\n"); printf("m x -- move to first element with value x\n"); printf("p -- print the current element\n"); printf("a -- print all elements in the list\n"); printf("l -- print this list of commands\n"); printf("q -- quit program\n"); break; /* print list of commands */ case 'q': /* quit program */ delete_list(list); /* delete the list */ return 0; /* and return `ok' */ default : /* ignore everything else */ printf("unknown command --- type l for a list\n"); break; } } /* while (1) */ } /* main() */