从数据到算法

数据与数据结构

任何问题解决方案都不可能脱离数据结构而单独存在。所谓数据类型就是一个值的集合和定义在这个值集上的一组操作的总称。一般而言，数据类型可分为原子型和结构型。在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。这些已经事先定义好的数据类型就是所谓的原子型。经过数据类型规定后的若干有序0和1的组合就在计算机中呈现出一定的意义。最初的表现形式就是原子型数据类型。而在某些时候，一旦需要引入某种新的数据类型时，总是借助编程语言所提供的原子型数据类型来描述或定义新数据的存储结构，这也就是所谓的结构型。换句话说，原子型数据经过一定规则重组后即可形成结构型数据。

原子数据类型：
这里需要注意的一些问题是：

char(signed char) -128 ~ 127;
unsigned char 0 ~ 255
short(signed short) -32768 ~ 32767
unsigned short 0 ~ 65535

仅有原子型数据仍然是不够的。将原子型数据按照一定规则重组，就可以形成结构型数据。换句话说，结构化的数据可以由简单的数据组成。将某人的联系地址想象一个结构化的数据，那么在这个结构中可能有若干个项目，它们都是一些简单的基本数据。例如，居住地的门牌号，然后是所在街道的名字、城市的名字、省份的名称和邮政编码、

C++中的STL

标准模板库（STL）是C++中的一个重要特性，也是本书介绍的重点内容之一。STL是一个具有工业强度的、高效的C++程序库。它被容纳于C++标准程序库中，是 ANSI/ISO C++标准中最新的也是极具革命性的一部分。该库包含了诸多在计算机科学领域里常用的基本数据结构和基本算法。为广大C++程序员提供了一个可扩展的应用框架，高度体现了软件的可复用性。

标准模板库体现了泛型化程序设计的思想（generic programming）,并引入了诸多新的名字，比如像需求（requirements)、概念（concept）、模型（model）、容器（container）和迭代器（iterator）等。这些都是支持泛型思想的概念，泛型思想也是一种软件的复用技术，这看起来与C++的特性是如此相合。

STL 构成

STL 的构成可以概括为：3大主体、6大组件、13个头文件。所谓13个头文件是指在C++标准中，STL被组织为下面的13个头文件，包括："algorithm"、"deque"、"functional"、"iterator"、"vector"、"list"、"map"、"memory"、"numeric"、"queue"、"set"、"stack" 和 "utility"。这些头文件包含了全部的代码，而这些代码从广义上讲可以被分成3大类：container（容器）、algorithm（算法）和iterator（迭代器），且几乎所有的代码都采用模板类和模板函数地方式，显然这有利于代码的重用。这3类也就是STL的3大主体。事实上如果细致地考虑STL的组成，它应当包括6个组件，除了前面比较重要的3大主体以外，还包括：仿函数、适配器和空间配置器。下面主要对3大主体进行一个概要介绍。

1.容器
在实际的开发过程中，数据结构本身的重要性不会逊于操作与数据结构的算法的重要性，当程序中存在着对时间要求很高的部分时，数据结构的选择就显得更加重要。这一点在很多算法题目的解答时表现得尤为明显。容器部分主要由头文件 "vector"、"list"、"deque"、"set"、"map"、"stack"和"queue" 组成，其中提供的容器主要包括：

• 向量（vector)
• 链表（list）
• 栈（stack）
• 队列（queue）
• 优先队列（priority_queue）
• 双向队列（deque）
• 集合（set）
• 多重集合（multiset）
• 映射（map）
• 多重映射（multimap）

2.算法
算法时STL的一个重要组成部分，STL中大约包含了70个通用算法，用于控制各种容器，同时也可以操纵内建数组。所有这些操作都是在保证执行效率的前提下进行的，且所有算法都遵循所谓的泛型算法通则，即

• 所有算法的前两个参数都一对 iterator：(first,last), 用来指出容器内一个范围内的元素
• 每个算法的声明中，都表现出它所需要的最低层次的iterator 类型。
• 大部分算法都可以用仿函数（function object，又称 functor）来更改准则。

STL利用模板机制提供了相当多的有用算法，其中常用的包括比较、交换、查找、遍历、复制、修改、移除、反转、排序、合并等。如此，在熟悉了STL之后，许多代码都可以被大大简化，只需要通过调用一两个算法模板，就可以完成所需要的功能并大大地提升效率。

