数据结构——串和数组.ppt

3.6 其他线性结构,串(String)是由零个或多个字符组成的有限序列。一般记为: S=a1 a2 . an (n0) 其中，S是串的名，用单引号括起来的字符序列是串的值；ai(1in)可以是字母、数字或其它字符，串中字符的数目n称为串的长度。 n=0的串称为空串(null string)。,3.6.1 串的定义和串的存储方式概念,串中任意个连续的字符组成的子序列称为该串的子串。 包含子串的串相应地称为主串。 通常称字符在序列中的序号为该字符在串中的位置。 子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。 当两个串的长度相等，并且各个对应位置上的字符都相等时，称两个串相等。,3.6.1 串的定义和串的存储方式概念,例：串名为A、B、C、D的四个串如下： A=very good； 长度为9，是D的主串； B= ； 长度为3； C=； 长度为0（空串）； D=good； 长度为4，是A的子串。 D在A中的位置是6。,3.6.1 串的定义和串的存储方式概念,(1) 赋值操作：StrAssign(S，chars) 初始条件：chars是字符串常量； 操作结果：生成一个值等于chars的字符串S； (2) 插入操作：StrInsert(S，pos，T) 初始条件：字符串S、T存在， 1pos StrLength(S)+1； 操作结果：在字符串S的第pos个字符之前插入串T。,3.6.1 串的定义和串的存储方式基本操作,(3) 删除操作：StrDelete(S，pos，len) 初始条件：字符串S存在， 1pos StrLength(S)-len+1； 操作结果：从字符串S中删除第pos个字符起长度为len的子串。 (4) 复制操作：StrCopy(S，T) 初始条件：字符串S存在； 操作结果：将字符串S的内容复制到串T。,3.6.1 串的定义和串的存储方式基本操作,(5) 判空操作：StrEmpty(S) 初始条件：字符串S存在； 操作结果：若S为空串，则返回TRUE，否则返回FALSE。 (6) 比较操作：StrCompare(S，T) 初始条件：字符串S、T存在； 操作结果：若ST，则返回值0；若S=T，则返回值=0；若ST，则返回值0 。,3.6.1 串的定义和串的存储方式基本操作,(7) 求串长操作：StrLength(S) 初始条件：字符串S存在； 操作结果：返回字符串S的长度，即串S中字符的个数。 (8) 置空操作：StrClear(S) 初始条件：字符串S存在； 操作结果：将字符串S清为空串。,3.6.1 串的定义和串的存储方式基本操作,(9) 联接操作：StrCat(S，T) 初始条件：字符串S、T存在； 操作结果：将字符串T的值连接在S的后面。 (10) 求子串操作：SubString(Sub，S，pos，len) 初始条件：字符串S存在， 1posStrLength(S) 且1lenStrLength(S)-pos+1； 操作结果：用Sub返回字符串S的第pos个字符开始长度为len的子串。,3.6.1 串的定义和串的存储方式基本操作,(11) 定位操作：StrIndex(S，pos，T) 初始条件：字符串S、T存在，T非空， 1posStrLength(S)； 操作结果：若字符串S中存在与T相等的子串，则返回它在字符串S中第pos个字符之后第一次出现的位置；否则返回0。 (7) 置换操作：StrReplace(S，T，V) 初始条件：字符串S、T、V存在，T非空； 操作结果：用V替换字符串S中出现的所有与T相等的不重叠的子串。,3.6.1 串的定义和串的存储方式基本操作,(13) 释放操作：StrDestroy(S) 初始条件：字符串S存在； 操作结果：销毁字符串S。,3.6.1 串的定义和串的存储方式基本操作,串的两种基本存储结构：顺序存储结构和链式存储结构。 定长顺序串：当串的长度基本固定时，主要考虑采用顺序存储结构实现。其C语言描述如下： #define Maxlen 20 /串的最大长度 typedef struct /串的定义 char chMaxlen; int len; /串的长度 Sstring；,3.6.1 串的定义和串的存储方式串的存储结构,在进行串的插入时： 插入位置pos将原字符串划分为两部分(分别假设为A和B，长度分别为LA和LB)； 待插入字符串假设为C，其长度为LC； 插入过程可能出现下列三种情况： 1) 插入后串的总长度为LA+LB+LC Maxlen； 2) 插入后串的总长度Maxlen，且pos+LCMaxlen，且pos+LCMaxlen；,3.6.2 定长顺序串运算插入算法分析,/* 在串s中序号为pos的字符之前插入串t */ int StrInsert(SString *s, int pos, SString t) int i; if(poss-len) return(0); /* 插入位置不合法 */ if(s-len+t.lenlen+t.len-1; i=t.len+pos; i-) s-chi=s-chi-t.len; for(i=0; ichi+pos=t.chi; s-len=s-len+t.len; ,3.6.2 定长顺序串运算插入算法实现,else if(pos+t.lenMaxlen， 但串t的字符序列可以全部插入 */ for(i=Maxlen-1; i=t.len+pos; i-) s-chi=s-chi-t.len; for(i=0; ichi+pos=t.chi; s-len=Maxlen; else /* 串t的部分字符序列要舍弃 */ for(i=0; ichi+pos=t.chi; s-len=Maxlen; return(1); ,3.6.2 定长顺序串运算插入算法实现,int StrDelete(SString *s, int pos, int len) if(pos(s-len-len) return(0); for(i=pos+len; ilen; i+) s-chi-len=s-chi; s-len=s-len-len; return(1); ,3.6.2 定长顺序串运算删除算法实现,在进行串的连接时： 假设原字符串为A，长度为LA； 待连接串假设为B，其长度为LB； 连接过程可能出现下列三种情况： 1) 连接后串的总长度为LA+LB Maxlen； 2) 连接后串的总长度Maxlen，且LAMaxlen，LA=Maxlen；,3.6.2 定长顺序串运算连接算法分析,/* 将串t连接在串s的后面 */ int StrCat(SString *s, SString t) int i, flag; if(s-len+t.lenlen; ilen+t.len; i+) s-chi=t.chi-s-len; s-len=s-len+t.len; flag=1; ,3.6.2 定长顺序串运算连接算法实现,else if(s-lenMaxlen， 但串s的长度len; ichi=t.chi-s-len; s-len=Maxlen; flag=0; else flag=0; /* 串s的长度=Maxlen，串t不被连接 */ return(flag); ,3.6.2 定长顺序串运算连接算法实现,数组(array)可看成是线性表的推广，是最常用的数据结构之一。 数组是有限个数组元素的集合，元素数目固定； 数组的每个元素与一组下标相对应，数组元素的下标关系具有上下界的约束且下标有序； 数组中所有数组元素的数据类型必须一致； 数组的两种基本运算： 给定下标，存取相应的数据元素； 给定下标，修改相应的数据元素。,3.6.3 二维数组的结构特点和存储方式定义,一个m行n列的二维数组(也称为矩阵)，记作Am, n。,3.6.3 二维数组的结构特点和存储方式定义,A=,a11 a12 . a1n a21 a22 . a2n am1 am2 . amn,按行优先顺序存储 对于上述二维数组A而言，可以将其看成是由m个行向量组成的向量，即： Amn =(a11，.，a1n)，(a21，.，a2n)，.，(am1，.，amn) 这种行向量表相当于一个线性表。 行优先顺序存储就是数组元素按行向量表次序进行存储，即第i+1个行表紧跟在第i个行表后面进行存储。,3.6.3 二维数组的结构特点和存储方式存储结构,当把n维数组的元素按行优先顺序地存放在存储器里，则每个元素的存储地址可以用公式计算出来。这个计算公式称为“地址公式”。 假设每个数据元素占c个存储单元，则上述二维数组Amn的地址公式为： Loc(aij)= Loc(a11)+ (i-1)* n +(j-1) * c (1im，1jn),3.6.3 二维数组的结构特点和存储方式存储结构,按列优先顺序存储 对于上述二维数组A而言，也可以将其看成是由n个列向量组成的向量，即： Amn =(a11，.，am1)，(a12，.，am2)，.，(a1n，.，amn) 这种列向量表也相当于一个线性表。 列优先顺序存储就是数组元素按列向量表次序进行存储，即第i+1个列表紧跟在第i个列表后面进行存储。,3.6.3 二维数组的结构特点和存储方式存储结构,当把n维数组的元素按列优先顺序地存放在存储器里，并假设每个数据元素占c个存储单元，则上述二维数组Amn的地址公式为： Loc(aij)= Loc(a11)+ (j-1)* m +(i-1) * c (1im，1jn),3.6.3 二维数组的结构特点和存储方式存储结构,根据二维数组的特性可以推出：一个三维数组可以用其数据元素为二维数组的线性表来定义；依次类推，n维数组是由数据元素为n-1维数组的线性表构成。 因此，对n维数组也有上述两种不同顺序分配的存储结构。当把n维数组的元素这样顺序地存放在存储器里，则每个元素的存储地址都可以用“地址公式”计算出来。,3.6.3 二维数组的结构特点和存储方式存储结构,在C语言中，可以把一个二维数组看作是一种特殊的一维数组，该一维数组的元素又是一个一维数组。例如定义： int a34； 其中，可以把a看作是一个一维数组，它有3个元素：a0、a1、a2，每个元素又是一个包含4个元素的一维数组。,3.6.3 二维数组的结构特点和存储方式示例,通常在实际计算中经常出现一些阶数很高的矩阵，且矩阵中有许多值相同的元素或者零元素。 为了节省存储空间，可以对这类矩阵进行压缩存储。 所谓压缩存储是指：为多个值相同的元素只分配一个存储空间；对零元素不分配空间。,3.6.3 二维数组的结构特点特殊矩阵的存储方式,下三角矩阵的存储方式： 设下三角矩阵为Ann，满足：,3.6.3 二维数组的结构特点特殊矩阵的存储方式,A=,a11 0 0 a21 a22 0 an1 an2 ann,若将其中的非零元素按行优先顺序存放为： 则一维数组Sak和矩阵元素aij之间存在着一一对应关系： (1ji n),3.6.3 二维数组的结构特点特殊矩阵的存储方式,k=,+j,假设每个数据元素占用一个字节的存储单元，则下三角矩阵的地址公式为：,3.6.3 二维数组的结构特点特殊矩阵的存储方式,Loc(aij) = Loc(a11)+ i(i1)/ 2 +(j1),三对角矩阵的存储方式： 设三对角矩阵为Ann，满足：,3.6.3 二维数组的结构特点特殊矩阵的存储方式,A=,a11 a12 0 0 a21 a22 a23 0 0 0 a32 a33 a34 0 0 0 0 an-1,n-2 an-1,n-1 an-1,n 0 0 0 an,n-1 ann,若将其中的非零元素按行优先顺序存放，假设每个数据元素占用一个字节的存储单元，则三对角矩阵的地址公式为：,3.6.3 二维数组的结构特点特殊矩阵的存储方式,Loc(aij) = Loc(a11)+2(i1)+(j1) 其中：i=1, j=1, 2 或：i=n, j=n-1, n 或：1in, j=i-1, i, i+1,对称矩阵的存储方式： 解决方案类似于下三角矩阵的存储。,3.6.3 二维数组的结构特点特殊矩阵的存储方式,稀疏矩阵： 如果一个矩阵中大多数元素为零，非零元素较少且分布无一定规律，则称之为稀疏矩阵。 顺序存储： 三元组表：线性表中的每个结点由三个字段组成，分别是该非零元素的行下标、列下标和值。,3.6.3 二维数组的结构特点特殊矩阵的存储方式,稀疏矩阵的C语言表示： #define smax 16 /* 最大非零元素个数 */ typedef int datatype; typedef struct int i, j; /* 行号，列号 */ datatype v; /* 元素值 */ node;,3.6.3 二维数组的结构特点特殊矩阵的存储方式,稀疏矩阵的C语言表示： typedef struct int m, n, t; /* 行数，列数，非零元素个数 */ node datasmax; /* 三元组表 */ spmatrix; /* 稀疏矩阵类型 */,3.6.3 二维数组的结构特点特殊矩阵的存储方式,稀疏矩阵举例：非零元素按行优先顺序存储。,3.6.3 二维数组的结构特点特殊矩阵的存储方式,该稀疏矩阵共有20个元素，仅有6个非零元素。其三元组表如下图所示。,3.6.3 二维数组的结构特点特殊矩阵的存储方式,伪地址表示法： 伪地址是指本元素在矩阵中按行优先顺序的相对位置，上述稀疏矩阵A中非零元素为： 5，8，1，3，-2，6 非零元素的伪地址=n*i+j，n为矩阵的列数。 因此，5的伪地址为1；1的伪地址为5；。,3.6.3 二维数组的结构特点特殊矩阵的存储方式,3.6.3 二维数组的结构特点特殊矩阵的存储方式,spmatrix TRANSMAT(spmatrix a) /* 返回稀疏矩阵A的转置 */ int ano, bno, col; /* ano和bno分别指示a-data 和b-data中结点序号； col指示*a的列号，即*b的行号 */ pmatrix *b; /* 存放转置后的矩阵 */ b=malloc(sizeof(spmatrix); b-m=a-n; b-n=a-m; /*行列数交换*/ b-t=a-t;,3.6.3 二维数组的结构特点特殊矩阵的存储方式,if (b-t0) /* 有非零元素，则转置 */ bno=0; for(col=0; coln; col+) /*按*a的列序转置*/ for(ano=0; anot; ano+) /* 扫描整个三元组表 */ if (a-dataano.j=col) /* 列号为col则进行置换 */ b-databno.i=a-dataano.j; b-databno.j=a-dataano.i; b-databno.v=a-dataano.v;,3.6.3 二维数组的结构特点特殊矩阵的存储方式,bno+; /* b-data结点序号加1 */ return b; /* 返回转置结果指针 */ /* TRANSMAT */,3.6.3 二维数组的结构特点特殊矩阵的存储方式,该算法的时间主要耗费在col和ano的二重循环上，若A的列数为n，非零元素个数为t，则执行时间为(nt)，即与的列数和非零元素个数的乘积成正比。 而通常用二维数组表示矩阵时，其转置算法的执行时间是(mn)。 由于非零元素个数一般远远大于行数，因此，上述稀疏矩阵转置算法虽然节省了空间，但增加了转置的时间。,3.6.3 二维数组的结构特点特殊矩阵的存储方式,链式存储结构： 带行指针向量的单链表表示。 行指针向量 列值 ,3.6.3 二维数组的结构特点特殊矩阵的存储方式,十字链表结构：,3.6.3 二维数组的结构特点特殊矩阵的存储方式,设已知一个nn的上三角矩阵X，其上三角元素已按行序为主序连续存放在数组Y中。 请设计一个tran函数，将数组Y中元素按列为主序连续存放在数组Z中。,3.6.4 应用实例问题描述,A=,1 2 3 4 5 0 6 7 8 9 0 0 10 11 12 0 0 0 13 14 0 0 0 0 15,根据已知条件： Y=(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15) 期望得到的结果： Z=(1, 2, 6, 3, 7, 10, 4, 8, 11, 13, 5, 9, 12, 14, 15) 解题思路： 用i和j表示矩阵X中元素的行和列下标。用k表示数组Y中元素的下标。 初始值设为：i=1, j=1, k=1； 将yk=xi, j元素存放在zj*(j-1)/2+i中，且当一行没有结束时j+，否则i+并修改下一行元素的个数及i和j的值，直到k=n(n+1)/2为止。,3.6.4 应用实例算法分析,#include #define N 5 void tran(int y, int n, int z) int k, step=n, count=0, i=0, j=0; for(k=0; kn*(n+1)/2; k+) count+; zj*(j-1)/2+i=yk; if(count=step) step-; count=0; i+; j=i; else j+; ,3.6.4 应用实例算法实现,main( ) int xNN, yN*(N+1)/2, zN*(N+1)/2; int i, j, k=0, n=N; for(i=0; in; i+) for(j=0; jn; j+) xij=0; printf(“please input non zero data of Matrix:n); for(i=0; in; i+) for(j=i; jn; j+) scanf(“%d”, ,3.6.4 应用实例算法实现,for(i=0; in; i+) for(j=0; jn; j+) printf(“%4d”,xij); printf(“n”); for(i=0; in; i+) for(j=i; jn; j+) yk=xij; k+; for(i=0; in*(n+1)/2; i+) printf(“%4d”, yi); printf(“n”); tran(y, n, z); for(i=0; in*(n+1)/2; i+) printf(“%4d”, zi); printf(“n”); ,3.6.4 应用实例算法实现,问题描述 输入一个稀疏矩阵，要求： 将其转化为三元组的表示形式； 在三元组存储矩阵中查找值为x的结点，若x存在，则输出其位置，否则输出“不存在”提示信息。,3.6.5 稀疏矩阵压缩存储方式和简单运算实例,算法描述 稀疏矩阵用二维数组A进行存储； 三元组用结构体B表示； 将数组A中的非零元素及它所在的行、列下标按行优先顺序存在到B中； 在B中查找值为x的结点，若存在，则输出其位置；否则输出“不存在”提示信息。,3.6.5 稀疏矩阵压缩存储方式和简单运算实例,C语言源程序 #include #define Max 100 typedef int Elemtype; typedef struct int i, j; Elemtype v; Pnode;,3.6.5 稀疏矩阵压缩存储方式和简单运算实例,typedef struct int rows, cols, terms; Pnode dataMax+1; PMatrix; PMatrix B;,3.6.5 稀疏矩阵压缩存储方式和简单运算实例,void crt_matrix(int AMax, int m, int n) int i, j, k=1; for(i=1; i=m; i+) for(j=1; j=n; j+) if(Aij!=0) B.datak.i=i; B.datak.j=j; B.