데이터 구조 - 두 링크 의 교 집합, 차 집합, 집합

4922 단어 데이터 구조
[제목 은 회색 대학원 입 니 다.]
(2018 남개대학 초시) 두 개의 질서 있 는 머리 없 는 노드 의 체인 시계 La, Lb.함수 작성: 어떻게 가장 좋 은 방식 으로 두 사람의 교 집합 을 찾 고 결 과 를 새로운 링크 에 저장 하여 되 돌려 줍 니까?
단일 체인 시트 의 유형 정 의 는 다음 과 같 습 니 다. 
Typeddf struct LNode{ 
Element Type data;  
Struct LNode *next; 
 }LNode, *ListNode; 
 
#include
#include
#include
#define MIN 0xc0c0c0c0
#define MAX 0x3f3f3f3f
using namespace std; 

typedef int ElementType;
typedef struct LNode{ 
	ElementType data;  
	struct LNode *next; 
}LNode, *ListNode; 

void CreateLinkList(ListNode A, ListNode B)
{
	/*
		                
	*/
	int n = 6, m = 6;
	ElementType dataA[] = {1, 2, 3, 7, 8, 10};
	ElementType dataB[] = {1, 3, 5, 7, 9, 11};
	LNode *p, *q;
	p = A;
	p->data = dataA[0];
	p->next = NULL;
	for(int i = 1; i < n; i++)
	{
		q = (LNode*)malloc(sizeof(LNode));
		q->data = dataA[i];
		p->next = q;
		p = p->next;
		p->next = NULL;
	} 
	p = B;
	p->data = dataB[0];
	p->next = NULL;
	for(int i = 1; i < m; i++)
	{
		q = (LNode*)malloc(sizeof(LNode));
		q->data = dataB[i];
		p->next = q;
		p = p->next;
		p->next = NULL;
	} 
}

ListNode intersection(ListNode A, ListNode B)
{
	/*
		         
		  :
		        ,               
		1。            ,         
		2。                  ,             
		3。                  ,             
		 
	*/ 
	ListNode C = (ListNode)malloc(sizeof(ListNode));
	C->next = NULL;
	LNode *p, *q, *r;
	p = A;
	q = B;
	r = C;
	while(p!=NULL && q!=NULL)
	{
		if(p->data < q->data)
		{
			p = p->next;
		}
		else if(p->data == q->data)
		{
			LNode *s = (LNode*)malloc(sizeof(LNode));
			s->next = NULL;
			s->data = p->data;
			
			p = p->next;
			q = q->next;
			r->next = s;
			r = s;
		}
		else
		{
			q = q->next;
		}
	}
	return C->next;
} 
ListNode Union(ListNode A, ListNode B)
{
	/*
		         (      ) 
		  :
		        last             
		        ,               
		1。            ,   last        ,                   ,      。             
		2。                  ,           last  ,       ,           。               
		3。                  ,           last  ,       ,           。               
		4。             ,  last  ... 
	*/ 
	ListNode F = (ListNode)malloc(sizeof(ListNode));
	F->next = NULL;
	F->data = MAX;
	LNode *p, *q, *r, *last;
	p = A;
	q = B;
	r = F;
	last = F;
	while(p!=NULL && q!=NULL)
	{
		if(p->data < q->data)
		{
			if(p->data != last->data)
			{
				LNode *s = (LNode*)malloc(sizeof(LNode));
				s->next = NULL;
				s->data = p->data;
				
				r->next = s;
				last = p;
				r = s;
			}
			p = p->next;
		}
		else if(p->data == q->data)
		{
			if(p->data != last->data)
			{
				LNode *s = (LNode*)malloc(sizeof(LNode));
				s->next = NULL;
				s->data = p->data;
				
				r->next = s;
				last = p;
				r = s;
			}
			p = p->next;
			q = q->next;
		}
		else
		{
			if(q->data != last->data)
			{
				LNode *s = (LNode*)malloc(sizeof(LNode));
				s->next = NULL;
				s->data = q->data;
				
				r->next = s;
				last = q;
				r = s;
			}
			q = q->next;
		}
	}
	if(q != NULL)
		p = q;
	while(p != NULL)
	{
		if(p->data != last->data)
		{
			LNode *s = (LNode*)malloc(sizeof(LNode));
			s->next = NULL;
			s->data = p->data;
			
			r->next = s;
			last = p;
			r = s;
		}
		p = p->next;	
	}
	return F->next;
} 
ListNode Difference(ListNode A, ListNode B) 
{
	/*
		         
		  :
		        ,               
		1。            ,             
		2。                  ,               ,           
		3。                  ,             
		 	
	*/ 
	ListNode D = (ListNode)malloc(sizeof(ListNode));
	D->next = NULL;
	LNode *p, *q, *r;
	p = A;
	q = B;
	r = D;
	while(p!=NULL && q!=NULL)
	{
		if(p->data < q->data)
		{
			LNode *s = (LNode*)malloc(sizeof(LNode));
			s->next = NULL;
			s->data = p->data;
			
			p = p->next;
			r->next = s;
			r = s;
		}
		else if(p->data == q->data)
		{
			p = p->next;
			q = q->next;
		}
		else
		{
			q = q->next;
		}
		
	}
	while(p != NULL)
	{
		LNode *s = (LNode*)malloc(sizeof(LNode));
		s->next = NULL;
		s->data = p->data;
		p = p->next;
		r->next = s;
		r = s;
	}
	return D->next;
}

int main()
{
	ListNode A, B, C, D, E, F, q;
	A = (ListNode)malloc(sizeof(ListNode));
	B = (ListNode)malloc(sizeof(ListNode));
	
	//C         
	CreateLinkList(A, B);
	C = intersection(A, B);
	q = C;
	while(q!=NULL)
	{
		cout<data<next;
	}
	cout<data<next;
	}
	cout<data<next;
	}
	cout<data<next;
	}
	cout<

좋은 웹페이지 즐겨찾기