chap9-C++课件-清华大学郑莉.ppt

《chap9-C++课件-清华大学郑莉.ppt》由会员分享，可在线阅读，更多相关《chap9-C++课件-清华大学郑莉.ppt（81页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、space std;templateT abs(T x) return x0?-x:x; int main() int n=-5; double d=-5.5; coutabs(n)endl; coutabs(d)endl; 函 数 模 板运行结果：运行结果：55.5C+语言程序设计清华大学 郑莉6求绝对值函数的模板分析求绝对值函数的模板分析l编译器从调用编译器从调用abs()时实参的类型，推时实参的类型，推导出函数模板的类型参数。例如，对导出函数模板的类型参数。例如，对于调用表达式于调用表达式abs(n)，由于实参，由于实参n为为int型，所以推导出模板中类型参数型，所以推导出模板中类型参数

3、T为为int。l当类型参数的含义确定后，编译器将当类型参数的含义确定后，编译器将以函数模板为样板，生成一个函数：以函数模板为样板，生成一个函数：int abs(int x) return x0?-x:x; 函 数 模 板C+语言程序设计清华大学 郑莉7类模板的作用类模板的作用使用类模板使用户可以为类声明一使用类模板使用户可以为类声明一种模式，使得类中的某些数据成员、种模式，使得类中的某些数据成员、某些成员函数的参数、某些成员函数某些成员函数的参数、某些成员函数的返回值，能取任意类型（包括基本的返回值，能取任意类型（包括基本类型的和用户自定义类型）。类型的和用户自定义类型）。类 模 板C+语言程

4、序设计清华大学 郑莉8类模板的声明类模板的声明l类模板：类模板：template class 类名类成员声明l如果需要在类模板以外定义其成员如果需要在类模板以外定义其成员函数，则要采用以下的形式：函数，则要采用以下的形式：template 类型名 类名:函数名（参数表）类 模 板C+语言程序设计清华大学 郑莉9例例9-2 类模板应用举例类模板应用举例#include #include using namespace std;/ 结构体结构体Studentstruct Student int id; /学号学号 float gpa; /平均分平均分; 类 模 板template /类模板：实现对

5、任意类型数据进行存取类模板：实现对任意类型数据进行存取class Store private: T item; / 用于存放任意类型的数据用于存放任意类型的数据 int haveValue; / 用于标记用于标记item是否已被存入内容是否已被存入内容 public: Store(void); / 默认形式（无形参）的构造函数默认形式（无形参）的构造函数 T GetElem(void); /提取数据函数提取数据函数 void PutElem(T x); /存入数据函数存入数据函数;/ 默认形式构造函数的实现默认形式构造函数的实现template Store:Store(void): haveV

6、alue(0) 10template / 提取数据函数的实现提取数据函数的实现T Store:GetElem(void) / 如果试图提取未初始化的数据，则终止程序如果试图提取未初始化的数据，则终止程序 if (haveValue = 0) cout No item present! endl; exit(1); return item; / 返回返回item中存放的数据中存放的数据 template / 存入数据函数的实现存入数据函数的实现 void Store:PutElem(T x) haveValue+; / 将将haveValue 置为置为 TRUE，表示，表示item中已存入数值中

7、已存入数值 item = x; / 将将x值存入值存入item11int 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 object D ;cout D.GetElem() endl; /输出对象输出对象D的数据成员的数据成员/ 由于由

8、于D未经初始化未经初始化,在执行函数在执行函数D.GetElement()时出错时出错12C+语言程序设计清华大学 郑莉13第二部分第二部分群体数据群体数据l线性群体线性群体 线性群体的概念 直接访问群体-数组类 顺序访问群体-链表类 栈类 队列类C+语言程序设计清华大学 郑莉14群体的概念群体的概念群体群体是指由多个数据元素组成的集是指由多个数据元素组成的集合体。群体可以分为两个大类：合体。群体可以分为两个大类：线性群线性群体体和和非线性群体非线性群体。线性群体中的元素按位置排列有序，线性群体中的元素按位置排列有序，可以区分为第一个元素、第二个元素等。可以区分为第一个元素、第二个元素等。非线

