68-双向循环链表的实现

「爱情、让人受尽委屈。」 2022-12-26 13:26 96阅读 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; 
    }RingLink;

以上是定义结构体。

以下是双向循环链表的实现

void RingLinkInit(RingLink *head) //初始化 
    {
         
    	if (head == NULL) exit(0); 
    	head->next = head->prev = head; 
    }
    
    static RingLink *ApplyNode(ElemType val, RingLink *prev, RingLink *next)//申请新的结点 
    {
         
    	RingLink *s = (RingLink*)malloc(sizeof(RingLink)); 
    	if (s == NULL) return NULL; 
    	s->data = val; 
    	s->prev = prev; 
    	s->next = next; 
    	return s; 
    }
    
    
    bool RingLinkInsert(RingLink *head, ElemType val, int pos)//按位置插入 
    {
         
    	if (head == NULL) exit(0); 
    	if (pos < 0) return false; 
    	RingLink *p = head; 
    	//pos %= (GetLength(head)+1); 
    	while (pos) 
    	{
         
    		p = p->next; 
    		pos--; 
    	}
    	RingLink *newNode = ApplyNode(val, p, p->next); 
    	if (newNode == NULL) return false; 
    	p->next->prev = newNode; // 不需要在判断p->next是否为空 
    	p->next = newNode; 
    	return true;
    }
    
    bool RingLinkInsertHead(RingLink *head, ElemType val) //头插 
    {
         
    	return RingLinkInsert(head, val, 0); 
    }
    
    // 尾插就是在head的前面插入一个节点 
    bool RingLinkInsertTail(RingLink *head, ElemType val) 
    {
         
    	if (head == NULL) exit(0); 
    	RingLink *newNode = ApplyNode(val, head->prev, head); 
    	if (newNode == NULL) return false; 
    	head->prev->next = newNode; 
    	head->prev = newNode; 
    	return true; 
    }
    
    bool RingDeletepos(RingLink *head, int pos)//按位置删除 
    {
        
    	if (head == NULL) exit(0); 
    	RingLink *p = head;
    	if(pos<0)  return false;
    	while (pos && p->next != head) 
    	{
         
    		p = p->next; 
    		pos--; 
    	} 
    	if (p->next == head) return false; 
    	RingLink *q = p->next; 
    	p->next = q->next; 
    	q->next->prev = p; 
    	free(q);
        return true;
    }
    
    bool RingDeletehead(RingLink *head) //头删 
    {
        
    	return RingDeletepos(head,0);
    }
    
    bool RingDeletetail(RingLink *head)//尾删除 
    {
        
    	if (head == NULL) exit(0); 
    	if (head->next == head) return false;
    	RingLink *p=head;
    	while (p->next != head) 
    	{
        
    		p = p->next; 
    	}
    	p->prev->next = head; 
    	p->next->prev=p->prev;
    	return true;
    }
    
    void RingDestroy(RingLink *head)//销毁 
    {
         
    	if (head == NULL) exit(0); 
    	while (head->next !=head)
    	{
         
    		RingDeletehead(head); 
    	} 
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/8216c86802d946899aa200218790720d.png