栈

struct stack {
    int top;
    int data[100];
};

bool stack_empty(stack s) { //判断是否为空，若空，返回true，不空返回false
    if(s.top == 0)
        return true;
    else
        return false;
}

stack_push(stack s, int key) { //入栈
    s.top = s.top + 1；
    s.data[s.top] = key;
}

stack_pop(stack s) { //出栈
    if(s.top == 0) {
        printf("underflow");
    }
    else {
        s.top = s.top - 1;
        return s.data[s.top+1];
    }
}

队列 – 循环

struct queue {
    int head;
    int tail;
    int length;
    int data[length+1];
};

void enqueue(queue Q, int key) { //入队
    Q.data[Q.tail] = key;
    if(Q.tail == Q.length) {
        Q.tail = 1;
    }
    else {
        Q.tail = Q.tail + 1;
    }
}

int dequeue(queue Q){ //出队
    int temp = Q.data[Q.head];
    if(Q.head == Q.length) {
        Q.head = 1;
    }
    else {
        Q.head = Q.head + 1;
    }
    return temp;
}

链表 – 双向

struct list {
    list *prev;
    int key;
    list *next;    
};

list *list_search(list *l, int key) { //查找
    while(l->key != key && l->next != null) {
        l = l->next;
    }
    return l;
}

void list_insert(list *l, list *x) { //表头插入
    x->next = l;
    if(l != NULL) {
        l->prev = x;
    }
    x->prev = NULL;
    l = x;
}


void list_delete(list *l, list x) { //删除
    if(x->prev != NULL) {
        x->prev->next = x->next;
    }
    else {
        l = l->next;
    }
    if(x->next != NULL) {
        x->next->prev = x->prev
    }
}

有哨兵的双向循环列表

哨兵是个哑对象，为空，位于表头和表尾之间，

struct list {
    list *prev;
    int key;
    list *next;    
};

list *list_search(list *l, int key) { //查找
    l = l->next;
    while(l->key != key && l->next != null) {
        l = l->next;
    }
    return l;
}

void list_insert(list *l, list x) { //表头插入
    x->next = l->next;
    l->next->prev = x;
    l->next = x;
    x->prev = l;
}


void list_delete(list *l, list x) { //删除
    if(x->prev != NULL) {
        x->prev->next = x->next;
    }
    else {
        l = l->next;
    }
    if(x->next != NULL) {
        x->next->prev = x->prev
    }
}

指针和对象的实现

有些语言不支持指针和对象数据类型时，为了实现链式数据结构，我们将利用数组和数组下标来构造对象和指针

1.对象的多数组表示

2.对象的单数组表示

为了读取next的值，需要加偏移量1，读取prev的值，需要加偏移量2