第2章 数组与结构 本章主题：ADT数组、结构与共同体、ADT多项式、矩阵 教学目的：掌握ADT数组的定义、运算及存储结构

Presentation on theme: "第2章 数组与结构 本章主题：ADT数组、结构与共同体、ADT多项式、矩阵 教学目的：掌握ADT数组的定义、运算及存储结构"— Presentation transcript:

1 第2章 数组与结构 本章主题：ADT数组、结构与共同体、ADT多项式、矩阵 教学目的：掌握ADT数组的定义、运算及存储结构
第2章 数组与结构 本章主题：ADT数组、结构与共同体、ADT多项式、矩阵 教学目的：掌握ADT数组的定义、运算及存储结构 教学难点：稀疏矩阵的表示与多维数组的存储 2018/9/20

2 本章学习导读 本章主要介绍数组的概念及多维数组在计算机中的存放，特殊矩阵的存储及相应运算实现。通过本章学习，要求掌握如下内容：
1. ADT数组的定义与存储表示及结构实现； 2. 线性表与ADT多项式 3. 稀疏矩阵的三元组表示及转置算法实现； 4．ADT字符串插入与模式匹配实现； 2018/9/20

3 2.1 ADT数 组 数组（Array）是由n(n>1)个相同类型数据元素a0，al，…ai…，an-1构成的有限序列。n是数组的长度。其中数组中的数据元素ai是一个数据结构，即ai可以是线性表中的一个元素，本身也可以是一个线性表. ADT数组： Structure Array object: 有序对<index,values>的集合 functions: Array Create(j,list) ::= return j 维数组. Item Retrieve(A,i) ::=if(i∈index) return values(i) else return error Array Store(A,I,x) ::=if(i∈index) return Add(I,x) to A else return error 2018/9/20

4 一维数组可以看成是一个线性表或一个向量，它在计算机内是存放在一块连续的存储单元中，适合于随机查找。
1．一维数组 一维数组可以看成是一个线性表或一个向量，它在计算机内是存放在一块连续的存储单元中，适合于随机查找。 一维数组记为A[n]或A=( a0，al，…ai，…，an-1) 一旦a0的存储地址、一个数据元素所占存储单元数k确定，则ai的存储地址LOC(ai)就可求出： LOC(ai)=LOC(a0)+i*k (0≤i<n) 如果定义：int a[n]; 则 k=sizeof(int) 2018/9/20

5 程序2-1数组应用：累加求和函数(教材P33) #define MAX_SIZE 100 float sum(float [],int);
float input[MAX_SIZE],answer; int i; void main(void) { for(i=0;i<MAX_SIZE; i++) input[i]=i; answer=sum(input, MAX_SIZE); printf(“The sum is:%f\n”,answer); } float sum(float list[],int n) { int i; float tempsum=0; for(i=0;i<n;i++) tempsum+=list[i]; return tempsum; 2018/9/20

6 程序2-2通过地址访问一维数组 { int i; printrf(“Address Contents\n”);
void print1(int *ptr,int rows) { int i; printrf(“Address Contents\n”); for(i=0;i<rows; i++) printf(“%8u%5d\n”,ptr+i, *(ptr+i)); printf(“\n”); } 2018/9/20

7 2.2结构与共同体 strcpy(person.name,”james”); person.age=25;
person.salary=35000; struct { char name[10]; int age; float salary; } person; typedef struct human_being { char name[10]; int age; float salary; date dob; sex_type sex_info; }; typedef struct sex_type { enum tag_field{femal,male} sex; union{ int children; int beard; }u; }; 2018/9/20

8 2.2.4 自引用结构 typedef struct list { char data; list *link; };
list item1, item2, item3; item1.data=‘a’; item2.data=‘b’; item3.data=‘c’; Item1.link=item2.link=item3.link=NULL; 或： item1.link=&item2; item2.link=&item3; 链接(表)：linking 2018/9/20

9 2.3 ADT多项式 数组实现常见的数据结构：有序表或线性表。例如： 每周七天:(星期日,星期一,星期二,星期三,星期四,星期五,星期六 )
纸牌点数: (Ace,2,3,4,5,6,7,8,9,10,Jack,Queen,King) 建筑物楼层: (地下室，大厅，夹楼，一层，二层) 二战中美国参战年份: (1941,1942,1943,1944,1945) 有序表的顺序映射： itemi,itemi+1存入在数组第i和第i+1位置。 对于多项式结构，数组是否适合？ ADT多项式加法与乘法： A(x)+B(x)=∑(ai+bi)xi A(x) ·B(x)=∑(aixi·∑(bixi)) 2018/9/20

10 ADT多项式结构： structure polynomial
objects: p(x)=a1xe1+… +anxen; 有序对<ei,ai>集合 functions: Polynomial Zero() ::= return 多项式p(x)=0; Boolean IsZero(poly) ::= if(poly) return False else return Ture Coefficient Coef(poly,expon)::= if(expon∈poly)return系数else return 0 Exponent Lead_Exp(poly)::= return poly的最大指数 Polynomial Attach(poly ,coef,expon)::=if(expon∈poly)return错误else 插入 项 <coef,expon>后的多项式poly Polynomial Remove(poly , expon)::=if(expon∈poly)return删除expon后多项式 else return 错误 Polynomial SingleMult(poly ,coef,expon)::=return 多项式poly·coef xexpon Polynomial Add(poly1,poly2)::= return 多项式poly1+poly2 Polynomial Mult(poly1,poly2)::= return 多项式poly1·poly2 End Polynomial 2018/9/20

11 程序2-4 padd函数 /*d=a+b,where a,b and d ard polynomials */ d=Zero();
while(! IsZero(a)&&! IsZero(b)) do { switch COMPARE(Lead_Exp(a), Lead_Exp(b)) { case -1: d= Attach(d ,coef(b,LeadExp(b)), Lead_Exp(b)); b=Remov(b, Lead_Exp(b)); break; case 0: sum = Coef(a, Lead_Exp(a))+ Coef(b, Lead_Exp(b)); if (sum) { Attach(d, sum, Lead_Exp(a)); a=Remov(a, Lead_Exp(a)); b=Remov(b, Lead_Exp(b)); } case 1: d= Attach(d ,coef(a,LeadExp(a)), Lead_Exp(a)); a=Remov(a, Lead_Exp(a)); } } insert and remaining terms of a or b into d 2018/9/20

12 padd函数算法中多项式的存储表示(I)：
#define MAX_DEGREE 101 typedef struct { int degree; float coef[MAX_DEGREE]; } polynomial; a的类型为polynomial 对于多项式 可表示为： 优点：简便 , 但是当a.degree << MAX_DEGREE 时浪费空间！ 2018/9/20

13 padd算法中多项式的存储另一种表示(II)：
MAX_TERMS 100 typedef struct { float coef; int expon; } polynomial; polynomial terms[MAX_TERMS]; int avail=0; starta finisha startb finishb avail coef exp 2 1 10 3 1000 4 Padd函数复杂度：设m,n分加为A(x),B(x)中非0项个数,循环次数不超过m+n-1, 惭近计算时间：O(n+m) 2018/9/20

14 程序2－5 两个多项式相加函数 P41 Void padd(int starta,int finisha,int startb,int finishb, int *startd,int *finishd) { float coefficient; *startd=avail; while(starta<=finisha&& startb<=finishb) switch(compare(terms[starta].expon,terms[startb].expon)){ case -1:/* a expon< bexpon */ attach(terms[startb].coef,terms[startb].expon); case 0:/*equal exponents */ cofficient=terms[starta].coef+terms[startb].coef; if(cofficient) attach(terms[starta].coef,terms[starta].expon); starta++; } for(;starta<=finisha;starta++) attach(terms[startb].coef,terms[startb].expon); *finishd=avail-1; } 2018/9/20

15 程序2－6 增加新项的函数 P41 Void attach(float coefficient , int exponent)
{ if(avail>=MAX_TERMS){ fprintf(stderr,”Too many terms in the polynomial\n”); exit(1); } terms[avail].coef=cofficient; terms[avail].expon=exponent; 2018/9/20

16 a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn
2.4 ADT稀疏矩阵 矩阵(matrix)实质是个二维数组 。二维数组中的每一个元素又是一个定长的线性表（一维数组）.例如，设A是一个有m行n列的二维数组，则A可以表示为： 可看成由m个行向量组成的向量，也可看由n个列向量组成的向量。 ⑴行优先顺序——将数组元素按行排列， a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn ⑵列优先顺序——将数组元素按列向量排列 a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anm 2018/9/20

17 【例1】对于给定的二维数组float a[3][4]，计算：
【解】(1)由于C语言中数组的行、列下标值的下界均为0，该数组行上界为3-1=2，列上界为4-1=3，所以该数组的元素数目共有3*4=12个。 (2)由于C语言采用行序为主序的存储方式，有： LOC(a2,3)=LOC(a0,0)+(i*n+j)*k =1000+(2*4+3)*4 =1044 2018/9/20

18 【例2】有m名学生，每人考n门功课，试写出求任一学生总分数和任一课程总分数的数据结构和算法。
【解】把学生的考试成绩存放在m行n列的二维数组中，则第i(0≤i<m)行第j(0≤j<n)列中存放了第i个学生的第j门课程考试成绩。即数据结构为： #define M //假设<学生人数>为10人 #define N //假设<课程门数>为3 int score[M][N]; //学生成绩二维数组 求第i名学生总分数的算法为： int student_sum(int score[M][N],int i) { int j,sum=0; for(j=0;j<N;j++) sum=sum+score[i][j]; return(sum); } 求第j门课程总分数的算法为： int course_sum(int score[M][N],int j) { int i,sum=0; for(i=0;i<M;i++) sum=sum+score[i][j]; return(sum); } 2018/9/20

19 稀疏矩阵(Sparse)的压缩存储 ADT稀疏矩阵定义:矩阵中包含多个零元素.如何节省存储空间？ 矩阵的最小的操作：创建、加法、乘法、转置。
要实现以上操作必须建立稀疏矩阵的存储表示： 三元组：<row ,col , value> Sparse_Matrix Create(max_row,max_col)::= #define sturc{ int col; int row; int value; }term; term a[Max_Terms]; 2018/9/20

20 稀疏矩阵的存储示例：P44 行 列 值 a[0] 6 6 8 a[1] 0 0 15 a[2] 0 3 22 a[3] 0 5 -15
行 列 值 a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] 2018/9/20

21 稀疏矩阵转置 转置矩阵的表示: a[i][j] 对应b[j][i]
算法1：for each i(row) get <i,j,value> to <j,i, value> save; 算法2：for 对于j列的所有元素 把元素<i,j,value>放在元素 <j,i, value> 中; 避免了算法1的不利处 . 2018/9/20

22 稀疏矩阵转置实现函数(按列转置的算法) void transpose ( term a[] ,term b[]) {
int n,I,j,currentb; n=a[0].value; b[0].row=a[0].col; b[0].col =a[0].row; b[0].value=n; if (n>0){ currentb=1; for(i=0;i<a[0].col; i++) //按列转置 for(j=1;j<=n; j++) if(a[j].col==i){ b[currentb].row=a[j].col; b[currentb].col=a[j].row; b[currentb].value=a[j].value; currentb++; } 外层循环: a[0].col 内层循环: a[0].value 总次数:columns*elements 时间复杂度O(columns*elements) 对于简单形式： for(j=0;j<columns;j++) for(i=0;i<rows; i++) b[j][i]=a[i][j]; 时间复杂度O(columns*row) 当稀疏变为全满columns*row时 时间复杂度O(columns2*elements) 此时，三元组表示虽节约空间，但浪费了时间，而fast_transpose算法 复杂度为：O(columns+elements) 2018/9/20

23 稀疏矩阵转置快速转置(选讲） void fast_transpose(term a[] ,term b[])
{ int row_terms[MAX_COL], starting_pos[MAX_COL]; int I, j, num_cols=a[0].col, num_term=a[0].value; b[0].row=num_col; b[0].col =a[0].row; b[0].value=num_term; if (num_term>0){ for(i=0;i<num_col; i++) row_terms[i]=0; for(i=1;i<=num_cols; i++) row_terms[a[i].col]++; starting_pos=1; starting_pos[i]=starting_pos[i-1]+row_terms[i-1]; for(i=1;i<num_num_term; i++) { j=starting_pos[a[i].col]++; b[j].row=a[i].col; b[j].col=a[i].row; b[j].value=a[i].value; } } 时间复杂度： O(columns+elements) 当元素为columns*row时 复杂度O (columns*row) 2018/9/20

24 三元组表示的稀疏矩阵的转置常用的算法有以下两种： 1）矩阵的列序转置（传统的转置算法）
矩阵A是按行序为主序存储的，若按列序为主序进行转置就可以得到A阵的转置矩阵B。假设矩阵A的三元组存入一维数组中，只要在数组中按三元组的列域cols的值开始扫描，从第0列至第n-1列，依序将三元组列域与行域之值对换，并顺次存人数组mb中。算法如下： int transpose(table ma,table mb) { int i,j,k=0,n,t; if(ma.nums==0)return(0)； //矩阵中无非零元素 m=ma.rows; //m为矩阵A的列数 n=ma.cols; //n为矩阵A的行数 t=ma.nums; //为矩阵中非零元素个数 mb.rows=n; //转置矩阵B的列数 mb.cols; //转置矩阵B的行数 mb.nums=t; //转置矩阵中的非零元素个数 for(i=0;i<n;i++) //按矩阵A的列序扫描 2018/9/20

25 for(j=0;j<t;j++) if(ma.data[j].c==i) //判断第j个三元组是不是第i列的 { mb.data[k].r=ma.data[j].c; mb.data[k].c=ma.data[j].r; mb.data[k++].d=ma.data[j].d; } return(1); //成功完成矩阵转置 以上算法的时间复杂度分析：若n为转置矩阵的列数，t为矩阵中非零元素个数，则算法的时间花费主要在两个循环上，所以若时间复杂度为O(n×t)。也就是说，时间的花费和矩阵A的列数和非零元素个数的乘积成正比。若用m×n的二维数组表示矩阵，则相应的矩阵转置算法的循环为： for ( i=0；i＜n；i++ ) for (j=0；j＜m；j++＝ b[i][j]=a[j][i]； 此时，时间复杂度为O(m×n) 。 2018/9/20

26 2）快速转置算法： 三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算是法的难度。因此，此算法仅适用于t<=m*n的情况。 其算法思想为：对A扫描一次，按A第二列提供的列号一次确定位置装入B的一个三元组。具体实施如下：一遍扫描先确定三元组的位置关系，二次扫描由位置关系装入三元组。可见，位置关系是此种算法的关键。 为了预先确定矩阵M中的每一列的第一个非零元素在数组T中应有的位置，需要先求得矩阵M中的每一列中非零元素的个数。因为矩阵M中第一列的第一个非零元素在数组T中应有的位置等于前一列第一个非零元素的位置加上前列非零元素的个数。 2018/9/20

27 （算法见教科书） 为此，需要设置两个一维数组num[0..n]和rpos[0..n]： num[0..n]：统计M中每列非零元素的个数。
rpos[0..n]：M中的每列第一个非零元素在T中的位置。 算法通过rpos数组建立位置对应关系： rpos[0]=0 ； rpos[col]=rpos[col-1]+num[col-1] ＜col＜M.rows； 例如图5-4(a) 所示的稀疏矩阵的三元组表对应的num[0..n-1]和rpos[0..n-1]如图5-5所示。 图5-5 矩阵的num和rpos 数组值 （算法见教科书） 2018/9/20

28 快速转置算法如下： void fasttranstri(tritupletable b,tritupletable a){
int p,q,col,k; int num[0..a.n],copt[0..a.n]; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t<=0) printf(“a=0”\n); for(col=1;col<=a.u;++col) num[col]=0; for(k=1;k<=a.t;++k) ++num[a.data[k].j]; cpot[0]=1; for(col=2;col<=a.t;++col) cpot[col]=cpot[col-1]+num[col-1]; for(p=1;p<=a.t;++p){ col=a.data[p].j; q=cpot[col]; b.data[q].i=a.data[p].j; b.data[q].j=a.data[p].i; b.data[q].v=a.data[p].v; ++cpot[col]; } 2018/9/20

29 2.4.3 矩阵乘法 两个稀疏矩阵可能不是稀疏矩阵： Mmult程序2-9调用storesum程序2-10对矩阵A和B进行乘积,得到矩阵D。 Void storesum(term[], int *totald, int row, int column, int *sum) { if(*sum) if(*totald<MAX_TERMS){ d[++*totald].row=row; d[*totald].col=column; d[*totald].value=*sum; *sum=0; } else{fprint(stderr,”Numbers of terms in product exceeds %d\n”,Max_terms); exit(1);)} 2018/9/20

30 for循环之前：O(cols_b+totalb)
程序2－9 稀疏矩阵乘法(I) Void mmult(term a[ ], term b[ ],term d[ ]) { int i,j,column, totalb=b[0].value,totald=0; int rows_a=a[0].row, cols_a=a[0].col, totala=a[0].value; int cols_b=b[0].col, row_begin=1,row=a[1].row,sum=0,new_b[MAX_TERMS][3]; if(cols_a !=b[0].row){ fprint(stderr,” Incompatible matrices\n”); exit(1); } fast_transpose(b,new_b); a[totala+1].row=row_a; new_b[totalb+1].row=cols_b; new_b[totalb+1].col=0; for(i=1;i<=totala;) { column=new_b[1].row; for(j=1;j<=totalb+1;){ if (a[i].row!=row){ storesum(d,&totald,row,column,&sum); i=row_begin; for( ;new_b[j].row==column;j++); column=new_b[j].row;} for循环之前：O(cols_b+totalb) 2018/9/20

31 O(∑(cols_b·termsrow+tobalb))= O(cols_b·total_a+rows_a·totalb)
程序2－9 稀疏矩阵乘法(II) else if(new_b[j].row!=column){ storesum(d,&totald,row,column,&sum); column=new_b[j].row; } else switch(compare(a[i].col,new_b[j].col)){ case -1: i++; break; case 0: sum+=(a[i++].value*new_b[j++].value); break; case 1: j++; } for( ; a[i].row==row; i++) ; row_begin=i ; row=a[i].row; } d[0].row=rows_a; d[0].col=cols_b; d[0].value=totald; } O(∑(cols_b·termsrow+tobalb))= O(cols_b·total_a+rows_a·totalb) 2018/9/20

32 对照两个矩阵经典相乘的例子，可看出上述方法的优越性： 若设 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)。 O(n3) -> O(n2) 2018/9/20

33 多维数组：a[upper0] [upper1] · · · a[uppern-1]
2.5 多维数组的存储表示 多维数组：a[upper0] [upper1] · · · a[uppern-1] 2018/9/20

34 2.6 ADT字符串 ADT string: P52 Structure String 字符串函数： objects:
Functions: String NuLL(m) Integer Compare(s,t) Boolean IsNUll(s) Integer Length(s) String Concat(s,t) String Substr(s,i,j) End String 字符串函数： char *strcat(char *dest,char *src) char *strncat(char *dest,char *src, int n) char *strcmp(char *str1,char *str2) char * strcpy(char *dest,char *src) 2018/9/20

35 例2-2 [字符串插入]: 将string2插入到string1的第i个位置
#include<string.h> #define MAX_SIZE 100 char string1[MAX_SIZE], *s =string1; char string2[MAX_SIZE], *t =string2; void strnins(char *s, char *t, int i) { char string[MAX_SIZE], *temp =string; if(i<0 && i>strlen(s)) {fprintf(“error”);exit(1);} if(!strlen(s)) strcpy(s,t); else if(stlen(t)){ strncpy(temp,s,i); strcat(temp,t); strcat(temp,(s+i)); strcpy(s, temp); } } 2018/9/20

36 string库中内置函数strstr具备功能，判断pat是否在string中：
2.6.2 模式匹配 string库中内置函数strstr具备功能，判断pat是否在string中： char pat[MAX_SIZE], String[MAX_SIZE],*t; if(t=strstr(string,pat)) printf(“The string from strstr is:%s\n”,t); else printf(“The pattern was not found with strstr\n”); Strstr的不足 Ansi中新增内容 效率问题 2018/9/20

37 int nfind(char *string, char *pat)
程序2-12 先检测末端标记的模式匹配方法 int nfind(char *string, char *pat) { int i,j,start=0; int lasts=strlen(string)-1; int lastp=strlen(pat)-1; int endmatch=lastp; for(i=0;endmatch<=lasts; endmatch++,start++){ if(string[endmatch]==past[lastp]) for(j=0;j=start;j<lastp&&string[i]==pat[j];i++,j++); if(j==lastp) return start; /*successful*/ } return -1 2018/9/20

38 程序2-13 模拟nfind: pat=“aab”, string=“ababbaabaa”
1.上述例子中，计算时间与字符串长度呈线性关系O(m) 最坏的情况,计算时间为：O(n·m) 2.如何确定失配在模式中出现的位置？ pat=‘abcabcacab’ 定义：令p=p0p1…pn-1 是一个模式，失配函数 2018/9/20

39 本章小结 数组作为一种数据类型，它是一种多维的线性结构，需要采用顺序存储结构，通常只进行存取或修改某个元素的值。
对于特殊矩阵的压缩存储，实质就是将特殊矩阵的二维表中的数据按照一定的次序存放到一维数组中，元素aij的位置通过相应的地址计算公式（映射公式）来确定；对于稀疏矩阵，由于非零元素排列无规律，通常采用三元组法来实现压缩存储。三元组法具体采用哪种实现形式，取决于应用中矩阵的形态以及主要进行什么样的运算。 ADT字符串定义、插入、模式匹配。 2018/9/20