第5章 数组和广义表要点：
1、掌握数组元素存储位置的换算；
2、了解特殊矩阵地存储方法和元素存储位置计算；
3、了解广义表的长度、深度、head、tail等概念和操作和存储结构。
教材习题解答：
5.1 288，1282，1126，1192（注：如果数组元素的下标从1开始则第3，4项的答案不同）
5.2 k = 2i+j-2
I = k/3 + 1
j = k – 2(k/3)
5.3
//p112 习题5.3 假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵
//相加的算法，另设三元组C存放结果矩阵。
#include <stdio.h>
#define MAXSIZE 100
typedef struct
{
int row,col;
int e;
}Triple;
typedef struct
{
Triple data[MAXSIZE+1];
int m,n,len;
}TSMatrix;
void Input(TSMatrix *pA)
{
int nrow,ncol,num,elem,i;
printf("请输入矩阵的行数、列数和非零元素个数：");
scanf("%d%d%d",&nrow,&ncol,&num);
pA->m = nrow;
pA->n = ncol;
pA->len = num;
for(i = 1; i <= num; i++)
{
printf("请输入第 %d 个元素的行号、列号和元素值：",i);
scanf("%d%d%d",&nrow,&ncol,&elem);
pA->data[i].row = nrow;
pA->data[i].col = ncol;
pA->data[i].e = elem;
}
}
void Print(TSMatrix *pA)
{
int i,j,t;
for(i = 1,t =1; i <= pA->m; i++)
{
for(j = 1; j <= pA->n; j++)
{
if(pA->data[t].row == i && pA->data[t].col ==j)
{
printf("%4d",pA->data[t].e);
t++;
}
else
printf("%4d",0);
}
printf("\n");
}
}
void Add(TSMatrix *pA,TSMatrix *pB,TSMatrix *pC)
{
int i,j,t;
if(pA->m != pB->m || pA->n != pB->n)
{
printf("两个矩阵的行数与列数不相等，不能相加！\n");
return;
}
pC->m = pA->m;
pC->n = pA->n;
i = 1;
j = 1;
t = 0;
while(i <= pA->len && j <= pB->len)
{
if(((pA->data[i].row - 1)*pA->n + pA->data[i].col -1) <
((pB->data[j].row - 1)*pB->n + pB->data[j].col -1) )
{
t++;
pC->data[t].row = pA->data[i].row;
pC->data[t].col = pA->data[i].col;
pC->data[t].e = pA->data[i].e;
i++;
}
else
if(((pA->data[i].row - 1)*pA->n + pA->data[i].col -1) >
((pB->data[j].row - 1)*pB->n + pB->data[j].col -1) )
{
t++;
pC->data[t].row = pB->data[j].row;
pC->data[t].col = pB->data[j].col;
pC->data[t].e = pB->data[j].e;
j++;
}
else
if(pA->data[i].e + pB->data[j].e != 0)
{
t++;
pC->data[t].row = pA->data[i].row;
pC->data[t].col = pA->data[i].col;
pC->data[t].e = pA->data[i].e + pB->data[j].e;
i++;
j++;
}
}
while(i <= pA->len)
{
t++;
pC->data[t].row = pA->data[i].row;
pC->data[t].col = pA->data[i].col;
pC->data[t].e = pA->data[i].e;
i++;
}
while(j <= pB->len)
{
t++;
pC->data[t].row = pB->data[j].row;
pC->data[t].col = pB->data[j].col;
pC->data[t].e = pB->data[j].e;
j++;
}
pC->len = t;
}
void main()
{
TSMatrix A,B,C;
Input(&A);
Print(&A);
Input(&B);
Print(&B);
Add(&A,&B,&C);
Print(&C);
}
5.5 //p112习题5.5 写一个在十字链表中删除非零元素a(i,j)的算法
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct OLNode
{
int row,col;
ElementType value;
struct OLNode *right,*down;
}OLNode,*OLink;
typedef struct
{
OLink *row_head,*col_head;
int m,n,len;
}CrossList;
void CreateCrossList(CrossList *M)
{
int m,n,t,i,j,e;
OLink p,q;
printf("请输入矩阵的行数、列数和非0元素个数：");
scanf("%d%d%d",&m,&n,&t);
if(m < 1 || n < 1 || t < 0)
return;
M->m = m; M->n = n; M->len = t;
M->row_head = (OLink *)malloc(sizeof(OLink) * (m + 1));
M->col_head = (OLink *)malloc(sizeof(OLink) * (n + 1));
for( i = 1; i <= m; i++)
M->row_head[i] = 0;
for( i = 1; i <= n; i++)
M->col_head[i] = 0;
for( m =1; m <= t; m++)
{
printf("请输入第 %d 个非0元素的行号、列号和元素值：",m);
scanf("%d%d%d",&i,&j,&e);
p = (OLink)malloc(sizeof(OLNode));
p->row = i; p->col = j; p->value = e;
if(M->row_head[i] == 0)
{
M->row_head[i] = p;
p->right = 0;
}
else
{
q = M->row_head[i];
while( q->right != 0 && q->right->col < j)
q = q->right;
p->right = q->right;
q->right = p;
}
if(M->col_head[j] == 0)
{
M->col_head[j] = p;
p->down = 0;
}
else
{
q = M->col_head[j];
while( q->down != 0 && q->down->row < i )
q = q->down;
p->down = q->down;
q->down = p;
}
}
}
int DeleElem(CrossList *M,int i,int j)
{
OLink p,q;
p = M->row_head[i];
if(p == 0)
return (0);
while(p != 0 && p->col != j)
{
q = p;
p = p->right;
}
if(p == 0)
return(0);
if(p == M->row_head[i])
M->row_head[i] = p->right;
else
q->right = p->right;
q = M->col_head[j];
if(q == p)
M->col_head[j] = p->down;
else
{
while(q->down != p)
q = q->down;
q->down = p->down;
}
free(p);
return(1);
}
void Print(CrossList *M)
{
int i,j;
OLink p;
for(i = 1; i <= M->m; i++)
{
p = M->row_head[i];
for(j = 1; j<= M->n; j++)
if(p != 0 && p->col == j)
{
printf("%4d",p->value);
p = p->right;
}
else
printf("%4d",0);
printf("\n");
}
}
void main()
{
int i,j;
CrossList M;
CreateCrossList(&M);
Print(&M);
printf("请输入要删除的元素的行号和列号");
scanf("%d%d",&i,&j);
if(DeleElem(&M,i,j))
printf("成功删除！\n");
else
printf("没有对应元素！\n");
Print(&M);
}
5.6
5.7 (a,b),((c,d)),(b),b,(d)
实习题：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void CreateArray(int *a,int m,int n)
{
time_t t;
int i;
time(&t);
srand((unsigned int)t);
for(i = 0; i<m*n; i++)
a[i] = rand() % 100;
}
int SearchSaddlePoint(int *a,int m,int n)
{
int i,j,k,pmin,pmax;
for(i=0; i<m;i++)
{
pmin = i*n;
for(j = 1; j<n; j++)
if(*(a+i*n+j) < *(a+pmin))
pmin = i*n + j;
pmax = pmin;
k = pmax % n; //得到第i行中最小元素所在的列号
for(j = k; j < m*n; j+=n)
if(*(a+j) > *(a+pmax))
pmax = j;
if(pmax == pmin)
{
printf("%d\t%d\n",pmax/n + 1,pmax%n + 1);
return 1;
}
}
return 0;
}
void PrintArray(int *a,int m,int n)
{
int i,j;
for(i = 0; i < m; i++)
{
for(j = 0; j < n; j++)
printf("%5d",*(a+i*n+j));
printf("\n");
}
}
void main()
{
int *a;
int m,n;
printf("请输入要创建的矩阵的行数和列数：");
scanf("%d%d",&m,&n);
a = (int *)malloc(sizeof(int)*m*n);
while(1)
{
CreateArray(a,m,n);
// PrintArray(a,m,n);
if(SearchSaddlePoint(a,m,n))
{
PrintArray(a,m,n);
break;
}
// printf("\n");
}
free(a);
}
补充练习：
1、对于一个二维数组A[m][n]，若按行序为主序存储，则任一元素A[i][j]相对于A[0][0]的地址是多少？
2、一个稀疏矩阵为，则对应的三元组表是什么？
3、设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有一个存储地址空间，则a85的地址是多少？
4、设有上三角矩阵（aij）n×n，将其上三角逐行存于数组B[m]中，使得B[m]= aij，且k=f1(i)+f2(j)+c。请写出函数f1，f2和常数c（f1和f2中不含常数项）。
5、求下列广义表操作的结果：
（1）Head((p,h,w));
（2）Tail((b,k,p,h));
（3）Tail(((a,b),(c,d)));
（4）Tail(Head(((a,b),(c,d))));
（5）Tail(Head(Tail(((a,b),(c,d)))));
6、假设稀疏矩阵A和B均以三元组顺序表作为存储结构，试写出矩阵相加的算法：
int AddMatrix(TSMatrix A,TSMatrix B,TSMatrix &C);
7、试编写一个以三元组形式输出用十字链表存储表示的稀疏矩阵中非零元素的下标及其元素值的算法：int Print(CrossList &M);
8、按照教材5.5节中图5.8所示结点结构，画出下列广义表的存储结构图，并求出它的深度。
（1）（（（）），a，（（b，c），（），d），（（（e））））
（2）（（（（a），b）），（（（），d），（e，f）））
9、设三角矩阵R=采用一维数组进行压缩存储，第一个元素为R11，存储位置为1，每个元素占一个存储位置，则R32的存储位置为几？
参考解答：
1、&A[0][0]+(i*n+j)*L //L为每一数据元素所占的字节数
2、((1,3,2),(2,1,3),(3,3,-1),(3,4,5))
3、&aij=&a00+(i*(i+1)/2+j)*L (i>=j) //&a00为第一个元素的地址，L为每一
&aij=&a00+(j*(j+1)/2+i)*L (j>=i) //元素所占存储空间则a85的地址为0+8*9/2+5=41
4、若行号与列号均从0开始，则元素aij前有i行，各行的非0元素个数从n到n-i+1，共有i*(n+n-i+1)/2个元素，aij所在的行中，其前面共有j个元素，但为0的元素有i个，不为0的元素个数则为j-i个，所以在上三角中aij前面共有i*(n+n-i+1)/2+ j-i个非0的元素，这些元素需要存储在一维数组B[]中，且在aij的前面，若一维数组的下标也从0开始，若用B[k]存储aij，则k= i*(n+n-i+1)/2+ j- i =(-i2-i+2in)/2+j
即： c=0
若下标均从1开始，则 c=-n
5、（1） p （2）（k，p，h） （3）（（c，d）） （4）（b） （5）（d）
6、参考上面教材习题解答。
7、Status Print(CrossList &M)
{ OLink *p;
p=M.rhead;
for(i=1;i<=M.mu;i++)
{ q=p[i];
while(q){ //将第i行链各结点输出
printf(“(%d,%d,%d),,q->i,q->j,q->e); //输出一个结点所对应的三元组
q=q->right;
}
}
}
8、深度均为4，画图略。
9、&Rij=&R11+(i*(i-1)/2+j-1)*L=1+4=5
1、掌握数组元素存储位置的换算；
2、了解特殊矩阵地存储方法和元素存储位置计算；
3、了解广义表的长度、深度、head、tail等概念和操作和存储结构。
教材习题解答：
5.1 288，1282，1126，1192（注：如果数组元素的下标从1开始则第3，4项的答案不同）
5.2 k = 2i+j-2
I = k/3 + 1
j = k – 2(k/3)
5.3
//p112 习题5.3 假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵
//相加的算法，另设三元组C存放结果矩阵。
#include <stdio.h>
#define MAXSIZE 100
typedef struct
{
int row,col;
int e;
}Triple;
typedef struct
{
Triple data[MAXSIZE+1];
int m,n,len;
}TSMatrix;
void Input(TSMatrix *pA)
{
int nrow,ncol,num,elem,i;
printf("请输入矩阵的行数、列数和非零元素个数：");
scanf("%d%d%d",&nrow,&ncol,&num);
pA->m = nrow;
pA->n = ncol;
pA->len = num;
for(i = 1; i <= num; i++)
{
printf("请输入第 %d 个元素的行号、列号和元素值：",i);
scanf("%d%d%d",&nrow,&ncol,&elem);
pA->data[i].row = nrow;
pA->data[i].col = ncol;
pA->data[i].e = elem;
}
}
void Print(TSMatrix *pA)
{
int i,j,t;
for(i = 1,t =1; i <= pA->m; i++)
{
for(j = 1; j <= pA->n; j++)
{
if(pA->data[t].row == i && pA->data[t].col ==j)
{
printf("%4d",pA->data[t].e);
t++;
}
else
printf("%4d",0);
}
printf("\n");
}
}
void Add(TSMatrix *pA,TSMatrix *pB,TSMatrix *pC)
{
int i,j,t;
if(pA->m != pB->m || pA->n != pB->n)
{
printf("两个矩阵的行数与列数不相等，不能相加！\n");
return;
}
pC->m = pA->m;
pC->n = pA->n;
i = 1;
j = 1;
t = 0;
while(i <= pA->len && j <= pB->len)
{
if(((pA->data[i].row - 1)*pA->n + pA->data[i].col -1) <
((pB->data[j].row - 1)*pB->n + pB->data[j].col -1) )
{
t++;
pC->data[t].row = pA->data[i].row;
pC->data[t].col = pA->data[i].col;
pC->data[t].e = pA->data[i].e;
i++;
}
else
if(((pA->data[i].row - 1)*pA->n + pA->data[i].col -1) >
((pB->data[j].row - 1)*pB->n + pB->data[j].col -1) )
{
t++;
pC->data[t].row = pB->data[j].row;
pC->data[t].col = pB->data[j].col;
pC->data[t].e = pB->data[j].e;
j++;
}
else
if(pA->data[i].e + pB->data[j].e != 0)
{
t++;
pC->data[t].row = pA->data[i].row;
pC->data[t].col = pA->data[i].col;
pC->data[t].e = pA->data[i].e + pB->data[j].e;
i++;
j++;
}
}
while(i <= pA->len)
{
t++;
pC->data[t].row = pA->data[i].row;
pC->data[t].col = pA->data[i].col;
pC->data[t].e = pA->data[i].e;
i++;
}
while(j <= pB->len)
{
t++;
pC->data[t].row = pB->data[j].row;
pC->data[t].col = pB->data[j].col;
pC->data[t].e = pB->data[j].e;
j++;
}
pC->len = t;
}
void main()
{
TSMatrix A,B,C;
Input(&A);
Print(&A);
Input(&B);
Print(&B);
Add(&A,&B,&C);
Print(&C);
}
5.5 //p112习题5.5 写一个在十字链表中删除非零元素a(i,j)的算法
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct OLNode
{
int row,col;
ElementType value;
struct OLNode *right,*down;
}OLNode,*OLink;
typedef struct
{
OLink *row_head,*col_head;
int m,n,len;
}CrossList;
void CreateCrossList(CrossList *M)
{
int m,n,t,i,j,e;
OLink p,q;
printf("请输入矩阵的行数、列数和非0元素个数：");
scanf("%d%d%d",&m,&n,&t);
if(m < 1 || n < 1 || t < 0)
return;
M->m = m; M->n = n; M->len = t;
M->row_head = (OLink *)malloc(sizeof(OLink) * (m + 1));
M->col_head = (OLink *)malloc(sizeof(OLink) * (n + 1));
for( i = 1; i <= m; i++)
M->row_head[i] = 0;
for( i = 1; i <= n; i++)
M->col_head[i] = 0;
for( m =1; m <= t; m++)
{
printf("请输入第 %d 个非0元素的行号、列号和元素值：",m);
scanf("%d%d%d",&i,&j,&e);
p = (OLink)malloc(sizeof(OLNode));
p->row = i; p->col = j; p->value = e;
if(M->row_head[i] == 0)
{
M->row_head[i] = p;
p->right = 0;
}
else
{
q = M->row_head[i];
while( q->right != 0 && q->right->col < j)
q = q->right;
p->right = q->right;
q->right = p;
}
if(M->col_head[j] == 0)
{
M->col_head[j] = p;
p->down = 0;
}
else
{
q = M->col_head[j];
while( q->down != 0 && q->down->row < i )
q = q->down;
p->down = q->down;
q->down = p;
}
}
}
int DeleElem(CrossList *M,int i,int j)
{
OLink p,q;
p = M->row_head[i];
if(p == 0)
return (0);
while(p != 0 && p->col != j)
{
q = p;
p = p->right;
}
if(p == 0)
return(0);
if(p == M->row_head[i])
M->row_head[i] = p->right;
else
q->right = p->right;
q = M->col_head[j];
if(q == p)
M->col_head[j] = p->down;
else
{
while(q->down != p)
q = q->down;
q->down = p->down;
}
free(p);
return(1);
}
void Print(CrossList *M)
{
int i,j;
OLink p;
for(i = 1; i <= M->m; i++)
{
p = M->row_head[i];
for(j = 1; j<= M->n; j++)
if(p != 0 && p->col == j)
{
printf("%4d",p->value);
p = p->right;
}
else
printf("%4d",0);
printf("\n");
}
}
void main()
{
int i,j;
CrossList M;
CreateCrossList(&M);
Print(&M);
printf("请输入要删除的元素的行号和列号");
scanf("%d%d",&i,&j);
if(DeleElem(&M,i,j))
printf("成功删除！\n");
else
printf("没有对应元素！\n");
Print(&M);
}
5.6
5.7 (a,b),((c,d)),(b),b,(d)
实习题：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void CreateArray(int *a,int m,int n)
{
time_t t;
int i;
time(&t);
srand((unsigned int)t);
for(i = 0; i<m*n; i++)
a[i] = rand() % 100;
}
int SearchSaddlePoint(int *a,int m,int n)
{
int i,j,k,pmin,pmax;
for(i=0; i<m;i++)
{
pmin = i*n;
for(j = 1; j<n; j++)
if(*(a+i*n+j) < *(a+pmin))
pmin = i*n + j;
pmax = pmin;
k = pmax % n; //得到第i行中最小元素所在的列号
for(j = k; j < m*n; j+=n)
if(*(a+j) > *(a+pmax))
pmax = j;
if(pmax == pmin)
{
printf("%d\t%d\n",pmax/n + 1,pmax%n + 1);
return 1;
}
}
return 0;
}
void PrintArray(int *a,int m,int n)
{
int i,j;
for(i = 0; i < m; i++)
{
for(j = 0; j < n; j++)
printf("%5d",*(a+i*n+j));
printf("\n");
}
}
void main()
{
int *a;
int m,n;
printf("请输入要创建的矩阵的行数和列数：");
scanf("%d%d",&m,&n);
a = (int *)malloc(sizeof(int)*m*n);
while(1)
{
CreateArray(a,m,n);
// PrintArray(a,m,n);
if(SearchSaddlePoint(a,m,n))
{
PrintArray(a,m,n);
break;
}
// printf("\n");
}
free(a);
}
补充练习：
1、对于一个二维数组A[m][n]，若按行序为主序存储，则任一元素A[i][j]相对于A[0][0]的地址是多少？
2、一个稀疏矩阵为，则对应的三元组表是什么？
3、设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有一个存储地址空间，则a85的地址是多少？
4、设有上三角矩阵（aij）n×n，将其上三角逐行存于数组B[m]中，使得B[m]= aij，且k=f1(i)+f2(j)+c。请写出函数f1，f2和常数c（f1和f2中不含常数项）。
5、求下列广义表操作的结果：
（1）Head((p,h,w));
（2）Tail((b,k,p,h));
（3）Tail(((a,b),(c,d)));
（4）Tail(Head(((a,b),(c,d))));
（5）Tail(Head(Tail(((a,b),(c,d)))));
6、假设稀疏矩阵A和B均以三元组顺序表作为存储结构，试写出矩阵相加的算法：
int AddMatrix(TSMatrix A,TSMatrix B,TSMatrix &C);
7、试编写一个以三元组形式输出用十字链表存储表示的稀疏矩阵中非零元素的下标及其元素值的算法：int Print(CrossList &M);
8、按照教材5.5节中图5.8所示结点结构，画出下列广义表的存储结构图，并求出它的深度。
（1）（（（）），a，（（b，c），（），d），（（（e））））
（2）（（（（a），b）），（（（），d），（e，f）））
9、设三角矩阵R=采用一维数组进行压缩存储，第一个元素为R11，存储位置为1，每个元素占一个存储位置，则R32的存储位置为几？
参考解答：
1、&A[0][0]+(i*n+j)*L //L为每一数据元素所占的字节数
2、((1,3,2),(2,1,3),(3,3,-1),(3,4,5))
3、&aij=&a00+(i*(i+1)/2+j)*L (i>=j) //&a00为第一个元素的地址，L为每一
&aij=&a00+(j*(j+1)/2+i)*L (j>=i) //元素所占存储空间则a85的地址为0+8*9/2+5=41
4、若行号与列号均从0开始，则元素aij前有i行，各行的非0元素个数从n到n-i+1，共有i*(n+n-i+1)/2个元素，aij所在的行中，其前面共有j个元素，但为0的元素有i个，不为0的元素个数则为j-i个，所以在上三角中aij前面共有i*(n+n-i+1)/2+ j-i个非0的元素，这些元素需要存储在一维数组B[]中，且在aij的前面，若一维数组的下标也从0开始，若用B[k]存储aij，则k= i*(n+n-i+1)/2+ j- i =(-i2-i+2in)/2+j
即： c=0
若下标均从1开始，则 c=-n
5、（1） p （2）（k，p，h） （3）（（c，d）） （4）（b） （5）（d）
6、参考上面教材习题解答。
7、Status Print(CrossList &M)
{ OLink *p;
p=M.rhead;
for(i=1;i<=M.mu;i++)
{ q=p[i];
while(q){ //将第i行链各结点输出
printf(“(%d,%d,%d),,q->i,q->j,q->e); //输出一个结点所对应的三元组
q=q->right;
}
}
}
8、深度均为4，画图略。
9、&Rij=&R11+(i*(i-1)/2+j-1)*L=1+4=5
