《C编程.开始C》12.演习

变量

命名

  1. 变量名称可以以数字开头吗?
  2. 变量名称可以以印刷符号开头(例如#,*,_)吗?
  3. 给将一个C变量名的例子工作。为什么不起作用?

数据类型

  1. 在C中列出至少三种数据类型
    1. 在您的计算机上,每个需要多少内存?
    2. 哪些可以用来代替另一个?为什么?
      1. 这些用途有任何限制吗?
      2. 如果是这样,他们是什么?
      3. 是否有必要做一些特殊的事情来使用替代方案?
  2. 我们用于数据类型的名称(例如’int’,’float’)可以用作变量吗?

作业

  1. 你如何将值3.14赋值给一个名为pi的变量?
  2. 是否有可能以一个指定INT
    1. 反过来可能吗?

参考

  1. 新学生的一个常见错误是撤销作业陈述。假设您要将存储在变量“pi”中的值分配给另一个变量,例如“pi2”:
    1. 什么是正确的陈述?
    2. 相反的是什么?这是一个有效的C语句(即使它给出了错误的结果)?
    3. 如果您想将常量值(如3.1415)分配给“pi2”,该怎么办?a。正确的陈述是什么样的?b。反过来会是有效或无效的C语句吗?

简单的I / O 

字符串操作

1.编写一个程序,提示用户输入字符串,并打印其反向。

2.编写一个程序,提示用户输入一个句子,并在各自的行上打印每个单词。

循环

1.编写一个函数,输出一个高度和宽度为n的右等腰三角形,所以n = 3就像

*
**
***

2.编写一个输出高度为2n-1和宽度为n的横向三角形的函数,因此n = 4的输出为:

*
**
***
****
***
**
*

3.编写一个输出高度为n且宽度为2n-1的右侧向上三角形的函数 ; n = 6的输出将是:

     *
    ***
   *****
  *******
 *********
***********

程序流程

1.构建一个程序,其中控制从4个不同的函数传递到4个调用。

2.现在在main中使用函数调用进行while循环。在循环开始时询问输入。如果用户点击Q,则结束while循环

3.接下来添加条件以在用户输入数字时调用函数,因此1进入函数1,2进入函数2等。

4.具有函数1调用函数a,调用函数b,调用函数c

5.绘制一个程序流程图,用箭头指示控制的位置

功能

1.编写一个函数来检查整数是否为负数; 声明应该看起来像bool is_positive(int i);

2.编写一个函数将浮点数提升为整数幂,例如,当您使用它时

浮 一个 =  raise_to_power (2 , 3 );     // a得到8 
浮子 b  =  raise_to_power (9 , 2 );     // b得到81 
浮点数 raise_to_power (浮点数 f , 整数 幂);     //把它作为你的宣言

数学

1.编写一个函数来计算一个数字是否为素数。如果是素数则返回1,如果不是素数则返回0。

2.编写一个函数来确定n下面的素数个数。

3.使用牛顿方法编写一个函数来查找平方根。

4.编写函数来评估三角函数。

5.尝试编写随机数生成器。

6.编写一个函数来确定2到100之间的素数。

递归

合并排序

1.编写C程序以生成给定长度为n的随机整数数组,并使用Merge排序算法对其进行递归排序。

  • 合并排序算法是递归算法。

– 排序一个元素数组很容易。

– 排序两个单元素数组,需要合并操作。合并操作将两个排序的数组作为列表进行查看,并比较列表的头部,并且哪个头部较小,此元素放在已排序的列表上,并且该列表的头部被勾选,因此下一个元素将成为该名单的负责人。这样做直到其中一个列表用尽,然后另一个列表被复制到排序列表的末尾。

– 发生递归,因为合并两个单元素数组会产生一个两元素排序数组,它可以与另一个以同一方式生成的两元素排序数组合并。这将生成一个已排序的4个元素数组,这同样适用于另一个4元素排序数组。

– 所以基本的合并排序是检查要排序的列表的大小,如果它大于1,则将数组分成两部分,并在两半上再次调用merge sort。在病房之后,将两半合并在相同大小的临时空间中,然后将最终排序的数组复制回原始数组。

二进制堆

2. 二进制堆  :

  • 二进制最大堆或最小堆是一种有序结构,其中一些节点保证比其他节点更大,例如父节点对两个节点。二进制堆可以存储在一个数组中,其中,

– 给定位置i(父母),i * 2是左孩子,i * 2 + 1是正确的孩子。

– (C数组从位置0开始,但0 * 2 = 0,0 * 2 + 1 = 1,这是不正确的,所以在位置1开始堆,或者为父子计算加1,并减去1用于子到父计算)。

  • 尝试用铅笔和纸模型,使用10个随机未分类的数字,并将它们插入10个元素的“heapsort”数组。
  • 要插入到堆中, 最后添加交换父级(如果更高),直到父级更高。
  • 要删除堆的顶部,请移动 端到端,并 推迟更高的子项筛选,直到没有子项更高。
  • 用笔在纸上试试数字10,4,6,3,5,11。
  • 答案是11,5,10,3,4,6。
  • 练习:现在尝试删除11,5,10,3,4,6中的每个顶部元素,使用end-to-top和sift-down(或swap-higher-child)来获取数字

按降序排列。

  • 优先级队列允许以优先级插入元素,并根据优先级提取。(如果元素具有配对结构,一个部分是键,另一部分是数据,这可能会有用。否则,它只是一种排序机制)。
  • 练习:使用insert-back / challenge-parent和delete-front / last-to-front / defer-higher-child的上述技术,实现堆排序或优先级队列。

Dijsktra的算法

Dijsktra的算法是使用优先级队列的搜索算法。它首先插入优先级为0的起始节点。插入所有其他节点的优先级值为大N.每个节点都有一个其他节点的邻接列表,到起始节点的当前距离,以及前一个指向上一个节点的指针计算当前节点。邻接列表的替代是邻接矩阵,它需要nxn布尔邻接。

该算法基本上遍历优先级队列,移除前节点,检查相邻节点,并以等于每个相邻节点的前节点距离之和的距离进行更新,以及相邻节点的邻接信息给出的距离。 。

在每个节点更新后,在该节点上使用额外操作“更新优先级”

节点的距离小于其父节点时(对于此优先级队列,父节点的距离小于子节点),节点与父节点交换。

在此之后,节点的距离大于其一个或多个子节点时,它与最远的子节点交换,因此最远的子节点成为其较远的兄弟节点的父节点,并且父节点变为较远的当前节点。

通过更新优先级,到当前节点的相邻节点具有改变到当前节点的后向指针。

当目标节点成为当前节点被移除时,算法结束,并且可以通过跟随后向指针将开始节点的路径记录在数组中,然后执行类似快速排序分区的操作以反转数组的顺序,从起始节点到目标节点的最短路径。

快速排序

3.编写C程序以使用快速排序分区交换算法进行递归排序。

  • 您可以使用Q1中的“驱动程序”或随机数测试数据。在mergesort上。这是“重复使用”,这是一般鼓励的。

– 重用的优点是减少了写入时间,调试时间,测试时间。

  • 分区交换的概念是(随机)选择分区元素,并且需要排序的每个东西都被置于3个等价物中

classes:小于分区值的那些元素,分区元素以及分区元素之上(和等于)的所有内容。

  • 这可以在不分配比一个临时元素空间更多空间的情况下完成,以交换两个元素。例如,整数数据的临时整数。
  • 但是,分区元素应该使用原始数组空间的位置是未知的。
  • 这通常是通过将分区放在要排序的数组的末尾,然后放入两个指针(一个在数组的开头,

并且在分区元素旁边的元素处有一个,并且向左重复扫描左指针,向左扫描右指针。

  • 当找到等于或大于分区的元素时,左扫描停止,而对于比分区值小的元素,右扫描停止,

这些是交换的,它使用临时的额外空间。

  • 如果左扫描到达分区元素,它将始终停止,分区元素是最后一个元素; 这意味着整个数组小于分区值。
  • 如果整个阵列大于分区,则右扫描可以到达第一个元素,这需要进行测试,否则扫描不会停止。
  • 当左右指针交叉时,外环退出。测试指针交叉和外环退出

应该在交换之前发生,否则右指针可能正在交换先前由左指针扫描的小于分区的元素。

  • 最后,一旦指针交叉,就需要将分区元素放在左右分区之间。
  • 在指针交叉处,左指针可能停在分区元素在数组中的最后位置,并且右指针没有经过指针

元素就在最后一个元素之前。当所有元素都小于分区时会发生这种情况。

– 如果选择右指针与分区交换,则会产生错误状态,其中左数组的最后一个元素变得小于分区元素值。

– 如果选择左指针与分区交换,则左数组将小于分区,并且分区将与值大于分区或分区本身的元素交换。

  • 必须检查快速分配2元素无序数组的角落情况。

– 左指针停在第一个乱序元素上。右指针从第一个无序元素开始,但外部循环退出,因为这是最左边的元素。然后使用左指针的第一个元素交换分区元素,现在这两个元素按顺序排列

– 对于order数组中的2个元素,最左边的指针会跳过小于分区的第一个元素,并在分区上停止。右指针从第一个元素开始并退出,因为它是第一个位置。指针已交叉,因此外环退出。分区与自身交换,因此保留了按顺序。

  • 执行交换后,左指针应递增,右指针递减,因此不会再次扫描相同的位置,因为可能会导致无限循环(可能是当元素等于或大于分区时左指针退出,右边的元素等于分区值)。一个实现,Sedgewick,用左指针减去一个和右指针启动指针

加一个预定的初始扫描位置,并使用预增量和预减量运算符,例如(++ i, – i)。

猜你想读:《C编程.中级C》1.高级数据类型

THE END
分享