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

Slides:



Advertisements
Similar presentations
电子成绩单项目实现.
Advertisements

Introduction 基本概念 授課老師:蕭志明
数据结构 2014年3月.
第4章 條件判斷與迴圈 Java 2 程式設計入門與應用.
第五章 二次型. 第五章 二次型 知识点1---二次型及其矩阵表示 二次型的基本概念 1. 线性变换与合同矩阵 2.
§1 二阶与三阶行列式 ★二元线性方程组与二阶行列式 ★三阶行列式
一、二阶行列式的引入 用消元法解二元线性方程组. 一、二阶行列式的引入 用消元法解二元线性方程组.
第五章 数组和广义表.
第一章 C语言概述 计算机公共教学部.
第三章 鏈結串列 Linked List.
§1 线性空间的定义与性质 ★线性空间的定义 ★线性空间的性质 ★线性空间的子空间 线性空间是线性代数的高等部分,是代数学
数据结构与算法 数据结构与算法实验
专题研讨课二: 数组在解决复杂问题中的作用
第4章 串 串的基本概念和C语言的串函数 串的存储结构 动态数组实现的顺序串 串的模式匹配算法——BF算法 主要知识点.
程式設計 博碩文化出版發行.
第二章 矩阵(matrix) 第8次课.
结构体和共用体 2 梁春燕 华电信息管理教研室.
第五章 数组和 广义表 数组 稀疏矩阵 广义表.
第五章 数组和广义表.
·线性表的定义及ADT ·线性表的顺序存储结构 ·线性表的链接存储结构 · 单向循环链表 · 双链表、双向循环链表 · 一元多项式的加法
第2章 线性表(三) 1/.
第 4章 串和数组(二) 本讲主要内容: 数组的定义及其顺序表示和实现。 矩阵的压缩存储。 广义表的定义。
串和数组.
第2讲 绪论(二).
第 3 讲 线性表(一).
五、链 表 1、单链表 2、双向链表 3、链表应用.
第4章 串、数组和广义表 4.1 串 4.2 数组 4.3 广义表.
第五章 习题课 电子信息与计算机科学系 曾庆尚.
第三章 链表 单链表 (Singly Linked List) 循环链表 (Circular List) 多项式及其相加
第4章 串和数组 本章主要介绍下列内容: 串的定义、存储结构和基本运算 数组的定义、基本运算和存储结构 特殊矩阵的压缩存储.
顺序表的插入.
工业机器人技术基础及应用 主讲人:顾老师
第1章 概述 本章要点: C语言程序结构和特点 C语言程序的基本符号与关键字 C语言程序的编辑及运行 学习方法建议:
第五章 数组 5.1 数组的定义 5.2 数组的表示和实现* 5.3 数组的压缩.
第五章 串和数组 5.1 串的定义和操作 5.2 串的表示和实现 5.3 字符串应用 5.4 字符串匹配算法 5.5 数组
第三章 链表 单链表 循环链表 多项式及其相加 双向链表 稀疏矩阵.
C++语言程序设计 C++语言程序设计 第七章 类与对象 第十一组 C++语言程序设计.
OOP6 結構Struct 黃兆武.
第6章 数组与广义表 6.1 数组的定义及其基本操作 6.2 数组的顺序存储结构 6.3 矩阵的压缩存储 6.4 广义表的概念
程式結構&語法.
顺序表的删除.
线性代数 第二章 矩阵 §1 矩阵的定义 定义:m×n个数排成的数表 3) 零矩阵: 4) n阶方阵:An=[aij]n×n
第二章 数组 作为抽象数据类型的数组 顺序表 多项式抽象数据类型 稀疏矩阵 字符串 小结.
线 性 代 数 厦门大学线性代数教学组 2019年4月24日6时8分 / 45.
数 据 结 构 与 算 法.
第5章 数组和广义表 本章主题:多维数组、特殊矩阵和广义表 教学目的:掌握数组和广义表的定义、运算及存储结构 教学难点:矩阵的压缩存储
第四章 串和数组 4.1 串的定义* 4.2 串的表示和实现* 4.3 数组 4.4 数组的压缩.
第1章 绪论(二) 教学目标 理解算法的特性及评价标准 掌握算法时间复杂度和空间复杂度的分析方法 1/
成绩是怎么算出来的? 16级第一学期半期考试成绩 班级 姓名 语文 数学 英语 政治 历史 地理 物理 化学 生物 总分 1 张三1 115
<编程达人入门课程> 本节内容 为什么要使用变量? 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ:
§6.7 子空间的直和 一、直和的定义 二、直和的判定 三、多个子空间的直和.
3.16 枚举算法及其程序实现 ——数组的作用.
本 章 说 明 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.4 广义表的定义 5.5 广义表的存贮结构
多层循环 Private Sub Command1_Click() Dim i As Integer, j As Integer
#include <iostream.h>
2.2矩阵的代数运算.
线 性 代 数 厦门大学线性代数教学组 2019年5月12日4时19分 / 45.
第五章 串和数组 5.1 串的定义和操作 5.2 串的表示和实现 5.3 正文匹配模式 5.4 正文编辑 5.5 数组 5.6 数组的压缩.
第七章  数 组.
§2 方阵的特征值与特征向量.
实验目的:掌握数据的顺序存储结构及它们在计算机中的操作。 实验内容:
基于列存储的RDF数据管理 朱敏
数据结构概论 第5章 数组和广义表 董黎刚 浙江工商大学信电学院.
定义5 把矩阵 A 的行换成同序数的列得到的矩阵,
第三章 流程控制 程序的运行流程 选择结构语句 循环结构语句 主讲:李祥 时间:2015年10月.
§4.5 最大公因式的矩阵求法( Ⅱ ).
第5章 其他线性数据结构.
第二章 线性表 东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件.
§2 自由代数 定义19.7:设X是集合,G是一个T-代数,为X到G的函数,若对每个T-代数A和X到A的函数,都存在唯一的G到A的同态映射,使得=,则称G(更严格的说是(G,))是生成集X上的自由T-代数。X中的元素称为生成元。 A变, 变 变, 也变 对给定的 和A,是唯一的.
9.3多项式乘多项式.
Presentation transcript:

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

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

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

