scottmyers - Tumblr blog

scottmyers · 7 years ago

Text

Tree Algorithms in C

Here are some more exercises from Algorithms in C. These are from the chapter on trees.

First up:

Write a recursive program to draw a binary tree so that the root appears at the center of the page, the root of the left subtree is at the center of the left half of the page, etc.

#include <stdbool.h> #include <stdio.h> #include <stdlib.h>

// right boundary; left boundary is assumed to be 0 #define MAX 10

struct node { char data; struct node *l, *r; };

struct node *A, *B, *C, *D, *E, *Z;

void draw(struct node *p, int pos); void init_tree(void); void terminate(const char *msg); void traverse(struct node *p, int l, int r);

int main(void) { /* | A | | B C | |D E| */

// CREATE TREE NODES init_tree(); // TRAVERSE traverse(A, 0, MAX); // CLEAN UP free(A); free(B); free(C); free(D); free(E); free(Z); return 0; }

void draw(struct node *p, int pos) { for (int i = 0; i < pos; i++) printf(" "); printf("%c\n", p->data); }

void init_tree(void) { Z = malloc(sizeof(*Z)); A = malloc(sizeof(*A)); B = malloc(sizeof(*B)); C = malloc(sizeof(*C)); D = malloc(sizeof(*D)); E = malloc(sizeof(*E));

if (A == NULL || B == NULL || C == NULL || D == NULL || E == NULL || Z == NULL) terminate("could not initialize tree");

Z->data = '0'; Z->l = Z; Z->r = Z;

A->data = 'A'; A->l = B; A->r = C; B->data = 'B'; B->l = D; B->r = Z; C->data = 'C'; C->l = Z; C->r = E; D->data = 'D'; D->l = Z; D->r = Z; E->data = 'E'; E->l = Z; E->r = Z; }

void terminate(const char *msg) { fprintf(stderr, "%s\n", msg); exit(EXIT_FAILURE); }

void traverse(struct node *p, int l, int r) { int m = (l+r) / 2; draw(p, m); if (m > l && m < MAX) { if (p->l != Z) traverse(p->l, 0, m-1); if (p->r != Z) traverse(p->r, m+1, MAX); } }

==============================================================

Second up:

Write a recursive program to compute the external path length of a binary tree

#include <stdbool.h> #include <stdio.h> #include <stdlib.h>

struct node { char data; struct node *l, *r; };

struct node *A, *B, *C, *D, *E, *F, *Z; int epl, h;

void init_tree(void); void terminate(const char *msg); void traverse(struct node *p); void visit(struct node *p, int level);

int main(void) { /* | A | | B C | |D E| | F | */

// CREATE TREE NODES init_tree();

// INIT EXTERNAL PATH LENGTH epl = 0;

// INIT HEIGHT TO -1 SO ROOT OF TREE IS AT LEVEL 0 h = -1;

// TRAVERSE traverse(A);

// CLEAN UP free(A); free(B); free(C); free(D); free(E); free(Z); return 0; }

void visit(struct node *p, int level) { printf("path length for external node %c: %d\n", p->data, level); epl += level; }

void init_tree(void) { Z = malloc(sizeof(*Z)); A = malloc(sizeof(*A)); B = malloc(sizeof(*B)); C = malloc(sizeof(*C)); D = malloc(sizeof(*D)); E = malloc(sizeof(*E)); F = malloc(sizeof(*F));

if (A == NULL || B == NULL || C == NULL || D == NULL || E == NULL || F == NULL || Z == NULL) terminate("could not initialize tree");

Z->data = '0'; Z->l = Z; Z->r = Z;

A->data = 'A'; A->l = B; A->r = C; B->data = 'B'; B->l = D; B->r = Z; C->data = 'C'; C->l = Z; C->r = E; D->data = 'D'; D->l = Z; D->r = Z; E->data = 'E'; E->l = F; E->r = Z; F->data = 'F'; F->l = Z; F->r = Z; }

void terminate(const char *msg) { fprintf(stderr, "%s\n", msg); exit(EXIT_FAILURE); }

void traverse(struct node *p) { h++; if (p != Z) { if (p->l == Z & p->r == Z) visit(p, h); traverse(p->l); traverse(p->r); } h--; }

#programming #computers #algorithms #hackers #hacking

2 notes · View notes

scottmyers · 7 years ago

Text

Josephus Problem Using an Array in C

The obvious data structure to use in this problem is a circular linked list. But the book, Algorithms in C, asks you to do it with an array. Here’s my implementation.

https://github.com/scottmurs/C_Programs/blob/master/algorithms_in_c/3-4.c

/* * ===================================================================================== * * Filename: 3-4.c * * Description: write a program to solve the Josephus problem, using an array * instead of a linked list * * Version: 1.0 * Created: 01/03/2018 03:28:13 AM * Revision: none * Compiler: gcc * * Author: scott myers * Organization: * * ===================================================================================== */ #include <stdio.h> #include <stdlib.h> #define N 10 void init_arr(void); // initialize the array with N members void execute(int n); // execute the nth member starting and index start int len_arr(void); // return the length of the array void reorder_arr(void); // reorder the array such that the member at index n is removed void print_arr(void); static int arr[N]; static int len = N, start = 0; int main(void) { // init array init_arr(); while (len_arr() > 1) { print_arr(); // execute one execute(5); // rebuild array reorder_arr(); } // print remaining member print_arr(); return 0; } void init_arr(void) { for (int i = 0; i < N; i++) arr[i] = i; } void execute(int n) { int i; i = (start + n-1) % len; arr[i] = -1; start = i; } int len_arr(void) { return len; } void reorder_arr(void) { int i; // find index with value == 0 for (i = 0; i < len && arr[i] != -1; i++) ; // copy i+1 into i until i == len for (i++; i < len; i++) arr[i-1] = arr[i]; // decrement len len--; } void print_arr(void) { printf("len: %d\n", len); for (int i = 0; i < len; i++) printf("%d ", arr[i]); printf("\n"); }

#C Programming #Algorithms #Data Structures #hacking

2 notes · View notes