C语言算法

C语言算法（共12篇）

C语言算法 篇1

0 引言

在数据处理中, 数据排序是相当重要的, 它可以使数据更有条理, 方便数据的处理。排序是程序设计的常见问题, 解决排序问题也有多种算法, 常用的算法有顺序比较排序法、选择排序法、冒泡排序法、直接插入排序法、快速排序和希尔排序法等排序算法。在学习C语言程序设计过程中排序算法也是重点研究问题之一, 本文主要用C语言来描述几种常见的排序算法, 以及分析实现算法的基本思路、模拟相应算法实现排序的过程及算法性能分析。文中所涉及的排序均为升序排序。

1 顺序比较排序法

1.1 算法思想

假设数组有n个元素, 从第一个元素开始为第一趟, 第一个元素和第二个元素开始到第n个元素按顺序作比较, 如果第一个元素大于某个元素则第一个元素和该元素进行交换, 第一个元素和其后的n-1个元素一一进行两两比较结束后将是所有元素中的最小值。接下来第二趟从第二个元素开始逐一和其后的n-2个元素两两比较, 在进行n-2次比较后第二个元素将是剩下n-1个元素中的最小值。依次类推一直到第n-1趟最后两个元素进行比较并得到第n-1个元素是剩下的两个元素中的较小值。

1.2 模拟排序执行过程

假设一个整型数组有5个元素, 分别为23、12、5、16、10, 排序执行过程如下所示:

第一趟: 23 12 5 16 10 (第一趟比较前元素)

第一次: 12 23 5 16 10 (由于23>12 两元素交换)

第二次: 5 23 12 16 10 (由于12>5 两元素交换)

第三次: 5 23 12 16 10 (由于5<16 两元素不交换)

第四次: 5 23 12 16 10 (由于5<10 两元素不交换)

第二趟: 5 23 12 16 10 (第二趟比较前元素)

第一次: 5 12 23 16 10 (由于23>12 两元素交换)

第二次: 5 12 23 16 10 (由于12<16 两元素不交换)

第三次: 5 10 23 16 12 (由于12>10 两元素交换)

第三趟: 5 10 23 16 12 (第三趟比较前元素)

第一次: 5 10 16 23 12 (由于23>16 两元素交换)

第二次: 5 10 12 23 16 (由于16>12 两元素交换)

第四趟: 5 10 12 23 16 (第四趟比较前元素)

第一次: 5 10 12 16 23 (由于23>16 两元素交换)

1.3 实现顺序比较排序法核心代码

1.4 算法性能分析

有n个元素参加排序要进行n-1趟比较, 第i趟要进行n-i次两两比较。时间复杂度为O (n2) 。顺序比较排序算法稳定, 比较次数已知, 但是该算法速度慢。

2 冒泡排序法

2.1 算法思想

假设数组有n个元素, 第一趟从第一个元素开始依次比较两个相邻元素的值, 如果前一个元素的值大于后一个元素的值则两个相邻元素进行交换, 第一趟比较n-1次, 经过一趟排序n个元素中的最大值存放到最后一个数组元素中。第二趟从第一个元素开始到第n-1个元素相邻两个元素作比较, 如果前一个数大于后一个数则两个相邻的元素进行交换, 经过n-2次比较, 这一趟中最大值放在第n-1个数组元素的位置。依次类推一直到第n-1趟第一个元素和第二个元素两个元素进行比较, 两个元素中的较大值放在第二个数组元素的位置, 较小值放在第一个数组元素的位置。

2.2 模拟排序执行过程

假设一个整型数组有5个元素, 分别为23、12、5、16、10, 用变量k保存最小值的下标, 排序执行过程如下所示:

第一趟: 23 12 5 16 10 (第一趟比较前元素)

第一次: 12 23 5 16 10 (由于23>12 两元素交换位置)

第二次: 12 5 23 16 10 (由于23>5 两元素交换位置)

第三次: 12 5 16 23 10 (由于23>16 两元素交换位置)

第四次: 12 5 16 10 23 (由于23>10 两元素交换位置)

第二趟: 12 5 16 10 23 (第二趟比较前元素)

第一次: 5 12 16 10 23 (由于12>5 两元素交换位置)

第二次: 5 12 16 10 23 (由于12<16 两元素不交换位置)

第三次: 5 12 10 16 23 (由于16>10 两元素交换位置)

第三趟: 5 12 10 16 23 (第三趟比较前元素)

第一次: 5 12 10 16 23 (由于5<12 两元素不交换位置)

第二次: 5 10 12 16 23 (由于12>10 两元素交换位置)

第四趟: 5 10 12 16 23 (第四趟比较前元素)

第一次: 5 10 12 16 23 (由于5<10 两元素不交换位置)

2.3 实现冒泡排序法核心代码

2.4 算法性能分析

有n个元素参加排序要进行n-1趟比较, 第i趟要进行n-i次两两比较。时间复杂度为O (n2) 。冒泡排序算法稳定, 比较次数已知, 但是该算法速度慢, 每次只能比较和移动相邻两个数据元素, 移动数据元素的次数多。

3 改进的冒泡排序法

3.1 算法思想

冒泡排序法存在的不足之处是在排序过程中, 虽然数据序列已经按要求排序完成, 但程序无法判断是否完成排序, 程序仍然要进行下一趟的排序, 这样势必浪费了程序执行的时间, 降低了程序的执行效率。为了解决这一不足, 在程序中可以设置一个标志变量flag, 每一趟排序开始前设置flag值为1, 表示待排序的数据序列是无序的。如果在程序的执行过程中发生数据交换操作, 则修改flag值为0。当前趟排序结束后检查flag标志, 若flag的值为1, 表示在当前趟排序过程中没有进行过交换数据, 则结束排序过程, 否则继续进行下一趟排序。

3.2 实现改进冒泡排序法核心代码

3.3 算法性能分析

若数据序列的初始状态为“正序”, 则冒泡排序过程只需进行一趟排序, 在排序过程中只需进行n-1次比较, 且不移动数据元素。若数据序列的初始状态为“逆序”, 则需进行n (n-1) /2次比较和数据元素交换, 而完成两个数据元素交换需移动操作3次, 故移动次数达到最大3n (n-1) /2。改进的冒泡排序算法的时间复杂度为O (n2) , 改进的冒泡排序算法是稳定的排序算法。

4 选择排序法

4.1 算法思想

假设数组有n个元素, 第一趟从第一个元素开始, 第一个元素和第二个元素开始到第n个元素按顺序作比较, 按排序要求找到最小元素的位置, 然后用该位置和第一个元素的下标进行比较, 如果不相等则两元素进行交换, 这样第一个元素将是n个元素中的最小值。接下来第二趟从第二个元素开始逐一和其后的n-2个元素两两比较, 在进行n-2次比较后找到剩下n-1个元素中的最小值的位置, 然后用该位置和第一个元素的下标进行比较, 如果不相等则两元素进行交换, 第二个元素将是后n-1个元素中的最小值。依次类推一直到第n-1趟最后两个元素进行比较并得到两个元素中的较小值的位置。

4.2 模拟排序执行过程

假设一个整型数组有5个元素, 分别为23、12、5、16、10, 用变量k保存最小值的下标, 排序执行过程如下所示:

第一趟: 23 12 5 16 10 (第一趟比较前元素)

第一次: k=1 (由于23>12)

第二次: k=2 (由于 12>5)

第三次: k=2 (由于 5<16)

第四次: k=2 (由于 5<10)

第一趟比较后, 由于0!=2, 则a[0]与a[2]交换。

第二趟: 5 12 23 16 10 (第二趟比较前元素)

