非递减单链表中的删除操作（删除所有值为x的结点）—— c语言实现

桃扇骨 2023-02-26 08:27 16阅读 0赞

/*************************** 
    * author：vivi
    * date: 20-07-14
    ****************************/  
    #include <stdio.h>
    #include <stdlib.h>
    
    // function：单链表递增直接插入排序
    
    typedef struct Node
    {
        
    	int data;
    	struct Node* next;
    }Node,* SList;
    
    void init_list(SList* head)
    {
        
    	*head = (SList)malloc(sizeof(Node));
    	(*head)->next = NULL;
    }
    
    void CreatList(SList* head)
    {
        
        int x;
        int flag = 1;
        printf("input data end 0:\n");
        while(flag ==1)
        {
        
            scanf("%d",&x);
            if(x != 0)
            {
        
                Node* p =(Node*)malloc(sizeof(Node));
        	    p->data = x;
        	    p->next = (*head)->next;    //头插法 
        	    (*head)->next = p;
    	        flag = 1;
    	    }else flag = 0;
        }
    }
    
    void insertsort(SList head)
    {
        
    	Node* pre,*q,*p,*s;
        if(head->next != NULL)
    	{
        
    	    pre = head;
    		q = head->next;
    		if(q->next != NULL)
    		{
        
    		    p = q->next;
    			while(p != NULL)
    			{
        
    				while(p->data >= q->data)
    				{
        
    			        p = p->next;
    				    q = q->next;
    			    }
    				if(p != NULL && p->data < q->data)
    				{
        
    				    s = p;
    					q->next = p->next;
    					p = p->next;
    					while(s->data > pre->next->data)
    					    pre = pre->next;	
    					s->next = pre->next;
    					pre->next = s;
    					pre = head;
    				}	
    			}	
    		}	
    	} 
    }
    
    //删除表中值为x的结点 
    void delete_list(SList head, int x)
    {
        
    	Node* p = head;
    	if(p->next != NULL)
    	{
        
    		Node* q = p->next;
    		while(q != NULL)
    		{
        
    			if(q->data < x)
    			{
        
    				q = q->next;
    			    p = p->next;
    			}
    			else if(q->data == x)
    			{
        
    				Node* s = q;
    				q = q->next;
    				p->next = q;
    				free(s);
    			}    
    			else if(q->data > x)
    			{
        
    				break;
    			}
    		}
    	}
    }
    
    void print(SList head)
    {
        
    	Node* p = head;
    	while(p->next != NULL)
    	{
        
    		printf("%d ",p->next->data);
    		p = p->next;
    	}
    }
    
    int main() {
        
    	SList mylist;
    	init_list(&mylist);
    	CreatList(&mylist);
    	printf("原始链表：\n");
    	print(mylist);
    	printf("\n非递减链表：\n");
    	insertsort(mylist);
    	print(mylist);
    	
    	printf("输入删除的值: \n");
    	int x;
    	scanf("%d",&x);
    	printf("删除后的链表： \n");
    	delete_list(mylist,x);
    	print(mylist);
    	return 0;
    }