当前位置：首页 > article >正文

数据结构---双向链表---循环链表---栈

article 2024/12/26 13:18:24

一、双向链表

1.1.创建双向链表

1.2.头插法

1.3.尾插法

1.4.查询节点

1.5.修改节点

1.6.删除节点

1.7.打印节点

1.8.销毁链表

二、循环链表

2.1.单循环链表

2.2.双循环链表

三、栈

3.1.顺序栈

1.创建栈

2.判断栈是否满

3.判断栈是否为空

4.进栈

5.出栈

6.销毁栈

3.2.链栈

四、总结

一、双向链表

typedef int DataType;

typedef struct double_list
{
    DataType data;
    struct double_list *pnext;
    struct double_list *pprev;

}LinkNode;

1.1.创建双向链表

LinkNode *CreateLinkList(void)
{
    LinkNode *phead = NULL;
    phead = malloc(sizeof(LinkNode));
    if (phead == NULL)
    {
        return NULL;
    }

    phead->data = 0;
    phead->pnext = NULL;
    phead->pprev = NULL;

    return phead;
}

1.2.头插法

int HeadInsertLinkList(LinkNode *phead, DataType data)
{
    LinkNode *pnode = NULL;

    pnode = malloc(sizeof(LinkNode));
    if (pnode == NULL)
    {
        return -1;
    }
    pnode->data = data;

    if (phead->pnext == NULL)
    {
        pnode->pnext = NULL;
        pnode->pprev = phead;
        phead->pnext = pnode;
    }
    else
    {
        pnode->pnext = phead->pnext;
        pnode->pprev = phead;
        phead->pnext = pnode;
        pnode->pnext->pprev = pnode;
    }

    return 0;

}

1.3.尾插法

int TailInsertLinkList(LinkNode *phead, DataType data)
{
    LinkNode *pnode = NULL;
    LinkNode *ptmp = NULL;

    ptmp = phead->pnext;
    pnode = malloc(sizeof(LinkNode));
    if (pnode == NULL)
    {
        return -1;
    }
    pnode->data = data;

    if (phead->pnext == NULL)
    {
        pnode->pnext = NULL;
        pnode->pprev = phead;
        phead->pnext = pnode;
    }
    else
    {
        while(ptmp->pnext != NULL)
        {
            ptmp = ptmp->pnext;
        }

        pnode->pnext = NULL;
        pnode->pprev = ptmp;
        ptmp->pnext = pnode;

    }

    return 0;

}

1.4.查询节点

LinkNode *FindLinkList(LinkNode *phead, DataType data)
{
    LinkNode *ptmp = NULL;

    if (phead->pnext == NULL)
    {
        return NULL;
    }
    ptmp = phead->pnext;

    while (ptmp->pnext != NULL)
    {
        if (ptmp->data == data)
        {
            printf("%d存在\n", ptmp->data);
            break;
        }

        ptmp = ptmp->pnext;
    }

    return ptmp;

}

1.5.修改节点

int UpdateLinkList(LinkNode *phead, DataType olddata, DataType newdata)
{
    LinkNode *ptmp = NULL;

    if (phead->pnext == NULL)
    {
        return -1;
    }

    ptmp = phead->pnext;
    
    while (ptmp != NULL)
    {
        if (ptmp->data == olddata)
        {
            ptmp->data = newdata;
        }

        ptmp = ptmp->pnext;
    }

    return 0;

}

1.6.删除节点

int DelteLinkList(LinkNode* phead, DataType data)
{
    LinkNode *ptmp = NULL;
    LinkNode *qtmp = NULL;

    if (phead->pnext == NULL)
    {
        return -1;
    }

    ptmp = phead->pnext;
    qtmp = phead->pnext;

     while (ptmp != NULL)
    {
        qtmp = qtmp->pnext;
        if (ptmp->data == data && ptmp->pnext != NULL)
        {
            ptmp->pnext->pprev = ptmp->pprev;
            ptmp->pprev->pnext = ptmp->pnext;
            free(ptmp);
            
        }
        else if (ptmp->data == data && ptmp->pnext == NULL)
        {
            ptmp->pprev->pnext = ptmp->pnext;
            free(ptmp);
        }
        ptmp =qtmp;
    }

    return 0;
}

