第二章补充.doc

习题1. 说明数组和链表的区别，各有何优缺点？1） 区别：数组占用连续的内存空间，链表不要求结点的空间连续。2） 各自的优缺点： 插入与删除操作：由于数组在插入与删除数据时需移动大量的数据元素，而链表只需要改变一些指针的链接，因此，链表比数组易于实现数据的插入和删除操作。 内存空间的占用情况：因链表多了一个指针域，故较浪费空间，因此，在空间占用方面，数组优于链表。 数据的存取操作：访问链表中的结点必须从表头开始，是顺序的存取方式，而数组元素的访问是通过数组下标来实现的，是随机存取方式，因此，在数据存取方面，数组优于链表。 数据的合并与分离：链表优于数组，因为只需要改变指针的指向。习题2. 已知长度为n的线性表A采用顺序存储结构，请写一算法，删除该线性表中所有值为item的数据元素。【解题思路】思路一：从线性表的第一个数据元素开始到最后那个数据元素，依次判断线性表中的数据元素是否满足删除条件。若某个数据元素满足条件，则从线性表中删除该数据元素，然后修改线性表的长度。算法一：算法的ADL描述：算法 DEL 1( A , n ，item )i 1 .WHILE (i n) DOIF ( Ai = item ) THEN(FOR j = i + 1 TO n DOAj-1 Aj .n n 1 .)ELSEi i + 1 . 说明：对于数据元素Ai，如果满足条件，将其从线性表中删除。由于从第i+1个位置移到第i个位置的元素也可能满足条件，因此，此时的i值不能增加1，还需要原地等待以判断从后面移来的那个元素是否也满足删除条件（如果也满足删除条件，接着删除该元素），只有当Ai不满足删除条件时，i才向后移一个位置。思路二：容易看出，算法一的时间复杂性为O(n2) 。下面我们对算法一进行改进，使时间复杂性为O(n)。思路如下：当判断某个数据元素Ai并得知其满足删除条件时，先不马上对其作删除操作，只记录这样的数据元素的个数m，只是在当某个数据元素不是要删除的数据元素时，这时将该数据元素移到线性表的第i-m个位置。算法一的思路虽然简单、朴实，可读性好，但时间复杂度较高。而算法二虽然在理解上较算法一稍微复杂一点，但算法的时间效率大大提高了。算法二：算法的ADL描述：算法 DEL 2( A , n ，item )m 0 .FOR i = 1 TO n DOIF ( Ai = item ) THENm m +1 .ELSEAi-m Ai . n n - m . 习题3. 已知非空线性链表第一个结点由list指出，请写一算法，交换p所指结点与其下一个结点在链表中的位置（设p指向的不是链表最后的那个结点）。【解题思路】整个算法应分成两个部分：（1）确定p的位置，同时给出p的前驱*p ；（2）将结点*p与p的后继结点交换。算法的ADL描述：算法CHANGE（list, p）q list .WHILE (next (q) p) DOq next (q) .IF (next (p) NULL)(r next (p) .next (q) r .next (p) next (r) .next (r) p .) . 习题4. 向LinkedList类中增加一个函数Contrary，功能为将其所有结点按相反次序链接。【解题思路】对这个问题而言，可以有多种解决办法。比如下面的两种方法。第一种方法：由于没有对空间限制，因此可利用堆栈作为中间数据结构来颠倒数据；第二种方法：将原链表中的头指针和头结点断开，构成一个新的空表（即令头指针head指向空），然后将原链表中各结点，从第一个结点起，依次插入这个新表的头部（即表头插入）。第二种方法的ADL描述：算法 Con