C++L2-002 링크 의 무 게 를 제거 합 니 다.

2898 단어 C++체인 워 치
정수 키 가 있 는 링크 L 을 지정 합 니 다.절대 값 이 중복 되 는 키 노드 를 삭제 해 야 합 니 다.즉,모든 키 값 K 에 대해 서 는 첫 번 째 절대 값 만 K 와 같은 결점 이 유지 되 는 것 이다.또한 삭 제 된 모든 노드 는 다른 링크 에 저장 되 어야 합 니 다.예 를 들 어 L 을 21→-15→-15→-7→15 로 지정 하면 무 거 운 링크 21→-15→-7,그리고 삭 제 된 링크-15→15 를 출력 해 야 합 니 다.
입력 형식:
첫 번 째 줄 에 L 의 첫 번 째 결점 을 주 는 주소 와 하나의 정수 N(≤10 5,결점 총수)을 입력 하 십시오.하나의 결산 점 의 주 소 는 마이너스 5 자리 정수 이 고 빈 주 소 는 NULL-1 로 표시 합 니 다.
다음 N 줄 에서 줄 마다 다음 형식 으로 노드 를 설명 합 니 다.
주소 키 다음 노드
그 중에서 주 소 는 이 노드 의 주소 이 고 키 값 은 절대 값 이 104 를 초과 하지 않 는 정수 이 며 다음 노드 는 다음 노드 의 주소 입 니 다.
출력 형식:
먼저 무 거 운 링크 를 출력 한 다음 삭 제 된 링크 를 출력 합 니 다.각 노드 가 한 줄 을 차지 하고 입력 한 형식 으로 출력 합 니 다.
입력 예시:
00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854
출력 예시:
00100 21 23854
23854 -15 99999
99999 -7 -1
00000 -15 87654
87654 15 -1
생각:
많은 방법 이 실 현 될 수 있 습 니 다.저 는 배열 시 뮬 레이 션 동적 메모 리 를 선택 합 니 다.먼저 링크 를 만 들 고 옮 겨 다 니 겠 습 니 다.시간 복잡 도 는 O(n)이 고 형식 제어 가 좋 습 니까?아니면 printf 가 좋 습 니까?

#include<iostream>
#include<cstdio>
#include<cmath>
#define NULL -1

using namespace std;

typedef struct node {
	int val;
	unsigned int next;
}node;

node store[100001];//        
int flag[10001];//    

int main() {
	int num, startM;//p      
	cin >> startM >> num;

	for (int i = 0; i < num; i++) {
		int now, val, next;
		cin >> now >> val >> next;
		store[now].val = val;
		store[now].next = next;
	}//      

	int p1=startM,startS=NULL;
	int p2 = 100000,pre;
	bool k = true;
	while (p1 != NULL) {
		if (flag[abs(store[p1].val)] != 0) {
			store[pre].next = store[p1].next;
			store[p2].next = p1;
			store[p1].next = NULL;
			p2 = p1;
			if (k) {
				k = false;
				startS = p2;
			}
			p1 = store[pre].next;
		}
		else {
			flag[abs(store[p1].val)] = 1;
			pre = p1;
			p1 = store[p1].next;
		}
	}//      

	p1 = startM;
	while (p1 != NULL) {
		if(store[p1].next!=NULL)
			printf("%05d %d %05d
",p1, store[p1].val, store[p1].next); else printf("%05d %d %d
", p1, store[p1].val, store[p1].next); p1 = store[p1].next; } p1 = startS; while (p1 != NULL) { if (store[p1].next != NULL) printf("%05d %d %05d
", p1, store[p1].val, store[p1].next); else printf("%05d %d %d
", p1, store[p1].val, store[p1].next); p1 = store[p1].next; } return 0; }
여기 서 C++L2-002 링크 의 무 게 를 실현 하 는 것 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C+링크 의 무 게 를 제거 하 는 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 바 랍 니 다!

좋은 웹페이지 즐겨찾기