第一次: k=1 (由于 12<23)

第二次: k=1 (由于 12<16)

第三次: k=4 (由于 12>10)

第二趟比较后, 由于1!=4, 则a[1]与a[4]交换。

第三趟: 5 10 23 16 12

第一次: k=3 (由于 23>16)

第二次: k=4 (由于 16>12)

第三趟比较后, 由于2!=4, 则a[2]与a[4]交换。

第四趟: 5 10 12 16 23

第一次: k=4 (由于 16>23)

第四趟比较后, 由于3!=4, 则a[3]与a[4]交换。

5 10 12 16 23

4.3 实现选择排序法核心代码

4.4 算法性能分析

有n个元素参加排序要进行n-1趟比较, 第i趟要进行n-i次两两比较, 每趟最多进行一次数据交换, 其余元素的相对位置不变。时间复杂度为O (n2) 。选择排序算法稳定, 比较次数与冒泡排序一样, 数据移动次数比冒泡排序少, 算法速度还是慢。

5 直接插入排序法

5.1 算法思想

将序列分为有序序列和无序序列, 依次从无序序列中取出元素值插入到有序序列的合适位置。初始是有序序列中只有第一个数, 其余n-1个数组成无序序列, 则n个数需进行n-1次插入。初始是有序序列中只有第一个数, 其余n-1个数组成无序序列, 则n个数需进进n-1次插入。寻找在有序序列中插入位置可以从有序序列的最后一个数往前找, 在未找到插入点之前可以同时向后移动元素, 为插入元素准备空间。

假设数组有n个元素, 第一趟首先对前两个元素进行比较, 按排序要求排列好, 第二趟将第3个元素与前两个已排好序的元素做比较, 按排序要求找到其相应的位置, 将第3个元素插入到该位置上。以此类推, 直到所有的元素排好序为止。

5.2 模拟排序执行过程

待排序列: 23 12 5 16 10

第一趟: 12 23 5 16 10 (23插入12之后, 23后移)

第二趟: 5 12 23 16 10 (5插入12之前, 12、23依次后移)

第三趟: 5 12 16 23 10 (16插入23之前, 23后移)

第四趟:5 10 12 16 23 (10插入12之前, 12、16、23依次后移)

5.3实现直接插入排序法核心代码

5.4算法性能分析

有n个元素参加排序要进行n-1趟比较。时间复杂度为O (n2) 。直接插入排序算法稳定, 执行速度快, 但是该算法的数据比较次数不确定, 比较次数越多, 插入点后的数据移动次数越多, 特别是当数据总量庞大的时候。

6结语

通过对顺序比较法、选择排序法、冒泡排序法、改进的冒泡排序法和直接插入排序法的介绍, 并从排序算法的思想、模拟排序执行过程、实现排序的算法代码及算法性能分析四个方面进行了详细的解析。本文可以帮助C语言初学者轻松理解几种常用的排序算法。

摘要：排序是计算机科学中最重要的研究问题之一, 也是学习C语言程序设计过程中重点研究问题之一。主要介绍了顺序比较法、选择排序法、冒泡排序法、改进的冒泡排序法和直接插入排序法, 并从排序算法的思想、模拟排序执行过程、实现排序的算法代码及算法性能分析4个方面进行了详细的解析, 可以帮助C语言初学者轻松理解几种常用的排序算法。

关键词：C语言,排序,算法思想,数组

参考文献

[1]谭浩强.C语言程序设计[M].第3版.北京:清华大学出版社, 2005.

[2]范兴福.C程序设计[M].北京:机械工业出版社, 2008.

[3]严蔚敏, 吴伟民.数据结构:C语言版[M].北京:清华大学出版社, 1997.

C语言算法 篇2

1.扫描整个棋盘，分别扫描四个方向是否有5个连子，网上找了很多五子棋源码都是用此算法，这意味着每下一个棋子都要扫描一遍19×19的棋盘，复杂而且低效，代码略。

2.每下一字，从该子开始扫描其四个方向(例如：从该子的(x-4，y)坐标开始扫描横向)是否存在5个连子。此算法较为常用，而且不涉及更为复杂的数据结构。

另外，为解决扫描越界的问题，在声明棋盘棋子位置时，可声明一个(4+19+4)×(4+19+4)的棋盘，而让棋子偏移(4，4)个坐标。

算法2源代码如下：

static void IfWin(int x,int y,int color)

{

TCHAR win[20];

int a,b;

if(stone[x][y]==1)

wcscpy_s(win,_T(“黑棋胜利!”));

else

wcscpy_s(win,_T(“白棋胜利!”));

for(a=x-4;a<=x+4;a++)//判断横

if(stone[a][y]==color&&stone[a+1][y]==color&&stone[a+2][y]==color&&stone[a+3][y]==color&&stone[a+4][y]==color)

{MessageBoxW(Xqwl.hWnd,win,TEXT(“”),MB_OK);return;}

for(b=y-4;b<=y+4;b++)//判断竖

if(stone[x][b]==color&&stone[x][b+1]==color&&stone[x][b+2]==color&&stone[x][b+3]==color&&stone[x][b+4]==color)

{MessageBoxW(Xqwl.hWnd,win,TEXT(“”),MB_OK);return;}

for(a=x-4,b=y-4;a<=x+4;a++,b++)//判断右斜

if(stone[a][b]==color&&stone[a+1][b+1]==color&&stone[a+2][b+2]==color&&stone[a+3][b+3]==color&&stone[a+4][b+4]==color)

{MessageBoxW(Xqwl.hWnd,win,TEXT(“”),MB_OK);return;}

for(a=x-4,b=y+4;a<=x+4;a++,b--)//判断左斜

if(stone[a][b]==color&&stone[a+1][b-1]==color&&stone[a+2][b-2]==color&&stone[a+3][b-3]==color&&stone[a+4][b-4]==color)

{MessageBoxW(Xqwl.hWnd,win,TEXT(“”),MB_OK);return;}

}

平衡排序二叉树的C＋＋算法实现 篇3

关键词：平衡排序二叉树；类模板；插入；删除；平衡化

中图分类号：TP311文献标识码：A文章编号：1009-3044(2007)16-31043-02

Sort Balanced Binary Tree in C++ Algorithms

DING Min-dou

(Nanjing Railway Vocational Technical College,Nanjing 210016,China)

Abstract:The article discussed a balanced binary tree sorting algorithm, focused on solving balanced binary tree in order to insert, delete nodes when the balance problem, as teaching exercises also use practical value.

Key words:Sort balanced binary tree;Template;Insert;Delete;Balancing

1 引言

平衡排序二叉树是数据结构中的重要知识点，在实际应用中多用于在内存中组织数据，因它在动态查找表中的查找效率非常高，所以得到广泛应用。它的优缺点在各种数据结构资料书中都有详细描述，这里不再细述。但大多资料书中并没有给出具体的算法实现，而具体算法的实现演练对我们提高编程技巧、更好的掌握平衡排序树是有很大帮助的。这里给出本人自编的一种实现算法，请编程爱好者指正。

平衡排序树算法重点是在树中插入、删除结点时要保持二叉树的平衡，也就是树中任一结点的左右子树的高度相差不超过1。平衡一个二叉树有两个基本方法：左旋和右旋，在不同的时候选择不同的旋转方法或将它们组合起来同时使用。

2 平衡排序二叉树类的数据成员介绍

