C++博客-马赛克的冬天

字符串删除子串(C++)

马赛克007 — Wed, 06 Oct 2010 12:45:00 GMT

#include <iostream>
using namespace std;

int main()
{
    char str[50] = {0};
    char subStr[10] = {0};

    //输入主串以#结尾
    cout<<"input the string:";
    for(int i = 0;i<sizeof(str)/sizeof(str[0]);i++)
    {
        cin>>str[i];
        if(str[i] == '#')
        {
            str[i] = '\0';
            break;
        }
    }

    //输入子串以#结尾
    cout<<"input the substring:";
    for(int i = 0;i<sizeof(subStr)/sizeof(subStr[0]);i++)
    {
      cin>>subStr[i];
      if(subStr[i] == '#')
      {
          subStr[i] = '\0';
          break;
      }
    }

    //用于标记是否找到子串
    bool isSub = true;

    //找子串
    for(int i = 0;i<strlen(str);i++)
    {
        isSub = true;
        for(int j = 0;j<strlen(subStr);j++)
        {
            if(subStr[j] == str[i+j]) continue;
            else
            {
                isSub = false;
                break;
            }

        }

        if(isSub)
        {//如果找到子串，则将后续字符全部前移
         for(int m = i;m<strlen(str)+1-strlen(subStr);m++)
         {
             str[m] = str[m+strlen(subStr)];
         }
        }
    }

    //输出删除后的
    cout<<"the result string:"<<str<<endl;
    system("pause");
    return 1;
}

马赛克007 2010-10-06 20:45 发表评论

冒泡排序(C++)

马赛克007 — Tue, 28 Sep 2010 13:46:00 GMT

/*
Subject:      Bubble sort
Author:       shexinwei
Date:         2010-09-28
Laguage:      C++
IDE | Tool:   GCC(DEV 5.0)
Version:      1.0
Modify Time:  2010-09-28
*/    

#include 
#include 
#include 
using namespace std;
//排序函数 
int Bublle_sort(int data[],int n);
//打印数组函数 
int print(int data[],int n);
int main(int argc, char *argv[])
{
    int data[] = { 2,1,5,3,5,2,6,2};
    int length = sizeof(data)/sizeof(data[0]);
    cout<<"初始序列:"<<endl;
    print(data,length);
    Bublle_sort(data,length);
    cout<<"最终结果:"<<endl;
    print(data,length);
    cout<<endl;
    system("pause");
    return 1;
}
int Bublle_sort(int data[],int n)
{
int tmp = 0;
for(int i = 0;i < n;i++)
{
    for(int j = 0;j < n-i-1;j++)
    {
            if(data[j]<data[j+1])
            {
               tmp = data[j];
               data[j] = data[j+1];
               data[j+1] = tmp;
            }
            else continue;
    }
    cout<<i+1<<"次排序结果:"<<endl;
    print(data,n);
    cout<<endl;
}
    return 1;
}
int print(int data[],int n)
{
    for(int i = 0;i < n;i++)
    {
            cout<<data[i]<<" ";
    }
            cout<<endl;
}

调试结果：

马赛克007 2010-09-28 21:46 发表评论

迅雷笔试题(C++)

马赛克007 — Sat, 25 Sep 2010 14:49:00 GMT

1/////////////////////////////////////////////////
2//迅雷笔试题：
3//有N个大小不等的自然数（1--N），请将它们由小到大排序。
4//要求程序算法：时间复杂度为O(n)，空间复杂度为O(1)。
5
6#define TEST_XUNLEI
7
8#ifdef TEST_XUNLEI
9
10#include <iostream>
11using namespace std;
12int sort(int data[],int n);
13int main()
14{
15    int data[] = {8,7,9,4,6,5,3,2,1};
16    for(int i = 0 ;i < sizeof(data)/sizeof(int);i++)
17        cout<<data[i]<<" ";
18    cout<<endl;
19    sort(data,sizeof(data)/sizeof(int));
20    system("pause");
21    return 1;
22}
23int sort(int data[],int n)
24{
25    //保证空间复杂度为O(1)
26    int tmp = 0;
27    for(int i = 0;i < n;i++)
28    {
29       //移动，直到第data[i]为i+1的时,while结束循环。向后继续判断
30        while(data[i] != i+1)
31        {
32            //每次循环保证了data[i-1]的正确。总共有n个所以时间复杂度为O(N)
33            tmp = data[data[i]-1];
34            data[data[i]-1] = data[i];
35            data[i] = tmp;
36        }
37    }
38    for(int i = 0;i < n;i++)
39        cout<<data[i]<<" ";
40    cout<<endl;
41    return 1;
42}
43
44
45#endif

