C数据结构导论基本概念.doc

概念部分 CH1 绪论 数据的逻辑结构 线性结构树结构图结构。 线性结构具有的特性是：数据集合的第一个数据元素没有前驱数据元素，最后一个数据元素没有后继数据元素，其他的每个元素只有一个前驱元素和一个后继元素。 树结构具有的特性是：数据集合有一个特殊的数据元素称为根（root）结点，它没有前驱数据元素；树中其他的每个数据元素都只有一个前驱数据元素，可有零个或若干个后继数据元素。 图结构具有的特性是：数据集合的每个数据元素可有零个或若干个前驱数据元素，可有零个或若干个后继数据元素。 数据的存储结构 顺序存储结构链式存储结构。 顺序存储结构将数据集合的元素存储在一块地址连续的内存空间中，并且逻辑上相邻的元素在物理上也相邻。例如，用C 语言中的数组可以实现顺序存储结构，数组元素之间的顺序体现了线性结构中元素之间的逻辑次序，数据元素的存储位置由其在集合中的逻辑位置确定。 链式存储结构使用称为结点（node）的扩展类型存储各个数据元素，结点由数据元素域和指向其他结点的指针域组成，链式存储结构使用指针将相互关联的结点链接起来。数据集合中逻辑上相邻的元素在物理上不一定相邻，元素间的逻辑关系表现在结点的链接关系上。 在顺序存储结构中，所有分配的存储空间都被数据元素占用了；而在链式存储结构中，每个结点至少由两部分组成：数据域和指针域，数据域保存数据，指针域指向相关结点。指针域保存指向相关结点的链信息，因此又称为链域。 算法与算法分析 算法（Algorithm）是对特定问题求解过程的一种描述，是解决该问题的一个确定的、有限长的操作序列。 算法的规则具有如下5 个重要特征：确定性 可行性 有穷性 有输入 有输出。 算法可用文字、流程图、高级程序设计语言或类同于高级程序设计语言的伪码描述。 一个好的算法设计应达到以下目标：正确性 可读性 健壮性 高效性 算法的时间复杂度：算法的执行时间是算法所处理的数据个数n 的某种函数，表示为O(f(n))。弱类型的语言的东西没有明显的类型,他能随着环境的不同,自动变换类型强类型不同类型间的操作有严格定义,只有相同类型的变量才能操作,虽然系统也有一定的默认转换,当绝没有弱类型那么随便[修饰符] class 类名 [: 基类名] 包含类主体的类结构如下： 类声明 { 数据成员声明 方法成员声明 } 声明字段成员必须给出变量名及其所属的类型，同时还可以指定其他特性。其格式如下： [修饰符] [static] 变量类型 变量名 声明方法成员的格式如下： [修饰符] [static] 返回值类型 方法名 (参数列表) { 方法体 } 属性提供对类的某个特征的访问。一个属性可以有 2 个访问操作符，分别是 get 和 set，它们分别指定属性读取或写入新值的方式。其格式如下： [修饰符] [static] 类型 属性名 { get {属性读取过程} set {写入新属性值的过程} } 属性的声明方式和方法非常相似，区别在于它没有使用括号，也不能使用显式的参数。对象的创建和使用： 对象声明的格式：类名 对象名; 在声明对象的同时可以使用 new 操作符创建对象，其格式如下： 类名 对象名 = new 与类名相同的构造方法(参数列表); Eg. Stack s = new Stack(); 通过对象引用类的成员变量的格式为： 对象名.成员名 通过对象调用成员方法的格式为： 对象名.方法名（参数列表） 多态： 一个方法可能有多个版本，一次单独的方法调用（invoke）可能是这些版本中的任何一种。多态性有两种表现形式：方法的重载和方法的覆盖。 一个类中如果有许多同名的方法带有不同的参数，称为方法的重载。重载的价值在于，它允许通过使用一个普通的方法来访问一系列相关的方法。当调用一个方法时，具体调用哪一个方法根据调用方法的参数由编译程序决定，编译程序将选择与调用的实参相匹配的重载方法。 C#通过为方法的定义引入 virtual（虚方法）和 override（方法覆盖/重写）提供父子类间方法继承的机制。当一个虚方法被调用时，该类的实例的运行时类型(run-time type)决定哪个方法体被调用。 C#的数据类型 两大类：值类型，引用类型。值类型的变量本身包含他们的数据，而引用类型的变量包含的是实际数据的引用或者叫句柄，即它是对真正包含数据的内存块的指向，类似于C++语言中的指针。值类型：结构类型：简单类型可分为布尔类型（bool），字符类型（char）和数值类型；用户自定义类型。 引用类型:类（class），接口（interface），数组（array）和委派（delegate）。loat浮点型 32-bit 单精度浮点数 double双精度浮点型 64-