데이터 구조 - 알고리즘 의 (033) (두 개의 질서정연 한 단일 체인 테이블 을 하나의 질서정연 한 단일 체인 테이블 로 통합)

[설명: 본 고 는 자기 귀납 적 정리 와 상호 교류 에 국한 되 며 오류 가 있 으 면 여러분 께 서 지적 해 주 십시오. 연락 메 일: [email protected]】
제목:
두 개의 질서정연 한 단일 체인 테이블 을 하나의 질서정연 한 단일 체인 테이블 (기본 오름차 순) 로 합 친 제목 분석:
1. 두 개의 링크 가 모두 질서 가 있 기 때문에 먼저 그 링크 의 머리 가 가장 작다 고 기록 해 야 합 니 다.
2. 대체적인 사상 은 하나의 가상 노드 순서 로 두 개의 링크 중의 노드 를 연결 하고 두 개의 링크 중의 머리 지침 을 따라 첫 번 째 연결 되 지 않 은 노드 를 가리 키 도록 하 는 것 이다.
알고리즘 구현:

#include <stdio.h>
#include <stdlib.h>

typedef struct _list_node
{
	int        key;
	struct _list_node  *next;
}list_node;

void *list_insert(list_node *head, int key)
{
	list_node *p = head;
	while(p->next != NULL)
		p = p->next;
	list_node *node = calloc(1, sizeof(list_node));
	node->key = key;
	node->next = NULL;

	p->next = node;
}


list_node *list_init()
{
	list_node *head = calloc(1, sizeof(list_node));
	head->key = 0;
	head->next = NULL;

	return head;
}

/*
**          :              (  )        
**   ,           
** h1-->:   1---4---7 ---12 
** h2-->:   3---9---13---14
*/
list_node *list_merger(list_node *h1, list_node *h2)
{
	if(!h1)	return h2;
	if(!h2) return h1;

	/*
	** @head                 
	*/
	list_node * head;
	if (h1->key > h2->key) 
	{
		head = h2;   
		h2 = h2->next;
	}
	else
	{
		head = h1; 
		h1 = h1->next;
	}

	list_node * current = head;
	while (h1 != NULL || h2 != NULL) 
	{
		/*
		** current             
		** (1)    @h1    ,     @h2       @current  
		*/
		if (h1 == NULL || (h2 != NULL && h1->key > h2->key)) 
		{
			current->next = h2;      /* @h2     @current    */ 
			current = current->next; /*  @current  ,         */
			h2 = h2->next;           /*            */
		}
		else 
		{
			current->next = h1; 
			current = current->next;
			h1 = h1->next;
		} 
	}
	current->next = NULL;
	return head->next;
}

void list_display(list_node *head)
{
    list_node *p = head->next;
    printf("list:");
	int count = 0;
    while(p != NULL)
    {
        printf(" %d", p->key);
        p = p->next;
		count++;
    }
	printf(" --->[%d]", count);
    printf("
");
}

int main(int argc, char *argv[])
{
	list_node *list1 = list_init();
	list_node *list2 = list_init();

	list_insert(list1, 1);
	list_insert(list1, 4);
	list_insert(list1, 7);
//	list_insert(list1, 12);
//	list_insert(list1, 19);
	list_insert(list1, 61);
	
	list_insert(list2, 3);
	list_insert(list2, 9);
	list_insert(list2, 13);
//	list_insert(list2, 14);
//	list_insert(list2, 61);

    list_display(list1);
    list_display(list2);

	list_node *all = list_merger(list1, list2);
	list_display(all);

	return 0;
}