[高等教育]函数模板c++ppt课件

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

2、函数声明 函 数 模 板C+语言程序设计清华大学 郑莉求绝对值函数的模板求绝对值函数的模板#includeusing namespace std;templateT abs(T x) return x0?-x:x; void main() int n=-5; double d=-5.5; coutabs(n)endl; coutabs(d)endl; 函 数 模 板运转结果：运转结果：55.5C+语言程序设计清华大学 郑莉求绝对值函数的模板分析求绝对值函数的模板分析l编译器从调用编译器从调用abs()时实参的类型，推时实参的类型，推导出函数模板的类型参数。例如，对导出函数模板的类型参数。例如，

3、对于调用表达式于调用表达式abs(n)，由于实参，由于实参n为为int型，所以推导出模板中类型参数型，所以推导出模板中类型参数T为为int。l当类型参数的含义确定后，编译器将当类型参数的含义确定后，编译器将以函数模板为样板，生成一个函数：以函数模板为样板，生成一个函数：int abs(int x) return x0?-x:x; 函 数 模 板C+语言程序设计清华大学 郑莉类模板的作用类模板的作用运用类模板运用户可以为类声明一运用类模板运用户可以为类声明一种方式，使得类中的某些数据成员、种方式，使得类中的某些数据成员、某些成员函数的参数、某些成员函数某些成员函数的参数、某些成员函数的前往值，能

4、取恣意类型包括根本的前往值，能取恣意类型包括根本类型的和用户自定义类型。类型的和用户自定义类型。类 模 板C+语言程序设计清华大学 郑莉类模板的声明类模板的声明l类模板：类模板：ltemplate lclass 类名类名l类成员声明类成员声明l假设在类模板以外定义其成员函数，假设在类模板以外定义其成员函数，那么要采用以下的方式那么要采用以下的方式(每个函数前均每个函数前均写写)ltemplate l类型名类型名 类名类名:函数名参数表函数名参数表类 模 板C+语言程序设计清华大学 郑莉例例9-2 类模板运用举例类模板运用举例#include #include using namespace s

5、td;/ 构造体构造体Studentstruct Student int id; /学号学号 float gpa; /平均分平均分; 类 模 板template /类模板：实现对恣意类型数据进展存取类模板：实现对恣意类型数据进展存取class Store private: T item; / 用于存放恣意类型的数据用于存放恣意类型的数据 int haveValue; / 用于标志用于标志item能否已被存入内容能否已被存入内容 public: Store(void); / 默许方式无形参的构造函数默许方式无形参的构造函数 T GetElem(void); /提取数据函数提取数据函数 void

6、PutElem(T x); /存入数据函数存入数据函数;/ 默许方式构造函数的实现默许方式构造函数的实现template Store:Store(void): haveValue(0) 10template / 提取数据函数的实现提取数据函数的实现T Store:GetElem(void) / 假设试图提取未初始化的数据，那么终止程序假设试图提取未初始化的数据，那么终止程序 if (haveValue = 0) cout No item present! endl; exit(1); return item; / 前往前往item中存放的数据中存放的数据 template / 存入数据函数的实

7、现存入数据函数的实现 void Store:PutElem(T x) haveValue+; / 将将haveValue 置为置为 TRUE，表示，表示item中已存入数值中已存入数值 item = x; / 将将x值存入值存入item11void main(void) 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.G

8、etElem().id endl; cout Retrieving object D ;cout D.GetElem() endl; /输出对象输出对象D的数据成员的数据成员/ 由于由于D未经初始化未经初始化,在执行函数在执行函数D.GetElement()时出错时出错12C+语言程序设计清华大学 郑莉第二部分第二部分群体数据群体数据l线性群体l线性群体的概念l直接访问群体-数组类l顺序访问群体-链表类l栈类l队列类C+语言程序设计清华大学 郑莉群体的概念群体的概念群体是指由多个数据元素组成的集群体是指由多个数据元素组成的集合体。群体可以分为两个大类：线性群合体。群体可以分为两个大类：线性群体

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

