C语言程序设计第九章群体类和群体数据的组织.ppt

第九章第九章 群体类群体类和群体数据的组织和群体数据的组织C++语言程序设计本章主要内容本章主要内容l模板模板l群体类群体类l群体数据的组织群体数据的组织2第一部分第一部分—模板模板l函数模板函数模板l类模板类模板3函数模板函数模板l函数模板可以用来创建一个通用功能函数模板可以用来创建一个通用功能的函数，以支持多种不同形参，进一的函数，以支持多种不同形参，进一步简化重载函数的函数体设计步简化重载函数的函数体设计l声明方法：声明方法：template 函数声明 函 数 模 板4求绝对值函数的模板求绝对值函数的模板#includeusing namespace std;templateT abs(T x){ return x<0?-x:x; }int main(){ int n=-5; double d=-5.5; cout<

例如，对导出函数模板的类型参数例如，对于调用表达式于调用表达式abs(n)，由于实参，由于实参n为为int型，所以推导出模板中类型参数型，所以推导出模板中类型参数T为为intl当类型参数的含义确定后，编译器将当类型参数的含义确定后，编译器将以函数模板为样板，生成一个函数：以函数模板为样板，生成一个函数：int abs(int x){ return x<0?-x:x; } 函 数 模 板6类模板的作用类模板的作用使用类模板使用户可以为类声明一使用类模板使用户可以为类声明一种模式，使得类中的某些数据成员、种模式，使得类中的某些数据成员、某些成员函数的参数、某些成员函数某些成员函数的参数、某些成员函数的返回值，能取任意类型（包括基本的返回值，能取任意类型（包括基本类型的和用户自定义类型）类型的和用户自定义类型）类 模 板7类模板的声明类模板的声明l类模板：类模板：template <模板参数表>class 类名{类成员声明}l如果需要在类模板以外定义其成员如果需要在类模板以外定义其成员函数，则要采用以下的形式：函数，则要采用以下的形式：template <模板参数表>类型名 类名::函数名（参数表）类 模 板8例例9-2 类模板应用举例类模板应用举例#include #include using namespace std;// 结构体结构体Studentstruct Student{ int id; //学号学号 float gpa; //平均分平均分}; 类 模 板9template //类模板：实现对任意类型数据进行存取类模板：实现对任意类型数据进行存取class Store{ private: T item; // 用于存放任意类型的数据用于存放任意类型的数据 int haveValue; // 用于标记用于标记item是否已被存入内容是否已被存入内容 public: Store(void); // 默认形式（无形参）的构造函数默认形式（无形参）的构造函数 T GetElem(void); //提取数据函数提取数据函数 void PutElem(T x); //存入数据函数存入数据函数};// 默认形式构造函数的实现默认形式构造函数的实现template Store::Store(void): haveValue(0) {}1010template // 提取数据函数的实现提取数据函数的实现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中已存入数值中已存入数值 item = x; // 将将x值存入值存入item}1111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 object D " ;cout << D.GetElem() << endl; //输出对象输出对象D的数据成员的数据成员// 由于由于D未经初始化未经初始化,在执行函数在执行函数D.GetElement()时出错时出错}1212第二部分第二部分—群群体数据体数据l线性群体线性群体–线性群体的概念–直接访问群体--数组类–顺序访问群体--链表类–栈类–队列类13群体的概念群体的概念群体群体是指由多个数据元素组成的集是指由多个数据元素组成的集合体。

