// llmax.c: create a linked list from numbers on stdin,
// and print all nodes starting with the maximum value in the list
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct node {
int data;
struct node *next;
} NodeT;
NodeT *maxstart(NodeT *);
NodeT *insertTail(NodeT *, int);
void printList(NodeT *);
void freeList(NodeT *);
int main(void) {
NodeT *lil = NULL;
int dataGood = 1;
int retval = EXIT_SUCCESS;
int number;
if (scanf("%d", &number) == 1) {
int n;
for (n=0; n<number && dataGood; n++) {
int data;
if (scanf("%d", &data) == 1) {
lil = insertTail(lil, data);
} else {
fprintf(stderr, "Data missing\n");
freeList(lil);
dataGood = 0;
}
}
if (n > 0 && dataGood) {
printf("Original list = ");
printList(lil); // original list
lil = maxstart(lil);
printf("Truncated list = ");
printList(lil); // truncated list
freeList(lil);
}
} else {
fprintf(stderr, "No data\n");
dataGood = 0;
}
if (!dataGood) {
retval = EXIT_FAILURE;
}
return retval;
}
NodeT *maxstart(NodeT *head) {
// returns pointer to first occurence of largest list element
NodeT *maxp = NULL;
NodeT *cur;
int max;
if (head != NULL) {
maxp = head;
max = maxp->data;
cur = head->next;
while (cur != NULL) {
if (cur->data > max) {
maxp = cur;
max = maxp->data;
}
cur = cur->next;
}
}
return maxp;
}
NodeT *insertTail(NodeT *head, int d) {
// create new node with data
NodeT *new = malloc(sizeof(NodeT));
assert(new != NULL);
new->data = d;
new->next = NULL;
if (head != NULL) { // check at least 1 node
NodeT *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; // if no list, list = new
}
return head;
}
void printList(NodeT *head) {
NodeT *cur = head;
while (cur != NULL) {
printf("%d", cur->data);
cur = cur->next;
if (cur != NULL) {
printf("->");
}
}
putchar('\n');
}
void freeList(NodeT *head) {
NodeT *cur = head;
while (cur != NULL) {
NodeT *tmp = cur->next;
free(cur);
cur = tmp;
}
}
|
// llunique.c: create a linked list from numbers on stdin,
// and remove all elements that occur more than once in the list
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct node {
int data;
struct node *next;
} NodeT;
NodeT *uniquifyList(NodeT *);
int find(NodeT *, int);
NodeT *destroy(NodeT *, int);
NodeT *insertTail(NodeT *, int); // as above
void printList(NodeT *); // as above
void freeList(NodeT *); // as above
int main(void) {
NodeT *lil = NULL;
int dataGood = 1;
int retval = EXIT_SUCCESS;
int number;
if (scanf("%d", &number) == 1) {
int n;
for (n=0; n<number && dataGood; n++) {
int data;
if (scanf("%d", &data) == 1) {
lil = insertTail(lil, data);
} else {
fprintf(stderr, "Data missing\n");
freeList(lil);
dataGood = 0;
}
}
if (n > 0 && dataGood) {
printf("Original list = ");
printList(lil); // original list
lil = uniquifyList(lil);
if (lil == NULL) {
printf("Unique list is empty\n");
} else {
printf("Unique list = ");
printList(lil); // uniquified list
freeList(lil);
}
}
} else {
fprintf(stderr, "No data\n");
dataGood = 0;
}
if (!dataGood) {
retval = EXIT_FAILURE;
}
return retval;
}
int find(NodeT *head, int v) {
int found = 0;
NodeT *cur = head;
while (cur != NULL && !found) {
found = (cur->data == v);
cur = cur->next;
}
return found;
}
NodeT *destroy(NodeT *head, int v) {
// destroy all occurrences of v (recursive version)
NodeT *retval;
if (head == NULL) {
retval = NULL;
} else {
head->next = destroy(head->next, v); // destroy recursively
if (head->data == v) { // destroy head too?
retval = head->next;
free(head);
} else {
retval = head;
}
}
return retval;
}
NodeT *uniquifyList(NodeT *head) {
// remove all elements that occur more than once (recursive version)
if (head != NULL) {
if (find(head->next, head->data)) {
head = uniquifyList(destroy(head, head->data));
} else {
head->next = uniquifyList(head->next);
}
}
return head;
}
|
Anyone with a better or more interesting solution?
// bfsTreeQ.c: input and print a BST twice
// - once in normal pretty-print fashion (note, this is infix)
// - once in BFS order
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "quack.h"
typedef struct node {
int value;
struct node *left;
struct node *right;
} Node;
typedef Node *Tree;
Node *newTreeNode(int); // make a new BST node
Tree insertTree(Tree t, int v); // insert a node 'v' into a BST
void freeTree(Tree t); // free the tree
void printTree(Tree t, int level); // pretty-print a BST in infix order
void printBFS(Tree t); // print nodes of BST in BFS order
int main(int argc, char **argv){
Tree t = NULL;
int i;
int dataGood = 1;
int retval = EXIT_SUCCESS;
if (argc == 1) {
fprintf(stderr, "Usage: %s integers ...\n", argv[0]);
dataGood = 0;
}
for (i=1; dataGood && i<argc; i++) {
int num;
if (sscanf(argv[i], "%d", &num) != 1) {
fprintf(stderr, "Usage: %s integers ...\n", argv[0]);
freeTree(t);
dataGood = 0;
} else {
t = insertTree(t, num);
}
}
if (!dataGood) {
retval = EXIT_FAILURE;
} else {
printTree(t, 0);
printf("BFS order = ");
printBFS(t);
freeTree(t);
}
return retval;
}
void printBFS(Tree t) {
Quack q = createQuack();
qush((int)t, q);
while (!isEmptyQuack(q)) {
t = (Tree)pop(q);
if (t != NULL) {
printf("%d ", t->value);
qush((int)t->left, q);
qush((int)t->right, q);
}
}
putchar('\n');
}
Node *newTreeNode(int v) {
Node *new = (Node *)malloc(sizeof(Node));
assert(new != NULL);
new->value = v;
new->left = NULL;
new->right = NULL;
return new;
}
Tree insertTree(Tree t, int v) {
if (t == NULL) {
t = newTreeNode(v);
} else if (v < t->value) {
t->left = insertTree(t->left, v);
} else if (v > t->value) {
t->right = insertTree(t->right, v);
}
return t;
}
void freeTree(Tree t) { // free in postfix fashion
if (t != NULL) {
freeTree(t->left);
freeTree(t->right);
free(t);
}
}
void printTree(Tree t, int depth) {
if (t != NULL) {
depth++;
printTree(t->left, depth);
int i;
for (i=1; i<depth; i++){
putchar('\t');
}
printf("%d\n", t->value);
printTree(t->right, depth);
}
}
|