删除单链表中 值 相同的结点与删除单链表中 绝对值 相同的结点
·
1 带头结点递增有序单链表L,删除表中相同元素
void Delete(LinkList &L){
LinkList p=L->next;
LinkList q;
while(q){
q=p->next;
if(p->data!=q->data){
p=p->next;
q=q->next;
}
else{
p->next=q->next;
free(q);
}
}
}
2 带头结点无序单链表L,删除表中相同元素
void Delete(LinkList &L){
LinkList p=L->next;
LinkList q,pre,t;
while(p){
pre=p; //q的前驱结点pre
q=p->next;
while(q){ //查找链表中有无和p值相同的结点
if(p->data!=q->data){
q=q->next;
pre=pre->next;
}
else{ //找到则删除
t=q;
q=q->next;
pre->next=q;
free(t);
}
}
p=p->next; //继续判断下一个结点
}
}
3 单链表删除绝对值相等的节点
void delCommonValue(LinkList& L, int n) {
LNOde* p = L, * r;
int* q, m;
q = (int*)malloc(sizeof(int) * (n + 1)); //申请n+1个位置的辅助空间
for (int i = 0; i < n + 1; i++){
*(q + i) = 0; //数组元素初始值赋值0
}
while (p->next != NULL) {//遍历单链表元素
m = p->next->data > 0 ? p->next->data : -p->next->data; //判断元素的正负
if (*(q + m) == 0) { //判断该节点的data是否出现过
*(q + m) = 1; //第一次出现
p = p->next; //保留
}
else { //重复出现则删除
r = p->next;
p->next = r->next;
free(r);
}
}
free(q);
arrayList(L);
}
4 删除单链表中绝对值相同的节点
#include <iostream>
#include<math.h>
using namespace std;
struct Lnode{
int data;
Lnode *link;
};
typedef Lnode* Linklist;
Linklist get_data(int m)//建表 尾插法,也可以建立尾指针
{
Linklist head=new Lnode;
Linklist t=head;
for(;m>0;m--)
{
Lnode *p=new Lnode;
cin>>p->data;
head->link=p;
head=head->link;
}
head->link=NULL;
return t;
}
void delete_repeat(Linklist p,int n)
{
int *a=new int[n+1];//记录绝对值为i的数是否已经出现
int i;
for(i=0;i<=n;i++)//初值置为0,表示未出现
a[i]=0;
while(p->link)
{
int t=abs(p->link->data);
if(a[t]==0)
{
a[t]=1;//首次出现,记录为已出现
p=p->link;//保留结点
}
else{//重复出现,删除
Lnode *t=p->link;
p->link=p->link->link;
delete t;
}
}
delete []a;
}
void print_Linklist(Linklist head)
{
while(head->link)
{
head=head->link;
cout<<head->data<<' ';
}
cout<<endl;
}
int main()
{
int m,n;
cin>>m>>n;
Linklist head=get_data(m);
delete_repeat(head, n);
print_Linklist(head);
return 0;
}
更多推荐
所有评论(0)