加载中…
个人资料
_陌上花开7_
_陌上花开7_
  • 博客等级:
  • 博客积分:0
  • 博客访问:68,244
  • 关注人气:29
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

字符串和多维数组

(2013-05-19 11:03:31)
标签:

字符串

三元组

十字链表

分类: 数据结构

字符串(简称)是零个或者多个字符组成的有限序列,只包含空格的串称为空格串。串中所包含的字符个数称为串的长度,长度为0的串称为空串,记住"",一个非空串通常记作:

S="s1s2s3……sn"

字符串中任一个连续的字符组成的子序列称为该串的子串,相应地,包含子串的串称为主串,子串的第一个字符在主串中的标号称为子串在主串中的位置

给定两个字符串S=“s1s2s3……sn”和T=“t1t2t3……tm”,在主串S中寻找子串T的过程称为模式匹配,T称为式,如果匹配成功,返回T在S中的位置,如果匹配失败,返回0

一般的匹配方法:朴素的模式匹配算法和改进的模式匹配算法KMP算法,其基本思想是主串不尽心回溯。具体细节不在阐述。

数组是有类型相同的数据元素构成的有序集合,每个数据元素称为一个数组元素(简称元素),每个元素受到n(n>=1)个线性关系的约束,每个元素都在n个线性关系中的序号i1,i2,……in称为该元素的下标,并称该数组为n维数组。数组是一个具有固定格式和数量的数据集合,在数组上一般不能执行插入或者删除某个数组元素的操作,因此,出来初始化和销毁之外,在数组中通常只有两种操作:读操作,写操作。

数组的存储结构:以二维数组为例,二维数组的每一个元素都含有两个下标,需要将二维关系映射成一维关系,常用的映射方法有两种,以行序为主序和以列序为主序,例如C++中的数组就是以行序存储的,例如按行优先存储的基本思想就是先行后列,先存储行号较小的元素,行号相同者先存储列号较小的元素。

矩阵的压缩存储

压缩存储的基本思想是:

1、为多个值相同的元素只分配一个存储空间

2、对零元素不分配存储空间

稀疏矩阵是零元素居多的矩阵,在工程应用中,经常会遇到级数很高的大型稀疏矩阵,如果按常规方法存储,势必会存储大量的零元素,造成存储浪费。一个显然的存储方法是仅存零元素,但对于这类矩阵,通常非零元素的分布没有分布规律,为了能找到相应的元素,进存储非零元素的值是不够的,还要存储该非零元素所在的行号和列号,即每个元素表示为三元组(行号,列号,非零元素值)。

在C++语言中,可以用结构体类型来描述三元组

template<class DataType>

struct element

{

   int row,col;

   DataType item;

};

将稀疏矩阵的非零元素对应的三元组所构成的集合,按行优先的顺序排列成一个线性表,称为三元组表(list of 3-tuples),则稀疏矩阵的压缩存储转换为三元组表的存储。

1、三元组顺序表

采用顺序存储结构存储的三元组称为三元组顺序表,显然,要唯一的表示一个稀疏矩阵,还需要在存储三元组表的同时存储该矩阵的行数,列数和非零元素的个数,棋存储结构定义如下:

const int MaxTerm=100;

struct SparseMatrix

{

element data[MaxTerm];

int mu,nu,tu;  //行数,列数,非零元素个数

};

2、十字链表

采用三元组顺序表存储稀疏矩阵,对于矩阵的加法,乘法等操作,非零元素的个数以及位置都会发生变化,这时顺序存储方法就非常不便,稀疏矩阵的链接存储结构称为十字链表(orthogonal list),它具备链接存储的特点,因此,在非零元素的个数及位置都会发生变化的情况下,通常采用十字链表存储稀疏矩阵。

十字链表存储稀疏矩阵的基本思想是:将每个非零元素对应的三元组存储为一个链表的结点,结点由5个域组成,其结构为element(row,col,item)+down+right 其中element为数据域,存储非零元素对应的三元组,right为指针域,指向同一行中的下一个三元组,down为指针域,指向同一列中的下一个三元组。

 

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有