天之道

享受编程的乐趣。
posts - 118, comments - 7, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

最全的C++ map的使用

 Map是c++的一个标准容器，她提供了很好一对一的关系，在一些程序中建立一个map可以起到事半功倍的效果，总结了一些map基本简单实用的操作！
1. map最基本的构造函数；
   map<string , int >mapstring;         map<int ,string >mapint;
   map<sring, char>mapstring;         map< char ,string>mapchar;
   map<char ,int>mapchar;            map<int ,char >mapint；

2. map添加数据；

   map<int ,string> maplive;  
   1.maplive.insert(pair<int,string>(102,"aclive"));
   2.maplive.insert(map<int,string>::value_type(321,"hai"));
   3, maplive[112]="April";//map中最简单最常用的插入添加！
3，map中元素的查找：

   find()函数返回一个迭代器指向键值为key的元素，如果没找到就返回指向map尾部的迭代器。        

   map<int ,string >::iterator l_it;; 
   l_it=maplive.find(112);
   if(l_it==maplive.end())
                cout<<"we do not find 112"<<endl;
   else cout<<"wo find 112"<<endl;
4,map中元素的删除：
   如果删除112；
   map<int ,string >::iterator l_it;;
   l_it=maplive.find(112);
   if(l_it==maplive.end())
        cout<<"we do not find 112"<<endl;
   else  maplive.erase(l_it);  //delete 112;
5,map中 swap的用法：
  Map中的swap不是一个容器中的元素交换，而是两个容器交换；
  For example：
  #include <map>
  #include <iostream>

  using namespace std;

  int main( )
  {
      map <int, int> m1, m2, m3;
      map <int, int>::iterator m1_Iter;

      m1.insert ( pair <int, int>  ( 1, 10 ) );
      m1.insert ( pair <int, int>  ( 2, 20 ) );
      m1.insert ( pair <int, int>  ( 3, 30 ) );
      m2.insert ( pair <int, int>  ( 10, 100 ) );
      m2.insert ( pair <int, int>  ( 20, 200 ) );
      m3.insert ( pair <int, int>  ( 30, 300 ) );

   cout << "The original map m1 is:";
   for ( m1_Iter = m1.begin( ); m1_Iter != m1.end( ); m1_Iter++ )
      cout << " " << m1_Iter->second;
      cout   << "." << endl;

   // This is the member function version of swap
   //m2 is said to be the argument map; m1 the target map
   m1.swap( m2 );

   cout << "After swapping with m2, map m1 is:";
   for ( m1_Iter = m1.begin( ); m1_Iter != m1.end( ); m1_Iter++ )
      cout << " " << m1_Iter -> second;
      cout  << "." << endl;
   cout << "After swapping with m2, map m2 is:";
   for ( m1_Iter = m2.begin( ); m1_Iter != m2.end( ); m1_Iter++ )
      cout << " " << m1_Iter -> second;
      cout  << "." << endl;
   // This is the specialized template version of swap
   swap( m1, m3 );

   cout << "After swapping with m3, map m1 is:";
   for ( m1_Iter = m1.begin( ); m1_Iter != m1.end( ); m1_Iter++ )
      cout << " " << m1_Iter -> second;
      cout   << "." << endl;
}

6.map的sort问题：
  Map中的元素是自动按key升序排序,所以不能对map用sort函数：
  For example：
  #include <map>
  #include <iostream>

  using namespace std;

 int main( )
 {
   map <int, int> m1;
   map <int, int>::iterator m1_Iter;

   m1.insert ( pair <int, int>  ( 1, 20 ) );
   m1.insert ( pair <int, int>  ( 4, 40 ) );
   m1.insert ( pair <int, int>  ( 3, 60 ) );
   m1.insert ( pair <int, int>  ( 2, 50 ) );
   m1.insert ( pair <int, int>  ( 6, 40 ) );
   m1.insert ( pair <int, int>  ( 7, 30 ) );

   cout << "The original map m1 is:"<<endl;
   for ( m1_Iter = m1.begin( ); m1_Iter != m1.end( ); m1_Iter++ )
      cout <<  m1_Iter->first<<" "<<m1_Iter->second<<endl;
  
}
  The original map m1 is:
  1 20
  2 50
  3 60
  4 40
  6 40
  7 30
  请按任意键继续. . .

