数据结构与算法 特殊矩阵和稀疏矩阵

《数据结构与算法》第五章数组和广义表本章介绍的数组与广义表可视为线性表的推广，其特点是数据元素仍然是一个表。

本章讨论多维数组的逻辑结构和存储结构、特殊矩阵、矩阵的压缩存储、广义表的逻辑结构和存储结构等。

5.1 多维数组5.1.1 数组的逻辑结构数组是我们很熟悉的一种数据结构，它可以看作线性表的推广。

数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推。

图5.1是一个m行n列的二维数组。

5.1.2 数组的内存映象现在来讨论数组在计算机中的存储表示。

通常，数组在内存被映象为向量，即用向量作为数组的一种存储结构，这是因为内存的地址空间是一维的，数组的行列固定后，通过一个映象函数，则可根据数组元素的下标得到它的存储地址。

对于一维数组按下标顺序分配即可。

对多维数组分配时，要把它的元素映象存储在一维存储器中，一般有两种存储方式：一是以行为主序（或先行后列）的顺序存放，如BASIC、PASCAL、COBOL、C等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。

另一种是以列为主序（先列后行）的顺序存放，如FORTRAN语言中，用的是以列为主序的分配顺序，即一列一列地分配。

以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，…，从右向左，最后是左下标。

以列为主序分配的规律恰好相反：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，…，从左向右，最后是右下标。

例如一个2×3二维数组，逻辑结构可以用图5.2表示。

以行为主序的内存映象如图5.3（a）所示。

分配顺序为：a11 ，a12 ，a13 ，a21 ，a22，a23 ; 以列为主序的分配顺序为：a11 ，a21 ，a12 ，a22，a13 ，a23 ; 它的内存映象如图5.3（b）所示。

数据结构——特殊矩阵数据结构，特殊矩阵特殊矩阵是一种在计算机科学中常见的数据结构，它是由一组元素组成的二维数组。

特殊矩阵具有特定的属性，使得它们在特定的问题领域中非常有用。

在这篇文章中，我们将介绍几种常见的特殊矩阵，并讨论它们的应用。

首先，我们来讨论对角矩阵。

对角矩阵是指只有主对角线上有非零元素的矩阵。

其他位置上的元素都是零。

对角矩阵可以用于多种计算问题，如线性方程组的求解和矩阵乘法。

由于对角矩阵的特殊结构，它的存储和运算都可以更高效地执行。

其次，我们来讨论上三角矩阵和下三角矩阵。

上三角矩阵是指只有主对角线及其以上的元素都不为零的矩阵，而下三角矩阵则是指只有主对角线及其以下的元素都不为零的矩阵。

这两种特殊矩阵也常用于矩阵运算中，因为它们具有更高效的存储和计算方式。

另一个常见的特殊矩阵是稀疏矩阵。

稀疏矩阵是指其中大部分元素都为零的矩阵。

在很多应用中，矩阵的元素并不是均匀分布的，而是集中在一些特定的位置。

因此，使用传统的二维数组来存储这种矩阵会浪费很多的空间。

稀疏矩阵的一个常见的存储方法是压缩矩阵，只存储非零元素的值和其对应的位置。

最后，我们来讨论特殊矩阵的应用。

特殊矩阵广泛应用于图论、网络分析和科学计算等领域。

在图论中，邻接矩阵是一种常见的特殊矩阵，用于表示图的连接关系。

在网络分析中，PageRank算法使用了特殊矩阵的运算方法，用于计算网页的重要性。

在科学计算中，特殊矩阵的高效存储和计算方式可以大大提高计算效率。

总结起来，特殊矩阵是一种重要的数据结构，它具有特定的结构和属性，使得它们在特定的问题领域中非常有用。

了解特殊矩阵的类型和应用可以帮助我们更好地理解和应用数据结构。

希望本文对读者对特殊矩阵有更深入的了解，并能在实际问题中灵活应用。

数据结构(第二版)习题答案第4章第4章字符串、数组和特殊矩阵4.1稀疏矩阵常用的压缩存储方法有（三元组顺序存储）和（十字链表）两种。

