依睛(IT blog) 我回来了,PHP<-->C/C++ LINUX

笨鸟

统计

积分与排名

友情连接

最新评论

]c++重点知识

论坛: http://www.ieee.org.cn/list.asp?boardid=61&page=2&action=

看看了这总结的真不错, 在反复看看, 书要反复读, 再反复看, 看自己还有哪些遗漏处.
]c++重点知识   [阅读: 1208]

C++知识点
一、#i nclude “filename.h”和#i nclude filename.h>的区别
#i nclude “filename.h”是指编译器将从当前工作目录上开始查找此文件
#i nclude filename.h>是指编译器将从标准库目录中开始查找此文件

二、头文件的作用
加强安全检测
通过头文件可能方便地调用库功能,而不必关心其实现方式

三、* , &修饰符的位置
对于*和&修饰符,为了避免误解,最好将修饰符紧靠变量名

四、if语句
不要将布尔变量与任何值进行比较,那会很容易出错的。
整形变量必须要有类型相同的值进行比较
浮点变量最好少比点,就算要比也要有值进行限制
指针变量要和NULL进行比较,不要和布尔型和整形比较

五、const和#define的比较
const有数据类型,
#define没有数据类型
个别编译器中const可以进行调试,#define不可以进行调试
在类中定义常量有两种方式
1、 在类在声明常量,但不赋值,在构造函数初始化表中进行赋值;
2、 用枚举代替const常量。

六、C++函数中值的传递方式
有三种方式:值传递(Pass by value)、指针传递(Pass by pointer)、引用传递(Pass by reference)
void fun(char c) //pass by value
void fun(char *str) //pass by pointer
void fun(char &str) //pass by reference
如果输入参数是以值传递的话,最好使用引用传递代替,因为引用传递省去了临时对象的构造和析构
函数的类型不能省略,就算没有也要加个void

七、函数体中的指针或引用常量不能被返回
Char *func(void)
{
char str[]=”Hello Word”;
//这个是不能被返回的,因为str是个指向栈内存的指针,不是一般的值,函数结束后会被注销掉
return str;
}

函数体内的指针变量并不会随着函数的消亡而自动释放

例子:
char * fun(void)
{
    char    * st="hello ssssssssssssss             ";

    return st; //函数体内的指针变量并不会随着函数的消亡而自动释放
}
void main()

     char    *p3;
    p3 = fun()
    printf(p3);

}


八、一个内存拷贝函数的实现体
void *memcpy(void *pvTo,const void *pvFrom,size_t size)
{
assert((pvTo!=NULL)&&(pvFrom!=NULL));
byte *pbTo=(byte*)pvTo; //防止地址被改变
byte *pbFrom=(byte*)pvFrom;
while (size-- >0)
pbTo++ = pbForm++;
return pvTo;
}

九、内存的分配方式
分配方式有三种,请记住,说不定那天去面试的时候就会有人问你这问题
1、 静态存储区,是在程序编译时就已经分配好的,在整个运行期间都存在,如全局变量、常量。
2、 栈上分配,函数内的局部变量就是从这分配的,但分配的内存容易有限。
3、 堆上分配,也称动态分配,如我们用new,malloc分配内存,用delete,free来释放的内存。

十、内存分配的注意事项
用new或malloc分配内存时,必须要对此指针赋初值。
用delete 或free释放内存后,必须要将指针指向NULL
不能修改指向常量的指针数据

十一、内容复制与比较
//数组……
char a[]=”Hello Word!”;
char b[10];
strcpy(b,a);
if (strcmp(a,b)==0)
{}
//指针……
char a[]=”Hello Word!”;
char *p;
p=new char[strlen(a)+1];
strcpy(p,a);
if (strcmp(p,a)==0)
{}

十二、sizeof的问题
记住一点,C++无法知道指针所指对象的大小,指针的大小永远为4字节
char a[]=”Hello World!”
char *p=a;
count sizeof(a) end; //12字节
count sizeof(p) endl; //4字节
而且,在函数中,数组参数退化为指针,所以下面的内容永远输出为4
void fun(char a[1000])
{
count sizeof(a) endl; //输出4而不是1000
}

