/*
 * =====================================================================================
 *       Filename:  list.h
 *    Description:  链表ADT
 *
 *        Version:  1.0
 *        Created:  2011年03月19日 20时29分27秒
 *         Author:  hohosd44 (), sd44sd44@yeah.net
 *        Company:  
 * =====================================================================================
 */

typedef int elem_t;

#ifndef _LIST_H_
#define _LIST_H_
#include    <stdio.h>
#include    <stdlib.h>
#include    <stdbool.h>
 
typedef struct node {
    elem_t element;
    struct node *next;
} Node;
 
typedef Node *List;
typedef Node *Position;
 
List initialization(void);
bool isempty(List);
bool islast(Position, List);
Position find(elem_t, List);
Position findprev(elem_t, List);
void deletes(elem_t, List);
void insert(elem_t, List, Position);
void deletelist(List);
bool additem(elem_t, List);
 
#endif
 
List initialization(void)
{
    Position l;
    l = (List) malloc(sizeof(Node));
    if (l == NULL)
        fprintf(stderr, "%s\n", "Out of memory!");
    l->next = NULL;
    return l;
}
 
bool isempty(List l)
{
    return l->next == NULL;
}
 
bool islast(Position y, List l)
{
    return y->next == NULL;
}
 
Position find(elem_t x, List l)
{
    Position tmp;
    tmp = l->next;
    while (tmp != NULL && tmp->element != x)
        tmp = tmp->next;
 
    return tmp;
}
 
Position findprev(elem_t x, List l)
{
    Position tmp;
    tmp = l;
    while (tmp->next != NULL && tmp->next->element != x)
        tmp = tmp->next;
 
    return tmp;
}
 
void deletes(elem_t x, List l)
{
    Position prevpos, tmp;
    prevpos = findprev(x, l);
 
    if (!islast(prevpos, l)) {
        tmp = prevpos->next;
        prevpos->next = tmp->next;
        free(tmp);
    }
}
 
void insert(elem_t x, List l, Position y)
{
    Position tmppos;
    tmppos = (Position) malloc(sizeof(Node));
    if (tmppos == NULL)
        fprintf(stderr, "%s\n", "out of space!!!");
    tmppos->element = x;
    tmppos->next = y->next;
    y->next = tmppos;
}
 
void deletelist(List l)
{
    Position tmppos, tmp2pos;
 
    tmppos = l->next;
    while (tmppos != NULL) {
        tmp2pos = tmppos->next;
        free(tmppos);
        tmppos = tmp2pos;
    }
    free(l);
}
 
bool additem(elem_t x, List l)
{
    Position tmppos = l->next;
    Position newpos;
 
    newpos = (Position) malloc(sizeof(Node));
    if (newpos == NULL) {
        fprintf(stderr, "%s\n", "Out of space!!!");
        return false;
    }
 
    newpos->element = x;
    newpos->next = NULL;
 
    if (tmppos == NULL)
        l->next = newpos;
    else {
        while (tmppos->next != NULL) {
            tmppos = tmppos->next;
        }
        tmppos->next = newpos;
    }
    return true;
 
}

// 双链表ADT
typedef int elem_t;
#ifndef _LIST_H_
#define _LIST_H_
 
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
    elem_t element;
    struct node *prev;
    struct node *next;
} Node;
 
typedef Node *List;
typedef Node *Position;
 
List initialization(void);
bool isempty(List);
bool islast(Position, List);
Position find(int , List);
Position findprev(int, List);
void deletes(elem_t, List);
void insert(elem_t, List, Position);
void deletelist(List);
bool additem(elem_t, List);
 
#endif
 
List initialization(void)
{
    Position l;
    l = (List) malloc(sizeof(Node));
    if (l == NULL)
        fprintf(stderr, "%s\n", "Out of memory!");
    l->prev = NULL;
    l->next = NULL;
    return l;
}
 
bool isempty(List l)
{
    return l->next == NULL;
}
 
bool islast(Position y, List l)
{
    return y->next == NULL;
}
 
