2.带头结点的单链表

青旅半醒 2022-11-22 12:51 160阅读 0赞

![在这里插入图片描述][20201104154337711.png_pic_center]

linkedlistwithhead.c

#include <stdio.h>
    #include <stdlib.h>
    
    #include "linkedlistwithhead.h"
    
    
    /* create_head: 给链表创建一个头结点 无参数 返回值： 返回创建好的头结点的指针 struct head_node * */
    struct head_node * create_head(void)
    { 
    	struct head_node * head = NULL;
    	head = (struct head_node *)malloc(sizeof(struct head_node));
    
    	//初始化以下结构体里面的内容 
    	head->first = NULL;
    	head->last = NULL;
    
    	head->num = 0;
    
    	return head;
    }
    
    //----------------------------------------
    
    
    /* add_Node:往一个有序的带头结点的单链表中添加一个数据结点 使添加后的单链表任然有序 @head： 原链表的头结点的指针 @p : 带加入数据结点的指针 */
    void add_Node(struct head_node * head, Node * p)
    { 
    	if(head == NULL || p == NULL)
    	{ 
    		return;
    	}
    
    	//head 里面是否有结点
    	if(head->first == NULL)
    	{ 
    		head->first = p;
    		head->last = p;	
    	}
    	else
    	{ 
    		//找到插入的位置
    		Node * pk = head->first;
    		Node * pr = head->first;
    
    		while(pk)
    		{ 
    			if(pk->data > p->data)
    			{ 
    				//找到啦
    				break;
    			}
    			pr = pk;
    			pk = pk->next;
    		}
    
    
    		//插入操作
    
    		if(pk == NULL)//没有找到一个比p->data还要大的结点
    		{ 
    			//加入到last 后面 “尾插法”
    			head->last->next = p;
    			head->last = p;
    		}
    		else //找到了
    		{ 
    			if(pk == head->first) // 第一个数据结点就比p->data “头插法”
    			{ 
    				p->next = head->first;
    				head->first = p;
    			}
    			else //"中间插入"
    			{ 
    				pr->next = p;
    				p->next = pk;
    			}
    		}
    	}
    
    	head->num ++;
    }
    
    
    //----------------------------------------------
    
    /* create_order_linkedlist: 根据用户的输入创建一个有序 的带头结点的单链表 @head: 链表的头结点 返回值： 不需要返回值 */
    void create_order_linkedlist(struct head_node* head)
    { 
    	Node * p = NULL; // 指向待添加的那个数据结点
    	int n;
    	while(1)
    	{ 
    		scanf("%d", &n);
    
    		//用户输入为0时候结束
    		if(n == 0)
    		{ 
    			break;
    		}
    
    		p = malloc(sizeof(*p));
    		p->data = n;
    		p->next = NULL;
    
    		add_Node(head,  p);
    	}
    	
    }
    
    //----------------------------------------
    
    
    /* print:打印每一个数据结点的数据域 @head: 头结点 无返回值 */
    
    void print(struct head_node * head)
    { 
    	if(head == NULL)
    	{ 
    		printf("Not Linkedlist!!\n");
    		return ;
    	}
    
    	if(head->first == NULL)
    	{ 
    		printf("Not Node!!\n");
    		return ;
    	}
    
    	Node * p = head->first;
    	while(p)
    	{ 
    		printf("%d ", p->data);
    		p = p->next;
    	}
    
    	printf("\n数据结点个数：%d\n", head->num);
    }
    
    
    //--------------------------
    /* delete_x : 删除一个data为X的数据结点 @head : 原链表的头结点 x : 要删除的那个结点的数据域 返回值： 无返回值 */
    void delete_x(struct head_node * head, Elemtype x)
    { 
    	if(head == NULL || head->first == NULL)
    	{ 
    		return;
    	}
    	
    	Node * px = head->first; //指向您要删除的那一个数据结点
    	Node * pr = NULL; //指向 px的前面那一个数据结点的 
    	
    	//找到要删除的那一个结点 "遍历链表"
    	while(px)
    	{ 
    		if(px->data == x)
    		{ 
    			//找到啦
    			break;
    		}
    		pr = px;
    		px = px->next;
    		//px就要往后挪
    	}
    	
    	
    	//分情况 
    	
    	if(px == NULL)//没有找到
    	{ 
    		return;
    	}
    	
    	
    
    	//找到的要删除的那个结点是第一个
    	if(px == head->first)
    	{ 
    		head->first = px->next;
    		px->next = NULL;
    
    		
    	}
    	else if(px == head->last)//找到的要删除的那个结点是最后一个结点
    	{ 
    		head->last = pr;
    		head->last->next = NULL;
    		
    	}
    	else //找到的要删除的那个结点是中间结点
    	{ 
    		pr->next = px->next;
    		px->next = NULL;
    	}
    	
    	free(px);
    	head->num --;
    }
    
    
    //--------------------------
    /* delete_all_x : 删除所有的data为X的数据结点 @head : 原链表的头结点 x : 要删除的那个结点的数据域 返回值： 无返回值 */
    void delete_all_x(struct head_node * head, Elemtype x)
    { 
    	if(head == NULL || head->first == NULL)
    	{ 
    		return;
    	}
    	
    	Node * px = head->first; //指向您要删除的那一个数据结点
    	Node * pr = NULL; //指向 px的前面那一个数据结点的 
    
    	Node * ps = head->first; //下一个开始遍历的结点
    	
    	while(1)
    	{ 
    		px = ps;
    		//找到要删除的那一个结点 "遍历链表"
    		
    		while(px)
    		{ 
    			if(px->data == x)
    			{ 
    				//找到啦
    				break;
    			}
    			pr = px;
    			px = px->next;
    			//px就要往后挪
    		}
    		
    		
    		//分情况 
    		if(px == NULL)//没有找到
    		{ 
    			return;
    		}
    
    		ps = px->next; 
    		
    
    		//找到的要删除的那个结点是第一个
    		if(px == head->first)
    		{ 
    			head->first = px->next;
    			px->next = NULL;
    
    			
    		}
    		else if(px == head->last)//找到的要删除的那个结点是最后一个结点
    		{ 
    			head->last = pr;
    			head->last->next = NULL;
    			
    		}
    		else //找到的要删除的那个结点是中间结点
    		{ 
    			pr->next = px->next;
    			px->next = NULL;
    		}
    		
    		free(px);
    		head->num --;
    		
    	}
    	
    }

