首页 考试资料幻灯片工程技术公务员考试小学教学中学教学大学教学外语资料
数据结构实验书


在本程序设计中,对命令的分析过程并不是很严格,并且在实现串的某些操作时并没有支持字符串常量的 操作,串的替换等操作还没有实现,因此,可在本程序的基础上作进一步的改进,完善相应的一些功能。

第四节

思考题

1. 以顺序存储结构表示串,设计算法,求串 S 中出现的第一个最长重复子串及其位置并分析算法的时间复 杂度。(东南大学 2000 数据结构研究生试题) 【简要分析】 此题算法较多,较好的算法时间复杂度为 0(length2(s)),可考虑从最长(length(s)-1)的 字符串入手进行比较,直到找到重复子串为止。 2. 假设以块链结构作串的存储结构,试编写判别给定串是否具有对称性的算法,并要求算法的时间复杂度 为 0(length(s)) 3. 文学研究人员需要统计某篇英文小说中某些词的出现次数。输入一段英文,试写一个文字统计程序,统 计该段英文中出现的单词和每个单词出现的次数。

第五章 矩阵的压缩存储与运算
【实验目的】 1. 熟练掌握稀疏矩阵的两种存储结构(三元组表和十字链表)的实现; 2. 掌握稀疏矩阵的加法、转置、乘法等基本运算; 3. 加深对线性表的顺序存储和链式结构的理解。

第一节 知识准备
矩阵是由两个关系(行关系和列关系)组成的二维数组,因此对每一个关系上都可以用线性表进 行处理;考虑到两个关系的先后,在存储上就有按行优先和按列优先两种存储方式,所谓按行优先,是指 将矩阵的每一行看成一个元素进行存储;所谓按列优先,是指将矩阵的每一列看成一个元素进行存储;这 是矩阵在计算机中用一个连续存储区域存放的一般情形,对特殊矩阵还有特殊的存储方式。 一、 特殊矩阵的压缩存储 1. 对称矩阵和上、下三角阵 若 n 阶矩阵 A 中的元素满足 = (0≤i,j≤n-1 )则称为 n 阶对称矩阵。对 n 阶对称矩阵,我们

只需要存储下三角元素就可以了。事实上对上三角矩阵(下三角部分为零)和下三角矩阵(上三角部分为 零),都可以用一维数组 ma[0.. ]来存储 A 的下三角元素(对上三角矩阵做转置存储),称 ma 为矩阵 A

的压缩存储结构,现在我们来分析以下,A 和 ma 之间的元素对应放置关系。 问题已经转化为:已知二维矩阵 A[i,j],如图 5-1, 我们将 A 用一个一维数组 ma[k]来存储,它们之间存在着如图 5-2 所示的一一对应关系。 任意一组下标(i,j)都可在 ma 中的位置 k 中找到元素 m[k]= ;这里: k=i(i+1)/2+j (i≥j)

图 5-1 下三角矩阵

a00 a10 a11 a20 ? an-1,0 ? an-1,n-1 k= 0 n(n+1)/2-1 1 2 3 ? n(n-1)/2 ?

图 5-2 下三角矩阵的压缩存储

反之, 对所有的 k=0,1, 2,?,n(n+1)/2-1, 都能确定 ma[k]中的元素在矩阵 A 中的位置 (i,j) 。 这里, i=d-1, (d 是使 sum= 2. 三对角矩阵 在三对角矩阵中,所有的非零元素集中在以主对角线为中心的带内状区域中,除了主对角线上和直接在对 角线上、下方对角线上的元素之外,所有其它的元素皆为零,见图 5-3。 > k 的最小整数),j= 。

图 5-3

三对角矩阵 A

与下三角矩阵的存储一样,我们也可以用一个一维数组 ma[0..3n-2]来存放三对角矩阵 A,其对应关系见图 5-4。

a00 a01 a10 a11 a12 ? an-1,n-2 an-1,n-1 k= 0 3n-3 3n-2 1 2 3 4 ?

图 5-4 下三角矩阵的压缩存储

A 中的一对下标(i,j)与 ma 中的下标 k 之间有如下的关系:

公式中采用了 C 语言的符号,int()表示取整,‘%’表示求余。

二、 稀疏矩阵 在 m×n 的矩阵中,有 t 个非零元。令 δ = ,称 δ 矩阵的稀疏因子,常认为 δ ≤0.05 时称为稀疏矩阵。

稀疏矩阵在工程中有着大量的应用,不少工程问题都可以转化为对稀疏矩阵的计算问题。如何进行稀疏矩 阵的压缩存储呢? 为节省存储空间,应只存储非零元素。除了存储非零元的值之外,还必须记下所在行和列的位置(i,j), 即一个三元组(i,j, 1. 三元组顺序表 以顺序存储结构来表示三元组表,则可称稀疏矩阵的一种压缩存储方式。 )唯一确定了矩阵 A 的一个非零元素。

