c语言排序算法总结（共5篇）
/*
file:quick.cpp
author:www.5dkx.com
*/
#include
using namespace std;
void Merge(int a[],int low,int mid,int high,int b[]);
void MSort(int a[],int low,int high,int b[]);
void main
{
int a[]={4,5,9,10,51,6,46,36,6,56,67,45,36};
int b[13];
MSort(a,0,12,b);
for(int i=0;i<13;i++)
cout<<<“ ”;
cout<
for(int j=0;j<13;j++)
cout<
cout<
}
void Merge(int a[],int low,int mid,int high,int b[])
{
int i=low,j=mid+1,k=low;
while((i<=mid)&&(j<=high))
{
if(a[i]<=a[j])
{
b[k]=a[i];
i++;
}
else
{
b[k]=a[j];
j++;
}
k++;
}
while(i<=mid)
{
a[k]=a[i];
k++;
i++;
}
while(j<=high)
{
a[k]=a[j];
k++;j++;
}
}
void MSort(int a[],int low,int high,int b[])
{
if(low==high)
b[low]=a[low];
else
{
int mid=(low+high)/2;
MSort(a,low,mid,b);
MSort(a,mid+1,high,b);
Merge(a,low,mid,high,b);
}
顺序查找又称线性查找，对给定的关键码值key，从表(一组数据)的一端开始，依次检查表中每个元素的关键码值，直至找到所需的元素或到达表的另一端。
2 对分查找及算法概述
首先在有序表中取表的中间位置上的元素R[i](i=[n/2])与待查元素key进行比较，如果key=R[i]·key，则已经找到该元素，成功返回;如果key
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.
递归方式实现
/** * 找到数组里面第k大的元素 * @param array 输入的数组 * @param arraySize 数组大小 * @param kthNumber 第k大元素的大小 * @param k 第k大的元素 */void randomizedSelect(int array[] , int arraySize , int * kthNumber , int k){ if(array == NULL || arraySize <= 0 || kthNumber == NULL || k <0 || k >= arraySize) return; randomizedSelectKernel(array, 0 , arraySize-1 , kthNumber , k);}/** * 找到leftBorder到rightBorder中第k大的元素,递归函数 * @param array 输入的数组 * @param leftBorder 左边界 * @param rightBorder 右边界 * @param kthNumber 第k大的元素的实际值 * @param k 第k大的元素 */void randomizedSelectKernel(int array[], int leftBorder , int rightBorder ,int * kthNumber , int k){ if(leftBorder >rightBorder) return ; // 这里采用快速排序的思想来完成 int i = leftBorder-1; int j = leftBorder; int x = array[rightBorder]; // 首先找到主元 for(; j < rightBorder ; ++j) { if(array[j] <= x) {exchange(array , j , ++i); } } ++i; exchange(array , i , rightBorder); // 现在位置i就是需要放置主元的地方 if(i == leftBorder+k-1) *kthNumber = array[i]; else if(i >leftBorder+k-1) randomizedSelectKernel(array , leftBorder , i-1 , kthNumber , k); else if(i < leftBorder+k-1) randomizedSelectKernel(array , i+1, rightBorder , kthNumber , k-(i-leftBorder+1));}
运行结果
input array is :
96 47 95 38 53 45 3 92 20 73
2th max number is———————- 20
3 20 45 38 47 53 73 92 96 95
1th max number is———————- 3
3 20 45 38 47 53 73 92 96 95
3th max number is———————- 38
3 20 38 45 47 53 73 92 96 95
6th max number is———————- 53
3 20 38 45 47 53 73 92 96 95
迭代方式实现
/** * 找到数组里面第k大的元素 * @param array 输入的数组 * @param arraySize 数组大小 * @param kthNumber 第k大元素的大小 * @param k 第k大的元素 */void randomizedSelect(int array[] , int arraySize , int * kthNumber , int k){ if(array == NULL || arraySize <= 0 || kthNumber == NULL || k <0 || k >= arraySize) return; int left = 0; int right = arraySize-1; int kTemp = k; while(left <= right) { // 采用快速排序的思想 // 首先找到主元 int i = left-1; int j = left; int x = array[right]; for(; j < right ; ++j) {if(array[j] <= x){ exchange(array , ++i , j);} } ++i; exchange(array , i , right); /** 现在位置i就是主元位置 */ if(i == kTemp+left-1)// 找到第k大的元素 {*kthNumber = array[i];return; } else if (i
运行结果:
input array is :
62 66 70 54 74 98 83 52 80 19
2th max number is———————- 52
19 52 54 62 74 98 83 70 80 66
1th max number is———————- 19
19 52 54 62 66 98 83 70 80 74
3th max number is———————- 54
19 52 54 62 66 98 83 70 80 74
6th max number is———————- 70
1.基本思想：
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。2.排序过程： 【示例】：
初始关键字 [49 38 65 97 76 13 27 49] 第一趟排序后 13 ［38 65 97 76 49 27 49] 第二趟排序后 13 27 ［65 97 76 49 38 49] 第三趟排序后 13 27 38 [97 76 49 65 49] 第四趟排序后 13 27 38 49 [49 97 65 76] 第五趟排序后 13 27 38 49 49 [97 97 76] 第六趟排序后 13 27 38 49 49 76 [76 97] 第七趟排序后 13 27 38 49 49 76 76 [ 97] 最后排序结果 13 27 38 49 49 76 76 97 3.void selectionSort(Type* arr,long len){ long i=0,j=0;/*iterator value*/ long maxPos;assertF(arr!=NULL,“In InsertSort sort,arr is NULLn”);for(i=len-1;i>=1;i--){ maxPos=i;for(j=0;j
直接插入排序（Straight Insertion Sort）：将一个记录插入到排好序的有序表中，从而得到一个新的、记录数增1的有序表。直接插入排序算法
哨兵（监视哨）有两个作用：一是作为临变量存放R[i]（当前要进行比较的关键字）的副本；二是在查找循环中用来监视下标变量j是否越界。
当文件的初始状态不同时，直接插入排序所耗费的时间是有很大差异的。最好情况是文件初态为正序，此时算法的时间复杂度为O(n)，最坏情况是文件初态为反序，相应的时间复杂度为O(n2)，算法的平均时间复杂度是O(n2)。算法的辅助空间复杂度是O(1)，是一个就地排序。
直接插入排序是稳定的排序方法。三.冒泡排序
[算法思想]：将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上“飘浮”。如此反
复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。
[算法]：
void BubbleSort(SeqList R){ //R（l..n)是待排序的文件，采用自下向上扫描，对R做冒泡排序 int i，j；
Boolean exchange； //交换标志
for(i=1;i exchange=FALSE； //本趟排序开始前，交换标志应为假 for(j=n-1;j>=i；j--)//对当前无序区R[i..n]自下向上扫描 if(R[j+1].key R[0]=R[j+1]； //R[0]不是哨兵，仅做暂存单元 R[j+1]=R[j]； R[j]=R[0]； exchange=TRUE； //发生了交换，故将交换标志置为真 } if(!exchange)return；//本趟排序未发生交换，提前终止算法 } //endfor(外循环)} //BubbleSort [分析]：起泡排序的结束条件为：最后一趟没有进行“交换”。从起泡排序的过程可见，起泡排序是一个增加有序序列长度的过程，也是一个缩小无序序列长度的过程，每经过一趟起泡，无序序列的长度只缩小1。[算法思想]：将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上“飘浮”。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。 [算法]： void BubbleSort(SeqList R){ //R（l..n)是待排序的文件，采用自下向上扫描，对R做冒泡排序 int i，j； Boolean exchange； //交换标志 for(i=1;i exchange=FALSE； //本趟排序开始前，交换标志应为假 for(j=n-1;j>=i；j--)//对当前无序区R[i..n]自下向上扫描 if(R[j+1].key R[0]=R[j+1]； //R[0]不是哨兵，仅做暂存单元 R[j+1]=R[j]； R[j]=R[0]； exchange=TRUE； //发生了交换，故将交换标志置为真 } if(!exchange)return；//本趟排序未发生交换，提前终止算法 } //endfor(外循环)} //BubbleSort [分析]：起泡排序的结束条件为：最后一趟没有进行“交换”。从起泡排序的过程可见，起泡排序是一个增加有序序列长度的过程，也是一个缩小无序序列长度的过程，每经过一趟起泡，无序序列的长度只缩小1。四.希尔排序 基本思想： 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d l的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2 该方法实质上是一种分组插入方法。给定实例的shell排序的排序过程 假设待排序文件有10个记录，其关键字分别是： 49，38，65，97，76，13，27，49，55，04。 增量序列的取值依次为： 5，3，1 Shell排序的算法实现 1． 不设监视哨的算法描述 void ShellPass(SeqList R，int d){//希尔排序中的一趟排序，d为当前增量 for(i=d+1;i<=n；i++)//将R[d+1．．n]分别插入各组当前的有序区 if(R[i].key R[j+d]；=R[j]； //后移记录 j=j-d； //查找前一记录 }while(j>0&&R[0].key R[j+d]=R[0]； //插入R[i]到正确的位置上 } //endif } //ShellPass void ShellSort(SeqList R){ int increment=n； //增量初值，不妨设n>0 do { increment=increment/3+1； //求下一增量 ShellPass(R，increment)； //一趟增量为increment的Shell插入排序 }while(increment>1)} //ShellSort 注意： 当增量d=1时，ShellPass和InsertSort基本一致，只是由于没有哨兵而在内循环中增加了一个循环判定条件“j>0”，以防下标越界。2．设监视哨的shell排序算法 算法分析 1．增量序列的选择 Shell排序的执行时间依赖于增量序列。 好的增量序列的共同特征： ① 最后一个增量必须为1； ② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。 有人通过大量的实验，给出了目前较好的结果：当n较大时，比较和移动的次数约在nl.25到1.6n1.25之间。 2．Shell排序的时间性能优于直接插入排序 希尔排序的时间性能优于直接插入排序的原因： ①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。 ②当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。 ③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。 因此，希尔排序在效率上较直接插人排序有较大的改进。3．稳定性 希尔 排序是不稳定的。参见上述实例，该例中两个相同关键字49在排序前后的相对次序发生了变化。五.堆排序 1、堆排序定义 n个关键字序列Kl，K2，„，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)： (1)ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤) 若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。 【例】关键字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分别满足堆性质(1)和(2)，故它们均是堆，其对应的完全二叉树分别如小根堆示例和大根堆示例所示。 2、大根堆和小根堆 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。注意： ①堆中任一子树亦是堆。 ②以上讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆。 3、堆排序特点 堆排序(HeapSort)是一树形选择排序。 堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系【参见二叉树的顺序存储结构】，在当前无序区中选择关键字最大(或最小)的记录。 4、堆排序与直接插入排序的区别 直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。 堆排序可通过树形结构保存部分比较结果，可减少比较次数。 5、堆排序 堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。（1）用大根堆排序的基本思想 ① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区 ② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key ③ 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有 序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。 „„ 直到无序区只有一个元素为止。（2）大根堆排序算法的基本操作： ① 初始化操作：将R[1..n]构造为初始堆； ② 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。注意： ①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。 ②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻，堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。（3）堆排序的算法： void HeapSort(SeqIAst R){ //对R[1..n]进行堆排序，不妨用R[0]做暂存单元 int i； BuildHeap(R)； //将R[1-n]建成初始堆 for(i=n;i>1；i--){ //对当前无序区R[1..i]进行堆排序，共做n-1趟。R[0]=R[1]；R[1]=R[i];R[i]=R[0]； //将堆顶和堆中最后一个记录交换 Heapify(R，1，i-1)； //将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质 } //endfor } //HeapSort（4）BuildHeap和Heapify函数的实现 因为构造初始堆必须使用到调整堆的操作，先讨论Heapify的实现。① Heapify函数思想方法 每趟排序开始前R[l..i]是以R[1]为根的堆，在R[1]与R[i]交换后，新的无序区R[1..i-1]中只有R[1]的值发生了变化，故除R[1]可能违反堆性质外，其余任何结点为根的子树均是堆。因此，当被调整区间是R[low..high]时，只须调整以R[low]为根的树即可。“筛选法”调整堆 R[low]的左、右子树(若存在)均已是堆，这两棵子树的根R[2low]和R[2low+1]分别是各自子树中关键字最大的结点。若R[low].key不小于这两个孩子结点的关键字，则R[low]未违反堆性质，以R[low]为根的树已是堆，无须调整；否则必须将R[low]和它的两个孩子结点中关键字较大者进行交换，即R[low]与R[large](R[large].key=max(R[2low].key，R[2low+1].key))交换。交换后又可能使结点R[large]违反堆性质，同样由于该结点的两棵子树(若存在)仍然是堆，故可重复上述的调整过程，对以R[large]为根的树进行调整。此过程直至当前被调整的结点已满足堆性质，或者该结点已是叶子为止。上述过程就象过筛子一样，把较小的关键字逐层筛下去，而将较大的关键字逐层选上来。因此，有人将此方法称为“筛选法”。 ②BuildHeap的实现 要将初始文件R[l..n]调整为一个大根堆，就必须将它所对应的完全二叉树中以每一结点为根的子树都调整为堆。 显然只有一个结点的 树是堆，而在完全二叉树中，所有序号 的结点都是叶子，因此以这些结点为根的子树均已是堆。这样，我们只需依次将以序号为，-1，„，1的结点作为根的子树都调整为堆即可。 具体算法【参见教材】。 5、大根堆排序实例 对于关键字序列(42，13，24，91，23，16，05，88)，在建堆过程中完全二叉树及其存储结构的变化情况参见。 6、算法分析 堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。 堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。 由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。 堆排序是就地排序，辅助空间为O(1)，它是不稳定的排序方法。六.快速排序 快速排序的基本思路是：首先我们选择一个中间值middle（程序中我们可使用数组中间值），把比中间值小的放在其左边，比中间值大的放在其右边。由于这个排序算法较复杂，我们先给出其进行一次排序的程序框架（从各类数据结构教材中可得）： void QuickSort(int *pData, int left, int right){ int i, j;int middle, iTemp;i = left;j = right;middle = pData[(left + right)/ 2];//求中间值 do { while((pData[i] < middle)&&(i < right))//从左扫描大于中值的数 i++; while((pData[j] > middle)&&(j > left))//从右扫描小于中值的数 j--; if(i <= j)//找到了一对值 { //交换 iTemp = pData[i]; pData[i] = pData[j]; pData[j] = iTemp; i++; j--; } } while(i <= j);//如果两边扫描的下标交错，就停止（完成一次） //当左边部分有值(left if(left QuickSort(pData,left,j); //当右边部分有值(right>i)，递归右半边 if(right>i) QuickSort(pData,i,right);} 对于n个成员，快速排序法的比较次数大约为n*logn 次，交换次数大约为(n*logn)/6次。如果n为100，冒泡法需要进行4950 次比较，而快速排序法仅需要200 次，快速排序法的效率的确很高。快速排序法的性能与中间值的选定关系密切，如果每一次选择的中间值都是最大值（或最小值），该算法的速度就会大大下降。快速排序算法最坏情况下的时间复杂度为O(n2)，而平均时间复杂度为O(n*logn)。七.合并排序 說明 之前所介紹的排序法都是在同一個陣列中的排序，考慮今日有兩筆或兩筆以上的資料，它可能是不同陣列中的資料，或是不同檔案中的資料，如何為它們進行排序？ 解法 可以使用合併排序法，合併排序法基本是將兩筆已排序的資料合併並進行排序，如果所讀入的資料尚未排序，可以先利用其它的排序方式來處理這兩筆資料，然後再將排序好的這兩筆資料合併。 有人問道，如果兩筆資料本身就無排序順序，何不將所有的資料讀入，再一次進行排序？排序的精神是儘量利用資料已排序的部份，來加快排序的效率，小筆資料的排序較為快速，如果小筆資料排序完成之後，再合併處理時，因為兩筆資料都有排序了，所有在合併排序時會比單純讀入所有的資料再一次排序來的有效率。那麼可不可以直接使用合併排序法本身來處理整個排序的動作？而不動用到其它的排序方式？答案是肯定的，只要將所有的數字不斷的分為兩個等分，直到最後剩一個數字為止，然後再反過來不斷的合併，就如下圖所示： 不過基本上分割又會花去額外的時間，不如使用其它較好的排序法來排序小筆資料，再使用合併排序來的有效率。 下面這個程式範例，我們使用快速排序法來處理小筆資料排序，然後再使用合併排序法處理合併的動作。例子 C #include quicksort(number1, 0, MAX1-1);quicksort(number2, 0, MAX2-1);printf(“n排序後：”);printf(“nnumber1[]：”);for(i = 0;i < MAX1;i++)printf(“%d ”, number1[i]);printf(“nnumber2[]：”);for(i = 0;i < MAX2;i++)printf(“%d ”, number2[i]);// 合併排序 mergesort(number1, MAX1, number2, MAX2, number3);printf(“n合併後：”);for(i = 0;i < MAX1+MAX2;i++)printf(“%d ”, number3[i]);printf(“n”);return 0;} int partition(int number[], int left, int right){ int i, j, s;s = number[right];i = left-1;for(j = left;j < right;j++){ if(number[j] <= s){ i++;SWAP(number[i], number[j]);} } SWAP(number[i+1], number[right]);return i+1;} void quicksort(int number[], int left, int right){ int q;if(left < right){ q = partition(number, left, right);quicksort(number, left, q-1);quicksort(number, q+1, right);} } void mergesort(int number1[], int M, int number2[], int N, int number3[]){ int i = 0, j = 0, k = 0;while(i < M && j < N){ if(number1[i] <= number2[j])number3[k++] = number1[i++];else number3[k++] = number2[j++];} while(i < M)number3[k++] = number1[i++];while(j < N)number3[k++] = number2[j++];} Java public class MergeSort { public static int[] sort(int[] number1, int[] number2){ int[] number3 = new int[number1.length + number2.length];int i = 0, j = 0, k = 0;while(i < number1.length && j < number2.length){ if(number1[i] <= number2[j])number3[k++] = number1[i++];else number3[k++] = number2[j++];} while(i < number1.length)number3[k++] = number1[i++];while(j < number2.length)number3[k++] = number2[j++];return number3;} } 八。基数排序 基数排序是根据组成关键字的各位值，用“分配”和“收集”的方法进行排序。例如，把扑克牌的排序看成由花色和面值两个数据项组成的主关键字排序。 花色：梅花<方块<红心<黑桃 面值：2<3<4<...<10 梅花2,...,梅花A,方块2,...,方块A,红心2,...,红心A,黑桃2,...,黑桃A。 有两种排序方法： 一、先按花色分成四堆，把各堆收集起来；然后对每堆按面值由小到大排列，再按花色从小到大按堆收叠起来。----称为“最高位优先”(MSD)法。 二、先按面值由小到大排列成13堆,然后从小到大收集起来；再按花色不同分成四堆,最后顺序收集起来。----称为“最低位优先”(LSD)法。 [例] 设记录键值序列为{88,71,60,31,87,35,56,18}，用基数排序(LSD)。如图所示：其中f[i]、e[i]为按位分配面值为i的队列的队头和队尾指针。 #define D 3 typedef struct { int key;float data;int link;} JD key data link int jspx(JD r[],int n){ /*链式存储表示的基数排序*/ int i,j,k,t,p,rd,rg,f[10],e[10];/*p为r[]的下标,rd,rg为比例因子,f[j],e[j]是代码为j的队的首尾指针*/ for(i=1;i 大家可以看出，指针、数组、字符串无论在笔试还是上机都是重中之重，既是重点又是难点。C语言程序初步、顺序结构、选择结构、循环结构、函数是基础。编译预处理、作用域与存储类、位运算、文件等是难点但不是重点，每年都会考到，但题量都不大。结构体与共用体可以说比较重点又是难点。公共基础部分除了程序设计基础这一部分，其他三部分旗鼓相当，都是重点。 第一章 C语言基本知识 【考点1】C程序 用C语言编写的程序称为C语言源程序，源程序文件的后缀名为“.c”。源程序经编译后生成后缀名为“.obj”的目标文件，再把目标文件与各种库函数连接起来，生成“.exe”可执行文件。C语言有三种基本结构：顺序结构、选择结构、循环结构。 【考点2】main函数 又称主函数，是C程序的入口。main后面跟一对小括号和一对花括号，花括号括起来的部分称为main函数的函数体。一个C程序从main函数开始执行，到main函数体执行完结束，而不论main函数在整个程序中的位置如何。每一个程序有且仅有一个main函数，其他函数都是为main函数服务的。 【考点3】存储形式 计算机在电脑中保存数据是采用二进制形式，由0或1构成的二进制称为位（bit），八个位构成一个字节（Byte），1个Byte=8个bit。二进制、八进制、十六进制转化为十进制采用乘法，十进制转化为二进制、八进制、十六进制采用除法。数据的存放位置就是它的地址。【考点4】注释 是对程序的说明，可出现在程序中任意合适的地方，注释从“/*”开始到最近一个“*/”结束，其间任何内容都不会被计算机执行，注释不可以嵌套。【考点5】书写格式 每条语句的后面必须有一个分号，分号是语句的一部分。一行内可写多条语句，一个语句可写在多行上。 【考点6】标识符 是标识名字的有效字符序列，可以理解为C程序中的单词。 标识符的命名规则是： （1）标识符只能由字母、数字和下划线组成，字母区分大小写。 （2）标识符的第一个字符必须是字母或下划线，不能为数字。C语言标识符分如下3类 （1）关键字。它们在程序中有固定的含义，不能另作他用。 如：int、for、switch等。 （2）预定义标识符。预先定义并具有特定含义的标识符。 如：define、include等。 （3）用户标识符。用户根据需要定义的标识符，符合命名规则且不与关键字相同。【考点7】常量与变量 常量是指在程序运行过程中，其值不能改变的量。常量分为整型常量、实型常量、字符常量、字符串常量、符号常量5种。在程序运行过程中其值可以改变的量称为变量。C语言中没有字符串变量。存放字符串使用字符数组。【考点8】整型数据 整型常量有十进制、八进制、十六进制三种表示形式，没有二进制形式。八进制整型常量加前导数字0，十六进制常量加前导0X，八进制常量中不会出现8。 整型变量可分为基本整型（int）、短整型（short）、长整型（long）、和无符号整型（unsigned）。一个基本整型占4个字节。其它类型的整型占用字节数和取值范围详见教材第9页。【考点9】实型数据 实型数据有两种表示形式：小数形式和指数形式。掌握判定指数形式合法性。口诀：E前E后必有数，E前为实E后整数。 实型变量分为单精度型（float）和双精度型 （double），单精度型占四个字节。【考点10】算术运算 算术运算符一共有+、—、*、/、%这五个。求余运算要求运算对象只能为整型，除法运算符两边运算对象都为整型时，运算结果也为整型即舍掉小数部分。【考点11】强制类型转换 将一个运算对象转换成指定类型，格式为（类型名）表达式，注意小括号位置。【考点12】赋值 赋值运算符为“=”，不同于关系等于“= =”。赋值表达式格式为：变量名=表达式，赋值运算符左边必须为变量，赋值运算是把赋值运算符右边表达式的值赋给左边变量。 复合赋值运算符是将算术运算符或位运算符与赋值运算符组合在一起组成的运算符，掌握复合赋值表达式转化为赋值表达式的方法。如n+=100可转化为n=n+100。【考点13】自加自减运算 自加运算符“++”与自减运算符“--”是单目运算符，运算对象必须是变量。自增自减运算分前缀运算和后缀运算，它们所对应的表达式的值是有区别的，如j=i++;等价于j=i;i=i+1;而j=++i;等价于i=i+1;j=i。口诀：加加在前先加后用，加加在后先用后加。【考点14】逗号运算 逗号运算符运算优先级最低，可将多个表达式构成一个新的表达式。 第二章 顺序结构 【考点1】运算符、表达式、语句 运算对象加运算符构成表达式，表达式加分号构成表达式语句，运算对象可以是表达式、常量、变量。如赋值运算符加运算对象构成赋值表达式，赋值表达式加分号又可构成赋值语句。【考点2】运算符的优先级和结合顺序 运算符按参加运算的对象数目可分为单目运算符、双目运算符和三目运算符。初等运算符的优先级别最高，然后依次是单目运算符、算术运算符、关系运算符、逻辑运算符（除逻辑非！）、条件运算符、赋值运算符、逗号运算符。位运算符优先级介于算术运算符与逻辑运算符之间。结合顺序大多为自左向右，而自右向左的有三个：单目运算符、条件运算符和赋值运算符。 口决: 圆方括号、箭头一句号，自增自减非反负、针强地址长度，乘除，加减，再移位，小等大等、等等不等，八位与，七位异，六位或，五与，四或，三疑，二赋，一真逗。 其中“，”号为一个等级分段。【考点3】printf函数 格式为：printf(输出控制，输出列表)。输出控制是用一对双引号括起来的，包含格式说明和原样信息。输出列表包含若干输出项。【考点4】printf函数中格式说明 %d对应整型，%f对应单精度实型，%c对应字符型，%o对应八进制无符号整型，%x对应无符号十六进制整型，%u对应无符号整型，%e对应指数型，%s对应字符串型。可在%和格式字符之间加一个数来控制数据所占的宽度和小数位数。【考点5】scanf函数 输入项要求带取地址符&。当用键盘输入多个数据时，数据之间用分隔符。分隔符包括空格符、制表符和回车符，但不包括逗号。【考点】6如何交换两个变量 要使用中间变量，语句为：t=x;x=y;x=t; 第三章 选择结构 【考点1】关系运算 C语言用非0表示逻辑真，用0表示逻辑假。关系运算符有6个，分别是>，>=，<，<=，==，!=，前四种优先级高于后两种。关系表达式真时为1，假时为0。注意a 【考点2】逻辑运算 逻辑运算符共有3个：逻辑与（&&），逻辑或（||），逻辑非（!）。注意短路现象，例a++||b++，如果表达式a++的值非零，则表达式b++不再执行。【考点3】if语句 可以单独出现，也可以与else匹配出现。if语句可以嵌套，这时else总是与离它最近的且没有与else匹配的if匹配。【考点4】条件运算 是唯一的三目运算符，格式为：表达式1?表达式2:表达式3。表达式1值为非0时，整个表达式值为表达式2的值，表达式1值为0时，整个表达式值为表达式3的值。口诀：真前假后 【考点5】switch语句 格式及执行过程详见教材P43，要注意每条case后有没有break语句的区别。还要注意switch后小括号里面的表达式不能为实型，case后表达式不能有变量。口诀：switch表不为实，case表不为变。 第四章 循环结构 【考点1】三种循环结构 三种循环结构分别为：while，do-while，for，三种结构的格式及执行顺序详见教材第50、53、55页。注意for循环中的小括号中必须是两个分号；循环一定要有结束条件，否则成了死循环；do-while()循环最后的while()；后一定要有分号。【考点2】break与continue break是终止所在整个循环，而continue是提前结束本轮循环。break语句可出现在循环结构与switch语句中，continue只出现在循环结构中。【考点3】循环的嵌套 就是循环里面还有循环，计算要一层一层分析，一般只考查两层嵌套，循环嵌套通常是处理二维数组。 【考点4】循环结构的复习 循环结构是重点，笔试所占分值一般在13分左右，在上机考试中也是必考点，应用性很强。要求学员重点理解并多加练习，领会掌握。 第五章 字符型数据 位运算 【考点1】字符常量 一个字符常量用一对单引号括起来，字符常量只能包括一个字符，‟ab‟是非法的。空格常用‟□‟来表示。字符常量可用对应的ASCII码表示，需记住：‟0‟的ASCII码为48，‟A‟的ASCII码为65，‟a‟的ASCII码为97。 【考点2】转义字符 一对单引号中以一个反斜线后跟一个特定字符或八进制、十六进制数来构成转义字符。比如‟n‟表示换行，‟101‟或‟x41‟表示ASCII码为65的字符‟A‟。【考点3】字符型数据可以和整型数据相互转换 如：‟0‟-0=48 „A‟+32=‟a‟ char a=65;printf(“%d%c”,a,a);结果为65A 【考点4】位运算符 C语言提供6种位运算符：按位求反~，按位左移<<，按位右移>>，按位与&，按位异或|，按位或^。一般情况下需要先转化进制。异或运算的规则：0异或1得到1，0异或0得到0，1异或1得到0。可记为“相同为0，不同为1”。【考点5】putchar与getchar函数 可用于输出或输入单个字符，这两个函数是stdio.h文件中的库函数，它们是printf与scanf函数的简化。 第六章 函数 【考点1】函数的定义 函数是具有一定功能的一个程序块。函数的首部为：函数类型 函数名（类型1 形参1，类型2 形参2，……）。在函数定义中不可以再定义函数，即不能嵌套定义函数。函数类型默认为int型。【考点2】库函数 调用C语言标准库函数时要包含include命令，include命令行以#开头，后面是””或<>括起来的后缀为”.h”的头文件。以#开头的一行称为编译预处理命令行，编译预处理不是C语言语句，不加分号，不占运行时间。【考点3】函数的返回值 函数通过return语句返回一个值，返回的值类型与函数类型一样。return语句只执行一次，执行完或函数体结束后退出函数。【考点4】函数的声明 函数要“先定义后调用”，或“先声明再调用后定义”。函数的声明一定要有函数名、函数返回值类型、函数参数类型，但不一定要有形参的名称。【考点5】函数的调用 程序从上往下执行，当碰到函数名后，把值传给调用函数，当程序得到了返回值或调用函数结束，再顺序往下执行。【考点6】函数的参数及值传递 形式参数简称形参，是定义函数时函数名后面括号中的参数。实在参数简称实参，是调用函数时函数名后面括号中的参数。实参和形参分别占据不同的存储单元。实参向形参单向传递数值。“传值”与“传址”的区别：传数值的话，形参的变化不会改变实参的变化。传地址的话，形参的变化就有可能改变实参所对应的量。 【考点7】函数的递归调用 函数直接或间接地调用自己称为函数的递归调用。递归调用必须有一个明确的结束递归的条件。在做递归题时可把递归的步骤一步步写下来，不要弄颠倒了。【考点8】要求掌握的库函数 sqrt()算术平方根函数，fabs()绝对值函数，pow()幂函数，sin()正弦函数 第七章 指针 【考点1】指针变量 指针变量是用来存储地址的，而一般变量是存储数值的。指针变量可指向任意一种数据类型，但不管它指向的数据占用多少字节，一个指针变量占用四个字节。【考点2】指针变量的定义 格式为：类型名 *指针变量名。二维指针int **p;可以理解为基类型为(int *)类型。【考点3】指针变量的初始化 指针变量在使用前必须要初始化，把一个具体的地址赋给它，否则引用时会有副作用，如果不指向任何数据就赋“空值”NULL。【考点4】指针变量的引用 &是取地址符，*是间接访问运算符，它们是互逆的两个运算符。在指针变量名前加间接访问运算符就等价它所指向的量。【考点5】指针的运算 *p++和(*p)++之间的差别：*p++是地址变化，(*p)++是指针变量所指的数据变化。一个指针变量加一个整数不是简单的数学相加，而是连续移动若干地址。当两个指针指向同一数组时，它们可以比较大小进行减法运算。 第八章 数组 【考点1】数组的定义 数组是一组具有相同类型的数据的集合，这些数据称为数组元素。格式为：类型名 数组名[常量表达式]。数组的所占字节数为元素个数与基类型所占字节数的乘积。【考点2】数组的初始化 第一维长度可以不写，其它维必须写。int a[]={1,2};合法，int a[][3]={2,3,4};合法，int a[2][]={2,3,4};非法。数组初始化元素值默认为0，没有初始化元素值为随机。如在int a[5]={0,1,2};中，元素a[4]值为0；而在int a[5];中，元素a[4]值为一个不确定的随机数。【考点3】元素的引用 数组元素的下标从0开始，到数组长度减1结束。所以int a[5];中数组最后一个元素是a[4]。要把数组元素看作一个整体，可以把a[4]当作一个整型变量。【考点4】二维数组 数组a[2][3]={1,2,3,4,5,6};中含6个元素，有2行3列。第一行为a[0]行，第2行为a[1]行，a[0]、a[1]叫行首地址，是地址常量。*(a[0]+1)是第一行第一个元素往后跳一列，即元素a[0][1]值为2，*(a[0]+3)是第一行第一个元素往后跳三个，即元素a[1][0]值为4。【考点5】行指针 是一个指针变量，占四个字节，行指针指向一行连续数据，形式为：int(*p)[2];，p只能存放含有两个整型元素的一维数组的首地址。注意(*p)两边的小括号不能省略，否则就成了指针数组，是若干指针元素的集合。【考点6】数组名 数组名是数组的首地址。数组名不能单独引用，不能通过一个数组名代表全部元素。数组名是地址常量，不能对数组名赋值，所以a++是错误的。但数组名可以作为地址与一个整数相加得到一个新地址。 【考点7】元素形式的转换 助记：“脱衣服法则”a[2]变成*(a+2)，a[2][3]变成*(a+2)[3]再可变成*(*(a+2)+3)。 第九章 字符串 【考点1】字符串常量及表示 字符串常量是由双引号括起来的一串字符，如”ABC”。在存储字符串时，系统会自动在其尾部加上一个空值‟‟，空值也要占用一个字节，也就是字符串”ABC”需要占四个字节。【考点2】字符数组 C语言没有字符串变量，只能采用字符数组来存储字符串。数组的大小应该比它将要实际存放的最长字符串多一个元素，从而存放‟‟。【考点3】字符串赋值 可以用下面的形式进行赋值：char str[]=”Hello!”;或char *p;p=”Hello!”;，但不能用下面的形式：char str[10];str=”Hello”;因为str是一个地址常量，不能进行赋值操作。【考点4】字符串的输入与输出 可以用scanf和printf函数，如scanf(”%s”,str);，也可用专门处理字符串的两个函数gets和puts函数，还可以对字符数组逐个元素进行赋值，但一定要在最后赋一个‟‟。使用gets函数可以接收空格，使用puts函数在最后输出一个换行。【考点5】字符串函数 要掌握的四个字符串函数：字符串拷贝函数 strcpy（），求字符串长度函数strlen（），字符串链接函数strcat（），字符串比较函数strcmp（）。使用这些函数需在预处理部分包含头文件”string.h”。字符串长度要小于字符数组的长度，例：char str[10]=”Hello”;sizeof(str)的值为10（数组长度），strlen(str)的值为5（字符串长度）。这些函数是考试常用到的函数，大家一定要熟练应用这几个函数。 第十章 结构体与共用体 【考点1】结构体类型的说明 结构体是若干个类型数据的集合，结构体类型说明格式如下：struct 类型名 {类型1 成员名1;类型2 成员名2;……};，以上整个部分是一个数据类型，与整型的int是同样地位。可用typedef把结构体类型替换成一个只有几个字母的简短标识符。【考点2】结构体变量的定义 结构体变量是用说明的结构体类型所定义的一个变量，与结构体类型不是一回事。一个结构体变量所占字节数为其所有成员所占字节数之和。如struct stu{char name[10];int age;} a,b;则表明定义了两个结构体变量a,b,每个变量占14个字节。a,b与int i,j;中的变量i,j是同样地位。【考点3】结构体成员的引用 引用成员可用以下3种方式：（1）结构体变量名.成员名；（2）指针变量名->成员名：（3）（*指针变量名）.成员名。点（.）称为成员运算符，箭头（->）称为结构指向运算符。【考点4】链表 链表是由一个个结点构成的，一个结点就是一个结构体变量。每个结点可以分为数据域与指针域两个部分，数据域用来存放要存储的数据，指针域用来指向下一个结点。链表是考试中的难点，在C语言和公共基础部分都会考到，要领悟掌握。【考点5】共用体 共用体的使用格式与结构体相似，共用体定义的关键字为union，共用体所占字节数是所有成员中字节数最大的那个。 第十一章 文件 【考点1】文件类型指针 文件指针是一个指向结构体类型的指针，定义格式为：FILE *指针变量名。在使用文件时，都需要先定义文件指针。【考点2】文本文件与二进制文件 文本形式存放的是字符的ASCII码，二进制形式存放的是数据的二进制。例如“100”如果是文本形式就是存储‟1‟、‟0‟、‟0‟三个字符的ASCII码（00110001 00110000 00110000），如果是二进制形式就把100转化成二进制（01100100）。【考点3】打开文件 文件的打开形式如下：FILE *fp;fp=fopen(“c:lab.c”,”rb”)。fopen函数的前面一部分为文件名，后面一部分为文件的使用方式。打开方式详见教材第127页，其中r代表读，w代表写，a代表添加，b代表二进制位的。【考点4】文件函数 判断文件结束feof函数，移动文件指针位置fseek函数，获得文件位置ftell函数，文件位置移到开头rewind函数，文件字符输入输出fgetc函数和fputc函数，文件输入输出fscanf函数和fprintf函数，文件字符串输入输出fgets函数和fputs函数，读写二进制文件fread函数和fwrite函数。 以上函数要求知道格式会用，清楚是用于二进制文件还是文本文件，要把教材文件这章仔细复习下，不要在考试的时候把这些文件函数搞混了。 第十二章 深 入 讨 论 【考点1】编译预处理 凡以#开头的这一行，都是编译预处理命令行，编译预处理不加分号，不占运行时间。宏替换仅是简单的文本替换，如#define f(x)(x)*(x)和#define f(x)x*x替换f(2+2)时就有区别，前者展开为(2+2)*(2+2)，后者为2+2*2+2。如果源文件f2.c中有#include”f1.c”可以理解为把源文件f1.c原样包含到f2.c中，使f1.c和f2.c融合到一起成为一个C程序编译。所以一个C程序必有主函数，但一个C源文件未必有主函数。 【考点2】标识符作用域 局部变量是在函数内或复合语句内定义的变量，作用域为定义它的函数内。局部变量有三种类型：自动auto，寄存器register和静态static。 自动变量随着函数的使用与否创建消失；寄存器变量分配在cpu中，没有内存地址；静态变量占用固定存储单元，在程序执行过程不释放，直到程序运行结束。 全局变量是在函数外定义的变量，作用域从定义它的位置到整个源文件结束为止，生存期为整个程序运行期间。全局变量都是静态变量。【考点3】动态存储分配 malloc(size)用来创建连续size个字节存储区，返回值类型为void *型。malloc函数常用于动态创建链表结点;如int *p;p=(int *)malloc(sizeof(int))。 calloc（n,size）创建n个同一类型的存储空间，可以理解为n个malloc。free(p)释放动态分配的存储单元。 一、基本数据结构与算法 1.算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。 2.数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。 3.线性表的定义；线性表的顺序存储结构及其插入与删除运算。4.栈和队列的定义；栈和队列的顺序存储结构及其基本运算。5.线性单链表、双向链表与循环链表的结构及其基本运算。 6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。 二、程序设计基础 1.程序设计方法与风格。2.结构化程序设计。 3.面向对象的程序设计方法，对象，方法，属性及继承与多态性。 三、软件工程基础 1.软件工程基本概念，软件生命周期概念，软件工具与软件开发环境。2.结构化分析方法，数据流图，数据字典，软件需求规格说明书。3.结构化设计方法，总体设计与详细设计。 4.软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。 5.程序的调试，静态调试与动态调试。 四、数据库设计基础 1.数据库的基本概念：数据库，数据库管理系统，数据库系统。2.数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型。 3.关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。4.数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。 基 本 要 求 1.熟悉Visual C++6.0集成开发环境。 2.掌握结构化程序设计的方法，具有良好的程序设计风格。3.掌握程序设计中简单的数据结构和算法并能阅读简单的程序。 4.在Visual C++6.0集成环境下，能够编写简单的C程序，并具有基本的纠错和调试程序的能力。 一、C语言的结构 1.程序的构成，main函数和其他函数。2.头文件，数据说明，函数的开始和结束标志。3.源程序的书写格式。4.C语言的风格。 二、数据类型及其运算 1.C的数据类型（基本类型、构造类型、指针类型、空类型）及其定义方法。2.C运算符的种类、运算优先级和结合性。3.不同类型数据间的转换与运算。 4.C表达式类型（赋值表达式，算术表达式，关系表达式，逻辑表达式，条件表达式，逗号表达式）和求值规则。 三、基本语句 1.表达式语句，空语句，复合语句。 2.输入与输出函数的调用，正确输入数据并正确设计输出格式。 四、选择结构程序设计 1.用if语句实现选择结构。 2.用switch语句实现多分支选择结构。3.选择结构的嵌套。 五、循环结构程序设计 1.for循环结构。 2.while和do-while循环结构。3.continue语句和break语句。4.循环的嵌套。 六、数组的定义和引用 1.一维数组和二维数组的定义、初始化和数组元素的引用。2.字符串与字符数组。 七、函数 1.库函数的正确调用。2.函数的定义方法。3.函数的类型和返回值。 4.形式参数与实在参数，参数值的传递。5.函数的正确调用，嵌套调用，递归调用。6.局部变量和全局变量。 7.变量的存储类别（自动，静态，寄存器，外部），变量的作用域和生存期。 八、编译预处理 1.宏定义和调用(不带参数的宏，带参数的宏)。2.“文件包含”处理。 九、指针 1.地址与指针变量的概念，地址运算符与间址运算符。 2.一维、二维数组和字符串的以及指向变量、数组、字符串、函数、结构体的指针变量的定义。通过指针引用以上各类型数据。3.用指针作函数参数。4.返回地址值的函数。5.指针数组，指向指针的指针。 十、结构体（即“结构”）与共用体（即“联合”） 1.用typedef说明一个新类型。 2.结构体和共用体类型数据的定义和成员的引用。 3.通过结构体构成链表，单向链表的建立，结构点的输出、删除与插入。 十一、位运算 1.位运算符的含义及使用。2.简单的位运算。 十二、文件操作 【c语言排序算法总结】推荐阅读： 排序算法总结09-26 python选择排序算法实例总结10-06 c语言总结07-15 c语言实验报告总结07-13 计算机二级考试C语言知识点总结09-13 规律排序教案06-17 c语言概念题09-22 C语言教学建议10-25 c语言递归程序11-06 c语言设计程序11-11c语言总结 篇5
