数据结构第五章习题课.doc

特殊矩阵和稀疏矩阵哪一种压缩存储后会失去随机存取的功能?为什么?答：后者在采用压缩存储后将会失去随机存储的功能。因为在这种矩阵中，非零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所在的行、列号一个结点存放在一起，这样的结点组成的线性表中叫三元组表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。 ）16、设对称矩阵A= （1）若将A中包括主对角线的下三角元素按列的顺序压缩到数组S中, 即S: 1 0 0 2 3 0 0 0 5 0 下标： 1 2 3 4 5 6 7 8 9 10 试求出A中任一元素的行列下标[i,j](1=i,j=4)与S中元素的下标K之间的关系. （2）若将A视为稀疏矩阵时,画出其三元组表形式压缩存储表。 答：（1）k=(2n-j+2)(j-1)/2+i-j+1 （当i≥j时，本题n=4） k=(2n-i+2)(i-1)/2+j-i+1 （当ij时，本题n=4） （2）稀疏矩阵的三元组表为： s=((4,4,6),(1,1,1),(1,4,2),(2,2,3),(3,4,5),(4,1,2),(4,3,5))。其中第一个三元组是稀疏矩阵行数、列数和非零元素个数。其它三元组均为非零元素行值、列值和元素值。 17、设任意n个整数存放于数组A(1:n)中，试编写程序，将所有正数排在所有负数前面（要求算法复杂性为0( n)）。 类似本题的另外叙述有： （1）已知数组A[1..n]的元素类型为整型，设计算法调整A，使其左边的所有元素小于零，右边的所有元素大于等于零。（要求算法的时间复杂度和空间复杂度均为0（n）） （2）设计一个算法，把整数数组中所有的偶数放到所有的奇数之前。要求时间、空间效率尽可能高。 （3）设一系列正整数存放在一个数组中，试设计算法，将所有奇数存放在数组的前半部分，将所有的偶数存放在数组的后半部分。要求尽可能少用临时存储单元并使时间最少。请试着分析你实现的算法的时间复杂度和空间复杂度。　 （4）设计算法将数组A[1..n]调整为左右两部分，使的左边所有的元素小于右边的所有元素，并给出这一划分的分界位置。要求算法的时间复度为O(n)。 答：[题目分析]本题属于排序问题，只是排出正负，不排出大小。可在数组首尾设两个指针i和j，i自小至大有哪些信誉好的足球投注网站到负数停止，j自大至小有哪些信誉好的足球投注网站到正数停止。然后i和j所指数据交换，继续以上过程，直到 i=j为止。 void Arrange(int A[],int n) //n个整数存于数组A中，本算法将数组中所有正数排在所有负数的前面 {int i=0,j=n-1,x; //用类C编写，数组下标从0开始 while(ij) {while(ij A[i]0) i++; while(ij A[j]0) j--; if(ij) {x=A[i]; A[i++]=A[j]; A[j--]=x; }//交换A[i] 与A[j] } }//算法Arrange结束. [算法讨论]对数组中元素各比较一次，比较次数为n。最佳情况(已排好,正数在前,负数在后)不发生交换，最差情况(负数均在正数前面)发生n/2次交换。用类c编写，数组界偶是0..n-1。空间复杂度为O(1). 类似本题的其它题的解答:： （1）与上题同，因要求空间复杂度也是O(n)，可另设一数组C，对A数组从左到右扫描，小于零的数在C中从左（低下标）到右（高下标）存，大于等于零的数在C中从右到左存。 （2）将19题中判定正数(A[i]0)改为判偶数(A[i]%2==0)，将判负数(A[j]0)改为(A[j]%2!=0)。 （3）同（2），只是要求奇数排在偶数之前。 （4）利用快速排序思想，进行一趟划分。 int Partition(int A[],int n) //将n个元素的数组A调整为左右两部分，且左边所有元素小于右边所有元素，返回分界位置。 {int i=0,j=n-1,rp=A[0]; //设数组元素为整型 while(ij) {while(ij A[j]=rp) j--; while(ij A[i]=rp) i++; if(ij) { x=A[i];A[i]=A[j]; A[j]=x; } } A[i]=rp; return(i); //分界元素 }// Partition 18、在数组 A[1..n]中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个。 答：[题目分析]本题要求建立有序的循环链表。从头到尾扫描数组A，取出A[i]（0=in）,然后到链表中去查找值为A[i]的结