C++语言程序设计：第9、10、11、12、13章

1、第九章第九章 群体类群体类 和群体数据的组织和群体数据的组织 c+语言程序设计 c+语言程序设计 2 本章主要内容本章主要内容 l模板模板 l群体类群体类 l群体数据的组织群体数据的组织 c+语言程序设计 3 第一部分第一部分模板模板 l函数模板函数模板 l类模板类模板 c+语言程序设计 4 函数模板函数模板 l函数模板可以用来创建一个通用功能函数模板可以用来创建一个通用功能 的函数，以支持多种不同形参，进一的函数，以支持多种不同形参，进一 步简化重载函数的函数体设计。步简化重载函数的函数体设计。 l声明方法：声明方法： template 函数声明 函 数 模 板 c+语言程序设计 5 求绝对

2、值函数的模板求绝对值函数的模板 #include using namespace std; template t abs(t x) return x0?-x:x; int main() int n=-5; double d=-5.5; coutabs(n)endl; coutabs(d)endl; 函 数 模 板 运行结果：运行结果： 5 5.5 c+语言程序设计 6 求绝对值函数的模板分析求绝对值函数的模板分析 l编译器从调用编译器从调用abs()时实参的类型，推时实参的类型，推 导出函数模板的类型参数。例如，对导出函数模板的类型参数。例如，对 于调用表达式于调用表达式abs(n)，由于实参

3、，由于实参n为为 int型，所以推导出模板中类型参数型，所以推导出模板中类型参数t 为为int。 l当类型参数的含义确定后，编译器将当类型参数的含义确定后，编译器将 以函数模板为样板，生成一个函数：以函数模板为样板，生成一个函数： int abs(int x) return x0?-x:x; 函 数 模 板 c+语言程序设计 7 类模板的作用类模板的作用 使用类模板使用户可以为类声明一使用类模板使用户可以为类声明一 种模式，使得类中的某些数据成员、种模式，使得类中的某些数据成员、 某些成员函数的参数、某些成员函数某些成员函数的参数、某些成员函数 的返回值，能取任意类型（包括基本的返回值，能取任

4、意类型（包括基本 类型的和用户自定义类型）。类型的和用户自定义类型）。 类 模 板 c+语言程序设计 8 类模板的声明类模板的声明 l类模板：类模板： template class 类名 类成员声明 l如果需要在类模板以外定义其成员如果需要在类模板以外定义其成员 函数，则要采用以下的形式：函数，则要采用以下的形式： template 类型名 类名:函数名（参数表） 类 模 板 c+语言程序设计 9 例例9-2 类模板应用举例类模板应用举例 #include #include using namespace std; / 结构体结构体student struct student int id;

5、/学号学号 float gpa; /平均分平均分 ; 类 模 板 template /类模板：实现对任意类型数据进行存取类模板：实现对任意类型数据进行存取 class store private: t item; / 用于存放任意类型的数据用于存放任意类型的数据 int havevalue; / 用于标记用于标记item是否已被存入内容是否已被存入内容 public: store(void); / 默认形式（无形参）的构造函数默认形式（无形参）的构造函数 t getelem(void); /提取数据函数提取数据函数 void putelem(t x); /存入数据函数存入数据函数 ; / 默认

6、形式构造函数的实现默认形式构造函数的实现 template store:store(void): havevalue(0) 10 template / 提取数据函数的实现提取数据函数的实现 t store:getelem(void) / 如果试图提取未初始化的数据，则终止程序如果试图提取未初始化的数据，则终止程序 if (havevalue = 0) cout no item present! endl; exit(1); return item; / 返回返回item中存放的数据中存放的数据 template / 存入数据函数的实现存入数据函数的实现 void store:putelem(t

7、 x) havevalue+; / 将将havevalue 置为置为 true，表示，表示 item中已存入数值中已存入数值 item = x; / 将将x值存入值存入item 11 int main() student g= 1000, 23; store s1, s2; store s3; store d; s1.putelem(3); s2.putelem(-7); cout s1.getelem() s2.getelem() endl; s3.putelem(g); cout the student id is s3.getelem().id endl; cout retrieving

