《数据结构-C语言描述》课件第5章.ppt

图5.24广义表A、B、C、D的存储结构图5.25广义表的另一种结点结构Tag=1hptpTag=1atomtp表结点原子结点图5.26广义表的第二种存储结构这种存储结构的形式说明如下：typedefenum{ATOM,LIST}ElemTag;/*ATOM＝0，表示原子；LIST＝1，表示子表*/typedefstructGLNode{ElemTagtag;union{AtomTypeatom;structGLNode*hp;}atom-hp;/*atom-hp是原子结点的值域atom和表结点的表头指针域hp的联合体域*/structGLNode*tp;}*GList;下面以广义表的头尾链表存储结构为例，介绍广义表的几个基本操作。(1)求广义表的表头和表尾。GListHead(GListL){if(L==NULL)return(NULL);/*空表无表头*/if(L-tag==ATOM)exit(0); /*原子不是表*/elsereturn(L-atom-htp.htp.hp);}GListTail(GListL){if(L==NULL)return(NULL);/*空表无表尾*/if(L-tag==ATOM)exit(0);/*原子不是表*/elsereturn(L-atom-htp.htp.tp);}(2)求广义表的长度和深度。intLength(GListL){intk=0;GLNode*s;if(L==NULL)return(0); /*空表长度为0*/if(L-tag==ATOM)exit(0); /*原子不是表*/s=L;while(s!=NULL) /*统计最上层表的长度*/{k++;s=s-atom-htp.htp.tp;}return(k);}intDepth(GListL){intd,max=0;GLNode*s;if(L==NULL)return(1);/*空表深度为1*/if(L-tag==ATOM)return(0);/*原子深度为0*/s=L;while(s!=NULL)/*求每个子表的深度的最大值*/{d=Depth(s-atom-htp.htp.hp);if(dmax)max=d;s=s-atom-htp.htp.tp;}return(max+1);/*表的深度等于最深子表的深度加1*/j=1;for(k=1;k=A.n;k++)for(i=1;i=A.len;i++)if(A.data［i］.col==k){B-data［j］.row=A.data［i］.colB-data［j］.col=A.data［i］.row;B-data［j］.e=A.data［i］.e;j++;}}}【算法5.1基于稀疏矩阵的三元组表示矩阵的转置算法】算法的时间耗费主要是在双重循环中，其时间复杂度为O（A.n×A.len）,最坏情况下，当A.len=A.m×A.n时，时间复杂度为O（A.m×A.n2）。采用正常方式实现矩阵转置的算法时间复杂度为O（A.m×A.n）。方法二：