习题二和上机答案(3)

LOC(3,3)=LOC(0,0 )+3*15+3=644+45+3=692

2.14 设稀疏矩阵采用十字链表结构表示。试写出实现两个稀疏矩阵相加的算法。 解：依题意，C=A+B，则 C 中的非零元素 cij只可能有 3 种情况：或者是 aij+bij，或者是 aij(bij=0)或者是 bij(aij=0)。因此，当 B 加到 A 上时，对 A 矩阵的十字链表来说，或者是改变结点的 val 域值(a+b≠0)，或者不变(b=0)，或者插入一个新结点(a=0)，还可能是删除一个结点(aij+bij=0)。整个运算可从矩阵的第一行起逐行进行。对每一行都从行表头出发分别找到 A 和 B 在该行中的第一个非零元素结点后开始比较，然后按 4 种不同情况分别处理（假设 pa 和 pb 分别指向 A 和 B 的十字链表中行值相同的两个结点）：

若 pa->col=pb->col 且 pa->val+pb->val≠0，则只要将 aij+bij的值送到 pa 所指结点的值域中即可。

（2）若 pa->col=pb->col 且 pa->val+pb->val=0，则需要在 A 矩阵的十字链表中删除pa 所指结点，此时需改变同一行中前一结点的 right 域值，以及同一列中前一结点的 down域值。

（3）若 pa->colcol 且 pa->col≠0（即不是表头结点），则只需要将 pa 指针往右推进一步，并重新加以比较。

（4）若 pa->col>pb->col 或 pa->col=0，则需要在 A 矩阵的十字链表中插入一个值为bij 的结点。

实现本题功能的程序如下：

#include #define MAX 100

struct matnode *createmat(struct matnode *h[]) /*h 是建立的十字链表各行首指针的数组*/ { int m，n，t，s，i，r，c，v;

struct matnode *p，*q;

printf(\行数 m，列数 n，非零元个数 t:\ scanf(\，%d，%d\，&m，&n，&t);

p=(struct matnode *)malloc(sizeof(struct matnode)); h[0]=p; p->row=m; p->col=n;

s=m>n ? m:n; /*s 为 m、n 中的较大者*/ for (i=1;i<=s;i++) {

p=(struct matnode *)malloc(sizeof(struct matnode)); h[i]=p;

h[i-1]->tag.next=p; p->row=p->col=0; p->down=p->right=p; }

h[s]->tag.next=h[0]; for (i=1;i<=t;i++) {

printf(\第%d 个元素(行号 r，列号 c，值 v):\，i); scanf(\，%d，%d\，&r，&c，&v);

p=(struct matnode *)malloc(sizeof(struct matnode)); p->row=r; p->col=c; p->tag.val=v; q=h[r];

while (q->right!=h[r] && q->right->colright; p->right=q->right; q->right=p; q=h[c];

while(q->down!=h[c] && q->down->rowdown; p->down=q->down; q->down=p; }

return(h[0]);

}

void prmat(struct matnode *hm) {

struct matnode *p，*q;

printf(\按行表输出矩阵元素:\\n\

printf(\，hm->row，hm->col); p=hm->tag.next; while (p!=hm) {

q=p->right; while (p!=q) {

printf(\，%d，%d\\n\，q->row，q->col，q->tag.val); q=q->right; }

p=p->tag.next; } }

struct matnode *colpred(i，j，h)

/*根据 i(行号)和 j(列号)找出矩阵第 i 行第 j 列的非零元素在十字链表中的前

驱结点*/

int i，j; struct matnode *h[]; {

struct matnode *d; d=h[j];

while (d->down->col!=0 && d->down->row

d=d->down; return(d);

}

struct matnode *addmat(ha，hb，h) struct matnode *ha，*hb，*h[]; {

struct matnode *p，*q，*ca，*cb，*pa，*pb，*qa; if (ha->row!=hb->row || ha->col!=hb->col) {

printf(\两个矩阵不是同类型的，不能相加\\n\ exit(0); } else

{

ca=ha->tag.next; cb=hb->tag.next; do {

pa=ca->right; pb=cb->right; qa=ca;

while (pb->col!=0)

if (pa->colcol && pa->col!=0) {

qa=pa; pa=pa->right; }

else if (pa->col>pb->col || pa->col==0) {

p=(struct matnode *)malloc(sizeof(struct matnode)); *p=*pb; p->right=pa; qa->right=p; qa=p; q=colpred(p->row，

p->col，h);

p->down=q->down; q->down=p; pb=pb->right; }

else {

pa->tag.val+=pb->tag.val; if (pa->tag.val==0)

{

qa->right=pa->right; q=colpred(pa->row，

pa->col，h);

q->down=pa->down; free(pa); }

else qa=pa; pa=pa->right; pb=pb->right; }

ca=ca->tag.next; cb=cb->tag.next;

} while (ca->row==0);

}

return(h[0]); }

main() {

struct matnode *hm，*hm1，*hm2; struct matnode *h[MAX]，*h1[MAX]; printf(\第一个矩阵:\\n\ hm1=createmat(h);

printf(\第二个矩阵:\\n\ hm2=createmat(h1);

hm=addmat(hm1，hm2，h); prmat(hm); }

第二章上机内容

1.设计一个程序，生成两个按值非递减有序排列的线性表LA和LB，再将LA和LB归并为一个新的线性表LC，且LC中的数据仍按值非递减有序排列，输出线性表LA，LB，LC。 解：

#include “stdio.h” #include “alloc.h” typedef struct node {

char data； struct node *next； } listnode；

typedef struct node *link； void print(link head) {

struct node *p； printf（“\\n”）； printf（“\\n”）； p= head->next； while(p)

{printf（“%c”, p->data)； p = p->next；} }

link creat() /*头插法建立单链表*/ {

link head ,s； char ch；

head = malloc(sizeof(listnode))； head->next =NULL； while(( ch= getchar())!=’\\n’) {

s= malloc(sizeof(listnode))； s->data= ch； s->next = head->next； head->next = s；