一维数组可以看成是一个线性表或一个向量,它在计算机内是存放在一块连续的存储单元中,适合于随机查找。 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

程序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

程序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

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

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

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

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

程序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

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

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 0 1 2 3 4 5 6 2 1 10 3 1000 4 Padd函数复杂度:设m,n分加为A(x),B(x)中非0项个数,循环次数不超过m+n-1, 惭近计算时间:O(n+m) 2018/9/20

程序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

程序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

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

【例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

【例2】有m名学生,每人考n门功课,试写出求任一学生总分数和任一课程总分数的数据结构和算法。 【解】把学生的考试成绩存放在m行n列的二维数组中,则第i(0≤i<m)行第j(0≤j<n)列中存放了第i个学生的第j门课程考试成绩。即数据结构为: #define M 10 //假设<学生人数>为10人 #define N 3 //假设<课程门数>为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

稀疏矩阵(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]; 0 0 22 0 -15 0 11 3 0 0 0 0 0 0 0 -6 0 0 0 0 0 0 0 91 0 0 0 0 0 0 0 28 0 0 0 2018/9/20

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

稀疏矩阵转置 转置矩阵的表示: 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的不利处 . 0 0 22 0 -15 0 11 3 0 0 0 0 0 0 0 -6 0 0 0 0 0 0 0 91 0 0 0 0 0 0 0 28 0 0 0 0 0 0 91 0 0 11 0 0 0 0 0 3 0 0 0 0 22 0 0 0 28 0 0 0 -6 0 0 0 -15 0 0 0 0 0 2018/9/20

稀疏矩阵转置实现函数(按列转置的算法) 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

稀疏矩阵转置快速转置(选讲) 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

三元组表示的稀疏矩阵的转置常用的算法有以下两种: 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

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

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

(算法见教科书) 为此,需要设置两个一维数组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] 0<col<M.rows; 例如图5-4(a) 所示的稀疏矩阵的三元组表对应的num[0..n-1]和rpos[0..n-1]如图5-5所示。 图5-5 矩阵的num和rpos 数组值 (算法见教科书) 2018/9/20

快速转置算法如下: 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

2.4.3 矩阵乘法 1 0 0 1 0 0 1 1 1 0 0 0 0 0 0 1 1 1 两个稀疏矩阵可能不是稀疏矩阵: 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

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

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

对照两个矩阵经典相乘的例子,可看出上述方法的优越性: 若设 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

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

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

例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

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

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

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

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