平衡排序二叉树类中有三个私有成员：分别表示树的高度、结点个数、根结点；一个公用内部类：定义了树结点数据成员及结点有关操作。树结点类中有一数据成员存储该结点的平衡因子，用于表示结点的左右子树高度之差，它的取值只有三个（－1，0，1），当在树中插入、删除结点时造成其它结点的平衡因子的值超出范围时，就需要进行平衡化操作；树结点类中还有结点关键字成员、结点数据成员、左右指针成员。为了适应各种结点数据，所以需采用类模板定义平衡排序二叉树类。

3 插入结点

在二叉树中插入结点时（生成树时也同于插入结点）会造成二叉树的不平衡，也就是有结点的左右子树的高度之差大于1，这时就需要进行树的平衡化操作。

插入结点时使用排序二叉树的递归插入算法先找到插入位置，将待插结点插入后回溯。在回溯时修改其它相关结点的平衡因子，左插的回溯后的结点平衡因子减1，右插的回溯后的结点平衡因子加1，然后再回溯，此时要分二种情况（以左插为例，右插算法思想相同）：

3.1回溯后的结点的平衡因子原为0、1时

此时左插入操作不破坏此结点的平衡，直接将此结点的平衡因子减1。如果此结点的左孩子的平衡因子为0时，则也不破坏整个树的平衡，直接回溯无需平衡化树。如果此结点的左孩子的平衡因子不等于0时，则有可能破坏树的平衡，再次回溯时需再次判断，直到符合上述条件或进行过平衡化操作后才能直接回溯。

3.2回溯后的结点的平衡因子原为－1时

此时左插入操作将破坏此结点及树的平衡，需进行平衡化操作。根据此结点的左孩子的平衡因子进行不同的平衡化操作。

3.2.1左孩子的平衡因子为－1、0时

即出现下两个图的情况时要进行右旋平衡化操作，平衡化操作后的结果如下图，同时调整相应结点的平衡因子，操作结束后树将恢复到平衡状态。

图1

图2

3.2.2左孩子的平衡因子为1时

即出现下两个图的情况时，要先进行左旋再进行右旋或先进行右旋再左旋最后右旋平衡化操作，平衡化操作后的结果如下图，同时调整相应结点的平衡因子，操作结束后树将恢复到平衡状态。

图3

图4

经过上述两种情况的平衡化操作后，树将恢复平衡，至此插入结点算法完成。

4 删除结点

在树中删除结点同样也可能会造成树的不平衡，需做相应的平衡化操作。删除结点也采用递归算法，先找到要删结点（如果存在），分三种情况实现删除结点算法（以左删为例，右删算法思想相同）：

4.1删除叶子结点

删除叶子结点较简单，当找到要删结点后回溯到它的父结点再删除结点，删除完毕后需考察当前结点的平衡因子做相应操作：

4.1.1平衡因子原为0时

此时删除结点不会破坏树的平衡，将平衡因子加1后直接回溯无需平衡化树。

4.1.2平衡因子原为-1时

此时删除结点不会破坏当前结点的平衡，但有可能破坏树的平衡。所以在将当前结点平衡因子加1后回溯，再进行判断树是否平衡，如果不平衡继续调整树。

4.1.3原平衡因子为1时

此时已破坏当前结点的平衡，所以要进行右树平衡化操作，具体如何平衡同插入结点右树平衡，不再详述。平衡化操作结束后看当前结点平衡因子，如果不为0则整个树也是平衡的，直接回溯无需再判断、调整树的平衡；如果为0则虽然当前结点已平衡，但有可能整个树还是非平衡的，需在回溯后再次判断、调整，直到树平衡为止。

4.2删除有一个孩子的结点（以有左孩子为例，有右孩子的算法思想相同）

当删除的结点有一个左孩子时，则在找到此结点时进行删除操作，同时将其左孩子上提到当前结点位置，完毕后再回溯。回溯后的结点的平衡因子及树的平衡化操作就和删除叶子结点相同了，这里不再重复细述了。

4.3删除中间结点（即此结点既有左孩子也有右孩子）

当删除的结点是中间结点时，相对比较复杂，这里采用如下算法思想：将删除中间结点转化成前两种情况来处理。具体算法是：

①先递归找到删除结点，用一引用保存待删结点内容；

②再找到跟待删结点关键字最接近的小关键字结点并保存，此结点要不是一叶子结点，要不就是有一个孩子的结点。找此结点的方法是先找其左孩子结点，再循环找其左孩子结点的右孩子结点，直到无右孩子结点为止；

③删除此小关键字结点，同时修改有关结点的平衡因子，有需要时调整使树保持平衡；

④将删除掉的小关键字结点的内容复制到原需删除的结点位置，完成删除操作。

5 结束语

至此插入、删除结点的算法大致介绍完毕，整个算法实现比较清楚，特别是在删除结点部分采用了较简单巧妙的算法过程，但这也带来了时间复杂度的增加，可以再考虑加于改进。其它一些功能相对简单的多，不再细述，详见代码注释。

类实现代码见附件。本程序在Winxp、VC++6.0下编译通过。

智能C语言操作题评分算法研究 篇4

随着人工智能技术的不断发展, 基于人工智能的解决方案被应用到各个领域中。其中教学领域也在引入该技术不断改进教学手段, 如计算机辅助教学等。为了提高考试工作效率节约开支和避免教师为学生划定考试范围来应付考试, 利用基于题库的考试软件进行考试成为首选。考试系统可以很好地完成选择判断等客观题的考试评卷工作, 但在评阅主观试题时效率就显得比较低下。一是主观题往往答案不唯一, 利用简单字符匹配很难公平给出成绩。二是当有多个答案时难以逐一列举, 同样造成评判不公。

二、C程序设计操作题考试系统总体设计

该系统用户分为两类, 分别是学生用户和教师用户。教师用户具有出题评分等权限, 学生用户抽题和答题权限。本系统分为出题模块、评分模块、成绩处理和答题模块。当用户登录时可以利用数据库用户表的权限字段加以区分用户角色, 然后分配给不同权限。用户如果是教师则在主界面显示出题评分等操作, 如果是学生用户则显示试题抽取操作, 学生抽取试题后进入答题界面。学生答题结束则提交操作后的C源文件。具体层次图如图1所示。

三、阅卷算法的实现

在该系统中除阅卷模块外, 其他模块的功能在实现方法上有比较成形的技术都能够比较容易达到设计目标。但对于评卷模块来说, 它要完成的是主观操作题的评阅因此实现起来有一定的难度。经过多次的实验和资料查阅, 最后选用了人工智能技术来实现。

(一) 基本设计思想。

本系统中主要包含三类操作题分别是程序改错, 程序填空和函数编写。每类题的答题点都有可能出现多种答案。可以将每个答题点的答案存放到答案表中, 答案表也可以被称为阅卷知识库。

对于改错和程序填空题在知识库中每个答题点都可以有多个可选答案相对应, 并且不同的答案具有不同的得分权重, 由此每个答题点Point有多个带有不同权重w的答案Ans构成:

每个答题点的成绩最终为某个Ans的权重w成绩该答题点的分值得出, 因此权重w取值为[0, 1]。

对于函数编写题则在答案知识库中与改错和程序填空有一定差别, 在该知识库中将答案视为一个文本T, T应该由多个关键词Key构成。每个关键词Key组合成T, 每个关键词Key在答案文本中有一定的得分比例Percent。由此每个题的答案可以为:

该式中得分比例累积为1, 该题得分为最终得分比累加和乘以该题分值。

(二) 基本数据表设计。

对应上述设计思想, 设计如下两个表作为阅卷知识库。

对于改错程序和程序填空题阅卷知识库表结构设计如表1:

对于函数编写题阅卷知识库表结构如表2:

(三) 算法实现。

