[理学]数据结构 第二章线性表应用.ppt

矩阵的压缩存储 对称矩阵 三角矩阵 稀疏矩阵的压缩存储方法 顺序存储结构 三元组表 带辅助行向量的二元组表 求转置矩阵 问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表 问题分析 一般矩阵转置算法： int trans_sparmat(JD ma[],JD mb[]) { int col,p,n,t,k; if(ma[0].v==0) return(0); n=ma[0].j; t=ma[0].v; mb[0].i=n; mb[0].j=ma[0].i; mb[0].v=t; k=1; for(col=1;col=n;col++) for(p=1;p=t;p++) if(ma[p].j==col) { mb[k].i=ma[p].j; mb[k].j=ma[p].i; mb[k].v=ma[p].v; k++; } return(1); } 十字链表 设行指针数组和列指针数组，分别指向每行、列第一个非零元 结点定义 void crt_linkedmat(JD *rh[],JD *ch[],int *hs,int *ls) int m,n,i,r,c,v; JD *p,*q,*s; printf(Input m,n:); scanf(%d,%d,m,n); for(i=0;im;i++) rh[i]=NULL; for(i=0;in;i++) ch[i]=NULL; *hs=m; *ls=n; for(;;){ printf(Input r,c,v:); scanf(%d,%d,%d,r,c,v); if(r==0 || c==0) break; if((rm)||(cn)) continue; s=(JD *)malloc(sizeof(JD)); s-row=r; s-col=c; s-val=v; s-right=s-down=NULL; q=NULL; p=rh[r-1]; while((p!=NULL) (cp-col)) { q=p; p=p-right; } if(p==NULL) { if(q==NULL) rh[r-1]=s; else q-right=s; } else if(c==p-col) { p-val=v; free(s); continue; } else { if(q==NULL) { rh[r-1]=s; s-right=p; } else { s-right=p; q-right=s; } } q=NULL; p=ch[c-1]; while((p!=NULL)(rp-row)) { q=p; p=p-down; } if(p==NULL) { if(q==NULL) ch[c-1]=s; else q-down=s; } else { if(q==NULL) { ch[c-1]=s; s-down=p; } else { s-down=p; q-down=s; } } } } 字符串 子字符串 字符串P是S的子字符串，则P中的任意字符都在S中出现，且字符间关系完全一致 acdbedaed -- abed acdbedaed -- aced acdbedaed -- cbfd acdbedaed -- dbed 子字符串模式匹配 可否优化算法？ 性能瓶颈所在 p != q，则回溯s以及pat，至si+1与p1重新比较 解决思路 缩短回溯 KMP算法 基本策略 预处理模式pat 获得其中与模式匹配有关的子字符串关系规律 当匹配失败发生时，可以确定继续与s当前位置匹配的pat的新位置 若Si != Pj，回溯Pat，继续比较Si与Pk+1 确定k+1 正确性证明 K+1的确定 x是y的两头匹配的最大真子字符串 正确性（不会遗漏子字符串模式） 反证法 * * a11 a12 …. … ….. a1n a21 a22 …….. ……. a2n