65-双向链表的实现（带头结点）

清疚 2022-12-26 04:50 267阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]

typedef int ElemType;
    typedef struct Node {
        
    	ElemType data;
    	struct Node *prev; 
    	struct Node *next;
    }SDoubleLink;

以上定义双向链表的结构体  
以下是对双向链表作用的实现

void DoubleLinkInit(SDoubleLink *head)//双向链表初始化
    {
         
    	if (head == NULL) exit(0);
    	head->next = head->prev = NULL; 
    }
    
    static SDoubleLink *ApplyNode(ElemType val, SDoubleLink *prev, SDoubleLink *next)//申请新的结点
    {
         
    	SDoubleLink *s = (SDoubleLink*)malloc(sizeof(SDoubleLink)); 
    	if (s == NULL) return NULL;
    	s->data = val; 
    	s->prev = prev;
    	s->next = next;
    	return s; 
    }
    
    void ShowDList(SDoubleLink *head)//输出双向链表 
    {
        
    	if(head ==NULL) exit(0);
    	SDoubleLink *p =head;
    	while( p->next !=NULL)
    	{
        
    		printf("%d -->",p->next->data);
    		p = p->next;
    	}
    	printf("NULL\n");
    	while(p !=head)
    	{
        
    		printf("%d-->",p->data);
    		p = p->prev;
    	}
    	printf("NULL\n");
    }
    
    bool DoubleLinkInsert(SDoubleLink *head, ElemType val, int pos)//按位置插入
    {
         
    	if (head == NULL) exit(0); 
    	if (pos < 0) return false; 
    	SDoubleLink *p = head; 
    	while (pos && p != NULL) 
    	{
         
    		p = p->next; 
    		pos--; 
    	} 
    	if (p == NULL) return false; 
    	SDoubleLink *newNode = ApplyNode(val, p, p->next); 
    	if (newNode == NULL) return false; 
    	if (p->next != NULL) 
    	{
         
    		p->next->prev = newNode; 
    	} 
    	p->next = newNode; 
    	return true; 
    }
    
    bool DoubleLinkInsertHead(SDoubleLink *head, ElemType val) //头插
    {
          
    	return DoubleLinkInsert(head, val, 0); 
    }
    
    bool DoubleLinkInsertTail(SDoubleLink *head, ElemType val) //尾插
    {
         
    	if (head == NULL) exit(0); 
    	SDoubleLink *p = head; 
    	while (p->next != NULL) p = p->next; 
    	p->next = ApplyNode(val, p, NULL); 
    	return true; 
    }
    
    bool DoubleLinkDelete(SDoubleLink *head, int pos) //按位置删除
    {
         
    	if (head == NULL) exit(0); 
    	if (pos < 0) return false; 
    	SDoubleLink *p = head; // p指针指向要删除的pos位置的节点的前驱 
    	while (pos && p->next != NULL) 
    	{
         
    		p = p->next; 
    		pos--; 
    	} 
    	if (p->next == NULL) return false; 
    	SDoubleLink *q = p->next; 
    	p->next = q->next; 
    	if (q->next != NULL) 
    	{
         
    		q->next->prev = p; 
    	} 
    	free(q); 
    	return true; 
    }
    
    bool DoubleLinkDeleteHead(SDoubleLink *head) //头删
    {
         
    	return DoubleLinkDelete(head, 0);
    }
    
    
    bool DoubleLinkDeleteTail(SDoubleLink *head) //尾删
    {
         
    	if (head == NULL) exit(0); 
    	if (head->next == NULL) return false; 
    	SDoubleLink *p = head; 
    	while (p->next != NULL) 
    		p = p->next; 
    	p->prev->next = NULL; 
    	free(p); 
    	return true;
    
    }
    
    // 删除遇到的第一个val值的结点 
    bool DoubleLinkDeleteValue(SDoubleLink *head, ElemType val) 
    {
         
    	if (head == NULL) exit(0); 
    	SDoubleLink *p = head->next; 
    	while (p != NULL && p->data != val) 
    	{
         
    		p = p->next; 
    	}
    	if (p == NULL) return false; 
    	p->prev->next = p->next; 
    	if(p->next != NULL) 
    	p->next->prev = p->prev; 
    	free(p); 
    	return true; 
    
    }
    
    
    void DoubleLinkDestroy(SDoubleLink *head) //销毁
    {
         
    	if (head == NULL) exit(0); 
    	while (head->next != NULL) // 直到链表为空 
    	{
         
    		DoubleLinkDeleteHead(head); 
    	} 
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/fc50a8c9f92f4b3db171168cdfa11c4a.png