下载文档原格式
第6章数组和广义表1．简述数组属于线性表的原因。
答：数组可以看成是线性表在下述含义上的扩展：线性表中的数据元素本身也是一个线性表。
在n维数组中的每个数据元素都受着n个关系的约束，在每个关系中，数据元素都有一个后继元素（除去最后一个元素）和一个前驱元素（除去最前一个元素）。
因此，这n个关系中的任一关系，就其单个关系而言仍是线性关系。
例如，m×n的二维数组的形式化定义如下：2．n阶对称矩阵A的下三角元素存储在一维数组B中，则B包含多少个元素?答：B中包含n阶对称矩阵A的下三角和主对角线上的元素，其元素个数为1+2+…+n=(n(n+1))/2，所以B包含(n(n+1))/2个元素。
3．设有三对角矩阵A n×n（从A1，1开始），将其三对角线上元素逐行存于数组B ［1．．m］中，使B［k］＝A i，j，求：（1）用i，j表示k的下标变换公式；（2）用k表示i，j的下标变换公式。
答：在三对角矩阵中，除了第一行和最后一行各有两个元素外，其余各行均有三个非零元素，所以共有3n-2个非零元素。
（1）主对角线左下角的对角线上的元素的下标有关系式：i=j+1，此时的k有：k=3(i-1)=2(i-1)+j主对角线上的元素的下标有关系式：i=j，此时的k有：k=3(i-1)+1=2(i-1)+j主对角线右上角的对角线上的元素的下标有关系式：i=j-1，此时的k有：k=3(i-1)+2=2(i-1)+j综合起来得到：k=2(i-1)+j（2）k与i，j的变换公式为：i=k/3+1；j=k-2(i-1)4．用十字链表表示一个有k个非0元素的m×n的稀疏矩阵，则其总的节点数为多少?答：该十字链表有一个十字链表头节点，MAX(m，n)个行、列头节点。
另外，每个非零元素对应一个节点，即k个元素节点，所以共有MAX(m，n)+k+1个节点。
5．设定二维整数数组B［0．．m-1，0．．n-1]的数据在行、列方向上都按从小到大的顺序排序，且整型变量x中的数据在B中存在。
李春葆《数据结构教程》（第4版）笔记和课后习题详解第8章图8.1复习笔记一、图的基本概念1．图的定义图都是由顶点和边构成的。
采用形式化的定义，图G由两个集合V和E组成，记为G ＝（V，E），其中V是顶点的有限集合，记为V（G），E是连接V中两个不同顶点（顶点对）的边的有限集合，记为E（G）。
抽象数据类型图的定义如下：2．图的基本术语（1）端点和邻接点在一个无向图中，若存在一条边（i，j），则称顶点i和顶点j为该边的两个端点，并称它们互为邻接点，即顶点i是顶点j的一个邻接点，顶点j也是顶点i的一个邻接点。
（2）顶点的度、入度和出度①度在无向图中，某顶点所具有的边的数目称为该顶点的度。
②入度在有向图中，顶点i的度又分为入度和出度，以顶点i为终点的入边的数目，称为该顶点的入度。
③出度以顶点i为起点的出边的数目，称为该顶点的出度。
一个顶点的入度与出度的和为该顶点的度。
（3）完全图若无向图中每两个顶点之间都存在一条边，或有向图中每两个顶点之间都存在着方向相反的两条边，则称此图为完全图。
（4）稠密图和稀疏图①稠密图当一个图接近完全图时，称为稠密图。
②稀疏图当一个图含有较少的边数（即当e＜＜n（n-1））时，则称为稀疏图。
（5）子图设有两个图G＝（V，E）和G′＝（V′，E′），若V′是V的子集，即V′≤V，且E′是E的子集，即E′≤E，则称G′是G的子图。
（6）路径和路径长度①路径在一个图G＝（V，E）中，从顶点i到顶点j的一条路径是一个顶点序列（i，i1，i2，…，i m），若此图G是无向图，则边（i，i1），（i1，i2），…，（i m－1，i m），（i m，j）属于E（G）；若此图是有向图，N<i，i1>，<i1，i2>，…，<i m－1，i m>，<i m，j>属于E（G）。
②路径长度路径长度是指一条路径上经过的边的数目。
（7）回路或环若一条路径上的开始点与结束点为同一个顶点，则称此路径为回路或环。
第1章绪论知识点归纳一、数据结构概述1.数据结构的定义（1）基本概念数据是描述客观事物的数和字符的集合，是计算机能操作的对象的总称，也是计算机处理信息的某种特定的符号表示形式。
（2）相关术语① 数据元素数据元素又称元素、节点、顶点、记录等。
数据元素是数据的基本单位。
有时候，一个数据元素可以由若干个数据项组成。
② 数据项数据项又称字段或域，它是具有独立含义的最小数据单位。
③ 数据对象数据对象是性质相同的数据元素的集合，它是数据的子集。
（3）数据结构的内容① 数据元素之间的逻辑关系，即数据的逻辑结构，它是数据结构在用户面前呈现的形式。
② 数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，又称数据的物理结构。
③ 施加在数据上的操作，即数据的运算。
（4）逻辑结构数据的逻辑结构是从逻辑关系（主要是指数据元素的相邻关系）上描述数据的，它与数据的存储无关，是独立于计算机的。
因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
（5）存储结构数据的存储结构是逻辑结构用计算机语言的实现或在计算机中的表示（又称映像），也就是逻辑结构在计算机中的存储方式，它是依赖于计算机语言的。
一般只在高级语言（例如C／C++语言）的层次上讨论存储结构。
数据的运算最终需在对应的存储结构上用算法实现。
总之，数据结构是一门讨论“描述现实世界实体的数学模型（通常为非数值计算）及其之上的运算在计算机中如何表示和实现”的学科。
（6）数据结构的表示对于一种数据结构，其逻辑结构总是惟一的，但它可能对应多种存储结构，并且在不同的存储结构中，同一运算的实现过程可能不同。
描述数据结构通常采用二元组表示：B=（D，R）其中，B是一种数据结构，它由数据元素的集合D和D上二元关系的集合R组成，即：D={d i | 1≤i≤n，n≥0}R={r j | 1≤j≤m，m≥0}其中d i表示集合D中的第i个数据元素（或节点），n为D中数据元素的个数，特别地，若n=0，则D 是一个空集。
李春葆《数据结构教程》（第4版）笔记和课后习题详解第11章外排序11.1复习笔记一、外排序概述文件存储在外存上，因此外排序方法与各种外存设备的特征有关。
外排序的基本方法是归并排序法。
它分为以下两个步骤：1．生成若干初始归并段（顺串）将一个文件（含待排序的数据）中的数据分段读入内存，在内存中对其进行内排序，并将经过排序的数据段（有序段）写到多个外存文件上。
2．多路归并对这些初始归并段进行多遍归并，使得有序的归并段逐渐扩大，最后在外存上形成整个文件的单一归并段，也就完成了这个文件的外排序。
二、磁盘排序1．磁盘排序概述磁盘是直接存取设备，读／写一个数据块的时间与当前读／写头所处的位置关系不大，存放在磁盘中的文件的排序属典型的外排序。
磁盘排序过程如图11-1所示.图11-1磁盘排序过程磁盘中的F in文件包括待排序的数据，通过相关算法将F in文件中数据一部分一部分地调入内存（每个记录被读一次）处理，产生若干个文件F1～F n（每个记录被写一次），它们都是有序的，称为顺串。
然后再次将F1～F n文件中的记录调入内存（每个记录被读一次），通过相关归并算法产生一个有序的F out文件（每个记录被写一次），从而达到数据排序的目的。
可见，提高排序速度很重要的一个方面是减少对数据的扫描遍数。
2．生成初始归并段使用置换—选择的排序算法用于生成较长的初始归并段。
采用置换—选择排序算法生成初始归并段时，内排序基于选择排序，即从若干个记录中通过关键字比较选择一个最小的记录，同时在此过程中进行记录的输入和输出，最后生成若干个长度可能各不相同的有序文件。
基本步骤如下：（1）从待排序文件F in中按内存工作区WA的容量（设为w）读入w个记录，设归并段编号i=1；（2）从WA中选出关键字最小的记录R min；（3）将R min 记录输出到文件F i 中，作为当前归并段的一个成员；（4）若F in 不空，则从F in 中读入下一个记录到WA 中替代刚输出的记录；（5）从WA 工作区中所有大于或等于R min 的记录中选择出最小记录作为新的R min ，转（3），直到选不出这样的R min ；（6）置i=i+1，开始一个新的归并段；（7）若WA 工作区已空，则初始归并段已全部产生，否则转（2）。
第2章线性表2.1 复习笔记一、线性表及其逻辑结构1．线性表的定义线性表是具有相同特性的数据元素的一个有限序列。
该序列中所含元素的个数叫做线性表的长度，用n表示，n≥0。
当n=0时，表示线性表是一个空表，即表中不包含任何元素。
2．线性表的表示设序列中第i（i表示逻辑序号）个元素为a i（1≤i≤n），则线性表的一般表示为：（a1，a2，…，a i，a i+1，…，a n）其中a1为第一个元素，又称做表头元素，a2为第二个元素，…，a n为最后一个元素，又称做表尾元素。
一个线性表可以用一个标识符来命名，如用L命名上面的线性表，则：L=（a1，a2，…，a i，a i+1，…，a n）线性表中的元素是与位置有关的，即第i个元素a i处在第i-1个元素a i-1的后面和第i+1个元素a i+1的前面。
这种位置上的有序性就是一种线性关系，所以线性表是一种线性结构，用二元组表示为：L=（D，R），其中：对应的逻辑结构如图2-1所示。
图2-1 线性表的逻辑结构示意图3．线性表的抽象数据类型描述抽象数据类型线性表的定义如下：二、线性表的顺序存储结构1．顺序表（1）线性表的存储结构线性表的顺序存储结构是把线性表中的所有元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中，如图2-2所示。
图2-2 线性表到顺序表的映射由于线性表中逻辑上相邻的两个元素在对应的顺序表中的存储位置也相邻，所以这种映射称为直接映射。
这样，线性表中第一个元素的存储位置就是指定的存储位置，第i+1个元素（1≤i≤n-1）的存储位置紧接在第i个元素的存储位置的后面。
假定线性表的元素类型为ElemType，则每个元素所占用存储空间大小（即字节数）为sizeof（ElemType），整个线性表所占用存储空间的大小为n×sizeof（ElemType），其中n表示线性表的长度。
在C／C++语言中，线性表的顺序存储结构是利用数组来实现的，数组的基本类型就是线性表中元素的类型，数组的大小要大于等于线性表的长度。
第4章串1．采用顺序结构存储串，编写一个实现串通配符匹配的算法pattern______index（），其中的通配符只有“？”，它可以和任一字符匹配成功，例如，pattern______index（″? re″，″there are″）返回的结果是2。
答：本题的基础是Brute—Force模式匹配算法，只是增加了“？”的处理功能。
对应的算法如下：2．有两个串s1和s2，设计一个算法求这样一个串，该串中的字符是s1和s2中的公共字符。
答：扫描s1，对于当前字符s1.data[i]，若在s2中，则将其加入到串s3中。
最后返回s3串。
对应的算法如下：3．设目标为t=’abcaabbabcabaacbacba’，模式p=’abcabaa’。
（1）计算模式P的nextval函数值。
（2）不写算法，只画出利用KMP算法进行模式匹配时的每一趟匹配过程。
答：（1）先计算next数组，在此基础上求nextval数组，如表4-1所示。
表4-1 计算next数组和nextval数组（2）采用KMP算法求子串位置的过程如下（开始时i=0，j=0）：第1趟匹配：此时i=4，j=4，匹配失败，而nextval[4]=0，则i=4，j=nextval[4]=0，即：第2趟匹配：此时i=6，j=2，匹配失败，而nextval[2]=0，则i=6，j=nextval[2]=0，即：第3趟匹配：此时i=6，j=0，匹配失败，而nextval[0]=-1，则i=6，j=nextval[0]=-1。
因j=-1，执行i=i+1=7，j=j+1=0，即：第4趟匹配：此时i=14，j=7，匹配成功，返回v=i-t．1ength=14-7=7。
上机实验题4实验题1编写一个程序algo4-1.cpp，实现顺序串的各种基本运算，并在此基础上设计一个程序exp4-1.cpp完成如下功能：（1）建立串s=″abcdefghefghijklmn″和串sl=″xyz″；（2）输出串s；（3）输出串s的长度；（4）在串s的第9个字符位置插入串s1而产生串s2；（5）输出串s2；（6）删除串s第2个字符开始的5个字符而产生串s2；（7）输出串s2；（8）将串s第2个字符开始的5个字符替换成串s1而产生串s2；（9）输出串s2；（10）提取串s的第2个字符开始的10个字符而产生串s3；（11）输出串s3；（12）将串s1和串s2连接起来而产生串s4；（13）输出串s4。
第6章数组和广义表一、选择题1．设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。
A．13B．33C．18D．40【答案】B【解析】对于对称矩阵,a i,j=a j,i。
为了节省存储空间，为多个相同的元素只分配一个存储空间。
对于对称矩阵，元素下表之间的对应关系为：当i>=j时，k=i(i-1)/2+j -1；当i< =j 时，k=j(j-1)/2+i-1。
其中k相当于地址空间的标号，i为行号，j为列号。
因为第一个元素存储地址为1，所以最后计算的k需要加1。
所以a85的存储位置为8*（8-1）/2+5=33。
2．设有数组A[i，j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为（）。
A．BA+141B．BA+180C．BA+222D．BA+225【答案】B【解析】在计算中，可以考虑按照列存放时，A[5,8]在内存的位置，比较容易计算元素的首地址。
比如A[5，8]顺序存放时，它是第7*8+5=61个元素，由于首地址为BA，所以它的存储首地址为BA+（61-1）*3=180+BA。
3．数组通常具有的两种基本操作是（）。
A．查找和修改B．查找和索引C．索引和修改D．建立和删除【答案】A【解析】数组中的元素是顺序存放的，通过下标可以很好地查找数组元素，同时通过对应的指针可以修改数组元素的值，因此数组通常具有的两种基本操作是查找和修改。
根据数组的性质，数组通常具有的两种基本运算是排序和查找。
4．将一个A[1．.100，1．.100]的三对角矩阵，按行优先存入一维数组B[1．.298]中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（）。
A．198B．195C．197【答案】B【解析】将对角矩阵a[i][j]存入b[k]，三对角矩阵压缩地址计算公式如下：k=2i+j-2。
第二部分课后习题第1章绪论1．简述数据与数据元素的关系与区别。
答：凡是能被计算机存储、加工的对象统称为数据，数据是一个集合。
数据元素是数据的基本单位，是数据的个体。
数据与元素之间的关系是元素与集合之间的关系。
2．数据结构和数据类型有什么区别？答：数据结构是互相之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，即数据的逻辑结构、存储结构和数据的运算。
而数据类型是一个值的集合和定义在这个集合上的一组运算的总称，如C语言中的int数据类型是由-32768~32767（16位机）的整数和+、-、*、/、%等运算符组成。
3．设3个表示算法频度的函数f、g和h分别为：f（n）=100n3+n2+1000g（n）=25n3+5000n2h（n）=n1.5+5000nlog2n求它们对应的时间复杂度。
答：f（n）=100n3+n2+1000=O（n3），g（n）=25n3+5000n2=O（n3），当n→∞时，√n>log2n，所以h（n）=n1.5+5000nlog2n=O（n1.5）。
4．用C／C++语言描述下列算法，并给出算法的时间复杂度。
（1）求一个n阶方阵的所有元素之和。
（2）对于输入的任意三个整数，将它们按从小到大的顺序输出。
（3）对于输入的任意n个整数，输出其中的最大和最小元素。
答：（1）算法如下：本算法的时间复杂度为O（n2）。
（2）算法如下：本算法的时间复杂度为O（1）。
（3）算法如下：本算法的时间复杂度为O（n）。
5．设n为正整数，给出下列各种算法关于n的时间复杂度。
（1）（2）（3）答：（1）设while循环语句执行次数为T（n），则：（2）算法中的基本运算语句是if（b[k]>b[j]）k=j，其执行次数T（n）为：（3）设while循环语句执行次数为T（n），则：则6．有以下递归算法用于对数组a[i．．j]的元素进行归并排序：求mergesort（a，0，n－1）的时间复杂度。
第二部分课后习题第1章绪论1．简述数据与数据元素的关系与区别。
答：凡是能被计算机存储、加工的对象统称为数据，数据是一个集合。
数据元素是数据的基本单位，是数据的个体。
数据与元素之间的关系是元素与集合之间的关系。
2．数据结构和数据类型有什么区别？答：数据结构是互相之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，即数据的逻辑结构、存储结构和数据的运算。
而数据类型是一个值的集合和定义在这个集合上的一组运算的总称，如C语言中的int数据类型是由-32768~32767（16位机）的整数和+、-、*、/、%等运算符组成。
3．设3个表示算法频度的函数f、g和h分别为：f（n）=100n3+n2+1000g（n）=25n3+5000n2h（n）=n1.5+5000nlog2n求它们对应的时间复杂度。
答：f（n）=100n3+n2+1000=O（n3），g（n）=25n3+5000n2=O（n3），当n→∞时，√n>log2n，所以h（n）=n1.5+5000nlog2n= O（n1.5）。
4．用C／C++语言描述下列算法，并给出算法的时间复杂度。
（1）求一个n阶方阵的所有元素之和。
（2）对于输入的任意三个整数，将它们按从小到大的顺序输出。
（3）对于输入的任意n个整数，输出其中的最大和最小元素。
答：（1）算法如下：本算法的时间复杂度为O（n2）。
（2）算法如下：本算法的时间复杂度为O（1）。
（3）算法如下：本算法的时间复杂度为O（n）。
5．设n为正整数，给出下列各种算法关于n的时间复杂度。
（1）（2）（3）答：（1）设while循环语句执行次数为T（n），则：（2）算法中的基本运算语句是if（b[k]>b[j]）k=j，其执行次数T（n）为：（3）设while循环语句执行次数为T（n），则：则6．有以下递归算法用于对数组a[i．．j]的元素进行归并排序：求mergesort（a，0，n－1）的时间复杂度。
第6章数组和广义表
6.1 复习笔记
一、数组
1．数组的基本概念
（1）数组的逻辑表示
从逻辑结构上看，数组A是由n（n>1）个相同类型数据元素a1，a2，…，a n构成的有限序列，其逻辑表示为：
A＝（a1，a2，…，a n）
其中，a i（1≤i≤n）表示数组A的第i个元素。
（2）多维数组
一个二维数组可以看做是每个数据元素都是相同类型一维数组的一维数组。
以此类推，任何多维数组都可以看做是一个线性表，且表中的每个数据元素也是一个线性表。
多维数组是线性表的推广。
推广到d（d≥3）维数组，不妨把它看做是一个以d-1维数组作为数据元素的线性表；或者这样理解，它是一种较复杂的线性表结构，由简单的数据结构即线性表辗转合成而得。
抽象数据类型d维数组定义如下：
2．数组的存储结构
（1）数组的性质
①数组中的数据元素数目固定，一旦定义了一个数组，其数据元素数目不再有增减的变化；
②数组中的数据元素具有相同的数据类型；
③数组中的每个数据元素都和惟一的下标值对应；
④数组是一种随机存储结构，可随机存取数组中的任意数据元素。
（2）数组的存储方式
①一维数组
由于数组的所有元素都存储在连续内存单元中，所以线性表的顺序存储结构应采用一维数组来描述。
在一维数组中，一旦a1的存储地址即LOC（a1）确定，且假设每个数据元素占用k个存储单元，则任一数据元素a i的存储地址LOC（a i）就可由以下公式求出：
LOC （a i ）＝LOC （a 1）+（i-1）×k（2≤i ≤n ）………………（6.1）
该式说明一维数组中任一数据元素的存储地址都可直接计算得到，即一维数组中任一数据元素都可直接存取。
所以一维数组具有随机存储特性。
②二维数组
二维及多维数组也具有随机存储特性。
对于一个m 行n 列的二维数组A m ×n ，有:
⎥⎥⎥⎥⎦
⎤⎢⎢⎢⎢⎣⎡=⨯n m m m n n n m a a a a a a a a a A ,2,1,,22,21,2,12,11,1 ………………………………………………（6.2） 将A m×n 简记为A ，A 是这样的一维数组：
A ＝（a 1，a 2，…，a i ，…，a m ）…………………………………（6.3）
其中，a i ＝（a i ，1，a i ，2，…a i ，n ）（1≤j ≤m ）
对于二维数组来说，由于计算机的存储结构是线性的，如何用线性的存储结构存放二维数组元素就有一个行／列排放次序问题。
对式（6.2）中m 行n 列的二维数组A m ×n ，当满足式（6.3）时，采用的即是以行序为主序的存储方式，即先存储第1行，然后紧接着存储第2行，最后存储第m 行。
此时，二维数组的线性排列次序为：
n m m m n n a a a a a a a a a ,2,1,,22,21,2,12,11,1,,,,,,,,,,,,
在大多数程序设计语言中采用的是以行序为主序的存储方式。
在FORTRAN 等少数程序设计语言中，采用的是以列序为主序的存储方式，即先存储第一列数据元素，紧接着存储第二列数据元素，最后存储第n 列数据元素。
对一个已知以行序为主序的计算机系统，当二维数组第一个数据元素a 1，1的存储地址 LOC （a 1，1）和每个数据元素所占用的存储单元k 确定后，该二维数组中任一数据元素a i ，j 的存储地址可由下式确定：
LOC （a i ，j ）=LOC （a 1，1）+［（i-1）×n+（j-1）］×k ……………………（6.4）
其中n 为列数。
由此可以得知：类似于一维数组，一旦二维数组的下标值确定，数据元素类型确定，各数组元素的存储位置也就可以确定，即二维数组也具有随机存储特性。
上述推导公式和结论可推广至三维甚至多维的数组。
以上的讨论均假设二维数组的行、列下界为1。
假设二维数组行下界是c 1，行上界是d 1，列下界是c 2，列上界是d 2，即数组A ［c 1,，c 2，d 2］，则式（6.4）可改写为：
k c j c d c i a LOC a LOC c c j i ⨯-++-⨯-+=)]()1()[()()(2221,,21……………（6.5）
3．特殊矩阵的压缩存储
特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。
（1）对称矩阵的压缩存储
①n 阶对称矩阵
若一个n 阶方阵A ［n ］［n ］中的元素满足a i ，j ＝a j ，i （0≤i ，j ≤n-1），则称其为n 阶对称矩阵。
②对称矩阵的压缩
假设以一维数组B ［0．．n （n+1）／2－1］作为n 阶对称矩阵A 的存储结构，在B 中只存储对称矩阵A 的下三角元素a i ，j （i ≥j ）。
假设A 的下三角中元素a i ，j 存储在B 数组的b k 元素中。
对于元素a i ，j ，不包括当前行，它前面共有i 行（行下标为0～i-1，行下标为0的行有1个元素，行下标为1的行有2个元素，…，行下标为i-1的行有i 个元素），则这i 行有1+2+…+i ＝i （i+1）／2个元素，在当前行中，元素a i ，j 的前面亦有j 个元素，即元素a i ，j 之前共有i （i+1）／2+j 个元素，即A 中任一元素a i ，j 和b k 之间存在着如下对应关系：
⎪⎪⎩⎪⎪⎨⎧≤++≥++=j i i j j j i j i i k 2
)1( 2)1( ③非对称矩阵的存储
有些非对称的矩阵也可借用此方法存储，如n 阶下（上）三角矩阵。
n 阶下（上）三角矩阵，是指矩阵的上（下）三角（不包括对角线）中的元素均为常数c 或0的n 阶方阵。
设以一维数组B ［0．．n （n+1）／2］作为n 阶三角矩阵A 的存储结构，则A 中任一元素a i ，j 和B 中元素b k 之间存在着如下对应关系：
上三角矩阵：
⎪⎪⎩⎪⎪⎨⎧≤+≥-++-=j i n n j i i j i n i k 2
)1( 2)12(* 下三角矩阵：
⎪⎪⎩⎪⎪⎨⎧≤+≥++=j i n n j i j i i k 2
)1( 2)1( 其中，B 的元素b n （n+1）/2中存放着常数c 。
（2）对角矩阵的压缩存储
若一个n 阶方阵A 其所有非零元素都集中在以主对角线为中心的带状区域中，则称之为n 阶对角矩阵。
若其主对角线上下方各有b 条次对角线，则称b 为矩阵半带宽，（2b+1）为矩阵带宽。
对于半带宽为b （0≤b ≤（n-1）／2）的对角矩阵，｜i-j ｜≤b 的元素a i ，j 不为零，其余元素为零。
半带宽为b 的对角矩阵示意图如图6-1所示。
图6-1 半带宽为b的对角矩阵
对于b=1的三对角矩阵，只存储其非零元素，并存储到一维数组B中，即将A的非零元素a i，j存储到B的元素b k中。
A中第0行和第n-1行都只有两个非零元素，其余各行均有3个非零元素。
对于不在第0行的非零元素a i，j来说，在它前面存储了矩阵的前i行元素，这些元素的总数为：2+3（i-1）。
若a i，j是本行中需要存储的第1个元素，则k＝2+3（i-1）=3i-1，此时，j＝i-1，即k=2i+i-1=2i+j。
若a i，j是本行中需要存储的第2个元素，则k=2+3（i-1）+1＝3i，此时，i=j，即k=2i+i=2i+j。
若a i，j是本行中需要存储的第3个元素，则k=2+3（i-1）+2＝3i+1，此时，j＝i+1，即k=2i+i+1=2i+j。
归纳起来有：k=2i+j。
（3）总结
以上讨论的对称矩阵、三角矩阵、对角矩阵的压缩存储方法是把有一定分布规律的值相同的元素（包括0）压缩存储到一个存储空间中。
这样的压缩存储只需在算法中按公式作映射即可实现矩阵元素的随机存取。
二、稀疏矩阵
1．稀疏矩阵的三元组表示
（1）表示方法
稀疏矩阵的压缩存储方法是只存储非零元素，由于稀疏矩阵中非零元素的分布没有任何规律，所以在存储非零元素时还必须同时存储该非零元素所对应的行下标和列下标。
这样，稀疏矩阵中的每一个非零元素需由一个三元组（i，j，a i，j）惟一确定，稀疏矩阵中的所有。
