数据结构与算法
数据结构与算法
《数据结构》这门课程的目的有三个。第一个是讲授常用的数据结构，这些数据结构形成了程序员基本数据结构工具箱(toolkit)。对于许多常见的问题，工具箱里的数据结构是理想的选择。就像.NET Framework 中 Windows 应用程序开发中的工具箱，程序员可以直接拿来或经过少许的修改就可以使用，非常方便。第二个是讲授常用的算法，这和数据结构一样，是人们在长期实践过程中的总结，程序员可以直接拿来或经过少许的修改就可以使用。可以通过算法训练来提高程序设计水平。第三个目的是通过程序设计的技能训练促进程序员综合能力的提高。
数据结构是程序员的内功修炼的一部分
基本概念和术语
1、 数据(Data)计算机程序处理各种各样的数据，可以是数值数据，如整数、实数或复数；也可以是非数值数据，如字符、文字、图形、图像、声音等。
2、 数据元素(Data Element)和数据项(Data Item)
单位，数据项有时也称为字段(Field)或域(Domain)。例如，一条学生记录就是一个数据元素。这条记录中的学生学号、姓名、性别、籍贯、出生年月、成绩等字段就是数据项。数据项分为两种，一种叫做初等项，如学生的性别、籍贯等，在处理时不能再进行分割；另一种叫做组合项，如学生的成绩，它可以再分为数学、物理、化学等更小的项。
3、 数据对象(Data Object)
数据对象是性质相同的数据元素的集合， 是数据的一个子集。例如，整数数据对象是{0,±1,±2,±3,…}，字符数据对象是{a,b,c,…}。
4、 数据类型(Data Type)
数据类型是高级程序设计语言中的概念，是数据的取值范围和对数据进行操作的总和。数据类型规定了程序中对象的特性。程序中的每个变量、常量或表达式的结果都应该属于某种确定的数据类型。例如，C#语言中的字符串类型（ String，经常写为 string）。一个 String 表示一个恒定不变的字符序列集合，所有的字符序列集合构成 String 的取值范围。我们可以对 String 进行求长度、复制、连接两个字符串等操作。
数据结构分类 (Data Structure)
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素之间都不是孤立的，而是存在着一定的关系，这种关系称为结构(Structure)。根据数据元素之间关系的不同特性，通常有 4 类基本数据结构：(1) 集合(Set)：如图 1.1(a)所示，该结构中的数据元素除了存在“同属于一个集合”的关系外，不存在任何其它关系。
(2) 线性结构(Linear Structure)：如图 1.1(b)所示，该结构中的数据元素存在着一对一的关系。
(3) 树形结构(Tree Structure)：如图 1.1(c)所示，该结构中的数据元素存在着一对多的关系。
算法和数据结构的关系
数据结构可以认为是数据在程序中的存储结构，和基本数据操作。
算法可以是认为解决问题的，算法是基于数据结构的。
数据结构是问题的核心，是算法的基础。
算法的评价标准
运行时间(Running Time)。
占用空间(Storage Space)。
有时需要牺牲空间来换取时间，有时需要牺牲时间来换取空间。
其他方面:正确性(Correctness)、可读性(Readability)、健壮性(Robustness
1.线性表
线性表是最简单、最基本、最常用的数据结构。线性表是线性结构的抽象(Abstract)，线性结构的特点是结构中的数据元素之间存在一对一的线性关系。这种一对一的关系指的是数据元素之间的位置关系，即：（ 1）除第一个位置的数据元素外，其它数据元素位置的前面都只有一个数据元素；（ 2）除最后一个位置的数据元素外，其它数据元素位置的后面都只有一个元素。也就是说，数据元素是一个接一个的排列。因此，可以把线性表想象为一种数据元素序列的数据结构。
线性表就是位置有先后关系，一个接着一个排列的数据结构。
c# 1.1 提供了一个非泛型接口IList接口，接口中的项是object,实现了IList解扣子的类有ArrayList,ListDictionary,StringCollection,StringDictionary.
c# 2.0 提供了泛型的IList<T>接口，实现了List<T>接口的类有List<T>
线性表的接口定义
public interface IListDS<T> {
int GetLength(); //求长度
void Clear(); //清空操作
bool IsEmpty(); //判断线性表是否为空
void Add(T item); //附加操作
void Insert(T item, int i); //插入操作
T Delete(int i); //删除操作
T GetElem(int i); //取表元
T this[int index]{get;}//定义一个索引器 获取元素
int Locate(T value); //按值查找
}