实验一 线性表和应用

《实验一 线性表和应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验一线性表及应用一、实验目的1．复习C语言的上机环境，掌握C语言的基本结构;2．会定义线性表的顺序存储结构和链表的存储结构;3． 熟悉对顺序表的一些基本操作和具体的函数定义。4．掌握顺序表和单链表的存储结构及相关运算5．掌握顺序表和单链表的基本应用二、实验硬软件环境硬件环境：赛扬433以上CPU，10GB以上硬盘，64MB以上内存软件环境：DOS+TurboC2.0或BorlandC++3.1以上Windowx9X+VC++5.0以上三、实验要求1．认真阅读和掌握本实验内容所给的全部程序。2．保存和打印出程

2、序运行结果，并结合程序进行分析。3． 按照你对顺序表操作的需要，屏幕考贝运行结果到实验报告中。4．撰写实验报告并准时上交四、注意事项在做第一次“数据结构”课程实验之前，要在硬盘上建立好自己的工作目录，专门用来存储你所做的实验程序及相关信息，以后每次做实验都采用这个目录。工作目录建议如下建立，最后注明实验作者（张三）：D:数据结构实验（张三）

3、+-----实验一

4、+-----实验二

5、…..+-----实验九实验一至九的有关材料请同学在网上下载（下载网址：http://eol.gzu.edu.cn），本实验设计

6、完全由老师设计，版权限本班同学使用，勿外传。实验材料下载到本机后，请用winrar软件释放到你的电脑磁盘的“数据结构实验（张三）”文件夹中，形成如上图的文件夹结构。上交实验报告时，请把“实验一”的所有内容（含实验报告）用winrar打包成.rar文件后一并交上来。上传名字为“实验一（张三）.rar”五、基本理论线性表：线性表（linearlist）是这样的数据对象，其实例形式为：(e1,e2,...en)，其中n是有穷自然数。ei是表中的元素，n是表的长度。元素可以被视为原子，因为它们本身的结构与线性表的结构

7、无关。当n=0时，表为空；当n>0时，e1是第一个元素，en是最后一个元素，可以认为el优先于e2，e2优先于e3，如此等等。除了这种优先关系之外，在线性表中不再有其他的结构。基本操作：•创建一个线性表。•确定线性表是否为空。•确定线性表的长度。•查找第k个元素。•查找指定的元素。•删除第k个元素。•在第k个元素之后/之前插入一个新元素。线性表ADT（图1）：图1线性表抽象数据类型顺序表：采用数组来表示一个对象的实例，数组中的每个位置被称之为单元（cell）或节点（node），每个数组单元应该足够大，以便能够

8、容纳数据对象实例中的任意一个元素。在某些情况下，每个实例可分别用一个独立的数组来描述，而在其他情况下，可能要使用一个数组来描述几个实例。实例中每个元素在数组中的位置可以用一个数学公式来指明。假定使用一个数组来描述表，需要把表中的每个元素映射到数组的具体位置上。第一个元素在什么地方？第二个元素在什么地方？在公式化描述中，可用一个数学公式来确定每个元素的位置。一个简单的映射公式如下：location(i)=i-1（式1-1）式1-1表明第i个元素的存储位置在数组的第i-1个位置;如果每个元素的长度为m，则可以通过

9、公式计算第i个元素的存储地址：Address(i)=Address(1)+(i-1)*m(式1-2)Address(1)为第1个元素的址，即数组的首地址。特别要记住的是第1个元素保存在数组的第0个位置。图2表性表实例简而言之，顺序表就是把线性表的元素存储在数组中，元素之间的关系直接通过相邻元素的位置来表达。优点：简单，数据元素的提取速度快；缺点：（1）静态存储，无法预知问题规模的大小，可能空间不足，或浪费存储空间；（2）插入元素和删除元素时间复杂度高——O（n）链表：在存储线性表List中的每个元素ei时，同

10、时存储元素的下一个元素的首地址（指针）Address(i+1),通过这种方法建立起元素之间的关系，从“逻辑”上看所有元素构成了图3所示的“链”，所以称为链表。图3一个单链表从图3可以看出元素之间的链接关系，为了“访问”每个元素ei的，必须知道ei的首地址，而这个首地址存储在其“直接前驱”结点ei-1中，……，按此规律，可以回推到元素e1的首地址。即要访问List中任一元素ei,都必须从第一个元素e1开始，所以，必须保存首元素e1的地址在一个变量中(first),有的书使用Head作为变量名。图3的单链表的首

11、元素的地址在first中，我们可以直接用“first”称呼此单链表。List中所有元素可以占用连续的存储空间，也可以占用不连续的存储空间。但是从“逻辑”上来看所有元素仍然满足“一对一”的关系，即：（1）首元素没有“直接前驱”，尾元素没有“直接后继”。（2）中间元素有且仅有一个“直接前驱”和“直接后继”为了实现这种存储结构，可以使用C语言作如下定义：typedefstructLnode{DataTyp