群体可以分为两个大类：合体群体可以分为两个大类：线性群线性群体体和和非线性群体非线性群体线性群体中的元素按位置排列有序，线性群体中的元素按位置排列有序，可以区分为第一个元素、第二个元素等可以区分为第一个元素、第二个元素等非线性群体不用位置顺序来标识元非线性群体不用位置顺序来标识元素14线性群体的概念线性群体的概念线性群体中的元素次序与其位置关线性群体中的元素次序与其位置关系是对应的性群体中，又可按照系是对应的性群体中，又可按照访问元素的不同方法分为访问元素的不同方法分为直接访问直接访问、、顺顺序访问序访问和和索引访问索引访问在本章我们只介绍直接访问和顺序在本章我们只介绍直接访问和顺序访问…第一个元素第二个元素第三个元素最后一个元素15数组数组l静态数组是具有固定元素个数的群体，其静态数组是具有固定元素个数的群体，其中的元素可以通过下标直接访问中的元素可以通过下标直接访问–缺点：大小在编译时就已经确定，在运行时无法修改l动态数组由一系列位置连续的，任意数量动态数组由一系列位置连续的，任意数量相同类型的元素组成相同类型的元素组成–优点：其元素个数可在程序运行时改变l动态数组类模板：例动态数组类模板：例9-3（（9_3.h））直接访问的线性群体16#ifndef ARRAY_CLASS#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: "};动态数组类模板程序1717template 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(void); Array& operator= (const Array& rhs); T& operator[](int i); operator T* (void) const; int ListSize(void) const; void Resize(int sz); };1818数组类模板的构造函数数组类模板的构造函数// 构造函数构造函数template Array::Array(int sz){ if (sz <= 0) //sz为数组大小（元素个数），若小于为数组大小（元素个数），若小于0，则输出错误信息，则输出错误信息 Error(invalidArraySize); size = sz; // 将元素个数赋值给变量将元素个数赋值给变量size alist = new T[size]; //动态分配动态分配size个个T类型的元素空间类型的元素空间 if (alist == NULL) //如果分配内存不成功，输出错误信息如果分配内存不成功，输出错误信息 Error(memoryAllocationError);}直接访问的线性群体19数组类的拷贝构造函数数组类的拷贝构造函数template Array::Array(const Array& X){ int n = X.size; size = n; alist = new T[n]; if (alist == NULL) Error(memoryAllocationError); T* srcptr = X.alist; // X.alist是对象是对象X的数组首地址的数组首地址 T* destptr = alist; // alist是本对象中的数组首地址是本对象中的数组首地址 while (n--) // 逐个复制数组元素逐个复制数组元素 *destptr++ = *srcptr++;}直接访问的线性群体20浅拷贝浅拷贝 alist sizeAA的数组元素占用的内存拷贝前 alist sizeAA的数组元素占用的内存拷贝后 alist sizeBint main(){ Array A(10); ...... Array B(A); ......}template Array::Array( const Array& X){ size = X.size; alist= X.alist;}21深拷贝深拷贝 alist sizeAA的数组元素占用的内存拷贝前 alist sizeAA的数组元素占用的内存拷贝后 alist sizeBB的数组元素占用的内存22数组类的重载数组类的重载"="运算符函数运算符函数template Array& Array::operator= (const Array& rhs){ int n = rhs.size; if (size != n) { delete [] alist; alist = new T[n]; if (alist == NULL) Error(memoryAllocationError); size = n; } T* destptr = alist; T* srcptr = rhs.alist; while (n--) *destptr++ = *srcptr++; return *this;}直接访问的线性群体23数组类的重载下标操作符函数数组类的重载下标操作符函数template T& Array::operator[] (int n){ // 检查下标是否越界检查下标是否越界 if (n < 0 || n > size-1) Error(indexOutOfRange,n); // 返回下标为返回下标为n的数组元素的数组元素 return alist[n];}直接访问的线性群体24为什么有的函数返回引用为什么有的函数返回引用l如果一个函数的返回值是一个对象的如果一个函数的返回值是一个对象的值，它就被认为是一个常量，不能成值，它就被认为是一个常量，不能成为左值。

