武汉理工大学华夏学院 -信息工程系第 4章串、数组与广义表
4.1 串的定义与操作定义：串（ string） 是由零个或多个字符组成的有限序列，也称字符串。
记为,s＝,a0a1a2a3…a n”
其中 s称为串名,a0a1a2a3…a n称为串值,n
称为串的长度（即串中字符的个数），当 n
为零时称为空串。
子串：串中任意连续的字符组成的子序列，
称为原串（主串）的子串。
例如,a＝,abcd”,b＝,abc”,x＝,d”
主串 子串 子串武汉理工大学华夏学院 -信息工程系串的比较运算两串相等：两串的长度相等且对应位置的字符都相同时，称为两串相等。
当两串不等时按字典序比较大小。
注意,1.串值必须用“”括起来；
2,空串与空白串的区别：空串长度为 0，
空白串的长度大于 0；
常用的串操作有：
赋值：将一个串值 t赋给串变量 s；
复制：将一个串 s1赋给另一个串变量 s；
连接：两个串首尾相连，形成另一个新串；
以及判串相等、求串长、求子串、定位、插入、
删除、替换等操作。
武汉理工大学华夏学院 -信息工程系
4.2 串的存储结构一、串的顺序存储用一组地址连续的存储单元存储串值的字符序列,c语言中用字符数组来实现。
例如,char s1〔 20〕,name〔 8〕 等二、串的堆分配存储串变量的存储空间是在程序执行过程中动态分配得到的，程序中出现的所有串变量的值共享一个称为“堆”的存储空间。
三、串的链式存储用单链表来实现。
武汉理工大学华夏学院 -信息工程系
4.5 数组一,数组的概念：一组相同类型数据有序的组合，其中每一个数据称为数组元素设一个 m行 n列的矩阵 A为：
| a11 a12 · · · a1 n |
| a21 a22 · · · a2 n |
A=| · · · |
| · · · |
| am1 am 2 · · · am n |
武汉理工大学华夏学院 -信息工程系二、二维数组的处理方法
1,矩阵的逻辑特点设一个 m行 n列的矩阵 A为：
| a11 a12 · · · a1 n |
| a21 a22 · · · a2 n |
A=| · · · |
| · · · |
| am1 am 2 · · · am n |
武汉理工大学华夏学院 -信息工程系
2,矩阵的存储表示在程序设计中，一个矩阵通常用一个二维数组来表示，顺序存储在一个地址连续的存储区内，
具体实现分为：
可以把矩阵 A看成一个把每一行当成一个结点的线性表 B,则表 B的结点个数（表 B的长度）
为 m； 也可以把矩阵 A看成一个把每一列当成一个结点的线性表 C,则表 C的结点个数（表 C的长度）为 n。
武汉理工大学华夏学院 -信息工程系按列序优先顺序存储是从第一个元素 a11开始,先存储第一列；再存储第二列，以此类推，直到每一列存储完。
在存储各列时，又按第一行、第二行 …… 的次序。
例矩阵 A按列序优先顺序存储的结构图为图 6-1(b)所示。
按行序优先顺序存储是从第一个元素 a11开始，先存储第一行；再存储第二行，以此类推，直到每一行存储完。在存储各行时，又按第一列、第二列 …… 的次序。
例矩阵 A按行序优先顺序存储的结构图为图 6-1 (a)
所示。
（ 1） 按行序优先顺序存储
（ 2） 按列序优先顺序存储武汉理工大学华夏学院 -信息工程系
amn
….am2
...
a22a12
amn
….
a2n
...
a22
a21
(a)按行序优先存储表 (b)按列序优先存储表图 4-1矩阵的存储结构表示图
a1n
...
a12
a11
am1
...
a21
a11
武汉理工大学华夏学院 -信息工程系
loc(I,j)＝ loc(1,1)＋〔（ I－ 1）× n＋ j〕× s
若矩阵 A按列序优先顺序存储，则
loc(I,j)＝ loc(1,1)＋〔（ j－ 1）× m＋ i〕× s
若矩阵 A按行序优先顺序存储，则
（ 3） 矩阵中元素的寻址公式设矩阵 A的第一个元素 a11的首地址为
loc(1,1),每一个元素占用的存储单元数为 s，
则矩阵 A的第 I行，第 j列的元素 aij的首地址为：
武汉理工大学华夏学院 -信息工程系
4.6 矩阵的压缩存储一、特殊矩阵的压缩存储
1,压缩存储的概念对数组中的零元素不分配存储单元，只对非零元素分配存储单元进行存储的存储方法称为压缩存储。
其目的是节省存储空间。
2,特殊矩阵
（ 1）定义在矩阵中存在大量的零元素，且这些零元素的分布是有规律的一类矩阵。
武汉理工大学华夏学院 -信息工程系
（ 2） 常见的特殊矩阵
1) 对称阵（三角矩阵）
A,特点,为一个 n行 n列的矩阵，且第 I行第 j
列的元素值与第 j行第 I列的元素值相等。
B,存储,对称阵不需要用二维数组存储所有的 n× n个元素，只需存储其上三角或下三角中的元素即可。存储结构图见图 4-2。
武汉理工大学华夏学院 -信息工程系例如：一个 m行 m列的三角矩阵 A为：
| a11 0 0 0 。。。。 0 |
| a21 a22 0 0 。。。。 0 |
A=| · · · |
| · · · |
| am1 am 2 · · · am m |
即 当 i>=j是是非零值，当 i<j是为零值而 对称矩阵是 aij＝ aji
（ 1<=i,j<=m）
武汉理工大学华夏学院 -信息工程系
ann
(b)按行序优先存储上三角
….
a2n
...
a23
a22
a1n
...
a12
a11
ann
(a)按行序优先存储下三角图 4-2对称矩阵的存储结构表示图
….
an1
...
a33
a32
a31
a22
a21
a11
武汉理工大学华夏学院 -信息工程系一般均按行序优先顺序存储的对称矩阵元素地址为：
若存储下三角，
则 loc(i,j)＝ loc(1,1)＋ i(i-1)/2+j （ i>=j）
loc（ i,j)=loc(j,i) （ i<j)
若存储上三角，
则 loc(i,j)＝ loc(1,1)＋ j(j-1)/2+i （ i< j）
loc（ i,j)=loc(j,i) （ i>=j)
显然,三角矩阵的元素地址在
i>=j时与对称矩阵相同；
在 i<j时 loc（ i,j)=0
武汉理工大学华夏学院 -信息工程系
（ 2) 对角阵
A.特点,为一个 n行 n列的矩阵，且所有的非零元素都集中在以主对角线为中心的带状区域中，也称为带状矩阵。
B,存储,与对称阵一样,对角阵不需要用二维数组存储所有的 n× n个元素，只需存储其中有规律排列的非零元素即可。
一般均按行序优先顺序存储。
武汉理工大学华夏学院 -信息工程系二,稀疏矩阵及存储
（ 1) 定义矩阵中非零元素的个数远远地少于零元素的个数的矩阵。
（ 2) 特点零元素多，非零元素少，且排列无规律。
（ 3) 存储方法采用压缩存储的方法只存储非零元素及非零元素在矩阵中的位置（行、列号）。即：每一个非零元素可以用一个三元组表示（ 行下标,列下标,元素值），把矩阵中的所有非零元素按行序优先顺序（或列序优先）构成一个线性表（称为三元组表 ） 。
如图 4-3所示。
武汉理工大学华夏学院 -信息工程系设矩阵 A为一个 5× 5的方阵
A=
3 0 0 0 7
0 0 -1 0 0
-1 -2 0 0 0
0 0 0 0 0
0 0 0 2 0
5 5 6 5 5 6
0 0 3
0 4 7
1 2 － 1
2 0 － 1
2 1 － 2
按行序优先存储
0 0 3
2 0 － 1
1 2 － 1
4 3 2
0 4 7
按列序优先存储
4 3 2
2 1 － 2
图 4-3 三元组表存储稀疏矩阵结构图行 列 值 行 列 值武汉理工大学华夏学院 -信息工程系
（ 1) 建立稀疏矩阵的三元组存储对于给定的稀疏矩阵 A,产生对应的三元组存储 B
typedef int smat[MAX][3] ;
void creatmat(int A[M][N],smat B)
{ int i,j,k=1;
for (i=0;I<M;i++) /*按行优先扫描 A的元素，不为 0者存入 B*/
for（ j＝ 0； j<N;j++）
if（ A [i][j]！＝ 0）
｛ B [k][0]＝ I； B [k][1]＝ j； B [k][2]＝ A [i][j] ；
k++；｝
B [0][0]＝ M； B [0][1]＝ N； B [0][2]＝ k－ 1；
/*存入非零元素的个数，制作三员组表的头 */
｝
三元组表的基本操作武汉理工大学华夏学院 -信息工程系
（ 2) 查找稀疏矩阵的元素对于给定的稀疏矩阵的三元组 A中查找元素 x,
若存在返回 1；否则返回 0。
int findval( smat A,int x)
{ int i,t ;
t＝ A[0][2];
/*t为非零元素的个数 */
i＝ 1；
while （ i<=t && A[i][2]!=x) i++ ；
if（ i！＝ t） return （ 1）
else return （ 0）
｝
武汉理工大学华夏学院 -信息工程系
（ 3) 稀疏矩阵相加对于给定的两个大小相同的稀疏矩阵的三元组 A，
B，产生相加后的稀疏矩阵的三元
void matadd( smat A,smat B,smat C)
{ int i=1,j＝ 1； k＝ 1;
while （ i<=A[0][2] && j<=B[0][2] )
if(A[i][0]==B[j][0])
if(A[i][1]<B[j][1])
{ C[k][0]= A[i][0];
C[k][1]= A[i][1];
C[k][2]= A[i][2];
k++; i++;
｝
方法：若 A的当前行号等于 B的行号，则比较列号，将小列的存入 C,若列号相等则相加后存入 C的对应行、列号元素中。
武汉理工大学华夏学院 -信息工程系
else if(A[i][1]>B[j][1])
｛ C[k][0]= B[i][0]; C[k][1]= B[i][1];
C[k][2]= B[i][2]; k++; j++;
｝
else
｛ C[k][0]= B[i][0]; C[k][1]= B[i][1];
C[k][2]= A[i][2] ＋ B[i][2];
k++; i++; j++;｝
else if(A[i][0]<B[j][0])
/*若 A当前行号小于 B当前行号，则送 B的值 */
｛ C[k][0]= A[i][0]; C[k][1]= A[i][1];
C[k][2]= A[i][2]; k++; i++;
｝
武汉理工大学华夏学院 -信息工程系
else /*若 A当前行号大于 B当前行号，则送 B的值 */
｛ C[k][0]= B[i][0];
C[k][1]= B[i][1];
C[k][2]= B[i][2];
k++; j++;
｝
C[0][0]= A[0][0];
C[0][1]= A[0][1];
C[0][2]= k－ 1;
｝
产生第 0行的结果武汉理工大学华夏学院 -信息工程系
（ 4) 稀疏矩阵的显示以三元组的形式显示稀疏矩阵 A中的非零元素 。
void display( smat A,char*s)
{ int i ;
printf(“%s 三元组,\n\t Row Col Val\n”,s)；
for(i=1;i<=A[0][2];i++)
printf(“\t%4d%4d%4d\n”,
A[i][0],A[i][1],A[i][2]）；
｝
思考：输出正常矩阵如何实现？
武汉理工大学华夏学院 -信息工程系
（ 5) 调试程序
#defile Max 100
#defile M 3
#defile N 3
#defile K 3
main()
｛
int A[M][N]={{0,1,0,{2,0,0},{1,0,0}};
int B[M][N]={{1,2,0,{0,1,0},{0,2,0}};
smat C,D,E,F,G;
武汉理工大学华夏学院 -信息工程系
creatmat(A,C);
creatmat(B,D);
display(“A矩阵”,C) ;
printf(“c(0,1)处的值：％ d\n”,c[0[1]）；
printf(“元素 3是否存在：％ d\n”findval(c,3))；
matadd(C,D,E);
display(“E=A+B”,E) ;
｝
思考：两个矩阵相乘、求转置矩阵等稀疏矩阵的常规运算的算法。
武汉理工大学华夏学院 -信息工程系对于非零元素的个数和位置变化较大的稀疏矩阵，可以采用十字链表表示。十字链表的结构是每个结点包含五个字段：
行下标,行指针,元素值,列下标,列指针其中,行指针指明同一行中下一个非零元素的位置 ；
列指针指明同一列中下一个非零元素的位置；
其余三个字段的内容同三元组表。
同一行中的非零元素通过行指针链接成一个链表，同一列中的非零元素通过列指针链接成一个链表。整个矩阵构成了一个十字交叉的链表，故称为十字链表。
图 4.4表示了一个矩阵 A的十字链表存储结构。
武汉理工大学华夏学院 -信息工程系
A=
3 2 0 5
0 -1 0 0
2 0 0 0
0 0 0 0
4 4 5 0 0 0 0 0 0 0 0 00 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0 0 0 0 0 0 0
0 0 0
0 0 0
head
图 4.4 矩阵 A的十字链表存储结构。
武汉理工大学华夏学院 -信息工程系
4.7 广义表一、广义表的逻辑特点
1,定义 一个长度为 n的广义表 L由 n个元素组成，元素之间的关系是一种线性关系，可以用
L=(a1,a2,…….a n ) 表示。其中的每一个元素
ai（ 1<=I<=n） 可以是原子（单个元素 ),也可以是子表的广义表。
2,特点 广义表是线性表的推广，表中的元素允许有两种类型（即原子和子表 ); 对于原子应有相同的类型,而子表可以具有不同的结构。
武汉理工大学华夏学院 -信息工程系
（ 1) 空表 A=() 该表没有元素，称为空 表。
（ 2) 有一个子表为空表的元素的表 B=(())
注：该表有一个元素。
（ 3) 既有原子又有子表的表 C=(a,（ b,c,d ))
注：该表有两个元素，其一为原子 a，
其二为子表 （ b,c,d）
3,几种典型的广义表武汉理工大学华夏学院 -信息工程系二,广义表的存储表示广义表采用链接方法存储：链表中的每一个结点代表广义表中的一个元素，其结点形式如图 4-5所示。
对于前面说明的几种典型的广义表其存储结构表示如图 4-6。
三、广义表结点类型的描述在 C语言中可以采用结构体描述（ C＋＋ 中用联合体,pascal中用记录描述 ）。
武汉理工大学华夏学院 -信息工程系
atom next 原子结点
head next 子表结点
tag next 通用表结点x
图 4-5 广义表中的结点形式武汉理工大学华夏学院 -信息工程系
A
1 ^ ^
（ 1) 空表
B
1 ^
（ 2) 具有空元素的表
1 ^ ^
C
1 ^ （ 3)具有一个原子一个子表的表
0 a 0 ^
0 b 0 c 0 d ^
图 4-6几个特殊的广义表的链接存储结构武汉理工大学华夏学院 -信息工程系具体描述为,
struct node /*表结点 */
{ int tog ; /*=1标识子表结点 */
struct node * child ； /*指向子表指针 */
struct node * next；
｝ /*指向下一个元素指针 */
struct node /*数据元素结点 */
{int tog ; /*=0标识原子结点 */
Int val; /*值域 */
struct node * next；
｝ /*指向下一个元素指针 */}
武汉理工大学华夏学院 -信息工程系
struct node
{ int tog ; /*=1标识子表结点,=0标识原子结点 */
union ｛
struct node * child ； /*指向子表指针 */
Int val; /*值域 */
struct node * next；
｝ /*指向下一个元素指针 */}
在该结构中,tag＝ 1表示该结点是表结点，联合中取 child域，而 tag＝ 0表示该结点是数据结点，在联合中取 val域。
为了便于处理，将 val和 child域以联合的方式存储,其结构定义为：
武汉理工大学华夏学院 -信息工程系
（ 1) A=( )是一个空广义表,
（ 2) B=(a，（ b,c,d)） B包含两个元素，一个为原子
a，另一个是子表（ b,c,d).
（ 3) C＝（ e）,C中只有一个原子元素 e。
（ 4) D＝（ A,B,C,f）,D中包含四个元素，前三个为子表，后一个为原子元素。
（ 5) E=(a,E）,E为一个递归表，它包含有两个元素，一个是原子 a，另一个子表为其自身。
这几个表的存储结构用图 4-7表示如下。
例如：
武汉理工大学华夏学院 -信息工程系
1 ^ ^
A
1 ^
B
0 a 1 ^
0 b
1 ^ 1 ^
1 0 f ^1 ^ 1
0 a 1 ^
0 c 0 d ^
C D
0 e ^
1 ^ ^
E
图 4-7广义表的存储结构武汉理工大学华夏学院 -信息工程系四、广义表的运算
1,创建广义表按递归的方法建立广义表的链接存储结构是创建广义表的基本方法。设广义表中的原子元素的类型为字符类型，一个非空的广义表可以由两部分组成（左部，右部）其中左部是一个元素，右部是一系列由逗号分割的元素（可以是原子也可以是子表），创建广义表的基本思想是：从字符序列中分离出左部和右部，依次为左部和右部建立存储。以建立一个无共享的广义表 A=(a，（ b,c),d)，其算法 如下。
武汉理工大学华夏学院 -信息工程系
struct node
{ int tog ;
union
｛ struct node * child ；
char val;
｝ content;
struct node * next；
｝；
typedef struct node NODE;
int=0;
char str〔 20]＝“（ a,（ b,c),d)”；
NODE*create()
｛ NODE *P； char ch；
ch＝ str〔 i]； i＋＋ ；
武汉理工大学华夏学院 -信息工程系
Switch(ch)
｛ case?(?,
p＝（ NODE*)malloc（ sizeof（ NODE))； p->tag＝ 1;
P->content.child＝ create();
P->next＝ create() ; break；
Case?a?,case?b?,case?c?,case?d?,p＝
（ NODE*)malloc（ sizeof（ NODE))； p->tag＝ 0
P->content.val＝ ch;
P->next＝ create() ; break；
case?,?,p＝ create() ； breate ；
Case?)? case?\0?,p＝ NULL；
｝ i＋＋ ；
return(p) ｝
武汉理工大学华夏学院 -信息工程系设有两个广义表 S和 T,si是广义表 S中的第 I个元素,ti
是广义表 T中的第 I个元素，两个广义表相等的条件是：
若 si是原子，则 ti是和 si相同的原子；若 si是子表，则
ti 是和 si 相同的子表。判断两个广义表是否相等的算法就是对其对应元素进行比较。
2,判两个广义表是否相等
3,复制广义表
4,求广义表的长度这些都是广义表的一些基本运算，一般采用递归方法实现，具体算法可参阅参考书籍。
4.1 串的定义与操作定义：串（ string） 是由零个或多个字符组成的有限序列，也称字符串。
记为,s＝,a0a1a2a3…a n”
其中 s称为串名,a0a1a2a3…a n称为串值,n
称为串的长度（即串中字符的个数），当 n
为零时称为空串。
子串：串中任意连续的字符组成的子序列，
称为原串（主串）的子串。
例如,a＝,abcd”,b＝,abc”,x＝,d”
主串 子串 子串武汉理工大学华夏学院 -信息工程系串的比较运算两串相等：两串的长度相等且对应位置的字符都相同时，称为两串相等。
当两串不等时按字典序比较大小。
注意,1.串值必须用“”括起来；
2,空串与空白串的区别：空串长度为 0，
空白串的长度大于 0；
常用的串操作有：
赋值：将一个串值 t赋给串变量 s；
复制：将一个串 s1赋给另一个串变量 s；
连接：两个串首尾相连，形成另一个新串；
以及判串相等、求串长、求子串、定位、插入、
删除、替换等操作。
武汉理工大学华夏学院 -信息工程系
4.2 串的存储结构一、串的顺序存储用一组地址连续的存储单元存储串值的字符序列,c语言中用字符数组来实现。
例如,char s1〔 20〕,name〔 8〕 等二、串的堆分配存储串变量的存储空间是在程序执行过程中动态分配得到的，程序中出现的所有串变量的值共享一个称为“堆”的存储空间。
三、串的链式存储用单链表来实现。
武汉理工大学华夏学院 -信息工程系
4.5 数组一,数组的概念：一组相同类型数据有序的组合，其中每一个数据称为数组元素设一个 m行 n列的矩阵 A为：
| a11 a12 · · · a1 n |
| a21 a22 · · · a2 n |
A=| · · · |
| · · · |
| am1 am 2 · · · am n |
武汉理工大学华夏学院 -信息工程系二、二维数组的处理方法
1,矩阵的逻辑特点设一个 m行 n列的矩阵 A为：
| a11 a12 · · · a1 n |
| a21 a22 · · · a2 n |
A=| · · · |
| · · · |
| am1 am 2 · · · am n |
武汉理工大学华夏学院 -信息工程系
2,矩阵的存储表示在程序设计中，一个矩阵通常用一个二维数组来表示，顺序存储在一个地址连续的存储区内，
具体实现分为：
可以把矩阵 A看成一个把每一行当成一个结点的线性表 B,则表 B的结点个数（表 B的长度）
为 m； 也可以把矩阵 A看成一个把每一列当成一个结点的线性表 C,则表 C的结点个数（表 C的长度）为 n。
武汉理工大学华夏学院 -信息工程系按列序优先顺序存储是从第一个元素 a11开始,先存储第一列；再存储第二列，以此类推，直到每一列存储完。
在存储各列时，又按第一行、第二行 …… 的次序。
例矩阵 A按列序优先顺序存储的结构图为图 6-1(b)所示。
按行序优先顺序存储是从第一个元素 a11开始，先存储第一行；再存储第二行，以此类推，直到每一行存储完。在存储各行时，又按第一列、第二列 …… 的次序。
例矩阵 A按行序优先顺序存储的结构图为图 6-1 (a)
所示。
（ 1） 按行序优先顺序存储
（ 2） 按列序优先顺序存储武汉理工大学华夏学院 -信息工程系
amn
….am2
...
a22a12
amn
….
a2n
...
a22
a21
(a)按行序优先存储表 (b)按列序优先存储表图 4-1矩阵的存储结构表示图
a1n
...
a12
a11
am1
...
a21
a11
武汉理工大学华夏学院 -信息工程系
loc(I,j)＝ loc(1,1)＋〔（ I－ 1）× n＋ j〕× s
若矩阵 A按列序优先顺序存储，则
loc(I,j)＝ loc(1,1)＋〔（ j－ 1）× m＋ i〕× s
若矩阵 A按行序优先顺序存储，则
（ 3） 矩阵中元素的寻址公式设矩阵 A的第一个元素 a11的首地址为
loc(1,1),每一个元素占用的存储单元数为 s，
则矩阵 A的第 I行，第 j列的元素 aij的首地址为：
武汉理工大学华夏学院 -信息工程系
4.6 矩阵的压缩存储一、特殊矩阵的压缩存储
1,压缩存储的概念对数组中的零元素不分配存储单元，只对非零元素分配存储单元进行存储的存储方法称为压缩存储。
其目的是节省存储空间。
2,特殊矩阵
（ 1）定义在矩阵中存在大量的零元素，且这些零元素的分布是有规律的一类矩阵。
武汉理工大学华夏学院 -信息工程系
（ 2） 常见的特殊矩阵
1) 对称阵（三角矩阵）
A,特点,为一个 n行 n列的矩阵，且第 I行第 j
列的元素值与第 j行第 I列的元素值相等。
B,存储,对称阵不需要用二维数组存储所有的 n× n个元素，只需存储其上三角或下三角中的元素即可。存储结构图见图 4-2。
武汉理工大学华夏学院 -信息工程系例如：一个 m行 m列的三角矩阵 A为：
| a11 0 0 0 。。。。 0 |
| a21 a22 0 0 。。。。 0 |
A=| · · · |
| · · · |
| am1 am 2 · · · am m |
即 当 i>=j是是非零值，当 i<j是为零值而 对称矩阵是 aij＝ aji
（ 1<=i,j<=m）
武汉理工大学华夏学院 -信息工程系
ann
(b)按行序优先存储上三角
….
a2n
...
a23
a22
a1n
...
a12
a11
ann
(a)按行序优先存储下三角图 4-2对称矩阵的存储结构表示图
….
an1
...
a33
a32
a31
a22
a21
a11
武汉理工大学华夏学院 -信息工程系一般均按行序优先顺序存储的对称矩阵元素地址为：
若存储下三角，
则 loc(i,j)＝ loc(1,1)＋ i(i-1)/2+j （ i>=j）
loc（ i,j)=loc(j,i) （ i<j)
若存储上三角，
则 loc(i,j)＝ loc(1,1)＋ j(j-1)/2+i （ i< j）
loc（ i,j)=loc(j,i) （ i>=j)
显然,三角矩阵的元素地址在
i>=j时与对称矩阵相同；
在 i<j时 loc（ i,j)=0
武汉理工大学华夏学院 -信息工程系
（ 2) 对角阵
A.特点,为一个 n行 n列的矩阵，且所有的非零元素都集中在以主对角线为中心的带状区域中，也称为带状矩阵。
B,存储,与对称阵一样,对角阵不需要用二维数组存储所有的 n× n个元素，只需存储其中有规律排列的非零元素即可。
一般均按行序优先顺序存储。
武汉理工大学华夏学院 -信息工程系二,稀疏矩阵及存储
（ 1) 定义矩阵中非零元素的个数远远地少于零元素的个数的矩阵。
（ 2) 特点零元素多，非零元素少，且排列无规律。
（ 3) 存储方法采用压缩存储的方法只存储非零元素及非零元素在矩阵中的位置（行、列号）。即：每一个非零元素可以用一个三元组表示（ 行下标,列下标,元素值），把矩阵中的所有非零元素按行序优先顺序（或列序优先）构成一个线性表（称为三元组表 ） 。
如图 4-3所示。
武汉理工大学华夏学院 -信息工程系设矩阵 A为一个 5× 5的方阵
A=
3 0 0 0 7
0 0 -1 0 0
-1 -2 0 0 0
0 0 0 0 0
0 0 0 2 0
5 5 6 5 5 6
0 0 3
0 4 7
1 2 － 1
2 0 － 1
2 1 － 2
按行序优先存储
0 0 3
2 0 － 1
1 2 － 1
4 3 2
0 4 7
按列序优先存储
4 3 2
2 1 － 2
图 4-3 三元组表存储稀疏矩阵结构图行 列 值 行 列 值武汉理工大学华夏学院 -信息工程系
（ 1) 建立稀疏矩阵的三元组存储对于给定的稀疏矩阵 A,产生对应的三元组存储 B
typedef int smat[MAX][3] ;
void creatmat(int A[M][N],smat B)
{ int i,j,k=1;
for (i=0;I<M;i++) /*按行优先扫描 A的元素，不为 0者存入 B*/
for（ j＝ 0； j<N;j++）
if（ A [i][j]！＝ 0）
｛ B [k][0]＝ I； B [k][1]＝ j； B [k][2]＝ A [i][j] ；
k++；｝
B [0][0]＝ M； B [0][1]＝ N； B [0][2]＝ k－ 1；
/*存入非零元素的个数，制作三员组表的头 */
｝
三元组表的基本操作武汉理工大学华夏学院 -信息工程系
（ 2) 查找稀疏矩阵的元素对于给定的稀疏矩阵的三元组 A中查找元素 x,
若存在返回 1；否则返回 0。
int findval( smat A,int x)
{ int i,t ;
t＝ A[0][2];
/*t为非零元素的个数 */
i＝ 1；
while （ i<=t && A[i][2]!=x) i++ ；
if（ i！＝ t） return （ 1）
else return （ 0）
｝
武汉理工大学华夏学院 -信息工程系
（ 3) 稀疏矩阵相加对于给定的两个大小相同的稀疏矩阵的三元组 A，
B，产生相加后的稀疏矩阵的三元
void matadd( smat A,smat B,smat C)
{ int i=1,j＝ 1； k＝ 1;
while （ i<=A[0][2] && j<=B[0][2] )
if(A[i][0]==B[j][0])
if(A[i][1]<B[j][1])
{ C[k][0]= A[i][0];
C[k][1]= A[i][1];
C[k][2]= A[i][2];
k++; i++;
｝
方法：若 A的当前行号等于 B的行号，则比较列号，将小列的存入 C,若列号相等则相加后存入 C的对应行、列号元素中。
武汉理工大学华夏学院 -信息工程系
else if(A[i][1]>B[j][1])
｛ C[k][0]= B[i][0]; C[k][1]= B[i][1];
C[k][2]= B[i][2]; k++; j++;
｝
else
｛ C[k][0]= B[i][0]; C[k][1]= B[i][1];
C[k][2]= A[i][2] ＋ B[i][2];
k++; i++; j++;｝
else if(A[i][0]<B[j][0])
/*若 A当前行号小于 B当前行号，则送 B的值 */
｛ C[k][0]= A[i][0]; C[k][1]= A[i][1];
C[k][2]= A[i][2]; k++; i++;
｝
武汉理工大学华夏学院 -信息工程系
else /*若 A当前行号大于 B当前行号，则送 B的值 */
｛ C[k][0]= B[i][0];
C[k][1]= B[i][1];
C[k][2]= B[i][2];
k++; j++;
｝
C[0][0]= A[0][0];
C[0][1]= A[0][1];
C[0][2]= k－ 1;
｝
产生第 0行的结果武汉理工大学华夏学院 -信息工程系
（ 4) 稀疏矩阵的显示以三元组的形式显示稀疏矩阵 A中的非零元素 。
void display( smat A,char*s)
{ int i ;
printf(“%s 三元组,\n\t Row Col Val\n”,s)；
for(i=1;i<=A[0][2];i++)
printf(“\t%4d%4d%4d\n”,
A[i][0],A[i][1],A[i][2]）；
｝
思考：输出正常矩阵如何实现？
武汉理工大学华夏学院 -信息工程系
（ 5) 调试程序
#defile Max 100
#defile M 3
#defile N 3
#defile K 3
main()
｛
int A[M][N]={{0,1,0,{2,0,0},{1,0,0}};
int B[M][N]={{1,2,0,{0,1,0},{0,2,0}};
smat C,D,E,F,G;
武汉理工大学华夏学院 -信息工程系
creatmat(A,C);
creatmat(B,D);
display(“A矩阵”,C) ;
printf(“c(0,1)处的值：％ d\n”,c[0[1]）；
printf(“元素 3是否存在：％ d\n”findval(c,3))；
matadd(C,D,E);
display(“E=A+B”,E) ;
｝
思考：两个矩阵相乘、求转置矩阵等稀疏矩阵的常规运算的算法。
武汉理工大学华夏学院 -信息工程系对于非零元素的个数和位置变化较大的稀疏矩阵，可以采用十字链表表示。十字链表的结构是每个结点包含五个字段：
行下标,行指针,元素值,列下标,列指针其中,行指针指明同一行中下一个非零元素的位置 ；
列指针指明同一列中下一个非零元素的位置；
其余三个字段的内容同三元组表。
同一行中的非零元素通过行指针链接成一个链表，同一列中的非零元素通过列指针链接成一个链表。整个矩阵构成了一个十字交叉的链表，故称为十字链表。
图 4.4表示了一个矩阵 A的十字链表存储结构。
武汉理工大学华夏学院 -信息工程系
A=
3 2 0 5
0 -1 0 0
2 0 0 0
0 0 0 0
4 4 5 0 0 0 0 0 0 0 0 00 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0 0 0 0 0 0 0
0 0 0
0 0 0
head
图 4.4 矩阵 A的十字链表存储结构。
武汉理工大学华夏学院 -信息工程系
4.7 广义表一、广义表的逻辑特点
1,定义 一个长度为 n的广义表 L由 n个元素组成，元素之间的关系是一种线性关系，可以用
L=(a1,a2,…….a n ) 表示。其中的每一个元素
ai（ 1<=I<=n） 可以是原子（单个元素 ),也可以是子表的广义表。
2,特点 广义表是线性表的推广，表中的元素允许有两种类型（即原子和子表 ); 对于原子应有相同的类型,而子表可以具有不同的结构。
武汉理工大学华夏学院 -信息工程系
（ 1) 空表 A=() 该表没有元素，称为空 表。
（ 2) 有一个子表为空表的元素的表 B=(())
注：该表有一个元素。
（ 3) 既有原子又有子表的表 C=(a,（ b,c,d ))
注：该表有两个元素，其一为原子 a，
其二为子表 （ b,c,d）
3,几种典型的广义表武汉理工大学华夏学院 -信息工程系二,广义表的存储表示广义表采用链接方法存储：链表中的每一个结点代表广义表中的一个元素，其结点形式如图 4-5所示。
对于前面说明的几种典型的广义表其存储结构表示如图 4-6。
三、广义表结点类型的描述在 C语言中可以采用结构体描述（ C＋＋ 中用联合体,pascal中用记录描述 ）。
武汉理工大学华夏学院 -信息工程系
atom next 原子结点
head next 子表结点
tag next 通用表结点x
图 4-5 广义表中的结点形式武汉理工大学华夏学院 -信息工程系
A
1 ^ ^
（ 1) 空表
B
1 ^
（ 2) 具有空元素的表
1 ^ ^
C
1 ^ （ 3)具有一个原子一个子表的表
0 a 0 ^
0 b 0 c 0 d ^
图 4-6几个特殊的广义表的链接存储结构武汉理工大学华夏学院 -信息工程系具体描述为,
struct node /*表结点 */
{ int tog ; /*=1标识子表结点 */
struct node * child ； /*指向子表指针 */
struct node * next；
｝ /*指向下一个元素指针 */
struct node /*数据元素结点 */
{int tog ; /*=0标识原子结点 */
Int val; /*值域 */
struct node * next；
｝ /*指向下一个元素指针 */}
武汉理工大学华夏学院 -信息工程系
struct node
{ int tog ; /*=1标识子表结点,=0标识原子结点 */
union ｛
struct node * child ； /*指向子表指针 */
Int val; /*值域 */
struct node * next；
｝ /*指向下一个元素指针 */}
在该结构中,tag＝ 1表示该结点是表结点，联合中取 child域，而 tag＝ 0表示该结点是数据结点，在联合中取 val域。
为了便于处理，将 val和 child域以联合的方式存储,其结构定义为：
武汉理工大学华夏学院 -信息工程系
（ 1) A=( )是一个空广义表,
（ 2) B=(a，（ b,c,d)） B包含两个元素，一个为原子
a，另一个是子表（ b,c,d).
（ 3) C＝（ e）,C中只有一个原子元素 e。
（ 4) D＝（ A,B,C,f）,D中包含四个元素，前三个为子表，后一个为原子元素。
（ 5) E=(a,E）,E为一个递归表，它包含有两个元素，一个是原子 a，另一个子表为其自身。
这几个表的存储结构用图 4-7表示如下。
例如：
武汉理工大学华夏学院 -信息工程系
1 ^ ^
A
1 ^
B
0 a 1 ^
0 b
1 ^ 1 ^
1 0 f ^1 ^ 1
0 a 1 ^
0 c 0 d ^
C D
0 e ^
1 ^ ^
E
图 4-7广义表的存储结构武汉理工大学华夏学院 -信息工程系四、广义表的运算
1,创建广义表按递归的方法建立广义表的链接存储结构是创建广义表的基本方法。设广义表中的原子元素的类型为字符类型，一个非空的广义表可以由两部分组成（左部，右部）其中左部是一个元素，右部是一系列由逗号分割的元素（可以是原子也可以是子表），创建广义表的基本思想是：从字符序列中分离出左部和右部，依次为左部和右部建立存储。以建立一个无共享的广义表 A=(a，（ b,c),d)，其算法 如下。
武汉理工大学华夏学院 -信息工程系
struct node
{ int tog ;
union
｛ struct node * child ；
char val;
｝ content;
struct node * next；
｝；
typedef struct node NODE;
int=0;
char str〔 20]＝“（ a,（ b,c),d)”；
NODE*create()
｛ NODE *P； char ch；
ch＝ str〔 i]； i＋＋ ；
武汉理工大学华夏学院 -信息工程系
Switch(ch)
｛ case?(?,
p＝（ NODE*)malloc（ sizeof（ NODE))； p->tag＝ 1;
P->content.child＝ create();
P->next＝ create() ; break；
Case?a?,case?b?,case?c?,case?d?,p＝
（ NODE*)malloc（ sizeof（ NODE))； p->tag＝ 0
P->content.val＝ ch;
P->next＝ create() ; break；
case?,?,p＝ create() ； breate ；
Case?)? case?\0?,p＝ NULL；
｝ i＋＋ ；
return(p) ｝
武汉理工大学华夏学院 -信息工程系设有两个广义表 S和 T,si是广义表 S中的第 I个元素,ti
是广义表 T中的第 I个元素，两个广义表相等的条件是：
若 si是原子，则 ti是和 si相同的原子；若 si是子表，则
ti 是和 si 相同的子表。判断两个广义表是否相等的算法就是对其对应元素进行比较。
2,判两个广义表是否相等
3,复制广义表
4,求广义表的长度这些都是广义表的一些基本运算，一般采用递归方法实现，具体算法可参阅参考书籍。