8、 object d ; cout d.getelem() endl; /输出对象输出对象d的数据成员的数据成员 / 由于由于d未经初始化未经初始化,在执行函数在执行函数d.getelement()时出错时出错 12 c+语言程序设计 13 第二部分第二部分群体数据群体数据 l线性群体线性群体 线性群体的概念 直接访问群体-数组类 顺序访问群体-链表类 栈类 队列类 c+语言程序设计 14 群体的概念群体的概念 群体群体是指由多个数据元素组成的集是指由多个数据元素组成的集 合体。群体可以分为两个大类：合体。群体可以分为两个大类：线性群线性群 体体和和非线性群体非线性群体。 线性群体中的元素按位置

9、排列有序，线性群体中的元素按位置排列有序， 可以区分为第一个元素、第二个元素等。可以区分为第一个元素、第二个元素等。 非线性群体不用位置顺序来标识元非线性群体不用位置顺序来标识元 素。素。 c+语言程序设计 15 线性群体的概念线性群体的概念 线性群体中的元素次序与其位置关线性群体中的元素次序与其位置关 系是对应的。在线性群体中，又可按照系是对应的。在线性群体中，又可按照 访问元素的不同方法分为访问元素的不同方法分为直接访问直接访问、顺顺 序访问序访问和和索引访问索引访问。 在本章我们只介绍直接访问和顺序在本章我们只介绍直接访问和顺序 访问。访问。 第一个元素第二个元素第三个元素最后一个元素

10、c+语言程序设计 16 数组数组 l静态数组是具有固定元素个数的群体，其静态数组是具有固定元素个数的群体，其 中的元素可以通过下标直接访问。中的元素可以通过下标直接访问。 缺点：大小在编译时就已经确定，在运 行时无法修改。 l动态数组由一系列位置连续的，任意数量动态数组由一系列位置连续的，任意数量 相同类型的元素组成。相同类型的元素组成。 优点：其元素个数可在程序运行时改变。 l动态数组类模板：例动态数组类模板：例9-3（9_3.h） 直接访问的线性群体 #ifndef array_class #define array_class using namespace std; #include

11、#include #ifndef null const int null = 0; #endif / null enum errortype invalidarraysize, memoryallocationerror, indexoutofrange ; char *errormsg = invalid array size, memory allocation error, invalid index: ; 动态数组类模板程序 17 template class array private: t* alist; int size; void error(errortype error,i

