// llinserth.c: use the insertTail and insertHead functions to build // a linked list containing strings #include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #define QUIT "." typedef struct node { char *data; struct node *next; } NodeT; NodeT *insertTail(NodeT *, char *); NodeT *insertHead(NodeT *, char *); NodeT *makeNode (char *); void printList(NodeT *); void freeList(NodeT *); int main(void) { NodeT *all = NULL; char data[BUFSIZ]; printf("Enter a string: "); while (scanf("%s", data) == 1 && strcmp(data, QUIT) != 0) { if (isupper(*data) || islower(*data)) { all = insertHead(all, data); } else { all = insertTail(all, data); } printf("Enter a string: "); } if (all) { printf("Finished: list is "); all = insertTail(all, QUIT); printList(all); freeList(all); } else { printf("Finished\n"); } return EXIT_SUCCESS; } NodeT *makeNode (char *s) { // create new node with data NodeT *new = (NodeT *)malloc(sizeof(NodeT)); assert (new != NULL); int lengths = strlen(s); // need to find length of string for malloc new->data = (char *)malloc((lengths+1)*sizeof(char)); // +1 for the '\0' assert (new->data != NULL); strcpy(new->data, s); // copy includes '\0' new->next = NULL; // set the next pointer to NULL for now return new; } NodeT *insertHead(NodeT *head, char *s) { // create new node with data NodeT *new = makeNode(s); new->next = head; return new; } NodeT *insertTail(NodeT *head, char *s) { // create new node with data NodeT *new = makeNode(s); new->next = NULL; if (head != NULL) { // check if at least 1 node NodeT *cur; cur = head; // start at the head while (cur->next != NULL) { // this must be defined cur = cur->next; } cur->next = new; // cur->next was NULL } else { head = new; } return head; } void printList(NodeT *head) { // changed from llbuild.c to print %s instead of %d NodeT *cur; cur = head; while (cur != NULL) { printf("%s", cur->data); cur = cur->next; if (cur != NULL) { printf("->"); } } if (head != NULL) { putchar('\n'); } } void freeList(NodeT *head) { // changed from llbuild.c to free dynamic string too NodeT *cur; cur = head; while (cur != NULL) { NodeT *tmp = cur->next; // remember next node before freeing this node free(tmp->data); // first, free string ... free(tmp); // ... then free struct cur = tmp; } } |
// rotate.c: rotate a string of characters on the command-line #include <stdio.h> #include <stdlib.h> #include <string.h> typedef enum {left, right, undefined} Direction; int main(int argc, char *argv[]) { char *string; // will point to the char string to be rotated int retval = EXIT_SUCCESS; // process the command-line arguments Direction dir = undefined; // 'undef' is print a usage message if (argc == 2) { // there is no command-line option string = argv[1]; // argv[1] is the string dir = right; // right rotate is default } if (argc == 3) { // there is a command-line option if (!strcmp(argv[1], "-l")) { // it must be this ... string = argv[2]; dir = left; } else if (!strcmp(argv[1], "-r")) { // ... or this string = argv[2]; dir = right; } } // the program body starts here if (dir == right) { char *plastchar = string + strlen(string) - 1; // ptr to last char char lastchar = *plastchar; // remember last char *plastchar = '\0'; // overwrite last char by nul printf("%c%s\n", lastchar, string); // print last char and then the rest } else if (dir == left) { char *psecchar = string + 1; // pointer to second char printf("%s%c\n", psecchar, *string); // print first char at back of string } else { fprintf(stderr, "Usage: %s [-r|-l] string\n", argv[0]); retval = EXIT_FAILURE; } return retval; } |
// llrotate1.c: rotate a string of characters on the command-line // using a reLinking of a linked list. #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <string.h> #define SWITCHLEFT "-l" #define SWITCHRIGHT "-r" typedef struct _node { char data; struct _node *next; } NodeT; typedef enum {left, right, undefined} Direction; NodeT *rightRotateList(NodeT *); NodeT *leftRotateList(NodeT *); NodeT *buildList(char *); void printList(NodeT *); void freeList(NodeT *); int main(int argc, char *argv[]) { NodeT *head; char *string; // will point to the char string to be rotated int retval = EXIT_SUCCESS; // PROCESS THE COMMAND-LINE ARGUMENTS Direction dir = undefined; // default is print a usage message if (argc == 2) { // there is no command-line option string = argv[1]; // argv[1] is the string dir = right; // right rotate is default } if (argc == 3) { // there is a command-line option if (strcmp(argv[1], SWITCHLEFT) == 0) { // it must be this ... string = argv[2]; dir = left; } else if (strcmp(argv[1], SWITCHRIGHT) == 0) { // ... or this string = argv[2]; dir = right; } } // PROGRAM BODY STARTS HERE if (dir == left || dir == right) { head = buildList(string); printList(head); if (dir == right) { head = rightRotateList(head); } else { head = leftRotateList(head); } printList(head); freeList(head); } else { fprintf(stderr, "Usage: %s [-r|-l] string\n", argv[0]); retval = EXIT_FAILURE; } return retval; } NodeT *rightRotateList(NodeT *head) { /* head | V 0->1->2->3->4 last | V 0->1->2->3 4 ^ | | | ------------- */ NodeT *penu; // penultimate node NodeT *last; // last node last = head; if ((head != NULL && // cannot rotate NULL node head->next != NULL)) { // cannot rotate a single node penu = head; // start at the head ... while (penu->next->next != NULL) { // ... find penultimate node penu = penu->next; } last = penu->next; // identify last node penu->next = NULL; // penu is new end of list last->next = head; // last points to head node } return last; // return last node as new head } NodeT *leftRotateList(NodeT *head) { /* head | V 0->1->2->3->4 second last | | V V 0 1->2->3->4 ^ | | | ------------- */ NodeT *second; // second node NodeT *last; // last node if ((head != NULL && // cannot rotate NULL node head->next != NULL)) { // cannot rotate a single node last = head; // start at the head node ... while (last->next != NULL) { // ... find last node last = last->next; } last->next = head; // last points back to head second = head->next; // this is the second node head->next = NULL; // head node is new last node } return second; // return second node as new head } NodeT *buildList(char *string) { NodeT *head = NULL; NodeT *prev = NULL; char *p; for (p = string; *p != '\0'; p++) { NodeT *n = (NodeT *)malloc(sizeof(NodeT)); assert(n != NULL); n->data = *p; n->next = NULL; if (p == string) { // if first iteration ... head = n; // ... it is the head } else { prev->next = n; // back-patch the prev node } prev = n; // this node becomes prev } return head; } void printList(NodeT *headn) { NodeT *n; for (n = headn; n != NULL; n = n->next) { if (n != headn) { printf("->"); } printf("%c", n->data); } putchar('\n'); } |
// llrotate2.c: rotate a string of characters on the command-line // using data copies #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <string.h> #define SWITCHLEFT "-l" #define SWITCHRIGHT "-r" typedef struct _node { char data; struct _node *next; } NodeT; typedef enum {left, right, undefined} Direction; void rightRotateList(NodeT *); void leftRotateList(NodeT *); NodeT *buildList(char *); void printList(NodeT *); void freeList(NodeT *); int main(int argc, char *argv[]) { NodeT *head; char *string; // will point to the char string to be rotated int retval = EXIT_SUCCESS; // PROCESS THE COMMAND-LINE ARGUMENTS Direction dir = undefined; // default is print a usage message if (argc == 2) { // there is no command-line option string = argv[1]; // argv[1] is the string dir = right; // right rotate is default } if (argc == 3) { // there is a command-line option if (strcmp(argv[1], SWITCHLEFT) == 0) { // it must be this ... string = argv[2]; dir = left; } else if (strcmp(argv[1], SWITCHRIGHT) == 0) { // ... or this string = argv[2]; dir = right; } } // PROGRAM BODY STARTS HERE if (dir == left || dir == right) { head = buildList(string); printList(head); if (dir == right) { rightRotateList(head); // notice no head can be returned } else { leftRotateList(head); // notice no head can be returned } printList(head); freeList(head); } else { fprintf(stderr, "Usage: %s [-r|-l] string\n", argv[0]); retval = EXIT_FAILURE; } return retval; } void rightRotateList(NodeT *head) { NodeT *step; if ((head != NULL && // cannot rotate NULL node head->next != NULL)) { // cannot rotate a single node int prevdata = head->data; for (step=head->next; step != NULL; step=step->next) { // traverse int tmp = step->data; // store current data step->data = prevdata; // copy prev data to the RIGHT prevdata = tmp; // remember current data } head->data = prevdata; // copy prevdata==last_node's_data to head } } void leftRotateList(NodeT *head) { NodeT *step; if ((head != NULL && // cannot rotate NULL node head->next != NULL)) { // cannot rotate a single node int headdata = head->data; // remember the head data NodeT *prev = head; for (step=head->next; step != NULL; step=step->next) { // traverse prev->data = step->data; // copy step->data to the LEFT prev = step; // need to rememebr prev node } // prev points to last node prev->data = headdata; // head data is copied to last node } } |