STL中的算法部分主要由头文件 "algorithm"、"numeric" 和 "functional" 组成。头文件"algorithm" 是所有STL头文件中最大的一个，也是 STL 中算法部分的主体。它由很多模板函数组成，可以认为每个函数在很大程度上都是独立的。"algorithm"囊括的算法包括查找、交换和排序等。"numeric"体积很小，只包含几个在序列上面进行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作。"functional"中则定义了一些模板类，用以声明函数对象。

3.迭代器
迭代器起初是设计模式中的一种，意思是提供一种方法，按顺序访问某个容器所含的各个元素，而无需暴露该容器的内部表述方法。这也是软件设计的一个基本原则，也就是说通过引进一个间接层来简化所有问题的解决。在STL中，迭代器被用来将算法和容器联系起来，起到某种粘合作用。容器提供迭代器，而算法使用迭代器。几乎STL提供的所有算法都是通过迭代器存取元素序列进行工作的，每一个容器都定义了其本身所专有的迭代器，用以存取容器中的元素。迭代器能够使容器与算法不干扰地相互发展，最后又能无间隙地粘合起来。特别地，迭代器还重载了*、++、==、！=、=等运算符，用以操作复杂的数据结构。

迭代器部分主要由头文件"utility"、"iterator" 和 "memory"组成。其中，utility 是一个很小的头文件，它包括了贯穿使用在 STL 中的几个模板的声明，"iterator" 中提供了迭代器使用的许多方法，可以认为是迭代器部分的主体。"memory" 则以不同寻常的方式为容器中的元素分配存储空间，同时也为某些算法执行期间产生的临时对象提供机制。

指针和数组

数组是最简单的、最基本的线性数据结构，它可以被认为是程序设计语言提供的一种已经封装好了的数据结构。此外，许多数据结构的实现也是以数组为基础的（例如顺序栈以及循环队列）。还有另外一种数据结构实现方法则以链表为基础（例如链式栈以及链式队列）。

（这里面涉及了关于动态内存管理以及指针方面的内容，而且指针和数组之间还具有非常紧密的联系。）

指针提供了对内存进行进行直接操作的手段，这使得C/C++语言灵活而强大，但是在某种程度上也增大了风险。内存错误往往导致严重的后果却难以察觉。

冯-诺依曼结构的一个核心理论要点就是将程序指令存储器和数据存储器合并在一起，即所谓的“程序存储”。依据这一原理，程序的数据和指令都存在内存中。从物理意义上讲，内存就是一块具有存储功能的半导体材料。任何需要被计算机执行的程序（包括指令和数据），都要先从外部存储器（包括硬盘、光盘等）调入内存后才能被执行。内存中同时持有很多数据，当前需要哪个数据，CPU都会从内存中精确地找到它然后再让其参与运算。

内存采取了同样的管理方法，首先内存被划分为许许多多个很小的存储单元，然后这些存储单元被编上了号，由于内存中的存储单元太多，所以这些编号往往是一个非常大的整数，例如 0x0019F878（这是一个十六进制表示的大整数）。换句话说，CPU执行的机器码通过各内存位置的唯一编号来操作这些内存中的数据，这些编号就是所谓的内存地址，而编译器的工作过程就是将程序中的变量和操作翻译成对内存地址进行操作的机器语言。所以，在最终的机器码里其实是不存在变量名或变量类型的。

简单来说，内存就是一段连续的存储空间，内存被均等地分为多个存储单元，每个单元都成为一个内存单元。数据在内存中按一定的顺序连续存放。为了便于管理，系统给每个内存单元都编了一个号，成为内存地址。每个内存单元的地址都是一个很大的整数，例如：0x0019F878。计算机中也提供了对于一个数据的“直接访问”和“间接访问” 。通过变量来访问数据就是间接的访问方式，通过地址来访问数据就是直接的访问方式。

在C++中，一个变量的地址成为该变量的“指针”。指针也是一种数据，它当然也可以被存在一个内存单元中。如果定义一个变量专门用来存放另一个变量的地址，则它就是一个指针变量。即用来存储指针的变量，就称为指针变量。指针变量的值就是指针。

int a,b,c; 相对于类型而言，可以认为和变量名结合的关系更紧密些，所以上述定义的结果是a是一个指针变量，而b和c都是int性变量！如果想将a、b和c都定义成指针型变量则只能采取如下的方式。
int *a;
int *b;
int *c;