#include <iostream>
#include <string>
#include <map>
using namespace std;
int main()
{
    char str[50];
    int count=0;
    map <string,int> counter;
map <string,int> ::iterator it;
    while(gets(str)!=NULL)
    {
        counter[str]++;
        count++;
    }
    for(it=counter.begin();it!=counter.end();it++)
    {
cout<<it->first<<" "<<it->second<<endl;
    }
    return 0;
}
7，   map的基本操作函数：
      C++ Maps是一种关联式容器，包含“关键字/值”对
      begin()          返回指向map头部的迭代器
      clear(）         删除所有元素
      count()          返回指定元素出现的次数
      empty()          如果map为空则返回true
      end()            返回指向map末尾的迭代器
      equal_range()    返回特殊条目的迭代器对
      erase()          删除一个元素
      find()           查找一个元素
      get_allocator()  返回map的配置器
      insert()         插入元素
      key_comp()       返回比较元素key的函数
      lower_bound()    返回键值>=给定元素的第一个位置
      max_size()       返回可以容纳的最大元素个数
      rbegin()         返回一个指向map尾部的逆向迭代器
      rend()           返回一个指向map头部的逆向迭代器
      size()           返回map中元素的个数
      swap()            交换两个map
      upper_bound()     返回键值>给定元素的第一个位置
      value_comp()      返回比较元素value的函数

                                                    

posted @ 2012-09-25 19:56 hoshelly 阅读(318) | 评论 (0) | 编辑 收藏

找出中间数（C++快排函数使用）

Totalsubmit: 790   Accepted: 47  
Description

一天，农夫乔伊像往常一样来到了他的牧场，他突然对他的奶牛产奶量产生了兴趣。
他想知道产奶量处于中间的那头奶牛的产奶量是多少，处于中间的意思是说，其中有一半牛的产奶量比它多，另一半牛的产奶量比它少。
    这个问题现在交由你来写程序完成！

Input

仅包括一组测试数据，第一行一个正整数N（1<=N<=10,000），接下来N行，每行一个正整数不会超过10^6，第i+1行的数字代表第i头牛的产奶量。
Output

产奶量处于中间的牛的产奶量。
Sample Input

5
1
2
4
5
3
Sample Output

3

#include<iostream>
#include<algorithm>
using namespace std;
int compare(const void * a,const void * b)
{
    return *(int*)a - *(int*)b;
}
int main()
{
    int n,cow[10005];
    while(cin>>n)
    {
        for(int i=1;i<=n;i++)
        {
            cin>>cow[i];
        }
        qsort(cow+1,n,sizeof(int),compare);
        cout<<cow[(n+1)/2]<<endl;
    }
    return 0;
}

posted @ 2012-09-23 17:18 hoshelly 阅读(1077) | 评论 (0) | 编辑 收藏

计数问题

给你两个数a和b,你的任务是计算出1在a和b之间出现的次数,比如说，如果a=1024,b=1032，那么a和b之间的数就是：

1024 1025 1026 1027 1028 1029 1030 1031 1032

则有10个1出现在这些数中。

Input

输入不会超过500行。每一行有两个数a和b，a和b的范围是0 < a, b < 100000000。输入两个0时程序结束，两个0不作为输入样例。

Output

对于每一对输入的a和b，输出一个数，代表1出现的个数。

Sample Input


1 10
44 497
346 542
1199 1748
1496 1403
1004 503
1714 190
1317 854
1976 494
1001 1960
0 0

Sample Output

2
185
40
666
113
105
1133
512
1375
1256


#include<stdio.h>
#include<string.h>
int Find_OneNum(long a)
{
    long i,b,count=0;
    while(a)
    {
        b=a%10;
        if(b == 1)
        {
            count++;
        }
        a=a/10;
    }
    return count;
}
int main()
{
    long a,b,i,sum;
    while((scanf("%ld%ld",&a,&b) == 2),a)
    {
        if(a>b)
        {
            int temp;
            temp=a;
            a=b;
            b=temp;
        }
        sum=0;
    for(i=a;i<=b;i++)
    {
        sum += Find_OneNum(i);
    }
    printf("%ld\n",sum);
    }
    return 0;
}

posted @ 2012-09-23 16:35 hoshelly 阅读(228) | 评论 (0) | 编辑 收藏

一元多项式相加实现

2.3x4+3.2x3+2x2+1.2x与5.6x5-2.3x4+3.4x3
相加结果为：5.6x5+6.6x3 +2x2+1.2x
首先考虑存储结构，多项式中的每一项包括“系数”和“指数”两项，且相加运算可能会改变系数和指数，故应采用链式存储结构。在一个单链表结点中，存储多项式一项的系数和指数。其次，考虑多项式的运算规则：对于两个一元多项式中所有指数相同的项，对应系数相加，若和不为0，则构成“和多项式”中的一项；对于两个一元多项式中所有指数不同的项，则分别复抄到“和多项式”中去。


#include  <iostream>
using  namespace  std;
    
    typedef struct{
    float  coef;   //系数
    int expn;        //指数
}DataType;

struct Node;
typedef struct Node *PNode;
struct Node{
    DataType info;
    PNode link;
};
typedef  struct  Node *LinkList;

typedef  LinkList  polynomial;    //带头结点的单链表表示多项式

int cmp(DataType a,DataType b){
    int flag;
    if(a.expn<b.expn) flag=-1;
    else if(a.expn==b.expn)    flag=0;
    else flag=1;
    return flag;
}

//建立多项式单链表
void CreatPolyn(polynomial &P,int m){    //m为多项式项数
    polynomial r,s;
    P=new struct Node;
    r=P;
    for(int i=0;i<m;i++){
        s=new struct Node;
        cout<<"输入系数和指数：";
        cin>>s->info.coef>>s->info.expn;
        r->link=s;
        r=s;
}
r->link=NULL;
}

//多项式相加得到新的多项式
polynomial AddPolyn(polynomial &pa,polynomial &pb){
    polynomial newp,p,q,s,r;
    float sum;
    p=pa->link;
    q=pb->link;
    newp=new struct Node;
    r=newp;
    while(p&&q){
        switch(cmp(p->info,q->info)){    //比较两个多项式的指数
        case -1:        //多项式pa当前结点的指数值小
            s=new struct Node;
            s->info.coef=q->info.coef;
            s->info.expn=q->info.expn;
            r->link=s;
            r=s;
            q=q->link;
            break;
        case 0:        //两个多项式指数值相等
            sum=p->info.coef+q->info.coef;
            if (sum!=0.0){
                s=new struct Node;
                s->info.coef=sum;
                s->info.expn=p->info.expn;
                r->link=s;
                r=s;
            }
            p=p->link;
            q=q->link;
            break;
        case 1:        //多项式pb当前结点的指数值小
            s=new struct Node;
            s->info.coef=p->info.coef;
            s->info.expn=p->info.expn;
            r->link=s;
            r=s;
            p=p->link;
            break;
        }//switch
    }//while

//链接pa剩余结点
while(p){
    s=new struct Node;
    s->info.coef=p->info.coef;
    s->info.expn=p->info.expn;
    r->link=s;
    r=s;
    p=p->link;
}
//链接pb剩余结点
while(q){
    s=new struct Node;
    s->info.coef=q->info.coef;
    s->info.expn=q->info.expn;
    r->link=s;
    r=s;
    q=q->link;
}
r->link=NULL;
return newp;
}    
//输出多项式单链表
void PrintPolyn(polynomial p){
    polynomial s;
    s=p->link;
    while(s){
    //输出系数和指数
    cout<<s->info.coef<<"("<<s->info.expn<<")";
    s=s->link;
}
cout<<endl;
}
    void main(){
    int m,n;
    polynomial p,q;
    cout<<"请输入多项式pa的项数：";
    cin>>m;
    CreatPolyn(p,m);
    cout<<"请输入多项式pb的项数：";
    cin>>n;
    CreatPolyn(q,n);
    PrintPolyn(p);
    PrintPolyn(q);
    PrintPolyn(AddPolyn(p,q));
}





posted @ 2012-09-23 15:48 hoshelly 阅读(1128) | 评论 (1) | 编辑 收藏

找出回文素数


The number 151 is a prime palindrome because it is both a prime number and a palindrome (it is the same number when read forward as backward). Write a program that finds all prime palindromes in the range of two supplied numbers a and b (5 <= a < b <= 1000,000,000); both a and b are considered to be within the range .
Input
Line 1: Two integers, a and b
Output
The list of palindromic primes in numerical order, one per line.
Sample Input
5 500
Sample Output
5
7
11
101
131
151
181
191
313
353
373
383


#include<stdio.h>
#include<math.h>
#include<stdlib.h>
int i;
int Is_Prime(int a)
{
    double t = a;
    for(i=2;i<=sqrt(t);i++)
    {
        if(a % i == 0)
            return 0;
    }
        return 1;
}
int diglen(int c)
{
    if(c/10 == 0)
        return 1;
    int count=0;
    while(c)
    {
        c=c/10;
        count++;
    }
    return count;
}

void IntoStr(int a,char* str) //将数字转换为字符串
{
    int h= diglen(a)-1,i=0;
    while(h+1)
    {
    int k,c,d=1;
    for(k=0;k<h;k++)
    {
        d=d*10;
    }

    c=a/d;//取本次数字的最高位
    str[i++] = c+48;
    a = a%d; //取余数
    h--;
    }
    str[i]='\0'; //最后末尾加字符串结束符
}

int Is_Pal(int b)
{
    int len = diglen(b);
    int ok = 1,j;
    char* str = (char*)malloc(sizeof(char)*(len+1));
    IntoStr(b,str); //将数字转换为字符数组，也可以用itoa函数或 sprintf函数
    for(i=0,j=len-1;i < len/2;i++,j--)
    {
        if(str[i] != str[j])
            ok = 0;
        
    }
    free(str);
    if(ok == 1)
        return 1;
    else
        return 0;
}

int main()
{
    int a,b,j;
    scanf("%d%d",&a,&b);
    for(j=a;j<=b;j++)
    {
        if(Is_Prime(j) && Is_Pal(j))
            printf("%d\n",j);
    }
    return 0;
}

posted @ 2012-09-22 17:45 hoshelly 阅读(287) | 评论 (0) | 编辑 收藏

C++STL标准库中队列的运用

卡片游戏

桌上有一叠牌，从第一张牌开始从上往下依次编号1~n。当至少还剩两张牌时进行如下操作：把第一张牌扔掉，然后把新的第一张牌放到整叠牌的最后。输入n，输出每次扔掉的牌，以及最后剩下的牌。

样例输入：7
样例输出：1 3 5 7 4 2 6

代码如下：

#include<iostream>
#include<queue>
using namespace std;
queue<int> q; //声明队列
int main()    
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++) q.push(i+1);
    while(!q.empty())
    {
        cout<<q.front()<<" ";
        q.pop();
        if(!q.empty()) //此处需要判断此时队列是否为空
        {
           q.push(q.front());
           q.pop();
        }
    }
    cout<<endl;
    return 0;
}

