基础知识

来自软件实验室
Lisongyang讨论 | 贡献2015年11月24日 (二) 09:14的版本 基础算法

跳转至: 导航搜索

计算机体系结构

C语言

基础算法

排序

  • 最快最简单的排序--桶排序
     直观的说,使用一个适当长度的一维数组,当数字出现一次的时候,就将对应数组下标的值加1,最后直接输出数组中非零值的数组下标,即为桶排序!
代码如下: 文件:BucketSimple.c
  • 选择排序
     基本思想就是:每次遍历,只选择最值元素进行交换,这样一次遍历,只需进行一次交换即可,从而避免了其它无价值的交换操作。
     具体方法为:
     遍历一次,记录下最值元素所在位置,遍历结束后,将此最值元素调整到合适的位置
     这样一次遍历,只需一次交换,便可将最值放置到合适位置
     文件:ChooseSort.c
  • 冒泡排序
     冒泡排序的基本思想是,每次比较两个相邻的元素,如果它们的顺序错误就把它们交换过来!
代码如下: 文件:BubbleSort.c
  • 快速排序
     快速排序采用的思想是分治思想。
     快速排序是找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值,如此作为基准的元素调整到排序后的正确位置。递归快速   排序,将其他n-1个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正 确位置,排序完成。所以快速排序算法的核心算法是分区操作,即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。
      举例说明一下吧,这个可能不是太好理解。假设要排序的序列为
       2 2 4 9 3 6 7 1 5 首先用2当作基准,使用i j两个指针分别从两边进行扫描,把比2小的元素和比2大的元素分开。首先比较2和5,5比2大,j左移
       2 2 4 9 3 6 7 1 5 比较2和1,1小于2,所以把1放在2的位置
       2 1 4 9 3 6 7 1 5 比较2和4,4大于2,因此将4移动到后面
       2 1 4 9 3 6 7 4 5 比较2和7,2和6,2和3,2和9,全部大于2,满足条件,因此不变
       经过第一轮的快速排序,元素变为下面的样子
       [1] 2 [4 9 3 6 7 5]
     之后,在把2左边的元素进行快排,由于只有一个元素,因此快排结束。右边进行快排,递归进行,最终生成最后的结果。
代码如下: 文件:QKSORT.c


搜索

  • 深度优先搜索
   最直观的例子是,往盒子中放置扑克牌。
   假设你手中有三张扑克牌,前面有三个盒子,将这三张牌放入盒子中,有多少排列组合?首先先将三张牌随机放入三个盒子,放完后后续没有盒子了。
然后回到第三个盒子取出牌,再回到第二个盒子取出牌,这时你手中有两张牌。再按照与第一次放牌顺序不同的方式往两个盒子中再放一次,形成另外一种不同的放牌组合。
这个算法用到了递归的思想。伪算法演示: //深度优先搜索的基本模型 void dfs(int step) { 判断边界 尝试每一种可能 for(i=1;i<=n;i++) { 继续下一步,有个递归调用dfs(step+1); } 返回 } 代码如下: 文件:DFS.c


  • 广度优先搜索
   如果说,深度优先搜索是一条道走到黑,广度优先搜索就是在每一个层面上先考虑周全后再走向下一个层面。
典型的应用就是走迷宫,从第一个点开始,向各个方向找可走的路径,未碰到障碍物就是可走的路径,若碰到障碍物就是不可走的路径。
一层一层的走下来,直到到达最后的目的地! 代码如下: 文件:BFS.c

数据结构

准备内容

注意:看下面内容之前,建议先复习下c语言基本知识,可以参考郝斌的c大纲。

  1. 指针
  2. 结构体
  3. 动态内存分配

数组

文件:Arr.cpp

链表

文件:List.cpp

链表的应用

  文件:Stack.cpp
  • 队列
    • 链式队列
    • 循环队列
   文件:CircleQueue.cpp

线性结构和非线性结构的分界线


补充内容

软件工程基本概念

设计模式

番外篇

看懂一个程序的步骤

  • 流程
首先搞明白程序中语句的执行顺序。
  • 语句功能
需要在搞明白流程的基础上,看每个类,每个方法中每条语句的功能以及执行后产生的结果。PS:单步调试是个好方式
  • 试数
将自己虚拟的一些符合程序定义的数据带入程序中,看执行后的结果如何!

预防因数组下标越界导致程序出错的问题

典型的例子就是使用for循环的时候,当遍历一个数组中的所有元素时,例如


int a[4] ={1,2,3,4};

int i;

for(i = 0; i < 4;i++) {

   // do Somethings...

}


在这里使用的是i<4而不是i<=3,我们以高等数学中的一张图来解释:

数组内容表示.png

按照图示内容进行分析可以尽量避免数组越界导致的一些问题!