10、个元素第二个元素第三个元素最后一个元素C+语言程序设计清华大学 郑莉数组数组l静态数组是具有固定元素个数的群体，其静态数组是具有固定元素个数的群体，其中的元素可以经过下标直接访问。中的元素可以经过下标直接访问。l缺陷：大小在编译时就曾经确定，在运转缺陷：大小在编译时就曾经确定，在运转时无法修正。时无法修正。l动态数组由一系列位置延续的，恣意数量动态数组由一系列位置延续的，恣意数量一样类型的元素组成。一样类型的元素组成。l优点：其元素个数可在程序运转时改动。优点：其元素个数可在程序运转时改动。l动态数组类模板：例动态数组类模板：例9-39_3.h直接访问的线性群体#ifndef ARRAY_CL

11、ASS#define ARRAY_CLASSusing namespace std;#include #include #ifndef NULLconst int NULL = 0;#endif / NULLenum ErrorType invalidArraySize, memoryAllocationError, indexOutOfRange ;char *errorMsg = Invalid array size, Memory allocation error, Invalid index: ;动态数组类模板程序17template class Array private: T* a

12、list; int size; void Error(ErrorType error,int badIndex=0) const; public: Array(int sz = 50); Array(const Array& A); Array(void); Array& operator= (const Array& rhs); T& operator(int i); operator T* (void) const; int ListSize(void) const; void Resize(int sz); ;18C+语言程序设计清华大学 郑莉数组类模板的

13、构造函数数组类模板的构造函数/ 构造函数构造函数template Array:Array(int sz) if (sz = 0) /sz为数组大小元素个数，假设小于为数组大小元素个数，假设小于0，那么输出错误，那么输出错误信息信息 Error(invalidArraySize); size = sz; / 将元素个数赋值给变量将元素个数赋值给变量size alist = new Tsize; /动态分配动态分配size个个T类型的元素空间类型的元素空间 if (alist = NULL) /假设分配内存不胜利，输出错误信息假设分配内存不胜利，输出错误信息 Error(memoryAllocat

14、ionError);直接访问的线性群体C+语言程序设计清华大学 郑莉数组类的拷贝构造函数数组类的拷贝构造函数template Array:Array(const Array& X) int n = X.size; size = n; alist = new Tn; if (alist = NULL) Error(memoryAllocationError); T* srcptr = X.alist; / X.alist是对象是对象X的数组首地址的数组首地址 T* destptr = alist; / alist是本对象中的数组首地址是本对象中的数组首地址 while (n-) / 逐个

15、复制数组元素逐个复制数组元素 *destptr+ = *srcptr+;直接访问的线性群体C+语言程序设计清华大学 郑莉浅拷贝浅拷贝 alist sizeAA的数组元素占用的内存拷贝前 alist sizeAA的数组元素占用的内存拷贝后 alist sizeBvoid main(void) Array A(10); . Array B(A); .template Array:Array( const Array& X) size = X.size; alist= X.alist;C+语言程序设计清华大学 郑莉深拷贝深拷贝 alist sizeAA的数组元素占用的内存拷贝前 alist

16、sizeAA的数组元素占用的内存拷贝后 alist sizeBB的数组元素占用的内存C+语言程序设计清华大学 郑莉数组类的重载数组类的重载=运算符函数运算符函数template Array& Array:operator= (const Array& rhs) int n = rhs.size; if (size != n) delete alist; alist = new Tn; if (alist = NULL) Error(memoryAllocationError); size = n; T* destptr = alist; T* srcptr = rhs.alis

17、t; while (n-) *destptr+ = *srcptr+; return *this;直接访问的线性群体C+语言程序设计清华大学 郑莉数组类的重载下标操作符函数数组类的重载下标操作符函数template T& Array:operator (int n) / 检查下标能否越界检查下标能否越界 if (n size-1) Error(indexOutOfRange,n); / 前往下标为前往下标为n的数组元素的数组元素 return alistn;直接访问的线性群体C+语言程序设计清华大学 郑莉为什么有的函数前往援用为什么有的函数前往援用l假设一个函数的前往值是一个对象的假设

18、一个函数的前往值是一个对象的值，它就被以为是一个常量，不能成值，它就被以为是一个常量，不能成为左值。为左值。l假设前往值为援用。由于援用是对象假设前往值为援用。由于援用是对象的别名，所以经过援用当然可以改动的别名，所以经过援用当然可以改动对象的值。对象的值。直接访问的线性群体C+语言程序设计清华大学 郑莉重载指针转换操作符重载指针转换操作符template Array:operator T* (void) const / 前往当前对象中私有数组的首地址前往当前对象中私有数组的首地址 return alist;直接访问的线性群体C+语言程序设计清华大学 郑莉指针转换运算符的作用指针转换运算符的作

