输入一个链表的头结点,从尾到头反过来输出每个结点的值。

前端之家收集整理的这篇文章主要介绍了输入一个链表的头结点,从尾到头反过来输出每个结点的值。前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

对于这个问题,可以利用"栈"的后进先出的思想,将链表中的节点先入栈后再出栈,这样就可以将链表从头 到位翻转过来。从网上搜索一下,没有找到可以直接调用栈的的方法,因此要用C语言实现必须要先写完栈的基本操作(入栈、出栈、初始化),幸好以前写过一个栈的基本操作的源码,可以把它放到工程中。

head.h文件

#ifndef HEAD_H_
#define HEAD_H_

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


#endif

stack.h文件
#ifndef STACK_H_
#define STACK_H_

#include "head.h"
typedef struct node
{
    int data;//数据域
    struct node *pNext;//指针域
}NODE,*PNODE;

typedef struct stack
{
    PNODE top;
    PNODE buttom;
}STACK,*PSTACK;

void initStack(PSTACK ps);
void pushStack(PSTACK ps,int val);
void traverse(PSTACK ps);
bool empty(PSTACK ps);
bool pop(PSTACK ps,int *pval);
void clear(PSTACK ps);


#endif

stack.c文件
#include "stack.h"

/**初始化栈**/
void initStack(PSTACK ps)
{
    ps->top = (PNODE)malloc(sizeof(NODE));
    if(NULL == ps->top)
    {
        printf("动态内存分配失败\n");
        exit(-1);
    }
    else
    {
        ps->top->pNext = NULL;//将栈顶指针指向的节点的指针域赋为空
        ps->buttom = ps->top;//将栈顶指针付给栈底指针
    }
}

/**入栈**/
void pushStack(PSTACK ps,int val)//在ps栈中压入值val
{
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    pNew->data = val;//将要压入的值赋给新申请的节点的数据域中
    pNew->pNext = NULL;//将新申请的节点的指针赋为空
    ///////////////////////////////////////////////////
    pNew->pNext = ps->top;
    ps->top = pNew;
}
/**遍历**/
void traverse(PSTACK ps)
{
    PNODE p;
    p = ps->top;

    while(p != ps->buttom)
    {
        printf("%d ",p->data);
        p = p->pNext;
    }
    printf("\n");
}

/**判空**/
bool empty(PSTACK ps)
{
    if(ps->top == ps->buttom)
        return true;
    else
        return false;
}

/**出栈**/
bool pop(PSTACK ps,int *pval)
{
    PNODE rm;
    if(empty(ps))
        return false;
    else
    {
        rm = ps->top;
        *pval = rm->data;
        ps->top = rm->pNext;
        free(rm);
        rm = NULL;//当不在使用申请的内存时,记得释放。释放后应该把指向这块内存的指针指向NULL
                  //以防程序后面不小心使用它。
        return true;
    }
}
/**清空栈**/
void clear(PSTACK ps)
{
    PNODE p = ps->top;
    PNODE q = NULL;

    while(p != ps->buttom)
    {
        q = p->pNext;
        free(p);//释放p所指向的用函数malloc所申请的空间
        p = q;
    }
    ps->top = ps->buttom;
}

main函数
#include "head.h"
#include "stack.h"

typedef struct Lnode
{
    int data;
    struct Lnode *pNode;
}Node,*PNode;


int main()
{
    STACK stack;
    PNode pHead,p,p1;
    int i,save,num;
    pHead = (PNode)malloc(sizeof(Node));
    pHead->pNode = NULL;
    p = pHead;
    printf("请输入链表的节点个数:\n");
    scanf("%d\n",&num);
    for(i = 0; i < num;i++)
    {
        p1 = (PNode)malloc (sizeof(Node));
        p1->pNode = NULL;
        scanf("%d",&p1->data);
        p->pNode = p1;
        p = p1;
    }

    p = pHead->pNode;
    while(p != NULL)
    {
        printf("%d",p->data);
        p = p->pNode;
    }

    initStack(&stack);
    p = pHead->pNode;
    while(p != NULL)
    {
        pushStack(&stack,p->data);
        p = p->pNode;
    }
    printf("\n");
    for(i = 0;i < num; i ++)
    {
        pop(&stack,&save);
        printf("%d",save);
    }

    return 0;
}
原文链接:https://www.f2er.com/javaschema/285749.html

猜你在找的设计模式相关文章