链表
链表就是一些包含数据的独立数据结构的集合。每个节点通过链或者指针连接在一起。程序通过指针访问链表的节点,节点通常是动态分配的,但有时你也能看到有节点数组构建的链表。即使这种情况下,程序也是通过指针来遍历链表的。
1. 单链表
每个节点饱和一个指向链表下一个节点的指针。链表最后一个节点的指针字段的值为NULL,提示链表后面不在有其他节点。
找到链表的第一个节点后,指针就可以带你访问剩余的所有节点。为了记住链表的起始位置,可以用一个根指针(root pointer)。根指针指向链表的第一个节点。注意根指针只是一个指针,不包含数据。
typedef struct NODE { struct NODE *link; int value; }NODE;
|
单链表可以通过链从开始位置遍历链表知道结束位置,但是链表无法从相反的方向进行遍历。
疑问:为什么无法从相反方向遍历?通过&查找不行么?
思考:一个内存地址可以由很多指针指向。地址说到底也只是一串数,指针就是在内存的其他位置存着这一串数,可能你又怎么知道那个位置存着这一串数呢?这串数可能出现很多次,也根本没法判断。&符号只是取出地址,而这个地址可以给其他任意地方存着。
2. 双链表
相比单链表,就是增加一个指向上一个节点的指针
堆栈
由于正常的堆栈没有给堆栈设置一个限额,为了安全起见,本文为堆栈设置了一个限制,如果需要取消这个限制,就#define STACK_LIMIT 0
1. 结构体定义
#ifndef __STACK_H_ #define __STACK_H_
#ifdef __cplusplus extern "C" { #endif
#define STACK_TYPE int
#define STACK_LIMIT 1
#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;
#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