19、用#include using namespace std;void main() int a10; void read(int *p, int n); read(a, 10);void read(int *p, int n) for (int i=0; ipi;void main() Array a(10); void read(int *p, n); read(a, 10);void read(int *p, int n) for (int i=0; ipi;直接访问的线性群体C+语言程序设计清华大学 郑莉Array类的运用类的运用l例例9-4求范围求范围2N中的质数，中的质数，N在程序在

20、程序运转时由键盘输入。运转时由键盘输入。直接访问的线性群体#include #include #include 9_3.husing namespace std;void main(void) 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(primecount + 1

21、0); 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;29C+语言程序设计清华大学 郑莉链表链表l链表是一种动态数据构造，可以用来链表是一种动态数据构造，可以用来表示顺序访问的线性群体。表示顺序访问的线性群体。l链表是由系列结点组成的，结点可以链表是由系列结点组成的，结点可以在运转时动态生成。在运转时动态生成。l每一个结点包括数据域和指向链表

22、中每一个结点包括数据域和指向链表中下一个结点的指针即下一个结点的下一个结点的指针即下一个结点的地址。假设链表每个结点中只需一地址。假设链表每个结点中只需一个指向后继结点的指针，那么该链表个指向后继结点的指针，那么该链表称为单链表。称为单链表。顺序访问的线性群体C+语言程序设计清华大学 郑莉单链表单链表 data1 data2 data3 datan NULLheadrear顺序访问的线性群体C+语言程序设计清华大学 郑莉单链表的结点类模板单链表的结点类模板template class Node private: Node *next; public: T data; Node(const T&

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

24、 顺序访问的线性群体C+语言程序设计清华大学 郑莉 删除结点之后的结点删除结点之后的结点顺序访问的线性群体 data1 data2 data3Node *Node:DeleteAfter(void) Node *tempPtr = next; if (next = NULL) return NULL; next = tempPtr-next; return tempPtr; tempPtrC+语言程序设计清华大学 郑莉链表的根本操作链表的根本操作l生成结点生成结点l插入结点插入结点l查找结点查找结点l删除结点删除结点l遍历链表遍历链表l清空链表清空链表顺序访问的线性群体C+语言程序设计清华大学

25、 郑莉链表类模板链表类模板(例例9-6)/9_6.h#ifndef LINKEDLIST_CLASS#define LINKEDLIST_CLASS#include #include using namespace std;#ifndef NULLconst 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(con

26、st T& item, Node *ptrNext=NULL); void FreeNode(Node *p); void CopyList(const LinkedList& L);37 public: LinkedList(void); LinkedList(const LinkedList& L); LinkedList(void); LinkedList& operator= (const LinkedList& L); int ListSize(void) const; int ListEmpty(void) const; void Reset

27、(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); void InsertAt(const T& item); void InsertAfter(const T& item); T DeleteFront(void); void DeleteAt(void); T& Data(void);

28、void ClearList(void);#endif / LINKEDLIST_CLASS39C+语言程序设计清华大学 郑莉链表类运用举例链表类运用举例(例例9-7)#include using namespace std;#include 9_6.h#include 9_6.cppvoid main(void) LinkedList Link; int i, key, item; for (i=0;i item; Link.InsertFront(item);顺序访问的线性群体 cout List: ; Link.Reset(); while(!Link.EndOfList() cout

29、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.EndOfList() cout Link.Data() ; Link.Next(); cout endl;42C+语言程序设计清华大学 郑莉特殊的线性群体特殊的线性群体栈栈栈是只能从一端访问的线性群体，栈是只能从一端访问的线性群体，可以访

30、问的这一端称栈顶，另一端称栈可以访问的这一端称栈顶，另一端称栈底。底。ana2a1入栈出栈栈顶栈底特殊的线性群体栈C+语言程序设计清华大学 郑莉栈的运用举例栈的运用举例函数调函数调用用特殊的线性群体栈main调fun(参数)终了fun(参数)前往参数当前现场前往地址入栈当前现场前往地址出栈参数出栈当前现场 前往地址C+语言程序设计清华大学 郑莉栈的运用举例栈的运用举例表达式表达式处置处置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+语言程序设计