十三、关于指针
1、 指针创建时必须被初始化
2、 指针在free 或delete后必须置为NULL
3、 指针的长度都为4字节
4、释放内存时,如果是数组指针,必须要释放掉所有的内存,如
char *p=new char[100];
strcpy(p,”Hello World”);
delete []p; //注意前面的[]号
p=NULL;//置为NULL
5、数组指针的内容不能超过数组指针的最大容易。
如:
char *p=new char[5];
strcpy(p,”Hello World”); //报错 目标容易不够大
delete []p; //注意前面的[]号
p=NULL;

十四、关于malloc/free 和new /delete
l malloc/free 是C/C+的内存分配符,new /delete是C++的内存分配符。
l 注意:malloc/free是库函数,new/delete是运算符
l malloc/free不能执行构造函数与析构函数,而new/delete可以
l new/delete不能在C上运行,所以malloc/free不能被淘汰
l 两者都必须要成对使用
l C++中可以使用_set_new_hander函数来定义内存分配异常的处理

十五、C++的特性
C++新增加有重载(overload),内联(inline),Const,Virtual四种机制
重载和内联:即可用于全局函数,也可用于类的成员函数;
Const和Virtual:只可用于类的成员函数;
重载:在同一类中,函数名相同的函数。由不同的参数决定调用那个函数。函数可要不可要Virtual关键字。和全局函数同名的函数
不叫重载。如果在类中调用同名的全局函数,必须用全局引用符号::引用。
覆盖是指派生类函数覆盖基类函数
函数名相同;
参数相同;
基类函数必须有Virtual关键字;
不同的范围(派生类和基类)。
隐藏是指派生类屏蔽了基类的同名函数相同
1、 函数名相同,但参数不同,此时不论基类有无Virtual关键字,基类函数将被隐藏。
2、 函数名相同,参数也相同,但基类无Virtual关键字(有就是覆盖),基类函数将被隐藏。
内联:inline关键字必须与定义体放在一起,而不是单单放在声明中。
Const:const是constant的缩写,“恒定不变”的意思。被const修饰的东西都受到强制保护,可以预防意外的变动,能提高程序的
健壮性。
1、 参数做输入用的指针型参数,加上const可防止被意外改动。
2、 按值引用的用户类型做输入参数时,最好将按值传递的改为引用传递,并加上const关键字,目的是为了提高效率。数据类型为
内部类型的就没必要做这件事情;如:
将void Func(A a) 改为void Func(const A &a)。
而void func(int a)就没必要改成void func(const int &a);
3、 给返回值为指针类型的函数加上const,会使函数返回值不能被修改,赋给的变量也只能是const型变量。如:函
数const char*GetString(void); char *str=GetString()将会出错。而const char *str=GetString()将是正确的。
4、 Const成员函数是指此函数体内只能调用Const成员变量,提高程序的键壮性。如声明函数 int GetCount(void) const;此函数
体内就只
能调用Const成员变量。
Virtual:虚函数:派生类可以覆盖掉的函数,纯虚函数:只是个空函数,没有函数实现体;

十六、extern“C”有什么作用?
Extern “C”是由C++提供的一个连接交换指定符号,用于告诉C++这段代码是C函数。这是因为C++编译后库中函数名会变
得很长,与C生成的不一致,造成C++不能直接调用C函数,加上extren “c”后,C++就能直接调用C函数了。
Extern “C”主要使用正规DLL函数的引用和导出 和 在C++包含C函数或C头文件时使用。使用时在前面加上extern “c” 关键字即
可。

十七、构造函数与析构函数
派生类的构造函数应在初始化表里调用基类的构造函数;
派生类和基类的析构函数应加Virtual关键字。
不要小看构造函数和析构函数,其实编起来还是不容易。
#i nclude
using namespace std;
class Base
{
public:
virtual ~Base() { cout "~Base" endl ; }
};
class Derived : public Base
{
public:
virtual ~Derived() { cout "~Derived" endl ; }
};
void main(void)
{
Base * pB = new Derived; // upcast
delete pB;
cin.get();
}
输出结果为:
~Derived
~Base
如果析构函数不为虚,那么输出结果为
~Base