当学生完成答题后, 将答题结果提交到学生答题答案表。表中包含学生学号、姓名、试题套号、程序改错答题结果、填空题答题结果和函数编写答题结果。算法按照改错题评阅、填空题评阅和函数编写题评阅顺序进行。

1.改错题与填空题评阅算法。首先提取答案表中的一条记录, 然后提取该记录中的试题各个答题点结果, 提取后放入相应变量内。提取该试题套号, 以试题套号、类别号和具体答题点号为条件在评阅知识库表Testans中查找相关记录, 将提取的结果集中记录的具体答题点的具体答案与学生答题点的答案进行字符串匹配测试。当某个评阅知识库表中的某个具体答案与学生答题结果中的答案匹配成功时则提取该记录的权重值然后乘以该答题点分值。依照上述方法重复进行直至所有答案表中的相关答案全部进行了匹配运算的出具体分值为止, 将所有分值累加, 结果为该考生改错与填空题最终成绩。

2.函数编写题评阅算法。在考生答案记录提取后, 将其中的函数编写答案字段提取, 此字段中存储考生函数编写题的程序文本。同时以试题套号为依据在函数编写题评阅知识库表progans中搜索该套试题答案关键词记录。得到结果集为该题程序中应该出现的关键词结果集, 以每个关键词为依据在考生函数编写题答案文本中搜索该关键词, 一旦匹配成功则累加该关键词对应的权重。结果集每个关键词都进行以上算法后累加的权重值乘以该题的分值即为考生得分。

(四) 知识库知识累积实现。

上述算法基本解决了当主观题答案出现多种变化时不能公平给分的矛盾。但是由于出题者对知识库构建时难免发生遗漏, 因此评阅试题知识库最初的质量并不一定很高。为了能使知识库中知识更加丰富本算法中还增加了知识库知识累积处理。主要是通过人工干预评阅试卷, 当教师对考生答题点逐个人工查看时, 如果知识库中没有出现相应答案但又是正确答案时评阅教师可以将该答案加入知识库。添加到知识库后的答案同时给予一个适当的权重, 如果是函数编写题在加入新的评阅关键词后所有的关键词权重要重新分配使得权重累加结果为1。

这样经过几轮人工干预评阅试卷知识库中的内容将更加丰富, 对以后的评阅更加公平起到促进作用。

四、结语

本文主要阐述了基于人工智能原理的C语言操作考试题的评阅算法。算法中主要利用了知识库功能和简单字符匹配算法。为了解决知识库内容起初不够丰富的问题, 设计了知识库知识累积算法。经过测试表明在经过若干轮人工干预后基本实现了公平评阅试卷。

参考文献

[1].蒋秀莲.基于人工智能技术的智能教学系统研究与设计[J].Microcomputer Applications, 2009

[2].李闯, 常锐.基于人工智能原理的考试系统[J].长春工业大学学报 (自然科学版) , 2009

C笔试题算法 篇5

现在我们终于可以看到一点希望：选择法，这种方法提高了一点性能(某些情况下)

这种方法类似我们人为的排序习惯：从数据中选择最小的同第一个值交换，在从省下的部分中选择最小的与第二个交换，这样往复下去。

#include

void SelectSort(int* pData,int Count)