31、清华大学 郑莉栈的根本形状栈的根本形状l栈空栈空l栈中没有元素栈中没有元素l栈满栈满l栈中元素个数到达上限栈中元素个数到达上限l普通形状普通形状l栈中有元素，但未到达栈满形状栈中有元素，但未到达栈满形状特殊的线性群体栈栈顶ana1a0入栈出栈数组下标maxn10普通形状栈顶入栈出栈数组下标初始形状栈空maxn10栈顶amaxana1a0入栈出栈数组下标maxn10栈满形状47C+语言程序设计清华大学 郑莉栈的根本操作栈的根本操作l初始化初始化l入栈入栈l出栈出栈l清空栈清空栈l访问栈顶元素访问栈顶元素l检测栈的形状满、空检测栈的形状满、空特殊的线性群体栈C+语言程序设计清华大学 郑莉栈类模板栈

32、类模板(例例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; public: Stack (void); void Push (const T& item); T Pop (void); void ClearStack(void); T Peek (void) con

33、st; int StackEmpty(void) const; int StackFull(void) const;/类的实现略C+语言程序设计清华大学 郑莉栈的运用栈的运用l例例9.9 一个简单的整数计算器一个简单的整数计算器l实现一个简单的整数计算器，可以进实现一个简单的整数计算器，可以进展加、减、乘、除和乘方运算。运用展加、减、乘、除和乘方运算。运用时算式采用后缀输入法，每个操作数、时算式采用后缀输入法，每个操作数、操作符之间都以空白符分隔。例如，操作符之间都以空白符分隔。例如，假设要计算假设要计算3+5那么输入那么输入3 5 +。乘方运算符用乘方运算符用表示。每次运算在表示。每次运算在

34、前次结果根底上进展，假设要将前次前次结果根底上进展，假设要将前次运算结果去除，可键入运算结果去除，可键入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&

35、; opnd2); void Compute(char 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 op

36、erand! endl; return False; opnd2 = 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(ope

37、rand2*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); b

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

39、头队尾入队出队a0C+语言程序设计清华大学 郑莉队列的根本形状队列的根本形状l队空队空l队列中没有元素队列中没有元素l队满队满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+语言程序设计清华大学 郑莉循环队列循环队列在

40、想象中将数组弯曲成环形，元素在想象中将数组弯曲成环形，元素出队时，后继元素不挪动，每当队尾到出队时，后继元素不挪动，每当队尾到达数组最后一个元素时，便再回到数组达数组最后一个元素时，便再回到数组开头。开头。特殊的线性群体队列1234m-1m-2m-30amam+1am+2a3队头队尾a4am-2am-3am-1队满形状 元素个数=m1234m-1m-2m-30队尾队头队空形状 元素个数=0队尾1234m-1m-2m-30a0a1a2a3队头普通形状60C+语言程序设计清华大学 郑莉例例9-10 队列类模板队列类模板特殊的线性群体队列#ifndef QUEUE_CLASS#define QUEU

41、E_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& item); T QDelete(void); void ClearQueue(void); T QFront(void) const; int QLength(void) const; int QEmpty(void)

42、const; int QFull(void) const; ;/成员函数的实现略C+语言程序设计清华大学 郑莉第三部分第三部分群体数据的组织群体数据的组织l插入排序插入排序l选择排序选择排序l交换排序交换排序l顺序查找顺序查找l折半查找折半查找C+语言程序设计清华大学 郑莉排序排序sortingl排序是计算机程序设计中的一种重要操作，排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素的恣意序列，重它的功能是将一个数据元素的恣意序列，重新陈列成一个按关键字有序的序列。新陈列成一个按关键字有序的序列。l数据元素：数据的根本单位。在计算机中通数据元素：数据的根本单位。在计算机中通常作为一

