24/07/11数据结构(6.1215)双链表实现-栈实现

像写单链表的一些功能接口一样,先来写一些双链表的接口熟悉一下它的主体框架:

#include<stdio.h>
#include<stdlib.h>

typedef int LDataType;

//双向带头循环链表的节点
typedef struct ListNode{
    LDataType _data;
    //指向下一个节点的起始位置
    struct ListNode* _next;
    //指向上一个节点的起始位置
    struct LIst* _prev;
}ListNode;

//双向带头循环链表
typedef struct List{
    struct ListNode* _head;
}List;

struct ListNode* createListNode(LDataType val){
    struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
    node->_data = val;
    node->_next = NULL;
    node->_prev = NULL;
}

void ListInit(List* lst){
    //空链表
    lst->_head = createListNode(0);
    lst->_head->_next = lst->_head->_prev = lst->_head;

}
//尾插 O(1) //给头的前面插一个数据ListInsert(lst, lst->_head, val);
void ListpushBack(List* lst, LDataType val){
    if (lst == NULL){
        return;
        struct ListNode* last = lst->_head->_prev;
        struct ListNode* newNode = createListNode(val);
        //_head ... last newNode
        last->_next = newNode;
        newNode->_prev = last;

        newNode->_next = lst->_head;
        lst->_head->_prev = newNode;
    }
}

//尾删://删除头的前一个节点 ListErase(lst, lst->_head->_prev);
void ListPopBack(List* lst){
    if (lst == NULL)
        return;
    //判断是否空链表
    if (lst->_head->_next == lst->_head)
        return;
    struct ListNode* last = lst->_head->_prev;
    struct ListNode* prev = last->_prev;

    free(last);

    lst->_head->_prev = prev;
    prev->_next = lst->_head;
}

void printList(List* lst){
    struct ListNode* cur = lst->_head->_next;
    while (cur != lst->_head){
        printf("%d", cur->_data);
        cur = cur->_next;
    }
    printf("\n");
}

//头插//ListInsert(lst,lst->_head->_next,val);
void ListPushFront(List* lst, LDataType val){
    if (lst == NULL)
        return;
    struct ListNode* next = lst->_head->_next;
    struct ListNode* newNode = createListNode(val);

    //_head, newNode, next
    lst->_head->_next = newNode;
    newNode->_prev = lst->_head;

    newNode->_next = next;
    next->_prev = newNode;
}

//头删//ListErase(lst,lst->_head->_next);
void ListPopFront(List* lst){
    if (lst == NULL || lst->_head  == lst->_head)
        return;
    struct ListNode* next = lst->_head->_next;
    struct ListNode* nextnext = next->_next;
    
    nextnext->_prev = next->_next;
    lst->_head->_next = nextnext;

    free(next);
    
}

void ListErase(List* lst, struct ListNode* node){
    //不能删除head节点
    if (lst == NULL || lst->_head == node)
        return;
    //prev, node, next
    struct ListNode* prev = node->_prev;
    struct ListNode* next = node->_next;

    prev->_next = next;
    next->_prev = prev;

    free(node);

}

void ListInsert(List* lst, struct ListNode* node, LDataType val){
    if (lst == NULL)
        return;
    struct ListNode* prev = node->_prev;
    struct ListNode* newNode = createListNode(val);

    //prev newNode node
    prev->_next = newNode;
    newNode->_prev = prev;

    newNode->_next = node;
    node->_prev = newNode;
}

//销毁
ListDestoty(List* lst){
    if (lst){
        if (lst->_head){
            struct ListNode* cur = lst->_head->_next;
            while (cur != lst->_head){
                struct ListNode* next = cut->_next;
                free(cur);
                cur = next;
            }

            free(lst->_head);
        }
    }
}

void test(){
    List lst;
    ListInit(&lst);
    ListPushFront(&lst, 5);
    printList(&lst);
    ListPushFront(&lst, 1);
    printList(&lst);
    ListPushFront(&lst, 2);
    printList(&lst);
    ListPushFront(&lst, 3);
    printList(&lst);
    ListPushFront(&lst, 4);
    printList(&lst);
    ListPopFront(&lst);
    printList(&lst);
    ListPopFront(&lst);
    printList(&lst);
    ListPopFront(&lst);
    printList(&lst);

    /*ListPopBack(&lst);
    printList(&lst);
    ListPopBack(&lst);
    printList(&lst);
    ListPopBack(&lst);
    printList(&lst);
    ListPopBack(&lst);
    printList(&lst);*/
}

int main(){

    test();
    system("pause");
    return 0;
}

顺序表和链表的区别和联系:

顺序表优劣:优:空间连续,支持随机访问,空间利用率高不容易造成内存碎片,尾插尾删效率高.

                   劣:1.中间或前面部分插入删除时间复杂度O(N) 2.增容的代价比较大:申请 拷贝 释放

链表的优劣(带头双向随机链表)

                优:1.任意位置插入删除时间复杂度O(1) 2.没有增容问题,插入一个开辟一个空间,任意位置插入删除效率高

                劣:以节点为单位存储,不支持随机访问,空间利用率低容易造成内存碎片

栈和队列

栈:一种特殊的线性表,其只允许固定在一端进行插入和删除元素操作.进行数据插入和删除操作的一端叫做栈顶,另一端称为栈底.栈中的数据遵守后进先出LIFO(last in first out)原则

压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶

出栈:栈的删除操作叫做出栈,出数据也在栈顶

压栈操作的实现push--->从栈顶存入元素

        顺序表:可以把它看成是一个尾插操作

        链表:(双向带头循环链表)表头看做栈顶就是头插,表尾看做栈顶就是尾插

出栈操作pop--->从栈顶取出元素

        顺序表:表尾看做栈顶,把它看成尾删操作        

        链表:(双向带头循环链表)表头看做栈顶就是头删,表尾看做栈顶就是尾删

#include<stdio.h>
#include<stdlib.h>

typedef int STDataType;
//顺序表实现一个栈
typedef struct stack{
    STDataType* _data;
    int _size;
    int _capacity;
}stack;

void stackInit(stack* st){
    if (st == NULL)
        return;
    st->_data = NULL;
    st->_size = st->_capacity = 0;
}

void checkCapcacity(stack* st){
    if (st->_size == st->_capacity){
        int newCapcacity = st->_capacity == 0 ? 1 : 2 * st->_capacity;
        st->_data = (STDataType*)realloc(st->_data, sizeof(STDataType)* newCapcacity);
        st->_capacity = newCapcacity;
    }

}

//入栈
void stackPush(stack* st, STDataType val){
    if (st == NULL)
        return;
    checkCapacity(st);
    //尾插
    st->_data[st->_size++] = val;

}

//出栈
void stackPop(stack* st){
    if (st == NULL)
        return;
    if (st->_size > 0)
        st->_size--;
}

STDataType stackTop(stack* st){
    return st->_data[st->_size - 1];
}

int stackSize(stack* st){
    if (st == NULL)
        return 0;
    return st->_size;
}

void test(){
    stack st;
    stackInit(&st);
    stackPush(&st, 1);
    stackPush(&st, 2);
    stackPush(&st, 3);
    stackPush(&st, 4);
    for (int i = 0; i < 4; ++i){
        printg("%d", stackTop(&st));
        stackPop(&st);
    }
    printf("\n");
}

int main(){
    test();
    system("pause");
    return 0;
}