Position find(elem_t x, List l)
{
    Position tmp;
    tmp = l->next;
    while (tmp != NULL && tmp->element != x)
        tmp = tmp->next;
 
    return tmp;
}
 
Position findprev(elem_t x, List l)
{
    Position tmp;
    tmp = l;
    while (tmp->next != NULL && tmp->next->element != x)
        tmp = tmp->next;
 
    return tmp;
}
 
void deletes(elem_t x, List l)
{
    Position prevpos, tmp;
    prevpos = findprev(x, l);
 
    if (!islast(prevpos, l)) {
        tmp = prevpos->next;
        prevpos->next = tmp->next;
        tmp->next->prev = prevpos;
        free(tmp);
    }
}
 
void insert(elem_t x, List l, Position y)
{
    Position tmppos;
    tmppos = (Position) malloc(sizeof(Node));
    if (tmppos == NULL)
        fprintf(stderr, "%s\n", "out of space!!!");
    tmppos->element = x;
    tmppos->prev = y;
    tmppos->next = y->next;
    y->next->prev = tmppos;
    y->next = tmppos;
}
 
void deletelist(List l)
{
    Position tmppos, tmp2pos;
 
    tmppos = l->next;
    while (tmppos != NULL) {
        tmp2pos = tmppos->next;
        free(tmppos);
        tmppos = tmp2pos;
    }
    free(l);
}
 
bool additem(elem_t x, List l)
{
    Position tmppos = l->next;
    Position newpos;
 
    newpos = (Position) malloc(sizeof(Node));
    if (newpos == NULL) {
        fprintf(stderr, "%s\n", "Out of space!!!");
        return false;
    }
 
    newpos->element = x;
    newpos->next = NULL;
 
    if (tmppos == NULL) {
        l->next = newpos;
        newpos->prev = l;
    } else {
        while (tmppos->next != NULL) {
            tmppos = tmppos->next;
        }
        tmppos->next = newpos;
        newpos->prev = tmppos;
    }
    return true;
}

/*
 * =====================================================================================
 *       Filename:  stack.c
 *    Description:  栈链表ADT
 *
 *        Version:  1.0
 *        Created:  2011年03月20日 14时17分49秒
 *         Author:  hohosd44 (), sd44sd44@yeah.net
 *        Company:  
 * =====================================================================================
 */

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

#ifndef  _stack_h__INC
#define  _stack_h__INC

typedef int elementtype;

struct node;
typedef struct node Node;
typedef Node *Stack;
typedef Node *Position;

bool isempty(Stack s);
Stack creatstack(void);
void freestack(Stack s);
void makeempty(Stack s);
void push(elementtype x, Stack s);
elementtype pop(Stack s);

#endif /* ----- #ifndef _stack_h__INC  ----- */

struct node {
	elementtype x;
	Position next;
};

bool isempty(Stack s)
{
	return s->next == NULL;
}

Stack creatstack(void)
{
	Stack s;
	s = (Position) malloc(sizeof(Node));

	if (s == NULL) {
		fprintf(stderr, "Out of space!!!");
		exit(1);
	}

	s->next = NULL;
	makeempty(s);
	return s;
}

void freestack(Stack s)
{
	makeempty(s);
	free(s);
}

void makeempty(Stack s)
{
	if (s == NULL) {
		fprintf(stderr, "Out of space!!!");
		exit(1);
	}
	while (!isempty(s))
		pop(s);
}

void push(elementtype x, Stack s)
{
	Position tmp;
	tmp = (Position) malloc(sizeof(Node));
	tmp->x = x;
	tmp->next = s->next;
	s->next = tmp;
}

elementtype pop(Stack s)
{
	Position tmp1;
	elementtype tmpdata;

	if (!isempty(s)) {
		tmpdata = s->next->x;
		tmp1 = s->next;
		s->next = s->next->next;
		free(tmp1);
		return tmpdata;
	} else {
		fprintf(stderr, "Empty Stack!!");
		exit(1);
	}
}