[理学]第二章 线性表2.ppt

数组 数组是一种特殊的线性表 表中的数据元素本身也是一种线性表 数组的定义 若线性表中的数据元素为简单元素，则称为一维数组，即向量 若一维数组中的数据元素都是一个一维数组，则称为二维数组 若二维数组中的数据元素都是一个一维数组，则称为三维数组 数组是线性表的扩展 数组特点：结构固定，元素同构 二维数组 数组A可看成一个线性表 A=(a0，a1 ，...，ak ) k=m-1或n-1 ai 或者是行向量 ai =(ai0 ，ai1 ，...，ai,n-1 ) 0≤i≤m-1 aj或者是列向量 aj =(a0j ，a1j ，...，am-1,j ) 0≤j≤n-1 数组的顺序存储结构 次序约定 以行序为主序 以列序为主序 稀疏矩阵 定义 非零元较零元少，且分布没有一定规律的矩阵 压缩存储原则 只存矩阵的行列维数和每个非零元的行列下标及其值 稀疏矩阵的三元组表示法 稀疏矩阵转置算法一 算法思想 将矩阵A的行数和列数互换=矩阵B 将每个三元组的i和j互换=矩阵B 对三元组表B，按其行序进行排序 转置后的三元组B以行（即A的列）为主序排列 稀疏矩阵转置算法二 算法思想 按矩阵A的列序进行转置 首先寻找矩阵A的第1列的所有三元组，将其(i,j,v)改为(j,i,v)后依次存放到矩阵B的三元组表中 然后中寻找矩阵A第2列的所有三元组，将其(i,j,v)改为(j,i,v)后依次存放到矩阵B的三元组表中 依次类推 转置后的三元组B以行（即A的列）为主序排列 稀疏矩阵的转置算法分析 算法的主要耗费时间是在col和p的两重循环中，所以算法的时间复杂度为O(nu*tu) 即和(A的列数与非零元素的个数的乘积)成正比 当非零元个数值tu-m*n时(m、n分别表示数组的行列数),算法的时间复杂度成为O(m*n2 ) 上述转置算法只适用于: tum*n的情况 快速转置算法如下： void fasttrans(mat b,mat a) { //a,b为三元素表 int p,q,col,k; int num[a.n+1],cpot[a.t+1]; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t=0) printf(“a=0”\n); else{ for(col=1;col=a.n; col++) num[col]=0; ];//a中同列非零元素个数归零 for(k=1;k=a.t; k++) //类似 for(j=1;j=a.n;j++)控制循环 ++num[a.data[k].j];//统计a中同列非零元素个数 十字链表的建立算法 算法步骤 Step0:首先输入的信息是:m(矩阵A的行数）,n(矩阵A的列数），紧跟随输入的是t个形如(i,j,aij)的三元组 Step1:建立每行（每列）只有头结点的空链表，并建立这些头结点组成的循环链表 Step2:每输入一个三元组（i,j,aij),则将其结点按其列号的大小插入到第i个行链表中去，同时也按其行号的大小将该结点插入到第j个列链表中去。 算法中将利用一个辅助组数MNodexhd[s+1],其中s=max(m,n),hd[i]指向第i行（第i列）链表的表头。这样做可以在建立链表时随机访问任何一行（列），为建表带来方便。 MLink CreateMLink() { //创建稀疏矩阵的十字链表存储，并返回十字链表的头指针 MLink H; MNode *p,*q,*hd[s+1]; int i,j,m,n,t; Datatype v; Cinmnt; H=new MNode; //申请总头结点 H-row=m; H-col=n; hd[0]=H; for(i=1,is;i++) {p=new MNode;//申请第i个头结点 p-row=0; p-col=0; p-rigth=p; p-down=p; hd[i]=p; 第二章 线性表 线性表的定义、逻辑结构特点及基本运算 线性表的顺序存储结构及基本运算 线性表的链式存储结构及基本运算 数组的逻辑结构定义及其存储方式 线性表的应用示例 本章要点 线性表的逻辑结构、物理结构、基本运算及运算实现的算法。 顺序表上的插入和删除算法及链表的建立、查找、插入和删除算法。 线性表的典型算法的应用及解决问题的方法。 数组的压缩存储及运算 作业 一、填空题 1、假设8行10列的二维数组a[1…8,1..10]分别以行序为主序和以列序为主序顺序存储时，其首地址相同，那么以行序为主