// 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
}
}
|