[데이터 구조] 순서 표 연습

(주: 다음은 순서 표 부분 연습 문제 의 연습 인 데 그 중에서 순서 표 와 단일 체인 표 의 관련 함 수 를 사 용 했 기 때문에 독자 들 은 참고 할 수 있 습 니 다. "https://blog.csdn.net/xing1584114471/article/details/83004289"단일 체인 표 와 관련 된 함수 실현 을 이해 하고 참고"https://blog.csdn.net/xing1584114471/article/details/83655736"순서 표 의 함수 실현 파악)
/ * (1) 설정 순서 표 va 의 데이터 요소 가 점점 질서 가 있 습 니 다.이 표 의 질서 성 을 유지 하기 위해 x 를 순서 표 의 적당 한 위치 에 삽입 하 는 알고리즘 을 시험 적 으로 쓰 십시오. * / 

int Insert_orderly(Psqlist list, ElemType val)
{
	assert(list != NULL);
	int i = 0;
	while( list->elem[i] < val && i < list->count)
	{
		i++;
	}
	InsertSqList(list, i , val);
	return TRUE;
}

/ * (2) 알고리즘 을 시험 적 으로 작성 하여 순서 표 의 현지 역 치 를 실현 합 니 다. 즉, 원 표 의 저장 공간 을 이용 하여 선형 표 a1... an 을 an... a1 * 로 역 치 합 니 다. 

void Inversion(Psqlist list)
{
	assert(list != NULL);
	int i = 0;
	int j = list->count - 1;
	int tmp = 0;
	while(i != j)
	{
		tmp = list->elem[i];
		list->elem[i] = list->elem[j];
		list->elem[j] = tmp;
		i++;
		j--;
	}
}

/*   (3) 요소 값 에 따라 질서 있 게 배 열 된 선형 표 A 와 B 가 두 개 있다 고 가정 하면 모두 단일 체인 표 로 저장 구 조 를 만 듭 니 다. 알고리즘 을 작성 하여 A 표 와 B 표를 요소 값 에 따라 질서 있 게 (즉, 질서 있 게 증가 하지 않 고 표 에 값 이 같은 요 소 를 포함 할 수 있 도록 합 니 다) 배 열 된 선형 표 C 로 분류 하고 원 표 (즉 A 표 와 B 표) 의 결점 공간 구조 C 표를 이용 하 십시오. * / 

Node* Decrease_Combine(Plist list_a, Plist list_b) 
{
	assert(list_a != NULL);
	assert(list_b != NULL);

	Node *p_a = list_a->head.next;
	Node *p_b = list_b->head.next;
	Node *head_c = p_a->data > p_b->data ? &list_b->head : &list_a->head;//       
	Node *p_c = head_c;

	while( p_a  != NULL && p_b != NULL)
	{
		if(p_a->data >= p_b->data)
		{
			p_c->next = p_b;
			p_b = p_b->next;
		}
		else
		{
			p_c->next = p_a;
			p_a = p_a->next;
		}
		p_c = p_c->next;
	}
	while( p_a != NULL)
	{
		p_c->next = p_a;
		p_c = p_c->next;
		p_a = p_a->next;
	}
	while( p_b != NULL)
	{
		p_c->next = p_b;
		p_c = p_c->next;
		p_b = p_b->next;
	}

	//  
	struct Node *m = head_c->next;
	struct Node *f = NULL;
	struct Node *l = m->next;
	while(1)
	{
		m->next = f;
		f = m;
		m = l;
		if( m == NULL)
		{
			break;
		}
		l = l->next;
	}
	head_c->next = f;
	return head_c;
}

 /*     (4) 이미 알 고 있 는 A, B 와 C 는 세 개의 질서 있 는 선형 표 이다. 현 재 는 A 표 에 대해 다음 과 같은 조작 을 해 야 한다. B 표 에 나타 나 고 C 표 에 나타 난 요 소 를 삭제 해 야 한다.순서 표를 작성 하여 상기 조작 을 실현 하 는 알고리즘 을 작성 하고 알고리즘 의 시간 복잡 도 를 분석 하 십시오 (주의: 문제 에서 같은 표 의 요소 값 이 각각 다르다 는 것 을 특별히 가리 키 지 않 았 습 니 다) * /

void Delete_Repetition(Plist list_a, Plist list_b, Plist list_c)
{
	assert(list_a != NULL);
	assert(list_b != NULL);
	assert(list_c != NULL);

	int pos = 1;
	Node *p_a = list_a->head.next;
	Node *p_b = list_b->head.next;
	Node *p_c = list_c->head.next;
	
	while( p_a != NULL && p_b != NULL && p_c != NULL)
	{
		if(p_b->data > p_c->data)
		{
			p_c = p_c->next;
			continue;
		}
		else if(p_b->data < p_c->data)
		{
			p_b = p_b->next;
			continue;
		}
		else
		{
			ElemType tmp = p_b->data;
			p_b = p_b->next;
			p_c = p_c->next;	
			while(p_a != NULL)
			{
				if(p_a->data < tmp)
				{
					p_a = p_a->next;
					pos++;		
					continue;
				}
				else if(p_a->data == tmp)
				{
					p_a = p_a->next;
					DeleteLinkList(list_a, pos);
				}
				else
				{			
					break;
				}
			}
		}		
	}
}

/ * (5) 두 순서 표 가 점점 질서 있 게 증가 하고 C = AUB 를 실행 합 니 다. 알고리즘 시간 복잡 도 는 O (n + m) (A, B 라 는 두 순서 표 는 한 번 만 옮 겨 다 닐 수 있 습 니 다) 입 니 다. * /

SqList Combine(Psqlist list_a, Psqlist list_b)
{
	assert(list_a != NULL);
	assert(list_b != NULL);

	SqList list_c;
	InitSqList(&list_c);
	int a = 0;
	int b = 0;
	int c = 0;

	while(a < list_a->count &&  b < list_b->count)
	{
		if(list_a->elem[a] <= list_b->elem[b])
		{
			InsertSqList(&list_c, c, list_a->elem[a]);
			if(list_a->elem[a] == list_b->elem[b])
			{
				b++;
			}
			a++;
		}
		else 
		{
			InsertSqList(&list_c, c, list_b->elem[b]);
			b++;
		}
		c++;
	}
	while(a < list_a->count)
	{
		InsertSqList(&list_c, c, list_a->elem[a]);
		c++;
		a++;
	}
	while(b < list_b->count)
	{
		InsertSqList(&list_c, c, list_b->elem[b]);
		c++;
		b++;
	}
	return list_c;
}

함수 테스트

int main()
{
/*
Combine    
********************************************************
	SqList list_a;
	SqList list_b;
	InitSqList(&list_a);
	InitSqList(&list_b);

	for( int i = 0; i < 10; i++)
	{
		InsertSqList(&list_a, i, i);
		InsertSqList(&list_b, i, i * 2);
	}
	ShowSqList(&list_a);
	ShowSqList(&list_b);
	printf("***************************
");
	SqList list_c = Combine(&list_a, &list_b);
	ShowSqList(&list_c);
********************************************************
*/

