数据结构论文--关于线性表的链式结构.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”,链表到此结束。 可以看到链表中各元素在内存中可以不是连续存放的。要找到某一元素，必须先找到上一个元素，根据它提供的下一元素才能找到下一个元素。如果不提供“头指针”，则整个链条都无法访问。链条如同一条铁链一样，一环扣一环，中间是不能断开的。 由此可以看到，这种链表的数据结构，必须利用指针变量才能实现，即一个接点中应包含一个指针变量，用它存放下一个接点的地址。通