6.cpp

数据结构课程设计

#include "head.h"

//函数功能----[合并]  
//（6.1）将2个排序好（同序)的链表合并----链表A和链表B排序后结果在A中，B销毁
void creat61(h_list	&lead)
{
	int		i=0,j=0,temp=0;
	char	moniker1[12],moniker2[12];
	link	ha,hb,p,q,m,n;
	printf("请输入要合并链表的A的名字:");
	scanf("%s",moniker1);
	for(i=0;i<lead->length;i++)
	{
		temp=strcmp(lead->assistant[i]->name,moniker1);
		if(!temp)	break;		
	}
	if(!temp)	
	{
		printf("有此线性表!!!\n");
		ha=lead->assistant[i]->tou;
		//display(ha);
	}
	else	
	{
		printf("无此线性表!!!\n");
		return;
	}	
	temp=0;
	printf("请输入要合并链表的B的名字:");
	scanf("%s",moniker2);
	for(i=0;i<lead->length;i++)
	{
		temp=strcmp(lead->assistant[i]->name,moniker2);
		if(!temp)	break;		
	}
	if(!temp)	
	{
		printf("有此线性表!!!\n");
		hb=lead->assistant[i]->tou;
		//display(hb);
	}
	else	
	{
		printf("无此线性表!!!\n");
		return;
	}									//以上是确定是否有A，B两个线性表的程序
	q=hb;								//q,p后移,查hb表中下一个位置
	p=hb;
	p=p->next;
	if(p->data<p->next->data)			//判断A，B是递增还是递减链表
	{
		while(p)
		{
			n=ha;
			m=n;
			m=m->next;
			while(m&&p->data>m->data)	//递增算法
			{
				n=m;
				m=m->next;
			}
			q->next=p->next;
			n->next=p;
			p->next=m;
			p=q;
			p=p->next;
		}
		for(j=i;j<lead->length;j++)
		{	
			lead->assistant[j]=lead->assistant[j+1];
			lead->length--;
		}
	}
	else
	{
		while(p)
		{
			n=ha;
			m=n;
			m=m->next;
			while(m&&p->data<m->data)	//递减算法
			{
				n=m;
				m=m->next;
			}
			q->next=p->next;
			n->next=p;
			p->next=m;
			p=q;
			p=p->next;
		}
		for(j=i;j<lead->length;j++)
		{	
			lead->assistant[j]=lead->assistant[j+1];
			lead->length--;
		}
	}
	printf("成功合并所有线性表!!!");
}

//函数功能----[合并]  
//（6.2）将2个排序好（同序)的链表合并----链表A和链表B排序后结果在C中，A、B不变
void	creat62(h_list	&lead)
{
	int		i=0,j=0,temp=0;
	char	moniker1[12],moniker2[12];
	link	ha,hb,hc,p,q,m,n,f;
	lead->assistant[lead->length]=(h_table)malloc(LENG2);
	lead->assistant[lead->length]->tou=(link)malloc(LENG3);
	printf("请输入要合并到的链表c的名字:");
	scanf("%s",lead->assistant[lead->length]->name);
	hc=lead->assistant[lead->length]->tou;
	hc->next=NULL;
	lead->length++;							//以上为插入线性表						
	printf("请输入要合并链表的A的名字:");
	scanf("%s",moniker1);
	for(i=0;i<lead->length;i++)
	{
		temp=strcmp(lead->assistant[i]->name,moniker1);
		if(!temp)	break;		
	}
	if(!temp)	
	{
		printf("有此线性表!!!\n");
		ha=lead->assistant[i]->tou;
	}
	else	
	{
		printf("无此线性表!!!\n");
		return;
	}	
	temp=0;
	printf("请输入要合并的链表B的名字:");
	scanf("%s",moniker2);
	for(i=0;i<lead->length;i++)
	{
		temp=strcmp(lead->assistant[i]->name,moniker2);
		if(!temp)	break;		
	}
	if(!temp)	
	{
		printf("有此线性表!!!\n");
		hb=lead->assistant[i]->tou;
	}
	else	
	{
		printf("无此线性表!!!\n");
		return;
	}										//以上是确定是否有A，B两个线性表的程序
	n=hc;									//尾指针指向表头
	p=ha->next;
	while(p)								//非空结点
	{
		m=(link)malloc(LENG3);				//生成新结点
		m->data=p->data;					//装入输入的元素
		n->next=m;							//新结点链接到表尾
		n=m;								//尾指针指向新结点
		p=p->next;							//下一个结点
	}
	n->next=NULL;							//尾结点的next置为空指针
	q=hb;									//q,p后移,查hb表中下一个位置
	p=hb;
	p=p->next;
	if(p->data<p->next->data)				//判断A，B是递增还是递减链表
		while(p)
		{
			n=hc;
			m=n;
			m=m->next;
			while(m&&p->data>m->data)		//递增算法
			{
				n=m;
				m=m->next;
			}
			f=(link)malloc(LENG3);
			f->data=p->data;
			f->next=m;
			n->next=f;
			q=p;
			p=p->next;
		}
	else
		while(p)
		{
			n=hc;
			m=n;
			m=m->next;
			while(m&&p->data<m->data)		//递减算法
			{
				n=m;
				m=m->next;
			}
			f=(link)malloc(LENG3);
			f->data=p->data;
			f->next=m;
			n->next=f;
			q=p;
			p=p->next;
		}
		display(ha);
		display(hb);
		display(hc);
	printf("成功合并所有线性表!!!");
}

