第5章 数组与广义表 【本章学习目标】 多维数组是一种最简单的非线性结构，它的存储结构也很简单，绝大多数高级语言采用顺序存储方式表示数组，存放顺序有的是行优先，有的是列优先。在多维数组中，使用最多的是二维数组，它和科学计算中广泛出现的矩阵相对应。对于某些特殊的矩阵，用二维数组表示会浪费空间，本章介绍了它的压缩存储方法。对元素分布有一定规律的特殊矩阵，通常将其压缩存储到一维数组中，还可以利用该矩阵和二维数组间元素下标的对应关系，容易、直接地算出元素的存储地址。对于稀疏矩阵，通常采用三元组表或十字链表来存放元素。 广义表是一种复杂的非线性结构，是线性表的推广。这里简要介绍了它的概念、基本运算和存储结构。 通过本章的学习，要求：  理解数组中元素逻辑存储结构；  理解数组元素寻址公式的含义；  掌握特殊矩阵压缩存储方法；  掌握稀疏矩阵压缩存储表示下转置和相乘运算的实现；  掌握广义表的概念和它的定义方式、表头和表尾的定义；  掌握广义表的性质；  掌握广义表的存储结构；  掌握广义表的基本操作。 5.1数组的定义和运算 数组的特点是每个数据元素可以又是一个线性表结构。因此，数组结构可以简单地定义如下。若线性表中的数据元素为非结构的简单元素，则称为一维数组，即为向量； 若一维数组中的数据元素又是一维数组结构，则称为二维数组； 以此类推，若二维数组中的元素又是一个一维数组结构，则称为三维数组。 结论： 线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展（见图5.1）。 Am×n= a00a01…a0，n-1 a10a11…a1，n-1 ………… am-1,0am-1,1…am-1，n-1 图5.1二维数组的逻辑结构 其中，A是数组结构的名称，整个数组元素可以看成是由m个行向量和n个列向量组成的，其元素总数为m×n。在C语言中，二维数组中的数据元素可以表示成a［表达式1］［表达式2］，表达式1和表达式2分别被称行下标表达式和列下标表达式，例如a［i］［j］。 5.1.1数组的定义 ADT Array { 数据对象： ji=0，…，bi-1，i=1，2，…n， D={aj1j2…jn|n(>0)称为数组的维度，bi是数组第i维的长度， ji是数组元素的第i维下标，aj1j2…jn∈ElemSet} 数据关系：R={R1，R2，…，Rn} Ri={| 0≤jk≤bk-1，1≤k≤n 且k≠i， 0≤ji≤bi-2， aj1…ji…jn，aj1…ji+1…jn∈D，i=2，…，n} } ADT Array 5.1.2数组的基本运算 ADT Array { InitArray(&A, n, bound1, …, boundn) 操作结果： 若维数n和各维长度合法，则构造相应的数组A，并返回OK。 DestroyArray(&A) 操作结果： 销毁数组A。 Value(A, &e, index1, …, indexn) 初始条件： A是n维数组，e为元素变量，随后是n个下标值。 操作结果： 若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。 Assign(&A, e, index1, …, indexn) 初始条件： A是n维数组，e为元素变量，随后是n个下标值。 操作结果： 若下标不超界，则将e的值赋给所指定的A的元素，并返回OK。 } ADT Array 5.2数组的顺序存储结构 直观上看，数组可看成一组数对，即下标和值。对每一个有定义的下标，都有一个与该下标相关联的值。一维数组的值对应一个下标，二维数组则对应两个，以此类推，n维数组的值对应n个下标。 数组是一种“均匀”结构，即数组中每个元素必须具有同样的类型。数组又是一种随机存取结构，只要给定一组下标，就可以访问与这组下标相关联的值。就数组而言，我们所关心的操作主要是值检索和值存储。 在内存中，数组元素是连续存储的。数组的第一个元素的地址称为基地址，也称为数组的起始地址。当用一组连续的存储单元存放多维数组的元素时会遇到次序问题。例如，对于二维数组a［2］［3］，如果每个元素占用1字节，那么分配给数组a的内存空间就有6字节，那么数组a的6个元素a［0］［0］、a［0］［1］、a［0］［2］、a［1］［0］、a［1］［1］和a［1］［2］在内存中如何排列呢？ 5.2.1行优先存储 一种方法是先放第一行的三个元素，再放第二行的三个元素。这种方式称为以行为主序的存储方式，按这种方法得到的排列次序如图5.2所示 图5.2二维数组以行为主序的存储方式 5.2.2列优先存储 另一种方法是先放第一列元素的两个元素，再放第二列的元素，最后放第三列的三个元素，这种方式称为以列为主序的存储方式，按这种方法得到的排列次序如图5.3所示。 图5.3二维数组以列为主序的存储方式 如果数组a［2］［3］采用以行为主序的存储方式，并假定其基地址为100，即元素a［0］［0］存储于单元100中，则a［0］［1］存储在单元101中，a［0］［2］存储在单元102中，a［1］［2］存储在单元105中。这个地址是很容易算出来的。其实，只要知道数组的维数，数组每个元素的地址可以很容易地通过数组的基地址得到。 对于一维数组a［n］，假定每个元素占1字节，α是数组的基地址。则元素a［0］的地址是α，元素a［1］的地址是α+1。由于在第i+1个元素之前有i个元素，因此任一元素a［i］的地址是α+i，元素与其地址的关系如下： 数组元素a［0］a［1］a［2］…a［i］…a［n-1］ 地址αα+1α+2…α+i…α+ n 对于二维数组a［m］［n］，我们可以理解为a是一维数组，它有m个元素，分别是行0、行1……行m-1，而每一行又由n个元素组成，如图5.4所示。 图5.4二维数组元素排列方式 若α是数组a的基地址，也就是其元素a［0］［0］的地址，则第1行的第1个元素的地址为α+1×n，第2行的第1个元素的地址为α+2×n。因为在第i+1行的第一个元素之前有i行，每行有n个元素，所以第i+1行的第一个元素a［i］［0］的地址是α+i×n，知道了a［i］［0］的地址，那么a［i］［j］的地址就是α+i×n+j。因此二维数组中元素a［i］［j］的地址为： α+i×n+j 对于三维数组a［m］［n］［p］，可以看成m个大小为n×p的二维数组，如图5.5所示。 图5.5三维数组的以行为主的顺序表示法 因为在元素a［i］［0］［0］之前有i个大小为n×p的二维数组，所以元素a［i］［0］［0］的地址为α+i×n×p，这也是第i个二维数组的基地址，由a［i］［0］［0］的地址及二维数组的寻址公式，可求得三维数组元素a［i］［j］［k］的寻址公式为（以行优先为例）： α+i×n×p+j×p+k 综上所述，可以看出数组的两个特点： 第一，对同一数组的任何一个元素，由下标求存储地址的运算时间是一样的，也就是说对任何一个数组元素的访问过程是平等的，这是随机存取结构的一个优点； 第二，为了在内存中给数组开辟足够的存储单元，数组的维数和大小必须事先给出。这对于数组大小不能预先确定的问题就很不方便，数组大小规定大了会浪费空间； 规定小了，运行时会出现越界，使程序无法运行下去。这是数组这种数据结构的一个缺点。不过，对于许多应用程序来说，数组仍然是完成任务的最合适的工具。 5.3矩阵的压缩存储 矩阵是许多科学与工程计算问题中经常出现的数学对象。这里，我们感兴趣的不是矩阵本身，我们所关心的是表示矩阵的方法，以使对矩阵的各种运算能有效地完成。数学上，一个矩阵一般由m行和n列元素组成，如图5.6所示。其中，矩阵元素都是数字。矩阵M1有3行4列共12个元素，矩阵M2有5行5列共25个元素。 图5.6两个矩阵M1与M2 5.3.1特殊矩阵——对称矩阵和三角矩阵 一般地，我们把一个m行n列的矩阵表示成m×n，矩阵的元素个数总计为m×n个。如果m等于n，则称该矩阵为方阵。对于一个m×n的矩阵，用二维数组，例如matrix［m］［n］来表示最简单不过了，这种表示法需要的存储空间是m×n。在这种表示方法下，通过matrix［i］［j］可以快速找到矩阵中的任意元素。然而，这种存储表示也存在一些问题，如果观察图5.7(b)所示的矩阵M2，就能够发现，该矩阵中的元素是对称的，即矩阵中第i行第j列与第j行第i列元素的值相等，这种矩阵称为对称矩阵。对于n×n的对称矩阵，我们只需要为每一对对称元素分配一个存储空间，这样就只需要存储其下三角或上三角（包括对角线）中的元素即可，如图5.7中的阴影部分所示。 图5.7矩阵M2的下三角和上三角元素 因为n×n矩阵的下三角或上三角的元素有n(n+1)/2个，所以可以将n2个元素压缩存储到n(n+1)/2个存储单元中。假设以一维数组a［n(n+1)/2］来存储n×n对称矩阵的下三角元素，那么矩阵中第i行第j列元素应该放在数组a中的哪一个位置呢？注意，矩阵的第0行只存储一个元素，第1行存储2个元素，以此类推。这样，第i+1行前面共有i行，因此总共要存储1+2+3+…+i=i×(1+i)/2个，反之，对所有的k=0，1，2，…，n(n+1)/2-1，都能确定a［k］中的元素在矩阵中的位置(i，j)。图5.8给出了图5.6(b)所示矩阵M2的压缩存储形式。 图5.8对称矩阵M2的压缩存储 当一个n×n矩阵的主对角线上方或下方的所有元素皆为0时，称该矩阵为三角矩阵。下三角矩阵中的右上角总是0，如图5.9（a）所示。而图5.9(b)所示的是一个上三角矩阵。对于这样的三角矩阵，同样也可采用对称矩阵的压缩存储方式将其上三角或下三角的元素存储在一维数组中，以达到节约存储空间的目的。 图5.9三角矩阵 5.3.2稀疏矩阵 除了上述介绍的对称矩阵和三角矩阵等特殊矩阵外，在实际应用中我们还经常遇到这样一种矩阵。观察如图5.10（a）所示的矩阵，就可发现矩阵中的很多元素为0，这样的矩阵称为稀疏矩阵。至于矩阵中0元素多少才能算作稀疏矩阵，并没有确切定义。这只是一个直观上的概念。在图5.10（a）所示的矩阵的42个元素中，只有8个是非0元素，就可以认为这个矩阵是稀疏矩阵。 图5.10稀疏矩阵示例 稀疏矩阵要求我们考虑一种新的表示方法。之所以如此，一方面是因为在实际应用中许多矩阵都是大型的，而同时又是稀疏的。例如1000×1000的矩阵，一百万个元素中只有1000个是非0元素。另一方面，矩阵中的0元素在矩阵运算中是没有意义的。例如在矩阵转置和矩阵相乘运算中，0元素的运算可不必考虑。如果采用二维数组表示矩阵既浪费了大量的存储单元来存储0元素，又要花大量的时间进行0元素的运算。所以我们要为稀疏矩阵寻找一种新的存储其元素的方法，这种表示法将只存储矩阵中的非0元素。 由于稀疏矩阵中的非0元素的位置是没有规定的，因此为了表示一个矩阵的非0元素Mij，我们必须存储该元素所在的行、列和其值。这样可将一个稀疏矩阵中的非零元素按三元组（行，列，值）存储。为操作方便起见，按照行号递增、任意行按照列号递增的方式组织三元组，最终形成三元组表结构。于是，图5.10（a）所示的稀疏矩阵M就可存储在三元组表a［t+1］［3］中，如图5.10（b）所示。其中t=8是稀疏矩阵中非0元素的个数，三元组表中a［0］［1］、a［0］［2］和a［0］［3］分别表示稀疏矩阵的行数、列数和非0元素个数。 在矩阵上最小的操作集合包括创建、转置、加法、减法和乘法。下面介绍矩阵转置和矩阵相乘算法。 1. 稀疏矩阵的转置算法 对于一个m×n的矩阵M，它的转置矩阵T是一个n×m的矩阵，而且原矩阵M的任意元素M［i］［j］应该成为其转置矩阵中的元素T［j］［i］。换句话说，就是把矩阵的行与列对换。图5.10(a)所示矩阵M的转置矩阵T和T对应的三元组表b如图5.11（a）和图5.11(b)所示。 图5.11矩阵转置示例 如果矩阵采用二维数组表示，转置算法很容易实现。对于一个m×n的矩阵M，得到其转置矩阵T的关键代码为 for (j = 0; j < n; j++) for (i = 0; i < m; i++) T［j］［i］ = M［i］［j］; 由于稀疏矩阵是用三元组表表示的，很显然不能使用上述算法进行转置。那么对于图5.10（b）中的三元组表来说，如何得到图5.11（b）所示的三元组表呢？一个简单的想法是，顺序地取出a 中的元素然后顺序地放到b中。例如，取出a中的第1个元素（0，0，5）变成（0，0，5）放到b中的第1行，取出a中的第2个元素（0，3，2）变成（3，0，2）放到b中的第2行，a的第3个元素（0，5，8）变成（5，0，8）放到b中的第3行，以此类推。但是观察图5.10（b）和图5.11(b)就能够发现，这种做法是错误的，因为我们看到a中元素（0，3，2）变成（3，0，2）并不是放在b中的第2行，而是放在b中的第6行。 正确的方法应该是将原矩阵M中的元素按每一列从上而下进行转置。为此，应对三元组表a中的第2列元素进行多次反复扫描，第一次取出矩阵M中列号为0的所有元素，将它们顺序放入b中，第二次取出矩阵M中列号为1的元素，将它们顺序放入b中。如此进行下去，直到a中所有元素均放入b中，转置过程结束。 以图5.10（a）所示的稀疏矩阵M为例。 第一次，挑出第2列所有数值为0者，即在矩阵M中的第0列者，逐个放入数组b中。a中第1行元素（0，0，5）和第7行元素(4，0，9)的列号为0，因此将它们分别放入b的第1行和第2行。三元组表b如图5.12所示。 图5.12稀疏矩阵M的三元组表1（第2列所有数值为0者） 第二次，挑出第2列所有数值为1的元素，只有第4行元素（1，1，6）的列号为1，将其放到b的第3行。此时的三元组表b如图5.13所示。 图5.13稀疏矩阵M的三元组表2（第2列所有数值为1者） 第三次，找列号为2的元素进行转置。列号为2的元素有两个，即（1，2，9）和 (5，2，2)，将a 中这两个元素分别放到b的第4和第5行。三元组表b如图5.14所示。 图5.14稀疏矩阵M的三元组表3（列号为2的元素转置后） 如此做下去，直到a中所有元素都放到b中为止，转置结束。最后的三元组表b如图5.11（b）所示。需要注意的是，当a的某行放到b中时，a的第1列数值放到b的第2列，a的第2列数值放到b的第1列。 实现上述矩阵转置算法的C语言函数transpose的算法如下所示。其中m和n分别为矩阵M的行数和列数，t为M的非0元素个数。p表示a中某行的下标，变量q指向转置矩阵三元组表b中下一个元素插入的位置。col表示矩阵M中某列的列号。 void transpose(a,b) {m=a［0］［0］; n=a［0］［1］; t=a［0］［2］; b［0］［0］=n; b［0］［1］=m; b［0］［2］=t; if(t==0) exit; q=1;/*从b的第一行做起*/ for(col=0;coltag == 1) p = ls->hp; returnp; } GList Tail(GList ls) { If( ls->tag == 1) p = ls->tp; returnp; } 2. 建立广义表的存储结构 算法1： intCreate(GList *ls, char *S) { Glistp;char*sub; if (StrEmpty(S)) *ls=NULL; else { if (!(*ls=(GList)malloc(sizeof(GLNode))))return0; if (StrLength(S)==1) { (*ls)->tag=0; (*ls)->data=S; } else { (*ls)->tag=1; p=*ls; hsub=SubStr(S,2,StrLength(S)-2); do { sever(sub,hsub); Create(&(p->ptr.hp), sub); q=p; if (!StrEmpty(sub)){ if (!(p=(GList)malloc(sizeof(GLNode))))return 0; p->tag=1; q->ptr.tp=p; } }while (!StrEmpty(sub)); q->ptr.tp=NULL; } } return 1; } 算法2： intsever(char *str, char *hstr) { intn=StrLength(str); i=1; k=0; for (i=1, k=0; i <=n || k !=0; ++i) { ch=SubStr(str,i,1); if (ch=='(')++k; elseif (ch==')')--k; } if (i <=n) { hstr=SubStr(str,1,i-2); str=SubStr(str,i,n-i+1); } else { StrCopy(hstr,str); ClearStr(str); } } 3. 以表头、表尾建立广义表 intMerge(GList ls1,GList ls2, Glist *ls) { if (!(*ls = (GList)malloc(sizeof(GLNode))))return 0; *ls->tag = 1; *ls->hp = ls1; *ls->tp = ls2; return 1; } 4. 求广义表的深度 int Depth(GList ls) { if (!ls) return1;/*空表深度为1*/ if (ls->tag == 0) return0;/*单元素深度为0*/ for (max = 0,p = ls; p; p = p->ptr.tp) { dep = Depth(p->ptr.hp);/*求以p->ptr.hp为头指针的子表深度*/ if (dep > max)max = dep; } return max+1;/*非空表的深度是各元素的深度的最大值加1*/ } 5. 复制广义表 intCopyGList(GList ls1, GList *ls2) { if (!ls1)*ls2 = NULL;/*复制空表*/ else { if (!(*ls2 = (Glist)malloc(sizeof(Glnode)))) return 0;/*建立表结点*/ (*ls2)->tag = ls1->tag; if (ls1->tag == 0) (*ls2)->data = ls1->data;/*复制单元素*/ else { CopyGList(&((*ls2)->ptr.hp), ls1->ptr.hp);/*复制广义表ls1->ptr.hp的 一个副本*/ CopyGList(&((*ls2)->ptr.tp) , ls1->ptr.tp);/*复制广义表ls1->ptr.tp的 一个副本*/ } } return 1; } 5.7数组的应用 请看下面的例题，希望能给读者带来一些指导和启发，在枯燥的学习之余给读者带来一些愉悦和收获！ 【例5.1】 请利用栈结构、利用非递归算法实现广义表的存储结构。 struct stack { struct GLNode elem［255］; int top; }S;//定义用于存储结点的栈 //pop(S) 和push(S, p)表示数据的出栈和入栈 struct GLNode *bulid_ptr()//建立表结点函数 { struct GLNode *p1; p1=(struct GLNode *)malloc(sizeof(struct GLNode)); p1->tag=1;//表示p结点是表结点,并初始化两个指针变量 p1->atom_ptr.hp=NULL; p1->atom_ptr.tp=NULL; return p1; } struct GLNode *bulid_atom(char c)//建立原子结点函数 { struct GLNode *p1; p1=(struct GLNode *)malloc(sizeof(struct GLNode)); p1->tag=0; p1->atom_ptr.atom=c; return p1; } 该算法的主体如下： S.top=-1; i=0; while(str［i］!='/0') { switch(str［i］) { case '(': p=build_ptr();//建立表结点 if(S.top>-1)//栈不为空,p赋给栈顶表结点的hp S.elem［S.top］->atom_ptr.hp=p; push(S,p);//p结点入栈 case ',': p=build_ptr();//建立表结点 q=pop(S);//S的栈顶元素出栈,并赋给q q->atom_ptr.tp=p; //q的tp指向p push(S,p); //p结点入栈 case ')': pop(S);// S的栈顶元素出栈 default : p=build_atom(str［i］); //建立原子结点 S.elem［S.top］->atom_ptr.hp=p; // p赋给栈顶表结点的hp } } 【例5.2】已知Ackerman函数定义如下： (1) 根据定义，写出它的递归求解算法； (2) 利用栈，写出它的非递归求解算法。 (1) 已知函数本身是递归定义的，所以可以用递归算法来解决： unsigned akm(unsigned m, unsigned n) { if (m ==0) return n+1;//m == 0 else if (n ==0) return akm (m-1, 1);//m > 0, n == 0 else returnakm (m,n-1);//m > 0, n > 0 } (2) 为了将递归算法改成非递归算法，首先改写原来的递归算法，将递归语句从结构中独立出来： unsigned akm(unsigned m, unsigned n) { unsigned v; if (m ==0) return n+1;//m == 0 if (n ==0) return akm (m-1, 1);//m > 0, n ==0 v = akm(m, n-1);//m > 0, n > 0 return akm(m-1, v); } 用一个栈记录每次递归调用时的实参值，每个结点有两个域{vm,vn}。对以上实例，栈的变化相应算法如下： #include #include "stack.h" #define maxSize 3500; unsigned akm(unsigned m, unsigned n) { struct node { unsigned vm, vn; } stack st(maxSize);node w; unsigned v; w.vm = m; w.vn = n; st.Push(w); do { while (st.GetTop().vm > 0) { //计算akm(m-1, akm(m, n-1) ) while (st.GetTop().vn > 0)//计算akm(m, n-1),直到akm(m, 0) { w.vn--; st.Push(w); } w = st.GetTop(); st.Pop(w0;//计算akm(m-1, 1) w.vm--; w.vn = 1; st.Push(w);//直到akm(0, akm(1, * ) ) w = st.GetTop(); st.Pop(); v = w.vn++;//计算v = akm(1,*)+1 if (st.IsEmpty() == 0)//如果栈不空， 改栈顶为(m-1, v) { w = st.GetTop(); st.Pop(); w.vm--; w.vn = v; st.Push(w); } } } while (st.IsEmpty() == 0); return v; } 【例5.3】背包问题： 设有一个背包可以放入的物品的重量为s，现有n件物品，重量分别为w［1］， w［2］， …， w［n］。问能否从这n件物品中选择若干件放入此背包中，使得放入的重量之和正好为s。如果存在一种符合上述要求的选择，则称此背包问题有解(或称其解为真)； 否则称此背包问题无解(或称其解为假)。试用递归方法设计求解背包问题的算法。 根据递归定义，可以写出递归的算法。 enum boolean { False, True } boolean Knap(int s, int n) { if (s == 0) return True; if (s < 0 || s > 0 && n < 1) return False; if (Knap(s - W［n］, n-1) == True) { printf("%f",W［n］);return True; } return Knap(s, n-1); } 若设w={0，1，2，4，8，16，32}，s=51，n=6,则递归执行过程如下： 递归 Knap(51, 6) return True;//完成 Knap(51-32, 5) return True;//打印32 Knap(19-16, 4) return True;//打印16 Knap(3-8, 3) return False; Knap(3,3) return True;//无动作s=-5 < 0 return False; Knap(3-4, 4) return False; Knap(3,2) return True;//无动作s=-1 < 0 return False ; Knap(3-2, 1) return True;//打印2 Knap(1-1, 0) return True;//打印1 s=0 return True 【例5.4】八皇后问题： 设在初始状态下在国际象棋棋盘上没有任何棋子(皇后)。然后顺序在第1行，第2行，…,第8行上布放棋子。在每一行中有8个可选择位置，但在任一时刻，棋盘的合法布局都必须满足三个限制条件，即任何两个棋子不得放在棋盘上的同一行、同一列，或者同一斜线上，试编写一个递归算法，求解并输出此问题的所有合法布局。(提示： 用回溯法。在第n行第j列安放一个棋子时，需要记录在行方向、列方向、正斜线方向、反斜线方向的安放状态，若当前布局合法，可向下一行递归求解，否则可移走这个棋子，恢复安放该棋子前的状态，试探本行的第j+1列)。 此为典型的回溯法问题。 在解决八皇后问题时，采用回溯法。在安放第i行皇后时，需要在列j的方向从1到n试探(j=1，2,…，n)。首先在第 j 列安放一个皇后，如果在列、主对角线、次对角线方向有其他皇后，则出现攻击，撤销在第j列安放的皇后。如果没有出现攻击，则在第j列安放的皇后不动，递归安放第i+1行皇后。 解题时设置如下4个数组。 (1) col［n］：col［i］ 标识第i列是否安放了皇后； (2) md［2n-1］：md［k］ 标识第k条主对角线是否安放了皇后； (3) sd［2n-1］：sd［k］ 标识第k条次对角线是否安放了皇后； (4) q［n］：q［i］ 记录第i行皇后在第n列。 利用行号i和列号j计算主对角线编号k的方法是k=n+i-j-1； 计算次对角线编号k的方法是k=i+j-n。八皇后问题解法如下： void Queen(int i) { for (int j = 0; j < n; j++ ) { if (col［j］ == 0 && md［n+i-j-1］ == 0 && sd［i+j］ == 0) { //第i行第 j 列没有攻击 col［j］ = md［n+i-j-1］ = sd［i+j］ = 1; q［i］ = j;//在第 i 行第 j 列安放皇后 if (i == n)//输出一个布局 for (j = 0; j < n; j++ ) printf("%d", q［j］); printf("＼n")； } else { Queen(i+1);//在第i+1行安放皇后 col［j］ = md［n+i-j-1］ = sd［i+j］ = 0; ［i］ = 0;//撤销第 i 行第 j 列的皇后 } } 【例5.5】如果矩阵A中存在这样的一个元素A［i］［j］满足条件： A［i］［j］是第i行中值最小的元素，且又是第j列中值最大的元素，则称为该矩阵的一个马鞍点。编写一个函数计算出1×n的矩阵A的所有马鞍点。 算法思想： 依题意，先求出每行的最小值元素，放入min［m］中，再求出每列的最大值元素，放入max［n］中，若某元素既在min［m］中又在max［n］中，则该元素A［i］［j］便是马鞍点。找出所有这样的元素，即找到了所有马鞍点。因此,实现本题功能的程序如下。 #include #define m 3 #define n 4 void minmax(int a［m］［n］) { int i1,j,have=0; int min［m］,max［n］; for(i1=0; i1max［j］) max［j］=a［i1］［j］; } for(i1=0; i1tag=1; h->dd.sublist=creat_GL(s); } else { h->tag=0; h->dd.data=ch; } } else h=NULL; ch=*(*s); (*s)++; if(h!=NULL) if(ch==',') h->link=creat_GL(s); else h->link=NULL; return(h); } void prn_GL(NODE *p) { if(p!=NULL) { if(p->tag==1) { printf("("); if(p->dd.sublist==NULL) printf(" "); else prn_GL(p->dd.sublist); } else printf("%c",p->dd.data); if(p->tag==1) printf(")"); if(p->link!=NULL) { printf(","); prn_GL(p->link); } } } NODE *copy_GL(NODE *p) { NODE *q; if(p==NULL)return(NULL); q=(NODE *)malloc(sizeof(NODE)); q->tag=p->tag; if(p->tag) q->dd.sublist=copy_GL(p->dd.sublist); else q->dd.data=p->dd.data; q->link=copy_GL(p->link); return(q); } NODE *head(NODE *p)/*求表头函数 */ { return(p->dd.sublist); } NODE *tail(NODE *p)/*求表尾函数 */ { return(p->link); } int sum(NODE *p)/*求原子结点的数据域之和函数 */ { int m,n; if(p==NULL) return(0); else {if(p->tag==0) n=p->dd.data; else n=sum(p->dd.sublist); if(p->link!=NULL) m=sum(p->link); else m=0; return(n+m); } } int depth(NODE*p)/*求表的深度函数 */ { inth, maxdh; NODE *q; if(p->tag==0) return(0); else if(p->tag==1&&p->dd.sublist==NULL) return 1; else { maxdh=0; while(p!=NULL) { if(p->tag==0) h=0; else {q=p->dd.sublist; h=depth(q); } if(h>maxdh)maxdh=h; p=p->link; } return(maxdh+1); } } main() { NODE*hd, *hc; char s［100］,*p; p=gets(s); hd=creat_GL(&p); prn_GL(head(hd)); prn_GL(tail(hd)); hc=copy_GL(hd); printf("copy after:"); prn_GL(hc); printf("sum:%d＼n",sum(hd)); printf("depth:%d＼n",depth(hd)); } 本 章 小 结 （1) 了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。 （2) 掌握对特殊矩阵进行压缩存储时的下标变换公式。 （3) 了解稀疏矩阵的两类压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。 （4) 掌握广义表的结构特点及其存储表示方法，读者可根据自己的习惯熟练掌握任意一种结构的链表，学会对非空广义表进行分解的两种分析方法，即可将一个非空广义表分解为表头和表尾两部分或者分解为n个子表。 （5) 学习利用分治算法的设计思想编制递归算法。 知 识 拓 展 编程语言中的数组下标为何从0开始 在大多数编程语言中，数组的下标均从0而不是从1开始编号，刚刚学习数组的读者很容易弄错。那你有没有想过这是为什么呢？ 从存储数组的内存模型来看，“下标”的确切含义应该是“偏移”(offset)。对于数组A，如果它的每个元素占用d个存储单元，那么它的a［0］就相于首地址偏移为0的内存地址，也就是数组A的起始存储地址，一般也称为基地址。a［i］则是相对于首地址偏移i×d个存储单元的内存地址。数组下标从0开始，计算a［i］的内存地址只需要使用如下公式： LOC(a［i］)=LOC(a［0］)+i×d 但是，如果数组下标从1开始，计算a ［i］的内存地址的公式就会变为如下形式： LOC(a［i］)=LOC(a［0］)+(i-1)×d 对比上面两个公式，不难发现，如果数组下标从1开始，每次按照下标访问数组元素，就会多进行一次减法运算。数组是最常用的基础的数据结构，通过下标访问数组元素又是其基础的操作，效率的优化就要尽可能做到极致。因此，为了减少一次减法操作，数组的下标选择了从0开始编号，而不是从1开始编号。 也许这个理由还不够充分，数组的下标从0开始编号还可能与历史原因有关。最初，C语言设计者用0作为数组的起始下标，目的是在一定程度上降低C语言程序员学习其他编程语言的成本，之后的Java、JavaScript等效仿了C语言，沿用了这一方式。 当然，并不是所有编程语言中的数组下标都从0开始，如 Pascal、FORTRAN、MATLAB。甚至有些语言支持负数下标，如Python。