该题的重点在于，N个1--N的数。

马赛克007 2010-09-25 22:49 发表评论

n个小于一百万可重复数的排序

马赛克007 — Mon, 20 Sep 2010 09:33:00 GMT

#define RAND
#define RANK

#ifdef RAND
#include <iostream>
using namespace std;
#include <time.h>
enum{MAX=10000};
int main()
{
    ofstream out("rand.txt");
    //输出总数
    out<<MAX<<" ";

    srand((unsigned int)time(NULL));

    for(int i = 0;i < MAX;i++)
    {
        out<<rand()<<" ";
    }
    out.close();
    cout<<"out over"<<endl;
    return 1;
}
#endif

#ifdef RANK
#include <iostream>
using namespace std;
int main()
{
    int max = 0;
    ifstream in("rand.txt");

    //获取要排序数的个数
    in>>max;

    //初始化统计数组
    int *num = new int[RAND_MAX];
    for (int i = 0;i < max;i++)
    {
        num[i] = 0;
    }

    int tmp = -1;
    //读取数据，并统计
    for (i = 0;i < max;i++)
    {
        in>>tmp;
        num[tmp] += 1;
    }

    //输出
    ofstream out("out.txt");
    for (i = 0;i < max;i++)
    {
        if(num[i] != 0)
            for (int j = 0;j < num[i];j++)
            { //如果有多个，则输出多个
                out<<i<<" ";
            }
    }
    out.close();
    in.close();
    return;
}
#endif

马赛克007 2010-09-20 17:33 发表评论

判断整型数中每一位的值(C++)

马赛克007 — Mon, 13 Sep 2010 12:48:00 GMT

怎么获取整形中某一位的值是最常见的面试题。

1/*
2Subject:        the value of the each bit on int
3Author:         shexinwei
4School:         xidian university
5Date:           2010-09-13
6Laguage:        C++
7IDE:            visual studio 6.o
8Version:        1.0
9Modify Time:    2010-09-13
10*/
11#include <iostream>
12using namespace std;
13int main()
14{
15    int i = 0;
16    cout<<"please input the number:";
17    cin>>i;
18    char *result = new char[sizeof(int)*8];
19    int j = 1;
20    for (int k = 0;k<sizeof(int)*8;(j=j<<1),k++)
21    {
22        if ( (i&j) == 0 )
23        {
24            result[k] = '0';
25        }
26        else result[k] = '1';
27    }
28    for (int m = sizeof(int)*8-1;m >=0 ; m--)
29{
30        cout<<result[m];
31    }
32    cout<<endl;
33    delete []result;
34    return 1;
35}

马赛克007 2010-09-13 20:48 发表评论

快速排序(C++)

