数据结构实验二 线性表及其应用

《数据结构实验二 线性表及其应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章 线性表及其应用【实验目的】1.熟练掌握线性表的基本操作在顺序存储和链式存储上的实现；2.以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点；3.掌握线性表的动态分配顺序存储结构的定义和基本操作的实现；4.通过本章实验帮助学生加深对C语言的使用（特别是函数的参数调用、指针类型的应用和链表的建立等各种基本操作）。第一节 知识准备一、线性表的逻辑结构线性表是由一组具有相同特性的数据元素组成的有限序列。至于每个数据元素，它可以是一个数，一个符号，也可以是一页书，甚至更复杂的信息。     例如：26个英文字母构成一个线性表 

2、（A，B，C，…，Y，Z）           一串数字构成另一个线性表    （45，45，32，65，123）每个数据元素可以由若干数据项组成，常把此数据元素称为记录。能唯一标识一个记录的数据项的值称为关键字。如：一个学校的学生情况表如表2-1所示，表中每个学生的情况为一个记录，它由学号、姓名、性别、年龄、年级等五个数据项组成。学号姓名性别年龄年级96001张平女21大二96002王极男20大一96003膨磊男23大三96004严正英女19大一96005李强男20大二综上所述，线性表有如下特性：1．第二章 线性表及其应用【实验目

3、的】1.熟练掌握线性表的基本操作在顺序存储和链式存储上的实现；2.以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点；3.掌握线性表的动态分配顺序存储结构的定义和基本操作的实现；4.通过本章实验帮助学生加深对C语言的使用（特别是函数的参数调用、指针类型的应用和链表的建立等各种基本操作）。第一节 知识准备一、线性表的逻辑结构线性表是由一组具有相同特性的数据元素组成的有限序列。至于每个数据元素，它可以是一个数，一个符号，也可以是一页书，甚至更复杂的信息。     例如：26个英文字母构成一个线性表 （A，B，C，…，Y，Z）  

4、         一串数字构成另一个线性表    （45，45，32，65，123）每个数据元素可以由若干数据项组成，常把此数据元素称为记录。能唯一标识一个记录的数据项的值称为关键字。如：一个学校的学生情况表如表2-1所示，表中每个学生的情况为一个记录，它由学号、姓名、性别、年龄、年级等五个数据项组成。学号姓名性别年龄年级96001张平女21大二96002王极男20大一96003膨磊男23大三96004严正英女19大一96005李强男20大二综上所述，线性表有如下特性：1．除第一个和最后一个元素以外，每个元素有且仅有一个直接前趋和一

5、个直接后继；第一个结点只有直接后继，最后一个结点只有直接前趋。2．线性表中的每个数据元素，其数据类型是一致的。3．数据元素之间的相对位置是线性的，结构中的数据元素之间存在一个对一个的关系。二、线性表的顺序表示和实现计算机的内存是由有限多个存储单元组成的，每个存储单元都有对应的整数地址，各存储单元的地址是连续编号的。对于一个线性表，如果用一组连续的存储单元依次存放它的各个数据元素，这就是线性表的顺序分配。也就是说，在线性表的顺序分配结构中，逻辑结构上相邻的数据元素，其物理位置也是相邻的。若一个数据元素只占用一个存储单元，则这种分配方式

6、如图2-1所示。从图可知，线性表的第i个数据元素的存储地址 LOC（ai）=LOC（a1）+（i-1）如果一个数据元素占据k个存储单元，则有   LOC（ai）=LOC（a1）+（i-1）×k其中，LOC（a1）是线性表的第一个数据元素的存储地址。三、线性表的链式表示和实现1.单链表线性链表即线性表的链式存储结构是用一组任意的存储单元（它们可以是连续的，也可以是不连续的）来存储线性表的各个数据元素。为了表示每个元素与其直接后继元素之间的逻辑关系，对每个元素来说，除了需要存储元素本身的信息之外，还需要存储一个指示其直接后继的信息（即直

7、接后继的存储位置），这两部分信息组成了一个数据元素的存储结构，称之为一个结点（node），当然每一个结点占用的存储单元应该是连续的。这样，每个结点包括两个域，存储数据元素本身信息的域称之为数据域（data），存储直接后继结点存储位置的域称之为指针域（next），该域内信息为一指针，它指出线性表某一数据元素逻辑上直接后继元素的存储位置。由于线性表的最后一个数据元素没有后继，故相应结点的指针域内容为空NULL（也可以用符号∧表示）。如图2-2所示为一个不带头结点的单链表。在实际应用中，有时也使用带头结点的单链表，如图2-3所示，虽然浪费

8、了一个结点，但是却换来了其它操作的便利，例如在插入删除操作中，不用判断是否对第一个结点进行。我们称这个结点为“哨兵”，其作用往往是不用判断出界；在以后的学习中，还会经常遇上“哨兵”。 2.循环链表循环链表是线性表的一种特殊的链式存储结