数据结构（4）

一、内核链表

        内核链表是操作系统内核和系统级编程中常用的一种数据结构，它与普通链表相比，在设计上更加灵活高效，它不再将数据存储再链表中，而将链表存储在数据中，而且本身是双向循环，提高了利用率。

        结构：

        struct

        {

        int id；

        char name [32];

        int score;

             宏定义：offset_of ：获取内核链表中链表结点到结构体起始位置的偏移量；

            container_of ： 通过偏移量，获取结构体的首地址

二级指针的作用：1.在被调函数中，想要修改主调函数中的指针变量，需要传递该指针变量的地址，形参用二级指针接受；

2.指针数组的数组名是一个二级指针，指针数组的数组名作为形参传递时，可用二级指针接受。

二、栈

        内存可分为五个区：栈区、堆区、内核、数据区、文本区。栈区是其中的一个。

        栈区存储着局部变量，函数的形参、返回值，函数的调用关系。

        栈区的存储特点为：FILO（先进后出）。这种        只允许从一端进行数据的插入和删除的线性存储结构称为栈结构。

        利用顺序表创建的栈称之为顺序栈，利用链表创建的栈称之为链式栈。

此外,栈还可以被分为满增栈、满减栈、空增栈、空减栈。

满栈：先设置栈顶，再入数据，使栈顶始终有数据；

栈顶

栈底

空栈：先存入栈数据，再移动栈顶，使栈顶保持为空；

栈顶

栈底

增栈：内存低地址向内存高地址入栈；

高地址

低地址（先进去为低）

减栈：内存高地址向内存低地址入栈：

高地址

低地址

链式栈的行为：

1.创建

Stack_t *create_stack()//创建栈链表
{Stack_t *pstack = malloc(sizeof(Stack_t));if(NULL == pstack){printf("malloc error!\n");return NULL;}pstack->ptop = NULL;pstack->clen = 0;return pstack;
}

2.入栈

int push_stack(Stack_t *pstack,Data_type_t data)//入栈
{STNode_t *ptmp = malloc(sizeof(Stack_t));if(NULL == ptmp){printf("malloc error!\n");return -1;}ptmp->data = data;ptmp->pnext = pstack->ptop;pstack->ptop = ptmp;

3.出栈

int pop_stack(Stack_t *pstack, Data_type_t *data)//出栈
{if(is_empty_stack(pstack)){printf("empty!\n");return -1;}else{if(NULL != data){*data = pstack->ptop->data;STNode_t *ptmp = pstack->ptop;pstack->ptop = pstack->ptop->pnext;free(ptmp);ptmp = NULL;}}pstack->clen--;return *data;
}

4.判断是否为空以及遍历

int is_empty_stack(Stack_t *pstack)//判断是否为空
{return NULL == pstack->ptop;
}void stack_for_each(Stack_t *pstack)//遍历
{STNode_t *ptmp = pstack->ptop;printf("%d\n", pstack->ptop->data);while(ptmp->pnext != NULL){ptmp = ptmp->pnext;printf("%d\n", ptmp->data);}
}

5.获取栈顶元素

int get_top_stack(Stack_t *pstack,Data_type_t *data)
{if(is_empty_stack(pstack)){printf("empty!\n");return -1;}else{if(NULL != data){*data = pstack->ptop->data;}}return *data;
}

6.销毁

void destroy_stack(Stack_t **pstack)
{if(is_empty_stack(*pstack)){printf("empty!\n");return ;}else{Stack_t *ptmp = *pstack;int data;while(ptmp->ptop != NULL){pop_stack(ptmp,&data);}free(ptmp);ptmp = NULL;}return ;
}