C 언어의 - 양 방향 링크

머리말
전에 'C 언어의 - 단 방향 링크' 라 는 글 을 썼 는데 관심 있 는 분 들 은 보 세 요.
양 방향 링크 는 특정한 장소 에서 단 방향 링크 와 결합 하면 매우 간편 하고 신속하게 데 이 터 를 조작 할 수 있다. 예 를 들 어 잠 금 대기 열 등 이다.
양 방향 링크 를 볼 수 있 는 백과: 백과 - 양 방향 링크
2. 실현 과정
우 리 는 주석 을 결합 하여 함께 양 방향 링크 를 배 웠 다.글 의 밑부분 에 모두 가 다운로드 할 수 있 도록 원본 코드 가 있다.
먼저 구조 체 노드 를 정의 합 니 다.

typedef struct s_msg
{
	int  count;    //    ：   count
	char str[20];  //    ：     ，  20   

	struct s_msg *prev; //    ：       
	struct s_msg *next; //    ：       
} s_msg_t;

1. 양 방향 링크 생 성

/************************************************************************* 
* Function:    void double_link_creat(s_msg_t **head, s_msg_t *new)
* Description:   /      
* Input:   
*              s_msg_t **head    
*              s_msg_t *new       
* Return:      NULL
* Others:      NULL
**************************************************************************/
void double_link_creat(s_msg_t **head, s_msg_t *pnew)
{
	s_msg_t *tmp = *head;
	if (NULL == *head) //     ，          
	{
		*head = pnew;
		pnew->prev = NULL;
		pnew->next = NULL;
	}
	else //           
	{
		while (NULL != tmp->next)
		{
			tmp = tmp->next;//           
		}
		tmp->next  = pnew;  //           
		pnew->prev = tmp;
		pnew->next = NULL;
	}
}

2. 양 방향 링크 의 인쇄

/************************************************************************* 
* Function:    void double_link_print(s_msg_t * head)
* Description:       
* Input:   
*              s_msg_t *head    
* Return:      NULL
* Others:      NULL
**************************************************************************/
void double_link_print(s_msg_t * head)
{
	if (NULL == head)
	{
		LOGD("double link is null, return.");
		return ;
	}
	
	s_msg_t *tmp = head;
	while (NULL != tmp)
	{
		LOGD("show link nodes: count = %d, str = %s
", tmp->count, tmp->str);
		tmp = tmp->next;
	}
}

3. 양 방향 링크 삭제 노드

/************************************************************************* 
* Function:    void double_link_delete_nodes_for_num(s_msg_t **head, int num)
* Description:       
* Input:   
*              s_msg_t *head    
*  int num                 
* Return:      NULL
* Others:      NULL
**************************************************************************/
void double_link_delete_nodes_for_num(s_msg_t **head, int num)
{
	if (NULL == *head)
	{
		LOGD("double link is null, return.");
		return ;
	}
	s_msg_t *tmp = *head, *pf;
	while ((num != tmp->count) && (NULL != tmp->next))
	{
		tmp = tmp->next;
	}
	if (num == tmp->count)
	{
		if (tmp == (*head)) //         
		{
			if (NULL == (*head)->next)  //            
			{
				(*head) = tmp->next;
			}
			else//           
			{
				(*head) = tmp->next;
				(*head)->prev = NULL;
			}
		}
		else //          
		{
			if (NULL != tmp->next) //         
			{
				pf = tmp->prev;
				pf->next = tmp->next;
				(tmp->next)->prev = pf;
			}
			else //      
			{
				pf = tmp->prev;
				pf->next = NULL;
			}
		}
		free(tmp); //     
	}
	else
	{
		LOGD("not find the num, can't delete.");
	}
}

4. 양 방향 링크 삽입 노드

/************************************************************************* 
* Function:    void double_link_insert_for_num(s_msg_t **head, s_msg_t *pnew)
* Description:            
* Input:   
*              s_msg_t **head    
*              s_msg_t *pnew        
* Return:      NULL
* Others:      NULL
**************************************************************************/
void double_link_insert_for_num(s_msg_t **head, s_msg_t *pnew)
{
	s_msg_t *pf, *tmp = (*head);
	if (NULL == tmp) //     ，        
	{
		(*head)= pnew;
		pnew->prev = NULL;
		pnew->next = NULL;
		return ;
	}
	while ((pnew->count >= tmp->count) && (NULL != tmp->next))
	{
		tmp = tmp->next;
	}
	if (pnew->count < tmp->count) //     tmp count pnew count ,  tmp  
	{
		if (tmp == (*head)) //        ,       
		{
			pnew->next = *head;
			(*head)->prev = pnew;
			pnew->prev = NULL;
			(*head) = pnew;
		}
		else //       
		{
			pf = tmp->prev; // pf            

			pnew->next = tmp;
			pnew->prev = pf;

			pf->next   = pnew;
			tmp->prev  = pnew;
		}
	}
	else // tmp  count  pnew  count ,     
	{
		tmp->next  = pnew;
		pnew->prev = tmp;
		pnew->next = NULL;
	}
}

5. 양 방향 링크 찾기 노드

/************************************************************************* 
* Function:    s_msg_t *double_link_search_for_num(s_msg_t *head, int num)
* Description:       
* Input:   
*              s_msg_t **head    
*              int num       num
* Return:      NULL
* Others:      NULL
**************************************************************************/
s_msg_t *double_link_search_for_num(s_msg_t *head, int num)
{
	if (NULL == head)
	{
		LOGD("double link is null, return.");
		return ;
	}

	s_msg_t *tmp = head;
	while (NULL != tmp)
	{
		if (num == tmp->count)
		{
			LOGD("find nodes: count = %d, str = %s", tmp->count, tmp->str);
			//return NULL;
		}
		tmp = tmp->next;
	}

	return NULL;
	
}

6. 양 방향 링크 의 방출
주의: 석방 방식 이 아직 완전 하지 않 을 수 있 습 니 다.

/************************************************************************* 
* Function:    s_msg_t *double_link_search_for_num(s_msg_t *head, int num)
* Description:       
* Input:   
*              s_msg_t **head    
* Return:      NULL
* Others:      NULL
**************************************************************************/
void double_link_free(s_msg_t **head)
{
	if (NULL == (*head)) //    ，    
	{
		LOGD("double link is null, return.");
		return ;
	}
	LOGD("free double link.");
	s_msg_t *tmp = NULL;
	while (NULL != (*head)) //       
	{
		tmp = (*head);  //       
		(*head) = tmp->next;// head    
		tmp->next = NULL;   //           
		if (NULL != *head)  //   head    
		{
			(*head)->prev = NULL; //           
		}
		free(tmp);
		tmp = NULL;
	}
}

demo 소스 코드: 다운로드 양 방향 링크 demo 추출 코드: vfer
원본 코드 를 Liux 시스템 에 다운로드 하여 직접 make 컴 파일 하면 됩 니 다.
끝 말
여러분 은 위의 예 를 통 해 유연 하 게 운용 하여 자신의 수요 에 따라 코드 를 수정 합 니 다.여기까지 소개 하 겠 습 니 다. 다 중 코드 를 통 해 링크 에 대한 사용 을 심화 시 킵 니 다.