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

关于线性表及链表的研究石燕20111105066数学科学学院信息与计算科学2011级信息3班指导教师张玉田摘要链表是数据结构中的重要概念，是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。通过对线性表的两种存储方式进行对比，分析与研究，使得对线性表做了进一步了解，加深学习者对线性表的理解，对链表的理解。关键词链表、指针、插入、删除、线性表、存储结构1．链表的概述1.1线性链表里的一些概念：为了表示每个数据元素与其直接后继数据元素之间的逻辑关系，对此数据元素来说，除了存储其本身信息外还需存储一个指示其直接后继的信息（即直接后继的存储位置）。这两部分信息组成这个数据元素的存储映像，称为结点。它包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域；有时我们在单链表的第一个结点之前附设一个结点，称之为头结点；指针域中存储的信息称为指针或链；n个结点链接成一个链表即为线性表的链式存储结构，又由于此链表的每个结点中只包含一个指针域，故又称为线性链表或单链表。1.2链表的有关概述：链表是一种常见的重要的数据结构。他是动态的进行存储分配的一种结构。我们知道，用数组存放数据时，必须事先定义固定的长度。如果事先难以确定数组中元素的个数，则必须把数组定义的足够大，以便能存放足够的数据。链表则没有这种缺点，他根据需要开辟内存单元。链表有一个“头指针”变量，他存放一个地址，该地址指向一个元素。链表中每一个元素称为“接点”，每个接点都应该包括两个部分：用户需用的实际数据和下一个接点的地址。可以看到头指针指向第一个元素;第一个元素又指向第二个元素„„直到最后一个元素，该元素不再指向其他元素，他称为“表尾”，他的地址部分放一个“NULL”,链表到此结束。可以看到链表中各元素在内存中可以不是连续存放的。要找到某一元素，必须先找到上一个元素，根据它提供的下一元素才能找到下一个元素。如果不提供“头指针”，则整个链条都无法访问。链条如同一条铁链一样，一环扣一环，中间是不能断开的。由此可以看到，这种链表的数据结构，必须利用指针变量才能实现，即一个接点中应包含一个指针变量，用它存放下一个接点的地址。通常我们把链表画成用箭头相链接的结点的序列，结点之间的箭头表示链域中的指针。在使用链表时关心的只是他所表示的线性表中数据元素之间的逻辑顺序，而不是每个数据元素在存储器中的实际位置，由此可见，单链表可由头指针唯一确定。在线性表的顺序存储结构中，由于逻辑上相邻的两个元素在物理位置上紧邻，则每个元素的存储位置都可从线性表的起始位置计算得到，而在单链表中任何两个元素的存储位置都包含在其直接前驱结点的信息之中。假设p是指向线性表中第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为计数器While(p&&ji){//顺指针向后查找，直到p指向第i个元素或p为空P=p-next；++j；}If(!pǁji)returnERROR；//第i个元素不存在e=p-data；//取第i个元素ReturnOK；}//GetElem_L1.3链表的存储方法：链表中的结点不需要以特定的方式存储，其存储方法主要有两种：共用存储空间和独立存储空间。（1）共用存储空间。链表的节点和其他的数据共用存储空间，这样可以存储无限多的内容，但处理器必需要提前分配内存，但由于内容分散，有时可能不方便调试。（2）独立存储空间。一个链表或多个链表使用独立存储空间，一般用数组或者类似结构实现，这样可以自动获得一个附加数据，也就是编号，并且方便调试，但不能动态分配内存。1.4链表的分类：链表按性质可以分为三类：单向链表，双向链表，循环链表。链表中最简单的是单向链表，包含两个域，一个是数据域，一个是指针域。这个链接指向下一个结点，而最后一个节点指向一个空值。单向链表中第一个节点，只能通过头指针来进行访问，者有一定的局限性。如果把单链表中的首节点和尾节点相连接，则从链表中任意节点出发，都能访问链表中所有节点，这就是循环链表。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环，由此，从表中任何一个结点出发均可找到表中其他结点。在单链表中，NextElem的执行时间为0（1），而PriorElem的执行时间为0（n）。为克服单链表这种单向性的缺点，可利用双向链表，在双向链表的节点中有两个指针域，其一指向直接后继，另一指向直接前趋。2.1.单链表的表示和实现2.1单链表的表示线性表的链式存储结构的特点是用一任意的存储单元存储线性表的数据元素。因此，为了表示每个数据元素Ai与一数据元素Ai+1的逻辑关系，对数据元素Ai来说，除了存储其本身的信息之外，还需存储一个其直接后继的信息。这两部分信息组成数据元素Ai的存储映像，称为结点，其结构如下：其中，data为数据域，用于存储数据元素信息；next为指针域，用于存储直接后继存储位置。单链表的类型定义如下：TypedfstructLnode{ElemTypedata;StructLnode*next;}lnode，*LinkLise;2.2单链表的插入运算单链表的插入运算可分为头插入（前插法）、尾插法（后插法）。2.21头插法单链表是用户不断申请存储单元和改变链接关系而得到的一种特殊数据结构，将链表的左边称为链头，右边称为链尾。头插法建单链表是将链表右端看成固定的，链表不断向左延伸而得到的。头插法最先得到的是尾结点。由于链表的长度是随机的，故用一个while循环来控制链表中结点个数。假设每个结点的值都大于O，则循环条件为输入的值大于o。申请存储空间可使用malloc()函数实现，需设立一申请单元指针，但malloc()函数得到的指针并不是指向结构体的指针，需使用强制类型转换，将其转换成结构体型指针。刚开始时，链表还没建立，是一空链表，head指针为NULL。链表建立的过程是申请空间、得到数据、建立链接的循环处理过程。如图a所示图a2.22尾插法若将链表的左端固定，链表不断向右延伸，这种建立链表的方法称为尾插法。尾插法建立链表时，头指针固定不动，故必须设立一个搜索指针，向链表右边延伸，则整个算法中应设立三个链表指针，即头指针head、搜索指针p2、申请单元指针pl。尾插法最先得到的是头结点。如图b所示：图b2.23单链表的删除运算我们若在单链表中删除一元素x时，为了实现原链表中其元素间的逻辑关系的变化仅需改变其中一个元素的指针域即可，所以在已知链表中元素删除的位置的情况下，仅需修改指针而不需移动元素。如以下算法所示：StatusListDelete_L(LinkList&L,intI,ElemType&e){//在带头结点的线性表L中，删除第i个元素，并由e返回i其值p=L;j=0；while（p-next&&ji-1）{//寻找第i个结点，并令p指向其前趋p=p-next;++j;}If(!(p-next)||j=i-1)returnERROR;//删除位置不合理q=p-next;p-next=q-next;//删除并释放结点e=q-data;free(q);returnOK;}//ListDelete_L2.3双链表的表示和实现2.3.1双链表的表示单链表只有一个直接后继的指针域，由此，从某个节点出发只能顺时针往后寻查其他结点。若要寻查结点的直接前趋，则需从表头指针出发。为了克服单链表这种但向性的缺点，可利用双向链表。双链表的每个结点结构中除了包含一个数据域，还有二个指针域，其中一个指针指向前驱结点，另一个指针指向后继结点，结构如图1所示。图1双链表的C语言表述：TypedfstructDuLNode{ElemTypedata;StructDuLNode*prior;StructDuLNode*next;}DuLNode,*DuLinkList;2.3.2双链表的插入运算双链表的前插运算算法描述：欲在双向链表第i个结点之前插入一个新的结点，则指针变化如图2所示：图2intDlinkIns(DoubleListL,inti,ElemTypee){DNode*s,*p;…/*先检查待插入的位置i是否合法（实现方法同单链表的前插操作）*/…/*若位置i合法，则让指针p指向它*/s=(DNode*)malloc(sizeof(DNode));if(s){s-data=e;s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;returnTRUE;}elseteturnfALSE;}2.3.3双链表的删除运算算法描述：欲删除双向链表中的第i个结点，则指针的变化情况如图3所示。图3intDlinkDel(DoubleListL,inti,ElemType*e){DNode*p;…/*首先检查待插入的位置i是否合法（实现方法同单链表的删除操作）*/…/*若位置i合法，则让指针p指向它*/*e=p-prior-next=p-next;p-next-prior-p=p-prior;free(p);returnTRUE;}3.“合并链表”操作的实现：假设头指针为La和Lb的单链表分别为线性表LA和LB的存储结构，先要归并La和Lb得到单链表Lc。我们需要建立三个指针pa，pb和pc，其中pa和pb分别指向La表和Lb表中当前待比较插入的结点，而pc指向Lc表中当前最后一个结点，若pa-data≤pb-data，则将pa所指结点链接到pc所指结点之后，否则将pb所指结点链接到pc所指结点之后。指针初始状态为：当LA和LB为非空表时，pa和pb分别指向La和Lb表中第一个结点，否则为空；pc指向空表Lc中的头结点。由于链表的长度为隐含的，则第一次循环执行的条件是pa和pb皆非空，当其中一个为空时，说明一个表的元素已经归并完，则只要将另一个表的剩余段链接在pc所指结点之后即可。由此可以得到归并两个单链表的算法：VoidMergeList_L(LinkList&La，LinkList&Lb，LinkList&Lc){//已知单链线性表La和Lb按值非递减排列。//归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。Pa=La-next；pb=Lb-next；Lc=pc=La；//用La的头结点作为Lc的头结点While（pa&&pb）{If(pa-data=pb-data){Pc-next=pa；pc=pa；pa=pa-next；}Else{pc-next=pb；pc=pb；pb=pb-next；}}Pc-next=pa?pa:pb；//插入剩余段Free(Lb)；//释放Lb的头结点}//MergeList_L参考文献;[1]严蔚敏、昊伟民.数据结构（C语言版）.[2]秦玉平、马靖善.《数据结构（C语言版）》.北京：清华大学出版社、2005年.[3]谭浩强.《C程序设计（第三版）》.北京：清华大学出版社、2005年.