12、nt badindex=0) const; public: array(int sz = 50); array(const array array(void); array t operator t* (void) const; int listsize(void) const; void resize(int sz); ; 18 c+语言程序设计 19 数组类模板的构造函数数组类模板的构造函数 / 构造函数构造函数 template array:array(int sz) if (sz = 0) /sz为数组大小（元素个数），若小于为数组大小（元素个数），若小于0，则输出错误信息，则输出错误

13、信息 error(invalidarraysize); size = sz; / 将元素个数赋值给变量将元素个数赋值给变量size alist = new tsize; /动态分配动态分配size个个t类型的元素空间类型的元素空间 if (alist = null) /如果分配内存不成功，输出错误信息如果分配内存不成功，输出错误信息 error(memoryallocationerror); 直接访问的线性群体 c+语言程序设计 20 数组类的拷贝构造函数数组类的拷贝构造函数 template array:array(const array size = n; alist = new tn;

14、if (alist = null) error(memoryallocationerror); t* srcptr = x.alist; / x.alist是对象是对象x的数组首地址的数组首地址 t* destptr = alist; / alist是本对象中的数组首地址是本对象中的数组首地址 while (n-) / 逐个复制数组元素逐个复制数组元素 *destptr+ = *srcptr+; 直接访问的线性群体 c+语言程序设计 21 浅拷贝浅拷贝 alist size a a的数组元素 占用的内存 拷贝前 alist size a a的数组元素 占用的内存 拷贝后 alist size

15、b int main() array a(10); . array b(a); . template array:array( const array alist= x.alist; c+语言程序设计 22 深拷贝深拷贝 alist size a a的数组元素 占用的内存 拷贝前 alist size a a的数组元素 占用的内存 拷贝后 alist size b b的数组元素 占用的内存 c+语言程序设计 23 数组类的重载数组类的重载=运算符函数运算符函数 template array if (size != n) delete alist; alist = new tn; if (ali

16、st = null) error(memoryallocationerror); size = n; t* destptr = alist; t* srcptr = rhs.alist; while (n-) *destptr+ = *srcptr+; return *this; 直接访问的线性群体 c+语言程序设计 24 数组类的重载下标操作符函数数组类的重载下标操作符函数 template t / 返回下标为返回下标为n的数组元素的数组元素 return alistn; 直接访问的线性群体 c+语言程序设计 25 为什么有的函数返回引用为什么有的函数返回引用 l如果一个函数的返回值是一个对

17、象的如果一个函数的返回值是一个对象的 值，它就被认为是一个常量，不能成值，它就被认为是一个常量，不能成 为左值。为左值。 l如果返回值为引用。由于引用是对象如果返回值为引用。由于引用是对象 的别名，所以通过引用当然可以改变的别名，所以通过引用当然可以改变 对象的值。对象的值。 直接访问的线性群体 c+语言程序设计 26 重载指针转换操作符重载指针转换操作符 template array:operator t* (void) const / 返回当前对象中私有数组的首地址返回当前对象中私有数组的首地址 return alist; 直接访问的线性群体 c+语言程序设计 27 指针转换运算符的作用指

18、针转换运算符的作用 #include using namespace std; int main() int a10; void read(int *p, int n); read(a, 10); void read(int *p, int n) for (int i=0; ipi; int main() array a(10); void read(int *p, n); read(a, 10); void read(int *p, int n) for (int i=0; ipi; 直接访问的线性群体 c+语言程序设计 28 array类的应用类的应用 l例例9-4求范围求范围2n中的质数

19、，中的质数，n在程序在程序 运行时由键盘输入。运行时由键盘输入。 直接访问的线性群体 #include #include #include 9_3.h using namespace std; int main() array a(10); int n; int primecount = 0, i, j; cout = 2 as upper limit for prime numbers: ; cin n; aprimecount+ = 2; / 2是一个质数是一个质数 for(i = 3; i n; i+) if (primecount = a.listsize() a.resize(pri

20、mecount + 10); if (i % 2 = 0) continue; j = 3; while (j i/2) aprimecount+ = i; for (i = 0; i primecount; i+) cout setw(5) ai; if (i+1) % 10 = 0) cout endl; cout endl; 29 c+语言程序设计 30 链表链表 l链表是一种动态数据结构，可以用来链表是一种动态数据结构，可以用来 表示顺序访问的线性群体。表示顺序访问的线性群体。 l链表是由系列链表是由系列结点结点组成的，结点可以组成的，结点可以 在运行时动态生成。在运行时动态生成。 l

21、每一个结点包括每一个结点包括数据域数据域和指向链表中和指向链表中 下一个结点的下一个结点的指针指针（即下一个结点的（即下一个结点的 地址）。如果链表每个结点中只有一地址）。如果链表每个结点中只有一 个指向后继结点的指针，则该链表称个指向后继结点的指针，则该链表称 为单链表。为单链表。 顺序访问的线性群体 c+语言程序设计 31 单链表单链表 data1 data2 data3 datan null headrear 顺序访问的线性群体 c+语言程序设计 32 单链表的结点类模板单链表的结点类模板 template class node private: node *next; public:

22、t data; node(const t void insertafter(node *p); node *deleteafter(void); node *nextnode(void) const; ; 顺序访问的线性群体 c+语言程序设计 33 在结点之后插入一个结点在结点之后插入一个结点 data1 data2 p data template void node:insertafter(node *p) /p节点指针域指向当前节点的后继节点节点指针域指向当前节点的后继节点 p-next = next; next = p; /当前节点的指针域指向当前节点的指针域指向p 顺序访问的线性群体

23、c+语言程序设计 34 删除结点之后的结点删除结点之后的结点 顺序访问的线性群体 data1 data2 data3 node *node:deleteafter(void) node *tempptr = next; if (next = null) return null; next = tempptr-next; return tempptr; tempptr c+语言程序设计 35 链表的基本操作链表的基本操作 l生成结点生成结点 l插入结点插入结点 l查找结点查找结点 l删除结点删除结点 l遍历链表遍历链表 l清空链表清空链表 顺序访问的线性群体 c+语言程序设计 36 链表类模板链

24、表类模板(例例9-6) /9_6.h #ifndef linkedlist_class #define linkedlist_class #include #include using namespace std; #ifndef null const int null = 0; #endif / null #include 9_5.h 顺序访问的线性群体 template class linkedlist private: node *front, *rear; node *prevptr, *currptr; int size; int position; node *getnode(co

25、nst t void freenode(node *p); void copylist(const linkedlist 37 public: linkedlist(void); linkedlist(const linkedlist linkedlist(void); linkedlist int listsize(void) const; int listempty(void) const; void reset(int pos = 0); void next(void); int endoflist(void) const; int currentposition(void) const

26、; 38 void insertfront(const t void insertrear(const t void insertat(const t void insertafter(const t t deletefront(void); void deleteat(void); t void clearlist(void); ; #endif / linkedlist_class 39 c+语言程序设计 40 链表类应用举例链表类应用举例(例例9-7) #include using namespace std; #include 9_6.h #include 9_6.cpp int ma

27、in() linkedlist link; int i, key, item; for (i=0;i item; link.insertfront(item); 顺序访问的线性群体 cout list: ; link.reset(); while(!link.endoflist() cout link.data() ; link.next(); cout endl; cout key; link.reset(); 41 while (!link.endoflist() if(link.data() = key) link.deleteat(); link.next(); cout list:

28、; link.reset(); while(!link.endoflist() cout link.data() ; link.next(); cout endl; 42 c+语言程序设计 43 特殊的线性群体特殊的线性群体栈栈 栈是只能从一端访问的线性群体，栈是只能从一端访问的线性群体， 可以访问的这一端称栈顶，另一端称栈可以访问的这一端称栈顶，另一端称栈 底。底。 an a2 a1 入栈出栈 栈顶 栈底 特殊的线性群体栈 c+语言程序设计 44 栈的应用举例栈的应用举例函数调用函数调用 特殊的线性群体栈 main 调fun(参数) 结束 fun(参数) 返回 参数 当前现场 返回地址 入栈

29、 当前现场 返回地址 出栈 参数 出栈 当前现场 返回地址 c+语言程序设计 45 栈的应用举例栈的应用举例表达式处理表达式处理 b a / a/b+c*d (a) t1+ a/b+c*d t1=a/b (b) d c t1 * + a/b+c*d (c) t3 a/b+c*d t3=t1+t2 (e) t2 t1 + a/b+c*d t2=c*d (d) 特殊的线性群体栈 c+语言程序设计 46 栈的基本状态栈的基本状态 l栈空栈空 栈中没有元素 l栈满栈满 栈中元素个数达到上限 l一般状态一般状态 栈中有元素，但未达到栈满状态 特殊的线性群体栈 栈顶 an a1 a0 入栈出栈 数组下标

30、max n 1 0 一般状态 栈顶 入栈出栈 数组下标 初始状态（栈空） max n 1 0 栈顶 amax an a1 a0 入栈出栈 数组下标 max n 1 0 栈满状态 47 c+语言程序设计 48 栈的基本操作栈的基本操作 l初始化初始化 l入栈入栈 l出栈出栈 l清空栈清空栈 l访问栈顶元素访问栈顶元素 l检测栈的状态（满、空）检测栈的状态（满、空） 特殊的线性群体栈 c+语言程序设计 49 栈类模板栈类模板(例例9-8) 特殊的线性群体栈 /9-8.h #ifndef stack_class #define stack_class #include #include using

31、namespace std; const int maxstacksize = 50; template class stack private: t stacklistmaxstacksize; int top; public: stack (void); void push (const t t pop (void); void clearstack(void); t peek (void) const; int stackempty(void) const; int stackfull(void) const; ; /类的实现略类的实现略 c+语言程序设计 50 栈的应用栈的应用 l例例

32、9.9 一个简单的整数计算器一个简单的整数计算器 实现一个简单的整数计算器，能够进 行加、减、乘、除和乘方运算。使用时算 式采用后缀输入法，每个操作数、操作符 之间都以空白符分隔。例如，若要计算 3+5则输入3 5 +。乘方运算符用表 示。每次运算在前次结果基础上进行，若 要将前次运算结果清除，可键入c。当键 入q时程序结束。 l9-9.h 9-9.cpp 特殊的线性群体栈 /9_9.h #include #include #include #include using namespace std; enum boolean false, true; #include 9_8.h class

33、calculator private: stack s; void enter(int num); boolean gettwooperands(int void compute(char op); public: void run(void); void clear(void); ; 51 void calculator:enter(int num) s.push(num); boolean calculator:gettwooperands(int return false; opnd1 = s.pop(); if (s.stackempty() cerr missing operand!

34、 endl; return false; opnd2 = s.pop(); return true; 52 void calculator:compute(char op) boolean result; int operand1, operand2; result = gettwooperands(operand1, operand2); if (result) switch(op) case +: s.push(operand2+operand1); break; case -: s.push(operand2-operand1); break; case *: s.push(operan

35、d2*operand1); break; case /: if (operand1 = 0) cerr divide by 0! endl; s.clearstack(); else s.push(operand2/operand1); break; case : s.push(pow(operand2,operand1); break; cout=s.peek() c, *c != q) switch(*c) case c: s.clearstack(); break; case -: if (strlen(c)1) enter(atoi(c); else compute(*c); brea

36、k; case +: case *: case /: case : compute(*c); break; default: enter(atoi(c); break; 54 void calculator:clear(void) s.clearstack(); /9_9.cpp #include 9-9.h int main() calculator calc; calc.run(); 55 c+语言程序设计 56 特殊的线性群体特殊的线性群体队列队列 队列是只能向一端添加元素，从另队列是只能向一端添加元素，从另 一端删除元素的线性群体一端删除元素的线性群体 a1 a2an-1 an 队头队

37、尾 入队出队a0 c+语言程序设计 57 队列的基本状态队列的基本状态 l队空队空 队列中没有元素 l队满队满 队列中元素个数达到上限 l一般状态一般状态 队列中有元素，但未达到队满状态 特殊的线性群体队列 a0 a1an-1 an 队头队尾 入队出队 数组下标 0 1 n-1 n max (一般状态) 队头队尾 入队出队 数组下标 0 1 n-1 n max (队空状态) a0 a1 an-1 an amax 队头队尾 入队出队 数组下标 0 1 n-1 n max (队满状态) 元素移动方向 元素移动方向 58 c+语言程序设计 59 循环队列循环队列 在想象中将数组弯曲成环形，元素在想象

38、中将数组弯曲成环形，元素 出队时，后继元素不移动，每当队尾达出队时，后继元素不移动，每当队尾达 到数组最后一个元素时，便再回到数组到数组最后一个元素时，便再回到数组 开头。开头。 特殊的线性群体队列 1 2 3 4 m-1 m-2 m-3 0 amam+1 am+2 a3 队头 队尾 a4 am-2 am-3 am-1 队满状态 元素个数=m 1 2 3 4 m-1 m-2 m-3 0 队尾 队头 队空状态 元素个数=0 队尾 1 2 3 4 m-1 m-2 m-3 0 a0a1 a2 a3 队头 一般状态 60 c+语言程序设计 61 例例9-10 队列类模板队列类模板 特殊的线性群体队列

39、#ifndef queue_class #define queue_class #include #include using namespace std; const int maxqsize = 50; template class queue private: int front, rear, count; t qlistmaxqsize; public: queue (void); void qinsert(const t t qdelete(void); void clearqueue(void); t qfront(void) const; int qlength(void) co

40、nst; int qempty(void) const; int qfull(void) const; ; /成员函数的实现略成员函数的实现略 c+语言程序设计 62 第三部分第三部分群体数据的组织群体数据的组织 l插入排序插入排序 l选择排序选择排序 l交换排序交换排序 l顺序查找顺序查找 l折半查找折半查找 c+语言程序设计 63 排序（排序（sorting） l排序排序是计算机程序设计中的一种重要操作，是计算机程序设计中的一种重要操作， 它的功能是将一个它的功能是将一个数据元素数据元素的任意序列，重的任意序列，重 新排列成一个按新排列成一个按关键字关键字有序的序列。有序的序列。 数据元素

41、：数据的基本单位。在计算机中通常作 为一个整体进行考虑。一个数据元素可由若干数 据项组成。 关键字：数据元素中某个数据项的值，用它可以 标识（识别）一个数据元素。 l在排序过程中需要完成两种基本操作：在排序过程中需要完成两种基本操作： 比较两个数的大小 调整元素在序列中的位置 群体数据的组织 c+语言程序设计 64 内部排序与外部排序内部排序与外部排序 l内部排序：内部排序：待排序的数据元素存放在待排序的数据元素存放在 计算机内存中进行的排序过程。计算机内存中进行的排序过程。 l外部排序：外部排序：待排序的数据元素数量很待排序的数据元素数量很 大，以致内存存中一次不能容纳全部大，以致内存存中一

42、次不能容纳全部 数据，在排序过程中尚需对外存进行数据，在排序过程中尚需对外存进行 访问的排序过程。访问的排序过程。 群体数据的组织 c+语言程序设计 65 内部排序方法内部排序方法 l插入排序插入排序 l选择排序选择排序 l交换排序交换排序 群体数据的组织 c+语言程序设计 66 插入排序的基本思想插入排序的基本思想 l每一步将一个待排序元素按其关键字值的大小插入到已排每一步将一个待排序元素按其关键字值的大小插入到已排 序序列的适当位置上，直到待排序元素插入完为止。序序列的适当位置上，直到待排序元素插入完为止。 初始状态：初始状态： 5 4 10 20 12 35 4 10 20 12 3 插

43、入操作：插入操作：1 1 44 4 5 10 20 12 3 4 5 10 20 12 3 2 2 1010 4 5 10 20 12 3 4 5 10 20 12 3 3 3 2020 4 5 10 20 12 3 4 5 10 20 12 3 4 4 1212 4 5 10 12 20 3 4 5 10 12 20 3 5 5 33 3 4 5 10 12 20 3 4 5 10 12 20 c+语言程序设计 67 直接插入排序直接插入排序 l在插入排序过程中，由于寻找插入位置的在插入排序过程中，由于寻找插入位置的 方法不同又可以分为不同的插入排序算法，方法不同又可以分为不同的插入排序算法

44、， 这里我们只介绍最简单的直接插入排序算这里我们只介绍最简单的直接插入排序算 法。法。 l例例9-11 直接插入排序函数模板（直接插入排序函数模板（9_11.h） 群体数据的组织 template void insertionsort(t a, int n) int i, j; t temp; for (i = 1; i 0 j-; aj = temp; 直接插入排序函数模板（9_11.h） 68 c+语言程序设计 69 选择排序的基本思想选择排序的基本思想 每次从待排序序列中选择一个关键字最小的元素，每次从待排序序列中选择一个关键字最小的元素， （当需要按关键字升序排列时），顺序排在已排序序

45、列的（当需要按关键字升序排列时），顺序排在已排序序列的 最后，直至全部排完。最后，直至全部排完。 5 4 10 20 12 5 4 10 20 12 3 3 初始状态：初始状态： 3 3 4 4 10 20 12 5 10 20 12 5 3 4 10 20 12 3 4 10 20 12 5 5 第 i i 次选择后，将选出的那个记录与第 i i 个记录做交换交换。 3 4 5 20 12 3 4 5 20 12 1010 . . c+语言程序设计 70 直接选择排序直接选择排序 l在选择类排序方法中，从待排序序列在选择类排序方法中，从待排序序列 中选择元素的方法不同，又分为不同中选择元素的

46、方法不同，又分为不同 的选择排序方法，其中最简单的是通的选择排序方法，其中最简单的是通 过顺序比较找出待排序序列中的最小过顺序比较找出待排序序列中的最小 元素，称为直接选择排序。元素，称为直接选择排序。 l例例9-12 直接选择排序函数模板（直接选择排序函数模板（9- 12.h） 群体数据的组织 template void swap (t temp = x; x = y; y = temp; template void selectionsort(t a, int n) int smallindex; int i, j; for (i = 0; i n-1; i+) smallindex =

47、i; for (j = i+1; j n; j+) if (aj asmallindex) smallindex = j; swap(ai, asmallindex); 直接选择排序函数模板（9-12.h） 71 c+语言程序设计 72 交换排序的基本思想交换排序的基本思想 两两比较待排序序列中的元素，并两两比较待排序序列中的元素，并 交换不满足顺序要求的各对元素，直到交换不满足顺序要求的各对元素，直到 全部满足顺序要求为止。全部满足顺序要求为止。 群体数据的组织 c+语言程序设计 73 最简单的交换排序方法最简单的交换排序方法 起泡排序起泡排序 对具有对具有n个元素的序列按升序进行起泡排序的

48、个元素的序列按升序进行起泡排序的 步骤：步骤： 首先将第一个元素与第二个元素进行比较，若为逆 序，则将两元素交换。然后比较第二、第三个元素， 依次类推，直到第n-1和第n个元素进行了比较和交 换。此过程称为第一趟起泡排序。经过第一趟，最 大的元素便被交换到第n个位置。 对前n-1个元素进行第二趟起泡排序，将其中最大元 素交换到第n-1个位置。 如此继续，直到某一趟排序未发生任何交换时，排 序完毕。对n个元素的序列，起泡排序最多需要进 行n-1趟。 群体数据的组织 c+语言程序设计 74 起泡排序举例起泡排序举例 对整数序列对整数序列 8 5 2 4 3 按升序排序按升序排序 8 5 2 4 3

49、 5 2 4 3 8 2 4 3 5 8 2 3 4 5 8 2 3 4 5 8 初 始 状 态 第 一 趟 结 果 第 二 趟 结 果 第 三 趟 结 果 第 四 趟 结 果 小 的 逐 渐 上 升 每 趟 沉 下 一 个 最 大 的 群体数据的组织 c+语言程序设计 75 例例9-13 起泡排序函数模板起泡排序函数模板 template void swap (t temp = x; x = y; y = temp; template void bubblesort(t a, int n) int i,j; int lastexchangeindex; i = n-1; while (i 0

50、) lastexchangeindex = 0; for (j = 0; j i; j+) if (aj+1 aj) swap(aj,aj+1); lastexchangeindex = j; i = lastexchangeindex; 群体数据的组织 c+语言程序设计 76 顺序查找顺序查找 l其基本思想其基本思想 从序列的首元素开始，逐个元素与待查 找的关键字进行比较，直到找到相等的。 若整个序列中没有与待查找关键字相等 的元素，就是查找不成功。 l顺序查找函数模板顺序查找函数模板 例9-14 群体数据的组织 template int seqsearch(t list, int n, t

51、 key) for(int i=0;i n;i+) if (listi = key) return i; return -1; 顺序查找函数模板 77 c+语言程序设计 78 折半查找的基本思想折半查找的基本思想 对于已按关键字排序的序列，经过 一次比较，可将序列分割成两部分，然 后只在有可能包含待查元素的一部分中 继续查找，并根据试探结果继续分割， 逐步缩小查找范围，直至找到或找不到 为止。 群体数据的组织 c+语言程序设计 79 折半查找举例折半查找举例 用折半查找法，在下列序列中查找值为用折半查找法，在下列序列中查找值为2121的元素：的元素： l=1 51319213756647580

52、8892 h=11m =int(l+h)/2)=6 513192137 l=1h=m-1=5m=int(l+h)/2)=3m 2137 h l=m+1=4 l m=int(l+h)/2)=4 m c+语言程序设计 80 例例10-5 折半查找函数模板折半查找函数模板 template int binsearch(t list, int n, t key) int mid, low, high; t midvalue; low=0; high=n-1; while (low = high) mid = (low+high)/2; midvalue = listmid; if (key = mid

53、value) return mid; else if (key ，=，=，= l方法（函数）方法（函数） 迭代方法 lbegin()，end()，rbegin()，rend() 访问方法 lsize()，max_size()，swap()，empty() c+语言程序设计 88 适配器适配器 l适配器是一种接口类适配器是一种接口类 为已有的类提供新的接口。 目的是简化、约束、使之安全、隐藏或 者改变被修改类提供的服务集合。 l三种类型的适配器：三种类型的适配器： 容器适配器 l用来扩展7种基本容器，它们和顺序容器相结 合构成栈、队列和优先队列容器 迭代器适配器 函数对象适配器。 概念和术语 c

54、+语言程序设计 89 迭代器迭代器 迭代器是面向对象版本的指针，它迭代器是面向对象版本的指针，它 们提供了访问容器、序列中每个元素的们提供了访问容器、序列中每个元素的 方法。方法。 概念和术语 c+语言程序设计 90 算法算法 lc+标准模板库中包括标准模板库中包括70多个算法多个算法 其中包括查找算法，排序算法，消除算 法，记数算法，比较算法，变换算法， 置换算法和容器管理等等。 l这些算法的一个最重要的特性就是它这些算法的一个最重要的特性就是它 们的统一性，并且可以广泛用于不同们的统一性，并且可以广泛用于不同 的对象和内置的数据类型。的对象和内置的数据类型。 概念和术语 c+语言程序设计

55、91 顺序容器顺序容器 l顺序容器的接口顺序容器的接口 插入方法 lpush_front()，push_back()，insert()，运算符“=” 删除方法 lpop() ，erase()，clear() 迭代访问方法 l使用迭代器 其它顺序容器访问方法（不修改访问方法） lfront()，back()，下标运算符 容 器 c+语言程序设计 92 顺序容器顺序容器向量向量 l向量属于顺序容器，用于容纳不定长向量属于顺序容器，用于容纳不定长 线性序列（即线性群体），提供对序线性序列（即线性群体），提供对序 列的快速随机访问（也称直接访问）列的快速随机访问（也称直接访问） l向量是动态结构，它的

56、大小不固定，向量是动态结构，它的大小不固定， 可以在程序运行时增加或减少。可以在程序运行时增加或减少。 l例例10-1 求范围2n中的质数，n在程序运行时由 键盘输入。 容 器 c+语言程序设计 93 /10_1.cpp/10_1.cpp #include iostream#include #include iomanip#include #include #include /包含向量容器头文件包含向量容器头文件 using namespace std ;using namespace std ; intint main() main() vectorint vector a(10); a(1

57、0); int int n; n; int primecount int primecount = 0, i, j; = 0, i, j; cout cout=2 as upper limit: ;=2 as upper limit: ; cin cin n; n; aprimecount aprimecount+ = 2;+ = 2; 93 c+语言程序设计 94 for(ifor(i = 3; i n; i+) = 3; i n; i+) if (primecount = a.size if (primecount = a.size()() a.resize(primecount a.re

58、size(primecount + 10); + 10); if (i % 2 = 0) if (i % 2 = 0) continue; continue; j = 3; j = 3; while (j = i/2 + = i; for (i = 0; iprimecount for (i = 0; iprimecount; i+)/; i+)/输出质数输出质数 coutsetw(5)ai coutsetw(5)ai; ; if (i+1) % 10 = 0) / if (i+1) % 10 = 0) /每输出每输出1010个数换行一次个数换行一次 cout endlcout endl; ;

59、 coutendl coutendl; ; 94 c+语言程序设计 95 顺序容器顺序容器双端队列双端队列 l双端队列是一种放松了访问权限的队双端队列是一种放松了访问权限的队 列。元素可以从队列的两端入队和出列。元素可以从队列的两端入队和出 队，也支持通过下标操作符队，也支持通过下标操作符“”进行进行 直接访问。直接访问。 l例例10-2 使用双端队列容器保存双精度数值序列 容 器 c+语言程序设计 96 顺序容器顺序容器列表列表 l列表主要用于存放双向链表，可以从任意列表主要用于存放双向链表，可以从任意 一端开始遍历。列表还提供了拼接一端开始遍历。列表还提供了拼接 （splicing）操作，

60、将一个序列中的元素从）操作，将一个序列中的元素从 插入到另一个序列中。插入到另一个序列中。 l例例10-3 改写例改写例9-7 从键盘输入10个整数，用这些整数值作为结点 数据，生成一个链表，按顺序输出链表中结点 的数值。然后从键盘输入一个待查找整数，在 链表中查找该整数，若找到则删除该整数所在 的结点（如果出现多次，全部删除），然后输 出删除结点以后的链表。在程序结束之前清空 链表。 容 器 c+语言程序设计 97 /10_3.cpp/10_3.cpp #include iostream#include #include #include using namespace std ;using