C++语言程序设计 第九章群体类 清华大学计算机与信息管理中心 郑莉
第九章 群体类 清华大学计算机与信息管理中心 郑 莉 C++语言程序设计
本章主要内率 线性群体 线性群体的概念 直接访问群体-数组类 顺序访问群体--链表类 栈类 队列类 休息
前一页 休息 2 本章主要内容 ⚫ 线性群体 – 线性群体的概念 – 直接访问群体--数组类 – 顺序访问群体--链表类 – 栈类 – 队列类
群体的概念 群体是指由多个数据元素组成的集 合体。群体可以分为两个大类:线性群 体和非线性群体。 线性群体中的元素按位置排列有序, 可以区分为第一个元素、第二个元素等。 非线性群体不用位置顺序来标识元 素。 休息 3
前一页 休息 3 群体的概念 群体是指由多个数据元素组成的集 合体。群体可以分为两个大类:线性群 体和非线性群体。 线性群体中的元素按位置排列有序, 可以区分为第一个元素、第二个元素等。 非线性群体不用位置顺序来标识元 素
线性群体的概念 线性群体中的元素次序与其位置关 系是对应的。在线性群体中,又可按照 访问元素的不同方法分为直接访问、顺 序访问和索引访问。 在本章我们只介绍直接访问和顺序 访问。 第一个元素第二个元素第三个元素 最后一个元素 休息
前一页 休息 4 线性群体的概念 线性群体中的元素次序与其位置关 系是对应的。在线性群体中,又可按照 访问元素的不同方法分为直接访问、顺 序访问和索引访问。 在本章我们只介绍直接访问和顺序 访问。 … 第一个元素 第二个元素 第三个元素 最后一个元素
数组 直 接·静态数组是具有固定元素个数的群体 访其中的元素可以通过下标直接访问 缺点:大小在编译时就已经确定,在运 线 行时无法修改 性●动态数组由一系列位置连续的,任意 群数量相同类型的元素组成 体 优点:其元素个数可在程序运行时改变。 休息
前一页 休息 5 数组 ⚫ 静态数组是具有固定元素个数的群体, 其中的元素可以通过下标直接访问。 – 缺点:大小在编译时就已经确定,在运 行时无法修改。 ⚫ 动态数组由一系列位置连续的,任意 数量相同类型的元素组成。 – 优点:其元素个数可在程序运行时改变。 直 接 访 问 线 性 群 体
动数组类模板 直 接·数组类模板: 访例91(91h) 线性群体 休息
前一页 休息 6 动态数组类模板 ⚫ 数组类模板: 例9.1(9_1.h) 直 接 访 问 线 性 群 体
ifndef array class define ArraY CLass Include include ifndef null const int nUll〓0 # endif∥NULL enum ErrorType IinvalidArraySize, memory Allocation Error, indexOutofRange 3 char *errorMMsgn i"Invalid array size ,"Memory allocation error Invalid index. }
#ifndef ARRAY_CLASS #define ARRAY_CLASS #include #include #ifndef NULL const int NULL = 0; #endif // NULL enum ErrorType { invalidArraySize, memoryAllocationError, indexOutOfRange }; char *errorMsg[] = { "Invalid array size", "Memory allocation error", "Invalid index: " };
template class Array I private T* alist. int size: void Error(ErrorType error, int badIndexe=0) const public Arrayint sz= 50); Array(const Array &A); rArray(void); Array& operator=(const Array & rhs); T& operator (int i; operator T*(void) const int Listsize(void) const; void Resize(int sz);
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); };
数组类模板部分成员函数的奥现 ∥构造函数 template f ysT>:: Array(int sz) Array if (sz<=0) ∥sz为数组大小(元素个数),若小于0,则输出错误信息 Error(invalidArray Size); size=sz;∥将元素个数赋值给变量size ait=newT[sze];动态分配sze个T类型的元素空间 if (alist==NUL)∥如果分配内存不成功,输出错误信息 Error(memory Allocation Error); 了一页休息
前一页 休息 9 数组类模板部分成员函数的实现 // 构造函数 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); }
拷贝构造函数 template fysT:: Array(const Array& X) Arra int n= X. size: SIze E n alist= new Tin if (alist== NULL) Error(memory Allocation Error) T srcptr= X alist;∥ Xalist是对象X的数组首地址 T* destptr=aist;∥ alist是本对象中的数组首地址 while(n--) ∥逐个复制数组元素 destptr++=‘ srcptr++; 了一页休息
前一页 休息 10 拷贝构造函数 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++; }