数据结构与算法(C语言)
20131007 · 共 86 篇文章
C语言退出多层嵌套循环技巧
由于break语句只能影响它的最内层循环,要想立即从深层嵌套循环中退出,有哪些方法呢? 1、使用goto语句: while(condition1) { while(condition2) { while(condition3) { if(some disaster) goto quit; } } } quit:; 要想在这种情况下避免使用goto语句,可以考虑以下两种方案: 2、设置状态标志: 当你希望退出所有循环时设置一个状态标志,但这个标志在每个循环中都必须进行测试: enum{EXIT, OK}status; ... status = OK; while(status == OK &&…
2014-04-24 11:33 · C语言 · 评论(0)
C语言实现泛型编程
泛型编程让你编写完全一般化并可重复使用的算法,其效率与针对某特定数据类型而设计的算法相同。在C语言中,可以通过一些手段实现这样的泛型编程。这里介绍一种方法——通过无类型指针void* 看下面的一个实现交换两个元素内容的函数swap,以整型int为例: void swap(int* i1,int* i2){ int temp; temp = *i1; *i1 = *i2; *i2 = temp; } 当你想交换两个char类型时,你还得重写一个参数类型为char的函数,是不是能用无类型的指针来作为参数呢?看如下改动: void swap(void *vp1,void *vp2){ void t…
2014-04-24 11:21 · C面向对象编程 · 评论(0)
C语言函数指针的用法
函数指针 是一种在C、C++、D语言、其他类 C 语言和Fortran 2003中的指针。函数指针可以像一般函数一样,用于调用函数、传递参数。在如 C 这样的语言中,通过提供一个简单的选取、执行函数的方法,函数指针可以简化代码。 函数指针只能指向具有特定特征的函数。因而所有被同一指针运用的函数必须具有相同的参数和返回类型。 下面的代码说明了一种初始化函数指针的方法: int f(int); int (*fp)(int) = &f; //使用三种方式调用函数 int ans; ans = f(25); ans = (*pf)(25); ans = pf(25); 以下为函数指针在C中的简单运用…
2014-04-24 11:06 · C语言 · 评论(0)
遍历二叉树的递归与非递归算法
利用递归实现二叉树的先序,中序,后序遍历操作 /* 先序、中序、后序递归遍历二叉树算法 */ void PreOrder(BiTree T) //先序遍历 { if(T != NULL) { visit(T); //访问根节点 PreOrder(T -> lchild); //递归遍历左子数 PreOrder(T -> rchild); //递归遍历右子数 } } void InOrder(BiTree T) //中序遍历 { if(T != NULL) { InOrder(T -> lchild); visit(T); InOrder(T -> rchild); } } void Post…
2013-12-20 11:00 · 算法设计(C语言) · 评论(0)
堆排序
堆排序 (Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足 堆积的性质 :即子结点的键值或索引总是小于(或者大于)它的父节点。 堆节点的访问 通常堆是通过一维数组来实现的。在起始数组为 0 的情形中: 父节点i的左子节点在位置 (2*i+1); 父节点i的右子节点在位置 (2*i+2); 子节点i的父节点在位置 floor((i-1)/2); 堆的操作 在堆的数据结构中,堆中的最大值总是位于根节点。堆中定义以下几种操作: 最大堆调整(Max_Heapify):将堆的末端子节点作调整,使得子节点永远小于父节点 创建最大堆(Build_Ma…
2013-12-12 10:56 · 算法设计(C语言) · 评论(0)
希尔排序
希尔排序 ,也称 递减增量排序算法 ,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。 希尔排序是基于插入排序的以下两点性质而提出改进方法的: 插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率 但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位 算法实现 原始的算法实现在最坏的情况下需要进行 O ( n 2)的比较和交换。V. Pratt的书对算法进行了少量修改,可以使得性能提升至O( n log2 n )。这比最好的比较算法的O( n log n )要差一些。 希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个…
2013-12-12 10:12 · 算法设计(C语言) · 评论(0)
插值查找算法
#include<stdio.h> #include<string.h> #include<math.h> #include<ctype.h> #include<stdbool.h> int Insert_search(int *a, int key, int n) { int pos, low, high; low = 0,high = n - 1; while(low <= high){ pos = ((key - a[low]) * (high - low )) / (a[high] - a[low]) + low; if(a[pos] < key){ low = pos + 1; }…
2013-12-11 22:31 · 算法设计(C语言) · 评论(0)
斐波那契查找算法
斐波那契查找的核心是: 1)当key=a[mid]时,查找成功; 2)当key<a[mid]时,新的查找范围是第low个到第mid-1个,此时范围个数为F[k-1] - 1个,即数组左边的长度,所以要在[low, F[k - 1] - 1]范围内查找; 3)当key>a[mid]时,新的查找范围是第mid+1个到第high个,此时范围个数为F[k-2] - 1个,即数组右边的长度,所以要在[F[k - 2] - 1]范围内查找。 #include<stdio.h> #include<string.h> #include<math.h> #include<ctype.h> #include<s…
2013-12-11 20:55 · 算法设计(C语言) · 评论(0)
折半查找算法
在计算机科学中,折半搜索,也称二分查找算法、二分搜索,是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。 复杂度分析 时间复杂度折半搜索每次把搜索区域减少一半,时间复杂度为。(n代表集合中元素的个数)空间复杂度 。虽以递归形式定义,但是尾递归,可改写为循环。 #include<stdio.h> #include<string.…
2013-12-11 20:52 · 算法设计(C语言) · 评论(0)
直接插入排序
直接插入排序(Insertion Sort)的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中的适当位置,直到全部记录插入完成为止。 设数组为a[0…n-1]。 1. 初始时,a[0]自成1个有序区,无序区为a[1..n-1]。令i=1 2. 将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。 3. i++并重复第二步直到i==n-1。排序完成。 #include<stdio.h> #include<string.h> #include<math.h> #include<ctype.h> #include<stdbool.h> #incl…
2013-12-11 01:05 · 算法设计(C语言) · 评论(0)
Gnome排序
Gnome排序(地精排序),起初由Hamid Sarbazi-Azad 于2000年提出,并被称为stupid排序,后来被Dick Grune描述并命名为“地精排序”,作为一个排序算法,和插入排序类似,除了移动一个元素到最终的位置,是通过交换一系列的元素实现,就像冒泡排序一样。概念上十分简单,不需要嵌套循环。时间复杂度为O ,但是如果初始数列基本有序,时间复杂度将降为O(n)。实际上Gnome算法可以和插入排序算法一样快。平均运行时间为O . Gnome排序算法总是查找最开始逆序的一对相邻数,并交换位置,基于交换两元素后将引入一个新的相邻逆序对,并没有假定当前位置之后的元素已经有序 Desc…
2013-12-11 01:03 · 算法设计(C语言) · 评论(0)
选择排序
选择排序 (Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。 选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。 #include<stdio.h> #include<stri…
2013-12-10 15:08 · 算法设计(C语言) · 评论(0)
Bogo排序
在计算机科学中, Bogo排序 (bogo-sort)是个既不实用又原始的排序算法,其原理等同将一堆卡片抛起,落在桌上后检查卡片是否已整齐排列好,若非就再抛一次。其名字源自Quantum bogodynamics,又称bozo sort、blort sort或猴子排序. #include<stdio.h> #include<string.h> #include<math.h> #include<ctype.h> #include<stdbool.h> #include<stdlib.h> #include<time.h> void swap(int *a, int *b) //交换两元素的值…
2013-12-10 15:05 · 算法设计(C语言) · 评论(0)
Stooge 排序
Stooge排序是一种低效的递归排序算法,甚至慢于冒泡排序。在《算法导论》第二版第7章(快速排序)的思考题中被提到,是由Howard、Fine等教授提出的所谓“漂亮的”排序算法。 实现 如果最后一个值小于第一个值,则交换它们 如果当前子集元素数量大于等于3: 使用Stooge排序前2/3的元素 使用Stooge排序后2/3的元素 再次使用Stooge排序前2/3的元素 #include<stdio.h> #include<string.h> #include<math.h> #include<ctype.h> #include<stdbool.h> void swap(int *a, int…
2013-12-10 14:46 · 算法设计(C语言) · 评论(0)
快排序
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要 Ο (n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。 算法 快速排序采用一种“分而治之、各个击破”的观念。 快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。 步骤为: 从数列中挑出一个元素,称为 "基准"(pivot), 重新排序数列,所有元素比基准值小的摆放在基准…
2013-12-10 14:42 · 算法设计(C语言) · 评论(0)