西安电子科技大学计算机学院数据结构课件 第5章（1）.pptVIP

数组是n(n＞1)个相同类型数据元素a0,a1,…,an-1构成的有限序列,且该有限序列存储在一块地址连续的内存单元中。 数组的定义类似于采用顺序存储结构的线性表，是线性表在维数上的扩张，也就是线性表中的元素又是一个线性表。 n维数组，bi是第i维的长度，则n维数组共有 个数据元素，每个元素受n个关系的制约，就单个关系而言，这n个关系仍然是线性的。 Status FastTranSMatrix(TSMatrix A, TSMatrix B) { B.rows=A.cols; B.cols=A.rows; B.nums=A.nums; if(B.nums){ for(col=1; col=A.nums; ++col) num[col] = 0; for(t=1; t=A.nums; ++t) ++num[A.data[t].j]; cpot[1] = 1; for(col=2; col=A.nums; ++col) cpot[col] = cpot[col-1]+num[col-1]; for(p=1; p=A.nums; ++p){ col = A.data[p].j; q = cpot[col]; B.data[q].i = A.data[p].j; B.data[q].j = A.data[p].i; B.data[q].e = A.data[p].e; ++cpot[col]; } } return OK; } 练习： 1. 将一个A[1..100, 1..100]的三对角矩阵，按行优先存入一维数组B[1..298]，A中元素a66,65在B数组中的位置k=?。 在主对角线左下方，65*3-1+1 = 195。 2. 有二维矩阵A[m][n]，其元素类型为int，每行每列按从小到大有序，试给出一个算法求数组中值为x的元素的行号和列号，前提是x在A中存在，要求比较次数不超过m+n次。 void search(int **A, int x, int i, int j) { i = 0; j = n-1; while(A[i][j] != x){ if(A[i][j] x) j--; else i++; } } 3. (4.18)编写算法，求串s所含不同字符的总数和每种字符的个数。 void StrCount(SString s) { SString r; int *num = new int[s[0]]; for(i=1; i=s[0]; i++) num[i] =0; r[1] = s[1]; num[1] = 1; r[0] = 1; for(i=2; i=s[0]; i++){ j = 1; while( s[i]!=r[j] j=r[0]) ++j ++num[j]; if(jr[0]) { r[j] = s[i]; ++r[0]; } } } void StrCount(SString s) { int num[256]; for(i=0; i256; ++i) num[i] = 0; for(i=0; is[0]; ++i) ++num[int(s[i])]; j = 0; for(i=0; i256; ++i) if(num[i]) ++j; } 作业： 5.2 5.3 5.6 5.25 * 第5章 数组和广义表 第5章 数组和广义表 5.1 数组的定义和运算 5.2 数组的顺序存储和实现 5.3 特殊矩阵的压缩存储 5.4 广义表 1. 数组的定义和运算 数组具有以下性质： (1)数组中的数据元素数目固定。一旦定义了一个 数组,其数据元素数目不再有增减变化。 (2)数组中的数据元素具有相同的数据类型。 (3)数组中