马赛克007欢迎你

htt://shexinwei.blogbus.com

http://www.cppblog.com/shexinwei

感谢大家的支持

置顶随笔

[置顶]快速排序(C++)

  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 }

posted @ 2010-09-12 17:02 马赛克007 阅读(4495) | 评论 (1)编辑 收藏

2010年10月6日

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

#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;
}

posted @ 2010-10-06 20:45 马赛克007 阅读(1027) | 评论 (0)编辑 收藏

2010年9月28日

冒泡排序(C++)

/*
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 <cstdlib>
#include <iostream>
#include <fstream>
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;
}

调试结果:


posted @ 2010-09-28 21:46 马赛克007 阅读(1695) | 评论 (0)编辑 收藏

2010年9月25日

迅雷笔试题(C++)

 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的数。

posted @ 2010-09-25 22:49 马赛克007 阅读(5128) | 评论 (16)编辑 收藏

2010年9月20日

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

#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

posted @ 2010-09-20 17:33 马赛克007 阅读(1635) | 评论 (2)编辑 收藏

2010年9月13日

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

怎么获取整形中某一位的值是最常见的面试题。
 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}

posted @ 2010-09-13 20:48 马赛克007 阅读(2568) | 评论 (4)编辑 收藏

2010年9月12日

快速排序(C++)

  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 }

posted @ 2010-09-12 17:02 马赛克007 阅读(4495) | 评论 (1)编辑 收藏

2010年9月10日

the difference of some Input function

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<Elem, Tr>& 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: <conio.h> 46 cout<<endl<<endl<<"the function getch():"<<endl; 47 tmp = getch(); //without echo 48 // cout<<tmp<<endl; //print the character 49 50 51 system("pause"); 52 return 0; 53 54 }

posted @ 2010-09-10 08:44 马赛克007 阅读(1383) | 评论 (0)编辑 收藏

版权声明文档

作为一个专业的程序员,我们需要在每一个源文件中做一些版权声明性的注释。现在根据我所见到的,和自己的理解,定义一份属于我自己的版权声明文档格式。不足之处日后继续添加补充。

示例

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 */


posted @ 2010-09-10 08:41 马赛克007 阅读(369) | 评论 (0)编辑 收藏

仅列出标题  
<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

公告

QQ:306334649 本博客所发代码皆为作者原创,大家可以随便使用。

常用链接

留言簿(1)

随笔档案

文章分类

我的博客

搜索

最新评论

阅读排行榜

评论排行榜