//稀疏矩阵的三元组顺序表存储表示。 #define MaxSize typedef int 10 //用户自定义 //用户自定义

Datatype;

typedef struct{ int int j;

//定义三元组

i; //非零元的行下标 //非零元的列下标 //非零元的数据值

Datatype v; }TriTupleNode; typedef struct{ TriTupleNode

data[MaxSize]; //非零元的三元组表

int m,n,t; //矩阵行,列及三元组表长度 }TriTupleTable; 2. 十字链表 当矩阵的非零元个数和位置在操作过程中变化较大时,就不宜采用顺序存储结构来表示三元组的线性表, 采用纵横交叉的十字链表就比较好。 在十字链表中,每个非零元可用一个含五个域的结点表示,其中 i, j 和 e 三个域分别表示该非零元所在 的行、列和非零元的值,向右域 right 用以链接同一行中下一个非零元。向下域 down 用以链接同一列中下 一个非零元。同一行中的非零元通过 right 域链接成一个线性链表,每个非零元既是某个行链表中的一个 结点,又是某个列链表中的一个结点,整个矩阵构成了一个十字交叉的链表,故称这样的存储结构为十字 链表,如图 5-5 所示。

图 5-5

稀疏矩阵 M 的十字链表

typedef int

Datatype;

//用户自定义

typedef struct OLNode{ int i,j; Datatype Struct v; OLNode *right,*down //该非零元所在行表和列表的后继链域 //该非零元的行和列下标

}OLNode;*OLink; typedef struct {

OLink *rhead,*chead int mu,nu,tu; }CrossList;

第二节 用三元组表实现稀疏矩阵的基本操作

【问题描述】用三元组表实现稀疏矩阵的按列转置。 【数据描述】 typedef int Datatype; //用户自定义

typedef struct { //定义三元组 int i,j; Datatype v; // 非零元素的行下标和列下标

}TriTupleNode; typedef struct{ //定义三元组表 TriTupleNode data[MaxSize];

int m,n,t; //矩阵行,列及三元组表长度 }TriTupleTable; 【算法描述】 按照列序来进行转置。为了找到每一列中所有的非零元素,需要对其三元组表从第一行起整个扫描一遍。 Status TransposeSMatrix(TriTupleTable a, TriTupleTable &b){

b.m=a.n;b.n=a.m;b.t=a.t; if(b.t){ q=0; for(col=1;col<=a.n;++col) for(p=0;p<=a..t;++p) if(a.data[p].j==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;++q;} }

123456789101112131415161718192021222324252627282930

 


 

  【Top

最新搜索

 

数据结构实验指导书 - 数据结构 实验指导书 院别 专业 班级 姓名 计算机学院编 实验一 线性表的顺序存储实验 一、实验目的及要求 1、掌握在TC环境下调试顺序表...

数据结构与算法实验指导书90969 - 数据结构与算法实验指导书 计算机与信息学院 实验一 【实验目的】 顺序表 熟练掌握线性表在顺序存储结构上的基本操作。 【实验...

数据结构实验指导书02 很好!很好!隐藏&gt;&gt; 实验二 2.1 实验目的: 线性表 (1)掌握线性表的顺序存储结构的定义及 C 语言实现。 (2)掌握线性表在顺序存储结构即...

数据结构实验说明书新版 - the principl e of simplified E IA of constr uction pr oject s in the regi on. In te...

数据结构实验指导书 - 数据结构实验指导(C语言版)... 数据结构实验指导书_IT/计算机_专业资料。数据结构实验指导(C语言版) 数据结构实验指导书 江西农业大学计算机与...

数据结构试验指导书V2[1].0 - V 2.0 数据结构与算法 实验指导书 编写: 编写:陆绍飞 校核: 校核:___ 湖南大学软件学院 2011 年 9 月 湖南大学软件学...

数据结构实验指导书(2012.9) - 1.2 实验报告(文档)书写规范 实验报告(文档)应包括以下 7 个方面的内容: 1、问题分析 根据对实验任务的理解, 以无歧义的陈述...

09级《数据结构》实验指导书 - 《数据结构实验指导书》 潘向辉/吴学毅编写 印包学院数字媒体技术专业 2011 年 3 月 实验说明 实验说明 【实验环境】 操作系统:...

空间数据结构基础实验指导书 隐藏&gt;&gt; 《空间数据结构基础》 课程实习指导书实习周数:2 周 学分数:2 一、实习目的 数据结构是一门重要的专业基础课,其特点是理论...

《数据结构(C 语言版) 》实验指导书(非计算机专业适用) 广州大学 2013.1 目 录 实验一 线性表的顺序存储及其操作... 1 实验二 线性表的链式存储及其操作......


 

热点推荐