单链表: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
linkList.h
#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 = ;
r->handler = newE(NULL);
return r;
}
//查
PE LinkList_get(PLinkList list, int id){//id:[0,n]
int i = ;
PE e = NULL;
assert(list!=NULL);
assert(id>=&&id<=list->count);
e = list->handler;
for(i=;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<|| id>list->count) return FALSE;
//id-1->next=id->next
LinkList_get(list, id-)->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<|| id>list->count) return FALSE;
e->next = LinkList_get(list, id)->next;
LinkList_get(list, id-)->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+)
id = list->count+;
assert(id>=&&id<=list->count+);
//e连接id-1->next,id-1连接e
e->next = LinkList_get(list, id-)->next;
LinkList_get(list, id-)->next = e;
list->count++;
return TRUE;
}
//叛空
BOOL LinikList_isEmpty(PLinkList list){
assert(list);
if(list->count==)
return TRUE;
return FALSE;
}
//取数量
int LinkList_getCount(PLinkList list){
assert(list);
return list->count;
}
linkList.c
栈: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
stack.h
#include "stack.h"
#include "linkList.h"
#include <assert.h>
#include <stdlib.h> //实例化一个空栈
PStack newStack(){
PStack r = NULL;
r = (PStack) malloc(sizeof(Stack));
r->top = ;
r->list = newLinkList();
return r;
}
//入栈
BOOL Stack_push(PStack stack, void* data){
assert(stack);
//创建一个新元素, 添加到表头(方便弹栈)
if(LinkList_add(stack->list, , newE(data)) ){
stack->top++;
return TRUE;
}
return FALSE;
}
//弹栈
void *Stack_pop(PStack stack){
assert(stack);
if(stack->top>&&stack->list->count>){
PE e = LinkList_get(stack->list, );
if(e){
stack->top--;;
LinkList_del(stack->list, );
return e->data;
}
}
return NULL;
}
void *Stack_getTop(PStack stack){
PE e = NULL;
assert(stack);
if(stack->top> && stack->list->count> ){
e = LinkList_get(stack->list, );
}
return e? e->data: NULL;
}
//叛空
BOOL Stack_isEmpty(PStack stack){
return !stack->top;
}
//取栈剩余元素数量
int Stack_getCount(PStack stack){
assert(stack);
return stack->top;
}
stack.c