/*
Delete_Repetition    
********************************************************
	Linklist list_a;
	Linklist list_b;
	Linklist list_c;
	InitLinkList(&list_a);
	InitLinkList(&list_b);
	InitLinkList(&list_c);

	for( int i = 0; i < 10; i++)
	{
		InsertLinkList(&list_a, i + 2 , i );
		InsertLinkList(&list_b, i * 2, i );
		InsertLinkList(&list_c, i + 1, i );
	}
	Show(&list_a);
	Show(&list_b);
	Show(&list_c);
	printf("***************************
");
	Delete_Repetition(&list_a, &list_b, &list_c);
	printf("****************************
");
	Show(&list_a);
********************************************************
*/

/*
Decrease_Combine     
********************************************************
	Linklist list_a;
	InitLinkList(&list_a);
	Linklist list_b;
	InitLinkList(&list_b);

	for( int i = 0; i < 5; i++)
	{
		InsertLinkList(&list_a, i + 1, i );
	}
	Show(&list_a);

	for( int i = 0; i < 8; i++)
	{
		InsertLinkList(&list_b, i + 3, i);
	}
	Show(&list_b);

	Node * tmp = Decrease_Combine(&list_a, &list_b);
	tmp = tmp->next;

	while(tmp != NULL)
	{
		printf("%3d",tmp->data);
		tmp = tmp->next;
	}
	printf("
");
********************************************************
*/

/*
Inversion     
********************************************************
	SqList list;
	InitSqList(&list);
	for( int i = 0; i < 15; i++)
	{
		InsertSqList(&list, i, i);
	}
	ShowSqList(&list);
	Inversion(&list);
	ShowSqList(&list);
********************************************************
*/

/*
Insert_orderly     
********************************************************
	Insert_orderly(&list, 11);
	ShowSqList(&list);

	Insert_orderly(&list, 19);
	ShowSqList(&list);
********************************************************
*/
	return 0;
}