数据结构初探--什么是数据结构？

一、什么是数据结构？

　　“数据结构（data structure）是计算机中存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来最优效率的算法。”　　　　　　　　　　----Wikipedia

　　没有统一的定义，但是却与数据在计算机中的存储以及查找调用密切相关，同时也决定了一个程序的运行效率。

　　众所周知，程序 = 数据结构 + 算法，那么数据结构在程序设计里的重要性可见一斑。

-------------------------------------------------------------------Gracefful Line--------------------------------------------------------

　　首先，举几个栗子----如何将书摆放在书架上？

　　我想没有所谓的正确答案，因为方法无数多种......

　　那么问题来了，怎样摆放才是最方便有效的呢？

图书拜访需要两个主要的操作步骤：

　　1：新书如何插入？

　　2：如何找到某本指定的书？

最实用的便是将图书分门别类，将一个大的存储空间划分为恰当的块，然后在新书来到时，首先找到它所属的类别，再进行插入。而插入是应用二分查找法来查找空位，移除空位将其插入。
查找时自然也是相似的，先找类别，再二分查找到某一本书。

+ 解决问题方法的效率，跟数据的组织方式有关---如何分类，并将种类细化到怎样的程度就是决定图书资源能否被高效利用的关键。

例2：写程序实现一个函数PrintN，使得传入一个正整数为N的参数后，能顺序打印从1到N的全部正整数

　　有两种简单方法：循环实现&递归实现

1 void PrintN ( int N )
2 {     int i;
3        for ( i=1; i<=N; i++ ) 
4     {
5        printf(“%d\n”, i );
6      }
7        return 0;
8 }//--------------------------1：循环实现

1 void PrintN ( int N )
2 {     
3     if ( N )
4     {
5         PrintN( N – 1 );
6         printf(“%d\n”, N );
7     }
8     return 0;
9 } //--------------------------2：递归实现

那么当程序在实际运行过后发现，当N为较小数字时，木有任何问题。若N = 100000时，递归程序就崩溃了，为什么呢？不是很好的一种方法吗？

答案就在于递归这种方法会耗费大量的存储空间。由于递归的本质是先逆推再正向计算，那么在逆推过程中需要占用大量存储空间，导致程序运行空间不足，使得程序无法达到预期的目的。

+ 解决问题方法的效率，跟空间的利用效率有关-----递归方法在使用时占用大量存储空间，有些时候可能效率会远不及简单的方法，空间利用效率也是决定数据资源能否被高效利用的关键。

Q:那么日常编程时如何测试自己的方法是否高效呢？

　　使用时钟函数clock()：捕捉从程序开始运行到clock()被调用时所耗费的时间。这个时间单位是clock tick，即“时钟打点”。常数CLK_TCK(或CLOCKS_PER_SEC)：机器时钟每秒所走的时钟打点数。（需在头文件中加入#include<time.h> ）。当时间过快时可以重复多次求平均值比较。

代码模板如下：

 1 #include <stdio.h>
 2 #include <time.h>
 3 
 4 clock_t start, stop;    /* clock_t是clock()函数返回的变量类型 */
 5 
 6 double duration;  /* 记录被测函数运行时间，以秒为单位 */
 7   
 8 int main ()
 9 {    
10     /* 不在测试范围内的准备工作写在clock()调用之前*/
11     start = clock();　　/* 开始计时*/
12     MyFunction();　　　　/* 被测函数*/
13     stop = clock();　　　/* 停止计时*/
14     duration = ((double)(stop - start))/CLK_TCK;
15     /* 其他不在测试范围的处理写在后面，例如输出duration的值*/
16     return 0;
17 }

+ 解决问题方法的效率，跟算法的巧妙程度有关-------可尝试多种方法实现，然后择优。

二、抽象数据类型（Abstract Data Type ）

 数据类型

　　 数据对象集

　　 数据集合相关联的操作集

 抽象：描述数据类型的方法不依赖于具体实现

　　 与存放数据的机器无关

　　 与数据存储的物理结构无关

　　 与实现操作的算法和编程语言均无关

注：只描述数据对象集和相关操作集 “是什么 ”，并不涉及 “如何做到 ”的问题。

-------------------------------------------------------------------Gracefful Line--------------------------------------------------------

　　　　　　　　　　　　　　　　　　　　　　　计算机小白的蜕变之路，艰辛亦单调，果断亦决绝。

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　敬请批评指正！

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　---yuhaow

数据结构初探--什么是数据结构？

推荐阅读