chapter10.htm

为清华大学出版社 Ｃ＋＋课后答案

  //输出数据<br>
  for(int k=0;k&lt;n;k++)<br>
  cout &lt;&lt; A[k] &lt;&lt; " ";<br>
  cout &lt;&lt; endl;<br>
  //结束输出 <br>
  <br>
  }<br>
  }</p>
<p class="style2">void main()<br>
  {<br>
  int i;<br>
  <br>
  int data1[]={1,3,5,7,9,11,13,15,17,19,2,4,6,8,10,12,14,16,18,20};<br>
  cout &lt;&lt; "排序前的数据：" &lt;&lt; endl;<br>
  for(i=0;i&lt;20;i++)<br>
  cout &lt;&lt; data1[i] &lt;&lt; " ";<br>
  cout &lt;&lt; endl;<br>
  cout &lt;&lt; "开始排序..." &lt;&lt; endl;<br>
  BubbleSort(data1, 20);<br>
  cout &lt;&lt; "排序后的数据：" &lt;&lt; endl;<br>
  for(i=0;i&lt;20;i++)<br>
  cout &lt;&lt; data1[i] &lt;&lt; " ";<br>
  cout &lt;&lt; endl;<br>
  }</p>
<p class="style2">程序运行输出：<br>
  排序前的数据：<br>
  1 3 5 7 9 11 13 15 17 19 2 4 6 8 10 12 14 16 18 20 <br>
  开始排序...<br>
  1 3 5 7 9 11 13 15 17 2 4 6 8 10 12 14 16 18 19 20 <br>
  1 3 5 7 9 11 13 15 2 4 6 8 10 12 14 16 17 18 19 20 <br>
  1 3 5 7 9 11 13 2 4 6 8 10 12 14 15 16 17 18 19 20 <br>
  1 3 5 7 9 11 2 4 6 8 10 12 13 14 15 16 17 18 19 20 <br>
  1 3 5 7 9 2 4 6 8 10 11 12 13 14 15 16 17 18 19 20 <br>
  1 3 5 7 2 4 6 8 9 10 11 12 13 14 15 16 17 18 19 20 <br>
  1 3 5 2 4 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 <br>
  1 3 2 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 <br>
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 <br>
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 <br>
  排序后的数据：<br>
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 <br>
</p>
<p class="style2"><strong>10-7 教材中的排序算法都是升序排序，稍做修改后即可完成降序排序，以起泡排序法为例，完成降序的起泡排序函数模板，初始化整型数组data1[]={1,3,5,7,9,11,13,15,17,19,2,4,6,8,10,12,14,16,18,20}，调用降序起泡排序函数模板进行排序，加入输出语句，每完成一趟起泡排序后显示整个数组，观察排序过程中数据的变化。</strong><br>
</p>
<p class="style2">解： <br>
  #include &lt;iostream.h&gt;</p>
<p class="style2">// 辅助函数：交换x和y的值<br>
  template &lt;class T&gt;<br>
  void Swap (T &amp;x, T &amp;y)<br>
  {<br>
  T temp;<br>
  <br>
  temp = x;<br>
  x = y;<br>
  y = temp;<br>
  }</p>
<p class="style2">// 用起泡法对数组A的n个元素进行排序<br>
  template &lt;class T&gt;<br>
  void BubbleSort(T A[], int n)<br>
  {<br>
  int i,j; <br>
  int lastExchangeIndex; <br>
  //用于记录每趟被交换的最后一对元素中较小的下标<br>
  i = n-1; // i是下一趟需参与排序交换的元素之最大下标<br>
  <br>
  while (i &gt; 0) <br>
  //持续排序过程，直到最后一趟排序没有交换发生，或已达n-1趟<br>
  {<br>
  lastExchangeIndex = 0; <br>
  //每一趟开始时，设置交换标志为0（未交换）<br>
  for (j = 0; j &lt; i; j++) //每一趟对元素A[0]..A[i]进行比较和交换<br>
  if (A[j+1] &gt; A[j]) //如果元素A[j+1] &lt; A[j]，交换之<br>
  { <br>
  Swap(A[j],A[j+1]);<br>
  lastExchangeIndex = j; <br>
  //记录被交换的一对元素中较小的下标<br>
  }<br>
  <br>
  // 将i设置为本趟被交换的最后一对元素中较小的下标<br>
  i = lastExchangeIndex;<br>
  //输出数据<br>
  for(int k=0;k&lt;n;k++)<br>
  cout &lt;&lt; A[k] &lt;&lt; " ";<br>
  cout &lt;&lt; endl;<br>
  //结束输出 <br>
  <br>
  }<br>
  }</p>