为左值l如果返回值为引用由于引用是对象如果返回值为引用由于引用是对象的别名，所以通过引用当然可以改变的别名，所以通过引用当然可以改变对象的值对象的值直接访问的线性群体25重载指针转换操作符重载指针转换操作符template Array::operator T* (void) const{ // 返回当前对象中私有数组的首地址返回当前对象中私有数组的首地址 return alist;}直接访问的线性群体26指针转换运算符的作用指针转换运算符的作用#include using namespace std;int main(){ int a[10]; void read(int *p, int n); read(a, 10);}void read(int *p, int n){ for (int i=0; i>p[i];}int main(){ Array a(10); void read(int *p, n); read(a, 10);}void read(int *p, int n){ for (int i=0; i>p[i];}直接访问的线性群体27Array类的应用类的应用l例例9-4求范围求范围2~N中的质数，中的质数，N在程序在程序运行时由键盘输入。

运行时由键盘输入直接访问的线性群体28#include #include #include "9_3.h"using namespace std;int main(){ Array A(10); int n; int primecount = 0, i, j; cout << "Enter a value >= 2 as upper limit for prime numbers: "; cin >> n; A[primecount++] = 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 && i % j != 0) j += 2; if (j > i/2) A[primecount++] = i; } for (i = 0; i < primecount; i++) { cout << setw(5) << A[i]; if ((i+1) % 10 == 0) cout << endl; } cout << endl;}2929链表链表l链表是一种动态数据结构，可以用来链表是一种动态数据结构，可以用来表示顺序访问的线性群体。

表示顺序访问的线性群体l链表是由系列链表是由系列结点结点组成的，结点可以组成的，结点可以在运行时动态生成在运行时动态生成l每一个结点包括每一个结点包括数据域数据域和指向链表中和指向链表中下一个结点的下一个结点的指针指针（即下一个结点的（即下一个结点的地址）如果链表每个结点中只有一地址）如果链表每个结点中只有一个指向后继结点的指针，则该链表称个指向后继结点的指针，则该链表称为单链表为单链表顺序访问的线性群体30单链表单链表 data1 data2 data3 datan NULL…headrear顺序访问的线性群体31单链表的结点类模板单链表的结点类模板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;}; 顺序访问的线性群体32在结点之后插入一个结点在结点之后插入一个结点 data1 data2… p data…template void Node::InsertAfter(Node *p){ //p节点指针域指向当前节点的后继节点节点指针域指向当前节点的后继节点 p->next = next; next = p; //当前节点的指针域指向当前节点的指针域指向p }顺序访问的线性群体33 删除结点之后的结点删除结点之后的结点顺序访问的线性群体 data1 data2 data3……Node *Node::DeleteAfter(void){ Node *tempPtr = next; if (next == NULL) return NULL; next = tempPtr->next; return tempPtr; }tempPtr34链表的基本操作链表的基本操作l生成结点生成结点l插入结点插入结点l查找结点查找结点l删除结点删除结点l遍历链表遍历链表l清空链表清空链表顺序访问的线性群体35链表类模板链表类模板(例例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"顺序访问的线性群体36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);3737 public: LinkedList(void); LinkedList(const LinkedList& 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; 3838 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); void ClearList(void);};#endif // LINKEDLIST_CLASS3939链表类应用举例链表类应用举例(例例9-7)#include using namespace std;#include "9_6.h"#include "9_6.cpp"int main(){ LinkedList Link; int i, key, item; for (i=0;i < 10;i++) { cin>>item; Link.InsertFront(item);}顺序访问的线性群体40 cout << "List: "; Link.Reset(); while(!Link.EndOfList()) { cout <> key; Link.Reset();4141 while (!Link.EndOfList()) { if(Link.Data() == key) Link.DeleteAt(); Link.Next();} cout << "List: "; Link.Reset(); while(!Link.EndOfList()) { cout <

底an┆a2a1入栈出栈栈顶栈底特殊的线性群体——栈43栈的应用举例栈的应用举例——函数调用函数调用特殊的线性群体——栈main{}调fun(参数)结束fun(参数)返回①②⑤⑦⑧参数当前现场返回地址③⑥入栈当前现场返回地址出栈参数④出栈当前现场 返回地址44栈的应用举例栈的应用举例——表达式处理表达式处理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)特殊的线性群体——栈45栈的基本状态栈的基本状态l栈空栈空–栈中没有元素l栈满栈满–栈中元素个数达到上限l一般状态一般状态–栈中有元素，但未达到栈满状态特殊的线性群体——栈46栈顶┆an┆a1a0入栈出栈数组下标maxn10一般状态栈顶入栈出栈数组下标初始状态（栈空）maxn10栈顶amax┆an┆a1a0入栈出栈数组下标maxn10栈满状态4747栈的基本操作栈的基本操作l初始化初始化l入栈入栈l出栈出栈l清空栈清空栈l访问栈顶元素访问栈顶元素l检测栈的状态（满、空）检测栈的状态（满、空）特殊的线性群体——栈48栈类模板栈类模板(例例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 stacklist[MaxStackSize]; int top; public: 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;};//类的实现略类的实现略49栈的应用栈的应用l例例9.9 一个简单的整数计算器一个简单的整数计算器实现一个简单的整数计算器，能够进行加、减、乘、除和乘方运算。