{

int iTemp;

int iPos;

for(int i=0;i

{

iTemp = pData[i];

iPos = i;

for(int j=i+1;j

{

if(pData[j]

{

iTemp = pData[j];

iPos = j;

}

}

pData[iPos] = pData[i];

pData[i] = iTemp;

}

}

void main

{

int data = {10,9,8,7,6,5,4};

SelectSort(data,7);

for (int i=0;i<7;i++)

cout<

}

倒序(最糟情况)

第一轮：10,9,8,7->(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7->(iTemp=7)7,9,8,10(交换1次) 第二轮：7,9,8,10->7,9,8,10(iTemp=8)->(iTemp=8)7,8,9,10(交换1次)

第一轮：7,8,9,10->(iTemp=9)7,8,9,10(交换0次)

循环次数：6次

交换次数：2次

其他：

第一轮：8,10,7,9->(iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9->(iTemp=7)7,10,8,9(交换1次) 第二轮：7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,9(交换1次)

第一轮：7,8,10,9->(iTemp=9)7,8,9,10(交换1次)

循环次数：6次

交换次数：3次

遗憾的是算法需要的循环次数依然是1/2*(n-1)*n。所以算法复杂度为O(n*n)。

我们来看他的交换。由于每次外层循环只产生一次交换(只有一个最小值)。所以f(n)<=n 所以我们有f(n)=O(n)。

高职院校C语言教学探讨 篇6

关键词：C语言；教学改革；教学方法

一、引 言

《C语言程序设计》是计算机专业的必修课和其他理工科学生的重要基础课程，由于覆盖面广、应用广泛，对于学生的基本编程素质的培养有较大的影响而备受重视。如何更好地完成教学目标，让学生真正掌握C语言，深入了解其精髓，值得每个C语言教学工作者不断探索。

当前，在高职高专院校，《C语言程序设计》课程一般都设置在一年级，学生从高中的基础教育转向学习全新的编程性的语言，学习难度比较大。主要有以下几个原因：一是学生的英文底子普遍薄弱，而C语言英文运行环境，对于运行过程和提示错误根本看不懂，导致上机调试困难重重；再加上对程序主观上认识过难，无形中挫伤了学习的积极性。二是学生的数学基础也比较差，一些编程算法都需要数学思想来支撑。诸多原因造成了C语言教学效果不佳，而对其掌握的程度如何，直接影响到后继相关课程的学习和掌握，甚至是整个专业的后继发展。

笔者根据多年的程序设计课程的教学实践，对《C语言程序设计》课程从教学内容、教学手段、教学方法等方面行了一些改革，并取得较好的教学效果。

二、教学改革措施

1.精简内容，培养兴趣

C语言语法繁多，学生初步接触容易有惧难情绪，因此第一堂课的教学显得尤为重要，它是能否激起学生学习热情的关键因素。一般建议在第一堂课介绍一些应用C语言的小项目，比如嵌入式开发驱动程序的编写、学生注册信息系统的管理。向学生演示运行一些信息管理系统及遥控电风扇运转的一些代码，让学生了解这门语言的一些基本功能，激发他们的学习兴趣。同时用每年获得大赛的学生的事迹激励他们，讲讲学好这门课的方式方法，帮助他们树立学好这门课的信心。

2.案例引导，项目驱动

以谭浩强主编的教材《C程序设计为例》为例，教学内容主要包括C语言语法基础、程序控制结构、数据类型、数组、指针、函数、文件以及它们的应用等。教材在内容组织上，虽然依逻辑思维方式进行了归类，但难点还是较为集中，跨度大；概念讲得多，分析少。再加上高职高专院校的学生，有相当一部分入校时，分数低，数学基础较差，逻辑思维能力不是很强，如果按照书本章节一步步讲下来，学生会产生畏难情绪，学习兴趣开始降低，以往一些学生在第三章节数据类型及表达式还没有完全上完心底就已经开始放弃这门课了。所以在上这门课的时候，建议采用“案例引导、项目驱动”[1]，把课程学习内容联系真实环境，提出各种问题并形成主题任务，进行任务驱动式教学；将学生置于发现问题、提出问题、思考问题、探究问提、解决问题的动态过程中学习。比如第二次授课，就可以提出做一个管理信息系统，先和学生进行基本的功能分析，然后逐步地以实现每一个功能将各个章节的知识点融入进去讲解，以任务驱动教学[2]，让学生真正了解语法为编程服务，而不是单纯的死记硬背一些语法知识。

3.建立良好的网络资源平台，促进师生互动

教学中涉及到的很多知识较抽象和难于理解，因此需要学生课下对课程的重点难点进行进一步消化和理解。因此，应该采用行之有效的办法来帮助学生解决在自主学习中可能遇到的一些问题，比如学生需要进行自主学习的一些教学资源，需要一个进行问题探讨交流的空间，以及教师需要及时地掌握学生自主学习的情况等等。为此，需要建立关于这门课程的学习网站，分别设置课程学习模块、在线练习及在线测试、学习资源建设、参考文献资料、教学论坛等。笔者在完成一个院级项目的过程中建立了一个关于C语言的重点课程建设网站：重难点动画演示课程中涉及的比较难理解的算法以及知识；常见问题解答以章为单位，由课程老师共同建设，不断的加以充实，逐年积累；利用留言板功能建立课程的论坛，教师可以根据自己的教学内容在其中创建话题（发帖），学生也可以在上面对自己的疑问发帖，针对这些话题学生被允许在课题后面发表自己的看法并与教师或其他同学交流，这一功能消除了传统教学中教师只能当面答疑的时空限制，学生能在讨论板上提出自己的问题，而教师可以对具有代表性的问题做出统一解答，避免重复解答，从而提高了教学效率及学习的主动性，同时教师可通过总结学生提出的问题对教学内容做出适时调整。

4.重视上机实践，注重综合考核。

C语言是一门实践性很强的学科，除课堂上的理论讲解外，实验教学也是至关重要的。由于学生是第一次接触程序设计，许多概念都是很抽象的，因此，要求在课程内容的安排上循序渐进，由浅入深，逐步引导。实践课除了需要携带教材以外，另外还需要与之相配套的实验指导书和实验报告册，对于实验指导书可以选择与课本相配套的，教师也可以根据自己的教学需要和学生的实际情况编写合适的实验指导书。对于这门课程学习结果如何，不是一张试卷就能给出答复。我们追求的不是学生懂了多少语法，而是能做出什么，所以对于这门课程，对学生学习成绩的评定，建议采用综合考核法，将平时的实践成绩与期末卷面成绩进行综合，得出本课程综合考评分。这样才能更加客观地反映学生的学习情况，同时也能更好地促进学生平时的学习。

三、结 语

C语言的教学需要不断探讨，我们应在教学过程中不断模索，化繁为简，多钻研教材教法，使学生将所学知识转化为实际工作的能力，提高学生的实际工作水平、综合素质和就业竞争能力，为企业提供适用型的人才。

参考文献：

[1] 邓云洲.案例教学在教学基本要素上与传统教学的区别.教育发展研究，2001，（12）.

常见密码算法分析及C语言实现 篇7

1 计算机密码学发展历史

密码学在人类发展历史中有着不可代替的作用,从2000多年前古埃及发生战争,密码就出现在了人类中,起初的密码就是简单的记录符号。随着时代的推移,在两次世界大战中人们开始意识到密码的重要性。

密码学真正成为一门学科是在二十世纪七十年代。美国国家标准局在1977年对DES(数据加密标准)进行了公布,并批准在非商业和非机密单位中对其进行应用,从此解开了密码的神秘面纱。早在1975年“密码学的新方向”一文中就提出了适用于网络的公钥密码理念,这也是人们对公钥密码进行研究的开始。受“密码学的新方向”影响,各种公钥密码体制被提了出来,在众多体制中,RSA成为了密码学研究的一个里程碑。不夸张的说,“没有公钥密码的研究也不会有近代密码学”。现代社会是一个信息高速发展的社会,随着科技的发展,密码学也取得了巨大进步,而且也成为了许多学科发展的基础。

2 常见的密码算法

2.1 密码系统保密机理

计算机及互联网在人们的日常生活中越来越普及,随之而来的,人们对信息安全方面的要求也越来越高。在网络环境中确保信息完整性、准确性和机密性都需要密码技术来实现。图1为密码系统保密机理。

在图1中key1表示的是加密密钥,key2表示的是解密密钥,密钥系统依据key1与key2是否相同,将密码算法分为对称密码算法和非对称密码算法。非对称密码算法在应用过程中既要使用公钥也要使用私钥。图1中的EK1(M)和DK2(C)就是在加密和解密过程中使用的密码算法。

密码技术是密码算法的核心,算法主要通过软件实现,少数算法可以通过硬件完成,软件实现算法的主要优势在于可优化和可维护,因此在编写上通常使用C语言。

2.2 对称密码算法

KP与KS在实质上是相同的,也就是说可以由KP导出KS。从加密模式上对对称加密模式进行分类,可以将其分为分组密码和序列密码两大类。在对称加密系统中,加密和解密过程中使用的密钥都是相同的,因为加密和解密需要使用相同的密钥,因此加密方和解密方都需要对他们使用的密钥进行保存,同时加密和解密方都需要严格的保存密钥,避免泄露,也只有这样才能实现密码的完整性和机密性[1]。

2.3 非对称密码算法

非对称密码算法也叫做双钥密码算法,在此算法中KP同KS之间有着很大差别,KP是公开密钥,也叫公钥,KS则是必须需要保密的密钥,也叫私钥。在公钥密码算法中可以较容易的由KS推导出KP,但很难实现反向推导,这种单向性的实现,主要是具有单向函数,其中单向函数满足以下条件:1) 指定x值,很容易完成y=kk(x)的计算;2) 指定y,对x进行计算,使x=f-1k(y)无法实现。3) 存在数值k,如果k为已知,给出任意一个y,如果存在相应的x,则很容易完成x=f-1k(y)的计算[2]。

2.4 两种算法的对比

对称密码与非对称密码算在实际应用中各有各的特点,将两者进行对比,优缺点如表1所示。从目前的应用情况来看,对称密码经常被应用在大量数据的加密。非对称密码经常应用在关键性数据加密。例如会话密钥。

3 常见密码算法分析

3.1常见的对称密码算法

IBM公司首先开发了DES算法,并在1977年被美国采纳,作为“非密级”使用标准,并且被广泛应用到生产中,DES曾经是世界上应用最为广泛的密钥算法。在对DES算法进行应用时,将明文分成块,运用8个S盒与8个P盒进行置换,在16轮迭代后,生成比特密文(64bit),在每一轮的迭代中运用的密钥都是由最初的56比特生成的[3]。在加密和解密过程中采用DES加密和解密,那么加密和解密流程以及密钥都完全相同,其中仅有的区别就是解密与加密中应用的子密钥序列是相反的。DES算法主要存在以下问题:1) DES密钥空间无法满足实际需求(256bit)。2) DES里刨除S盒其余计算都是线性的,然而在实际应用中,S盒的密码算法对安全性影响巨大,而NIST(美国国家标准局)并没有将S盒设计原则公布于众,因此,并不排除S盒中藏有“陷门”,同时因为空间问题DES密钥的组合形式有限,在被攻击时,如果攻击人员采用穷举法很可能在短时间内获取成功。因此在实际应用中,为了使DES算法安全性能够得到增加,从事密码设计的工作中虽然又提出了独立密钥方法、基于DES的Triple算法,但在应用中起到的效果并不明显[4]。

在对称密码算法中IDEA算法是由我国学者莱学嘉和美国著名密码专家James L.Massey共同提出的,在IDEA数据加密算法中密文和明文都是64比特,但密钥长度则为128比特。IDEA算法需要建立在群运算的基础之上对密钥和数据进行运算,最后得到解密结果或密文输出。

IDEA算法品质优良,2128比特的密钥空间对其安全性予以了有利的支持,而且无论在硬件上还是在软件上都可以较快的实现。从本质上来看,IDEA算法算是一种“强”加算法,从目前情况来看,还没有出现对其产生有效供给的算法。

