48-没有头结点的单链表

- 日理万妓 2022-12-24 00:45 236阅读 0赞

typedef int ElemType;
    
    typedef struct Node
    {
        
    	ElemType data;
    	struct Node *next;
    }PointList;

没有头结点的单链表

#include "pointlist.h"
    #include <string.h>
    #include <stdlib.h>
    
    
    static PointList* ApplyNode(ElemType val, PointList *nt)//申请新的结点 
    {
        
    	PointList *s = (PointList *)malloc(sizeof(PointList));
    	if (s == NULL) return NULL;
    	s->data = val;
    	s->next = nt;
    	return s;
    	
    }
    
    
    void  InitPointList(PointList **pp)//初始化 
    {
        
    	if (pp == NULL)  exit(0);
    	*pp = NULL;
    	
    }
    
    bool InsertHead(PointList **pp, ElemType val)//头插入 
    {
        
    	if (pp == NULL) exit(0);
    	*pp = ApplyNode(val, *pp);
    	if (*pp == NULL) return false;
    	return true;
    	
    }
    
    
    bool  InsertPointList(PointList **pp, ElemType val, int pos)//按位置插入 
    {
        
    	if (pp == NULL) exit(0);
    	if (pos < 0) return false;
    	if (*pp == NULL || pos == 0)  return InsertHead(pp, val);
    	PointList *p = *pp;
    	while (pos > 1 && p != NULL)
    	{
        
    		pos--;
    		p = p->next;
    	}
    	if (p == NULL) return false;
    	PointList *newNode = ApplyNode(val, p->next);
    	if (newNode == NULL) return false;
    	p->next = newNode;
    	return true;
    	
    }
    
    bool InsertTail(PointList **pp, ElemType val)//尾插入 
    {
        
    	if (pp == NULL) exit(0);
    	if (*pp == NULL) return InsertHead(pp, val);
    	PointList *p = *pp;
    	while (p->next != NULL) p = p->next;
    	p->next = ApplyNode(val, NULL);
    	return false;
    	
    }
    
    bool DeleteHead(PointList **pp)//头删除 
    {
        
    	if (pp == NULL) exit(0);
    	if (*pp == NULL) return false;
    	PointList *q = *pp;
    	*pp = q->next;
    	free(q);
    	return true;
    	
    }
    
    bool  DeletePonitList(PointList **pp, int pos)//按位置删除 
    {
        
    	if (pp == NULL) exit(0);
    	if (*pp == NULL || pos < 0) return false;
    	if (pos == 0)
    	{
        
    		return DeleteHead(pp);
    	}
    	PointList *p = *pp;
    	while (pos > 1 && p->next != NULL)
    	{
        
    		pos--;
    		p = p->next;
    	}
    	if (p->next == NULL)  return false;  // pos越界
    	PointList *q = p->next;
    	p->next = q->next;
    	free(q);
    	return true;
    	
    }
    
    bool DeleteTail(PointList **pp)//尾删除 
    {
        
    	if (pp == NULL) exit(0);
    	if (*pp == NULL) return false;
    	if ((*pp)->next == NULL) return DeleteHead(pp);
    	PointList *p = *pp;
    	PointList *q = p->next;
    	while (q->next != NULL)
    	{
        
    		p = q;
    		q = q->next;
    	}
    	p->next = NULL;
    	free(q);
    	return true;
    	
    }
    
    bool DeleteValue(PointList **pp, ElemType val)//按值删除 
    {
        
    	if (pp == NULL) exit(0);
    	if (*pp == NULL) return false;  // 进来就是空链表
    	while (*pp != NULL && (*pp)->data == val)
    	{
        
    		DeleteHead(pp);
    	}
    	if (*pp == NULL) return true;  //  将链表删除成空链
    	PointList *p = *pp;
    	PointList *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 DestroyPointList(PointList **pp)//销毁 
    {
        
    	if (pp == NULL) exit(0);
    	while (*pp != NULL)
    	{
        
    		DeleteHead(pp);
    	}
    }
    
    //将不带头结点的链表转化为带头结点的链表，新思想 
    bool  InsertPointList2(PointList **pp, ElemType val, int pos)
    {
        
    	if (pp == NULL) exit(0);
    	if (pos < 0) return false;
    	PointList vmNode;
    	vmNode.next = *pp;
    	PointList *p = &vmNode;
    	while (pos && p != NULL)
    	{
        
    		pos--;
    		p = p->next;
    	}
    	if (p == NULL) return false;
    	PointList *newNode = ApplyNode(val, p->next);
    	if (newNode == NULL) return false;
    	p->next = newNode;
    	*pp = vmNode.next;
    	return true;
    	
    }