对于上例中的指针类型p,如果有操作p++,那么对于指针变量p自加1意味着什么呢？因为p是一个int型指针，因此p++操作意味着将指针p移动4个字节（假设一个int型变量占据4字节的空间）。可见正确地定义指针类型是非常重要的。指针是变量的地址，这个地址的获得必须通过一个已经被分配了存储空间的变量来完成，变量的地址只能通过指针运算符*或取地址符&来获得，而不能直接指定一个具体的地址。另外，对于&*p 和 *&p的区别。因为*和&具有相同的优先级，按照从右向左的方向结合。

动态内存管理
数组在定义时，系统会为其分配固定大小的内存空间，这被称为是静态内存分配。静态内存分配的好处在实现简单，操作方便，但也致使程序的可伸缩性大大降低。因为在很多的情况下，程序员无法预先确定要使用多大的数组。为了解决这样的问题，就需要使用动态内存分配。所谓动态内存分配就是指在程序执行的过程中动态地分配或者回收存储空间的分配内存的方法。由于动态分配不需要预先分配存储空间，而且分配的空间还可以根据程序的需要扩大或缩小，因此它能够有效地克服静态内存分配所带来的种种弊病。

创建一个新的类对象时，通常需要完成的工作包括：首先，为对象分配内存；其次调用构造函数来初始化那块内存。程序员应当保证初始化过程正确进行，这一点非常重要，因为初始化的问题是程序出错的主要原因之一。

在C++中，程序员可以利用关键字new和delete来实现内存空间的动态管理，new可以根据具体对象的不同而自动开辟合适的内存空间，而delete则负责回收由new开辟的内存空间，它们帮助程序在运行时从堆中分配存储单元。为普通的变量申请内存空间，可以使用下面的语法规则:
float * p = new float(3.14)
在C++里同样可以使用new来为一个数组分配内存空间，并相应地使用delete来将其释放。其具体语法如下例所示：
Point * pt = new Point[100];
上述代码使用new 在堆上创建了一个含有100个对象的数组，并把返回的指针赋给了指针变量pt。这样就在堆上为100个Point对象分配了足够的内存并为每一个对象调用了构造函数。那如何将这个数组所占据的空间释放呢？
delete pt 这就表示把数组中的第一个对象释放了，也就仅仅只是为第一个对象调用了析构函数，而另外99个析构函数没有进行，所以这是错误的语句。正确的语句应当采取下面这样的语句来实现：
delete [] pt;
空的方括号告诉编译器产生从数组创建时存放的地方取回数组中对象数量的代码，并为数组的所有对象调用析构函数。

避免内存错误
内存管理上的错误是用C/C++语言进行程序设计时最可怕的一类错误，它的危险首先原自它的不易察觉性，另一方面不得不承认这种错误的结果也常常是非常致命的。通常的内存错误被归结为以下4点：内存泄漏、重复释放、坏指针问题和超量写内存。

1.内存泄漏
在分配了一块内存空间之后，如果不再需要这些数据就应当考虑将其释放。而如果程序员没有将其释放，那么这块空间将随同程序运行而一直存在。对于一个需要运行较长时间的计算机程序而言，如果它只是一味地分配而不进行回收，那么最终系统资源无疑将被耗尽。于是程序在这个过程中将被运行得越来越慢，最终系统陷入瘫痪。在计算机中有很多程序要运行很长时间，操作系统实际上就是一个"死循环"。还有很多网络服务程序也会运行很长时间。比如一个图像处理程序，它打开的图片文件可能有几百字节，也有可能是几百兆，如果内存仅仅是分配而忘记了回收，或是没有得到很好的回收，那么内存资源就好像一个漏了的水箱中的水不断地泄漏，直到最终耗尽为止----这就是所谓的内存泄漏。

内存的泄漏通常是由回收失败导致的，例如下面的这个例子，被分配的内存在函数的最后一行进行了释放，但当执行到"if(End()) return;" 处时，函数如果满足结束条件就会直接返回，于是发生了回收失败。异常、错误和其他各种throw和catch语句经常是导致内存泄漏的原因。

void Memory_Leak()
{
     int * list = new int[100];
     ... ...
     if (End()) return;
     ... ...
     delete[] list;
}

还有一种可能引起内存泄漏的原因是忘记了释放一个数据结构的某些部分。例如定义以下结构。

typedef struct{
    char *name;
    int number;
    int age;
    char *address;
    int phonel
} Student;

对于 Student 这个结构的担忧一个相关函数如下：

