快捷導(dǎo)航

C++ 實(shí)現(xiàn)L2-002 鏈表去重

更新時(shí)間：2021年07月06日 15:55:19 作者：一只特立獨(dú)行的貓

這篇文章主要介紹了C++ 實(shí)現(xiàn)L2-002 鏈表去重,本文通過(guò)簡(jiǎn)要的案例,解題思路講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

給定一個(gè)帶整數(shù)鍵值的鏈表 L，你需要把其中絕對(duì)值重復(fù)的鍵值結(jié)點(diǎn)刪掉。即對(duì)每個(gè)鍵值 K，只有第一個(gè)絕對(duì)值等于 K 的結(jié)點(diǎn)被保留。同時(shí)，所有被刪除的結(jié)點(diǎn)須被保存在另一個(gè)鏈表上。例如給定 L 為 21→-15→-15→-7→15，你需要輸出去重后的鏈表 21→-15→-7，還有被刪除的鏈表 -15→15。

輸入格式：

輸入在第一行給出 L 的第一個(gè)結(jié)點(diǎn)的地址和一個(gè)正整數(shù) N（≤105，為結(jié)點(diǎn)總數(shù)）。一個(gè)結(jié)點(diǎn)的地址是非負(fù)的 5 位整數(shù)，空地址 NULL 用 −1 來(lái)表示。

隨后 N 行，每行按以下格式描述一個(gè)結(jié)點(diǎn)：

地址鍵值下一個(gè)結(jié)點(diǎn)

其中地址是該結(jié)點(diǎn)的地址，鍵值是絕對(duì)值不超過(guò)104的整數(shù)，下一個(gè)結(jié)點(diǎn)是下個(gè)結(jié)點(diǎn)的地址。

輸出格式：

首先輸出去重后的鏈表，然后輸出被刪除的鏈表。每個(gè)結(jié)點(diǎn)占一行，按輸入的格式輸出。

輸入樣例：

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

思路：
很多辦法都可以實(shí)現(xiàn)，我選擇數(shù)組模擬動(dòng)態(tài)內(nèi)存，先建立一個(gè)鏈表再遍歷，時(shí)間復(fù)雜度是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];//開(kāi)辟一片模擬內(nèi)存
int flag[10001];//標(biāo)記結(jié)點(diǎn)

int main() {
	int num, startM;//p標(biāo)記當(dāng)前節(jié)點(diǎn)
	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;
	}//鏈表構(gòu)建完成

	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\n",p1, store[p1].val, store[p1].next);
		else
			printf("%05d %d %d\n", 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\n", p1, store[p1].val, store[p1].next);
		else
			printf("%05d %d %d\n", p1, store[p1].val, store[p1].next);
		p1 = store[p1].next;
	}
	return 0;
}

到此這篇關(guān)于C++ 實(shí)現(xiàn)L2-002 鏈表去重的文章就介紹到這了,更多相關(guān)C++ 鏈表去重內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: