数据结构5陈慧南-数组和字符串.ppt

第5讲 DATASTRUCTURE DATASTRUCTURE 第4章数组和字符串 DATASTRUCTURE 4 1 1数组ADT 数组的定义数组是下标index和值value组成的序对的集合 index value 一维数组 A 0 15 1 24 2 33 3 21 DATASTRUCTURE 4 1 1数组ADT 数组ADTADTArray 数据 下标index和元素值value组成的数据对集合 其中任意两个数据对的下标index各不相同 运算 Create 建立一个数组 Retrieve i 返回下标为i的元素值 Store i x 将下标为i的数据对的值置为x DATASTRUCTURE 4 1 2数组的顺序表示 一维数组的顺序表示loc a i loc a 0 i k i 0 1 2 n 1 基地址 loc a 0 每个元素占k个存储单元 templateA a0 a1 ai an 1 pA newT 100 然后赋值Tb1 pA i 获取第i个元素Tb2 pA i 获取第i个元素 DATASTRUCTURE 4 1 2数组的顺序表示 二维数组的顺序表示二维数组a m n 映射到一维的存储空间时有两种顺序 行优先和列优先 大多数语言如PASCAL BASIC C C 等都是按行优先顺序存储的 FORTRAN是按列优先顺序存储的 A m n 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 行优先的存储方法 DATASTRUCTURE 4 1 2数组的顺序表示 二维数组的顺序表示loc a i j loc a 0 0 i n j k 0 i m 0 j n 基地址 loc a 0 0 每个元素占k个存储单元 DATASTRUCTURE 4 1 2数组的顺序表示 C C 中申请二维数组的方法 introw 3 col 4 方法1 intMtrx row col 1 2 3 4 5 6 7 8 9 10 11 12 方法2 int ppMtrx newint row for inti 0 i row i ppMtrx i newint col intn 0 for i 0 i row i for intj 0 j col j ppMtrx i j n for i 0 i row i delete ppMtrx i delete ppMtrx DATASTRUCTURE 4 1 2数组的顺序表示 方法3 definerow3 definecol4typedefintMtrx row main intn 0 Mtrx pMtrx newMtrx col 用法与二维数组相同for inti 0 i row i for intj 0 j col j pMtrx i j n delete pMtrx 定义二维数组 将数组定义为数据类型 DATASTRUCTURE 4 1 2数组的顺序表示 多维数组的顺序表示推广到多维数组a m1 m2 mn 数组元素a i1 i2 in 的存储地址为 loc a i1 i2 in loc a 0 0 i1 m2 m3 mn i2 m3 m4 mn in 1 mn in k DATASTRUCTURE 4 1 3一维数组的C 类 用C 的模板类定义的一维数组抽象数据类型 公有成员函数包括 构造函数析构函数重载下标操作符 重载下标操作符用来返回指向第i个元素的引用重载数组赋值 赋值操作符实现数组的整体赋值 DATASTRUCTURE 4 1 3一维数组的C 类 includetemplateclassArray1D public Array1D intsz 0 Array1D delete elements T 取元素值 整体赋值 缺少拷贝构造函数 DATASTRUCTURE 4 1 3一维数组的C 类 构造函数 申请数组空间templateArray1D Array1D intsz assert sz 0 越界检查size sz elements newT sz 运算符 获取第i个元素templateT DATASTRUCTURE 4 1 3一维数组的C 类 重载运算符 templateArray1D DATASTRUCTURE 4 1 3一维数组的C 类 重载流运算符 和istream DATASTRUCTURE main中测试该类的效果 include array1d h main Array1Da 5 b 8 Array1Dc 采用缺省长度0cin a cout b cout b b cout c c cout a 0 a 0 b 5 b 5 endl c b cout c b c c b a cout b a b b 4 1 3一维数组的C 类 DATASTRUCTURE 1C 中有关数组的类 classArray public Array intsize 0 char ptr NULL defaultconstructorArray constArray DATASTRUCTURE 1C 中有关数组的类 Array Array intsize char ptr NULL m ptr NULL SetArray size ptr Array Array constArray 浅拷贝 要改成深拷贝 DATASTRUCTURE 1C 中有关数组的类 include includemain charstr 9 strcpy str Software 注意 此处不能用char str Software 因为这样的字符串是只读的 Arrayar1 8 str Arrayar2 ar1 调用拷贝构造函数 其中调用了SetArray str 0 6 改变数组内容cout ar1 getPtr cout ar2 getPtr endl 输出 6oftware6oftware 浅拷贝的后果 DATASTRUCTURE 1C 中有关数组的类 voidArray SetArray intsize char ptr if size 0 ptr NULL return if m ptr NULL delete m ptr 释放原数组m size size m ptr newchar size 申请新的空间strncpy m ptr ptr size 拷贝 输出 Software6oftware DATASTRUCTURE 第4章数组和字符串 DATASTRUCTURE 4 2 1对称矩阵 对称矩阵和三角矩阵在n n的矩阵A中 若aij aji 0 i j n 则称其为n阶对称矩阵 对于对称矩阵 可以只存储上三角 或下三角 中的元素 包括对角线上的元素 DATASTRUCTURE 4 2 1对称矩阵 如果采用二维数组 n维对称矩阵的元素为n2 如果只存储三角中元素 则元素个数为n n 1 2其中行列序号与元素序号的对应关系 DATASTRUCTURE 第4章数组和字符串 DATASTRUCTURE 4 3 1稀疏矩阵ADT 稀疏矩阵大多数元素为零的矩阵称为稀疏矩阵 对于稀疏矩阵可只存非零元素 DATASTRUCTURE 4 3 1稀疏矩阵ADT 稀疏矩阵ADTADTSparseMatrix 数据 绝大多数元素为零的矩阵 运算 Create 建立一个稀疏矩阵 Destroy 撤消一个稀疏矩阵 Add B C 当前矩阵对象与B相加 C中返回相加和 Mul B C 当前矩阵对象与B相乘 C中返回相乘积 Transpose B B中返回当前矩阵对象的转置矩阵 DATASTRUCTURE 4 3 1稀疏矩阵ADT includetemplateclassSparseMatrix public SparseMatrix intmaxRowSize intmaxColSize SparseMatrix virtualvoidAdd constSparseMatrix 稀疏矩阵的C 类 DATASTRUCTURE 4 3 2稀疏矩阵的顺序表示 三元组表示法按照压缩存储的思想 稀疏矩阵Am n中的每一个非零元素aij的值 行号和列号可以用一个三元组 i j v 表示 三元组可以按行或按列的顺序存储 三元组的Term类templatestructTerms introw col Tvalue DATASTRUCTURE 4 3 2稀疏矩阵的顺序表示 0016 0322 05 16 1112 123 23 8 4091 6215 DATASTRUCTURE 4 3 2稀疏矩阵的顺序表示 includetemplateclassSeqTriple public SeqTriple intmSize SeqTriple delete trip voidAdd constSeqTriple 行三元组表的C 类 DATASTRUCTURE 第4章数组和字符串 DATASTRUCTURE 4 4 1字符串ADT 字符串的定义字符串 简称为串 是由n 0 个字符组成的有限序列 S a0a1 an 1 n 0 其中 S是串名 单引号括起来的字符序列是串S的值 n是串中字符个数 又称串长度 n 0的串称为空串 要注意区分空串和空白串 串中任意连续个字符组成的子序列称为该串的子串 包含子串的串称为主串 通常以子串的首字符在主串中的位置作为子串在主串中的位置 S abcabcaabcbcde P aabc DATASTRUCTURE 4 4 1字符串ADT 字符串ADTADTString 数据 字符串是由n 0 个字符组成的有限序列S a0a1 an 1 0 i n 运算 Create 建立一个空串 Destroy 撤消一个串 Length 返回当前串对象的长度 Clear 置为空串 Assign S 串S的值赋给当前串对象 Concat b 将串b连接在当前串对象之后 DATASTRUCTURE 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 DATASTRUCTURE 4 4 2字符串的存储表示 顺序表示串的顺序表示可用C 的一维字符数组来描述 includechars 20 cdabcde 链接表示 DATASTRUCTURE 4 4 2字符串的存储表示 includeclassString public String String constchar p String delete str intFind inti String DATASTRUCTURE 4 4 2字符串的存储表示 C语言中字符串操作函数函数原型 char strdup constchar s 函数功能 字符串拷贝 目的空间由该函数分配函数返回 指向拷贝后的字符串指针函数原型 char strcpy char str1 char str2 函数功能 把str2指向的字符串拷贝到str1中去函数返回 返回str1 即指向str1的指针函数原型 char strncpy char dest constchar src intcount 函数功能 将字符串src中的count个字符拷贝到字符串dest中去函数返回 指向dest的指针函数原型 unsignedintstrlen char str 函数功能 统计字符串str中字符的个数 不包括终止符 0 函数返回 返回字符串的长度 DATASTRUCTURE 4 4 2字符串的存储表示 C语言中字符串操作函数函数原型 char strchr char str charch 函数功能 找出str指向的字符串中第一次出现字符ch的位置函数返回 返回指向该位置的指针 如找不到 则返回空指针函数原型 char strrchr constchar s intc 函数功能 得到字符串s中最后一个含有c字符的位置指针函数返回 位置指针函数原型 char strstr char str1 char str2 函数功能 找出str2字符串在str1字符串中第一次出现的位置 不包括str2的串结束符 函数返回 返回该位置的指针 如找不到 返回空指针函数原型 char strpbrk constchar s1 constchar s2 函数功能 得到s1中第一个 同时也出现在s2中 字符的位置指针函数返回 位置指针 DATASTRUCTURE 4 4 2字符串的存储表示 C语言中字符串操作函数函数原型 char strnset char s intch size tn 函数功能 将字符串s中前n个字符设置为ch的值函数返回 指向s的指针函数原型 char strset char s intch 函数功能 将字符串s中所有字符设置为ch的值函数返回 指向s的指针函数原型 char strupr char s 函数功能 将字符串s中的字符变为大写函数返回 指向s的指针函数原型 char strlwr char s 函数功能 将字符串中的字符变为小写字符函数返回 指向s的指针 DATASTRUCTURE 4 4 2字符串的存储表示 C语言中字符串操作函数还有 intm