马赛克007 — Sun, 12 Sep 2010 09:02:00 GMT

  1 //版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
  2 //http://shexinwei.blogbus.com/logs/74827291.html
  3
  4
  5 /*
  6
  7 Subject:      Quick sort
  8
  9 Author:       shexinwei
10
11 School:       xidian university
12
13 Date:         2010-09-12
14
15 Laguage:      C++
16
17 IDE | Tool:   GCC
18
19 Version:      1.0
20
21 Modify Time:  2010-09-12
22
23 */
24
25 #include <iostream>
26
27 using namespace std;
28
29 int sort(int begin,int end,int data[],int n);
30
31 int recurs(int begin,int end,int data[],int n);
32
33 int print(int data[],int n);
34
35 int main()
36
37 {
38
39     int data[] = {20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};
40
41     //打印初始序列
42
43     print(data,20);
44
45     //递归排序
46
47     recurs(0,19,data,20);
48
49     //打印最终序列
50
51     print(data,20);
52
53     cout<<endl;
54
55         return 1;
56
57 }
58
59
60
61 //打印序列
62
63 int print(int data[],int n)
64
65 {
66
67     for(int i = 0;i<n;i++)
68
69         cout<<data[i]<<" ";
70
71     cout<<endl;
72
73     return 1;
74
75 }
76
77
78
79
80
81 int sort(int begin,int end,int data[],int n)
82
83 {
84
85     //选择最后一位做初始的中枢
86
87     int pos = end;
88
89     int key  = data[end];
90
91     //索引初始化
92
93     int front = begin;
94
95     int last = end;
96
97     for(;front != last;front++)
98
99     { //向后查找
100
101
102
103         if((data[front] < key) || (data[front] == key)) continue;
104
105         else
106
107         { //遇到比中枢值大的元素，交换位置，修改pos的值，并开始从后向前找
108
109             data[pos] = data[front];
110
111             pos = front;
112
113             //以下一句可注释，只需要保存中枢的位置，可以不修改值，因中枢值在key中保存，最后找到最终位置后再赋值即可
114
115             data[pos] = key;
116
117             //输出改变一次后的序列
118
119             print(data,n);
120
121             for(;front != last;last--)
122
123             {//从后向前查找
124
125                 if((data[last] > key)||(data[last] == key)) continue;
126
127                 else
128
129                 { //遇到比中枢值小的元素，交换位置，修改pos值，并重新开始从前向后查找
130
131                    data[pos] = data[last];
132
133                    pos = last;
134
135                  //以下一句可注释，只需要保存中枢的位置，可以不修改值，因中枢值在key中保存，最后找到最终位置后再赋值即可
136
137                        data[pos] = key;
138
139                  //打印修改以后的序列
140
141                    print(data,n);
142
143                  //重新开始从前向后查找
144
145                    break;
146
147                 }
148
149             }
150
151
152
153         }
154
155         //如果从后向前已经使得front==last，那么一趟分割完毕
156
157         if(front == last) break;
158
159     }
160
161     data[pos] = key;
162
163     return pos;
164
165 }
166
167 int recurs(int begin,int end,int data[],int n)
168
169 {
170
171     //递归出口
172
173     if((begin == end) || (begin > end)) return 1;
174
175     else
176
177     {
178
179     //做分割
180
181     int index = sort(begin,end,data,n);
182
183     //前一部分递归
184
185     recurs(begin,index-1,data,n);
186
187     //后一部分递归
188
189     recurs(index+1,end,data,n);
190
191     }
192
193 }

马赛克007 2010-09-12 17:02 发表评论

the difference of some Input function

马赛克007 — Fri, 10 Sep 2010 00:44:00 GMT

1 /* 2 Subject: the difference of gets(),getch(),getchar() and getline() 3 Author: shexinwei 4 School: xidian university 5 Date: 2010-09-09 6 Laguage: C++ 7 IDE: visual studio 6.o 8 Version: 1.0 9 Modify Time: 2010-09-09 10 */ 11 #include <iostream> 12 using namespace std; 13 #include <conio.h> 14 #define MAX_LEN 20 15 int main() 16 { 17 18 //gets() : Get a line from the stdin stream. 19 //Get a line from the stdin stream. 20 21 cout<<"the function gets():"<<endl; 22 char buffer[MAX_LEN]; 23 gets(buffer); 24 cout<<buffer<<endl; 25 26 // getchar(): 27 // marco: #define getchar() getc(stdin) File: STDIO.H Get a character from a file; 28 // function: _CRTIMP int __cdecl getchar(void); File: STDIO.H Get a character from stdin; 29 char tmp = 0; 30 cout<<endl<<endl<<"the function getchar():"<<endl; 31 cout<< (char)getchar(tmp) <<endl; 32 33 //getline(): 34 //basic_istream& getline(char_type *_Str, streamsize _Count); 35 //Gets a line from the input stream. 36 cout<<endl<<endl<<"the function getline():"<<endl; 37 cin.getline(buffer,MAX_LEN); 38 cout<<buffer<<endl; 39 40 //getch(): 41 //This POSIX function is deprecated beginning in Visual C++ 2005. Use the ISO C++ conformant _getch instead 42 //Gets a character from the console without echo. 43 //int _getch( void ); 44 //Returns the character read. There is no error return. 45 //Headers: 46 cout<<endl<<endl<<"the function getch():"<<endl; 47 tmp = getch(); //without echo 48 // cout<//print the character 49 50 51 system("pause"); 52 return 0; 53 54 }

马赛克007 2010-09-10 08:44 发表评论

版权声明文档

马赛克007 — Fri, 10 Sep 2010 00:41:00 GMT

示例

 1 /*
 2 Subject:        the difference of gets(),getch(),getchar() and getline()
 3 Author:         shexinwei
 4 School:         xidian university
 5 Date:            2010-09-09
 6 Laguage:       C++
 7 IDE:              visual studio 6.o
 8 Version:        1.0
 9 Modify Time:  2010-09-09
10 */

马赛克007 2010-09-10 08:41 发表评论