The C language data structure implements linked list de duplication instances
- 2020-05-26 09:52:52
- OfStack
The C language data structure implements linked list de-duplication instances
Topic and analysis
List to heavy
The time limit
300 ms
Memory limit
65536 kB
Code length limitation
8000 B
Sentenced to topic program
Standard
Given a single linked list L with integer key values, you are asked to write a program that removes the absolute values of those key values and has duplicate nodes. That is, for any key value K, only the first node whose key value or its absolute value is equal to K can be retained. At the same time, all deleted nodes must be saved in another linked list. For example, if L is 21→-15→-15→-7→15, then you must output the de-duplicated list 21→-15→-7, and the deleted list -15→15.
Input format:
Enter the first line containing the address of the first node in the list, as well as the number of nodes N ( < = a positive integer of 105. The node address is a non-negative 5-bit integer, and the NULL pointer is denoted by -1.
Then, each row of N gives the information of 1 node in the following format:
Address Key Next
Where Address is the address of the node, Key is the integer whose absolute value does not exceed 104, and Next is the address of the next node.
Output format:
First output the de-weighted list, and then output the list of deleted nodes. Each node occupies 1 row and is output in the input format.
Input sample:
00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854
Output sample:
00100 21 23854
23854 -15 99999
99999 -7 -1
00000 -15 87654
87654 15 -1
3. Code and results
//L2-002. List to heavy
/*
What you get is an out-of-order list, an order that makes it a normal sequence
Then start the output list with the collection set To see if the absolute has been output, if so, put it on the chain where the delete list is located
*/
#include <iostream>
#include <algorithm>
#include <set>
#include <cmath>//abs function
using namespace std;
string firstAdd;
int n;
struct node{
string add;
int value;
string next;
int sortNul;
int vis;
}a[10005],b[10005],d[10005];
bool operator <(const node &p,const node &p1){
return p.sortNul<p1.sortNul;
}
// Read the data
void readData(){
cin>>firstAdd>>n;
for(int i=1;i<=n;i++){
cin>>a[i].add>>a[i].value>>a[i].next;
a[i].sortNul=0;
a[i].vis=0;
}
}
void printData(){
for(int i=1;i<=n;i++){
cout<<a[i].add<<" "<<a[i].value<<" "<<a[i].next<<" "<<a[i].sortNul<<endl;
}
}
// Make the list sortNum Number order
void findSortNum(){
string next(firstAdd);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(!a[j].vis&&a[j].add==next){
a[j].sortNul=i;
a[j].vis=1;
next=a[j].next;
break;
}
}
}
}
// find To list b and To delete a linked list d
set<int> set1;
int b1=0,d1=0;
void findAns(){
for(int i=1;i<=n;i++){
if(!set1.count(abs(a[i].value))){
set1.insert(abs(a[i].value));
b[++b1]=a[i];
}
else{
d[++d1]=a[i];
}
}
// Revised list
for(int i=1;i<b1;i++){
b[i].next=b[i+1].add;
}
b[b1].next="-1";
for(int i=1;i<d1;i++){
d[i].next=d[i+1].add;
}
d[d1].next="-1";
}
// Output to duplicate the list and To delete a linked list
void printAns(){
for(int i=1;i<=b1;i++){
cout<<b[i].add<<" "<<b[i].value<<" "<<b[i].next<<endl;
}
for(int i=1;i<=d1;i++){
cout<<d[i].add<<" "<<d[i].value<<" "<<d[i].next<<endl;
}
}
int main(){
//freopen("in.txt","r",stdin);
readData();
findSortNum();
sort(a+1,a+n+1);
//printData();
findAns();
//cout<<"-----------------------------------------"<<endl;
printAns();
return 0;
}
The above is to the linked list to the heavy explanation, local to the data structure of the article is still a lot, hope you can search and view, thank you for reading, hope to help you, thank you for the support of the site!