43、个整体进展思索。一个数据元素可常作为一个整体进展思索。一个数据元素可由假设干数据项组成。由假设干数据项组成。l关键字：数据元素中某个数据项的值，用它关键字：数据元素中某个数据项的值，用它可以标识识别一个数据元素。可以标识识别一个数据元素。l在排序过程中需求完成两种根本操作：在排序过程中需求完成两种根本操作：l比较两个数的大小比较两个数的大小l调整元素在序列中的位置调整元素在序列中的位置群体数据的组织C+语言程序设计清华大学 郑莉内部排序与外部排序内部排序与外部排序l内部排序：待排序的数据元素存放在内部排序：待排序的数据元素存放在计算机内存中进展的排序过程。计算机内存中进展的排序过程。l外部排序

44、：待排序的数据元素数量很外部排序：待排序的数据元素数量很大，以致内存存中一次不能包容全部大，以致内存存中一次不能包容全部数据，在排序过程中尚需对外存进展数据，在排序过程中尚需对外存进展访问的排序过程。访问的排序过程。群体数据的组织C+语言程序设计清华大学 郑莉内部排序方法内部排序方法l插入排序插入排序l选择排序选择排序l交换排序交换排序群体数据的组织C+语言程序设计清华大学 郑莉插入排序的根本思想插入排序的根本思想l每一步将一个待排序元素按其关键字值的大小插入到已排每一步将一个待排序元素按其关键字值的大小插入到已排序序列的适当位置上，直到待排序元素插入完为止。序序列的适当位置上，直到待排序元素

45、插入完为止。初始形状：初始形状： 5 4 10 20 12 3 5 4 10 20 12 3插入操作：插入操作：1 4 4 5 10 20 12 31 4 4 5 10 20 12 32 10 4 5 10 20 12 32 10 4 5 10 20 12 33 20 4 5 10 20 12 33 20 4 5 10 20 12 34 12 4 5 10 12 20 34 12 4 5 10 12 20 35 3 3 4 5 10 12 205 3 3 4 5 10 12 20C+语言程序设计清华大学 郑莉直接插入排序直接插入排序l在插入排序过程中，由于寻觅插入位置的在插入排序过程中，由于寻

46、觅插入位置的方法不同又可以分为不同的插入排序算法，方法不同又可以分为不同的插入排序算法，这里我们只引见最简单的直接插入排序算这里我们只引见最简单的直接插入排序算法。法。l例例9-11 直接插入排序函数模板直接插入排序函数模板9_11.h群体数据的组织template void InsertionSort(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.h68C+语言程序设计清华大学 郑莉选择排序的根本思想选择排序的根本思想每次从待排序序

47、列中选择一个关键字最小的元素，每次从待排序序列中选择一个关键字最小的元素，当需求按关键字升序陈列时，顺序排在已排序序列的当需求按关键字升序陈列时，顺序排在已排序序列的最后，直至全部排完。最后，直至全部排完。5 4 10 20 12 35 4 10 20 12 3初始形状：初始形状：3 4 10 20 12 53 4 10 20 12 53 4 10 20 12 53 4 10 20 12 5第 i 次选择后，将选出的那个记录与第 i 个记录做交换。3 4 5 20 12 103 4 5 20 12 10. .C+语言程序设计清华大学 郑莉直接选择排序直接选择排序l在选择类排序方法中，从待排序序

48、列在选择类排序方法中，从待排序序列中选择元素的方法不同，又分为不同中选择元素的方法不同，又分为不同的选择排序方法，其中最简单的是经的选择排序方法，其中最简单的是经过顺序比较找出待排序序列中的最小过顺序比较找出待排序序列中的最小元素，称为直接选择排序。元素，称为直接选择排序。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 smal

49、lIndex; 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, AsmallIndex); 直接选择排序函数模板9-12.h71C+语言程序设计清华大学 郑莉交换排序的根本思想交换排序的根本思想两两比较待排序序列中的元素，并两两比较待排序序列中的元素，并交换不满足顺序要求的各对元素，直到交换不满足顺序要求的各对元素，直到全部满足顺序要求为止。全部满足顺序要求为止。群体数据的组织C+语言程序设计清华大学 郑莉最简单的交换排序方法最简单的交换排序方法 起泡排序起泡排序对具有对具有n个元素的序列按升序进展起泡排序的个元素的序列按升序进展起泡排序的步骤：步骤：首先将第一个元素与第二个元素进展比较，假首先将第一个元素与第二个元素进展比较，假设为逆序，那么将两元素交换。然后比较第二、设为逆序，那么将两元素交换。然后比较第二、第三个元素，依次类推，直到第