十八、#IFNDEF/#DEFINE/#ENDIF有什么作用
仿止该头文件被重复引用
一、#i nclude “filename.h”和#i nclude filename.h>的区别
#i nclude “filename.h”是指编译器将从当前工作目录上开始查找此文件
#i nclude filename.h>是指编译器将从标准库目录中开始查找此文件

二、头文件的作用
加强安全检测
通过头文件可能方便地调用库功能,而不必关心其实现方式

三、* , &修饰符的位置
对于*和&修饰符,为了避免误解,最好将修饰符紧靠变量名

四、if语句
不要将布尔变量与任何值进行比较,那会很容易出错的。
整形变量必须要有类型相同的值进行比较
浮点变量最好少比点,就算要比也要有值进行限制
指针变量要和NULL进行比较,不要和布尔型和整形比较

五、const和#define的比较
const有数据类型,#define没有数据类型
个别编译器中const可以进行调试,#define不可以进行调试
在类中定义常量有两种方式
1、 在类在声明常量,但不赋值,在构造函数初始化表中进行赋值;
2、 用枚举代替const常量。

六、C++函数中值的传递方式
有三种方式:值传递(Pass by value)、指针传递(Pass by pointer)、引用传递(Pass by reference)
void fun(char c) //pass by value
void fun(char *str) //pass by pointer
void fun(char &str) //pass by reference
如果输入参数是以值传递的话,最好使用引用传递代替,因为引用传递省去了临时对象的构造和析构
函数的类型不能省略,就算没有也要加个void

七、函数体中的指针或引用常量不能被返回
Char *func(void)
{
char str[]=”Hello Word”;
//这个是不能被返回的,因为str是个指定变量,不是一般的值,函数结束后会被注销掉
return str;
}
函数体内的指针变量并不会随着函数的消亡而自动释放

八、一个内存拷贝函数的实现体
void *memcpy(void *pvTo,const void *pvFrom,size_t size)
{
assert((pvTo!=NULL)&&(pvFrom!=NULL));
byte *pbTo=(byte*)pvTo; //防止地址被改变
byte *pbFrom=(byte*)pvFrom;
while (size-- >0)
pbTo++ = pbForm++;
return pvTo;
}

九、内存的分配方式
分配方式有三种,请记住,说不定那天去面试的时候就会有人问你这问题
1、 静态存储区,是在程序编译时就已经分配好的,在整个运行期间都存在,如全局变量、常量。
2、 栈上分配,函数内的局部变量就是从这分配的,但分配的内存容易有限。
3、 堆上分配,也称动态分配,如我们用new,malloc分配内存,用delete,free来释放的内存。

十、内存分配的注意事项
用new或malloc分配内存时,必须要对此指针赋初值。
用delete 或free释放内存后,必须要将指针指向NULL
不能修改指向常量的指针数据

十一、内容复制与比较
//数组……
char a[]=”Hello Word!”;
char b[10];
strcpy(b,a);
if (strcmp(a,b)==0)
{}
//指针……
char a[]=”Hello Word!”;
char *p;
p=new char[strlen(a)+1];
strcpy(p,a);
if (strcmp(p,a)==0)
{}

十二、sizeof的问题
记住一点,C++无法知道指针所指对象的大小,指针的大小永远为4字节
char a[]=”Hello World!”
char *p=a;
count sizeof(a) end; //12字节
count sizeof(p) endl; //4字节
而且,在函数中,数组参数退化为指针,所以下面的内容永远输出为4
void fun(char a[1000])
{
count sizeof(a) endl; //输出4而不是1000
}

十三、关于指针
1、 指针创建时必须被初始化
2、 指针在free 或delete后必须置为NULL
3、 指针的长度都为4字节
4、释放内存时,如果是数组指针,必须要释放掉所有的内存,如
char *p=new char[100];
strcpy(p,”Hello World”);
delete []p; //注意前面的[]号
p=NULL;
5、数组指针的内容不能超过数组指针的最大容易。
如:
char *p=new char[5];
strcpy(p,”Hello World”); //报错 目标容易不够大
delete []p; //注意前面的[]号
p=NULL;

十四、关于malloc/free 和new /delete
l malloc/free 是C/C+的内存分配符,new /delete是C++的内存分配符。
l 注意:malloc/free是库函数,new/delete是运算符
l malloc/free不能执行构造函数与析构函数,而new/delete可以
l new/delete不能在C上运行,所以malloc/free不能被淘汰
l 两者都必须要成对使用
l C++中可以使用_set_new_hander函数来定义内存分配异常的处理

