双链表

矫情吗；* 2023-08-17 15:15 149阅读 0赞

1、建立双链表

/*头插法*/
    void CreateDLink(DLinkNode*& L, ElemType a[], int n)
    {
    	DLinkNode* s;
    	L = (DLinkNode*)malloc(sizeof(DLinkNode));
    	L->prior = L->next = NULL;
    	
    	for (int i = 0; i < n; i++)
    	{
    		s = (DLinkNode*)malloc(sizeof(DLinkNode));
    		s->data = a[i];
    		s->next = L->next;
    		
    		if (L->next != NULL)
    		{
    			L->next->prior = s;
    		}
    		
    		L->next = s;
    		s->prior = L;
    	}
     }

/*尾插法*/
    void CreateDLink1(DLinkNode*& L, int a[], int n)
    {
    	DLinkNode* s, * r;
    	L = (DLinkNode*)malloc(sizeof(DLinkNode));
    	L->next = L->prior = NULL;
    	r = L;
    
    	for (int i = 0; i < n; i++)
    	{
    		s = (DLinkNode*)malloc(sizeof(DLinkNode));
    		s->data = a[i];
    		r->next = s;
    		s->next = NULL;
    		s->prior = r;
    		r = s;
    	}
    	r->next = NULL;
    }

插入节点

bool ListInsert(DLinkNode*& L, int i, int e)
    {
    	DLinkNode* p,* s;
    	p = L;
    	s = (DLinkNode*)malloc(sizeof(DLinkNode));
    	int j = 0;
    
    	while (j < i - 1 && p != NULL)
    	{
    		p = p->next;
    		j++;
    
    	}
    	if (p == NULL)
    		return false;
    	else
    	{
    		s->data = e;
    		s->next = p->next;
    		if (p->next != NULL)
    		{
    			p->next->prior = s;
    		}
    		p->next = s;
    		s->prior = p;
    		return true;
    
    	}
    
    }

删除节点

bool ListDelete(DLinkNode*& L, int i, int& e)
    {
    	DLinkNode* p = L,* q;
    	int j = 0;
    
    	if (i < 0)
    		return false;
    	while (j < i - 1&& p != NULL)
    	{
    		j++;
    		p = p->next;
    	}
    	if (p == NULL)
    		return false;
    	else
    	{
    		q = p->next;
    		if (q == NULL)
    			return false;
    		else
    		{
    			e = q->data;
    			p->next = q->next;
    			if (q->next != NULL)
    			{
    				p->next->prior = p;
    			}
    			free(q);
    			return true;
    		}
    	}
    
    }

逆置

void reserse(DLinkNode*& L)
    {
    	DLinkNode* p = L->next,* q;
    	L->next = NULL;
    
    	while (p != NULL)
    	{
    		q = p->next;
    		p->next = L->next;
    		if (L->next != NULL)
    		{
    			L->next->prior = p;
    		}
    		L->next = p;
    		p->prior = L;   
    		p = q;
    
    	}
     }

递增

void sort(DLinkNode*& L)
    {
    	DLinkNode* p, * q, * pre;
    	p = L->next->next;
    	L->next->next = NULL;
    	
    	while (p != NULL)
    	{
    		pre = L;
    		q = p->next;
    
    		while (pre->next != NULL && pre->next->data < p->data)
    		{
    			pre = pre->next;
    
    		}
    		p->next = pre->next;
    		if (pre->next != NULL)
    		{
    			pre->next->prior = p;
    		}
    		pre->next = p;
    		p->prior = pre;
    
    		p = q;
    
    	}
    	
    }

转载于:https://www.cnblogs.com/KIROsola/p/11318179.html