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

关注公众号凡花花的小窝，收获更多的考研计算机专业编程相关的资料 第5章 数组与广义表 5.1 解： (1) 6×8×6=288 Byte (2) LOC(5,7)=1000+(5×8+7)×6=1282 (3) LOC(1,4)=1000+(1×8+4)×6=1072 (4) LOC(4,7)=1000+(7×6+4)×6=1276 5.2 解： (1) LOC(0,0,0,0)=100 (2) LOC(1,1,1,1)=100+(1×3×5×8 + 1×5×8 + 1×8 + 1)×4=776 (3) LOC(3,1,2,5)=100+(3×3×5×8 + 1×5×8 + 2×8 + 5)×4=1784 (4) LOC(8,2,4,7)=100+(8×3×5×8 + 2×5×8 + 4×8 + 7)×4=4416 5.3 解： (0,0,0,0) (1,0,0,0) (0,1,0,0) (1,1,0,0) (0,0,1,0) (1,0,1,0) (0,1,1,0) (1,1,1,0) (0,0,2,0) (1,0,2,0) (0,1,2,0) (1,1,2,0) (0,0,0,1) (1,0,0,1) (0,1,0,1) (1,1,0,1) (0,0,1,1) (1,0,1,1) (0,1,1,1) (1,1,1,1) (0,0,2,1) (1,0,2,1) (0,1,2,1) (1,1,2,1) (0,0,0,2) (1,0,0,2) (0,1,0,2) (1,1,0,2) (0,0,1,2) (1,0,1,2) (0,1,1,2) (1,1,1,2) (0,0,2,2) (1,0,2,2) (0,1,2,2) (1,1,2,2) 5.4 解： 其中，a=Max(i,j)，b=Min(i,j) 5.5 解： (，，)

5.6 解：u=i-j+1 v=j-1 5.7 解：(1) k=2(i-1)+j-1 () (2) i=(k+1) DIV 3 + 1 () j=k+1-2(k DIV 3) 5.8 解：i为奇数时，k=i+j-2 j为偶数时，k=i+j-1 k=2(i DIV 2)+j-1 5.9 解：设稀疏矩阵为n行n列，其中的非零元为m个，m远小于。从时间上来说，采用二维数组存储稀疏矩阵需要-1次加法运算，而用三元组只需m-1次加法运算。从空间上来说，用二维数组需要个基本存储单元，而三元组需要m个基本存储单元外加2m个整型存储单元。由于远远大于m，故实际存储空间也较大。 5.10 解： (1) GetHead【(p,h,w)】= p (2) GetTail【(b,k,p,h)】= (k,p,h) (3) GetHead【((a,b),(c,d))】= (a,b) (4) GetTail【((a,b),(c,d))】= ((c,d)) (5) GetHead【GetTail【((a,b),(c,d))】】= GetHead【((c,d))】= (c,d) (6) GetTail【GetHead【((a,b),(c,d))】】= GetTail【(a,b)】= (b) (7) GetHead【GetTail【GetHead【((a,b),(c,d))】】】= GetHead【(b)】= b (8) GetTail【GetHead【GetTail【((a,b),(c,d))】】】= GetTail【(c,d)】= (d) 5.11 解： (1) GetHead【GetTail【GetTail【L1】】】 (2) GetHead【GetHead【GetTail【L2】】】 (3) GetHead【GetHead【GetTail【GetTail【GetHead【L3】】】】】 (4) GetHead【GetHead【GetHead【GetTail【GetTail【L4】】】】】 (5) GetHead【GetHead【GetTail【GetTail【L5】】】】 (6) GetHead【GetTail【GetHead【L6】】】 (7) GetHead【GetHead【GetTail【GetHead【GetTail【L7】】】】】 5.12 解：