十五、C++的特性
C++新增加有重载(overload),内联(inline),Const,Virtual四种机制
重载和内联:即可用于全局函数,也可用于类的成员函数;
Const和Virtual:只可用于类的成员函数;
重载:在同一类中,函数名相同的函数。由不同的参数决定调用那个函数。函数可要不可要Virtual关键字。和全局函数同名的函数
不叫重载。如果在类中调用同名的全局函数,必须用全局引用符号::引用。
覆盖是指派生类函数覆盖基类函数
函数名相同;
参数相同;
基类函数必须有Virtual关键字;
不同的范围(派生类和基类)。
隐藏是指派生类屏蔽了基类的同名函数相同
1、 函数名相同,但参数不同,此时不论基类有无Virtual关键字,基类函数将被隐藏。
2、 函数名相同,参数也相同,但基类无Virtual关键字(有就是覆盖),基类函数将被隐藏。
内联:inline关键字必须与定义体放在一起,而不是单单放在声明中。
Const:const是constant的缩写,“恒定不变”的意思。被const修饰的东西都受到强制保护,可以预防意外的变动,能提高程序的健壮性。
1、 参数做输入用的指针型参数,加上const可防止被意外改动。
2、 按值引用的用户类型做输入参数时,最好将按值传递的改为引用传递,并加上const关键字,目的是为了提高效率。数据类型为内部类型
的就没必要做这件事情;如:
将void Func(A a) 改为void Func(const A &a)。
而void func(int a)就没必要改成void func(const int &a);
3、 给返回值为指针类型的函数加上const,会使函数返回值不能被修改,赋给的变量也只能是const型变量。如:函
数const char*GetString(void); char *str=GetString()将会出错。而const char *str=GetString()将是正确的。
4、 Const成员函数是指此函数体内只能调用Const成员变量,提高程序的键壮性。如声明函数 int GetCount(void) const;此函数体内就只能
调用Const成员变量。
Virtual:虚函数:派生类可以覆盖掉的函数,纯虚函数:只是个空函数,没有函数实现体;

十六、extern“C”有什么作用?
Extern “C”是由C++提供的一个连接交换指定符号,用于告诉C++这段代码是C函数。这是因为C++编译后库中函数名会变得
很长,与C生成的不一致,造成C++不能直接调用C函数,加上extren “c”后,C++就能直接调用C函数了。
Extern “C”主要使用正规DLL函数的引用和导出 和 在C++包含C函数或C头文件时使用。使用时在前面加上extern “c” 关键字即可。

十七、构造函数与析构函数
派生类的构造函数应在初始化表里调用基类的构造函数;
派生类和基类的析构函数应加Virtual关键字。
不要小看构造函数和析构函数,其实编起来还是不容易。
#i nclude iostream.h>
class Base
{
public:
virtual ~Base() { cout "~Base" endl ; }
};
class Derived : public Base
{
public:
virtual ~Derived() { cout "~Derived" endl ; }
};
void main(void)
{
Base * pB = new Derived; // upcast
delete pB;
}
输出结果为:
~Derived
~Base
如果析构函数不为虚,那么输出结果为
~Base

十八、#IFNDEF/#DEFINE/#ENDIF有什么作用
仿止该头文件被重复引用

学习C++必须掌握的概念
一、指针的概念
char str[] = “ABCDEFG”;
char *pc = str; //pc是指向string str的指针
short x = 33;  
short *px = &x; //px是指向short x的指针
cout *pc endl; //这条语句将打印字符‘A’
pc += 4; //指针向右移动4指向第5个字符
cout *pc endl; //这时这条语句将打印字符‘E’
pc--; //向左移动指针
cout *pc endl; //这时这条语句将打印字符‘D’
cout *px + 3 endl; //这条语句打印36因为=33+3
在 C 程序中,假设我们已定义了以下的几个变量及函数: int k, tem, *P1, *P2, a[5], f(), *P3(); 以下的设定
叙述(Assignment statements)中, 那些有语法上的错误? 并请说明其原因
1.P1 = &k;
2.P2 = a;
3.P3 = f;
4.P1 = &a[3];
5.P1 = P2;
答案:
(1) P1 = &k; P1是指针变量, 因此P1表位址,而k表示一般变量,&k表示取出k的位址,故正确.
(2) P2 = a; a是数组名称,此时可代表数组存放在内存中的起始位址,而P2为指针变量,故正确.
(3) P3 = f; f代表函数的名称,此时代表呼叫函数f,因此含有传回值,而P3为指针变量,故此式有错误.
(4) P1 = &a[3];P1表指针变量,代表位址,而&a[3]表取出索引(index)为3的数组元素的位址,故正确.
(5) P1 = P2; P1,P2皆为指针变量代表位址,此叙述是指将P2的位址指定给P1,故正确.

