数据结构源代码(C语言描述)(5)

p->i=0; p->j=0; p->rptr=p; p->cptr=p; cp[i]=p;

cp[i-1]->k.next=p; }

cp[s]->k.next=hm; for( x=1;x<=t;x++)

{ printf(\请输入一个三元组(i,j,v)\\n\

scanf(\ /*输入一个非零元的三元组*/

p=(struct linknode*)malloc(sizeof(struct linknode)); /*生成一个三元组的结点*/ p->i=i; p->j=j; p->k.v=k;

/*以下是将p插入到第i行链表中 */ q=cp[i];

while ((q->rptr!=cp[i]) &&( q->rptr->jrptr;

p->rptr=q->rptr; q->rptr=p;

/*以下是将P插入到第j列链表中*/ q=cp[j];

while((q->cptr!=cp[j]) &&( q->cptr->icptr;

p->cptr=q->cptr; q->cptr=p; }

return hm; }

void main()

{ struct linknode *p,*q; struct linknode *hm;

hm=creatlindmat( ); /*生成十字链表*/ p=hm->k.next;

while(p->k.next!=hm) /*输出十字链表*/ { q=p->rptr;

while(q->rptr!=p)

{ printf(\ q=q->rptr; } if(p!=q)

printf(\ printf(\ p=p->k.next; }

q=p->rptr;

while(q->rptr!=p)

{ printf(\ q=q->rptr; } if(p!=q)

printf(\printf(\}

P88 稀疏矩阵十字链表相加算法如下：

/*假设ha为A稀疏矩阵十字链表的头指针，hb为B稀疏矩阵十字链表的头指针*/

#include #define maxsize 100 struct linknode { int i,j;

struct linknode *cptr,*rptr; union vnext { int v;

struct linknode *next;} k; };

struct linknode creatlindmat( ) /*建立十字链表*/ { int x, m, n, t, s, i, j, k;

struct linknode *p , *q, *cp[maxsize],*hm;

printf(\请输入稀疏矩阵的行、列数及非零元个数\\n\scanf(\if (m>n) s=m; else s=n;

hm=(struct linknode*)malloc(sizeof(struct linknode)) ; hm->i=m; hm->j=n; cp[0]=hm;

for (i=1; i<=s;i++)

{ p=(struct linknode*)malloc(sizeof(struct linknode)) ; p->i=0; p->j=0; p->rptr=p; p->cptr=p; cp[i]=p;

cp[i-1]->k.next=p; }

cp[s]->k.next=hm; for( x=1;x<=t;x++)

{ printf(\请输入一个三元组(i,j,v)\\n\scanf(\

p=(struct linknode*)malloc(sizeof(struct linknode)); p->i=i; p->j=j; p->k.v=k;

/*以下是将p插入到第i行链表中 */

q=cp[i];

while ((q->rptr!=cp[i]) &&( q->rptr->jrptr;

p->rptr=q->rptr; q->rptr=p;

/*以下是将P插入到第j列链表中*/ q=cp[j];

while((q->cptr!=cp[j]) &&( q->cptr->icptr;

p->cptr=q->cptr; q->cptr=p; }

return hm; }

/* ha和hb表示的两个稀疏矩阵相加，相加的结果放入ha中*/ struct linknode *matadd(struct linknode *ha, struct linknode *hb) { struct linknode *pa, *pb, *qa, *ca,*cb,*p,*q; struct linknode *hl[maxsize]; int i , j, n;

if((ha->i!=hb->i)||(ha->j!=hb->j)) printf(\矩阵不匹配,不能相加\\n\else

{ p=ha->k.next; n=ha->j; for (i=1;i<=n; i++) { hl[i]=p; p=p->k.next; }

ca=ha->k.next; cb=hb->k.next; while(ca->i==0)

{pa=ca->rptr; pb=cb->rptr; qa=ca;

while(pb->j!=0)

{ if((pa->jj)&&(pa->j!=0)) { qa=pa; pa=pa->rptr;}

else if ((pa->j>pb->j)||(pa->j==0)) /*插入一个结点*/ { p=(struct linknode*)malloc(sizeof(struct linknode)); p->i=pb->i; p->j=pb->j; p->k.v=pb->k.v;

qa->rptr=p; p->rptr=pa; qa=p; pb=pb->rptr; j=p->j; q=hl[j]->cptr;

while((q->ii)&&(q->i!=0)) { hl[j]=q; q=hl[j]->cptr;} hl[j]->cptr=p; p->cptr=q;

hl[j]=p; } else

{pa->k.v=pa->k.v+pb->k.v;

if(pa->k.v==0) /*删除一个结点*/ { qa->rptr=pa->rptr; j=pa->j; q=hl[j]->cptr; while (q->ii)

{hl[j]=q; q=hl[j]->cptr;} hl[j]->cptr=q->cptr;

pa=pa->rptr; pb=pb->rptr; free(q); } else

{ qa=pa; pa=pa->rptr; pb=pb->rptr; } } }

ca=ca->k.next; cb=cb->k.next; } }

return ha; }

void print(struct linknode *ha) /*输出十字链表*/ { struct linknode *p,*q; p=ha->k.next; while(p->k.next!=ha) { q=p->rptr;

while(q->rptr!=p)

{ printf(\ q=q->rptr; }

if(p!=q)

printf(\ printf(\ p=p->k.next; }

q=p->rptr;

while(q->rptr!=p)

{ printf(\ q=q->rptr; }

if(p!=q)

printf(\ printf(\}

void main() {

struct linknode *ha=NULL,*hb=NULL,*hc=NULL; ha=creatlindmat( ); /*生成一个十字链表ha*/

hb=creatlindmat( ); /*生成另一个十字链表hb*/ printf(\ /*输出十字链表ha*/ print(ha);printf(\

printf(\ /*输出十字链表hb*/ print(hb);printf(\

hc=matadd(ha,hb); /*十字链表相加*/ printf(\/*输出相加后的结果*/ print(hc);printf(\}

P94 数据类型描述如下： #define elemtype char struct node1 { int atom;

struct node1 *link; union {

struct node1 *slink; elemtype data; } ds; }

P95 数据类型描述如下： struct node2

{ elemtype data;

struct node2 *link1,*link2; }

P96 求广义表的深度depth(LS) int depth(struct node1 *LS) {

int max=0,dep; while(LS!=NULL)

{ if(LS->atom==0) //有子表 { dep=depth(LS->ds.slink); if(dep>max) max=dep;