1.7.打印节点

int PrintLinkList(LinkNode *phead)
{
    LinkNode *ptmp = NULL;
    ptmp = phead->pnext;

    if (phead->pnext == NULL)
    {
        return -1;
    }

    while(ptmp != NULL)
    {
        printf("%d ", ptmp->data);
        ptmp = ptmp->pnext;
    }

    printf("\n");

    return 0;
}

1.8.销毁链表

int DestoryLinkList(LinkNode **phead)
{
    LinkNode *ptmp = NULL;

    if ((*phead)->pnext == NULL)
    {
        free(*phead);
        return 0;
    }

    if ((*phead)->pnext->pnext == NULL)
    {
        free((*phead)->pnext);
        free((*phead));
        return 0;
    }

    ptmp = (*phead)->pnext->pnext;
    while(ptmp != NULL)
    {
        free(ptmp->pprev);
        if (ptmp->pnext == NULL)
        {
            free(ptmp);
            ptmp = NULL;
            continue;
        } 
        ptmp = ptmp->pnext;
    }

    free(*phead);
    *phead = NULL;
                                                                                                                                                                                                                    
    return 0;

}

二、循环链表

2.1.单循环链表

2.2.双循环链表

三、栈

栈顶：允许进出栈位置

栈底：不允许进出栈的位置

3.1.顺序栈

typedef int DataType;

typedef struct stack 
{
    DataType *pdata;
    int top;    
    int tlen;
    
}seqstack;

1.创建栈

seqstack *CreateStack(int maxlen)
{
    //1.
    seqstack *pstack = NULL;
    pstack = malloc(sizeof(seqstack));
    if (pstack == NULL)
    {
        return 0;
    }

    //2.
    pstack->tlen = maxlen;
    pstack->top = 0;
    pstack->pdata = malloc(maxlen * sizeof(DataType));

    return pstack;

}

2.判断栈是否满

int IsFullStack(seqstack *pstack)
{
    if (pstack->top == pstack->tlen)
    {
        return 1;
    }
    return 0;
}

3.判断栈是否为空

int IsEmptyStack(seqstack *pstack)
{
    if (pstack->top == 0)
    {
        return 1;
    }

    return 0;
}

4.进栈

int EnterSqlStack(seqstack *pstack, DataType data)
{   
    if (IsFullStack(pstack) == 0)
    {
        pstack->pdata[pstack->top] = data;
        pstack->top++;
        return 0;
    }
    else 
    {
        return -1;
    }

}

5.出栈

DataType PopSqlStack(seqstack *pstack)
{
    DataType data = 0;
    if (IsEmptyStack(pstack) == 0)
    {
        data = pstack->pdata[pstack->top - 1];
        pstack->top--;
        return data;
    }
    else
    {
        return -1;
    }
}

6.销毁栈

int DestroySeqStack(seqstack **seqstack)
{
    free((*seqstack)->pdata);
    free(*seqstack);
    *seqstack = NULL;

    return 0;
}

3.2.链栈

使用普通的链表就可以实现，采用头插法插入节点，在从头第一个数据节点可以遍历删除节点，便可以实现栈先进后出的规则。

四、总结

双向链表的好处是，可以直接访问一个节点的上一个节点；循环链表是将所有节点形成环，单循环链表，可以在末尾节点快速访问到第一个节点；双循环链表是可以，快速的访问尾节点；栈的特点就是先进栈的元素最后出战；栈的类型可以分为四种：满增栈、满减栈、空增栈、空减栈；链式栈，不要想复杂啦，普通的链表只要满足先进后出原则就可以啦！

查看全文

http://www.kler.cn/a/291500.html