9、性群体不用位置顺序来标识元非线性群体不用位置顺序来标识元素。素。C+语言程序设计清华大学 郑莉15线性群体的概念线性群体的概念线性群体中的元素次序与其位置关线性群体中的元素次序与其位置关系是对应的。在线性群体中，又可按照系是对应的。在线性群体中，又可按照访问元素的不同方法分为访问元素的不同方法分为直接访问直接访问、顺顺序访问序访问和和索引访问索引访问。在本章我们只介绍直接访问和顺序在本章我们只介绍直接访问和顺序访问。访问。第一个元素第二个元素第三个元素最后一个元素C+语言程序设计清华大学 郑莉16数组数组l静态数组是具有固定元素个数的群体，其静态数组是具有固定元素个数的群体，其中的元素可以通过

10、下标直接访问。中的元素可以通过下标直接访问。 缺点：大小在编译时就已经确定，在运行时无法修改。l动态数组由一系列位置连续的，任意数量动态数组由一系列位置连续的，任意数量相同类型的元素组成。相同类型的元素组成。 优点：其元素个数可在程序运行时改变。l动态数组类模板：例动态数组类模板：例9-3（9_3.h）直接访问的线性群体#ifndef ARRAY_CLASS#define ARRAY_CLASSusing namespace std;#include #include #ifndef NULLconst int NULL = 0;#endif / NULLenum ErrorType inva

11、lidArraySize, memoryAllocationError, indexOutOfRange ;char *errorMsg = Invalid array size, Memory allocation error, Invalid index: ;动态数组类模板程序17template class Array private: T* alist; int size; void Error(ErrorType error,int badIndex=0) const; public: Array(int sz = 50); Array(const Array& A); Array(

12、void); Array& operator= (const Array& rhs); T& operator(int i); operator T* (void) const; int ListSize(void) const; void Resize(int sz); ;18C+语言程序设计清华大学 郑莉19数组类模板的构造函数数组类模板的构造函数/ 构造函数构造函数template Array:Array(int sz) if (sz = 0) /sz为数组大小（元素个数），若小于为数组大小（元素个数），若小于0，则输出错误信息，则输出错误信息 Error(invalidArraySiz

13、e); size = sz; / 将元素个数赋值给变量将元素个数赋值给变量size alist = new Tsize; /动态分配动态分配size个个T类型的元素空间类型的元素空间 if (alist = NULL) /如果分配内存不成功，输出错误信息如果分配内存不成功，输出错误信息 Error(memoryAllocationError);直接访问的线性群体C+语言程序设计清华大学 郑莉20数组类的拷贝构造函数数组类的拷贝构造函数template Array:Array(const Array& X) int n = X.size; size = n; alist = new Tn; if

14、 (alist = NULL) Error(memoryAllocationError); T* srcptr = X.alist; / X.alist是对象是对象X的数组首地址的数组首地址 T* destptr = alist; / alist是本对象中的数组首地址是本对象中的数组首地址 while (n-) / 逐个复制数组元素逐个复制数组元素 *destptr+ = *srcptr+;直接访问的线性群体C+语言程序设计清华大学 郑莉21浅拷贝浅拷贝 alist sizeAA的数组元素占用的内存拷贝前 alist sizeAA的数组元素占用的内存拷贝后 alist sizeBint mai

15、n() Array A(10); . Array B(A); .template Array:Array( const Array& X) size = X.size; alist= X.alist;C+语言程序设计清华大学 郑莉22深拷贝深拷贝 alist sizeAA的数组元素占用的内存拷贝前 alist sizeAA的数组元素占用的内存拷贝后 alist sizeBB的数组元素占用的内存C+语言程序设计清华大学 郑莉23数组类的重载数组类的重载=运算符函数运算符函数template Array& Array:operator= (const Array& rhs) int n = rhs

16、.size; if (size != n) delete alist; alist = new Tn; if (alist = NULL) Error(memoryAllocationError); size = n; T* destptr = alist; T* srcptr = rhs.alist; while (n-) *destptr+ = *srcptr+; return *this;直接访问的线性群体C+语言程序设计清华大学 郑莉24数组类的重载下标操作符函数数组类的重载下标操作符函数template T& Array:operator (int n) / 检查下标是否越界检查下标