4.2设有一个10 × 10的对称矩阵 A采用压缩方式进行存储，存储时以按行优先的顺序存储其下三角阵，假设其起始元素 a00的地址为 1，每个数据元素占 2个字节，则 a65的地址为（ 53 ）。

4.3若串S =“software”，其子串的数目为（ 36 ）。

4.4常对数组进行的两种基本操作为（访问数据元素）和（修改数组元素）。

4.5 要计算一个数组所占空间的大小，必须已知（数组各维数）和（每个元素占用的空间）。

4.6对于半带宽为 b的带状矩阵，它的特点是：对于矩阵元素 aij，若它满足（|i-j|>b），则 aij = 0。

4.7字符串是一种特殊的线性表，其特殊性体现在（该线性表的元素类型为字符）。

4.8试编写一个函数，实现在顺序存储方式下字符串的 strcompare （S1，S2）运算。

【答】：#include <stdio.h>#include <string.h>#define MAXSIZE 100typedef struct{char str[MAXSIZE];int length;}seqstring;/* 函数 strcompare()的功能是：当 s1>s2时返回 1，当 s1==s2时返回 0，当 s1<s2时返回-1*/int strcompare(seqstring s1,seqstring s2){ int i,m=0,len;len=s1.length<s2.length ?s1.length:s2.length;for(i=0;i<=len;i++)if(s1.str[i]>s2.str[i]){m=1;break;}else if(s1.str[i]<s2.str[i]){m=-1;break;}return m;}int main(){ seqstring s1,s2;int i,m;printf("input char to s1:\n");gets(s1.str);s1.length=strlen(s1.str);printf("input char to s2:\n");gets(s2.str);s2.length=strlen(s2.str);m=strcompare(s1,s2);if(m==1) printf("s1>s2\n");else if(m==-1) printf("s2>s1\n");else if(m==0) printf("s1=s2\n");}4.9试编写一个函数，实现在顺序存储方式下字符串的replace（S，T1，T2）运算。

第5章数组与广义表习题练习答案5.1请按行及按列优先顺序列出四维数组A2*3*2*3的所有元素在内存中的存储次序，开始结点为a0000。

解：按行优先的顺序排列时，先变化右边的下标，也就是右到左依次变化，这个四维数组的排列是这样的：(将这个排列分行写出以便与阅读，只要按从左到右的顺序存放就是在内存中的排列位置) a0000a0001a0002a0010a0011a0012a0100a0101a0102a0110a0111a0112a0200a0201a0202a0210a0211a0212a1000a1001a1002a1010a1011a1012a1100a1101a1102a1110a1111a1112a1200a1201a1202a1210a1211a1212按列优先的顺序排列恰恰相反，变化最快的是左边的下标，然后向右变化，所以这个四维数组的排列将是这样的，(这里为了便于阅读，也将其书写为分行形式)：a0000a1000a0100a1100a0200a1200a0010a1010a0110a1110a0210a1210a0001a1001a0101a1101a0201a1201a0011a1011a0111a1111a0211a1211a0002a1002a0102a1102a0202a1202a0012a1012a0112a1112a0212a02125.2 给出C语言的三维数组地址计算公式。

解：因为C语言的数组下标下界是0，所以Loc(A mnp)=Loc(A000)+((i*n*p)+k)*d其中Amnp表示三维数组。

Loc(A000)表示数组起始位置。

i、j、k表示当前元素的下标,d表示每个元素所占单元数。

5.3设有三对角矩阵A n*n，将其三条对角线上的元素逐行地存储到向量B[0...3n-3]中，使得B[k]=a ij,求：(1)用i , j 表示k的下标变换公式。

(2)用k 表示i,j 的下标变换公式。

《数据结构与算法》课程教学大纲一、《数据结构》课程说明（一）课程代码：（二）课程英文名称：Data Stucture（三）开课对象：电子专业的本科生（四）课程性质：专业基础课《数据结构》是计算机专业的技术基础课。

主要讲述算法设计和数据结构的基础原理和技术。

是计算机科学与技术专业的核心课程。

由于本课程是计算机程序设计理论基础，所以也是非计算机理工类专业的重要选修课程。

本课程的学习过程也是算法设计的技巧和能力的训练过程。