//函数功能---- 一般合并
//（6.3）链表A和链表B首尾相连在A中，B销毁
void creat63(h_list	&lead)
{
	int		i=0,j=0,temp=0;
	char	moniker1[12],moniker2[12];
	link	ha,hb,p;
	printf("请输入要合并链表的A的名字:");
	scanf("%s",moniker1);
	for(i=0;i<lead->length;i++)
	{
		temp=strcmp(lead->assistant[i]->name,moniker1);
		if(!temp)	break;		
	}
	if(!temp)	
	{
		printf("有此线性表!!!\n");
		ha=lead->assistant[i]->tou;
	}
	else	
	{
		printf("无此线性表!!!\n");
		return;
	}	
	temp=0;
	printf("请输入要合并链表的B的名字:");
	scanf("%s",moniker2);
	for(i=0;i<lead->length;i++)
	{
		temp=strcmp(lead->assistant[i]->name,moniker2);
		if(!temp)	break;		
	}
	if(!temp)	
	{
		printf("有此线性表!!!\n");
		hb=lead->assistant[i]->tou;
	}
	else	
	{
		printf("无此线性表!!!\n");
		return;
	}										//以上是确定是否有A，B两个线性表的程序
	printf("i=%d  length=%d\n",i,lead->length);	
	p=ha;
	while(p->next)
	{
		p=p->next;
	}
	p->next=hb->next;
	for(j=i;j<lead->length;j++)
	{	
		lead->assistant[j]=lead->assistant[j+1];
		lead->length--;
	}
	printf("成功合并所有线性表!!!");
}

//合并 (将2个排序好（同序）的链表合并)
void	main6(h_list	&lead)
{
	int		choice=1;
	while (choice!=0)
	{          
		printf("      ////////////////////////////////////////////////// \n");
		printf("      //  请输入数字 0 到 3 选择:                     // \n");	
		printf("      //  将2个排序好（同序）的链表合并               // \n");
		printf("      //  1.  链表A和链表B排序后结果在A中，B销毁      // \n");
		printf("      //  2.  链表A和链表B排序后结果在C中，A、B不变   // \n");
		printf("      //  一般合并                                    // \n");
		printf("      //  3.  链表A和链表B首尾相连在A中，B销毁        // \n");
		printf("      //  0.  退出程序!!!                             // \n");
		printf("      //  请输入你的选择:                             // \n");
		printf("      ////////////////////////////////////////////////// \n");
		scanf("%d",&choice);
		system("cls");
		switch (choice)
		{
			case 1:	 creat61(lead);break;	//函数功能----将2个排序好（同序)的链表合并----链表A和链表B排序后结果在A中，B销毁		
			case 2:  creat62(lead);break;	//函数功能----将2个排序好（同序)的链表合并----链表A和链表B排序后结果在C中，A、B不变
			case 3:  creat63(lead);break;	//函数功能----一般合并----链表A和链表B排序后结果在A中，B销毁
			case 0:  break;
			default: printf("输入错误!!!\n");
		}
	}
}