数据结构-C语言描述(第三版)第1章概论.ppt

1.3.2 实现数据结构 　　实现一个数据结构必须首先确定数据的存储表示，然后在给定的存储方式下实现相应的运算。本书中，C语言的结构、数组、指针等被用于描述数据的存储表示。这里，不妨假定C语言的数组和结构都是顺序存储的：认为数组元素具有相同的数据类型，按照下标的次序存储在连续的存储区；结构可以由不同类型的域(成分)组成，按照域表的次序顺序存放。借助于C语言的数组、结构和指针可以描述和实现本书讨论的数据结构的各种不同的存储表示。 　　C语言也被用于描述运算的算法。当一个算法采用程序设计语言描述时，需要了解算法足够多的实现细节，这有些麻烦。所幸的是书中算法的C程序都较短，不至掩盖算法实质，由此带来的好处是有助于提高学生C语言程序设计的能力。 　　程序1－1是复数ADT的C语言实现。代码可分为两部分：复数结构类型和实现复数运算的C函数。注意区分Complex和complex。此处complex是结构名，不是类型名，它只是一个结构标记。程序1－1首先采用typedef将复数ADT Complex的存储表示描述为一个C语言的结构，然后给出实现各个运算的算法。程序1－1中，运算Add由一个C函数实现。用同样的方法可以写出其他运算的实现代码。 　 【程序1－1】 Complex的实现。 　　 #include stdio.h 　　 #include stdlib.h 　　 typedef struct complex 　　 { 　　 float x,y; 　　 }Complex; 　　 Complex CreateComp(float x,float y) 　 { 　　　　Complex c; 　　　　c.x=x;c.y=y; 　　　　return c; 　　} 　　 Complex Add (Complex a,Complex b) 　　 { 　　 Complex c; 　　 c.x=a.x+b.x; 　　 c.y=a.y+b.y; 　　 return c; 　　 } … 　　一旦实现Complex的全部运算，我们便可在主函数或其他应用程序中使用Complex的运算进行复数计算。一个简单的测试程序见程序1－2。程序1－2中还需要使用函数void PrintComplex(Complex a)。从封装和信息隐蔽的角度看，也应将这一运算添加到ADT 1－1中，并在程序1－1中实现之。 　　【程序1－2】 测试复数加法运算。 　　void PrintComplex(Complex a) 　 { 　　 printf(%3.2f+ %3.2fi \n,a.x,a.y); 　　} 　　void main() 　　 { 　　 Complex a,b,c; 　　 a=CreateComp(1.0f,2.0f); /*构造复数a=(1+2i) */ 　　 b=CreateComp(3.0f,4.0f); /*构造复数 b=(3+4i)*/ 　　 c=Add(a,b); /*复数c=a+b */ 　　 PrintComplex(a); PrintComplex(b); 　　 PrintComplex(c); 　 } 1.4 算法和算法分析 1.4.1 算法及其性能标准 　　什么是算法？笼统地说，算法是求解一类问题的任意一种特殊的方法。较严格的说法是：一个算法(algorithm)是对特定问题的求解步骤的一种描述，它是指令的有限序列。此外，算法具有下列五个特征： 　　(1) 输入(input)：算法有零个或多个输入。 　　(2) 输出(output)：算法至少产生一个输出。 　　(3) 确定性(definite)：算法的每一条指令都有确切的定义，没有二义性。 　　(4) 能行性(effective)：算法的每一条指令都足够基本，它们可以通过执行有限次已经实现的基本运算来实现。 　　(5) 有穷性(terminative)：算法总能在执行有限步之后终止。 　　凡是算法，都必须满足以上五条特征。对于书中讨论的数据结构上定义的运算，我们将讨论实现它们的相应算法。 　　描述一个算法有多种方法，它可以用自然语言、流程图或程序设计语言来描述。当一个算法直接使用计算机程序设计语言描述时，该算法便成为程序。算法必须可终止，但计算机程序并没有这一限制，比如操作系统是一个程序，但不是一个算法。本书中，我们使用C语言描述算法，当然只有当了解了算法的足够多的实现细节后，才能写成程序，同时，这也使得对算法的性能分析往往成为对相应程序的性能分析。