数据结构关于线性表及链表的研究

《数据结构关于线性表及链表的研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、关于线性表及链表的研究石燕20111105066数学科学学院信息与计算科学2011级信息3班指导教师张玉田摘要链表是数据结构中的重要概念，是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。通过对线性表的两种存储方式进行对比，分析与研究，使得对线性表做了进一步了解，加深学习者对线性表的理解，对链表的理解。关键词链表、指针、插入、删除、线性表、存储结构1．链表的概述1.1线性链表里的一些概念：为了表示每个数据元素与其直接后继数据元素之间的逻辑关系，对此数据元素来说，除了存储其本身信息外还需存储一个指示其直接后继的信息（即

2、直接后继的存储位置）。这两部分信息组成这个数据元素的存储映像，称为结点。它包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域；有时我们在单链表的第一个结点之前附设一个结点，称之为头结点；指针域中存储的信息称为指针或链；n个结点链接成一个链表即为线性表的链式存储结构，又由于此链表的每个结点中只包含一个指针域，故又称为线性链表或单链表。1.2链表的有关概述：链表是一种常见的重要的数据结构。他是动态的进行存储分配的一种结构。我们知道，用数组存放数据时，必须事先定义固定的长度。如果事先难以确定数组中元素的个数，则必须把数组定义的足够大，以便

3、能存放足够的数据。链表则没有这种缺点，他根据需要开辟内存单元。链表有一个“头指针”变量，他存放一个地址，该地址指向一个元素。链表中每一个元素称为“接点”，每个接点都应该包括两个部分：用户需用的实际数据和下一个接点的地址。可以看到头指针指向第一个元素;第一个元素又指向第二个元素„„直到最后一个元素，该元素不再指向其他元素，他称为“表尾”，他的地址部分放一个“NULL”,链表到此结束。可以看到链表中各元素在内存中可以不是连续存放的。要找到某一元素，必须先找到上一个元素，根据它提供的下一元素才能找到下一个元素。如果不提供“头指针”，则整个链条都无法访问。链条如同一条铁链

4、一样，一环扣一环，中间是不能断开的。由此可以看到，这种链表的数据结构，必须利用指针变量才能实现，即一个接点中应包含一个指针变量，用它存放下一个接点的地址。通常我们把链表画成用箭头相链接的结点的序列，结点之间的箭头表示链域中的指针。在使用链表时关心的只是他所表示的线性表中数据元素之间的逻辑顺序，而不是每个数据元素在存储器中的实际位置，由此可见，单链表可由头指针唯一确定。在线性表的顺序存储结构中，由于逻辑上相邻的两个元素在物理位置上紧邻，则每个元素的存储位置都可从线性表的起始位置计算得到，而在单链表中任何两个元素的存储位置都包含在其直接前驱结点的信息之中。假设p是指向

5、线性表中第i个数据元素（结点ai）的指针，则p->next是指向第i+1个数据元素（结点ai+1）的指针，即若p->data=ai，则p->next->data=ai+1.由此，在单链表中，取得第i个数据元素必须从头指针出发寻找，因此，单链表是表示非随机存取的存储结构。如下是函数GetElem在单链表中的实现：StatusGetElem_L(LinklListL,inti,ElemType&e){//L为带头结点的单链表的头指针。//当第i个元素存在时，其值赋给e并返回ok，否则返回ERRORP=L->next；j=1；//初始化，p指向第一个结点，j为计数器Wh

6、ile(p&&jnext；++j；}If(!pǁj>i)returnERROR；//第i个元素不存在e=p->data；//取第i个元素ReturnOK；}//GetElem_L1.3链表的存储方法：链表中的结点不需要以特定的方式存储，其存储方法主要有两种：共用存储空间和独立存储空间。（1）共用存储空间。链表的节点和其他的数据共用存储空间，这样可以存储无限多的内容，但处理器必需要提前分配内存，但由于内容分散，有时可能不方便调试。（2）独立存储空间。一个链表或多个链表使用独立存储空间，一般用数组或者类

7、似结构实现，这样可以自动获得一个附加数据，也就是编号，并且方便调试，但不能动态分配内存。1.4链表的分类：链表按性质可以分为三类：单向链表，双向链表，循环链表。链表中最简单的是单向链表，包含两个域，一个是数据域，一个是指针域。这个链接指向下一个结点，而最后一个节点指向一个空值。单向链表中第一个节点，只能通过头指针来进行访问，者有一定的局限性。如果把单链表中的首节点和尾节点相连接，则从链表中任意节点出发，都能访问链表中所有节点，这就是循环链表。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环，由此，从表中任何一个结点出发均可找到表中其他结点。在单链表

8、中，Nex