void Memory_Leak()
{
     Student* s;
     s= new Student;
     s->name = new char[100];
     ... ...
     s->address = new char[50];
     ... ...
     delete s;
}

上面的例子中，一个 Student 结构体被分配了内存并在程序结束的时候内存空间得以释放，但这个结构体的一些域并没有释放，
例如 name 和 address 都被分配了空间，但它们没有释放。这里要注意结构体被释放并不表示它的域也被释放了！

2、重复释放
分配内存必须释放，而且每次分配仅能对应一次释放。如果释放一个根本不存在的指针，亦或对于一个指针重复释放都会引起不必要的麻烦。要是释放函数能够自动检查将要被释放的空间是否已经被释放过了该有多好，然后并不是所有的存储分配器都留用足够的空间来记录那些内存块的释放和分配状态。何况内存分配的效率对于整个程序的运行表现影响巨大，如果在运行时反复进行检查势必导致程序效率大幅降低。当然，如果这个释放函数并不是经常被调用，而且出于程序的安全性和可读性考虑可以试着写一个防止重复释放的小函数，如下定义了一个宏，它可以用来避免重复释放。

#define SAFE_DELETE(P)
{
 if((p)!=NULL)
 {
    delete (p);
    (p) = NULL;
 }
}

下面是可能发生重复释放的情况，首先看一个例子，下面的例子对同一空间进行了重复释放。

void Twice_Free(x)
{
   ... ...
   delete[] x;
}

