线性表的链式存储和运算实现.doc

2.3线性表的链式存储和运算实现由于顺序表的存贮特点是用物理上的相邻实现了逻辑上的相邻，它要求用连续的存储单元顺序存储线性表中各元素，因此，对顺序表插入、删除时需要通过移动数据元素来实现，影响了运行效率。本节介绍线性表链式存储结构，它不需要用地址连续的存储单元来实现，因为它不要求逻辑上相邻的两个数据元素物理上也相邻，它是通过“链”建立起数据元素之间的逻辑关系来，因此对线性表的插入、删除不需要移动数据元素。2.3.1单链表链表是通过一组任意的存储单元来存储线性表中的数据元素的，那么怎样表示出数据元素之间的线性关系呢？为建立起数据元素之间的线性关系，对每个数据元素ai，除了存放数据元素的自身的信息ai之外，还需要和ai一起存放其后继ai+1所在的存贮单元的地址，这两部分信息组成一个“结点”，结点的结构如图2.6所示，每个元素都如此。存放数据元素信息的称为数据域，存放其后继地址的称为指针域。因此n个元素的线性表通过每个结点的指针域拉成了一个“链子”，称之为链表。因为每个结点中只有一个指向后继的指针，所以称其为单链表。链表是由一个个结点构成的，结点定义如下：typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；定义头指针变量：LinkListH；如图2.7是线性表(a1,a2,a3,a4,a5,a6,a7,a8)对应的链式存储结构示意图。当然必须将第一个结点的地址160放到一个指针变量如H中，最后一个结点没有后继,其指针域必需置空，表明此表到此结束，这样就可以从第一个结点的地址开始“顺藤摸瓜”，找到每个结点。作为线性表的一种存储结构，我们关心的是结点间的逻辑结构，而对每个结点的实际地址并不关心，所以通常的单链表用图2.8的形式而不用图2.7的形式表示。通常我们用“头指针”来标识一个单链表，如单链表L、单链表H等，是指某链表的第一个结点的地址放在了指针变量L、H中，头指针为“NULL”则表示一个空表。110a5200……150a2190160a1150……190a3210200a6260210a4110…….240a8NULL…...260a7240需要进一步指出的是：上面定义的LNode是结点的类型，LinkList是指向Lnode类型结点的指针类型。为了增强程序的可读性，通常将标识一个链表的头指针说明为LinkList类型的变量，如LinkListL;当L有定义时，值要么为NULL，则表示一个空表；要么为第一个结点的地址，即链表的头指针；将操作中用到指向某结点的指针变量说明为LNode*类型，如LNode*p；则语句：p=malloc(sizeof(LNode))；则完成了申请一块Lnode类型的存储单元的操作，并将其地址赋值给变量p。如图2.9所示。P所指的结点为*p，*p的类型为LNode型，所以该结点的数据域为(*p).data或p->data，指针域为(*p).next或p->next。free(p)则表示释放p所指的结点。2.3.2单链表上基本运算的实现1.建立单链表(1)在链表的头部插入结点建立单链表链表与顺序表不同，它是一种动态管理的存储结构，链表中的每个结点占用的存储空间不是预先分配，而是运行时系统根据需求而生成的，因此建立单链表从空表开始，每读入一个数据元素则申请一个结点，然后插在链表的头部，如图2.10展现了线性表：（25,45,18,76,29）之链表的建立过程，因为是在链表的头部插入，读入数据的顺序和线性表中的逻辑顺序是相反的。算法如下：LinkListCreat_LinkList1(){LinkListL=NULL；/*空表*/Lnode*s;intx;/*设数据元素的类型为int*/scanf(＂%d＂,&x);while(x!=flag){s=malloc(sizeof(LNode));s->data=x;s->next=L;L=s;Scanf(＂%d＂,&x);}returnL;}算法2.8(2)在单链表的尾部插入结点建立单链表头插入建立单链表简单，但读入的数据元素的顺序与生成的链表中元素的顺序是相反的，若希望次序一致，则用尾插入的方法。因为每次是将新结点插入到链表的尾部，所以需加入一个指针r用来始终指向链表中的尾结点，以便能够将新结点插入到链表的尾部，如图2.11展现了在链表的尾部插入结点建立链表的过程。算法思路：初始状态：头指针H=NULL，尾指针r=NULL;按线性表中元素的顺序依次读入数据元素，不是结束标志时，申请结点，将新结点插入到r所指结点的后面，然后r指向新结点（但第一个结点有所不同，读者注意下面算法中的有关部分）。算法如下：LinkListCreat_LinkList2(){LinkListL=NULL;Lnod