数据结构(C#语言描述)第一章

数据结构与算法第一章预习检查预习内容泛型的基本知识本章任务

数据结构的基本概念算法的基本概念泛型(预备知识）什么是数据结构?它用来反映一个数据的内部构成，即一个数据由哪些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。算法设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构数据结构逻辑结构&物理结构逻辑结构:数据之间的逻辑关系物理结构:数据结构在计算机中的表示（映像）数据元素之间的关系在计算机中有两种不同的表示方法:①顺序映像 以存储位置的相邻表示后继关系①链式映像以指针表示后继关系xYxY数据结构什么是程序、软件?(程序＝算法＋数据结构)程序设计:为计算机处理问题编制一组指令集算法:处理问题的策略数据结构:问题的数学模型软件＝程序+文档（软件工程的观点）数据结构计算机的用途?□早期：主要用于数值计算。□后来：□ 处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。数据结构计算机解决问题步骤?数值计算解决问题的一般步骤数学模型→选择计算机语言→编出程序→测试→最终解答数值计算的关键是：如何得出数学模型(方程)?—— 根据操作对象间的关系，用数学语言表示。程序设计人员比较关注程序设计的技巧。比如：y = x2数据结构例2.人机对弈算法:每下完一步棋,分析对手可能出现的所有可能性,并找到最佳对策非数值型数学模型数据元素之间的相互关系一般无法用数学方程加以描述例1.求一组(n个)整数中的最大值算法:基本操作是“比较两个数的大小”数据结构求解非数值计算的问题：主要考虑的是设计出合适的数据结构及相应的算法。即：首先要考虑对相关的各种信息如何表示、组织和存储?因此，可以认为：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。数据结构基本概念和术语数据:所有能被输入到计算机中，且能被计算机处理的符号的集合数据元素:是数据(一个集合)中的一个个体，是数据结构中讨论的基本单位数据项:数据结构中讨论的最小单位数据结构基本概念和术语数据结构:数据以及数据之间的关系常用的数据结构集合线性结构树形结构图状结构数据结构{<ai, ai+1>| i=1, 2, 3, 4, 5}可见:不同的关系构成不同的结构，而数据结构就是带结构的数据元素的集合数据结构的形式定义为:数据结构是一个二元组Data_Structures=(D,S)其中:D是数据元素的有限集，S是D上关系的有限集。数据结构例一维数组{a1,a2,a3,a4,a5,a6}中存在次序关系:问题：有三个牧师和三个野人过河，只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于牧师的人数，那牧师就会有被吃掉的危险。你能不能找出一种安全的渡河方法呢?动画演示什么是算法?算法是指解决问题的一种方法或者一个过程。一个问题可以用多种算法来解决，一个给定的算法解决一个特定的问题算法算法的五个重要特性:有穷性对于任意合法输入值，在执行有穷步骤之后一定能结束，即:算法中的每个步骤都能在有限时间内完成；确定性对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径可行性算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之；有输入作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中；有输出它是一组与“输入”与确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。算法算法效率的衡量方法和准则时间复杂度:执行算法所要的时间和算法执行时间相关的因素:算法选用的策略问题的规模编写程序的语言编译程序产生的机器代码的质量计算机执行指令的速度算法算法效率的衡量方法和准则算法的空间复杂度:执行算法所要的存储空间表示随着问题规模的增大,算法运行所需存储量的增加。算法的存储量包括:输入数据所占空间;程序本身所占空间；辅助变量所占空间。算法小结数据结构作为一门独立的课程始于1968年,在我国数据结构作为一门独立课程在80年代初,早期的数据结构对课程的范围没有明确的规定,数据结构的内容几乎和图论、树的理论是相同的,在60到70年代随着大型程序的出现,软件也相对独立,结构程序设计逐步成为程序设计方法学的主要内容,人们已经认识到程序设计的实质就是对所确定的问题选择一种好的结构,从而设计一种好的算法。作业专业程序员,数据结构是一门不可不学的课程.C#语言的一个最大变化是引入了泛型。在.NET1.0中,要创建一个灵活的类或方法,但该类或方法在编译期间不知道使用什么类,就必须以Object类为基础。而Object类在编译期间没有类型安全性,因此必须进行强制类型转换。NET2.0提供了泛型。有了泛型，就不再需要Object类了。泛型类使用泛型类型，并可以根据需要用特定的类型替换泛型类型。这就保证了类型安全性:如果某个类型不支持泛型类，编译器就会生成错误。泛型//拆箱list.Add(44);

//装箱

int

i1=(int)list[0];foreach(int

i2

in

list){}Console.WriteLine(i2); //拆箱Add()方法定义为需要把一个对象作为参数,所以要装箱一个整数类型。在读取ArrayList中的值时,要进行拆箱,把对象转换为整数类型。在访问int类型的变量i2的foreach语句中,也要使用类型转换运算符。泛型不使用泛型的例子:ArrayListlist=newArrayList();使用泛型的例子List<int>list=newList<int>();list.Add(44); //不用装箱inti1=list[0]; //不用拆箱foreach(inti2inlist){Console.WriteLine(i2);}由此看出:使用泛型要比不使用泛型的性能要好泛型不使用泛型的例子:ArrayListlist=newArrayList();list.Add(44);list.Add("mystring");list.Add(newMyClass());foreach(intiinlist){Console.WriteLine(i);}问题一:这段代码在编译时是否有问题?问题二:这段代码在运行时是否有问题?泛型使用泛型的例子List<int>

list

=

new

List<int>();list.Add(44);list.Add("mystring");list.Add(new

MyClass());问题一:这段代码在编译时是否有问题?由此可以看出:泛型的另一个优点是类型安全泛型泛型类的定义与一般类类似,只是要使用泛型类型声明。之后,泛型类型就可以在类中用作一个字段成员,或者方法的参数类型。public

class

FanXingClass<T>{T

data;public

void

SetData(T

elem){data=elem;}public

T

GetDate(){return

data;}}泛型使用类:FanXingClass<int>fanxing=newFanXingClass<int>();fanxing.SetData(400);Console.WriteLine(fanxing.GetDate());除了定义泛型类之外,还可以定义泛型方法。在泛型方法中,泛型类型用方法声明来定义。//泛型方法public

void

UseParam<T,B>(T

data1,

B

data2){Console.WriteLine(data1);Console.WriteLine(data2);}fanxing.UseParam(111,

"222");泛型C#泛型是开发工具库中的一个无价之宝。它们可以提高性能、类型安全和质量,减少重复性的编程任务,简化总体编程模型,而这一切都是通过优雅的、可读