结构的概念
结构是一种类型,它的成员默认是public.
struct Student //定义一个结构Student用来存放学生的资料
{
int id; //编号
char name[30]; //名字
}
Student s = {555, “Davis, Samuel”}; //初始化Student的实例s
cout s.id “ “ s.name endl; //这条将打印“ 555 Davis,Samuel”
类的概念我想大家都应该很清楚了,我就不废话了。
类的继承的概念
class base
{
private:
int a;
protected:
int b;
public:
int c;
};
class sub1:public base {…};
class sub2:private base{…};
说明在base,sub1,sub2中所能取用的data members各为何.并指出这些data members的access mode(private, protected或public).
Ans:
class data members access mode
base a private
b protected
c public
sub1
b protected
c public
sub2
b private
c private

虚函数和抽象类
多态 (polymorphism)
面向对象程设计的核心观念之一就是多态--它使一群类似的行为的同名称的方法, 但各对象可依适合自己所需的方式建构此同名动作的实行
细节, C++多态的关键在于所谓的虚函数这一类的函数。
虚函数(virtual function)
透过虚拟函数, 衍生类可重新定义基类的成员函数, 若想在C++程式中建立虚拟函数(然後才能实行多态), 只需利用virtual关键字声明函数即
可(如下所示)
virtual void Display();
虚函数的用处
针对共享相同基类的那些对象, 可有较一致的使用态度, 例如, 你可能定义一个名为Shape且带有一 个Draw虚拟成员函数的基类, 然后从它派
生了Circle类和Square类, 而且它们各自带有自己的Draw成员函数.从这些类派生建立的每个对象都可呼叫Draw成员函数; 但是编译程式可确
保各自应呼叫那个版本的Draw 函数.是基类的还是派生类的。
一个例子
重要观念: 指向父类的指针也可用来指向子类别
#i nclude iostream.h>
class BaseClass
{
public:
virtual void Display( ) { cout 100 "\n"; }
};
class DerivedClass: public BaseClass
{
public:
virtual void Display( ) { cout 200 "\n"; }
};
void Print(BaseClass* pbc)
{ pbc->Display( ); }
int main( )
{ BaseClass* pbc = new BaseClass;
DerivedClass* pdc = new DerivedClass;
Print(pbc);//显示 100
Print(pdc);//显示 200
return 0;
}
V-table (Virtual function table)
当C++程式呼叫非虚函数, 采用与C程式呼叫函数所用方式一样的静态绑定来呼叫函数. 但是C++程式 若是透过指向类别的指针来呼叫虚函数
时, 编译程式则采用所谓的晚期绑定(late binding)或静态绑定 (static binding)技术来呼叫函数.
而C++虚函数用虚函数表(virtual function table), 或称V-表来实作动态绑定, 所谓的V-表是一 个函数指针的阵列, 这是编译程序替每个
使用虚函数的类所建制的。
纯虚函数 (pure virtual function)
一个不仅可被重新定义, 而且必须被重新定义的成员函数就称为纯虚函数, 你只要指定函数一个零值 (更有效说法是一个空指针),就可将虚
成员函数转为纯虚成员函数,如以下所示
virtual void PrintData() = 0;
抽象类 (abstract class)
当一个类含有至少一个纯虚函数时, 此类就称为抽象类,而你无法以此类来衍生建立对象.

C++ template classes
一般的声明及使用
class Collection
{ …
int A[10];
}
Collection object;
模板的声明及使用
template class T> //注意这里
class Collection
{ …
T A[10]; }// generic declaration
Collection int> object; //注意这里
Collection char> object; //注意这里

