数据结构（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 ;
}