posted @ 2012-09-18 23:12 hoshelly 阅读(14394) | 评论 (0) | 编辑 收藏

堆栈的链表实现

#include<stdio.h>
#include<stdlib.h>
typedef struct STACKnode* link; //堆栈的链表实现
struct STACKnode
{
    int item;
    link next;
};
static link head;
link NEW(int item,link next)
{
    link x=(link)malloc(sizeof(STACKnode));
    x->item = item; //将新建立的结点添加到链表头
    x->next = next; //此时head指向新建立的结点，此结点的next结点，即为原先是头结点的结点(旧头结点)
    return x;  //函数返回新建立的头结点，此结点总是位于栈顶
}

void STACKinit()
{
    head = NULL;
}
int STACKempty()  //置空栈
{
    return head == NULL;
}
void STACKpush(int item)
{
    head = NEW(item,head);
}
int STACKpop()
{
    int item = head->item; //将头结点上的值取出
    link t = head->next;
    free(head); //释放此头结点内存
    head = t; //head指向新的头结点t
    return item; //返回旧的头结点的值
}

int main()
{
    int i;
    STACKinit();
    for(i=1;i<=10;i++)
        STACKpush(i);
    for(i=1;i<=10;i++)
        printf("%d ",STACKpop());
    printf("\n");
    return 0;
}

