欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C语言实现使用带头结点的单链表来模拟栈结构

程序员文章站 2022-05-13 17:35:21
我在前面两篇博客中分别使用了静态数组、动态数组两种方式来构造栈,实现起来很方便,但总觉得灵活性还不够,因为无论怎样,我们都是要指定数组的长度。这篇博客中我们将会使用带头结点的单链表...

我在前面两篇博客中分别使用了静态数组、动态数组两种方式来构造栈,实现起来很方便,但总觉得灵活性还不够,因为无论怎样,我们都是要指定数组的长度。这篇博客中我们将会使用带头结点的单链表来模拟栈。为什么选用单链表呢?因为对于栈来说,弹出、压入等操作都是对栈顶来操作的。而单链表对第一个节点的操作是最为方便的。两者刚好能对应起来。代码上传至 https://github.com/chenyufeng1991/Stack_LinkedList

(1)声明节点类型、函数

 

typedef int elemType;
typedef struct NodeList{

    int element;
    struct NodeList *next;
}Node;

void createStack(Node **pNode);
void destroyStack(Node *pNode);
void push(Node *pNode,int value);
void pop(Node *pNode);
void top(Node *pNode);
int isEmpty(Node *pNode);
int isFull(Node *pNode);
void printStack(Node *pNode);

(2)初始化单链表

 

 

//初始化带头结点的单链表
void createStack(Node **pNode){

    *pNode = (Node *)malloc(sizeof(Node));
    if (*pNode == NULL) {
        printf("%s函数执行,内存分配失败,初始化单链表失败\n",__FUNCTION__);
    }else{

        (*pNode)->next = NULL;
        printf("%s函数执行,带头结点的单链表初始化完成\n",__FUNCTION__);
    }
}

(3)压入一个元素

 

 

//压入一个元素
void push(Node *pNode,int value){

    Node *pInsert;
    pInsert = (Node *)malloc(sizeof(Node));//需要检测分配内存是否成功 pInsert == NULL  ?
    memset(pInsert, 0, sizeof(Node));
    pInsert->next = NULL;
    pInsert->element = value;

    pInsert->next = pNode->next;
    pNode->next = pInsert;
}

(4)弹出一个元素

 

 

//弹出一个元素
void pop(Node *pNode){

    if (!isEmpty(pNode)) {

        Node *pNext;
        pNext = pNode->next;

        pNode->next = pNext->next;
        free(pNext);
        pNext = NULL;
    }
}

(5)打印栈元素

 

 

//打印栈元素
void printStack(Node *pNode){

    if (!isEmpty(pNode)) {

        Node *pMove;
        pMove = pNode->next;
        while (pMove != NULL) {
            printf("%d ",pMove->element);
            pMove = pMove->next;
        }
        printf("\n");
    }else{
        printf("栈为空,打印失败\n");
    }
}

(6)清空栈元素

 

 

//清空栈元素
void destroyStack(Node *pNode){

    Node *pMove;
    pMove = pNode->next;
    while (pMove != NULL) {

        pNode->next = pMove->next;
        free(pMove);
        pMove = pNode->next;
    }
}

(7)判断栈是否为空

 

 

//判断栈是否为空
int isEmpty(Node *pNode){
    /**
     *  当只有一个头结点的时候,该链表就为空
     */
    if (pNode->next == NULL) {
        return 1;
    }
    return 0;
}

(8)取栈顶元素

 

 

//取栈顶元素
void top(Node *pNode){
    if (!isEmpty(pNode)) {
        printf("栈顶元素为%d\n",pNode->next->element);
    }
}

(8)测试代码

 

 

int main(int argc, const char * argv[]) {

    Node *pList;
    createStack(&pList);

    push(pList, 3);push(pList, 1);push(pList, 9);push(pList, 4);push(pList, 7);
    printStack(pList);

    pop(pList);pop(pList);
    printf("经过pop后栈的元素为:\n");
    printStack(pList);

    top(pList);
    
    destroyStack(pList);
    printStack(pList);
    
    return 0;
}