5.13 解： (1) List=((x,(y)),(((())),(()),(z))) (2) List=(((a,b,()),()),(a,(b)),()) 5.14 解： (n>=1) ElemType s(int i) { if(i>1) return s(i-1)+a1+(i-1)*d; else return a1; } 5.16 解： 5.17 解： int Max(SqList &L,int k) { if(k<L.length-1) if(L.elem[k]<Max(L,k+1)) return Max(L,k+1); else return L.elem[k]; else return L.elem[k]; } int Min(SqList &L,int k) { if(k<L.length-1) if(L.elem[k]>Min(L,k+1)) return Min(L,k+1); else return L.elem[k]; else return L.elem[k]; } int Sum(SqList &L,int k) { if(k0) return L.elem[0]; else return L.elem[k]+Sum(a,k-1); } int Product(SqList &L,int k) { if(k0) return L.elem[0]; else return L.elem[k]Sum(a,k-1); } double Avg(SqList &L,int k) { if(k==0) return L.elem[0]; else return (Avg(a,k-1)k+L.elem[k])/(k+1); } 5.18 解：算法的基本思想是将数组分成k组，将第一组与第二组进行两两交换，再将第一组与第三组进行两两交换，…，总共需进行n-k次交换。注意最后一组可能出现不足k个元素的情况，此时最后一组为剩余元素加第一组的前几个元素共k个构成最后一组。 void RRMove(ElemType A[],int k,int n) { ElemType e; int i=0,j,p; while(i<n-k){ p=i/k+1; for(j=0;j<k;j++){ e=A[j]; A[j]=A[(pk+j)%n]; A[(pk+j)%n]=e; i++; } } } 5.19 解： #include <iostream.h> #define RS 4 #define CS 4

typedef int ElemType; typedef struct{ ElemType e; int i,j; int Flags; }NodeType;

void Initialize(NodeType a[RS][CS],ElemType A[RS][CS]); void SaddlePoint(NodeType a[RS][CS]); ElemType RowMin(NodeType a[RS][CS],int k); ElemType ColMax(NodeType a[RS][CS],int k); void Show(NodeType a[RS][CS]);

int main() { ElemType A[RS][CS]={ {2,1,3,4}, {1,3,1,2}, {2,7,1,3}, {3,2,4,1} }; NodeType a[RS][CS]; Initialize(a,A); SaddlePoint(a); Show(a); return 0; }

void Initialize(NodeType a[RS][CS],ElemType A[RS][CS]) { int i,j; for(i=0;i<RS;i++){ for(j=0;j<CS;j++){ a[i][j].e=A[i][j]; a[i][j].i=i; a[i][j].j=j; a[i][j].Flags=0; } } }

void SaddlePoint(NodeType a[RS][CS]) { int i,j; ElemType x,y; for(i=0;i<RS;i++){ x=RowMin(a,i); for(j=0;j<CS;j++){ y=ColMax(a,j); if(a[i][j].ex&&a[i][j].ey) a[i][j].Flags=1; } } }

ElemType RowMin(NodeType a[RS][CS],int k) { ElemType x; x=a[k][0].e; int i; for(i=1;i<CS;i++) if(x>a[k][i].e){ x=a[k][i].e; } return x; }

ElemType ColMax(NodeType a[RS][CS],int k) { ElemType x; x=a[0][k].e; int i; for(i=1;i<RS;i++) if(x<a[i][k].e){ x=a[i][k].e; } return x; }

void Show(NodeType a[RS][CS]) { for(int i=0;i<RS;i++) for(int j=0;j<CS;j++) if(a[i][j].Flags) cout<<i<<" “<<j<<” is a saddle point"<<endl; } 5.21 解： typedef int ElemType; class Triple{ public: int row; int col; ElemType e;

Triple(){} virtual ~Triple(){} BOOL operator<(Triple b); BOOL operator==(Triple b);

};

BOOL Triple::operator<(Triple b) { if(row<b.row) return TRUE; if(rowb.row&&col<b.col) return TRUE; return FALSE; } BOOL Triple::operator(Triple b) { if(rowb.row && colb.col) return TRUE; else return FALSE; }

class CSparseMat { public: CSparseMat(){} virtual ~CSparseMat(){} CSparseMat(int r,int c,int n); CSparseMat operator+(CSparseMat B); void ShowSparse(CDC* pDC);

Triple *m_pt; // 指向非零元的指针 int m_nCol; // 矩阵列数 int m_nRow; // 矩阵行数 int m_nTrs; // 非零元个数

};

