链表

链表就是一些包含数据的独立数据结构的集合。每个节点通过链或者指针连接在一起。程序通过指针访问链表的节点,节点通常是动态分配的,但有时你也能看到有节点数组构建的链表。即使这种情况下,程序也是通过指针来遍历链表的。

1. 单链表

每个节点饱和一个指向链表下一个节点的指针。链表最后一个节点的指针字段的值为NULL,提示链表后面不在有其他节点。

找到链表的第一个节点后,指针就可以带你访问剩余的所有节点。为了记住链表的起始位置,可以用一个根指针(root pointer)。根指针指向链表的第一个节点。注意根指针只是一个指针,不包含数据。

typedef struct NODE {
struct NODE *link;
int value;
}NODE;

单链表可以通过链从开始位置遍历链表知道结束位置,但是链表无法从相反的方向进行遍历。

疑问:为什么无法从相反方向遍历?通过&查找不行么?

思考:一个内存地址可以由很多指针指向。地址说到底也只是一串数,指针就是在内存的其他位置存着这一串数,可能你又怎么知道那个位置存着这一串数呢?这串数可能出现很多次,也根本没法判断。&符号只是取出地址,而这个地址可以给其他任意地方存着。

2. 双链表

相比单链表,就是增加一个指向上一个节点的指针

堆栈

由于正常的堆栈没有给堆栈设置一个限额,为了安全起见,本文为堆栈设置了一个限制,如果需要取消这个限制,就#define STACK_LIMIT 0

1. 结构体定义

/******************************************************************
* 作 者 :xiaoqinxing
* 功能描述 :单链表实现的动态堆栈
* 使用说明 :
******************************************************************/
#ifndef __STACK_H_
#define __STACK_H_

#ifdef __cplusplus
extern "C" {
#endif
//定义存储数据类型(可以定义为指针)
#define STACK_TYPE int

//是否限制堆栈长度
#define STACK_LIMIT 1

//堆栈默认长度,开启STACK_LIMIT后生效
#define STACK_LIMIT_DEFAULT_LENTH 10

typedef struct STACK_NODE {
STACK_TYPE value;
struct STACK_NODE *next;
}StackNode;

typedef struct STACK_PRIVATE{
unsigned int length;
unsigned int max_len;
}STACK_PRIVATE;
//结构体里面的函数指针 参数中包含结构体时一定要加struct,否则会报错,
//但是c文件里面可以不加;可能是Stack还没有定义完就使用了
#if 0
//第一种写法
typedef char (*is_empty_func)(struct Stack *stack_obj);
typedef void (*push_func)(struct Stack *stack_obj, STACK_TYPE value);
typedef void (*pop_func)(struct Stack *stack_obj);
typedef STACK_TYPE(*top_func)(struct Stack *stack_obj);

typedef struct Stack {
StackNode *node;
is_empty_func is_empty;
push_func push;
pop_func pop;
top_func top;
}Stack;
#else
//第二种写法
typedef struct Stack {
StackNode *node;
#if STACK_LIMIT
STACK_PRIVATE stack_private;
char(*is_full)(struct Stack *stack_obj);
void(*set_length)(struct Stack *stack_obj);
#endif
char(*is_empty)(struct Stack *stack_obj);
void(*push)(struct Stack *stack_obj, STACK_TYPE value);
STACK_TYPE(*pop)(struct Stack *stack_obj);
STACK_TYPE(*top)(struct Stack *stack_obj);
}Stack;
#endif

char is_stack_full(struct Stack *stack_obj);
void set_stack_length(struct Stack *stack_obj, unsigned int value);
char is_stack_empty(Stack * stack_obj);
void push(Stack * stack_obj, STACK_TYPE value);
STACK_TYPE pop(Stack * stack_obj);
STACK_TYPE top(Stack * stack_obj);
Stack* create_stack(void);
void destroy_stack(Stack *stack_obj);



#ifdef __cplusplus
}
#endif

#endif

2. 创建和销毁

Stack* create_stack(void) {
Stack *stack_obj=MALLOC(1,Stack);
stack_obj->node = NULL;
#if STACK_LIMIT
stack_obj->stack_private.length = 0;
stack_obj->stack_private.max_len = STACK_LIMIT_DEFAULT_LENTH;
stack_obj->set_length = set_stack_length;
stack_obj->is_full = is_stack_full;
#endif
stack_obj->push = push;
stack_obj->pop = pop;
stack_obj->top = top;
stack_obj->is_empty = is_stack_empty;
return stack_obj;
}

void destroy_stack(Stack *stack_obj){
while (!is_stack_empty(stack_obj)) {
pop(stack_obj);
}
FREE(stack_obj);
}

3. 判断是否为空或满

#if STACK_LIMIT
char is_stack_full(Stack * stack_obj)
{
return stack_obj->stack_private.length >= stack_obj->stack_private.max_len;
}
#endif
char is_stack_empty(Stack *stack_obj) {
return stack_obj->node == NULL;
}

4. 设置堆栈最大长度

#if STACK_LIMIT
void set_stack_length(Stack * stack_obj, unsigned int value)
{
stack_obj->stack_private.max_len = value;
}
#endif

5. push

void push(Stack *stack_obj, STACK_TYPE value){
StackNode *new_node;
#if STACK_LIMIT
if (is_stack_full(stack_obj)) {
LOGE("stack is full,push is error");
return;
}
#endif
new_node = MALLOC(1, StackNode);
new_node->value = value;
new_node->next = stack_obj->node;
stack_obj->node = new_node;
#if STACK_LIMIT
stack_obj->stack_private.length++;
#endif
}

6. pop

STACK_TYPE pop(Stack *stack_obj) {
StackNode *first_node = stack_obj->node;
if (is_stack_empty(stack_obj)) {
LOGE("stack is empty,pop is error");
return -1;
}
STACK_TYPE rc = first_node->value;
stack_obj->node = stack_obj->node->next;
FREE(first_node);
#if STACK_LIMIT
stack_obj->stack_private.length--;
#endif
return rc;
}

队列

与堆栈类似,这里就不列出来了,具体可以参考我的代码仓库

代码位置https://github.com/xiaoqinxing/myrepo_c