【2015年数据结构真题】

用单链表保存m个整数，结点的结构为 [data] [link]，且|data|<=n(n为正整数)。现要求设计一个时问复杂度尽可能高效的算法，对于链表中 data 的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。例如， 若给定的单链表 head 如下：则删除结点后的 head 为

1. 给出算法的基本设计思想。
2. 使用采用C或C++语言描述算法， 给出单链表结点的数据类型定义。
3. 根据设计思想， 采用C或C++语言描述算法，关键之处给出注释。
4. 说明你所设计算法的时间复杂度和空间算杂度。

方法一：暴力求解

定义两个指针，p指向21，q指向-15，p每走一步，q就走剩下所有元素并比较，相等就删除

时间：O(m²) 空间：O(1)

typedef struct Node
{
    int data;          //该节点权值
    struct Node *link; //下一个节点
} Node;

void ans(Node *HEAD)
{
    Node *p = HEAD->link; //外层遍历节点p
    Node *q, *r; //q是r的前一个节点
    while (p != NULL)
    {
        q = p;
        if (abs(r->data) == abs(p->data)) //r表示待比较节点
        {
            q->link = r->link;
            free(r);
        }
        else   //不相同时才修改q
            q = q->link;
    }
    p = p->link;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

方法二

算法的基本思想：

算法的核心思想是用空间换时间。使用辅助数组记录链表中已出现的
数值，从而只需对链表进行一趟扫描。
因为|data|≤n,故辅助数组 temp 的大小至少为 n+1,各元素的初值均
0。依次扫描链表中的各结点，同时检查 temp[|data|]的值，如果为 0，则
保留该结点，并令++temp[|data|]；否则，将该结点从链表中删除。

#include 
#include 
#include 

typedef struct ListNode
{
    int data;          //该节点权值
    struct Node *pNext; //下一个节点
} Node,*PNODE;

//筛选链表中绝对值重复的元素
void FiltrateRep(PNODE L,int len)
{
    int temp[len];
    
    memset(temp,0,sizeof(int)*len);//初始化位0

    PNODE pre,p;
    pre=L;
    while(pre->pNext!=NULL){
        p=pre->pNext;
        if(p!=NULL){
            if(temp[abs(p->data)]<1){
                ++temp[abs(p->data)];//辅助数组对应元素位置+1
                pre=p;
            }
            else{//如果temp[p->data]大于1,正在判断的元素，是重复的元素，需要删除
                pre->pNext=p->pNext;
                free(p);
            }
        }
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35