3.2非对称加密算法

RSA与上述的DES算法最大的区别就是它的密钥算法被相对完整的公开,在加密过程中使用的加密密钥并不是私密的,在必要时可以通过广播或网络的形式对密钥进行公布,这也就是在加密过程中使用的公钥。在解密过程中应用的密钥则具有私密性,也就是我们常说的私钥。RSA的安全性基于大整数素因子分解的困难性,大数因子分解在数学界一直都是一道难题,到目前还没有人发现合理的解决方法。目前在最快的算法就是参数对照,然而完成1024比特的一个整数因子分解所需要的时间是巨大的。RSA在应用过程中不仅能够用于加密,而且也能用于认证和数字签名和密钥发布[5]。

3.3 ECC算法

ECC算法早在1985年就被提出,是非对称密码算法的一种。其安全性主要源于椭圆曲线离散对数问题求解难度大。建设Q是W(JR)(椭圆曲线)上的一点,点F是W(JR)上为Q倍数点,则存在整数Y大于0,使F与YF相等,椭圆曲线离散问题就是由给出的Q和F来确定出Y的值。依据目前的研究结果来看,对椭圆曲线上的离散对数问题处理要比离散对数处理难度更大,也就是说在椭圆曲线公钥密码上运用较小的数就可以实现同大区域相同的安全性。

4 密码算法的C语言实现

4.1 数据与逻辑运算

在DES算法中,多数为逻辑运算,密钥和明文都需要依照按ASCII码标准统一转化为十进制码,然后再进行密钥置换和IP置换,明文在完成置换后,要进行非线性置换,在DES算法中涉及到的置换都应当为按位逻辑运算。运算过程中的数据类型十分重要。

4.2 随机最大数的生成

无论是使用什么密码算法,在应用中随机最大数都是不可或缺的。一般来说一个能够被应用的密码随机数发生器应当具有以下特性:1) 产生的数值应当是无法预测的。2) 产生的数应当平均分布。3) 拥有一个大范围的取值范围,也就是在使用中能够获取到不同的数值。rand()函数经常用于C语言中随机函数的生成,但如果对信息的安全要求较高则不建议使用rand()函数。这主要是因为rand()具有一定的可预测性,rand()函数是以之前产生的随机数作为种子,然后再生成下一个随机数。

正确的做法是在系统中选取一个高级的函数方法Crypt-Gen Random,该方法具有平均分布和不可预测的特点,此函数已经在Winerypt.h中进行了声明,因此可使用于任意Windows平台。但在对该方法进行调用时需要C++中的CCryp Random类的支持,Crypt Gen Random主要从Windows系统中获取以下随机资源:当前进程、时钟数、内部CPU计数器、当前时间等。

4.3 大数运算

RSA加密需要有大数运算予以支持,目前主流RSA算法需要512位以上作为支持,而从目前情况来看,多数计算机中使用的编译器,仅支持64位,因此无法满足RSA加密的使用需求,为了解决这一问题则需要建立大数运算数据库,数据库中应当包含加、减、乘、除等。

大数表示一种思想:用数学完成对数据的存储,也就是利用10进制数对数组加以表示,然后函数进行编写,这样做的最大优点是符合人们长期以来养成的思维习惯,便于人们对其进行理解;主要弊端是效率低,而且在处理过程中需要优化,而且对该思想进行运算需要许多额外空间。另一种思路是将大数当作一个二进制流进行处理,使用各种移位和逻辑操作来进行加减乘除运算,这样做的最大弊端是代码的可读性差、调试难度大。

4.4 C语言代码的实现

以求模为例,算法流程如下:

int mod(int* arrayA, int* arrayB,int arrayA_Length,int ar-rayB_Length)

{if(arrayA_Length<arrayB_Length)

{for(i=arrayA_Length-l ;i >=0;i—)

{modend[i]=a[i];

}return arrayA_Length;

}

else

{for(i=arrayB_Length;i < arrayA_Length;i++)

{arrayC[j]=arrayA[i]; j=j+1;

}

arrayC_Length = multiply(arrayC,arrayB);

sub(arrayA,arrayC,arrayB,arrayA_Length,arrayC_Length,ar -rayB_Length);

while(arrayA_Length>arrayB_Length)

{sub(arrayA,arrayB,arrayA_Length,arrayB_Length);

}

for(i=arrayA_Length-l ;i >=0;i—)

{modend[i]=a[i];

}

return arrayA_Length;

}}

5 结束语

现代社会是信息社会,计算机技术、网络技术发迅速,信息安全已经成为当今社会的热点话题。尤其是网络信息安全已经成为了信息安全领域亟待解决的问题。使用密码算法是保证网络信息安全的一个重要手段。计算机密码学在解决信息安全上有无可代替的作用,而伴随着计算技术被应用到社会的各个领域,密码技术的应用领域也得到了进一步扩大,因此在日后的研究过程中要加强对密码学的研究,使其能够更好的为人类服务。

摘要：计算机的高速发展使信息安全面临着巨大的挑战。在计算机应用中要想确保信息安全,就必须要对密码算法进行合理应用。基于此,该文对密码算法进行了分析,并将密码算法的C语言实现进行了简单介绍和说明。

关键词：密码算法,C语言,随机数

参考文献

[1]胡小敏.密码算法专用描述语言多项式和大数运算的设计与实现[D].陕西:西安电子科技大学,2012.

[2]陈曼.分组密码算法能量与错误分析攻击及其防御对策研究[D].山东:山东大学,2013.

[3]张晓新,仲丛久.基于C语言实现的数据加密DES算法[J].沈阳航空工业学院学报,2004,21(2):48-49.

[4]张文质,郝鹏翼.Huffman编码和解码的C语言实现[J].洛阳大学学报,2005,4(12):37-41.

C语言算法 篇8

一、Roberts算子介绍

Roberts算子根据任意一对互相垂直方向上的差分可用来计算梯度的原理,采用对角线方向相邻两像素之差近似梯度幅值,表达式为:

用卷积模板表示方法,上式变成

其中Gx和Gy用图1所示的模板计算。

二、使用Roberts算法检测图像边缘的C语言实现

三、使用以上程序检测图像边缘的效果

摘要：在图像处理的研究和应用中,边缘检测技术是一种基本的、关键的技术,经过几十年的研究已经形成了许多成熟的算法。本文给出了Roberts边缘检测算法的C语言实现,以使这一算法能应用于实际。

基于C语言的线性表链式存储算法 篇9

1 线性表数据结构

线性表是最简单、最常用的一种数据结构,在现实生活和工作中,线性表的应用非常普遍。

线性表是由n个类型相同的数据元素组成的有限序列,可以表示为:

线性表是一种线性结构,数据元素在线性表中的位置取决于该数据元素的序号,一个非空的线性表如图1所示,具有如下特征:

(1)表中有且仅有一个根结点a1,该结点无前件。

(2)表中有且仅有一个终端结点an,该结点无后件。

(3)表中除根结点a1和终端结点an外,其余结点都有且仅有一个前件,有且仅有一个后件。

2 线性表的存储

存储通常有两种方式:顺序存储和链式存储。

线性表的顺序存储也叫顺序表,是用内存中一组地址连续的存储单元依次存储线性表中的数据元素,数据元素之间的逻辑关系通过内存中数据元素间的物理位置关系来体现,如图2所示。

顺序表的优点是:容易实现;可以实现对数据元素的随机存取;没有为体现数据元素间逻辑关系而增加额外的空间开销。缺点是:当线性表的规模n较大时,线性表的插入和删除等常规操作的效率较低;对线性表进行插入和删除等常规操作后,可能导致存储空间溢出和闲置。

