SDUT-2122 数据结构实验之链表七：单链表中重复元素的删除

seven_ • 2023年2月21日下午10:13 • Python • 阅读 647

数据结构实验之链表七：单链表中重复元素的删除
Time Limit: 1000MS Memory Limit: 65536KB
Submit Statistic Discuss
Problem Description

按照数据输入的相反顺序（逆位序）建立一个单链表，并将单链表中重复的元素删除（值相同的元素只保留最后输入的一个）。
Input

第一行输入元素个数 n (1 <= n <= 15)；
第二行输入 n 个整数，保证在 int 范围内。
Output

第一行输出初始链表元素个数；
第二行输出按照逆位序所建立的初始链表；
第三行输出删除重复元素后的单链表元素个数；
第四行输出删除重复元素后的单链表。
Example Input

10
21 30 14 55 32 63 11 30 55 30
Example Output

10
30 55 30 11 63 32 55 14 30 21
7
30 55 11 63 32 14 21

一道算是经典的数据结构题吧，删除元素是比较简单了，但是在这个题目中，还是有一些地方需要注意的，就比如
1. 1 2 3 3 – – -测试是否操作对最后一个元素也有效
2. 1 2 1 1 3 – – -测试连续出现相同元素是否操作有效
基本上注意到这两个地方就差不多了。

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;

typedef struct node{
    int num;
    struct node *next;
}Node,*List;

int Create(List &L,int n){           //逆序建立链表
  L = (List)malloc(sizeof(Node));
  L->next = NULL;
  while(n--){
    List p = (List)malloc(sizeof(Node));
    cin>>p->num;
    p->next = L->next;
    L->next =  p;
  }
}
int Print(List L){                 //按格式打印链表
  List p = L->next;
  int cou = 0;
  while(p){
    if(!cou){
        cout<<p->num;
        cou = 1;
    }
    else
        cout<<" "<<p->num;
    p = p->next;
  }
  cout<<endl;
}
int DelList(List &L, int n, int &e){     //n为链表长度，使用e接收删除元素之后的链表长度
  List p1 = L->next;
  int cou = n;
  while(p1){                             //最外层的循环，控制 p1 从头到尾走一遍
    List p2 = p1;
    while(p2->next){                     //因为没有使用双向链表，所以我们要使用 p2->next 的 num值与最外层的 p1 的 num 比较
        if(p2->next->num == p1->num){
            p2->next = p2->next->next;   //有相等的元素就 “跳过去” ，这里没有释放节点，也可以使用一个指针指向 p2->next 然后释放
            cou--;
        }
        else{
            p2 = p2->next;
        }
    }
    p1 = p1->next;
    p2 = p1;                           //p2 要与 p1 保持开始位置一致
  }
  e = cou;
}
/*int DelList2(List &L,int n,int &e){
   List p = L;
   int cou = n;
    while(p->next){
        List p1 = p->next->next;
        while(p1){
            if(p->next->num == p1->num){
                p->next = p->next->next;
                cou--;
            }
            p1 = p1->next;
        }
        p = p->next;
    }
    e = cou;
}*/                         //一开始看错了题目，以为是保留最后一个相同元素，删除前面的...=_=||,也贴一下。
int main(){
  int n;
  List L;
  int e;
  cin>>n;
  Create(L,n);
  cout<<n<<endl;
  Print(L);
  DelList(L, n, e);
  cout<<e<<endl;
  Print(L);
  return 0;
}