link3.c

来自「自己做的常用库和实现的数据结构。public domain.」· C语言 代码 · 共 84 行

/* Demo of merging 2 ascending/descending dynmaic link into 1, in same order.
 *
 * Written by Cyril Hu ([e-mail]), public domain.
 */

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

typedef struct l {
	int sn;
	struct l *next;
} L;

L *ssort(L *head)
{
	int tt;
	L *p, *t, *q;
	for(p=head; p; p = p->next) {
		for(t=p, q = p->next; q; q = q->next)
			if(t->sn > q->sn)
				t = q;
		tt = p->sn; p->sn = t->sn; t->sn = tt;
	}
	return head;
}

L *initlink(int n)
{
	int i;
	L a, *p;
	for(p = &a, i=0; i<n; i++) {
		if((p->next = malloc(sizeof(L))) == NULL) {
			fprintf(stderr, "Fatal: mem alloc fail !");
			exit(EXIT_FAILURE);
		}
		p = p->next;
		p->sn =(int)( (double)(n+50) * rand()/(RAND_MAX + 1.0) );
	}
	p->next = NULL;
	return ssort(a.next);
}

void pntlink(L *head)
{
	L *p;
	for(p=head; p; p = p->next)
		printf("%2d ", p->sn);
	if(head)
		puts("");
}

L *mergelink(L *a, L *b)
{
	L *c = NULL, *head = NULL;	
	if(a && b) {
		if(a->sn < b->sn)
			c = head = a,  a = a->next;
		else
			c = head = b,  b = b->next;
	}
	while(a && b) 
		if(a->sn < b->sn)
			c = c->next = a, a = a->next;
		else
			c = c->next = b, b = b->next;
	if(c)
		c->next = b ? b : a;
	return head;
}

int main(void)
{
	L *a, *b, *c;
	srand(time(NULL));
	a = initlink(5);	
	pntlink(a);
	b = initlink(20);	
	pntlink(b);
	c = mergelink(a,b);
	pntlink(c);
	return EXIT_SUCCESS;
}