使用时算式采用后缀输入法，每个操作数、操作符之间都以空白符分隔例如，若要计算"3+5"则输入"3 5 +"乘方运算符用"^"表示每次运算在前次结果基础上进行，若要将前次运算结果清除，可键入"c"当键入"q"时程序结束l9-9.h 9-9.cpp特殊的线性群体——栈50//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 op); public: void Run(void); void Clear(void); };5151void 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 = S.Pop(); return True;}5252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(operand2*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<<'='<> 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 '^': Compute(*c); break; default: Enter(atoi(c)); break; }}5454void Calculator::Clear(void){ S.ClearStack(); }//9_9.cpp#include "9-9.h"int main(){ Calculator CALC; CALC.Run();}5555特殊的线性群体特殊的线性群体——队列队列队列是只能向一端添加元素，从另队列是只能向一端添加元素，从另一端删除元素的线性群体一端删除元素的线性群体a1 a2an-1 an……队头队尾入队出队a056队列的基本状态队列的基本状态l队空队空–队列中没有元素l队满队满–队列中元素个数达到上限l一般状态一般状态–队列中有元素，但未达到队满状态特殊的线性群体——队列57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(队满状态)元素移动方向元素移动方向5858循环队列循环队列在想象中将数组弯曲成环形，元素在想象中将数组弯曲成环形，元素出队时，后继元素不移动，每当队尾达出队时，后继元素不移动，每当队尾达到数组最后一个元素时，便再回到数组到数组最后一个元素时，便再回到数组开头。

开头特殊的线性群体——队列591234……m-1m-2m-30amam+1am+2a3队头队尾a4am-2am-3am-1队满状态 元素个数=m1234……m-1m-2m-30队尾队头队空状态 元素个数=0队尾1234……m-1m-2m-30a0a1a2a3队头一般状态6060例例9-10 队列类模板队列类模板特殊的线性群体——队列#ifndef QUEUE_CLASS#define QUEUE_CLASS#include #include using namespace std;const int MaxQSize = 50; template class Queue{ private: int front, rear, count; T qlist[MaxQSize]; 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; };//成员函数的实现略成员函数的实现略61第三部分第三部分—群群体数据的组织体数据的组织l插入排序插入排序l选择排序选择排序l交换排序交换排序l顺序查找顺序查找l折半查找折半查找62排序（排序（sorting））l排序排序是计算机程序设计中的一种重要操作，是计算机程序设计中的一种重要操作，它的功能是将一个它的功能是将一个数据元素数据元素的任意序列，重的任意序列，重新排列成一个按新排列成一个按关键字关键字有序的序列。

有序的序列–数据元素：数据的基本单位在计算机中通常作为一个整体进行考虑一个数据元素可由若干数据项组成–关键字：数据元素中某个数据项的值，用它可以标识（识别）一个数据元素l在排序过程中需要完成两种基本操作：在排序过程中需要完成两种基本操作：–比较两个数的大小–调整元素在序列中的位置群体数据的组织63内部排序与外部排序内部排序与外部排序l内部排序：内部排序：待排序的数据元素存放在待排序的数据元素存放在计算机内存中进行的排序过程计算机内存中进行的排序过程l外部排序：外部排序：待排序的数据元素数量很待排序的数据元素数量很大，以致内存存中一次不能容纳全部大，以致内存存中一次不能容纳全部数据，在排序过程中尚需对外存进行数据，在排序过程中尚需对外存进行访问的排序过程访问的排序过程群体数据的组织64内部排序方法内部排序方法l插入排序插入排序l选择排序选择排序l交换排序交换排序群体数据的组织65插入排序的基本思想插入排序的基本思想l每一步将一个待排序元素按其关键字值的大小插入到已排每一步将一个待排序元素按其关键字值的大小插入到已排序序列的适当位置上，直到待排序元素插入完为止序序列的适当位置上，直到待排序元素插入完为止。

初始状态：初始状态： [5] 4 10 20 12 3[5] 4 10 20 12 3插入操作：插入操作：1 1 [4][4] [4 5] 10 20 12 3 [4 5] 10 20 12 32 2 [10][10] [4 5 10] 20 12 3 [4 5 10] 20 12 33 3 [20][20] [4 5 10 20] 12 3 [4 5 10 20] 12 34 4 [12][12] [4 5 10 12 20] 3 [4 5 10 12 20] 35 5 [3][3] [3 4 5 10 12 20] [3 4 5 10 12 20]66直接插入排序直接插入排序l在插入排序过程中，由于寻找插入位置的在插入排序过程中，由于寻找插入位置的方法不同又可以分为不同的插入排序算法，方法不同又可以分为不同的插入排序算法，这里我们只介绍最简单的直接插入排序算这里我们只介绍最简单的直接插入排序算法。

