数据结构以及应用算法教程参考答案（8）第5章 数组与广义表

关注公众号凡花花的小窝，收获更多的考研计算机专业编程相关的资料 5.26 解： typedef int ElemType; typedef struct OLNode{ int row; int col; ElemType e; struct OLNode *right,*down; }OLNode,*OLink;

class CCrossListMat { public: OLink *RHead,*CHead; // 行与列指针向量的头指针 int m_nCol; // 矩阵列数 int m_nRow; // 矩阵行数 int m_nNum; // 非零元个数 public: CCrossListMat(){} CCrossListMat(int r,int c,int n); virtual ~CCrossListMat(){} void ShowMat(int i,int j); };

CCrossListMat::CCrossListMat(int r, int c, int n) { m_nRow=r; m_nCol=c; m_nNum=n; int i;

RHead=new OLink[m_nRow]; if(!RHead) exit(-2); CHead=new OLink[m_nCol]; if(!CHead) exit(-2); for(i=0;i<m_nRow;i++) RHead[i]=NULL; for(i=0;i<m_nCol;i++) CHead[i]=NULL; OLink p,q,qf; for(i=0;i<m_nNum;i++){ p=new OLNode; if(!p) exit(-2); cout<<"请输入非零元的行标、列标和值："; cin>>p->row>>p->col>>p->e; q=RHead[p->row]; if(!q){ RHead[p->row]=p; p->right=NULL; } else{ qf=q; while(q && q->col<p->col){ qf=q; q=q->right; } p->right=qf->right; qf->right=p; } q=CHead[p->col]; if(!q){ CHead[p->col]=p; p->down=NULL; } else{ qf=q; while(q && q->row<p->row){ qf=q; q=q->down; } p->down=qf->down; qf->down=p; } }

}

void CCrossListMat::ShowMat(int i,int j) { ElemType x=0; OLink p; p=RHead[i]; while(p && p->col!=j) p=p->right; if§ x=p->e; cout<<x<<endl; }

5.27 解： #include<iostream.h> #include<stdlib.h>

typedef int ElemType; typedef struct OLNode{ int row; int col; ElemType e; struct OLNode *right,*down; }OLNode,*OLink;

class CCrossListMat { public: OLink *RHead,*CHead; // 行与列指针向量的头指针 int m_nCol; // 矩阵列数 int m_nRow; // 矩阵行数 int m_nNum; // 非零元个数 public: CCrossListMat(){} virtual ~CCrossListMat(){} CCrossListMat(int r,int c,int n); void Add(CCrossListMat B); void ShowMat(); };

CCrossListMat::CCrossListMat(int r, int c, int n) { m_nRow=r; m_nCol=c; m_nNum=n; int i;

RHead=new OLink[m_nRow]; if(!RHead) exit(-2); CHead=new OLink[m_nCol]; if(!CHead) exit(-2); for(i=0;i<m_nRow;i++) RHead[i]=NULL; for(i=0;i<m_nCol;i++) CHead[i]=NULL; OLink p,q,qf; for(i=0;i<m_nNum;i++){ p=new OLNode; if(!p) exit(-2); cout<<"请输入非零元的行标、列标和值："; cin>>p->row>>p->col>>p->e; q=RHead[p->row]; if(!q){ RHead[p->row]=p; p->right=NULL; } else{ qf=q; while(q && q->col<p->col){ qf=q; q=q->right; } p->right=qf->right; qf->right=p; } q=CHead[p->col]; if(!q){ CHead[p->col]=p; p->down=NULL; } else{ qf=q; while(q && q->row<p->row){ qf=q; q=q->down; } p->down=qf->down; qf->down=p; } }

}

void CCrossListMat::Add(CCrossListMat B) { int i,k=0; OLink pa,pb; OLink pre,p; // 按行插入 OLink qpre,q; // 按列插入

for(i=0;i<m_nRow;i++){ pa=RHead[i]; pb=B.RHead[i]; pre=NULL; while(pb){ while(pa&&pa->col<pb->col){ pre=pa; pa=pa->right; } if(pa&&pa->col==pb->col){ pa->e=pa->e+pb->e; pb=pb->right; pre=pa; pa=pa->right; } else{ // 在A中插入一个新结点 p=new OLNode; p->row=pb->row; p->col=pb->col; p->e=pb->e; pb=pb->right; if(!pre){ p->right=pa; RHead[i]=p; } else{ p->right=pre; pre->right=p; } // 处理列指针 qpre=NULL; q=CHead[p->col]; while(q&&q->row<i){ qpre=q; q=q->down; } if(!qpre){ p->down=q; CHead[p->col]=p; } else{ p->down=pre; pre->down; } k++; } } // end while(pb) } // end for m_nNum=m_nNum+k;

}

void CCrossListMat::ShowMat() { int i,j; OLink p; for(i=0;i<m_nRow;i++){ p=RHead[i]; for(j=0;j<m_nCol;j++){ if(p && p->rowi && p->colj){ cout<e<<" “; p=p->right; } else cout<<0<<” "; } cout<<endl; } }

int main() { CCrossListMat A(3,3,4),B(3,3,2); A.Add(B); A.ShowMat(); return 0; } 以下是关于广义表算法涉及的描述及方法 #include “DSConst.h” // 常量定义头文件 #include “StrStat.h” // 字符串定义头文件

// 广义表数据结构声明 typedef char AtomType; typedef enum{ATOM,LIST} ElemTag; typedef struct GLNode{ ElemTag tag; union{ AtomType atom; struct GLNode *hp; }; struct GLNode *tp; }*GList;

// 将非空串Str分割成两部分，HStr为第一个，TStr为之后的子串 int StrDistrict(CString& Str,CString& HStr,CString& TStr) { int n,i,k; CString s1; CString s2(","), s3("("), s4(")"); // 定义常量串 n=Str.StrLength(); i=1; k=0; while(i<=n && s1.StrCompare(s2) || k!=0){ s1=Str.SubString(i,1); if(!s1.StrCompare(s3)) k++; else if(!s1.StrCompare(s4)) k–; i++; } if(i<=n){ HStr=Str.SubString(1,i-2); TStr=Str.SubString(i,n-i+1); } else{ HStr=Str; TStr.StrClear(); } return OK; }

// 用串s建立广义表L int CreateGList(GList& L,CString& s) { CString Sub,HSub,TSub; // 子串，表头串，表尾串 if(s.StrEmpty()) L=NULL; else{ // 非空串，建立广义表 L=new GLNode; // 开辟一个结点 if(!L) exit(OVERFLOW);

if(s.StrLength()>1){ // 如果串长大于1，说明是表结点 L->tag=LIST; Sub=s.SubString(2,s.StrLength()-2); // 取括号内子串 if(!Sub.StrEmpty()){ // 建立子表 StrDistrict(Sub,HSub,TSub); if(!HSub.StrEmpty()) // 表头不空 CreateGList(L->hp,HSub); else L->hp=NULL; if(!TSub.StrEmpty()) // 表尾不空 CreateGList(L->tp,TSub); else L->tp=NULL; } else{ // 空表 L->hp=NULL; L->tp=NULL; } } else{ // 建立原子结点 L->tag=ATOM; L->atom=s.GetStr()[0]; L->tp=NULL; } } return OK;

}

// 显示广义表串 void ShowGList(GList &L) { if(L){ if(L->tag==LIST){ cout<<"("; if(L->hp) ShowGList(L->hp); if(L->tp){ cout<<","; ShowGList(L->tp); } cout<<")"; } else cout<atom; } }

5.30 解： // 求广义表深度的递归算法 int GListDepth(GList& L) { int Depth=0; int HDepth,TDepth; // 表头深度，表尾深度 if(!L) return Depth; // 广义表不存在 if(L->tagATOM) return Depth; // 原子结点深度为0 else{ Depth++; // 表结点深度为1 HDepth=Depth+GListDepth(L->hp); TDepth=Depth+GListDepth(L->tp); return HDepth>TDepth?HDepth:TDepth; } } 5.31 解： // 由广义表L复制广义表T int CopyGList(GList& T,GList& L) { if(!L) T=NULL; else{ T=new GLNode; if(!T) exit(OVERFLOW); T->tag=L->tag; if(L->tagATOM) T->atom=L->atom; else{ CopyGList(T->hp,L->hp); CopyGList(T->tp,L->tp); } } return OK; } 5.32 解： // 判两广义表是否相等，相等返回OK，否则返回FALSE Status GListCompare(GList& L1,GList& L2) { if(!L1 && !L2) return OK; // L1和L2均为空表 if((!L1 && L2) || (L1 && !L2)) return FALSE; else{ // L1和L2均非空表 if(L1->tagL2->tag){ // 表属性相同 if(L1->tagATOM){ // 均为原子结点 if(L1->atom==L2->atom) return OK; else return FALSE; } else{ // 均为表结点 if(GListCompare(L1->hp,L2->hp) && GListCompare(L1->tp,L2->tp)) return OK; // 表头、表尾均相同 else return FALSE; } } else return FALSE; // 表属性不同 } } 5.33 解：