17、是否越界 if (n size-1) Error(indexOutOfRange,n); / 返回下标为返回下标为n的数组元素的数组元素 return alistn;直接访问的线性群体C+语言程序设计清华大学 郑莉25为什么有的函数返回引用为什么有的函数返回引用l如果一个函数的返回值是一个对象的如果一个函数的返回值是一个对象的值，它就被认为是一个常量，不能成值，它就被认为是一个常量，不能成为左值。为左值。l如果返回值为引用。由于引用是对象如果返回值为引用。由于引用是对象的别名，所以通过引用当然可以改变的别名，所以通过引用当然可以改变对象的值。对象的值。直接访问的线性群体C+语言程序设计清华大学

18、 郑莉26重载指针转换操作符重载指针转换操作符template Array:operator T* (void) const / 返回当前对象中私有数组的首地址返回当前对象中私有数组的首地址 return alist;直接访问的线性群体C+语言程序设计清华大学 郑莉27指针转换运算符的作用指针转换运算符的作用#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() Arra

19、y a(10); void read(int *p, n); read(a, 10);void read(int *p, int n) for (int i=0; ipi;直接访问的线性群体C+语言程序设计清华大学 郑莉28Array类的应用类的应用l例例9-4求范围求范围2N中的质数，中的质数，N在程序在程序运行时由键盘输入。运行时由键盘输入。直接访问的线性群体#include #include #include 9_3.husing namespace std;int main() Array A(10); int n; int primecount = 0, i, j; cout = 2

20、 as upper limit for prime numbers: ; cin n; Aprimecount+ = 2; / 2是一个质数是一个质数 for(i = 3; i n; i+) if (primecount = A.ListSize() A.Resize(primecount + 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 e

21、ndl;29C+语言程序设计清华大学 郑莉30链表链表l链表是一种动态数据结构，可以用来链表是一种动态数据结构，可以用来表示顺序访问的线性群体。表示顺序访问的线性群体。l链表是由系列链表是由系列结点结点组成的，结点可以组成的，结点可以在运行时动态生成。在运行时动态生成。l每一个结点包括每一个结点包括数据域数据域和指向链表中和指向链表中下一个结点的下一个结点的指针指针（即下一个结点的（即下一个结点的地址）。如果链表每个结点中只有一地址）。如果链表每个结点中只有一个指向后继结点的指针，则该链表称个指向后继结点的指针，则该链表称为单链表。为单链表。顺序访问的线性群体C+语言程序设计清华大学 郑莉31

22、单链表单链表 data1 data2 data3 datan NULLheadrear顺序访问的线性群体C+语言程序设计清华大学 郑莉32单链表的结点类模板单链表的结点类模板template class Node private: Node *next; public: T data; Node(const T& item,Node* ptrnext = NULL); void InsertAfter(Node *p); Node *DeleteAfter(void); Node *NextNode(void) const; 顺序访问的线性群体C+语言程序设计清华大学 郑莉33在结点之后插入一

23、个结点在结点之后插入一个结点 data1 data2 p datatemplate void Node:InsertAfter(Node *p) /p节点指针域指向当前节点的后继节点节点指针域指向当前节点的后继节点 p-next = next; next = p; /当前节点的指针域指向当前节点的指针域指向p 顺序访问的线性群体C+语言程序设计清华大学 郑莉34 删除结点之后的结点删除结点之后的结点顺序访问的线性群体 data1 data2 data3Node *Node:DeleteAfter(void) Node *tempPtr = next; if (next = NULL) retu

24、rn NULL; next = tempPtr-next; return tempPtr; tempPtrC+语言程序设计清华大学 郑莉35链表的基本操作链表的基本操作l生成结点生成结点l插入结点插入结点l查找结点查找结点l删除结点删除结点l遍历链表遍历链表l清空链表清空链表顺序访问的线性群体C+语言程序设计清华大学 郑莉36链表类模板链表类模板(例例9-6)/9_6.h#ifndef LINKEDLIST_CLASS#define LINKEDLIST_CLASS#include #include using namespace std;#ifndef NULLconst int NULL

25、= 0;#endif / NULL#include 9_5.h顺序访问的线性群体template class LinkedList private: Node *front, *rear; Node *prevPtr, *currPtr; int size; int position; Node *GetNode(const T& item, Node *ptrNext=NULL); void FreeNode(Node *p); void CopyList(const LinkedList& L);37 public: LinkedList(void); LinkedList(const L

26、inkedList& L); LinkedList(void); LinkedList& operator= (const LinkedList& L); int ListSize(void) const; int ListEmpty(void) const; void Reset(int pos = 0); void Next(void); int EndOfList(void) const; int CurrentPosition(void) const; 38 void InsertFront(const T& item); void InsertRear(const T& item);

27、 void InsertAt(const T& item); void InsertAfter(const T& item); T DeleteFront(void); void DeleteAt(void); T& Data(void); void ClearList(void);#endif / LINKEDLIST_CLASS39C+语言程序设计清华大学 郑莉40链表类应用举例链表类应用举例(例例9-7)#include using namespace std;#include 9_6.h#include 9_6.cppint main() LinkedList Link; int i,

28、 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: ; Link.Reset(); while(!Link.En

29、dOfList() cout Link.Data() ; Link.Next(); cout endl;42C+语言程序设计清华大学 郑莉43特殊的线性群体特殊的线性群体栈栈栈是只能从一端访问的线性群体，栈是只能从一端访问的线性群体，可以访问的这一端称栈顶，另一端称栈可以访问的这一端称栈顶，另一端称栈底。底。ana2a1入栈出栈栈顶栈底特殊的线性群体栈C+语言程序设计清华大学 郑莉44栈的应用举例栈的应用举例函数调用函数调用特殊的线性群体栈main调fun(参数)结束fun(参数)返回参数当前现场返回地址入栈当前现场返回地址出栈参数出栈当前现场 返回地址C+语言程序设计清华大学 郑莉45栈的应

30、用举例栈的应用举例表达式处理表达式处理ba/a/b+c*d(a)t1+a/b+c*dt1=a/b(b)dct1*+a/b+c*d(c)t3a/b+c*dt3=t1+t2(e)t2t1+a/b+c*dt2=c*d(d)特殊的线性群体栈C+语言程序设计清华大学 郑莉46栈的基本状态栈的基本状态l栈空栈空 栈中没有元素l栈满栈满 栈中元素个数达到上限l一般状态一般状态 栈中有元素，但未达到栈满状态特殊的线性群体栈栈顶ana1a0入栈出栈数组下标maxn10一般状态栈顶入栈出栈数组下标初始状态（栈空）maxn10栈顶amaxana1a0入栈出栈数组下标maxn10栈满状态47C+语言程序设计清华大学

31、郑莉48栈的基本操作栈的基本操作l初始化初始化l入栈入栈l出栈出栈l清空栈清空栈l访问栈顶元素访问栈顶元素l检测栈的状态（满、空）检测栈的状态（满、空）特殊的线性群体栈C+语言程序设计清华大学 郑莉49栈类模板栈类模板(例例9-8)特殊的线性群体栈/9-8.h#ifndef STACK_CLASS#define STACK_CLASS#include #include using namespace std;const int MaxStackSize = 50; template class Stack private: T stacklistMaxStackSize; int top; p

32、ublic: Stack (void); void Push (const T& item); T Pop (void); void ClearStack(void); T Peek (void) const; int StackEmpty(void) const; int StackFull(void) const;/类的实现略类的实现略C+语言程序设计清华大学 郑莉50栈的应用栈的应用l例例9.9 一个简单的整数计算器一个简单的整数计算器实现一个简单的整数计算器，能够进行加、减、乘、除和乘方运算。使用时算式采用后缀输入法，每个操作数、操作符之间都以空白符分隔。例如，若要计算3+5则输入3

33、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 Calculator private: Stack S; void Enter(int num); Boolean GetTwoOperands(int& opnd1, int& opnd2); void Compute(char

34、 op); public: void Run(void); void Clear(void); ;51void Calculator:Enter(int num) S.Push(num); Boolean Calculator:GetTwoOperands(int& opnd1, int& opnd2) if (S.StackEmpty() cerr Missing operand! endl; return False; opnd1 = S.Pop(); if (S.StackEmpty() cerr Missing operand! endl; return False; opnd2 =

35、S.Pop(); return True;52void 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(operand2*operand1); break; case /: if

36、(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); break; case +: case *: case /: case

37、: Compute(*c); break; default: Enter(atoi(c); break; 54void Calculator:Clear(void) S.ClearStack(); /9_9.cpp#include 9-9.hint main() Calculator CALC; CALC.Run();55C+语言程序设计清华大学 郑莉56特殊的线性群体特殊的线性群体队列队列队列是只能向一端添加元素，从另队列是只能向一端添加元素，从另一端删除元素的线性群体一端删除元素的线性群体a1 a2an-1 an队头队尾入队出队a0C+语言程序设计清华大学 郑莉57队列的基本状态队列的基本

38、状态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(队满状态)元素移动方向元素移动方向58C+语言程序设计清华大学 郑莉59循环队列循环队列在想象中将数组弯曲成环形，元素在想象中将数组弯曲成环形，元素出队时，后继元素不移动，每当队尾达出队时，后继元素不移动，每当队尾达到数组最

39、后一个元素时，便再回到数组到数组最后一个元素时，便再回到数组开头。开头。特殊的线性群体队列1234m-1m-2m-30amam+1am+2a3队头队尾a4am-2am-3am-1队满状态 元素个数=m1234m-1m-2m-30队尾队头队空状态 元素个数=0队尾1234m-1m-2m-30a0a1a2a3队头一般状态60C+语言程序设计清华大学 郑莉61例例9-10 队列类模板队列类模板特殊的线性群体队列#ifndef QUEUE_CLASS#define QUEUE_CLASS#include #include using namespace std;const int MaxQSize =

40、 50; template class Queue private: int front, rear, count; T qlistMaxQSize; public: Queue (void); void QInsert(const T& item); T QDelete(void); void ClearQueue(void); T QFront(void) const; int QLength(void) const; int QEmpty(void) const; int QFull(void) const; ;/成员函数的实现略成员函数的实现略C+语言程序设计清华大学 郑莉62第三部分

41、第三部分群体数据的组织群体数据的组织l插入排序插入排序l选择排序选择排序l交换排序交换排序l顺序查找顺序查找l折半查找折半查找C+语言程序设计清华大学 郑莉63排序（排序（sorting）l排序排序是计算机程序设计中的一种重要操作，是计算机程序设计中的一种重要操作，它的功能是将一个它的功能是将一个数据元素数据元素的任意序列，重的任意序列，重新排列成一个按新排列成一个按关键字关键字有序的序列。有序的序列。 数据元素：数据的基本单位。在计算机中通常作为一个整体进行考虑。一个数据元素可由若干数据项组成。 关键字：数据元素中某个数据项的值，用它可以标识（识别）一个数据元素。l在排序过程中需要完成两种基

42、本操作：在排序过程中需要完成两种基本操作： 比较两个数的大小 调整元素在序列中的位置群体数据的组织C+语言程序设计清华大学 郑莉64内部排序与外部排序内部排序与外部排序l内部排序：内部排序：待排序的数据元素存放在待排序的数据元素存放在计算机内存中进行的排序过程。计算机内存中进行的排序过程。l外部排序：外部排序：待排序的数据元素数量很待排序的数据元素数量很大，以致内存存中一次不能容纳全部大，以致内存存中一次不能容纳全部数据，在排序过程中尚需对外存进行数据，在排序过程中尚需对外存进行访问的排序过程。访问的排序过程。群体数据的组织C+语言程序设计清华大学 郑莉65内部排序方法内部排序方法l插入排序插

43、入排序l选择排序选择排序l交换排序交换排序群体数据的组织C+语言程序设计清华大学 郑莉66插入排序的基本思想插入排序的基本思想l每一步将一个待排序元素按其关键字值的大小插入到已排每一步将一个待排序元素按其关键字值的大小插入到已排序序列的适当位置上，直到待排序元素插入完为止。序序列的适当位置上，直到待排序元素插入完为止。初始状态：初始状态： 5 4 10 20 12 35 4 10 20 12 3插入操作：插入操作：1 1 44 4 5 10 20 12 3 4 5 10 20 12 32 2 1010 4 5 10 20 12 3 4 5 10 20 12 33 3 2020 4 5 10 2

44、0 12 3 4 5 10 20 12 34 4 1212 4 5 10 12 20 3 4 5 10 12 20 35 5 33 3 4 5 10 12 20 3 4 5 10 12 20C+语言程序设计清华大学 郑莉67直接插入排序直接插入排序l在插入排序过程中，由于寻找插入位置的在插入排序过程中，由于寻找插入位置的方法不同又可以分为不同的插入排序算法，方法不同又可以分为不同的插入排序算法，这里我们只介绍最简单的直接插入排序算这里我们只介绍最简单的直接插入排序算法。法。l例例9-11 直接插入排序函数模板（直接插入排序函数模板（9_11.h）群体数据的组织template void Ins

45、ertionSort(T A, int n) int i, j; T temp; for (i = 1; i 0 & temp Aj-1) Aj = Aj-1; j-; Aj = temp; 直接插入排序函数模板（9_11.h）68C+语言程序设计清华大学 郑莉69选择排序的基本思想选择排序的基本思想每次从待排序序列中选择一个关键字最小的元素，每次从待排序序列中选择一个关键字最小的元素，（当需要按关键字升序排列时），顺序排在已排序序列的（当需要按关键字升序排列时），顺序排在已排序序列的最后，直至全部排完。最后，直至全部排完。5 4 10 20 12 5 4 10 20 12 3 3 初始状态：

46、初始状态：3 3 4 4 10 20 12 5 10 20 12 53 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在选择类排序方法中，从待排序序列在选择类排序方法中，从待排序序列中选择元素的方法不同，又分为不同中选择元素的方法不同，又分为不同的选择排序方法，其中最简单的是通的选择排序方法，其中最简单的是通过顺序比较找出待排序序列中的最小过顺序比较找出待排序序列中的最小元素，称为直接选择排序

47、。元素，称为直接选择排序。l例例9-12 直接选择排序函数模板（直接选择排序函数模板（9-12.h）群体数据的组织template void Swap (T &x, T &y) T temp; 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 = i; for (j = i+1; j n; j+) if (Aj AsmallIndex) smallIndex = j; Swap(Ai, Asma

48、llIndex); 直接选择排序函数模板（9-12.h）71C+语言程序设计清华大学 郑莉72交换排序的基本思想交换排序的基本思想两两比较待排序序列中的元素，并两两比较待排序序列中的元素，并交换不满足顺序要求的各对元素，直到交换不满足顺序要求的各对元素，直到全部满足顺序要求为止。全部满足顺序要求为止。群体数据的组织C+语言程序设计清华大学 郑莉73最简单的交换排序方法最简单的交换排序方法 起泡排序起泡排序对具有对具有n个元素的序列按升序进行起泡排序的个元素的序列按升序进行起泡排序的步骤：步骤： 首先将第一个元素与第二个元素进行比较，若为逆序，则将两元素交换。然后比较第二、第三个元素，依次类推，

49、直到第n-1和第n个元素进行了比较和交换。此过程称为第一趟起泡排序。经过第一趟，最大的元素便被交换到第n个位置。 对前n-1个元素进行第二趟起泡排序，将其中最大元素交换到第n-1个位置。 如此继续，直到某一趟排序未发生任何交换时，排序完毕。对n个元素的序列，起泡排序最多需要进行n-1趟。群体数据的组织C+语言程序设计清华大学 郑莉74起泡排序举例起泡排序举例对整数序列对整数序列 8 5 2 4 3 按升序排序按升序排序8524352438243582345823458初始状态第一趟结果第二趟结果第三趟结果第四趟结果小的逐渐上升每趟沉下一个最大的群体数据的组织C+语言程序设计清华大学 郑莉75例

50、例9-13 起泡排序函数模板起泡排序函数模板template void Swap (T &x, T &y) T temp; temp = x; x = y; y = temp;template void BubbleSort(T A, int n) int i,j; int lastExchangeIndex; i = n-1; while (i 0) lastExchangeIndex = 0; for (j = 0; j i; j+) if (Aj+1 Aj) Swap(Aj,Aj+1); lastExchangeIndex = j; i = lastExchangeIndex; 群体数据