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!


Related articles: