C语言

单链表:linkList.h linkList.c

#ifndef LINKLIST_H_INCLUDE
#define LINKLIST_H_INCLUDE
#include <Windows.h>

//什么是链表 是一种动态数组 管理一堆不断变化的元素

typedef struct e{
    void *data;//元素通过一个万能的指针指向代表的数据
    struct e *next;//指向下一个元素
}E, *PE;

//单链表 对象属性:一个元素句柄 元素个数
typedef struct linkList{
    PE handler;//元素的句柄
    int count;//元素的总数
}LinkList, *PLinkList;

//以下是接口

//实例化一个元素 最常用的构造方法:直接指定数据
PE newE(void *);
//实例化一个空链表
PLinkList newLinkList();
//查
PE LinkList_get(PLinkList, int);
//删
BOOL LinkList_del(PLinkList, int);
//改
BOOL LinkList_set(PLinkList, int, PE);
//增
BOOL LinkList_add(PLinkList, int, PE);
//叛空
BOOL LinikList_isEmpty(PLinkList);
//取数量
int LinkList_getCount(PLinkList);

#endif

#include "linkList.h"
#include <stdlib.h>
#include <assert.h>

//实例化一个元素 最常用的构造方法:直接指定数据
PE newE(void *data){
    PE r = NULL;
    r = (PE) malloc(sizeof(E));
    r->data = data;
    r->next = NULL;
    return r;
}
//实例化一个空链表
PLinkList newLinkList(){
    PLinkList r = NULL;
    r = (PLinkList) malloc(sizeof(LinkList));
    r->count = 0;
    r->handler = newE(NULL);
    return r;
}
//查
PE LinkList_get(PLinkList list, int id){//id:[0,n]
    int i = 0;
    PE e = NULL;
    assert(list!=NULL);
    assert(id>=0&&id<=list->count);
    e = list->handler;
    for(i=1;i<=id;i++){
        e = e->next;
    }
    return e;
}
//删
BOOL LinkList_del(PLinkList list, int id){//id[1,n]
    //assert(list);
    //assert(id>=1&&id<=list->count);
    if(!list|| id<1|| id>list->count) return FALSE;
    //id-1->next=id->next
    LinkList_get(list, id-1)->next = LinkList_get(list, id)->next;
    list->count--;
    return TRUE;
}
//改
BOOL LinkList_set(PLinkList list, int id, PE e){//id:[1,n]
    if(!list|| !e|| id<1|| id>list->count) return FALSE;
    e->next = LinkList_get(list, id)->next;
    LinkList_get(list, id-1)->next = e;
    return TRUE;
}
//增
BOOL LinkList_add(PLinkList list, int id, PE e){//id:[1,n+1]=>[1,~)
    assert(list&&e);
    if(id>list->count+1)
        id = list->count+1;
    assert(id>=1&&id<=list->count+1);
    //e连接id-1->next,id-1连接e
    e->next = LinkList_get(list, id-1)->next;
    LinkList_get(list, id-1)->next = e;
    list->count++;
    return TRUE;
}
//叛空
BOOL LinikList_isEmpty(PLinkList list){
    assert(list);
    if(list->count==0)
        return TRUE;
    return FALSE;
}
//取数量
int LinkList_getCount(PLinkList list){
    assert(list);
    return list->count;
}

栈:stack.h stack.c

#ifndef STACK_H_INCLUDE
#define STACK_H_INCLUDE
#include <Windows.h>
#include "linkList.h"
/**
 *对象:栈
 *属性:链表指针 栈帧
 *接口:实例化 入栈 弹栈 取栈顶元素 叛空 取元素数量
 */
typedef struct stack{
    PLinkList list;//链表
    int top;//栈顶
}Stack, *PStack;

//以下为接口

PStack newStack();//实例化一个空栈
BOOL Stack_push(PStack, void*);//入栈
void *Stack_pop(PStack);//弹栈
void *Stack_getTop(PStack);//取栈顶元素但不弹出 相当于将该元素弹栈使用后又入栈
BOOL Stack_isEmpty(PStack);//叛空
int Stack_getCount(PStack);//取栈剩余元素数量


#endif

#include "stack.h"
#include "linkList.h"
#include <assert.h>
#include <stdlib.h>

//实例化一个空栈
PStack newStack(){
    PStack r = NULL;
    r = (PStack) malloc(sizeof(Stack));
    r->top = 0;
    r->list = newLinkList();
    return r;
}
//入栈
BOOL Stack_push(PStack stack, void* data){
    assert(stack);
    //创建一个新元素, 添加到表头(方便弹栈)
    if(LinkList_add(stack->list, 1, newE(data)) ){
        stack->top++;
        return TRUE;
    }
    return FALSE;
}
//弹栈
void *Stack_pop(PStack stack){
    assert(stack);
    if(stack->top>0&&stack->list->count>0){
        PE e = LinkList_get(stack->list, 1);
        if(e){
            stack->top--;;
            LinkList_del(stack->list, 1);
            return e->data;
        }
    }
    return NULL;
}
void *Stack_getTop(PStack stack){
    PE e = NULL;
    assert(stack);
    if(stack->top> 0  && stack->list->count> 0 ){
        e = LinkList_get(stack->list, 1);
    }
    return e? e->data: NULL;
}
//叛空
BOOL Stack_isEmpty(PStack stack){
    return !stack->top;
}
//取栈剩余元素数量
int Stack_getCount(PStack stack){
    assert(stack);
    return stack->top;
}