/*
* stack.h
*/
#ifndef STACK_H
#define STACK_H
/*
* typedef item_t as const char*, or int,
* or float, or others.
*/
typedef float item_t;
extern void push(item_t);
extern item_t pop(void);
extern int is_empty();
#endif
/*
* stack.c ---- Full stack.
*/
#include "stack.h"
static item_t stack[512];
static int top = -1;
void push(item_t c)
{
stack[++top] = c;
}
item_t pop(void)
{
return (stack[top--]);
}
int is_empty()
{
return top == -1;
}
/*
* stack.c ---- Empty stack.
*/
#include "stack.h"
static item_t stack[512];
static int top = 0;
void push(item_t c)
{
stack[top++] = c;
}
item_t pop(void)
{
return (stack[--top]);
}
int is_empty()
{
return top == 0;
}
/*
* binary tree.
*/
typedef struct node *link;
struct node {
char item;
link l, r;
};
link NODE(char item)
{
link t = malloc(sizeof *t);
t->item = item;
t->l = t->r = NULL;
return t;
}
link tree_init(char VLR[], char LVR[], int n)
{
link t;
int k;
if (n <= 0)
return NULL;
for (k = 0; VLR[0] != LVR[k]; k++)
;
t = NODE(VLR[0]);
t->l = tree_init(VLR + 1, LVR, k);
t->r = tree_init(VLR + 1 + k, LVR + 1 + k, n - k - 1);
return t;
}
void pre_order(link x)
{
if (!x)
return;
printf("%c", x->item);
pre_order(x->l);
pre_order(x->r);
}
void in_order(link x)
{
if (!x)
return;
in_order(x->l);
printf("%c", x->item);
in_order(x->r);
}
void post_order(link x)
{
if (!x)
return;
post_order(x->l);
post_order(x->r);
printf("%c", x->item);
}
int count(link x)
{
if (!x)
return 0;
return 1 + count(x->l) + count(x->r);
}
int depth(link x)
{
int dl, dr;
if (!x)
return 0;
dl = depth(x->l);
dr = depth(x->r);
return 1 + (dl > dr ? d1 : dr);
}
/*
* huffman coding.
*/
typedef struct node *link;
/*
* f -- frequency.
*/
struct node
{
int f;
link l, r;
};
int N;
link *h;
link new_node(int f, link l, link r)
{
link t = malloc(sizeof *t);
t->f = f;
t->l = l;
t->r = r;
return t;
}
void get_freq()
{
int i;
int f;
scanf("%d",&N);
h = malloc(N * sizeof(link));
for(i = 0;i <N; i++)
{
scanf("%d",&f);
h[i] = new_node(f, NULL, NULL);
}
h--;
}
void swap(int i, int j)
{
link tmp = h[i];
h[i] = h[j];
h[j] = tmp;
}
int less(int i, int j)
{
return h[i]->f < h[j]->f;
}
void sift_down(int k, int n)
{
int j;
while(2 * k <= n)
{
j = 2 * k;
if(j + 1 <= n && less(j + 1, j))
j++;
if(!less(j, k)) break;
swap(k, j);
k = j;
}
}
void sift_up(int k)
{
int j;
while (k > 1)
{
j = k / 2;
if (!less(k,j)) break;
swap(k,j);
k = j;
}
}
void pq_init()
{
int i;
for (i = N / 2; i >= 1; i--)
{
sift_down(i,N);
}
}
link get_min()
{
swap(1,N);
sift_down(1,--N);
return h[N+1];
}
void insert(link t)
{
h[++N] = t;
sift_up(N);
}
void pre_order(link t)
{
if (t)
{
printf("(");
printf("%d",t->f);
pre_order(t->l);
pre_order(t->r);
printf(")");
}
else
printf("()");
}
int main(void)
{
get_freq();
pq_init();
while (N > 1)
{
link t1 = get_min();
link t2 = get_min();
insert(new_node(t1->f + t2->f,t1,t2));
}
printf("\\tree ");
pre_order(h[1]);
puts(" ");
return 0;
}
/*
* list.h
*/
struct _list_t{
struct _list_t *next;
void *data;
};
typedef struct _list_t list_t;
/* initialize a list */
void list_init(list_t **list);
/*destroy a list */
void list_destroy(list_t **list);
/*
* list.c
*/
void list_init(list_t **list)
{
*list=(list_t*)malloc(sizeof(list_t));
memset(*list,0,sizeof(list_t));
}
void list_destroy(st_t **list)
{
free(*list);
*list=NULL;
}
/*
*
*/
/**
* circular linked list.
*/
struct list_head {
struct list_head *next, *prev;
};
void list_head_init(struct list_head * ptr) {
ptr->next = ptr;
ptr->prev = ptr;
}
/**
* Insert a new entry between two known consecutive entries.
*/
void list_add(struct list_head * new, struct list_head * prev,
struct list_head * next)
{
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;
}
/**
* Delete a list entry by making the prev/next entries
* point to each other.
*/
void list_del(struct list_head * prev, struct list_head * next)
{
next->prev = prev;
prev->next = next;
}
/**
* list_empty - tests whether a list is empty
* @head: the list to test.
*/
int list_empty(struct list_head *head)
{
return head->next == head;
}
/**
* list_splice - join two lists
* @list: the new list to add.
* @head: the place to add it in the first list.
*/
void list_splice(struct list_head *list, struct list_head *head)
{
struct list_head *first = list->next;
if (first != list) {
struct list_head *last = list->prev;
struct list_head *at = head->next;
first->prev = head;
head->next = first;
last->next = at;
at->prev = last;
}
}
/**
* list_entry - get the struct for this entry
* @ptr: the &struct list_head pointer.
* @type: the type of the struct this is embedded in.
* @member: the name of the list_struct within the struct.
*/
#define list_entry(ptr, type, member) \
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
/**
* list_for_each - iterate over a list
* @pos: the &struct list_head to use as a loop counter.
* @head: the head for your list.
*/
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
/*
* unidirectionl (or single) linked list.
*/
typedef char* item_t; //int
typedef struct node *link;
struct node {
item_t item;
link next;
};
link head;
link NODE(item_t item, link next)
{
link t = malloc(sizeof *t);
t->item = item;
t->next = next;
return t;
}
/*
* insert q behind p.
*/
void insert(link p, link q)
{
q->next = p->next;
p->next = q;
}
/*
* delete q which is behind p.
*/
void delete(link p, link q)
{
p->next = q->next;
free(q);
}
/*
* sort the list '*head'.
*/
void list_sort(link *head)
{
struct node new_head;
link phead, pnew, t, u, x;
phead = *head;
pnew = &new_head;
pnew->next = NULL;
for (t = phead->next; t != NULL; t = u) {
u = t->next;
for (x = pnew; x->next != NULL; x = x->next)
if(x->next->item > t->item)
break;
t->next = x->next;
x->next = t;
}
*head = pnew;
}
/*
* bidirectional linked list.
*/
typedef char* item_t; //int
typedef struct node *link;
struct node {
item_t item;
link prev;
link next;
}
/*
* static linked list.
*/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>
#define MAX_N 4096
#define N 8
typedef struct {
int item;
int next;
} node;
node *L;
int head, avail;
void init_list(int n)
{
int i;
L = malloc(n*sizeof(*L));
for (i=0; i<n-1; i++) L[i].next = i+1;
L[i].next = -1;
avail = 0;
}
int destroy_list(int head)
{
int i, j;
for (i = j = head; i != -1; j = i, i =L[i].next)
if (it)
}
int new_node(int item, int next)
{
int i = avail;
avail = L[avail].next;
L[i].item = item;
L[i].next = next;
return i;
}
void free_node(int k)
{
L[k].next = avail;
avail = k;
}
int create_list()
{
head = new_node(-INT_MAX, -1);
}
void insert_node(int item)
{
int i, j;
for (i=j=head; i!=-1; j=i, i=L[i].next)
if (item<L[i].item) break;
L[j].next = new_node(item, i);
}
void remove_node(int item)
{
int i, j;
for (i=j=head; i!=-1; j=i, i=L[i].next)
if (item==L[i].item) break;
if (i==-1) return;
L[j].next = L[i].next;
free_node(i);
}
void print_list()
{
int i;
for (i=L[head].next; i!=-1; i=L[i].next)
printf("%3d", L[i].item);
printf("\n");
}
int main()
{
int i; int k;
srand(time(NULL));
init_list(MAX_N);
create_list();
for (i=0; i<N; i++)
insert_node(rand()%100);
print_list();
for (k=L[head].next, i=0; i<3; i++) k=L[k].next;
remove_node(L[k].item);
print_list();
return 0;
}
/*
* josephus.c
*/
typedef struct node *link;
struct node {int item; link next;};
link NODE(int item, link next)
{
link t = malloc(sizeof(*t));
t->item = item;
t->next = next;
return t;
}
int main(int argc, char *argv[])
{
int i, N = atoi(argv[1]), M = atoi(argv[2]);
link t = NODE(1, NULL);
t->next = t;
for (i = 2; i <= N; i++)
t = t->next = NODE(i, t->next);
while (t != t->next) {
for (i = 1; i < M; i++)
t = t->next;
printf("%d\n", t->next->item);
t->next = t->next->next;
}
printf("%d\n", t->item);
return 0;
}
/* vector or matrix */
typedef struct node *link;
struct node {
char item;
link next;
link front;
};
typedef struct {
link head;
link tail;
} *vector_t;
link NODE(int item, link front, link next)
{
link t = malloc(sizeof *t);
t->item = item;
t->front = front;
t->next = next;
return t;
}
vector_t vector_init()
{
vector_t p = malloc(sizeof *p);
p->head = p->tail = NODE(0, NULL, NULL);
}
void vector_read(vector_t v, char *str)
{
int i, n;
n = strlen(str);
for (i = 0; i < n; i++)
v->tail = v->tail->next = NODE(str[i], v->tail, NULL);
}
vector_t vector_add(vector_t v1, vector_t v2)
{
int n, flag = 0;
char c;
vector_t v = vector_init();
link t1 = v1->tail;
link t2 = v2->tail;
while (t1->front->front != NULL && t2->front->front != NULL) {
n = (t1->item - '0') + (t2->item - '0') + flag;
if (n >= 10)
flag = 1;
else
flag = 0;
c = n - 10 * flag + '0';
v->head->next = NODE(c, v->head, v->head->next);
t1 = t1->front;
t2 = t2->front;
}
return v;
}
void vector_print(vector_t v)
{
link t;
for (t = v->head->next; t->next != NULL; t = t->next)
printf("%c", t->item);
printf("%c", t->item);
printf("\n");
}