冒泡排序
陀陀木修 发表于2005-5-22 12:23:00
1、排序方法
 将被排序的记录数组R[1..n]垂直排列,每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则,从下往
上扫描数组R:凡扫描到违反本原则的轻气泡,就使其向上"飘浮"。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。
(1)初始
  R[1..n]为无序区。
(2)第一趟扫描
  从无序区底部向上依次比较相邻的两个气泡的重量,若发现轻者在下、重者在上,则交换二者的位置。即依次比较(R[n],R[n-1]),(R[n-1],R[n-2]),…,(R[2],R[1]);对于每对气泡(R[j+1],R[j]),若R[j+1].key  第一趟扫描完毕时,"最轻"的气泡就飘浮到该区间的顶部,即关键字最小的记录被放在最高位置R[1]上。
(3)第二趟扫描
  扫描R[2..n]。扫描完毕时,"次轻"的气泡飘浮到R[2]的位置上……
 最后,经过n-1 趟扫描可得到有序区R[1..n]
注意:
  第i趟扫描时,R[1..i-1]和R[i..n]分别为当前的有序区和无序区。扫描仍是从无序区底部向上直至该区顶部。扫描完毕时,该区中最
轻气泡飘浮到顶部位置R[i]上,结果是R[1..i]变为新的有序区。
2、冒泡排序过程示例
 对关键字序列为49 38 65 97 76 13 27 49的文件进行冒泡排序的过程【参见动画演示】
3、排序算法
(1)分析
 因为每一趟排序都使有序区增加了一个气泡,在经过n-1趟排序之后,有序区中就有n-1个气泡,而无序区中气泡的重量总是大于等于
有序区中气泡的重量,所以整个冒泡排序过程至多需要进行n-1趟排序。
 若在某一趟排序中未发现气泡位置的交换,则说明待排序的无序区中所有气泡均满足轻者在上,重者在下的原则,因此,冒泡排序过程
可在此趟排序后终止。为此,在下面给出的算法中,引入一个布尔量exchange,在每趟排序开始前,先将其置为FALSE。若排序过程中发生了交换,则将其置为TRUE。各趟排序结束时检查exchange,若未曾发生过交换则终止算法,不再进行下一趟排序。
(2)具体算法
void BubbleSort(SeqList R)
{ //R(l..n)是待排序的文件,采用自下向上扫描,对R做冒泡排序
int i,j;
Boolean exchange; //交换标志
for(i=1;i exchange=FALSE; //本趟排序开始前,交换标志应为假
for(j=n-1;j>=i;j--) //对当前无序区R[i..n]自下向上扫描
if(R[j+1].key R[0]=R[j+1]; //R[0]不是哨兵,仅做暂存单元
R[j+1]=R[j];
R[j]=R[0];
exchange=TRUE; //发生了交换,故将交换标志置为真
}
if(!exchange) //本趟排序未发生交换,提前终止算法
return;
} //endfor(外循环)
} //BubbleSort
4、算法分析
(1)算法的最好时间复杂度
 若文件的初始状态是正序的,一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值:
Cmin=n-1
Mmin=0。
 冒泡排序最好的时间复杂度为O(n)。
(2)算法的最坏时间复杂度
 若初始文件是反序的,需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值:
Cmax=n(n-1)/2=O(n2)
Mmax=3n(n-1)/2=O(n2)
 冒泡排序的最坏时间复杂度为O(n2)。
(3)算法的平均时间复杂度为O(n2)
 虽然冒泡排序不一定要进行n-1趟,但由于它的记录移动次数较多,故平均时间性能比直接插入排序要差得多。
(4)算法稳定性
 冒泡排序是就地排序,且它是稳定的。
5、算法改进
 上述的冒泡排序还可做如下的改进:
(1)记住最后一次交换发生位置lastExchange的冒泡排序
  在每趟扫描中,记住最后一次交换发生的位置lastExchange,(该位置之前的相邻记录均已有序)。下一趟排序开始时,R[1..lastExchange-1]是有序区,R[lastExchange..n]是无序区。这样,一趟排序可能使当前有序区扩充多个记录,从而减少排序的趟数。具体算法【参见习题】。