posted @ 2012-09-17 15:41 hoshelly 阅读(292) | 评论 (0) | 编辑 收藏

中缀--后缀转换

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define M 1000
static int N; //N栈的大小
static int *s;
void STACKinit(int maxN) //建立一个动态数组s，相当于建立并初始化栈
{
    s = (int *)malloc(maxN*sizeof(int));
    N=0;
}
int STACKempty()
{
    return N==0;
}
void STACKpush(int item)
{
    s[N++] = item;
}
int STACKpop()
{
    return s[--N];
}

int main()  //程序作用：将中缀表达式转为后缀表达式
{
    char a[M];
    gets(a); //输入中缀表达式
    STACKinit(N);
    int i,len=strlen(a);
    for(i=0;i<len;i++)
    {
        if(a[i] == ')')
            printf("%c ",STACKpop()); //遇到右括号弹出栈顶的运算符
        if((a[i] == '+') || (a[i] == '*'))
            STACKpush(a[i]);             //将运算符压入栈
        if((a[i] == '-') || (a[i] =='/'))
            STACKpush(a[i]);
        if((a[i] >= '0') && (a[i] <= '9')) //遇到数字则输出
            printf("%c ",a[i]);
    }
    return 0;
}

示例：

posted @ 2012-09-17 13:06 hoshelly 阅读(240) | 评论 (0) | 编辑 收藏

