질서 정연 한 단일 체인 테이블 의 합병

\ # 이전 단계 로 돌아 가기
@ 저자: 장 해발
@Update: 2014-01-23
@Link: http://www.cnblogs.com/zhanghaiba/p/3531142.html
 

  1 /*

  2  *Author: ZhangHaiba

  3  *Date: 2014-1-23

  4  *File: sorted_list_merge.c

  5  *

  6  *a demo shows how to merge two sorted single linked list by

  7  *creating a new list or in-place.

  8  */

  9 

 10 #include <stdio.h>

 11 #include <stdbool.h>

 12 #include <stdlib.h>

 13 #define INF 0x7fffffff

 14 #define CMD_LNE 128

 15 

 16 typedef struct node* link;

 17 typedef struct node {

 18     int item;

 19     link next;

 20 }node;

 21 

 22 //public

 23 link NODE(int item, link next);

 24 link list_create(int n);

 25 link sorted_list_merge_create1(link list_src_a, link list_src_b);

 26 link sorted_list_merge_create2(link list_src_a, link list_src_b);

 27 link sorted_list_merge_in_place1(link list_src_a, link list_src_b);

 28 link sorted_list_merge_in_place2(link list_src_a, link list_src_b);

 29 void list_travel(link head);

 30 void list_destroy(link head);

 31 //private

 32 //accept list without Head Node, and return list without Head Node as well

 33 link sorted_list_merge_create_iter(link a, link b);

 34 link sorted_list_merge_in_place_iter(link a, link b);

 35 link sorted_list_merge_create_rec(link a, link b);

 36 link sorted_list_merge_in_place_rec(link a, link b);

 37 

 38 

 39 int main(void)

 40 {

 41     int len_a, len_b;

 42 

 43     scanf("%d", &len_a);

 44     link list_a = list_create(len_a);

 45     printf("list_a travel: ");

 46     list_travel(list_a);

 47 

 48     scanf("%d", &len_b);

 49     link list_b = list_create(len_b);

 50     printf("list_b travel: ");

 51     list_travel(list_b);

 52 

 53     printf("create list_c by using(merging) list_a and list_b nodes.
");

 54     //link list_c = sorted_list_merge_create1(list_a, list_b);

 55     link list_c = sorted_list_merge_create2(list_a, list_b);

 56     printf("list_c travel: ");

 57     list_travel(list_c);

 58 

 59     printf("merge list_c and list_a to list_d.
");

 60     //link list_d = sorted_list_merge_in_place1(list_c, list_a);

 61     link list_d = sorted_list_merge_in_place2(list_c, list_a);

 62     printf("list_d travel: ");

 63     list_travel(list_d);

 64 

 65     list_c = list_a = NULL;

 66     list_destroy(list_b);

 67     printf("list_b destroyed!
");

 68     list_destroy(list_d);

 69     printf("list_d destroyed!
");

 70     return 0;

 71 }

 72 

 73 link NODE(int item, link next)

 74 {

 75     link born = malloc(sizeof (node));

 76     born->item = item;

 77     born->next = next;

 78     return born;

 79 }

 80 

 81 //tail insert

 82 link list_create(int n)

 83 {

 84     int i, item;

 85     link head = NODE(INF, NULL);

 86     link tail = head;

 87 

 88     for (i = 0; i < n; ++i) {

 89         scanf("%d", &item);

 90         tail->next = NODE(item, NULL);

 91         tail = tail->next;

 92     }

 93     return head;

 94 }

 95 

 96 //Iterative implementation begin here

 97 link sorted_list_merge_create_iter(link a, link b)

 98 {

 99     link tmp_head = NODE(INF, NULL);

100     link c = tmp_head; //c as tail pointer for the list_c

101 

102     for (; a != NULL && b != NULL; c = c->next)

103         if (a->item < b->item)

104               c->next = NODE(a->item, NULL), a = a->next;

105         else

106             c->next = NODE(b->item, NULL), b = b->next;

107     for (; a != NULL; c = c->next, a = a->next)

108         c->next = NODE(a->item, NULL);

109     for (; b != NULL; c = c->next, b = b->next)        

110         c->next = NODE(b->item, NULL);

111     link first = tmp_head->next;

112     free(tmp_head);

113     return first;

114 }

115 

116 link sorted_list_merge_create1(link a, link b)

117 {

118     if (a == NULL || b == NULL)

119         return NULL;

120     return NODE(INF, sorted_list_merge_create_iter(a->next, b->next));

121 }

122 

123 link sorted_list_merge_in_place_iter(link a, link b)

124 {

125     link tmp_head = NODE(INF, NULL);

126     link c = tmp_head; //c as tail pointer for the list_c

127 

128     for (; a != NULL && b != NULL; c = c->next)

129         if (a->item < b->item)

130             c->next = a, a = a->next;

131         else

132             c->next = b, b = b->next;

133     c->next = a != NULL ? a : b; //link left ordered list

134     link first = tmp_head->next;

135     free(tmp_head);

136     return first;

137 }

138 

139 link sorted_list_merge_in_place1(link a, link b)

140 {

141     if (a == NULL || b == NULL)

142         return NULL;

143     link head = NODE(INF, sorted_list_merge_in_place_iter(a->next, b->next));

144     free(a);

145     free(b);

146     return head;

147 }

148 //Iterative implementation end here

149 

150 

151 //Recursive implementation begin here

152 link sorted_list_merge_create_rec(link a, link b)

153 {

154     link first = NULL;

155 

156     if (a == NULL) {

157         link tmp_head = NODE(INF, NULL);

158         link c = tmp_head; //c as tail pointer for left list

159         while (b != NULL) {

160             c->next = NODE(b->item, NULL);

161             c = c->next;

162             b = b->next;

163         }

164         link left = tmp_head->next;

165         free(tmp_head);

166         return left;

167     }

168     if (b == NULL) {

169         link tmp_head = NODE(INF, NULL);

170         link c = tmp_head; //c as tail pointer for left list

171         while (a != NULL) {

172             c->next = NODE(a->item, NULL);

173             c = c->next;

174             a = a->next;

175         }

176         link left = tmp_head->next;

177         free(tmp_head);

178         return left;

179     }

180     if (a->item < b->item) {

181         first = NODE(a->item, NULL);

182         first->next = sorted_list_merge_create_rec(a->next, b);

183     } else {

184         first = NODE(b->item, NULL);

185         first->next = sorted_list_merge_create_rec(b->next, a);

186     }

187     return first;

188 }

189 

190 link sorted_list_merge_create2(link a, link b)

191 {

192     if (a == NULL || b == NULL)

193         return NULL;

194     return NODE(INF, sorted_list_merge_create_rec(a->next, b->next));

195 }

196 

197 link sorted_list_merge_in_place_rec(link a, link b)

198 {

199     if (a == NULL)

200         return b;

201     if (b == NULL)

202         return a;

203     link first = NULL;

204     if (a->item < b->item) {

205         first = a;

206         first->next = sorted_list_merge_in_place_rec(a->next, b);

207     } else {

208         first = b;

209         first->next = sorted_list_merge_in_place_rec(a, b->next);

210     }

211     return first;

212 }

213 

214 link sorted_list_merge_in_place2(link a, link b)

215 {

216     if (a == NULL || b == NULL)

217         return NULL;

218     link head = NODE(INF, sorted_list_merge_in_place_rec(a->next, b->next));

219     free(a);

220     free(b);

221     return head;

222 }

223 //Recursive implementation end here

224 

225 void list_travel(link head)

226 {

227     for (head = head->next; head != NULL; head = head->next)

228         printf(head->next == NULL ? "%d
" : "%d ", head->item);

229 }

230 

231 void list_destroy(link head)

232 {

233     head->next == NULL ? free(head) : list_destroy(head->next);

234 }

 
테스트 예시:

ZhangHaiba-MacBook-Pro:code apple$ ./a.out

6

30 53 65 77 88 99

list_a travel: 30 53 65 77 88 99

9

11 22 33 44 55 100 120 199 211

list_b travel: 11 22 33 44 55 100 120 199 211

create list_c by using(merging) list_a and list_b nodes.

list_c travel: 11 22 30 33 44 53 55 65 77 88 99 100 120 199 211

merge list_c and list_a to list_d.

list_d travel: 11 22 30 30 33 44 53 53 55 65 65 77 77 88 88 99 99 100 120 199 211

list_b destroyed!

list_d destroyed!

 
단일 체인 표 의 합병 으로 두 개의 인터페이스 (함수) 를 제공 합 니 다: sortedlist_merge_create () 와 sortedlist_merge_in_place()。비 현지 합병 과 현지 합병 에 각각 대응 하 다.
두 함수 가 각각 쓸모 가 있 고 그 자리 에서 합병 하지 않 고 새로운 링크 를 만 들 며 입력 한 두 개의 링크 는 계속 사용 할 수 있 습 니 다.
현지에서 합병 하면 입력 한 두 개의 링크 a 와 b 를 하나의 링크 c 로 합 쳐 합병 하면 a 와 b 는 논리 적 으로 존재 하지 않 습 니 다.
 
여기 서 작 동 하 는 링크 는 앞장 서 는 노드 의 단일 링크 이기 때문이다.
함수 의 재 활용 성 을 고려 하여 먼저 디자인 된 합병 함수 A: 앞장 서지 않 는 노드 의 링크 두 개 를 받 고 앞장 서지 않 는 노드 의 (새로운) 링크 를 되 돌려 줍 니 다.
앞장 서 는 노드 의 링크 는 앞장 서지 않 는 노드 의 링크 의 한정 (부분 집합) 일 뿐이다.
그래서 케이스 함수 포장 을 통 해 이전 단계 에 실 현 된 합병 함수 A 를 디자인 하면 선두 노드 의 단일 체인 표 합병 함수 B 를 실현 할 수 있다.
병합 함수 B: 두 개의 선두 노드 의 링크 를 받 고 선두 노드 의 (새) 링크 를 되 돌려 줍 니 다.링크 에 들 어 오 는 헤드 노드 가 비어 있 으 면 안 되 며, 그렇지 않 으 면 NULL 로 돌아 갑 니 다.
A 함 수 는 상기 실현 중의
sorted_list_merge_create_iter () 와 sortedlist_merge_create_rec()
sorted_list_merge_in_place_iter () 와 sortedlist_merge_in_place_rec()
다음은 실현 방법의 측면 에서 수직 대 비 를 한다.
(1) 반복 실현
교체 실현 에서 임시 헤드 노드 를 빌 렸 습 니 다. 그래 야 첫 번 째 노드 의 지침 first 를 저장 할 수 있 습 니 다. first 로 돌아 가기 전에 임시 헤드 노드 를 먼저 방출 할 수 있 습 니 다.
1) 비 현지 합병
만약 에 b 가 a 가 아직 끝나 지 않 았 다 면 a 의 나머지 를 새 링크 뒤에 순서대로 복사 합 니 다.마찬가지
2) 현지 합병
만약 에 b 가 a 가 아직 끝나 지 않 았 다 면 a 남 은 링크 를 tail 포인터 c 에 한 번 에 연결 하면 효율 이 높다 고 말 할 수 있다.마찬가지
(2) 귀속 실현
1) 비 현지 합병
만약 에 링크 a 가 비어 있 으 면 b 남 은 링크 를 복사 합 니 다 (임시 헤드 노드 를 통 해 이 루어 지고 left 로 돌아 가기 전에 임시 헤드 노드 를 방출 합 니 다).마찬가지
그렇지 않 으 면 작은 노드 를 선택 하여 현재 링크 의 루트 노드 로 복사 한 다음 에 나머지 링크 를 합 쳐 서브 링크 로 한다.
2) 현지 합병
링크 a 가 비어 있 으 면 링크 b 로 바로 돌아 갑 니 다.마찬가지
그렇지 않 으 면 비교적 작은 노드 를 현재 링크 의 루트 노드 로 선택 한 다음 에 나머지 링크 를 합 쳐 서브 링크 로 한다.
 
케이스 함수 에 대해 서 는 현지에서 합병 하지 않 으 면 할 말 이 없고 현지에서 합병 하기 전에 a 와 b 의 머리 노드 를 방출 해 야 합 니 다.
클 라 이언 트 프로그램 (주 함수) 에서 c 와 a 를 현지에서 합병 한 후에 c 와 a 를 NULL 로 설정 할 책임 이 있 습 니 다. 호출 자 는 이때 c 와 a 가 존재 하지 않 는 다 는 것 을 알 기 때 문 입 니 다.
 
소결: 단일 체인 표 의 비 현지 합병 과 현지 합병 은 모두 체인 표 의 '꼬리 삽입 법' 을 이용 하여 표를 만 들 었 다.차이 점 은 전 자 는 노드 를 생 성하 고 후 자 는 노드 에 연결 하 며 후자 의 효율 이 더욱 높다 는 것 이다.
 
   \ # 이전 단계 로 돌아 가기