数据结构论文关于线性表的链式结构.doc

数据结构 课程小论文 题目： 线性表的链式表示 学 号： 090510126 姓 名： 叶妍莉 班 级： 090510 学 院： 经济管理学院 2011年 12月 8日一引言：- 2 -二链表的概述- 3 -1.线性链表里的一些概念：- 3 -2.链表的有关概述：- 3 -3.链表的存储方法：- 4 -4.链表的分类：- 4 -三线性表的链式实现- 5 -1.“插入”和“删除”操作的实现：- 5 -2.“合并链表”操作的实现：- 6 -四链表的优点与缺点- 6 -五总结- 7 -线性表的链式表示姓名：叶妍莉 班级：090510 学号：090510126摘 要:线性表对于学过数据结构的人来说都是再熟悉不过了，它是数据结构的一个基本内容，是最常用且最简单的一种数据结构。线性表的存储结构有顺序存储结构和链式存储结构，也就是我们常说的顺序表和链表.顺序和链式存储是线性表不同的存储方式，各有优劣，线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，然而这个特点也铸成了他的弱点：在做插入和删除操作时须移入大量元素，链式存储结构就克服了顺存储结构的弱点。而不同的存储方式所对应的算法操作也不同，实现的效率也有差异。通过对线性表的两种存储方式进行对比，分析与研究，使得对线性表做了进一步了解，加深学习者对线性表的理解，对链表的理解。关键词：线性表 链表 存储结构 优点 缺点一引言： 线性表是线性结构的一种，线性结构的特点是：在数据元素的非空有限集中存在唯一的被称作“第一个”的数据元素；存在唯一一个被称作“最后一个”的数据元素；除第一个之外集合中的每个元素均只有一个前驱；出最后一个之外，集合中每个元素只有一个后继。线性表是最简单的一种数据结构，一个线性表是n个数据元素的有限序列。线性表的顺序表示指用一组地址连续的存储单元依次存储线性表的数据元素；线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存取表中任意元素它的存储位置可以用一个简单直观的公式表示，然而从另一个方面看这个特点也铸成了他的弱点：在做插入和删除操作时须移入大量元素。链式存储结构就克服了顺存储结构的弱点，不要求逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序存储结构所具有的弱点，但同时也失去了顺序表可以随机存取的优点。线性表的链式结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。用线性链表表示线性表时，数据元素之间的逻辑关系是由结点中的指针指示的。二链表的概述 1.线性链表里的一些概念：为了表示每个数据元素与其直接后继数据元素之间的逻辑关系，对此数据元素来说，除了存储其本身信息外还需存储一个指示其直接后继的信息（即直接后继的存储位置）。这两部分信息组成这个数据元素的存储映像，称为结点。它包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域；有时我们在单链表的第一个结点之前附设一个结点，称之为头结点；指针域中存储的信息称为指针或链；n个结点链接成一个链表即为线性表的链式存储结构，又由于此链表的每个结点中只包含一个指针域，故又称为线性链表或单链表。2.链表的有关概述：链表是一种常见的重要的数据结构。他是动态的进行存储分配的一种结构。我们知道，用数组存放数据时，必须事先定义固定的长度。如果事先难以确定数组中元素的个数，则必须把数组定义的足够大，以便能存放足够的数据。链表则没有这种缺点，他根据需要开辟内存单元。链表有一个“头指针”变量，他存放一个地址，该地址指向一个元素。链表中每一个元素称为“接点”，每个接点都应该包括两个部分：用户需用的实际数据和下一个接点的地址。可以看到头指针指向第一个元素;第一个元素又指向第二个元素直到最后一个元素，该元素不再指向其他元素，他称为“表尾”，他的地址部分放一个“NULL”,链表到此结束。可以看到链表中各元素在内存中可以不是连续存放的。要找到某一元素，必须先找到上一个元素，根据它提供的下一元素才能找到下一个元素。如果不提供“头指针”，则整个链条都无法访问。链条如同一条铁链一样，一环扣一环，中间是不能断开的。由此可以看到，这种链表的数据结构，必须利用指针变量才能实现，即一个接点中应包含一个指针变量，用它存放下一个接点的地址。通常我们把链表画成用箭头相链接的结点的序列，结点之间的箭头表示链域中的指针。在使用链表时关心的只是他所表示的线性表中数据元素之间的逻辑顺序，而不是每个数据元素在存储器中的实际位置，由此可见，单链表可由头指针唯一确定。在线性表的顺序存储结构中，由于逻辑上相邻的两个元素在物理位置上紧邻，则每个元素的存储位置都可从线性表的起始位置计算得到，而在单链表中任何两个元素的存储位置都包含在其直接前驱结点的信息之中。假设p是指向线性表中第i个数据元素（结点ai）的指针，则p->next是指向第i+1个数据元素（结点ai+1）的指针，即若p->data=ai，则p->next->data=ai+1.由此，在单链表中，取得第i个数据元素必须从头指针出发寻找，因此，单链表是表示非随机存取的存储结构。如下是函数GetElem在单链表中的实现：Status GetElem_L(LinklList L,int i,ElemType&e) /L为带头结点的单链表的头指针。 /当第i个元素存在时，其值赋给e并返回ok，否则返回ERRORP=L->next；j=1； /初始化，p指向第一个结点，j为计数器While (p&&j<i) /顺指针向后查找，直到p指向第i个元素或p为空 P=p->next；+j；If (!pj>i) return ERROR； /第i个元素不存在e = p->data； /取第i个元素Return OK； /GetElem_L3.链表的存储方法：链表中的结点不需要以特定的方式存储，其存储方法主要有两种：共用存储空间和独立存储空间。（1）共用存储空间。链表的节点和其他的数据共用存储空间，这样可以存储无限多的内容，但处理器必需要提前分配内存，但由于内容分散，有时可能不方便调试。（2）独立存储空间。一个链表或多个链表使用独立存储空间，一般用数组或者类似结构实现，这样可以自动获得一个附加数据，也就是编号，并且方便调试，但不能动态分配内存。4.链表的分类：链表按性质可以分为三类：单向链表，双向链表，循环链表。链表中最简单的是单向链表，包含两个域，一个是数据域，一个是指针域。这个链接指向下一个结点，而最后一个节点指向一个空值。单向链表中第一个节点，只能通过头指针来进行访问，者有一定的局限性。如果把单链表中的首节点和尾节点相连接，则从链表中任意节点出发，都能访问链表中所有节点，这就是循环链表。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环，由此，从表中任何一个结点出发均可找到表中其他结点。在单链表中，NextElem的执行时间为0（1），而PriorElem的执行时间为0（n）。为克服单链表这种单向性的缺点，可利用双向链表，在双向链表的节点中有两个指针域，其一指向直接后继，另一指向直接前趋。三线性表的链式实现 1.“插入”和“删除”操作的实现：假设我们要在线性表的两个数据元素a和b之间插入一个数据元素x，已知p为其单链表存储结构中指向结点a的指针。为插入元素x，首先要生成一个数据域为x的结点，然后插入在单链表中，根据插入操作的逻辑定义，还需要修改结点a中的指针域，令其指向结点x，而结点x中的指针域应指向结点b从而实现3个元素a，b和x之间逻辑关系的变化。假设s为指向结点x的指针，则上述指针修改用语句描述即为：s->next=p->next；p->next=s；反之，在线性表中删除元素b时，在为单链表中实现元素a，b和c之间逻辑关系的变化，仅需修改结点a中的指针域即可。假设p为指向结点a的指针，则修改指针的语句为：P->next=p->next->next；可见，在已知链表中元素插入和删除的确切位置的情况下，在单链表中插入或删除一个结点时，仅需修改指针而不需要移动元素。下面分别是ListInsert在单链表中的实现：Status ListInsert_L(LinkList&L，int i，ElemType e) /在带头结点的单链线性表L中第i个位置前插入元素e P=L；j=0； While (p&&j<i-1) p=p->next；+j； /寻找第i-1个结点 If (!pj>i-1) return ERROR； /i小于1或者大于表长加1 S=(LinkList) malloc (sizeof (LNode) )； /生成新结点 S->data = e；s->next=p->next； /插入L中 P->next=s； Return OK；/ListInsert_LListDelete在单链表中的实现：Status ListDelete_L(LinkList&L，int i，ElemType e) /在带头结点的单链线性表L中删除第i个元素，并由e返回其值 P=L；j=0； While (p->next&&j<i-1) /寻找第i个结点，并令p指向其前趋 p=p->next；+j； If ( ! ( p->next j>i-1) return ERROR；/删除位置不合理 q=p->next；p->next=q->next； /删除并释放结点 e=q->data；free(q)； Return ok；/ListDelete_L在归并两个链表为一个链表时，不需要另建新表的结点空间，而只需将原来链表中结点之间的关系解除，重新按元素值非递减的关系将所有结点链接成一个链表即可，有时也可借用一维数组来描述线性链表。2.“合并链表”操作的实现： 假设头指针为La和Lb的单链表分别为线性表LA和LB的存储结构，先要归并La和Lb得到单链表Lc。我们需要建立三个指针pa，pb和pc，其中pa和pb分别指向La表和Lb表中当前待比较插入的结点，而pc指向Lc表中当前最后一个结点，若pa->datapb->data，则将pa所指结点链接到pc所指结点之后，否则将pb所指结点链接到pc所指结点之后。指针初始状态为：当LA和LB为非空表时，pa和pb分别指向La和Lb表中第一个结点，否则为空；pc指向空表Lc中的头结点。由于链表的长度为隐含的，则第一次循环执行的条件是pa和pb皆非空，当其中一个为空时，说明一个表的元素已经归并完，则只要将另一个表的剩余段链接在pc所指结点之后即可。由此可以得到归并两个单链表的算法：Void MergeList_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四链表的优点与缺点线性链表不能像顺序链表那样随机存取，但它不要求逻辑上相邻的元素在物理位置上也相邻。数组与链表是两种截然不同的存储结构，一种是顺序存储，一种是链式存储。由于他们的存储结构不同，在进行某些相同操作时他们的效率也不一样。下面我们从他们解决约瑟夫问题，插入操作，删除操作去分析他们的效率。在分析它们效率的时候，我们引用时间函数。也就是说通过时间函数在执行操作前记录开始时间begin，在操作完成后记录结束时间end。则操作运行时间可以用end-begin来表示。由于计算机运行速度很快，时间会很小，在代码中会将代码适当放大进行讨论。（1）使用链表与数组解决约瑟夫问题的时间比较约瑟夫环问题可以分为很多种，在这里我们概括为假设有编号为1，2，3，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一人开始重新从1报数，如此下去，直到所有人全部出列为止。使用链表解决约瑟夫问题的步骤：建立一个具有n个结点的循环链表，设定一个头结点，以这个结点为起点开始报数，不断的删除链表符合要求的的结点，一直到链表为空。需要注意的是：设立n个结点的循环链表一定要设立一个头结点，否则循环将不断运行，进入死循环。当记到m，将元素从链表中提出时，下一次起始位置从m+1开始。重复上述操作，直到表中剩下一个元素为止。使用数组解决约瑟夫问题的步骤：开辟一个数组，选择数组的大小，以及出表的规则num，也就是从表头开始经过num-1个元素，将这个元素取出数组，数组长度减一，不断执行这一操作，最终数组剩下一个元素。由上面的一些介绍和比较，我们应该能大致的理解线性表的一些定义。五总结 线性表是线性结构里最基本，很重要的一个类型，通过对其一些概念的掌握，对其更深入的研究，对其各种操作的实现的掌握，对其优缺点的了解使得对线性表的链式结构有了更深入地了解，也将会对之后对其它与它有关的知识的了解更深入一步。参考文献：【1】、秦玉平，马靖善.数据结构（C语言版）.北京：清华大学出版社，2005年【2】、谭浩强.C程序设计（第三版）.北京：清华大学出版社，2005年【3】严蔚敏，吴伟民.数据结构（C语言版）.北京：清华大学出版社，2007年