数据结构（C#语言描述）第四章.ppt

数据结构与算法 第四章 预习检查 预习内容 数组 数组 数组定义 数组是数据结构的基本结构形式，它是一种顺序式的结构，数组是存储同一类型数据的数据结构，使用数组时需要定义数组的大小和存储数据的数据类型，数组分为一维数组和多维数组。数组的维数是由数组的下标的个数确定的，一个下标称为一维数组，一个下标以上的数组称为多维数组。从这个意义上讲，确定了对于数组的一个下标总有一个相应的数值与之对应的关系；或者说数组是有限个同类型数据元素组成的序列。 目标 一 数组 二 递归 三 存储管理 四 进程和线程 五 线性结构总结 数组 一维数组 一维数组是指下标的个数只有一个的数组，有时称为向量，是最基本的数据类型，需要事先声名，程序才能够在编译过程中预留内存空间。声明的格式一般是： 数据类型[] 变量名称 = new 数据类型 [数组大小]； 数组 多维数组 多维数组是指下标的个数有两个以上，我们比较常用的是二维数组（因为三维以上的数组存储可以简化为二维数组的存储）。下面以二维数组为例说明多维数组。二维数组的声明同一维数组。格式为： 数据类型[,] 数组名称 =new 数据类型 [size1,size2] 数组 数组的内存映象 通常，采用顺序存储结构来存储数组中的数据元素，因为数组中的元素要求连续存放。本质上，计算机的内存是一个一维数组，内存地址就是数组的下标。所以，对于一维数组，可根据数组元素的下标得到它的存储地址，也可根据下标来访问一维数组中的元素。 而对于多维数组，需要把多维的下标表达式转换成一维的下标表达式。当行列固定后，要用一组连续的存储单元存放数组中的元素，有一个次序约定问题，这产生了两种存储方式：一种是以行序为主序（先行后列）的顺序存放，另一种是以列序为主序（先列后行）的顺序存放。 数组 当以行序为主序进行存储时，设数组的基址是Loc(a11)，每个数据元素占w个存储单元，则a11的物理地址可由下式计算： Loc(aij)= Loc(a11)+((i-1)*n+j-1)*w 这是因为数组元素aij的前面有i-1行，每一行有n个数据元素，在第i行中aij的前面还有j-1个元素。 数组 当以列序为主序进行存储时，则a11的物理地址可由下式计算： Loc(aij)= Loc(a11)+((j-1)*m+i-1)*w 这是因为数组元素aij的前面有j-1列，每一列有m个数据元素，在第j列中aij的前面还有i-1个元素。 由以上的公式可知，数组元素的存储位置是其下标的线性函数，一旦确定了数组各维的长度，就可以计算任意一个元素的存储地址，并且时间相等。所以，存取数组中任意一个元素的时间也相等，因此，数组是一种随机存储结构。 求n! long int Fact(int n) { int x; long int y; if(n 0) //n 0时阶乘无定义 return -1; if(n == 0) return 1; else { y = Fact(n - 1); //递归调用 return n * y; } } 存储管理 在介绍的数据结构时，使用高级语言描述了它们的内存映象但并没有涉及具体的存储分配 实际上结构中的每个数据元素都占有一定的内存位置，在程序的执行过程中，数据元素的存取是通过对应的存储单元来进行的 存储管理 当计算机是被单个用户使用时，那么整个内存除操作系统占用一部分之外，都归这个用户的程序使用。但在多用户分时并发系统中，多个用户程序共享一个内存区域，此时每个用户程序使用的内存就由操作系统来进行分配了。 存储管理 存储管理的基本问题是系统如何应用户提出的“请求”分配内存 如何回收那些用户不再使用而“释放”的内存，以备新的“请求”产生时重新进行分配 存储管理 垃圾回收机制 所谓垃圾回收机制，指的是内存和各种变量或者目标所使用内存的释放和回收机制 ，早期的一些程序员，如C/C++程序员,程序员负责内存的分配和释放,经常出现了内存丢失的问题，就是内存分配后忘记释放了---内存泄露。 存储管理 .NET框架垃圾回收机制 在.net中两种变量类型，一种是值类型，一种是引用类型，值类型所占的内存，存放在当前线程的栈上，垃圾回收不负责回收这方面的内存，当前方法运行完毕后，内存会自动释放。 NET框架包含一个托管堆，所有的.NET语言在分配引用类型对象时都要使用它,引用类型所占的内存存放在托管堆上，.net的