数据结构-几个经典例子

作为一个程序员需要对算法和数据结构具有一定理论和经验的基础。

在程序员的经典教程中很多人提到 算法+数据结构=程序设计。

如果你想要在开发这一行谋求很好的发展，这个基础是一定要打好的。本文中讲述的都是一些基础知识但是对写好程序至关重要的。

我们写程序的目的是要通过程序描述外部世界的事物，而数据结构就是对外在世界的信息方面的抽象，而算法是在数据集基础上的遍历和操作。这些东西在离散数学中都有所描述。

在面向过程的程序设计达到一定水平之后，才使构造一定复杂程度的系统成为可能。我在实际项目中看到有些程序员写超过6级的For 语句循环和结构很复杂的函数。这些都需要加强算法和基础理论的修养才能达到。

面向对象的设计思想是另外的一种设计思想但是对对象世界的规划也是建立在理论能力基础上的。

我的建议在学习数据结构和算法的时候，需要理论结合实践。有些东西看过一遍之后 觉得自己掌握了，但是如果自己没有动手写程序之前，对算法的理解还是很浅的，而且很容易忘记，另外就是很多时候对于一些算法如递归，很多和我交流的人都是看的时候明白实际上完全没有掌握。

我个人学习过程中获益最深的几个程序包含：

1、  八后问题

在一个８Ｘ８国际象棋盘上放８个王后，并且所有的王后相互不能杀（国际象棋棋子摆在方格内，王后可以杀横向和纵向和两个４５度角上的所有子）。

我刚学编程的时候花了一个星期苦思冥想，当时主要是用递归后来写出来死机（哈哈）后来上课老师讲回溯方法。这里我就基础的递归算法　和八后的递归和回溯算法都写一下（我建议只要真正想搞好编程的人要把这两种方法都掌握好）

数据结构

一个 8个整形长度的数组 表示棋盘的当前状态，有些人可能考虑8X8 的数组（不是不可以，我一开始学程序时也是这样的，但是既然8个的数组就可以了，何必多用，small is beautiful ）.

一个整形 int current （0 ——7）表示当前有效的行。

回溯算法

在 讲八后的这个问题的时候顺便说一下 自顶向下的程序设计思想。（强烈建议一定要掌握 自顶向下的程序设计思想，这个是非常重要的）

首先确定自己的初步思想：

第一遍

开始准备

当没有结束的时候

如果 当前的棋盘状态没有冲突

如果达到了8行打印

否则 到下一行

否则把本行的棋子向下移一个子，如果当前的子已经超过8个了 退到上一行

然后根据初步设计进行细化

 

current=0;
         For (int i=0;i<8;i++) array\[i\]=0; // 实际这行没有用 Current=0; Array\[Current\]=0; //在第一行第一列放一个后 While(current>=0) //当退回到第一行的前面时结束
                 {
                       If（CheckOk()） //函数未细化
{
       If (current>7)
{
Print();// 8行摆完打印
BackLine(); //回退一行
} else
{
         NextLine();//进一行
}
}else
{
    If (Array\[Current\]>7) //到最下面了，仍然不能满足需要退回一行
       BackLine();
    Else Array\[Current\]++;
}
}

最后把 所有的函数写完

Void BackLine()
{
Current--;
}
Void NextLine()
{
  Array\[++Current\]=0;
}
Bool CheckOk()
{
   For (int i=0;i<Current;i++)
{
   For (int j=0;j<I;j++)
{
If ((Array\[i\]==Array\[j\])     //同列
||Array\[i\]+i==Array\[j\]=j）//一侧斜线
||Array\[i\]+j==Array\[j\]+i) //另一侧斜线
Return false;
}
}
Return true;
}

2、 跳马问题 自掌握了回溯问题后，好像所有的问题都能解决了。这个问题老师点拨了一下就会了，但是使用这个方法真的可以解决很多问题的。 3、 其他 使用回溯方法的其他著名问题有　旅行商问题　还有递归的汉诺塔问题。还有一个比较困难的问题　希望可以帮大家拓展一下关于算法的思路。 一个数可以拆成多种方式相加　比如５可以分成5, 4+1,3+2,3+1+1,2+2+1 ,2+1+1+1,1+1+1+1+1 共7种方式。写一个函数可以算出所有的数的拆法有多种。 （请自己仔细考虑后，在看相关的算法） 这个问题很多人用很多的方法来算，这里介绍一个比较简单的

Function Split(int num,int min)
{
  Int sum=1;
  For (int i=min;i<num/2;i++)
{
   Sum+=Split(num-i,i);
}
     Return sum;
}

５的拆法是 Split(5,1) 参数的含义　第一个参数表示　需要被拆的数，后面表示这个数拆出的数不得小于的大小。