贵州大学数据结构实验1线性表及应用.doc

实验一 线性表及应用 一、实验目的 1．复习C语言的上机环境，掌握C语言的基本结构; 2．会定义线性表的顺序存储结构和链表的存储结构; 3．? 熟悉对顺序表的一些基本操作和具体的函数定义。 4．掌握顺序表和单链表的存储结构及相关运算 5．掌握顺序表和单链表的基本应用 二、实验硬软件环境 硬件环境：赛扬433以上CPU，10GB以上硬盘，64MB以上内存 软件环境：DOS+Turbo C 2.0 或 Borland C++ 3.1以上 Windowx 9X+VC++ 5.0以上 三、实验要求 1．认真阅读和掌握本实验内容所给的全部程序。 2．保存和打印出程序运行结果，并结合程序进行分析。 3．? 按照你对顺序表操作的需要，屏幕考贝运行结果到实验报告中。 4．撰写实验报告并准时上交 四、注意事项 在做第一次“数据结构”课程实验之前，要在硬盘上建立好自己的工作目录，专门用来存储你所做的实验程序及相关信息，以后每次做实验都采用这个目录。工作目录建议如下建立，最后注明实验作者（张三）： D:\数据结构实验（张三） | +-----实验一 | +-----实验二 |….. +-----实验九 实验一至九的有关材料请同学在网上下载（下载网址：），本实验设计完全由老师设计，版权限本班同学使用，勿外传。 实验材料下载到本机后，请用winrar软件释放到你的电脑磁盘的“数据结构实验（张三）”文件夹中，形成如上图的文件夹结构。 上交实验报告时，请把“实验一”的所有内容（含实验报告）用winrar打包成.rar文件后一并交上来。上传名字为“实验一（张三）.rar” 五、基本理论 线性表：线性表（linear list）是这样的数据对象，其实例形式为： (e1 , e2 ,... en )，其中n 是有穷自然数。ei 是表中的元素，n 是表的长度。元素可以被视为原子，因为它们本身的结构与线性表的结构无关。当n = 0 时，表为空；当n 0时，e1 是第一个元素，en 是最后一个元素，可以认为el优先于e2，e2 优先于e3，如此等等。除了这种优先关系之外，在线性表中不再有其他的结构。 基本操作： ? 创建一个线性表。 ? 确定线性表是否为空。 ? 确定线性表的长度。 ? 查找第k个元素。 ? 查找指定的元素。 ? 删除第k个元素。 ? 在第k个元素之后/之前插入一个新元素。 线性表ADT（图1）： 图1 线性表抽象数据类型 顺序表： 采用数组来表示一个对象的实例，数组中的每个位置被称之为单元（cell）或节点（node），每个数组单元应该足够大，以便能够容纳数据对象实例中的任意一个元素。在某些情况下，每个实例可分别用一个独立的数组来描述，而在其他情况下，可能要使用一个数组来描述几个实例。实例中每个元素在数组中的位置可以用一个数学公式来指明。 假定使用一个数组来描述表，需要把表中的每个元素映射到数组的具体位置上。第一个元素在什么地方？第二个元素在什么地方？在公式化描述中，可用一个数学公式来确定每个元素的位置。一个简单的映射公式如下： location(i)= i - 1 （式1-1） 式1-1表明第i个元素的存储位置在数组的第i-1个位置; 如果每个元素的长度为m，则可以通过公式计算第i个元素的存储地址： Address(i)=Address(1)+(i-1)*m (式1-2) Address(1)为第1个元素的址，即数组的首地址。特别要记住的是第1个元素保存在数组的第0个位置。 图2 表性表实例 简而言之，顺序表就是把线性表的元素存储在数组中，元素之间的关系直接通过相邻元素的位置来表达。 优点：简单，数据元素的提取速度快； 缺点：（1）静态存储，无法预知问题规模的大小，可能空间不足，或浪费存储空间；（2）插入元素和删除元素时间复杂度高——O（n） 链 表： 在存储线性表List中的每个元素ei时，同时存储元素的下一个元素的首地址（指针）Address(i+1),通过这种方法建立起元素之间的关系，从“逻辑”上看所有元素构成了图3所示的“链”，所以称为链表。 图3 一个单链表 从图3可以看出元素之间的链接关系，为了“访问”每个元素ei的，必须知道ei的首地址，而这个首地址存储在其“直接前驱”结点ei-1中，……，按此规律，可以回推到元素e1的首地址。即要访问List中任一元素ei,都必须从第一个元素e1开始，所以，必须保存首元素e1的地址在一个变量中(first),有的书使用Head作为变量名。图3的单链表的首元素的地址在first中，我们可以直接用“first”称呼此单