线性表的链式存储也叫线性链表,是用内存中一组随机的存储单元存储线性表中的数据元素,数据元素之间的逻辑关系通过与数据元素一起存储的、指向该数据元素前件、或后件的指针来体现,图3所示是一种通过指向数据元素后件的指针来体现数据间逻辑结构的单向链式存储。

线性链表的优点是:对存储空间没有连续性要求,容易满足;对线性表的插入和删除等常规操作的效率高;根据需要分配存储单元,不会引起存储空间溢出和闲置;缺点是:实现较复杂;只能对数据元素进行顺序存取。

3 线性表链式存储算法及其C语言

在实际应用中,对线性表的插入和删除等常规操作是经常性的,从线性表两种常用存储方式的特点可以看出,线性表链式存储的优势是非常明显的。

对线性表进行插入和删除等常规操作的前提是线性表的存储,线性链表的实现比顺序表的实现复杂,不能直接通过数据类型的定义来建立,需要一个节点一个节点地建立链接关系。

线性链表的建立是一个动态存储空间分配和形成链接关系的过程,通常采用的方法有尾插法和头插法两种。

3.1 尾插法

尾插法建立的是如图3所示的正序线性表。

尾插法的基本思想是:新插入的节点总是放在链表尾部。如图4所示。

用尾插法建立带头结点的单向链表的算法如下:

(1)建立一个空链表;

(2)分配新节点存储单元,对新节点的数据域和指针域赋值。由于新插入的节点总是尾节点,因此,它的指针域的值为空;

(3)将新节点链接到链表的尾部;

(4)重复步骤(2)~(3),继续插入新节点直到结束。

用C语言描述如下:

3.2 头插法

头插法建立的是一种逆序线性表,如图5所示。

头插法的基本思想是:新插入的节点总是作为链表的第一个节点,放在头结点之后。如图6所示。

用头插法建立带头结点的单向链表的算法如下:

(1)建立一个空链表;

(2)分配新节点存储单元,对新节点的数据域赋值;

(3)将新节点插入到头结点和第一个结点之间;

(4)重复步骤(2)~(3),继续插入新节点直到结束。

用C语言描述如下:

4 结语

线性表的顺序存储和线性表的链式存储各有其优缺点,在实际应用中,应根据线性表的操作需要进行选择。在进行线性表的插入和删除操作时,采用线性表的链式存储将会降低算法的空间复杂度和时间复杂度,合理利用存储空间,提高处理效率。因此,对经常需要进行插入和删除操作的线性表,应采用链式存储方式。

摘要：在进行线性表的插入和删除操作时,采用线性表的链式存储将会降低算法的空间复杂度和时间复杂度,合理利用存储空间,提高处理效率。基于C语言的线性表链式存储算法的实现有尾插法和头插法两种。

关键词：数据结构,线性表,链式存储,C语言,算法

参考文献

[1]陈明.数据结构.清华大学出版社,2005.

[2]徐士良.实用数据结构.清华大学出版社,2006.

[3]严蔚敏,吴伟民.数据结构.清华大学出版社,1997.

C语言算法 篇10

顺序查找又称线性查找，对给定的关键码值key，从表(一组数据)的一端开始，依次检查表中每个元素的关键码值，直至找到所需的元素或到达表的另一端。

2 对分查找及算法概述

首先在有序表中取表的中间位置上的元素R[i](i=[n/2])与待查元素key进行比较，如果key=R[i]·key，则已经找到该元素，成功返回;如果keyR[i]·key，则在该表的后一半R[0]，……，R[i-1]中进行n查找;如此反复进行，直到找到该元素或全表对分查找完毕。

3 选择排序及算法概述

首先选出关键码最小的元素，将其与第一个元素交换。再从剩下的n-1个元素中选出关键码最小的元素，将其与第二个元素交换，如此反复进行，直到剩下最后两个元素(假设按关键码由小到大排序)。

4 冒泡排序及算法概述

从表的一端开始，依次比较两个相邻元素的关键码R[i]·key和R[i+1]·ke y，如果R[i]·ke y>R[i+1]·ke y，则交换元素R[i]和R[i+1]。如此反复进行，直到其最大关键码的元素移到表的最末端的位置。

5 直接插入排序及算法概述

如果表中元素R[0], R[1], ……R[i-1]已经按关键码(key)有序，则将R[i]·key与R[i-1]·key, R[i-2]·key，……，R[1]·key, R[0]·key进行比较，一旦R[i]·key≥R[j]·key则将R[j+1]，R[j+2]，……，R[j-1]后移一个位置，并将R[i]插到第j+1个位置上。该过程从表中第二个元素R[1]开始直到表中最后一个元素R[n-1]止反复进行。

参考文献

[1]谭浩强.C程序设计 (第二版) .清华大学出版社, 2002.

C语言中数组的元素 篇11

关键词：数组；元素；数据；类型

中图分类号：TP313文献标识码：A文章编号：1007-9599 (2010) 16-0000-02

Elements of the Array in C-language

Zhang Kexing

（Foreign Language Teachers College of Taiyuan University,Taiyuan030012,China）

Abstract:The array is the most commonly used programming data st-

ructure.Array can be divided into array of values（integer group,real array）,a character array and pointer array and the array of structures.

This array will be examples of various types were analyzed and explained.

Keywords:Array;Element;Data;Type

一、引言

數组是相互关联的一批数据的序列，序列中的数据称为数组的元素，可按照排列顺序编号，起始编号一般为0，前后两个数据的编号有差异，通过编号可以唯一指定数组中的数据成员。数组中的元素可以是基本类型，也可以是构造类型。按照数组元素的不同可将数组分为数值数组、字符数组、指针数组、结构数组。

二、数值数组

数值数组是指数组元素是整型、实型、及其相关类型的数据，简单说，就是元素是数字的数组。

例1：

main（）

{

int i，a[10]；

for（i=0；i<=9；i++）

a[i]=i；

for（i=9；i>=0；i--）

printf（"%d "，a[i]）；

}

在该例中，第一个for语句给数组a中的10个元素赋值为整形数据0-9，赋值以后数组中数据如下：

第二个for语句将数组a中的10个数字反序输出，即9、8、7、6、5、4、3、2、1、0

数值数组是数组中使用率最高的数组，需要注意的是一个数组中的数据必须是同一种类型的数据，

{int a[3]；

a[0]=3；

a[1]=2.5；

a[2]=3.0；}

是不合法的。

三、字符数组

C语言没有专门定义字符串数据类型（如其他语言中的string），它用以''结尾的字符数组来表示一个逻辑意义上的字符串。

字符数组主要有两种用途，（1）存储字符串，（2）存储字符或字符变量。这两个是不同的，刚开始接触时很容易混淆。下面进一步分析这两者的不同。

首先初始化时不同，用于存储字符串，例如：char str[]="Hello"； 用于存储字符或字符变量，例如：char Chars[]={‘H‘‘e‘，‘1‘‘1‘，‘o‘}。这两者的存储方式是一样的，但是存储内容稍微有所不同，那就是第一种情况会在结尾加上‘’，存储情况类似于{‘H‘‘e‘，‘1‘‘1‘，‘o‘，‘‘}，存储空间会比第二种情况大一点，但是这个存在空间并不被计算进字符串（其实只是字符数组）变量中。

C语言中提供的字符串操作函数其实是针对于结尾是‘‘的字符数组进行的。输出函数printf中的输出参数%s也是针对于结尾是‘‘的字符数组。

