武汉软件工程职业学院数据结构讲义线性表的链式存储结构.doc

第四讲 线性表的链式存储结构1掌握线性链表、单链表、静态链表的概念。2掌握线性链表的表示及实现方法。 教学重点： 线性链表之单链表的表示及实现方法。 教学难点： 线性链表的概念。 授课内容2.3 线性表的链式存储结构由于顺序表的存贮特点是用物理上的相邻实现了逻辑上的相邻，它要求用连续的存储单元顺序存储线性表中各元素，因此，对顺序表插入、删除时需要通过移动数据元素来实现，影响了运行效率。本节介绍线性表链式存储结构，它不需要用地址连续的存储单元来实现，因为它不要求逻辑上相邻的两个数据元素物理上也相邻，它是通过“链”建立起数据元素之间的逻辑关系来，因此对线性表的插入、删除不需要移动数据元素。2.3.1 单链表链表是通过一组任意的存储单元来存储线性表中的数据元素的，那么怎样表示出数据元素之间的线性关系呢？为建立起数据元素之间的线性关系，对每个数据元素ai，除了存放数据元素的自身的信息 ai 之外，还需要和ai一起存放其后继 ai+1 所在的存贮单元的地址，这两部分信息组成一个“结点”，结点的结构如图2.6 所示，每个元素都如此。存放数据元素信息的称为数据域，存放其后继地址的称为指针域。因此n个元素的线性表通过每个结点的指针域拉成了一个“链子”，称之为链表。因为每个结点中只有一个指向后继的指针，所以称其为单链表。链表是由一个个结点构成的，结点定义如下：图2.6 单链表结点结构data nexttypedef struct node datatype data; struct node *next; LNode，*LinkList；定义头指针变量：LinkList H；如图2.7是线性表 (a1,a2,a3,a4,a5,a6,a7,a8) 对应的链式存储结构示意图。当然必须将第一个结点的地址160 放到一个指针变量如 H 中，最后一个结点没有后继, 其指针域必需置空，表明此表到此结束，这样就可以从第一个结点的地址开始“顺藤摸瓜”，找到每个结点。作为线性表的一种存储结构，我们关心的是结点间的逻辑结构，而对每个结点的实际地址并不关心，所以通常的单链表用图2.8的形式而不用图2.7的形式表示。通常我们用“头指针”来标识一个单链表，如单链表L、单链表H等，是指某链表的第一个结点的地址放在了指针变量 L、H 中， 头指针为“NULL”则表示一个空表。110a5200150a2190160a1150190a3210200a6260210a4110 .240a8NULL .260a7240图2.8 链表示意图a1anHa2Pp-datap-next 图2.9 申请一个结点H160图2.7 链式存储结构 需要进一步指出的是：上面定义的LNode是结点的类型，LinkList是指向Lnode类型结点的指针类型。 为了增强程序的可读性，通常将标识一个链表的头指针说明为LinkList类型的变量，如LinkList L ; 当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）之链表的建立过程，因为是在链表的头部插入，读入数据的顺序和线性表中的逻辑顺序是相反的。25452518762976182545251825452525452525图2.10 在头部插入建立单链表算法如下：LinkList Creat_LinkList1( ) LinkList L=NULL；/*空表*/Lnode *s; int x; /*设数据元素的类型为int*/scanf(%d,&x);while (x!=flag) s=malloc(sizeof(LNode); s-data=x; s-next=L; L=s; Scanf (%d,&x); return L;算法2.8(2)在单链表的尾部插入结点建立单链表头插入建立单链表简单，但读入的数据元素的顺序与生成的链表中元素的顺序是相反的，若希望次序一致，则用尾插入的方法。因为每次是将新结点插入到链表的尾部，所以需加入一个指针 r 用来始终指向链表中的尾结点，以便能够将新结点插入到链表的尾部，如图2.11展现了在链表的尾部插入结点建立链表的过程 。算法思路：初始状态：头指针H=NULL，尾指针 r=NULL; 按线性表中元素的顺序依次读入数据元素，不是结束标志时，申请结点，将新结点插入到 r 所指结点的后面，然后 r 指向新结点（但第一个结点有所不同，读者注意下面算法中的有关部分）。图2.11 在尾部插入建立单链表H=NULL r=NULL /*初始状态*/29rH7629rH187629rH254525187629rH4525187629rH算法如下：LinkList Creat_LinkList2( ) LinkList L=NULL;Lnode *s,*r=NULL; int x; /*设数据元素的类型为int*/scanf(%d,&x);while (x!=flag) s=malloc(sizeof(LNode); s-data=x; if (L=NULL) L=s; /*第一个结点的处理*/ else r-next=s; /*其它结点的处理*/ r=s; /*r 指向新的尾结点*/ scanf(%d,&x); if ( r!=NULL) r-next=NULL; /*对于非空表，最后结点的指针域放空指针*/ return L;算法2.9在上面的算法中，第一个结点的处理和其它结点是不同的，原因是第一个结点加入时链表为空，它没有直接前驱结点，它的地址就是整个链表的指针， 需要放在链表的头指针变量中；而其它结点有直接前驱结点，其地址放入直接前驱结点的指针域。“第一个结点”的问题在很多操作中都会遇到，如在链表中插入结点时，将结点插在第一个位置和其它位置是不同的，在链表中删除结点时，删除第一个结点和其它结点的处理也是不同的，等等，为了方便操作，有时在链表的头部加入一个“头结点”，头结点的类型与数据结点一致，标识链表的头指针变量L中存放该结点的地址，这样即使是空表，头指针变量L也不为空了。头结点的加入使得“第一个结点”的问题不再存在，也使得“空表”和“非空表”的处理成为一致。头结点的加入完全是为了运算的方便，它的数据域无定义，指针域中存放的是第一个数据结点的地址，空表时为空。图2.12(a)、（b）分别是带头结点的单链表空表和非空表的示意图。图2.12 带头结点的单链表H(a)a1a2anH(b)2. 查找操作(1) 按序号查找 Get_Linklist(L,i)算法思路：从链表的第一个元素结点起，判断当前结点是否是第i个，若是，则返回该结点的指针，否则继续后一个，表结束为止。没有第个结点时返回空。算法如下：Lnode * Get_LinkList(LinkList L, Int i);/*在单链表L中查找第i个元素结点，找到返回其指针，否则返回空*/ Lnode * p=L; int j=0;while (p-next !=NULL & jnext; j+; if (j=i) return p; else return NULL; 算法2.11(a)(2) 按值查找即定位 Locate_LinkList(L,x)算法思路：从链表的第一个元素结点起，判断当前结点其值是否等于x，若是，返回该结点的指针，否则继续后一个，表结束为止。找不到时返回空。算法如下：Lnode * Locate_LinkList( LinkList L, datatype x) /*在单链表L中查找值为x的结点，找到后返回其指针，否则返回空*/ Lnode * p=L-next; while ( p!=NULL & p-data != x) p=p-next; return p; 算法2.11(b)算法2.11(a)、(b)的时间复杂度均为O(n)。 3.插入(1)后插结点：设p指向单链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的后面，插入示意图如图2.13。操作如下： s-next=p-next;p-next=s;注意：两个指针的操作顺序不能交换。图2.14 在*p之前插入*s spq图2.13 在*p之后插入*s p s (2)前插结点：设指向链表中某结点，指向待插入的值为x的新结点，将*s插入到*p的前面，插入示意图如图2.14，与后插不同的是：首先要找到*p的前驱*q，然后再完成在*q之后插入*s，设单链表头指针为L，操作如下：q=L;while (q-next!=p) q=q-next; /*找*p的直接前驱*/s-next=q-next; q-next=s;后插操作的时间复杂性为O(1)，前插操作因为要找 *p 的前驱，时间性能为O(n)；其实我们关心的更是数据元素之间的逻辑关系，所以仍然可以将 *s 插入到 *p 的后面，然后将-data与s-data交换即可，这样即满足了逻辑关系，也能使得时间复杂性为O(1)。 (3)插入运算 Insert_LinkList(L,i,x)算法思路：1.找到第i-1个结点；若存在继续2，否则结束2.申请、填装新结点； 3.将新结点插入。结束。算法如下：int Insert_LinkList( LinkList L, int i, datatype x) /*在单链表L的第i个位置上插入值为x的元素*/ Lnode * p,*s; p=Get_LinkList(L,i-1); /*查找第i-1个结点*/ if (p=NULL) printf(参数i错);return 0; /*第i-1个不存在不能插入*/ else s=malloc(sizeof(LNode); /*申请、填装结点*/ s-data=x; s-next=p-next; /*新结点插入在第i-1个结点的后面*/ p-next=s return 1; 算法2.12算法2.12的时间复杂度为O(n)。4. 删除 (1)删除结点：设p指向单链表中某结点，删除*p。操作示意图如图2.15所示。通过示意图可见，要实现对结点*p的图2.15 删除*p pq删除，首先要找到*p的前驱结点*q，然后完成指针的操作即可。指针的操作由下列语句实现：q-next=p-next;free(p);显然找*p前驱的时间复杂性为O(n)。若要删除*p的后继结点(假设存在)，则可以直接完成：s=p-next;p-next=s-next;free(s);该操作的时间复杂性为O(1) 。(2)删除运算：Del_LinkList(L,i)算法思路：1.找到第i-1个结点；若存在继续2，否则结束；2.若存在第i个结点则继续3，否则结束； 3.删除第i个结点，结束。算法如下：int Del_LinkList(LinkList L，int i) /*删除单链表L上的第i个数据结点*/ LinkList p,s; p=Get_LinkList(L,i-1); /*查找第i-1个结点*/ if (p=NULL) printf(第i-1个结点不存在);return -1; else if (p-next=NULL) printf(第i个结点不存在);return 0; else s=p-next; /*s指向第i个结点*/ p-next=s-next; /*从链表中删除*/ free(s); /*释放*s */ return 1; 算法2.13算法2.13的时间复杂度为O(n)。通过上面的基本操作我们得知：(1) 在单链表上插入、删除一个结点，必须知道其前驱结点。(2) 单链表不具有按序号随机访问的特点，只能从头指针开始一个个顺序进行。【例1】将单链接表反转【解析】（一）流程图如下：Xq