代码如下
#include<iostream>
using namespace std;
#include <cmath>
struct Num_node
{
int data;
Num_node* next;
};
typedef Num_node* LinkList;
//创建头结点和头指针
int InitList(LinkList*L)
{
*L = new Num_node;
if (!(*L))
return 0;
(*L)->next = NULL;
return 1;
}
//向链表输入数据
void CreatList(LinkList* L,int n)
{
//p指向新结点,r指向最后一个结点
LinkList p, r;
//初始化r
r = *L;
int num;
cout << "请输入要保存的整数:" << endl;
for (int i = 0; i < n; i++)
{
cin >> num;
p = new Num_node;
p->data = num;
//把新结点接在最后
r->next = p;
//更新最末结点标志r
r = p;
r->next = NULL;
}
}
//对data中绝对值相等的结点,仅仅保留第一次出现的结点
void AbvList(LinkList* L)
{
//大概估测输入数据的绝对值在100以内
//用空间换时间
int flag[100];
for (int i = 0; i < 100; i++)
{
flag[i] = 0;
}
LinkList p, pre,s;
//初始化p和pre
p = (*L)->next;
pre = p->next;
//让p指向的结点中的值的绝对值作为数组flag的下标,把该下标内的0改为1,说明出现了该数据
flag[abs(p->data)] = 1;
while (pre)
{
s = pre->next;
//p结点的下一个结点数据域的数据与p不同的情况
if (flag[abs(pre->data)] == 0)
flag[abs(pre->data)] = 1;
//当pre指针指向的位置不是链表的最后一位,且数据域中的数据的绝对值在之前出现过
//删除pre此时指向的结点
else if (pre->next && flag[abs(pre->data)] == 1)
{
//用指针s记录待删除的结点位置
delete pre;
p->next = s;
}
//当pre指针指向的位置是链表的最后一位,且数据域中的数据的绝对值在之前出现过
//删除pre此时指向的结点
else if (pre->next == NULL && flag[abs(pre->data)] == 0)
{
//用指针s记录待删除的结点位置
delete pre;
p->next = NULL;
}
//让指针pre向前遍历
pre = s;
//指针p要一直在指针pre的后方,但不能pre向前走,p就向前走
//因为pre指向的结点数据域的绝对值要是在之前出现过,此时pre指向的结点就要删除
//删除pre结点后p不需要移动
//要是没有删除pre结点p就需要向前移动
if (p->next != pre)
p = p->next;
}
}
void Show(LinkList* L)
{
LinkList m = (*L)->next;
while (m)
{
cout << m->data << " " ;
m = m->next;
}
}
int main()
{
LinkList L;
//判断的同时创建头结点和头指针
if (InitList(&L) == 0)
{
cout << "链表创建失败" << endl;
return 0;
}
int n;
cout << "要输入的整数数量为:" << endl;
cin >> n;
//向链表输入数据
CreatList(&L,n);
//对data中绝对值相等的结点,仅仅保留第一次出现的结点
AbvList(&L);
Show(&L);
system("pause");
}
链表的建立就不需要多说什么了,主要是程序中的AbvList()函数实现了判断绝对值相同的数,并进行删除的操作。
AbvList()函数的逻辑:
创建一个数组flag,这个数组用来储存链表数据域的数据(所以这个方法也导致了一个缺点,用户输入的数不能超过我们建立的数组的大小,要不然就无法储存就会报错)定义两个指针p和pre遍历链表,并始终让p指针在pre指针的后方(要让p和pre相互配合才能删掉结点),让p指针指向第一个结点并以这个结点的数据域的数据作为数组flag的下标,在数组flag的该下标的值改为1,表示这个下标的绝对值出现过(比如结点的数据域的数据为-8,则将数组下标为8的值改为1,表示出现过绝对值为8的数,要是后面再出现便可以删除后出现的结点)(注意因为数组不能确定每一个空间都能因为链表而被赋值,所以在一开始便要将数组中的值全初始化为0),然后同样判断pre指针指向的结点数据域的值(有3种情况)
(1).要是在数组中以该数据域作为下标的空间中储存的值为0,说明之前没有出现过,便把数组中该空间储存的值改为1,让pre指针和p指针向前遍历一个结点。
(2).要是在数组中以该数据域作为下标的空间中储存的值为1,说明之前出现过,且pre->next不为空说明,不是链表的最后一个结点,便删除此时pre指向的结点,让pre指针向前遍历一个结点,p指针不动(注意此时pre指向的结点已经删除了,所以pre向前遍历一个结点,p指针还是在pre结点后面)
(3).要是在数组中以该数据域作为下标的空间中储存的值为1,说明之前出现过,且pre->next为空说明,是链表的最后一个结点,便删除此时pre指向的结点,让p指针指向空。
处理完后,直接输出此时的链表,便是最终结果。