逆置链表（C语言）栈和头插法

╰+攻爆jí腚メ 2022-03-11 09:41 248阅读 0赞

本题的要求就是采用顺序栈来进行逆置输出单链表中的所有元素。  
解：首先我们定义一个创建链表的函数用来创建一个链表，并在函数中直接对链表进行数据输入，在逆置函数中，先将链表的数据一次放入到顺序栈中，然后将栈中元素从栈顶开始进行输出即可，算法如下：

#include<stdio.h>
    #include<malloc.h>
    #define maxsize 100
    
    typedef struct node{
    	int data;
    	struct node *next;
    }listnode;
    
    struct Node{
    	int element[maxsize];
    	int top;
    }st;
    
    typedef listnode* Linklist;
    
    void creatlist(Linklist *head)
    {
    	(*head)= (listnode *)malloc(sizeof(listnode));
    	Linklist p1, L;
    	L = (*head);
    	for(int i = 0;i < 10;i++)
    	{
    		p1 = (listnode *)malloc(sizeof(listnode));
    		p1 -> data  = i;
    		L -> next = p1; 
    		L = p1;
    	}
    	L -> next = NULL;			//尾节点指针域置空 
    }
    
    void reserve(Linklist L)
    {
    	int x;
    	Linklist p = L -> next;
    	while(p)		//链表数据输入 
    	{
    		st.top++;		//栈顶指针加一 
    		st.element[st.top] = p -> data;
    		p = p -> next;
    	}
    	while(st.top != -1)
    	{
    		x = st.element[st.top];
    		st.top--;
    		printf("%d    ", x);
    	}
    	puts("");
    }
    
    int main()
    {
    	st.top = -1;			//定义一个顺序栈 
    	Linklist L;
    	creatlist(&L);
    	reserve(L);
    	
    	return 0;
     }

逆置链表初始为空，表中节点从原链表中依次“删除”，再逐个插入逆置链表的表头（即“头插”到逆置链表中），使它成为逆置链表的“新”的第一个结点，如此循环，直至原链表为空。

#include<stdio.h>
    #include<malloc.h>
    
    typedef struct node{
    	int data;
    	struct node *next;
    }listnode;
    
    typedef listnode *Linklist;
    
    void creatlist(Linklist *head)
    {
    	(*head) = (Linklist)malloc(sizeof(listnode)); 
    	Linklist p1, L;
    	L = (*head);
    	for(int i = 0;i < 10;i++)
    	{
    		p1 = (Linklist)malloc(sizeof(listnode));
    		p1 -> data = i;
    		L -> next = p1;
    		L = p1;
    	}
    	L -> next = NULL;
     } 
    
    void reserve(listnode *head)
    {
    	listnode *p, *q;
    	p = head -> next;
    	head -> next = NULL;
    	while(p)
    	{
    		/*向后挪动一个位置*/
    		q=p;
    		p=p->next;
    		
    		/*头插*/
    		q->next=head->next;
    		head->next=q;
    	}
    }
    
    void print(Linklist head)
    {
    	listnode *L = head -> next;
    	while(L)
    	{
    		printf("%d\t", L -> data);
    		L = L -> next;
    	}
    	puts("");
    }
    
    int main()
    {
     	listnode *head;
     	creatlist(&head);
    
     	reserve(head);
    	print(head);
    	 	
     	return 0; 
    }