linkedlistwithhead.h

#ifndef __LINKEDLISTWITHHEAD_H__
    #define __LINKEDLISTWITHHEAD_H__ 
    
    
    typedef int Elemtype; //数据元素的类型 
    
    //数据结点 
    typedef struct node 
    { 
    	//指针域 
    	struct node * next; //指向下一个数据结点
    	
    	//数据域 
    	Elemtype data;
    }Node;
    
    
    //头结点 
    struct head_node
    { 
    	Node * first ; //指向链表的第一个结点
    	Node * last ; // 指向链表的最后一个结点
    
    	int num; //记录链表中数据结点的个数
    };
    
    struct head_node * create_head(void);
    
    void add_Node(struct head_node * head, Node * p);
    
    void create_order_linkedlist(struct head_node* head);
    void print(struct head_node * head);
    void delete_x(struct head_node * head, Elemtype x);
    void delete_all_x(struct head_node * head, Elemtype x);
    
    
    #endif

main.c

#include <stdio.h>
    #include <stdlib.h>
    
    #include "linkedlistwithhead.h" 
    
    
    int main()
    { 
    	//创建一个头结点
    	struct head_node * h = NULL;
    	h = create_head();
    
    	//创建一个带头结点的有序单链表
    	create_order_linkedlist(h);
    	
    	//打印
    	print( h);
    
    	//printf("%s ------ %d \n", __FUNCTION__, __LINE__);
    	//用户输入一个x,再删除数据域为x的那一个结点
    	Elemtype x;
    	scanf("%d", &x);
    	//printf("%s ------ %d \n", __FUNCTION__, __LINE__);
    	delete_all_x(h, x);
    	//printf("%s ------ %d \n", __FUNCTION__, __LINE__);
    
    	printf("----------------\n");
    	print(h);
    	//printf("%s ------ %d \n", __FUNCTION__, __LINE__);
    }

[20201104154337711.png_pic_center]: /images/20221120/7ba8cbab651443e38944e7e75ddb1046.png