13.删除单链表中重复的元素

水深无声 2022-05-26 10:39 224阅读 0赞

思路：

使用哈希表。

从头扫描，将出现过的节点存入哈希表中。

如果元素已经在哈希表中出现过则删除，没有则存入。

注意：

删除时需要知道前一节点。

我使用的链表中存储的是char型变量，所以哈希表即为含有256个元素的数组。

如果存储的是其他数据类型，则可以使用stl中的hash\_set容器。

// LinkTable.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include <iostream>
    #include <string>
    using namespace std;
    
    //链表的结构体
    struct node
    {
    	char val;
    	node * next;
    };
    
    //建立链表
    struct node * create( string & str_link )
    {
    	int len = str_link.length();
    
    	struct node * phead = new node();     //带有表头的链表，表头中不存储任何元素
    	struct node * preNode = phead;
    	for( int i=0; i<len; i++ )
    	{
    		struct node * pNode = new node();
    		pNode->val = str_link[i];
    		pNode->next = NULL;
    		preNode->next = pNode;
    		preNode = pNode;
    	}
    	return phead;
    }
    
    //输出链表
    void out_link( struct node * phead )
    {
    	if( phead == NULL )
    		return;
    	struct node * pNode = phead->next;
    	while( pNode )
    	{
    		cout <<pNode->val;
    		pNode = pNode->next;
    	}
    	cout << endl;
    }
    
    //去掉重复元素
    void delete_repeat_element( struct node * phead )
    {
    	if( !phead || !phead->next ) return;
    	int * hashTable = new int[256](); //加括号是为了将hashTable中所有元素初始化为0
    	struct node * pNode = phead->next;
    	struct node * pPreNode = phead;
    	while( pNode )
    	{
    		if( hashTable[pNode->val] !=0 )		//说明已经出现过，该结点要删除
    		{
    			pPreNode->next = pNode->next;
    			delete pNode;			//删除结点
    			pNode = pPreNode->next;
    		}
    		else					//没有出现过，则置出现标记
    		{
    			hashTable[pNode->val] = 1;
    			pPreNode = pNode;
    			pNode = pNode->next;
    		}
    	}
    	delete [] hashTable;                 //释放资源
    }
    
    
    
    void test()
    {
    	string str;
    	cout << "Input the link table :"<<endl;
    	cin >> str;
    	struct node *phead = create( str );
    	
    	delete_repeat_element( phead );
    	
    	cout<< "The result is:" <<endl;
    	out_link( phead );
    
    }
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	test();
    	return 0;
    }