另外，还有一种方法可以定义字符串（其实也是字符数组），声明如下：

char * string = "this is a point charArray."；字符指针指向字符数据的第一个字符的位置。

最后，有两点特别说明。

（1）字符串常量给出的是地址值。如

char *p， s[10]；

p="hello"；//正确

（2）不能用赋值语句给字符数组整体赋一串字符，例：

char str[10]；

str = "abc"；//错误

例2：

char c[10]={‘c’， ‘’， ‘p’， ‘r’， ‘o’， ‘g’， ‘r’， ‘a’，’m’}；

赋值后数组元素如下：

四、指针数组

在C语言中，一个数组的元素值为指针则是指针数组。 指针数组是一组有序的指针的集合。指针数组的所有元素都必须是具有相同存储类型和指向相同数据类型的指针变量。

指针数组说明的一般形式为：

类型说明符*数组名[数组长度]

其中类型说明符为指针值所指向的变量的类型。

例如：

int *pa[3]

表示pa是一个指针数组，它有三个数组元素，每个元素值都是一个指针，指向整型变量。

例3：

通常可用一个指针数组来指向一个二维数组。指针数组中的每个元素被赋予二维数组每一行的首地址，因此也可理解为指向一个一维数组。

main（）{

int a[3][3]={1，2，3，4，5，6，7，8，9}；

int *pa[3]={a[0]，a[1]，a[2]}；

int *p=a[0]；

int i；

for（i=0；i<3；i++）

printf（"%d，%d，%dn"，a[i][2-i]，*a[i]，*（*（a+i）+i））；

for（i=0；i<3；i++）

printf（"%d，%d，%dn"，*pa[i]，p[i]，*（p+i））；

}

本例程序中，pa是一个指针数组，三个元素分别指向二维数组a的各行。然后用循环语句输出指定的数组元素。其中*a[i]表示i行0列元素值；*（*（a+i）+i）表示i行i列的元素值；*pa[i]表示i行0列元素值；由于p与a[0]相同，故p[i]表示0行i列的值；*（p+i）表示0行i列的值。

在C语言中，数组元素全为指针的数组成为指针数组。

一维指针数组的定义形式为：“类型名*数组标识符[数组长度]”。

例如，一个一维指针数组的定义：int *ptr_array[10]。

指针数组的含义：

指针数组中的每一个元素均为指针，即有诸形如“*ptr_array[i]”的指针。

由于数组名本身也是一个指针，因此指针数组中的元素亦可以表示为“*（*（ptr_ayyry+i））”。又因为“（）”的优先级较“*”高，且“*”是右结合的，因此可以写作**（ptr_array+i）。

五、结构数组

数组的元素也可以是结构类型的。因此可以构成结构型数组。结构数组的每一个元素都是具有相同结构类型的下标结构变量。在实际应用中，经常用结构数组来表示具有相同数据结构的一个群体。如一个班的学生档案，一个车间职工的工资表等。

方法和结构变量相似，只需说明它为数组类型即可。

例4：

struct stu

{

int num；

char *name；

char sex；

float score；

}boy[5]；

定义了一个结构数组boy，共有5个元素，boy[0]～boy[4]。每个数组元素都具有struct stu的结构形式。

例5：计算学生的平均成绩和不及格的人数。

struct stu

{

int num；

char *name；

char sex；

float score；

}boy[5]={

{101，"Li ping"，'M'，45}，

{102，"Zhang ping"，'M'，62.5}，

{103，"He fang"，'F'，92.5}，

{104，"Cheng ling"，'F'，87}，

{105，"Wang ming"，'M'，58}，

}；

main（）

{

int i，c=0；

float ave，s=0；

for（i=0；i<5；i++）

{

s+=boy[i].score；

if（boy[i].score<60） c+=1；

}

printf（"s=%fn"，s）；

ave=s/5；

printf（"average=%fncount=%dn"，ave，c）；

}

本例程序中定义了一个外部结构数组boy，共5个元素，并作了初始化赋值。在main函数中用for语句逐个累加各元素的score 成员值存于s之中，如score的值小于60（不及格）即计数器C加1，循环完毕后计算平均成绩，并输出全班总分，平均分及不及格人数。

六、总结

数组是程序设计中最常用的数据结构。数组可分为数值数组（整数组，实数组），字符数组以及指针数组和结构数组。数组可以是一维的，二维的或多维的。数组类型说明由类型说明符、数组名、数组长度（数组元素个数）三部分组成。要想将不同的数据用不同类型的数组存放，就需要深入了解每一种类型的数组及其特点，这样才能灵活运用，充分发挥每种数据类型的长处。

参考文献：

[1]谭浩强.C程序设计教程[M].北京:清华大学出版社,2007,7

[2]李岩.C语言程序设计基础与上机知道[M].北京:清华大学出版社,2006,3

[3]马秀丽等.C语言程序设计[M].北京:清华大学出版社,2008,3

[4]罗坚.C语言程序设计[M].北京:中国铁道出版社,2009,2

作者簡介：

张科星（1980-），女，山西太原人，研究生，太原大学外语师范学院，助教，研究方向：网络，计算机教育。

C语言的N皇后算法的优化设计 篇12

N皇后问题是各类语言程序设计中的较著名的题目.该问题由19世纪著名的数学家高斯在1850年提出:在N×N格的国际象棋上摆放N个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法.国际象棋的规则是:皇后可以在横、竖、斜线上不限步数地吃掉其它棋子。如何在N×N的棋盘上放置N个皇后,使它们不能相吃,显然每行每列只能摆放一个皇后,因此怎么快速准确的计算出能同时放置N个皇后的摆法有多少种,成了大家都很感兴趣的一个研究问题。

2 算法优化

通常N皇后的算法都是通过递归来进行计算,因此从算法速度上来说,微小的改进都会在N皇后问题中有显著的提高,下面基于C语言来讨论几方面的优化。

2.1 对称改进

因为N皇后的棋盘是个N×N的对称的棋盘,所以当进行程序计算时,可以只依次进行N/2个格子的冲突判断,就可以相应的通过对称计算出剩下的N个格子的冲突,也就是说,算出N/2个格子里面可以摆放的种数,然后乘以2,就可以得到所有的摆放种数,这里还要注意处理N为偶数和奇数的情况。

2.2 消除函数调用

在程序设计语言中,调用函数,都会产生新的堆栈空间,进行调用记录,在调用过程中会耗费多余的运行时间,所以在程序核心部分将所有的函数调用全部取消以增加计算速度。

2.3 设置斜线和列标志改进

在程序中最耗时的就是循环部分,通过设置斜线和列被皇后占用的标志来减少循环,使整个计算的循环次数显著的减少,当某列或斜线标志被占用时,就不进行循环的比较,而直接将此斜线和列的循环跳过,这样可以极大的提高运行速度。

2.4 进一步对称改进

看图1,在这里只选取了5个格式来说明,当一个皇后摆在A点后,剩余的N-1个皇后形成的摆放图形,与一个皇后在B点形成的摆放图形是对称相同的。所以当得出A点的摆放种数后,当皇后出现在B点时,可以不进行循环,而是加上在A点时的方法种数就可以了。

3 源程序

4 总结

通过以上的优化方法,经过测试,程序运行时间提高60%以上。在皇后数量每增加一个时,这种优势越明显。所以对N皇后的算法优化的方法可以应用在各种关键算法中,对计算机程序的执行效率的提高有着很高的实用价值。

参考文献

[1]谭浩强.C程序设计[M].北京:清华大学出版社,1998.

[2]宋文,吴晟,杜亚军.算法设计与分析[M].重庆:重庆大学出版社,2001:51—67.