CSparseMat::CSparseMat(int r, int c, int n) { m_nRow=r; m_nCol=c; m_nTrs=n; m_pt=new Triple[m_nTrs];

// 输入矩阵的所有三元组 int i; for(i=0;i<m_nTrs;i++){ CInputDlg dlg1; if(dlg1.DoModal()==IDOK){ m_pt[i].row=dlg1.m_nRow; m_pt[i].col=dlg1.m_nCol; m_pt[i].e=dlg1.m_nElem; } }

}

void CSparseMat::ShowSparse(CDC pDC) { char str[10]; int k=0; for(int i=0;i<m_nRow;i++){ for(int j=0;j<m_nCol;j++){ if(m_pt[k].rowi && m_pt[k].colj){ itoa(m_pt[k].e,str,10); k++; } else itoa(0,str,10); pDC->TextOut(0+j20,0+i*20,str,strlen(str)); } } }

// 矩阵相加的运算符重载函数 CSparseMat CSparseMat::operator+(CSparseMat B) { CSparseMat temp(m_nRow,m_nCol,0); if(m_nRow!=B.m_nRow || m_nCol!=B.m_nCol) return temp;

temp.m_pt=new Triple[m_nTrs+B.m_nTrs]; if(!temp.m_pt) return temp; temp.m_nTrs=m_nTrs+B.m_nTrs; int i=0; int j=0; int k=0; while(i<m_nTrs && j<B.m_nTrs){ if(m_pt[i]<B.m_pt[j]){ temp.m_pt[k].row=m_pt[i].row; temp.m_pt[k].col=m_pt[i].col; temp.m_pt[k].e=m_pt[i].e; i++; } else{ if(m_pt[i]==B.m_pt[j]){ temp.m_pt[k].row=m_pt[i].row; temp.m_pt[k].col=m_pt[i].col; temp.m_pt[k].e=m_pt[i].e+B.m_pt[j].e; i++; j++; } else{ temp.m_pt[k].row=B.m_pt[j].row; temp.m_pt[k].col=B.m_pt[j].col; temp.m_pt[k].e=B.m_pt[j].e; j++; } } k++; } while(i<m_nTrs){ temp.m_pt[k].row=m_pt[i].row; temp.m_pt[k].col=m_pt[i].col; temp.m_pt[k].e=m_pt[i].e; i++; k++; } while(j<B.m_nTrs){ temp.m_pt[k].row=B.m_pt[j].row; temp.m_pt[k].col=B.m_pt[j].col; temp.m_pt[k].e=B.m_pt[j].e; j++; k++; } temp.m_nTrs=k; return temp;

} 5.23 解： #include<iostream.h> #include<stdlib.h> #define Max 128

typedef int ElemType; typedef struct{ int col; ElemType e; }Twin;

class CSparseMat { public: CSparseMat(){} CSparseMat(int r,int c,int n); virtual ~CSparseMat(){} void ShowSparse(int i,int j);

Twin* m_pt; // 指向非零元的指针 int rpos[Max]; int m_nCol; // 矩阵列数 int m_nRow; // 矩阵行数 int m_nTws; // 非零元个数

};

CSparseMat::CSparseMat(int r, int c, int n) { m_nRow=r; m_nCol=c; m_nTws=n; m_pt=new Twin[m_nTws]; if(!m_pt) return;

// 输入矩阵的所有二元组 int i; for(i=0;i<m_nTws;i++){ cout<<"请输入非零元二元组的列标和值："; cin>>m_pt[i].col>>m_pt[i].e; } for(i=0;i<m_nRow;i++){ cout<<"请输入每行第一个非零元在二元组中的序号(没有输入-1)："; cin>>rpos[i]; // 该行没有非零元输入-1 }

}

void CSparseMat::ShowSparse(int i,int j) { if(i>m_nRow||j>m_nCol) return;

ElemType x=0; int s,d; if(i==m_nRow){ s=rpos[i]; d=m_nTws; } else{ s=rpos[i]; int m=1; d=rpos[i+m]; while(d<0){ if(i+m<m_nRow){ m++; d=rpos[i+m]; } else d=m_nTws; } } if(s>=0){ int k=s; while(k<d){ if(m_pt[k].col==j) x=m_pt[k].e; k++; } } cout<<x<<endl;

}

int main() { CSparseMat A(3,3,5); A.ShowSparse(2,1); return 0; }