《群体类和群体数据的组织优秀课件》由会员分享，可在线阅读，更多相关《群体类和群体数据的组织优秀课件（91页珍藏版）》请在金锄头文库上搜索。
1、第第9 9章章 群体类和群体数据的组织群体类和群体数据的组织2021/3/2911、函数模板和类模板、函数模板和类模板2、线性群体、线性群体3、群体数据的组织、群体数据的组织4、综合实例、综合实例2021/3/292函数模板函数模板类模板类模板2021/3/293理想的函数重载是针对不同的参数做不同的事理想的函数重载是针对不同的参数做不同的事. 函函数数模模板板int abs(int x) return x0?-x:x;double abs(double x) return x0?-x:x;2021/3/294函数模板可以用来创建一个通用功能的函函数模板可以用来创建一个通用功能的函数，以支持多
2、种不同形参，进一步简化重数，以支持多种不同形参，进一步简化重载函数的函数体设计。载函数的函数体设计。 函函数数模模板板2021/3/295函数模板的定义形式：函数模板的定义形式：template返回类型返回类型 函数名函数名(函数模板形参表函数模板形参表) 函数模板定义体函数模板定义体 函函数数模模板板template T abs(T x) return x0?-x:x;2021/3/296/9_0.cpp#includeusing namespace std;templateT abs(T x) return x0?-x:x; int main() int n=-5; double d=-5
3、.5; coutabs(n)endl; coutabs(d)endl;return 0; 函函数数模模板板2021/3/297编译器从调用编译器从调用abs()时实参的类型，推时实参的类型，推导出函数模板的类型参数。导出函数模板的类型参数。 例如，对于调用表达式例如，对于调用表达式abs(n)，由于，由于实参实参n为为int型，所以推导出模板中类型型，所以推导出模板中类型参数参数T为为int。当类型参数的含义确定后，编译器将以当类型参数的含义确定后，编译器将以函数模板为样板，生成一个函数：函数模板为样板，生成一个函数：int abs(int x) return x0?-x:x; 函函数数模模板
4、板2021/3/298/9_1.cpp#includeusing namespace std;templatevoid outputArray(const T* array,int count)for(int i=0;icount;i+)coutarrayi ;coutendl; 函函数数模模板板2021/3/299int main() const int A_COUNT=8,B_COUNT=8,C_COUNT=20;int aA_COUNT=1,2,3,4,5,6,7,8;double bB_COUNT=1.1,2.2,3.3,4.4,5.5,6.6,7.7,8.8;char cC_COUN
5、T=Welcome to see you!;couta array contains:endl;outputArray(a,A_COUNT);coutb array contains:endl;outputArray(b,B_COUNT);coutc array contains:endl;outputArray(c,C_COUNT);return 0; 函函数数模模板板2021/3/2910使用类模板使用户可以为类声明一使用类模板使用户可以为类声明一种模式，使得类中的某些数据成员、种模式，使得类中的某些数据成员、某些成员函数的参数、某些成员函数某些成员函数的参数、某些成员函数的返回值，能取任
6、意类型。（包括基的返回值，能取任意类型。（包括基本类型的和用户自定义类型）。本类型的和用户自定义类型）。类类 模模 板板2021/3/2911类模板：类模板：template class 类名类名类成员声明类成员声明如果需要在类模板以外定义其成员函数，则要如果需要在类模板以外定义其成员函数，则要采用以下的形式：采用以下的形式：template 返回类型返回类型名名 类名类名:函数函数名名(参参数表数表)类类 模模 板板2021/3/2912/9_2.cpp#include #include using namespace std;/ 结构体结构体Studentstruct Student in
7、t id; /学号学号 float gpa; /平均分平均分;类类 模模 板板2021/3/2913/类模板：实现对任意类型数据进行存取类模板：实现对任意类型数据进行存取 template class Storepublic: Store(); / 默认形式（无形参）的构造函数默认形式（无形参）的构造函数 T& getElem(); /提取数据函数提取数据函数 void putElem(T x); /存入数据函数存入数据函数private: T item; / 用于存放任意类型的数据用于存放任意类型的数据 bool haveValue; / 用于标记用于标记item是否已被存入内是否已被存入内
8、容容 ;template Store:Store():haveValue(false) 142021/3/2914template / 提取数据函数的实现提取数据函数的实现T& Store:getElem() / 如果试图提取未初始化的数据，则终止程序如果试图提取未初始化的数据，则终止程序 if (!haveValue) cout No item present! endl; exit(1); return item; / 返回返回item中存放的数据中存放的数据 template / 存入数据函数的实现存入数据函数的实现 void Store:putElem(T x) haveValue=t
9、rue; / 将将haveValue 置为置为 TRUE，表示，表示item中已存入数值中已存入数值 item=x; / 将将x值存入值存入item152021/3/2915int main() Store s1, s2; s1.putElem(3); s2.putElem(-7); couts1.getElem() s2.getElem()endl; Student g=1000, 23; Store s3; s3.putElem(g); cout The student id is s3.getElem().id endl;Store d; cout Retrieving object d
10、. ;cout d.getElem() endl; /输出对象输出对象D的数据成员的数据成员/ 由于由于D未经初始化未经初始化,在执行函数在执行函数D.getElement()时出错时出错return 0;162021/3/2916线性群体线性群体线性群体的概念线性群体的概念直接访问群体直接访问群体-数组类数组类顺序访问群体顺序访问群体-链表类链表类栈类栈类队列类队列类2021/3/2917群体群体是指由多个数据元素组成的集合体。是指由多个数据元素组成的集合体。群体可以分为两个大类：群体可以分为两个大类：线性群体线性群体和和非线性非线性群体。群体。线性群体线性群体中的元素按中的元素按位置排列有
11、序位置排列有序，可，可以区分为第一个元素、第二个元素等。以区分为第一个元素、第二个元素等。非线性群体不用位置顺序非线性群体不用位置顺序来标识元素。来标识元素。2021/3/2918线性群体中的元素次序与其位置关系是对线性群体中的元素次序与其位置关系是对应的。在线性群体中，又可按照访问元素的不应的。在线性群体中，又可按照访问元素的不同方法分为直接访问、顺序访问和索引访问。同方法分为直接访问、顺序访问和索引访问。在本章我们只介绍直接访问和顺序访问。在本章我们只介绍直接访问和顺序访问。第一个元素第二个元素第三个元素最后一个元素2021/3/2919静态数组是具有固定元素个数的群体，其中静态数组是具有
12、固定元素个数的群体，其中的元素可以通过下标直接访问。的元素可以通过下标直接访问。缺点：大小在编译时就已经确定，在运行缺点：大小在编译时就已经确定，在运行时无法修改。时无法修改。动态数组由一系列位置连续的，任意数量相动态数组由一系列位置连续的，任意数量相同类型的元素组成。同类型的元素组成。优点：其元素个数可在程序运行时改变。优点：其元素个数可在程序运行时改变。动态数组类模板：例动态数组类模板：例9-3（9_3.h）直直接接访访问问的的线线性性群群体体2021/3/2920/Array.h#ifndef ARRAY_H#define ARRAY_H#include /数组类模板的定义数组类模板的定
13、义template class Arrayprivate:T* list;int size;public:Array(int sz=50); /构造函数构造函数Array(const Array &a);/复制构造函数复制构造函数Array(); 212021/3/2921Array& operator=(const Array &rhs);T& operator(int i);const T& operator(int i) const;operator T*();operator const T*()const;int getSize()const;void resize(int size
14、);222021/3/2922/构造函数构造函数templateArray:Array(int sz)assert(sz=0);size=sz;list=new Tsize;/析构函数析构函数templateArray:Array()deletelist;直直接接访访问问的的线线性性群群体体2021/3/2923/复制构造函数复制构造函数templateArray:Array(const Array &a)size=a.size;list=new Tsize;for(int i=0;isize;i+)listi=a.listi;直直接接访访问问的的线线性性群群体体2021/3/2924 ali
15、st sizeAA的数组元素的数组元素占用的内存占用的内存拷贝前拷贝前 alist sizeAA的数组元素占用的内存拷贝后拷贝后 alist sizeBint main() Array A(10); . Array B(A); .template Array:Array( const Array& X) size = X.size; alist= X.alist;2021/3/2925 alist sizeAA的数组元素的数组元素占用的内存占用的内存拷贝前拷贝前 alist sizeAA的数组元素的数组元素占用的内存占用的内存拷贝后拷贝后 alist sizeBB的数组元素的数组元素占用的内存
16、占用的内存直直接接访访问问的的线线性性群群体体2021/3/2926templateArray& Array:operator =(const Array& rhs)if(&rhs!=this)if(size!=rhs.size)delete list;size=rhs.size;list=new Tsize;for(int i=0;isize;i+)listi=rhs.listi;return *this;直直接接访访问问的的线线性性群群体体2021/3/2927templateT& Array:operator (int n)assert(n=0&nsize);return listn;t
17、emplateconst T& Array:operator (int n)constassert(n=0&nsize);return listn;直直接接访访问问的的线线性性群群体体2021/3/2928如果一个函数的返回值是一个对象的值，它如果一个函数的返回值是一个对象的值，它就被认为是一个常量，不能成为左值。就被认为是一个常量，不能成为左值。如果返回值为引用。由于引用是对象的别名，如果返回值为引用。由于引用是对象的别名，所以通过引用当然可以改变对象的值。所以通过引用当然可以改变对象的值。2021/3/2929template Array:operator T*()return list;
18、template Array:operator const T*()constreturn list;2021/3/2930#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;直直接接访访问
19、问的的线线性性群群体体2021/3/2931例例9-4求范围求范围2N中的质数，中的质数，N在程序在程序运行时由键盘输入。运行时由键盘输入。直直接接访访问问的的线线性性群群体体2021/3/2932/9_4.cpp#include #include #include Array.husing namespace std;int main()Array a(10);int count=0;int n;cout=2 as upper limit for prime numbers:;cinn;acount+=2;332021/3/2933for(int i=2;i=n;i+)bool isPrim
20、e=true;for(int j=0;jcount;j+)/检查检查i是否能被比它小的质数整除是否能被比它小的质数整除if(i%aj=0)isPrime=false;break;if(isPrime)/如果质数表满了，将其空间加倍如果质数表满了，将其空间加倍if(count=a.getSize()a.resize(count*2);acount+=i;for(i=0;icount;i+)coutsetw(8)ai;coutendl;return 0;342021/3/2934链表是一种动态数据结构，可以用来链表是一种动态数据结构，可以用来表示顺序访问的线性群体。表示顺序访问的线性群体。链表是由
21、系列链表是由系列结点结点组成的，结点可以组成的，结点可以在运行时动态生成。在运行时动态生成。每一个结点包括每一个结点包括数据域数据域和指向链表中和指向链表中下一个结点的下一个结点的指针指针（即下一个结点的（即下一个结点的地址）。如果链表每个结点中只有一地址）。如果链表每个结点中只有一个指向后继结点的指针，则该链表称个指向后继结点的指针，则该链表称为单链表。为单链表。顺顺序序访访问问的的线线性性群群体体2021/3/2935 data1 data2 data3 datan NULLheadrear顺顺序序访访问问的的线线性性群群体体2021/3/2936/结点类模板的定义结点类模板的定义temp
22、lateclass Nodeprivate:Node* next;public:T data;Node(const T &data,Node *next=0);void insertAfter(Node *p);Node* deleteAfter();Node* nextNode();const Node* nextNode() const;顺顺序序访访问问的的线线性性群群体体2021/3/2937/构造函数构造函数templateNode:Node(const T&data,Node*next):data(data),next(next) 顺顺序序访访问问的的线线性性群群体体/返回后继结点的
23、指针返回后继结点的指针templateNode* Node:nextNode()return next;/返回后继结点的指针返回后继结点的指针templateconst Node* Node:nextNode()constreturn next;2021/3/2938/在当前结点之后插入一个结点在当前结点之后插入一个结点ptemplatevoid Node:insertAfter(Node*p)p-next=next;next=p; data1 data2 p data顺顺序序访访问问的的线线性性群群体体2021/3/2939/删除当前结点的后继结点，并返回其地址删除当前结点的后继结点，并返回
24、其地址templateNode* Node:deleteAfter()Node* tempPtr=next;if(next=0)return 0;next=tempPtr-next;return tempPtr; data1 data2 data3tempPtr顺顺序序访访问问的的线线性性群群体体2021/3/2940#ifndef LINKEDLIST_H#define LINKEDLIST_H#include Node.htemplate class LinkedListprivate:Node*front,*rear;/表头和表尾指针表头和表尾指针Node*prevPtr,*currPt
25、r;/记录表当前遍历位记录表当前遍历位置的指针，由插入和删除操作更新置的指针，由插入和删除操作更新int size; /表中元素的个数表中元素的个数int position;/当前元素在表中的位置序号。由函当前元素在表中的位置序号。由函数数reset使用使用顺顺序序访访问问的的线线性性群群体体2021/3/2941/生成新结点，数据域为生成新结点，数据域为item，指针域为，指针域为ptrNext;Node* newNode(const T &item,Node* ptrNext=NULL); /释放结点释放结点void freeNode(Node*p);/将链表将链表L复制到当前辈复制到当前
26、辈(假设当前表位空假设当前表位空)/被复制构造函数和被复制构造函数和“operator=”调用调用void copy(const LinkedList&L);public:LinkedList();LinkedList(const LinkedList&L);LinkedList(); int getSize() const;/返回链表中元素的个数返回链表中元素的个数 bool isEmpty() const;/链表是否为空链表是否为空顺顺序序访访问问的的线线性性群群体体2021/3/2942void reset(int pos=0);/初始化游标的位置初始化游标的位置void next();
27、 /使游标移动到下一个结点使游标移动到下一个结点bool endOfList()const;/游标是否到了链尾游标是否到了链尾int currentPosition(void) const;/返回游标的当前位返回游标的当前位void insertFront(const T&item);/在表头插入结点在表头插入结点void insertRear(const T& item);/在表尾插入结点在表尾插入结点void insertAt(const T& item);/在当前结点之前插入结点在当前结点之前插入结点void insertAfter(constT& item);/在当前结点之后插入结点在
28、当前结点之后插入结点void deleteFront();/删除头结点删除头结点void deleteCurrent(); /删除当前结点删除当前结点T& data();/返回对当前结点数据成员的引用返回对当前结点数据成员的引用const T&data()const;/返回对当前结点数据成员的常引用返回对当前结点数据成员的常引用/清空链表：释放所有结点的内存空间。被析构函数和清空链表：释放所有结点的内存空间。被析构函数和operator=调用调用 void clear();顺顺序序访访问问的的线线性性群群体体2021/3/2943#include #include LinkedList.hus
29、ing namespace std;int main()LinkedList list;/输入输入10个整数依次向表头插入个整数依次向表头插入for(int i=0;iitem;list.insertFront(item);顺顺序序访访问问的的线线性性群群体体2021/3/2944 /输出链表输出链表coutList ;list.reset();while(!list.endOfList()coutlist.data() ;list.next();coutendl;452021/3/2945 /输入要删除的整数输入要删除的整数int key;coutkey;/查找并删除结点查找并删除结点lis
30、t.reset();while(!list.endOfList()if(list.data()=key)list.deleteCurrent();list.next();462021/3/2946 /输出链表输出链表coutList: ;list.reset();/输出各结点数据，直到链表尾输出各结点数据，直到链表尾while(!list.endOfList()coutlist.data() ;list.next();coutendl;return 0; 472021/3/2947栈是只能从一端访问的线性群体，可以访问的栈是只能从一端访问的线性群体，可以访问的这一端称栈顶，另一端称栈底。这一端
31、称栈顶，另一端称栈底。ana2a1入栈出栈栈顶栈底特特殊殊的的线线性性群群体体栈栈2021/3/2948ba/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)特特殊殊的的线线性性群群体体栈栈2021/3/2949栈空栈空栈中没有元素栈中没有元素栈满栈满栈中元素个数达到上限栈中元素个数达到上限一般状态一般状态栈中有元素，但未达到栈满状态栈中有元素，但未达到栈满状态特特殊殊的的线线性性群群体体栈栈2021/3/2950栈顶ana1a0入栈出栈数组下标maxn10一般状态栈顶入
32、栈出栈数组下标初始状态（栈空）maxn10栈顶amaxana1a0入栈出栈数组下标maxn10栈满状态512021/3/2951初始化初始化入栈入栈出栈出栈清空栈清空栈访问栈顶元素访问栈顶元素检测栈的状态（满、空）检测栈的状态（满、空）特特殊殊的的线线性性群群体体栈栈2021/3/2952/Stack.h#ifndef STACK_H#define STACK_H#include /栈类模板的定义栈类模板的定义,SIZE为栈的大小为栈的大小template class Stackprivate:T listSIZE;int top; 特特殊殊的的线线性性群群体体栈栈2021/3/2953pub
33、lic: Stack(); void push(const T &item); T pop(); void clear(); const T &peek() const; bool isEmpty() const; bool isFull() const;/类的实现略类的实现略特特殊殊的的线线性性群群体体栈栈2021/3/2954例例9_9 一个简单的整数计算器一个简单的整数计算器实现一个简单的整数计算器，能够进行加、实现一个简单的整数计算器，能够进行加、减、乘、除和乘方运算。使用时算式采用后缀输减、乘、除和乘方运算。使用时算式采用后缀输入法，每个操作数、操作符之间都以空白符分隔。入法，每个操
34、作数、操作符之间都以空白符分隔。例如，若要计算例如，若要计算“3+5”则输入则输入“3 5 +”。乘方运。乘方运算符用算符用“”表示。每次运算在前次结果基础上进表示。每次运算在前次结果基础上进行，若要将前次运算结果清除，可键入行，若要将前次运算结果清除，可键入“c”。当。当键入键入“q”时程序结束。时程序结束。2021/3/2955/Calculator.h#ifndef CALCULATOR_H#define CALCULATOR_H#include Stack.hclass Calculatorprivate:Stack s;void enter(double num);bool getT
35、woOperands(double &opnd1,double &opnd2);void compute(char op);public:void run();void clear();#endif562021/3/2956/Calculator.cpp#include Calculator.h#include #include #include using namespace std;void Calculator:enter(double num) s.push(num); 572021/3/2957/连续将两个操作数弹出栈，放在连续将两个操作数弹出栈，放在opnd1和和opnd2中中/如
36、果栈中没有两个操作数，则返回如果栈中没有两个操作数，则返回false并输出相关信息并输出相关信息bool Calculator:getTwoOperands(double& opnd1, double& opnd2) if (s.isEmpty() cerr Missing operand! endl; return false; opnd1 = s.pop(); if (s.isEmpty() cerr Missing operand! endl; return false; opnd2 = s.pop(); return true;582021/3/2958void Calculator:
37、compute(char op) double operand1, operand2;bool 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.clear(); e
38、lse s.push(operand2/operand1); break; case : s.push(pow(operand2,operand1); break;default:cerrUnrecognized operator!endl;break;cout=s.peek()result;return result;void Calculator:clear(void) s.clear(); 602021/3/2960void Calculator:run(void) string str; while(cinstr, str!=q) switch(str0) case c: s.clea
39、r(); break; case -: if(str.size()1) enter(stringToDouble(str); else compute(str0); break; case +: case *: case /: case : compute(str0); break; default: enter(stringToDouble(str); break; 612021/3/2961/9_9.cpp#include Calculator.hint main() Calculator c; c.run(); return 0;622021/3/2962队列是只能向一端添加元素，从另一
40、端队列是只能向一端添加元素，从另一端删除元素的线性群体删除元素的线性群体a1 a2an-1 an队头队尾入队出队a02021/3/2963队空队空队列中没有元素队列中没有元素队满队满队列中元素个数达到上限队列中元素个数达到上限一般状态一般状态队列中有元素，但未达到队满状态队列中有元素，但未达到队满状态特特殊殊的的线线性性群群体体队队列列2021/3/2964a0 a1an-1 an队头队头队尾队尾入队入队出队出队数组下标数组下标 0 1 n-1 n max(一般状态一般状态)队头队头队尾队尾入队入队出队出队数组下标数组下标 0 1 n-1 n max(队空状态队空状态) a0 a1 an-1
41、an amax队头队头队尾队尾入队入队出队出队数组下标数组下标 0 1 n-1 n max(队满状态队满状态)元素移动方向元素移动方向652021/3/2965在想象中将数组弯曲成环形，元素出队时，在想象中将数组弯曲成环形，元素出队时，后继元素不移动，每当队尾达到数组最后一个后继元素不移动，每当队尾达到数组最后一个元素时，便再回到数组开头。元素时，便再回到数组开头。特特殊殊的的线线性性群群体体队队列列2021/3/29661234m-1m-2m-30amam+1am+2a3队头队头队尾队尾a4am-2am-3am-1队满状态队满状态 元素个数元素个数=m1234m-1m-2m-30队尾队尾队头
42、队头队空状态队空状态 元素个数元素个数=0队尾队尾1234m-1m-2m-30a0a1a2a3队头队头一般状态一般状态672021/3/2967/Queue.h#ifndef QUEUE_H#define QUEUE_H#include /队列类模板的定义队列类模板的定义,SIZE为队列的长度为队列的长度template class Queueprivate:int front,rear,count;/队头指针、队尾指针、元素个数队头指针、队尾指针、元素个数T listSIZE;/队列元素数组队列元素数组public:Queue();/构造函数，初始化队头指针、队尾指针、元素个数构造函数，初始
43、化队头指针、队尾指针、元素个数void insert(const T &item);/新元素入队新元素入队T remove(); /元素出队元素出队特特殊殊的的线线性性群群体体队队列列2021/3/2968void clear();/清空队列清空队列const T&getFront() const;/访问队首元素访问队首元素/测试队列状态测试队列状态int getLength() const;/求队列长度求队列长度bool isEmpty() const;/判断队列空否判断队列空否bool isFull() const;/判断队列满否判断队列满否;/队列类模板的实现队列类模板的实现/构造函数，
44、初始化队头指针、队尾指针、元素个数构造函数，初始化队头指针、队尾指针、元素个数template Queue:Queue():front(0),rear(0),count(0) 2021/3/2969/访问队首元素访问队首元素template const T& Queue:getFront() constreturn listfront;/返回队列元素的个数返回队列元素的个数template int Queue:getLength() constreturn count;/测试队列是否为空测试队列是否为空template bool Queue:isEmpty() constreturn coun
45、t=0;2021/3/2970template bool Queue:isFull() constreturn count=SIZE;template void Queue:clear()count=0;front=0;rear=0;#endif2021/3/2971插入排序插入排序选择排序选择排序交换排序交换排序顺序查找顺序查找折半查找折半查找2021/3/2972排序排序是计算机程序设计中的一种重要操作，是计算机程序设计中的一种重要操作，它的功能是将一个数据元素的任意序列，重它的功能是将一个数据元素的任意序列，重新排列成一个按新排列成一个按关键字关键字有序的序列。有序的序列。数据元素数据元
46、素：数据的基本单位。在计算机中：数据的基本单位。在计算机中通常作为一个整体进行考虑。一个数据元通常作为一个整体进行考虑。一个数据元素可由若干数据项组成。素可由若干数据项组成。关键字关键字：数据元素中某个数据项的值，用：数据元素中某个数据项的值，用它可以标识（识别）一个数据元素。它可以标识（识别）一个数据元素。在排序过程中需要完成两种基本操作：在排序过程中需要完成两种基本操作：比较两个数的大小比较两个数的大小调整元素在序列中的位置调整元素在序列中的位置群群体体数数据据的的组组织织2021/3/2973内部排序内部排序：待排序的数据元素存放在计算机内：待排序的数据元素存放在计算机内存中进行的排序过
47、程。存中进行的排序过程。外部排序外部排序：待排序的数据元素数量很大，以致：待排序的数据元素数量很大，以致内存存中一次不能容纳全部数据，在排序过程内存存中一次不能容纳全部数据，在排序过程中尚需对外存进行访问的排序过程。中尚需对外存进行访问的排序过程。群群体体数数据据的的组组织织2021/3/2974插入排序插入排序选择排序选择排序交换排序交换排序群群体体数数据据的的组组织织2021/3/2975每一步将一个待排序元素按其关键字值的大小插每一步将一个待排序元素按其关键字值的大小插入到已排序序列的适当位置上，直到待排序元素入到已排序序列的适当位置上，直到待排序元素插入完为止。插入完为止。初始状态：初
48、始状态： 5 4 10 20 12 35 4 10 20 12 3插入操作：插入操作：1 1 4 4 4 5 10 20 12 34 5 10 20 12 32 2 10 10 4 5 10 20 12 3 4 5 10 20 12 33 3 2020 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 202021/3/2976在插入排序过程中，由于寻找插入位置的方法不在插入排序过程中，由于寻找插入位置的方法不同又可以分为不同的插入排序算法
49、，这里我们只同又可以分为不同的插入排序算法，这里我们只介绍最简单的直接插入排序算法。介绍最简单的直接插入排序算法。例例9-11 直接插入排序函数模板（直接插入排序函数模板（9_11.h）群群体体数数据据的的组组织织2021/3/2977templatevoid insertionSort(T a,int n)int i,j;T temp;/将下标为将下标为1n-1的元素逐个插入到已排序序列中适当的位置的元素逐个插入到已排序序列中适当的位置for(i=1;i0&temp=aj-1时，时，j便是应插入的位置便是应插入的位置/若达到若达到j=0，则，则0是应插入的位置是应插入的位置aj=aj-1;j
50、-;/插入位置已找到，立即插入插入位置已找到，立即插入aj=temp;782021/3/2978每次从待排序序列中选择一个关键字最小的每次从待排序序列中选择一个关键字最小的元素，（当需要按关键字升序排列时），顺序排元素，（当需要按关键字升序排列时），顺序排在已排序序列的最后，直至全部排完。在已排序序列的最后，直至全部排完。5 4 10 20 12 3初始状态：初始状态：3 4 10 20 12 53 4 10 20 12 5第第 i i 次选择后，将选出的那个记录与第次选择后，将选出的那个记录与第 i i 个记录做交换。个记录做交换。3 4 5 20 12 10.2021/3/2979在选择类
51、排序方法中，从待排序序列中选在选择类排序方法中，从待排序序列中选择元素的方法不同，又分为不同的选择排择元素的方法不同，又分为不同的选择排序方法，其中最简单的是通过顺序比较找序方法，其中最简单的是通过顺序比较找出待排序序列中的最小元素，称为直接选出待排序序列中的最小元素，称为直接选择排序。择排序。例例9-12 直接选择排序函数模板（直接选择排序函数模板（9-12.h）群群体体数数据据的的组组织织2021/3/2980/辅助函数：交换辅助函数：交换x和和y的值的值templatevoid mySwap(T &x,T &y)T temp=x;x=y;y=temp;/用选择法对数组用选择法对数组a的的
52、n个元素进行排序个元素进行排序template void selectionSort(T a,int n)for(int i=0;in-1;i+)int leastIndex=i;/在元素在元素ai+1.an-1中逐个比较，显出最小值中逐个比较，显出最小值for(int j=i+1;jn;j+)if(ajaleastIndex)leastIndex=j;mySwap(ai,aleastIndex);812021/3/2981两两比较待排序序列中的元素，两两比较待排序序列中的元素，并交换不满足顺序要求的各对元素，并交换不满足顺序要求的各对元素，直到全部满足顺序要求为止。直到全部满足顺序要求为止。
53、群群体体数数据据的的组组织织2021/3/2982对具有对具有n个元素的序列按升序进行起泡排序个元素的序列按升序进行起泡排序的步骤：的步骤：首先将第一个元素与第二个元素进行比较，若为逆序，首先将第一个元素与第二个元素进行比较，若为逆序，则将两元素交换。然后比较第二、第三个元素，依次则将两元素交换。然后比较第二、第三个元素，依次类推，直到第类推，直到第n-1和第和第n个元素进行了比较和交换。个元素进行了比较和交换。此过程称为第一趟起泡排序。经过第一趟，最大的元此过程称为第一趟起泡排序。经过第一趟，最大的元素便被交换到第素便被交换到第n个位置。个位置。对前对前n-1个元素进行第二趟起泡排序，将其中
54、最大元个元素进行第二趟起泡排序，将其中最大元素交换到第素交换到第n-1个位置。个位置。如此继续，直到某一趟排序未发生任何交换时，排序如此继续，直到某一趟排序未发生任何交换时，排序完毕。对完毕。对n个元素的序列，起泡排序最多需要进行个元素的序列，起泡排序最多需要进行n-1趟。趟。群群体体数数据据的的组组织织2021/3/2983群群体体数数据据的的组组织织/用选择法对数组用选择法对数组a的的n个元素进行排序个元素进行排序template void bubbleSort(T a,int n)int i=n-1;while(i0)int lastExchangeIndex=0;for(int j=0
55、;ji;j+)if(aj+1aj) mySwap(aj,aj+1); lastExchangeIndex=j;i=lastExchangeIndex;2021/3/2984其基本思想其基本思想从从序序列列的的首首元元素素开开始始，逐逐个个元元素素与与待待查查找找的的关关键键字字进进行行比比较较，直直到到找找到到相相等等的的。若若整整个个序序列列中中没没有有与与待查找关键字相等的元素，就是查找不成功。待查找关键字相等的元素，就是查找不成功。顺序查找函数模板顺序查找函数模板例例9-14群群体体数数据据的的组组织织2021/3/2985templateint seqSearch(const T li
56、st,int n,const T &key)for(int i=0;in;i+)if(listi=key)return i;return -1;862021/3/2986对于已按关键字排序的序列，经过对于已按关键字排序的序列，经过一次比较，可将序列分割成两部分，然一次比较，可将序列分割成两部分，然后只在有可能包含待查元素的一部分中后只在有可能包含待查元素的一部分中继续查找，并根据试探结果继续分割，继续查找，并根据试探结果继续分割，逐步缩小查找范围，直至找到或找不到逐步缩小查找范围，直至找到或找不到为止。为止。群群体体数数据据的的组组织织2021/3/2987用折半查找法，在下列序列中查找值为用
57、折半查找法，在下列序列中查找值为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)=4M2021/3/2988templateint binSearch(const T list,int n,const T &key)int low=0;int high=n-1;while(low=high)int mid=(low+high)/2;if(key=listmid)return mid;else if(keylis
58、tmid)high=mid-1;elselow=mid+1;return -1;群群体体数数据据的的组组织织2021/3/2989综综合合实实例例使用动态数组模板类使用动态数组模板类Array来代替来代替C+预定预定义的数组类型也可以完成同样的功能义的数组类型也可以完成同样的功能。允许用户随时动态添加新的账户。允许用户随时动态添加新的账户。2021/3/2990第第第第9 9章课后习题章课后习题章课后习题章课后习题 9-19-1、9-29-2、9-79-7、9-89-8、9-199-19 。写在作业本上，并及时交作业。写在作业本上，并及时交作业。写在作业本上，并及时交作业。写在作业本上，并及时交作业。2021/3/2991
