第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 1 pA->len =num for(i =1: i 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 #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 data[i].row = nrow; pA->data[i].col = ncol; pA->data[i].e = elem; }
void Print(SMAtrix * pA) for(i=1,t=1;im;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 len &&jlen) if(((pA->datai]. row-1)*pA->n+ pA->data[i]. col-1)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 m; i++) { for(j = 1; j 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 len && j len) { if(((pA->data[i].row - 1)*pA->n + pA->data[i].col -1) 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 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(jlen 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 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 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 #include 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: icol 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 #include 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 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 row_head[i] = 0; for( i = 1; i col_head[i] = 0; for( m =1; m 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 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 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
g->right p-right: q = M->col head[j] if(q = p) M->col head [j] p->down while(g->down p) q q->down ->dot free(p) return (1) void Print(crosslist *M) int 1, J OLink p for(i=1;im;i++) p= M->row head[i] for(j= 1: jn: j++) if(p !=0&& p->col = j) tf(%4d", p->value) p= p->right else void maino int l, J Crosslist m: CreateCrossList(&M) nt(&M) printf("请输入要删除的元素的行号和列号") scanf(%d%d", &i,&j) if(DeleElem(&M, 1, j)) printf("成功删除!Ⅶn") printf("没有对应元素!\n");
q->right = p->right; q = M->col_head[j]; if(q == p) M->col_head[j] = p->down; else { while(q->down != p) q = q->down; q->down = p->down; } free(p); return(1); } void Print(CrossList *M) { int i, j; OLink p; for(i = 1; i m; i++) { p = M->row_head[i]; for(j = 1; jn; j++) if(p != 0 && p->col == j) { printf("%4d", p->value); p = p->right; } else printf("%4d", 0); printf("\n"); } } void main() { int i,j; CrossList M; CreateCrossList(&M); Print(&M); printf("请输入要删除的元素的行号和列号"); scanf("%d%d",&i, &j); if(DeleElem(&M, i, j)) printf("成功删除！\n"); else printf("没有对应元素！\n");
十A[ob口A A 山∧ a 回b回d∧pe→f 5.7(a,b),((c,d),(b),b,(d) 实习题 #include <stdio. h #include <stdlib. h #include <time. h void CreateArray (int *a, int m, int n) time t t int 1 time(&t) srand((unsi gned int)t) for(i =0: i<m*n: i++) ali= rando%100 int SearchSaddlePoint(int *a, int m, int n) int i,j, k, pmin, pmax for(i=0: i<m; i++) 1冰n for(j=1: j<n: j++) if(*(a+i*n+j)< *(a+pmin))
Print(&M); } 5.6 5.7 (a,b), ((c,d)), (b), b, (d) 实习题： #include #include #include void CreateArray(int *a, int m, int n) { time_t t; int i; time(&t); srand((unsigned int)t); for(i = 0; i<m*n; i++) a[i] = rand() % 100; } int SearchSaddlePoint(int *a, int m, int n) { int i,j,k,pmin,pmax; for(i=0; i<m;i++) { pmin = i*n; for(j = 1; j<n; j++) if(*(a+i*n+j) < *(a+pmin))
1*n k=pmax%n;/得到第i行中最小元素所在的列号 if(*(a+j)>*(atpmax)) pmax = J f(pi printf(%\t%d\n", pmax/n+1, pmax%n 1) void Printarray (int *a, int int 1 printf( %5d", *(ati=n+j)) printf("\") void main o printf("请输入要创建的矩阵的行数和列数: scanf(%d%d", &m, &n) a =(int *)malloc(sizeof (int)*mpn while(1) CreateArray(a, m, n) if(SearchSaddlePoint(a, m, n)) Printarray(a, m, n)
pmin = i*n + j; pmax = pmin; k = pmax % n; //得到第 i 行中最小元素所在的列号 for(j = k; j *(a+pmax)) pmax = j; if(pmax == pmin) { printf("%d\t%d\n",pmax/n + 1, pmax%n + 1); return 1; } } return 0; } void PrintArray(int *a, int m, int n) { int i,j; for(i = 0; i < m; i++) { for(j = 0; j < n; j++) printf("%5d", *(a+i*n+j)); printf("\n"); } } void main() { int *a; int m,n; printf("请输入要创建的矩阵的行数和列数："); scanf("%d%d",&m, &n); a = (int *)malloc(sizeof(int)*m*n); while(1) { CreateArray(a, m, n); // PrintArray(a, m, n); if(SearchSaddlePoint(a, m, n)) { PrintArray(a, m, n); break; } // printf("\n"); }
free(a) 补充练习 1、对于一个二维数组A[m][n],若按行序为主序存储,则任一元素A[i][j相对于A[O][0]的地 址是多少? 0020 3000 2、一个稀疏矩阵为 则对应的三元组表是什么? 0000 、设有一个10阶的对称矩阵A,采用压缩存储方式以行序为主序存储,a0.第一个元素,其存 储地址为0,每个元素占有一个存储地址空间,则a85的地址是多少? 4、设有上三角矩阵(a)x,将其上三角逐行存于数组B[m]中,使得B[m=a1,且k=f1(i)+f2(j)+c 请写出函数f1,f2和常数c(f1和f2中不含常数项) 5、求下列广义表操作的结果: (1)Head ((p, h, w)) (2) Tail((b, k, p, h)) (3) Tail(((a, b),(c, d))) (4) Tail(Head(((a, b),(c, d))) (5)Tail(Head(Tail(((a, b),(c, d)))) 6、假设稀疏矩阵A和B均以三元组顺序表作为存储结构,试写出矩阵相加的算法: nt AddMatrix (TSMatrix A, TSMatrix B, TSMatrix &C) 7、试编写一个以三元组形式输出用十字链表存储表示的稀疏矩阵中非零元素的下标及其元素值的 算法: int print( Crosslist&M) 8、按照教材5.5节中图5.8所示结点结构,画出下列广义表的存储结构图,并求出它的深度 (1)((()),a,((b,c),(),d),(((e)))) (2)(((a),b)),(),d),(e,f) 31000 9、设三角矩阵43000 采用一维数组进行压缩存储,第一个元素为R1,存储位置 5836750 10146991 为1,每个元素占一个存储位置,则R32的存储位置为几? 参考解答: 1、&A[O][0]+(i*n+j)米//L为每一数据元素所占的字节数 2、(1,3,2),(2,1,3),(3,3,-1),(3,4,5)) 3、&a;=&ao+(i*(i+1)/2+j)米(i≥=j)//&a0.第一个元素的地址,L为每一 &a=&ao+(j*(j+1)/2+i)*L(j>=i)//元素所占存储空间 则a5的地址为0+8*9/2+5=41 4、若行号与列号均从0开始,则元素a;前有i行,各行的非0元素个数从n到n-i+1,共有 i*(n+n-i+1)/2个元素,a所在的行中,其前面共有j个元素,但为0的元素有i个,不为0的
free(a); } 补充练习： 1、对于一个二维数组 A[m][n]，若按行序为主序存储，则任一元素 A[i][j]相对于 A[0][0]的地 址是多少？ 2、一个稀疏矩阵为 − 0 0 0 0 0 0 1 5 3 0 0 0 0 0 2 0 ，则对应的三元组表是什么？ 3、设有一个 10 阶的对称矩阵 A，采用压缩存储方式以行序为主序存储，a00 为第一个元素，其存 储地址为 0，每个元素占有一个存储地址空间，则 a85 的地址是多少？ 4、设有上三角矩阵（aij）n×n，将其上三角逐行存于数组 B[m]中，使得 B[m]= aij，且 k=f1(i)+f2(j)+c。 请写出函数 f1，f2 和常数 c（f1 和 f2 中不含常数项）。 5、求下列广义表操作的结果： （1）Head((p,h,w)); （2）Tail((b,k,p,h)); （3）Tail(((a,b),(c,d))); （4）Tail(Head(((a,b),(c,d)))); （5）Tail(Head(Tail(((a,b),(c,d))))); 6、假设稀疏矩阵 A 和 B 均以三元组顺序表作为存储结构，试写出矩阵相加的算法： int AddMatrix(TSMatrix A, TSMatrix B, TSMatrix &C); 7、试编写一个以三元组形式输出用十字链表存储表示的稀疏矩阵中非零元素的下标及其元素值的 算法：int Print(CrossList &M); 8、按照教材 5.5 节中图 5.8 所示结点结构，画出下列广义表的存储结构图，并求出它的深度。 （1）（（（）），a，（（b，c），（），d），（（（e）））） （2）（（（（a），b）），（（（），d），（e，f））） 9、设三角矩阵 R= 10 14 69 91 58 36 75 0 43 0 0 0 31 0 0 0 采用一维数组进行压缩存储，第一个元素为 R11，存储位置 为 1，每个元素占一个存储位置，则 R32 的存储位置为几？ 参考解答： 1、&A[0][0]+(i*n+j)*L //L 为每一数据元素所占的字节数 2、((1,3,2),(2,1,3),(3,3,-1),(3,4,5)) 3、&aij=&a00+(i*(i+1)/2+j)*L (i>=j) //&a00 为第一个元素的地址，L 为每一 &aij=&a00+(j*(j+1)/2+i)*L (j>=i) //元素所占存储空间 则 a85 的地址为 0+8*9/2+5=41 4、若行号与列号均从 0 开始，则元素 aij 前有 i 行，各行的非 0 元素个数从 n 到 n-i+1，共有 i*(n+n-i+1)/2 个元素，aij 所在的行中，其前面共有 j 个元素，但为 0 的元素有 i 个，不为 0 的
元素个数则为ji个,所以在上三角中a;前面共有i*n+n-i+1)/2+j-i个非0的元素,这些元 素需要存储在一维数组B[中,且在a;的前面,若一维数组的下标也从0开始,若用B[k]存储 au,则k=i*(n+n-i+1)/2+j-i=(-i2-i+2in)/2+j 即:f1(1)=(-i+2n-1)f2()= 若下标均从1开始,则f()=÷(-i+2n+1)f2()=jc=n 5、(1)p(2)(k,p,h)(3)((c,d))(4)(b)(5)(d) 6、参考上面教材习题解答。 7, Status Print(CrossList &M) for(i=1; ii,q->j,q->e);//输出一个结点所对应的三元组 g=q-right 8、深度均为4,画图略。 9、&R1=&R1+(i*(i-1)/2+j-1)米=1+4=5
元素个数则为 j-i 个，所以在上三角中 aij 前面共有 i*(n+n-i+1)/2+ j-i 个非 0 的元素，这些元 素需要存储在一维数组 B[]中，且在 aij 的前面，若一维数组的下标也从 0 开始，若用 B[k]存储 aij，则 k= i*(n+n-i+1)/2+ j- i =(-i 2 -i+2in)/2+j 即： ( 2 1) 2 ( ) 1 = −i + n − i f i f ( j) = j 2 c=0 若下标均从 1 开始，则 ( 2 1) 2 ( ) 1 = −i + n + i f i f ( j) = j 2 c=-n 5、（1） p （2）（k，p，h） （3）（（c，d）） （4）（b） （5）（d） 6、参考上面教材习题解答。 7、Status Print(CrossList &M) { OLink *p; p=M.rhead; for(i=1;ii,q->j,q->e); //输出一个结点所对应的三元组 q=q->right; } } } 8、深度均为 4，画图略。 9、&Rij=&R11+(i*(i-1)/2+j-1)*L=1+4=5