本课程的先导课程为《C语言》，《计算机基础》。

（五）教学目的：通过本课程的学习，使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习《操作系统》、《编译原理》和《数据库》等课程奠定基础。

（六）教学内容：本课程主要包括绪论、线性表、树型结构、图、查找、排序等几个部分。

通过教学的各个环节使学生达到各章中所提的基本要求。

习题课是重要的教学环节，教师必须予以重视。

（七）学时数、学分数及学时数具体分配学时数： 68学时学分数： 4学分（八）教学方式以多媒体教学手段为主要形式的课堂教学。

（九）考核方式和成绩记载说明考核方式为考试。

严格考核学生出勤情况，达到学籍管理规定的旷课量取消考试资格。

综合成绩根据平时成绩和期末成绩评定，平时成绩占20% ，期末成绩占80% 。

二、讲授大纲与各章的基本要求第一章绪论教学要点：通过本章的教学使学生初步了解《数据结构》的内容和目的，掌握数据结构的概念以及分类、抽象数据类型的表示与实现、算法的概念、算法的特性、算法的目标、算法效率的度量、算法的存储空间需求。

1、使学生准确掌握数据结构的概念。

2、使学生领会抽象数据类型的表示与实现。

3、使学生充分理解算法的概念。

4、明确算法的特性。

5、明确算法的目标。

6、熟练地掌握算法效率的度量。

7、掌握算法的存储空间需求。

教学时数：4学时教学内容：第一节数据结构概述第二节数据结构的概念一、基本概念二、数据结构及分类三、数据结构课程的内容第三节数据类型和抽象数据类型一、数据类型二、抽象数据类型第四节算法和算法分析考核要求：1、数据结构概述（识记）2、数据结构的概念2.1基本概念（识记）2.2数据结构及分类（识记）2.3数据结构课程的内容（识记）3、数据类型和抽象数据类型3.1数据类型（领会）3.2抽象数据类型（领会）4、算法和算法分析（应用）第二章线性表教学要点：通过本章的教学使学生初步了解线性表的结构特点；掌握顺序的和链式的存储结构各自特色；熟练掌握线性表的操作，以及链表的指针运算和各种链表的操作；理解循环链表以及双向链表。

数据结构之特殊矩阵特殊矩阵在数据结构中是一个重要的概念，它是一种具有特定性质的矩阵，可以帮助我们解决很多实际问题。

在本文中，我将介绍几种常见的特殊矩阵，并说明它们的结构和用途。

一、对称矩阵对称矩阵是指矩阵的第i行第j列元素等于第j行第i列元素的矩阵。

对称矩阵的主对角线上的元素对称于矩阵的副对角线上的元素。

对称矩阵在图论、物理学和金融学领域有广泛的应用。

例如，在图论中，对称矩阵常用于表示图的邻接矩阵。

二、上三角矩阵上三角矩阵是指矩阵的下三角部分全为0的矩阵。

上三角矩阵可以有效地节省内存空间，并且在矩阵乘法和矩阵求逆等运算中具有重要的作用。

在线性代数中，上三角矩阵常用于解线性方程组和计算特征值等问题。

三、下三角矩阵下三角矩阵是指矩阵的上三角部分全为0的矩阵。

和上三角矩阵一样，下三角矩阵也可以节省空间并且在矩阵运算中有重要的应用。

在数值分析中，下三角矩阵常用于求解线性方程组和计算矩阵的特征值。

四、稀疏矩阵稀疏矩阵是指矩阵中绝大部分元素为0的矩阵。

稀疏矩阵在图论、网络分析和机器学习等领域有广泛的应用。

由于稀疏矩阵的元素非常稀少，因此可以有效地压缩存储和加速计算过程。

在处理大规模数据时，稀疏矩阵的优势更加明显。

五、对角矩阵对角矩阵是指除了主对角线上的元素外，其他元素都为0的矩阵。

对角矩阵在线性代数和微分方程等领域有广泛的应用。

由于对角矩阵的特殊结构，其乘法和逆运算非常简单，可以提高计算效率。

六、压缩矩阵压缩矩阵是一种用于存储稀疏矩阵的数据结构。