<p class="style2">void main()<br>
  {<br>
  int i;<br>
  <br>
  int data1[]={1,3,5,7,9,11,13,15,17,19,2,4,6,8,10,12,14,16,18,20};<br>
  cout &lt;&lt; "排序前的数据：" &lt;&lt; endl;<br>
  for(i=0;i&lt;20;i++)<br>
  cout &lt;&lt; data1[i] &lt;&lt; " ";<br>
  cout &lt;&lt; endl;<br>
  cout &lt;&lt; "开始排序..." &lt;&lt; endl;<br>
  BubbleSort(data1, 20);<br>
  cout &lt;&lt; "排序后的数据：" &lt;&lt; endl;<br>
  for(i=0;i&lt;20;i++)<br>
  cout &lt;&lt; data1[i] &lt;&lt; " ";<br>
  cout &lt;&lt; endl;<br>
  }<br>
  程序运行输出：<br>
  排序前的数据：<br>
  1 3 5 7 9 11 13 15 17 19 2 4 6 8 10 12 14 16 18 20 <br>
  开始排序...<br>
  3 5 7 9 11 13 15 17 19 2 4 6 8 10 12 14 16 18 20 1 <br>
  5 7 9 11 13 15 17 19 3 4 6 8 10 12 14 16 18 20 2 1 <br>
  7 9 11 13 15 17 19 5 4 6 8 10 12 14 16 18 20 3 2 1 <br>
  9 11 13 15 17 19 7 5 6 8 10 12 14 16 18 20 4 3 2 1 <br>
  11 13 15 17 19 9 7 6 8 10 12 14 16 18 20 5 4 3 2 1 <br>
  13 15 17 19 11 9 7 8 10 12 14 16 18 20 6 5 4 3 2 1 <br>
  15 17 19 13 11 9 8 10 12 14 16 18 20 7 6 5 4 3 2 1 <br>
  17 19 15 13 11 9 10 12 14 16 18 20 8 7 6 5 4 3 2 1 <br>
  19 17 15 13 11 10 12 14 16 18 20 9 8 7 6 5 4 3 2 1 <br>
  19 17 15 13 11 12 14 16 18 20 10 9 8 7 6 5 4 3 2 1 <br>
  19 17 15 13 12 14 16 18 20 11 10 9 8 7 6 5 4 3 2 1 <br>
  19 17 15 13 14 16 18 20 12 11 10 9 8 7 6 5 4 3 2 1 <br>
  19 17 15 14 16 18 20 13 12 11 10 9 8 7 6 5 4 3 2 1 <br>
  19 17 15 16 18 20 14 13 12 11 10 9 8 7 6 5 4 3 2 1 <br>
  19 17 16 18 20 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 <br>
  19 17 18 20 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 <br>
  19 18 20 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 <br>
  19 20 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 <br>
  20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 <br>
  排序后的数据：<br>
  20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 </p>
<p class="style2">&nbsp;</p>
<p class="style2"><strong>10-8 简单说明顺序查找的算法思想。</strong><br>
</p>
<p class="style2">解： <br>
  顺序查找是一种最简单、最基本的查找方法。<br>
  其基本思想是：从数组的首元素开始，逐个元素与待查找的关键字进行比较，直到找到相等的。若整个数组中没有与待查找关键字相等的元素，就是查找不成功。<br>
</p>
<p class="style2"><strong>10-9 初始化整型数组data1[]={1,3,5,7,9,11,13,15,17,19,2,4,6,8,10,12,14,16,18,20}，提示用户输入一个数字，调用教材中的顺序查找函数模板找出它的位置。</strong><br>
</p>
<p class="style2">解： <br>
  #include &lt;iostream.h&gt;</p>
<p class="style2">template &lt;class T&gt;<br>
  int SeqSearch(T list[], int n, T key)<br>
  {<br>
  for(int i=0;i &lt; n;i++)<br>
  if (list[i] == key)<br>
  return i; <br>
  return -1; <br>
  }</p>