法l例例9-11 直接插入排序函数模板（直接插入排序函数模板（9_11.h））群体数据的组织67template void InsertionSort(T A[], int n){ int i, j; T temp; for (i = 1; i < n; i++) { j = i; temp = A[i]; while (j > 0 && temp < A[j-1]) { A[j] = A[j-1]; j--; } A[j] = temp; }}直接插入排序函数模板（9_11.h）6868选择排序的基本思想选择排序的基本思想每次从待排序序列中选择一个关键字最小的元素，每次从待排序序列中选择一个关键字最小的元素，（当需要按关键字升序排列时），顺序排在已排序序列的（当需要按关键字升序排列时），顺序排在已排序序列的最后，直至全部排完最后，直至全部排完[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] ]... ...69直接选择排序直接选择排序l在选择类排序方法中，从待排序序列在选择类排序方法中，从待排序序列中选择元素的方法不同，又分为不同中选择元素的方法不同，又分为不同的选择排序方法，其中最简单的是通的选择排序方法，其中最简单的是通过顺序比较找出待排序序列中的最小过顺序比较找出待排序序列中的最小元素，称为直接选择排序元素，称为直接选择排序l例例9-12 直接选择排序函数模板（直接选择排序函数模板（9-12.h））群体数据的组织70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 (A[j] < A[smallIndex]) smallIndex = j; Swap(A[i], A[smallIndex]); }}直接选择排序函数模板（9-12.h）7171交换排序的基本思想交换排序的基本思想两两比较待排序序列中的元素，并两两比较待排序序列中的元素，并交换不满足顺序要求的各对元素，直到交换不满足顺序要求的各对元素，直到全部满足顺序要求为止。

全部满足顺序要求为止群体数据的组织72最简单的交换排序方法最简单的交换排序方法 ——起泡排序起泡排序对具有对具有n个元素的序列按升序进行起泡排序的个元素的序列按升序进行起泡排序的步骤：步骤：–首先将第一个元素与第二个元素进行比较，若为逆序，则将两元素交换然后比较第二、第三个元素，依次类推，直到第n-1和第n个元素进行了比较和交换此过程称为第一趟起泡排序经过第一趟，最大的元素便被交换到第n个位置–对前n-1个元素进行第二趟起泡排序，将其中最大元素交换到第n-1个位置–如此继续，直到某一趟排序未发生任何交换时，排序完毕对n个元素的序列，起泡排序最多需要进行n-1趟群体数据的组织73起泡排序举例起泡排序举例对整数序列对整数序列 8 5 2 4 3 按升序排序按升序排序8524352438243582345823458初始状态第一趟结果第二趟结果第三趟结果第四趟结果小的逐渐上升每趟沉下一个最大的群体数据的组织74例例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 (A[j+1] < A[j]) { Swap(A[j],A[j+1]); lastExchangeIndex = j; } i = lastExchangeIndex; }}群体数据的组织75顺序查找顺序查找l其基本思想其基本思想–从序列的首元素开始，逐个元素与待查找的关键字进行比较，直到找到相等的。

若整个序列中没有与待查找关键字相等的元素，就是查找不成功l顺序查找函数模板顺序查找函数模板–例9-14群体数据的组织76template int SeqSearch(T list[], int n, T key){ for(int i=0;i < n;i++) if (list[i] == key) return i; return -1; }顺序查找函数模板7777折半查找的基本思想折半查找的基本思想对于已按关键字排序的序列，经过一次比较，可将序列分割成两部分，然后只在有可能包含待查元素的一部分中继续查找，并根据试探结果继续分割，逐步缩小查找范围，直至找到或找不到为止群体数据的组织78折半查找举例折半查找举例用折半查找法，在下列序列中查找值为用折半查找法，在下列序列中查找值为2121的元素：的元素：L=1513192137566475808892H=11M =INT((L+H)/2)=6513192137L=1H=M-1=5M=INT((L+H)/2)=3M2137HL=M+1=4LM=INT((L+H)/2)=4M79例例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 = list[mid]; if (key == midvalue) return mid; else if (key < midvalue) high = mid-1; else low = mid+1; } return -1; }群体数据的组织80。