47-有头结点的单链表

浅浅的花香味﹌ 2022-12-24 00:44 161阅读 0赞

typedef int ElemType;
    
    typedef struct Node
    {
        
    	union {
               //  共同体
    		ElemType  data;
    		int       length;
    	};
    	struct Node *next;
    }HeadList;

**有头结点的单链表**

#include "headlist.h"
    #include <string.h>
    #include <stdlib.h>
    #include <stdio.h>
    
    static HeadList* ApplyNode(ElemType val, HeadList *nt)//申请新的结点 
    {
        
    	HeadList *s = (HeadList *)malloc(sizeof(HeadList));
    	if (s == NULL) return NULL;
    	s->data = val;
    	s->next = nt;
    	return s;
    	
    }
    
    void InitHeadList(HeadList * head)//初始化 
    {
        
    	if (head == NULL)  exit(0);
    	head->next = NULL;
    	head->length = 0;
    	
    }
    
    int GetLength(HeadList *head)//求出长度 
    {
        
    	if (head == NULL) exit(0);
    	int length = 0;
    	HeadList *p = head->next;
    	while (p != NULL)
    	{
        
    		length++;
    		p = p->next;
    	}
    	return length;
    	
    }
    
    void ShowList(HeadList *head)//输出链表值 
    {
        
    	if (head == NULL) exit(0);
    	HeadList *p = head->next;
    	while (p != NULL)
    	{
        
    		printf("%d  ", p->data);
    		p = p->next;
    	}
    	printf("\n");
    }
    
    bool  InsertOFPos(HeadList *head, ElemType val, int pos)//按位置插入 
    {
        
    	if (head == NULL) exit(0);
    	if (pos < 0) return false;  // pos和链表长度做对比
    	HeadList *p = head;
    	while (pos && p != NULL)
    	{
        
    		pos--;
    		p = p->next;
    	}
    	if (p == NULL)  return false;
    	HeadList *newNode = ApplyNode(val, p->next);
    	if (newNode == NULL) return false;
    	p->next = newNode;
    	return true;
    	
    }
    
    bool InsertOFHead(HeadList *head, ElemType val)//头插 
    {
        
    	if (head == NULL) return false;
    	// 方法一
    	return InsertOFPos(head, val, 0);
    	/* 方法二
    	HeadList *newNode = ApplyNode(val, head->next);
    	if (newNode == NULL) return false;
    	head->next = newNode;
    	return true;
    	*/
    }
    
    bool InsertOFTail(HeadList *head, ElemType val)//尾插 
    {
        
    	if (head == NULL) return false;
    	//return InsertOFPos(head, val, GetLength(head));
    	HeadList *p = head;
    	while (p->next != NULL) p = p->next;
    	p->next = ApplyNode(val, NULL);
    	return true;
    	
    }
    
    bool DeleteOFPos(HeadList *head, int pos)//按位置删除 
    {
        
    	if (head == NULL) exit(0);
    	if (pos < 0) return false;
    	HeadList *p = head;
    	while (pos && p->next != NULL)
    	{
        
    		p = p->next;
    		pos--;
    	}
    	if (p->next == NULL) return false;  // pos越界的情况
    	HeadList *q = p->next;  // q就是要删除的节点
    	p->next = q->next;
    	free(q);
    	return true;
    	
    }
    bool DeleteOFHead(HeadList *head)//头删除 
    {
        
    	if (head == NULL) exit(0);
    	return DeleteOFPos(head, 0);
    	
    }
    bool DeleteOFTail(HeadList *head)//尾删 
    {
        
    	if (head == NULL) exit(0);
    	if (head->next == NULL) return false;
    	HeadList *p = head;
    	HeadList *q = p->next;
    	while (q->next != NULL)
    	{
        
    		p = q;
    		q = q->next;
    	}
    	p->next = NULL;
    	free(q);
    	return true;
    	
    }
    
    // 将所有重复的值都删除
    bool DeleteOFValue(HeadList *head, ElemType val)
    {
        
    	if (head == NULL) exit(0);
    	if (head->next == NULL)  return false;
    	HeadList *p = head;
    	HeadList *q = p->next;
    	while (q != NULL)
    	{
        
    		if (q->data == val)
    		{
        
    			p->next = q->next;
    			free(q);
    			q = p->next;
    		}
    		else
    		{
        
    			p = q;
    			q = q->next;
    		}
    	}
    
    	return true;
    	
    }
    
    
    void DestroyHeadList(HeadList *head)//销毁 
    {
        
    	if (head == NULL) exit(0);
    	while (head->next != NULL)
    	{
        
    		DeleteOFHead(head);
    	}
    }
    void ClearHeadList(HeadList *head)//清除 
    {
        
    	if (head == NULL) exit(0);
    	DestroyHeadList(head);
    	
    }