int main(int argc, char** argv)
{
     int *x = new int[10];
     ... ...
     Twice_Free(x);
     ... ...
     delete[] x;
     return 0;

程序最开始开辟了一块内存内存空间用来存储一些整型数据，并在最后将这些数据释放。但是在程序运行过程中调用一个函数“Twice_Free(X);”，在这个函数中x被释放过了一次，因此程序发生了重复释放。因为在很多情况下，指针可能发生了传递，而传递的仅仅是地址，也就是说在一个程序中可能存在多个指针同时指向一块内存空间，对于其中任何一个指针的释放都会对这块空间进行回收。但由于其他指针貌似并没有回收，于是粗心的人就会画蛇添足地进行重复释放。可以举一个更极端的例子来说明这种现象。

BYTE* temp_buffer1 = new BYTE[100];
... ...
BYTE* temp_buffer2 = temp_buffer1;
... ...
BYTE* temp_buffer3 = temp_buffer2;
... ...
delete [] temp_buffer1;
delete [] temp_buffer2;
delete [] temp_buffer3;

事实上，temp_buffer1、temp_buffer2和temp_buffer3 都指向同一块内存区域，无需释放3次，仅仅释放其中一次就可以达到目的。程序访问一段已经被释放了的内存空间可能引起很多危险。因为一旦内存块被释放，它其中的数据就有可能被应用程序或堆分配管理器修改。恰恰在修改之后，这块被占用的内存再次被其他的数据块访问到，后果就不堪设想了。一方面你所读到的程序其实是无用的，应用了这些没有任何意义的数据之后整个系统的运作都有可能受到影响，更糟的情况是你对这个块进行了写操作，也就是说你改写了本不该属于你的数据，结果程序就崩溃了！下面给出了一个小例子，在这个例子中程序引用了一个已经被释放了的指针。

void Twice_Free(x)
{
     ... ...
     delete[] x;
}

int main(int argc, char** argv){
     int *x = new int[10];
     ... ...
     Twice_Free(x);
     ... ...
     Function(x); // 错误！
     ... ...
     return 0;
}

一种避免上述错误发生的方法是当一个指针被释放时，就随即将其赋值为NULL,前面的宏定义里这样做了。但如果该指针同时存在多份副本的时候，仅对其中之一赋NULL，并不能从根本上预防错误的发生。总之，务必保证被分配的内存块仅被释放一次，保证已经被释放了的指针不会再次使用。如果这个指针曾经被复制了，就必须保证当它所指向的内存区域被释放之后，所以的副本都不应当被使用。

3、坏指针问题
内存管理方面的错误最主要是由坏指针问题所导致的，坏指针是一类问题的总称，它可能是由很多原因引起的。如果一个指针没有按预期指向应当指向的位置，那么当废弃这个指针时，一个通常的错误就发生了。

在这种情况下，最乐观的结果是指针终止于一些无效的内存空间。当发生这种情况时，程序经常会被立即终止。而可能发生的最糟糕的情况是一些随机的内存位置被修改了，但程序却继续运行下去。最终程序没有一点征兆地奔溃了，导致程序奔溃的数据看似与问题毫不相关，因为程序不知道从何时起就开始使用错误的数据了！这样一来，要想查出问题到底出在哪是非常不容易的。

那么问题是：坏指针从哪来呢？一个不可忽视的根源就是没有被很好初始化的数据。假设你声明了一个本地指针但忘记了初始化它，因为变量是被储存在栈里的，而栈可能充满了那些来自先前活动记录的数据，恰巧这些数据没有被丢弃，那么指针就可能带有它们的值。

由堆来分配的对象存在同样的初始化问题。C++能够通过初始化函数来帮助避免这些问题，当一个类的实例被创建后，初始化函数会被自动调用，无论是在堆上还是在栈上。写初始化函数是一个非常好的习惯，它确实非常有效。如果不知道正确的初始值，那么就将指针赋值为NULL，那么它将不会指向任何数据。大部分环境下，NULL是一个无效的地址，因此任何尝试读取数据的行为都会被立即中止。于是这些错误将相对比较容易定位和修正。

4、超量写内存
有时尽管指针被正确地初始化了，但程序员却不正确地进行了指针运算或者错误的内存地址操作，这同样会引起内存管理上的错误。

第一个常见的情况是数组越界；另一个可能的错误是分配了不足的内存，这种错误可能有很多情况：

#define array_size 10
int *a = new int[array_size];
... ...
int *b = new int[array_size];
... ...
memcpy(b,a,array_size); // 这个错误可能较数组越界访问更为隐蔽。原意是对两个整型数组进行复制，但上面的代码仅仅复制了其中array_size个字节，而事实上程序要完成既定任务，用于指示内存空间大小的参数应该为array_size*sizeof(int)个字节。

再举一个分配空间不足的例子。有时程序员会因为粗心而忘记字符串最后需要一个结束符"\0",如果忘记了这一点就有可能引起错误，考虑下面一段代码：

char *new_string(char *s)
{
    int len = strlen(s);
    char *new_s = new char[len];
    strcpy(new_s,s);
    return new_s;
}

上述例子中的错误在于程序没有为 string 分配足够的空间，用于指示新字符串长度的参数应该是 len +1,这样才给结束符留下了一个字节。

操作符的优先权也是迷惑程序员并诱使他们犯错的一个常见因素，在本章前面关于指针运算的介绍中强调过这一点，不慎地使用*和++（或--）,都有可能导致超量写内存。

另一个可能的错误是构造一个指向运行时栈中某值的指针，并将这个指针返回给函数调用者，例如：

int *p()
{
   int i=0;
   return &i;

尽管函数返回了一个指向零值整型的指针，但由于该整型变量位于一个活动记录中，而这个记录在函数返回时就会被删除。因此这个指针指向的内容随时会变成任何一个值，这完全取决于下一个使用它的函数如何操作它。

大整数乘法问题：（或许是我想复杂了）

#include <iostream>
#include <memory.h>
#define SIZE 14
using namespace std;

// 返回位数为 size1+size2
int* multi(int* num1,int size1, int* num2, int size2)
{
    int size = size1 + size2;
    int* ret = new int[size];
    int i=0;
    memset(ret,0,sizeof(int)*size);
    for(i=0;i<size2;++i){
       int k = i;
       for(int j=0;j<size1;++j)
          ret[k++] += num2[i] * num1[j];
    }
    
    for(i=0;i<size;++i){
       if(ret[i]>=10)
       {
           ret[i+1]+=ret[i]/10;
           ret[i]%=10;
       }
    }
    return ret;
}

int main(int argc, char** argv){
     int num1[SIZE]={1,2,3,4,5,6,7,8,9,1,1,1,1,1}; //第1个大整数 11111987654321
     int num2[SIZE]={1,1,1,2,2,2,3,3,3,4,4,4,5,5}; //第2个大整数 55444333222111
     int* ret = multi(num1,SIZE,num2,SIZE);
     for(int i=SIZE*2-1;i>=0;i--) cout<< ret[i];
     delete[] ret;
     return 0;

关于数组的引用

#include<iostream>
using namespace std;
int main(int argc,char* argv[]){
     int a[10] = {0,1,2,3,4,5,6,7,8,9};
     int *p;
     p= &a[0];
     cout<<a[0]<<endl;
     cout<<&a[0]<<endl;
     cout<<&a<<endl;
     cout<<a<<endl;
     cout<<p<<endl;
     cout<< *p<<endl;
     return 0;
}

可见指针p中存放着数组a的第一个元素a[0]处的地址，数组a的地址&a和数组名a的值都与首元素a[0]处的地址相同。*p的内容就是首元素a[0]的值。p+offset就是a[offset]的地址，或者说将指针p移动偏移量offset后，它就指向数组a中的第offset个元素。

#include<iostream>
using namespace std;
int main(int argc, char* argv[]){
     int a[10] = {0,1,2,3,4,5,6,7,8,9};
     int *p;
     p = &a[0];
     cout<< *(p++)<<endl;
     p = &a[0];
     cout<< *p++<<endl;
     p = &a[0];
     cout<< *(++p)<<endl;
     return 0;
}

• (*p)++ 表示p所指向的内容加1，在上例中，若p=&a[0]且a[0]=0,则(*p)++=1;
• 如果p当前指向数组a中的第i个元素，那么有如下结论：
  *(--p)与a[--i]的作用相同，p先自减，再做*运算；
  *(p--)与a[i--]的作用相同，先进行p运算，p再自减；
  *(++p)与a[++i]的作用相同，p先自加，再做运算。

需要说明的是，最后一点将指针运算和数组名a联系了起来。但两者并不能完全等同视之，即并非所有的运算都一样。特别地，可以通过指针运算来改变指针变量的值（也就是使指针向上或者向下移动），但是不能将同样的操作运用于a，即不存在a++之类的运算。只是因为a表示的是数组首元素的地址，它是一个指针常量，所包含的值在程序运行时是不能被改变的。这相当于"int i=0;i++;" 是可行的，但"int i=1++;" 则是错误的。这里定义一个二维数组a[3][3],则这个二维数组中各项在内存中的排序为a00,a01,a02,a10,a11,a12,a20,a21,a22。可以试图将其推广到更加复杂和通用的情况下，例如，有一个二维数组b[M][N]，若将其转化成一个一维数组B[MN],那么原二维数组中的b[m][n]项就对应一维数组中的B[(m+1)(n+1)-1].

基于上面的认识，可以编写一个简单的示例小程序如下：（遍历二维数组的正确方式）

#include<iostream>
using namespace std;
int main(int argc,char* argv[]){
     int a[3][3] = {0,1,2,3,4,5,6,7,8};
     int *p;
     p=&a[0][0];
     for(int i=0;i<9;i++) cout<<*p++<<endl;
     return 0;
}

数组的抽象数据类型

前面的介绍多偏重于数组的语法形式，一维数组其实是一个连续存储的线性表，而由于高维数组都可以转化成对应的一维数组，所以从这个角度来说，数组就是一个连续存储的线性表。

C++中的字符串

字符串是n个字符的有限序列，其中n>=0，例如"Hello World!" 。这些字符在内存中按顺序逐个存放，并以结束符"\0"结尾。
string 类的操作符：
== 是用来判断字符串s 和字符串t 是否相等
!= 是用来判断字符串s 和字符串t 是否不相等
（其实，我更想知道，字符串的小于、大于是怎么比较的，应该是从第一个字母开始，然后如果第一个字母是相等的，那么就接着比较第二个字母了，如果第二个字母是相等的，那么就接着比较第三个字母这样。）
string append(const chars); 该函数的作用是将字符串s追加到本字符串的末尾。
string assign(const chars); 该函数的作用是将字符串s赋给本字符串。
int compare(const string& str) const; 该函数的作用是比较两个字符串是否相同。
string& insert(unsigned int p0,const char *s); 该函数的作用是将字符串s插入到本字符串p0位置之前。
string substr(unsigned int pos,unsigned int n)const; 该函数的作用是取出本字符串中位置pos开始的n个字符，并将该新字符串返回。
unsigned int find(const basic_string& str)const;
该函数的作用是查找子字符串str在本字符串中第一次出现的位置。
unsigned int length()const;
该函数的作用是获得本字符串的长度。
void swap(string& str);
该函数的作用是将本字符串与字符串str进行交换。

文本的精确匹配

字符串是一种线性表，它在计算机应用系统（如文本编辑、情报检索、拼写检查、互联网搜索引擎和自然语言翻译等）中有着广泛的应用。模式匹配是指在目标文本串T（to,t1,t2,t3,...,tn-1)中检索子串P(p0,p1,p2,p3,...,pm-1)的过程，其中P成为模式（Pattern）。若能够在T中找到子串P，则称为匹配成功，否则匹配失败。