C++研究

C++细节深度探索及软件工程

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  37 随笔 :: 0 文章 :: 74 评论 :: 0 Trackbacks
#include "stdafx.h"
#include 
<iostream>
#include 
<map>
#include 
<sstream>
using namespace std;

#pragma warning (disable:
4305)

typedef map
<intfloat> FloatMap;
typedef FloatMap::iterator FloatMapIter;
typedef FloatMap::const_iterator FloatMapCIter;
int main()
{
    FloatMap _map1, _map2;
    _map1[
1= 0.01;
    _map1[
3= 0.03;
    _map1[
4= 0.04;
    _map1[
5= 0.05;
    _map1[
7= 0.07;
    _map1[
101= 0.101;
    _map1[
109= 0.109;

    _map2[
1= 0.01;
    _map2[
4= 0.04;
    _map2[
5= 0.05;
    _map2[
7= 0.07;
    _map2[
101= 0.101;
    _map2[
103= 0.103;
    _map2[
108= 0.108;

    FloatMapCIter it1 
= _map1.begin();
    FloatMapCIter it2 
= _map2.begin();

    FloatMapCIter it22 
= _map2.begin();
    FloatMapCIter it11 
= _map1.begin();
    ostringstream os1; 
//fenzi
    ostringstream os11; //fenmu1
    ostringstream os22; //fenmu2

    
//是否有公共部分
    int flag = 0;

    
while(it1 != _map1.end())
    
{
        
int id = (*it1).first;
        
float v1 = (*it1).second;

        
while( it22 != _map2.end() && (*it22).first < id) ++it22;

        
if( it22 == _map2.end())
        
{
            
break;
        }


        
if( (*it22).first == id )
        
{
            
//有公共部分
            flag = 1;
            os1 
<< (*it22).first <<  "  "//fenzi
            cout << (*it22).second << "*" << v1 << endl;
            it22
++;
        }

        
//it2 -- it22
        FloatMapCIter itemp = it2;
        
while( itemp != it22)
        
{
            os22 
<< (*itemp).first << "  " ; //fenmu
            ++itemp;
        }

        it2 
= it22;
        
        
int id2 = (*it2).first;
        
float v2 = (*it2).second;
        
while( it11 != _map1.end() && (*it11).first < id2)
        
{
            
++it11;
        }


        
if ( it11 == _map1.end())
        
{
            
break;
        }


        
if( (*it11).first == id2 )
        
{
            
//有公共部分
            flag = 1;
            os1 
<< (*it11).first << "  "//fenzi
            cout << (*it11).second << "*" <<  v2 << "  ";
            it11
++;
        }

        itemp 
= it1;
        
while( itemp != it11)
        
{
            os11 
<< (*itemp).first << "  " ; //fenmu
            ++itemp;
        }
    
        it1 
= it11;    

    }
//while

    
//是否有公共部分
    if (flag == 1)
    
{
        
while( it2 != _map2.end() )
        
{
            os22 
<< (*it2).first << "  " ; //fenmu
            ++it2;
        }


        
while( it1 != _map1.end() )
        
{
            os11 
<< (*it1).first << "  " ; //fenmu
            ++it1;
        }

    }

    
else
    
{
        
return 0;
    }

    
        
    


    cout 
<< "Common:" << os1.str() << endl;
    cout 
<< "fenmu:" << os11.str() << endl;
    cout 
<< "fenmu:" << os22.str() << endl;

    system(
"pause");

    
return 0;
}
posted on 2008-01-15 21:12 常兴龙 阅读(2126) 评论(1)  编辑 收藏 引用 所属分类: STLAlgorithmACM

评论

# re: 求有序序列公共部分(集合交集的O(n)复杂度求法) 2014-04-10 15:34 黄智
取交集可不是这么取的吧?一趟循环即可!  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


> hi的博客