后缀表达式求值

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define M 1000
static int N; //N栈的大小
static int *s;
void STACKinit(int maxN) //建立一个动态数组s，相当于建立并初始化栈
{
    s = (int *)malloc(maxN*sizeof(int));
    N=0;
}
int STACKempty()
{
    return N==0;
}
void STACKpush(int item)
{
    s[N++] = item;
}
int STACKpop()
{
    return s[--N];
}

int main()
{
    char a[M];
    gets(a); //输入后缀表达式，每个整数之后至少要有一个空格
    int i,len,ok;
    char k[15]={' ','0','1','2','3','4','5','6','7','8','9','+','-','/','*'};
    len=strlen(a);
    while(1)  //检查输入字符串的合法性（仅限于检查输入是否为包含数字和+ - * / 和 ' '的字符串）
    {
       ok=0;
       for(i=0;i<len;i++) 
      {
         for(int j=0;j<15;j++)
         {
            if(a[i] == k[j])
            {
                ok=1;
            }
         }
         if(!ok)
         {
             printf("Input error! please input again:\n");
             break;
         }
       }
       if(!ok)
       {
          gets(a);
          len=strlen(a);
       }
       else
           break;
    }

    STACKinit(len); //初始化N=0
    for(i=0;i<len;i++)
    {
        if(a[i] == '+')
            STACKpush(STACKpop()+STACKpop());
        if(a[i] == '*')
            STACKpush(STACKpop()*STACKpop());
        if(a[i] == '-')
        {
            b = STACKpop();
            c = STACKpop();
            STACKpush(c-b);
        }

        if(a[i] == '/')
        {
            b = STACKpop();
            c = STACKpop();
            STACKpush(c/b);
        }

            
        if((a[i] >= '0') && (a[i] <= '9')) //如果遇到数字，则先压入0进栈
            STACKpush(0);
        while((a[i] >='0') && (a[i] <='9'))
            STACKpush(10*STACKpop()+(a[i++]-'0'));//再将“字符数字”转换为数字
    }

    printf("%d \n",STACKpop());
    return 0;
}

示例：

posted @ 2012-09-17 12:03 hoshelly 阅读(1383) | 评论 (0) | 编辑 收藏

二分搜索算法

二分搜索算法的使用前提条件是表中的数已经是有序的，如果还没排好序，则不能用二分搜索算法。


int search(int a[],int v,int l,int r) //在数组a[]内查找v，l为左下标，r为右下标
{
    while (r>=l)
    {
        int m=(l+r)/2; //每次取数组的一半,此处要加1
        if(v == a[m]) //如果查找到v，则返回下标m
            return m;
        if(v < a[m])  //如果v小于此时的数，则右下标变成r=m-1，去掉数组中一半的数，反之亦然
            r=m-1;
        else 
            l=m+1;
    }
    return -1;
}

posted @ 2012-09-16 00:05 hoshelly 阅读(614) | 评论 (0) | 编辑 收藏

仅列出标题
共12页: 1 2 3 4 5 6 7 8 9 Last