[工学]数据结构5陈慧南_数组和字符串.ppt

第5讲,DATA STRUCTURE,DATA STRUCTURE,第4章 数组和字符串,DATA STRUCTURE,4.1.1 数组ADT,数组的定义 数组是下标index 和值value 组成的序对的集合。 ( index, value ) 一维数组： A = (0, 15), (1, 24), (2, 33), (3, 21) ,DATA STRUCTURE,4.1.1 数组ADT,数组ADT ADT Array 数据： 下标index和元素值value组成的数据对集合,其中任意两个数据对的下标index各不相同。 运算： Create(): 建立一个数组。 Retrieve(i): 返回下标为i的元素值。 Store(i,x): 将下标为i的数据对的值置为x。 ;,DATA STRUCTURE,4.1.2 数组的顺序表示,一维数组的顺序表示 loc(ai) = loc(a0)+i*k ( i = 0, 1, 2, , n-1 ) 基地址：loc(a0) 每个元素占 k 个存储单元。,template A = a0, a1, , ai, , an-1 ; pA = new T100; / 然后赋值 T b1 = pAi; / 获取第i个元素 T b2 = *( pA + i ); / 获取第i个元素,DATA STRUCTURE,4.1.2 数组的顺序表示,二维数组的顺序表示 二维数组amn映射到一维的存储空间时有两种顺序：行优先和列优先。 大多数语言如PASCAL、BASIC、C、C+等都是按行优先顺序存储的，FORTRAN是按列优先顺序存储的。,Amn = a0,0, a0,1, a0,n-1 , , ai,0, ai,1, ai,n-1 , ,am-1,0, am-1,1, am-1,n-1 ;,C/C+行优先的存储方法,DATA STRUCTURE,4.1.2 数组的顺序表示,二维数组的顺序表示 loc(aij) = loc(a00)+(i*n+j)*k (0 i m; 0 j n) 基地址：loc(a00) 每个元素占 k 个存储单元。,DATA STRUCTURE,4.1.2 数组的顺序表示,C/C+中申请二维数组的方法： int row=3, col=4; / 方法1：= int Mtrxrowcol= 1,2,3,4,5,6,7,8,9,10,11,12 ; / 方法2：= int *ppMtrx = new int*row; for (int i = 0; i row; i+) ppMtrxi = new intcol; int n=0; for( i = 0; i row; i+) for(int j = 0; j col; j+) ppMtrxij = +n; for ( i = 0; i row; i+) delete ppMtrxi; delete ppMtrx;,DATA STRUCTURE,4.1.2 数组的顺序表示,/ 方法3：= #define row 3 #define col 4 typedef int Mtrxrow; main() int n = 0; Mtrx *pMtrx = new Mtrxcol; / 用法与二维数组相同 for(int i = 0; i row; i+) for(int j = 0; j col; j+) pMtrxij = +n; delete pMtrx; ,定义二维数组,将数组定义为数据类型,DATA STRUCTURE,4.1.2 数组的顺序表示,多维数组的顺序表示 推广到多维数组am1m2 mn，数组元素ai1i2 in的存储地址为 ： loc(ai1i2 in) = loc(a00) + ( i1* m2 * m3 * mn + i2* m3 * m4 * mn + + in-1* mn + in ) * k =,DATA STRUCTURE,4.1.3 一维数组的C+类,用C+的模板类定义的一维数组抽象数据类型。公有成员函数包括： 构造函数 析构函数 重载下标操作符： 重载下标操作符用来返回指向第i个元素的引用 重载数组赋值： 赋值操作符实现数组的整体赋值。,DATA STRUCTURE,4.1.3 一维数组的C+类,#include template class Array1D public: Array1D(int sz=0); Array1D() delete elements; T,取元素值,整体赋值,缺少拷贝构造函数！,DATA STRUCTURE,4.1.3 一维数组的C+类,构造函数，申请数组空间 template Array1D:Array1D(int sz) assert(sz=0); /越界检查 size = sz; elements = new Tsz; 运算符，获取第i个元素 template T ,DATA STRUCTURE,4.1.3 一维数组的C+类,重载运算符 = template Array1D ,DATA STRUCTURE,4.1.3 一维数组的C+类,重载流运算符和 istream ,DATA STRUCTURE,main中测试该类的效果 #include “array1d.h“ main() Array1D a(5),b(8); Array1D c; /采用缺省长度0 cina; coutb; cout“b “b; cout“c “c; cout“a0=“a0“;“ “b5=“b5endl; c=b; cout“c=b, c “c; b=a; cout“b=a, b “b; ,4.1.3 一维数组的C+类,DATA STRUCTURE,1 C+中有关数组的类,class Array public: Array (int size=0,char* ptr=NULL); / default constructor Array (const Array,DATA STRUCTURE,1 C+中有关数组的类,Array:Array(int size, char* ptr /*=NULL*/ ) m_ptr = NULL; SetArray(size, ptr); Array:Array (const Array ,浅拷贝！要改成深拷贝。,DATA STRUCTURE,1 C+中有关数组的类,#include #include main() char str9; strcpy(str,“Software”); / 注意：此处不能用char* str=”Software”; / 因为这样的字符串是只读的。 Array ar1(8,str); Array ar2(ar1); / 调用拷贝构造函数，其中调用了SetArray() str0 = 6; / 改变数组内容 cout ar1.getPtr() “ ” ; cout ar2.getPtr() endl; ,输出： 6oftware 6oftware,浅拷贝的后果。,DATA STRUCTURE,1 C+中有关数组的类,void Array:SetArray(int size, char* ptr) if ( size = 0 | ptr = NULL ) return; if ( m_ptr != NULL ) delete m_ptr; / 释放原数组 m_size = size; m_ptr = new charsize; / 申请新的空间 strncpy( m_ptr, ptr, size); / 拷贝 ,输出： Software 6oftware,DATA STRUCTURE,第4章 数组和字符串,DATA STRUCTURE,4.2.1 对称矩阵,对称矩阵和三角矩阵 在nn的矩阵A中，若aij=aji (0 i, j n)，则称其为n阶对称矩阵。 对于对称矩阵，可以只存储上三角(或下三角)中的元素(包括对角线上的元素)。,DATA STRUCTURE,4.2.1 对称矩阵,如果采用二维数组，n维对称矩阵的元素为n2。 如果只存储三角中元素，则元素个数为 n(n+1)/2 其中行列序号与元 素序号的对应关系：,DATA STRUCTURE,第4章 数组和字符串,DATA STRUCTURE,4.3.1 稀疏矩阵ADT,稀疏矩阵 大多数元素为零的矩阵称为稀疏矩阵。 对于稀疏矩阵可只存非零元素。,DATA STRUCTURE,4.3.1 稀疏矩阵ADT,稀疏矩阵ADT ADT SparseMatrix 数据： 绝大多数元素为零的矩阵。 运算： Create():建立一个稀疏矩阵。 Destroy():撤消一个稀疏矩阵。 Add(B,C):当前矩阵对象与B相加，C中返回相加和。 Mul(B,C):当前矩阵对象与B相乘，C中返回相乘积。 Transpose(B): B中返回当前矩阵对象的转置矩阵。 ,DATA STRUCTURE,4.3.1 稀疏矩阵ADT,#include template class SparseMatrix public: SparseMatrix(int maxRowSize, int maxColSize) SparseMatrix() virtual void Add(const SparseMatrix ,稀疏矩阵的C+类,DATA STRUCTURE,4.3.2 稀疏矩阵的顺序表示,三元组表示法 按照压缩存储的思想，稀疏矩阵Am n中的每一个非零元素 aij 的值、行号和列号可以用一个三元组（ i, j, v）表示。 三元组可以按行或按列的顺序存储。 三元组的Term类 template struct Terms int row,col; T value; ;,DATA STRUCTURE,4.3.2 稀疏矩阵的顺序表示,0 0 16,0 3 22,0 5 -16,1 1 12,1 2 3,2 3 -8,4 0 91,6 2 15,DATA STRUCTURE,4.3.2 稀疏矩阵的顺序表示,#include template class SeqTriple public: SeqTriple(int mSize); SeqTriple() delete trip; ; void Add(const SeqTriple ,行三元组表的C+类,DATA STRUCTURE,第4章 数组和字符串,DATA STRUCTURE,4.4.1 字符串ADT,字符串的定义 字符串(简称为串)是由n(0)个字符组成的有限序列。 S = “a0 a1 an-1” ( n0 ) 其中，S 是串名，单引号括起来的字符序列是串S的值。n 是串中字符个数，又称串长度，n=0的串称为空串。 要注意区分空串和空白串。 串中任意连续个字符组成的子序列称为该串的子串，包含子串的串称为主串。通常以子串的首字符在主串中的位置作为子串在主串中的位置。 S = “abcabcaabcbcde” P = “aabc”,DATA STRUCTURE,4.4.1 字符串ADT,字符串ADT ADT String 数据： 字符串是由n(0)个字符组成的有限序列 S = “a0a1an-1”，0 i n 。 运算： Create():建立一个空串。 Destroy():撤消一个串。 Length():返回当前串对象的长度。 Clear():置为空串。 Assign(S):串S的值赋给当前串对象。 Concat(b):将串b连接在当前串对象之后。,DATA STRUCTURE,4.4.1 字符串ADT,Insert(P,i):将串P插在当前串对象的位置i处。 Delete(i,len):从当前串对象的位置i起删除len个字符。 Substr(i,len):返回当前串对象中，从位置i开始的len个字符组成的子串。 Find(i,P):返回子串P在当前串对象中的位置。若当前串对象不包含串P，则返回-1。 ,DATA STRUCTURE,4.4.2 字符串的存储表示,顺序表示 串的顺序表示可用C+的一维字符数组来描述。 #include char s20=“cdabcde“； 链接表示,DATA STRUCTURE,4.4.2 字符串的存储表示,#include class String public: String(); String(const char *p); String() delete str; int Find(int i, String ,DATA STRUCTURE,4.4.2 字符串的存储表示,C语言中字符串操作函数 函数原型: char* strdup(const char* s) 函数功能: 字符串拷贝，目的空间由该函数分配 函数返回: 指向拷贝后的字符串指针 函数原型: char* strcpy(char* str1,char* str2); 函数功能: 把str2指向的字符串拷贝到str1中去 函数返回: 返回str1,即指向str1的指针 函数原型: char* strncpy(char* dest, const char* src，int count) 函数功能: 将字符串src中的count个字符拷贝到字符串dest中去 函数返回: 指向dest的指针 函数原型: unsigned int strlen(char* str); 函数功能: 统计字符串str中字符的个数(不包括终止符0) 函数返回: 返回字符串的长度.,DATA STRUCTURE,4.4.2 字符串的存储表示,C语言中字符串操作函数 函数原型: char* strchr(char* str,char ch); 函数功能: 找出str指向的字符串中第一次出现字符ch的位置 函数返回: 返回指向该位置的指针,如找不到,则返回空指针 函数原型: char* strrchr(const char *s, int c) 函数功能: 得到字符串s中最后一个含有c字符的位置指针 函数返回: 位置指针 函数原型: char* strstr(char* str1,char* str2); 函数功能: 找出str2字符串在str1字符串中第一次出现的位置(不包括str2的串结束符) 函数返回: 返回该位置的指针,如找不到,返回空指针 函数原型: char* strpbrk(const char* s1, const char* s2) 函数功能: 得到s1中第一个“同时也出现在s2中”字符的位置指针 函数返回: 位置指针,DATA STRUCTURE,4.4.2 字符串的存储表示,C语言中