(2) 改变扫描方向的冒泡排序
①冒泡排序的不对称性
  能一趟扫描完成排序的情况:
 只有最轻的气泡位于R[n]的位置,其余的气泡均已排好序,那么也只需一趟扫描就可以完成排序。
【例】对初始关键字序列12,18,42,44,45,67,94,10就仅需一趟扫描。
需要n-1趟扫描完成排序情况:
  当只有最重的气泡位于R[1]的位置,其余的气泡均已排好序时,则仍需做n-1趟扫描才能完成排序。
【例】对初始关键字序列:94,10,12,18,42,44,45,67就需七趟扫描。

②造成不对称性的原因
  每趟扫描仅能使最重气泡"下沉"一个位置,因此使位于顶端的最重气泡下沉到底部时,需做n-1趟扫描。
③改进不对称性的方法
 在排序过程中交替改变扫描方向,可改进不对称性。具体算法【参见习题】。

C++,这个词在中国大陆的程序员圈子中通常被读做“C加加”,而西方的程序员通常读做“see plus plus”, 它是一种被使用的非常广泛的计算机编程语言。C++是一种静态数据类型检查的,支持多重编程范式的通用程序设计语言。它支持过程序程序设计、数据抽象、面向对象程序设计、泛型程序设计等多种程序设计风格。
布贾尼•斯特劳斯特卢普(Bjarne Stroustrup)博士在20世纪80年代发明并实现了C++(最初这种语言被称作“C with Classes”)。一开始C++是作为C语言的增强版出现的,从给C语言增加类开始,不断的增加新特性。虚函数、运算符重载、多重继承、模板、异常、RTTI、名字空间逐渐被加入标准。1998年国际标准组织(ISO)颁布了C++程序设计语言的国际标准ISO/IEC 14882-1998。遗憾的是,由于C++语言过于复杂,以及他经历了长年的演变,直到现在(2004年)只有少数几个完全符合这个标准的编译器出现。
另外,就目前学习C++而言,可以认为他是一门独立的语言;他并不依赖C语言,我们可以完全不学C语言,而直接学习C++。根据《C++编程思想》(Thinking in C++)一书所评述的,C++与C的效率往往相差在正负5%之间。所以有人认为在大多数场合C++ 完全可以取代C语言。
C++语言发展大概可以分为三个阶段:第一阶段从80年代到1995年。这一阶段C++语言基本上是传统类型上的面向对象语言,并且凭借着接
近C语言的效率,在工业界使用的开发语言中占据了相当大份额;第二阶段从1995年到2000年,这一阶段由于STL和后来的Boost等程序库的出
现,泛型程序设计在C++中占据了越来越多的比重性。当然,同时由于Java、C#等语言的出现和硬件价格的大规模下降,C++开始逐渐退出用户
级程序的开发领域,转向系统级别的程序开发;第三阶段从2000年至今,由于以Loki、MPL等程序库为代表的产生式编程和模板元编程的出
现,C++出现了发展历史上又一个新的高峰,这些新技术的出现以及和原有技术的融合,使C++已经成为当今主流程序设计语言中最庞大,最
复杂的一员。

