第5章数组和广义表 要点: 1、掌握数组元素存储位置的换算: 2、了解特殊矩阵地存储方法和元素存储位置计算 3、了解广义表的长度、深度、head、tail等概念和操作和存储结构 教材习题解答 5.1288,1282,1126,1192(注:如果数组元素的下标从1开始则第3,4项的答案不同) 5.2k=2i+j-2 I=k/3+1 j=k-2(k/3) //p112习题5.3假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵 /相加的算法,另设三元组C存放结果矩阵 #include <stdio. h #define maXsize 100 typedef struct int row, col typedef struct Triple data [MAXSIZE+1 int l I SMAtrix void Input(SMAtrix * pA) int nrow, ncol, num, elem, i printf("请输入矩阵的行数、列数和非零元素个数:"); scanf(%d%d%d", &nrow, &ncol, &num nrow pA->1 pA->len =num for(i =1: i < num; i++) printf("请输入第%d个元素的行号、列号和元素值:",i) scanf(%d%d%d",&nrow, &ncol, &elem) A->datai]. row = nrow pA->data[i]. col = ncol pA->data[i] e elem;
第 5 章 数组和广义表 要点： 1、掌握数组元素存储位置的换算； 2、了解特殊矩阵地存储方法和元素存储位置计算； 3、了解广义表的长度、深度、head、tail 等概念和操作和存储结构。 教材习题解答： 5.1 288，1282，1126，1192（注：如果数组元素的下标从 1 开始则第 3，4 项的答案不同） 5.2 k = 2i+j-2 I = k/3 + 1 j = k – 2(k/3) 5.3 //p112 习题 5.3 假设稀疏矩阵 A 和 B 均以三元组表作为存储结构。试写出矩阵 //相加的算法，另设三元组 C 存放结果矩阵。 #include <stdio.h> #define MAXSIZE 100 typedef struct { int row, col; int e; }Triple; typedef struct { Triple data[MAXSIZE+1]; int m, n, len; }TSMatrix; void Input(TSMatrix *pA) { int nrow, ncol, num, elem, i; printf("请输入矩阵的行数、列数和非零元素个数："); scanf("%d%d%d",&nrow,&ncol,&num); pA->m = nrow; pA->n = ncol; pA->len = num; for(i = 1; i <= num; i++) { printf("请输入第 %d 个元素的行号、列号和元素值：", i); scanf("%d%d%d",&nrow,&ncol,&elem); pA->data[i].row = nrow; pA->data[i].col = ncol; pA->data[i].e = elem; }
void Print(SMAtrix * pA) for(i=1,t=1;i<=pA->m;i++) if(pA->data[t]. row ==i & pA->data[t]. col ==j) printf ("%4d", pA->data[t]e) t++; el se printf( %4d, 0) void Add(TSMatrix *pA, TSMatrix *pB, TSMatrix pC) int l if(pA->m! pB->m II pA->n != pB->n) printf("两个矩阵的行数与列数不相等,不能相加!n"); return while(i <= pA->len &&j<= pB->len) if(((pA->datai]. row-1)*pA->n+ pA->data[i]. col-1)< ((pB->data[j]. row -1)*pB->n pB->data[j]. col -1)) t++ pC->data[t]. row pA->data[i]. row: pC->data[t]. col pA->data[i]. col pC->datal[t] e=pA->datai]e
} void Print(TSMatrix *pA) { int i, j, t; for(i = 1, t =1; i <= pA->m; i++) { for(j = 1; j <= pA->n; j++) { if(pA->data[t].row == i && pA->data[t].col ==j) { printf("%4d",pA->data[t].e); t++; } else printf("%4d",0); } printf("\n"); } } void Add(TSMatrix *pA, TSMatrix *pB, TSMatrix *pC) { int i, j, t; if(pA->m != pB->m || pA->n != pB->n) { printf("两个矩阵的行数与列数不相等，不能相加！\n"); return; } pC->m = pA->m; pC->n = pA->n; i = 1; j = 1; t = 0; while(i <= pA->len && j <= pB->len) { if(((pA->data[i].row - 1)*pA->n + pA->data[i].col -1) < ((pB->data[j].row - 1)*pB->n + pB->data[j].col -1) ) { t++; pC->data[t].row = pA->data[i].row; pC->data[t].col = pA->data[i].col; pC->data[t].e = pA->data[i].e; i++; } else
if(((pA->datai]. row-1)*pA->n+ pA->data[i]. col-1)> ((pB-data[j]. row-1)*pB-n+ pB->datalj] col -1)) t++; >datalt]. row pB->datalj] pC->data[t]. col pB->data[j].col pC->data[t] e= pB->datalj]e el if(pA->data[]. e+ pB->data [j] e!=0) pC->data[t]. row pA->data[i]. row pC->data[t]. col pA->data[i].col pC->data[t] e= pA->data[i] e+ pB->data [j]e while(i <= pA->len pC->data[]. row pA->data[i].row pC->data[t]. col pA->data[i]. col; pC->data[t] e= pA->data[i]e while(j<=pB->len pC->data[t]. row pB->data [j]. row c->data[t]. col pB->data lil. col C->data[t]e= pB->data[j]e void main O TSMatrix A, B, C: Print(&A)
if(((pA->data[i].row - 1)*pA->n + pA->data[i].col -1) > ((pB->data[j].row - 1)*pB->n + pB->data[j].col -1) ) { t++; pC->data[t].row = pB->data[j].row; pC->data[t].col = pB->data[j].col; pC->data[t].e = pB->data[j].e; j++; } else if(pA->data[i].e + pB->data[j].e != 0) { t++; pC->data[t].row = pA->data[i].row; pC->data[t].col = pA->data[i].col; pC->data[t].e = pA->data[i].e + pB->data[j].e; i++; j++; } } while(i <= pA->len) { t++; pC->data[t].row = pA->data[i].row; pC->data[t].col = pA->data[i].col; pC->data[t].e = pA->data[i].e; i++; } while(j <= pB->len) { t++; pC->data[t].row = pB->data[j].row; pC->data[t].col = pB->data[j].col; pC->data[t].e = pB->data[j].e; j++; } pC->len = t; } void main() { TSMatrix A, B, C; Input(&A); Print(&A); Input(&B);
Print(&B) Add(&A, &B, &C) Print(&c) 5.5//p12习题5.5写一个在十字链表中删除非零元素a(i,j)的算法 #include <stdio. h> #include <stdlib. h typedef int ElementTyp typedef struct oLNode ol ElementType value struct OLNode *right, *down J OLNode, *oLink typedef struct OLink row head, *col head I CrossList void CreateCrossList(CrossList *M) int m. n. t J, OLink p, q printf("请输入矩阵的行数、列数和非0元素个数:"); scanf(%d%d%d", &m, &n, &t) if(m<1‖n<1|lt<0) return M->m m: M->n = n: M->len =t M>row head =(OLink **)malloc(sizeof (OLink) *(m + 1)) M->col head =(OLink *)malloc(sizeof (OLink)*(n + 1)) for( i M->row head[i] =0 for(i=l: i<=n: i++) M->col head[i]=0 f or( m printf("请输入第%个非0元素的行号、列号和元素值:",m) scanf(%d%d%d",&i,&j, &e) p=(OLink)malloc(sizeof(OLNode)) >col=j: p->value =e if (M->row head [i = 0)
Print(&B); Add(&A, &B,&C); Print(&C); } 5.5 //p112 习题 5.5 写一个在十字链表中删除非零元素 a(i,j)的算法 #include <stdio.h> #include <stdlib.h> typedef int ElementType; typedef struct OLNode { int row, col; ElementType value; struct OLNode *right, *down; }OLNode, *OLink; typedef struct { OLink *row_head, *col_head; int m, n, len; }CrossList; void CreateCrossList(CrossList *M) { int m, n, t, i, j, e; OLink p, q; printf("请输入矩阵的行数、列数和非 0 元素个数："); scanf("%d%d%d", &m, &n, &t); if(m < 1 || n < 1 || t < 0) return; M->m = m; M->n = n; M->len = t; M->row_head = (OLink *)malloc(sizeof(OLink) * (m + 1)); M->col_head = (OLink *)malloc(sizeof(OLink) * (n + 1)); for( i = 1; i <= m; i++) M->row_head[i] = 0; for( i = 1; i <= n; i++) M->col_head[i] = 0; for( m =1; m <= t; m++) { printf("请输入第 %d 个非 0 元素的行号、列号和元素值：", m); scanf("%d%d%d", &i, &j, &e); p = (OLink)malloc(sizeof(OLNode)); p->row = i; p->col = j; p->value = e; if(M->row_head[i] == 0)
M->row head[i]= p M->row head[il while( g>right !=0&& qright->col j) q= q-right p->right g->right if(M->col head [j] = 0 M->col head[j]=p p 0 q M->col head [j] while( g->down 1=0 && g->down->row i q= q->down p->down = g->down int DeleElem(CrossList * M, int 1, int j) OLink p, q p= M->row head[i] retur hile(p l =0 && p->col !=j) >right if( return(O) if(p = M->row head[i]) M d[il ls
{ M->row_head[i] = p; p->right = 0; } else { q = M->row_head[i]; while( q->right != 0 && q->right->col < j) q = q->right; p->right = q->right; q->right = p; } if(M->col_head[j] == 0) { M->col_head[j] = p; p->down = 0; } else { q = M->col_head[j]; while( q->down != 0 && q->down->row < i ) q = q->down; p->down = q->down; q->down = p; } } } int DeleElem(CrossList *M, int i, int j) { OLink p, q; p = M->row_head[i]; if(p == 0) return (0); while(p != 0 && p->col != j) { q = p; p = p->right; } if(p == 0) return(0); if(p == M->row_head[i]) M->row_head[i] = p->right; else