第四章串和数组-北京师范大学.ppt

二、数组与矩阵——矩阵的压缩存储 6 1．初始化十字链表 int InitCrossLinklist CROSSLINKLIST *m,int row,int col,int sum /*初始化一个十字链表，成功则返回1，否则返回0*/ int i; /*根据行数和列数分配相应数量的行链和列链的表头结点*/ m- rhead CROSSNODEPTR malloc row*sizeof CROSSNODE ; m- chead CROSSNODEPTR malloc col*sizeof CROSSNODE ; if m- rhead NULL||m- chead NULL return 0; /*分配失败*/ for i 0;i row;i++ m- rhead[i].right NULL; /*将所有行链设为空链*/ for i 0;i col;i++ m- chead[i].down NULL; /*将所有列链设为空链*/ m- rnum row; m- cnum col; m- sum sum; /*设置行数、列数和非零元素的个数*/ return 1; 二、数组与矩阵——矩阵的压缩存储 7 2.建立一个十字链表的稀疏矩阵 void InputData CROSSLINKLIST *m /*建立一个存储数据的十字链表*/ int len,count; CROSSNODEPTR p,q; int i,j; elemtype v; int row,col,sum; scanf %d,%d,%d,row,col,sum ; /*获取行数、列数和非零元素个数*/ if !InitCrossLinklist m,row,col,sum /*初始化十字链表*/ printf no enough memory\n ; exit 0 ; count 0;/*计数器清零*/ while 1 scanf %d,%d,%d,i,j,v ;/*输入三元组数据*/ if i 0i m- rnumj 0j m- cnum /*三元组数据合法*/ p CROSSNODEPTR malloc sizeof CROSSNODE ; if !p /*分配失败*/ printf no enough memory\n ; return; p- i i; p- j j; p- v v; /*设置三元组结点p的数据域*/ 二、数组与矩阵——矩阵的压缩存储 8 /*开始按列序插入行链，读者应该很熟悉操作细节了*/ q m- rhead[i]; while q- right! NULLq- right- j j q q- right; p- right q- right; q- right p; /*开始按行序插入列链*/ q m- chead[j]; while q- down! NULLq- down- i i q q- down; p- down q- down; q- down p; count++; if count m- sum break;/*数据输入完毕*/ else/*三元组数据非法*/ printf illegal input data\n ; break; //while 二、数组与矩阵——矩阵的压缩存储 9 3．销毁十字链表 void DestroyCrossLinklist CROSSLINKLIST *m /*销毁一个十字链表*/ CROSSNODEPTR p; int i; for i 0;i m- rnum;i++ /*沿着行链，释放链上所有的三元组结点*/ while m- rhead[i].right! NULL p m- rhead[i].right; m- rhead[i].right p- right; free p ; free m- rhead ; free m- chead ; /*释放行链和列链表头结点数组*/ m- rhead m- chead NULL; m- rnum 0; m- cnum 0; m- sum 0; /*其他成员设置成安全值*/ 二、数组与矩阵——稀疏矩阵的转置 1 转置的含义： 三元组数组的转置算法 遍历三元组数组，记下这个稀疏矩阵中每列的非零元素个数，存储数组count 推算出转置后矩阵的各三元组数据的正确的存储位置 ，存储位置存放在数组rpos中 再次遍历三元组数组，对每个数据单元进行转置，按照rpos中的数据存放到新的三元组数组中 0,1,12 0,2,5 1,0,3 1,2,9 2,