何为算法?
陀陀木修 发表于2005-5-22 12:09:00
不论您在您的生活或工作中是否已经注意到,算法的直接或隐含的存在已经日益增多。算法是软件运算部分功能的基础,它存在于嵌入或
非嵌入的系统中间,默默地做着底层的事情。有些计算的功能是显而易见的,因此在编程的过程中算法并不显得很重要,不需要单独去考虑它,例如控制单一的开关,或单一的视窗。而越来越多与物理世界相关的复杂运算,人们并不直接地了解如何去算;那么在编程的过程中就需要对于这些算法进行开发;例如,如何最有效地压缩音乐信号数据,诸如通行的MP3算法;或者手机里面的GSM编解码算法。
计算机硬件的发展的速度之快,在其存储量与运算速度方面都早已超过了人类大脑。但是,却因为大大缺少足够的算法,使人们尚做不出
能够充分使用这些硬件的软件,以至于巨大的计算机还模拟不出一个简单蚂蚁的功能。模拟人类就更加遥远,即使是模拟人类的某个单一功能,如,语音对话。
那些已经相对成熟并经常使用的算法,就已经被固化在软件模块里面,甚至半导体芯片之中;可以方便地直接使用而无须重新开发。越是
尚未成熟标准化的领域,算法越需要直接去开发,例如语音识别的算法。更有人类与日俱增的观察世界和控制世界的欲望,了解自身、相互沟
通、以及提高生活的舒适程度的愿望。而这些新的愿望在刚出现的时候,往往还没有已经固化的算法可供选用,这样就不断产生出对新的算法
研发的需求。当然也存在由于商业的考虑而需要‘重新发明车轮’的情况。
任何算法以及软件都是要在一定的硬件系统中运行。一个完整的计算机或嵌入电子装置的功能,都是软、硬件结合的结果。因此系统结构
的合理性和算法同样很重要。但是,我们工作室的侧重面是对算法的探讨、研发和设计、实现。对于系统我们仅仅是去优化地选择使用,并不
花主要的精力去设计。在一切情况下,对于算法的需求包括未知算法本身的研发,以及已知算法在具体系统中的实现。


可以运用分而治之方法来解决排序问题,该问题是将n 个元素排成非递减顺序。分而治之方法通常用以下的步骤来进行排序算法:若n 为1,算法终止;否则,将这一元素集合分割成两个或更多个子集合,对每一个子集合分别排序,然后将排好序的子集合归并为一个集合。
假设仅将n 个元素的集合分成两个子集合。现在需要确定如何进行子集合的划分。一种可能性就是把前面n- 1个元素放到第一个子集中(称为A),最后一个元素放到第二个子集里(称为B)。按照这种方式对A递归地进行排序。由于B仅含一个元素,所以它已经排序完毕,在A排完序后,只需要用程序2 - 1 0中的函数i n s e r t将A和B合并起来。把这种排序算法与I n s e r t i o n S o r t(见程序2 - 1 5)进行比较,可以发现这种排序算法实际上就是插入排序的递归算法。该算法的复杂性为O (n 2 )。把n 个元素划分成两个子集合的另一种方法是将含有最大值的元素放入B,剩下的放入A中。然后A被递归排序。为了合并排序后的A和B,只需要将B添加到A中即可。假如用函数M a x(见程序1 - 3 1)来找出最大元素,这种排序算法实际上就是S e l e c t i o n S o r t(见程序2 - 7)的递归算法。
假如用冒泡过程(见程序2 - 8)来寻找最大元素并把它移到最右边的位置,这种排序算法就是B u b b l e S o r t(见程序2 - 9)的递归算法。这两种递归排序算法的复杂性均为(n2 )。若一旦发现A已经被排好序就终止对A进行递归分割,则算法的复杂性为O(n2 )(见例2 - 1 6和2 - 1 7)。
上述分割方案将n 个元素分成两个极不平衡的集合A和B。A有n- 1个元素,而B仅含一个元素。下面来看一看采用平衡分割法会发生什么情况: A集合中含有n/k 个元素,B中包含其余的元素。递归地使用分而治之方法对A和B进行排序。然后采用一个被称之为归并( m e rg e)的过程,将已排好序的A和B合并成一个集合。
例2-5 考虑8个元素,值分别为[ 1 0,4,6,3,8,2,5,7 ]。如果选定k = 2,则[ 1 0 , 4 , 6 , 3 ]和[ 8 , 2 , 5 , 7 ]将被分别独立地排序。结果分别为[ 3 , 4 , 6 , 1 0 ]和[ 2 , 5 , 7 , 8 ]。从两个序列的头部开始归并这两个已排序的序列。元素2比3更小,被移到结果序列;3与5进行比较,3被移入结果序列;4与5比较,4被放入结果序列;5和6比较,.。如果选择k= 4,则序列[ 1 0 , 4 ]和[ 6 , 3 , 8 , 2 , 5 , 7 ]将被排序。排序结果分别为[ 4 , 1 0 ]和[ 2 , 3 , 5 , 6&n

文章来源:CSDN

posted on 2009-02-16 10:52 向左向右走 阅读(743) 评论(0)  编辑 收藏 引用 所属分类: C/C++学习资料库

只有注册用户登录后才能发表评论。