数据结构第四章
第四章数组和串
数组
数组的定义及其基本操作
数组的存贮结构
特殊矩阵的压缩存储
稀疏矩阵的压缩存储
数组的定义及其基本操作
数组的定义：数组（Array）：是n(n>1)个相同类型的数据元素a0 , a1 , …,an-1构成的有限序列，且该有限序列存储在块地址连续的内存单元中。（即物理存储与逻辑结构相一致）?数组中的数据元素数目固定。
?数组中的每个数据元素具有相同的数据类型。
?数组中的每个数据元素都和一组唯一的下标值相对应。
?数组是一种随机存储结构，可随机存取数组中的任意数据元素。
?地址计算：一维数组同线性表相同；
计算公式：Loc(ai) = Loc(a0) + i*k (0<= i 注：Loc(a0) 是a0元素的地址，Loc(ai)是ai元素的地址，k是每个元素所占的存储单元数。 二维数组 设m行n列的二维数组Am*n，有 地址计算： 1、按行序列序计算： Loc( aij)=Loc(a11)+[(i-1)n+(j-1)]*l 注：k是每个元素所占的单元数。 2、按列序序列计算： Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l 数组的基本操作 1. arraylength(D) 2. Storage(D, i, x) 3. Get(D, i, x) 数组的存储结构 数组一般在计算机中采用线性结构存储，对于一维数组同线性表相同；关于二维数组和多维数组，一般语言中采用行序列序，即先存第一（或零）行，然后第二行依次存储。 数组也允许有两种存储分配方法：静态和动态。 ?静态数组：运行期间数组大小不能改变，需预先给出。 ?动态数组：可以动态建立和动态撤消的数组。 动态数组： 一维动态数组 int *a; a=(int *)malloc(n*sizeof(int)); a[0]…a[n-1] free(a); 二维动态数组 int **a,i; a=(int **)malloc(row *sizeof(int *)); for (i=0;i a[i]=(int *)malloc(col*sizeof(int)); 释放空间free(a)? for(i=0;i free(a[i]); free(a); 特殊矩阵的压缩存储 *特殊矩阵 1、对称矩阵的压缩存储 对称矩阵 ?定义：设n 阶方阵中的元素关于主对角线对称，即满足条件：aij = aji 1<=i , j <=n, 这样的方阵称为n阶对称方阵。 ?存储方法：只存储矩阵中上三角或下三角中的元素，这样可以将n2个元素压缩存储到n(n+1)/2个元素。即用一维数组a[n*(n+1)/2]来存储该矩阵，一维数组中的元素同二维数组.元素的对应关系： i(i-1)/2+j-1 当 i>=j 时 k= j(j-1)/2+i-1 当 j>i 时 则[n(n+1)/2]为n 阶对称方阵的压缩存储（下三角存储即用行序列序）。 2、 n 阶下三角矩阵 3、对角矩阵 Loc(aij)=Loc(a11)+2(i-1)+(j-1) 4、稀疏矩阵的压缩存储 定义：非零元较零元少，且分布没有一定规律的矩阵 假设在m*n 的矩阵中，有t 个元素不为零，令 ，称 为矩阵的稀疏因子。通常 认为 ≤0.05时称为稀疏矩阵。 稀疏矩阵M 和T M 由{(1,2,12), (1,3,9), (3,1,-3), (3,6,14), (4,3,24), (5,2,18), (6,1,15), (6,4,-7) } 和矩阵维数（6,7）唯一确定 n m t *=δδδ *压缩储存 稀疏矩阵的压缩存储方法是只存非零元素，但由于稀疏矩阵元素中的非零元素是没有规律的，所以在存储时还必须存储每个元素的行下标和列下标值。这样稀疏矩阵中的每一个非零元素需由一个三元组(i,j,aij)唯一确定。 稀疏矩阵的压缩存储方法：链式存储结构——三元组十字链表 稀疏矩阵的三元组也可采用链式存储结构。单链表结构， 缺点：操作复杂度高——由链表的非随机存取特性限定的。 十字链表 *设行指针数组和列指针数组，分别指向每行、列第一个非零元 *结点定义 typedef struct node { int row,col,val; struct node *down, *right; }JD; 从键盘接收信息建立十字链表算法 1、初始化头指针向量 2、初始化各行列链表 3、动态生成结点，输入非零元 4、将结点插入行 5、将结点插入列 Status CreateSMatrix_OL(CrossList &M) { //创建稀疏矩阵M。采用十字链表存储表示 if (M) free(M); ｛ scanf(&m,&n,&t); //输入M的行数、列数和非零元个数 M.mu=m; M.nu=n; M.tu=t; if (!(M.rhead=(Olink *) malloc ((m+1)*sizeof(Olink)))) exit (overflow); if (!(M.chead=(Olink *) malloc ((n+1)*sizeof(Olink)))) exit (overflow); M.rhead[ ]=M.chead[ ]=NULL; //初始化行列头指针向量； //各行列链表为空链表 for (scanf(&i,&j,&e); i!=0;scanf(&i,&j,&e)) { //按任意次序输入非零元 if (!(p=(OLNode *) malloc (sizeof(OLNode)))) exit (overflow); p->I=I; p->j=j; p->e=e; //生成结点 If (M.rhead[I]==NULL || M.rhead[I]->j>j) { p->right=M.rhead[I];M.rhead[I]=p; } Else { //寻查在行表中的插入位置 for (q=M.rhead[I]; (q->right)&&q->right->j ｛p->right=q->right; q->right=p;｝ } //完成行插入 If (M.chead[j]==NULL || M.chead[j]->i>i) { p->down=M.chead[j];M.chead[j]=p; } Else { //寻查在列表中的插入位置 for (q=M.chead[j]; (q->down)&&q->down->i p->down=q->down; q->down=p; } //完成列插入 ｝//for } //if Return OK; }//CreateSMatrix_OL 稀疏矩阵的压缩存储方法：顺序存储结构——三元组顺序表 三元顺序表的定义 typedef struct { int i,j; Elemtype e; }Triple; typedef struct{ Triple data[MAXSIZE+1]; int mu,nu,tu; }TSMatrix; TSMatrix M; 矩阵运算 矩阵运算通常包括：矩阵转置、矩阵加、矩阵减、矩阵乘、矩阵求逆等。 求矩阵的转置运算（最简单的运算） 对于一个m*n的矩阵A m*n，其转置矩阵是一个n*m的矩阵，为B n*m，满足a ij = b ji , 要实现三元组顺序表的转置，只要实现以下两点： 第一点：把矩阵中元素的下标转置后，送入矩阵中； 第二点：对矩阵中的元素按行序列序进行排序。 方法一：按M的列序转置 即按T.data中三元组次序依次在M.data中找到相应的三元组进行转置。为找到M中每一列所有非零元素，需对其三元组表M.data从第一行起扫描一遍。由于M.data中以M行序为主序,所以由此得到的恰是T.data中应有的顺序 算法： Status TransposeSMatrix(TSMatrix M, TSMatrix &T) { T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if (T.tu) { q=1; for (col=1; col<=M.nu; ++col) for (p=1; p<=M.tu; ++p) if (M.data[p].j==col) { T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i; T.data[q].e=M.data[p].e; ++q; } } return OK; } 方法二：稀疏矩阵的快速转置 算法思想是：以M矩阵的三元组为中心, 依次取出 M.data 中的每一个三元组，交换行列后，直接将其写入T.data合适的位置中。 实现：引入两辅助数组 num[col]：存储矩阵M中第col列中非零元个数 cpot[col]：存储M中第col列第一个非零元在T.data中位置 显然有： 算法描述： Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) { T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if (T.tu) { for (col=1; col<=M.nu; ++col) num[col]=0; for (t=1; t<=M.tu; ++t) ++num[M.data[t].j]; cpot[1]=1; for (col=2; col<=M.nu; ++col) cpot[col]=cpot[col-1]+num[col-1]; for (p=1; p<=M.tu; ++p) { col=M.data[p].j; q=cpot[col]; T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i; T.data[q].e=M.data[p].e; ++cpot[col]; } } return OK; } 求矩阵乘运算 行逻辑链接的顺序表：有时为了方便某些矩阵运算，我们在按行优先存储的三元组中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置。当将行表作为三元组表的一个新增属性加以描述时，我们就得到了稀疏矩阵的另一种顺序存储结构：“带行链接信息”的三元组表。 其类型描述如下： #define maxsize 100 typedef struct{ triple data[maxsize+1];//非零元三元组表 int rpos[maxrc+1]; //各行第一个非零元的位置表 int n,m,t; //矩阵的行数、列数和非零元个数 }TSMatrix; 下面讨论两个稀疏矩阵相乘的例子，容易看出这种表示方法的优越性。 若设Q=M*N 其中，M是m1*n1矩阵，N是m2*n2矩阵。 常规的二维数组表示时转置的算法： 当n1=m2时,有： for(i=1;i<=m1;++i) for(j=1;j<=n2;++j) { q[i][j]=0； for(k=1;k<=n1;++k) q[i][j]+=m[i][k]*n[k][j]； } 此算法的复杂度为O(m1*n1*n2)。 行逻辑链接的顺序表从M和N求得Q 1、求乘积矩阵Q中元素 由矩阵乘法规则知： Q（i，j）=M(i,1)×N(1,j)+M(i,2)×N(2,j)+…+M(i,n)×N(n,j) 这就是说，为求Q的值，只有M(i,k)与N(k,j)（即M元素的列与N元素的行相等的两项）才有相乘的机会，且当两项都不为零时，乘积中的这一项才不为零。 即只找到M.data中的j值和N.data中的i值相等的各对元素相乘即可。 2、相乘的基本操作是：对于M中每个元素M.data[p]，找到N中所有满足条件M.data[p].j=N.data[q].i的元素N.data[q]，求得M.data[p].e和M.data[q].e的乘积。 为了便于N.data中寻找N中的第row行第一个非零元素，与前面类似，在此需引入num 和rpos两个向量。num[row]表示矩阵N中第row行的非零元素的个数；rpos[row]表示第row行的第一个非零元素在N.data中的位置。于是有 rpos[1]=1 rpos[row]=rpos[row-1]+num[row-1] 2≤row≤n 3、根据以上分析，稀疏矩阵的乘法运算的粗略步骤如下： ⑴初始化。清理一些单元，准备按行顺序存放乘积矩阵; ⑵求N的num，rpos; ⑶做矩阵乘法。将M.data中三元组的列值与N.data中三元组的行值相等的非零元素相乘，并将具有相同下标的乘积元素相加。 例如： 算法描述： Status MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix &Q) { //求矩阵乘积Q=M* N，采用行逻辑链接存储。设M.nu=N.mu if (M.nu != N.mu) return ERROR; if (M.tu*N.tu != 0) { // Q是非零矩阵 Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0; p=1 // Q初始化 do { crow=M.data[p].i; //crow指示当前处理的行号 ctemp[] = 0; // 当前行各元素累加器清零 while (p<=M.tu && M.data[p].i==crow) { brow=M.data[p].j; //找到对应元在N中的行号 for (q=N.rpos[brow]; q { ccol = N.data[q].j; // 乘积元素在Q中列号 ctemp[ccol] += M.data[p].e * N.data[q].e; } // for q ++p; }//求得Q中第crow行的非零元 for (ccol=1; ccol<=Q.nu; ++ccol) // 压缩存储该行非零元 ｛ if (ctemp[ccol]) { ++Q.tu; Q.data[Q.tu] = (crow, ccol, ctemp[ccol]); } // if ｝ } // do while (p<=M.tu); } // if return OK; } // MultSMatrix 相乘算法的时间复杂度就相当于O (m×p)。 求矩阵加运算 算法思路：假设非空指针pa和pb分别指向矩阵A和B中行值相同的两个结点： 则主要处理过程为： 1、若pa==NULL或pa->j>pb->j，则需要在A矩阵的链表中插入一个值为bij的结点。此时，需改变同一行中前一结点的right域值，以及同一列中前一结点的down域值。 2、若pa->j 3、若pa->j==pb->j且pa->e+pb->e!=0，则只要将aij+bij的值送到pa所指结点的e域即可，其他所有域的值都不变。 4、若pa->j==pb->j且pa->e+pb->e==0，则需要在A矩阵的链表中删除pa所指的结点。此时，需改变同一行中前一结点的right域值，以及同一列中前一结点的down域值。 广义表 广义表的概念： 广义表也称为列表，是线性表的一种扩展，也是数据元素的有限序列。记作：LS= (d0, d1, d2, . . . . . .dn-1)。其中di既可以是单个元素，也可以是广义表。 说明 1）广义表的定义是一个递归定义，因为在描述广义表时又用到了广义表； 2）在线性表中数据元素是单个元素，而在广义表中，元素可以是单个元素, 称为单元素(原子)，也可以是广义表，称为广义表的子表； 3）n 是广义表长度； 4）下面是一些广义表的例子 A = ( ) 空表，表长为0； B = (a,(b,c,d)) B的表长为2，两个元素分别为a 和子表（b,c,d)； C = (e) C中只有一个元素e，表长为1； D = (A,B,C,f ) D 的表长为4，它的前三个元素A，B，C 广义表,第四个f 是单 元素； E=( a ,E ) 递归表. 5）若广义表不空，则可分成表头和表尾，反之，一对表头和表尾可唯一确定广义表 对非空广义表：称第一个元素为L的表头，其余元素组成的表称为LS的表尾； B = (a,(b,c,d)) 表头：a 表尾((b,c,d)) 即HEAD（B）=a, TAIL(B)=((b,c,d)), C = (e) 表头：e 表尾( ) 运算可以嵌套，如： HEAD（TAIL（B））=b, TAIL(TAIL(B))=(c, d) 。 广义表的元素之间除了存在次序关系外，还存在层次关系。如： 广义表的存储结构 由于广义表中数据元素可以具有不同结构，故难以用顺序结构表示广义表。通常采用链表存储方式 如何设定链表结点？广义表中的数据元素可能为单元素(原子)或子表，由此需要两种结点：一种是表结点，用以表示广义表；一种是单元素结点，用以表示单元素（原子）。 按结点形式的不同，广义表的链式存储结构又可以分为不同的两种存储方式。一种称为头尾表示法，另一种称为孩子兄弟表示法。 ⒈头尾表示法 ⒉孩子兄弟表示法 广义表链表结点的类型定义如下： Typedef struct GLNode { int tag; //标志域：用于区分原子结点和表结点 union { int atom; //原子结点的值域 struct GLNode *hp; //表结点的表头指针域， }; struct GLNode *tp; //指向下一个元素的指针 }*GList; 广义表的基本操作的递归算法 广义表是递归结构，所以广义表的许多操作可以用递归算法实现求广义表的深度int depth(NODE *head) 广义表 L= (α1, α2。。。αn) 的深度=广义表中括号重数 串 本章主要内容: 1、串的基本概念 2、串的存储结构 3、串的基本操作 4、串的模式匹配算法 5、串的应用----文本编辑 本章重点：串的存储与基本操作。 本章难点：串基本操作的灵活使用。 串的基本概念 串的定义： 串（或字符串）（String）是由零个或多个字符组成的有限序列。一般记作 s=〃s0s1s2…sn-1〃(n≥0) 其中：s为串名，用双引号括起来的字符序列是串的值；si(0≤i≤n-1)可以是字 母、数字或其它字符；双引号为串值的定界符，不是串的一部分；字符串字符的 数目n称为串的长度。零个字符的串称为空串，通常以两个相邻的双引号来表示空 串，如：s=〃〃，它的长度为零；仅由空格组成的的串称为空格串，如：s=〃└┘〃；若串中含有空格，在计算串长时，空格应计入串的长度中，如： s=〃I’m a student〃的长度为13。 请读者注意，在C语言中，用单引号引起来的单个字符与单个字符的串是不同的，如s1=＇a＇与s2=〃a〃两者是不同的，s1表示字符，而s2表示字符串。 串的基本操作 对于串的基本操作，许多高级语言均提供了相应的运算或标准库函数来实现。下面仅介绍几种在C语言中常用的串运算，其它的串操作见的文件。 定义下列几个变量： char s1[20]=“dirtreeformat”,s2[20]=“file.mem”; char s3[30],*p; int result; （1）串复制 strcpy(str1,str2) 赋值：把str2指向的字符串拷贝到str1中，返回str1。 库函数和形参说明如下： char * strcpy(char * str1,char * str2) 例如：strcpy(s3,s1); //s3=“dirtreeformat” (2) 求串长 strlen(str) 求字符串的长度：统计字符串str中字符的个数（不包括＇\0＇），返回字符的个数，若str为空串，则返回值为0。 库函数和形参说明如下： unsigned int strlen(char *str) 例如：printf(“%d”,strlen(s1)); 输出13 (3)串比较 c函数：int strcmp(char s1,char s2); 该函数比较串s1和串s2的大小，当返回值小于0，等于0或大于0时分别表示 s1 例如：result=strcmp(“baker”,”Baker”) result>0 result=strcmp(“12”,”12”); result=0 result=strcmp(“Joe”,”Joseph”); result<0 (4)串联接 char strcat(char *to,char *from) 该函数将串from复制到串to的末尾，并且返回一个指向串to的开 始处的指针。 例如：strcat(s3,”/”) strcat(s3,s2); //s3=“dirtreeformat/file.mem” （5）字符定位 char strchr(char *s,char c); 该函数是在串s中寻找字符c第一次出现的位置，若找到则返回该 位置，否则返回NULL。 例如：p=strchr(s2,”.”); p 指向“file”之后的位置 （6）求子串 substr(s,t,i, k) 求子串的过程即为复制字符序列的过程，将串S中的第i个字符开始长度为k的字符串。 0<=i （7）置换 Replace(s,t,v) 若主串s中存在与串t相等的子串则用v替换主串。 （8）插入 insert(s,i,t) 若0<=I<=length(s)，则在串s的第i个字符之前插入串t。 自定义函数和形参说明如下： Void insstr(char *str1,int m,char *str2) （9）删除 delete(s,i,k) 从串s中删除从第i个字符开始的长度为k的串， 自定义函数和形参说明如下： Void delete(char *str,int m,int n) 串的存储结构 对串的存储方式取决于我们对串所进行的运算，如果在程序设计语言中，串的运算只是作为输入或输出的常量出现，则此时只需存储该串的字符序列，这就是串值的存储。此外，一个字符序列还可赋给一个串变量，操作运算时通过串变量名访问串值。实现串名到串值的访问，在C语言中可以有两种方式：一是可以将串定义为字符型数组，数组名就是串名，串的存储空间分配在编译时完成，程序运行时不能更改。这种方式为串的静态存储结构。另 一种是定义字符指针变量，存储串值的首地址，通过字符指针变量名访问串值，串的存储空间分是在程序运行时动态分配的，这种方式称为串的动态存储结构。 串值的存储 我们称串是一种特殊的线性表，因此串的存储结构表示也有两种方法：静态存储采用顺序存储结构，动态存储采用的是链式存储和堆存储结构。 1．串的静态存储结构 类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。由于一个字符只占1个字节，而现在大多数计算机的存储器地址是采用的字编址，一个字（即一个存储单元）占多个字节，因此顺序存储结构方式： typedef struct { char str[MAXNUM]; int length; /*串长度*/ } String; /* 串类型定义*/ typedef struct { char *str; int maxlength; int length; /*串长度*/ } String; /* 串类型定义*/ 2．串的动态存储结构 我们知道，串的各种运算与串的存储结构有着很大的关系，在随机取子串时，顺序存储方式操作起来比较方便，而对串进行插入、删除等操作时，就会变得很复杂。因此，有必要采用串的动态存储方式。 串的动态存储方式采用链式存储结构和堆存储结构两种形式： （1）链式存储结构 串的链式存储结构中每个结点包含字符域和结点链接指针域，字符域用于存放字符，指针域用于存放指向下一个结点的指针，因此，串可用单链表表示。 用链表存放字符串时，其结构用C语言定义如下： typedef struct node{ char str; struct node *next; } SCharNode; 用单链表存放串，每个结点仅存储一个字符，如图1所示，因此，每个结点的指针域所占空间比字符域所占空间要大得多。为了提高空间的利用率，我们可以使每个结点存放多个字符，称为块链结构，如图2所示每个结点存放4个字符。 串基本操作的实现算法 本小节中，我们将讨论串值在静态存储方式和动态存储方式下，其运算如何实现。 如前所述，串的存储可以是静态的，也可以是动态的。静态存储在程序编译时就分配了存储空间，而动态存储只能在程序执行时才分配存储空间。不论在哪种方式下，都能实现串的基本运算。本节讨论求子串运算在三种存储方式下的实现方法。 一、C语言中字符串的静态数组结构定义如下： #define MaxSize 80 typedef struct { char str[MaxSize ]; int length; /*串长度*/ } String; /* 串类型定义*/ 1、初始化操作 void Initiate(String *S) {S->length=0;} 2、插入子串操作 (在串S的pos位置插入子串T) int Insert(String *S, int pos, String T) { int i; if(pos<0||pos>S->length ) { printf(“参数出错”)；return 0;} else if (S->length+T.length>=MaxSize) { printf(“not enough space”)；return 0; } else { for(i=S->length-1;i>=pos;i--) S->str[i+T.length]=S->str[i]; /*依次后移元素*/ for(i=0;i S->str[pos+i]=T.str[i]; S->length= S->length+ T.length; S->str[S->length]=‘\0’; return 1; } 3、删除子串操作(在串S的pos位置删除子串T) int Ｄelete(String *S, int pos, int len) { int i; if(pos<0||len<0||pos+len>S->length|| S->length<=0) { printf(“参数出错或S为空串”)；return 0; } for(i=pos+len;i< S->length;i++) S->str[i-len]=S->str[i]; /*依次前移元素*/ S->length= S->length-len; S->str[S->length]=…\0?; return 1; } 4、求子串 求主串S中第pos个字符起，长度为len的子串T，操作成功，则返回1；否则返回0。算法如下 int substring(String S, int pos, int len, String * T) {int i; if(pos<0||len<0||pos+len>S.length) {printf(“参数错误”);return 0;} for(i=0;i T->str[i]=S.str[pos+i]; T->length=len; T->str[len]=…\0?; /*置结束标记*/ return 1; } 二、动态数组下定义： typedef struct{ char *str; int maxlength; int length; } DString; １、初始化 void Initiate(DString *S, int max, char *string) {int i; S->str=(char*)malloc(sizeof(char)*max); S->maxLength=max; S->length=strlen(string); for(i=0;i S->str[i]=string[i]; S->str[i]=…\0?; /*赋串值*/ } 2、插入子串操作(在串S的pos位置插入子串T) int Insert(String *S, int pos, String T) { int i; char *p; if(pos<0||pos>S->length) {printf(“参数出错”)；return 0;} if(S->length+T.length>=MaxLength) { p=(char*)realloc(S->str, (S->length+T.length+1)*sizeof(char)) if(p==NULL) {printf(“内存不足”)；return 0;} S->str=p; S-> MaxLength= S->length+T.length+1; } for(i=S->length-1;i>=pos;i--) S->str[i+T.length]=S->str[i]; /*依次后移元素*/ for(i=0;i S->str[pos+i]=T.str[i]; S->length= S->length+ T.length; S->str[S->length]=…\0?; return 1; } 3、删除子串操作(在串S的pos位置删除子串T) int Delete(String *S, int pos, int len) {int i; if(pos<0||len<0||pos+len>S->length|| S->length<=0) {printf(“参数出错或为空串”)；return 0;} for(i=pos+len;i< S->length;i++) S->str[i-len]=S->str[i]; /*依次前移元素*/ S->length= S->length-len; S->str[S->length]=…\0?; return 1; } 串的模式匹配算法 (1) 求子串位置的定位函数 子串的定位操作index(s, t, start) 通常称作串的模式匹配（其中t 被称为模式串），是各种串处理系统中最重要的操作之一。 s=“abcdef”, t=“cde” in dex(s, t, 0)=2, index( s, t, 1)=2, t=“ab” index( s, t, 0)=0 t=“ad” index( s, t, 0)=-1 (2) BF 算法 该算法的基本思想是，在主串s 中从第i ( i 的初值为start)个字符起，并且长度和t 串相等的子串和t 比较，若相等，则找到, 否则i 增1 ，直至串s 中不存在从i 开始和t 相等的子串为止。 Ｂrute-Force算法设计如下： int Bfindex(String S, int start, String T) {int i= start, j=0, v; while(i { if(S.str[i]==T.str[j]) {i++; j++;} else {i=i-j+1; j=0; } } if(j==T.length) v=i-T.length;else v=-1; return v; 第四章习题（P111-113） 一、复习题 1、试述数据和数据结构的概念及其区别。 数据是对客观事物的符号表示，是信息的载体；数据结构则是指互相之间存在着一种或多种关系的数据元素的集合。（P93） 2、列出算法的五个重要特征并对其进行说明。 算法具有以下五个重要的特征：有穷性：一个算法必须保证执行有限步之后结束。确切性：算法的每一步骤必须有确切的定义。输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件。输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法没有实际意义。可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。（P95） 3、算法的优劣用什么来衡量试述如何设计出优秀的算法。 时间复杂度空间复杂度（P97-98） 4、线性和非线性结构各包含哪些种类的数据结构线性结构和非线性结构各有什么特点 线性结构用于描述一对一的相互关系，即结构中元素之间只有最基本的联系，线性结构的特点是逻辑结构简单。所谓非线性结构是指，在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。树型和图型结构就是其中十分重要的非线性结构，可以用来描述客观世界中广泛存在的层次结构和网状结构的关系。（P99-105） 5、简述树与二叉树的区别；简述树与图的区别。 树用来描述层次结构，是一对多或多对一的关系；二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。二叉树是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。图也称做网，是一种比树形结构更复杂的非线性结构。在图中，任意两个节点之间都可能相关，即节点之间的邻接关系可以是任意的，图表示的多对多的关系。（P102-P104） 6、请举出遍历算法在实际中使用的例子。 提示：根据实际生活中需要逐个访问处理的情况举例。 7、编写一个算法，统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验证这个算法。 提示：根据查找算法和串中求子串的算法，查找输入串中以单个字符形式的子串。 8、若对有n个元素的有序顺序表和无序顺序表进行顺序搜索，试就下列三种情况分别讨论两者在等搜索概率时的平均搜索长度是否相同 (1) 搜索失败； (2) 搜索成功，且表中只有一个关键码等于给定值k的对象； (3) 搜索成功，且表中有若干个关键码等于给定值k的对象，要求一次搜索找出所有对象。 第 4 章广义线性表——多维数组和广义表 2005-07-14 第 4 章广义线性表——多维数组和广义表 课后习题讲解 1. 填空 ⑴数组通常只有两种运算：（）和（），这决定了数组通常采用（）结构来实现存储。 【解答】存取，修改，顺序存储 【分析】数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。除了初始化和销毁之外，在数组中通常只有存取和修改两种操作。 ⑵二维数组A中行下标从10到20，列下标从5到10，按行优先存储，每个元素占4个存储单元，A[10][5]的存储地址是1000，则元素A[15][10]的存储地址是（）。 【解答】1140 【分析】数组A中每行共有6个元素，元素A[15][10]的前面共存储了(15-10)×6+5个元素，每个元素占4个存储单元，所以，其存储地址是1000+140=1140。 ⑶设有一个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其存储地址为d，每个元素占1个存储单元，则元素A[8][5]的存储地址为（）。 【解答】d+41 【分析】元素A[8][5]的前面共存储了(1+2+…+8)+5=41个元素。 ⑷稀疏矩阵一般压缩存储方法有两种，分别是（）和（）。 【解答】三元组顺序表，十字链表 ⑸广义表((a), (((b),c)),(d))的长度是（），深度是（），表头是（），表尾是（）。【解答】3，4，(a)，((((b),c)),(d)) ⑹已知广义表LS=(a，(b，c，d)，e)，用Head和Tail函数取出LS中原子b的运算是（）。 【解答】Head(Head(Tail(LS))) 2. 选择题 ⑴二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8，列下标的范围是从0~9，则存放A至少需要（）个字节，A的第8列和第5行共占（）个字节，若A按行优先方式存储，元素A[8][5]的起始地址与当A按列优先方式存储时的（）元素的起始地址一致。 A 90 B 180 C 240 D 540 E 108 F 114 G 54 H A[8][5] I A[3][10] J A[5][8] K A[4][9] 【解答】D，E，K 【分析】数组A为9行10列，共有90个元素，所以，存放A至少需要90×6=540个存储单元，第8列 11． 写算法，实现顺序串的基本操作 StrReplace(&s,t,v) r1 中第 index 个字符起求出首次与串 r2 相同的子串的起始位置。 写一个函数将顺序串 s1 中的第 i 个字符到第 j 个字符之间的字符用 s2 串替换。 写算法，实现顺序串的基本操作 StrCompare(s,t) 。 第四章习题 1. 设 s=' I AM A STUDENT , t= ' GOO D, q=' WORKER 给出下列操作的结果: StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1); StrIndex(s, ' A ' ,4); StrReplace(s, ' STUDEN 'T,q); StrCat(StrCat(sub1,t), StrCat(sub2,q)); 2. 编写算法，实现串的基本操作 StrReplace(S,T,V) 。 3. 假设以块链结构表示串，块的大小为 1，且附设头结点。 试编写算法，实现串的下列基本操作： StrAsign(S,chars) ； StrCopy(S,T) ； StrCompare(S,T) ； StrLength(S) ； StrCat(S,T) ； SubString(Sub,S,pos,len) 。 4． 叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变 量的值。 5． 已知：S=”(xyz)* ” ,T= ”(x+z)*y ”。试利用联接、求子串和置换等操作，将 S 转换为T. 6． S 和T 是用结点大小为1的单链表存储的两个串，设计一个算法将串 S 中首次与T 匹配的子串逆 置。 7． S 是用结点大小为4的单链表存储的串，分别编写算法在第k 个字符后插入串T ,及从第k 个字符 删除 len 个字符。 以下算法用定长顺序串： 8． 编写下列算法： 1) 将顺序串 r 中所有值为 ch1 的字符换成 ch2 的字符。 2) 将顺序串 r 中所有字符按照相反的次序仍存放在 r 中。 3) 从顺序串 r 中删除其值等于 ch 的所有字符。 5) 从顺序串 r 中删除所有与串 r1 相同的子串。 从顺序串 9． 10． 第四章串 重点难点 理解"串"类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作；掌握串类型的各种存储表示方法；理解串的两种匹配算法。 典型例题 1、简述下列每对术语的区别： 空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；【解】 （1）空串是指不包含任何字符的串，它的长度为零。 空白串是指包含一个或多个空格的串，空格也是字符。 （2）串常量是指在程序中只可引用但不可改变其值的串。 串变量是可以在运行中改变其值的。 （3）主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。 （4）静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。 动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。 2、以HString为存储表示，写一个求子串的算法。 【解】HString 是指以动态分配顺序串为存储表示，其定义为： typedef struct { char *ch; int length; }HString; void *substr( HString *sub,HString *s,int pos,int len) {//用sub返回串s的第pos个字符起长度为len的子串。sub初始时为一空串 //pos的合法位置为0<=pos<=s->length-1 int i; if (pos<0||pos>s->length-1||len<=0) Error("parameter error!");//参数不合法，子串为空串 if (s->length 第四章 一、简述下列每对术语的区别： 空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。 答： ●空串是指不包含任何字符的串，它的长度为零。 空白串是指包含一个或多个空格的串，空格也是字符。 ●串常量是指在程序中只可引用但不可改变其值的串。 串变量是可以在运行中改变其值的。 ●主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。 ●静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。 动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。 ●目标串和模式串:在串匹配运算过程中，将主串称为目标串，而将需要匹配的子串称为模式串，两者是相对的。 ●有效位移和无效位移：在串定位运算中，模式串从目标的首位开始向右位移，每一次合法位移后如果模式串与目标中相应的字符相同，则这次位移就是有效位移(也就是从此位置开始的匹配成功)，反之，若有不相同的字符存在，则此次位移就是无效位移(也就是从此位置开始的匹配失败)。 二、假设有如下的串说明： char s1[30]="Stocktom,CA", s2[30]="March 5 1999", s3[30], *p; (1)在执行如下的每个语句后p的值是什么? p=stchr(s1,'t'); p=strchr(s2,'9'); p=strchr(s2,'6'); (2)在执行下列语句后，s3的值是什么? strcpy(s3,s1); strcat(s3,","); strcat(s3,s2); (3)调用函数strcmp(s1,s2)的返回值是什么? 第四章空间数据的处理 学习要求：掌握数据处理的基本内容、途径和算法。 §4.1 矢量数据拓扑关系的自动建立 矢量数据拓扑关系在空间数据的查询与分析中非常重要，矢量数据拓扑关系自动建立的算法是GIS中的关键算法之一，这里介绍其实现的基本步骤和要点： 一、链的组织 找出在链的中间相交，而不是在端点相交的情况，自动切成新链；把链按一定顺序存储，然后把链按顺序编号。 二、结点匹配 结点匹配是指把一定限差内的链的端点作为一个结点，其坐标值取多个端点的平均值。 三、检查多边形是否闭合 检查多边形是否闭合可以通过判断一条链的端点是否有与之匹配的端点来进行。 四、建立多边形 建立多边形是矢量数据自动拓扑中最关键的部分，由于其算法比较复杂。先介绍了几个基本概念：顺时针方向构多边形、最靠右边的链、多边形面积的计算，然后介绍其实现的过程。 五、岛的判断 论述多边形之间的一种关系。岛的判断即指找出多边形互相包含的情况，也即寻找多边形的连通边界。 六、确定多边形的属性 多边形以内点标识。内点的属性常赋于多边形。 §4.2 矢量数据的图形编辑 图形编辑是纠正数据采集错误的重要手段，其基本的功能要求是：具有友好的人机界面；具有对几何数据和属性编码的修改功能；具有分层显示和窗口功能。图形编辑的关键是点、线、面的捕捉。 一、点的捕捉 图形编辑是纠正数据采集错误的重要手段。点的捕捉就是计算机屏幕上进行图形编辑时如何根据光标的位置找到需要编辑的要素点。 1、点的捕捉 图4-2-1 图4-2-2 但是由于在计算d时需进行乘方运算，所以影响了搜索的速度，因此，把距离d的计算改为： 二、线的捕捉 线的捕捉就是计算机屏幕上进行图形编辑时如何根据光标的位置找到需要编辑的线。方法是计算点到直线的距离。 图4-2-3 图 4-2-4 图4-2-5 如图4-2-5所示，点S(x,y)到直线段(x 1,y 1 ),(x 2 ,y 2 )的距离d的计算公 式为： 数据结构第四章 第四章习题 1. 设s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’。给出下列操作的结果： StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1); StrIndex(s,’A’,4); StrReplace(s,’STUDENT’,q); StrCat(StrCat(sub1,t), StrCat(sub2,q)); 2. 编写算法，实现串的基本操作StrReplace(S,T,V)。 3. 假设以块链结构表示串，块的大小为1，且附设头结点。 试编写算法，实现串的下列基本操作： StrAsign(S,chars)； StrCopy(S,T)； StrCompare(S,T)； StrLength(S)； StrCat(S,T)； SubString(Sub,S,pos,len)。 4．叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。 5．已知：S=”(xyz)*”,T=”(x+z)*y”。试利用联接、求子串和置换等操作，将S转换为T. 6．S和T是用结点大小为1的单链表存储的两个串，设计一个算法将串S中首次与T匹配的子串逆置。 7．S是用结点大小为4的单链表存储的串,分别编写算法在第k个字符后插入串T，及从第k个字符删除len个字符。 以下算法用定长顺序串： 8．编写下列算法： （1）将顺序串r中所有值为ch1的字符换成ch2的字符。 （2）将顺序串r中所有字符按照相反的次序仍存放在r中。 （3）从顺序串r中删除其值等于ch的所有字符。 （4）从顺序串r1中第index 个字符起求出首次与串r2相同的子串的起始位置。 （5）从顺序串r中删除所有与串r1相同的子串。 9．写一个函数将顺序串s1中的第i个字符到第j个字符之间的字符用s2串替换。 10．写算法，实现顺序串的基本操作StrCompare(s,t)。 11．写算法，实现顺序串的基本操作StrReplace(&s,t,v)。 实习题 1．已知串S和T，试以以下两种方式编写算法，求得所有包含在S中而不包含在T中的字符构成的新串R，以及新串R中每个字符在串S中第一次出现的位置。 （1）利用CONCAT、LEN、SUB和EQUAL四种基本运算来实现。 （2）以顺序串作为存储结构来实现。 2．编写一个行编辑程序EDLINE，完成以下功能： （1）显示若干行：list [[n1]-[n2]]：显示第n1行到第n2行，n1缺省时，从第一行开始，n2缺省时，到最后一行， 读书破万卷下笔如有神 《一定能摸到红球吗？》说课稿 林银花 教材说明：一、１、课题：《一定能摸到红球吗？》 ２、本节内容的地位和作用 在现代社会中，人们面临着更多的机会和选择，常常需要在不确定情境中作出合理的决策,概率正是通过对不确定现象和事件发生的可能性的刻画,来为人们更好的制定决策提供依据和建议.本节内容又是 义务教育阶段,唯一培养学生从不确定的角度来观察世界的数学内容,让学生了解可能性是普遍的,有助于他们理解社会,适应生活. ３、教学目标设计： (１)认知目标： （Ａ）经历猜测．实验．收集与分析试验结果等过程 （Ｂ）体会事件的发生的不确定性知道事情发生的可能性有多大。 （２）、能力目标： (Ａ)经历游戏等的活动过程，初步认识确定事件和不确定事件 （Ｂ）在与其它人交流的过程中，能合理清晰地表达自己的思维过程； （３）、情感目标： （Ａ）通过创设游戏情境，让学生主动参与，做“数学实验”，激发学生学习的热情和兴趣，激活学生思维。 （Ｂ）在与他人的合作过程中，增强互相帮助、团结协作的精神。 （Ｃ）体会到在生活中我们可以从确定和不确定两方面分析一件事情. ４、本课重点、难点分析： 学习的重点是初步体验事情发生的确定性和不确定性. 学习的难点是确定事件发生的可能性大小. 学习本节知识应注意猜测,试验,收集与分析实验结果,从中体会事件发生的可能性及大小. 二、教学对象分析： 1、初一学生性格开朗活泼，对新鲜事物特别敏感，且较易接受，因此，教学过程中创设的问题情境应较生动活泼，直观形象，且贴近学生的生活，从而引起学生的有意注意。 2、初一学生的概括能力较弱，推理能力还有待不断发展，所以在教学时，可让学生充分试验, 收集，分析,帮助他们直观形象地感知。 一、判断题 （第一章绪论） 1.数据元素是数据的最小单元。 答案：错误 2.一个数据结构是由一个逻辑结构和这个逻辑结构上的基本运算集构成的整体。 答案：错误 3.数据的存储结构是数据元素之间的逻辑关系和逻辑结构在计算机存储器内的映像。 答案：正确 4.数据的逻辑结构是描述元素之间的逻辑关系，它是依赖于计算机的。 答案：错误 5.用语句频度来表示算法的时间复杂度的最大好处是可以独立于计算机的软硬件，分析算法的时间 答案：正确 （第二章线性表） 6.取顺序存储线性表的第i个元素的时间同i的大小有关。 答案：错误 7.线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。 答案：正确 8.线性链表的每一个节点都恰好包含一个指针域。 答案：错误 9.顺序存储方式的优点的存储密度大，插入和删除效率不如练市存储方式好。 答案：正确 10.插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。答案：错误 （第三章栈） 11.栈是一种对进栈和出栈作了限制的线性表。 答案：错误 12.在C（或C++）语言中设顺序栈的长度为MAXLEN，则top=MAXLEN表示栈满。答案：错误 13.链栈与顺序栈相比，其特点之一是通常不会出现满栈的情况。 答案：正确 14.空栈就是所有元素都为0上的栈。 答案：错误 15.将十进制数转换为二进制数是栈的典型应用之一。 答案：正确 （第四章队列） 16.队列式限制在两端进行操作的线性表。 答案：正确 17.判断顺序队列为空的标准是头指针和尾指针都指向同一结点。 答案：错误 18.在循环链列队中无溢出现像。 答案：错误 19.在循环队列中，若尾指针rear大于头指针front，则元素个数为rear-front。 答案：正确 20.顺序队列和循环队列关于队满和队空的判断条件是一样的。 答案：错误 （第五章串） 21.串是n个字母的有限序列。 答案：错误 22.串的堆分配存储是一种动态存储结构。 练习 4 1.空间数据处理（融合、合并、剪切、交叉、合并） 2.设置地图投影及投影变换 空间数据处理 (1) 第1步裁剪要素 (2) 第2步拼接图层 (3) 第3步要素融合 (4) 第4步图层合并 (6) 第5步图层相交 (7) 定义地图投影 (9) 第6步定义投影 (9) 第7步投影变换――地理坐标系－>北京1954坐标系转换－>西安80坐标系 (10) 补充：图层相减，计算面积 (11) 空间数据处理 ●数据：云南县界.shp; Clip.shp西双版纳森林覆盖.shp 西双版纳县界.shp ●步骤： 将所需要的数据下载后，解压到到 e:\gisdata, 设定工作区:在ArcMap中 执行菜单命令：<工具>－><选项>，在“空间处理”选项页里，点 击“环境变量”按钮，在环境变量对话框 中的常规设置选项中，设定“临时工作空 间”为 e:\gisdata 第1步 裁剪要素 ◆在ArcMap中，添数据GISDATA\云南县界.shp，添加数据GISDATA\Clip.shp （Clip 中有四 个要素） ◆激活Clip图层。选中Clip图层中的一个要素，注意确保不要选中“云南县界”中的要素！ 点击打开ArcToolbox， 指定输出要素类路径及名称，这里请命名 为“云南县界_Clip1” 指定输入类：云南县界 指定剪切要素：Clip（必须是多边形要素） 依次选中Clip主题中其它三个要素，重复以上的操作步骤， 完成操作后将得到共四个图层（“云南县界_Clip1” , “云南县界_Clip2”，“云南县界_Clip3”，“云南县界_Clip4” ）。 第2步 拼接图层 ◆在ArcMap中新建地图文档，加载你在剪切要素操作中得到的 四个图层 ◆点击打开ArcToolbox 第四章空间数据与数据质量 空间数据是对现实世界对象(地理特征)的空间信息和专题属性信息描述，它具有诸如数据量巨大，结构复杂多样、操作是计算密集型的，具有自相关性等特征。空间数据是地理信息系统不可缺少的组成部分，其质量在很大程度上影响和制约着地理信息系统的可用性，为地理信息系统用户提供满足质量要求的空间数据是地理信息系统建设的关键任务之一。 4.1空间数据 4.1.1空间数据的来源 地理信息系统的数据源是指建立地理信息系统数据库所需要的各种类型数据的来源。地理信息系统的数据源是多种多样的，并随系统功能的不同而不同，通常包括以下几种： （1）地图数据：各种类型的地图是GIS最主要的数据源，因为地图是地理数据的传统描述形式，是具有共同参考坐标系统的点、线、面的二维平面形式的表示，内容丰富，图上实体间的空间关系直观，而且实体的类别或属性可以用各种不同的符号加以识别和表示。 （2）遥感数据：遥感数据是GIS中一个极其重要的信息源。通过遥感影象可以快速、准确地获得大面积的、综合的各种专题信息，航天遥感影象还可以取得周期性的资料，这些都为GIS提供了丰富的信息。 （3）测量数据：测量数据主要指使用大地测量、GPS、城市测量、摄影测量和其他一些测量方法直接量测所得到的测量对象的空间位置信息。各种实测数据特别是一些GPS点位数据、地籍测量数据常常是GIS的一个很准确和很现势的资料。（4）国民经济的各种统计数据常常也是GIS的数据源。如人口数量、人口构成、国民生产总值等等。各种文字报告和立法文件在一些管理类的GIS系统中，有很大的应用，如在城市规划管理信息系统中，各种城市管理法规及规划报告在规划管理工作中起着很大的作用。 4.1.2空间数据的基本特征 地理数据一般具有三个基本特征：属性特征（非定位数据）,描述空间对象的特性，即是什么，如对象的类别、等级、名称、数量等。空间特征（定位数据）：描述空间对象的地理位置以及相互关系，又称几何特征和拓扑特征，前者用经纬度、坐标表示，后者如交通学院与电力学院相邻等。时间特征（时间尺度）：指现象或物体随时间的变化，其变化的周期有超短期的、短期的、中期的、长期的 《一定能摸到红球吗？》说课稿 林银花 一、教材说明： １、课题：《一定能摸到红球吗？》 ２、本节内容的地位和作用 在现代社会中，人们面临着更多的机会和选择，常常需要在不确定情境中作出合理的决策,概率正是通过对不确定现象和事件发生的可能性的刻画,来为人们更好的制定决策提供依据和建议.本节内容又是义务教育阶段,唯一培养学生从不确定的角度来观察世界的数学内容,让学生了解可能性是普遍的,有助于他们理解社会,适应生活. ３、教学目标设计： (１)认知目标： （Ａ）经历猜测．实验．收集与分析试验结果等过程 （Ｂ）体会事件的发生的不确定性知道事情发生的可能性有多大。 （２）、能力目标： (Ａ)经历游戏等的活动过程，初步认识确定事件和不确定事件 （Ｂ）在与其它人交流的过程中，能合理清晰地表达自己的思维过程； （３）、情感目标： （Ａ）通过创设游戏情境，让学生主动参与，做“数学实验”，激发学生学习的热情和兴趣，激活学生思维。 （Ｂ）在与他人的合作过程中，增强互相帮助、团结协作的精神。 （Ｃ）体会到在生活中我们可以从确定和不确定两方面分析一件事情. ４、本课重点、难点分析： 学习的重点是初步体验事情发生的确定性和不确定性. 学习的难点是确定事件发生的可能性大小. 学习本节知识应注意猜测,试验,收集与分析实验结果,从中体会事件发生的可能性及大小. 二、教学对象分析： 1、初一学生性格开朗活泼，对新鲜事物特别敏感，且较易接受，因此，教学过程中创设的问题情境应较生动活泼，直观形象，且贴近学生的生活，从而引起学生的有意注意。 2、初一学生的概括能力较弱，推理能力还有待不断发展，所以在教学时，可让学生充分试验,收集，分析,帮助他们直观形象地感知。 3、初一学生已经具备了一定的学习能力，所以本节课中，应多为学生创造自主学习、 第四章空间数据库 第一节数据库概述 数据库技术是60年代初开始发展起来的一门数据管理自动化的综合性新技术。数据库的应用领域相当广泛，从一般事务处理，到各种专门化数据的存储与管理，都可以建立不同类型的数据库。建立数据库不仅仅是为了保存数据，扩展人的记忆，而主要是为了帮助人们去管理和控制与这些数据相关联的事物。地理信息系统中的数据库就是一种专门化的数据库，由于这类数据库具有明显的空间特征，所以有人把它称为空间数据库，空间数据库的理论与方法是地理信息系统的核心问题。 一、数据库的定义 数据库就是为了一定的目的，在计算机系统中以特定的结构组织、存储和应用的相关联的数据集合。 计算机对数据的管理经过了三个阶段—最早的程序管理阶段，后来的文件管理阶段，现在的数据库管理阶段。其中，数据库是数据管理的高级阶段，它与传统的数据管理相比有许多明显的差别，其中主要的有两点：一是数据独立于应用程序而集中管理，实现了数据共享，减少了数据冗余，提高了数据的效益；二是在数据间建立了联系，从而使数据库能反映出现实世界中信息的联系。 地理信息系统的数据库(以下称为空间数据库)是某区域内关于一定地理要素特征的数据集合。空间数据库与一般数据库相比，具有以下特点： (1) 数据量特别大，地理系统是一个复杂的综合体，要用数据来描述各种地理要素，尤其是要素的空间位置，其数据量往往大得惊人。即使是一个很小区域的数据库也是如此。 (2) 不仅有地理要素的属性数据(与一般数据库中的数据性质相似)，还有大量的空间数据，即描述地理要素空间分布位置的数据，并且这两种数据之间具有不可分割的联系。 （3) 数据应用的面相当广，如地理研究、环境保护、土地利用与规划、资源开发、生态环境、市政管理、道路建设等等。 上述特点，尤其是第二点，决定了在建立空间数据库时，一方面应该遵循和应用通用数据库的原理和方法，另一方面又必须采取一些特殊的技术和方法来解决其它数据库所没有的管理空间数据的问题。 第四章串 一、选择题 1．下面关于串的的叙述中，哪一个是不正确的（）【北方交通大学2001 一、5（2分）】A．串是字符的有限序列B．空串是由空格构成的串 C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储 2 若串S1=‘ABCDEFG’, S2=‘9898’,S3=‘###’,S4=‘012345’,执行 concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2))) 其结果为（）【北方交通大学1999 一、5 （25/7分）】 A．ABC###G0123 B．ABCD###2345 C．ABC###G2345 D．ABC###2345 E．ABC###G1234 F．ABCD###1234 G．ABC###01234 ~ 3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A．求子串B．联接C．匹配D．求串长 【北京邮电大学2000 二、4（20/8分）】【西安电子科技大学1996 一、1 （2分）】 4．已知串S=‘aaab’,其Next数组值为（）。【西安电子科技大学1996 一、7 （2分）】A．0123 B．1123 C．1231 D．1211 5．串‘ababaaababaa’的next数组为（）。【中山大学1999 一、7】 A．0 B．012121111212 C．0 D．0 6．字符串‘ababaabab’的nextval 为（） A．(0,1,0,1,04,1,0,1) B．(0,1,0,1,0,2,1,0,1) C．(0,1,0,1,0,0,0,1,1) D．(0,1,0,1,0,1,0,1,1 ) , 【北京邮电大学1999 一、1（2分）】 7．模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（），nextval数组的值为（）。 A．0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B．0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2 C．0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D．0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2 E．0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F．0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1 【北京邮电大学1998 二、3 （2分）】 8．若串S=’software’,其子串的数目是（）。【西安电子科技大学2001应用一、2（2分）】A．8 B．37 C．36 D．9 9．设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S 本身）的个数为（）。【中科院计算所1997 】 A．2n-1 B．n2 C．(n2/2)+(n/2) D．(n2/2)+(n/2)-1 E. (n2/2)-(n/2)-1 F.其他情况 、 10．串的长度是指（）【北京工商大学2001 一、6 （3分）】 A．串中所含不同字母的个数B．串中所含字符的个数 C．串中所含不同字符的个数D．串中所含非空格字符的个数 二、判断题 1．KMP算法的特点是在模式匹配时指示主串的指针不会变小。（）【北京邮电大学2002 一、4 （1分）】 2．设模式串的长度为m,目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（）【长沙铁道学院1998 一、1 (1分)】 3．串是一种数据对象和操作都特殊的线性表。（）【大连海事大学2001 1、L (1分)】 二、填空题 ) 1．空格串是指__(1)__，其长度等于___(2)__。【西安电子科技大学2001软件一、4（2分）】 2．组成串的数据元素只能是________。【中山大学1998 一、5 （1分）】 3．一个字符串中________称为该串的子串。【华中理工大学2000 一、3（1分）】 4．INDEX（‘DATASTRUCTURE’，‘STR’）=________。【福州大学1998 二、4 (2分)】 第四章习题 1. 设s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’。给出下列操作的结果： StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1); StrIndex(s,’A’,4); StrReplace(s,’STUDENT’,q); StrCat(StrCat(sub1,t), StrCat(sub2,q)); 2. 编写算法，实现串的基本操作StrReplace(S,T,V)。 3. 假设以块链结构表示串，块的大小为1，且附设头结点。 试编写算法，实现串的下列基本操作： StrAsign(S,chars)；StrCopy(S,T)；StrCompare(S,T)；StrLength(S)； StrCat(S,T)；SubString(Sub,S,pos,len)。 4．叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。 5．已知：S=”(xyz)*”,T=”(x+z)*y”。试利用联接、求子串和置换等操作，将S转换为T. 6．S和T是用结点大小为1的单链表存储的两个串，设计一个算法将串S中首次与T匹配的子串逆置。 7．S是用结点大小为4的单链表存储的串,分别编写算法在第k个字符后插入串T，及从第k个字符删除len个字符。 以下算法用定长顺序串： 8．编写下列算法： （1）将顺序串r中所有值为ch1的字符换成ch2的字符。 （2）将顺序串r中所有字符按照相反的次序仍存放在r中。 （3）从顺序串r中删除其值等于ch的所有字符。 （4）从顺序串r1中第index 个字符起求出首次与串r2相同的子串的起始位置。 （5）从顺序串r中删除所有与串r1相同的子串。 9．写一个函数将顺序串s1中的第i个字符到第j个字符之间的字符用s2串替换。 10．写算法，实现顺序串的基本操作StrCompare(s,t)。 11．写算法，实现顺序串的基本操作StrReplace(&s,t,v)。 实习题 1．已知串S和T，试以以下两种方式编写算法，求得所有包含在S中而不包含在T中的字符构成的新串R，以及新串R中每个字符在串S中第一次出现的位置。 （1）利用CONCAT、LEN、SUB和EQUAL四种基本运算来实现。 （2）以顺序串作为存储结构来实现。 2．编写一个行编辑程序EDLINE，完成以下功能： 数据结构练习第四章串 一、选择题 1．函数substr(“DATASTRUCTURE”，5，9)的返回值为（）。 A. “STRUCTURE” B.“DATA” C. “ASTRUCTUR” D. “DATASTRUCTURE” 2．字符串的长度是指（）。 A. 串中不同字符的个数 B. 串中不同字母的个数 C. 串中所含字符的个数 D. 串中不同数字的个数 3．两个字符串相等的充要条件是（）。 A. 两个字符串的长度相等 B. 两个字符串中对应位置上的字符相等 C. 同时具备(A)和(B)两个条件 D. 以上答案都不对 4．关于串的叙述中，正确的是（） A．空串是只含有零个字符的串 B.空串是只含有空格字符的串 C.空串是含有零个字符或含有空格字符的串 D.串是含有一个或多个字符的有穷序列 5．下面关于串的的叙述中，哪一个是不正确的？（） A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 6．设有两个串S1和S2，求S2在S1中首次出现的位置的运算称作( ) A．求子串 B.判断是否相等 C．模型匹配 D.连接 7．若串S=’software’,其子串的数目是( )。 A．8 B．37 C．36 D．9 8．串的长度是指（） A．串中所含不同字母的个数 B．串中所含字符的个数 C．串中所含不同字符的个数 D．串中所含非空格字符的个数 9．串是一种特殊的线性表，其特殊性体现在( )。 A．数据元素是一个字符 B. 可以顺序存储 C. 数据元素可以是多个字符 D. 可以链接存储 10．下面关于串的的叙述中，哪一个是不正确的（B） A. 串是字符的有限序列 B. 空串是由空格构成的串 C. 模式匹配是串的一种重要运算 D. 串既可以采用顺序存储，也可以采用链式存储 11．若串＝‘software’，其非平凡子串（非空且不同于串本身）的数目是（C）A. 8 B. 37 C. 35 D. 9 12．串是一种特殊的线性表，其特殊性体现在（B） A. 可以顺序存储 B. 数组元素是一个字符 C. 可以连续存储 D. 数据元素可以是多个字符 13. 下面关于串的的叙述中，哪一个是不正确的？（B） 第四章串 注：子串的定义是：串中任意个连续的字符组成的子序列，并规定空串 是任意串的子串，任意串是其自身的子串。若字符串长度为n（n>0），长 为n的子串有1个，长为n-1的子串有2个，长为n-2的子串有3个，……， 长为1的子串有n个。由于空串是任何串的子串，所以本题的答案为：8* （8+1）/2+1=37。故选B。但某些教科书上认为“空串是任意串的子串” 无意义，所以认为选C。为避免考试中的二意性，编者认为第9题出得好。 二、判断题 三．填空题 1．(1) 由空格字符（ASCII值32）所组成的字符串 (2)空格个数 2．字符 3．任意个连续的字符组成的子序列4．5 5.O(m+n) 6．01122312 7．01010421 8．(1)模式匹配 (2)模式串 9．(1)其数据元素都是字符(2)顺序存储(3)和链式存储(4)串的长度相等且 两串中对应位置的字符也相等 10．两串的长度相等且两串中对应位置的字符也相等。 11．’xyxyxywwy’ 12．*s++=*t++ 或（*s++=*t++）!=‘\0’ 13．（1）char s[ ] (2) j++ (3) i >= j 14．[题目分析]本题算法采用顺序存储结构求串s和串t的最大公共子串。 串s用i指针（1<=i<=s.len）。t串用j指针（1<=j<=t.len）。算法思想 是对每个i（1<=i<=s.len，即程序中第一个WHILE循环），来求从i开始 的连续字符串与从j（1<=j<=t.len，即程序中第二个ＷHILE循环）开始的 连续字符串的最大匹配。程序中第三个（即最内层）的WHILE循环，是当 s中某字符（s［i］）与t中某字符（t［j］）相等时，求出局部公共子串。 若该子串长度大于已求出的最长公共子串（初始为０），则最长公共子串的 长度要修改。 程序（a）：（1）（i+k<=s.len）AND(j+k<=t.len) AND(s[i+k]=t[j+k]) //如果在s和t的长度内，对应字符相等，则指针k 后 移（加1）。 8．请用SQL的GRANT 和REVOKE语句(加上视图机制)完成以下授权定义或存取控制功能: ( a ）用户王明对两个表有SELECT 权力。 GRANT SELECT ON 职工,部门 TO 王明 ( b ）用户李勇对两个表有INSERT 和DELETE 权力。 GRANT INSERT,DELETE ON 职工,部门 TO 李勇 ( c ) 每个职工只对自己的记录有SELECT 权力。 GRANT SELECT ON 职工 WHEN USER()=NAME TO ALL; ( d ）用户刘星对职工表有SELECT 权力，对工资字段具有更新权力。 GRANT SELECT,UPDATE(工资) ON 职工 TO 刘星 ( e ）用户张新具有修改这两个表的结构的权力。 GRANT ALTER TABLE ON 职工,部门 TO 张新; ( f ）用户周平具有对两个表所有权力（读，插，改，删数据），并具有给其他用户授权的权力。 GRANT ALL PRIVILIGES ON 职工,部门 TO 周平 WITH GRANT OPTION; ( g ）用户杨兰具有从每个部门职工中SELECT 最高工资、最低工资、平均工资的权力，他不能查看每个人的工资。 CREATE VIEW 部门工资AS SELECT 部门.名称,MAX(工资),MIN(工资),AVG(工资) FROM 职工,部门 WHERE 职工.部门号=部门.部门号 GROUP BY 职工.部门号 GRANT SELECT ON 部门工资 TO 杨兰; 9 ．把习题8 中（1）---（7）的每一种情况，撤销各用户所授予的权力 (1) REVOKE SELECT ON 职工，部门FROM 王明； (2) REVOKE INSERT , DELETE ON 职工，部门FROM 李勇； (3) REOVKE SELECT ON 职工 WHEN USER ( ) =NAME FROM ALI ; (4) REVOKE SELECT , UPDATE ON 职工 FROM 刘星； (5) REVOKE ALTER TABLE ON 职工，部门 FROM 张新； (6) REVOKE ALL PRIVILIGES ON 职工，部门 第四章串 任意串是其自身的子串。若字符串长度为n（n>0），长为n的子串有1个，长为n-1的子串有2个，长为n-2的子串有3个，……，长为1的子串有n个。由于空串是任何串的子串，所以本题的答案为：8*（8+1）/2+1=37。故选B。但某些教科书上认为“空串是任意串的子串”无意义，所以认为选C。为避免考试中的二意性，编者认为第9题出得好。 二、判断题 三．填空题 1．(1) 由空格字符（ASCII值32）所组成的字符串 (2)空格个数 2．字符 3．任意个连续的字符组成的子序列 4．5 5.O(m+n) 6． 7． 8．(1)模式匹配 (2)模式串 9．(1)其数据元素都是字符(2)顺序存储(3)和链式存储(4)串的长度相等且两串中对应位置的字符也相等 10．两串的长度相等且两串中对应位置的字符也相等。 11．’xyxyxywwy’ 12．*s++=*t++ 或（*s++=*t++）!=‘\0’ 13．（1）char s[ ] (2) j++ (3) i >= j 14．[题目分析]本题算法采用顺序存储结构求串s和串t的最大公共子串。串s用i指针（1<=i<=s.len）。t串用j指针（1<=j<=t.len）。算法思想是对每个i（1<=i<=s.len，即程序中第一个WHILE循环），来求从i开始的连续字符串与从j（1<=j<=t.len，即程序中第二个ＷHILE循环）开始的连续字符串的最大匹配。程序中第三个（即最内层）的WHILE循环，是当s中某字符（s［i］）与t中某字符（t［j］）相等时，求出局部公共子串。若该子串长度大于已求出的最长公共子串（初始为０），则最长公共子串的长度要修改。 程序（a）：（1）（i+k<=s.len）AND(j+k<=t.len) AND(s[i+k]=t[j+k]) //如果在s和t的长度内，对应字符相等，则指针k 后移（加1）。 （2）con:=false //s和t对应字符不等时置标记退出 （3）j:=j+k //在t串中，从第j+k字符再与s[i]比较 （4）j:=j+1 //t串取下一字符 （5）i：=i+1 //s串指针i后移（加1）。 程序（b）：(1) i+k<=s.len && j+k<=t.len && s[i+k]==t[j+k] //所有注释同上（a） (2) con=0 (3) j+=k (4) j++ (5) i++ 15．（1）0 （2）next[k] 16．（1）i：=i+1 （2）j:=j+1 (3)i:=i-j+2 (4)j:=1; (5)i-mt（或i:=i-j+1） (6)0 17.程序中递归调用 （1）ch1<>midch //当读入不是分隔符&和输入结束符$时，继续读入字符 （2）ch1=ch2 //读入分隔符&后，判ch1是否等于ch2，得出真假结论。 （3）answer：=true （4）answer：=false （5）read（ch） （6）ch=endch第4章数据结构与算法习题与答案
数据结构答案第4章
数据结构课后习题及解析第四章
数据结构C语言版第四章 串
数据结构课后习题答案第四章
GIS原理与应用教案——第四章 空间数据的处理
数据结构第四章备课讲稿
严蔚敏数据结构c语言版习题集答案第四章串
实用数据结构基础(第四版)课后习题知识讲解
第四章 空间数据的处理及投影变换
空间数据与数据质量
严蔚敏《数据结构(c语言版)习题集》答案第四章串
GIS概论 第四章 空间数据库
数据结构第四章考试题库(含答案)
数据结构课后习题与解析第四章
数据结构练习第四章 串
第四章 串答案52450
数据结构第四章习题答案
数据结构 习题 第四章 串 答案