常见的压缩矩阵包括行压缩矩阵、列压缩矩阵和坐标压缩矩阵。

压缩矩阵可以提高稀疏矩阵的存储效率，并且可以支持基本的矩阵运算。

总结起来，特殊矩阵是指具有一定特性的矩阵，包括对称矩阵、上三角矩阵、下三角矩阵、稀疏矩阵、对角矩阵和压缩矩阵等。

这些特殊矩阵在不同的领域和问题中有广泛的应用，能够提高存储效率和计算效率，对于处理大规模数据和复杂计算任务具有重要的作用。

因此，了解和熟悉特殊矩阵的结构和特点对于数据结构的学习和实践非常重要。

1. 解释下列术语：数据、数据元素、数据对象、数据结构、存储结构、线性结构、算法、 抽象数据类型。

2. 试举一个数据结构的例子，叙述其逻辑结构、存储结构及运算3方面的内容。

3. 选择题1）在数据结构中，从逻辑上可以把数据结构分成（ ）。

3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。

A. 数据具有同一特点B. 不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C. 每个数据元素都一样D. 数据元素所包含的数据项的个数要相等 4）以下说法正确的是（ ）。

A. 数据元素是数据的最小单位B. 数据项是数据的基木单位C. 数据结构是带有结构的各数据项的集合D. 一些表面上很不相同的数据可以有相同的逻辑结构4. 填空题1） _____________________________________________________________ 数据结构是一门研究非数值计算的程序设计问题中计算机的 ____________________________ 以及它们之I'可的 __________ 和运算等的学科。

2） ________________________________________________ 数据结构被形式定义为（D,R ）,其屮D 是 _______________________________________ 的有限集合，R 是D 上的___________ 有限集合。

3） ___________________________ 数据结构包括数据的 __ 、数据的 _______________ 和数据的 ____________________________ 这三个方面的内容。

A. 动态结构和静态结构 C.线性结构和非线性结构B. 紧凑结构和非紧凑结构D.内部结构和外部结构2）与数据元素本身的形式、 内容、相对位置、个数无关的是数据的（）。

《数据结构与算法》课程教学大纲课程代码：12281030适用专业：计算机应用技术总学时数： 68学时，其中：理论教学34学时，实践教学34学时。

学分：4.5先修课程：《C语言程序导论》、《程序设计导论》考核方式：机试一、制订大纲的依据本大纲根据2013年软件技术专业教学计划制订。

二、课程简介数据结构是介于数学、计算机硬件和计算机软件之间的一门计算机科学与技术专业的核心课程，是高级程序设计语言、编译原理、操作系统、数据库等课程的基础。

同时，数据结构技术也广泛应用于信息科学、系统工程、应用数学以及各种工程技术领域。

数据结构课程集中讨论软件开发过程中的设计阶段、同时设计编码和分析阶段的若干基本问题。

此外，为了构造出好的数据结构及其实现，还需考虑数据结构及其实现的评价与选择。

因此，数据结构的内容包括抽象、实现和评价三个层次，从数据表示和数据处理上看有五个基本组成“要素”分别是逻辑结构，存储结构、基本运算、算法及不同数据结构的比较与算法分析。

三、课程性质、教育目标(一)性质：本课程为计算机系软件技术专业的专业课。

（二）教育目标：通过本课程的学习，使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、编译原理和数据库等课程奠定基础。

四、课程教学内容与基本要求第一部分绪论(一)教学内容数据结构的基本概念和术语；抽象数据类型的表示；算法和算法分析。

(二)重点、难点重点：数据结构的基本概念及相关术语。

难点：算法的时间复杂度分析。

(三)教学基本要求知识要求：了解：抽象数据类型及面向对象概念；理解：算法的定义及算法的特性；掌握：数据结构的基本概念、算法的性能分析与度量方法。

第二部分线性表(一)教学内容1．线性表的定义及操作；2．线性表的顺序存储定义及操作实现；3．单链表的定义；单链表中的插入与删除；带表头结点的单链表；静态链表；4．循环链表的类定义及运算；5．双向链表的类定义及运算；6．线性表的应用：多项式及其相加。