【数据结构-带头结点的单链表】二表合一及排序 *** 作

【数据结构-带头结点的单链表】二表合一及排序 *** 作,第1张

来自数据结构 ( c语言版 ) 的一个实验题

题目大意:已知两个带头结点的单链表L1和L2(结点值按升序排序),现在要将这两个表合并成一个表,先升序合并、输出,再降序合并,输出。


思路:因为我写的函数破坏了原来表的结构(lll¬ω¬),所以我直接在升序排序前复制了h1和h2的值(主要是没写出来不破坏结构的qwq!!!)

代码:

#include
#include
typedef struct link_node{
	int info;
	struct link_node *next;
}node;
typedef node *linklist;
linklist init()
{
	node *head;
	head=(node*)malloc(sizeof(node));
	head->next=NULL;
	return head;
}
linklist creatbyqueue()
{
	linklist head=init(),r,s;
	int x;
	head->next=r=NULL;
	printf("请输入若干整数序列:\n");
	scanf("%d",&x);
	while(x){
		s=(linklist)malloc(sizeof(node));
		s->info=x;
		if(head->next==NULL) head->next=s;
		else r->next=s;
		r=s;
		scanf("%d",&x);
	}
	if(r) r->next=NULL;
	return head;
}
linklist copy(linklist L)
{
	linklist head=init(),r,s,pl=L->next;
	head->next=r=NULL;
	while(pl&&pl->info){
		s=(linklist)malloc(sizeof(node));
		s->info=pl->info;
		if(head->next==NULL) head->next=s;
		else r->next=s;
		r=s;
		pl=pl->next;
	}
	if(r) r->next=NULL;
	return head;
}
void delList(linklist head)
{
 	linklist p=head->next;
 	while(p){
 		head=p->next;
 		free(p);
 		p=head;
	}
	return ;
}
void print(linklist head)
{
 	linklist p;
	int i=0;
 	p=head->next;
 	printf("List is:\n");
 	while(p){
 		printf("%-5d",p->info);
 		p=p->next;
 		i++;
 		if(i%10==0) printf("\n");
	}
	printf("\n");
	return ;
}
linklist mergeAscend(linklist L1,linklist L2)
{
    linklist L3,r,p,q;
    L3=r=(linklist)malloc(sizeof(node));
    p=L1->next;
    q=L2->next;
    while(p&&q){
        if(p->infoinfo){
            L1->next=p->next;
            r->next=p;
            r=p;
			p=L1->next;
        }
        else{
            L2->next=q->next;
            r->next=q;
            r=q;
        	q=L2->next;
		}
    }
	while(p){
        L1->next=p->next;
    	r->next=p;
        r=p;
		p=L1->next;
    }
	while(q){
        L2->next=q->next;
        r->next=q;
        r=q;
        q=L2->next;
	}
	r->next=NULL;
	free(L1);
	free(L2);
    return L3;
}
linklist mergeDescend(linklist L1,linklist L2)
{
	linklist L3,r,q,p;
	L3=r=(linklist)malloc(sizeof(node));
	L3->next=NULL;
	p=L1->next;
	q=L2->next;
	while(p&&q){
		if(p->infoinfo){
		 	L1->next=p->next;
		 	p->next=r->next;
		 	r->next=p;
		 	p=L1->next;
		}
		else{
	 		L2->next=q->next;
	 		q->next=r->next;
	 		r->next=q;
	 		q=L2->next;		
		}
	}
	while(p){
		L1->next=p->next;
		p->next=r->next;
		r->next=p;
		p=L1->next;
	}
	while(q){
		L2->next=q->next; 
		q->next=r->next;
		r->next=q;
		q=L2->next;
	}
	free(L1);
	free(L2);
	return L3;
}
int main()
{
	linklist h1,h2,h3,h4,h5;
	h1=creatbyqueue();
	h2=creatbyqueue();
	h4=copy(h1);
	h5=copy(h2);
	print(h1);
	print(h2);
	h3=mergeAscend(h1,h2);
	print(h3);
	h3=mergeDescend(h4,h5);
	print(h3);
	delList(h3);
	return 0;
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/568831.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-09
下一篇 2022-04-09

发表评论

登录后才能评论

评论列表(0条)

保存