C语言:链表的反向输出（反转链表+栈结构）

分手后的思念是犯贱 2022-08-04 05:12 147阅读 0赞

/*
    	链表的反向输出
    	1.反转链表
    	2.链表节点从头到尾入栈，在出栈
    */
    
    # include <stdio.h>
    # include <malloc.h>
    
    # define SIZE 5  //初始定义链表的长度
    
    //定义节点
    typedef struct Node
    {
    	int data;
    	struct Node * pNext;
    }NODE, * PNODE;
    
    //定义栈
    typedef struct Stack
    {
    	int * base;  //栈空间基址
    	int * top;  //指向栈顶有效元素的下一个位置
    }Stack;
    
    
    void traverse(PNODE pHead);   //遍历链表
    void reverseTrans_reverse(PNODE pHead);   //反转链表
    void reverseTrans_stack(PNODE pHead);  //用栈反向输出链表
    Stack creat_stack();   //创建栈
    void push(Stack &s, int val);   //元素入栈
      
    int main(void)
    {
    	int i, len, val;
    
    	//创建链表
    	PNODE pHead = (PNODE)malloc(sizeof(NODE));  //头结点
    	PNODE pTail = pHead;    //尾节点
    	PNODE pNew;  //新节点
    
    	printf("创建链表的长度为：len = %d\n", SIZE);
    	len = SIZE;
    
    	for(i = 0; i < len; i++)
    	{
    		printf("输入第%d个元素：", i+1);
    		scanf("%d", &val);
    
    		//创建新节点
    		pNew = (PNODE)malloc(sizeof(NODE));
    		pNew->data = val;
    		pNew->pNext = NULL;
    
    		//新节点添加在尾节点后面
    		pTail->pNext = pNew;
    		pTail = pNew;
    	}
    
    	//遍历链表
    	traverse(pHead);
    
    	//反向遍历链表， 从头到尾节点入栈，然后再出栈
    	printf("用栈，反向输出链表:");
    	reverseTrans_stack(pHead);
    
    	//反向遍历链表，反转链表
    	printf("反转链表:");
    	reverseTrans_reverse(pHead);
    
    	return 0;
    }
    
    void traverse(PNODE pHead)
    {
    	printf("遍历链表：");
    	PNODE p = pHead->pNext;
    
    	while(p != NULL)
    	{
    		printf("%d ", p->data);
    		p = p->pNext;
    	}
    
    	printf("\n");
    }
    
    //反转链表，并遍历
    void reverseTrans_reverse(PNODE pHead)
    {
    	//反向链表的头结点
    	PNODE pRever = (PNODE)malloc(sizeof(NODE));
    	pRever->pNext = NULL;
    
    	PNODE p = pHead->pNext;
    
    	PNODE mid = NULL;  //两个临时变量
    	PNODE pTail;
    
    	while(p != NULL)
    	{
    		pTail = mid;
    		mid = p;
    		p = p->pNext;
    		mid->pNext = pTail;
    	}
    
    	pRever->pNext = mid;
    
    	traverse(pRever);
    
    }
    
    //根据栈，反向输出链表
    void reverseTrans_stack(PNODE pHead)	
    {
    	int val;
    	Stack s = creat_stack();  //创建栈
    
    	PNODE p = pHead->pNext;
    	while(p != NULL)
    	{
    		push(s, p->data); //节点从头到尾如入栈
    		p = p->pNext;
    	}
    
    	while(s.top != s.base)  //元素再出栈
    	{
    		s.top --;
    		val = *(s.top);
    		printf("%d ", val);
    	}
    	printf("\n");
    
    }
    
    //创建栈
    Stack creat_stack()
    {
    	Stack s;
    	s.base = (int *)malloc(sizeof(int) * SIZE); //分配栈空间
    	s.top = s.base;
    	return s;
    }
    
    //元素入栈
    void push(Stack &s, int val)
    {
    	if((s.top - s.base) > SIZE)
    	{
    		printf("栈满！");
    		return;
    	}
    	else
    	{
    		*(s.top) = val;
    		s.top ++;
    	}
    }

![Image 1][]

[Image 1]: