资源描述：
《数据结构张铭习题》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第一章概论练习答案上一章 下一章 本章练习题答案分页： [1][2]1、解答：【题意解析】 本题指定了字符的顺序，所以不能按照ASCII字符顺序来排序。【典型错误】1.不按照题目给出的字符顺序进行排序，而按照ASCII字符顺序。2.没有给出排序结果3.认为顺序存储法比较节约空间，事实上由于字符空隙，顺序法并不节约空间；4.没有比较各种方法的优劣。【数据结构】 本题可以采用的存储结构有顺序（数组）和链表。1.用二维数组array[NUMOFSTRING][MAX_LENGTH]，此题可定
2、义constintNUMOFSTRING=8,MAX_LENGTH=5;B899 B9 CRSI CXY PAB PABC 5C 7 优点:为紧凑存储结构，没有用于存储其他附加的信息，表示方法比较直观简单，代码实现十分容易。 缺点:为每个但此都开辟了同样长度的空间,造成空间的浪费。 2.用链表的结构存储，结点为结构 structstrings{ charstring[MAX_LENGTH];
3、 strings*pNext; } 优点:如果有后续工作如反复增删结点,效率很高.并且可以使用不连续的空间。 缺点:操作过程相对复杂,容易出错.而且排序过程需要从表头开始沿链索一个结点一个结点的比较搜索,相当费时。 3.索引存储 是顺序存储的一种推广.使用一个字符串chardata[500],其中将大小长度不等的数据结点(单词)顺序存储其中.令使用一个字符指针数组char*index[n],存储一系列指针,每个指针指向存储区域的一个数据结点. 排序时,直接对in
4、dex中的地址值进行调换修改即可,而不用修改data中的任何内容。索引存储的优点是:由于单词长度不同,在存储时充分考虑了这个因素,可以节省空间,此外由于交换的不是单词本身而是单词的地址,可以节省时间,从时空两方面得到了优化。【排序结果】B899，B9，CRSI，CXY，PAB，PABC，5C，7 2、解答：【题意解析】 本题没有指明这100个实数是否存在相等的情况，在这里，我们考虑存在多个最大值的情形（即100个实数可能有相等的），为了保存其位置，利用intpos[100]（因为
5、有可能这100个实数都是相同的）来保存最大值的所有位置。【典型错误】 1.用int类型的数组来保存这100个元素，没有注意题目中说的是“每个元素的值都是实数”。 2.求最大值的时候代码如下： temp=0; for(inti=0;i<100;i++) if(Num[i]>temp) temp=Num[i];评注：这样是错误的，例如：当Num[i]都是负数的时候。 3
6、.未考虑可能存在多个最大值的情况，只保存了一个最大值的位置。【数据结构】 本题可以采用的存储结构有顺序（数组），链表和索引。本题最好使用数组存储结构。由于其他存储方法需要记录附加信息，使得空间有效利用不能够最大化。因此在空间上顺序存储是最优的。时间上，无论如何此题都要遍历所有的数，因此O(n)为可能的最优时间代价。加之此题的规模较小，因此使用大家最熟悉的顺序存储是较为优先的选择。【算法描述】 1.由于最大值可能不止一个，甚至可能都是最大值，所以创建一个长度为100的整型数组pos[100]，用来
7、记录最大值的位置。 2.初始情况，取这个数组的第一个位置为最大值所在的位置，存入变量position中。 3.假设有n（1≤n≤99）个最大值，那么pos[0,1,2,…,n-1]记录这些最大值的位置，且pos[n]=-1(-1是标记值，表明pos数组下标为n-1及以前的元素记录了最大值的位置)；假设有n（n=100）个最大值，那么pos[0,1,2,…,n-1]记录这些最大值的位置，pos数组不再设-1的标记值。具体源码如下： #include voidmain()
8、{ //存放100个实数的数组 doubleNum[100]={4543.9,4543.9,3,45,654.7,7,66,35,45,4,6,4543.9,5,46,54,6,43,5.980,34}; //记录最大值所在位置的数组 intpos[100]; //初始设定数组的第1个元素为最大值 intposition=0;
