/*---------------------------------------------------------------------- File : intvecs.c Contents: operations on lists of integer numbers (vector version) Author : Christian Borgelt History : 04.06.1998 file created ----------------------------------------------------------------------*/ #include #include #include /*---------------------------------------------------------------------- Preprocessor Definitions ----------------------------------------------------------------------*/ #define VECSIZE 1000 /* vector size */ #define HEAD -1 /* position at head of list */ #define INVALID -1 /* invalid position */ /*---------------------------------------------------------------------- Type Definitions ----------------------------------------------------------------------*/ typedef struct vector *LISTPTR; /* a pointer to a list */ typedef int POSITION; /* a position in a list (index) */ typedef struct vector { /* --- a vector --- */ int cnt; /* number of elements in vector */ int data[VECSIZE]; /* data vector (of fixed size) */ } VECTOR; /* (vector) */ /*---------------------------------------------------------------------- List Functions ----------------------------------------------------------------------*/ LISTPTR create_list (void) { /* --- create an empty list */ LISTPTR list; /* created list */ list = (LISTPTR)malloc(sizeof(VECTOR)); if (!list) return NULL; /* allocate memory and */ list->cnt = 0; /* initialize element counter */ return list; /* return created vector */ } /* create_list() */ /*--------------------------------------------------------------------*/ void delete_list (LISTPTR list) { /* --- delete a given list */ free(list); /* deallocate memory */ } /* delete_list() */ /*--------------------------------------------------------------------*/ int is_empty (LISTPTR list) { /* --- is the list empty? */ return (list->cnt <= 0); /* check number of elements */ } /* is_empty() */ /*--------------------------------------------------------------------*/ int is_last (LISTPTR list, POSITION pos) { /* --- is this the last element? */ return (pos >= list->cnt-1); /* check vector index against */ } /* is_last() */ /* number of elements */ /*--------------------------------------------------------------------*/ POSITION find (LISTPTR list, int datum) { /* --- find a given datum in a list */ int i; /* loop variable (vector index) */ for (i = 0; i < list->cnt; i++) if (list->data[i] == datum) /* traverse elements of vector and */ return i; /* return the index of the datum */ return -1; /* if not found, return illegal index */ } /* find() */ /*--------------------------------------------------------------------*/ POSITION find_inspos (LISTPTR list, int datum) { /* --- find insertion position */ int i; /* loop variable (vector index) */ for (i = 0; i < list->cnt; i++) if (list->data[i] > datum) /* traverse elements of vector and */ break; /* stop at first higher number */ return i-1; /* return position of predecessor */ } /* find_inspos() */ /*--------------------------------------------------------------------*/ POSITION find_last (LISTPTR list) { /* --- find last list element */ return list->cnt-1; /* return index of last element */ } /* find_last() */ /*--------------------------------------------------------------------*/ POSITION next (LISTPTR list, POSITION pos) { /* --- go to next list element */ if (pos >= list->cnt -1) /* if at or beyond end of vector, */ return -1; /* return illegal index */ return (pos < 0) ? 0 : pos+1; /* otherwise return successor index */ } /* next() */ /*--------------------------------------------------------------------*/ int get (LISTPTR list, POSITION pos) { /* --- get datum from a list element */ return ((pos >= 0) && (pos < list->cnt)) ? list->data[pos] : 0; /* check index and return datum */ } /* get() */ /* or (for an illegal index) 0 */ /*--------------------------------------------------------------------*/ LISTPTR insert (LISTPTR list, POSITION pos, int datum) { /* --- insert a datum into a list */ int i; /* loop variable (vector index) */ if (list->cnt >= VECSIZE) /* if the vector is full, */ return NULL; /* abort the function */ for (i = list->cnt; --i > pos; ) /* shift up elements and */ list->data[i+1] = list->data[i]; /* thus empty element at pos+1 */ list->data[pos+1] = datum; /* enter new datum into vector */ list->cnt++; /* increment list element counter */ return list; /* return the modified list */ } /* insert() */ /*--------------------------------------------------------------------*/ LISTPTR delete (LISTPTR list, int datum) { /* --- delete a datum from a list */ int i; /* loop variable (vector index) */ for (i = 0; i < list->cnt; i++) if (list->data[i] == datum) /* traverse elements of vector */ break; /* and find index of datum */ if (i >= list->cnt) /* if datum not found, */ return list; /* return unchanged list */ while (++i < list->cnt) /* shift down following elements */ list->data[i-1] = list->data[i]; /* to close the gap */ list->cnt--; /* decrement list element counter */ 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 (vector version)\n", argv[0]); printf("type l for a list of commands\n"); list = create_list(); /* create an integer list */ if (!list) { printf("%s: not enough memory\n", argv[0]); return -1; } 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() */ /*---------------------------------------------------------------------- Note that the function `main' of this program differs from the function `main' of the program `intlists.c' only in the startup message printed and the additional line after `create_list', which is necessary here, since there may not be enough memory to create the vector, whereas an empty list can always be created. The latter difference vanishes, if an additional structure holding a pointer to the first element and maybe some other information about the list (e.g. the number of elements) is used, which needs to be allocated in the function `create_list'. ----------------------------------------------------------------------*/