알고리즘 필기 연습 7.3 링크 처리 문제 F: 알고리즘 2 - 25 질서 있 는 단일 링크 삭제 중복 요소

알고리즘 필기 연습 문제 풀이 집합
링크
제목.
제목 설명 은 점차적으로 증가 하 는 정수 서열 에 따라 질서 있 는 단일 체인 표를 구성 하고 그 중의 중복 요 소 를 삭제 합 니 다.
입력 은 여러 조 의 테스트 데 이 터 를 포함 하고 각 조 의 테스트 데 이 터 는 한 줄 을 차지 하 며 첫 번 째 는 0 보다 큰 정수 n 으로 이 단일 체인 표 의 길 이 를 나타 내 고 그 다음 에 n 개의 정 수 를 따라 링크 의 모든 요 소 를 나타 낸다.정수 사 이 를 빈 칸 으로 나누다
출력 은 각 그룹의 테스트 데 이 터 를 대상 으로 합 니 다. 출력 은 두 줄 을 포함 합 니 다. 각각 삭제 전과 삭 제 된 링크 요 소 를 빈 칸 으로 구분 합 니 다.
링크 가 비어 있 으 면 한 줄 만 출력 합 니 다. list is empty
샘플 입력

5 1 2 3 4 5
5 1 1 2 2 3
0

샘플 출력

1 2 3 4 5 
1 2 3 4 5 
1 1 2 2 3 
1 2 3 
list is empty

사고의 방향deleteTheSame 이 함 수 를 중점적으로 말씀 드 리 겠 습 니 다. 즉, 체인 시계 에 무 게 를 줄 수 있 는 방법 입 니 다.

포인터 p 로 머리 결 점 head 의 링크 를 옮 겨 다 닌 다.

포인터 last 로 마지막 효과 적 인 결점 (효과 적 인 뜻 은 이 결점 이 보존 되 어야 한 다 는 것 이다. 예 를 들 어 링크 42 -> 42 -> 100 에 대해 첫 번 째 42 결점 과 100 결점 만 효과 적 인 결점 이 고 두 번 째 42 는 삭제 되 어야 한다).

먼저 이 함수 의 링크 가 비어 있 지 않 고 p 를 head->next 로 초기 화 합 니 다.

p != nullptr 시 선령 last = p 은 현재 의 유효 결산 점 을 기록 한 다음 에 p 은 링크 말단 방향 으로 계속 탐색 하고 만족 p != nullptr 과 p->data == last->data 만 만족 하면 p 을 앞으로 이동 시 켰 다.이 과정 에서 잘못된 노드 를 삭제 합 니 다 (메모리 누 출 방지).그래서 마지막 p 은 빈 지침 이거 나 다음 유효 노드 를 가리 키 거나 last->next = p; 다음 라운드 의 교 체 를 계속 합 니 다.

코드

#include 
struct Lnode {
	int data; 
	Lnode *next; 
};
void initLinklist(Lnode *&head, int n) {
	Lnode *tail = head;
	while (n--) {
		Lnode *p = new Lnode;
		scanf("%d", &(p->data));
		tail->next = p;
		p->next = nullptr;
		tail = p;
	} 
}
void deleteTheSame(Lnode *&head) {
	Lnode *p = head->next, *last;
	while (p) {
		last = p;
		while (p && p->data == last->data) {
			Lnode *temp = p;
			p = p->next;
			if (temp != last)
				free(temp);
		}
		last->next = p;
	} 
} 
void showLinklist(Lnode *&head) {
	Lnode *p = head->next;
	if (p) {
		while (p) {
			if (p != head->next)
				putchar(' '); 
			printf("%d", p->data);
			p = p->next;
		}
		putchar('
'); 
	}
} 
int main() {
	int n;
	while (scanf("%d", &n) != EOF) {
		if (n == 0) {
			puts("list is empty");
			continue;
		} 
		Lnode *head = new Lnode;
		head->next = nullptr;
		initLinklist(head, n);
		showLinklist(head);
		deleteTheSame(head); 
		showLinklist(head);
	} 
	return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

leetcode 스크립트 일기의 검증 두 갈래 검색 트리

두 갈래 나무를 정해 효과적인 두 갈래 검색 나무인지 아닌지를 판단한다. 두 갈래 검색 트리에는 다음과 같은 정의가 있습니다. 예 1: 두 갈래 나무[2,1,3],true로 돌아갑니다. 예 2: 두 갈래 나무[1,2...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

알고리즘 필기 연습 7.3 링크 처리 문제 F: 알고리즘 2 - 25 질서 있 는 단일 링크 삭제 중복 요소

좋은 웹페이지 즐겨찾기