<p class="style2">void main()<br>
  {<br>
  int i, n;<br>
  <br>
  int data1[]={1,3,5,7,9,11,13,15,17,19,2,4,6,8,10,12,14,16,18,20};<br>
  cout &lt;&lt; "输入想查找的数字(1~20)：";<br>
  cin &gt;&gt; n;<br>
  cout &lt;&lt; "数据为：" &lt;&lt; endl;<br>
  for(i=0;i&lt;20;i++)<br>
  cout &lt;&lt; data1[i] &lt;&lt; " ";<br>
  cout &lt;&lt; endl;<br>
  i = SeqSearch ( data1 , 20 , n );<br>
  if (i&lt;0)<br>
  cout &lt;&lt; "没有找到数字" &lt;&lt; n &lt;&lt; endl;<br>
  else<br>
  cout &lt;&lt; n &lt;&lt; "是第" &lt;&lt; i+1 &lt;&lt; "个数字" &lt;&lt; endl;<br>
  }</p>
<p class="style2">程序运行输出：<br>
  输入想查找的数字(1~20)：6<br>
  数据为：<br>
  1 3 5 7 9 11 13 15 17 19 2 4 6 8 10 12 14 16 18 20 <br>
  6是第13个数字</p>
<p class="style2">&nbsp;</p>
<p class="style2"><strong>10-10 简单说明折半查找的算法思想。</strong><br>
</p>
<p class="style2">解： <br>
  如果是在一个元素排列有序的数组中进行查找，可以采用折半查找方法。<br>
  折半查找方法的基本思想是：对于已按关键字排序的序列，经过一次比较，可将序列分割成两部分，然后只在有可能包含待查元素的一部分中继续查找，并根据试探结果继续分割，逐步缩小查找范围，直至找到或找不到为止。<br>
</p>
<p class="style2"><strong>1</strong><strong>0-11 初始化整型数组data1[]={1,3,5,7,9,11,13,15,17,19,2,4,6,8,10,12,14,16,18,20}，提示用户输入一个数字，调用教材中的折半查找函数模板找出它的位置。</strong><br>
</p>
<p class="style2">解： <br>
  #include &lt;iostream.h&gt;</p>
<p class="style2">// 用折半查找方法，在元素呈升序排列的数组list中查找值为key的元素<br>
  template &lt;class T&gt;<br>
  int BinSearch(T list[], int n, T key)<br>
  {<br>
  int mid, low, high;<br>
  T midvalue;<br>
  low=0;<br>
  high=n-1;<br>
  while (low &lt;= high) // low &lt;= high表示整个数组尚未查找完<br>
  {<br>
  mid = (low+high)/2; // 求中间元素的下标<br>
  midvalue = list[mid]; // 取出中间元素的值<br>
  if (key == midvalue) <br>
  return mid; // 若找到,返回下标<br>
  else if (key &lt; midvalue)<br>
  high = mid-1; <br>
  // 若key &lt; midvalue将查找范围缩小到数组的前一半<br>
  else<br>
  low = mid+1; // 否则将查找范围缩小到数组的后一半<br>
  }<br>
  return -1; // 没有找到返回-1<br>
  }</p>
<p class="style2">void main()<br>
  {<br>
  int i, n;<br>
  <br>
  int data1[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};<br>
  cout &lt;&lt; "输入想查找的数字(1~20)：";<br>
  cin &gt;&gt; n;<br>
  cout &lt;&lt; "数据为：" &lt;&lt; endl;<br>
  for(i=0;i&lt;20;i++)<br>
  cout &lt;&lt; data1[i] &lt;&lt; " ";<br>
  cout &lt;&lt; endl;<br>
  i = BinSearch ( data1 , 20 , n );<br>
  if (i&lt;0)<br>
  cout &lt;&lt; "没有找到数字" &lt;&lt; n &lt;&lt; endl;<br>
  else<br>
  cout &lt;&lt; n &lt;&lt; "是第" &lt;&lt; i+1 &lt;&lt; "个数字" &lt;&lt; endl;<br>
  <br>
  }</p>
<p class="style2">程序运行输出：<br>
  输入想查找的数字(1~20)：9<br>
  数据为：<br>
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 <br>
  9是第9个数字</p>
<p>&nbsp;</p>
</body>
</html>