删除链表中的重复元素(删除链表重复数据)

本篇文章给大家谈谈删除链表中的重复元素,以及删除链表重复数据对应的知识点,希望对各位有所帮助,不要忘了收藏本站喔。

本文目录一览:

c++ 有序链表删除重复元素

给察郑全代码帮你调一下吧,你这个函数确实有问题

void delete_duplicate(LinkList head) {

    LinkNode* tmp=head;

    if(tmp == NULL)

return;

LinkNode* q;

    while(tmp!=NULL) {

        q = tmp-next;

if ( q )

{

if(tmp-data == q-data) 

{

LinkList t = q-next;

tmp-逗辩next = t;

free(q);

continue;

}

tmp=tmp-next;

  败指颂  }

}

已知单链表L,写一算法,删除其中的重复结点,要运行结果急求

您应该将单链表L的情况贴出来,否则怎么给您运行结果呢。

该问题最简单的算法如下:

1. 将L中的结点加入另一个链表L1中,预加入的结点的值若已经位于原链表中则不加入

2. 最巧穗终L1即为需要的结果

该算法实现最为简单,但是效率不高,可以做如下改进

结点加入L1时按照从小到大进行排序,新加入的结点依照顺序进行比较,这样符合加入条件的

结点就无需比较L1的全部元素,只需要比较到第一个比自己大的元素培蠢即可。

如果效率依然不够可以依据L链表中的数据取值区间做Hash,新加入的结点通过Hash表进行比较,若不存在则插入L1中并将其值加入Hash表。

如果L中的结点值的域太广,则可以依据L中的结点个数建立Hash表,运用线性再散列之类的方法处理冲突,从而优化算法。按照这个算法思想编写的程序如下。

#include stdio.h

#define INVAILD_VALUE -1000 //这个值一定要是无效值,即所有的结点元素都不可能取的值

typedef struct node{ //结点的结构

int data;

struct node *next;

}NODE;

typedef struct{ //链表的结构

NODE *head;

int len; //链表的长度

}List;

void deleteSameNode(List srclist) //删除相似的结点

{

if (srclist.len = 1) //如果结点只有一个或零个肯定不重复,无需配宽陪处理

return;

int len = srclist.len;

int *nHash = new int[2 * len]; //Hash表,设定为链表长的2倍,这样再散列时无需循环

for(int i = 0; i 2 * len; i++) //初始化Hash表,初始值都是无效值

nHash[i] = INVAILD_VALUE;

NODE *pos_Node;

NODE *tmp_Node;

pos_Node = srclist.head;

srclist.head = NULL;

while(pos_Node != NULL) //循环所有元素

{

//若利用哈希函数直接找到了此元素,则删除该元素

if(pos_Node-data == nHash[pos_Node-data%len])

{

srclist.len--;

tmp_Node = pos_Node;

pos_Node = pos_Node-next;

delete tmp_Node;

continue;

//若利用哈希函数找到的此元素为无效值,说明不重复加入链表中,并记录到Hash表中

} else if (INVAILD_VALUE == nHash[pos_Node-data%len]) {

nHash[pos_Node-data%len] = pos_Node-data;

tmp_Node = pos_Node;

pos_Node = pos_Node-next;

tmp_Node-next = srclist.head;

srclist.head = tmp_Node;

} else {

//否则需要线性在散列

for (int i = 1; i 2 * len; i++)

{

//若再散列时找到了,删除该元素

if (nHash[pos_Node-data%len + i] == pos_Node-data)

{

srclist.len--;

tmp_Node = pos_Node;

pos_Node = pos_Node-next;

delete tmp_Node;

break;

} else if (INVAILD_VALUE == nHash[pos_Node-data%len + i]) {

//若找不到,则将元素加入到Hash表,并加入该元素到链表

nHash[pos_Node-data%len + i] = pos_Node-data;

tmp_Node = pos_Node;

pos_Node = pos_Node-next;

tmp_Node-next = srclist.head;

srclist.head = tmp_Node;

break;

}

}

}

}

delete[] nHash; //释放哈希表空间

}

测试程序如下:

void main()

{

List list_a;

int i;

//建立链表,长度按照实际的设置,我这里为了简单设置为10个元素

list_a.len = 10;

list_a.head = NULL;

NODE *p_node;

NODE *p_free;

//链表元素,用数组记录便于初始化

int list[] = {1,3,5,7,8,5,4,3,2,2};

//初始化链表

for(i = 0; i 10; i++)

{

p_node = new NODE();

p_node-data = list[i];

p_node-next = list_a.head;

list_a.head = p;

}

//删除相同元素

deleteSameNode(list_a);

//输出结果链表,并释放空间

p_node = list_a.head;

while(p_node != NULL)

{

printf("%d ",p_node-data);

p_free = p_node;

p_node = p_node-next;

delete p_free;

}

}

输出:1 7 8 5 4 3 2

[img]

C++ 删除单链表相同元素

while( p!=NULL )

{

if((p-info)==(q-info))

这段代码中发现p节点和q节点是相等的,想要删除p节点,首先应该保存p节点前面的陪型派芦贺那个节点,即在第一次循环开始前(while(p!=NULL)前),先将pPrior = q,赋初值,然后再循环末尾处p=p-link前将pPrior = p;这样每次进入循环,发现相等的情况是,用p前面的节点(pPrior)指向p节点的下一个节点,就可以删除当前节点租扒p

c语言链表 删除相同的元素值

你只是对相邻的元素进行比较,所以只能删除相邻且相同的元素。如果按照你的思想,则要先经排序后的链表,再执行Puge(L)才能删除链表中所有的相同的元素。

以下是唯让我写的一个链表排序山激(冒泡法):

/*单链表排序(mark=1,降序;mark=0,升序)*/

void SortList(LNode *L,int mark)

{

int i,j,change=TRUE;

ElemType temp;

LNode *p=L-next,*q;

if(p (p-next)) //如果单链表长度2,则不用排序

{

for(j=1;jL-data change;j++)

{

change=FALSE;

p=L-next;

q=p-next;

for(i=0;iL-data-j;i++)

{

if((q-datap-data mark) || (q-datap-data (!mark)))

{

temp=p-data;

p-data=q-data;

q-data=temp;

change=TRUE;

}

p=q;

q=q-指唯局next;

}

}

}

printf("排序成功\r\n");

}

/*删除链表中相同的数据项(基于排序)*/

void DelSameItem(LNode *L)

{

LNode *p,*q;

SortList(L,0);

p=L;

q=L-next;

while(q)

{

if(p-data==q-data)

{

q=q-next ;

p-next =q;

}

p=p-next ;

q=q-next ;

}

}

关于删除链表中的重复元素和删除链表重复数据的介绍到此就结束了,不知道你从中找到你需要的信息了吗 ?如果你还想了解更多这方面的信息,记得收藏关注本站。

标签列表